Stochastic minimax problems with decision-dependent distributions (SMDD) have emerged as a crucial framework for modeling complex systems where data distributions drift in response to decision variables. Most existing methods for SMDD rely on an explicit functional relationship between the decision variables and the probability distribution. In this paper, we propose two sample-based zeroth-order algorithms, namely Single-Directional Zeroth-Order Stochastic Gradient Descent Ascent (SD-ZO-SGDA) and Multi-Directional Zeroth-Order Stochastic Gradient Descent Ascent (MD-ZO-SGDA), to find an \(\epsilon\)-stationary point of the nonconvex-strongly concave SMDD. Under accuracy-independent constant step-sizes, SD-ZO-SGDA achieves an iteration complexity of \(\mathcal{O}({d}^3\kappa^3\epsilon^{-2})\) with a batch size of \(\mathcal{O}(\epsilon^{-4}\kappa^2)\), where \({d}\) denotes the total variable dimension and \(\kappa\) is the condition number. Under accuracy-dependent step-sizes, SD-ZO-SGDA attains an iteration complexity of \(\mathcal{O}({d}^3\kappa^3\epsilon^{-5})\) with a relaxed batch size of \(\mathcal{O}(\epsilon^{-2}\kappa^2)\). On the other hand, the multi-directional variant MD-ZO-SGDA further reduces gradient estimation variance, which improves the complexity dependence on the condition number \(\kappa\) and dimension \(d\) under both step-size settings. Numerical experiments on a synthetic problem and a real-world competitive EV charging application demonstrate the effectiveness of our algorithms.
Zeroth-Order Methods for Nonconvex-Strongly Concave Stochastic Minimax Problems with Decision-Dependent Distributions
\(\)