Theorem 6.2, p. 24, corrected — the fully adaptive Frank-Wolfe algorithm converges linearly at rate max{1 − δ/2, 1 − (1 − √(1 − δ))²αε/(4β̄)}

Linear convergence of the fully adaptive Frank-Wolfe algorithm.

Let $\mathcal S=\times_{k=1}^K\mathcal S^{[k]}\subseteq\mathbb R^{d_1}\times\dots\times\mathbb R^{d_K}$ be a product of convex compact sets, let $f$ be convex on $\mathcal S$ and differentiable at its points, with optimal value $f^\star=\min_{s\in\mathcal S}f(s)$, and let $F$ be an inexact oracle with precision $\delta\in[0,1]$:

Suppose Assumption 6.1 holds:

1. $f$ is $\beta$-smooth on $\mathcal S$ for some $\beta>0$;
2. the marginal feasible sets are $\alpha$-strongly convex with respect to $f$ for some $\alpha>0$;
3. $f$ is $\varepsilon$-steep on $\mathcal S$ for some $\varepsilon>0$.

Let $(s_t,\beta_t,\eta_t)_{t\ge0}$ be a run of Algorithm 1 with inputs $s_0\in\mathcal S$, $\beta_{-1}>0$, $\tau>1$, $\zeta>1$, and let $\bar\beta=\max\{\tau\beta,\beta_{-1}\}$. Then

The rate depends only on the oracle precision and the regularity constants, not on the unknown smoothness parameter actually used by the line search; the algorithm never needs $\beta$.

Formalization Note The paper prints the second term of the maximum as $1-(1-\sqrt{1-\delta})\alpha\varepsilon/(4\bar\beta)$, without the square. That version is false for $\delta\in(0,1)$: with $K=1$, $\mathcal S$ the unit disk in $\mathbb R^2$, $f(s)=s_2$ ($\beta=\alpha=\varepsilon=1$, $f^\star=-1$), $s_0=(1,0)$, $\delta=0.19$, $\tau=\zeta=2$, $\beta_{-1}=100$ (so $\bar\beta=100$) and the oracle value $F(s_0)=(-\sqrt{1-\delta^2},-\delta)$, which satisfies (6.2) with equality, the first step accepts $\beta_0=50$ and gives $f(s_1)-f^\star\approx0.999818$, above the printed bound $0.99975$ and below the corrected bound $0.999975$. The error comes from Lemma 6.3 (ii), where substituting $\theta^\star=(1-\sqrt{1-\delta})/\delta$ into (6.8) drops a square. At $\delta=1$ (exact oracle) the printed and corrected rates coincide. The statement holds for every $t\ge0$, including the trivial $t=0$. $f$ is assumed differentiable at the points of $\mathcal S$ as a function on the ambient space, and convex on $\mathcal S$ only. In (6.2) the minimum is written as "$\le\delta(z-s)^\top\nabla f(s)$ for all $z\in\mathcal S$", which is equivalent on the compact set $\mathcal S$. At $d_t=0$, where the page's stepsize is undefined, Lean's $0/0=0$ gives $\eta_t=0$.