Convergence rate of the semi-supervised greedy algorithm

This paper proposes a new greedy algorithm combining the semi-supervised learning and the sparse representation with the data-dependent hypothesis spaces. The proposed greedy algorithm is able to use a small portion of the labeled and unlabeled data to represent the target function, and to efficiently reduce the computational burden of the semi-supervised learning. We establish the estimation of the generalization error based on the empirical covering numbers. A detailed analysis shows that the error has O(n−1)O(n−1) decay. Our theoretical result illustrates that the unlabeled data is useful to improve the learning performance under mild conditions.