論文の概要: A Two-Time-Scale Stochastic Optimization Framework with Applications in
Control and Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2109.14756v1
- Date: Wed, 29 Sep 2021 23:15:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-01 14:39:16.876828
- Title: A Two-Time-Scale Stochastic Optimization Framework with Applications in
Control and Reinforcement Learning
- Title（参考訳）: 制御と強化学習を応用した2時間スケール確率最適化フレームワーク
- Authors: Sihan Zeng, Thinh T. Doan, Justin Romberg
- Abstract要約: 本研究では, 時間変化勾配から試料が生成する問題を解くための2段階勾配法について検討した。
我々は$mathcal(k-2/3O)$の収束が達成されていることを示す。
- 参考スコア（独自算出の注目度）: 22.07834608976826
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a novel two-time-scale stochastic gradient method for solving
optimization problems where the gradient samples are generated from a
time-varying Markov random process parameterized by the underlying optimization
variable. These time-varying samples make the stochastic gradient biased and
dependent, which can potentially lead to the divergence of the iterates. To
address this issue, we consider a two-time-scale update scheme, where one scale
is used to estimate the true gradient from the Markovian samples and the other
scale is used to update the decision variable with the estimated gradient.
While these two iterates are implemented simultaneously, the former is updated
"faster" (using bigger step sizes) than the latter (using smaller step sizes).
Our first contribution is to characterize the finite-time complexity of the
proposed two-time-scale stochastic gradient method. In particular, we provide
explicit formulas for the convergence rates of this method under different
objective functions, namely, strong convexity, convexity, non-convexity under
the PL condition, and general non-convexity.
Our second contribution is to apply our framework to study the performance of
the popular actor-critic methods in solving stochastic control and
reinforcement learning problems. First, we study an online natural actor-critic
algorithm for the linear-quadratic regulator and show that a convergence rate
of $\mathcal{O}(k^{-2/3})$ is achieved. This is the first time such a result is
known in the literature. Second, we look at the standard online actor-critic
algorithm over finite state and action spaces and derive a convergence rate of
$\mathcal{O}(k^{-2/5})$, which recovers the best known rate derived
specifically for this problem. Finally, we support our theoretical analysis
with numerical simulations where the convergence rate is visualized.
- Abstract（参考訳）: 最適化変数によってパラメータ化されるマルコフ確率過程から勾配サンプルが生成される最適化問題の解法として,新しい2時間スケール確率勾配法を提案する。
これらの時間変化のサンプルは確率勾配を偏り、依存させ、それが繰り返しの発散につながる可能性がある。
この問題に対処するために、マルコフサンプルから真の勾配を推定するために1スケール、推定した勾配で決定変数を更新するために別のスケールを使用する2段階の更新方式を検討する。
これら2つのイテレートは同時に実装されるが、前者は後者(より小さなステップサイズを使用して)よりも"高速"に更新される。
第1の貢献は,提案する2時間スケール確率勾配法の有限時間複雑性を特徴付けることである。
特に、異なる目的関数、すなわち、pl条件下での強い凸性、凸性、非凸性、一般非凸性の下での収束率に対する明示的な公式を提供する。
第2のコントリビューションは,確率的制御と強化学習問題の解法におけるアクター批判手法の性能に関する研究に,我々の枠組みを適用することである。
まず,線形量子レギュレータに対するオンライン自然アクター-クリティックアルゴリズムについて検討し,$\mathcal{o}(k^{-2/3})$ の収束が達成されることを示す。
このような結果が文献に知られるのはこれが初めてである。
第二に、有限状態および作用空間上の標準的なオンラインアクター批判アルゴリズムを考察し、この問題に特化して導出された最もよく知られたレートを回復する$\mathcal{O}(k^{-2/5})$を導出する。
最後に,収束率を可視化する数値シミュレーションによる理論的解析を支援する。
関連論文リスト
- Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。
提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
論文 参考訳（メタデータ） (2024-05-15T19:03:08Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳（メタデータ） (2023-01-28T12:09:58Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳（メタデータ） (2022-07-31T19:41:22Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳（メタデータ） (2020-09-23T20:02:00Z) - 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) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。