Understanding and Mitigating the Tradeoff Between Robustness and Accuracy

Aditi Raghunathan; Sang Michael Xie; Fanny Yang; John Duchi; Percy Liang

Source-linked AI summary

Understanding and Mitigating the Tradeoff Between Robustness and Accuracy

Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, Percy Liang

arXiv:2002.10716v2Feb 25, 2020cs.LGstat.ML

TL;DR

Adversarial training can improve robustness while worsening standard accuracy, even when the true predictor is both perfectly standard- and robust-accurate. This paper characterizes that finite-data tradeoff in linear regression, identifies inductive bias as its source, and studies RST, which removes the tradeoff theoretically and improves both errors empirically.

Problem
Adversarial training often lowers robust error but raises standard error, while prior explanations do not cover settings where an accurate and robust predictor exists.
Method
The paper analyzes minimum-norm interpolation under consistent perturbations in noiseless linear regression and uses the resulting understanding to motivate robust self-training.
Results
RST does not increase standard error while achieving the best possible robust error in noiseless linear regression, and empirically improves both errors across the evaluated CIFAR-10 perturbations.
Takeaways & Limitations
The standard–robust tradeoff can arise from mismatch between estimator inductive bias and input geometry rather than imperfect labels, and RST can eliminate it in the analyzed setting.
Takeaways & Limitations
The theoretical guarantees are stated for noiseless linear regression and RST procedures using pseudo-labels from an interpolating estimator.

Abstract

from arXiv · show

Adversarial training augments the training set with perturbations to improve the robust error (over worst-case perturbations), but it often leads to an increase in the standard error (on unperturbed test inputs). Previous explanations for this tradeoff rely on the assumption that no predictor in the hypothesis class has low standard and robust error. In this work, we precisely characterize the effect of augmentation on the standard error in linear regression when the optimal linear predictor has zero standard and robust error. In particular, we show that the standard error could increase even when the augmented perturbations have noiseless observations from the optimal linear predictor. We then prove that the recently proposed robust self-training (RST) estimator improves robust error without sacrificing standard error for noiseless linear regression. Empirically, for neural networks, we find that RST with different adversarial training methods improves both standard and robust error for random and adversarial rotations and adversarial $\ell_\infty$ perturbations in CIFAR-10.

1. Introduction

The paper explains the robustness–accuracy tradeoff as a finite-data generalization phenomenon that can persist even when accurate and robust predictors exist. It characterizes this effect through overparameterization and inductive bias, then motivates RST as a way to improve robustness without sacrificing standard accuracy.

Adversarial training reduces robust error but often increases standard error on unperturbed inputs.
Previous explanations assume either no classifier fits perturbed data accurately or the hypothesis class cannot represent the true classifier.
Even with noiseless, consistent perturbations and a true linear predictor having zero standard and robust error, augmentation can increase standard error.
The tradeoff stems from overparameterization: after invariances restrict the hypothesis class, the estimator’s inductive bias can still determine generalization.
Cubic-spline illustrations show augmentation fitting local perturbations can damage global-tail accuracy, whereas RST preserves low error on test points and perturbations.
RST regularizes augmented predictions toward a standard estimator and, in linear regression, achieves the best possible robust error without increasing standard error.

2. Setup

The setup defines standard and robust prediction errors for inputs and perturbations, then compares minimum-norm interpolants trained on standard data versus augmented data. The theoretical analysis specializes to noiseless linear regression with squared loss and population covariance Σ.

The learning problem maps inputs x ∈ X ⊆ R^d to targets y ∈ Y, with theoretical analysis using regression and empirical studies using general targets.
Standard error measures performance on unperturbed inputs, while robust error measures performance over perturbations T(x).
Consistent perturbations preserve the conditional target distribution and can include rotations, flips, brightness changes, ℓ_p perturbations, or synonym replacements.
The theoretical model is noiseless linear regression with y = x^Tθ⋆, squared loss, and population covariance Σ = E_Px[xx^T].
The analysis focuses on interpolating estimators in highly overparameterized models, especially minimum-Euclidean-norm solutions.
The standard estimator interpolates standard data, whereas the augmented estimator interpolates standard data together with extra perturbed examples.

3. Analysis in the linear regression setting

In noiseless linear regression, augmentation can increase standard error despite perfectly consistent perturbation labels, because minimum-norm interpolation reallocates parameter error across covariance-weighted directions. The paper characterizes this effect and identifies conditions, inductive-bias effects, and complexity requirements governing when the increase occurs.

Setup: The analysis compares minimum-norm estimators trained on standard data alone versus standard data augmented with consistent extra points.The standard estimator fits Xstd, while the augmented estimator additionally fits Xext; the analysis focuses on standard error before revisiting robust error.
3.1. Simple illustrative problem: In the 3-D example, adding a constraint along e1 + e2 can increase parameter error along e2, although the augmented estimator still fits the original training point.Depending on θ⋆, the augmented error along e2 can be larger or smaller than the standard estimator’s zero error in that direction.
3.1. Simple illustrative problem: The population covariance Σ weights parameter-error directions differently, so errors in heavily weighted directions contribute more to standard error.For diagonal Σ, the ratio between eigenvalues determines which error components matter most; when λ2 ≫ λ1, increased e2 error can dominate.
3.2. General characterizations: Theorem 1 decomposes the standard-error change into a positive fitting benefit v⊤Σv and a potentially negative cross-term 2w⊤Σv representing error increases in other directions.The augmented estimator has higher standard error when the covariance-weighted cost outweighs the benefit.
3.2. General characterizations: Sufficient conditions preventing increased standard error include identity covariance, full span of augmented and standard data, or a single extra point aligned with an eigenvector of Σ.Under Σ = I, the norm minimized by interpolation matches the norm governing standard error, giving the estimators the stated matching inductive bias.
3.2. General characterizations: A large augmentation-induced increase in standard error requires the true parameter to be sufficiently more complex in ℓ2 norm than the standard estimator.The spline example illustrates this through a complex staircase function versus a simpler linear interpolant; local components can be fit at the expense of global structure.

4. Robust self-training

Robust self-training combines labeled and unlabeled data to regularize robust estimators toward standard estimators. In noiseless linear regression, this eliminates the standard–robust error tradeoff, while CIFAR-10 experiments show improvements across perturbations and training methods.

Robust self-training for linear regression: RST rewrites the unlabeled-data objective as a Σ-induced distance to the standard estimator, while enforcing robust consistency constraints.
General formulation of RST: RST performs standard training on labeled data, then robust training on labeled data together with unlabeled inputs.
General formulation of RST: RST minimizes a weighted combination of four losses, including standard and robust losses on labeled and unlabeled data.
Robust self-training for linear regression: In noiseless linear regression, RST never has larger standard error than the standard estimator and achieves robust error equal to its standard error.
Empirical evaluation of RST: RST+AT and RST+TRADES have lower robust and standard error than supervised AT and TRADES across all tested perturbation types.
Empirical evaluation of RST: For spatial transformations, RST further improves standard error by almost 1% and robust error by 2-3% over standard and robust estimators.
Empirical evaluation of RST: Both standard and robust unlabeled-data losses are necessary: standard self-training has approximately 100% robust error, while robust consistency training hurts standard error.

5. Related Work

Related work explains the robustness–accuracy tradeoff through either incompatible targets, insufficient hypothesis classes, or finite-data generalization. This paper instead studies mitigation theoretically and empirically, with RST as the central method.

Existence of a tradeoff: Several prior explanations assume that no classifier is simultaneously accurate and robust, or that the hypothesis class cannot represent the true classifier.
Existence of a tradeoff: Min et al. distinguish strong-adversary settings with an infinite-data tradeoff from weak-adversary settings where the gap eventually decreases.
Mitigating the tradeoff: Unlike concurrent work restricted to simulated validation, this paper studies how to mitigate the finite-data tradeoff.
Mitigating the tradeoff: The paper presents RST as the first theoretically studied method for eliminating the tradeoff in noiseless linear regression and evaluates it across perturbations and training algorithms.
Mitigating the tradeoff: IAT uses Mixup and NAS searches for robust architectures, so RST, IAT, and NAS are incomparable because they target different standard–robust tradeoffs.

6. Conclusion

Consistent perturbation augmentation can increase standard error even in noiseless linear regression with a true predictor achieving zero standard and robust error. The analysis attributes this to inductive-bias mismatch under overparameterization and motivates robust self-training as a remedy.

Consistent, perfectly labeled perturbations can increase standard error despite zero standard and robust error for the true linear predictor.The setting is noiseless linear regression with augmentation samples consistent with the true conditional distribution.
The tradeoff arises when overparameterized estimation uses an inductive bias mismatched with the input distribution.The paper emphasizes that restricting the hypothesis class through invariances does not remove the issue if overparameterization remains.
Robust self-training uses an input-distribution-aware regularizer to eliminate the standard–robust error tradeoff in linear regression.The procedure estimates the input distribution from additional unlabeled data.
The general minimum-norm formulation extends beyond Euclidean norm because positive definite matrix norms can be handled through rotations.The paper presents ℓ2 ridgeless regression for simplicity while retaining the broader Mahalanobis-norm result.

B.4. Proof of Corollary 1

Corollary 1 identifies sufficient conditions ensuring augmentation does not increase standard error. These include isotropic population covariance, no augmented nullspace component, and an eigenvector condition.

Corollary 1 gives three sufficient conditions under which augmentation does not increase standard error.
Isotropic population covariance Σ = I guarantees the standard-error comparison is favorable.
If the augmented nullspace projection Π⊥aug = 0, the relevant vector in Theorem 1 vanishes.
The eigenvector condition is established by analyzing augmentation with a single extra point.

B.5. Proof of Proposition 1

The proof characterizes when augmentation can increase standard error through interactions between augmentation-induced directions and the population covariance. A single augmentation is safe for all true predictors only along covariance eigenvectors; mixed eigendirections can be harmful.

Proposition 1: A standard-error increase is possible exactly when suitable directions in the augmented nullspace satisfy the covariance interaction condition.The construction then produces a true parameter θ⋆ for which the augmented estimator has larger standard error.
Proposition 1: The required true predictor must be sufficiently more complex than a good standard solution, with a lower bound on norm difference.The bound depends on the original and augmentation data.
Corollary 2: For a single augmentation, directions aligned with covariance eigenvectors do not increase standard error for any θ⋆.
Corollary 2: A mixture of covariance eigenvectors with different eigenvalues admits a θ⋆ for which augmentation increases standard error.The mechanism reflects inhomogeneous scaling and rotation by the population covariance.
Spline illustration: The spline illustration shows that local augmentation can damage extrapolation by changing its direction, while augmentation on the linear set leaves bias unchanged.

C.4. Data augmentation can be quite painful for splines

A staircase-spline construction shows that consistent augmentation can make the augmented estimator’s standard error grow while the standard estimator’s error vanishes. The section also presents robust self-training as a finite basis construction for population robustness constraints.

Data augmentation can be quite painful for splines: The simplified staircase setting makes augmented standard error grow while standard-estimator error decays to zero.
Data augmentation can be quite painful for splines: The standard-error ratio between augmented and standard estimators diverges as the number of stairs s tends to infinity.At the same time, R(θ̂std) tends to zero.
Data augmentation can be quite painful for splines: The augmented spline extrapolates with zero derivative beyond the largest observed stair, producing large errors on later stairs.
Robust self-training algorithm: Robust self-training summarizes infinitely many population perturbations with a basis spanning the perturbation space.This avoids naive augmentation with infinitely many points.
Robust self-training algorithm: The iterative construction terminates within O(d) iterations when no new non-invariant perturbation direction remains.

D.2. Proof of Theorem 2

The proof establishes that RST matches robust and standard error in noiseless linear regression, then describes its general estimator and neural-network evaluation settings.

Theorem 2 assumes a noiseless linear model and an arbitrary interpolant of the standard data.
The proof represents the RST estimator using orthogonal bases for null spaces associated with standard and augmented data.The construction introduces operators and vectors that decompose the difference between a standard interpolant and the RST estimator.
Fitting at most d basis vectors spanning the adversarial directions makes the robustness constraint equal to zero.This yields agreement between the estimator’s predictions on clean inputs and their allowed adversarial perturbations.
RST achieves equal robust and standard error, attaining the lowest possible robust error while maintaining perfect consistency.
The general RST estimator combines standard and robust losses on labeled and unlabeled data; PG-AT uses multiclass logistic loss for the standard objective.Adversarial examples are obtained in practice with projected gradient steps, while TRADES uses a KL-divergence-based robust loss.
The neural-network experiments evaluate RST with adversarial perturbations, adversarial rotations, and random rotations.

E.2.1. SUBSAMPLING CIFAR-10

The CIFAR-10 subsampling experiments compare adversarial training with RST across dataset sizes, finding robust-accuracy gains while avoiding the standard-error penalty.

RST uses 500k unlabeled Tiny Images examples while comparing its standard error with an augmented estimator.
The experiments train Wide ResNet 40-2 models on CIFAR-10 subsamples and average results over two trials per subsampling factor.Models are trained for 200 epochs and attain almost 100% standard and robust training accuracy.
5-15% percentage points: RST improves robust accuracy above PGD-trained robust models for all subsamples, including the full dataset.Robustness is evaluated with a 40-step, 5-restart PGD attack.
Adversarial augmentation increases standard error even at ϵ = 2/255, whereas RST is reported to fix this issue.The experiments use a smaller model and therefore a smaller perturbation size than existing baselines.
Up to 20% better standard error: RST and adversarially augmented estimators outperform the standard model on small CIFAR-10 subsamples.
Table 1 evaluates RST with PGD and TRADES on full CIFAR-10, including models trained with 500k unlabeled Tiny Images examples.Rotation and translation experiments use grids of rotations up to 30 degrees and translations of approximately 10% of image size.

F. Comparison to standard self-training algorithms

RST is framed as a robustness-aware extension of self-training that uses standard-model pseudo-labels while enforcing behavior on augmented unlabeled data.

RST regularizes an augmented estimator to produce labels close to a standard estimator on unlabeled data.
RST generalizes self-training to data augmentation and robustness by generating pseudo-labels with a standard, non-augmented estimator.Classical self-training instead uses all labeled data to generate pseudo-labels.
The comparison uses full-CIFAR-10 models at ϵ = 2/255, with robust test accuracy of the standard model near 0%.
RST differs from robust consistency training by generating pseudo-labels through standard training rather than enforcing only prediction consistency across perturbations.

G. Minimum ℓ1-norm problem where data augmentation hurts standard error

A constructed minimum-ℓ1-norm example shows that consistent data augmentation can worsen standard error despite a perfect linear predictor, and that the gap can grow with dimension and sample size.

The construction demonstrates that augmentation can increase standard error for minimum-ℓ1-norm estimators, not only minimum-Mahalanobis-norm estimators.
The three-dimensional setup uses three feature vectors, an all-ones optimal predictor, and consistent perturbations that preserve the optimal labels.The optimal predictor gives x⊤θ⋆ = 2 + δ for every possible input.
When all n training samples equal x1, standard and augmented minimum-norm estimators can select different sparse solutions.The augmented estimator fits the added consistent perturbation, changing which coordinates carry the solution.
The augmented estimator can incur squared error (2 + δ)^2 on x3, while the standard estimator fits x3 perfectly but has high error on x2.The discrepancy is attributed to augmentation-driven changes in the sparsity pattern under the ℓ1 inductive bias.
In the repeated 3-dimensional construction, the difference between augmented and standard errors grows without bound as d, n →∞.
Conditioned on the all-x1 event, the standard errors are ϵd^2(2 + δ)^2 and (p − ϵ)d^2(2 + δ)^2 for the standard and augmented estimators, respectively.The event occurs with probability (1 − p)^n + (p − ϵ)^n.