Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

MaRDI QIDQ6347329arXivFDO

Authors Feihu Huang, Shangqian Gao, Jian Pei, Heng Huang

Publication date 18 August 2020

Published in arXiv

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

arXiv classification

cs.CVcs.LGmath.OC

Abstract: 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 where only function values can be obtained. Moreover, we prove that our Acc-ZOM method achieves a lower query complexity of $ildeO(d^{3/4}epsilo{n}^{-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, our Acc-ZOM does not need large batches required in the existing zeroth-order stochastic algorithms. Meanwhile, we propose an accelerated zeroth-order momentum descent ascent (Acc-ZOMDA) method for black-box minimax optimization, where only function values can be obtained. Our Acc-ZOMDA obtains a low query complexity of $ildeO((d_1+d_2{)}^{3/4}kapp{a}_y^{4.5}epsilo{n}^{-3})$ without requiring large batches for finding an $epsilon$-stationary point, where $d_1$ and $d_2$ denote variable dimensions and $kapp{a}_y$ is condition number. Moreover, we propose an accelerated first-order momentum descent ascent (Acc-MDA) method for minimax optimization, whose explicit gradients are accessible. Our Acc-MDA achieves a low gradient complexity of $ildeO(kapp{a}_y^{4.5}epsilo{n}^{-3})$ without requiring large batches for finding an $epsilon$-stationary point. In particular, our Acc-MDA can obtain a lower gradient complexity of $ildeO(kapp{a}_y^{2.5}epsilo{n}^{-3})$ with a batch size $O(kapp{a}_y^4)$, which improves the best known result by a factor of $O(kapp{a}_y^{1/2})$. Extensive experimental results on black-box adversarial attack to deep neural networks and poisoning attack to logistic regression demonstrate efficiency of our algorithms.

This page was built for publication: Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6347329)