Implicit rate-constrained optimization of non-decomposable objectives

Abhishek Kumar, Harikrishna Narasimhan, Andrew Cotter

In the world of machine learning, we often train models using simple loss functions like cross-entropy, but evaluate them using complex, "non-decomposable" metrics. Consider the challenge of optimizing the False Negative Rate (FNR) while strictly keeping the False Positive Rate (FPR) below 1%, or maximizing the area under a Precision-Recall curve. These metrics are notoriously tricky because they do not break down into a simple average over individual data points; rather, they depend on the global distribution of scores and the specific classification thresholds chosen.

A recent paper from Google Research introduces a clever approach to tackle these problems: Implicit Constrained Optimization (ICO). By leveraging a classic piece of calculus—the Implicit Function Theorem—the authors demonstrate how to transform these messy constrained problems into a much simpler unconstrained optimization task.

The Challenge of Non-Decomposable Metrics

Most standard loss functions are decomposable, meaning the total loss is simply the sum of losses for each individual example. However, many real-world requirements are non-decomposable. Common examples include:

  • Security and Medical Diagnostics: "Minimize false negatives, but don't let the false positive rate exceed 0.1%."
  • Fairness: "Ensure the selection rate for demographic group A is at least 80% of the rate for group B."
  • Search and Retrieval: "Maximize Precision at a specific Recall level."

The traditional approach to solving these is via Lagrangian multipliers, which turns the problem into a "min-max" game. One player minimizes the loss, while another player (the multiplier) maximizes the penalty for violating constraints. These games are notoriously difficult to tune, prone to instability, and often require many iterations to converge.

Implicit Constrained Optimization (ICO)

The core innovation of this paper is the ICO algorithm. Instead of treating the classification threshold ($\lambda$) as an independent variable to be "played" against the model weights ($\theta$), the authors recognize that for any given set of weights, there is an "ideal" threshold that perfectly satisfies the constraint.

  1. The Implicit Function Theorem (IFT): The authors treat the threshold $\lambda$ as an implicit function of the weights, $\lambda = h(\theta)$. Even without an explicit formula for $h(\theta)$, the IFT allows them to calculate the gradient of the objective with respect to the weights, fully accounting for how the threshold must shift to maintain the constraint.
  2. Surrogate Losses: Because metrics like "counts of false positives" are step-like and non-differentiable, the method uses smooth surrogates (such as sigmoids) to calculate these gradients.
  3. The Correction Step: To prevent the model from drifting away from the actual constraint due to surrogate approximations, the algorithm employs a periodic "correction step." Every few iterations, it performs a simple line search to find the exact threshold that satisfies the real, non-smooth constraint on the current batch of data.
  4. Handling Multiple Constraints: For metrics like AUC (which involve integrating over many thresholds), the authors introduce a "stop-gradient" trick that prevents computational costs from exploding as the number of constraints increases.

Experimental Results

The researchers evaluated ICO across a diverse set of benchmarks, including image classification tasks like CelebA (face attributes) and BigEarthNet (satellite imagery), as well as classic UCI datasets (Letter, IJCNN1, Adult, Spambase, and Communities & Crime) to test robustness against class imbalance and fairness constraints.

Superior Performance at the "Edges" ICO significantly outperformed the state-of-the-art TensorFlow Constrained Optimization (TFCO) library, particularly at extreme operating points. For example, when tasked with minimizing FNR at a very low 1% FPR, ICO provided noticeably better trade-offs.

ROC curves for the Black-hair attribute on CelebA, highlighting ICO's superior performance at low False Positive Rates.

Robustness to Imbalance On highly imbalanced datasets, ICO proved highly effective. For instance, on the "Letter" dataset (which contains only 4% positive examples), ICO achieved a PR-AUC of 23.04, compared to 20.49 for the Lagrangian baseline and a mere 15.13 for standard cross-entropy.

Precision-Recall curves on the IJCNN1 dataset comparing standard Cross-Entropy, TFCO, and the proposed Implicit method.

Efficiency and Speed By folding the constraint into the objective via the IFT, the problem becomes a standard unconstrained optimization. Practitioners can use off-the-shelf optimizers like Adam or Adagrad without worrying about the instabilities of primal-dual training. In many cases, ICO converged to a better solution in less wall-clock time because it avoids the oscillatory behavior common in min-max optimization.

Limitations and Future Directions

While the paper provides a theoretical roadmap for multi-class and ranking metrics, the experimental results primarily focus on binary classification tasks. Additionally, the Implicit Function Theorem only guarantees that the implicit function exists locally. While this works well for gradient-based updates, global behavior remains more complex.

Looking forward, the authors suggest that this "implicit thresholding" could be revolutionary for query-based ranking (like search engines). In such systems, every single query essentially acts as a separate constraint—a scenario that is currently a computational nightmare for traditional Lagrangian methods, but potentially solvable with ICO.

Summary updated

Abstract

We consider a popular family of constrained optimization problems arising in machine learning that involve optimizing a non-decomposable evaluation metric with a certain thresholded form, while con...
BibTeX
@inproceedings{kumar2021implicit,
  author = {Abhishek Kumar and Harikrishna Narasimhan and Andrew Cotter},
  title = {{Implicit rate-constrained optimization of non-decomposable objectives}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=_dvaLvkgceO},
}
Figure