The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods

Abstract

We present a general technique for the analysis of first-order methods. The technique relies on the construction of a duality gap for an appropriate approximation of the objective function, where the function approximation improves as the algorithm converges. We show that in continuous time enforcement of an invariant that this approximate duality gap decreases at a certain rate exactly recovers a wide range of first-order continuous-time methods. We characterize the discretization errors incurred by different discretization methods, and show how iteration-complexity-optimal methods for various classes of problems cancel out the discretization error. The techniques are illustrated on various classes of problems -- including convex minimization for Lipschitz-continuous objectives, smooth convex minimization, composite minimization, smooth and strongly convex minimization, solving variational inequalities with monotone operators, and convex-concave saddle-point optimization -- and naturally extend to other settings.

In SIAM Journal on Optimization. The most recent version corrected a few typos

References in corpus (5)

• On Acceleration with Noise-Corrupted Gradients
• Potential-Function Proofs for First-Order Methods
• Integration Methods and Accelerated Optimization Algorithms
• Alternating Randomized Block Coordinate Descent
• Solving Packing and Covering LPs in $\tilde{O}(\frac{1}{{\epsilon }^2})$ Distributed Iterations with a Single Algorithm and Simpler Analysis

Cited by in corpus (24)

• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• From differential equation solvers to accelerated first-order methods for convex optimization
• Direct Runge-Kutta Discretization Achieves Acceleration
• A Dynamical Systems Perspective on Nesterov Acceleration
• Acceleration Methods
• From Nesterov's Estimate Sequence to Riemannian Acceleration
• Robust Reinforcement Learning via Adversarial training with Langevin Dynamics
• Federated Composite Optimization
• Alternating Randomized Block Coordinate Descent
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives
• Global Riemannian Acceleration in Hyperbolic and Spherical Spaces
• Conjugate Gradients and Accelerated Methods Unified: The Approximate Duality Gap View
• Locally Accelerated Conditional Gradients
• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
• Heavy Ball Momentum for Conditional Gradient
• Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Breaking the $O(1/\epsilon )$ Optimal Rate for a Class of Minimax Problems
• Monotone Inclusions, Acceleration and Closed-Loop Control
• A Continuized View on Nesterov Acceleration