Sharp Analysis of Random Fourier Features in Classification

Zhu Li

TL;DR

Random Fourier Features (RFFs) are a popular way to make powerful kernel-based machine learning models run faster, but theoretical work previously suggested you needed as many features as data points to maintain accuracy. This paper proves that for classification tasks, you can actually achieve optimal accuracy with significantly fewer features—specifically $O(\sqrt{n} \log n)$ instead of $O(n)$—leading to massive savings in both time and memory.

What Problem Does This Paper Address?

Kernel methods (like Support Vector Machines) are beloved for their ability to model complex, non-linear relationships with strong theoretical guarantees. The catch? They don't scale. A standard kernel algorithm requires $O(n^3)$ computation time and $O(n^2)$ memory, where $n$ is the number of training samples. For a million data points, that’s a non-starter.

Random Fourier Features (RFFs) were proposed to solve this by approximating the "infinite-dimensional" kernel map with a finite, $s$-dimensional feature map. This turns a slow kernel problem into a fast linear one. However, a major theoretical gap remained: researchers couldn't prove that RFFs worked well in classification unless the number of features ($s$) was nearly as large as the number of data points ($n$). If $s \approx n$, the computational "savings" vanish. This paper aims to prove that we can have our cake and eat it too: high accuracy with low $s$.

Methods

The author provides a "sharp" (mathematically tight) analysis of RFFs specifically for classification using Lipschitz continuous loss functions (like the hinge loss in SVMs or logistic loss).

The study focuses on two main sampling strategies:

  1. Plain RFF: Sampling features directly from the kernel's spectral measure (the standard approach).
  2. Leverage Weighted RFF: A more sophisticated "problem-dependent" sampling method that uses ridge leverage scores to pick the most informative features.

The key mathematical "lever" used in this paper is the regularity condition. This condition describes how "smooth" the target function is relative to the kernel. By incorporating this into the analysis, the author is able to provide much more optimistic bounds on the number of features required compared to previous "worst-case" analyses.

Datasets

This is a purely theoretical paper. It does not use empirical datasets or benchmarks. Instead, it provides mathematical proofs that hold true across any dataset that satisfies certain general assumptions (like the regularity of the kernel and the noise level of the labels).

Key Insights and Ideas

  • The Regularity Breakthrough: Previous bounds for classification were pessimistic because they didn't account for the "regularity" or smoothness of the underlying problem. By assuming the target function belongs to a specific range of the integral operator (Assumption A.3), the author shows that the "bias" of the RFF approximation decays much faster than previously thought.
  • Breaking the $O(n)$ Barrier: For the first time, this work proves that for a wide range of benign conditions, RFF classification achieves the minimax optimal learning rate of $O(1/\sqrt{n})$ using only $\Omega(\sqrt{n} \log n)$ features.
  • Fast Rates are Possible: Under "Massart’s low noise assumption" (where the two classes are well-separated), the paper proves RFFs can achieve a "fast" learning rate of $O(1/n)$.
  • Dimension Independence: Unlike some previous works that suffered from the "curse of dimensionality," these results depend on the effective dimension (the decay of the kernel's eigenvalues) rather than the raw input dimension $d$.

Key Results

The paper's findings are summarized in a series of comparisons against prior state-of-the-art (SOTA) results:

  • Computational Speedup: The analysis shows that RFFs can reduce time complexity from $O(n^3)$ to $O(n^2)$ and space complexity from $O(n^2)$ to $O(n\sqrt{n})$ without any loss in statistical accuracy.
  • Feature Efficiency: In the "benign" case (smooth functions), the required number of features is reduced from $O(n)$ to $O(\sqrt{n} \log n)$.
  • Dominating Prior Work: Tables 1 and 2 in the paper show that this new analysis strictly improves upon previous bounds (e.g., Li et al. 2021 and Sun 2018) across various scenarios, including finite rank, exponential decay, and polynomial decay of the kernel's spectrum.

Limitations and Future Work

  • The Worst-Case Scenario: The author acknowledges that if the problem is highly "irregular" (the regularity parameter $r = 1/2$), the analysis reverts to the old $O(n)$ feature requirement. In these "worst-case" scenarios, RFFs might not provide significant computational gains.
  • Computing Leverage Scores: While leverage-weighted RFFs are more efficient in terms of the number of features, calculating the leverage scores themselves can be computationally expensive ($O(n^3)$). The author notes that finding ways to efficiently approximate these scores is a vital direction for future research.
  • Closing the Gap: There is still a slight gap in the "worst-case" analysis for classification compared to regression; the author suggests that finding a way to obtain a sharper result for the $r=1/2$ case is an interesting open problem.

Summary updated

Abstract

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 $Ω(\sqrt{n} \log n)$ features, as opposed to $Ω(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.
BibTeX
@inproceedings{li2022sharp,
  author = {Zhu Li},
  title = {{Sharp Analysis of Random Fourier Features in Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i7.20708},
}
Figure