Stochastic model-based minimization of weakly convex functions
From MaRDI portal
Abstract: We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate . As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss-Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set.
Recommendations
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
- Stochastic subgradient method converges on tame functions
- A zeroth order method for stochastic weakly convex optimization
- Random gradient-free minimization of convex functions
Cites work
- A geometric analysis of phase retrieval
- A proximal method for composite minimization
- A Stochastic Approximation Method
- Amenable functions in optimization
- AN OLD‐NEW CONCEPT OF CONVEX RISK MEASURES: THE OPTIMIZED CERTAINTY EQUIVALENT
- Angular synchronization by eigenvectors and semidefinite programming
- Asymptotic and finite-sample properties of estimators based on stochastic gradients
- Block stochastic gradient iteration for convex and nonconvex optimization
- Convex Analysis
- Descent methods for composite nondifferentiable optimization problems
- Dictionary Learning for Stereo Image Representation
- Efficient online and batch learning using forward backward splitting
- Ergodic convergence of a stochastic proximal point algorithm
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
- Expected Utility, Penalty Functions, and Duality in Stochastic Nonlinear Programming
- First-order methods of smooth convex optimization with inexact oracle
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1113627 (Why is no real title available?)
- Katyusha: the first direct acceleration of stochastic gradient methods
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- On proximal subgradient splitting method for minimizing the sum of two nonsmooth convex functions
- Phase retrieval via Wirtinger flow: theory and algorithms
- Phase retrieval: stability and recovery guarantees
- Prox-regular functions in variational analysis
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- Proximité et dualité dans un espace hilbertien
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust principal component analysis?
- Robust Stochastic Approximation Approach to Stochastic Programming
- Self-calibration and biconvex compressive sensing
- Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
- Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic model-based minimization of weakly convex functions
- The nonsmooth landscape of phase retrieval
- The Proximal Robbins–Monro Method
- Universal gradient methods for convex optimization problems
- Variational Analysis
- Variational analysis of spectral functions simplified
Cited in
(only showing first 100 items - show all)- Projected semi-stochastic gradient descent method with mini-batch scheme under weak strong convexity assumption
- An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity
- Variable smoothing for weakly convex composite functions
- Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
- Stochastic proximal splitting algorithm for composite minimization
- A zeroth order method for stochastic weakly convex optimization
- Stochastic generalized gradient methods for training nonconvex nonsmooth neural networks
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces
- Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization
- Perturbed iterate SGD for Lipschitz continuous loss functions
- Distributed stochastic nonsmooth nonconvex optimization
- Provably training overparameterized neural network classifiers with non-convex constraints
- Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization
- Proximal methods avoid active strict saddles of weakly convex functions
- Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
- A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization
- A stochastic subgradient method for distributionally robust non-convex and non-smooth learning
- Sub-linear convergence of a stochastic proximal iteration method in Hilbert space
- Stochastic AUC optimization with general loss
- Primal-dual block-proximal splitting for a class of non-convex problems
- Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria
- Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization
- Stochastic subgradient method converges on tame functions
- Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
- On the computation of equilibria in monotone and potential stochastic hierarchical games
- Stochastic model-based minimization of weakly convex functions
- A Stochastic Subgradient Method for Nonsmooth Nonconvex Multilevel Composition Optimization
- scientific article; zbMATH DE number 7370566 (Why is no real title available?)
- Ghost penalties in nonconvex constrained optimization: diminishing stepsizes and iteration complexity
- Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
- A study of convex convex-composite functions via infimal convolution with applications
- Weakly-convex-concave min-max optimization: provable algorithms and applications in machine learning
- scientific article; zbMATH DE number 7625199 (Why is no real title available?)
- Zeroth-order stochastic compositional algorithms for risk-aware learning
- Stochastic multilevel composition optimization algorithms with level-independent convergence rates
- Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
- Graphical convergence of subgradients in nonconvex optimization and learning
- Sublinear convergence of a tamed stochastic gradient descent method in Hilbert space
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Multicomposite nonconvex optimization for training deep neural networks
- New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization
- An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems
- The importance of better models in stochastic optimization
- A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization
- Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
- Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
- Accelerate stochastic subgradient method by leveraging local growth condition
- Distributed stochastic inertial-accelerated methods with delayed derivatives for nonconvex problems
- Stochastic difference-of-convex-functions algorithms for nonconvex programming
- Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
- Hybrid SGD algorithms to solve stochastic composite optimization problems with application in sparse portfolio selection problems
- A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
- Nonconvex optimization with inertial proximal stochastic variance reduction gradient
- A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization
- Learning with risks based on M-location
- Conditions for linear convergence of the gradient method for non-convex optimization
- The landscape of the proximal point method for nonconvex-nonconcave minimax optimization
- Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods
- Radial duality. II: Applications and algorithms
- Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization
- On Proximal Algorithms with Inertial Effects Beyond Monotonicity
- Optimal Convergence Rates for the Proximal Bundle Method
- Consistent approximations in composite optimization
- Alternating Proximal-Gradient Steps for (Stochastic) Nonconvex-Concave Minimax Problems
- Algorithms with gradient clipping for stochastic optimization with heavy-tailed noise
- Recent Theoretical Advances in Non-Convex Optimization
- A semismooth Newton stochastic proximal point algorithm with variance reduction
- Global solutions to nonconvex problems by evolution of Hamilton-Jacobi PDEs
- Complexity-optimal and parameter-free first-order methods for finding stationary points of composite optimization problems
- Stochastic algorithms with geometric step decay converge linearly on sharp functions
- A functional model method for nonconvex nonsmooth conditional stochastic optimization
- No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
- Efficient algorithms for implementing incremental proximal-point methods
- High probability bounds on AdaGrad for constrained weakly convex optimization
- Convergence properties of proximal (sub)gradient methods without convexity or smoothness of any of the functions
- Stochastic optimization over proximally smooth sets
- Derivative-free stochastic bilevel optimization for inverse problems
- Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods
- Policy gradient algorithms for robust MDPs with nonrectangular uncertainty sets
- Inexact zeroth-order nonsmooth and nonconvex stochastic composite optimization and applications
- Outlier-robust nonsmooth stochastic optimization
- Mean-semideviation-based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees
- Nonsmooth nonconvex-nonconcave minimax optimization: primal-dual balancing and iteration complexity analysis
- A new random reshuffling method for nonsmooth nonconvex finite-sum optimization
- Stochastic optimization under hidden convexity
- Zeroth-order proximal clipped gradient method with shifts for distributed stochastic composite optimization problems with infinite variance
- Revisiting subgradient method: complexity and convergence beyond Lipschitz continuity
- Exact convergence rate of the last iterate in subgradient methods
- Non-asymptotic analysis of hybrid SPG for non-convex stochastic composite optimization
- A stochastic objective-function-free adaptive regularization method with optimal complexity
- First-order methods for nonsmooth nonconvex functional constrained optimization with or without Slater points
- Almost sure convergence of stochastic composite objective mirror descent for non-convex non-smooth optimization
- Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization
- Identifiability, the KL property in metric spaces, and subgradient curves
- Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization
- Unified convergence analysis for adaptive optimization with moving average estimator
- Understanding the Douglas-Rachford splitting method through the lenses of Moreau-type envelopes
- A constraint dissolving approach for nonsmooth optimization over the Stiefel manifold
- Differentially private non-convex optimization under the KL condition with optimal rates
This page was built for publication: Stochastic model-based minimization of weakly convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620418)
