論文の概要: 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})$を導出する。
最後に,収束率を可視化する数値シミュレーションによる理論的解析を支援する。
関連論文リスト
- Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳(メタデータ) (2022-07-31T19:41:22Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳(メタデータ) (2022-03-30T11:39:00Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes [22.07834608976826]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳(メタデータ) (2021-10-21T18:05:40Z) - COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic
Convex Optimization [4.970364068620608]
我々は,勾配オラクルによって出力される雑音の推定値を改善するために,凸性およびL平滑性を利用する。
問合せ点の数と近さの増加は、より良い勾配推定に繋がることを示す。
また、SGD、Adam、STRSAGAといった既存のアルゴリズムにCOCOをプラグインすることで、バニラ設定にもCOCOを適用します。
論文 参考訳(メタデータ) (2021-09-07T17:21:09Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳(メタデータ) (2021-06-28T00:17:01Z) - 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) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z) - Convergence and sample complexity of gradient methods for the model-free
linear quadratic regulator problem [27.09339991866556]
本稿では,コントローラの空間を直接探索することにより,未知の計算系に対する最適制御を求める。
我々は、安定化フィードバックゲインの勾配-フローのダイナミクスセットに焦点をあてて、そのような手法の性能と効率を最小化するための一歩を踏み出した。
論文 参考訳(メタデータ) (2019-12-26T16:56:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。