  Kernel method has been developed as one of the standard approaches for
nonlinear learning, which however, does not scale to large data set due to its
quadratic complexity in the number of samples. A number of kernel approximation
methods have thus been proposed in the recent years, among which the random
features method gains much popularity due to its simplicity and direct
reduction of nonlinear problem to a linear one. The Random Binning (RB)
feature, proposed in the first random-feature paper \cite{rahimi2007random},
has drawn much less attention than the Random Fourier (RF) feature. In this
work, we observe that the RB features, with right choice of optimization
solver, could be orders-of-magnitude more efficient than other random features
and kernel approximation methods under the same requirement of accuracy. We
thus propose the first analysis of RB from the perspective of optimization,
which by interpreting RB as a Randomized Block Coordinate Descent in the
infinite-dimensional space, gives a faster convergence rate compared to that of
other random features. In particular, we show that by drawing $R$ random grids
with at least $\kappa$ number of non-empty bins per grid in expectation, RB
method achieves a convergence rate of $O(1/(\kappa R))$, which not only
sharpens its $O(1/\sqrt{R})$ rate from Monte Carlo analysis, but also shows a
$\kappa$ times speedup over other random features under the same analysis
framework. In addition, we demonstrate another advantage of RB in the
L1-regularized setting, where unlike other random features, a RB-based
Coordinate Descent solver can be parallelized with guaranteed speedup
proportional to $\kappa$. Our extensive experiments demonstrate the superior
performance of the RB features over other random features and kernel
approximation methods. Our code and data is available at {
\url{https://github.com/teddylfwu/RB_GEN}}.
