Duality between subgradient and conditional gradient methods
From MaRDI portal
Abstract: Given a convex optimization problem and its dual, there are many possible first-order algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality, and implies notably that for certain problems, such as for supervised machine learning problems with non-smooth losses or problems regularized by non-smooth regularizers, the primal subgradient method and the dual conditional gradient method are formally equivalent. The dual interpretation leads to a form of line search for mirror descent, as well as guarantees of convergence for primal-dual certificates.
Recommendations
- Primal-dual subgradient methods for convex problems
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- Convergence analysis of approximate primal solutions in dual first-order methods
- Perturbed Fenchel duality and first-order methods
- Dual subgradient algorithms for large-scale nonsmooth learning problems
Cited in
(37)- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- Level-set methods for convex optimization
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Optimal complexity and certification of Bregman first-order methods
- Screening for a reweighted penalized conditional gradient method
- Submodular functions: from discrete to continuous domains
- Inexact successive quadratic approximation for regularized optimization
- Perturbed Fenchel duality and first-order methods
- Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm
- Low-rank spectral optimization via gauge duality
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- The cyclic block conditional gradient method for convex optimization problems
- Generalized conditional gradient for sparse estimation
- Linear coupling: an ultimate unification of gradient and mirror descent
- Dual subgradient algorithms for large-scale nonsmooth learning problems
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- On the effectiveness of Richardson extrapolation in data science
- Projection-free accelerated method for convex optimization
- Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods
- Efficient Relaxations for Dense CRFs with Sparse Higher-Order Potentials
- Dual space preconditioning for gradient descent
- Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Riemannian optimization via Frank-Wolfe methods
- Unifying mirror descent and dual averaging
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
- Short paper -- A note on the Frank-Wolfe algorithm for a class of nonconvex and nonsmooth optimization problems
- The Frank-Wolfe algorithm: a short introduction
- Stochastic incremental mirror descent algorithms with Nesterov smoothing
- A generalized Frank-Wolfe method with ``dual averaging for strongly convex composite optimization
- Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems
- First-order methods for convex optimization
- Primal and dual predicted decrease approximation methods
- Riemannian conditional gradient methods for composite optimization problems
- A nonsmooth Frank-Wolfe algorithm through a dual cutting-plane approach
- Geometry-dependent matching pursuit: a transition phase for convergence on linear regression and Lasso
- Distributed block-diagonal approximation methods for regularized empirical risk minimization
This page was built for publication: Duality between subgradient and conditional gradient methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954379)
