Optimizing Generalized Rate Metrics through Game Equilibrium

Harikrishna Narasimhan, Andrew Cotter, Maya R. Gupta

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 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.

Introduction

In standard machine learning, optimization typically focuses on "decomposable" metrics like accuracy or log-loss, where the total error is a simple sum of errors on individual data points. However, many real-world objectives are non-linear functions of classification rates. These "Generalized Rate Metrics" (GRMs) include the F-measure and G-mean for imbalanced data, as well as fairness constraints like predictive parity and distribution divergences.

Optimizing GRMs is challenging because they are often non-continuous and non-linear. Previous approaches relied on smooth approximations (surrogates) or idealized black-box optimizers (oracles). Surrogates can be unstable; for example, a surrogate for a logarithm might evaluate to a negative number, causing the optimization to fail. Oracles, meanwhile, are rarely available in practical settings.

Table of Generalized Rate Metrics and their definitions, illustrating the non-linear nature of common performance and fairness objectives.

Methodology: The Three-Player Game

The authors propose a novel three-player game framework to find a stable equilibrium for these complex objectives. The framework introduces a third player to manage slack variables, effectively decoupling the classification rates from the non-linear components of the objective function. The three players are:

  1. The $\theta$-player: Optimizes model parameters (e.g., neural network weights) using surrogates like hinge loss.
  2. The $\lambda$-player: Manages Lagrange multipliers to enforce constraints.
  3. The $\xi$-player: Manages slack variables using the true, original rates.

This decoupling is the framework's primary innovation. In the practical surrogate-based version (Algorithm 2), only the $\theta$-player uses approximations, while the other players operate on true rates. This prevents the optimization from entering mathematically undefined regions and allows for tighter constraint handling.

Comparison of the proposed algorithms (Alg. 1, 2, 3) with existing methods like SPADE and NEMSIS, highlighting the differences in player objectives and strategies.

Experimental Evaluation

The framework was evaluated across six diverse datasets, including COMPAS, Law School, Adult, and Wiki Toxicity, focusing on fairness and classification tasks.

Key Results

  • Stability and Feasibility: Unlike previous methods (SPADE, NEMSIS) that often failed on metrics like KL-divergence due to surrogate instability, this three-player approach consistently found valid solutions.
  • Fairness Performance: On the Wiki Toxicity and Adult datasets, the framework achieved top-tier fairness scores while respecting a pre-defined 10% limit on error rate increases.
  • Handling Complex Ratios: For difficult "sum-of-ratios" constraints like F-measure parity, the proposed biconvex optimizer significantly outperformed unconstrained baselines.

Discussion and Limitations

While the framework offers significant improvements in stability and flexibility, it has some trade-offs. The theoretical convergence rate for the surrogate-based version is $O(T^{-1/4})$, which is slower than standard convex optimization. Additionally, the game-theoretic output is often a distribution over models (a stochastic classifier), though the authors provide a "shrinking" procedure to distill this into a sparse set of models for practical use. Finally, while the sum-of-ratios algorithms perform well empirically, they currently lack the same rigorous convergence guarantees as the convex versions, marking a clear path for future research.

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