Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to
  Decision-Dependent Risk Minimization
  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.
