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 constraining another metric of interest. Examples of such problems include optimizing the false negative rate at a fixed false positive rate, optimizing precision at a fixed recall, optimizing the area under the precision-recall or ROC curves, etc. Our key idea is to formulate a rate-constrained optimization that expresses the threshold parameter as a function of the model parameters via the Implicit Function theorem. We show how the resulting optimization problem can be solved using standard gradient based methods. Experiments on benchmark datasets demonstrate the effectiveness of our proposed method over existing state-of-the art approaches for these problems.
Introduction
In many real-world machine learning applications, standard accuracy is an insufficient metric. For instance, a medical diagnostic tool may need to minimize false negatives while strictly maintaining false positives below a 1% threshold. Similarly, a search engine might aim to maximize precision at a specific recall level. These scenarios involve non-decomposable metrics—objectives that cannot be calculated by simply averaging a loss over individual data points because they depend on the entire dataset and a specific decision threshold.
Traditional approaches to these problems rely on constrained optimization, often utilizing Lagrangian multipliers in a "min-max" game between model weights and constraints. However, these methods frequently suffer from instability, slow convergence, and poor performance at extreme operating points, such as very low false positive rates (FPR).
Methodology: Implicit Constrained Optimization (ICO)
Researchers at Google have introduced Implicit Constrained Optimization (ICO) to address these limitations. The core innovation is a shift in perspective: instead of treating the decision threshold ($\lambda$) as an independent variable to be balanced against model weights ($\theta$), the threshold is treated as an implicit function of the weights.
The Implicit Function Theorem (IFT)
By leveraging the Implicit Function Theorem, the researchers can calculate the gradient of the objective function with respect to model parameters without requiring an explicit formula for the threshold. This mathematical framework essentially determines how the optimal threshold must shift to maintain a satisfied constraint whenever the model weights are updated.
The ICO Algorithm
The training process alternates between two primary phases:
- Gradient Updates: Standard updates are performed using IFT-derived gradients.
- Correction Step: A periodic line search ensures the threshold precisely satisfies the target constraint (e.g., exactly 5% FPR) every few minibatches.
To handle the non-differentiable nature of metrics like FPR (which are essentially staircase functions), the method employs smooth surrogate losses, such as Sigmoid or Softplus, during the gradient calculation phase.
Experimental Results
The ICO method was evaluated across diverse tasks, including computer vision (CelebA facial attributes, BigEarthNet satellite imagery) and various UCI tabular benchmarks (Letter, Adult, Spambase).
Superiority at the "Tails"
One of the most significant findings is ICO's effectiveness at extreme operating points. While Lagrangian methods often provide loose approximations at the "tails" of a distribution (e.g., 1% or 2% FPR), ICO’s direct modeling of threshold sensitivity maintains high performance.
Performance and Efficiency
On the CelebA dataset, ICO consistently achieved lower False Negative Rates than the state-of-the-art TFCO (TensorFlow Constrained Optimization) library. For multi-constraint problems, such as optimizing the Area Under the Curve (AUC), ICO proved to be up to 5x faster in wall-clock time. This efficiency stems from its ability to collapse multiple gradient calls into just two, whereas standard tools require separate gradient computations for every constraint.
Conclusion and Future Work
ICO transforms difficult constrained problems into simpler unconstrained ones by bypassing the traditional min-max game. While the Implicit Function Theorem provides only local guarantees, the method demonstrates robust empirical success. Future research may explore expressing thresholds as functions of only a subset of parameters (such as the final layer of a neural network) to further increase efficiency, or extending the framework to complex query-based ranking systems.
Summary updated