Stochastic subgradient method converges on tame functions
From MaRDI portal
Abstract: 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.
Recommendations
- Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
- Stochastic subgradient method for quasi-convex optimization problems
- scientific article; zbMATH DE number 3887445
- Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
- A multistep stochastic ϵ-subgradient method of minimizing a convex function
- scientific article; zbMATH DE number 5221408
- Subdifferential Convergence in Stochastic Programs
- A note on the convergence of subgradient optimization methods
- Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization
- Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity
Cites work
- A function not constant on a connected set of critical points
- A Stochastic Approximation Method
- A vector forward mode of automatic differentiation for generalized derivative evaluation
- An introduction to measure theory
- An Invitation to Tame Optimization
- Asymptotic convergence of nonlinear contraction semigroups in Hilbert space
- Clarke Subgradients of Stratifiable Functions
- Critical values of set-valued maps with stratifiable graphs. Extensions of Sard and Smale-Sard theorems
- Curves of descent
- Evaluating an element of the Clarke generalized Jacobian of a composite piecewise differentiable function
- Generalized Gradients and Applications
- Geometric categories and o-minimal structures
- scientific article; zbMATH DE number 5348356 (Why is no real title available?)
- scientific article; zbMATH DE number 3724209 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 46303 (Why is no real title available?)
- scientific article; zbMATH DE number 1113627 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 3398324 (Why is no real title available?)
- Introduction to the theory of differential inclusions
- Lipschitz functions with maximal Clarke subdifferentials are generic
- Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic Approximations and Differential Inclusions
- Stochastic Approximations and Differential Inclusions, Part II: Applications
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic Methods for Composite and Weakly Convex Optimization Problems
- Stochastic model-based minimization of weakly convex functions
- Variational Analysis
- Variational analysis of regular mappings. Theory and applications
Cited in
(78)- Stochastic proximal gradient methods for nonconvex problems in Hilbert spaces
- Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning
- Incremental without replacement sampling in nonconvex optimization
- Stochastic generalized gradient methods for training nonconvex nonsmooth neural networks
- A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs
- Stopping criteria for, and strong convergence of, stochastic gradient descent on Bottou-Curtis-Nocedal functions
- Perturbed iterate SGD for Lipschitz continuous loss functions
- Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem
- Convergence of constant step stochastic gradient descent for non-smooth non-convex functions
- A framework for differential calculus on persistence barcodes
- Generalized gradients in dynamic optimization, optimal control, and machine learning problems
- Discussion of: ``Nonparametric regression using deep neural networks with ReLU activation function
- Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization
- Determination of convex functions via subgradients of minimal norm
- A forward-backward dynamical approach for nonsmooth problems with block structure coupled by a smooth function
- Conservative and semismooth derivatives are equivalent for semialgebraic maps
- Stochastic proximal subgradient descent oscillates in the vicinity of its accumulation set
- Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
- Stochastic model-based minimization of weakly convex functions
- A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization
- Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
- The structure of conservative gradient fields
- Graphical convergence of subgradients in nonconvex optimization and learning
- Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
- Pathological subgradient dynamics
- Multicomposite nonconvex optimization for training deep neural networks
- Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization
- Stochastic approximation for optimization in shape spaces
- Complete dictionary learning via ^4-norm maximization over the orthogonal group
- An inertial Newton algorithm for deep learning
- Manifold sampling for optimizing nonsmooth nonconvex compositions
- Every Local Minimum Value Is the Global Minimum Value of Induced Model in Nonconvex Machine Learning
- Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
- Examples of Pathological Dynamics of the Subgradient Method for Lipschitz Path-Differentiable Functions
- A gradient sampling algorithm for stratified maps with applications to topological data analysis
- Global convergence of the gradient method for functions definable in o-minimal structures
- Lyapunov stability of the subgradient method with constant step size
- Subgradient Sampling for Nonsmooth Nonconvex Minimization
- An Improved Unconstrained Approach for Bilevel Optimization
- Stochastic approximation with discontinuous dynamics, differential inclusions, and applications
- Certifying the Absence of Spurious Local Minima at Infinity
- Sufficient Conditions for Instability of the Subgradient Method with Constant Step Size
- Conservative parametric optimality and the ridge method for tame min-max problems
- First-order methods for convex optimization
- A Decomposition Algorithm for Two-Stage Stochastic Programs with Nonconvex Recourse Functions
- Nonsmooth nonconvex stochastic heavy ball
- Convergence properties of stochastic proximal subgradient method in solving a class of composite optimization problems with cardinality regularizer
- Long term dynamics of the subgradient method for Lipschitz path differentiable functions
- Stochastic algorithms with geometric step decay converge linearly on sharp functions
- Global stability of first-order methods for coercive tame functions
- Asymptotic normality and optimality in nonsmooth stochastic approximation
- Stochastic subgradient descent escapes active strict saddles on weakly convex functions
- No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
- Structure learning for continuous time Bayesian networks via penalized likelihood
- On the existence of minimizers in shallow residual ReLU neural network optimization landscapes
- Gradient descent provably escapes saddle points in the training of shallow ReLU networks
- Convergence properties of proximal (sub)gradient methods without convexity or smoothness of any of the functions
- Robust neural Lyapunov control for nonlinear systems with quadratically bounded disturbances
- Closed-loop performance optimization of model predictive control with robustness guarantees
- A new random reshuffling method for nonsmooth nonconvex finite-sum optimization
- On squared-variable formulations
- Constrained approximate optimal transport maps
- Stochastic Bregman subgradient methods for nonsmooth nonconvex optimization problems
- On the existence of optimal shallow feedforward networks with ReLU activation
- On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
- Quantifier elimination for normal cone computations
- An ADMM approach of a nonconvex and nonsmooth optimization model for low-light or inhomogeneous image segmentation
- A local nearly linearly convergent first-order method for nonsmooth functions with quadratic growth
- Statistical inference of constrained stochastic optimization via sketched sequential quadratic programming
- A constraint dissolving approach for nonsmooth optimization over the Stiefel manifold
- Properties of discrete sliced Wasserstein losses
- Learning-rate-free momentum SGD with reshuffling converges in nonsmooth nonconvex optimization
- Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
- A minimization approach for minimax optimization with coupled constraints
- Convergence of gradient descent for learning linear neural networks
- The gradient's limit of a definable family of functions admits a variational stratification
- Non-convergence to global minimizers in data driven supervised deep learning: Adam and stochastic gradient descent optimization provably fail to converge to global minimizers in the training of deep neural networks with ReLU activation
- A normal map-based proximal stochastic gradient method: convergence and identification properties
This page was built for publication: Stochastic subgradient method converges on tame functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291732)
