論文の概要: New Insights and Algorithms for Optimal Diagonal Preconditioning

• arxiv url: http://arxiv.org/abs/2509.23439v1
• Date: Sat, 27 Sep 2025 18:16:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.22869
• Title: New Insights and Algorithms for Optimal Diagonal Preconditioning
• Title（参考訳）: 最適対角プレコンディショニングのための新しい洞察とアルゴリズム
• Authors: Saeed Ghadimi, Woosuk L. Jung, Arnesh Sujanani, David Torregrosa-Belén, Henry Wolkowicz,
• Abstract要約: 我々は,対角的プレコンディショニング問題を解決するために,保証付き競争力のある下位段階法を開発した。 提案手法は,既存のSDP手法よりも線形システムの解法が優れていることを示す。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: プリコンディショニング(スケーリング)は数学の多くの分野、特に最適化において不可欠である。 本研究では,最適対角形プレコンディショナーの探索問題について検討する。 我々は、古典的、最悪のケースタイプ、$\kappa$- Condition number、そしてより平均化された$\omega$- Condition numberという2つの異なる条件番号の概念を最小化することに重点を置いている。 両最適化問題のアフィンに基づく擬凸再構成を行う。 我々の定式化の利点は、目的の勾配が計算に安価であり、最適化変数は単に$n\times 1$ vectorであることである。 また、両問題の最適条件のエレガントな特徴付けも提供する。 我々は、既存のSDPベースのアプローチよりもずっと良くスケールし、効率的である$\kappa$-optimal diagonal preconditioningに対して、収束を保証するような競合的な下位段階法を開発する。 また, 線形システムの解法におけるPCG性能が, 他の手法よりも優れていることを示す。 最後に、$\omega$-optimal preconditionerを正確な$\kappa$-optimally ditimally preconditioned matrix $A$に適用し、PCG法に対する一貫性と大幅に改善された収束結果を得るという興味深い現象を示す。

関連論文リスト

• A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
  パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。 滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-16T05:26:03Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Optimal Diagonal Preconditioning: Theory and Practice [23.79536881427839]
  本稿では,列数や列数の最大化を同時に達成するために,最適対角前処理の問題を提案する。 実装が容易なベースライン分岐アルゴリズムを提案する。 次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを実証する。
  論文  参考訳（メタデータ） (2022-09-02T04:21:28Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。