Affine Invariant Convergence Rates of the Conditional Gradient Method
- 13 October 2023
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 33 (4) , 2654-2674
Abstract
We show that the conditional gradient method for the convex composite problem [Formula: see text] generates primal and dual iterates with a duality gap converging to zero provided a suitable 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 [Formula: see text] in an affine invariant and norm-independent fashion.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Variable quasi-Bregman monotone sequencesNumerical Algorithms, 2016
- Duality Between Subgradient and Conditional Gradient MethodsSIAM Journal on Optimization, 2015
- New analysis and results for the Frank–Wolfe methodMathematical Programming, 2014
- Conditional gradient algorithms for norm-regularized smooth convex optimizationMathematical Programming, 2014
- Analysis of the Convergence Rate for the Cyclic Projection Algorithm Applied to Basic Semialgebraic Convex SetsSIAM Journal on Optimization, 2014
- A generalized conditional gradient method and its connection to an iterative shrinkage methodComputational Optimization and Applications, 2007
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical SystemsSIAM Journal on Optimization, 2007
- On gradients of functions definable in o-minimal structuresAnnales de l'institut Fourier, 1998
- A minimization method for the sum of a convex function and a continuously differentiable functionJournal of Optimization Theory and Applications, 1981
- Constrained minimization methodsUSSR Computational Mathematics and Mathematical Physics, 1966