Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence

Abstract

Many important machine learning applications amount to solving minimax optimization problems, and in many cases there is no access to the gradient information, but only the function values. In this paper, we focus on such a gradient-free setting, and consider the nonconvex-strongly-concave minimax stochastic optimization problem. In the literature, various zeroth-order (i.e., gradient-free) minimax methods have been proposed, but none of them achieve the potentially feasible computational complexity of $\mathcal{O}({\epsilon }^{-3})$ suggested by the stochastic nonconvex minimization theorem. In this paper, we adopt the variance reduction technique to design a novel zeroth-order variance reduced gradient descent ascent (ZO-VRGDA) algorithm. We show that the ZO-VRGDA algorithm achieves the best known query complexity of $\mathcal{O}(\kappa (d_1+d_2){\epsilon }^{-3})$, which outperforms all previous complexity bound by orders of magnitude, where $d_1$ and $d_2$ denote the dimensions of the optimization variables and $\kappa$ denotes the condition number. In particular, with a new analysis technique that we develop, our result does not rely on a diminishing or accuracy-dependent stepsize usually required in the existing methods. To our best knowledge, this is the first study of zeroth-order minimax optimization with variance reduction. Experimental results on the black-box distributional robust optimization problem demonstrates the advantageous performance of our new algorithm.

arXiv commentThis is an updated version to replace the previous arXiv post titled "Enhanced First and Zeroth Order Variance Reduced Algorithms for Min-Max Optimization" on 17 Jun, 2020

References in corpus (11)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Max-value Entropy Search for Efficient Bayesian Optimization
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Stochastic Variance Reduction Methods for Policy Evaluation
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Adversarially Robust Optimization with Gaussian Processes
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems

Cited by in corpus (2)

• Provably Faster Algorithms for Bilevel Optimization
• New First-Order Algorithms for Stochastic Variational Inequalities