# Polynomial Preconditioning for Gradient Methods

arXiv: https://arxiv.org/abs/2301.13194 · HTML: https://mlsanity.com/paper/2301.13194/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Builds on (most cited first, 7 of 7)

- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Super-Acceleration with Cyclical Step-sizes](https://mlsanity.com/paper/2106.09687/) (2021)
- [Universal Average-Case Optimality of Polyak Momentum](https://mlsanity.com/paper/2002.04664/) (2020)
- [A Randomized Coordinate Descent Method with Volume Sampling](https://mlsanity.com/paper/1904.04587/) (2019)
- [Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime](https://mlsanity.com/paper/2206.09901/) (2022)
- [Stochastic Spectral and Conjugate Descent Methods](https://mlsanity.com/paper/1802.03703/) (2018)
- [Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses](https://mlsanity.com/paper/2301.01530/) (2023)

## Built on by (most cited first, 2 of 2)

- [Dual Natural Gradient Descent for Scalable Training of Physics-Informed Neural Networks](https://mlsanity.com/paper/2505.21404/) (2025)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)

## Abstract (arXiv)

We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.