OpenAlex ·

Counterexamples to $R$-superlinear convergence of cyclic steepest descent

Yu Li and Qihang Wang

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.00939
Original
Read it at the publisher
Topics
Computational ComplexityNumerical Analysis

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\ge(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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Computational Complexity

Get the few papers worth your time in Computational Complexity every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics