The Implicit Regularization of Stochastic Gradient Flow for Least Squares

Abstract

We study the implicit regularization of mini-batch stochastic gradient descent, when applied to the fundamental problem of least squares regression. We leverage a continuous-time stochastic differential equation having the same moments as stochastic gradient descent, which we call stochastic gradient flow. We give a bound on the excess risk of stochastic gradient flow at time $t$, over ridge regression with tuning parameter $\lambda =1/t$. The bound may be computed from explicit constants (e.g., the mini-batch size, step size, number of iterations), revealing precisely how these quantities drive the excess risk. Numerical examples show the bound can be small, indicating a tight relationship between the two estimators. We give a similar result relating the coefficients of stochastic gradient flow and ridge. These results hold under no conditions on the data matrix $X$, and across the entire optimization path (not just at convergence).

arXiv commentICML 2020

References in corpus (38)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• One weird trick for parallelizing convolutional neural networks
• Don't Decay the Learning Rate, Increase the Batch Size
• Large Batch Training of Convolutional Networks
• A mathematical theory of semantic development in deep neural networks
• Three Factors Influencing Minima in SGD
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• On exponential convergence of SGD in non-convex over-parametrized learning
• Gradient methods for convex minimization: better rates under weaker conditions
• SGD on Neural Networks Learns Functions of Increasing Complexity
• Optimal Rates for Multi-pass Stochastic Gradient Methods
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• Theory of Deep Learning IIb: Optimization Properties of SGD
• Asynchronous stochastic convex optimization
• An Alternative View: When Does SGD Escape Local Minima?
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Implicit Regularization for Optimal Sparse Recovery
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• On the diffusion approximation of nonconvex stochastic gradient descent
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Theoretical Issues in Deep Networks: Approximation, Optimization and Generalization
• Iterate averaging as regularization for stochastic gradient descent
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
• A Continuous-Time View of Early Stopping for Least Squares
• Constant Step Size Stochastic Gradient Descent for Probabilistic Modeling
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Implementing regularization implicitly via approximate eigenvector computation
• Semi-groups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations

Cited by in corpus (17)

• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• The Heavy-Tail Phenomenon in SGD
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Noisy Recurrent Neural Networks
• Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
• The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion
• Implicit Gradient Regularization
• Stochastic gradient descent with random learning rate
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• Implicit bias of deep linear networks in the large learning rate phase
• RATT: Leveraging Unlabeled Data to Guarantee Generalization
• Implicit Regularization in Tensor Factorization
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• Robust Generalization of Quadratic Neural Networks via Function Identification
• The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models
• On Computability, Learnability and Extractability of Finite State Machines from Recurrent Neural Networks
• Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?