A geometric alternative to Nesterov's accelerated gradient descent

Abstract

We propose a new method for unconstrained optimization of a smooth and strongly convex function, which attains the optimal rate of convergence of Nesterov's accelerated gradient descent. The new algorithm has a simple geometric interpretation, loosely inspired by the ellipsoid method. We provide some numerical evidence that the new method can be superior to Nesterov's accelerated gradient descent.

Cited by in corpus (46)

• A Variational Perspective on Accelerated Methods in Optimization
• A Lyapunov Analysis of Momentum Methods in Optimization
• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• Direct Runge-Kutta Discretization Achieves Acceleration
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• A Dynamical Systems Perspective on Nesterov Acceleration
• Towards Riemannian Accelerated Gradient Methods
• Dissipativity Theory for Nesterov's Accelerated Method
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• A general system of differential equations to model first order adaptive algorithms
• Accelerating Greedy Coordinate Descent Methods
• A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
• A unified convergence bound for conjugate gradient and accelerated gradient
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• The condition of a function relative to a polytope
• A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities
• A variable metric mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Tensor optimal transport, distance between sets of measures and tensor scaling
• Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
• Parametrized Accelerated Methods Free of Condition Number
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• Acceleration via Fractal Learning Rate Schedules
• Black-box optimization with a politician
• Potential-based analyses of first-order methods for constrained and composite optimization
• Locally Accelerated Conditional Gradients
• Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Chebyshev Center of the Intersection of Balls: Complexity, Relaxation and Approximation
• Partial minimization of strict convex functions and tensor scaling
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• On the Curved Geometry of Accelerated Optimization
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• An Explicit Convergence Rate for Nesterov's Method from SDP
• A Continuized View on Nesterov Acceleration
• Resource-Aware Discretization of Accelerated Optimization Flows
• Algorithmic Instabilities of Accelerated Gradient Descent
• FLAG n' FLARE: Fast Linearly-Coupled Adaptive Gradient Methods