Abstract
Black-box stochastic optimization involves sampling in both the solution and data spaces. Traditional variance reduction methods mainly designed for reducing the data sampling noise may suffer from slow convergence if the noise in the solution space is poorly handled. In this paper, we present a novel zeroth-order optimization method, termed Population-based Variance-Reduced Evolution (PVRE), which simultaneously mitigates noise in both the solution and data spaces. PVRE uses a normalized-momentum mechanism to guide the search and reduce the noise due to data sampling. A population-based gradient estimation scheme, a well-established evolutionary optimization technique, is incorporated to further reduce noise in the solution space. We show that PVRE exhibits the convergence properties of theory-backed optimization algorithms and the adaptability of evolutionary algorithms. In particular, PVRE achieves the best-known function evaluation complexity of [Formula: see text] for finding an ε-accurate first-order optimal solution, up to a logarithmic factor, with any initial step-size. We assess the performance of PVRE through numerical experiments on benchmark problems as well as a real-world task involving adversarial attacks against neural image classifiers.