A Convex Surrogate Operator for General Non-Modular Loss Functions

Jiaqian Yu, Matthew B. Blaschko

TL;DR

This paper introduces a novel convex surrogate operator that can efficiently handle general non-modular loss functions, a significant limitation of previous methods. By decomposing these complex losses into submodular and supermodular components, they achieve a tractable solution for optimization, demonstrating improved performance and scalability on challenging real-world tasks.

What Problem Does This Paper Address?

In machine learning, we often want to minimize a "loss function" that quantifies how bad a prediction is. For many complex problems, especially those involving predicting multiple labels or structured outputs (like segmenting an image or identifying multiple objects in a video), the ideal loss functions are "non-modular." This means their behavior doesn't simply break down into independent parts. However, optimizing these non-modular losses directly is computationally intractable.

Traditional approaches use "convex surrogates" to approximate these difficult losses with easier-to-optimize convex functions. The problem is that existing convex surrogates are only effective for specific types of losses: modular (like Hamming loss), submodular, or supermodular. They struggle with the general case of non-modular losses, leaving a gap in our ability to efficiently train models for a wide range of important problems.

Methods

The core innovation of this paper is a method to decompose any general non-modular loss function into two parts: a submodular component and a supermodular component. They prove that this decomposition is unique and can be found efficiently.

Once this decomposition is achieved, they construct a novel convex surrogate operator, denoted as $B\Delta$. This operator is formed by taking the sum of two existing, well-behaved convex surrogates:

  1. Slack-rescaling: Applied to the supermodular component. This is a standard technique for supermodular losses.
  2. Lovász hinge: Applied to the submodular component. This is a standard technique for submodular losses.

By combining these, they create a surrogate that inherits the desirable properties of both while being applicable to the combined, general non-modular loss. They then prove that their proposed surrogate $B\Delta$ is convex, piecewise linear, an extension of the original loss function, and crucially, allows for polynomial-time computation of subgradients, which is essential for efficient optimization.

Datasets

  • Synthetic Data: Used to evaluate the Sørensen-Dice loss on a binary classification problem with two-dimensional data generated from different Gaussian mixtures.
  • Face Track Dataset: A real-world dataset containing 1437 tracks and 27504 frames from the TV series "Buffy the Vampire Slayer." This dataset was used for a binary classification task to recognize the leading role ("Buffy" vs. "not Buffy").

Key Insights and Ideas

  • Decomposition is Key: The fundamental insight is that any complex loss function can be broken down into simpler, well-understood submodular and supermodular parts. This decomposition unlocks the ability to handle previously intractable loss functions.
  • Bridging the Gap: By combining specialized surrogates for submodular and supermodular functions, the authors create a unified approach for general non-modular losses. This is a significant step beyond existing methods that are limited to specific loss types.
  • Tractability for Non-Modular Losses: The paper demonstrates that even for complex, non-modular losses, efficient optimization is possible. This opens doors for applying machine learning to a wider array of problems where previously only approximations or simpler loss functions were feasible.
  • Sørensen-Dice Loss is Non-Modular: The paper explicitly shows that the Sørensen-Dice loss, a popular metric in fields like image segmentation, is neither submodular nor supermodular, highlighting its relevance to the problem addressed.

Key Results

  • Improved Performance: On synthetic data using the Sørensen-Dice loss, their method ($B\Delta$) achieved the best empirical error compared to slack-rescaling ($S$) and a standard 0-1 loss SVM.
  • Scalability and Efficiency: Experiments on a large face track dataset showed that their convex surrogate operator ($B\Delta$) achieved convergence rates comparable to SVMs, demonstrating its efficiency and scalability for large-scale problems.
  • Tighter Surrogate: They proved that their surrogate ($B\Delta$) is a tighter approximation to the convex closure of the loss function than slack-rescaling.
  • Generalization: $B\Delta$ generalizes the Lovász hinge and is proven to be convex, piecewise linear, and an extension of the original loss.
  • Polynomial-Time Subgradients: Crucially, subgradient computation for $B\Delta$ is polynomial time, making it practical for optimization.

Limitations and Future Work

  • Decomposition Algorithm: While the paper proves the existence and uniqueness of the canonical decomposition, the direct computation of the decomposition operator $D$ is framed as a linear program, which can be computationally expensive for very large sets. The authors note that for specific types of set functions (e.g., symmetric ones), the LP complexity can be reduced.
  • Non-Negative Submodular Component: The paper highlights that the most significant performance gains were observed when the submodular component of the decomposition was non-negative. Characterizing and understanding loss functions where this holds true is suggested as a promising avenue for future research.
  • Broader Applicability: The authors suggest that their convex surrogate operator could be integrated with other optimization techniques like stochastic gradient descent or Frank-Wolfe, and extended to other function classes such as neural networks.

Summary updated

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 can only tightly bound modular loss functions, sub-modular functions or supermodular functions separately while maintaining polynomial time computation. In this work, a novel generic convex surrogate for general non-modular loss functions is introduced, which provides for the first time a tractable solution for loss functions that are neither super-modular nor submodular. This convex surro-gate is based on a submodular-supermodular decomposition for which the existence and uniqueness is proven in this paper. It takes the sum of two convex surrogates that separately bound the supermodular component and the submodular component using slack-rescaling and the Lov{\'a}sz hinge, respectively. It is further proven that this surrogate is convex , piecewise linear, an extension of the loss function, and for which subgradient computation is polynomial time. Empirical results are reported on a non-submodular loss based on the S{{\o}}rensen-Dice difference function, and a real-world face track dataset with tens of thousands of frames, demonstrating the improved performance, efficiency, and scalabil-ity of the novel convex surrogate.
BibTeX
@inproceedings{yu2016convex,
  author = {Jiaqian Yu and Matthew B. Blaschko},
  title = {{A Convex Surrogate Operator for General Non-Modular Loss Functions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=8iAcxSNAT0U},
}
Figure