Adaptive Open-Loop Step-Sizes for Accelerated Convergence Rates of the Frank-Wolfe Algorithm

Recent work has shown that in certain settings, the Frank-Wolfe algorithm (FW) with open-loop step-sizes ηₜ = /t+ for a fixed parameter ∈ N,\, ≥ 2, attains a convergence rate faster than the traditional O(t⁻¹) rate. In particular, when a strong growth property holds, the convergence rate attainable with open-loop step-sizes ηₜ = /t+ is O(t⁻). In this setting there is no single value of the parameter that prevails as superior. This paper shows that FW with log-adaptive open-loop step-sizes ηₜ = 2+log(t+1)/t+2+log(t+1) attains a convergence rate that is at least as fast as that attainable with fixed-parameter open-loop step-sizes ηₜ = /t+ for any value of ∈ N,\,≥ 2. To establish our main convergence results, we extend our previous affine-invariant accelerated convergence results for FW to more general open-loop step-sizes of the form ηₜ = g(t)/(t+g(t)), where g:N≥ 0 is any non-decreasing function such that the sequence of step-sizes (ηₜ) is non-increasing. This covers in particular the fixed-parameter case by choosing g(t) = and the log-adaptive case by choosing g(t) = 2+ log(t+1). To facilitate adoption of log-adaptive open-loop step-sizes, we have incorporated this rule into the { FrankWolfe.jl} software package.