論文の概要: Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions

• arxiv url: http://arxiv.org/abs/2205.12856v1
• Date: Wed, 25 May 2022 15:33:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-26 17:18:30.912901
• Title: Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions
• Title（参考訳）: 勾配支配関数に対するsgdを打ち負かす確率的二階法
• Authors: Saeed Masiha, Saber Salehkaleybar, Niao He, Negar Kiyavash, Patrick Thiran
• Abstract要約: SCRNは,最もよく知られた勾配勾配勾配勾配の複雑さを$mathcalO(epsilon-1/2)$で改善することを示した。 また, SCRNのサンプルの複雑さは, バッチサイズが異なる分散還元法を用いて$mathcalO(epsilon-1/2)$で改善できることを示した。
• 参考スコア（独自算出の注目度）: 42.57892322514602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that SCRN improves the best-known sample complexity of stochastic gradient descent in achieving $\epsilon$-global optimum by a factor of $\mathcal{O}(\epsilon^{-1/2})$. Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the sample complexity of SCRN can be improved by a factor of ${\mathcal{O}}(\epsilon^{-1/2})$ using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.
• Abstract（参考訳）: 確率的立方体正規化ニュートン(scrn)の勾配支配性を満たす関数群における性能について検討し,機械学習と信号処理の幅広い応用について検討した。 この条件は、任意の一階定常点が大域的最適であることを保証する。 SCRNは、$\epsilon$-global optimumを$\mathcal{O}(\epsilon^{-1/2})$の係数で達成することで、確率勾配降下の最もよく知られたサンプル複雑性を改善する。 政策ベース強化学習(RL)に適用可能な勾配支配特性の弱いバージョンであっても、SCRNは確率的政策勾配法に対して同様の改善を行う。 さらに, SCRNのサンプル複雑性は, 時間変化したバッチサイズを持つ分散還元法を用いて${\mathcal{O}}(\epsilon^{-1/2})$の係数で改善できることを示した。 各種RL設定実験の結果, SCRNの性能は1次法と比較して顕著であった。

関連論文リスト

• On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization [10.36447258513813]
  我々は、強化学習(RL)における既存の問題の多くを網羅する非文献設定における正規化期待報酬最適化問題を考える。 特に、標準条件下では、$O(epsilon-4)$サンプルを$epsilon$-stationaryポイントに含めることが示されている。 分析の結果,サンプルの複雑さは,追加条件下では$O(epsilon-4)$から$O(epsilon-3)$に改善できることがわかった。
  論文  参考訳（メタデータ） (2024-01-23T06:01:29Z)
• Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
  政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。 本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
  論文  参考訳（メタデータ） (2023-11-15T12:36:45Z)
• A Homogenization Approach for Gradient-Dominated Stochastic Optimization [6.1144486886258065]
  勾配支配を享受する関数に対する同次二階降下法(SHSOD)を提案する。 以上の結果から,SHSODMは勾配優先最適化法において,他の2次法で達成された最もよく知られたサンプルの複雑さと一致していることがわかった。
  論文  参考訳（メタデータ） (2023-08-21T11:03:04Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
  ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。 その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
  論文  参考訳（メタデータ） (2021-04-09T14:50:59Z)
• 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)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
  本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。 本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
  論文  参考訳（メタデータ） (2020-04-27T17:11:06Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。