# Scalable Approximate Optimal Diagonal Preconditioning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Dec 2023.

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

- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/2502.11229/) (2025)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [Gradient Methods with Online Scaling Part II. Practical Aspects](https://mlsanity.com/paper/2509.11007/) (2025)
- [Optimization Geometrodynamics: Variational Reduction and Interaction Curvature](https://mlsanity.com/paper/2607.06723/) (2026)
- [Interior-Point Vanishing Problem in Semidefinite Relaxations for Neural Network Verification](https://mlsanity.com/paper/2506.10269/) (2025)
- [Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling](https://mlsanity.com/paper/2509.23439/) (2025)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)

## Abstract (arXiv)

We consider the problem of finding the optimal diagonal preconditioner for a positive definite matrix. Although this problem has been shown to be solvable and various methods have been proposed, none of the existing approaches are scalable to matrices of large dimension, or when access is limited to black-box matrix-vector products, thereby significantly limiting their practical application. In view of these challenges, we propose practical algorithms applicable to finding approximate optimal diagonal preconditioners of large sparse systems. Our approach is based on the idea of dimension reduction, and combines techniques from semi-definite programming (SDP), random projection, semi-infinite programming (SIP), and column generation. Numerical experiments demonstrate that our method scales to sparse matrices of size greater than 107. Notably, our approach is efficient and implementable using only black-box matrix-vector product operations, making it highly practical for a wide variety of applications.