A counterexample to R-superlinear convergence of cyclic steepest descent

Abstract

Cyclic steepest descent recomputes an exact steepest-descent stepsize once per cycle and reuses it for m updates. Dai's ICM 2022 survey states that this method is likely to converge R-superlinearly on n-dimensional convex quadratics when m is at least (n+1)/2. We show that the corresponding universal assertion is false. For n = m = 2, A = diag(1,3), b = 0, and x0 = (1,1/3)^T, the complete orbit is nonterminating: x_k = 2^{-k}(1,(-1)^k/3)^T, and its Euclidean error norm ratio is exactly 1/2 at every iteration. Thus the method is R-linear, not R-superlinear, on this instance. The mechanism is the equal-weight exact-line-search steepest-descent orbit, whose constant stepsize is preserved by cyclic reuse. For this fixed quadratic the witness lies in a Lebesgue-null exceptional set, but one such initialization still refutes a statement quantified over all initializations.