WorksMathematics
Counterexamples to -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 of iterations. For strictly convex quadratics in variables, it has been suggested that the method converges -superlinearly whenever . We show that this cannot hold for every initial point, already at the threshold cycle length. For 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 and 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 . Both trajectories are given in closed form. Consequently, any -superlinear convergence result for this method at the threshold must exclude a set of initial points, as recent almost-everywhere results do.
Introduction
Cyclic steepest descent (CSD) reuses an exact steepest-descent stepsize for a prescribed number of consecutive updates. It is a special delayed gradient method in the sense of Friedlander, Martínez, Molina, and Raydan [6]; Dai and Fletcher studied its asymptotic behavior on positive-definite quadratics [3]. With reference to that analysis, Dai’s ICM 2022 survey states that CSD is likely to converge -superlinearly when the cycle length satisfies [2]; the survey writes the condition as , which for integer is the ceiling condition used here and is equivalent to , the superlinear side of the threshold in the simplified model of Dai and Fletcher. The ICM Conjectures directory records the corresponding universal assertion as problem 2022-opt-18 [8]. Our counterexamples address this universal formulation, not an almost-everywhere interpretation of the survey’s conjectural statement.
Theorem 3.1 gives a counterexample at the smallest nontrivial dimension and cycle length (for the method terminates after one update), with error norm ratio at every actual update. The statement describes the complete orbit, not a finite numerical trace. Proposition 3.2 extends this invariant family to arbitrary pairs of eigendirections and cycle lengths.
Theorem 3.3 gives a second obstruction at the three-dimensional threshold: and . All three spectral components remain nonzero. The cycle-boundary weights alternate between two interior points of the simplex, and every four updates multiply the gradient and error by . The proof identifies the two Rayleigh quotients and verifies the two weight transitions exactly. Thus both counterexamples describe entire trajectories, but only the first uses a constant stepsize.
The underlying spectral mechanism is classical for ordinary exact-line-search steepest descent. Akaike’s probability-map analysis contains the equal-weight fixed distribution [1], and Yu recently stated the corresponding worst-case linear orbit and its higher-dimensional embedding explicitly [13 Proposition 3.1 of the arXiv version]. The decisive observation for CSD is that the exact stepsize is constant on this orbit. Consequently, cyclic reuse for any number of updates preserves the orbit exactly, turning the classical equal-weight trajectory into a threshold counterexample to the universal CSD assertion.
Periodic behavior under cyclic reuse has a direct precedent. Dai, Hager, Schittkowski, and Zhang [4 Section 3.3] identify the alternate-step method as CSD with and construct a five-dimensional cyclic example. Theorem 3.3 provides a closed-form full-support example at the three-dimensional threshold; periodic CSD behavior itself is already documented. The alternate minimization method of Dai and Yuan [5] uses different steps and has a two-dimensional -superlinear result. Shen, Li, and Dai [11 Theorem 1] state -superlinear convergence of the cycle-boundary gradient subsequence for two-dimensional CSD; their argument parameterizes the initial gradient by the logarithm of its component ratio and uses that this logarithm is nonzero. The balanced initializations of Theorem 3.1 and Proposition 3.2 are exactly the fixed point of their recurrence at which this logarithm vanishes, where the cycle-boundary subsequence is geometric; this boundary case is treated here. Their revised preprint studies the triangle steepest-descent method instead [12].
The companion paper [9 Theorem 3.1] classifies CSD for Hessians with exactly two distinct eigenvalues and arbitrary eigenspace multiplicities. For , the equal-norm spectral-block cone is precisely the nonterminating exceptional set; every other mixed initialization is -superlinear. In the fixed two-dimensional instance here this cone is the union of two lines. The two papers therefore separate the construction of exact exceptions from the classification of all initializations for two-spectrum Hessians. A recent preprint of Gu [7 Theorem 2.1] states an almost-everywhere doubly exponential convergence theorem for general spectra when exceeds the number of distinct eigenvalues. Both instances here satisfy that condition, so by that theorem the orbits constructed below must lie in its Lebesgue-null exceptional set; by Theorem 3.3 that set can contain full-support, nonresonant orbits, so it cannot be dropped. Exact exceptional orbits and almost-everywhere convergence are compatible. Neither positive result is needed in our proofs.
§ 2 fixes the method, the notation, and the rate terminology. § 3 proves the two counterexamples and the invariant family. § 4 summarizes the consequences.
Cyclic Steepest Descent
On , let
where , and write . All norms are Euclidean. The method terminates whenever . Otherwise, the exact steepest-descent stepsize is
Let be an integer. At the boundary of cycle , CSD computes from (2) and performs the updates
Thus a newly computed exact stepsize is used for exactly consecutive updates. Equivalent index shifts do not change the method. The unique minimizer of (1) is . Set
For any update with stepsize ,
A null sequence converges -superlinearly if , that is, if its root-convergence factor is zero [10 Chapter 9]; equivalently, is bounded by a null sequence whose successive ratios tend to zero, which is the form used in [11]. It converges -linearly if this root factor lies in . A positive geometric lower bound on the errors, even along a fixed-stride subsequence, forces a positive root factor and hence excludes -superlinear convergence. This elementary observation suffices for the exact orbits below.
Exact Counterexamples
The Balanced Zig-Zag Obstruction
Theorem 3.1 (Exact threshold counterexample) Let
Every stepsize recomputed by CSD is , and the complete orbit is
It is nonterminating and satisfies
Consequently, the assertion of universal -superlinear convergence for does not hold.
Proof of Theorem 3.1. Here and . Whenever a cycle starts with two gradient components of equal magnitude, its recomputed stepsize is
For this stepsize,
The two component magnitudes therefore remain equal after each of the two updates in a cycle. Induction over the cycles gives (7); applying gives (8), and (9) follows. In particular , so the error sequence has exactly -linear convergence with factor and hence, by the observation of Section 2, is not -superlinearly convergent. Finally, is the smallest admissible integer cycle length, so the universal assertion fails at its threshold. The proof is complete. ☐
The same calculation extends to any pair of eigendirections and any cycle length.
Proposition 3.2 (Two-eigendirection invariant family) Let have orthonormal eigenvectors with distinct eigenvalues , respectively. Fix any cycle length , any , and any . Initialize CSD so that
Define
Then every stepsize recomputed at a cycle boundary is
and the full orbit is
In particular,
None of the full gradient sequence, the full error sequence, and their cycle-boundary subsequences converges -superlinearly.
Proof of Proposition 3.2. For a vector of the form with and , orthonormality and the eigenvalue relations give
For this stepsize,
Equation (5) therefore changes the sign of the -component and multiplies both component magnitudes by . After any number of updates, and hence at every cycle boundary, the two components still have equal magnitude. Induction proves (12) and (13). Applying gives (14).
The norms of the two parenthesized vectors in (13) and (14) are independent of , so (15) follows. The full sequences are geometric with factor , while their cycle-boundary subsequences are geometric with factor in the cycle index; by the observation of § 2, none of them converges -superlinearly. The proof is complete. ⊓⊔
A Full-Support Non-Zig-Zag Obstruction
Theorem 3.3 (Full-support three-spectral period-two counterexample). Let
and set
Define
The CSD orbit is nonterminating, has full support (every component of is nonzero for every ), and is nonresonant: no cycle-boundary stepsize annihilates a spectral component, i.e., for every . The orbit has projective period two at cycle boundaries: writing , the normalized squared component weights alternate between two distinct interior points of the simplex. The stepsize pattern is , and
Consequently the orbit is -linearly convergent with root factor , but not -superlinearly convergent, and it is not a two-dimensional balanced-zigzag orbit.
Proof of Theorem 3.3. For a nonzero gradient , write and , where . At a cycle boundary the exact stepsize is ; after two updates the th gradient component is multiplied by . Therefore the normalized squared component weights obey the map
Let , whose entries sum to one, so that is the initial weight vector; let be obtained by interchanging with in the three entries. Explicitly,
Both vectors are positive and sum to one, so they are interior points of the simplex. Their weighted means are and , respectively. Since
direct substitution gives
Hence and , so and for every . This proves the cycle-boundary projective period two and the displayed stepsize pattern. Since , each update multiplies every gradient component by a nonzero factor ; hence all three components are nonzero at every iteration, so the orbit is nonterminating, has full support, and is nonresonant. Moreover , so over the four updates the th gradient component is multiplied by
for each . Any four consecutive updates contain two factors of each type, and these diagonal update matrices commute. Thus the identity holds for every starting index , proving (18); applying gives the error relation. The subsequence is positive geometric with ratio , so by the observation of Section 2 the orbit is not -superlinearly convergent, while (18) gives the stated -linear root factor . The proof is complete. ⊓⊔
Remark 3.4 (Higher-dimensional embedding). For every and , augment by arbitrary positive diagonal entries and initialize the added gradient components at zero. They remain zero, so the active plane follows Proposition 3.2, and the obstruction occurs in every dimension and at every cycle length as a lower-dimensional support phenomenon. Theorem 3.3 is different: all three spectral components are nonzero, so its obstruction is full-support. Either theorem alone disproves the universal statement.
Conclusions
Cyclic reuse preserves the classical balanced orbit and also admits the full-support three-dimensional periodic orbit constructed above. Together these examples show why a universal convergence guarantee must account for exact exceptional initializations, even at the proposed cycle threshold. The three-dimensional construction also shows that full spectral support does not exclude periodic projective dynamics.
Sampling from a distribution absolutely continuous with respect to Lebesgue measure misses a fixed Lebesgue-null set with probability one, whereas prescribed or discretely sampled initializations may lie on it. Exceptional-orbit checks therefore matter for guarantees covering a specified initialization, alongside almost-everywhere convergence results.
Acknowledgements We thank Yu-Hong Dai for helpful comments on the exceptional-orbit calculation, its interpretation as a classical zigzagging trajectory, and the distinction between universal and almost-everywhere convergence. We acknowledge Gewu Intelligence Lab for providing the collaborative research environment in which this project was developed.
Declarations
Funding. No funding was received for this work.
Competing interests. The authors declare no competing interests.
Data availability. No datasets were generated or analysed. The results are established analytically in the article.
Disclosure of automated assistance
The main results of this paper were obtained through a generative-AI workflow using OpenAI GPT-5.6 Sol, Anthropic Claude Fable 5, OpenAI GPT-6 Astra, OpenAI GPT-6.1 Sol, Anthropic Claude Fable 5.1, and Anthropic Claude Opus 5.5. The workflow contributed to identifying and checking the exact counterexamples, reviewing the cited literature, and preparing and revising the LaTeX manuscript.
References
- [1]Hirotugu Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, *Ann. Inst. Stat. Math.* 11 (1959), no. 1, 1–16. https://doi.org/10.1007/BF01831719.
- [2]Yu-Hong Dai, An overview of nonlinear optimization, in *Proceedings of the International Congress of Mathematicians—2022*, vol. 7, 5290–5313, EMS Press, Berlin, 2023. https://doi.org/10.4171/ICM2022/72.
- [3]Yu-Hong Dai and Roger Fletcher, On the asymptotic behaviour of some new gradient methods, *Math. Program.* 103 (2005), no. 3, 541–559. https://doi.org/10.1007/s10107-004-0516-9.
- [4]Yu-Hong Dai, William W. Hager, Klaus Schittkowski, and Hongchao Zhang, The cyclic Barzilai–Borwein method for unconstrained optimization, *IMA J. Numer. Anal.* 26 (2006), no. 3, 604–627. https://doi.org/10.1093/imanum/drl006.
- [5]Yu-Hong Dai and Ya-Xiang Yuan, Alternate minimization gradient method, *IMA J. Numer. Anal.* 23 (2003), no. 3, 377–393. https://doi.org/10.1093/imanum/23.3.377.
- [6]Ana Friedlander, José Mario Martínez, Brigida Molina, and Marcos Raydan, Gradient method with retards and generalizations, *SIAM J. Numer. Anal.* 36 (1998), no. 1, 275–289. https://doi.org/10.1137/S003614299427315X.
- [7]Ran Gu, *Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions*, arXiv:2609.25800v1 [math.OC] (2026).arXiv
- [8]Conjectures, I. (2026). Entry 2022-opt-18: cyclic steepest descent, curated online directory. https://icmconjectures.com/2022-opt-18icmconjectures.com/2022-opt-18
- [9]Yu Li and Qihang Wang, *Convergence of cyclic steepest descent for quadratics with two distinct eigenvalues*, arXiv:2610.15335v2 [math.OC] (2026).arXiv
- [10]James M. Ortega and Werner C. Rheinboldt, *Iterative Solution of Nonlinear Equations in Several Variables*, Classics in Applied Mathematics, vol. 30, SIAM, Philadelphia, 2000. https://doi.org/10.1137/1.9780898719468.
- [11]Shen, Y., Li, Q.-N., & Dai, Y.-H. (2025). On the acceleration of gradient methods: the triangle steepest descent method. arXiv:2501.16731v1
- [12]Ya Shen, Qing-Na Li, and Yu-Hong Dai, *Triangle steepest descent: a geometry-based gradient algorithm with guaranteed R-linear convergence*, arXiv:2501.16731v2 [math.OC], revised October 17, 2025.arXiv
- [13]Thomas Yu, The essential best and average rate of convergence of the exact line search gradient descent method, *Numer. Algorithms* 103 (2026), no. 1, 683–710. https://doi.org/10.1007/s11075-025-02244-0. arXiv:2305.09140v4 [math.OC].