New Insights and Algorithms for Optimal Diagonal Preconditioning

• URL: http://arxiv.org/abs/2509.23439v1
• Date: Sat, 27 Sep 2025 18:16:21 GMT
• Title: New Insights and Algorithms for Optimal Diagonal Preconditioning
• Authors: Saeed Ghadimi, Woosuk L. Jung, Arnesh Sujanani, David Torregrosa-Belén, Henry Wolkowicz,
• Abstract summary: We develop a competitive subgradient method, with guarantees, for solving diagonal preconditioning problems.<n>We show that our method leads to better results for solving linear systems than existing SDP-based approaches.
• Score: 1.8105377206423159
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Preconditioning (scaling) is essential in many areas of mathematics, and in particular in optimization. In this work, we study the problem of finding an optimal diagonal preconditioner. We focus on minimizing two different notions of condition number: the classical, worst-case type, $\kappa$-condition number, and the more averaging motivated $\omega$-condition number. We provide affine based pseudoconvex reformulations of both optimization problems. The advantage of our formulations is that the gradient of the objective is inexpensive to compute and the optimization variable is just an $n\times 1$ vector. We also provide elegant characterizations of the optimality conditions of both problems. We develop a competitive subgradient method, with convergence guarantees, for $\kappa$-optimal diagonal preconditioning that scales much better and is more efficient than existing SDP-based approaches. We also show that the preconditioners found by our subgradient method leads to better PCG performance for solving linear systems than other approaches. Finally, we show the interesting phenomenon that we can apply the $\omega$-optimal preconditioner to the exact $\kappa$-optimally diagonally preconditioned matrix $A$ and get consistent, significantly improved convergence results for PCG methods.

Related papers

• Structured Preconditioners in Adaptive Optimization: A Unified Analysis [30.17859434112402]
  We present a novel unified analysis for a broad class of adaptive optimization algorithms with structured preconditioners.<n>Our analysis provides matching rate to several important structured preconditioned algorithms including diagonal AdaGrad, full-matrix AdaGrad, and AdaGrad-Norm.<n>We show that one-sided Shampoo, which is relatively much cheaper than full-matrix AdaGrad could outperform it both theoretically and experimentally.
  arXiv  Detail & Related papers  (2025-03-13T16:51:59Z)
• A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
  We show that line search is superfluous in attaining the optimal rate of convergence for solving a convex optimization problem whose parameters are not given a priori. We present a novel accelerated gradient descent type algorithm called AC-FGM that can achieve an optimal $mathcalO (1/k2)$ rate of convergence for smooth convex optimization.
  arXiv  Detail & Related papers  (2023-10-16T05:26:03Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  We study the complexity of producing neither smooth nor convex points of Lipschitz objectives which are possibly using only zero-order evaluations. Our analysis is based on a simple yet powerful. Goldstein-subdifferential set, which allows recent advancements in. nonsmooth non optimization.
  arXiv  Detail & Related papers  (2023-07-10T11:56:04Z)
• Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
  This paper presents the problem of optimal diagonal preconditioning to achieve maximal reduction in any full-rank number of rows or columns or simultaneously. We provide a baseline bisection algorithm that is easy to implement in practice. Next, we specialize to one-sided optimal diagonal preconditioning problems, and demonstrate that they can be formulated as standard dual SDP problems.
  arXiv  Detail & Related papers  (2022-09-02T04:21:28Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.