Scalar and combinatorial statements behind all theorems, lemmas, and corollaries are formalized in Lean 4/Mathlib, with AI-assisted proof scripts checked by the kernel.
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 \geq 1$, the optimized ConPP/OBS-S schedules satisfy $$f(x_{N-1})-f_\ast \le \frac{1}{2N^pΦ(\log_2N)-1} \frac{L}{2}\|x_0-x_\ast\|^2, \qquad p=\log_2(1+\sqrt2), $$ where $Φ$ 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.
Problem
Recursively composed predetermined stepsize schedules (ConPP/OBS-S and ConPD/OBS-F) accelerate gradient descent on smooth convex functions. Their exact convergence behavior and optimal splitting structure were not known, including a conjecture of Zhang and Jiang that balanced splitting is optimal.
Approach
The authors prove a sharp four-point rearrangement theorem for the scalar composition law, with full equality cases. From it they derive an abstract balanced-composition principle showing the Bellman sequence equals the balanced sequence. Dyadic scaling then gives a continuum interpolation with a periodic phase function. A separate comparison and compactness argument handles the asymmetric OBS-F recursion, and the scalar and combinatorial statements are formalized in Lean 4/Mathlib.
Results
Balanced splitting is optimal at every horizon for OBS-S, which resolves the Zhang–Jiang conjecture. The resulting bound is f(x_{N-1})-f* ≤ L||x0-x*||²/(2(2N^pΦ(log2 N)-1)), where p=log2(1+√2) and Φ is a nonconstant, Lipschitz, 1-periodic function. For OBS-F, the same Silver exponent holds asymptotically, with a distinct nonconstant Lipschitz log-periodic phase.
Figure 2: Numerical approximation of the asymmetric OBS-F phase \Psi_{F} by the interpolant \Psi_{18} from Section 6.2 . Its nodes are N^{p}\eta^{\mathrm{F}}_{N} for 2^{18}\leq N\leq 2^{19} , computed by exhaustive optimization over all ordered splits in the Bellman recursion. The annotated extrema belong to this finite-scale interpolant. The dashed line is the support barrier c_{*}\approx 0.42080