In high-dimensional optimization, the "projection" step is often the most expensive part of an algorithm. If you are optimizing over a complex set—like a nuclear norm ball for matrix completion or a base polytope for submodular flow—projecting a point back onto that set requires solving a costly quadratic subproblem in every single iteration.
The Frank-Wolfe (FW) algorithm, also known as the Conditional Gradient method, offers a "projection-free" alternative. Instead of a projection, it uses a Linear Minimization Oracle (LMO) to find the extreme point (vertex) of the feasible set that is furthest in the direction of the negative gradient. It then takes a small step toward that vertex.
However, standard Frank-Wolfe has a notorious flaw: it is painfully slow. While gradient descent often enjoys linear convergence (where the error drops exponentially), standard Frank-Wolfe is typically restricted to a sublinear rate of $O(1/t)$. This slowdown happens because the algorithm gets "trapped" near the boundaries of the feasible set, leading to an inefficient zig-zagging behavior.
The Zig-Zagging Problem
To understand why Frank-Wolfe slows down, imagine you are trying to reach an optimal point that lies on the edge of a polytope. The gradient points toward the edge, but the LMO can only return vertices.
As Simon Lacoste-Julien and Martin Jaggi explain in On the Global Linear Convergence of Frank-Wolfe Optimization Variants, the algorithm begins to oscillate between the vertices defining that edge. Because it can only move toward new vertices, it can never quite "straighten out" its path. It keeps adding small amounts of weight to new vertices without ever being able to fully discard the suboptimal ones it picked up earlier.
Moving Away to Move Faster
The breakthrough that restores linear convergence is the Away-Step. Instead of only looking for a new vertex to move toward, the algorithm maintains an "active set" of all vertices it has previously visited. In each iteration, it asks two questions:
- Which new vertex is most promising to move toward?
- Which vertex in my current active set is most hindering my progress?
By moving away from the worst vertex in the active set—effectively reducing its weight—the algorithm can "undo" its previous mistakes. As noted by Francesco Rinaldi and colleagues in Frank-Wolfe and friends, this mechanism allows the optimizer to prune suboptimal directions and navigate the geometry of the polytope more directly.
This modification, known as the Away-step Frank-Wolfe (AFW), achieves global linear convergence on polytopes. The rate of this convergence is governed by a geometric constant called the pyramidal width, which captures the "thickness" of the polytope relative to the objective function.
Why It Scales: The Geometry of the Face
A common mystery in this field was why these algorithms perform so well in massive, high-dimensional problems where the number of vertices is astronomical. Dan Garber provided a key insight in Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity.
Garber proved that the convergence rate doesn't actually depend on the massive ambient dimension of the entire problem. Instead, it depends on the dimension of the optimal face—the specific low-dimensional slice of the polytope where the solution lives. This explains why AFW is so effective at finding sparse solutions: it quickly identifies the correct "active set" of vertices and ignores the rest of the high-dimensional space.
Modern Extensions and Tools
The intuition of away-steps has recently been extended far beyond simple convex optimization:
- Saddle Point Problems: Gauthier Gidel and Simon Lacoste-Julien demonstrated in Frank-Wolfe Algorithms for Saddle Point Problems that away-steps can solve min-max problems (like those in GANs or game theory) with linear convergence, resolving conjectures that had stood for decades.
- Non-Euclidean Geometry: Researchers like Shota Takahashi and Sebastian Pokutta have integrated away-steps with Bregman distances in Fast Frank–Wolfe Algorithms with Adaptive Bregman Step-Size for Weakly Convex Functions. This allows the algorithm to adapt to the local curvature of non-Lipschitz functions, maintaining speed even when the objective is poorly behaved.
- Stochastic Settings: For massive datasets, Donald Goldfarb and Chaoxu Zhou showed in Linear Convergence of Stochastic Frank Wolfe Variants that combining variance reduction with away-steps allows for linear convergence even when using only small batches of data.
To make these techniques accessible, Mathieu Besançon and others developed FrankWolfe.jl, a high-performance toolbox that implements these advanced variants. By focusing on the geometric removal of suboptimal vertices, these algorithms have transformed from slow, theoretical curiosities into some of the most efficient tools for structured, high-dimensional optimization.