論文の概要: Deep Learning for Computing Convergence Rates of Markov Chains

• arxiv url: http://arxiv.org/abs/2405.20435v1
• Date: Thu, 30 May 2024 19:26:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-03 18:24:43.293228
• Title: Deep Learning for Computing Convergence Rates of Markov Chains
• Title（参考訳）: マルコフ連鎖の収束率の深層学習
• Authors: Yanlin Qu, Jose Blanchet, Peter Glynn,
• Abstract要約: Deep Contractive Drift Calculator (DCDC)は、マルコフ連鎖の収束をワッサーシュタイン距離における定常性にバウンドするための、最初の汎用的なサンプルベースアルゴリズムである。 DCDCは,処理ネットワークから生じる現実的なマルコフ連鎖の収束境界と,ステップサイズを一定に最適化できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Convergence rate analysis for general state-space Markov chains is fundamentally important in areas such as Markov chain Monte Carlo and algorithmic analysis (for computing explicit convergence bounds). This problem, however, is notoriously difficult because traditional analytical methods often do not generate practically useful convergence bounds for realistic Markov chains. We propose the Deep Contractive Drift Calculator (DCDC), the first general-purpose sample-based algorithm for bounding the convergence of Markov chains to stationarity in Wasserstein distance. The DCDC has two components. First, inspired by the new convergence analysis framework in (Qu et.al, 2023), we introduce the Contractive Drift Equation (CDE), the solution of which leads to an explicit convergence bound. Second, we develop an efficient neural-network-based CDE solver. Equipped with these two components, DCDC solves the CDE and converts the solution into a convergence bound. We analyze the sample complexity of the algorithm and further demonstrate the effectiveness of the DCDC by generating convergence bounds for realistic Markov chains arising from stochastic processing networks as well as constant step-size stochastic optimization.
• Abstract（参考訳）: 一般状態空間のマルコフ連鎖に対する収束速度解析は、マルコフ連鎖モンテカルロやアルゴリズム解析(明示的な収束境界の計算)のような領域において本質的に重要である。 しかし、従来の解析手法では、現実的なマルコフ連鎖に対して実用的に有用な収束境界を生成できないことが知られている。 We propose the Deep Contractive Drift Calculator (DCDC) was proposed the first general-purpose sample-based algorithm for boundnce of Markov chains to stationarity in Wasserstein distance。 DCDCには2つのコンポーネントがある。 まず、(Qu et.al, 2023) の新たな収束解析フレームワークに着想を得て、契約ドリフト方程式(CDE: Contractive Drift Equation)を導入する。 第2に、ニューラルネットワークに基づく効率的なCDEソルバを開発する。 これら2つの成分を組み込んだ DCDC は CDE を解き、解を収束境界に変換する。 確率的処理ネットワークから生じる現実的マルコフ連鎖の収束境界と,一定のステップサイズの確率的最適化を生成することで,アルゴリズムのサンプル複雑性を分析し,さらにDCDCの有効性を実証する。

関連論文リスト

• On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes [11.868402302316131]
  本稿では,マルコフ決定過程(MDP)の強化学習(RL)アルゴリズムを,平均回帰基準の下で解析する。 本稿では,MDPを弱通信する反復RVI法のモデル自由集合であるRVI(Rexent Value)に基づくQ-learningアルゴリズムに着目した。
  論文  参考訳（メタデータ） (2024-08-29T04:57:44Z)
• Decentralized Sum-of-Nonconvex Optimization [42.04181488477227]
  我々は、平均的な非合意数である保証関数(sum-of-non function)の最適化問題を考察する。 本稿では,勾配,速度追跡,マルチコンセンサスといった手法を用いて,高速化された分散化1次アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:48:45Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Stability and Generalization for Randomized Coordinate Descent [19.687456295228156]
  RCDによってトレーニングされたモデルがどのように例をテストするかを研究する作業はない。 本稿では,アルゴリズム安定性の強力なツールを活用することにより,RCDの一般化解析を初期化する。 解析の結果,RCDは勾配降下よりも安定性がよいことがわかった。
  論文  参考訳（メタデータ） (2021-08-17T02:52:50Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence [4.688616907736838]
  本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。 本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-25T13:45:16Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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