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

Abstract

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