mlsanityData to 7 Oct 2026

From inexact optimization to learning via gradient concentration

arXiv 2106.05397 ↗First posted 9 Jun 2021stat.ML cs.LG math.OCcited by 4

Not on the map. Why?

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.

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

Builds on

28 of 54 references.

References · 28

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  4. 2016A vector-contraction inequality for Rademacher complexitiescited by 141
  5. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  6. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  7. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  8. 2017Implicit Regularization in Deep Learningcited by 90
  9. 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 86
  10. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  11. 2016Optimal Rates For Regularization Of Statistical Inverse Learning Problemscited by 68
  12. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
16 more
  1. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  2. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  3. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  4. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  5. 2017Early stopping for kernel boosting algorithms: A general analysis with localized complexitiescited by 27
  6. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  7. 2020The Statistical Complexity of Early-Stopped Mirror Descentcited by 19
  8. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  9. 2020Analyzing the discrepancy principle for kernelized spectral filter learning algorithmscited by 15
  10. 2018Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descentcited by 14
  11. 2019Implicit Regularization of Accelerated Methods in Hilbert Spacescited by 14
  12. 2015Iterative Regularization for Learning with Convex Loss Functionscited by 9
  13. 2016Convergence rates of Kernel Conjugate Gradient for random design regressioncited by 8
  14. 2017Efficient learning with robust gradient descentcited by 6
  15. 2020On lower bounds for the bias-variance trade-offcited by 6
  16. 2017Don't relax: early stopping for convex regularizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 1; 2024: 0; 2025: 0; 2026: 1.

4 papers.

  1. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  2. 2023How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descentcited by 10
  3. 2022Iterative regularization in classification via hinge loss diagonal descentcited by 0
  4. 2026Self-Regularized Learning Methodscited by 0