# Fast and Near-Optimal Diagonal Preconditioning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2020.

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

- [Towards Quantifying the Preconditioning Effect of Adam](https://mlsanity.com/paper/2402.07114/) (2024)
- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Tight Clusters Make Specialized Experts](https://mlsanity.com/paper/2502.15315/) (2025)
- [Model Immunization from a Condition Number Perspective](https://mlsanity.com/paper/2505.23760/) (2025)
- [Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2209.00809/) (2022)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)
- [Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries](https://mlsanity.com/paper/2605.23854/) (2026)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)

## Abstract (arXiv)

The convergence rates of iterative methods for solving a linear system A x = b typically depend on the condition number of the matrix A. Preconditioning is a common way of speeding up these methods by reducing that condition number in a computationally inexpensive way. In this paper, we revisit the decades-old problem of how to best improve A's condition number by left or right diagonal rescaling. We make progress on this problem in several directions. First, we provide new bounds for the classic heuristic of scaling A by its diagonal values (a.k.a. Jacobi preconditioning). We prove that this approach reduces A's condition number to within a quadratic factor of the best possible scaling. Second, we give a solver for structured mixed packing and covering semidefinite programs (MPC SDPs) which computes a constant-factor optimal scaling for A in widetildeO(nnz(A) · poly(kappa^star)) time; this matches the cost of solving the linear system after scaling up to a widetildeO(poly(kappa^star)) factor. Third, we demonstrate that a sufficiently general width-independent MPC SDP solver would imply near-optimal runtimes for the scaling problems we consider, and natural variants concerned with measures of average conditioning. Finally, we highlight connections of our preconditioning techniques to semi-random noise models, as well as applications in reducing risk in several statistical regression models.