論文の概要: Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance

• arxiv url: http://arxiv.org/abs/2011.01868v3
• Date: Tue, 23 Mar 2021 13:44:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-30 06:29:31.248852
• Title: Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
• Title（参考訳）: 非線形二時間スケール確率近似:収束と有限時間性能
• Authors: Thinh T. Doan
• Abstract要約: 非線形2時間スケール近似の収束と有限時間解析について検討する。 特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
• 参考スコア（独自算出の注目度）: 1.52292571922932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Two-time-scale stochastic approximation, a generalized version of the popular stochastic approximation, has found broad applications in many areas including stochastic control, optimization, and machine learning. Despite its popularity, theoretical guarantees of this method, especially its finite-time performance, are mostly achieved for the linear case while the results for the nonlinear counterpart are very sparse. Motivated by the classic control theory for singularly perturbed systems, we study in this paper the asymptotic convergence and finite-time analysis of the nonlinear two-time-scale stochastic approximation. Under some fairly standard assumptions, we provide a formula that characterizes the rate of convergence of the main iterates to the desired solutions. In particular, we show that the method achieves a convergence in expectation at a rate $\mathcal{O}(1/k^{2/3})$, where $k$ is the number of iterations. The key idea in our analysis is to properly choose the two step sizes to characterize the coupling between the fast and slow-time-scale iterates.
• Abstract（参考訳）: 一般的な確率近似の一般化版である2-time-scale stochastic approximationは、確率制御、最適化、機械学習など、多くの分野で広く応用されている。 その人気にもかかわらず、この手法の理論的保証、特に有限時間性能は、線形の場合において主に達成されるが、非線形の場合の結果は非常に少ない。 特異摂動系の古典的な制御理論に動機づけられ,非線形2時間スケール確率近似の漸近収束と有限時間解析を行った。 いくつかのかなり標準的な仮定の下で、主イテレートの所望の解への収束率を特徴づける公式を提供する。 特に、この手法が期待値の収束を$\mathcal{O}(1/k^{2/3})$で達成することを示し、$k$は反復数である。 分析の鍵となるアイデアは、2つのステップサイズを適切に選択し、高速かつ遅い時間スケールのイテレート間の結合を特徴付けることです。

関連論文リスト

• Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation [23.89036529638614]
  近似(SA)におけるパラメータの時間一様統計的推測について検討する。 線形および非線形のSA問題の両方において,平均的反復のほぼ無限収束率をガウスのスケールした和に解析する。
  論文  参考訳（メタデータ） (2024-10-19T10:27:26Z)
• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
  本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。 私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。 これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
  論文  参考訳（メタデータ） (2024-01-23T13:44:15Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise [2.0305676256390934]
  2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。 特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。 演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
  論文  参考訳（メタデータ） (2021-04-04T15:19:19Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)

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

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