論文の概要: Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving
$O(1/k)$ Finite-Sample Complexity
- arxiv url: http://arxiv.org/abs/2401.12764v2
- Date: Wed, 24 Jan 2024 02:02:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-25 11:39:35.456374
- Title: Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving
$O(1/k)$ Finite-Sample Complexity
- Title(参考訳): 高速非線形2時間スケール確率近似:$O(1/k)$ Finite-Sample Complexity
- Authors: Thinh T. Doan
- Abstract要約: 本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。
私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。
- 参考スコア(独自算出の注目度): 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 $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
$O(1/k^{2/3})$.
- Abstract(参考訳): 本稿では,2つの結合した非線形作用素の根を探すために,2時間スケール確率近似の新しい変種を開発することを提案する。
私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を利用して、サンプルを通して演算子を動的に推定することです。
これらの平均化ステップの推定値は、望ましい解を見つけるために二度スケールの確率近似更新で使用される。
我々の理論的な主な結果は、基礎となる非線形作用素の強い単調条件の下で、提案手法によって生成されるイテレートの平均二乗誤差が最適速度$O(1/k)$でゼロに収束することを示すことである。
この結果は, 2 倍の確率近似の既存の結果を大幅に改善し, 最もよく知られた有限時間収束率は $o(1/k^{2/3})$ である。
関連論文リスト
- Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳(メタデータ) (2022-10-11T17:04:45Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳(メタデータ) (2022-04-20T07:14:21Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - A Two-Time-Scale Stochastic Optimization Framework with Applications in
Control and Reinforcement Learning [22.07834608976826]
本研究では, 時間変化勾配から試料が生成する問題を解くための2段階勾配法について検討した。
我々は$mathcal(k-2/3O)$の収束が達成されていることを示す。
論文 参考訳(メタデータ) (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) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。