Affine Invariant Convergence Rates of the Conditional Gradient Method
From MaRDI portal
Abstract: We show that the conditional gradient method for the convex composite problem [min_x{f(x) + Psi(x)}] generates primal and dual iterates with a duality gap converging to zero provided a suitable {em growth property} holds and the algorithm makes a judicious choice of stepsizes. The rate of convergence of the duality gap to zero ranges from sublinear to linear depending on the degree of the growth property. The growth property and convergence results depend on the pair in an affine invariant and norm-independent fashion.
Recommendations
- A conditional gradient method with linear rate of convergence for solving convex linear systems
- Duality between subgradient and conditional gradient methods
- A variant of the constrained gradient method
- Adaptive conditional gradient method
- Convergence rates of proximal gradient methods via the convex conjugate
Cites work
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A generalized conditional gradient method and its connection to an iterative shrinkage method
- A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
- A minimization method for the sum of a convex function and a continuously differentiable function
- A simplified view of first order methods for optimization
- Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient type methods for composite nonlinear and stochastic optimization
- Duality between subgradient and conditional gradient methods
- Forward-backward splitting with Bregman distances
- Generalized conditional gradient for sparse estimation
- Generalized conditional gradient method for elastic-net regularization
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3293978 (Why is no real title available?)
- scientific article; zbMATH DE number 3381034 (Why is no real title available?)
- Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems
- New analysis and results for the Frank-Wolfe method
- On gradients of functions definable in o-minimal structures
- Relatively smooth convex optimization by first-order methods, and applications
- Restarting Frank-Wolfe: faster rates under Hölderian error bounds
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Variable quasi-Bregman monotone sequences
Cited in
(8)- A conditional gradient method with linear rate of convergence for solving convex linear systems
- Convergence of the exponentiated gradient method with Armijo line search
- Duality between subgradient and conditional gradient methods
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- Linear convergence of accelerated conditional gradient algorithms in spaces of measures
- Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
- Convergence rate analysis of the multiplicative gradient method for PET-type problems
- Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes
This page was built for publication: Affine Invariant Convergence Rates of the Conditional Gradient Method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076864)
