論文の概要: A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness
- arxiv url: http://arxiv.org/abs/2403.15244v2
- Date: Thu, 26 Sep 2024 15:56:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 03:48:22.305126
- Title: A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness
- Title（参考訳）: 非一様滑らかな非凸最適化のための確率的準ニュートン法
- Authors: Zhenyu Sun, Ermin Wei,
- Abstract要約: 滑らか性に不均一性が存在する場合の高速準ニュートン法を提案する。
我々のアルゴリズムは、最もよく知られた$mathcalO(epsilon-3)$サンプルの複雑さを達成でき、収束のスピードアップを楽しむことができる。
我々の数値実験により,提案アルゴリズムは最先端の手法よりも優れていることが示された。
- 参考スコア（独自算出の注目度）: 4.097563258332958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Classical convergence analyses for optimization algorithms rely on the widely-adopted uniform smoothness assumption. However, recent experimental studies have demonstrated that many machine learning problems exhibit non-uniform smoothness, meaning the smoothness factor is a function of the model parameter instead of a universal constant. In particular, it has been observed that the smoothness grows with respect to the gradient norm along the training trajectory. Motivated by this phenomenon, the recently introduced $(L_0, L_1)$-smoothness is a more general notion, compared to traditional $L$-smoothness, that captures such positive relationship between smoothness and gradient norm. Under this type of non-uniform smoothness, existing literature has designed stochastic first-order algorithms by utilizing gradient clipping techniques to obtain the optimal $\mathcal{O}(\epsilon^{-3})$ sample complexity for finding an $\epsilon$-approximate first-order stationary solution. Nevertheless, the studies of quasi-Newton methods are still lacking. Considering higher accuracy and more robustness for quasi-Newton methods, in this paper we propose a fast stochastic quasi-Newton method when there exists non-uniformity in smoothness. Leveraging gradient clipping and variance reduction, our algorithm can achieve the best-known $\mathcal{O}(\epsilon^{-3})$ sample complexity and enjoys convergence speedup with simple hyperparameter tuning. Our numerical experiments show that our proposed algorithm outperforms the state-of-the-art approaches.
- Abstract（参考訳）: 最適化アルゴリズムの古典的な収束解析は、広く適応された均一な滑らかさの仮定に依存する。
しかし、最近の実験では、多くの機械学習問題が不均一な滑らかさを示しており、つまり滑らかさ係数は普遍定数ではなくモデルパラメータの関数である。
特に、トレーニング軌道に沿った勾配ノルムに対して滑らかさが増加することが観察されている。
この現象に触発され、最近導入された$(L_0, L_1)$-smoothnessは、従来の$-L$-smoothnessと比較してより一般的な概念であり、滑らかさと勾配ノルムの間のそのような正の関係を捉えている。
このタイプの非一様滑らか性の下で、既存の文献は勾配クリッピング法を利用して確率的一階法を設計し、最適な$\mathcal{O}(\epsilon^{-3})$サンプル複雑性を求め、$\epsilon$-approximate 1階定常解を求める。
しかし、準ニュートン法の研究はいまだに不足している。
本稿では, 準ニュートン法について, より精度が高く, より堅牢性が高いことを考慮し, 滑らか性に非均一性が存在する場合の高速確率的準ニュートン法を提案する。
勾配のクリッピングとばらつきの低減を利用して、我々のアルゴリズムは最もよく知られた$\mathcal{O}(\epsilon^{-3})$サンプルの複雑さを達成でき、単純なハイパーパラメータチューニングで収束速度を上げることができる。
我々の数値実験により,提案アルゴリズムは最先端の手法よりも優れていることが示された。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - 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) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient
Clipping [69.9674326582747]
そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。
この場合、最先端の結果を上回る新たな複雑さが証明される。
本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
論文 参考訳（メタデータ） (2020-05-21T17:05:27Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。