On Nonconvex Optimization for Machine Learning
From MaRDI portal
Abstract: Gradient descent (GD) and stochastic gradient descent (SGD) are the workhorses of large-scale machine learning. While classical theory focused on analyzing the performance of these methods in convex optimization problems, the most notable successes in machine learning have involved nonconvex optimization, and a gap has arisen between theory and practice. Indeed, traditional analyses of GD and SGD show that both algorithms converge to stationary points efficiently. But these analyses do not take into account the possibility of converging to saddle points. More recent theory has shown that GD and SGD can avoid saddle points, but the dependence on dimension in these analyses is polynomial. For modern machine learning, where the dimension can be in the millions, such dependence would be catastrophic. We analyze perturbed versions of GD and SGD and show that they are truly efficient---their dimension dependence is only polylogarithmic. Indeed, these algorithms converge to second-order stationary points in essentially the same time as they take to converge to classical first-order stationary points.
Recommendations
- A Diffusion Approximation Theory of Momentum Stochastic Gradient Descent in Nonconvex Optimization
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- Second-order guarantees in centralized, federated and decentralized nonconvex optimization
- Convergence rates for the stochastic gradient descent method for non-convex objective functions
- Gradient descent finds the cubic-regularized nonconvex Newton step
Cited in
(31)- Second-order guarantees in centralized, federated and decentralized nonconvex optimization
- First-order methods almost always avoid strict saddle points
- Classical algebraic geometry. Abstracts from the workshop held June 20--26, 2021 (hybrid meeting)
- A quasi-Newton approach to nonsmooth convex optimization problems in machine learning
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- Non-convex optimization for machine learning
- On the fast convergence of random perturbations of the gradient flow
- Adaptive Hamiltonian variational integrators and applications to symplectic accelerated optimization
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Non-convex matrix completion and related problems via strong duality
- Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals
- Decentralized nonconvex optimization with guaranteed privacy and accuracy
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness
- Optimizing mean field spin glasses with external field
- Recent Theoretical Advances in Non-Convex Optimization
- The complexity of gradient descent: CLS = PPAD pls
- Minimizing robust density power-based divergences for general parametric density models
- A deterministic gradient-based approach to avoid saddle points
- No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians
- The threshold energy of low temperature Langevin dynamics for pure spherical spin glasses
- Losing momentum in continuous-time stochastic optimisation
- Sharp global guarantees for nonconvex low-rank recovery in the noisy overparameterized regime
- A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Counterexamples for noise models of stochastic gradients
- Efficiently escaping saddle points in bilevel optimization
- Properties of discrete sliced Wasserstein losses
- A gentle introduction to gradient-based optimization and variational inequalities for machine learning
- Only strict saddles in the energy landscape of predictive coding networks?
- Transformation of bi-level transit network design problem into single-objective unconstrained optimization
- Kolmogorov–Smirnov learning by neural networks with a nonconvex surrogate loss
This page was built for publication: On Nonconvex Optimization for Machine Learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056442)
