論文の概要: Efficiently Escaping Saddle Points for Non-Convex Policy Optimization
- arxiv url: http://arxiv.org/abs/2311.08914v1
- Date: Wed, 15 Nov 2023 12:36:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-16 16:12:34.862797
- Title: Efficiently Escaping Saddle Points for Non-Convex Policy Optimization
- Title（参考訳）: 非凸政策最適化のための効率的なサドルポイントの抽出
- Authors: Sadegh Khorasani, Saber Salehkaleybar, Negar Kiyavash, Niao He,
Matthias Grossglauser
- Abstract要約: 政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
- 参考スコア（独自算出の注目度）: 40.0986936439803
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Policy gradient (PG) is widely used in reinforcement learning due to its
scalability and good performance. In recent years, several variance-reduced PG
methods have been proposed with a theoretical guarantee of converging to an
approximate first-order stationary point (FOSP) with the sample complexity of
$O(\epsilon^{-3})$. However, FOSPs could be bad local optima or saddle points.
Moreover, these algorithms often use importance sampling (IS) weights which
could impair the statistical effectiveness of variance reduction. In this
paper, we propose a variance-reduced second-order method that uses second-order
information in the form of Hessian vector products (HVP) and converges to an
approximate second-order stationary point (SOSP) with sample complexity of
$\tilde{O}(\epsilon^{-3})$. This rate improves the best-known sample complexity
for achieving approximate SOSPs by a factor of $O(\epsilon^{-0.5})$. Moreover,
the proposed variance reduction technique bypasses IS weights by using HVP
terms. Our experimental results show that the proposed algorithm outperforms
the state of the art and is more robust to changes in random seeds.
- Abstract（参考訳）: ポリシーグラデーション(pg)はそのスケーラビリティと優れたパフォーマンスのために強化学習で広く使われている。
近年では、O(\epsilon^{-3})$のサンプル複雑性を持つ近似一階定常点(FOSP)に収束する理論的保証として、分散還元PG法がいくつか提案されている。
しかし、FOSPはローカルの最適点やサドルポイントが悪いかもしれない。
さらに、これらのアルゴリズムは、分散還元の統計効果を損なう重要なサンプリング(is)重みを用いることが多い。
本稿では, Hessian ベクトル積 (HVP) の形で二階情報を用い, サンプル複雑性$\tilde{O}(\epsilon^{-3})$で近似二階定常点 (SOSP) に収束する分散還元二階法を提案する。
この速度は、近似SOSPを$O(\epsilon^{-0.5})$とすることで、最もよく知られたサンプル複雑性を改善する。
さらに、提案手法は、HVP項を用いてIS重みをバイパスする。
実験結果から,提案アルゴリズムは技術状況よりも優れ,無作為な種子の変化に対してより堅牢であることがわかった。
関連論文リスト
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。
所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
論文 参考訳（メタデータ） (2024-05-23T11:46:03Z) - 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) - Momentum-Based Policy Gradient with Second-Order Information [40.51117836892182]
本稿では,2次情報を勾配降下に組み込んだSHARP法を提案する。
従来の研究と異なり,提案アルゴリズムでは,分散還元プロセスの利点を損なうような重要サンプリングを必要としない。
提案手法が様々な制御課題に対して有効であることを示すとともに,実際の技術状況に対する優位性を示す。
論文 参考訳（メタデータ） (2022-05-17T11:56:50Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Cautiously Optimistic Policy Optimization and Exploration with Linear
Function Approximation [48.744735294559824]
政策最適化手法は、その漸進的かつ政治的性質が価値に基づくアルゴリズムよりも安定しているため、一般的な強化学習アルゴリズムである。
本稿では,PCPGのサンプル複雑性問題を克服し,モデルのミスセグメンテーションに頑健さを保ちながら,新しいアルゴリズムCOPOEを提案する。
その結果、PCPGの$widetildeO (1/epsilon11)$からPCPGの$widetildeO (1/epsilon3)$まで、サンプルの複雑さが改善され、値ベースの技術とのギャップがほぼ埋められます。
論文 参考訳（メタデータ） (2021-03-24T01:42:59Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。