Revisiting the Dimension Dependence of Zeroth-Order Optimization under Hessian Trace-Norm Conditions

Zeroth-order (ZO) optimization is broadly applied to high-dimensional problems where gradients are unavailable or costly, yet classical theory predicts rates that scale with the ambient dimension. Recent work replaces the dimension with a spectral quantity of the Hessian but assumes a fixed Hessian or a curvature envelope on a neighborhood or on the whole space. We show that, for the standard two-point Gaussian estimator, a pointwise Hessian trace-norm condition suffices: the sum of the absolute Hessian eigenvalues is bounded by a constant $H$ at every point. Under this condition, we prove convergence to first-order stationary points at rate $\mathcal{O}(H/T)$ for general non-convex objectives and, under the Polyak–ojasiewicz (PL) condition with constant $\mu$, linear convergence with contraction factor $1-\Theta (\mu /H)$. A “Twisted Valley” function whose principal curvature direction sweeps through every coordinate direction satisfies the condition with constants independent of the dimension, whereas the envelope conditions of prior analyses hold on it only with a trace that grows linearly in the dimension. Numerically, on this function and on the forward-only adaptation of a CNN and a Vision Transformer, the loss reached by the Gaussian estimator within a fixed query budget is insensitive to the dimension, while uniform coordinate probing degrades with it.