Accelerated Zeroth-Order Momentum Methods from Mini to Minimax Optimization
Feihu Huang, Shangqian Gao, Jian Pei, Heng Huang
In the paper, we propose a new accelerated zeroth-order momentum (Acc-ZOM)
method to solve the non-convex stochastic mini-optimization problems. We prove
that the Acc-ZOM method achieves a lower query complexity of
$O(d^{3/4}\epsilon^{-3})$ for finding an $\epsilon$-stationary point, which
improves the best known result by a factor of $O(d^{1/4})$ where $d$ denotes
the parameter dimension. The Acc-ZOM does not require any batches compared to
the large batches required in the existing zeroth-order stochastic algorithms.
Further, we extend the Acc-ZOM method to solve the non-convex stochastic
minimax-optimization problems and propose an accelerated zeroth-order momentum
descent ascent (Acc-ZOMDA) method. We prove that the Acc-ZOMDA method reaches
the best know query complexity of
$\tilde{O}(\kappa_y^3(d_1+d_2)^{3/2}\epsilon^{-3})$ for finding an
$\epsilon$-stationary point, where $d_1$ and $d_2$ denote dimensions of the
mini and max optimization parameters respectively and $\kappa_y$ is condition
number. In particular, our theoretical result does not rely on large batches
required in the existing methods. Moreover, we propose a momentum-based
accelerated framework for the minimax-optimization problems. At the same time,
we present an accelerated momentum descent ascent (Acc-MDA) method for solving
the white-box minimax problems, and prove that it achieves the best known
gradient complexity of $\tilde{O}(\kappa_y^3\epsilon^{-3})$ without large
batches. Extensive experimental results on the black-box adversarial attack to
deep neural networks (DNNs) and poisoning attack demonstrate the efficiency of
our algorithms.