Frank-Wolfe: Why Linear Oracles Beat Projections on Constrained Problems
Constrained optimisation has a quiet asymmetry. Taking a gradient step is usually easy. Staying inside the feasible set is often the hard part. Projected gradient descent assumes you can project any point back onto the s
Constrained optimisation has a quiet asymmetry. Taking a gradient step is usually easy. Staying inside the feasible set is often the hard part. Projected gradient descent assumes you can project any point back onto the set cheaply. For many sets that matter in machine learning, you cannot. The Frank-Wolfe algorithm, also called the conditional gradient method, replaces the projection with something much cheaper: minimising a linear function over the same set.
That one substitution changes which problems are tractable. It also changes the structure of the iterates, in a way that is useful for sparsity, low rank structure, and large scale problems where a projection would be a bottleneck.
The problem
Consider minimising a smooth convex function over a compact convex set:
Here f is convex and differentiable, and C is a compact convex set. The classic example is minimising a loss subject to an L1β ball constraint, a nuclear norm ball constraint, or a flow polytope constraint.
Projected gradient descent iterates as follows:
The projection Ξ Cβ finds the closest point in C to its argument. For a Euclidean ball, that is trivial. For a nuclear norm ball, it requires a full singular value decomposition at every step. For a flow polytope, it requires solving a quadratic program. In both cases, the projection can dominate the cost of the whole algorithm, even though the gradient itself is cheap.
Frank-Wolfe asks a different question at each step. Instead of asking where the closest feasible point is, it asks which feasible point is most aligned with the negative gradient. That is a linear minimisation problem, and for many structured sets it is far cheaper than a projection.
The linear minimisation oracle
Define the linear minimisation oracle, often shortened to LMO, as:
The oracle returns a feasible point that minimises the linear approximation to f at xtβ . Geometrically, it finds the point in C that points most strongly in the descent direction.
Why is this cheaper? Consider three examples.
First, the L1β ball, defined by β£xβ£1ββ€R . Minimising a linear function over this ball has a closed form: put all the mass on the coordinate where the gradient has the largest absolute value, with the opposite sign. No sorting beyond finding a maximum is needed, and no iterative solver is involved.
Second, the nuclear norm ball, defined by matrices whose singular values sum to at most R . Minimising a linear function over this ball requires only the top left and right singular vectors of the gradient matrix, which can be approximated with a few power iterations. A projection onto the same ball would require the full singular value decomposition.
Third, a flow polytope or a spanning tree polytope. Minimising a linear function over such a set is a shortest path or minimum spanning tree problem, both of which have fast combinatorial algorithms. Projecting onto the same set has no such shortcut.
The pattern is general: linear optimisation over a structured set is often combinatorially simple, while Euclidean projection onto the same set is not. Frank-Wolfe exploits exactly that gap.
The algorithm
Given the oracle point stβ , Frank-Wolfe does not jump to it. It moves a fraction of the way toward it:
The step size Ξ³tβ lies in [0,1] . Because xtβ and stβ are both in the convex set C , any convex combination of them is also in C . Feasibility is therefore automatic. There is no projection step, no correction step, and no need to check whether the iterate has left the set.
A standard choice is Ξ³tβ=2/(t+2) . This requires no line search and no knowledge of the smoothness constant. Alternatively, Ξ³tβ can be chosen by exact line search along the segment from xtβ to stβ , which is a one dimensional problem and is often worth the small extra cost.
In code, the skeleton is short:
def frank_wolfe(grad, lmo, x0, steps):
x = x0
for t in range(steps):
g = grad(x)
s = lmo(g) # linear minimisation over C
gamma = 2.0 / (t + 2)
x = (1.0 - gamma) * x + gamma * s
return x
The whole algorithm is the gradient, the oracle, and a convex combination. Everything else is a variant that improves the rate or the structure of the iterates.
A built in stopping certificate
Frank-Wolfe also gives a free measure of progress. The Frank-Wolfe gap at xtβ is:
Because f is convex, the gap upper bounds the suboptimality:
where xβ is a minimiser. This is unusually convenient. Most first order methods require a separate argument to bound how far the current point is from optimal. Frank-Wolfe computes a valid upper bound as a byproduct of the oracle call, since stβ is already available. In practice, the gap is a principled stopping criterion: stop when gtβ falls below a tolerance, and you have a certificate that the objective is within that tolerance of optimal.
Why the iterates are sparse or low rank
The convex combination update has a structural consequence that projected methods do not share. Suppose x0β is a vertex of C , or more generally a combination of a few vertices. Each oracle call adds at most one new vertex, namely stβ . After t steps, xtβ is a convex combination of at most t+1 vertices.
For the L1β ball, the vertices are signed coordinate vectors, so xtβ has at most t+1 nonzero coordinates. The algorithm builds sparsity incrementally, rather than imposing it through thresholding. For the nuclear norm ball, the vertices are rank one matrices, so xtβ has rank at most t+1 . The algorithm builds a low rank solution one rank one update at a time.
This is the same intuition behind matching pursuit and greedy basis selection, and it is a genuine advantage when the solution is expected to be sparse or low rank. A projected method can also produce such solutions, but it typically does so by projecting a dense iterate, which destroys the incremental structure and costs a full decomposition at each step.
Convergence, and its honest rate
For a smooth convex objective, Frank-Wolfe with the step size Ξ³tβ=2/(t+2) converges at a rate of order 1/t in function value. More precisely, the suboptimality after t steps is bounded by a constant divided by t , where the constant depends on the smoothness of f and the diameter of C .
That rate is slower than the accelerated rates available for projected gradient methods on well conditioned problems. This is the honest trade. Frank-Wolfe trades a faster rate for a cheaper iteration and for structured iterates. When the projection is expensive, the cheaper iteration wins in wall clock time even if it needs more steps. When the projection is cheap, projected gradient or accelerated methods are usually the better choice.
The rate also has a known weakness: zigzagging. As the iterates approach the optimum, the oracle point can oscillate between vertices, and the algorithm makes small progress along a segment that repeatedly revisits similar directions. This is not a bug in the implementation. It is a property of moving toward extreme points of the set.
Variants that fix the zigzag
Several variants address zigzagging without giving up the projection free structure.
Away step Frank-Wolfe maintains the explicit convex combination of vertices that defines xtβ . At each step it considers two moves: a standard Frank-Wolfe step toward a new vertex, and an away step that moves away from a vertex currently in the combination, reducing its weight. Choosing the better of the two lets the algorithm drop bad vertices instead of slowly diluting them, and it can give linear convergence when the optimum lies on a face of the set and the objective is strongly convex in the relevant directions.
Pairwise Frank-Wolfe combines both moves into a single step that shifts weight directly from the worst active vertex to the best new vertex. Fully corrective Frank-Wolfe goes further and reoptimises the weights over all vertices collected so far at each step, at the cost of a small subproblem over the active set.
These variants keep the same oracle interface. They change only how the convex combination is updated. That modularity is part of why Frank-Wolfe remains a useful framework rather than a single algorithm: new sets need only a new oracle, and new update rules plug into the same loop.
A practical example: sparse regression
Consider least squares with an L1β constraint:
The gradient is AT(Axβb) . The oracle picks the coordinate j where the gradient entry has the largest absolute value, and returns βRβ sign(gjβ)ejβ , where ejβ is the j th coordinate vector. Each step therefore activates at most one new coordinate. After a modest number of steps, the iterate is a sparse vector whose support was chosen greedily by gradient magnitude.
Contrast this with projected gradient descent on the same problem, which would require projecting onto the L1β ball at every step. That projection is not prohibitively expensive, but it touches every coordinate and it does not preserve the greedy support structure. For larger structured problems, such as matrix completion with a nuclear norm constraint, the difference is between a top singular vector computation and a full singular value decomposition at every iteration. That difference is often the difference between a feasible algorithm and an impractical one.
Limitations and common pitfalls
First, Frank-Wolfe is not a general purpose replacement for projected methods. If the projection is cheap, use it. The 1/t rate is a real cost, and on problems where a projection costs almost nothing, it is hard to justify giving up acceleration.
Second, the basic method can be slow in the tail. The gap shrinks steadily, but the last digits of accuracy can take many steps when zigzagging sets in. If high accuracy is required, use an away step or pairwise variant, or switch to a method that can take larger steps near the optimum.
Third, the oracle must be exact, or at least accurate enough, for the gap certificate to be valid. An approximate oracle, such as a few power iterations for the top singular vector, gives an approximate gap. That is often fine in practice, but it should not be reported as an exact certificate.
Fourth, the step size matters more than it looks. The simple 2/(t+2) schedule is safe but conservative. Line search along the segment usually performs noticeably better and costs little, because the segment is one dimensional. Skipping line search out of habit leaves performance on the table.
Finally, do not confuse the Frank-Wolfe gap with the gradient norm. A small gradient does not imply a small gap on a constrained problem, because the optimum may lie on the boundary where the gradient is nonzero. The gap accounts for the constraint geometry. The gradient norm alone does not.
When to reach for it
Reach for Frank-Wolfe when three conditions hold together. The feasible set is convex and compact, minimising a linear function over it is substantially cheaper than projecting onto it, and a sparse or low rank or otherwise vertex structured solution is desirable. Matrix completion, sparse regression with a hard L1β budget, video co-localisation, and structured prediction with a combinatorial polytope are the canonical cases.
If any of those conditions fails, the case weakens. If the set is a simple ball or box, projection is cheap. If the solution is dense, the vertex structure buys nothing. If the oracle itself requires solving a hard problem, the whole advantage disappears.
The deeper lesson is about algorithm design. Many optimisation methods are built around one expensive operation, usually a projection or a matrix factorisation. Frank-Wolfe shows that replacing that operation with a weaker but cheaper one, a linear minimisation, can change the economics of the problem entirely. The method is old, dating to the 1950s, and it survives because that economic argument keeps recurring whenever a new structured set appears.
Takeaway
Frank-Wolfe replaces projection with linear minimisation. Each iteration asks the oracle for the feasible point most aligned with the descent direction, then moves part of the way toward it. Feasibility is automatic, the gap gives a free optimality certificate, and the iterates inherit sparsity or low rank structure from the vertices they combine. The price is a slower 1/t rate and possible zigzagging, both mitigated by away step and pairwise variants. When projection is the bottleneck, that trade is often the right one.
Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial
Originally published by Dev.to AI. Aggregated on AIWithGhost for educational purposes β full credit and traffic to the original publisher.