Adaptive open-loop step-sizes for accelerated convergence rates of the Frank–Wolfe algorithm

Abstract Recent work has shown that, in several growth settings, the Frank–Wolfe algorithm () with fixed-parameter open-loop step-sizes $$\eta _t = \frac{\ell }{t+\ell }$$ η t = ℓ t + ℓ for $$\ell \in \mathbb {N}_{\ge 2}$$ ℓ ∈ N ≥ 2 can converge faster than the classical $${\mathcal {O}}(t^{-1})$$ O ( t - 1 ) rate. In the strong-growth regime, increasing $$\ell $$ ℓ improves the asymptotic rate, so no single fixed choice of $$\ell $$ ℓ is uniformly preferable. We study the broader family of adaptive open-loop step-sizes $$\eta _t = \frac{g(t)}{t+g(t)}$$ η t = g ( t ) t + g ( t ) and extend the affine-invariant analysis from the fixed-parameter case to non-decreasing functions g for which the resulting step-size sequence is non-increasing. For the log-adaptive choice $$g(t)=2+\log (t+1)$$ g ( t ) = 2 + log ( t + 1 ) , this yields a schedule that matches the asymptotic rates of fixed-parameter rules up to polylogarithmic factors in the weak-growth settings considered here, while improving the asymptotic sublinear rate in strong-growth settings. We also report numerical experiments demonstrating the efficacy of the new proposed step-size rule.