In many classication learning tasks, labeled data may be expensive or scarce. At the same time, unlabeled or \weakly labeled" samples, may be available in abundance. We consider three algorithmic paradigms that utilize unlabeled or \weakly labeled" samples to help classication tasks. On top of proposing some meta-algorithms for utilizing such samples, we analyse the sample complexity of these paradigms. We show that in some semi-supervised learning task, as well as in some domain adapta- tion and query learning tasks, unlabeled samples can be applied to provably achieve saving in the sizes of required labeled samples.