Stochastic Subgradient Method Converges on Tame Functions

By Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, Jason D. Lee. Foundations of Computational Mathematics, 2018

324 citations recorded by the source corpus.

This work considers the question: what convergence guarantees does the stochastic subgradient method have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. In particular, this work endows the stochastic subgradient method, and its proximal extension, with rigorous convergence guarantees for a wide class of problems arising in data science—including all popular deep learning architectures.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/1a3a683a24c819e6f2da5e85a3b52817378ca43b

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 Statistics and Probability

Citations in the corpus

Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “…W p h q r i, j s in the network we can compute t p W p h q r i, j sq 2 “ 2 W p h q r i, j s ¨ p h q r i,j s d t “ ´ 2 W p h q r i, j s ¨ B p q B W p h q r i B W p h q r i,j s , using the sharp chain rule of diﬀerential inclusions for tame functions [Drusvyatskiy et al., 2015, Davis et al., 2018].”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, background): “2), feedforward neural networks with arbitrary number of layers of arbitrary dimensions, with activations such as sigmoid, ReLU, leaky ReLU, tanh, softplus (and many others), with a loss function such as lp norm, hinge loss, logistic loss or cross entropy (and many others), belong to this class of s”
A Subsampling Line-Search Method with Second-Order Results (2018, background): “We point out that many state-of-the-art first-order optimization algorithms do not enjoy convergence theory for nonsmooth nonconvex objectives either, and only standard diminishing stepsize stochastic subgradient methods [30, 20] or ones with a simple momentum term [28] enjoy asymptotic convergence ”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, methodology): “As shown in [Davis et al., 2019], the output of almost every neural network admits a chain rule (as long as the neural network is composed by deﬁnable pieces in an o-minimal structure, e.g., ReLU, sigmoid, LeakyReLU).”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “(6)Strictly speaking, this should be differential inclusion (Davis et al., 2018)”
ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring for Minimax Problems and GANs (2019, unknown): “[14] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D.”
Analysis of nonsmooth stochastic approximation: the differential inclusion approach (2018, background): “Specifically, it is assumed in [19] that if z : R+ →R d is a solution of the differential inclusion ż(t) ∈−∂̄ f (z(t)) and z(0) 6∈S (i.”