# Optimal Rates for Robust Stochastic Convex Optimization

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

## Key facts

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

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

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [Optimal Robust Linear Regression in Nearly Linear Time](https://mlsanity.com/paper/2007.08137/) (2020)
- [Robust Regression Revisited: Acceleration and Improved Estimation Rates](https://mlsanity.com/paper/2106.11938/) (2021)
- [Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing](https://mlsanity.com/paper/2403.10547/) (2024)

## Abstract (arXiv)

Machine learning algorithms in high-dimensional settings are highly susceptible to the influence of even a small fraction of structured outliers, making robust optimization techniques essential. In particular, within the ε-contamination model, where an adversary can inspect and replace up to an ε-fraction of the samples, a fundamental open problem is determining the optimal rates for robust stochastic convex optimization (SCO) under such contamination. We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the ε-contamination model. Our approach improves over existing algorithms, which are not only suboptimal but also require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions. By contrast, our optimal algorithms do not require these stringent assumptions, assuming only population-level smoothness of the loss. Moreover, our algorithms can be adapted to handle the case in which the covariance parameter is unknown, and can be extended to nonsmooth population risks via convolutional smoothing. We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.