# Optimal Diagonal Preconditioning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 59 references that are in the map.
- First posted on arXiv 2 Sep 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [An ADMM-Based Interior-Point Method for Large-Scale Linear Programming](https://mlsanity.com/paper/1805.12344/) (2018)
- [Geometry, Computation, and Optimality in Stochastic Optimization](https://mlsanity.com/paper/1909.10455/) (2019)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions](https://mlsanity.com/paper/1612.06965/) (2016)
- [HDSDP: Software for Semidefinite Programming](https://mlsanity.com/paper/2207.13862/) (2022)
- [Preconditioning via Diagonal Scaling](https://mlsanity.com/paper/1610.03871/) (2016)

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

- [Adam-mini: Use Fewer Learning Rates To Gain More](https://mlsanity.com/paper/2406.16793/) (2024)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Towards Quantifying the Hessian Structure of Neural Networks](https://mlsanity.com/paper/2505.02809/) (2025)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Weight Conditioning for Smooth Optimization of Neural Networks](https://mlsanity.com/paper/2409.03424/) (2024)
- [Structured Semidefinite Programming for Recovering Structured Preconditioners](https://mlsanity.com/paper/2310.18265/) (2023)
- [On the Principles Behind Neural Network Optimizers](https://mlsanity.com/paper/2608.16760/) (2026)

## Abstract (arXiv)

Preconditioning has long been a staple technique in optimization, often applied to reduce the condition number of a matrix and speed up the convergence of algorithms. Although there are many popular preconditioning techniques in practice, most lack guarantees on reductions in condition number. Moreover, the degree to which we can improve over existing heuristic preconditioners remains an important practical question. In this paper, we study the problem of optimal diagonal preconditioning that achieves maximal reduction in the condition number of any full-rank matrix by scaling its rows and/or columns. We first reformulate the problem as a quasi-convex problem and provide a simple algorithm based on bisection. Then we develop an interior point algorithm with O(log(1/ε)) iteration complexity, where each iteration consists of a Newton update based on the Nesterov-Todd direction. Next, we specialize to one-sided optimal diagonal preconditioning problems, and demonstrate that they can be formulated as standard dual SDP problems. We then develop efficient customized solvers and study the empirical performance of our optimal diagonal preconditioning procedures through extensive experiments on large matrices. Our findings suggest that optimal diagonal preconditioners can significantly improve upon existing heuristics-based diagonal preconditioners at reducing condition numbers and speeding up iterative methods. Moreover, our implementation of customized solvers, combined with a random row/column sampling step, can find near-optimal diagonal preconditioners for matrices up to size 200,000 in reasonable time, demonstrating their practical appeal.