Anytime Convergence Rate of Gradient Descent

Kornowski et al. (2024): With constant stepsize $\eta_t\equiv\eta\in(0,2/L)$, standard analysis yields an anytime worst-case bound of the form $f(x_T)-f^* \le C\,L\|x_0-x^*\|^2/T$ for all $T\in\mathbb{N}$.

Kornowski et al. (2024): There exist non-constant stepsize schedules that achieve an accelerated bound at selected, pre-specified horizons (e.g., along a sparse subsequence of times), but such horizon-specific acceleration does not by itself imply an anytime bound for the specific iterate $x_T$ at every $T$.

Kornowski et al. (2024): A horizon-specific guarantee can be converted into an anytime guarantee only for "best-so-far" performance (e.g., $\min_{t\le T} f(x_t)-f^*$ by selecting a nearby special horizon), which is strictly weaker than bounding $f(x_T)-f^*$ for each $T$.

Kornowski et al. (2024): Any oblivious schedule that would improve the anytime worst-case rate beyond $O(1/T)$ uniformly over all $L$-smooth convex objectives (in the sense $f(x_T)-f^* = o(L\|x_0-x^*\|^2/T)$ for all $T$) must use unbounded stepsizes, i.e., $\limsup_{t\to\infty} \eta_t = \infty$.

Kornowski et al. (2024): Large individual steps can cause persistent large errors: in dimension $d=1$, if at some time $T$ one has $\eta_T\ge 2/L$ and also $\sum_{t=0}^{T-1}\eta_t\ge 1/L$, then there exists an $L$-smooth convex $f$ such that

Kornowski et al. (2024): Consequently, if a schedule has infinitely many times where the ratio $\eta_T/\sum_{t<T}\eta_t$ is bounded away from $0$ while taking such "long" steps, then $f(x_T)-f^*$ can remain on the order of $L\|x_0-x^*\|^2$ at arbitrarily large times, ruling out any decaying anytime bound for that schedule.