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 O ( 1 / 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.