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

We show that for linear classifiers defined by convex marginbased surrogate losses that are monotonically 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. For non-monotonically decreasing loss functions, we demonstrate safe improvements are possible. Key words and phrases: Semi-supervised Learning, Margin-based loss, Surrogate loss, Logistic Loss, Hinge Loss, Quadratic Loss, Absolute Loss. 1. INTRODUCTION Semi-supervised learning has delivered encouraging results in various settings, e.g. for object detection in computer vision [1], protein function prediction from sequence data [2] or prediction of cancer recurrence [3] in the biomedical domain and part-of-speech tagging in natural language processing [4]. In other settings, however, using unlabeled data has been shown to lead to a decrease in performance when compared to the supervised solution [4, 5]. For semi-supervised classifiers to be used safely in practice, we may at least want some guarantee that they improve performance over their supervised alternatives.