Doubly exponential convergence of the cyclic steepest descent method for strictly convex quadratics in arbitrary dimensions
En palabras de los autores
We study the cyclic steepest descent method (CSD) for strictly convex quadratic minimization. CSD repeats, for j consecutive iterations, the exact steepest-descent step size computed at the beginning of each cycle. The only rigorous result for the real algorithm has so far been restricted to two dimensions, where the cycle-starting gradient sequence is known to converge doubly exponentially. For the simplified ("simple") model obtained by discarding bounded logarithmic terms, Dai and Fletcher predicted that CSD is superlinear whenever the number n of distinct eigenvalues is below twice the cycle length m, and linear otherwise. Let A be symmetric positive definite with q distinct eigenvalues, and suppose 2j > q. We prove the superlinear side of this threshold for the real algorithm in arbitrary dimensions, and in fact obtain a faster, doubly exponential, decay. Except for a Lebesgue-null set of initial points, for every kappa below an explicit positive threshold kappa_0, the cycle-starting gradient satisfies ||g_k|| <= exp(-C exp(kappa k)), and the full gradient and iterate errors satisfy analogous bounds with exponent kappa/j after m iterations. This is the first rigorous proof for the real CSD in arbitrary dimensions, including repeated eigenvalues, and confirms the threshold 2j > q (the simple-model prediction n < 2m); the doubly exponential rate is faster than the superlinear one predicted by the simple model. The proof combines arbitrary-reference ratio coordinates, inverse-image volume contraction, thin-band estimates, and a per-component Borel-Cantelli argument.
Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 20 pages