Convergence Rate of Frank-Wolfe for Non-Convex Objectives

Simon Lacoste-Julien 1, 2, 3
1 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of $O(1/\sqrt{t})$ on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gradient methods (though on slightly different measures of stationarity).
Complete list of metadatas

https://hal.inria.fr/hal-01415335
Contributor : Simon Lacoste-Julien <>
Submitted on : Tuesday, December 13, 2016 - 1:26:11 AM
Last modification on : Wednesday, January 30, 2019 - 11:07:42 AM

Links full text

Identifiers

  • HAL Id : hal-01415335, version 1
  • ARXIV : 1607.00345

Collections

Citation

Simon Lacoste-Julien. Convergence Rate of Frank-Wolfe for Non-Convex Objectives. 2016. ⟨hal-01415335⟩

Share

Metrics

Record views

414