Semi-Supervised Learning.pdf

Semi-supervised learning algorithms utilize unlabeled data to improve learning performance. Under certain conditions, unlabeled data is equally useful as labeled data in terms of learning rate. The learning rate of semi-supervised learning scales as O(1/n) if the number of unlabeled data (m) is comparable to the number of labeled data (n), and scales as O(1/n^1+γ) if m is larger than n by a factor of n^γ for some γ > 0. In contrast, the learning rate of supervised learning scales as O(1/n).

The paper provides an upper bound on the excess risk characterized by a conditional mutual information term, and obtains the learning rate of supervised and semi-supervised learning problems. The results show that under appropriate conditions, unlabeled data is equally useful as labeled data in terms of convergence rate. A lower bound on the learning rate of supervised learning algorithms is also given, showing that the characterization of the learning rate is tight.

The problem is formulated as a universal prediction problem, where the goal is to design a universal predictor that performs well in the absence of exact knowledge of the distribution. The paper assumes that the data-generating distribution is not exactly known except that it comes from a parameterized family. The main contributions include providing an upper bound on the excess risk, obtaining the learning rate of supervised and semi-supervised learning problems, and giving a lower bound on the learning rate of supervised learning algorithms.

The learning scenarios considered are supervised learning and semi-supervised learning (SSL). In supervised learning, the hypothesis is generated by labeled data, while in SSL, the hypothesis is generated by both labeled and unlabeled data. The optimal expected excess risk is defined for both scenarios, and the paper assumes that the density function does not depend on the number of samples. The results are stated for a given true parameter θ0, and it is noted that similar results can be derived within a minimax problem formulation.