Finite Sample and Large Deviations Analysis of Stochastic Gradient Algorithm with Correlated Noise

We analyze the finite sample regret of a decreasing step size stochastic gradient algorithm. We assume correlated noise and use a perturbed Lyapunov function as a systematic approach for the analysis. Finally we analyze the escape time of the iterates using large deviations theory.

cs.LG eess.SY Neural Networks and Applications Advanced Numerical Analysis Techniques Sparse and Compressive Sensing Techniques

View graph Source

Paper

Similar papers

On the diffusion approximation of nonconvex stochastic gradient descentC. Li, Lei Li, Junyang Qian et al.2017 · arXiv.org · 24 citations In Library

First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient NoiseT. H. Nguyen, Umut Simsekli, M. Gürbüzbalaban et al.2019 · Neural Information Processing Systems · 81 citations In Library

Second-order Properties of Noisy Distributed Gradient DescentLei Qin, Michael Cantoni, Ye Pu2023 · arXiv (Cornell University) · 3 citations In Library

Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling DistributionsAlexandre Défossez, F. Bach2014 · International Conference on Artificial Intelligence and Statistics · 14 citations In Library

Stochastic Gradient Descent in Correlated Settings: A Study on Gaussian ProcessesHao Chen, Lili Zheng, Raed Al Kontar et al.2020 · Neural Information Processing Systems In Library

Non asymptotic analysis of Adaptive stochastic gradient algorithms and applicationsAntoine Godichon‐Baggioni, Pierre Tarrago2023 · arXiv (Cornell University) In Library

Variance Reduction for Stochastic Gradient Generalized Non-reversible Langevin Monte Carlo AlgorithmsBingye Ni, Xiaoyu Wang, Yingli Wang et al.2026 · 0 citations In Library

Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential PrivacyAnastasia Koloskova, Ryan M. McKenna, Zachary Charles et al.2023 · arXiv (Cornell University) · 22 citations In Library

Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear ModelRaphaël Berthier, Francis Bach, Pierre Gaillard2020 · arXiv (Cornell University) · 48 citations In Library

Singular-limit analysis of gradient descent with noise injectionAnna Shalova, André Schlichting, M. Peletier2024 · arXiv.org · 6 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