論文の概要: Convergence of Recursive Stochastic Algorithms using Wasserstein
Divergence
- arxiv url: http://arxiv.org/abs/2003.11403v2
- Date: Tue, 5 Jan 2021 15:47:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 03:25:27.372462
- Title: Convergence of Recursive Stochastic Algorithms using Wasserstein
Divergence
- Title(参考訳): Wasserstein分散を用いた再帰確率アルゴリズムの収束
- Authors: Abhishek Gupta and William B. Haskell
- Abstract要約: 本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。
本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。
- 参考スコア(独自算出の注目度): 4.688616907736838
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper develops a unified framework, based on iterated random operator
theory, to analyze the convergence of constant stepsize recursive stochastic
algorithms (RSAs). RSAs use randomization to efficiently compute expectations,
and so their iterates form a stochastic process. The key idea of our analysis
is to lift the RSA into an appropriate higher-dimensional space and then
express it as an equivalent Markov chain. Instead of determining the
convergence of this Markov chain (which may not converge under constant
stepsize), we study the convergence of the distribution of this Markov chain.
To study this, we define a new notion of Wasserstein divergence. We show that
if the distribution of the iterates in the Markov chain satisfy a contraction
property with respect to the Wasserstein divergence, then the Markov chain
admits an invariant distribution. We show that convergence of a large family of
constant stepsize RSAs can be understood using this framework, and we provide
several detailed examples.
- Abstract(参考訳): 本稿では,反復的確率演算子理論に基づく統一的フレームワークを開発し,定数ステップサイズ再帰確率アルゴリズム(RSA)の収束度を解析する。
RSAはランダム化を用いて予測を効率的に計算し、その反復は確率過程を形成する。
我々の分析の鍵となる考え方は、RSAを適切な高次元空間に上げ、それと等価なマルコフ連鎖として表現することである。
このマルコフ連鎖の収束を決定するのではなく、このマルコフ連鎖の分布の収束を考察する。
これを研究するために、ワッサーシュタイン発散の新しい概念を定義する。
マルコフ連鎖におけるイテレートの分布がワッサーシュタインの発散に関して収縮性を満たすならば、マルコフ鎖は不変分布を認める。
定常段差RSAの集団の収束をこの枠組みを用いて理解できることを示し、いくつかの詳細な例を示す。
関連論文リスト
- Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - Accelerating Distributed Stochastic Optimization via Self-Repellent
Random Walks [11.3631620309434]
エージェントのネットワークをランダムウォーク方式で横断するトークンによって勾配をサンプリングする分散最適化アルゴリズムの一群について検討する。
我々は、正則線型マルコフトークンを非線形マルコフ連鎖、すなわち自己推進ラドムウォーク(SRRW)に従うものに置き換えることで、新しいアプローチをとる。
結果のSA-SRRWの最適化誤差はほぼ確実にゼロに収束し、中心極限定理を証明する。
論文 参考訳(メタデータ) (2024-01-18T00:50:37Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling,
Optimization and Boosting [72.01080271666859]
この研究は、幾らかの微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
ほぼ任意の等方性ノイズと状態依存ノイズが伴うが、ほとんどの関連論文ではそうである。
我々の鎖のドリフトと拡散係数は、グラディエント・ランゲヴィン・ダイナミクス、サンプリング、グラディエント・ダイスティング、グラディエント・ブースティングのような広範囲の応用をカバーするために不完全である。
論文 参考訳(メタデータ) (2023-10-09T18:38:56Z) - Covariate shift in nonparametric regression with Markovian design [0.0]
ナダラヤ・ワトソン核推定器の滑らかさリスクに対する収束速度は、ソースとターゲットマルコフ連鎖に関連する不変分布の類似性によって決定されることを示す。
我々は、Kpotufe と Martinet からの分布指数の概念を、一様エルゴードなマルコフ鎖の核移動指数に拡張する。
論文 参考訳(メタデータ) (2023-07-17T14:24:27Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳(メタデータ) (2023-06-27T08:15:28Z) - Self-Repellent Random Walks on General Graphs -- Achieving Minimal
Sampling Variance via Nonlinear Markov Chains [11.3631620309434]
ランダムウォーカーは、サンプリングと近傍探索により、ネットワークトポロジ上のターゲット量を近似するように設計されている。
目的とする確率分布に対応するマルコフ連鎖が与えられた場合、過去に頻繁に訪れたノードに遷移する可能性が低く、滅多に訪れないノードに遷移する可能性が低い自己反発ランダムウォーク(SRRW)を設計する。
正の実アルファでパラメータ化されたSRRWのクラスに対して、プロセスの経験的分布がターゲットにほぼ確実に収束することを証明する。
論文 参考訳(メタデータ) (2023-05-08T23:59:09Z) - Rosenthal-type inequalities for linear statistics of Markov chains [20.606986885851573]
幾何学的エルゴード的マルコフ鎖の加法関数に対する新しい偏差境界を確立する。
我々は、対応する鎖の混合時間に対する境界の依存に特に注意を払う。
論文 参考訳(メタデータ) (2023-03-10T10:24:46Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳(メタデータ) (2021-10-07T17:51:10Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳(メタデータ) (2020-06-11T19:40:38Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z) - Probabilistic Contraction Analysis of Iterated Random Operators [10.442391859219807]
バナッハ縮約写像定理は、ある決定論的アルゴリズムの収束を確立するために用いられる。
ランダム化アルゴリズムのクラスでは、各反復において、縮約写像は、ある確率変数の独立分布と同一分布のサンプルを使用する演算子と近似される。
これにより、完備距離空間において初期点に作用する反復ランダム作用素が導かれ、マルコフ連鎖が生成される。
論文 参考訳(メタデータ) (2018-04-04T00:10:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。