  Large-scale kernel approximation is an important problem in machine learning
research. Approaches using random Fourier features have become increasingly
popular [Rahimi and Recht, 2007], where kernel approximation is treated as
empirical mean estimation via Monte Carlo (MC) or Quasi-Monte Carlo (QMC)
integration [Yang et al., 2014]. A limitation of the current approaches is that
all the features receive an equal weight summing to 1. In this paper, we
propose a novel shrinkage estimator from "Stein effect", which provides a
data-driven weighting strategy for random features and enjoys theoretical
justifications in terms of lowering the empirical risk. We further present an
efficient randomized algorithm for large-scale applications of the proposed
method. Our empirical results on six benchmark data sets demonstrate the
advantageous performance of this approach over representative baselines in both
kernel approximation and supervised learning tasks.
