Adaptively Incorporating Directional Hints into Zeroth-Order Optimization
Abstract
We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order O(1/T) rate and the zeroth-order O(d/T) rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.
Related
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Training with ML-labeled Data via Stochastic First- and Zeroth-Order Optimization
- ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
BibTeX
@misc{ryabchenko2026adaptively,
title = {{Adaptively Incorporating Directional Hints into Zeroth-Order Optimization}},
author = {Alexander Ryabchenko and Jian Qian and Wenlong Mou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08277},
eprint = {2609.08277},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08277},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptively Incorporating Directional Hints into Zeroth-Order Optimization
AU - Alexander Ryabchenko
AU - Jian Qian
AU - Wenlong Mou
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08277
UR - https://arxiv.org/abs/2609.08277
AB - We study zeroth-order optimization of non-convex functions with the aid of directional hints, which are cheap but potentially inaccurate approximations of the true gradient direction, given by linear subspaces at each iteration. To leverage these hints adaptively while maintaining robustness to their quality, we introduce Control-Variate Zeroth-Order Descent (CV-ZOD), a new framework that refines the classical zeroth-order gradient estimator with a control variate that can be set based on the directional hints. We first show that the oracle algorithm that optimally sets the reference vector and step size at each iteration achieves a convergence rate that interpolates between the first-order O(1/T) rate and the zeroth-order O(d/T) rate, depending on the quality of the hints along the trajectory. We then develop a practical variant of CV-ZOD that achieves the same oracle guarantee up to logarithmic factors, without any prior knowledge of the hint quality. We validate the method empirically on simulation-based scientific optimization tasks, demonstrating sustained progress on non-convex landscapes where zeroth-order descent is slower and existing guided methods stall as guidance deteriorates.
ER -