論文の概要: A Homogenization Approach for Gradient-Dominated Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2308.10630v1
• Date: Mon, 21 Aug 2023 11:03:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-22 13:59:52.552761
• Title: A Homogenization Approach for Gradient-Dominated Stochastic Optimization
• Title（参考訳）: 勾配支配確率最適化のための均質化手法
• Authors: Jiyuan Tan, Chenyu Xue, Chuwen Zhang, Qi Deng, Dongdong Ge, Yinyu Ye
• Abstract要約: 本稿では, エンフィロン正則化を伴わない勾配支配正規化法のロバスト性について検討する。 本結果は, エンフィロン正則化を伴わない勾配支配正則化のための最先端試料境界値と一致した。
• 参考スコア（独自算出の注目度）: 6.478966569118394
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gradient dominance property is a condition weaker than strong convexity, yet it sufficiently ensures global convergence for first-order methods even in non-convex optimization. This property finds application in various machine learning domains, including matrix decomposition, linear neural networks, and policy-based reinforcement learning (RL). In this paper, we study the stochastic homogeneous second-order descent method (SHSODM) for gradient-dominated optimization with $\alpha \in [1, 2]$ based on a recently proposed homogenization approach. Theoretically, we show that SHSODM achieves a sample complexity of $O(\epsilon^{-7/(2 \alpha) +1})$ for $\alpha \in [1, 3/2)$ and $\tilde{O}(\epsilon^{-2/\alpha})$ for $\alpha \in [3/2, 2]$. We further provide a SHSODM with a variance reduction technique enjoying an improved sample complexity of $O( \epsilon ^{-( 7-3\alpha ) /( 2\alpha )})$ for $\alpha \in [1,3/2)$. Our results match the state-of-the-art sample complexity bounds for stochastic gradient-dominated optimization without \emph{cubic regularization}. Since the homogenization approach only relies on solving extremal eigenvector problems instead of Newton-type systems, our methods gain the advantage of cheaper iterations and robustness in ill-conditioned problems. Numerical experiments on several RL tasks demonstrate the efficiency of SHSODM compared to other off-the-shelf methods.
• Abstract（参考訳）: 勾配支配性は強い凸性よりも弱い条件であるが、非凸最適化においても一階法に対する大域収束を十分に保証する。 この性質は、マトリックス分解、線形ニューラルネットワーク、ポリシーベース強化学習(rl)など、さまざまな機械学習領域で応用されている。 本稿では,最近提案されたホモゲナイズアプローチに基づき,$\alpha \in [1, 2]$を用いた勾配優位最適化のための確率的均質二階降法(shsodm)について検討する。 理論的には、SHSODM は $O(\epsilon^{-7/(2 \alpha) +1})$ for $\alpha \in [1, 3/2)$ and $\tilde{O}(\epsilon^{-2/\alpha})$ for $\alpha \in [3/2, 2]$ のサンプル複雑性を達成する。 さらに,$O( \epsilon ^{-(7-3\alpha ) /(2\alpha )})$ for $\alpha \in [1,3/2)$の改善されたサンプル複雑性を享受する分散低減技術を備えたSHSODMを提供する。 以上の結果は, 確率的勾配優位最適化のための, 最先端のサンプル複雑性境界と一致する。 ホモジェナイゼーションアプローチはニュートン型システムの代わりに極端固有ベクトル問題の解法にのみ依存するため、我々の手法は不条件問題においてより安価な反復と堅牢性の利点を得る。 いくつかのRLタスクに関する数値実験は、SHSODMの他のオフザシェルフ法と比較して効率を実証している。

関連論文リスト

• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
  論文  参考訳（メタデータ） (2024-01-26T01:16:59Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Stochastic Second-Order Methods Provably Beat SGD For Gradient-Dominated Functions [42.57892322514602]
  SCRNは,最もよく知られた勾配勾配勾配勾配の複雑さを$mathcalO(epsilon-1/2)$で改善することを示した。 また, SCRNのサンプルの複雑さは, バッチサイズが異なる分散還元法を用いて$mathcalO(epsilon-1/2)$で改善できることを示した。
  論文  参考訳（メタデータ） (2022-05-25T15:33:00Z)
• Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations [83.3201889218775]
  広く使われている1次サドル点最適化法は、帰納的導出時に同一の連続時間常微分方程式(ODE)を導出する。 しかし、これらの方法の収束特性は、単純な双線型ゲームでさえ質的に異なる。 いくつかのサドル点最適化法のための微分方程式モデルの設計に流体力学の研究フレームワークを採用する。
  論文  参考訳（メタデータ） (2021-12-27T18:31:34Z)
• 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)
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization [0.0]
  ネステロフの外挿は、非滑らかな問題に対して勾配降下法の個人収束を最適にする強さを持つことを証明している。 提案手法は,設定の非滑らかな損失を伴って正規化学習タスクを解くためのアルゴリズムの拡張である。 本手法は,大規模な1-正規化ヒンジロス学習問題の解法として有効である。
  論文  参考訳（メタデータ） (2020-06-08T03:35:41Z)
• Distributed Stochastic Nonconvex Optimization and Learning based on Successive Convex Approximation [26.11677569331688]
  本稿では,ネットワーク内のエージェントの総和の分散アルゴリズム最小化のための新しいフレームワークを提案する。 提案手法は分散ニューラルネットワークに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-04-30T15:36:46Z)

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

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