Zeroth-order optimization improves using adaptive directional hints
Adaptively Incorporating Directional Hints into Zeroth-Order Optimization
Machine Learning
Summary
Optimizing complicated functions without direct information about their slope is hard and slow. The authors study a way to speed this up by using approximate directional hints that suggest good directions to move. They develop a method called CV-ZOD that combines these hints with existing techniques, adjusting how much it trusts the hints based on their quality. Their approach works well in practice, maintaining steady progress even when the hints get worse, unlike previous methods that struggle when guidance is inaccurate.
What this means in practice
- •For simulation software developers: Improve optimization speed in scientific simulations lacking explicit gradients by adapting to directional hints for better search directions.
- •For automation engineers: Enhance black-box tuning of complex system parameters when gradient information is unavailable or unreliable by integrating adaptive directional feedback.
Authors
Alexander Ryabchenko, Jian Qian, Wenlong Mou
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.