Constant Steps Are s-Composable: An Exact Interpolation Certificate for Gradient Descent
Abstract
Grimmer, Shu, and Wang asked whether a balanced constant schedule is s-composable at every horizon. More precisely, for an integer n≥ 1, let h̅=1+r, where r∈(0,1) is the unique solution of rn(1+n(1+r))=1, and run gradient descent for n steps with normalized stepsize h̅. The cases n=1,2 were known, while the general case n≥3 was left open. We prove the conjecture for every n. Our proof gives an explicit, dimension-free nonnegative linear combination of the smooth convex interpolation inequalities. The certificate is assembled from matrices supported on contiguous index intervals. Its off-diagonal entries are automatically positive, its quadratic part is diagonal, and its remaining multipliers reduce to two scalar families. We derive closed forms for those families and prove positivity using strict concavity and elementary rational inequalities. Consequently, for every L-smooth convex function, the constant schedule satisfies the sharp mixed terminal Lyapunov inequality conjectured in the original paper, together with the associated simultaneous objective-gap and gradient-norm bounds. All exceptional horizons and boundary indices are treated explicitly.
Related
- The double descent and Runge phenomena in overparametrized polynomial interpolation
- Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
- PL conditions do not guarantee convergence of gradient descent-ascent dynamics
- Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
BibTeX
@misc{zhao2026constant,
title = {{Constant Steps Are s-Composable: An Exact Interpolation Certificate for Gradient Descent}},
author = {Jinze Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11784},
eprint = {2609.11784},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11784},
}
RIS
TY - UNPB
TI - Constant Steps Are s-Composable: An Exact Interpolation Certificate for Gradient Descent
AU - Jinze Zhao
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11784
UR - https://arxiv.org/abs/2609.11784
AB - Grimmer, Shu, and Wang asked whether a balanced constant schedule is s-composable at every horizon. More precisely, for an integer n≥ 1, let h̅=1+r, where r∈(0,1) is the unique solution of r^n(1+n(1+r))=1, and run gradient descent for n steps with normalized stepsize h̅. The cases n=1,2 were known, while the general case n≥3 was left open. We prove the conjecture for every n. Our proof gives an explicit, dimension-free nonnegative linear combination of the smooth convex interpolation inequalities. The certificate is assembled from matrices supported on contiguous index intervals. Its off-diagonal entries are automatically positive, its quadratic part is diagonal, and its remaining multipliers reduce to two scalar families. We derive closed forms for those families and prove positivity using strict concavity and elementary rational inequalities. Consequently, for every L-smooth convex function, the constant schedule satisfies the sharp mixed terminal Lyapunov inequality conjectured in the original paper, together with the associated simultaneous objective-gap and gradient-norm bounds. All exceptional horizons and boundary indices are treated explicitly.
ER -