← All papers
First page of Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes

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

Yu Liu, Kang Chen, Rujun Jiang, Tianyu Wang

math.OC Sep 10, 2026 · v2
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.
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.

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.

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.

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