Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML

Abstract

In this paper, we study the problem of constrained robust (min-max) optimization ina black-box setting, where the desired optimizer cannot access the gradients of the objective function but may query its values. We present a principled optimization framework, integrating a zeroth-order (ZO) gradient estimator with an alternating projected stochastic gradient descent-ascent method, where the former only requires a small number of function queries and the later needs just one-step descent/ascent update. We show that the proposed framework, referred to as ZO-Min-Max, has a sub-linear convergence rate under mild conditions and scales gracefully with problem size. From an application side, we explore a promising connection between black-box min-max optimization and black-box evasion and poisoning attacks in adversarial machine learning (ML). Our empirical evaluations on these use cases demonstrate the effectiveness of our approach and its scalability to dimensions that prohibit using recent black-box solvers.

ICML 2020

References in corpus (23)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Delving into Transferable Adversarial Examples and Black-box Attacks
• Spectral Signatures in Backdoor Attacks
• Black-box Adversarial Attacks with Limited Queries and Information
• Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• 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
• NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Adversarial Deep Learning for Robust Detection of Binary Encoded Malware
• FLAML: A Fast and Lightweight AutoML Library
• Towards Distributed Coevolutionary GANs
• On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization
• Efficiently avoiding saddle points with zero order methods: No gradients required
• How can AI Automate End-to-End Data Science?
• Approximating Nash Equilibria for Black-Box Games: A Bayesian Optimization Approach
• CAAD 2018: Iterative Ensemble Adversarial Attack

Cited by in corpus (9)

• Just How Toxic is Data Poisoning? A Unified Benchmark for Backdoor and Data Poisoning Attacks
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• 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