Lazy Queries Can Reduce Variance in Zeroth-order Optimization
A major challenge of applying zeroth-order (ZO) methods is the high query
complexity, especially when queries are costly. We propose a novel gradient
estimation technique for ZO methods based on adaptive lazy queries that we term
as LAZO. Different from the classic one-point or two-point gradient estimation
methods, LAZO develops two alternative ways to check the usefulness of old
queries from previous iterations, and then adaptively reuses them to construct
the low-variance gradient estimates. We rigorously establish that through
judiciously reusing the old queries, LAZO can reduce the variance of stochastic
gradient estimates so that it not only saves queries per iteration but also
achieves the regret bound for the symmetric two-point method. We evaluate the
numerical performance of LAZO, and demonstrate the low-variance property and
the performance gain of LAZO in both regret and query complexity relative to
several existing ZO methods. The idea of LAZO is general, and can be applied to
other variants of ZO methods.