Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization

Abstract

Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. We propose a random reshuffling-based gradient free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. We further specialize the algorithm to solve distributionally robust, decision-dependent learning problems, where gradient information is not readily available. Through illustrative simulations, we observe that our proposed approach learns models that are simultaneously robust against adversarial distribution shifts and strategic decisions from the data sources, and outperforms existing methods from the strategic classification literature.

arXiv comment38 pages, 6 figures

References in corpus (16)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Distributionally Robust Logistic Regression
• 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
• Why Random Reshuffling Beats Stochastic Gradient Descent
• Does Distributionally Robust Supervised Learning Give Robust Classifiers?
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networks
• Bandit learning in concave $N$-person games
• Optimal Decision Making Under Strategic Behavior
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Outside the Echo Chamber: Optimizing the Performative Risk
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Performative Prediction in a Stateful World
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Learning to Play Sequential Games versus Unknown Opponents