{"id":"arxiv/2604.23613","url":"https://arxiv.org/abs/2604.23613","tags":["math.OC"],"score":0,"title":"High-Probability Guarantees for Random Zeroth-Order (Stochastic) Gradient Descent","domain":"math.OC","source":"arxiv","authors":["Haishan Ye"],"reviews":0,"subject":"math.OC","summary":"Zeroth-order optimization aims to minimize an objective function using only function evaluations, and is therefore fundamental in black-box optimization, hyperparameter tuning, bandit learning, and adversarial machine learning. While classical zeroth-order methods are well understood in expectation, much less is known about their high-probability behavior, especially for smooth and strongly convex objectives. In this paper, we establish high-probability convergence guarantees for random zeroth-order gradient descent in both deterministic and stochastic settings. For deterministic $L$-smooth…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-26","reactions":{}}