Learning to Discover Iterative Spectral Algorithms
This work addresses the need for efficient algorithms in numerical linear algebra and optimization, offering a novel method for automating algorithm discovery, though it is incremental as it builds on classical spectral theory.
The authors tackled the problem of discovering iterative spectral algorithms for large-scale numerical linear algebra and optimization by introducing AutoSpec, a neural network framework that predicts recurrence coefficients based on coarse spectral information, resulting in orders-of-magnitude improvements in accuracy and reductions in iteration count on real-world matrices.
We introduce AutoSpec, a neural network framework for discovering iterative spectral algorithms for large-scale numerical linear algebra and numerical optimization. Our self-supervised models adapt to input operators using coarse spectral information (e.g., eigenvalue estimates and residual norms), and they predict recurrence coefficients for computing or applying a matrix polynomial tailored to a downstream task. The effectiveness of AutoSpec relies on three ingredients: an architecture whose inference pass implements short, executable numerical linear algebra recurrences; efficient training on small synthetic problems with transfer to large-scale real-world operators; and task-defined objectives that enforce the desired approximation or preconditioning behavior across the range of spectral profiles represented in the training set. We apply AutoSpec to discovering algorithms for representative numerical linear algebra tasks: accelerating matrix-function approximation; accelerating sparse linear solvers; and spectral filtering/preconditioning for eigenvalue computations. On real-world matrices, the learned procedures deliver orders-of-magnitude improvements in accuracy and/or reductions in iteration count, relative to basic baselines. We also find clear connections to classical theory: the induced polynomials often exhibit near-equiripple, near-minimax behavior characteristic of Chebyshev polynomials.