論文の概要: Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing

• arxiv url: http://arxiv.org/abs/2502.00882v1
• Date: Sun, 02 Feb 2025 19:23:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:01:34.385557
• Title: Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing
• Title（参考訳）: 価値:前処理なしでランダムで正規化されたブロックKaczmarzアルゴリズム
• Authors: Gil Goldshlager, Jiang Hu, Lin Lin,
• Abstract要約: ランダム化ブロックKaczmarz法(RBK)のデータの一様サンプリング時の収束を解析し,その繰り返しがモンテカルロの感覚で$textit$ least-squaresの解に収束することを示す。 RBKに正規化を組み込むことで、これらの問題を解決する。 自然勾配最適化から生じる例を含む数値実験により、正規化アルゴリズムReBlocKは、高速特異値減衰を示す現実的な問題に対して、最小バッチ勾配勾配よりも優れていることが示唆された。
• 参考スコア（独自算出の注目度）: 2.542838926315103
• License:
• Abstract: Due to the ever growing amounts of data leveraged for machine learning and scientific computing, it is increasingly important to develop algorithms that sample only a small portion of the data at a time. In the case of linear least-squares, the randomized block Kaczmarz method (RBK) is an appealing example of such an algorithm, but its convergence is only understood under sampling distributions that require potentially prohibitively expensive preprocessing steps. To address this limitation, we analyze RBK when the data is sampled uniformly, showing that its iterates converge in a Monte Carlo sense to a $\textit{weighted}$ least-squares solution. Unfortunately, for general problems the condition number of the weight matrix and the variance of the iterates can become arbitrarily large. We resolve these issues by incorporating regularization into the RBK iterations. Numerical experiments, including examples arising from natural gradient optimization, suggest that the regularized algorithm, ReBlocK, outperforms minibatch stochastic gradient descent for realistic problems that exhibit fast singular value decay.
• Abstract（参考訳）: 機械学習や科学計算に利用されるデータの量が増え続けているため、データのごく一部を一度にサンプリングするアルゴリズムを開発することがますます重要になっている。 線形最小二乗法の場合、ランダム化されたブロックKaczmarz法(RBK)はそのようなアルゴリズムの魅力的な例であるが、その収束は、潜在的に高価な前処理ステップを必要とするサンプリング分布の下でのみ理解されている。 この制限に対処するために、データが一様にサンプリングされたときにRBKを分析し、その反復がモンテカルロの感覚で$\textit{weighted}$ least-squaresの解に収束することを示す。 残念なことに、一般的な問題では、重み行列の条件数と反復行列のばらつきは任意に大きくなる。 RBKイテレーションに正規化を組み込むことで、これらの問題を解決する。 自然勾配最適化から生じる例を含む数値実験により、正規化アルゴリズムReBlocKは、高速特異値減衰を示す現実的な問題に対して、最小バッチ確率勾配よりも優れていることが示唆された。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Learning Large Scale Sparse Models [6.428186644949941]
  サンプルの数や特徴次元が数百万から数十億にも達する大規模環境でスパースモデルを学習することを検討する。 ラッソのようなスパースモデルをオンライン的に学習し、ランダムに選択されたサンプルが1つだけ露呈してスパース勾配を更新することを提案する。 これにより、メモリコストはサンプルサイズに依存しず、1つのサンプルの勾配評価が効率的となる。
  論文  参考訳（メタデータ） (2023-01-26T06:29:49Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
  離散分布の様々なクラスを対象としたミニマックスフレームワークにおいて,リジェクションサンプリングのクエリ複雑性について検討した。 本研究は,アルファベットサイズに比例して複雑度が増大するサンプリングのための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-29T01:00:42Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Smooth Deformation Field-based Mismatch Removal in Real-time [10.181846237133167]
  非剛性変形は、パラメトリック変換が見つからないため、ミスマッチの除去を困難にする。 再重み付けと1点RANSAC戦略(R1P-RNSC)に基づくアルゴリズムを提案する。 両アルゴリズムの組み合わせは,他の最先端手法と比較して精度が高いことを示す。
  論文  参考訳（メタデータ） (2020-07-16T18:20:25Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Stochastic Proximal Gradient Algorithm with Minibatches. Application to Large Scale Learning Models [2.384873896423002]
  非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。 我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
  論文  参考訳（メタデータ） (2020-03-30T10:43:56Z)

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

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