When optimizing smooth functions over complex constraints, machine learning practitioners face a difficult trade-off between the cost of an individual iteration and the total number of iterations required to converge.
Projection-based methods, such as projected gradient descent, enjoy fast linear or accelerated convergence rates. However, they require projecting back onto the feasible constraint set at every step—a requirement that becomes prohibitively expensive when dealing with high-dimensional polytopes or trace-norm balls where projections demand full Singular Value Decompositions (SVD).
To bypass this computational bottleneck, the Frank-Wolfe (FW) algorithm—also known as the Conditional Gradient Method (CGM)—replaces expensive projections with a Linear Minimization Oracle (LMO). As emphasized by Jaggi in a foundational review, the LMO simply finds a vertex of the constraint set that minimizes a linear approximation of the objective. This makes each iteration incredibly cheap and naturally promotes sparse solutions.
Yet, this per-iteration efficiency comes at a steep price. Standard projection-free methods suffer from a notorious sublinear convergence bottleneck, typically scaling at a slow rate of $O(1/t)$ (Yu et al.; d'Aspremont et al.). This sublinear rate means that as the algorithm approaches the optimal solution, its progress crawls to a halt, making high-precision solutions practically unattainable.
An active line of research focuses on understanding the geometric roots of this bottleneck and developing structural and algorithmic modifications to unlock linear convergence.
Why Standard Frank-Wolfe Zig-Zags
To understand why the sublinear bottleneck occurs, we must look at the trajectory of the algorithm near the boundaries of the constraint set.
Polytopal Constraint Set
/\
/ \
/ \
/ * <-- Target Optimum (on the boundary)
/ / \
/ /\ \ <-- Zig-zagging trajectory
/ / \ \
/__________\
Consider minimizing a function where the true optimum lies on the boundary of a polytope. At any given iterate, the negative gradient points outward, past the boundary. When we query the LMO, it returns a single vertex of the face containing the optimum. The algorithm then takes a convex step toward this vertex.
Crucially, because a standard Frank-Wolfe step can only move toward a vertex returned by the LMO, it cannot slide smoothly along the face of a polytope. Instead, as soon as the iterate moves toward one vertex, the gradient shifts, causing the LMO to pick an adjacent vertex on the next iteration. The trajectory begins to violently alternate between vertices, creating a jagged "zig-zag" pattern. Because the step size must decay over time ($\gamma \approx 1/t$) to guarantee convergence, the step lengths shrink, and the algorithm gets trapped in an oscillatory loop of diminishing returns (Pokutta).
Algorithmic Remedies: Away-Steps and Active Corrections
The most direct way to eliminate zig-zagging is to give the algorithm a mechanism to undo past mistakes. If the iterate is being dragged down by an old vertex in its active set, it should be allowed to move away from that vertex.
Lacoste-Julien et al. proved that by incorporating "away-steps"—which explicitly allow the algorithm to decrease the weight of a bad vertex currently in its history—variants of Frank-Wolfe can completely bypass the sublinear bottleneck, achieving global linear convergence on polytopes. This acceleration is governed by a geometric constant known as the pyramidal width, which quantifies the thickness of the polytope faces.
Other structural variants build on this intuition by introducing deeper memory and correction mechanisms:
- Fully Corrective Frank-Wolfe (FCFW): Instead of moving toward a single vertex, methods like the one proposed by Liu 0005 et al. re-optimize the objective over the entire convex hull of all previously discovered vertices, unlocking linear convergence for complex regularizers like the $k$-support-norm.
- Blended Conditional Gradients (BCG): To avoid the high computational cost of full re-optimization, Braun et al. introduced a method that blends standard LMO steps with projection-free simplex gradient descent steps over the active vertices, maintaining high solution sparsity while converging linearly.
- Quadratic Corrections and Gradient Chasing: Rather than relying on a single weak descent direction from one LMO query, Pokutta designed a "gradient chasing" subroutine via matching pursuit to build highly aligned descent directions. Similarly, Halbey et al. introduced efficient quadratic corrections that solve small linear systems to accelerate convergence without expensive sub-optimization.
Exploiting the Geometry of the Constraint Set
The zig-zagging phenomenon is fundamentally a consequence of the "pointiness" of polytopes. If the constraint set has no sharp vertices, the behavior of the LMO changes entirely.
d'Aspremont et al. analyzed Frank-Wolfe optimization on uniformly convex sets (such as $\ell_p$-balls for $p > 2$). Because the boundaries of these sets are smoothly curved rather than flat, a small shift in the gradient results in a small, continuous shift in the vertex returned by the LMO.
Polytopal Set (Pointy) Uniformly Convex Set (Curved)
LMO jumps discretely LMO moves continuously
/\ .--.
/ \ / \
/____\ '------'
The authors proved that this curvature naturally prevents the worst-case zig-zagging behavior. On these curved geometries, the standard Frank-Wolfe algorithm automatically accelerates to faster intermediate or linear convergence rates without needing away-steps, active sets, or extra memory.
Structural and Block-Level Acceleration
For large-scale matrix problems, such as matrix completion or structured low-rank matrix minimization, the sublinear bottleneck often manifests because a standard LMO only returns a rank-one update (the top singular vectors). Bouncing between individual rank-one components makes it incredibly slow to learn a high-rank target matrix.
To resolve this, researchers have looked at expanding the scope of the oracle or reformulating the optimization space:
- Block Updates: Allen-Zhu et al. introduced
blockFWfor optimization over trace-norm balls. Instead of querying the top single singular vector, their algorithm queries a block-LMO to compute the top-$k$ singular vectors simultaneously. This richer directional information breaks the sublinear barrier, yielding true linear convergence. - Primal-Dual Block Updates: For sparse and low-rank problems like Elastic Net, Zhuo et al. proposed a Primal-Dual Block Frank-Wolfe algorithm. By performing partial, coordinate-aligned block updates, they achieved a linear convergence rate where the per-iteration cost scales only with the intrinsic sparsity or rank of the solution, completely bypassing the full feature dimension.
- Greedy Pursuit: In matrix completion, Wang et al. developed Rank-One Matrix Pursuit (R1MP), which treats rank-one matrices as a basis set and greedily refines their weights, achieving linear convergence by reframing the projection-free step as an iterative refinement process.
By matching the correction mechanism to the underlying geometry—whether through away-steps on polytopes, leveraging natural boundary curvature, or expanding to block-level oracles—modern projection-free optimization successfully bridges the gap between cheap per-iteration costs and fast, high-precision convergence.
Key Foundational Work
Sparse Convex Optimization Methods for Machine Learning (2011) — contributed 2 concept elements to this direction.
Lower Bounds for BMRM and Faster Rates for Training SVMs (2009) — contributed 1 concept elements to this direction.