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

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 $\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, 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 $\tilde{O}((d_1+d_2{)}^{3/4}{\kappa }_y^{4.5}{\epsilon }^{-3})$ without requiring large batches for finding an $\epsilon$-stationary point, where $d_1$ and $d_2$ denote variable dimensions and ${\kappa }_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 $\tilde{O}({\kappa }_y^{4.5}{\epsilon }^{-3})$ without requiring large batches for finding an $\epsilon$-stationary point. In particular, our Acc-MDA can obtain a lower gradient complexity of $\tilde{O}({\kappa }_y^{2.5}{\epsilon }^{-3})$ with a batch size $O({\kappa }_y^4)$, which improves the best known result by a factor of $O({\kappa }_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.

Published in Journal of Machine Learning Research (JMLR)

References in corpus (15)

• Near-Optimal Algorithms for Minimax Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Accelerated Stochastic Gradient-free and Projection-free Methods
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Zeroth-order Deterministic Policy Gradient
• Momentum-Based Policy Gradient Methods

Cited by in corpus (6)

• Secure Bilevel Asynchronous Vertical Federated Learning with Backward Updating
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization
• Randomized Stochastic Gradient Descent Ascent