In standard machine learning, we usually assume that our loss function is decomposable. This means the total loss is simply the average of the losses calculated for each individual data point. If you have a million images, you can calculate the error for each one independently, sum them up, and you have your objective. This property is the bedrock of Stochastic Gradient Descent (SGD): because the loss decomposes, a small random "minibatch" of data provides an unbiased estimate of the true gradient.
However, the metrics we actually care about in the real world—like Area Under the Precision-Recall Curve (AUPRC), Average Precision (AP), or "Accuracy at the Top"—are non-decomposable. You cannot calculate the Precision of a single image in isolation; Precision only exists in the context of how that image is ranked relative to every other image in the dataset.
The Loss-Metric Mismatch
When we train a model using a decomposable surrogate like cross-entropy, we hope that minimizing this proxy will also improve our target ranking metric. As Chen Huang and colleagues point out in MetricOpt: Learning To Optimize Black-Box Evaluation Metrics, this often leads to a "loss-metric mismatch." A model might continue to drive its cross-entropy loss lower while its actual performance on a metric like Recall or Average Precision plateaus or even declines.
The challenge is that these ranking metrics are often non-differentiable (due to the sorting operation) and globally dependent. As noted in the survey by Shu Hu and Siwei Lyu, Rank-based Decomposable Losses in Machine Learning: A Survey, this interdependency breaks the fundamental assumptions of SGD. If the loss for sample A depends on the score of sample B, a minibatch containing only A cannot give you an accurate gradient.
Reformulating Ranking as Compositional Optimization
To solve this, researchers have moved toward reformulating these global ranking metrics into forms that SGD can handle. Qi Qi and Shuiwang Ji introduced SOAP in Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence. They treat Average Precision as a "coupled compositional" problem.
In this view, the objective is seen as a function of a function. The "inner" part of the function estimates the statistics of the global distribution (like the rank of a sample), while the "outer" part optimizes the model parameters based on those estimates. By maintaining moving averages of these global statistics across many minibatches, the algorithm can "remember" the rest of the dataset while only looking at a small slice of it.
Bridging the Minibatch Gap
A recurring problem in this field is gradient bias. If you calculate a ranking metric using only the samples in your current minibatch, you will almost always get a biased estimate of the true global ranking.
Lukáš Adam and Václav Mácha addressed this in DeepTopPush: Simple and Scalable Method for Accuracy at the Top. Their approach, DeepTopPush, focuses on the extreme end of the ranking—ensuring the very highest-scored samples are correct. To fix the bias inherent in minibatches, they carry over a "delayed" sample from previous batches. This simple memory mechanism allows the optimizer to compare current samples against a representative "best-so-far" sample from the global set, effectively anchoring the local gradient to the global distribution.
Stability and Robustness in Ranking
Optimizing for ranking is not just about the training error; it’s about how that ranking holds up on unseen data or under pressure. Peisong Wen and Qianqian Xu explored this in Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability. They introduced the concept of "listwise stability"—the idea that a small change in the training set shouldn't radically reorder the entire list of predictions. This theoretical framework ensures that algorithms like their SOPRC generalize well even when the data is highly imbalanced.
Furthermore, Gang Li and Tianbao Yang have extended these ideas to security-critical applications in Maximization of Average Precision for Deep Learning with Adversarial Ranking Robustness. They demonstrate that even if a model's accuracy is robust against adversarial attacks, its ranking can still be fragile. By directly maximizing AP within an adversarial training loop, they ensure that the relative ordering of samples remains stable even when the input data is perturbed.
By treating ranking not as a post-processing step but as a first-class citizen of the optimization process, these methods allow deep learning models to excel in high-stakes retrieval and detection tasks where being "mostly right" isn't enough—the order of the results is what matters.