Counterexamples to R-superlinear convergence of cyclic steepest descent
Abstract
The cyclic steepest descent method computes the exact steepest descent stepsize at the start of each cycle and reuses it for a fixed number m of iterations. For strictly convex quadratics in n variables, it has been suggested that the method converges R-superlinearly whenever m≥(n+1)/2. We show that this cannot hold for every initial point, already at the threshold cycle length. For n=m=2 we exhibit an initial point from which the method follows the classical zigzag trajectory of steepest descent: the stepsize never changes and the error is halved at every iteration. The same mechanism yields linearly convergent trajectories for every Hessian with at least two distinct eigenvalues and every cycle length. For n=3 and m=2 we construct a second, genuinely three-dimensional counterexample: all components of the gradient remain nonzero, consecutive cycles use two different stepsizes, and every four iterations reduce the gradient exactly by the factor 1/49. Both trajectories are given in closed form. Consequently, any R-superlinear convergence result for this method at the threshold must exclude a set of initial points, as recent almost-everywhere results do.
Related
- Convergence of cyclic steepest descent for quadratics with two distinct eigenvalues
- Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions
- Superlinear Convergence of Cyclic Gradient Methods with Historical Ritz Step Sizes
- PowerStep: Memory-Efficient Adaptive Optimization via ℓp-Norm Steepest Descent
- A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization
BibTeX
@misc{li2026counterexamples,
title = {{Counterexamples to $R$-superlinear convergence of cyclic steepest descent}},
author = {Yu Li and Qihang Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00939},
eprint = {2610.00939},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00939},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counterexamples to R-superlinear convergence of cyclic steepest descent
AU - Yu Li
AU - Qihang Wang
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.00939
UR - https://arxiv.org/abs/2610.00939
AB - The cyclic steepest descent method computes the exact steepest descent stepsize at the start of each cycle and reuses it for a fixed number m of iterations. For strictly convex quadratics in n variables, it has been suggested that the method converges R-superlinearly whenever m≥(n+1)/2. We show that this cannot hold for every initial point, already at the threshold cycle length. For n=m=2 we exhibit an initial point from which the method follows the classical zigzag trajectory of steepest descent: the stepsize never changes and the error is halved at every iteration. The same mechanism yields linearly convergent trajectories for every Hessian with at least two distinct eigenvalues and every cycle length. For n=3 and m=2 we construct a second, genuinely three-dimensional counterexample: all components of the gradient remain nonzero, consecutive cycles use two different stepsizes, and every four iterations reduce the gradient exactly by the factor 1/49. Both trajectories are given in closed form. Consequently, any R-superlinear convergence result for this method at the threshold must exclude a set of initial points, as recent almost-everywhere results do.
ER -