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

Overview and Recommendation: Many popular binary classifiers are defined by convex margin-based surrogate losses such as SVMs and Logistic regression. Designing a semi-supervised learning algorithm for these classifiers, that is guaranteed to improve upon the "lazy" approach of throwing away the unlabeled data and just using the labeled data while training, is of considerable interest, because of the time-consuming experimentation that the use of SSL currently requires. This paper analyzes this problem and the results presented in the paper are primarily of theoretical interest. I had great difficulty in rating the significance of this work, therefore my own confidence rating is only 3. The proofs of the theorems use elementary steps. I checked them in detail and they are correct, but, the significance of the theorems themselves was hard to measure.