High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.26547
curl -X POST /api/v1/records/arxiv/2605.26547/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.26547/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'