Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities

Abstract

In this paper, we study zeroth-order algorithms for minimax optimization problems that are nonconvex in one variable and strongly-concave in the other variable. Such minimax optimization problems have attracted significant attention lately due to their applications in modern machine learning tasks. We first consider a deterministic version of the problem. We design and analyze the Zeroth-Order Gradient Descent Ascent (\texttt{ZO-GDA}) algorithm, and provide improved results compared to existing works, in terms of oracle complexity. We also propose the Zeroth-Order Gradient Descent Multi-Step Ascent (\texttt{ZO-GDMSA}) algorithm that significantly improves the oracle complexity of \texttt{ZO-GDA}. We then consider stochastic versions of \texttt{ZO-GDA} and \texttt{ZO-GDMSA}, to handle stochastic nonconvex minimax problems. For this case, we provide oracle complexity results under two assumptions on the stochastic gradient: (i) the uniformly bounded variance assumption, which is common in traditional stochastic optimization, and (ii) the Strong Growth Condition (SGC), which has been known to be satisfied by modern over-parametrized machine learning models. We establish that under the SGC assumption, the complexities of the stochastic algorithms match that of deterministic algorithms. Numerical experiments are presented to support our theoretical results.

arXiv commentTo appear in the Journal of Global Optimization

References in corpus (28)

• Practical Bayesian Optimization of Machine Learning Algorithms
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Towards Deep Learning Models Resistant to Adversarial Attacks
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Delving into Transferable Adversarial Examples and Black-box Attacks
• Evolutionary Algorithms for Reinforcement Learning
• Max-value Entropy Search for Efficient Bayesian Optimization
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• A Variational Inequality Perspective on Generative Adversarial Networks
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Optimization, Learning, and Games with Predictable Sequences
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Fast Convergence of Regularized Learning in Games
• Connecting Generative Adversarial Networks and Actor-Critic Methods
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Adversarially Robust Optimization with Gaussian Processes
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Efficient Algorithms for Smooth Minimax Optimization
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization
• Finding Mixed Nash Equilibria of Generative Adversarial Networks
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games

Cited by in corpus (9)

• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Model-Free Learning of Optimal Ergodic Policies in Wireless Systems
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Solving smooth min-min and min-max problems by mixed oracle algorithms
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• New First-Order Algorithms for Stochastic Variational Inequalities
• Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization
• Direct-Search for a Class of Stochastic Min-Max Problems