Timezone: »

 
Spotlight
Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
Thomas Kerdreux · Lewis Liu · Simon Lacoste-Julien · Damien Scieur

Tue Jul 20 07:40 PM -- 07:45 PM (PDT) @
in Optimization (Convex) 2 »
It is known that the Frank-Wolfe (FW) algorithm, which is affine covariant, enjoys faster convergence rates than $\mathcal{O}\left(1/K\right)$ when the constraint set is strongly convex. However, these results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds, in contradiction with FW's affine covariant property. In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. We show that our rates are better than any other known convergence rates of FW in this setting. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function present similar performances than its affine invariant counterpart, despite using affine dependent norms in the step size's computation.
Keywords: Convex Optimization

Author Information

Thomas Kerdreux (INRIA)
Lewis Liu (Mila & DIRO)
Simon Lacoste-Julien (Mila, University of Montreal & Samsung SAIL Montreal)
Simon Lacoste-Julien

Simon Lacoste-Julien is an associate professor at Mila and DIRO from Université de Montréal, and Canada CIFAR AI Chair holder. He also heads part time the SAIT AI Lab Montreal from Samsung. His research interests are machine learning and applied math, with applications in related fields like computer vision and natural language processing. He obtained a B.Sc. in math., physics and computer science from McGill, a PhD in computer science from UC Berkeley and a post-doc from the University of Cambridge. He spent a few years as a research faculty at INRIA and École normale supérieure in Paris before coming back to his roots in Montreal in 2016 to answer the call from Yoshua Bengio in growing the Montreal AI ecosystem.

Damien Scieur (Samsung - SAIT AI Lab, Montreal)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors