  Classifiers can be trained with data-dependent constraints to satisfy
fairness goals, reduce churn, achieve a targeted false positive rate, or other
policy goals. We study the generalization performance for such constrained
optimization problems, in terms of how well the constraints are satisfied at
evaluation time, given that they are satisfied at training time. To improve
generalization performance, we frame the problem as a two-player game where one
player optimizes the model parameters on a training dataset, and the other
player enforces the constraints on an independent validation dataset. We build
on recent work in two-player constrained optimization to show that if one uses
this two-dataset approach, then constraint generalization can be significantly
improved. As we illustrate experimentally, this approach works not only in
theory, but also in practice.
