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:

x∈Cmin​f(x)

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:

xt+1​=ΠC​(xt​−ηt​∇f(xt​))

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:

st​=args∈Cmin​⟨∇f(xt​),s⟩

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:

xt+1​=(1−γt​)xt​+γt​st​

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:

gt​=⟨∇f(xt​),xt​−st​⟩

Because f is convex, the gap upper bounds the suboptimality:

f(xt​)−f(x∗)≤gt​

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:

∣x∣1​≤Rmin​21​∣Ax−b∣22​

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​Source:https://dev.to/umeshtharukaofficial/frank-wolfe-why-linear-oracles-beat-projections-on-constrained-problems-2me6