# From inexact optimization to learning via gradient concentration

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 54 references that are in the map.
- First posted on arXiv 9 Jun 2021.

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

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [Early stopping and non-parametric regression: An optimal data-dependent stopping rule](https://mlsanity.com/paper/1306.3574/) (2013)
- [Robust Estimation via Robust Gradient Estimation](https://mlsanity.com/paper/1802.06485/) (2018)
- [Optimal Rates For Regularization Of Statistical Inverse Learning Problems](https://mlsanity.com/paper/1604.04054/) (2016)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Uniform Convergence of Gradients for Non-Convex Learning and Optimization](https://mlsanity.com/paper/1810.11059/) (2018)
- [Early stopping for kernel boosting algorithms: A general analysis with localized complexities](https://mlsanity.com/paper/1707.01543/) (2017)
- [Beating SGD Saturation with Tail-Averaging and Minibatching](https://mlsanity.com/paper/1902.08668/) (2019)
- [The Statistical Complexity of Early-Stopped Mirror Descent](https://mlsanity.com/paper/2002.00189/) (2020)
- [Generalization Properties and Implicit Regularization for Multiple Passes SGM](https://mlsanity.com/paper/1605.08375/) (2016)
- [Analyzing the discrepancy principle for kernelized spectral filter learning algorithms](https://mlsanity.com/paper/2004.08436/) (2020)
- [Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent](https://mlsanity.com/paper/1809.06958/) (2018)
- [Implicit Regularization of Accelerated Methods in Hilbert Spaces](https://mlsanity.com/paper/1905.13000/) (2019)
- [Iterative Regularization for Learning with Convex Loss Functions](https://mlsanity.com/paper/1503.08985/) (2015)
- [Convergence rates of Kernel Conjugate Gradient for random design regression](https://mlsanity.com/paper/1607.02387/) (2016)
- [Efficient learning with robust gradient descent](https://mlsanity.com/paper/1706.00182/) (2017)
- [On lower bounds for the bias-variance trade-off](https://mlsanity.com/paper/2006.00278/) (2020)
- [Don't relax: early stopping for convex regularization](https://mlsanity.com/paper/1707.05422/) (2017)

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

- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descent](https://mlsanity.com/paper/2309.08044/) (2023)
- [Iterative regularization in classification via hinge loss diagonal descent](https://mlsanity.com/paper/2212.12675/) (2022)
- [Self-Regularized Learning Methods](https://mlsanity.com/paper/2603.17160/) (2026)

## Abstract (arXiv)

Optimization in machine learning typically deals with the minimization of empirical objectives defined by training data. However, the ultimate goal of learning is to minimize the error on future data (test error), for which the training data provides only partial information. In this view, the optimization problems that are practically feasible are based on inexact quantities that are stochastic in nature. In this paper, we show how probabilistic results, specifically gradient concentration, can be combined with results from inexact optimization to derive sharp test error guarantees. By considering unconstrained objectives we highlight the implicit regularization properties of optimization for learning.