論文の概要: On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2409.10323v1
- Date: Mon, 16 Sep 2024 14:35:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-17 15:20:31.992990
- Title: On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization
- Title（参考訳）: 非滑らかな非凸最適化における意味のある局所保証者の硬さについて
- Authors: Guy Kornowski, Swati Padmanabhan, Ohad Shamir,
- Abstract要約: 暗号非既知の正規最適化の複雑さを示す。
リプシッツ関数に作用する局所アルゴリズムは、最悪の場合、亜指数最小値の値に関して有意義な局所を与えることができない。
- 参考スコア（独自算出の注目度）: 37.41427897807821
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the oracle complexity of nonsmooth nonconvex optimization, with the algorithm assumed to have access only to local function information. It has been shown by Davis, Drusvyatskiy, and Jiang (2023) that for nonsmooth Lipschitz functions satisfying certain regularity and strictness conditions, perturbed gradient descent converges to local minimizers asymptotically. Motivated by this result and by other recent algorithmic advances in nonconvex nonsmooth optimization concerning Goldstein stationarity, we consider the question of obtaining a non-asymptotic rate of convergence to local minima for this problem class. We provide the following negative answer to this question: Local algorithms acting on regular Lipschitz functions cannot, in the worst case, provide meaningful local guarantees in terms of function value in sub-exponential time, even when all near-stationary points are global minima. This sharply contrasts with the smooth setting, for which it is well-known that standard gradient methods can do so in a dimension-independent rate. Our result complements the rich body of work in the theoretical computer science literature that provide hardness results conditional on conjectures such as $\mathsf{P}\neq\mathsf{NP}$ or cryptographic assumptions, in that ours holds unconditional of any such assumptions.
- Abstract（参考訳）: 我々は非滑らかな非凸最適化のオラクル複雑性について検討し、アルゴリズムは局所関数情報のみにアクセス可能であると仮定した。
Davis, Drusvyatskiy, and Jiang (2023) は、非滑らかリプシッツ函数が一定の規則性と厳密性条件を満たすとき、摂動勾配勾配は漸近的に局所最小化に収束することを示した。
この結果と、ゴールドスタイン定常性に関する非凸非滑らかな最適化における最近のアルゴリズムの進歩により、この問題クラスに対する局所ミニマへの非漸近的な収束率を得るという問題を考える。
正則リプシッツ関数に作用する局所アルゴリズムは、最悪の場合、すべての準定常点が大域最小値である場合でも、部分指数時間における関数値の観点から有意義な局所保証を提供できない。
これはスムーズな設定とは対照的であり、標準勾配法が次元に依存しない速度で行うことはよく知られている。
我々の結果は、$\mathsf{P}\neq\mathsf{NP}$や暗号的仮定のような予想に条件づけられた硬度結果を提供する理論計算機科学文学における豊富な研究を補完する。
関連論文リスト
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。
これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
論文 参考訳（メタデータ） (2024-09-28T02:30:44Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees [7.08249229857925]
勾配 Hessian に不連続な滑らかな非オラクル関数の最小化を考える。
提案手法の新たな特徴は, 負曲率の近似方向が選択された場合, 感覚緩和を等勾配で負となるように選択することである。
論文 参考訳（メタデータ） (2023-10-28T22:57:56Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Projective Proximal Gradient Descent for A Class of Nonconvex Nonsmooth Optimization Problems: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property [19.988762532185884]
非滑らかな最適化問題は、学習にとって重要かつ困難である。
本稿では,PSGDの高速収束を示す新しい解析法について述べる。
論文 参考訳（メタデータ） (2023-04-20T17:39:24Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - A Local Convergence Theory for the Stochastic Gradient Descent Method in
Non-Convex Optimization With Non-isolated Local Minima [0.0]
非孤立ミニマは、未探索のままのユニークな挑戦を示す。
本稿では, 勾配降下法の非溶解大域ミニマへの局所収束について検討する。
論文 参考訳（メタデータ） (2022-03-21T13:33:37Z) - Tackling benign nonconvexity with smoothing and stochastic gradients [28.197694894254305]
非最適化問題は機械学習、特にディープラーニングでは一般的な問題である。
本稿では,そのような問題を解決するために勾配勾配勾配を利用する方法を示す。
論文 参考訳（メタデータ） (2022-02-18T07:27:32Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。