Abstract
Empirical risk minimization frequently employs convex surrogates to underlying discrete loss functions in order to achieve computational tractability during optimization. However, classical convex surrogates are often limited to specific classes of functions, such as submodular or supermodular losses. This paper introduces a novel convex surrogate operator, $B_D$, designed to handle general "non-modular" loss functions—those that are neither submodular nor supermodular (like the Sørensen-Dice loss). By proving a unique way to decompose these complex losses into submodular and supermodular components, the authors provide a tractable, polynomial-time optimization framework that significantly outperforms traditional methods in structured prediction tasks.
Introduction
In machine learning, the objective is often to minimize a specific discrete loss function, such as the Hamming loss or F1-score, during training. However, these discrete functions are typically non-convex and non-differentiable, making them impossible to optimize directly using standard gradient-based methods. To overcome this, researchers utilize convex surrogates—smooth, bowl-shaped approximations that are computationally easier to minimize.
Existing surrogates are highly specialized: "slack rescaling" is effective for supermodular losses, while the "Lovász hinge" is tailored for submodular losses. A significant gap remains for non-modular losses, such as the Sørensen-Dice coefficient or Jaccard index. These metrics are essential in fields like image segmentation and natural language processing but do not fit neatly into either category. Until now, there was no mathematically rigorous and efficient method to create a tight convex surrogate for these complex functions.
Methodology: The $B_D$ Operator
The authors propose a "divide and conquer" strategy based on a new mathematical foundation involving a Canonical Decomposition. They prove that any non-negative set function can be uniquely decomposed into a sum of a submodular function and a supermodular function ($l = f^* + g^*$). They define a specific operator, $D$, to identify this canonical version via a linear program, resolving previous ambiguities where such decompositions were not unique.
Once the loss is decomposed, the framework applies the optimal tool for each component: slack rescaling for the supermodular part and the Lovász hinge for the submodular part. The resulting surrogate, $B_D$, is proven to be convex and piecewise linear. Crucially, its subgradients can be computed in polynomial time, allowing for efficient training using standard cutting-plane algorithms similar to those employed in Structural SVMs.
Experimental Evaluation
The researchers evaluated the $B_D$ operator on two primary benchmarks to test both theoretical validity and real-world scalability.
Synthetic 2D Data
A binary classification task using Gaussian mixtures was used to demonstrate the theoretical correctness and tightness of the surrogate. This controlled environment allowed the authors to verify that $B_D$ provides a closer approximation to the true convex closure of the loss function than standard slack rescaling alone.
Face Track Dataset (Buffy)
To test scalability, the method was applied to a real-world dataset derived from the TV series Buffy the Vampire Slayer. This dataset contains 1,437 tracks and 27,504 frames, where the goal is to recognize the leading role across video sequences of varying lengths. This task represents a complex structured prediction problem where non-modular losses are common.
Key Results and Insights
- Superior Accuracy: On the Sørensen-Dice loss, the $B_D$ surrogate achieved an average loss of 0.1121, significantly outperforming standard SVMs (0.1497) and basic slack rescaling (0.3183).
- Scalability and Convergence: Despite the mathematical complexity of the decomposition, the method scaled effectively to the Buffy dataset. The convergence rate (primal-dual gap) remained comparable to standard SVMs, indicating no significant training slowdown.
- Polynomial Tractability: While the decomposition involves a linear program that could be exponential in the general case, the authors show that for practical losses (e.g., those based on false positives/negatives), the problem reduces to a manageable quadratic size.
Conclusion and Future Work
The $B_D$ operator provides a robust framework for optimizing non-modular loss functions that were previously difficult to handle. By ensuring a unique and stable decomposition, the authors have created a tighter and more reliable surrogate for structured prediction. Future work will focus on integrating this surrogate with stochastic gradient descent (SGD) and exploring its application within deep neural network architectures to enable loss-aware training in more complex models.
Summary updated