# Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals

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

## Key facts

- Cited by 103 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2018.

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

- [Bias Mitigation for Machine Learning Classifiers: A Comprehensive Survey](https://mlsanity.com/paper/2207.07068/) (2022)
- [Re-imagining Algorithmic Fairness in India and Beyond](https://mlsanity.com/paper/2101.09995/) (2021)
- [Are Gender-Neutral Queries Really Gender-Neutral? Mitigating Gender Bias in Image Search](https://mlsanity.com/paper/2109.05433/) (2021)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [Achieving Fairness at No Utility Cost via Data Reweighing with Influence](https://mlsanity.com/paper/2202.00787/) (2022)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Towards Trustworthy and Aligned Machine Learning: A Data-centric Survey with Causality Perspectives](https://mlsanity.com/paper/2307.16851/) (2023)
- [On the Reproducibility of Neural Network Predictions](https://mlsanity.com/paper/2102.03349/) (2021)
- [Understanding Instance-Level Impact of Fairness Constraints](https://mlsanity.com/paper/2206.15437/) (2022)
- [Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints](https://mlsanity.com/paper/2208.04425/) (2022)
- [FairGBM: Gradient Boosting with Fairness Constraints](https://mlsanity.com/paper/2209.07850/) (2022)
- [Bayes-Optimal Classifiers under Group Fairness](https://mlsanity.com/paper/2202.09724/) (2022)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [Re-weighting Based Group Fairness Regularization via Classwise Robust Optimization](https://mlsanity.com/paper/2303.00442/) (2023)
- [Mitigating Test-Time Bias for Fair Image Retrieval](https://mlsanity.com/paper/2305.19329/) (2023)
- [Unprocessing Seven Years of Algorithmic Fairness](https://mlsanity.com/paper/2306.07261/) (2023)
- [The KL-Divergence between a Graph Model and its Fair I-Projection as a Fairness Regularizer](https://mlsanity.com/paper/2103.01846/) (2021)
- [Churn Reduction via Distillation](https://mlsanity.com/paper/2106.02654/) (2021)
- [Weak Proxies are Sufficient and Preferable for Fairness with Missing Sensitive Attributes](https://mlsanity.com/paper/2210.03175/) (2022)
- [Net benefit, calibration, threshold selection, and training objectives for algorithmic fairness in healthcare](https://mlsanity.com/paper/2202.01906/) (2022)
- [Fair Bayes-Optimal Classifiers Under Predictive Parity](https://mlsanity.com/paper/2205.07182/) (2022)
- [Beyond Adult and COMPAS: Fairness in Multi-Class Prediction](https://mlsanity.com/paper/2206.07801/) (2022)
- [FRAPPE: A Group Fairness Framework for Post-Processing Everything](https://mlsanity.com/paper/2312.02592/) (2023)
- [Unified Group Fairness on Federated Learning](https://mlsanity.com/paper/2111.04986/) (2021)
- [Resilient Constrained Learning](https://mlsanity.com/paper/2306.02426/) (2023)
- [Predictive Churn with the Set of Good Models](https://mlsanity.com/paper/2402.07745/) (2024)
- [Fair Enough: Searching for Sufficient Measures of Fairness](https://mlsanity.com/paper/2110.13029/) (2021)
- [Omnipredictors for Constrained Optimization](https://mlsanity.com/paper/2209.07463/) (2022)
- [Post-hoc Bias Scoring Is Optimal For Fair Classification](https://mlsanity.com/paper/2310.05725/) (2023)

## Abstract (arXiv)

We show that many machine learning goals, such as improved fairness metrics, can be expressed as constraints on the model's predictions, which we call rate constraints. We study the problem of training non-convex models subject to these rate constraints (or any non-convex and non-differentiable constraints). In the non-convex setting, the standard approach of Lagrange multipliers may fail. Furthermore, if the constraints are non-differentiable, then one cannot optimize the Lagrangian with gradient-based methods. To solve these issues, we introduce the proxy-Lagrangian formulation. This new formulation leads to an algorithm that produces a stochastic classifier by playing a two-player non-zero-sum game solving for what we call a semi-coarse correlated equilibrium, which in turn corresponds to an approximately optimal and feasible solution to the constrained optimization problem. We then give a procedure which shrinks the randomized solution down to one that is a mixture of at most m+1 deterministic solutions, given m constraints. This culminates in algorithms that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints with theoretical guarantees. We provide extensive experimental results enforcing a wide range of policy goals including different fairness metrics, and other goals on accuracy, coverage, recall, and churn.