Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes

Abstract

Predetermined stepsize schedules featuring carefully chosen long steps have recently been shown to accelerate gradient descent (GD) on smooth convex functions. A prominent class of such schedules is built through recursive composition. In this paper, we characterize the convergence of these optimized recursive schedules, revealing a nonconstant log-periodic modulation across prescribed horizons. Specifically, we prove that for every $N\ge 1$, the optimized ConPP/OBS-S schedules satisfy $$f(x_{N-1})-f_{\ast }\le \frac{1}{2N^p\Phi ({\log }_{2}N)-1}\frac{L}{2}\Vert x_0-x_{\ast }{\Vert }^2,p={\log }_2(1+\sqrt{2}),$$ where $\Phi$ is a positive, Lipschitz, nonconstant $1$-periodic function. We derive this by proving that balanced splitting is optimal at every horizon for these constructions, resolving a conjecture of Zhang and Jiang. Furthermore, for their asymmetric counterparts (ConPD/OBS-F schedules), we show that although optimal splits are not necessarily balanced, the same Silver exponent asymptotically persists alongside a distinct log-periodic modulation.