# Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 3 Oct 2024.

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

- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [Out-of-sample error estimate for robust M-estimators with convex penalty](https://mlsanity.com/paper/2008.11840/) (2020)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning](https://mlsanity.com/paper/2107.05143/) (2021)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [A non-asymptotic distributional theory of approximate message passing for sparse and robust regression](https://mlsanity.com/paper/2401.03923/) (2024)
- [Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing](https://mlsanity.com/paper/2402.01599/) (2024)
- [Failures and Successes of Cross-Validation for Early-Stopped Gradient Descent](https://mlsanity.com/paper/2402.16793/) (2024)
- [Noise Covariance Estimation in Multi-Task High-dimensional Linear Models](https://mlsanity.com/paper/2206.07256/) (2022)
- [Uncertainty quantification for iterative algorithms in linear models with application to early stopping](https://mlsanity.com/paper/2404.17856/) (2024)

## Abstract (arXiv)

This paper studies the generalization performance of iterates obtained by Gradient Descent (GD), Stochastic Gradient Descent (SGD) and their proximal variants in high-dimensional robust regression problems. The number of features is comparable to the sample size and errors may be heavy-tailed. We introduce estimators that precisely track the generalization error of the iterates along the trajectory of the iterative algorithm. These estimators are provably consistent under suitable conditions. The results are illustrated through several examples, including Huber regression, pseudo-Huber regression, and their penalized variants with non-smooth regularizer. We provide explicit generalization error estimates for iterates generated from GD and SGD, or from proximal SGD in the presence of a non-smooth regularizer. The proposed risk estimates serve as effective proxies for the actual generalization error, allowing us to determine the optimal stopping iteration that minimizes the generalization error. Extensive simulations confirm the effectiveness of the proposed generalization error estimates.