論文の概要: Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving
$\mathcal{O}(1/k)$ Finite-Sample Complexity
- arxiv url: http://arxiv.org/abs/2401.12764v1
- Date: Tue, 23 Jan 2024 13:44:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 15:31:27.973817
- Title: Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving
$\mathcal{O}(1/k)$ Finite-Sample Complexity
- Title（参考訳）: 高速非線形2時間スケール確率近似:$\mathcal{O}(1/k)$ Finite-Sample Complexity
- Authors: Thinh T. Doan
- Abstract要約: 2つの結合非線形作用素の根を求めるため、2時間スケール近似の新しい変種を開発する。
我々の理論の主な結果は、基礎となる非線形作用素の強い単調条件の下で、平均二乗誤差がゼロに収束することを示すことである。
- 参考スコア（独自算出の注目度）: 2.5382095320488665
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proposes to develop a new variant of the two-time-scale stochastic
approximation to find the roots of two coupled nonlinear operators, assuming
only noisy samples of these operators can be observed. Our key idea is to
leverage the classic Ruppert-Polyak averaging technique to dynamically estimate
the operators through their samples. The estimated values of these averaging
steps will then be used in the two-time-scale stochastic approximation updates
to find the desired solution. Our main theoretical result is to show that under
the strongly monotone condition of the underlying nonlinear operators the
mean-squared errors of the iterates generated by the proposed method converge
to zero at an optimal rate $\mathcal{O}(1/k)$, where $k$ is the number of
iterations. Our result significantly improves the existing result of
two-time-scale stochastic approximation, where the best known finite-time
convergence rate is $\mathcal{O}(1/k^{2/3})$.
- Abstract（参考訳）: 本稿では,2つの結合した非線形作用素の根を探すために,2時間スケール確率近似の新しい変種を開発することを提案する。
私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を利用して、サンプルを通して演算子を動的に推定することです。
これらの平均化ステップの推定値は、望ましい解を見つけるために二度スケールの確率近似更新で使用される。
我々の理論的な主な結果は、基礎となる非線形作用素の強い単調条件の下で、提案法によって生成されるイテレートの平均二乗誤差が最適速度$\mathcal{O}(1/k)$でゼロに収束することを示すことである。
この結果は、最もよく知られた有限時間収束速度が$\mathcal{O}(1/k^{2/3})$である2時間確率近似の既存の結果を著しく改善する。
関連論文リスト
- Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。
提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
論文 参考訳（メタデータ） (2024-05-15T19:03:08Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - 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) - A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
最適化問題の解法として,新しい2段階勾配法を提案する。
最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。
我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
論文 参考訳（メタデータ） (2021-09-29T23:15:23Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
非線形2時間スケール近似の収束と有限時間解析について検討する。
特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
論文 参考訳（メタデータ） (2020-11-03T17:43:39Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms [58.57004511121862]
アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
論文 参考訳（メタデータ） (2020-05-07T15:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。