Convergence rates for the stochastic gradient descent method for non-convex objective functions

We prove the local convergence to minima and estimates on the rate of convergence for the stochastic gradient descent method in the case of not necessarily globally convex nor contracting objective functions. In particular, the results are applicable to simple objective functions arising in machine learning.

math.NA cs.LG math.PR stat.ML Computer Science Mathematics

View graph Source

Paper

References (72)

01Gradient descent optimizes over-parameterized deep ReLU networksDifan Zou, Yuanbin Cao, Dongruo Zhou et al.2019 · Machine-mediated learning · 290 citations

02Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient AssumptionsYunwen Lei, Ting Hu, Guiying Li et al.2019 · IEEE Transactions on Neural Networks and Learning Systems · 145 citations In Library

03Gradient Descent Finds Global Minima of Deep Neural NetworksS. Du, J. Lee, Haochuan Li et al.2018 · International Conference on Machine Learning · 1.3k citations In Library

04Gradient Descent Provably Optimizes Over-parameterized Neural NetworksS. Du, Xiyu Zhai, B. Póczos et al.2018 · International Conference on Learning Representations · 1.4k citations In Library

05A Convergence Theory for Deep Learning via Over-ParameterizationZeyuan Allen-Zhu, Yuanzhi Li, Zhao Song2018 · International Conference on Machine Learning · 1.7k citations In Library

06Stochastic Nested Variance Reduction for Nonconvex OptimizationDongruo Zhou, Pan Xu, Quanquan Gu2018 · Journal of machine learning research · 168 citations In Library

07Neural Tangent Kernel: Convergence and Generalization in Neural NetworksArthur Jacot, Franck Gabriel, Clément Hongler2018 · Neural Information Processing Systems · 4.2k citations In Library

08AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initializationRachel A. Ward, Xiaoxia Wu, L. Bottou2018 · International Conference on Machine Learning · 453 citations In Library

09On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal TransportLénaïc Chizat, F. Bach2018 · Neural Information Processing Systems · 859 citations In Library

10On the Convergence of Stochastic Gradient Descent with Adaptive StepsizesXiaoyun Li, Francesco Orabona2018 · International Conference on Artificial Intelligence and Statistics · 345 citations In Library

11Neural Networks as Interacting Particle Systems: Asymptotic Convexity of the Loss Landscape and Universal Scaling of the Approximation ErrorGrant M. Rotskoff, E. Vanden-Eijnden2018 · arXiv.org · 216 citations

12Strong error analysis for stochastic gradient descent optimization algorithmsArnulf Jentzen, Benno Kuckuck, Ariel Neufeld et al.2018 · IMA Journal of Numerical Analysis · 60 citations In Library

Scroll for more · 38 remaining

Similar papers

A Local Convergence Theory for the Stochastic Gradient Descent Method in Non-Convex Optimization With Non-isolated Local MinimaTaehee Ko, Xiantao Li2022 · arXiv (Cornell University) · 2 citations In Library

Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized OptimizationMichael R. Metel, Akiko Takeda2019 · International Conference on Machine Learning · 23 citations In Library

Almost sure convergence of randomised‐difference descent algorithm for stochastic convex optimisationXiaoxue Geng, Gao Huang, Wenxiao Zhao2021 · IET Control Theory and Applications In Library

Accelerated and Unaccelerated Stochastic Gradient Descent in Model GeneralityDarina Dvinskikh, Alexander Tyurin, Alexander Gasnikov et al.2020 · Mathematical Notes In Library

Accelerated Almost-Sure Convergence Rates for Nonconvex Stochastic Gradient Descent using Stochastic Learning RatesTheodoros Mamalis, Dušan M. Stipanović, Petros G. Voulgaris2021 · arXiv (Cornell University) · 2 citations In Library

Linear Convergence of Accelerated Stochastic Gradient Descent for Nonconvex Nonsmooth OptimizationFeihu Huang, Songcan Chen2017 · arXiv.org · 2 citations In Library

Convergence rate analysis of the gradient descent–ascent method for convex–concave saddle-point problemsMoslem Zamani, Hadi Abbaszadehpeivasti, Etienne de Klerk2024 · Optimization methods & software · 0 citations In Library

Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and ApplicationsRajeeva Laxman Karandikar, M. Vidyasagar2024 · Journal of Optimization Theory and Applications In Library

Learning Rates for Stochastic Gradient Descent With Nonconvex ObjectivesYunwen Lei, Ke Tang2021 · IEEE Transactions on Pattern Analysis and Machine Intelligence · 38 citations In Library

Accelerated and nonaccelerated stochastic gradient descent with model conceptionDarina Dvinskikh, Alexander Tyurin, Alexander Gasnikov et al.2020 · arXiv (Cornell University) · 5 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal