論文の概要: The Computational Complexity of Finding Stationary Points in Non-Convex Optimization

• arxiv url: http://arxiv.org/abs/2310.09157v2
• Date: Wed, 11 Sep 2024 18:24:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-13 22:22:54.201057
• Title: The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
• Title（参考訳）: 非凸最適化における定常点探索の計算複雑性
• Authors: Alexandros Hollender, Manolis Zampetakis,
• Abstract要約: 近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。 制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
• 参考スコア（独自算出の注目度）: 53.86485757442486
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions $f$ over unrestricted $d$-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension $d$ of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results: 1. The problem of finding approximate stationary points over unrestricted domains is PLS-complete. 2. For $d = 2$, we provide a zero-order algorithm for finding $\varepsilon$-approximate stationary points that requires at most $O(1/\varepsilon)$ value queries to the objective function. 3. We show that any algorithm needs at least $\Omega(1/\varepsilon)$ queries to the objective function and/or its gradient to find $\varepsilon$-approximate stationary points when $d=2$. Combined with the above, this characterizes the query complexity of this problem to be $\Theta(1/\varepsilon)$. 4. For $d = 2$, we provide a zero-order algorithm for finding $\varepsilon$-KKT points in constrained optimization problems that requires at most $O(1/\sqrt{\varepsilon})$ value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be $\Theta(1/\sqrt{\varepsilon})$. 5. Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.
• Abstract（参考訳）: 非凸だが滑らかな目的関数 $f$ over unrestricted $d$-dimensional domain は古典的非凸最適化における最も基本的な問題の1つである。 それでも、この問題の計算とクエリの複雑さは、その問題の次元$d$が近似誤差とは無関係であるときにはまだよく理解されていない。 本稿では,以下の計算およびクエリの複雑性結果を示す。 1. 制限のない領域に近似した定常点を求める問題はPLS完全である。 2.$d = 2$ の場合、目的関数に対して最大$O(1/\varepsilon)$値クエリを必要とする $\varepsilon$-approximate 定常点を求めるゼロオーダーアルゴリズムを提供する。 3. 任意のアルゴリズムが対象関数に対する少なくとも$\Omega(1/\varepsilon)$クエリと/またはその勾配を求め、$d=2$のとき$\varepsilon$-approximateの定常点を見つける。 上記の問題と組み合わせると、この問題のクエリの複雑さは$\Theta(1/\varepsilon)$である。 4.$d = 2$の場合、最大$O(1/\sqrt{\varepsilon})$値クエリを必要とする制約付き最適化問題において、$\varepsilon$-KKTを求めるゼロオーダーアルゴリズムを提供する。 これは、Bubeck と Mikulincer [2020] と Vavasis [1993] の間のギャップを埋め、この問題のクエリ複雑性を$\Theta(1/\sqrt{\varepsilon})$と特徴づける。 5) Fearnley et al [2022] の最近の結果と組み合わせて, 制約付き最適化における近似KKT点の発見は, 制約なし最適化における近似定常点の発見には有効であるが, 逆は不可能であることを示す。

関連論文リスト

• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。 代理オラクル関数に対するゼロ階量子推定器を構築する。
  論文  参考訳（メタデータ） (2024-10-21T16:52:26Z)
• On the Complexity of First-Order Methods in Stochastic Bilevel Optimization [9.649991673557167]
  両レベル最適化における定常点を求める問題は、下層問題に制約がなく、強い凸がある場合に考慮する。 既存のアプローチは、それらの分析を低レベルの解を知っているジェニーアルゴリズムに結びつける。 我々は、$O(epsilon-6), O(epsilon-4)$ 1次$y*$-aware oraclesを使って、$epsilon$固定点に収束する単純な一階法を提案する。
  論文  参考訳（メタデータ） (2024-02-11T04:26:35Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• 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)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain [11.562923882714093]
  Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。 我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
  論文  参考訳（メタデータ） (2021-10-08T07:46:18Z)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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