| The emergence of a new paradigm in machine learning known as semi-supervised learning (SSL) has seen benefits to many applications where labeled data is expensive to obtain. However, unlike supervised learning (SL), which enjoys a rich and deep theoretical foundation, semi-supervised learning, which uses additional unlabeled data for training, still remains a theoretical mystery lacking a sound fundamental understanding. The purpose of this research thesis is to take a first step towards bridging this theory-practice gap.;Roughly, our conclusion is that unless the learner is absolutely certain there is some non-trivial relationship between labels and the unlabeled distribution ("SSL type assumption"), semi-supervised learning cannot provide significant advantages over supervised learning. Technically speaking, we show that the sample complexity of SSL is no more than a constant factor better than SL for any unlabeled distribution, under a no-prior-knowledge setting (i.e. without SSL type assumptions).;We prove that for the class of thresholds in the realizable setting the sample complexity of SL is at most twice that of SSL. Also, we prove that in the agnostic setting for the classes of thresholds and union of intervals the sample complexity of SL is at most a constant factor larger than that of SSL. We conjecture this to be a general phenomenon applying to any hypothesis class.;We also discuss issues regarding SSL type assumptions, and in particular the popular cluster assumption. We give examples that show even in the most accommodating circumstances, learning under the cluster assumption can be hazardous and lead to prediction performance much worse than simply ignoring unlabeled data and doing supervised learning.;We focus on investigating the inherent limitations of the benefits semi-supervised learning can provide over supervised learning. We develop a framework under which one can analyze the potential benefits, as measured by the sample complexity of semi-supervised learning. Our framework is utopian in the sense that a semi-supervised algorithm trains on a labeled sample and an unlabeled distribution, as opposed to an unlabeled sample in the usual semi-supervised model. Thus, any lower bound on the sample complexity of semi-supervised learning in this model implies lower bounds in the usual model.;This thesis concludes with a look into future research directions that builds on our investigation. |
