Understanding the acceleration phenomenon via high-resolution differential equations

DOI10.1007/s10107-021-01681-8zbMath1500.65026arXiv1810.08907OpenAlexW3181590451WikidataQ115385304 ScholiaQ115385304MaRDI QIDQ2089769

Bin Shi, Weijie J. Su, Michael I. Jordan, Simon S. Du

Publication date: 24 October 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationLyapunov functionordinary differential equationfirst-order methodgradient minimizationNesterov's accelerated gradient methodsPolyak's heavy ball method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Convex programming (90C25) Numerical optimization and variational techniques (65K10) Stability and convergence of numerical methods for ordinary differential equations (65L20) Perturbations, asymptotics of solutions to ordinary differential equations (34E10)

Related Items

From the Ravine Method to the Nesterov Method and Vice Versa: A Dynamical System Perspective, A new minimizing-movements scheme for curves of maximal slope, Newton-type inertial algorithms for solving monotone equations Governed by sums of potential and nonpotential operators, Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping, Accelerated dynamics with dry friction via time scaling and averaging of doubly nonlinear evolution equations, Fast convergence of inertial dynamics with Hessian-driven damping under geometry assumptions, Fast continuous dynamics inside the graph of subdifferentials of nonsmooth convex functions, Deterministic neural networks optimization from a continuous and energy point of view, A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization, No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization, Inertial Newton algorithms avoiding strict saddle points, First order inertial optimization algorithms with threshold effects associated with dry friction, Convergence of inertial dynamics driven by sums of potential and nonpotential operators with implicit Newton-like damping, Accelerated gradient methods combining Tikhonov regularization with geometric damping driven by the Hessian, Fast optimization via inertial dynamics with closed-loop damping, Continuous Newton-like Methods Featuring Inertia and Variable Mass, Unnamed Item, A piecewise conservative method for unconstrained convex optimization, Two structure-preserving time discretizations for gradient flows, On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Fast convex optimization via inertial dynamics with Hessian driven damping
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics.
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• The Rate of Convergence of Nesterov's Accelerated Forward-Backward Method is Actually Faster Than $1/k^2$
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• An Optimal First Order Method Based on Optimal Quadratic Averaging
• The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$
• Convergence Rates of Inertial Forward-Backward Algorithms
• A variational perspective on accelerated methods in optimization
• A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization
• Some methods of speeding up the convergence of iteration methods