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

By Andrew Cotter, Heinrich Jiang, Serena Wang, Taman Narayan, Maya R. Gupta, Seungil You, Karthik Sridharan. 2018

191 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Optimization & Training

Citations in the corpus

Controlled Sparsity via Constrained Optimization or: How I Learned to Stop Tuning Penalties and Love Constraints (2022, background): “[5] propose an algorithm for non-convex constrained problems that returns an approximately optimal and feasible solution, consisting of a pair of mixed strategies (with support size of at most m + 1 for a problem with m constraints).”
Fair Resource Allocation in Federated Learning (2019, background): “[6] uses a notion of ‘minimum accuracy’ as one special case of ‘rate constraints’, which is conceptually similar to our goal.”
The Ideal Continual Learner: An Agent That Never Forgets (2023, background): “Constrained learning naturally arises when learning under certain requirements, e.g., robustness (Zhang et al., 2019; Robey et al., 2021), safety (Paternain et al., 2019), or fairness (Cotter et al., 2019).”
Identifying and Correcting Label Bias in Machine Learning (2019, methodology): “In the non-convex case, there is work which frames the constrained optimization problem as a two-player game (Kearns et al., 2017; Agar-wal et al., 2018; Cotter et al., 2018b) .”
A General Approach to Fairness with Optimal Transport (2020, background): “…et al. 2012; Feldman et al. 2015; Goh et al. 2016; Chouldechova 2017; Corbett-Davies et al. 2017; Gajane and Pechenizkiy 2017; Kusner et al. 2017; Cotter et al. 2018; Mitchell, Potash, and Barocas 2018; Verma and Rubin 2018; Zhang and Bareinboim 2018; Chi-appa and Isaac 2019; Narasimhan et al.…”