論文の概要: Randomized batch-sampling Kaczmarz methods for general linear systems

• arxiv url: http://arxiv.org/abs/2511.09872v1
• Date: Fri, 14 Nov 2025 01:14:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.541102
• Title: Randomized batch-sampling Kaczmarz methods for general linear systems
• Title（参考訳）: 一般線形系に対するランダム化されたバッチサンプリングKaczmarz法
• Authors: Dong-Yue Xie, Xi Yang,
• Abstract要約: ランダム化されたバッチサンプリングを行うKaczmarzフレームワークを,循環ブロック法と同じくらい低コストで採用する。 我々は収束保証を確立するための一般的な解析手法を開発した。
• 参考スコア（独自算出の注目度）: 4.909043927828085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To conduct a more in-depth investigation of randomized solvers for general linear systems, we adopt a unified randomized batch-sampling Kaczmarz framework with per-iteration costs as low as cyclic block methods, and develop a general analysis technique to establish its convergence guarantee. With concentration inequalities, we derive new expected linear convergence rate bounds. The analysis applies to any randomized non-extended block Kaczmarz methods with static stochastic samplings. In addition, the new rate bounds are scale-invariant which eliminate the dependence on the magnitude of the data matrix. In most experiments, the new bounds are significantly tighter than existing ones and better reflect the empirical convergence behavior of block methods. Within this new framework, the batch-sampling distribution, as a learnable parameter, provides the possibility for block methods to achieve efficient performance in specific application scenarios, which deserves further investigation.
• Abstract（参考訳）: 一般線形系に対するランダム化解法について,より詳細な調査を行うために,循環ブロック法と同程度のコストでランダム化バッチサンプリングを統一したKaczmarzフレームワークを採用し,収束保証を確立するための一般解析手法を開発した。 濃度不等式により、新しい期待される線形収束速度境界を導出する。 この分析は任意のランダム化された非拡張ブロック Kaczmarz 法と静的確率的サンプリングに適用できる。 さらに、新しいレート境界はスケール不変であり、データマトリックスの大きさへの依存を排除している。 ほとんどの実験では、新しい境界は既存の境界よりもかなり強く、ブロック法の経験的収束挙動を反映している。 この新しいフレームワークでは、学習可能なパラメータとしてバッチサンプリングディストリビューションが、ブロックメソッドが特定のアプリケーションシナリオで効率的なパフォーマンスを達成する可能性を提供しており、さらなる調査に値する。

関連論文リスト

• Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees [70.88473359544084]
  離散拡散モデルに対する新たな解析的アプローチを導入し,正規性仮定の必要性を排除した。 標準的な$tau$-leaping法では、語彙サイズとともに線形にスケールするKL発散の収束保証を確立する。 我々のアプローチはより広く適用可能であり、他の広く使われているサンプルに対して最初の収束保証を提供する。
  論文  参考訳（メタデータ） (2025-09-20T17:42:29Z)
• Discretization-free Multicalibration through Loss Minimization over Tree Ensembles [22.276913140687725]
  深度2の決定木をアンサンブルする離散化のない多重校正法を提案する。 本アルゴリズムは,データ分布が損失飽和と呼ばれる技術的条件を満たすことを前提として,マルチキャリブレーションを確実に達成する。
  論文  参考訳（メタデータ） (2025-05-23T03:29:58Z)
• Randomized Kaczmarz Methods with Beyond-Krylov Convergence [8.688801614519988]
  高速化されたランダム化ブロックであるKaczmarz++を導入し,入力中の特異値から高速なKrylov型収束を実現する。 Kaczmarz++は、過度に決定されたシステムと過度に決定されたシステムの両方において、一般的なKrylovメソッドよりも確実に高速なアウトリーニング特異値をキャプチャする。
  論文  参考訳（メタデータ） (2025-01-20T18:55:51Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints [7.936519714074615]
  カッツマルツ行列(英語版)(KZ)とその変種は、部分線型方程式系を解く際の単純さと効率性のために広く研究されている。 KHT に対する最初の理論的収束保証は、空間的制約のある系の解に線形に収束することを示すことである。
  論文  参考訳（メタデータ） (2023-04-20T07:14:24Z)
• Distributed Dynamic Safe Screening Algorithms for Sparse Regularization [73.85961005970222]
  本稿では,分散動的安全スクリーニング(DDSS)手法を提案し,共有メモリアーキテクチャと分散メモリアーキテクチャにそれぞれ適用する。 提案手法は, 線形収束率を低次複雑度で達成し, 有限個の繰り返しにおいてほとんどすべての不活性な特徴をほぼ確実に除去できることを示す。
  論文  参考訳（メタデータ） (2022-04-23T02:45:55Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  ガウス過程後部をシミュレーションするための従来のアプローチでは、有限個の入力位置のプロセス値の限界分布からサンプルを抽出する。 この分布中心の特徴づけは、所望のランダムベクトルのサイズで3次スケールする生成戦略をもたらす。 条件付けのこのパスワイズ解釈が、ガウス過程の後部を効率的にサンプリングするのに役立てる近似の一般族をいかに生み出すかを示す。
  論文  参考訳（メタデータ） (2020-11-08T17:09:37Z)
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning [27.775096437736973]
  独立サンプリング方式は、一般に使用されている一様サンプリング方式の性能を向上させる傾向にあることを示す。 我々の新しい分析は、サンプリングの速度が今までで最高のものより速いことも示しています。
  論文  参考訳（メタデータ） (2020-09-14T16:41:32Z)

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

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