# Two-Player Games for Efficient Non-Convex Constrained Optimization

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

## Key facts

- Cited by 55 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2018.

## Built on by (most cited first, 30 of 55)

- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Data Collection and Quality Challenges in Deep Learning: A Data-Centric AI Perspective](https://mlsanity.com/paper/2112.06409/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [User-oriented Fairness in Recommendation](https://mlsanity.com/paper/2104.10671/) (2021)
- [Characterizing Fairness Over the Set of Good Models Under Selective Labels](https://mlsanity.com/paper/2101.00352/) (2021)
- [Sample Selection for Fair and Robust Training](https://mlsanity.com/paper/2110.14222/) (2021)
- [Personalized Counterfactual Fairness in Recommendation](https://mlsanity.com/paper/2105.09829/) (2021)
- [Evaluating Debiasing Techniques for Intersectional Biases](https://mlsanity.com/paper/2109.10441/) (2021)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [Understanding Instance-Level Impact of Fairness Constraints](https://mlsanity.com/paper/2206.15437/) (2022)
- [Promoting Fairness through Hyperparameter Optimization](https://mlsanity.com/paper/2103.12715/) (2021)
- [Churn Reduction via Distillation](https://mlsanity.com/paper/2106.02654/) (2021)
- [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023)
- [Improving Fair Training under Correlation Shifts](https://mlsanity.com/paper/2302.02323/) (2023)
- [Don't Throw it Away! The Utility of Unlabeled Data in Fair Decision Making](https://mlsanity.com/paper/2205.04790/) (2022)
- [FORML: Learning to Reweight Data for Fairness](https://mlsanity.com/paper/2202.01719/) (2022)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)
- [PDPGD: Primal-Dual Proximal Gradient Descent Adversarial Attack](https://mlsanity.com/paper/2106.01538/) (2021)
- [FairGrad: Fairness Aware Gradient Descent](https://mlsanity.com/paper/2206.10923/) (2022)
- [Perceptually Constrained Adversarial Attacks](https://mlsanity.com/paper/2102.07140/) (2021)
- [Fairness Evaluation in Text Classification: Machine Learning Practitioner Perspectives of Individual and Group Fairness](https://mlsanity.com/paper/2303.00673/) (2023)
- [Addressing Fairness, Bias and Class Imbalance in Machine Learning: the FBI-loss](https://mlsanity.com/paper/2105.06345/) (2021)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Learning Distributionally Robust Models at Scale via Composite Optimization](https://mlsanity.com/paper/2203.09607/) (2022)
- [Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment](https://mlsanity.com/paper/2307.14668/) (2023)
- [Lexicographically Fair Learning: Algorithms and Generalization](https://mlsanity.com/paper/2102.08454/) (2021)
- [Breaking Fair Binary Classification with Optimal Flipping Attacks](https://mlsanity.com/paper/2204.05472/) (2022)
- [Towards Fairness-Aware Multi-Objective Optimization](https://mlsanity.com/paper/2207.12138/) (2022)
- [Aequitas Flow: Streamlining Fair ML Experimentation](https://mlsanity.com/paper/2405.05809/) (2024)
- [A Pre-processing Method for Fairness in Ranking](https://mlsanity.com/paper/2110.15503/) (2021)

## Abstract (arXiv)

In recent years, constrained optimization has become increasingly relevant to the machine learning community, with applications including Neyman-Pearson classification, robust optimization, and fair machine learning. A natural approach to constrained optimization is to optimize the Lagrangian, but this is not guaranteed to work in the non-convex setting, and, if using a first-order method, cannot cope with non-differentiable constraints (e.g. constraints on rates or proportions). The Lagrangian can be interpreted as a two-player game played between a player who seeks to optimize over the model parameters, and a player who wishes to maximize over the Lagrange multipliers. We propose a non-zero-sum variant of the Lagrangian formulation that can cope with non-differentiable--even discontinuous--constraints, which we call the "proxy-Lagrangian". The first player minimizes external regret in terms of easy-to-optimize "proxy constraints", while the second player enforces the original constraints by minimizing swap regret. For this new formulation, as for the Lagrangian in the non-convex setting, the result is a stochastic classifier. For both the proxy-Lagrangian and Lagrangian formulations, however, we prove that this classifier, instead of having unbounded size, can be taken to be a distribution over no more than m+1 models (where m is the number of constraints). This is a significant improvement in practical terms.