# Exponential convergence of testing error for stochastic gradient methods

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Dec 2017.

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

- [Phenomenology of Double Descent in Finite-Width Neural Networks](https://mlsanity.com/paper/2203.07337/) (2022)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [On the Benefits of Large Learning Rates for Kernel Methods](https://mlsanity.com/paper/2202.13733/) (2022)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Multiclass learning with margin: exponential rates with no bias-variance trade-off](https://mlsanity.com/paper/2202.01773/) (2022)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [A Case of Exponential Convergence Rates for SVM](https://mlsanity.com/paper/2205.10055/) (2022)
- [Active Labeling: Streaming Stochastic Gradients](https://mlsanity.com/paper/2205.13255/) (2022)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)
- [Binary Classification with Instance and Label Dependent Label Noise](https://mlsanity.com/paper/2306.03402/) (2023)
- [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)

## Abstract (arXiv)

We consider binary classification problems with positive definite kernels and square loss, and study the convergence rates of stochastic gradient methods. We show that while the excess testing loss (squared loss) converges slowly to zero as the number of observations (and thus iterations) goes to infinity, the testing error (classification error) converges exponentially fast if low-noise conditions are assumed.