1. The Problem Frank–Wolfe Is Designed For
Frank–Wolfe (FW), also called the conditional gradient method, solves constrained smooth convex optimization problems min_{x∈D} f(x) when projecting onto D is expensive but minimizing a linear function over D is easy. Instead of taking a gradient step and projecting back, FW asks a linear minimization oracle for an extreme feasible direction and moves toward it by a convex combination.
Key points
- FW is not 'better gradient descent' in general; it exploits a specific feasible-set geometry.
- Typical domains include simplices, ℓ1 balls, flow polytopes, matroid polytopes, and nuclear-norm balls.
- The method is especially attractive when sparse/low-rank iterates are valuable.
2. Why Projection Can Be the Bottleneck
Projected gradient descent computes y_t=x_t−η∇f(x_t) and then solves a projection problem min_{x∈D} ‖x−y_t‖². For simple boxes this projection is trivial, but for structured domains it may require a full optimization or matrix decomposition. FW replaces this potentially expensive projection by a linear optimization problem over the same domain.
Key points
- On an ℓ1 ball, Euclidean projection requires thresholding/sorting-like operations, while the LMO simply chooses one signed coordinate.
- On a nuclear-norm ball, projection needs a full or large SVD, while the LMO only needs a leading singular-vector pair.
3. Linear Minimization Oracle: The Key Primitive
At x_t, convexity suggests that the gradient is the local direction of increase. FW therefore solves s_t=argmin_{s∈D}⟨∇f(x_t),s⟩, asking which feasible point looks best under the first-order linear approximation. Because a linear objective over a compact convex polytope achieves its optimum at an extreme point, s_t is often an atom or vertex of D.
Key points
- The LMO depends only on the feasible set and the current gradient, so it can often exploit specialized combinatorial solvers.
- For the probability simplex, the LMO chooses the coordinate with the smallest gradient component.
- For a flow polytope, the LMO may reduce to a shortest-path or min-cost-flow problem.
4. Basic Frank–Wolfe Iteration
After the LMO returns s_t, define direction d_t=s_t−x_t and move x_{t+1}=x_t+γ_t d_t with γ_t∈[0,1]. Because x_{t+1} is a convex combination of two feasible points, it stays feasible automatically. This is the projection-free property. Starting from a feasible x_0, every iterate is feasible without solving any projection problem.
Key points
- One FW step adds at most one new atom to the active representation.
- This incremental representation is why FW often produces sparse mixtures or low-rank matrices early.
- If γ_t=1, the previous point is discarded and x_{t+1}=s_t; smaller γ keeps history through the convex combination.
5. Step Size: Predefined Schedule vs Line Search
The step size controls how much weight is transferred toward the new atom. A classical theoretical schedule is γ_t=2/(t+2). Exact line search chooses γ∈[0,1] minimizing f(x_t+γd_t), which can be very effective when the one-dimensional problem is cheap. Adaptive rules based on smoothness estimates are useful when exact line search is unavailable.
Key points
- Too small a step wastes LMO calls; too large a step can bounce between vertices.
- For a quadratic objective, line search often has a closed-form clipped scalar solution.
- Step-size choice affects constants and practical speed, but the geometry of the feasible set often dominates long-run behavior.
6. Frank–Wolfe Gap: A Computable Optimality Certificate
The FW gap is g_FW(x_t)=⟨∇f(x_t),x_t−s_t⟩. Because s_t minimizes the linearized objective over D, convexity implies f(x_t)−f(x*)≤g_FW(x_t). Therefore the gap is both a stationarity measure and an upper bound on primal suboptimality for convex f. Crucially, it comes almost for free because s_t is already computed by the LMO.
Key points
- A small objective change between iterations is not a reliable stopping rule; the FW gap has a clearer optimization meaning.
- For nonconvex smooth objectives, a FW-type gap can still measure first-order stationarity, but the global suboptimality bound no longer follows.
7. Why Classical FW Converges at O(1/t)
For smooth convex f over a compact convex domain, curvature controls how inaccurate the first-order model becomes when moving toward s_t. Combining the descent lemma with the LMO property yields a recurrence on the objective error h_t=f(x_t)−f(x*). With the classical step size, this gives h_t=O(1/t). The key point is that the method makes guaranteed progress without projections, but classical FW does not generally enjoy linear convergence on polytopes because it may have difficulty removing weight from previously chosen atoms.
Key points
- The curvature constant C_f combines objective smoothness and domain diameter in an affine-invariant way.
- O(1/t) means halving the optimization error may require roughly doubling the iteration count in the asymptotic regime.
- Whether FW is practically faster than projected methods depends on cost per iteration, not just iteration complexity.
8. Active Sets, Sparsity, and the Zig-Zag Problem
If D is the convex hull of atoms, an FW iterate can be represented as x_t=Σ_{v∈S_t} α_v v with nonnegative weights summing to one. The active set S_t stores atoms selected so far. This makes sparsity explicit, but classical FW can only move toward a new atom; it has no dedicated mechanism to quickly remove a bad old atom. Near a boundary optimum this can cause zig-zagging and slow progress.
Key points
- After t iterations, the representation uses at most t+1 atoms if no corrective compression is performed.
- This property is attractive for sparse mixtures, structured prediction, and low-rank matrix construction.
- The same sparsity can slow convergence when the correct optimum requires reducing coefficients on previously selected atoms.
9. Away-Step, Pairwise, and Fully Corrective FW
Away-step FW adds a second option: instead of moving toward a new atom, move away from an active atom whose gradient contribution is worst. Pairwise FW transfers weight directly from a bad active atom to the new LMO atom. Fully corrective FW periodically re-optimizes all active coefficients. These variants fix the main weakness of classical FW and can achieve linear convergence on suitable polytopes under stronger assumptions.
Key points
- Away steps have a maximum feasible step because an active coefficient cannot become negative.
- Pairwise FW often changes support more aggressively than classical FW.
- Fully corrective methods may reduce iteration count but require a nontrivial subproblem over the current active set.
10. Important Structured Examples
FW becomes most intuitive when the LMO has a concrete structure. On the simplex, the LMO returns one basis vector, so iterates are sparse probability mixtures. On an ℓ1 ball, it returns one signed coordinate, yielding sparse vectors. On a nuclear-norm ball, it returns a rank-one matrix from the leading singular vectors, so every iteration increases rank by at most one. These are not side examples—they explain why projection-free methods are used in large structured optimization.
Key points
- Simplex D={x≥0, Σx_i=1}: choose e_j with j=argmin_i ∇_i f(x).
- ℓ1 ball ‖x‖_1≤τ: choose s=−τ sign(∇_j f)e_j where j has the largest absolute gradient.
- Nuclear-norm ball ‖X‖_*≤τ: choose s=−τ u_1v_1^T from the top singular vectors of ∇f(X).
11. Stochastic, Block-Coordinate, and Large-Scale Variants
Large learning problems may make a full gradient or a global LMO expensive. Stochastic FW uses sampled gradients, block-coordinate FW updates only one subset of variables/atoms, and lazy/cached variants reuse previous LMO solutions when they remain sufficiently good. The algorithmic design should target whichever operation—gradient computation, LMO, communication, or active-set maintenance—is the actual bottleneck.
Key points
- Approximate LMOs can still preserve convergence if their approximation error is controlled relative to progress requirements.
- Distributed FW is attractive when the LMO decomposes across agents or data blocks, but communication can dominate.
- For matrix problems, randomized leading singular-vector methods can accelerate the LMO dramatically.
12. When to Use Frank–Wolfe: Decision and Debugging Guide
Choose FW when the feasible set has a cheap linear optimization oracle, projection is significantly more expensive, and sparse/extreme-point structure is useful. Do not choose it merely because the problem has constraints. If projection is trivial, projected gradient or proximal methods may be faster. If classical FW stagnates near the boundary, inspect the active set and try away-step or pairwise variants before concluding that the entire projection-free approach is unsuitable.
Key points
- Monitor objective value, FW gap, LMO time, step size, and active-set size separately.
- If the gap is large but objective barely changes, the step-size rule may be too conservative.
- If the LMO dominates runtime, improving the oracle may matter more than changing the outer FW variant.
- If active-set size grows too much, use corrective steps, atom dropping, or compression strategies.
What you should remember
After this note, you should be able to derive the FW step, build an LMO for common domains, use the FW gap as a stopping certificate, explain the O(1/t) rate, and know when away-step or pairwise variants are needed.