論文の概要: 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の集団の収束をこの枠組みを用いて理解できることを示し、いくつかの詳細な例を示す。

関連論文リスト

• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  連続時間マルコフ連鎖(CTMC)に基づくスコアベース離散拡散モデルの理論的側面について検討する。 本稿では,事前定義された時間点におけるスコア推定値を利用する離散時間サンプリングアルゴリズムを一般状態空間$[S]d$に導入する。 我々の収束解析はジルサノフ法を用いて離散スコア関数の重要な性質を確立する。
  論文  参考訳（メタデータ） (2024-10-03T09:07:13Z)
• Deep Learning for Computing Convergence Rates of Markov Chains [0.0]
  Deep Contractive Drift Calculator (DCDC)は、マルコフ連鎖の収束をワッサーシュタイン距離における定常性にバウンドするための、最初の汎用的なサンプルベースアルゴリズムである。 DCDCは,処理ネットワークから生じる現実的なマルコフ連鎖の収束境界と,ステップサイズを一定に最適化できることを示す。
  論文  参考訳（メタデータ） (2024-05-30T19:26:51Z)
• 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 [64.0722630873758]
  我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。 伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
  論文  参考訳（メタデータ） (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)
• 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)

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

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