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

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 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 are possible.

arXiv comment32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montreal, Canada

Cited by in corpus (3)

• Minimizers of the Empirical Risk and Risk Monotonicity
• Reliable Semi-Supervised Learning when Labels are Missing at Random
• Semi-supervised learning objectives as log-likelihoods in a generative model of data curation