Data-Driven Minimax Optimization with Expectation Constraints

Attention to data-driven optimization approaches, including the well-known stochastic gradient descent method, has grown significantly over recent decades, but data-driven constraints have rarely been studied because of the computational challenges of projections onto the feasible set defined by these hard constraints. In this paper, we focus on the nonsmooth convex-concave stochastic minimax regime and formulate the data-driven constraints as expectation constraints. The minimax expectation constrained problem subsumes a broad class of real-world applications, including data-driven robust optimization, optimization with misspecification, and area under the receiver operating characteristic curve (AUC) maximization with fairness constraints. We propose a class of efficient primal-dual algorithms to tackle the minimax expectation constrained problem and show that our algorithms converge at the optimal rate of $\mathcal{O}(1/\sqrt{N})$, where N is the number of iterations. We demonstrate the practical efficiency of our algorithms by conducting numerical experiments on large-scale real-world applications.

Funding: This work was supported by the National Key R&D Program of China [Grants 2020YFA0711900 and 2020YFA0711901]; the National Natural Science Foundation of China [Grants 12271107 and 62141407]; the Shanghai Science and Technology Program [21JC1400600]; and the National Science Foundation [Grant DMS-1953199].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0110.