  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.
