Source-linked AI summary
Stochastic subgradient method converges on tame functions
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, Jason D. Lee
TL;DR
The paper addresses the lack of convergence guarantees for stochastic subgradient methods on nonsmooth, nonconvex objectives. It uses differential-inclusion and chain-rule arguments for locally Lipschitz functions with Whitney-stratifiable graphs, proving stationary limit points and extending the result to proximal methods.
Problem
Convergence behavior of stochastic subgradient methods remains largely not understood for nonsmooth, nonconvex functions, including objectives for nonsmooth deep networks.
Method
The paper combines a Lyapunov-type differential-inclusion analysis with Whitney stratification, whose chain rule yields descent along subgradient trajectories.
Results
Every limit point lies in the stationary set for the analyzed stochastic method, and the guarantees apply to semialgebraic and more generally Whitney-stratifiable locally Lipschitz functions.
Takeaways & Limitations
The results provide rigorous convergence guarantees for stochastic subgradient methods on definable deep networks and for proximal extensions without convexity assumptions on f, g, or X.
Takeaways & Limitations
The guarantees require structural and technical conditions, including the descent property along differential-inclusion trajectories and, for proximal settings, boundedness conditions checked for each algorithm.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether stochastic subgradient methods converge on nonsmooth, nonconvex functions and gives positive guarantees for locally Lipschitz functions with Whitney-stratifiable graphs. These guarantees cover semialgebraic objectives, popular nonsmooth deep networks, and proximal extensions without convexity assumptions.
- Motivation: The stochastic subgradient method’s convergence remains largely unknown for nonsmooth, nonconvex functions, despite its use in TensorFlow and PyTorch.Prior guarantees cover convex, smooth, and weakly convex settings but not even simple non-pathological examples or nonsmooth neural networks.
- Contribution: The paper assumes that f strictly decreases along differential-inclusion trajectories from noncritical points, enabling almost-sure convergence of every stochastic-method limit point to a critical point.The analysis uses a Lyapunov-type argument and supports direct extensions to proximal variants.
- Function class: Whitney stratifiability of the graph guarantees the chain rule along absolutely continuous curves and consequently the descent condition along subgradient trajectories.Semialgebraic functions form an important subclass of Whitney stratifiable functions.
- Function class: Definable nonsmooth deep networks built from pieces such as quadratics, hinge losses, and log-exp functions receive rigorous stochastic subgradient convergence guarantees.The conclusion follows because compositions of definable functions remain definable.
- Proximal extension: The proximal stochastic subgradient extension has subsequential convergence guarantees for locally Lipschitz f and g over arbitrary closed X, without convexity assumptions on f, g, or X.The proximal setting combines the paper’s techniques with prior results and includes constrained problems.
2 Preliminaries
The preliminaries establish notation for curves, set-valued maps, and the Clarke subdifferential used to analyze nonsmooth dynamics.
- Absolutely continuous curves admit an integrable velocity representation, with the velocity equal to the derivative almost everywhere.
- A set-valued map assigns each x a subset of the target space.
- For locally Lipschitz functions, the Clarke subdifferential is outer-semicontinuous and compact, convex, and nonempty valued.
- A point is Clarke critical when 0 belongs to its Clarke subdifferential.
3 Differential inclusions and discrete approximations
This section develops a framework showing that noisy, vanishing-step discrete iterations asymptotically track differential-inclusion trajectories and converge subsequentially to equilibria under a Lyapunov condition.
- The discrete recursion uses step sizes, approximate evaluations of a set-valued map, and error terms to track a differential inclusion.
- Assumption A requires limit-point feasibility, bounded approximate evaluations, square-summable but nonsummable step sizes, controlled noise, and asymptotic map consistency.
- Theorem 3.1 states that shifted interpolated paths are relatively compact, and their limit points are trajectories of the differential inclusion.
- Assumption B combines a weak Sard property with descent of a lower-bounded continuous Lyapunov function along non-equilibrium trajectories.
- Under Assumptions A and B, every limit point lies in G^-1(0), while the Lyapunov values of the iterates converge.
- The proof uses a non-escape argument, vanishing successive increments, and convergence of the continuous Lyapunov values.
4 Subgradient dynamical system
The general differential-inclusion framework is specialized to stochastic subgradient dynamics, yielding almost-sure subsequential convergence under stochastic approximation and Lyapunov assumptions.
- The stochastic subgradient method is treated as a stochastic approximation process with G = −∂f, alongside a stochastic proximal extension.
- Assumption C imposes standard step-size and noise conditions that ensure the stochastic iteration satisfies the abstract approximation framework almost surely.
- Martingale arguments establish convergence of the weighted noise process, supporting asymptotic tracking of a differential-inclusion trajectory.
- Assumption D uses f itself as Lyapunov function, requiring dense noncritical values and descent along trajectories starting away from critical points.
- Under Assumptions C and D, almost surely every limit point of the stochastic subgradient iterates is critical for f, and the function values converge.
5 Verifying the descent condition
The section identifies chain rules as sufficient for descent along continuous subgradient trajectories, then establishes them for subdifferentially regular and Whitney stratifiable functions. These properties yield almost-sure subsequential convergence of stochastic subgradient iterates under the stated assumptions.
- Chain rule and descent: A chain rule makes the function value decrease along differential-inclusion trajectories, establishing the descent property needed for convergence.The argument combines the chain rule with the equality between trajectory speed and subgradient distance.
- Subdifferentially regular functions: Subdifferentially regular functions admit a chain rule and therefore satisfy the required descent condition.This class excludes downward-facing cusps, so it does not include several simple nonsmooth examples.
- Subdifferentially regular functions: For the stochastic subgradient method, every limit point is critical almost surely and the function values converge under Assumption C.The same subsequential guarantee is also stated for the broader stochastic approximation process under Assumption A with G = −∂f.
- Whitney stratifiable functions: Whitney stratifiability supplies a broader geometric class: it gives a chain rule, while stratified Sard ensures the critical values have zero measure.Together these results establish both descent-related properties required by the main convergence theorem.
- Whitney stratifiable functions: For locally Lipschitz C^d-stratifiable functions, every stochastic subgradient limit point is critical almost surely and the function values converge.The paper obtains this corollary by combining the general convergence theorems with the stratifiability results.
A corollary for deep learning
The paper applies definability to recursively constructed nonsmooth neural networks. Under the standing stochastic-subgradient assumptions, their iterates have critical limit points almost surely and convergent loss values.
- Definable network construction: Definable pieces compose into definable nonsmooth deep networks, including architectures using ReLU, quadratic, hinge, and SoftPlus functions.The stated consequences cover convolutional, recurrent, and feed-forward networks.
- Definable network construction: The network model uses linear parameterized maps, coordinatewise definable activations, and a definable loss function.Examples include logistic, hinge, absolute deviation, and square losses.
- Convergence guarantee: For the resulting empirical loss, stochastic subgradient iterates have critical limit points almost surely and convergent function values under standing Assumption C.Criticality is expressed as 0 ∈ ∂f(w∗).
6 Proximal extensions
The paper extends its unconstrained convergence framework to proximal stochastic subgradient methods for composite problems with a closed constraint set. Under assumptions E and F, limit points are composite critical and objective values converge almost surely.
- Algorithm and assumptions: The composite problem uses locally Lipschitz f and g over a closed set X, with assumptions controlling regularity, noise, and proximal minimization.Assumption F contains weak Sard and descent conditions for the associated differential inclusion.
- Algorithm and assumptions: The proximal extension combines a stochastic subgradient oracle for f with a measurable selection of the proximity map for g + δ_X.The map may be set-valued because convexity is not imposed on g or X.
- Algorithm and assumptions: Convex, globally Lipschitz, or coercive locally Lipschitz regularizers satisfy the relevant condition on g.This provides three sufficient classes for the proximal regularizer assumption.
- Convergence guarantees: Under Assumptions E and F, every proximal stochastic-subgradient limit point is composite critical almost surely and the function values converge.The result applies to the composite objective ϕ.
- Convergence guarantees: Definability of f, g, and X yields the same proximal convergence guarantee through the o-minimal framework.The conclusion is stated for every limit point and the sequence of objective values.
- Boundedness of iterates: A coercive regularizer can also ensure bounded iterates when the stochastic oracle grows no faster than L(1 + ∥x∥^ν) with ν < β − 1.The boundedness theorem assumes X = R^d and the regularizer condition in Assumption G.
A Proofs for the proximal extension
The appendix sets up the proximal extension using the history of the stochastic process and standard variational-analysis normal cones. These definitions support the proximal convergence arguments but do not themselves state an additional convergence result.
- Stochastic-process notation: The proximal analysis tracks iterates and sampled oracle variables through the filtration generated by the algorithm’s history.The notation defines x_k, ω_k, and the associated sigma algebra F_k.
- Normal-cone constructions: The appendix reviews proximal, limiting, and Clarke normal cones for the closed constraint set X.The Clarke normal cone is the construction used in the composite differential inclusion.
A.1 Auxiliary lemmas
The auxiliary lemmas establish proximal-step bounds and show that weighted stochastic subgradient noise vanishes almost surely under summability conditions.
- Proximal-step bound: Lemma A.1 bounds the proximal update using local Lipschitz behavior and the stochastic vector norm.The proof applies the proximal-map optimality inequality before dividing by the step-size-dependent term.
- Noise control: Lemma A.2 shows that βkζ(zk, ω) converges to zero almost surely for bounded zk when the nonnegative sequence βk satisfies a finite-square-sum condition.Boundedness of zk makes p(zk) bounded, enabling the summability argument.
- Noise control: Standard measure-theoretic results imply Xk converges to zero almost surely.
- Noise control: Lemma A.3 concludes that αk∥ζ(xk, ωk)∥ tends to zero almost surely.The argument combines convergence of the centered weighted noise with a conditional-expectation bound.
A.2 Proof Theorem 6.2
The proof verifies the assumptions needed for Theorem 3.2 by controlling proximal iterates and stochastic noise, then concludes the required theorem is valid.
- Assumption verification: The composite stochastic method is represented by G = −∂f −∂g−NX, and Assumption F is identified with Assumption B for this map.Properties A.1 and A.3 hold vacuously, so the proof focuses on A.2, A.4, and A.5.
- Noise sequence: The centered proximal noise sequence ξk is defined by subtracting the expected proximal update from the sampled proximal update.The method is written in proximal stochastic subgradient form before introducing the weighted noise sequence.
- Noise sequence: Lemma A.5 establishes the required weighted-noise limit by treating {αkξk} as an L2 martingale difference sequence.The proof uses conditional zero mean, a variance bound, boundedness of L(xk) and p(xk), and martingale convergence.
- Iterate boundedness: Almost surely, the iterates {yk} are bounded, with the proof relying on bounded {xk}, local Lipschitzness of g, the proximal bound, and Jensen’s inequality.
A.3 Verifying Assumption F for composite problems
For composite problems, the proof verifies the chain-rule and descent properties of Assumption F and establishes its weak Sard property using Whitney stratification.
- Descent property: Along an absolutely continuous arc satisfying ż(t) ∈ −G(z(t)), the method yields ∥ż(t)∥ = dist(0; G(z(t))) almost everywhere and equation (6.6).The chain rules for f, g, and the normal cone provide the preceding identities.
- Descent property: If the initial point is not composite critical, equation (6.6) implies strict decrease over every positive time interval.Equality of the endpoint value would force zero velocity almost everywhere and hence a constant arc.
- Definable composite problems: For definable f, g, and X, the chain rule and descent property follow from o-minimal definability and the cited structural theorem.
- Weak Sard property: Whitney stratification embeds the composite subdifferential and normal-cone terms into smooth stratum gradients and normal spaces.On each stratum, the resulting smooth restriction is used with Sard’s theorem to establish the weak Sard property.