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

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.