Journal
MATHEMATICAL PROGRAMMING
Volume 195, Issue 1-2, Pages 693-734Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-021-01710-6
Keywords
Stochastic gradient descent; Nonconvex; Stopping criteria; Strong convergence
Categories
Funding
- Wisconsin Alumni Research Foundation
Ask authors/readers for more resources
This work introduces two stopping criteria for SGD that can be applied to nonconvex functions, addresses the issue of heuristic stopping criteria for SGD methods, and proves the convergence of gradient function evaluated at SGD's iterates to zero for Bottou-Curtis-Nocedal functions.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available