Ding-Xuan Zhou

Title:  Learnability of Gaussians with Flexible Variances

Abstract:

Gaussian kernels with flexible variances provide a rich family of Mercer kernels for learning algorithms. We show that the union of the unit balls of reproducing kernel Hilbert spaces generated by Gaussian kernels with flexible variances is a uniform Glivenko-Cantelli class. This result confirms a conjecture concerning learnability of Gaussian kernels and verifies the uniform convergence of many learning algorithms involving Gaussians with changing variances. Rademacher averages and empirical covering numbers are used to estimate sample errors of multi-kernel regularization schemes associated with general loss functions. It is then shown that the regularization error associated with the least square loss and the Gaussian kernels can be greatly improved when flexible variances are allowed. Finally for regularization schemes generated by Gaussian kernels with flexible variances we present explicit learning rates of the regression with the least square loss and the classification with the hinge loss. Extensions to manifold and Markov sampling settings will also be discussed.