Technical Summary: On the existence of consistent adversarial attacks in high-dimensional linear classification

Problem Statement

This work investigates the fundamental distinction between consistent (or proper) and inconsistent (or improper) adversarial attacks in the context of high-dimensional binary classification. While standard adversarial robustness literature often treats all perturbations that flip model predictions as equivalent, this paper argues that a critical distinction exists:

• Consistent attacks: Perturbations that flip the model's prediction but preserve the ground-truth label (e.g., an image of a panda remains a panda to a human observer but is classified as a guacamole by the model).
• Inconsistent attacks: Perturbations that flip both the model's prediction and the ground-truth label (e.g., transforming a panda image into a genuinely different animal).

The authors posit that vulnerability to consistent attacks represents a genuine failure of the model to capture invariant features perceived by humans. Despite the prevalence of this assumption in computer vision, the mathematical properties of consistent attacks—specifically their existence, effectiveness, and interaction with overparameterization in linear classifiers—remain elusive. The paper addresses this gap by analyzing these phenomena in the high-dimensional proportional regime (where dimension $d$, features $p$, and sample size $n$ scale to infinity at fixed ratios).

Methodology

The authors employ tools from high-dimensional statistics, statistical physics, and random matrix theory to derive exact asymptotic characterizations. The analysis is conducted in two complementary settings:

1. Well-Specified Linear Models: A setting where input covariates are directly available and generated from a ground-truth linear classifier with Gaussian design.
2. Latent Space Models: A setting where the statistician observes transformed features $x = Fz + u$ (where $z$ are latent variables), allowing for the study of misspecification and overparameterization (where feature dimension $p$ differs from latent dimension $d$).

Key Technical Tools

• Novel Error Metrics: The paper defines three metrics to quantify vulnerability:
  • Robust Error ($E_{rob}$): Standard adversarial error considering all perturbations.
  • Consistent Robust Error ($E^{cns}_{rob}$): Error considering only perturbations that preserve the ground-truth label.
  • Consistent Boundary Error ($E^{cns}_{bnd}$): Error considering only perturbations that flip the prediction of already correctly classified points (isolating the vulnerability of the decision boundary).
• Geometric Analysis: The existence of consistent attacks is characterized geometrically. For a linear classifier with weights $\hat{w}$ and ground truth $w^*$, a consistent attack exists if the perturbation budget $\epsilon$ exceeds a margin defined by the distance of $\hat{w}$ to the span of $w^*$ in the dual norm space.
• Asymptotic Characterization: Using the Gaussian universality principle and the Convex Gaussian Min-Max Theorem (CGMT), the authors derive closed-form asymptotic expressions for the defined metrics. They analyze the behavior of Robust Empirical Risk Minimization (R-ERM) estimators in the limit $d, n, p \to \infty$.

Key Contributions

1. Conditions for Existence of Consistent Attacks

The authors establish necessary and sufficient conditions for the existence of consistent perturbations.

• In the well-specified case, a consistent attack exists if and only if $\epsilon \cdot d^*_{q^*}(\hat{w}_\perp) \geq |\langle \hat{w}, x \rangle|$, where $d^*_{q^*}$ is the $\ell_{q^*}$ distance to the span of the ground-truth weights.
• This reveals that consistent attacks are strictly harder to execute than inconsistent ones because the attacker is constrained to the hyperplane orthogonal to the ground-truth weights.
• Under Gaussian designs, the probability of existence is derived explicitly, showing that in high dimensions, consistent attacks become almost certain unless the predictor is perfectly aligned with the ground truth.

2. Asymptotic Formulas for Consistent Metrics

The paper provides exact asymptotic formulas for $E^{cns}_{rob}$ and $E^{cns}_{bnd}$ in both well-specified and latent space models.

• The limiting behavior depends on the overlap between the learned weights and the ground truth, as well as the geometry of the attack (norm $q$).
• The analysis reveals that consistent errors are generally lower than inconsistent errors for the same attack strength, confirming that the constraint of label preservation limits the attacker's power.

3. The Role of Overparameterization

A central contribution is the nuanced analysis of how overparameterization (specifically in latent space models where $p > d$) affects consistent robustness.

• Dual Effect: The paper finds that overparameterization has opposing effects depending on the metric:
  • Boundary Vulnerability ($E^{cns}_{bnd}$): Increases with overparameterization. Correctly classified points become more susceptible to consistent attacks as the model becomes more flexible.
  • Overall Consistent Robustness ($E^{cns}_{rob}$): Decreases (improves) with overparameterization. This is because overparameterization significantly improves "clean" generalization (reducing the number of initially misclassified points), which compensates for the increased boundary vulnerability.
• This finding challenges the conventional wisdom that overparameterization universally degrades adversarial robustness, suggesting instead that it can improve overall performance metrics even if specific subsets of data become more fragile.

4. Robust Training Analysis

The authors characterize the performance of Robust Empirical Risk Minimization (R-ERM) in these settings. They derive self-consistent equations for the sufficient statistics of the robust estimator in the latent space model. Results indicate that while robust training mitigates consistent attacks, the optimal level of overparameterization depends on the data availability ($\alpha = n/d$).

Results

• Vulnerability Patterns: Consistent attacks are less effective than inconsistent ones, but their existence probability approaches 1 in high dimensions unless the model is perfectly aligned with the ground truth.
• Scaling Laws: The probability of a consistent attack existing scales with the dimension and the attack geometry ($q$). For $q > 1$, the probability is almost surely 1 for random predictors in high dimensions.
• Overparameterization Trade-off: In latent space models, increasing the feature dimension $p$ (overparameterization) leads to a decrease in the overall consistent robust error ($E^{cns}_{rob}$) due to better clean generalization, despite an increase in the boundary error ($E^{cns}_{bnd}$).
• Robust Training: Robust training effectively reduces all error metrics, but the rate of improvement varies. The consistent robust error decreases faster with sample size than the standard robust error, suggesting robust training learns representations particularly effective against proper attacks.

Significance and Claims

The authors claim that their work provides the first rigorous, exact asymptotic characterization of consistent adversarial attacks in high-dimensional linear settings. The significance of these findings lies in:

1. Refining the Understanding of Robustness: By distinguishing between consistent and inconsistent attacks, the paper clarifies that model sensitivity to adversarial examples is not a monolithic property.
2. Re-evaluating Overparameterization: The results offer a theoretical explanation for contradictory empirical observations regarding overparameterization and robustness. The paper argues that overparameterization should not be viewed solely as detrimental to robustness; rather, it can improve overall metrics by correcting misclassifications, even if it makes the decision boundary more fragile.
3. Guidance for System Design: The exact formulas provide theoretical guidance for selecting regularization parameters and attack budgets during robust training, emphasizing the importance of the consistent/inconsistent distinction when evaluating model robustness.

The paper concludes that while overparameterization increases vulnerability on specific subsets of inputs (correctly classified points), the net effect on overall robustness can be positive, offering a more nuanced perspective for designing robust machine learning systems.