Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions
Abstract
We study the cyclic steepest descent method (CSD) for strictly convex quadratic minimization. CSD repeats, for j consecutive iterations, the exact steepest-descent step size computed at the beginning of each cycle. The only rigorous result for the real algorithm has so far been restricted to two dimensions, where the cycle-starting gradient sequence is known to converge doubly exponentially. For the simplified ("simple") model obtained by discarding bounded logarithmic terms, Dai and Fletcher predicted that CSD is superlinear whenever the number n of distinct eigenvalues is below twice the cycle length m, and linear otherwise. Let A be symmetric positive definite with q distinct eigenvalues, and suppose 2j > q. We prove the superlinear side of this threshold for the real algorithm in arbitrary dimensions, and in fact obtain a faster, doubly exponential, decay. Except for a Lebesgue-null set of initial points, for every kappa below an explicit positive threshold kappa_0, the cycle-starting gradient satisfies ||g_k|| <= exp(-C exp(kappa k)), and the full gradient and iterate errors satisfy analogous bounds with exponent kappa/j after m iterations. This is the first rigorous proof for the real CSD in arbitrary dimensions, including repeated eigenvalues, and confirms the threshold 2j > q (the simple-model prediction n < 2m); the doubly exponential rate is faster than the superlinear one predicted by the simple model. The proof combines arbitrary-reference ratio coordinates, inverse-image volume contraction, thin-band estimates, and a per-component Borel-Cantelli argument.
Related
- Convergence of cyclic steepest descent for quadratics with two distinct eigenvalues
- R-Linear Convergence of Barzilai-Borwein Methods on Strictly Convex Quadratics via Closed-Cone Homogeneous Dynamics
- Global and Unconditional R-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics
- Counterexamples to R-superlinear convergence of cyclic steepest descent
- Performance Evaluation of an Adaptive Quadrature and a Double Exponential Formula Using Arbitrary-Precision Floating-Point Arithmetic
BibTeX
@misc{gu2026doubly,
title = {{Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions}},
author = {Ran Gu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25800},
eprint = {2609.25800},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25800},
}
RIS
TY - UNPB
TI - Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions
AU - Ran Gu
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.25800
UR - https://arxiv.org/abs/2609.25800
AB - We study the cyclic steepest descent method (CSD) for strictly convex quadratic minimization. CSD repeats, for j consecutive iterations, the exact steepest-descent step size computed at the beginning of each cycle. The only rigorous result for the real algorithm has so far been restricted to two dimensions, where the cycle-starting gradient sequence is known to converge doubly exponentially. For the simplified ("simple") model obtained by discarding bounded logarithmic terms, Dai and Fletcher predicted that CSD is superlinear whenever the number n of distinct eigenvalues is below twice the cycle length m, and linear otherwise. Let A be symmetric positive definite with q distinct eigenvalues, and suppose 2j > q. We prove the superlinear side of this threshold for the real algorithm in arbitrary dimensions, and in fact obtain a faster, doubly exponential, decay. Except for a Lebesgue-null set of initial points, for every kappa below an explicit positive threshold kappa_0, the cycle-starting gradient satisfies ||g_k|| <= exp(-C exp(kappa k)), and the full gradient and iterate errors satisfy analogous bounds with exponent kappa/j after m iterations. This is the first rigorous proof for the real CSD in arbitrary dimensions, including repeated eigenvalues, and confirms the threshold 2j > q (the simple-model prediction n < 2m); the doubly exponential rate is faster than the superlinear one predicted by the simple model. The proof combines arbitrary-reference ratio coordinates, inverse-image volume contraction, thin-band estimates, and a per-component Borel-Cantelli argument.
ER -