# Data-Driven Minimax Optimization with Expectation Constraints

arXiv: https://arxiv.org/abs/2202.07868 · HTML: https://mlsanity.com/paper/2202.07868/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 66 references that are in the map.
- First posted on arXiv 16 Feb 2022.

## Builds on (most cited first, 18 of 18)

- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Challenges of Big Data Analysis](https://mlsanity.com/paper/1308.1479/) (2013)
- [Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/1908.02734/) (2019)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Efficient Generation of Structured Objects with Constrained Adversarial Networks](https://mlsanity.com/paper/2007.13197/) (2020)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Constrained Generative Adversarial Networks for Interactive Image Generation](https://mlsanity.com/paper/1904.02526/) (2019)
- [Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems](https://mlsanity.com/paper/1311.1098/) (2013)
- [On the solution of stochastic optimization and variational problems in imperfect information regimes](https://mlsanity.com/paper/1402.1457/) (2014)
- [Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints](https://mlsanity.com/paper/1705.00822/) (2017)
- [A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints](https://mlsanity.com/paper/1908.03077/) (2019)
- [Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints](https://mlsanity.com/paper/2007.00153/) (2020)
- [Stochastic Approximation Proximal Method of Multipliers for Convex Stochastic Programming](https://mlsanity.com/paper/1907.12226/) (2019)
- [Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso](https://mlsanity.com/paper/1711.04734/) (2017)

## Built on by (most cited first, 5 of 5)

- [Stochastic Methods for AUC Optimization subject to AUC-based Fairness Constraints](https://mlsanity.com/paper/2212.12603/) (2022)
- [Stochastic Compositional Optimization with Compositional Constraints](https://mlsanity.com/paper/2209.04086/) (2022)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)
- [First-order methods for Stochastic Variational Inequality problems with Function Constraints](https://mlsanity.com/paper/2304.04778/) (2023)
- [Simultaneous Learning and Optimization via Misspecified Saddle Point Problems](https://mlsanity.com/paper/2510.05241/) (2025)

## Abstract (arXiv)

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 O(frac1√N). We demonstrate the practical efficiency of our algorithms by conducting numerical experiments on large-scale real-world applications.