Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets

By Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, Damien Scieur. 2020

21 citations recorded by the source corpus.

It is known that the Frank-Wolfe (FW) algorithm, which is affine-covariant, enjoys accelerated convergence rates 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. 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 surprisingly converge to an affine invariant step size, despite using affine-dependent norms in the step size's computation. This indicates that we do not necessarily need to know the set's structure in advance to enjoy the affine-invariant accelerated rate.

Subfields: Aerospace Engineering, Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Francesco Rinaldi
2. Damiano Zeffiro
3. Immanuel M. Bomze

In Optimization & Training

1. Francesco Rinaldi
2. Damiano Zeffiro
3. Immanuel M. Bomze

Citations in the corpus

• Fast Cluster Detection in Networks by First Order Optimization (2021, background): “, [12], [19], [23], [21] and references therein) thanks to their sparse approximation properties, their weaker requirement of a linear minimization oracle instead of a projection oracle with respect to proximal gradient like methods, and their ability to quickly identify the support of a solution.”