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

arXiv:2509.23439 · math.OC, cs.LG, cs.NA, math.NA · Submitted 2025-09-27 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning".

Jane: The gist The authors study optimal diagonal preconditioning under two distinct notions of conditioning—the classical worst-case κ-condition number and the averaging-based ω-condition number—and find that ω-optimal preconditioning generally outperforms κ-optimal…

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper now, "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling." It’s by Ghadimi, Jung, Sujanani, Torregrossa-Belen´§ and Wolkowicz.

Jane: It tackles how we precondition linear systems to make iterative methods like PCG or LSQR run faster. The title tells us it's looking at going beyond the classical worst-case condition number and looking at something else called the omega condition number.

Tom: Exactly. So, what this paper is doing is comparing two ways of finding optimal diagonal preconditioners: one based on the worst-case kappa kappa condition number, and another based on an averaging concept called the omega omega condition number.

Jane: And they found that when you look at it practically, the omega optimal preconditioning usually beats the kappa optimal preconditioning in terms of computational cost and how well it actually makes those iterative methods perform.

Lu: It’s interesting because for the kappa problem, they set up this affine-based pseudoconvex reformulation. That means all the stationary points are global minima, and they can use a simple subgradient method to find them without needing heavy semidefinite programming approaches which involve n times n matrices <ref:2509.23439#pg6>.

Meng: That sounds good for theory, but from an engineering standpoint, I’m more interested in what this means for building these preconditioners on real-world sparse matrices. How much cheaper is this subgradient method compared to those SDP approaches they're comparing it to?

Tom: They did show that their method is more scalable and efficient at computing kappa optimal diagonal preconditioners than existing SDP-based approaches in the literature one thousand two hundred twenty-five <ref:2509.23439#pg1>. Plus, they found that the resulting preconditioners yield more substantial improvements in PCG performance compared to those produced by twelve twenty-five <ref:2509.23439#pg1>.

Jane: So we're talking about a method that finds a good diagonal scaling much faster computationally and one that gives better actual speedups for solving those linear systems. This paper is called "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling" <ref:2509.23439#pg1>.

Lu: They also provided explicit characterizations for the omega condition number, showing that classical things like Jacobi scaling are actually omega optimal preconditioners, which is a nice result because it validates some existing methods in a new light <ref:2509.23439#pg28>.

Meng: That’s something I can see applying right away. If we can find an explicit formula for these block diagonal preconditioners, like the ones they discuss for tall full-rank matrices A, that's huge for practical implementation <ref:2509.23439#pg3>.

Tom: Right. And they show that this characterization works by looking at Q-less QR decompositions of the blocks of A to find the right-sided omega optimal block-diagonal preconditioner <ref:2509.23439#pg28>. That’s a concrete recipe for finding a better preconditioner structure.

Jane: And they found that applying this omega optimal scaling to linear systems that are already kappa optimally preconditioned leads to further improvements in PCG iterations, often reducing the number of iterations by a factor of thirty-eight point five on average <ref:2509.23439#pg26>.

Title and authors: Meng: Thirty-eight point five is a lot of reduction in iteration counts. If we're talking about solving systems with hundreds of thousands of variables, that kind of reduction can translate to solving them within minutes instead of hours Lu.

Tom: That’s the practical implication there. They also showed that the Sinkhorn-Knopp algorithm converges to a stationary point of the two-sided omega optimal preconditioning problem and produces preconditioners that significantly outperform the two-sided kappa optimal method of twenty-five in terms of LSQR iteration counts for minimizing b ax <ref:2509.23439#pg3>.

Jane: So, we have this theory about omega scaling, and we see it’s practically superior to the worst-case approach because it makes the actual iterative work much faster and cheaper.

Lu: They also developed a two-sided matrix balancing scheme where they alternate between column and row normalization to reduce the omega value at each iteration <ref:2509.23439#pg21>. This is related to the Square-Root Sinkhorn–Knopp algorithm, which converges linearly to a matrix where all column and row norms are equal to one <ref:2509.23439#pg21>.

Meng: Alternating right and left scaling sounds like something we could build into our iterative solvers. It’s an iterative process that tries to reach a balanced state, which is mathematically sound for improving the omega condition number <ref:2509.23439#pg28>.

Tom: And they showed that the optimality conditions for this two-sided problem imply that the column and row norms of the optimal solution must all be equal to a constant, which is characterized by equation three point one zero <ref:2509.23439#pg10>. That confirms why this balancing scheme works so well.

Jane: It really boils down to moving away from just obsessing over the absolute worst-case scenario when designing these preconditioners for large problems, which is what this paper suggests with their focus on omega scaling <ref:2509.23439#pg6>.

Lu: They also looked at block diagonal preconditioning for least squares solutions of full rank possibly overdetermined linear systems, showing the optimal block diagonal scaling B satisfies a specific factorization involving p a t i and t i <ref:2509.23439#pg19>.

Meng: That’s an extension that’s very useful because many real-world problems we face are not square matrices, but overdetermined systems where you have more equations than variables <ref:2509.23439#pg19>.

Tom: And they linked it back to QR decomposition for these block diagonal solutions, showing that if the blocks are upper-triangular, the optimal B is related to R one i and Q i R i from the QR decomposition of Ai <ref:2509.23439#pg19>.

Jane: So they’ve given us a way to handle those non-square systems by using these structured block diagonal approaches derived from the omega analysis.

Lu: They also provided a simple and highly efficient subgradient method, Algorithm two point two, that exploits the pseudoconvex structure of the kappa optimal preconditioning problem <ref:2509.23439#pg11>. This method has convergence guarantees and all stationary points are global minima <ref:2509.23439#pg1>.

Title and authors: Meng: That’s a big help for us because it means we don't have to rely on those heavy SDP methods just to find a good kappa preconditioner anymore, which makes the whole process much more accessible <ref:2509.23439#pg11>.

Tom: And they also introduced a reformulation of the minimization problem that removes positive homogeneity, which helps with computational stability in practice <ref:2509.23439#pg24>. This is important because it makes the subgradient method more reliable when you're running it on real hardware.

Jane: So to wrap up this section, we’ve seen how they characterized both kappa and omega optimal preconditioners, and they’ve shown that the omega approach offers better performance for iterative methods like PCG and LSQR <ref:2509.23439#pg6>.

Lu: They also showed that applying the omega optimal diagonal scaling to matrices already kappa optimally scaled leads to significant improvements in PCG performance, often reducing the number of iterations by a factor of thirty-eight point five on average <ref:2509.23439#pg26>.

Meng: That's a huge practical win for anyone using these iterative solvers. It’s not just theoretical reduction; it’s tangible speedup in real computation, which is what I care about most <ref:2509.23439#pg11>.

Tom: So, to summarize this paper, the core message of "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling" is that omega-based preconditioning provides a computationally efficient and practically superior alternative to kappa-based approaches for large scale problems <ref:2509.23439#pg6>.

Jane: They are showing us that even though the worst-case kappa condition number reduction might look aggressive on paper, the omega approach is substantially cheaper to compute and more strongly correlated with how well those iterative methods like PCG and LSQR actually perform <ref:2509.23439#pg26>.

Lu: It highlights that moving beyond just worst-case conditioning when designing preconditioners is important for practical application in large scale problems <ref:2509.23439#pg6>.

Meng: For us, it means we should probably prioritize these omega-based scaling strategies over the kappa ones unless we have a very specific reason to worry about the absolute worst-case number <ref:2509.23439#pg6>.

Tom: Well, that’s what this paper is all about. We’ve discussed the theory behind omega scaling, how it beats the worst-case kappa approach in terms of speed and cost, and we've seen how it applies to practical problems like block diagonal preconditioners <ref:2509.23439#pg19>.

Jane: This paper really gives us a solid framework for designing better preconditioning strategies, especially when dealing with large sparse matrices or overdetermined systems <ref:2509.23439#pg6>.

Lu: And we’re looking forward to seeing how this omega theory can be extended into more complex settings in the future <ref:2509.23439#pg6>.

Meng: I'm curious to see how quickly we can integrate these scaling strategies into our existing solvers for real-time applications <ref:2509.23439#pg11>.

Tom: That’s the path forward, folks. We’re done with this paper on "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling" for today.

The paper's summary: Tom: So, to wrap up this paper, Ghadimi and his team are showing us that when we design diagonal preconditioners for big linear systems, we don't always have to obsess over the absolute worst-case scenario.

Jane: They’re proposing omega scaling as a way to look at it. It’s about moving away from just aiming for the biggest possible condition number reduction and focusing on something more practical called the omega condition number.

Lu: They give explicit formulas for what these optimal diagonal and block diagonal preconditioners actually look like. For instance, classical things like Jacobi scaling turn out to be omega optimal solutions or at least stationary points <ref:2509.23439#pg28>.

Meng: That’s good because it means existing methods we already use, the ones that are pretty simple, can actually be optimal under this new omega metric.

Tom: But the real punch comes when they compare them to kappa scaling for things like PCG and LSQR. The results show that while kappa scaling might slash the worst-case number aggressively, it’s not always the best for how fast those iterative solvers actually run.

Jane: And omega scaling wins on performance for those iterative methods. They’re substantially cheaper to build, and they lead to much better actual speedups in practice when you’re solving a linear system.

Lu: They showed that applying this omega optimal diagonal scaling to systems that are already kappa optimally preconditioned gives huge benefits, sometimes reducing the iteration count by over thirty-eight point five percent <ref:2509.23439#pg26>.

Meng: Thirty-eight point five percent reduction in iterations is a massive win for real computation. That translates directly into solving those kinds of large sparse problems way faster than before, which is exactly what we need at this startup.

Tom: And they handled non-square systems too. They found explicit ways to find the optimal block diagonal scaling B for those overdetermined linear systems by looking at QR decompositions of the matrix blocks <ref:2509.23439#pg19>.

Jane: So, what this paper really changes for us is that we have a much more grounded way to think about preconditioners. Instead of just chasing the theoretical worst case, we can design things based on how the actual math works for iterative solvers.

Lu: They developed a two-sided matrix balancing scheme where you alternate between column and row normalization to drive that omega number down <ref:2509.23439#pg21>. It converges to a perfectly balanced matrix where all column and row norms are equal, which is the necessary condition for optimality <ref:2509.23439#pg10>.

Tom: The implication here is that we can stop relying on those heavy semidefinite programming approaches just to find a good kappa preconditioner, because they have this simpler subgradient method that has convergence guarantees <ref:2509.23439#pg11>.

Jane: It’s about making the tools easier to use for people who are actually building things, not just doing pure math research. The focus shifts from finding a perfect worst-case solution to finding a very good, practical one that actually makes the software run well.

The paper's improvements: Tom: So, we're looking at what else this paper suggests we should be doing because of these omega results <ref:2509.23439#pg6>. It’s not just a trick for one problem; it’s a new way to look at preconditioners generally.

Jane: Exactly. They suggest that when you're designing any solver for large systems, especially those with sparse matrices, you should stop just looking at the absolute worst-case condition number <ref:2509.23439#pg6>.

Lu: Instead, the paper pushes us to use a unified characterization. This lets us pick a scaling strategy based on what actually matters for performance metrics like PCG iteration counts <ref:2509.23439#pg6>.

Meng: For an engineer like me, that means we can prioritize these omega-based scaling strategies over the kappa ones most of the time because they are cheaper to compute and give better actual speedups for our solvers <ref:2509.23439#pg26>.

Tom: It’s about practical performance versus theoretical worst-case reduction. The paper suggests that even if a kappa method seems theoretically aggressive, the omega method is far more relevant to how our code actually runs on real hardware <ref:2509.23439#pg6>.

Jane: And they show that this approach works across different matrix structures too. They gave explicit recipes for block diagonal preconditioners for overdetermined systems, which is something a lot of us deal with in data science <ref:2509.23439#pg19>.

Lu: They showed that you can use QR decompositions to find the right scaling B for those blocks, which is a concrete way to build those structures without needing heavy machinery like semidefinite programming <ref:2509.23439#pg11>.

Meng: That makes sense because we need recipes, not just high-level theory. If we can get an explicit formula for block diagonal scaling, that’s a huge step for implementation speed <ref:2509.23439#pg19>.

Tom: And they developed this two-sided matrix balancing scheme <ref:2509.23439#pg21>. It alternates between column and row normalization to systematically reduce the omega value until you get a balanced matrix where all norms are equal <ref:2509.23439#pg10>.

Jane: So, instead of picking one fixed scaling and hoping for the best, we have an iterative process that actively tries to find that balanced state for better performance <ref:2509.23439#pg21>.

Lu: And they showed this process relates to algorithms like the Sinkhorn-Knopp algorithm, which is a really interesting connection to other areas of matrix scaling <ref:2509.23439#pg21>.

Tom: The implication for the future is that we should be designing preconditioners with this performance metric in mind from the start <ref:2509.23439#pg6>. It shifts the focus away from just minimizing some theoretical number and toward optimizing how our solvers actually perform on large, messy data.

Conclusion: Tom: So we're wrapping up this look at "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling." Basically, we’ve seen that omega scaling gives us a much better way to choose preconditioners for iterative methods like PCG and LSQR <ref:2509.23439#pg6>.

Jane: It boils down to this idea that when you're doing large-scale linear algebra, you should care more about how the solver actually performs in practice than just chasing the absolute worst-case theoretical number <ref:2509.23439#pg6>.

Lu: They’ve shown that this omega approach is not just theoretical; it gives us a concrete recipe for finding block diagonal preconditioners for those non-square systems, linking it directly to QR decompositions <ref:2509.23439#pg19>.

Meng: That structure is what matters. If we can build a recipe that works on those real-world overdetermined matrices, that’s where the real engineering value is found <ref:2509.23439#pg19>.

Lalam: From an AI culture standpoint, this means our AI systems won't just be theoretically optimized for a worst-case scenario; they'll be tuned to perform better on the actual data we feed them, which builds more reliable and trustworthy applications <ref:2509.23439#pg6>.

Tom: The big picture here is that we can move toward designing solvers that are inherently more efficient because we’re using a metric that reflects reality, not just the theoretical limits of the problem <ref:2509.23439#pg6>.

Jane: It's about moving beyond worst-case conditioning when designing these preconditioners for large problems, which is what this paper suggests with their focus on omega scaling <ref:2509.23439#pg6>.

Lu: They also showed that the optimality conditions for the two-sided problem imply that the column and row norms must all be equal, which is a necessary condition for any optimal solution <ref:2509.23439#pg10>.

Meng: That balancing scheme, alternating between column and row normalization to reach that balanced state, is something we could definitely integrate into our solvers for sequential decision optimization <ref:2509.23439#pg18>.

Tom: It’s about finding a unified way to characterize both kappa and omega optimal preconditioners, which gives us flexibility in picking the right tool for the job <ref:2509.23439#pg6>.

Jane: And that unified characterization helps everyone understand what makes a scaling strategy truly optimal for our specific problems <ref:2509.23439#pg6>.

Lu: They also provided a simple subgradient method with convergence guarantees, which means we can actually find these omega optimal solutions without having to run those heavy semidefinite programming methods <ref:2509.23439#pg11>.

Meng: That makes the whole process much more accessible for our teams because we don't have to rely on computationally expensive setups just to get a decent preconditioner <ref:2509.23439#pg11>.

Lalam: This kind of practical optimization, focusing on real-world performance metrics like iteration counts, really helps improve the culture around building robust and efficient AI applications <ref:2509.23439#pg6>.

Tom: So to summarize this paper, "Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling" is showing us that omega-based preconditioning provides a computationally efficient and practically superior alternative to kappa-based approaches for large scale problems <ref:2509.23439#pg6>.

Jane: They are showing us that even though the worst-case kappa condition number reduction might look aggressive on paper, the omega approach is substantially cheaper to compute and more strongly correlated with how well those iterative methods like PCG and LSQR actually perform <ref:2509.23439#pg26>.

Lu: It highlights that moving beyond just worst-case conditioning when designing preconditioners is important for practical application in large scale problems <ref:2509.23439#pg6>.

Meng: For us, it means we should probably prioritize these omega-based scaling strategies over the kappa ones unless we have a very specific reason to worry about the absolute worst-case number <ref:2509.23439#pg6>.

Tom: Well, that’s what this paper is all about. We’ve discussed the theory behind omega scaling, how it beats the worst-case kappa approach in terms of speed and cost, and we've seen how it applies to practical problems like block diagonal preconditioners <ref:2509.23439#pg19>.

Jane: This paper really gives us a solid framework for designing better preconditioning strategies, especially when dealing with large sparse matrices or overdetermined systems <ref:2509.23439#pg6>.

Lu: And we’re looking forward to seeing how this omega theory can be extended into more complex settings in the future <ref:2509.23439#pg6>.

Meng: I'm curious to see how quickly we can integrate these scaling strategies into our existing solvers for real-time applications <ref:2509.23439#pg11>.

University of Waterloo · University of Alicante

math.OC, cs.LG, cs.NA, math.NA

Submitted: 2025-09-27

Updated: 2026-10-12

Code: https://github.com/asujanani6/Optimal

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: The gist The authors study optimal diagonal preconditioning under two distinct notions of conditioning—the classical worst-case κ-condition number and the averaging-based ω-condition number—and

Key concepts

$\kappa$-Optimal Preconditioning

This approach focuses on minimizing the largest/smallest eigenpairs of a matrix, aiming to reduce the absolute worst-case condition number. The paper reformulates this problem using an affine-based pseudoconvex structure, allowing for efficient subgradient methods to find solutions.

$\omega$-Optimal Preconditioning

This metric uses an averaging-based condition number that is more relevant to the actual performance of iterative methods. Optimal $\omega$-preconditioners are often found using explicit formulae, such as Jacobi scaling or matrix balancing schemes, and are much cheaper to implement.

Subgradient Method (Algorithm 2.2)

This is a simple optimization technique used to find the optimal diagonal scaling vector for the $\kappa$-optimal problem. Because the problem has a specific structure (pseudoconvex), this method is guaranteed to converge, providing an efficient way to solve for the optimal scaling.

PCG and LSQR Performance Correlation

The research shows that iterative methods like Preconditioned Conjugate Gradient (PCG) and Least Squares Method (LSQR) are more strongly correlated with the $\omega$-condition number than the worst-case $\kappa$-condition number. Therefore, using $\omega$-optimal scaling often leads to substantial improvements in iteration counts.

Terminology

• Preconditioner — 4× in this paper · explained in 2 episodes
• Convergence Guarantees — 1× in this paper · explained in 3 episodes
• Semidefinite Programming (SDP) — 1× in this paper · explained in 4 episodes

Summary

Improvements for AI systems

Sources

• Connecting Kaporin's condition number and the Bregman log determinant divergence
• Gradient Methods with Online Scaling
• Scalable Approximate Optimal Diagonal Preconditioning
• Gradient Multi-Normalization for Stateless and Scalable LLM Training

Related papers

• Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
• Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
• Incremental Learning in Mirror Flows
• Second-Order Optimization with Asynchronous Curvature
• Online Control via Counterfactual Tracking
• Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability