# Stopping Criteria for, and Strong Convergence of, Stochastic Gradient Descent on Bottou-Curtis-Nocedal Functions

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

## Key facts

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

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

- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [Global Convergence and Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2110.01663/) (2021)
- [On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks](https://mlsanity.com/paper/2112.09684/) (2021)
- [A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions](https://mlsanity.com/paper/2108.04620/) (2021)
- [A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2104.00277/) (2021)
- [Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation](https://mlsanity.com/paper/2108.08106/) (2021)
- [Convergence proof for stochastic gradient descent in the training of deep neural networks with ReLU activation for constant target functions](https://mlsanity.com/paper/2112.07369/) (2021)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)
- [Distributed Stochastic Optimization under a General Variance Condition](https://mlsanity.com/paper/2301.12677/) (2023)
- [A Retrospective Approximation Approach for Smooth Stochastic Optimization](https://mlsanity.com/paper/2103.04392/) (2021)
- [Dynamic Decoupling of Placid Terminal Attractor-based Gradient Descent Algorithm](https://mlsanity.com/paper/2409.06542/) (2024)
- [GradES: Significantly Faster Training in Transformers with Gradient-Based Early Stopping](https://mlsanity.com/paper/2509.01842/) (2025)

## Abstract (arXiv)

Stopping criteria for Stochastic Gradient Descent (SGD) methods play important roles from enabling adaptive step size schemes to providing rigor for downstream analyses such as asymptotic inference. Unfortunately, current stopping criteria for SGD methods are often heuristics that rely on asymptotic normality results or convergence to stationary distributions, which may fail to exist for nonconvex functions and, thereby, limit the applicability of such stopping criteria. To address this issue, in this work, we rigorously develop two stopping criteria for SGD that can be applied to a broad class of nonconvex functions, which we term Bottou-Curtis-Nocedal functions. Moreover, as a prerequisite for developing these stopping criteria, we prove that the gradient function evaluated at SGD's iterates converges strongly to zero for Bottou-Curtis-Nocedal functions, which addresses an open question in the SGD literature. As a result of our work, our rigorously developed stopping criteria can be used to develop new adaptive step size schemes or bolster other downstream analyses for nonconvex functions.