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

2024/10/11 by George Yin, Vikram Krishnamurthy, Yin, George +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Neural Networks and Applications #Sparse and Compressive Sensing Techniques #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2410.08449

openalex publication_date 2024/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• A weak convergence approach to large deviations for stochastic approximations
• What is the long-run distribution of stochastic gradient descent? A large deviations analysis
• Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent
• The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations