Lazy Queries Can Reduce Variance in Zeroth-order Optimization. (arXiv:2206.07126v1 [cs.LG])

Web: http://arxiv.org/abs/2206.07126

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 …

arxiv lg optimization reduce variance