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 ∈ C f ( x ) \min_{x \in \mathcal{C}} f(x)
Here f f is convex and differentiable, and C \mathcal{C} is a compact convex set.…