Source-linked AI summary
The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure
Saeed Mahloujifar, Dimitrios I. Diochnos, Mohammad Mahmoody
TL;DR
Robust classifiers remain difficult to obtain because concentrated instance spaces can make classifiers with initial error vulnerable to small adversarial changes. The paper proves concentration-based impossibility results for evasion and poisoning, including eO(√n)-scale test perturbations and eO(√m)-scale training substitutions, while noting scope boundaries for image data and offline poisoning.
Problem
The paper asks what inherent limitations defense mechanisms face against evasion and poisoning attacks, and how powerful such attacks can be.
Method
The paper conducts a theoretical study connecting concentration of measure in metric probability spaces with evasion and poisoning attacks.
Results
In normal Lévy spaces, adversarial examples can be eO(√n)-far, while poisoning can substitute eO(√m) correctly labeled training examples and raise initially non-negligible bad-event probabilities to ≈1.
Takeaways & Limitations
Concentration yields broad impossibility results for robust classification and exposes new evasion attacks for product spaces under Hamming distance.
Takeaways & Limitations
The poisoning attacks are offline, and implications for real data require a smooth generative model from a concentrated space; image-space concentration is left for future work.
Abstract
from arXiv · showhide
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 concentration of measure 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 Levy families that include many natural distributions. In this special case, our attacks only need to perturb the test instance by at most $O(\sqrt n)$ to make it misclassified, where $n$ is the data dimension. Using our general result about Levy instance spaces, we first recover as special case some of the previously proved results about the existence of adversarial examples. However, many more Levy 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(\sqrt n)$. Finally, we show that concentration of measure for product spaces implies the existence of forms of "poisoning" 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 "bad property" (e.g., failing on a particular test instance) that initially happens with non-negligible probability to $\approx 1$ by substituting only $\tilde{O}(\sqrt m)$ of the examples with other (still correctly labeled) examples.
1 Introduction
The paper connects concentration of measure with inherent vulnerabilities to both evasion and poisoning attacks. It proves broad impossibility results, including O(√n)-scale evasion attacks in normal Lévy spaces and eO(√m)-scale poisoning attacks using correctly labeled replacements.
- Core results: Concentration of measure implies that any classifier with Ω(1) initial error can be driven to risk ≈1 by a close test-instance perturbation.This establishes an inherent limitation on robust classification in concentrated metric probability spaces.
- Scope and limitations: The results have broader asymptotic scope than prior isoperimetric analyses, but with worse constants, and leave concentration studies for real image data as future work.Potential application to real data assumes a smooth generative model mapping from a concentrated space; the poisoning attacks are offline because they require the full training set.
- Core results: In normal Lévy spaces, misclassified adversarial instances can be only eO(√n)-far from the original instance when initial error is at least 1/poly(n).The result recovers prior cases including the n-sphere, isotropic n-Gaussian, and Boolean hypercube, while covering additional families.
- Extensions: The paper introduces target-error robustness, where an adversary plans average-case-bounded perturbations to reach a specified error probability.This extends the concentration-based analysis beyond worst-case perturbation bounds.
- Core results: For product spaces under Hamming distance, an adversary can cause misclassification by changing O(√n) input blocks.This extends the Boolean-hypercube case to any product space of dimension n.
- Core results: Concentration in product training spaces yields poisoning attacks that substitute eO(√m) correctly labeled examples and drive initially non-negligible bad properties to probability ≈1.The framework applies to deterministic learners and includes increasing error on a chosen test instance.
2 Preliminaries
The paper formalizes metric probability spaces, classification problems, concentration functions, and product-space concentration tools used to analyze robustness.
- Nice metric probability spaces: A nice metric probability space requires measurable set expansions and existing average distances between Borel sets.These conditions support defining adversarial risk and generalized robustness.
- Classification problems: A classification problem specifies instances, labels, a distribution, concept and hypothesis classes, and optionally a metric for perturbations.Risk is the probability that hypothesis h disagrees with concept c under the instance distribution.
- Concentration function: The concentration function measures how much a set of measure at least one-half expands under metric neighborhoods.The paper introduces this function as the central quantitative description of concentration.
- Product-space concentration: Product probability spaces under Hamming distance satisfy a concentration bound for measurable sets and their b-expansions.The result is attributed to a version of Talagrand’s product-space concentration lemma.
- Product-space concentration: McDiarmid’s inequality applies to measurable functions whose values change by at most one when a single coordinate changes.It is stated for product measures and provides another concentration tool.
3 Evasion Attacks: Finding Adversarial Examples from Concentration
The paper defines adversarial risk and robustness through error-region perturbations, then uses concentration to show that modest budgets can drive classifiers toward large error.
- Definitions: Adversarial risk is the measure of the error region after expanding it by perturbation budget b, while target-error robustness is the expected perturbation needed to reach error ρ.At b = 0, adversarial risk equals ordinary risk; full robustness corresponds to expected distance to the error region.
- General concentration results: Concentration results apply beyond Levy families because any upper bound on the concentration function can produce risk and robustness guarantees.The framework also permits bounds on target-error robustness derived from adversarial-risk bounds.
- General concentration results: If initial error exceeds the concentration function at budget b, an adversary can raise adversarial risk above one-half.The proof uses the complement of the expanded error region and the concentration property.
- General concentration results: If additional concentration conditions hold, total budget b1 + b2 yields adversarial risk at least 1 − γ.The first budget pushes risk above one-half, and the second expands the error region toward measure 1 − γ.
- Normal Levy families: In normal Levy families, constant initial error permits adversarial risk 1 − γ using O(1/√n) perturbations for any constant γ.Sub-exponential initial error permits risk 1 − exp(−o(n)) with o(1) perturbations, and full robustness is also o(1).
- Normal Levy families: Under metrics whose typical distances scale as Θ(n), the normal-Levy risk and robustness bounds scale accordingly.The paper contrasts normalized metrics with settings such as Boolean-hypercube Hamming distance.
4 Poisoning Attacks from Concentration of Product Measures
The paper defines plausible poisoning attacks that alter correctly labeled training examples and uses concentration of product spaces to show that small tampering budgets can sharply degrade learner confidence or increase chosen-instance error.
- Definitions: Poisoning adversaries replace training examples with correctly labeled examples while preserving the training-set size and can be constrained by worst-case or average Hamming tampering budgets.A plausible attack keeps every modified pair correctly labeled; its budget bounds the number of changed coordinates.
- Confidence and error: Theorem 4.5 considers deterministic learners whose original confidence is defined for achieving error at most ε.The theorem analyzes how an adversary changes confidence for a fixed concept and sample size.
- Confidence degradation: For any γ, a plausible adversary can reduce confidence using a tampering budget bounded by a concentration-dependent expression, including a bound involving −ln(δ · γ) · m.The result applies to poisoning attacks against deterministic learning algorithms and is proved using a concentration claim for product distributions.
- Attack construction: The attacks target training sets near those producing a bad event, then leave other training sets unchanged, while remaining plausible and within the tampering budget.The construction uses Hamming neighborhoods of bad training sets and concentration bounds to control the average number of substitutions.
- Generalization: The proof extends to any bad property of a deterministically produced hypothesis, and to bad events defined directly over training data for randomized learning rules.The bad property need not be classification error specifically.
- Chosen-instance error: For a chosen test instance, plausible attacks can drive the adversarial error to 1, while asymptotically eO(√m) tampering can amplify initially inverse-polynomial bad probabilities to near certainty.The section also states sublinear tampering regimes for subexponential initial confidence or error probabilities.
A Risk and Robustness Based on Hypothesis’s Prediction Change
This section separates adversarial properties based on changing a classifier’s prediction from those based on entering its error region, then bounds prediction-change risk and robustness using concentration functions.
- Prediction-change risk: Prediction-change adversarial properties concern perturbations that change h(x), independently of whether the original prediction matches the ground-truth label.This contrasts with error-region definitions that require misclassification relative to the concept function.
- Concentration framework: The paper uses concentration functions to derive bounds on prediction-change risk and robustness for hypotheses over concentrated metric probability spaces.The same concentration-based proof framework can be applied to different concentration bounds, including those for Lévy families.
- Definitions: The setup treats a classification problem as nice when the relevant hypothesis-label preimages are measurable, including under a trivial constant concept class.The prediction-change quantities are defined for hypothesis regions hℓ = {x ∈ X | h(x) = ℓ}.
- Definitions: For a nonconstant hypothesis, PC risk measures the probability that a perturbation changes the prediction, while PC robustness measures the expected perturbation needed to do so.Target-label variants instead seek perturbations that produce a specified label.
- Normal Lévy families: In normal Lévy families, prediction-change risk can reach 0.99 with O(1/√n) perturbations when no label occupies more than 0.99 probability mass.If a target label has constant probability, its target-label PC risk and robustness also have O(1/√n) bounds; subexponentially large label regions yield o(1) bounds.