The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
From MaRDI portal
Publication:4629338
DOI10.1137/18M1172314zbMATH Open1412.90085arXiv1712.02485OpenAlexW2772443375WikidataQ128286883 ScholiaQ128286883MaRDI QIDQ4629338FDOQ4629338
Jelena Diakonikolas, Lorenzo Orecchia
Publication date: 22 March 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1712.02485
Numerical mathematical programming methods (65K05) Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Duality theory (optimization) (49N15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Convex analysis and monotone operator theory in Hilbert spaces
- Smooth minimization of non-smooth functions
- Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
- Primal-dual subgradient methods for convex problems
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Universal gradient methods for convex optimization problems
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- Lectures on convex optimization
- Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
- A variational perspective on accelerated methods in optimization
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Complexity bounds for primal-dual methods minimizing the model of objective function
- An Optimal First Order Method Based on Optimal Quadratic Averaging
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- A new approach to computing maximum flows using electrical flows
- Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
Cited In (16)
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- Discrete processes and their continuous limits
- Triggered gradient tracking for asynchronous distributed optimization
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- The regularized submodular maximization via the Lyapunov method
- Fair Packing and Covering on a Relative Scale
- Cyclic Coordinate Dual Averaging with Extrapolation
- Unified Acceleration of High-Order Algorithms under General Hölder Continuity
- Title not available (Why is that?)
- Generalized Momentum-Based Methods: A Hamiltonian Perspective
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- Complementary composite minimization, small gradients in general norms, and applications
- Continuous-Time Convergence Rates in Potential and Monotone Games
- A control-theoretic perspective on optimal high-order optimization
- Perturbed Fenchel duality and first-order methods
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
Uses Software
This page was built for publication: The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629338)
