Binary Classification Under ๐“0 Attacks for General Noise Distribution

Payam Delgosha, Hamed Hassani, Ramtin PedarsaniarXiv 2022 · DOI · arXiv

TL;DR

This paper uncovers a dramatic "all-or-nothing" phase transition in adversarial robustness. For binary classification under $\ell_0$ attacks (where an attacker can change a limited number of features by any amount), the authors prove that if the attacker's budget is less than $\sqrt{d}$ (where $d$ is the number of features), the adversary can be completely neutralized. However, if the budget exceeds $\sqrt{d}$, no classifier can perform better than a random guess.

What Problem Does This Paper Address?

Most research into adversarial machine learning focuses on $\ell_2$ or $\ell_\infty$ attacks, where an attacker makes tiny, nearly invisible changes to every feature (like pixels in an image). This paper tackles the $\ell_0$ attack, which is fundamentally different: the attacker can only change a few features, but they can change them to any value they want.

This is a "sparse" attack. Imagine a malware detector that looks at 10,000 file features; an $\ell_0$ attacker might only be able to modify 10 of those features, but they can set them to extreme values to fool the system. Because $\ell_0$ constraints are combinatorial and non-convex, standard gradient-based defenses often fail. The authors seek to find the fundamental limits: how many features can an adversary corrupt before classification becomes impossible?

Methods

The authors study a high-dimensional binary classification model where data samples are generated with i.i.d. (independent and identically distributed) noise. To defend against the adversary, they propose a Truncated Classifier.

  1. Log-Likelihood Calculation: For each input coordinate, the classifier calculates the log-likelihood ratio (how much more likely the value is to come from class +1 vs class -1).
  2. Truncation: Instead of simply summing these values (which a single extreme adversarial value could easily corrupt), the classifier sorts the values and discards the top $k$ and bottom $k$ entries, where $k$ is the adversary's budget.
  3. Decision: It then sums the remaining "middle" values to make a prediction.

To prove that this is the best one can do, the authors use Optimal Transport theory and Maximal Coupling. They show that an adversary with a large enough budget can use these mathematical tools to "shift" the distribution of one class until it is statistically indistinguishable from the other.

Datasets

As a theoretical work focused on fundamental statistical limits, this paper does not use empirical datasets like ImageNet or CIFAR-10. Instead, it uses a rigorous mathematical model:

  • Generative Model: $x_i = y\mu + z_i$, where $y$ is the label, $\mu$ is the mean, and $z_i$ is noise.
  • Noise Distributions: The proofs apply to a general class of noise (the "Exponential Family"), which includes Gaussian (Normal) distributions and others with polynomial exponents.

Key Insights and Ideas

  • The $\sqrt{d}$ Threshold: The most striking insight is the "Phase Transition." In a $d$-dimensional space, the natural "noise" of the system scales with $\sqrt{d}$. If the adversary's power is less than this natural variance, they get "lost in the noise" and can be filtered out via truncation. If they exceed it, they can fundamentally alter the identity of the data point.
  • No Trade-off Zone: Unlike many areas of ML where there is a trade-off between accuracy and robustness, this paper shows that in the "sub-$\sqrt{d}$" regime, you can achieve the optimal standard error (the same error you would get if there were no attacker at all).
  • Truncation as a Universal Shield: The paper demonstrates that simple non-linear truncation is incredibly powerful against sparse attacks. By ignoring outliers, the defender effectively "deletes" the adversary's modifications without losing too much information from the clean coordinates.

Key Results

  • Achievability: If the adversary's budget $k < d^{1/2 - \epsilon}$, the proposed truncated classifier achieves the same error rate as the optimal Bayes classifier in a non-adversarial setting as $d \to \infty$.
  • Converse (The Limit): If the adversary's budget $k > d^{1/2 + \epsilon}$, the optimal robust error is at least 1/2. This means the attacker can make the data so confusing that any classifier is essentially just flipping a coin.
  • Fisher Information Connection: The authors show that the performance of the classifier in the robust regime is governed by the Fisher Information of the noise distribution, providing a bridge between adversarial robustness and classical information theory.

Limitations and Future Work

  • I.I.D. Assumption: The results rely on the assumption that noise is independent across coordinates. In real-world data (like images), pixels are highly correlated, which might change the $\sqrt{d}$ scaling.
  • Binary Focus: The paper focuses on binary classification. Extending these sharp phase transition results to multi-class problems or regression remains an open challenge.
  • Asymptotic Nature: The results are "asymptotic," meaning they hold true as the number of features $d$ becomes very large. The exact behavior for small-scale problems (low $d$) isn't explicitly mapped.
  • Known Budget: The defense assumes the defender knows (or can estimate) the adversary's budget $k$ to perform the correct amount of truncation.

Summary updated

BibTeX
@misc{delgosha2022binary,
  author = {Payam Delgosha and Hamed Hassani and Ramtin Pedarsani},
  title = {{Binary Classification Under ๐“0 Attacks for General Noise Distribution}},
  year = {2022},
  eprint = {2203.04855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.04855},
}
Figure