Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent
Abstract
This work considers stepsize schedules for gradient descent on smooth strongly convex objectives. We develop a curvature-dependent concatenation framework for constructing stepsize schedules of arbitrary length with sharp worst-case guarantees. Within this framework, we introduce two families of schedules for the function-value gap and gradient norm of the last iterate, respectively. For each fixed condition number κ=L/μ>1, both families attain iteration complexity Θ(κρlog(1/ε)) for sufficiently small ε, where ρ=log√2+12≈0.7864. This complexity is optimal up to a subpolynomial factor in κ among predetermined nonnegative stepsize schedules. The framework also recovers the strongly convex silver schedule at power-of-two iteration budgets and applies to smooth convex and smooth weakly convex functions.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
- Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
- Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
- On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
BibTeX
@misc{zhang2026accelerated,
title = {{Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent}},
author = {Zehao Zhang and Rujun Jiang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05242},
eprint = {2611.05242},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05242},
}
RIS
TY - UNPB
TI - Accelerated Concatenation of Stepsize Schedules for Smooth Strongly Convex Gradient Descent
AU - Zehao Zhang
AU - Rujun Jiang
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05242
UR - https://arxiv.org/abs/2611.05242
AB - This work considers stepsize schedules for gradient descent on smooth strongly convex objectives. We develop a curvature-dependent concatenation framework for constructing stepsize schedules of arbitrary length with sharp worst-case guarantees. Within this framework, we introduce two families of schedules for the function-value gap and gradient norm of the last iterate, respectively. For each fixed condition number κ=L/μ>1, both families attain iteration complexity Θ(κ^ρlog(1/ε)) for sufficiently small ε, where ρ=log_√2+12≈0.7864. This complexity is optimal up to a subpolynomial factor in κ among predetermined nonnegative stepsize schedules. The framework also recovers the strongly convex silver schedule at power-of-two iteration budgets and applies to smooth convex and smooth weakly convex functions.
ER -