Optimization Online


Affine invariant convergence rates of the conditional gradient method

Javier Pena(jfp***at***andrew.cmu.edu)

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 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 exclusively on the pair $(f,\Psi)$. They are both affine invariant and norm-independent.

Keywords: affine-invariance, conditional gradient, convergence rates, growth condition

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Working Paper. Carnegie Mellon University. December, 2021.

Download: [PDF]

Entry Submitted: 12/29/2021
Entry Accepted: 12/29/2021
Entry Last Modified: 12/29/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society