Binning in Gaussian Kernel Regularization

• Activity Number: 45
• Type: Invited
• Date/Time: Sunday, August 6, 2006 : 4:00 PM to 5:50 PM
• Sponsor: International Chinese Statistical Association
• Author(s): Bin Yu*+ and Tao Shi
• Companies: University of California, Berkeley and University of California, Berkeley

Abstract

Gaussian kernel regularization is used widely in the machine learning literature and has been proven successful in many empirical experiments. The periodic version of the Gaussian kernel regularization has been shown to be minimax rate optimal in estimating functions in any finite order Sobolev spaces. However, for a dataset with n points, the computation complexity of the Gaussian kernel regularization method is of order O(n^3). In this talk, we propose using binning to reduce the computation of Gaussian kernel regularization in both regression and classification. For the periodic Gaussian kernel regression, we show the binned estimator achieves the same minimax rates of the unbinned estimator, but the computation is reduced to O(m^3), with m as the number of bins. To achieve the minimax rate in the kth order Sobolev space, m needs to be in the order of O(kn^{1/(2k+1)}).