The approximate duality gap technique: a unified theory of first-order methods
From MaRDI portal
(Redirected from Publication:4629338)
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.
Recommendations
- Convergence analysis of approximate primal solutions in dual first-order methods
- Perturbed Fenchel duality and first-order methods
- Convergence of first-order methods via the convex conjugate
- First-order methods for convex optimization
- Efficient first-order methods for convex minimization: a constructive approach
Cites work
- scientific article; zbMATH DE number 6680986 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- A new approach to computing maximum flows using electrical flows
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- A variational perspective on accelerated methods in optimization
- Accelerated extra-gradient descent: a novel accelerated first-order method
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- An optimal first order method based on optimal quadratic averaging
- Catalyst acceleration for first-order convex optimization: from theory to practice
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Convex analysis and monotone operator theory in Hilbert spaces
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Lectures on convex optimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Linear coupling: an ultimate unification of gradient and mirror descent
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Smooth minimization of non-smooth functions
- The approximate duality gap technique: a unified theory of first-order methods
- Universal gradient methods for convex optimization problems
Cited in
(22)- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Discrete processes and their continuous limits
- Continuous-time convergence rates in potential and monotone games
- Triggered gradient tracking for asynchronous distributed optimization
- Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization
- Approximate Farkas lemma and approximate duality for fractional optimization problems
- The regularized submodular maximization via the Lyapunov method
- A continuous-time perspective on global acceleration for monotone equation problems
- Global Riemannian acceleration in hyperbolic and spherical spaces
- Cyclic Coordinate Dual Averaging with Extrapolation
- On the mathematics of the natural physics of optimization
- The approximate duality gap technique: a unified theory of first-order methods
- scientific article; zbMATH DE number 7370590 (Why is no real title available?)
- Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences
- Optimization on a finer scale: bounded local subgradient variation perspective
- Complementary composite minimization, small gradients in general norms, and applications
- A control-theoretic perspective on optimal high-order optimization
- Some primal-dual theory for subgradient methods for strongly convex optimization
- Fair packing and covering on a relative scale
- Generalized momentum-based methods: a Hamiltonian perspective
- Perturbed Fenchel duality and first-order methods
- Unified acceleration of high-order algorithms under general Hölder continuity
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)
