Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization

By Navid Azizan, Babak Hassibi. 2018

73 citations recorded by the source corpus.

Stochastic descent methods (of the gradient and mirror varieties) have become increasingly popular in optimization. In fact, it is now widely recognized that the success of deep learning is not only due to the special deep architecture of the models, but also due to the behavior of the stochastic descent methods used, which play a key role in reaching "good" solutions that generalize well to unseen data. In an attempt to shed some light on why this is the case, we revisit some minimax properties of stochastic gradient descent (SGD) for the square loss of linear models---originally developed in the 1990's---and extend them to general stochastic mirror descent (SMD) algorithms for general loss functions and nonlinear models. In particular, we show that there is a fundamental identity which holds for SMD (and SGD) under very general conditions, and which implies the minimax optimality of SMD (and SGD) for sufficiently small step size, and for a general class of loss functions and general nonlinear models. We further show that this identity can be used to naturally establish other properties of SMD (and SGD), namely convergence and implicit regularization for over-parameterized linear models (in what is now being called the "interpolating regime"), some of which have been shown in certain cases in prior literature. We also argue how this identity can be used in the so-called "highly over-parameterized" nonlinear setting (where the number of parameters far exceeds the number of data points) to provide insights into why SMD (and SGD) may have similar convergence and implicit regularization properties for deep learning.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares (2022, neutral): “are many parameter vectors in the vicinity of the current solution that perfectly fit the new datapoint [1], [2], [12].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, methodology): “The following result characterizes the solution that SMD converges to, in the linear overparameterized setting [5, 13].”
Π-ORFit: One-Pass Learning with Bregman Projection (2024, background): “The global optimality induced by the local geometry of the fitting process resembles the implicit regularization of mirror descent studied in [4], [5].”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, result): “To the best of our knowledge, all existing results are with constant stepsize (Section 5, Dragomir et al., 2021; Azizan & Hassibi, 2019), or with conditions on the initialization of parameters Azizan et al. (2019).”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, background): “(2019); Bartlett et al. (2019). See also Frénay et al. (2014); Shen and Sanghavi (2018); Menon et al.”
On the distance between two neural networks and the stability of learning (2020, background): “This framework was studied in relation to deep learning [21, 22], but it is still unclear whether there is a Bregman divergence that models the compositional structure of neural networks.”