Contributed Video: Affine-Invariant Analysis of Frank-Wolfe on Strongly Convex Sets, Lewis Liu

When the constraint set $\mathcal{C}$ is strongly convex, the Frank-Wolfe algorithm, which is affine co-variant, enjoys accelerated convergence rates. In contrast, existing results rely on norm-dependent assumptions, usually incurring non-affine invariant bounds. In this work, we introduce new structural assumptions on the problem 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 stepsize, despite using affine-dependent norms in the computation of the stepsize.