Research map / Adversarial robustness and security / Certified and empirical robustness
The Price of Implicit Bias in Adversarially Robust Generalization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how implicit bias of optimization (steepest descent choice and diagonal-network parameterization) shapes robust generalization of linear and neural models under l_inf adversarial perturbations, showing the induced bias can help or hurt robust generalization.
Problem
Robust ERM (adversarial training) generalizes poorly, with large robust generalization gaps; it is unclear which implicit regularization (from optimizer or architecture) suits a given perturbation set.
Approach
Characterizes steepest descent in robust ERM for linear models: under (epsilon,p)-separable data, the iterates converge in direction to the min l_r-norm robust separator, so choosing the optimizer's norm matters; also shows diagonal linear networks trained by GD in robust ERM are biased toward min l_1 solutions in predictor space, unlike linear models (min l_2). Combines with margin-based robust R
Key results
- On synthetic dense-dense data with l_inf perturbations, GD and coordinate descent generalize similarly in ERM but robust generalization gap differs by over 20% for small training sets in robust ERM.
- On MNIST (2 vs 7) with 1-hidden-layer ReLU nets at epsilon=0.2, sign descent outperforms gradient descent by 4.11% mean robust test accuracy over 3 seeds, with both reaching 100% robust train accuracy.
- Robust ERM with gradient descent on linear models converges to min l_2 robust separators, which can generalize worse than min l_1 solutions for l_inf perturbations on sparse teacher data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use coordinate descent (CD) instead of gradient descent (GD) | Linear models with a sparse teacher and dense inputs under ℓ∞ robust ERM · Synthetic data, 4-Sparse, Dense | robust generalization gap | Helped |
| Use gradient descent (GD) instead of coordinate descent (CD) | Linear models with a dense teacher and sparse inputs under ℓ∞ robust ERM · Synthetic data, Dense, k-Sparse | generalization gap | Helped |
| Increase ℓ∞ perturbation from 0 to ε*/4 | CD compared with GD on synthetic linear classification · Synthetic data | average difference in generalization gaps: 0 to \frac{\epsilon^\star}{4} | Helped |
| Increase ℓ∞ perturbation toward ε* | CD compared with GD on synthetic linear classification · Synthetic data | average difference in generalization gaps | No clear effect |
| Use sign descent (SD) instead of GD | One-hidden-layer ReLU networks trained with robust ERM · MNIST (digits 2 vs 7), ε=0.2 | robust generalization: 4.11% mean difference over 3 random seeds | Helped |
| Use sign descent (SD) instead of GD | One-hidden-layer ReLU networks trained with robust ERM · MNIST (digits 2 vs 7), ε=0.2 | robust overfitting | Helped |
| Use GD instead of SD | Convolutional neural networks trained with robust ERM · MNIST, all classes | test accuracy | Helped |
| Use GD instead of SD | Convolutional neural networks trained with robust ERM · MNIST, all classes; larger ε or fewer training samples | generalization | Helped |
| Use ℓ1 regularization instead of ℓ2 regularization | Robust linear classifiers with sparse teacher and dense inputs · ℓ∞ perturbations; k-sparse teacher, dense samples | robust generalization error | Helped |
| Use ℓ2 regularization instead of ℓ1 regularization | Robust linear classifiers with dense teacher and sparse inputs · ℓ∞ perturbations; dense teacher, k-sparse samples | robust generalization error | Helped |
| Use ℓ1 regularization instead of ℓ2 regularization as perturbation magnitude increases | Robust linear classifiers with sparse teacher and sparse inputs · ℓ∞ perturbations; k-sparse teacher and samples | robust generalization error | Helped |
| Use ℓ1 regularization instead of ℓ2 regularization | Robust linear classifiers with dense teacher and dense inputs · ℓ∞ perturbations; dense teacher and samples | robust generalization error | No clear effect |
Surprising findings
- For CNNs with bias terms, gradient descent generalizes better than sign descent despite the opposite ordering in homogeneous networks.
- Reparameterizing a linear model as a diagonal network changes the implicit bias under robust ERM, even though expressive power is identical.
Limitations
- Theoretical results for linear and diagonal models only; the neural network experiments are empirical and the implicit bias is not characterized there.
- Diagonal network result only proves convergence to a KKT point, not global optimality of the l_1 problem.
- Continuous-time steepest flow analysis rather than discrete-step algorithms.
Experimental setup
Datasets: MNIST synthetic teacher-labeled Gaussian data
Benchmarks: MNIST
Metrics: robust test accuracy robust generalization gap clean generalization gap
Baselines: gradient descent (GD) coordinate descent (CD) diagonal network gradient descent sign gradient descent (SD)
Builds on: adversarial training (robust ERM) steepest descent implicit bias margin-based Rademacher bounds for adversarial classification implicit bias of gradient descent in robust linear models
Closest papers by meaning
- The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks (NeurIPS 2023 · similarity 0.90)
- Fantastic Robustness Measures: The Secrets of Robust Generalization (NeurIPS 2023 · similarity 0.90)
- Can Implicit Bias Imply Adversarial Robustness? (ICML 2024 · similarity 0.89)
- Understanding Domain Generalization: A Noise Robustness Perspective (ICLR 2024 · similarity 0.88)
- Feature Averaging: An Implicit Bias of Gradient Descent Leading to Non-Robustness in Neural Networks (ICLR 2025 · similarity 0.88)
- The Implicit Bias of Gradient Descent toward Collaboration between Layers: A Dynamic Analysis of Multilayer Perceptions (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.