Generalized momentum-based methods: a Hamiltonian perspective

DOI10.1137/20M1322716zbMATH Open1462.90087arXiv1906.00436OpenAlexW3136523593MaRDI QIDQ5857293FDOQ5857293

Authors: Jelena Diakonikolas, Michael Jordan 

Publication date: 31 March 2021

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We take a Hamiltonian-based perspective to generalize Nesterov's accelerated gradient descent and Polyak's heavy ball method to a broad class of momentum methods in the setting of (possibly) constrained minimization in Euclidean and non-Euclidean normed vector spaces. Our perspective leads to a generic and unifying nonasymptotic analysis of convergence of these methods in both the function value (in the setting of convex optimization) and in norm of the gradient (in the setting of unconstrained, possibly nonconvex, optimization). Our approach relies upon a time-varying Hamiltonian that produces generalized momentum methods as its equations of motion. The convergence analysis for these methods is intuitive and is based on the conserved quantities of the time-dependent Hamiltonian.

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

Recommendations

• A variational perspective on accelerated methods in optimization
• Steepest descent with momentum for quadratic functions is a version of the conjugate gradient method
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Nonlinear acceleration of momentum and primal-dual algorithms
• An adaptive gradient method with energy and momentum

zbMATH Keywords

accelerationHamiltonian dynamicsstationary pointsmomentum-based methods

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Duality theory (optimization) (49N15)

Cites Work

• Title not available (Why is that?)
• Linear coupling: an ultimate unification of gradient and mirror descent
• Title not available (Why is that?)
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Inertial game dynamics and applications to constrained optimization
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• Optimal methods of smooth convex minimization
• 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
• Some methods of speeding up the convergence of iteration methods
• A second-order differential system with Hessian-driven damping; application to non-elastic shock laws
• On the long time behavior of second order differential equations with asymptotically small dissipation
• Title not available (Why is that?)
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Universal method for stochastic composite optimization problems
• New Proximal Point Algorithms for Convex Minimization
• Title not available (Why is that?)
• Discrete processes and their continuous limits
• Lectures on convex optimization
• Catalyst acceleration for first-order convex optimization: from theory to practice
• Generalizing the optimized gradient method for smooth convex minimization
• A variational perspective on accelerated methods in optimization
• Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
• Generalized uniformly optimal methods for nonlinear programming
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• First-order optimization algorithms via inertial systems with Hessian driven damping
• Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
• On damped second-order gradient systems
• Lower bounds for parallel and randomized convex optimization
• Lower bounds for finding stationary points I
• Conformal symplectic and relativistic optimization
• An optimal first order method based on optimal quadratic averaging
• The approximate duality gap technique: a unified theory of first-order methods
• Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems
• Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
• Behavior of accelerated gradient methods near critical points of nonconvex functions
• A new approach to computing maximum flows using electrical flows
• Area-convexity, \(\ell_\infty\) regularization, and undirected multicommodity flow
• Accelerated extra-gradient descent: a novel accelerated first-order method

Cited In (12)

• On the convergence analysis of aggregated heavy-ball method
• Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
• Implicit Regularization and Momentum Algorithms in Nonlinearly Parameterized Adaptive Control and Prediction
• A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization
• Momentum and Hamiltonian operators in generalized coordinates
• Iteration complexity of fixed-step methods by Nesterov and Polyak for convex quadratic functions
• Bregman dynamics, contact transformations and convex optimization
• Asymptotic analysis of a structure-preserving integrator for damped Hamiltonian systems
• Convergence of the Momentum Method for Semialgebraic Functions with Locally Lipschitz Gradients
• Fast symplectic integrator for Nesterov-type acceleration method
• A variational perspective on accelerated methods in optimization
• Recent Theoretical Advances in Non-Convex Optimization

This page was built for publication: Generalized momentum-based methods: a Hamiltonian perspective

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