# Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond

arXiv: https://arxiv.org/abs/2301.13486 · HTML: https://mlsanity.com/paper/2301.13486/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 31 Jan 2023.

## Builds on (most cited first, 20 of 20)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Rademacher Complexity for Adversarially Robust Generalization](https://mlsanity.com/paper/1810.11914/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Precise Tradeoffs in Adversarial Training for Linear Regression](https://mlsanity.com/paper/2002.10477/) (2020)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [The Implicit Regularization of Stochastic Gradient Flow for Least Squares](https://mlsanity.com/paper/2003.07802/) (2020)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [Precise Statistical Analysis of Classification Accuracies for Adversarial Training](https://mlsanity.com/paper/2010.11213/) (2020)
- [The Curse of Concentration in Robust Learning: Evasion and Poisoning Attacks from Concentration of Measure](https://mlsanity.com/paper/1809.03063/) (2018)
- [The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression](https://mlsanity.com/paper/2201.05149/) (2022)
- [Provable tradeoffs in adversarially robust classification](https://mlsanity.com/paper/2006.05161/) (2020)
- [The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization](https://mlsanity.com/paper/2002.11080/) (2020)
- [Gradient Methods Provably Converge to Non-Robust Networks](https://mlsanity.com/paper/2202.04347/) (2022)
- [Adversarially Robust Estimate and Risk Analysis in Linear Regression](https://mlsanity.com/paper/2012.10278/) (2020)
- [Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes](https://mlsanity.com/paper/2106.02630/) (2021)
- [Adversarial robustness for latent models: Revisiting the robust-standard accuracies tradeoff](https://mlsanity.com/paper/2110.11950/) (2021)

## Built on by (most cited first, 4 of 4)

- [Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Norms](https://mlsanity.com/paper/2308.00556/) (2023)
- [On damage of interpolation to adversarial robustness in regression](https://mlsanity.com/paper/2601.16070/) (2026)
- [auto-fpt: Automating Free Probability Theory Calculations for Machine Learning Theory](https://mlsanity.com/paper/2504.10754/) (2025)
- [Information Hidden in Gradients of Regression with Target Noise](https://mlsanity.com/paper/2601.18546/) (2026)

## Abstract (arXiv)

In this work we study the robustness to adversarial attacks, of early-stopping strategies on gradient-descent (GD) methods for linear regression. More precisely, we show that early-stopped GD is optimally robust (up to an absolute constant) against Euclidean-norm adversarial attacks. However, we show that this strategy can be arbitrarily sub-optimal in the case of general Mahalanobis attacks. This observation is compatible with recent findings in the case of classification~citeVardi2022GradientMP that show that GD provably converges to non-robust models. To alleviate this issue, we propose to apply instead a GD scheme on a transformation of the data adapted to the attack. This data transformation amounts to apply feature-depending learning rates and we show that this modified GD is able to handle any Mahalanobis attack, as well as more general attacks under some conditions. Unfortunately, choosing such adapted transformations can be hard for general attacks. To the rescue, we design a simple and tractable estimator whose adversarial risk is optimal up to within a multiplicative constant of 1.1124 in the population regime, and works for any norm.