Theorem 2 — a small duality gap within K iterations

Let $f$ be convex and continuously differentiable on a compact convex domain $D$, with finite curvature constant $C_f$. Run one of the paper's four Frank–Wolfe algorithms from $x^{(0)}\in D$ with linear-subproblem quality $\delta\ge0$. If $K\ge2$, some iterate indexed by $1\le\widehat k\le K$ satisfies

The result guarantees an observable optimality certificate within the stated number of iterations, rather than only a bound on the unknown primal error.

Formalization Note The run has the paper's steps $k=0,\ldots,K$; $x^{(0)}$ is feasible, while later feasibility follows from the update rules. The exact curvature supremum is used with its boundedness stated explicitly. The Hilbert-space pairing is expressed through the Fréchet derivative on a real normed space, and convexity is required only on $D$. For Algorithm 1 the exact oracle is represented for every $\delta\ge0$, including its source value $\delta=0$.