論文の概要: Fast and Near-Optimal Diagonal Preconditioning
- arxiv url: http://arxiv.org/abs/2008.01722v2
- Date: Wed, 3 Nov 2021 07:15:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-02 23:58:32.720201
- Title: Fast and Near-Optimal Diagonal Preconditioning
- Title（参考訳）: 高速・至近対角プレコンディショニング
- Authors: Arun Jambulapati, Jerry Li, Christopher Musco, Aaron Sidford, Kevin
Tian
- Abstract要約: 左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。
構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
- 参考スコア（独自算出の注目度）: 46.240079312553796
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The convergence rates of iterative methods for solving a linear system
$\mathbf{A} x = b$ typically depend on the condition number of the matrix
$\mathbf{A}$. Preconditioning is a common way of speeding up these methods by
reducing that condition number in a computationally inexpensive way. In this
paper, we revisit the decades-old problem of how to best improve $\mathbf{A}$'s
condition number by left or right diagonal rescaling. We make progress on this
problem in several directions.
First, we provide new bounds for the classic heuristic of scaling
$\mathbf{A}$ by its diagonal values (a.k.a. Jacobi preconditioning). We prove
that this approach reduces $\mathbf{A}$'s condition number to within a
quadratic factor of the best possible scaling. Second, we give a solver for
structured mixed packing and covering semidefinite programs (MPC SDPs) which
computes a constant-factor optimal scaling for $\mathbf{A}$ in
$\widetilde{O}(\text{nnz}(\mathbf{A}) \cdot \text{poly}(\kappa^\star))$ time;
this matches the cost of solving the linear system after scaling up to a
$\widetilde{O}(\text{poly}(\kappa^\star))$ factor. Third, we demonstrate that a
sufficiently general width-independent MPC SDP solver would imply near-optimal
runtimes for the scaling problems we consider, and natural variants concerned
with measures of average conditioning.
Finally, we highlight connections of our preconditioning techniques to
semi-random noise models, as well as applications in reducing risk in several
statistical regression models.
- Abstract（参考訳）: 線形系 $\mathbf{a} x = b$ を解くための反復的手法の収束率は、通常行列 $\mathbf{a}$ の条件数に依存する。
プリコンディショニングは、この条件数を計算的に安価な方法で削減することで、これらの方法を高速化する一般的な方法である。
本稿では、左あるいは右の対角線再スケーリングによる$\mathbf{A}$の条件数を改善する方法に関する数十年前の問題を再考する。
我々はこの問題をいくつかの方向に進める。
まず、その対角値によって$\mathbf{a}$をスケーリングするという古典的なヒューリスティックの新しい境界(jacobi preconditioning)を提供する。
このアプローチは、$\mathbf{a}$の条件数を最良のスケーリングの2次係数の範囲に減少させることを証明します。
第二に、構造的混合パッキングと半定義型プログラム(mpc sdps)の解法を与える。これは、$\widetilde{o}(\text{nnz}(\mathbf{a}) \cdot \text{poly}(\kappa^\star))$ factor の定値最適スケーリングを計算し、$\widetilde{o}(\text{poly}(\kappa^\star)$ factor までスケールした後の線形系を解くコストに一致する。
第3に、十分に一般的な幅独立なmpc sdpソルバは、我々が検討するスケーリング問題や平均条件付けの尺度に関連する自然変種に対して、ほぼ最適のランタイムであることを示す。
最後に, 半ランダム雑音モデルへのプレコンディショニング手法の接続や, 各種統計回帰モデルにおけるリスク低減への応用について注目する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳（メタデータ） (2023-10-27T16:54:29Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
論文 参考訳（メタデータ） (2023-06-25T16:32:00Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Coordinate Methods for Matrix Games [41.821881312775496]
我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
論文 参考訳（メタデータ） (2020-09-17T17:55:03Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。