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.

arXiv commentPublished in Journal of Machine Learning Research (JMLR)

References in corpus (25)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Simple Black-box Adversarial Attacks
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• 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
• Towards Gradient Free and Projection Free Stochastic Optimization
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Accelerated Stochastic Gradient-free and Projection-free Methods
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• 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