FrankWolfe on Uniformly Convex Sets.
TITLE: FrankWolfe on Uniformly Convex Sets.
AUTHORS: Thomas Kerdreux, Alexandre d'Aspremont.
ABSTRACT: The FrankWolfe 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 stronglyconvex sets. Uniformly convex sets nontrivially 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 FrankWolfe 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 FrankWolfe. These results also importantly highlight that FrankWolfe is adaptive to much more generic constraint set structures, thus explaining faster empirical convergence.
STATUS: Preprint.
ArXiv PREPRINT: 2004.11053
