{"id":"arxiv/2605.26547","url":"https://arxiv.org/abs/2605.26547","tags":["math.OC"],"score":0,"title":"High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions","domain":"math.OC","source":"arxiv","authors":["Haishan Ye"],"reviews":0,"subject":"math.OC","summary":"Randomized zeroth-order methods are classically analyzed in expectation, but a black-box Markov conversion can give misleading high-probability guarantees, in particular by forcing the finite-difference smoothing radius to shrink with the confidence parameter. This paper gives a direct finite-horizon high-probability analysis of a two-query Gaussian finite-difference method for deterministic objectives with Lipschitz gradients. The method uses the classical two-point estimator together with the normalized stepsize \\(η_t=1/(4L\\norm{\\bu_t}^2)\\). We prove that it finds an…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-26","reactions":{}}