Affine invariant convergence rates of the conditional gradient method

2021/12/13 by Pena, Javier · 1 citation
#90C25 #90C46 #90C52 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2112.06727

Abstract

We show that the conditional gradient method for the convex composite problem min_x\f(x) + Ψ(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 (f,Ψ) in an affine invariant and norm-independent fashion.

Cited by

• Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets

Related

• A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
• Splitting the Conditional Gradient Algorithm
• Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry
• Convergence rates of proximal gradient methods via the convex conjugate
• Generalized conditional gradient: analysis of convergence and applications