Learning with Complex Loss Functions and Constraints

Harikrishna NarasimhanAISTATS 2018 · OpenReview

Abstract

We develop a general approach for solving constrained classification problems where the loss and constraints are defined as general functions of the confusion matrix. Our framework reduces these complex, non-linear optimization problems into a sequence of standard cost-sensitive learning tasks. We introduce two primary algorithms: COCO for convex objectives and constraints, and FRACO for fractional-convex objectives. We demonstrate that our approach is statistically consistent and performs well on real-world datasets involving fairness and coverage constraints.

Introduction

Standard machine learning typically focuses on minimizing simple accuracy (0-1 loss). However, many practical applications require optimizing more nuanced metrics like the F1-score or G-mean, especially in the presence of class imbalance. Furthermore, real-world deployment often necessitates satisfying hard constraints, such as demographic parity for fairness or specific coverage targets for budget management. Existing methods often struggle with non-linearities in both the objective and the constraints. This work provides a unified, theoretically grounded framework to address these challenges simultaneously.

Methodology: Optimization over Confusion Matrices

The key insight of this work is that for a wide range of performance metrics, the confusion matrix serves as a sufficient statistic. Instead of optimizing over the high-dimensional space of all possible classifiers, we optimize over the convex space of $n \times n$ confusion matrices.

COCO and FRACO Algorithms

The COCO (Convex losses with Convex constraints) algorithm handles cases where both the loss and constraints are convex functions of the confusion matrix. It employs a Lagrange multiplier approach where the "outer loop" updates multipliers via gradient ascent, and the "inner loop" solves the resulting Lagrangian using the Frank-Wolfe algorithm. Crucially, each Frank-Wolfe step reduces to a standard cost-sensitive learning problem, allowing the use of existing black-box solvers like logistic regression.

For fractional-convex objectives (e.g., F-measure), we propose FRACO (Fractional-convex losses). This algorithm uses a bisection method to transform the fractional problem into a series of convex sub-problems, which are then solved using the COCO framework. The final output is a randomized classifier—an ensemble of base classifiers that achieves the target performance in expectation.

Experimental Results

Constraint Satisfaction

We evaluated the COCO algorithm on tasks requiring the minimization of H-mean subject to specific coverage constraints. As shown in Figure 1, COCO is able to hit the desired coverage targets almost exactly while maintaining a competitive H-mean loss. In contrast, unconstrained baselines and standard logistic regression fail to satisfy the constraints or result in significantly higher losses.

H-mean loss vs. coverage (left) and coverage vs. constraint parameter ε (right).

Fairness and Complex Metrics

A major application of this framework is in fair machine learning. We optimized the Q-mean metric under demographic parity constraints on datasets like UCI Adult and COMPAS. Figure 2 illustrates that COCO significantly outperforms baselines like "Lin-con," which only optimizes linear loss under fairness constraints. By directly optimizing the complex Q-mean metric while strictly adhering to the demographic parity constraint, COCO achieves a better trade-off between performance and fairness.

Q-mean loss vs. demographic parity (left) and demographic parity vs. constraint parameter ε (right).

Conclusion

This framework offers a statistically consistent and computationally tractable way to handle complex objectives and constraints in classification. By reducing the problem to cost-sensitive learning, it leverages existing ML infrastructure. While the resulting randomized classifiers can be complex, the ability to precisely satisfy non-linear constraints makes this a powerful tool for high-stakes applications like fairness and resource-constrained prediction. Future work will focus on reducing ensemble size and improving scalability for massive datasets.

Summary updated

Abstract

We develop a general approach for solving constrained classification problems, where the loss and constraints are defined in terms of a general function of the confusion matrix. We are able to hand...
BibTeX
@inproceedings{narasimhan2018learning,
  author = {Harikrishna Narasimhan},
  title = {{Learning with Complex Loss Functions and Constraints}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=a8KzOilLx9M},
}
Figure