  The Frank-Wolfe method solves smooth constrained convex optimization problems
at a generic sublinear rate of $\mathcal{O}(1/T)$, and it (or its variants)
enjoys accelerated convergence rates for two fundamental classes of
constraints: polytopes and strongly-convex sets. Uniformly convex sets
non-trivially subsume strongly convex sets and form a large variety of
\textit{curved} convex sets commonly encountered in machine learning and signal
processing. For instance, the $\ell_p$-balls are uniformly convex for all $p >
1$, but strongly convex for $p\in]1,2]$ only. We show that these sets
systematically induce accelerated convergence rates for the original
Frank-Wolfe algorithm, which continuously interpolate between known rates. Our
accelerated convergence rates emphasize that it is the curvature of the
constraint sets -- not just their strong convexity -- that leads to accelerated
convergence rates. These results also importantly highlight that the
Frank-Wolfe algorithm is adaptive to much more generic constraint set
structures, thus explaining faster empirical convergence. Finally, we also show
accelerated convergence rates when the set is only locally uniformly convex and
provide similar results in online linear optimization.
