Gradient Descent in RKHS with Importance Labeling
arXiv:2006.10925
Abstract
Labeling cost is often expensive and is a fundamental limitation of supervised learning. In this paper, we study importance labeling problem, in which we are given many unlabeled data and select a limited number of data to be labeled from the unlabeled data, and then a learning algorithm is executed on the selected one. We propose a new importance labeling scheme that can effectively select an informative subset of unlabeled data in least squares regression in Reproducing Kernel Hilbert Spaces (RKHS). We analyze the generalization error of gradient descent combined with our labeling scheme and show that the proposed algorithm achieves the optimal rate of convergence in much wider settings and especially gives much better generalization ability in a small label noise setting than the usual uniform sampling scheme. Numerical experiments verify our theoretical findings.
arXiv comment18 pages, 14 figures
References in corpus (9)
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Generalization Properties of Learning with Random Features
- Generalization error bounds in semi-supervised classification under the cluster assumption
- Variance Reduction in SGD by Distributed Importance Sampling
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- Learning with SGD and Random Features
- Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration