Cyclic steepest descent is R-superlinearly convergent for almost every initialization on two-spectrum quadratics

We completely classify cyclic steepest descent (CSD) on strictly convex quadratics whose Hessian has exactly two distinct eigenvalues. At the beginning of each cycle CSD recomputes an exact steepest-descent stepsize and reuses it for m updates. For every m >= 2, write A = aP + bQ with 0 < a < b and let r = ||Pg||_2 / ||Qg||_2 at a cycle boundary. The exact projective dynamics is r^+ = r^(1-2m). The nonzero equal-norm cone ||Pg_0||_2 = ||Qg_0||_2 is precisely the nonterminating exceptional set: there convergence is R-linear with factor (b-a)/(b+a), whereas every other nonterminating initialization is R-superlinear; one-eigenspace initializations terminate in one step. The exceptional cone has Lebesgue measure zero, so R-superlinear convergence holds almost everywhere in this two-spectrum class. No claim is made for Hessians with three or more distinct eigenvalues.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-01
DOI
https://doi.org/10.5281/zenodo.22211249
Primary Topic
Markov Chains and Monte Carlo Methods
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Cyclic steepest descent is R-superlinearly convergent for almost every initialization on two-spectrum quadratics

Yu Li, Qihang Wang
Zenodo (CERN European Organization for Nuclear Research)
Markov Chains and Monte Carlo Methods
preprint

Cyclic steepest descent is R-superlinearly convergent for almost every initialization on two-spectrum quadratics

Yu Li, Qihang Wang
preprint en

Abstract

We completely classify cyclic steepest descent (CSD) on strictly convex quadratics whose Hessian has exactly two distinct eigenvalues. At the beginning of each cycle CSD recomputes an exact steepest-descent stepsize and reuses it for m updates. For every m >= 2, write A = aP + bQ with 0 < a < b and let r = ||Pg||_2 / ||Qg||_2 at a cycle boundary. The exact projective dynamics is r^+ = r^(1-2m). The nonzero equal-norm cone ||Pg_0||_2 = ||Qg_0||_2 is precisely the nonterminating exceptional set: there convergence is R-linear with factor (b-a)/(b+a), whereas every other nonterminating initialization is R-superlinear; one-eigenspace initializations terminate in one step. The exceptional cone has Lebesgue measure zero, so R-superlinear convergence holds almost everywhere in this two-spectrum class. No claim is made for Hessians with three or more distinct eigenvalues.

Zenodo (CERN European Organization for Nuclear Research)
Peking University (CN), Lanzhou University (CN)
Markov Chains and Monte Carlo Methods
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.