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

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