Projection-Free Optimization on Uniformly Convex Sets

Abstract

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.

References in corpus (18)

• Generalized power method for sparse principal component analysis
• Learning a Text-Video Embedding from Incomplete and Heterogeneous Data
• Optimal Transport for structured data with application on graphs
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle
• On the Equivalence between Herding and Conditional Gradient Algorithms
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Subspace Robust Wasserstein Distances
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
• An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms
• Convex Optimization without Projection Steps
• Faster Rates for Convex-Concave Games
• Uniformly convex subsets of the Hilbert space with modulus of convexity of the second order
• Local characterization of strongly convex sets
• Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
• Curvature of Feasible Sets in Offline and Online Optimization
• On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations
• The condition of a function relative to a polytope

Cited by in corpus (4)

• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• Local and Global Uniform Convexity Conditions
• Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
• Strong Convexity of Sets in Riemannian Manifolds