論文の概要: Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?

• arxiv url: http://arxiv.org/abs/2002.11962v3
• Date: Thu, 15 Apr 2021 19:09:29 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 09:24:57.508965
• Title: Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• Title（参考訳）: 非滑らかな非凸関数のほぼ定常点が見つかるか?
• Authors: Ohad Shamir
• Abstract要約: 有界で滑らかな非函数が与えられたとき、標準勾配法は特定の点を見つけることができることはよく知られている。 おそらく最も自然な緩和は、そのような$ilon$点である点を見つけることである。
• 参考スコア（独自算出の注目度）: 31.714928102950584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that given a bounded, smooth nonconvex function, standard gradient-based methods can find $\epsilon$-stationary points (where the gradient norm is less than $\epsilon$) in $\mathcal{O}(1/\epsilon^2)$ iterations. However, many important nonconvex optimization problems, such as those associated with training modern neural networks, are inherently not smooth, making these results inapplicable. Moreover, as recently pointed out in Zhang et al. [2020], it is generally impossible to provide finite-time guarantees for finding an $\epsilon$-stationary point of nonsmooth functions. Perhaps the most natural relaxation of this is to find points which are near such $\epsilon$-stationary points. In this paper, we show that even this relaxed goal is hard to obtain in general, given only black-box access to the function values and gradients. We also discuss the pros and cons of alternative approaches.
• Abstract（参考訳）: 有界で滑らかな非凸函数が与えられたとき、標準勾配法は$\epsilon$-定常点(勾配ノルムが$\epsilon$より小さい)を$\mathcal{O}(1/\epsilon^2)$反復で見つけることができる。 しかし、現代のニューラルネットワークのトレーニングなど、多くの重要な非凸最適化問題は本質的に滑らかではないため、これらの結果は適用できない。 さらに、zhang et alで最近指摘されたように。 [2020] は一般に、非滑らか関数の$\epsilon$-定常点を求める有限時間保証を提供することは不可能である。 おそらく最も自然な緩和は、そのような$\epsilon$-定常点に近い点を見つけることである。 本稿では,関数値や勾配へのブラックボックスアクセスのみを考慮すれば,この緩和目標でさえ一般には得られないことを示す。 代替アプローチの長所と短所についても論じる。

関連論文リスト

• The Computational Complexity of Finding Stationary Points in Non-Convex Optimization [53.86485757442486]
  近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
  論文  参考訳（メタデータ） (2023-10-13T14:52:46Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
  局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。 SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。 我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
  論文  参考訳（メタデータ） (2021-10-25T07:20:05Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms [0.0]
  主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。 標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
  論文  参考訳（メタデータ） (2021-02-04T19:17:13Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
  本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。 この方法はこの問題でよく知られている。
  論文  参考訳（メタデータ） (2020-01-11T09:05:03Z)
• Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond [25.845034951660544]
  我々は,一階述語法では改善できないことを示した。 我々は、$$quasar のアログ関数を計算する変種加速降下を開発する。 ファーストオーダーの方法では改善できません。
  論文  参考訳（メタデータ） (2019-06-27T22:39:35Z)

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

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