High-Probability Last-Iterate Guarantees for Two-Point Gaussian Zeroth-Order Stochastic Gradient Descent

We establish a direct high-probability last-iterate guarantee for the standard same-sample two-point Gaussian zeroth-order stochastic-gradient method applied to smooth, strongly convex stochastic optimization. At each iteration, the method draws a fresh Gaussian direction, evaluates the objective at two symmetric perturbations using the same stochastic sample, and takes a norm-normalized stochastic-approximation step. Assuming unbiased stochastic gradients and a conditional exponential-moment bound on the squared norm of the stochastic-gradient noise, we prove that, whenever (d\ge16\log(6T/δ)), [ f(\bx_T)-f(\bx^*) = \widetilde{\mathcal O}!\left(\frac{d}{T}\right) ] with probability at least (1-δ), up to fixed problem parameters and logarithmic factors. The confidence dependence is therefore logarithmic rather than polynomial in (1/δ). The analysis is direct: it neither invokes Markov's inequality to convert an expectation bound nor truncates the noise. We are not aware of a prior direct high-probability last-iterate result at this zeroth-order scale for the same-sample Gaussian recursion under conditional sub-Gaussian stochastic-gradient noise. The proof combines a uniform weighted scan for Gaussian angles with an angle-enlarged product-martingale boundary that controls the signed suffix-product term arising from the unrolled stochastic recursion.

Source: arXiv:2606.20446v1 - http://arxiv.org/abs/2606.20446v1 PDF: https://arxiv.org/pdf/2606.20446v1 Original Link: http://arxiv.org/abs/2606.20446v1