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 (22)

• Explaining and Harnessing Adversarial Examples
• Generative Adversarial Networks
• Ensemble Adversarial Training: Attacks and Defenses
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Robust Adversarial Reinforcement Learning
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• A Variational Inequality Perspective on Generative Adversarial Networks
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Structured Evolution with Compact Architectures for Scalable Policy Optimization
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• On the convergence of single-call stochastic extra-gradient methods
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Gradient-Free Methods for Saddle-Point Problem
• Gradient-free prox-methods with inexact oracle for stochastic convex optimization problems on a simplex
• An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
• Optimal rates for zero-order convex optimization: the power of two function evaluations
• Solving variational inequalities with Stochastic Mirror-Prox algorithm
• A randomized gradient-free attack on ReLU networks

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