High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911718288916480 |
|---|---|
| author | Ye, Haishan |
| author_facet | Ye, Haishan |
| contents | 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 \(\varepsilon\)-suboptimal point with probability at least \(1-δ\) using \(\cO((dL/μ)\log(1/\varepsilon)+\log(1/δ))\) function queries under strong convexity, subject to an explicit finite-difference smoothing-radius condition. We also establish high-probability guarantees for smooth convex objectives under a level-set distance-to-solution radius condition and a pathwise smoothing-radius condition. For lower-bounded smooth non-convex objectives, the trajectory average is certified in stationarity with \(\cO(LΔ_0(d+\log(1/δ))/\varepsilon)\) function queries. The proofs combine lower-tail bounds for adaptive sums of Gaussian directional projections with upper-tail bounds for accumulated finite-difference smoothing errors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_26547 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions Ye, Haishan Optimization and Control 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 \(\varepsilon\)-suboptimal point with probability at least \(1-δ\) using \(\cO((dL/μ)\log(1/\varepsilon)+\log(1/δ))\) function queries under strong convexity, subject to an explicit finite-difference smoothing-radius condition. We also establish high-probability guarantees for smooth convex objectives under a level-set distance-to-solution radius condition and a pathwise smoothing-radius condition. For lower-bounded smooth non-convex objectives, the trajectory average is certified in stationarity with \(\cO(LΔ_0(d+\log(1/δ))/\varepsilon)\) function queries. The proofs combine lower-tail bounds for adaptive sums of Gaussian directional projections with upper-tail bounds for accumulated finite-difference smoothing errors. |
| title | High-Probability Guarantees for Random Zeroth-Order Gradient Descent on Smooth Functions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.26547 |