論文の概要: Probabilistic Contraction Analysis of Iterated Random Operators

• arxiv url: http://arxiv.org/abs/1804.01195v6
• Date: Fri, 22 Sep 2023 01:02:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-25 19:54:12.759109
• Title: Probabilistic Contraction Analysis of Iterated Random Operators
• Title（参考訳）: 繰り返しランダム演算子の確率的収縮解析
• Authors: Abhishek Gupta and Rahul Jain and Peter Glynn
• Abstract要約: バナッハ縮約写像定理は、ある決定論的アルゴリズムの収束を確立するために用いられる。 ランダム化アルゴリズムのクラスでは、各反復において、縮約写像は、ある確率変数の独立分布と同一分布のサンプルを使用する演算子と近似される。 これにより、完備距離空間において初期点に作用する反復ランダム作用素が導かれ、マルコフ連鎖が生成される。
• 参考スコア（独自算出の注目度）: 10.442391859219807
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many branches of engineering, Banach contraction mapping theorem is employed to establish the convergence of certain deterministic algorithms. Randomized versions of these algorithms have been developed that have proved useful in data-driven problems. In a class of randomized algorithms, in each iteration, the contraction map is approximated with an operator that uses independent and identically distributed samples of certain random variables. This leads to iterated random operators acting on an initial point in a complete metric space, and it generates a Markov chain. In this paper, we develop a new stochastic dominance based proof technique, called probabilistic contraction analysis, for establishing the convergence in probability of Markov chains generated by such iterated random operators in certain limiting regime. The methods developed in this paper provides a general framework for understanding convergence of a wide variety of Monte Carlo methods in which contractive property is present. We apply the convergence result to conclude the convergence of fitted value iteration and fitted relative value iteration in continuous state and continuous action Markov decision problems as representative applications of the general framework developed here.
• Abstract（参考訳）: 工学の多くの分野において、バナッハの縮約写像定理は、ある決定論的アルゴリズムの収束を確立するために用いられる。 これらのアルゴリズムのランダム化バージョンは、データ駆動問題に有用であることが証明された。 ランダム化アルゴリズムのクラスでは、各反復において、縮約写像は、ある確率変数の独立分布と同一分布のサンプルを使用する演算子と近似される。 これにより、完備距離空間において初期点に作用する反復ランダム作用素が導かれ、マルコフ連鎖が生成される。 本稿では,そのような反復乱数演算子が生成するマルコフ連鎖の確率収束性を確立するために,確率的縮小解析と呼ばれる確率的支配に基づく新しい証明手法を開発した。 本研究で開発された手法は, 契約性のあるモンテカルロ法を多種多様な方法で収束させるための一般的な枠組みを提供する。 この収束結果を用いて、連続状態における適合値反復と適合相対値反復の収束と連続行動マルコフ決定問題を一般的なフレームワークの代表的応用として結論付ける。

関連論文リスト

• Tree-structured Markov random fields with Poisson marginal distributions [0.0]
  離散カウントランダム変数のベクトルに対する木構造ランダムフィールドの新しいファミリーを導入する。 極端ポアソンランダム場は、すべて同じ平均を持ち、それらの組込み依存の強さや構造から解放される。
  論文  参考訳（メタデータ） (2024-08-24T18:30:15Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
  論文  参考訳（メタデータ） (2023-03-10T16:43:48Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。 提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
  論文  参考訳（メタデータ） (2021-10-07T17:51:10Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。 決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。 我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
  論文  参考訳（メタデータ） (2021-09-20T21:48:19Z)
• A greedy reconstruction algorithm for the identification of spin distribution [0.0]
  確率分布の分数的定数近似の識別性は行列の可逆性に関係していることを示す。 このアルゴリズムは、この行列が特異行列からできるだけ遠くにあることを保証する、特定の制御を設計することを目的としている。
  論文  参考訳（メタデータ） (2021-08-26T12:40:52Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。 この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
  論文  参考訳（メタデータ） (2021-01-16T17:11:02Z)
• 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)
• Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence [4.688616907736838]
  本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。 本研究では, 定常段差RSAの集団の収束が, この枠組みを用いて理解可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-25T13:45:16Z)

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

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