論文の概要: Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2606.05438v1
• Date: Wed, 03 Jun 2026 21:01:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-05 22:39:44.405035
• Title: Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
• Title（参考訳）: 高次スムーズ非凸最適化のためのシャープ一階下界
• Authors: Dongruo Zhou,
• Abstract要約: 我々は高次スムーズな非次関数に対する新しい次元自由一階勾配を証明した。 この構造はChatGPT 5.5 Proの助けを借りて発見され、その後著者たちによって検証された。
• 参考スコア（独自算出の注目度）: 22.27814708607424
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study the deterministic first-order oracle complexity of finding \(ε\)-stationary points in smooth nonconvex optimization when the objective satisfies higher-order smoothness assumptions. While the classical \(ε^{-2}\) rate is optimal under only Lipschitz gradients, higher-order smoothness leads to accelerated first-order upper bounds, most notably the \(ε^{-7/4}\) rate under Lipschitz Hessians and the \(ε^{-5/3}\) rate under Lipschitz third derivatives. The matching lower bounds, however, have remained open. We resolve this gap by proving a new dimension-free first-order lower bound for higher-order smooth nonconvex functions, valid for every finite smoothness order. In particular, our construction gives a matching \(Ω(ε^{-7/4})\) lower bound in the Hessian-Lipschitz case and a matching \(Ω(ε^{-5/3})\) lower bound in the third-order-smooth regime. The hard instance is based on a \emph{block-chain} mechanism that enforces blockwise oracle revelation while preserving the smoothness structure needed for the scalar hard instance. The lower-bound construction was discovered with the assistance of ChatGPT 5.5 Pro and subsequently verified by the authors.
• Abstract（参考訳）: 目的が高次滑らか性仮定を満たすとき, 滑らかな非凸最適化において, \(ε\)-定常点を求める決定論的一階オラクル複雑性について検討する。 古典的な \(ε^{-2}\) はリプシッツ勾配のみにおいて最適であるが、高次の滑らかさは、リプシッツ・ヘッセンの \(ε^{-7/4}\) とリプシッツの第3微分の \(ε^{-5/3}\) の3階上界を加速させる。 しかし、一致する下界は依然として開である。 このギャップは、高次の滑らかな非凸函数に対する新しい次元自由な一階下界を証明し、すべての有限な滑らかさ順序に有効である。 特に、我々の構成は、ヘッセン・リプシッツのケースにおける整合 \(Ω(ε^{-7/4})\ と、3階スムース体制における整合 \(Ω(ε^{-5/3})\ を与える。 ハードインスタンスは、スカラーハードインスタンスに必要な滑らかな構造を維持しながらブロックワイドなオラクルの啓示を強制する \emph{block-chain} メカニズムに基づいている。 下界の建設はChatGPT 5.5 Proの助けを借りて発見され、その後著者たちによって検証された。

関連論文リスト

• Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles [26.059192929942842]
  少なくとも$()/2$呼び出しは、関連する設定で最もよく知られた境界を強化する必要があります。 我々の結果は、単純化された体制でさえ、そのような体制が低レベルに適用可能であることを示唆していることを示唆している。
  論文  参考訳（メタデータ） (2025-11-24T19:43:40Z)
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits [53.773695219320125]
  重み付き雑音下での2階最適化の理論的理解に向けて第一歩を踏み出す。 勾配とヘッセン切断に基づく新しいアルゴリズムを導入し、基本限界にほぼ一致する高い確率上の境界を証明した。
  論文  参考訳（メタデータ） (2025-10-12T16:36:54Z)
• Mirror Descent Under Generalized Smoothness [23.5387392871236]
  一般ノルムと双対という観点からヘッセンのノルムを測定する新しい$ell*$-smoothnessの概念を導入する。 我々は、古典的な滑らかさの下でのレートに一致するミラー・ディフレッシュ型アルゴリズムの収束性を確立する。
  論文  参考訳（メタデータ） (2025-02-02T11:23:10Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization [1.6973426830397942]
  平滑な非有限和最適化における高階法の下限を証明する。 pth-order regularized method は有限和の目的から利益を得ることができないことを示す。 新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
  論文  参考訳（メタデータ） (2021-03-08T23:33:58Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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