The Frank-Wolfe Algorithm

Imagine you want to minimize a smooth function over a constrained set — say, pick the best portfolio of stocks subject to a budget. The standard gradient-descent recipe says: step opposite the gradient, then project back onto the feasible region. Easy to say, brutal to do — projecting onto complicated sets is itself an expensive optimization problem.

In 1956, Marguerite Frank and Philip Wolfe proposed a radical shortcut: instead of projecting, ask a simpler question. Where in the feasible set does the linear approximation of the objective reach its minimum? That is just a linear program over the constraint set — often trivially solved by inspection. Then blend the current point toward that vertex. No projection, ever.

The resulting algorithm — variously called Frank-Wolfe, the conditional gradient method, or the linearized Bregman method — trades a slower convergence rate for an enormous structural gift: the expensive projection oracle is simply not needed. When the feasible set has special structure (a simplex, a spectrahedron, a flow polytope), the linear subproblem can be solved in near-linear time while a full projection would cost orders of magnitude more.

Frank-Wolfe was largely forgotten for decades once interior-point methods arrived, but its revival in the 2000s and 2010s — driven by machine learning workloads that involve nuclear-norm balls, traffic assignment, and structured sparsity — placed it back at the frontier of large-scale optimization.

Below is Frank-Wolfe running on a quadratic objective minimized over a triangle (a 2-simplex). The shaded ellipses are level curves of the loss; the triangle is the feasible region. Each iteration finds the vertex of the triangle where the gradient points most steeply downward, then moves toward it with a fixed step size.

<div class="controls">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="info" class="info"></span>
</div>
<canvas id="canvas" width="400" height="360"></canvas>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; align-items: center; gap: .45rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.info { font-size: .85rem; color: #555; margin-left: .3rem; }
canvas { display: block; border: 1px solid #dde3ea; border-radius: 8px; max-width: 100%; }
.log { font: .8rem/1.55 ui-monospace, monospace; color: #444; max-height: 100px;
       overflow-y: auto; margin-top: .4rem; background: #f6f8fa; border-radius: 6px;
       padding: .35rem .6rem; }

// Code not found

Notice the zig-zag pattern: because each step is attracted to a vertex of the feasible polytope, the iterates bounce between corners before settling near the true minimum. This is Frank-Wolfe's signature behavior — and also its main weakness: the zig-zagging slows convergence compared to gradient descent with projection. The trade-off is that each step costs far less.

Press Reset to restart from the initial point, or drag the target point (the star) to explore different optima. Compare linear programming to see why finding a vertex of a polytope is so cheap.

Frank-Wolfe belongs firmly in the solved camp: its convergence is fully understood, with both upper and lower bounds tight.

• Convergence rate: $O(1/k)$. After k iterations, the suboptimality gap is at most O(L·$diam^{2}$/k), where L is the Lipschitz constant of the gradient and diam is the diameter of the feasible set. Proved by Frank and Wolfe in their 1956 paper and tightened by subsequent work.
• Each iteration costs one gradient evaluation plus one linear minimization over the feasible set — the linear oracle. For polytopes this is an LP with structure; for a simplex it reduces to finding the minimum-gradient coordinate; for a spectrahedron it is a leading eigenvector computation.
• Slower than projected gradient descent. Standard projected gradient descent achieves $O(1/k)$ too, but with a smaller constant — and accelerated variants reach $O(1/k^{2})$. Frank-Wolfe cannot be accelerated beyond $O(1/k)$ for general convex objectives without further assumptions (a proven lower bound).
• Away-step and pairwise variants (Lacoste-Julien & Jaggi, 2015) achieve linear convergence (exponential in k) on strongly convex problems with polytope constraints, recovering the speed advantage while keeping the projection-free property.
• Sparsity of iterates. Because each step moves toward a vertex, Frank-Wolfe solutions are always sparse convex combinations of at most k+1 vertices after k steps. This is not just a nicety — in machine learning it means structured, interpretable solutions automatically.

The algorithm's status: solved and well-characterized. The open questions are about tighter constants, fine-grained oracle complexity, and whether gap-free analysis extends to non-convex settings.

Frank-Wolfe's projection-free nature is decisive whenever the feasible set is easier to optimize a linear function over than to project onto:

• Traffic assignment (Beckmann model): Routing traffic on a road network minimizes a separable convex cost. The linear oracle is just shortest-path computation — trivial. Projection onto the flow polytope is far harder. Frank-Wolfe has been the standard solver here since the 1970s.
• Nuclear-norm regularization (matrix completion): Minimizing over the nuclear-norm ball means the linear oracle is a leading singular-vector computation — $O(mn)$ per step. Projection requires full SVD at O(mn·min(m,n)). Frank-Wolfe wins by orders of magnitude on large matrices.
• Structural SVM and learning with structured outputs: The feasible set of valid label assignments defines a combinatorial polytope. Frank-Wolfe's linear oracle is finding the highest-scoring label structure — exactly what a standard decoder does.
• Video object co-localization: Joint optimization over bounding boxes in multiple frames is a quadratic program whose linear oracle is an easy box search.
• Neural network compression: Weights constrained to a low-rank or sparse polytope can be optimized with Frank-Wolfe without expensive projection steps.

Whenever you see a constrained optimization problem where the domain has combinatorial or spectral structure, the first question worth asking is: "how hard is the linear subproblem?" If the answer is "easy," Frank-Wolfe is the right tool — even compared to methods like linear programming that handle the global problem at once.

Frank-Wolfe is a masterclass in trading one hard operation for an easier one. By replacing the projection step with a linear minimization — often a hundred times cheaper — it opens up entire classes of large-scale problems that would otherwise be inaccessible.

The zig-zag path is not a bug. It is the geometric signature of an algorithm that lives at the vertices of the feasible set, producing sparse, structured solutions almost for free. When you next encounter a constrained optimization problem where the feasible region has rich combinatorial structure, remember: the best move might not be to project — it might be to ask which direction is cheapest, and just lean that way.

Explore the companion article on linear programming to see why solving a linear subproblem over a polytope is so much cheaper than you might expect.