論文の概要: On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2610.19652v1
• Date: Wed, 14 Oct 2026 06:20:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:15.991955
• Title: On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
• Title（参考訳）: ゼロ階非凸最適化における大域的合同下界について
• Abstract要約: 我々は, 正確なスカラー, マルチフィールド推定, アンチサンプル実現による大域的に定義された非値構成を示す。 以上の結果から, サンプル関数の再利用を任意のサンプリング箇所で適応的に選択するアルゴリズムをRd$で示すことができた。
• 参考スコア（独自算出の注目度）: 16.685523134793723
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work has sought to transfer first-order nonconvex optimization guarantees to zeroth-order methods through gradient estimators, typically incurring a factor linear in $d$. \citet{kornowski2024} obtained an $\mathcal{O}(dδ^{-1}ε^{-3})$ oracle complexity for nonsmooth nonconvex optimization and asked whether its dependence on all three parameters is jointly optimal. Although the dimension dependence and the first-order dependence on $(δ,ε)$ are separately known to be unavoidable, a matching zeroth-order lower bound has remained open. We answer this question in the unrestricted full-space setting. For smooth stochastic nonconvex optimization, we establish a scalar-oracle lower bound of $Ω\!\left(dL_0^2\min\{ΔH,L_0^2\}/ε^4\right)$ assuming a smooth, globally lower-bounded population objective and a second-moment bound on sample Lipschitz constants. A smooth reduction then yields a lower bound for Goldstein stationarity, proving the joint minimax optimality of the dependence on $(d,δ,ε)$ under explicit high-dimensional and small-accuracy conditions. Crucially, our results allow algorithms to query arbitrary points in $\mathbb{R}^d$, adaptively select sample-function labels, reuse the same sampled function at any number of locations, and output points without spatial restrictions. Thus, unlike lower bounds based on bounded query regions or fresh evaluation noise, our guarantees apply to a fully adaptive, reusable-sample scalar oracle. We also establish a separate noiseless exact-value lower bound against randomized algorithms, and hence also against deterministic methods. Our proof combines a globally defined sequential nonconvex construction with an exact Gaussian scalar channel, multistage random-field estimates, and an antithetic finite-sample realization that preserves information hardness under adaptive reuse.
• Abstract（参考訳）: 最近の研究は、勾配推定器を通して一階の非凸最適化の保証をゼロ階のメソッドに転送し、通常$d$で係数線型化する。 \citet{kornowski2024} は非滑らかな非凸最適化に対して $\mathcal{O}(dδ^{-1}ε^{-3})$ Oracle complexity を取得し、その3つのパラメータへの依存が共役最適かどうかを問うた。 次元依存と$(δ,ε)$に対する一階依存は別々に避けられないことが知られているが、一致するゼロ階下界は開である。 制限のないフルスペース設定でこの質問に答える。 滑らかな確率的非凸最適化のために、スカラー・オークルの下限が$Ω\! \left(dL_0^2\min\{ΔH,L_0^2\}/ε^4\right)$ はスムーズで、大域的に低い人口目標とサンプルリプシッツ定数に有界な第二モーメントを仮定する。 滑らかな還元によりゴールドスタインの定常性は低くなり、明示的な高次元および小精度条件下での$(d,δ,ε)$への依存の最小値のジョイント極小性が証明される。 重要な点としては,アルゴリズムが$\mathbb{R}^d$の任意の点を問合せ,サンプル関数ラベルを適応的に選択し,任意の箇所で同じサンプル関数を再利用し,空間的制約なしに出力点を出力することができる。 したがって、有界なクエリ領域や新しい評価ノイズに基づく下位境界とは異なり、我々の保証は完全適応的で再利用可能なスカラーオラクルに適用できる。 また、ランダム化アルゴリズムに対するノイズレスの完全値下界を分離し、従って決定論的手法にも対処する。 我々の証明は、グローバルに定義された逐次的非凸構造と、正確なガウススカラーチャネル、多段階ランダムフィールド推定と、適応的再利用の下で情報の硬さを保存するアンチセティック有限サンプル実現とを組み合わせている。

関連論文リスト

• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)

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

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