Frank-Wolfe on Uniformly Convex Sets.

TITLE: Frank-Wolfe on Uniformly Convex Sets.

AUTHORS: Thomas Kerdreux, Alexandre d'Aspremont.

ABSTRACT: The Frank-Wolfe method solves smooth constrained convex optimization problems at a generic sublinear rate of O(1/T), and 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 curved convex sets commonly encountered in machine learning and signal processing. For instance, the ℓp balls are uniformly convex for all p>1, but strongly convex for p in (1,2] only. We show that these sets induce accelerated convergence rates for the 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 for Frank-Wolfe. These results also importantly highlight that Frank-Wolfe is adaptive to much more generic constraint set structures, thus explaining faster empirical convergence.

STATUS: Preprint.

ArXiv PREPRINT: 2004.11053