論文の概要: Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

• arxiv url: http://arxiv.org/abs/2610.27550v2
• Date: Wed, 21 Oct 2026 02:39:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.086383
• Title: Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace
• Title（参考訳）: 滑らかな非凸ゼロ階最適化のための下界:低曲率トレースによる決定論の価格
• Abstract要約: 有効ランク条件である低曲率トレースは、高次元タスクに対してゼロ階法がスケールする理由の一般的な説明である。 そのメソッドは、固定された$E$と$T$に対して$d$で対数的に成長し、対数係数によって$E$が一度あると、メソッドは、トレースなしで$(dT)$コールを必要とします。
• 参考スコア（独自算出の注目度）: 8.428362872515416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\varepsilon$-stationary points of $L$-smooth nonconvex functions on $\mathbb{R}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=LΔ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(d\min\{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min\{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism thus multiplies the cost by a factor of order $d/(E+\sqrt{ET})$ up to logarithmic factors, which grows linearly with $d$ for fixed $E$ and $T$; once $E$ exceeds $T$ by a logarithmic factor, deterministic methods need $Ω(dT)$ calls, as without any trace budget. Our lower bounds hold for $C^\infty$ functions with the matrix bound on all of $\mathbb{R}^d$, even when each call also returns gradient projections priced by rank.
• Abstract（参考訳）: 低曲率トレースは効果的なランク条件であり、なぜランダム化されたゼロ階法が言語モデルファインチューニングのような高次元のタスクにスケールするかの一般的な説明である。 決定論的手法は、同じ貯蓄を達成できるのか? 私たちは彼らができないことを示します。 我々は、$\varepsilon$-stationary points of $L$-smooth nonconvex function on $\mathbb{R}^d$を正確に関数値から発見し、Hessian が最大で $LE$ の固定行列で支配されていることを仮定する。 ここで$T=LΔ/\varepsilon^2$は初期ギャップからの勾配降下の反復数であり、すべてのランダム化メソッドが$Ω(ET)$呼び出しを必要とすることを証明しているので、このコストは定数まで最適である。 対照的に、すべての決定論的メソッドは$\widetildeΩ(d\min\{T,\sqrt{ET}\})$コールを必要とし、適応的部分空間探索は$O(d\min\{T,\sqrt{ET}\})$: 決定論的メソッドは発見方向当たり約$d$コールを支払う。 従って、決定論は、$d/(E+\sqrt{ET})$を対数因子に乗じると、固定された$E$と$T$に対して$d$で線形に成長し、もし$E$が対数因子によって$T$を超えると、決定論的なメソッドは、トレース予算なしで$Ω(dT)$呼び出しを必要とする。 我々の下限は$C^\infty$関数であり、行列は$\mathbb{R}^d$のすべてに有界である。

関連論文リスト

• Adaptivity via a Parallel Architecture for Stochastic Gradient Methods Adaptivity via a Parallel Architecture for Stochastic Gradient Methods Adaptivity via a Parallel Architecture for Stochastic Gradient Methods [17.47003987676889]
  適応性を向上するために静的勾配法を組み立てる並列フレームワークを開発する。 静的勾配法は、初期点 $x_0inmathbbRn$ と $Tin mathbbR+$ を入力として、反復数 $floorT$ を指定する。
  論文  参考訳（メタデータ） (2026-07-31T00:02:30Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification [19.32160757444549]
  非函数 $f(X)=phi(XXT)$ を$ntimes r$ factor matrix $X$ で最小化するために勾配降下を考える。 本稿では,勾配降下の収束率を線形に戻すための安価なプレコンディショナーを提案する。
  論文  参考訳（メタデータ） (2022-06-07T14:26:49Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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