Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

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\Delta/\varepsilon^2$ is the iteration count of gradient descent from initial gap $\Delta$, and we prove that every randomized method needs $\Omega(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetilde\Omega(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 $\Omega(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.

Machine Learning (cs.LG)

arXiv:2610.27550 [cs.LG]

(or arXiv:2610.27550v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.27550 Focus to learn more arXiv-issued DOI via DataCite

ExactZO/CappedModel.lean

ExactZO/ChainBarrier.lean

ExactZO/ChainBounds.lean

ExactZO/ChainPrefix.lean

ExactZO/CoordinateAlgorithm.lean

ExactZO/DeterministicLower.lean

ExactZO/DimensionFloor.lean

ExactZO/FiniteDifference.lean

ExactZO/FinitePiece.lean

ExactZO/FrameGeometry.lean

ExactZO/GaussianDensity.lean

ExactZO/GaussianDirection.lean

ExactZO/GaussianPolar.lean

ExactZO/GaussianProjection.lean

ExactZO/GaussianScalar.lean

ExactZO/GaussianUpper.lean

ExactZO/HessianSegment.lean

ExactZO/HistorySpace.lean

ExactZO/Householder.lean

ExactZO/LineSearch.lean

ExactZO/LipschitzFTC.lean

ExactZO/Model.lean

ExactZO/Normalization.lean

ExactZO/Oracle.lean

ExactZO/QuantizedSigns.lean

ExactZO/RadialCompression.lean

ExactZO/RadialLift.lean

ExactZO/RadialSecond.lean

ExactZO/RandomEmbedding.lean

ExactZO/RandomModel.lean

ExactZO/S4Lower.lean

ExactZO/S4Scaling.lean

ExactZO/S4Selection.lean

ExactZO/STPCore.lean

ExactZO/STPDescent.lean

ExactZO/STPIID.lean

ExactZO/STPJoint.lean

ExactZO/STPProbability.lean

ExactZO/STPProcedure.lean

ExactZO/STPUpper.lean

ExactZO/ScalarChain.lean

ExactZO/ScalarGluing.lean

ExactZO/ScalingLemma.lean

ExactZO/SelectionEntropy.lean

ExactZO/SelectionGeometry.lean

ExactZO/SelectionHamming.lean

ExactZO/Simulation.lean

ExactZO/SphereFoundation.lean

ExactZO/SphereSign.lean

ExactZO/SphereSplit.lean

ExactZO/Stage.lean

ExactZO/StageGeometry.lean

ExactZO/SublevelBarrier.lean

ExactZO/SublevelFamily.lean

ExactZO/SublevelHessian.lean

ExactZO/SublevelMatrix.lean

ExactZO/SublevelPotential.lean

ExactZO/SublevelUpper.lean

ExactZO/SublevelWrapper.lean

ExactZO/SubspaceBudget.lean

ExactZO/SubspaceCost.lean

ExactZO/SubspaceEstimate.lean

ExactZO/SubspaceInvariant.lean

ExactZO/SubspaceOptimize.lean

ExactZO/SubspaceProcedure.lean

ExactZO/SubspaceResidual.lean

ExactZO/SubspaceTermination.lean

ExactZO/SubspaceUpper.lean

ExactZO/Transcript.lean

ExactZO/TranscriptCap.lean

ExactZO/Transfer.lean

ExactZO/ValueProcedure.lean

MainResults.lean

lake-manifest.json

(81 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.