DEV Community

Umesh Tharuka Malaviarachchi
Umesh Tharuka Malaviarachchi

Posted on

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 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:

min⁡x∈Cf(x) \min_{x \in \mathcal{C}} f(x)

Here ff is convex and differentiable, and C\mathcal{C} is a compact convex set. The classic example is minimising a loss subject to an L1L_1 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)) x_{t+1} = \Pi_{\mathcal{C}}(x_t - \eta_t \nabla f(x_t))

The projection ΠC\Pi_{\mathcal{C}} finds the closest point in C\mathcal{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=arg⁡min⁡s∈C⟨∇f(xt),s⟩ s_t = \arg\min_{s \in \mathcal{C}} \langle \nabla f(x_t), s \rangle

The oracle returns a feasible point that minimises the linear approximation to ff at xtx_t . Geometrically, it finds the point in C\mathcal{C} that points most strongly in the descent direction.

Why is this cheaper? Consider three examples.

First, the L1L_1 ball, defined by ∣x∣1≤R|x|_1 \leq 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 RR . 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 sts_t , Frank-Wolfe does not jump to it. It moves a fraction of the way toward it:

xt+1=(1−γt)xt+γtst x_{t+1} = (1 - \gamma_t) x_t + \gamma_t s_t

The step size γt\gamma_t lies in [0,1][0, 1] . Because xtx_t and sts_t are both in the convex set C\mathcal{C} , any convex combination of them is also in C\mathcal{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)\gamma_t = 2 / (t + 2) . This requires no line search and no knowledge of the smoothness constant. Alternatively, γt\gamma_t can be chosen by exact line search along the segment from xtx_t to sts_t , 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
Enter fullscreen mode Exit fullscreen mode

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 xtx_t is:

gt=⟨∇f(xt),xt−st⟩ g_t = \langle \nabla f(x_t), x_t - s_t \rangle

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

f(xt)−f(x∗)≤gt f(x_t) - f(x^{*}) \leq g_t

where x∗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 sts_t is already available. In practice, the gap is a principled stopping criterion: stop when gtg_t 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 x0x_0 is a vertex of C\mathcal{C} , or more generally a combination of a few vertices. Each oracle call adds at most one new vertex, namely sts_t . After tt steps, xtx_t is a convex combination of at most t+1t + 1 vertices.

For the L1L_1 ball, the vertices are signed coordinate vectors, so xtx_t has at most t+1t + 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 xtx_t has rank at most t+1t + 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)\gamma_t = 2 / (t + 2) converges at a rate of order 1/t1 / t in function value. More precisely, the suboptimality after tt steps is bounded by a constant divided by tt , where the constant depends on the smoothness of ff and the diameter of C\mathcal{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 xtx_t . 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 L1L_1 constraint:

min⁡∣x∣1≤R12∣Ax−b∣22 \min_{|x|_1 \leq R} \frac{1}{2} |A x - b|_2^2

The gradient is AT(Ax−b)A^T (A x - b) . The oracle picks the coordinate jj where the gradient entry has the largest absolute value, and returns −R⋅sign(gj)ej-R \cdot \mathrm{sign}(g_j) e_j , where eje_j is the jj 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 L1L_1 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/t1 / 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)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 L1L_1 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/t1 / 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

Top comments (0)