Fugu-MT 論文翻訳(概要): Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm

論文の概要: Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm

arxiv url: http://arxiv.org/abs/2412.07643v1
Date: Tue, 10 Dec 2024 16:21:26 GMT
ステータス: 翻訳完了
システム内更新日: 2024-12-11 14:36:06.442724
Title: Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm
Title（参考訳）: ヒット・アンド・ラン・モンテカルロの弾道収束とランダム化Kaczmarzアルゴリズム
Authors: Nawaf Bou-Rabee, Andreas Eberle, Stefan Oberdörster,
Abstract要約: ガウス目標測度におけるHit-and-Runのワッサーシュタイン収縮の推定を結合法を用いて検証する。我々はこれらの知見をランダム化Kaczmarzアルゴリズムの座標自由変種に拡張する。
参考スコア（独自算出の注目度）: 0.20482269513546453
License:
Abstract: Hit-and-Run is a coordinate-free Gibbs sampler, yet the quantitative advantages of its coordinate-free property remain largely unexplored beyond empirical studies. In this paper, we prove sharp estimates for the Wasserstein contraction of Hit-and-Run in Gaussian target measures via coupling methods and conclude mixing time bounds. Our results uncover ballistic and superdiffusive convergence rates in certain settings. Furthermore, we extend these insights to a coordinate-free variant of the randomized Kaczmarz algorithm, an iterative method for linear systems, and demonstrate analogous convergence rates. These findings offer new insights into the advantages and limitations of coordinate-free methods for both sampling and optimization.
Abstract（参考訳）: ヒット・アンド・ラン(Hit-and-Run)は、座標のないギブスのサンプル装置であるが、その座標のない性質の量的利点は、実証的な研究以外には明らかにされていない。本稿では,ガウス目標測度におけるHit-and-RunのWasserstein縮合について,結合法と混合時間境界による鋭い推定値を示す。その結果,特定の条件下での弾道的および超拡散的収束率を明らかにした。さらに,これらの知見を,線形システムの反復的手法であるランダム化 Kaczmarz アルゴリズムの座標自由変種に拡張し,類似収束率を示す。これらの知見は、サンプリングと最適化の両方において、座標自由手法の利点と限界に関する新たな洞察を与える。

関連論文リスト

Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner [6.408773096179187]
本稿では,GPモデルの前と後をランダムに実現するためのスケーラブルなアルゴリズムを提案する。提案アルゴリズムはスパースグリッドを用いた点近似と加法的シュワルツプレコンディショナーを利用する。
論文参考訳（メタデータ） (2024-08-01T00:19:36Z)
Weighted Riesz Particles [0.0]
対象分布を、パラメータの無限次元空間が多くの決定論的部分多様体からなる写像と考える。我々は、Rieszと呼ばれる点の性質を研究し、それをシーケンシャルMCMCに埋め込む。低い評価で高い受け入れ率が得られることが分かりました。
論文参考訳（メタデータ） (2023-12-01T14:36:46Z)
Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文参考訳（メタデータ） (2023-09-29T15:24:48Z)
Learning Gaussian Mixtures Using the Wasserstein-Fisher-Rao Gradient Flow [12.455057637445174]
ガウス混合モデルを用いて非パラメトリック最大推定器(NPMLE)を計算するための新しいアルゴリズムを提案する。この手法は、ワッサーシュタイン-フィッシャー-ラオ幾何学を備えた確率測度空間上の勾配降下に基づく。提案アルゴリズムの有効性を確認するため,広範囲な数値実験を行った。
論文参考訳（メタデータ） (2023-01-04T18:59:35Z)
Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文参考訳（メタデータ） (2022-02-26T19:10:48Z)
Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文参考訳（メタデータ） (2021-10-20T02:25:25Z)
A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文参考訳（メタデータ） (2021-10-07T17:51:10Z)
Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文参考訳（メタデータ） (2021-07-21T17:10:14Z)
On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文参考訳（メタデータ） (2021-06-30T17:51:36Z)
The Convergence Indicator: Improved and completely characterized parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文参考訳（メタデータ） (2020-06-06T19:08:05Z)
Ensemble Slice Sampling: Parallel, black-box and gradient-free inference for correlated & multimodal distributions [0.0]
スライスサンプリング (Slice Sampling) は、最小ハンドチューニングで目標分布の特性に適応するマルコフ連鎖モンテカルロアルゴリズムとして登場した。本稿では,初期長さ尺度を適応的に調整することで,そのような困難を回避できるアルゴリズムであるEnsemble Slice Sampling(ESS)を紹介する。これらのアフィン不変アルゴリズムは簡単に構築でき、手作業で調整する必要がなく、並列計算環境で容易に実装できる。
論文参考訳（メタデータ） (2020-02-14T19:00:12Z)

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