Mirror descent and Frank-Wolfe
Both methods start from projected gradient descent and change one piece of it. Mirror descent changes how distance is measured. Frank-Wolfe changes how the constraint is enforced.
The step they both modify
A projected gradient step solves a small problem at every iteration. Go downhill along the gradient g_k, stay close to the current point x_k, and stay inside the feasible set C.
Mirror descent changes the ruler
The feasible set is the probability simplex in three dimensions, drawn as a triangle. Each corner puts all the weight on one coordinate. The loss is a bowl f(x) = \tfrac12 \|x - t\|_2^2 and you can drag its bottom t.
Each outline marks the points that a method treats as equally far from where it stands. The next iterate is the point on that outline that goes furthest downhill according to the current gradient.
Projected gradient descent draws a circle. A circle knows nothing about the edges, so the raw step can leave the triangle and must be projected back.
Mirror descent with the entropy ruler measures distance with KL divergence. Its outline flattens against nearby edges, because pushing a small coordinate toward zero counts as a long trip. The update multiplies each coordinate by a positive number, so the iterate can never leave.
On a small smooth bowl like this one the circle often arrives in fewer steps. The entropy ruler pays off in high dimension, which the next chart shows.
The payoff appears as the dimension grows
The Euclidean guarantee scales with the 2-norm of the gradient, which grows like \sqrt{d} in this problem. The entropy guarantee scales with the largest single coordinate of the gradient and pays only a \sqrt{\log d} factor for the dimension.
Frank-Wolfe skips the projection
The feasible set is a polygon and the loss is the same kind of bowl. Its bottom sits outside the polygon, so the best feasible point lies on an edge.
Each step asks one question. Which point of C lies furthest in the downhill direction? Picture a line perpendicular to the gradient sliding across the set. The last point it touches is the answer, and for a polygon that point is always a corner. The dashed grey line shows that last contact.
Then move part of the way toward that corner. The fraction is \gamma_k = \frac{2}{k+2}, so the first step jumps all the way and later steps shrink. The new point is a weighted average of two feasible points, which makes it feasible with no projection.
Watch the zigzag. When the best point lies on an edge, the answer alternates between the two corners of that edge, and only the shrinking fraction settles it. The Frank-Wolfe gap bounces instead of falling steadily, and projected gradient descent with step size 0.5 pulls ahead within a few steps on this toy. Frank-Wolfe wins when projecting costs far more than the linear question. Under a nuclear norm constraint, projection needs a full SVD while the linear question needs only the top singular vector pair.
Side by side
| Projected gradient descent | Mirror descent | Frank-Wolfe | |
|---|---|---|---|
| Work per step | A gradient and a Euclidean projection onto C | A gradient and a projection in the chosen geometry, often available in closed form | A gradient and one linear minimization over C |
| How it stays feasible | Projects back after each step | The distance grows steeply near the boundary | Averages feasible points |
| Worst-case guarantee, convex f | \dfrac{RG}{\sqrt{K}} with noisy gradients | The same form, with R and G measured in the chosen geometry | \dfrac{2LD^2}{K+2} for smooth f with exact gradients, where L is the smoothness constant and D is the diameter of C |
| Reach for it when | The set is simple and Euclidean distance is natural | The set has its own geometry, such as probability vectors in high dimension | Projection is expensive, or you want iterates built from few corners |