論文の概要: $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation

• arxiv url: http://arxiv.org/abs/2504.19375v1
• Date: Sun, 27 Apr 2025 22:45:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.260688
• Title: $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
• Title（参考訳）: O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation
• Authors: Siddharth Chandak,
• Abstract要約: 非線形2時間スケール近似に対して$O (1/k)$の勾配境界を改良した。 この結果は、降下度や2時間スケールのラグランジアン最適化などのアルゴリズムに適用できる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two-time-scale stochastic approximation is an algorithm with coupled iterations which has found broad applications in reinforcement learning, optimization and game control. While several prior works have obtained a mean square error bound of $O(1/k)$ for linear two-time-scale iterations, the best known bound in the non-linear contractive setting has been $O(1/k^{2/3})$. In this work, we obtain an improved bound of $O(1/k)$ for non-linear two-time-scale stochastic approximation. Our result applies to algorithms such as gradient descent-ascent and two-time-scale Lagrangian optimization. The key step in our analysis involves rewriting the original iteration in terms of an averaged noise sequence which decays sufficiently fast. Additionally, we use an induction-based approach to show that the iterates are bounded in expectation.
• Abstract（参考訳）: 2時間スケール確率近似(英: two-time-scale stochastic approximation)は、強化学習、最適化、ゲーム制御において幅広い応用を見出した反復型アルゴリズムである。 いくつかの先行研究は、線形2時間スケールの反復に対して平均2乗誤差の$O(1/k)$を得たが、非線形の収縮条件における最もよく知られた境界は$O(1/k^{2/3})$である。 本研究では,非線形2時間スケール確率近似に対して,O(1/k)$を改良した値を求める。 この結果は勾配降下指数や2時間スケールラグランジアン最適化などのアルゴリズムに適用できる。 我々の分析における重要なステップは、十分に高速に減衰する平均的なノイズシーケンスの観点から、元の繰り返しを書き換えることである。 さらに、帰納的アプローチを用いて、反復が期待通りに束縛されていることを示す。

関連論文リスト

• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
  線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。 我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。 既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
  論文  参考訳（メタデータ） (2025-04-10T09:59:43Z)
• Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise [7.770605097524015]
  2時間スケール近似(英: Two-time-scale Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 強化学習の応用により、非線型2時間スケール SA 上の最初の平均正方形を与える。
  論文  参考訳（メタデータ） (2025-03-24T07:03:23Z)
• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis [0.0]
  より遅い時間スケールが拡張性のないマッピングを持つ2段階のイテレーションについて検討する。 平均二乗誤差は$O (1/k1/4-epsilon)$で減衰し、$epsilon>0$は任意に小さくなる。
  論文  参考訳（メタデータ） (2025-01-18T16:00:14Z)
• 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)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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