Frank–Wolfe Dual Gap

Worked Example

Consider minimizing f(w) = 1/2 ‖A w - b‖² over the unit simplex where the columns of A are (0, 0), (1, 0), and (0, 1), and b = (0.2, 0.3).

1. Initialize w_0 = (1, 0, 0), corresponding to point (0, 0).
2. Gradient of weights is (0, -0.2, -0.3).
3. Linear oracle picks the minimum gradient vertex: index 2, s = (0, 0, 1) corresponding to (0, 1).
4. Frank-Wolfe gap: ⟨ w_0 - s, ∇ f(w_0) ⟩ = 0.3.
5. Exact line search: d = (0, 1) - (0, 0) = (0, 1), residual is (-0.2, -0.3). γ = 0.3 / 1 = 0.3.
6. Update weights: w_1 = (0.7, 0, 0.3).

Experiment

Observe the convergence of the Frank-Wolfe algorithm and the primal-dual gap in the Frank–Wolfe Dual Gap module.

1. Select Target "Outside".
2. Select Start "Origin".
3. Observe the Exact optimal objective is 2.25 and the Primal gap drops to 0 after 2 Steps.

Limitations

The Frank-Wolfe algorithm is projection-free and well-suited for problems where the linear optimization oracle is cheap, such as optimizing over a trace norm or nuclear norm ball. However, it can exhibit sublinear convergence rates and zig-zagging behavior compared to projected gradient methods, especially when the optimal solution lies on a low-dimensional face of the constraint set. The dual gap provides a certificate of suboptimality but can be a loose upper bound.

References

For more details on the Frank-Wolfe algorithm and the primal-dual gap, see:

• Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (Jaggi, 2013).