# Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 37 references that are in the map.
- First posted on arXiv 27 Sep 2025.

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

- [Gradient Methods with Online Scaling](https://mlsanity.com/paper/2411.01803/) (2024)
- [Scalable Approximate Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2312.15594/) (2023)
- [Gradient Multi-Normalization for Stateless and Scalable LLM Training](https://mlsanity.com/paper/2502.06742/) (2025)
- [Convergence Rates of Subgradient Methods for Quasi-convex Optimization Problems](https://mlsanity.com/paper/1910.10879/) (2019)

## Abstract (arXiv)

We study optimal diagonal preconditioning using the classical worst-case kappa-condition number and the averaging-based ω-condition number. For the kappa-optimal preconditioning problem, we derive an affine-based pseudoconvex reformulation with three key advantages: all stationary points are global minima, subgradients are inexpensive to compute, and the optimization variable is an n-dimensional vector rather than an n× n matrix as in semidefinite programming (SDP) approaches. We develop a simple and highly efficient subgradient method, with convergence guarantees, for solving this pseudoconvex formulation that is substantially more scalable and accurate than existing SDP-based methods. For the ω-condition number, we provide explicit characterizations of optimal diagonal and block diagonal preconditioners. In particular, we show that several classical preconditioners, including Jacobi and row/column normalization, are ω-optimal, and that matrix balancing schemes monotonically reduce ω and converge to stationary points of the two-sided problem. To the best of our knowledge, this is the first unified and explicit characterization of optimality conditions for both kappa and ω-based preconditioning. Our numerical experiments further reveal a striking phenomenon: although kappa-optimal preconditioners achieve stronger reductions in the worst-case condition number, ω-optimal preconditioners are substantially cheaper to compute and yield better performance for iterative methods such as preconditioned conjugate gradient (PCG) and least squares method (LSQR). Moreover, applying ω-optimal scaling to linear systems that are already kappa-optimally preconditioned leads to further improvements in PCG iterations.