Zeroth-Order Algorithms for Smooth Saddle-Point Problems

Abstract

Saddle-point problems have recently gained increased attention from the machine learning community, mainly due to applications in training Generative Adversarial Networks using stochastic gradients. At the same time, in some applications only a zeroth-order oracle is available. In this paper, we propose several algorithms to solve stochastic smooth (strongly) convex-concave saddle-point problems using zeroth-order oracles and estimate their convergence rate and its dependence on the dimension $n$ of the variable. In particular, our analysis shows that in the case when the feasible set is a direct product of two simplices, our convergence rate for the stochastic term is only by a $\log n$ factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the minimization part and first-order oracle for the maximization part. Finally, we demonstrate the practical performance of our zeroth-order and 1/2th-order methods on practical problems.

References in corpus (6)

• Explaining and Harnessing Adversarial Examples
• Generative Adversarial Networks
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Robust Adversarial Reinforcement Learning
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Gradient-Free Methods for Saddle-Point Problem

Cited by in corpus (5)

• Randomized gradient-free methods in convex optimization
• Solving smooth min-min and min-max problems by mixed oracle algorithms
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Improved Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandit
• One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems