{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T22:55:27Z","timestamp":1771973727245,"version":"3.50.1"},"reference-count":0,"publisher":"Association for the Advancement of Artificial Intelligence (AAAI)","issue":"01","license":[{"start":{"date-parts":[[2019,7,17]],"date-time":"2019-07-17T00:00:00Z","timestamp":1563321600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.aaai.org"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AAAI"],"abstract":"<jats:p>Many modern machine learning classifiers are shown to be vulnerable to adversarial perturbations of the instances. Despite a massive amount of work focusing on making classifiers robust, the task seems quite challenging. In this work, through a theoretical study, we investigate the adversarial risk and robustness of classifiers and draw a connection to the well-known phenomenon of \u201cconcentration of measure\u201d in metric measure spaces. We show that if the metric probability space of the test instance is concentrated, any classifier with some initial constant error is inherently vulnerable to adversarial perturbations.One class of concentrated metric probability spaces are the so-called L\u00e9vy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most O(\u221an) to make it misclassified, where n is the data dimension. Using our general result about L\u00e9vy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more L\u00e9vy families are known (e.g., product distribution under the Hamming distance) for which we immediately obtain new attacks that find adversarial examples of distance O(\u221an).Finally, we show that concentration of measure for product spaces implies the existence of forms of \u201cpoisoning\u201d attacks in which the adversary tampers with the training data with the goal of degrading the classifier. In particular, we show that for any learning algorithm that uses m training examples, there is an adversary who can increase the probability of any \u201cbad property\u201d (e.g., failing on a particular test instance) that initially happens with non-negligible probability to \u2248 1 by substituting only \u00d5e(\u221am) of the examples with other (still correctly labeled) examples.<\/jats:p>","DOI":"10.1609\/aaai.v33i01.33014536","type":"journal-article","created":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T07:40:09Z","timestamp":1567410009000},"page":"4536-4543","source":"Crossref","is-referenced-by-count":42,"title":["The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure"],"prefix":"10.1609","volume":"33","author":[{"given":"Saeed","family":"Mahloujifar","sequence":"first","affiliation":[]},{"given":"Dimitrios I.","family":"Diochnos","sequence":"additional","affiliation":[]},{"given":"Mohammad","family":"Mahmoody","sequence":"additional","affiliation":[]}],"member":"9382","published-online":{"date-parts":[[2019,7,17]]},"container-title":["Proceedings of the AAAI Conference on Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/4373\/4251","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/download\/4373\/4251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T06:35:47Z","timestamp":1667802947000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/4373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,17]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,7,23]]}},"URL":"https:\/\/doi.org\/10.1609\/aaai.v33i01.33014536","relation":{},"ISSN":["2374-3468","2159-5399"],"issn-type":[{"value":"2374-3468","type":"electronic"},{"value":"2159-5399","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7,17]]}}}