Geometric Acceleration in Projection-Free Optimization

This direction is split into other directions: geometric acceleration. Its last version stays readable and citable here.

Version 1 of 129 papers44 conceptsfrozen 2026-10-04

In large-scale machine learning, the Frank-Wolfe (FW) algorithm is a staple because it is "projection-free." While standard gradient descent requires a computationally expensive projection step to keep the solution within a constraint set (like an $\ell_1$-ball), Frank-Wolfe only requires a Linear Minimization Oracle (LMO)—essentially finding the "corner" of the set that points most in the direction of the negative gradient.

However, Frank-Wolfe has historically been plagued by a slow $O(1/t)$ convergence rate. This slowness is usually blamed on the "zig-zagging" behavior that occurs when the algorithm bounces between the vertices of a polytope (a flat-sided set like a diamond or a cube).

Recent research has revealed that this slow rate is not a fundamental limit of the algorithm, but rather a consequence of the geometry of the constraint set. When the feasible set is "curvy" rather than "flat," the Frank-Wolfe algorithm naturally accelerates.

The Geometry of Curvature

The core intuition is that the "roundness" of a constraint set prevents the linear optimizer from making poor, extreme choices. In a polytope, the LMO always returns a vertex, which can be far from the actual path toward the optimum. In a "strongly convex" set—think of a smooth ball rather than a diamond—the boundary is curved.

Dan Garber and Elad Hazan proved in Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets that this curvature eliminates oscillations. Because the boundary is curvy, the update direction remains high-quality throughout the process, allowing the vanilla FW algorithm to jump from a rate of $O(1/t)$ to $O(1/t^2)$. This effectively bridges the gap between projection-free methods and accelerated gradient descent without adding any computational overhead.

From Global to Local Uniform Convexity

The acceleration effect is not limited to perfectly "round" sets. Alexandre d'Aspremont, Thomas Kerdreux, and Sebastian Pokutta expanded this idea to "uniformly convex" sets, such as $\ell_p$-balls for $p > 2$. In Projection-Free Optimization on Uniformly Convex Sets, they showed that the algorithm is inherently adaptive: it automatically exploits whatever curvature is present to speed up.

Crucially, they discovered that you don't even need the entire set to be curved. In Local and Global Uniform Convexity Conditions, the authors demonstrate that if the boundary is curved specifically near the optimal solution, the algorithm still achieves faster convergence. This means that even in complex, mixed geometries, the local "roundness" at the finish line is enough to drive efficiency.

Achieving Affine Invariance

One theoretical hurdle was that many proofs for these faster rates relied on specific coordinate systems. However, the Frank-Wolfe algorithm itself is "affine-invariant"—it doesn't care if you stretch or rotate the space.

Thomas Kerdreux and colleagues addressed this in Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets. They introduced a "directional smoothness" framework showing that standard backtracking line-searches automatically find the optimal, coordinate-independent step sizes. This unified the geometric intuition with the practical reality of the algorithm's performance.

Beyond Euclidean Space: Riemannian Manifolds

The principle that set geometry drives acceleration is so fundamental that it extends beyond flat Euclidean space. Damien Scieur, David Martínez-Rubio, and others explored this in Strongly Convex Sets in Riemannian Manifolds. By defining a "Riemannian Scaling Inequality," they proved that the Riemannian version of Frank-Wolfe also achieves linear convergence when the constraint set on the manifold is sufficiently "round."

Area Convexity and High Dimensions

While strong convexity helps in many settings, it often struggles in high-dimensional $\ell_\infty$ spaces (like boxes), where performance usually degrades with the number of dimensions. To solve this, researchers like Arun Jambulapati and Aaron Sidford have utilized a weaker geometric property called area convexity.

As detailed in A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport, area convexity focuses on the area spanned by gradients rather than the distance between points. This allows for accelerated convergence in problems like Optimal Transport and Mixed Packing/Covering LPs (Digvijay Boob and Saurabh Sawlani, Faster width-dependent algorithm for mixed packing and covering LPs), bypassing the dimensionality penalties that usually slow down first-order methods.

Summary of Convergence Rates

Constraint Set Geometry Convergence Rate Key Reference
Polytopal (Flat) $O(1/t)$ Standard FW
Strongly Convex (Curved) $O(1/t^2)$ Garber & Hazan (2014)
Uniformly Convex Interpolated Rates d'Aspremont et al. (2020)
Local Curvature at Optimum Accelerated/Linear d'Aspremont et al. (2021)

By shifting the focus from the properties of the objective function to the geometric curvature of the feasible set, this line of research has transformed Frank-Wolfe from a "slow but simple" method into a high-performance tool for modern, high-dimensional optimization.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geometric_acceleration_in_projection_fre_c2e98bc0,
  title = {Geometric Acceleration in Projection-Free Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-acceleration-in-projection-free-optimization/rdr_c2e98bc0b13c46b693417d0b181b1469},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_geometric_acceleration_in_projection_fre_c2e98bc0_v1,
  title = {Geometric Acceleration in Projection-Free Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-acceleration-in-projection-free-optimization/rdr_c2e98bc0b13c46b693417d0b181b1469/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}