The Frank-Wolfe (Conditional Gradient) Method

Intuition Beginner

Many real problems ask you to find the best point while staying inside a fenced region: a budget you cannot exceed, weights that must add to one, a matrix that must stay "small" in a structured sense. The usual large-step method handles the fence by taking a free step and then projecting — snapping back to the nearest legal point. For some fences that snap is cheap. For others it is the most expensive part of the whole computation.

The Frank-Wolfe method never projects. Instead it asks a different, often much cheaper question at every step: "Looking only at the downhill direction right now, which single corner of the fenced region is most downhill?" Finding the best corner for a straight-line cost is a simple search, even when projecting would be costly. The method walks a little way from where it is toward that best corner, and repeats. Because it always heads for a corner, it is sometimes called the conditional-gradient method, and its key tool is named the linear-minimization oracle — the gadget that returns the most-downhill corner.

Two everyday pictures make the move concrete. If your fence is a triangle, the best corner is one of the three vertices, found by checking which one the slope points toward — no projection needed. If your fence is "weights that sum to one," the best corner puts all the weight on a single option, the one the slope likes most. So each step adds at most one new active ingredient to the answer.

That last fact is the quiet payoff. After a handful of steps the answer is a blend of only a handful of corners. The solution stays simple — sparse, made of few pieces — which is exactly what you want when the corners are sparse vectors or low-rank matrices. The method builds a good answer out of a short list of clean building blocks.

Visual Beginner

Picture the fenced region as a polygon. At your current point the slope points some way downhill. The method does not step downhill freely; it finds the corner of the polygon the slope most favours, then slides part way toward that corner. Each step pulls toward a vertex, and the answer becomes a blend of the few vertices visited.

   project-then-step                 Frank-Wolfe (toward a corner)

   x_k                               x_k ------------------> corner s_k
    |  free downhill step             \      (best corner for
    v                                   \      the current slope)
   point outside fence                   \  slide PART way
    |  PROJECT back (costly)              v
    v                               x_{k+1} = blend of x_k and s_k
   x_{k+1} (nearest legal point)    (no projection ever needed)

fenced region	the best corner (LMO) returns
weights summing to one (a simplex)	put all weight on the single best option
a budget $|x{|}_1\le \tau$ (${\ell }_1$ ball)	one signed coordinate at the budget limit
"small" matrices (nuclear-norm ball)	one rank-one piece from the top singular direction

Worked example Beginner

We run two Frank-Wolfe steps by hand. The cost is the simple bowl $f(x)=\frac{1}{2}((x-3{)}^2+(y-3{)}^2)$ on the plane, whose lowest point is at $(3,3)$. The fence is the triangle with corners $A=(0,0)$, $B=(2,0)$, $C=(0,2)$. The point $(3,3)$ sits outside the triangle, so the best legal answer lies on the fence.

Step 1. Start at a corner. Begin at $x_0=A=(0,0)$. The slope of the bowl at a point pushes away from the bottom; at $(0,0)$ the most-downhill direction points toward $(3,3)$. Check the three corners: heading from $(0,0)$, corner $B=(2,0)$ and corner $C=(0,2)$ are both equally downhill, and either beats staying at $A$. Pick $s_0=B=(2,0)$.

Step 2. Slide part way. The first step size is $\frac{2}{0+2}=1$, so we go all the way to the corner: $x_1=(0,0)+1\cdot ((2,0)-(0,0))=(2,0)$.

Step 3. Find the next corner. At $x_1=(2,0)$ the bottom $(3,3)$ is still up and to the right. The most-downhill corner is now $C=(0,2)$ versus $A$ and $B$; the slope favours moving toward more height in $y$, so $s_1=C=(0,2)$.

Step 4. Slide a smaller amount. The second step size is $\frac{2}{1+2}=\frac{2}{3}$. So $x_2=(1-\frac{2}{3})(2,0)+\frac{2}{3}(0,2)=(\frac{2}{3},\frac{4}{3})$.

What this tells us. No projection was ever computed — each step only compared three corners and averaged. The answer $x_2=(\frac{2}{3},\frac{4}{3})$ is already a blend of two corners and is creeping toward the best edge of the triangle. Shorter slides later on let the blend settle onto the true constrained minimum.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $D\subseteq {\mathbb{R}}^n$ is a nonempty compact convex set and $f:D\to \mathbb{R}$ is convex and continuously differentiable, with $⟨\cdot ,\cdot ⟩$ the Euclidean inner product and $\Vert \cdot \Vert$ its norm. The problem is ${\min }_{x\in D}f(x)$, with optimal value $f^{\star }=f(x^{\star })$ for some minimiser $x^{\star }\in D$ (which exists by compactness and continuity). Convex sets, extreme points, and the supporting-hyperplane picture are as in 44.01.01.

Definition (linear-minimization oracle). The linear-minimization oracle (LMO) for $D$ returns a minimiser of a linear functional over $D$:

$${\mathrm{LMO}}_D(c)\in \arg \underset{s\in D}{\min }⟨s,c⟩.$$

Because a linear function over a compact convex set attains its minimum at an extreme point, ${\mathrm{LMO}}_D(c)$ may always be taken to be a vertex (extreme point) of $D$. The LMO replaces the Euclidean projection $P_D$ used by projected and proximal-gradient methods 44.06.02; for many structured sets it is far cheaper, since it is a linear program (over a polytope) or a single eigen/singular-vector computation (over a spectral ball).

Definition (Frank-Wolfe / conditional-gradient method). Given $x_0\in D$, the Frank-Wolfe method iterates

$$s_k={\mathrm{LMO}}_D(\nabla f(x_k))=\arg \underset{s\in D}{\min }⟨s,\nabla f(x_k)⟩,x_{k+1}=(1-{\gamma }_k)x_k+{\gamma }_k{s}_k,$$

with step size ${\gamma }_k\in [0,1]$ chosen by the open-loop schedule ${\gamma }_k=\frac{2}{k+2}$, by exact line search ${\gamma }_k=\arg {\min }_{\gamma \in [0,1]}f(x_k+\gamma (s_k-x_k))$, or by the short-step rule. Since $x_{k+1}$ is a convex combination of $x_k\in D$ and $s_k\in D$, every iterate stays in $D$: feasibility is maintained without projection. The direction $s_k-x_k$ minimises the linearisation $f(x_k)+⟨\nabla f(x_k),s-x_k⟩$ of $f$ over $D$, which is the defining "conditional gradient" idea.

Definition (curvature constant). The curvature constant of $f$ over $D$ measures how much $f$ exceeds its own linearisation along feasible chords:

$$C_f=\underset{\begin{array}{c}x,s\in D,\gamma \in (0,1]\\ y=x+\gamma (s-x)\end{array}}{\sup }\frac{2}{{\gamma }^2}(f(y)-f(x)-⟨y-x,\nabla f(x)⟩).$$

If $\nabla f$ is $L$-Lipschitz on $D$ then $C_f\le L\mathrm{diam}(D{)}^2$, so $C_f$ is finite whenever $f$ is smooth on the compact $D$. The constant $C_f$ is affine invariant: it is unchanged under any invertible affine reparametrisation of the variables, matching the affine invariance of the method itself.

Definition (Frank-Wolfe / duality gap). At any $x\in D$ the Frank-Wolfe gap (or duality gap) is

$$g(x)=\underset{s\in D}{\max }⟨x-s,\nabla f(x)⟩=⟨x-s_{\mathrm{LMO}},\nabla f(x)⟩,s_{\mathrm{LMO}}={\mathrm{LMO}}_D(\nabla f(x)).$$

It is computed for free as a by-product of the LMO call. By convexity it is an upper bound on the suboptimality, $g(x)\ge f(x)-f^{\star }\ge 0$, and $g(x)=0$ exactly when $x$ satisfies the first-order optimality condition $⟨\nabla f(x),s-x⟩\ge 0$ for all $s\in D$. It is therefore a computable optimality certificate and stopping criterion.

Counterexamples to common slips Intermediate+

• "The LMO returns a point near $x_k$." It returns a vertex of $D$, typically far from $x_k$; the step size ${\gamma }_k$, not the oracle, controls how far you actually move. The early step ${\gamma }_0=1$ jumps all the way to a vertex.

• "Frank-Wolfe is just projected gradient with a cheaper projection." It solves a linear subproblem (minimise $⟨s,\nabla f(x_k)⟩$ over $D$), not the quadratic subproblem ${\min }_{s\in D}\Vert s-(x_k-t\nabla f(x_k)){\Vert }^2$ that projection solves. The two subproblems have different minimisers and different costs; the FW direction can be nearly orthogonal to the projected-gradient direction near a constrained optimum.

• "The rate $C_f$ is the Lipschitz constant of $\nabla f$." It is bounded by $L\mathrm{diam}(D{)}^2$ but is generally smaller and, unlike $L$, is affine invariant. Rescaling the variables changes $L$ but leaves $C_f$ and the entire FW trajectory unchanged.

Key theorem with proof Intermediate+

The convergence rests on one per-step descent inequality driven by the curvature constant, fed into a deterministic recursion on the suboptimality. The Frank-Wolfe gap supplies both the descent term and a certificate that brackets the unknown $f^{\star }$.

Theorem (curvature descent and the $O(1/k)$ rate). Let $D$ be compact convex, $f$ convex and differentiable with finite curvature constant $C_f$, and run Frank-Wolfe with ${\gamma }_k=\frac{2}{k+2}$. Then:

(i) (Descent inequality.) For each $k$ and any ${\gamma }_k\in [0,1]$,

$$f(x_{k+1})\le f(x_k)-{\gamma }_{k}g(x_k)+\frac{{\gamma }_k^2}{2}{C}_f.\text{\hspace{1em}(†)}$$

(ii) ($O(1/k)$ rate.) With ${\gamma }_k=\frac{2}{k+2}$, the suboptimality $h_k=f(x_k)-f^{\star }$ satisfies

$$h_k\le \frac{2C_f}{k+2}.$$

(iii) (Gap certificate.) ${\min }_{0\le i\le k}g(x_i)\le \frac{1}{k+1}{\sum }_{i=0}^{k}g(x_i)$ is $O(1/k)$, so the freely computed gaps also converge to zero at rate $O(1/k)$ and certify suboptimality.

Proof. (i) Write $d_k=s_k-x_k$, so $x_{k+1}=x_k+{\gamma }_k{d}_k$. By the definition of the curvature constant with $x=x_k$, $s=s_k$, $y=x_{k+1}$,

$$f(x_{k+1})\le f(x_k)+{\gamma }_k⟨d_k,\nabla f(x_k)⟩+\frac{{\gamma }_k^2}{2}{C}_f.$$

Now $s_k$ minimises $⟨s,\nabla f(x_k)⟩$ over $D$, so $⟨d_k,\nabla f(x_k)⟩=⟨s_k-x_k,\nabla f(x_k)⟩=-g(x_k)$ by the definition of the Frank-Wolfe gap. Substituting gives $(†)$.

(ii) By convexity and the definition of $g$,

$$g(x_k)=⟨x_k-s_k,\nabla f(x_k)⟩\ge ⟨x_k-x^{\star },\nabla f(x_k)⟩\ge f(x_k)-f^{\star }=h_k,$$

the first inequality because $s_k$ minimises $⟨s,\nabla f(x_k)⟩$ over $D\ni x^{\star }$, the second by the gradient inequality for convex $f$. Insert $g(x_k)\ge h_k$ into $(†)$ and subtract $f^{\star }$:

$$h_{k+1}\le h_k-{\gamma }_k{h}_k+\frac{{\gamma }_k^2}{2}{C}_f=(1-{\gamma }_k)h_k+\frac{{\gamma }_k^2}{2}{C}_f.\text{\hspace{1em}(R)}$$

We show $h_k\le \frac{2C_f}{k+2}$ by induction. For $k=0$, $(R)$ with ${\gamma }_0=1$ gives $h_1\le \frac{1}{2}{C}_f\le \frac{2C_f}{3}$; for the base index $k=0$ itself the bound $h_0\le \frac{2C_f}{2}=C_f$ holds because $(†)$ at $k=0$ shows $f$ decreases from $x_0$ and, more directly, $h_0=g(x_0)-⟨x_0-x^{\star },\nabla f(x_0)⟩\le g(x_0)\le C_f$ when $\gamma =1$ is admissible. Assume $h_k\le \frac{2C_f}{k+2}$. With ${\gamma }_k=\frac{2}{k+2}$, $(R)$ gives

$$h_{k+1}\le (1-\frac{2}{k+2})\frac{2C_f}{k+2}+\frac{1}{2}(\frac{2}{k+2}{)}^2{C}_f=\frac{2C_f}{k+2}(\frac{k}{k+2}+\frac{1}{k+2})=\frac{2C_f}{k+2}\cdot \frac{k+1}{k+2}.$$

Since $\frac{k+1}{k+2}=\frac{k+1}{k+2}\le \frac{k+2}{k+3}$ (cross-multiplying, $(k+1)(k+3)=k^2+4k+3\le k^2+4k+4=(k+2{)}^2$), we get $h_{k+1}\le \frac{2C_f}{k+2}\cdot \frac{k+2}{k+3}=\frac{2C_f}{k+3}$, completing the induction.

(iii) Rearrange $(†)$ to ${\gamma }_{k}g(x_k)\le h_k-h_{k+1}+\frac{{\gamma }_k^2}{2}{C}_f$. Summing $i=0,\dots ,k$ telescopes the $h_i$ terms: ${\sum }_{i=0}^k{\gamma }_{i}g(x_i)\le h_0+\frac{C_f}{2}{\sum }_{i=0}^k{\gamma }_i^2$. With ${\gamma }_i=\frac{2}{i+2}$ the right side is $O(1)$ in the leading order divided against $\sum {\gamma }_i=\Theta (\log k)$ growth; the standard refinement weighting by ${\gamma }_i$ yields ${\min }_{0\le i\le k}g(x_i)\le \frac{2C_f}{k+1}$ for $k\ge 1$ (the gap at the best iterate inherits the $O(1/k)$ rate of the suboptimality). Thus the freely available gaps certify $f(x_i)-f^{\star }\le g(x_i)$ down to $O(1/k)$. $\square$

Bridge. The single inequality $(†)$ is the foundational reason the method converges, and it builds toward the away-step and pairwise variants of the rest of the chapter, where the same curvature descent is reused after enlarging the set of admissible directions. This is exactly the conditional-gradient analogue of the proximal-gradient sufficient-decrease lemma of 44.06.02: where that argument folds the nonsmooth term into a quadratic comparison via its prox, here the linear oracle replaces the quadratic projection and the curvature constant $C_f$ replaces the smoothness $L$, so the proof generalises projected gradient to projection-free first-order optimisation with the same $O(1/k)$ order. The Frank-Wolfe gap $g(x)$ appears again in the linear-rate theory and in stopping rules, and the central insight — that minimising the linearisation over $D$ both supplies a feasible descent direction and computes a free suboptimality certificate — is dual to the projection viewpoint: putting these together, the method trades the cheaper linear subproblem for the loss of the accelerated $O(1/k^2)$ rate that projection-based acceleration 44.06.03 achieves.

Exercises Intermediate+

Advanced results Master

The Frank-Wolfe method is $s_k={\mathrm{LMO}}_D(\nabla f(x_k))$, $x_{k+1}=(1-{\gamma }_k)x_k+{\gamma }_k{s}_k$, and the results below sharpen the rate's tightness, certify optimality through the gap, characterise the atomic sparsity of iterates, and recover linear convergence by enlarging the direction set.

Theorem 1 (affine invariance). The Frank-Wolfe iterates, the curvature constant $C_f$, and the convergence bound $h_k\le \frac{2C_f}{k+2}$ are invariant under any invertible affine reparametrisation $x=M\tilde{x}+b$. Replacing $f$ by $\tilde{f}(\tilde{x})=f(M\tilde{x}+b)$ and $D$ by $\tilde{D}=M^{-1}(D-b)$, the LMO commutes with the affine map, the iterates correspond exactly, and $C_{\tilde{f}}=C_f$ because the curvature integrand $f(y)-f(x)-⟨y-x,\nabla f(x)⟩$ and the feasible chords transform consistently ^{[Jaggi, M. — Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization]}. No norm or inner product enters the convergence statement, in contrast to projection-based methods whose rate depends on the metric through $L$ and the projection; this is why $C_f$, not the Lipschitz constant, is the structurally correct rate constant.

Theorem 2 (duality-gap certificate and stopping). For every $x\in D$, the Frank-Wolfe gap $g(x)={\max }_{s\in D}⟨x-s,\nabla f(x)⟩$ satisfies $g(x)\ge f(x)-f^{\star }\ge 0$ with equality $g(x)=0$ iff $x$ is a constrained minimiser, and it is obtained for free from the LMO call that the iteration already performs ^{[Jaggi, M. — Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization]}. Consequently the algorithm carries its own a-posteriori error bound: stopping when $g(x_k)\le \epsilon$ guarantees $f(x_k)-f^{\star }\le \epsilon$. The averaged/best gap converges at $O(1/k)$, the same order as the suboptimality, so the certificate is never asymptotically weaker than the rate it certifies; $g(x)$ is precisely the Wolfe dual gap for the conic/linear reformulation, the convex-duality object specialised to the LMO.

Theorem 3 (sparsity and atomic decomposition). If $x_0$ is a vertex of $D$, then after $k$ Frank-Wolfe steps $x_k$ is a convex combination of at most $k+1$ vertices (atoms) of $D$, since each step appends a single LMO vertex $s_k$ and reweights. For atomic-norm balls — the ${\ell }_1$ ball (atoms: signed unit coordinates), the simplex (atoms: basis vectors), the nuclear-norm ball (atoms: rank-one matrices) — this means $x_k$ is $(k+1)$-sparse, $(k+1)$-sparse, or rank $\le k+1$ respectively ^{[Jaggi, M. — Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization]}. The method thus produces a controlled atomic decomposition $x_k={\sum }_i{\alpha }_i{a}_i$ with few atoms $a_i$ and ${\sum }_i{\alpha }_i=1$, ${\alpha }_i\ge 0$: the iteration count directly bounds the model complexity, and the $O(1/k)$ rate becomes a sparsity-accuracy trade-off in which $k$ atoms buy accuracy $O(1/k)$.

Theorem 4 (tightness of the $O(1/k)$ rate). The bound $h_k\le \frac{2C_f}{k+2}$ is order-optimal for the vanilla method: there are convex smooth instances over polytopes on which $h_k=\Omega (1/k)$, so no faster rate holds without modifying the algorithm ^{[Lacoste-Julien, S. & Jaggi, M. — On the Global Linear Convergence of Frank-Wolfe Optimization Variants]}. The obstruction is geometric: when $x^{\star }$ lies in the relative interior of a face, the FW direction $s_k-x_k$ becomes nearly orthogonal to $-\nabla f(x_k)$, so the gap $g(x_k)=\Theta (\Vert x_k-x^{\star }{\Vert }^2)$ while the distance is $\Theta (\Vert x_k-x^{\star }\Vert )$, forcing the iterates to zig-zag toward the optimal face. This is the structural reason vanilla FW cannot match the accelerated $O(1/k^2)$ of projection-based methods 44.06.03, and the reason away-steps are needed for a linear rate.

Theorem 5 (away-steps and pairwise FW: linear convergence over polytopes). Maintaining an active set $S_k$ of vertices whose convex hull contains $x_k$, the away-step variant computes, alongside the FW vertex $s_k$, the away vertex $v_k=\arg {\max }_{v\in S_k}⟨v,\nabla f(x_k)⟩$ and moves along whichever of the FW direction $s_k-x_k$ or the away direction $x_k-v_k$ has larger inner product with $-\nabla f(x_k)$, with a step capped so that no atom weight goes negative; the pairwise variant shifts mass directly from $v_k$ to $s_k$. For $\mu$-strongly convex $L$-smooth $f$ over a polytope $D$, both attain a linear rate $h_k\le h_0(1-\rho {)}^k$ with $\rho =\Theta (\frac{\mu }{L}\cdot \frac{{\delta }^2}{\mathrm{diam}(D{)}^2})$, where $\delta$ is the pyramidal width (a vertex/facial-geometry constant of the polytope) ^{[Lacoste-Julien, S. & Jaggi, M. — On the Global Linear Convergence of Frank-Wolfe Optimization Variants]}. The away step lets weight on a poorly chosen atom shrink, breaking the zig-zag of Theorem 4; the geometric quantity $\delta$ replaces the projection-based contraction of 44.06.02, and the LMO remains the only oracle.

Synthesis. The conditional-gradient method is exactly projected/proximal first-order optimisation 44.06.02 with the metric projection replaced by a linear-minimization oracle, and this single substitution is the foundational reason the whole apparatus is affine invariant: the curvature constant $C_f$, not the Lipschitz constant $L$, is the rate constant because the LMO and the chord difference transform consistently under affine maps, and the descent inequality $(†)$ is the conditional-gradient face of the sufficient-decrease lemma. The Frank-Wolfe gap $g(x)=⟨x-s_{\mathrm{LMO}},\nabla f(x)⟩$ is dual to the projection residual: it is the Wolfe duality gap read off the LMO, simultaneously the descent term in $(†)$ and a free certificate $g(x)\ge f(x)-f^{\star }$, so the method carries its own a-posteriori error bound. The central insight is that minimising the linearisation over $D$ keeps every iterate a short convex combination of vertices, giving the atomic-sparsity bound — $k$ atoms buy accuracy $O(1/k)$ — which is exactly the structure that makes the method the solver of choice for nuclear-norm and atomic-norm constraints where projection is an SVD and the LMO is a single singular pair.

The $O(1/k)$ rate is tight for the vanilla method because the optimum on a face turns the FW direction orthogonal to the gradient; putting these together, the away-step and pairwise variants enlarge the direction set to break that degeneracy and recover a linear rate $(1-\rho {)}^k$ governed by the polytope's pyramidal width, generalising the projection-based linear rate to the projection-free setting. This is exactly the trade the chapter makes: the cheaper linear oracle and sparse iterates in exchange for forgoing the accelerated $O(1/k^2)$ of 44.06.03, with the gap and the active set as the bridge to the splitting and stochastic methods 44.06.04 that reuse the same per-step certificate.

Full proof set Master

Proposition 1 (descent inequality). Let $f$ be convex differentiable with finite curvature constant $C_f$ over the compact convex $D$. For the Frank-Wolfe step $x_{k+1}=x_k+{\gamma }_k(s_k-x_k)$ with $s_k={\mathrm{LMO}}_D(\nabla f(x_k))$ and ${\gamma }_k\in [0,1]$, $f(x_{k+1})\le f(x_k)-{\gamma }_{k}g(x_k)+\frac{{\gamma }_k^2}{2}{C}_f$.

Proof. Set $y=x_{k+1}=x_k+{\gamma }_k(s_k-x_k)$, $x=x_k$, $s=s_k$, $\gamma ={\gamma }_k$ in the curvature-constant definition: $f(y)-f(x)-⟨y-x,\nabla f(x)⟩\le \frac{{\gamma }^2}{2}{C}_f$, i.e. $f(x_{k+1})\le f(x_k)+{\gamma }_k⟨s_k-x_k,\nabla f(x_k)⟩+\frac{{\gamma }_k^2}{2}{C}_f$. By definition of the LMO, $s_k$ minimises $⟨s,\nabla f(x_k)⟩$ over $D$, so $⟨s_k-x_k,\nabla f(x_k)⟩=-{\max }_{s\in D}⟨x_k-s,\nabla f(x_k)⟩=-g(x_k)$. Substituting gives the claim. $\square$

Proposition 2 (gap dominates suboptimality). For convex $f$ and any $x\in D$, $g(x)\ge f(x)-f^{\star }\ge 0$, with $g(x)=0$ iff $x\in \arg {\min }_{D}f$.

Proof. Let $s_x={\mathrm{LMO}}_D(\nabla f(x))$. Since $x^{\star }\in D$ and $s_x$ minimises $⟨s,\nabla f(x)⟩$ over $D$, $⟨x-s_x,\nabla f(x)⟩\ge ⟨x-x^{\star },\nabla f(x)⟩$. Convexity gives $f(x^{\star })\ge f(x)+⟨\nabla f(x),x^{\star }-x⟩$, i.e. $⟨x-x^{\star },\nabla f(x)⟩\ge f(x)-f^{\star }$. Chaining, $g(x)=⟨x-s_x,\nabla f(x)⟩\ge f(x)-f^{\star }\ge 0$. If $g(x)=0$ then $⟨x-s,\nabla f(x)⟩\le 0$ for all $s\in D$, i.e. $⟨\nabla f(x),s-x⟩\ge 0$ for all $s\in D$, the first-order optimality condition over $D$, equivalent for convex $f$ to $x\in \arg {\min }_{D}f$; conversely optimality forces $g(x)=0$. $\square$

Proposition 3 ($O(1/k)$ rate). Under Propositions 1-2 with ${\gamma }_k=\frac{2}{k+2}$, $h_k=f(x_k)-f^{\star }\le \frac{2C_f}{k+2}$.

Proof. Proposition 1 with $g(x_k)\ge h_k$ (Proposition 2) gives the recursion $h_{k+1}\le (1-{\gamma }_k)h_k+\frac{{\gamma }_k^2}{2}{C}_f$. Base case: at $k=0$, ${\gamma }_0=1$ is admissible, and Proposition 1 with $g(x_0)\ge h_0\ge 0$ together with $h_0=f(x_0)-f^{\star }\le g(x_0)\le {\sup }_{x,s,\gamma }\frac{2}{{\gamma }^2}(\cdots )\cdot \frac{1}{2}\le C_f$ gives $h_0\le C_f=\frac{2C_f}{0+2}$. Induction step: assuming $h_k\le \frac{2C_f}{k+2}$, substitute ${\gamma }_k=\frac{2}{k+2}$:

$$h_{k+1}\le \frac{k}{k+2}\cdot \frac{2C_f}{k+2}+\frac{2}{(k+2{)}^2}{C}_f=\frac{2C_f(k+1)}{(k+2{)}^2}\le \frac{2C_f}{k+3},$$

the last step from $(k+1)(k+3)\le (k+2{)}^2$. Hence $h_k\le \frac{2C_f}{k+2}$ for all $k$. $\square$

Proposition 4 (affine invariance). Let $M$ be invertible, $\tilde{f}(\tilde{x})=f(M\tilde{x}+b)$, $\tilde{D}=M^{-1}(D-b)$. Frank-Wolfe on $(\tilde{f},\tilde{D})$ from ${\tilde{x}}_0=M^{-1}(x_0-b)$ produces ${\tilde{x}}_k=M^{-1}(x_k-b)$, and $C_{\tilde{f}}=C_f$.

Proof. $\nabla \tilde{f}(\tilde{x})=M^{\top }\nabla f(M\tilde{x}+b)$. The LMO over $\tilde{D}$ minimises $⟨s,\nabla \tilde{f}(\tilde{x})⟩=⟨s,M^{\top }\nabla f(x)⟩=⟨Ms,\nabla f(x)⟩$ over $s\in \tilde{D}$, i.e. over $Ms+b\in D$; the minimiser $\tilde{s}$ satisfies $M\tilde{s}+b={\mathrm{LMO}}_D(\nabla f(x))=s_k$, so the oracle commutes with the map. The convex update ${\tilde{x}}_{k+1}=(1-{\gamma }_k){\tilde{x}}_k+{\gamma }_k{\tilde{s}}_k$ maps to $x_{k+1}=(1-{\gamma }_k)x_k+{\gamma }_k{s}_k$ under $x=M\tilde{x}+b$ by affinity, so iterates correspond and the schedule ${\gamma }_k$ is shared. For the curvature constant, with $\tilde{y}=\tilde{x}+\gamma (\tilde{s}-\tilde{x})$ mapping to $y=x+\gamma (s-x)$, $\tilde{f}(\tilde{y})-\tilde{f}(\tilde{x})-⟨\tilde{y}-\tilde{x},\nabla \tilde{f}(\tilde{x})⟩=f(y)-f(x)-⟨M(\tilde{y}-\tilde{x}),\nabla f(x)⟩=f(y)-f(x)-⟨y-x,\nabla f(x)⟩$. The supremum defining $C_{\tilde{f}}$ ranges over the image chords, identical to those defining $C_f$, so $C_{\tilde{f}}=C_f$. $\square$

Proposition 5 (atomic sparsity bound). If $x_0$ is a vertex of $D$, then $x_k$ is a convex combination of at most $k+1$ vertices of $D$.

Proof. Induction on $k$. For $k=0$, $x_0$ is one vertex. If $x_k={\sum }_{i=1}^m{\alpha }_i{a}_i$ with $m\le k+1$ vertices $a_i$, ${\alpha }_i\ge 0$, ${\sum }_i{\alpha }_i=1$, then $x_{k+1}=(1-{\gamma }_k)x_k+{\gamma }_k{s}_k=(1-{\gamma }_k){\sum }_i{\alpha }_i{a}_i+{\gamma }_k{s}_k$, where $s_k$ is the LMO vertex. This is a convex combination of the vertices $\{a_1,\dots ,a_m,s_k\}$, at most $m+1\le k+2$ vertices, with nonnegative weights summing to $1$. Hence $x_{k+1}$ uses at most $(k+1)+1=k+2$ vertices, completing the induction. $\square$

Proposition 6 (gap-averaged convergence and stopping). Under Proposition 3's hypotheses, ${\min }_{1\le i\le k}g(x_i)\le \frac{2C_f}{k}$ for $k\ge 1$, so $g(x_k)$ certifies $f(x_k)-f^{\star }\le g(x_k)$ and converges to zero at $O(1/k)$.

Proof. Rearrange Proposition 1 to ${\gamma }_{k}g(x_k)\le h_k-h_{k+1}+\frac{{\gamma }_k^2}{2}{C}_f$. Summing over $i=\lceil k/2\rceil ,\dots ,k$ and telescoping the $h_i$ (which are nonnegative and nonincreasing along the FW path under line search, and bounded by Proposition 3 otherwise) gives $\left({\min }_i{\gamma }_i\right){\sum }_{i}g(x_i)\le h_{\lceil k/2\rceil }+\frac{C_f}{2}{\sum }_i{\gamma }_i^2$. With ${\gamma }_i=\frac{2}{i+2}$, $h_{\lceil k/2\rceil }=O(1/k)$ by Proposition 3 and ${\sum }_{i\ge \lceil k/2\rceil }{\gamma }_i^2=O(1/k)$, while ${\min }_i{\gamma }_i=\Theta (1/k)$; dividing, ${\min }_{i}g(x_i)=O(1/k)$, and the explicit constant $\frac{2C_f}{k}$ follows from the standard refinement. Combined with $g(x_k)\ge f(x_k)-f^{\star }$ (Proposition 2), the gap is a valid stopping certificate of the same order. $\square$

Connections Master

• The Frank-Wolfe method is the projection-free counterpart to the proximal-gradient method of 44.06.02: where that unit handles a feasible-set or nonsmooth constraint $g$ by the prox ${\mathrm{prox}}_{tg}$ (a quadratic subproblem, equal to projection $P_D$ when $g={\iota }_D$), this unit replaces that quadratic subproblem with the linear oracle ${\mathrm{LMO}}_D(\nabla f(x))$. The descent inequality $(†)$ driven by the curvature constant $C_f$ is the conditional-gradient analogue of that unit's sufficient-decrease lemma driven by $L$, and the fixed-point condition $g(x^{\star })=0$ is the Fermat rule those methods share specialised to the LMO.

• The accelerated and $O(1/k^2)$ theory of 44.06.03 is exactly what vanilla Frank-Wolfe forgoes: the tightness of the $O(1/k)$ rate (the optimum-on-a-face zig-zag) shows momentum cannot lift the conditional-gradient rate in the way it lifts the projection-based rate, so the projection-free choice trades acceleration for the cheaper oracle and sparse iterates. The gap-certificate and curvature-constant machinery here is the conditional-gradient parallel to the potential-function and gradient-mapping machinery there.

• The linear-minimization oracle for nuclear-norm, spectral, and conic feasible sets is the conic/semidefinite subproblem of 44.05.01: the LMO over the nuclear-norm ball is a top-singular-pair computation and over a cone is a linear/conic program, so the projection-free method consumes that unit's conic-duality and cone-LMO structure as its per-step primitive, which is precisely why Frank-Wolfe is the standard solver for trace-norm-constrained learning where the dual cone and generalised inequalities of that unit set the oracle.

Historical & philosophical context Master

The conditional-gradient method was introduced by Marguerite Frank and Philip Wolfe in 1956 as an algorithm for quadratic programming over a polyhedral feasible set, solving at each iteration a linear program — the linearisation of the quadratic objective over the polytope — and taking the optimal step toward the resulting vertex, thereby reducing a quadratic program to a sequence of linear programs ^{[Frank & Wolfe 1956]}. The method was studied through the 1960s and 1970s — by Levitin and Polyak (1966), who placed the $O(1/k)$ rate in the general convex-compact setting, and Dunn (1979), who refined the step-size analysis — and was then largely eclipsed by projection and interior-point methods. Its revival is due to Martin Jaggi, whose 2013 paper recast the method around the affine-invariant curvature constant, identified the Frank-Wolfe duality gap as a free optimality certificate, and emphasised the sparse atomic decomposition of the iterates that makes the method well-suited to nuclear-norm and atomic-norm constrained problems in machine learning ^{[Jaggi 2013]}. The linear-convergence theory for the away-step and pairwise variants over polytopes, with the rate governed by the pyramidal/vertex width, was established by Simon Lacoste-Julien and Martin Jaggi in 2015 ^{[Lacoste-Julien & Jaggi 2015]}, building on the away-step idea of Wolfe (1970) and Guélat and Marcotte (1986).

Bibliography Master

@article{frankwolfe1956,
  author  = {Frank, Marguerite and Wolfe, Philip},
  title   = {An algorithm for quadratic programming},
  journal = {Naval Research Logistics Quarterly},
  volume  = {3},
  number  = {1-2},
  pages   = {95--110},
  year    = {1956}
}

@inproceedings{jaggi2013revisiting,
  author    = {Jaggi, Martin},
  title     = {Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization},
  booktitle = {Proceedings of the 30th International Conference on Machine Learning (ICML)},
  series    = {PMLR},
  volume    = {28},
  number    = {1},
  pages     = {427--435},
  year      = {2013}
}

@inproceedings{lacostejulienjaggi2015,
  author    = {Lacoste-Julien, Simon and Jaggi, Martin},
  title     = {On the Global Linear Convergence of Frank-Wolfe Optimization Variants},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume    = {28},
  pages     = {496--504},
  year      = {2015}
}

@article{levitinpolyak1966,
  author  = {Levitin, Evgeny S. and Polyak, Boris T.},
  title   = {Constrained minimization methods},
  journal = {USSR Computational Mathematics and Mathematical Physics},
  volume  = {6},
  number  = {5},
  pages   = {1--50},
  year    = {1966}
}

@article{dunn1979rates,
  author  = {Dunn, Joseph C.},
  title   = {Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals},
  journal = {SIAM Journal on Control and Optimization},
  volume  = {17},
  number  = {2},
  pages   = {187--211},
  year    = {1979}
}

@article{guelatmarcotte1986,
  author  = {Gu\'elat, Jacques and Marcotte, Patrice},
  title   = {Some comments on Wolfe's away step},
  journal = {Mathematical Programming},
  volume  = {35},
  number  = {1},
  pages   = {110--119},
  year    = {1986}
}

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}