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.
greedy algorithm semi-supervised learning sparse data-dependent hypothesis space generalization error