An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias

Abstract

Structured non-convex learning problems, for which critical points have favorable statistical properties, arise frequently in statistical machine learning. Algorithmic convergence and statistical estimation rates are well-understood for such problems. However, quantifying the uncertainty associated with the underlying training algorithm is not well-studied in the non-convex setting. In order to address this shortcoming, in this work, we establish an asymptotic normality result for the constant step size stochastic gradient descent (SGD) algorithm--a widely used algorithm in practice. Specifically, based on the relationship between SGD and Markov Chains [DDB19], we show that the average of SGD iterates is asymptotically normally distributed around the expected value of their unique invariant distribution, as long as the non-convex and non-smooth objective function satisfies a dissipativity property. We also characterize the bias between this expected value and the critical points of the objective function under various local regularity conditions. Together, the above two results could be leveraged to construct confidence intervals for non-convex problems that are trained using the SGD algorithm.

References in corpus (15)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• The Randomized Midpoint Method for Log-Concave Sampling
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• On the Łojasiewicz Exponent of the Quadratic Sphere Constrained Optimization Problem
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Error Lower Bounds of Constant Step-size Stochastic Gradient Descent

Cited by in corpus (8)

• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
• Learning Curves for SGD on Structured Features
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization
• Bootstrapping the error of Oja's algorithm