Optimizing Generalized Rate Metrics with Three Players

Harikrishna Narasimhan, Andrew Cotter, Maya R. Gupta

The Challenge of Non-Linear Metrics

Most machine learning models are trained to minimize "decomposable" losses, where the total error is simply the sum of individual errors. However, real-world performance is often measured by non-linear rate metrics. For example, imbalanced classification tasks frequently rely on the F-measure or G-mean, where simple accuracy is misleading. Similarly, fairness goals—such as "predictive parity" or "distributional divergence"—ensure a model treats different demographic groups equitably, while "churn" measures how much a new model changes predictions compared to an old one.

Examples of non-linear rate metrics including G-mean, F-measure, and fairness constraints.

Optimizing these metrics is notoriously difficult because they are non-linear and non-continuous. Previous solutions typically relied on either surrogates or oracles. Surrogates can be inaccurate and "over-constrain" the model, leading to poor performance. Oracles, on the other hand, assume you already have a near-perfect solver—a practical "chicken-and-egg" problem.

A Novel Three-Player Game Framework

To overcome these limitations, this paper frames the optimization process as a three-player game. In a standard constrained optimization game, there are two players: one minimizing the loss (model parameters $\theta$) and one maximizing the penalty for breaking constraints (Lagrange multipliers $\lambda$).

The authors introduce a third player ($\xi$) who manages "slack variables." Here is how the trio interacts:

  1. The $\theta$-player (Model): Tries to minimize a surrogate version of the Lagrangian. It uses differentiable approximations (like hinge loss) to make standard gradient descent possible.
  2. The $\lambda$-player (Constraints): Acts as the "rule enforcer," increasing penalties when constraints are violated. Crucially, this player uses the original, non-linear rates, not the surrogates.
  3. The $\xi$-player (Slack): This player handles the non-linearity of the objective function, effectively "decoupling" it from the raw classification rates.
Pseudocode for the Oracle-based (Algorithm 1) and Surrogate-based (Algorithm 2) Optimizers.

By decoupling the non-linear mapping from the model parameters, the model only has to optimize a weighted sum of rates, which is significantly easier. The authors prove that this setup eventually reaches a Coarse-Correlated Equilibrium, corresponding to a near-optimal solution for the original problem.

Key Insights

  • Surrogate Hybridization: The framework uses surrogates for the model updates while using the actual rates for the constraint updates. This prevents the "over-constraining" problem where a model becomes uselessly conservative because its surrogate constraints were too strict.
  • Handling Restricted Domains: Some metrics, like KL-divergence, are only defined for specific input ranges. Previous methods often failed here because surrogates could push values out of bounds. The three-player game naturally keeps variables within the valid domain.

Experimental Validation

The framework was evaluated on five standard datasets frequently used in fairness and classification research: COMPAS, Communities & Crime, Law School, Adult, and Wiki Toxicity.

  • Fairness without Oracles: On KL-divergence fairness tasks, the surrogate-based approach (Algorithm 2) performed as well as state-of-the-art methods that require an expensive and often unrealistic optimization oracle.
  • Constraint Satisfaction: In F-measure parity experiments, the three-player approach significantly reduced constraint violations compared to unconstrained baselines, often achieving near-zero violation on the training set.
  • Theoretical Robustness: The authors resolved an open question from previous work regarding the convergence of Lagrangian optimizers in non-zero-sum games, providing a solid theoretical foundation for their algorithm.

Limitations and Future Directions

While powerful, the approach has a few limitations. The equilibrium solution often results in a "stochastic classifier"—essentially a probability distribution over several different models. Deploying a model that requires flipping a coin to make a prediction can be challenging in some production environments.

Additionally, while the convex case has strong guarantees, the "sum-of-ratios" approach (Algorithm 3) remains a heuristic without the same rigorous convergence proofs. Finally, the convergence rate for the surrogate-based constrained case is $O(T^{-1/4})$, which is slower than the $O(T^{-1/2})$ rate typical of simpler gradient descent problems, meaning it may require more iterations to find a stable equilibrium.

Summary updated

Abstract

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 an approach with 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.
BibTeX
@inproceedings{narasimhan2019optimizing,
  author = {Harikrishna Narasimhan and Andrew Cotter and Maya R. Gupta},
  title = {{Optimizing Generalized Rate Metrics with Three Players}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=NiUKdYs2v8},
}
Figure