On partially blind learning complexity

We call a learning environment partially blind when there is an admixture of supervised and unsupervised (or blind) learning. Such situations typically arise in practice when supervised training data labelled by a teacher are scarce or expensive and are supplemented by inexpensive unlabelled (or blind) data available in relative profusion. Vapnik-Cervonenkis theory can be deployed in such settings to quantify the relative worth of supervision (and the lack thereof) in learning. We illustrate the nature of the trade-offs possible in a simple setting of hyperplane decision functions and make explicit the role of dimensionality and side-information in these trade-offs in the context of d-variate Gaussian mixtures