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 ≥ 1, the optimized ConPP/OBS-S schedules satisfy f(xN−1)−f∗ ≤ 1/(2NpΦ(log2N)−1) L/2|x0−x∗|2, p=log2(1+√2), 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.
Related
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- The Maximum Principle and Optimal Gradient Estimates of Solutions to the Insulated Conductivity Problem
- Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
BibTeX
@misc{liu2026optimal,
title = {{Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes}},
author = {Yu Liu and Kang Chen and Rujun Jiang and Tianyu Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.11788},
eprint = {2609.11788},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11788},
}
RIS
TY - UNPB
TI - Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes
AU - Yu Liu
AU - Kang Chen
AU - Rujun Jiang
AU - Tianyu Wang
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2609.11788
UR - https://arxiv.org/abs/2609.11788
AB - 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 ≥ 1, the optimized ConPP/OBS-S schedules satisfy f(x_N−1)−f_∗ ≤ 1/(2N^pΦ(log_2N)−1) L/2|x_0−x_∗|^2, p=log_2(1+√2), 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.
ER -