論文の概要: Randomized Kaczmarz Methods with Beyond-Krylov Convergence
- arxiv url: http://arxiv.org/abs/2501.11673v1
- Date: Mon, 20 Jan 2025 18:55:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-22 14:23:39.247437
- Title: Randomized Kaczmarz Methods with Beyond-Krylov Convergence
- Title（参考訳）: Beyond-Krylov Convergence を用いたランダム化 Kaczmarz 法
- Authors: Michał Dereziński, Deanna Needell, Elizaveta Rebrova, Jiaming Yang,
- Abstract要約: 高速化されたランダム化ブロックであるKaczmarz++を導入し,入力中の特異値から高速なKrylov型収束を実現する。
Kaczmarz++は、過度に決定されたシステムと過度に決定されたシステムの両方において、一般的なKrylovメソッドよりも確実に高速なアウトリーニング特異値をキャプチャする。
- 参考スコア（独自算出の注目度）: 8.688801614519988
- License:
- Abstract: Randomized Kaczmarz methods form a family of linear system solvers which converge by repeatedly projecting their iterates onto randomly sampled equations. While effective in some contexts, such as highly over-determined least squares, Kaczmarz methods are traditionally deemed secondary to Krylov subspace methods, since this latter family of solvers can exploit outliers in the input's singular value distribution to attain fast convergence on ill-conditioned systems. In this paper, we introduce Kaczmarz++, an accelerated randomized block Kaczmarz algorithm that exploits outlying singular values in the input to attain a fast Krylov-style convergence. Moreover, we show that Kaczmarz++ captures large outlying singular values provably faster than popular Krylov methods, for both over- and under-determined systems. We also develop an optimized variant for positive semidefinite systems, called CD++, demonstrating empirically that it is competitive in arithmetic operations with both CG and GMRES on a collection of benchmark problems. To attain these results, we introduce several novel algorithmic improvements to the Kaczmarz framework, including adaptive momentum acceleration, Tikhonov-regularized projections, and a memoization scheme for reusing information from previously sampled equation~blocks.
- Abstract（参考訳）: ランダム化されたカッツマルツ法は、その反復をランダムにサンプリングされた方程式に繰り返し投影することによって収束する線形系解の族を形成する。
非常に過度に決定された最小二乗法のようないくつかの文脈では有効であるが、カツマルツ法は伝統的にクリロフ部分空間法に準ずるものとして扱われる。
本稿では,高速化されたランダム化ブロックであるKaczmarz++について紹介する。
さらに,Kaczmarz++は,過度に決定されたシステムと過度に決定されたシステムにおいて,一般的なKrylov法よりも確実に高速なアウトリーニング特異値をキャプチャすることを示した。
また,CD++ と呼ばれる正半定値システムの最適化版を開発し,CG と GMRES の双方とベンチマーク問題に対する演算に競合することを示す。
これらの結果を得るために、適応運動量加速度、Tikhonov-regularized projections、および以前にサンプリングされた方程式~ブロックからの情報を再利用するためのメモ化スキームを含む、Kaczmarzフレームワークにいくつかの新しいアルゴリズム的改善を導入する。
関連論文リスト
- Linear Convergence of Reshuffling Kaczmarz Methods With Sparse
Constraints [7.936519714074615]
カッツマルツ行列(英語版)(KZ)とその変種は、部分線型方程式系を解く際の単純さと効率性のために広く研究されている。
KHT に対する最初の理論的収束保証は、空間的制約のある系の解に線形に収束することを示すことである。
論文 参考訳（メタデータ） (2023-04-20T07:14:24Z) - Bregman Power k-Means for Clustering Exponential Family Data [11.434503492579477]
我々は、ブレグマン発散の下でのハードクラスタリングに関する古典的な研究のアルゴリズム的進歩を橋渡しする。
ブレグマン発散のエレガントな性質は、単純で透明なアルゴリズムで閉形式更新を維持できる。
シミュレーション実験の徹底的な実証分析と降雨データに関するケーススタディを考察し,提案手法はガウス以外の様々なデータ設定において,既存のピア手法よりも優れていることを示した。
論文 参考訳（メタデータ） (2022-06-22T06:09:54Z) - Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
本稿では,分散動的安全スクリーニング(DDSS)手法を提案し,共有メモリアーキテクチャと分散メモリアーキテクチャにそれぞれ適用する。
提案手法は, 線形収束率を低次複雑度で達成し, 有限個の繰り返しにおいてほとんどすべての不活性な特徴をほぼ確実に除去できることを示す。
論文 参考訳（メタデータ） (2022-04-23T02:45:55Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Nesterov Accelerated ADMM for Fast Diffeomorphic Image Registration [63.15453821022452]
ディープラーニングに基づくアプローチの最近の発展は、DiffIRのサブ秒間実行を実現している。
本稿では,中間定常速度場を機能的に構成する簡易な反復スキームを提案する。
次に、任意の順序の正規化項を用いて、これらの速度場に滑らかさを課す凸最適化モデルを提案する。
論文 参考訳（メタデータ） (2021-09-26T19:56:45Z) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with
State-Dependent Event Rates [0.0]
連続目標分布に対するマルコフ連鎖モンテカルロ法に代わる,頑健で,使いやすく,計算的に高速な手法を提案する。
提案アルゴリズムは、関連するベンチマークと比較して大きなスピードアップと安定性の向上をもたらす可能性がある。
高品質なODEコードへのアクセスが保証され、提案手法は実装も使用も容易であり、高度に困難で高次元のターゲット分布に対しても有効である。
論文 参考訳（メタデータ） (2020-05-04T06:23:13Z) - Stochastic gradient algorithms from ODE splitting perspective [0.0]
我々は、ODEの近似解の分割スキームに遡る最適化に関する異なる見解を示す。
そこで本研究では, ODE の勾配一階分割方式と降下アプローチの関連性について述べる。
我々は、機械学習アプリケーションにインスパイアされた分割の特殊なケースを考察し、それに対するグローバルスプリッティングエラーに新たな上限を導出する。
論文 参考訳（メタデータ） (2020-04-19T22:45:32Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Average-case Acceleration Through Spectral Density Estimation [35.01931431231649]
ランダム2次問題の平均ケース解析のためのフレームワークを開発する。
この分析で最適なアルゴリズムを導出する。
我々は, 均一性, マルテンコ・パストゥル, 指数分布の明示的アルゴリズムを開発した。
論文 参考訳（メタデータ） (2020-02-12T01:44:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。