Convergence Rate of Frank-Wolfe for Non-Convex Objectives

1 SIERRA - Statistical Machine Learning and Parsimony
Inria de Paris, CNRS - Centre National de la Recherche Scientifique, ENS Paris - École normale supérieure - Paris, DI-ENS - Département d'informatique de l'École normale supérieure
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).
Type de document :
Pré-publication, Document de travail
6 pages. 2016
Domaine :

https://hal.inria.fr/hal-01415335
Contributeur : Simon Lacoste-Julien <>
Soumis le : mardi 13 décembre 2016 - 01:26:11
Dernière modification le : mardi 17 avril 2018 - 09:08:33

Identifiants

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

Citation

Simon Lacoste-Julien. Convergence Rate of Frank-Wolfe for Non-Convex Objectives. 6 pages. 2016. 〈hal-01415335〉

Métriques

Consultations de la notice