Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance

DOI10.1214/21-EJS1880zbMATH Open1471.62442arXiv2012.04002OpenAlexW3192961449MaRDI QIDQ2233558FDOQ2233558

Authors: Anas Barakat, Pascal Bianchi, W. Hachem, Sholom Schechtman 

Publication date: 11 October 2021

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: In this paper, a general stochastic optimization procedure is studied, unifying several variants of the stochastic gradient descent such as, among others, the stochastic heavy ball method, the Stochastic Nesterov Accelerated Gradient algorithm (S-NAG), and the widely used Adam algorithm. The algorithm is seen as a noisy Euler discretization of a non-autonomous ordinary differential equation, recently introduced by Belotto da Silva and Gazeau, which is analyzed in depth. Assuming that the objective function is non-convex and differentiable, the stability and the almost sure convergence of the iterates to the set of critical points are established. A noteworthy special case is the convergence proof of S-NAG in a non-convex setting. Under some assumptions, the convergence rate is provided under the form of a Central Limit Theorem. Finally, the non-convergence of the algorithm to undesired critical points, such as local maxima or saddle points, is established. Here, the main ingredient is a new avoidance of traps result for non-autonomous settings, which is of independent interest.

Full work available at URL: https://arxiv.org/abs/2012.04002

Recommendations

• Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization
• A Diffusion Approximation Theory of Momentum Stochastic Gradient Descent in Nonconvex Optimization
• Publication:4862190
• Convergence rates for the stochastic gradient descent method for non-convex objective functions
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods

zbMATH Keywords

dynamical systemsstochastic approximationADAMadaptive gradient methods with momentumavoidance of trapsNesterov accelerated gradient

Mathematics Subject Classification ID

Stochastic approximation (62L20) Limit theorems in probability theory (60F99) Artificial intelligence (68T99) Initial value problems, existence, uniqueness, continuous dependence and continuation of solutions to ordinary differential equations (34A12)

Cites Work

• Adaptive subgradient methods for online learning and stochastic optimization
• Convergence of a stochastic approximation version of the EM algorithm
• Nonautonomous dynamical systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• Ordinary differential equations.
• Title not available (Why is that?)
• Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing
• Taylor approximation of integral manifolds
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• THE HEAVY BALL WITH FRICTION METHOD, I. THE CONTINUOUS DYNAMICAL SYSTEM: GLOBAL EXPLORATION OF THE LOCAL MINIMA OF A REAL-VALUED FUNCTION BY ASYMPTOTIC ANALYSIS OF A DISSIPATIVE DYNAMICAL SYSTEM
• Nonconvergence to unstable points in urn models and stochastic approximations
• On the long time behavior of second order differential equations with asymptotically small dissipation
• Title not available (Why is that?)
• Asymptotic pseudotrajectories and chain recurrent flows, with applications
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• Do stochastic algorithms avoid traps?
• Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas decroissant
• Stochastic heavy ball
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• First-order methods almost always avoid strict saddle points
• Optimal convergence rates for Nesterov acceleration
• Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization
• A general system of differential equations to model first-order adaptive algorithms

Cited In (12)

• Risk-Sensitive Reinforcement Learning via Policy Gradient Search
• Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
• A general system of differential equations to model first-order adaptive algorithms
• A Convergence Study of SGD-Type Methods for Stochastic Optimization
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Convergence analysis of AdaBound with relaxed bound functions for non-convex optimization
• Convergence and dynamical behavior of the ADAM algorithm for nonconvex stochastic optimization
• Nonlinear Gradient Mappings and Stochastic Optimization: A General Framework with Applications to Heavy-Tail Noise
• An adaptive gradient method with energy and momentum
• SGEM: stochastic gradient with energy and momentum
• Switched diffusion processes for non-convex optimization and saddle points search
• Stochastic modified equations and dynamics of stochastic gradient algorithms. I: Mathematical foundations

Uses Software

• AdaGrad
• RMSprop
• Adam

This page was built for publication: Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2233558)