論文の概要: Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity

• arxiv url: http://arxiv.org/abs/2503.04712v1
• Date: Thu, 06 Mar 2025 18:57:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-07 15:57:37.003461
• Title: Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity
• Title（参考訳）: 自己境界規則性による平滑化下でのサドル点の効率的な脱出
• Authors: Daniel Yiming Cao, August Y. Chen, Karthik Sridharan, Benjamin Tang,
• Abstract要約: 一階法および二階法における適切な点を示す。 我々の知る限り、これは一階一般化の下での非定常最適化のための最初のノンテキストブックである。
• 参考スコア（独自算出の注目度）: 7.075987963315121
• License:
• Abstract: In this paper, we study the problem of non-convex optimization on functions that are not necessarily smooth using first order methods. Smoothness (functions whose gradient and/or Hessian are Lipschitz) is not satisfied by many machine learning problems in both theory and practice, motivating a recent line of work studying the convergence of first order methods to first order stationary points under appropriate generalizations of smoothness. We develop a novel framework to study convergence of first order methods to first and \textit{second} order stationary points under generalized smoothness, under more general smoothness assumptions than the literature. Using our framework, we show appropriate variants of GD and SGD (e.g. with appropriate perturbations) can converge not just to first order but also \textit{second order stationary points} in runtime polylogarithmic in the dimension. To our knowledge, our work contains the first such result, as well as the first 'non-textbook' rate for non-convex optimization under generalized smoothness. We demonstrate that several canonical non-convex optimization problems fall under our setting and framework.
• Abstract（参考訳）: 本稿では,一階法で必ずしも滑らかでない関数に対する非凸最適化の問題について検討する。 スムースネス(スムースネス、勾配とヘシアンがリプシッツである関数)は、理論と実践の両方において多くの機械学習問題に満たされず、スムースネスの適切な一般化の下で第一次定常点への一階法収束を研究する最近の研究の行を動機付けている。 本研究では,一階法から一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法,一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、二階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一階法、一 我々のフレームワークを用いて、GD と SGD の適切な変種(例えば、適切な摂動を持つ)は、一階だけでなく、次元のランタイム多元対数において \textit{second order stationary points} にも収束できることを示す。 我々の知る限り、我々の研究は、一般化された滑らかさの下での非凸最適化のための最初の「非テキストブック」レートと、そのような結果を含む。 いくつかの標準的非凸最適化問題は、我々の設定とフレームワークに該当することを示した。

関連論文リスト

• Mirror Descent Under Generalized Smoothness [23.5387392871236]
  一般ノルムと双対のヘッセン項のノルムを測定する新しい$ell*$-smoothnessの概念を導入する。 我々は、古典的な滑らかさの下でのレートに一致するミラー・ディフレッシュ型アルゴリズムの収束性を確立する。
  論文  参考訳（メタデータ） (2025-02-02T11:23:10Z)
• Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization [52.61737731453222]
  非マシーン学習問題は通常、標準的な滑らかさの仮定に従わない。 本稿では,ローカルステップ,クライアントの部分的参加,ランダムランダムリシャッフルによる新しい手法の提案と解析を行う。 我々の理論は、標準的な滑らかな問題に対する既知の結果と一致している。
  論文  参考訳（メタデータ） (2024-12-03T19:20:56Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
  論文  参考訳（メタデータ） (2022-06-23T08:10:54Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• 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)
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization [1.6973426830397942]
  平滑な非有限和最適化における高階法の下限を証明する。 pth-order regularized method は有限和の目的から利益を得ることができないことを示す。 新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
  論文  参考訳（メタデータ） (2021-03-08T23:33:58Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。 実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
  論文  参考訳（メタデータ） (2020-05-19T07:44:52Z)

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

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