Data-Driven Minimax Optimization with Expectation Constraints
This addresses a bottleneck in applying data-driven methods to real-world applications like two-player zero-sum games and robust optimization, though it is incremental in extending existing optimization techniques to constrained settings.
The paper tackles the problem of data-driven minimax optimization with expectation constraints, which are computationally challenging due to projection difficulties, and proposes primal-dual algorithms that achieve an optimal convergence rate of O(1/√N).
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 non-smooth 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 two-player zero-sum game and data-driven robust optimization. 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}(\frac{1}{\sqrt{N}})$. We demonstrate the practical efficiency of our algorithms by conducting numerical experiments on large-scale real-world applications.