論文の概要: The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
- arxiv url: http://arxiv.org/abs/2609.23837v1
- Date: Sun, 20 Sep 2026 19:37:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-22 20:29:01.007375
- Title: The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
- Title（参考訳）: 非滑らかな非凸最適化における決定論の指数価格
- Abstract要約: 非滑らかな非滑らかなリプシッツ関数の発見の複雑さについて検討する。
我々は、決定論的アルゴリズムに対して位数$()(d)$の低い境界を証明した。
その結果,非滑らかなアルゴリズムにおいて指数関数計算の優位性を確立した。
- 参考スコア（独自算出の注目度）: 8.5859167770773
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.
- Abstract（参考訳）: 我々は、非滑らかな非凸リプシッツ函数の(δ,ε)$-ゴールドスタイン定常点を求める複雑さについて研究する。
現在までに、ランダム化された一階述語アルゴリズムはこの問題を次元自由オラクル複雑性(Zhang et al , 2020)で解けることが知られているが、決定論的アルゴリズムは、その複雑さは少なくとも次元$d$[Jordan et al , 2023, Tian and So, 2024]で線形にスケールする必要があるため、決定論的アルゴリズムではできない。
これにより、決定論的アルゴリズムがそれにもかかわらず、オラクル複雑性多項式の問題を$d$で解くことができるかどうかが明らかになる。
我々は、決定論的アルゴリズムの次数$(1/ε)^{Ω(d)}$の下位境界を証明し、既知下界と上界の間の指数的ギャップを閉じ、Jordan et al [2023] による開問題を解くことで、この疑問に否定的に答える。
さらに、この結果のいくつかの拡張と、より弱い定常性の概念への含意、降下方向の発見、決定論的滑らか化について論じる。
全体として、ランダム化によって提供される非滑らかな非凸最適化において、指数関数的な計算優位性を確立した。
関連論文リスト
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - On the Complexity of Finding Small Subgradients in Nonsmooth Optimization [37.300102993926046]
決定論的アルゴリズムにより次元自由度を達成できないことを示す。
関数が凸である場合に、$(delta,epsilon)$-定常点を見つける収束率をどのように改善できるかを示す。
論文 参考訳（メタデータ） (2022-09-21T13:30:00Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。