Name
Title | ||
|---|---|---|
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals |
Abstract | ||
|---|---|---|
We show that many machine learning goals can be expressed as "rate constraints" on a model's predictions. We study the problem of training non-convex models subject to these rate constraints (or other non-convex or 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 a new "proxy-Lagrangian" formulation. This leads to an algorithm that, assuming access to an optimization oracle, 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 that shrinks the randomized solution down to a mixture of at most m + 1 deterministic solutions, given m constraints. This culminates in a procedure that can solve non-convex constrained optimization problems with possibly non-differentiable and non-convex constraints, and enjoys theoretical guarantees. We provide extensive experimental results covering a broad range of policy goals, including various fairness metrics, accuracy, coverage, recall, and churn. |
Year | Venue | Keywords |
|---|---|---|
2019 | JOURNAL OF MACHINE LEARNING RESEARCH | constrained optimization,non-convex,fairness,churn,swap regret,non-zero-sum game |
DocType | Volume | Issue |
Journal | 20 | 172 |
ISSN | Citations | PageRank |
1532-4435 | 2 | 0.36 |
References | Authors | |
0 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Cotter | 1 | 851 | 78.35 |
| Heinrich Jiang | 2 | 32 | 9.45 |
| Maya R. Gupta | 3 | 595 | 49.62 |
| Serena Wang | 4 | 4 | 4.09 |
| Taman Narayan | 5 | 2 | 0.36 |
| Seungil You | 6 | 39 | 6.79 |
| Karthik Sridharan | 7 | 1145 | 76.94 |