Is conditional gradient a different algorithm?

It is another established name for Frank - Wolfe.

Does it require exact line search?

No. Suitable prescribed step sizes and other supported choices are possible.

Can it leave the feasible set?

The standard convex-combination update remains feasible when both endpoints belong to a convex feasible set.

AI Glossary / Mathematics and optimization / Advanced

Frank - Wolfe algorithm

Definition

The Frank - Wolfe algorithm, also called the conditional gradient method, solves constrained optimization problems by repeatedly minimizing a linear approximation of the objective over the feasible set and moving toward the resulting point. Its standard convex form maintains feasibility without performing a projection step.

What it means

Many optimization methods take an unconstrained step and then project the result back into the permitted region. Frank - Wolfe instead asks which feasible point best matches the current linearized objective, then blends the current point with that choice.

This is useful when linear optimization over the constraints is easier than projection. The advantage depends on the particular feasible set and objective; avoiding projection does not guarantee that every iteration or the complete optimization will be inexpensive.

How it works

For a differentiable objective f and a compact convex feasible set D, start with x in D. Find s minimizing the inner product of s and the gradient of f at x over D. Update x to (1 − gamma)x + gamma s, with gamma between zero and one.

Convexity of D keeps the updated point feasible. Step sizes may follow a suitable schedule or be chosen by line search along the segment. For convex f, the exact linear subproblem supplies the Frank - Wolfe gap g = gradient(f(x)) dot (x − s). This bounds the objective error above: f(x) − f(optimum) is at most g.

Standard convergence guarantees require appropriate assumptions, including smoothness or bounded curvature for familiar rate statements. Approximate subproblem solutions need corresponding error controls; nonconvex objectives require different interpretations of the gap.

Three practical examples

1. Mixture weights: optimize nonnegative weights summing to one. The linear subproblem chooses a coordinate with the smallest gradient component, making each update a blend with one vertex of the probability simplex.

2. Structured prediction: some constrained formulations permit a useful linear optimization routine even when direct projection is difficult. Frank - Wolfe can use that routine, provided its accuracy and computational cost are understood.

3. Matrix estimation: suitable atomic constraint sets allow updates using low-rank components. Maintaining a compact representation can be useful, although the number of components may grow as the algorithm proceeds.

Think of it this way

Suppose a permitted recipe is any mixture of several ingredients. At each step, a local taste assessment suggests which ingredient would improve the mixture most. You add a calculated proportion of that ingredient instead of making an arbitrary change and then repairing an invalid recipe. Each intermediate mixture still obeys the mixing rules.

Worked example

Consider an original three-weight problem. Minimize f(x) = one-half the squared Euclidean distance between x and q = (0.2, 0.3, 0.5), subject to nonnegative weights summing to one. Because q is feasible, the exact minimum is zero at q.

Start at x = (1, 0, 0). The gradient x − q is (0.8, −0.3, −0.5). Minimizing its linear function over the simplex selects s = (0, 0, 1), the vertex corresponding to the smallest gradient component.

Along the segment, x(gamma) = (1 − gamma, 0, gamma). Exact line search gives gamma = 0.65, producing x = (0.35, 0, 0.65). The objective falls from 0.49 to 0.0675. Both points satisfy the constraints.

At the new point the gradient is (0.15, −0.3, 0.15), so the next selected vertex is (0, 1, 0). The gap is gradient dot (x − s) = 0.45. The true objective error is 0.0675, which is indeed no greater than the bound. The bound is valid but not tight.

The second search direction is (−0.35, 1, −0.65). Its squared length is 1.545, so exact line search gives gamma = 0.45 / 1.545 = 30/103. The next weights are approximately (0.248058, 0.291262, 0.460680), and the objective is 81/41200, approximately 0.001966.

These calculations demonstrate two iterations, not finite-step convergence to the target. Starting from one vertex, the first update uses two vertices and the second uses three. The representation is built incrementally while remaining feasible throughout.

Illustrative case study

In a fictional analytics project, a team fits a constrained mixture of several predictive components. The initial implementation projects a dense weight vector after every gradient step. Engineers investigate Frank - Wolfe because choosing one component through a linear subproblem is straightforward.

They compare elapsed time to a common objective-error target rather than comparing iteration counts alone. They also record the number of active components and the computed gap. Early iterates are economical to represent, but later progress slows near the desired solution.

The team keeps the method only if the complete accuracy-and-cost comparison supports it. A simple linear subproblem and feasible iterates are useful properties, but they do not settle the choice of optimizer by themselves.

Common misconceptions and mistakes

Projection-free does not mean constraint-free. Every selected point must satisfy the feasible-set requirements, and feasibility of the blend relies on convexity.

The selected vertex is generally not the final answer. The algorithm combines it with the existing iterate.

A small gap certifies global objective accuracy in the stated convex setting with an appropriately solved linear subproblem. It is not automatically a global certificate for an arbitrary nonconvex problem.

Sparse intermediate representations do not imply that the exact optimum is sparse. Also, the basic method may progress slowly near a boundary; variants have different assumptions and behavior.

Business use

The method is relevant when a model has meaningful convex constraints and linear optimization over those constraints is tractable. Its gap can help express a stopping rule in terms of remaining optimization error.

Evaluation should include the cost of the linear subproblem, gradient computation, required accuracy and representation size. Separate optimization error from predictive error: solving the chosen objective accurately does not guarantee good performance on future data.

Check your understanding

Which vertex is selected first in the example?

Answer: (0, 0, 1), because the third gradient component is smallest.

Does a gap of 0.45 mean the objective error equals 0.45?

Answer: No; it is an upper bound. The actual error there is 0.0675.

Why do the updated weights still sum to one?

Answer: They are a convex combination of two vectors whose weights sum to one.

Related terms

Convex optimization
Duality gap
Line search
Conditional gradient
linear minimization oracle
simplex
projection

Learn next

Reproduce both line searches and compare their results with a prescribed step-size schedule. Then examine how an approximate linear subproblem changes the reliability of a stopping certificate.

Step size

Sources

Martin Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML 2013, Algorithms 1–3 and Section 2: https://proceedings.mlr.press/v28/jaggi13.pdf

The simplex calculations and analytics case are original illustrations.

Previous: Framing effect Next: Fraud detection