The Pessimistic Limits and Possibilities of Margin-based Losses in Semi-supervised Learning

Jesse H. Krijthe, Marco LoogNeurIPS 2018 · OpenReview

Introduction

Semi-supervised learning (SSL) is often viewed as the "free lunch" of machine learning: it leverages a small amount of labeled data alongside a mountain of unlabeled data to build a better model. While SSL frequently works wonders in domains like computer vision and natural language processing, it has a well-known dark side—sometimes, incorporating unlabeled data actually decreases performance compared to using the labeled data alone.

For practitioners, this lack of reliability is a major hurdle. The ideal scenario is a "safe" SSL algorithm that is mathematically guaranteed to perform at least as well as its purely supervised counterpart, regardless of the underlying ground-truth labels of the unlabeled data. This paper investigates a fundamental theoretical question: For which types of loss functions can we build such a "safe" learner without relying on restrictive assumptions about the data distribution?

The authors prove a sobering reality: for many common "decreasing" loss functions (like those used in Logistic Regression or Support Vector Machines), it is mathematically impossible to guarantee that SSL will outperform a simple supervised baseline in a worst-case scenario. However, they also reveal that "non-monotonic" losses—such as the quadratic loss—do allow for guaranteed, safe improvements.

Methodology

As a theoretical study, the authors analyze binary linear classifiers within the framework of Empirical Risk Minimization (ERM). They focus specifically on margin-based surrogate losses, which are functions that penalize the model based on the product of the true label and the prediction ($yx^\top w$).

Key components of their analytical framework include:

  • The Pessimistic Criterion: Safety is defined as a minimax problem. A semi-supervised solution is considered "safe" only if its loss is lower than or equal to the supervised solution's loss for every possible labeling of the unlabeled data.
  • Transductive Setting: The evaluation focuses on the specific set of labeled and unlabeled data at hand, rather than the general population risk.
  • Responsibility Analysis: The authors examine "responsibilities" ($q$), which act as soft assignments of labels to unlabeled points. They investigate whether a supervised solution can be "recovered" by choosing a specific set of responsibilities.

Key Insights

The most striking insight from the paper is that the "shape" (specifically, the monotonicity) of the loss function dictates whether safe SSL is possible.

  • Decreasing Losses (The "Bad" News): If a loss function strictly decreases as the margin increases (e.g., Logistic or Hinge loss), safe SSL is impossible. There will always be a potential adversarial labeling of the unlabeled data that makes the SSL model perform worse than the supervised baseline. The authors prove that for these losses, the supervised solution is always an "extremal" point in the set of possible semi-supervised solutions. Because it is already optimal for some potential labeling, deviating from it risks degradation.
  • Non-Monotonic Losses (The "Good" News): If the loss can increase after a certain point (e.g., Quadratic loss, which penalizes being "too correct" or over-confident), safe improvements become mathematically possible.

Key Results

The theoretical findings are formalized in three main theorems:

  • Theorems 1 & 2 (Impossibility): For any unique supervised classifier defined by a convex, strictly decreasing margin-based loss, no semi-supervised procedure can guarantee an improvement over all possible hard or soft labelings.
  • Theorem 3 (Possibility): For losses that eventually increase (like the quadratic loss), if unlabeled points fall outside the "margin" (the region where the loss starts increasing), a semi-supervised estimator can be constructed that strictly outperforms the supervised one.

Based on these theorems, common loss functions can be categorized into "Unsafe" (Logistic, Hinge, Exponential) and "Potentially Safe" (Quadratic, Absolute).

Table of common margin-based loss functions and their properties.

Limitations and Future Work

  • Linear Classifiers: The proofs center on linear models. While the core intuition may extend to complex non-linear models like deep neural networks, formal proofs for those architectures are left for future work.
  • Transductive Focus: The analysis is strictly transductive. Although this provides insights into the inductive (generalization) setting as unlabeled data grows, the two settings are not perfectly identical.
  • Strictness of Safety: The "pessimistic" definition of safety is exceptionally high. In practice, users might accept a small risk of degradation for a large expected gain. Future research could explore "relaxed" safety constraints.
  • The Quadratic Trade-off: While quadratic loss enables safe SSL, it is often considered a "worse" surrogate for classification than logistic loss in purely supervised scenarios. This creates a fascinating practical trade-off: choose a "better" loss that is unsafe, or a "worse" loss that allows for guaranteed semi-supervised gains.

Summary updated

Abstract

Consider a classification problem where we have both labeled and unlabeled data available. We show that for linear classifiers defined by convex margin-based surrogate losses that are decreasing, it is impossible to construct \emph{any} semi-supervised approach that is able to guarantee an improvement over the supervised classifier measured by this surrogate loss on the labeled and unlabeled data. For convex margin-based loss functions that also increase, we demonstrate safe improvements \emph{are} possible.
BibTeX
@inproceedings{krijthe2018pessimistic,
  author = {Jesse H. Krijthe and Marco Loog},
  title = {{The Pessimistic Limits and Possibilities of Margin-based Losses in Semi-supervised Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=BJWJouZ_-B},
}
Figure