Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization. (arXiv:2008.08170v5 [math.OC] UPDATED)

In the paper, we propose a class of accelerated zeroth-order and first-order
momentum methods for both nonconvex mini-optimization and minimax-optimization.
Specifically, we propose a new accelerated zeroth-order momentum (Acc-ZOM)
method for black-box mini-optimization. Moreover, we prove that our Acc-ZOM
method achieves a lower query complexity of $\tilde{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 variable dimension. In
particular, the Acc-ZOM does not require large batches required in …

arxiv math minimax optimization