  We present a general framework for solving a large class of learning problems
with non-linear functions of classification rates. This includes problems where
one wishes to optimize a non-decomposable performance metric such as the
F-measure or G-mean, and constrained training problems where the classifier
needs to satisfy non-linear rate constraints such as predictive parity
fairness, distribution divergences or churn ratios. We extend previous
two-player game approaches for constrained optimization to a game between three
players to decouple the classifier rates from the non-linear objective, and
seek to find an equilibrium of the game. Our approach generalizes many existing
algorithms, and makes possible new algorithms with more flexibility and tighter
handling of non-linear rate constraints. We provide convergence guarantees for
convex functions of rates, and show how our methodology can be extended to
handle sums of ratios of rates. Experiments on different fairness tasks confirm
the efficacy of our approach.
