Hessian-Dependent Sample Complexity in Zeroth-Order Stochastic Optimization: Suboptimality of Convex-Support Sampling and Optimal Sample Complexity

Zeroth-order stochastic optimization is a fundamental formulation that arises in real-world design problems where gradients are inaccessible. A central challenge in this pursuit is to design gradient estimators and optimization algorithms under noisy, function-only feedback that exploit local Hessian geometry to achieve optimal sample efficiency. We introduce the Spectrally Grouped Estimator (SGE), a novel gradient estimator that samples over a non-convex union of sphere sections, and utilize it to build an algorithm that achieves order-wise improved Hessian-dependent simple regrets over second-order smooth, strongly convex functions compared to conventional convex-sets sampling baseline methods. We complement these results with the first tight analyses of the baseline schemes, revealing a shared performance bottleneck and thus emphasizing the necessity of non-convex sampling for optimality. We further establish matching converse bounds that tightly characterize the optimal sample complexities within general subclasses of functions sharing the same Hessian at the global minimum, thereby proving the universal optimality of SGE with respect to the Hessian-dependent rates. This fully resolves an open conjecture from the preliminary version of this work. This fully resolves an open conjecture in the preliminary version of this work.