Small errors in random zeroth-order optimization are imaginary

Abstract

Most zeroth-order optimization algorithms mimic a first-order algorithm but replace the gradient of the objective function with some gradient estimator that can be computed from a small number of function evaluations. This estimator is constructed randomly, and its expectation matches the gradient of a smooth approximation of the objective function whose quality improves as the underlying smoothing parameter $\delta$ is reduced. Gradient estimators requiring a smaller number of function evaluations are preferable from a computational point of view. While estimators based on a single function evaluation can be obtained by use of the divergence theorem from vector calculus, their variance explodes as $\delta$ tends to $0$. Estimators based on multiple function evaluations, on the other hand, suffer from numerical cancellation when $\delta$ tends to $0$. To combat both effects simultaneously, we extend the objective function to the complex domain and construct a gradient estimator that evaluates the objective at a complex point whose coordinates have small imaginary parts of the order $\delta$. As this estimator requires only one function evaluation, it is immune to cancellation. In addition, its variance remains bounded as $\delta$ tends to $0$. We prove that zeroth-order algorithms that use our estimator offer the same theoretical convergence guarantees as the state-of-the-art methods. Numerical experiments suggest, however, that they often converge faster in practice.

Final version (33 pages), to appear in the SIAM Journal on Optimization

References in corpus (14)

• Derivative-free optimization methods
• Artificial Intelligence and Statistics
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Derivative-Free Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
• On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
• Online convex optimization in the bandit setting: gradient descent without a gradient
• A One-bit, Comparison-Based Gradient Estimator