Abstract:
Variance reduction techniques are designed to decrease the sampling variance, thereby accelerating convergence rates of first-order (FO) and zeroth-order (ZO) optimization methods. However, in composite optimization problems, ZO methods encounter an additional variance called the coordinate-wise variance, which stems from the random gradient estimation. To reduce this variance, prior works require estimating all partial derivatives, essentially approximating FO information. This approach demands function evaluations ( is the dimension size), which incurs substantial computational costs and is prohibitive in high-dimensional scenarios. This paper proposes the Zeroth-order Proximal Double Variance Reduction () method, which utilizes the averaging trick to reduce both sampling and coordinate-wise variances. Compared to prior methods, relies solely on random gradient estimates, calls the stochastic zeroth-order oracle (SZO) in expectation times per iteration, and achieves the optimal SZO query complexity in the strongly convex and smooth setting, where represents the condition number and is the desired accuracy. Empirical results validate 's linear convergence and demonstrate its superior performance over other related methods.
Chat is not available.