Direct Optimization of Non-Decomposable Performance Metrics

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 237 papers37 conceptsfrozen 2026-10-04

In standard machine learning, we typically train models by minimizing a "decomposable" loss function, such as cross-entropy or mean squared error. These losses are convenient because the total error is simply the sum of errors on individual data points. However, the metrics we actually care about—such as the $F_1$-score, Area Under the ROC Curve (AUC), and Normalized Discounted Cumulative Gain (NDCG)—are non-decomposable. They are calculated over an entire dataset or a set of predictions, meaning the score for one data point depends on the model's performance on all others.

This creates a fundamental mismatch: we train models to minimize point-wise error but evaluate them on set-wise utility. A growing body of research seeks to bridge this gap by developing optimization frameworks that target these complex metrics directly.

The Challenge of Global Dependencies

The primary hurdle in optimizing metrics like AUC or $F_1$ is that they cannot be broken down into independent per-instance losses. For example, the $F_1$-score is a non-linear combination of precision and recall. If you change the prediction for one instance, it shifts the denominators for both, affecting the "loss" of every other instance in the set.

Early foundational work by Thorsten Joachims in A support vector method for multivariate performance measures addressed this by reformulating the problem within a Support Vector Machine (SVM) framework. By treating the entire sequence of labels as a single structured object, researchers could optimize for any metric derivable from a contingency table. Similarly, Martin Jansche proposed a Maximum Expected Utility Framework to align the "decoding" phase of sequence labeling with the F-measure used during evaluation.

From Batch to Stochastic Optimization

While batch methods work for small datasets, modern deep learning requires stochastic gradient descent (SGD), which operates on small mini-batches. This is inherently difficult for non-decomposable metrics because a mini-batch rarely provides an unbiased estimate of a global metric like AUC.

To solve this, researchers have moved toward compositional and bilevel optimization. For instance, Zi-Hao Qiu and Tianbao Yang demonstrated in Large-scale Stochastic Optimization of NDCG Surrogates that ranking metrics like NDCG can be reframed as a nested optimization problem. This allows the model to update its parameters based on a moving average of the global ranking structure, rather than just the items present in the current mini-batch.

For the $F_1$-measure, Robert Istvan Busa-Fekete and Xiaoxuan Zhang developed online algorithms like OFO and FOFO. These methods treat $F_1$ optimization as a root-finding problem, iteratively adjusting a classification threshold as new data streams in, ensuring the model converges to the true optimal $F_1$ without needing multiple passes over the data.

Handling Data Interdependencies in Federated Learning

The complexity of non-decomposable metrics is amplified in Federated Learning (FL), where data is distributed across many machines. To calculate a metric like AUC, one would theoretically need to compare a positive sample on "Machine A" with a negative sample on "Machine B."

The FeDXL framework, developed by Zhishuai Guo and colleagues, introduces the concept of X-Risk Optimization. They decompose the global gradient into "active" parts (calculated locally) and "passive" parts (historical information communicated from the network). This allows for the optimization of "X-risks"—complex objectives like AUROC and NDCG—with the same communication efficiency as standard federated averaging.

Efficiency through Mathematical Reparameterization

Directly optimizing these metrics often involves non-smooth or non-convex functions that are difficult for standard backpropagation. Researchers have introduced several "plug-in" strategies to make this computationally feasible:

  • Lagrangian Reparameterization: Sathya N. Ravi showed in Optimizing Nondecomposable Data Dependent Regularizers that global constraints can be integrated into deep networks using a dual formulation, allowing for direct $F_1$ or AUC optimization with minimal overhead.
  • Adaptive Scaling: In information extraction, where positive instances are rare, Hongyu Lin proposed Adaptive Scaling, which uses marginal utility to dynamically reweight samples, effectively forcing the model to prioritize the $F_1$-score during training.
  • ADMM Frameworks: For multi-task learning, Ge-Yang Ke utilized the Alternating Direction Method of Multipliers to decouple the optimization of task-specific metrics from the shared model parameters.

By moving beyond simple point-wise losses, this research direction ensures that models are not just "accurate" in a general sense, but are specifically tuned for the high-stakes, imbalanced, and ranking-heavy environments where they are actually deployed.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 26 papers
  2. Version 1 · 2026-10-04 · 37 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_ranking_metric_generalization_80333a7c,
  title = {ranking metric generalization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ranking-metric-generalization/rdr_80333a7cdccf462a8802b7861f681ced},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_direct_optimization_of_non_decomposable__80333a7c_v1,
  title = {Direct Optimization of Non-Decomposable Performance Metrics},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/direct-optimization-of-non-decomposable-performance-metrics/rdr_80333a7cdccf462a8802b7861f681ced/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}