  We study the theoretical properties of random Fourier features classification
with Lipschitz continuous loss functions such as support vector machine and
logistic regression. Utilizing the regularity condition, we show for the first
time that random Fourier features classification can achieve $O(1/\sqrt{n})$
learning rate with only $\Omega(\sqrt{n} \log n)$ features, as opposed to
$\Omega(n)$ features suggested by previous results. Our study covers the
standard feature sampling method for which we reduce the number of features
required, as well as a problem-dependent sampling method which further reduces
the number of features while still keeping the optimal generalization property.
Moreover, we prove that the random Fourier features classification can obtain a
fast $O(1/n)$ learning rate for both sampling schemes under Massart's low noise
assumption. Our results demonstrate the potential effectiveness of random
Fourier features approximation in reducing the computational complexity
(roughly from $O(n^3)$ in time and $O(n^2)$ in space to $O(n^2)$ and
$O(n\sqrt{n})$ respectively) without having to trade-off the statistical
prediction accuracy. In addition, the achieved trade-off in our analysis is at
least the same as the optimal results in the literature under the worst case
scenario and significantly improves the optimal results under benign regularity
conditions.
