Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes
Abstract
Simplified spectral models predict dimension-dependent superlinear convergence for gradient methods, but the corresponding behavior of actual iterations remains only partially understood. Historical methods introduce an additional difficulty: the gradients defining the step sizes differ from those receiving them. We study this offset for cyclic reuse of historical Ritz step sizes on strictly convex quadratics. Within the existing limited memory steepest descent with retards (LMSDR) family, a rolling cyclic Ritz (RCR) rule reuses m historical Ritz values ℓ times per cycle, ending with a complete sweep. At q=m+1 active distinct eigenvalues, an exact delayed recurrence gives almost-everywhere doubly exponential convergence with an explicit rate and exceptional weights. Nonempty open basins also exist for m+1<q≤2m and ℓ≥4. Rebuilding the history from each cycle-start gradient costs m additional updates and gives sampled cyclic Ritz reuse (SCR) a cycle-end map determined by the current weights. Under uniform sampling bounds, SCR converges doubly exponentially almost everywhere when (2ℓ−1)m>binomq−1m. Increasing ℓ admits larger q for fixed m. The guarantee extends to history-dependent choices from finite sampling menus under a bound on the number of admissible sampling sequences. Geometrically spaced decisions retain the SCR condition and rate range. Every update is counted, including sampling; a numerical illustration compares finite-tolerance update counts.
Related
- Counterexamples to R-superlinear convergence of cyclic steepest descent
- On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression
- Global 𝒪(k−2) Convergence of Multilevel Gradient-Regularized Newton Methods
- Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
- Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise
BibTeX
@misc{gu2026superlinear,
title = {{Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes}},
author = {Ran Gu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32705},
eprint = {2610.32705},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32705},
}
RIS
TY - UNPB
TI - Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes
AU - Ran Gu
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32705
UR - https://arxiv.org/abs/2610.32705
AB - Simplified spectral models predict dimension-dependent superlinear convergence for gradient methods, but the corresponding behavior of actual iterations remains only partially understood. Historical methods introduce an additional difficulty: the gradients defining the step sizes differ from those receiving them. We study this offset for cyclic reuse of historical Ritz step sizes on strictly convex quadratics. Within the existing limited memory steepest descent with retards (LMSDR) family, a rolling cyclic Ritz (RCR) rule reuses m historical Ritz values ℓ times per cycle, ending with a complete sweep. At q=m+1 active distinct eigenvalues, an exact delayed recurrence gives almost-everywhere doubly exponential convergence with an explicit rate and exceptional weights. Nonempty open basins also exist for m+1<q≤2m and ℓ≥4. Rebuilding the history from each cycle-start gradient costs m additional updates and gives sampled cyclic Ritz reuse (SCR) a cycle-end map determined by the current weights. Under uniform sampling bounds, SCR converges doubly exponentially almost everywhere when (2ℓ−1)^m>binomq−1m. Increasing ℓ admits larger q for fixed m. The guarantee extends to history-dependent choices from finite sampling menus under a bound on the number of admissible sampling sequences. Geometrically spaced decisions retain the SCR condition and rate range. Every update is counted, including sampling; a numerical illustration compares finite-tolerance update counts.
ER -