In machine learning, we routinely encounter a frustrating paradox: we train models using one objective, but evaluate them using another. During training, gradient-based optimization requires loss functions to be smooth and continuous so that every tiny adjustment to a model's parameters yields a predictable change in the loss. However, the real-world metrics we actually care about—such as the F1-score in classification, BLEU in machine translation, Average Precision (AP) in object detection, and Intersection over Union (IoU) in semantic segmentation—are inherently discrete. They rely on hard operations like thresholding, counting, sorting, or dynamic programming.
This discrepancy creates a loss-metric mismatch. As highlighted by Yash Patel et al. in [Learning Surrogates via Deep Embedding] and Gabriel Bénédict et al. in [sigmoidF1: A Smooth F1 Score Surrogate Loss for Multilabel Classification], optimizing a proxy like cross-entropy leaves performance on the table because the training objective does not perfectly align with the evaluation criteria. The same challenge appears in structural optimization; for instance, Shangqian Gao et al. in [Network Pruning via Performance Maximization] observe that minimizing standard classification loss does not necessarily yield the most accurate pruned sub-network.
To understand why we cannot directly optimize these metrics with standard gradient descent, imagine the error surface of a discrete metric as a staircase or a flat plateau punctuated by sudden steps. If you change a model's weights slightly, the discrete counts of true positives or correct words do not change at all, meaning the gradient is exactly zero. At the precise boundary where a prediction crosses a threshold, the metric jumps discontinuously, making the gradient undefined. Standard backpropagation cannot navigate a landscape of zeros and sudden jumps.
To bridge this gap, researchers have developed techniques to optimize non-differentiable metrics directly or via smooth mathematical stand-ins.
Smoothing the Staircase: Differentiable Relaxations
The most intuitive way to resolve the zero-gradient problem is to replace the discrete, step-like operations within a metric with smooth, continuous approximations.
Consider the F1-score, which depends on counting true positives, false positives, and false negatives based on a hard threshold (e.g., predicting a class if the output probability $p \ge 0.5$). The indicator function responsible for this hard threshold has a derivative of zero everywhere except at $0.5$, where it is undefined.
To bypass this, Gabriel Bénédict et al. replace the hard indicator function with a soft sigmoid function. Instead of counting a prediction as a strict $0$ or $1$, the continuous probability itself is used to compute "soft" versions of true positives and false positives. Because the sigmoid function is differentiable, the resulting sigmoidF1 loss yields meaningful gradients across the entire parameter space, allowing the model to target the F1-score directly during backpropagation.
This strategy of continuous relaxation applies widely across different domains:
- Clinical Constraints: In early warning systems, Michael C Hughes et al. in [Optimizing Early Warning Classifiers to Control False Alarms via a Minimum Precision Constraint] utilize tight sigmoidal bounds to optimize recall while strictly enforcing a minimum precision threshold, smoothing out the discrete counts that define false alarms.
- Structured Text: Coreference resolution systems evaluate clusters of mentions using discrete set operations. While Jian-Bo Yang et al. note in [Domain Adaptation for Coreference Resolution: An Adaptive Ensemble Approach] that metrics like MUC and B-CUBED resist direct optimization, Phong Le et al. demonstrate in [Optimizing Differentiable Relaxations of Coreference Evaluation Metrics] that these cluster-based metrics can be relaxed into differentiable forms, outperforming reinforcement learning alternatives in both speed and accuracy.
- Signal Processing: In radar signal deinterleaving, Stefano Gasperini et al. [Signal Clustering With Class-Independent Segmentation] replace non-differentiable clustering metrics like purity and fragmentation with a differentiable "soft confusion matrix" loss.
- Time-Series Alignment: Traditional sequence alignment relies on Dynamic Time Warping (DTW), a discrete dynamic programming algorithm. Abubakar Abid et al. in [Learning a Warping Distance from Unlabeled Time Series Using Sequence Autoencoders] introduce a flexible, differentiable family of warping distances, enabling gradient-based optimization to automatically tune alignment parameters without human engineering.
Direct Loss Minimization: Shifting the Inference
Instead of smoothing the metric itself, an alternative approach changes the optimization mechanics. Direct Loss Minimization computes a mathematically rigorous gradient for a discrete task loss by modifying the model's inference step during training.
The core mechanism relies on loss-adjusted inference. During a standard training forward pass, a structured prediction model outputs the configuration that maximizes its internal scores. In loss-adjusted inference, we intentionally perturb this step by adding the actual task loss (e.g., the negative BLEU score or word error rate) directly to the scoring function.
$$\hat{y}_{\text{loss-adjusted}} = \arg\max_{y} \left[ \text{Score}(x, y) + \text{Loss}(y_{\text{true}}, y) \right]$$
This adjustment forces the model to search for an alternative prediction that has both a high model score and a high task error. By comparing the features of this loss-augmented prediction with the true target, the system uncovers exactly which parameters caused the catastrophic metric failure.
David A. McAllester et al. formalized this in [Direct Loss Minimization for Structured Prediction] by proving the Loss Gradient Theorem. They showed that a simple, perceptron-like update rule driven by this loss-adjusted inference step directly corresponds to the gradient of the expected task loss.
Alex Schwing et al. extended this framework to non-linear deep architectures in [Direct Loss Minimization for Training Deep Neural Nets], demonstrating that optimizing application-specific metrics like Average Precision directly makes deep networks significantly more robust to label noise. To guarantee that minimizing these surrogates truly minimizes the target task loss, Anqi Mao et al. introduced in [Structured Prediction with Stronger Consistency Guarantees] new families of structured losses (comp-sum and constrained losses) that provide non-asymptotic, hypothesis-aware consistency bounds.
Automated Search and Refactoring of Surrogates
Manually designing a custom differentiable relaxation for every new metric is challenging. Consequently, researchers have built frameworks to automate the discovery and construction of surrogate losses.
The authors of [A Unified Framework of Surrogate Loss by Refactoring and Interpolation], Lanlan Liu et al., introduced UniLoss, a framework that systematically refactors any discrete metric. UniLoss breaks an evaluation metric down into a sequence of primitive comparison operations (such as ranking or thresholding) and applies multivariate interpolation to automatically generate a differentiable surrogate. This eliminates the need to manually engineer task-specific losses.
Alternatively, the search for a surrogate loss can be framed as an optimization problem itself, solved via reinforcement learning or parameter search:
┌────────────────────────────────────────────────────────┐
│ Reinforcement Learning Loop │
│ │
│ ┌──────────────────┐ ┌────────────────────┐ │
│ │ Search Controller│───────>│ Surrogate Loss │ │
│ │ (Proposes Loss) │ │ Function Candidate│ │
│ └──────────────────┘ └─────────┬──────────┘ │
│ ▲ │ │
│ │ ▼ │
│ │ ┌────────────────────┐ │
│ │ │ Train Target Model │ │
│ │ └─────────┬──────────┘ │
│ │ ▼ │
│ │ ┌────────────────────┐ │
│ └─────────────────│ Evaluate True │ │
│ Reward Signal │ Non-Diff Metric │ │
│ └────────────────────┘ │
└────────────────────────────────────────────────────────┘
Using this paradigm, Hao Li et al. developed [Auto Seg-Loss: Searching Metric Surrogates for Semantic Segmentation], which uses a reinforcement learning controller to discover differentiable surrogate losses that align with non-differentiable segmentation metrics like mean Intersection over Union (mIoU). Similarly, Chenxin Tao et al. in [Searching Parameterized AP Loss for Object Detection] automate the discovery of parameterized surrogate functions to optimize Average Precision, bypassing the non-differentiable ranking steps native to object detection evaluation.
Non-Decomposable Objectives and Global Constraints
A significant complication arises when metrics are non-decomposable. A decomposable loss (like cross-entropy) can be computed independently for each individual data point and averaged across the dataset. Non-decomposable metrics—such as the Area Under the ROC Curve (AUC) or the True Accept Rate (TAR) at a fixed False Accept Rate (FAR)—cannot be broken down this way. They depend on the global distribution of model scores and the relative ranking of data points across the entire dataset.
Early work by Michael C. Mozer et al. [Prodding the ROC Curve: Constrained Optimization of Classifier Performance] addressed this by "prodding" specific regions of the ROC curve during training to maximize accuracy within targeted operational windows. To handle these global properties systematically, Abhishek Kumar et al. developed [Implicit rate-constrained optimization of non-decomposable objectives], a framework that optimizes global rate constraints implicitly without requiring the objective to decompose over individual samples.
This global perspective is vital for practical deployment:
- Face Recognition: Systems are evaluated on their True Accept Rate at an extremely low, fixed False Accept Rate (e.g., TAR@FAR=1e-4). Jiaheng Liu et al. introduce [AnchorFace: Boosting TAR@FAR for Practical Face Recognition], which directly optimizes the validation metric by anchoring the loss function around the target operational FAR threshold.
- Multi-Objective Trade-offs: When multiple non-smooth constraints conflict, Soumyajit Gupta et al. in [Learning a neural Pareto manifold extractor with constraints] present a scalable framework (SUHNPF) that maps out the entire Pareto manifold of optimal trade-offs using a double gradient descent strategy, bypassing the limitations of continuous proxies in multi-task learning.
Optimization Without Gradients
When the parameter space is small or gradients are completely unavailable, researchers bypass differentiability entirely by using direct search algorithms or reinforcement learning.
In early statistical machine translation, Franz Josef Och developed Minimum Error Rate Training (MERT) [Minimum Error Rate Training in Statistical Machine Translation]. Because the parameter space for combining translation features was low-dimensional, MERT calculated the exact piecewise linear error surface along a line search direction. This allowed the algorithm to find optimal parameter steps directly on the non-differentiable BLEU or Word Error Rate surface without computing gradients.
For post-hoc adjustments, such as finding the optimal decision thresholds for sound event detection, Qiuqiang Kong [Sound Event Detection of Weakly Labelled Data with CNN-Transformer and Automatic Threshold Optimization] demonstrates that threshold optimization can be automated directly against the non-differentiable F1-score metric after the primary model has been trained.
Finally, when the parameter space is large and the metric cannot be relaxed, reinforcement learning algorithms like REINFORCE treat the non-differentiable metric as a black-box reward signal. This approach is demonstrated by Rasool Fakoor et al. in [Direct optimization of F-measure for retrieval-based personal question answering], where they optimize personal voice-retrieval models directly against the F1-score by treating text selection as a discrete action, bypassing the need for a differentiable loss function entirely.
Key Foundational Work
Prodding the ROC Curve: Constrained Optimization of Classifier Performance (2001) — contributed 1 concept elements to this direction.
Minimum Error Rate Training in Statistical Machine Translation (2003) — contributed 1 concept elements to this direction.