Kernel methods, such as Support Vector Machines (SVMs), are incredibly powerful tools for non-linear machine learning. However, they suffer from a well-known "scaling wall": their computational complexity grows quadratically or even cubically with the number of training examples. This makes them impractical for modern datasets containing millions of points.
To circumvent this, researchers often use explicit feature maps. These maps transform data into a new, lower-dimensional space where a simple linear model can mimic the behavior of a complex kernel. While effective for some kernels, deriving compact maps for polynomial kernels—which are widely used in computer vision and natural language processing—remains a significant challenge.
Existing approximation techniques, like Random Maclaurin and Tensor Sketch, have notable drawbacks. They often require a massive number of dimensions to be accurate, suffer from high variance, or produce "rank-deficient" features where many of the new dimensions are highly correlated and redundant.
Researchers from Google noticed a specific gap in the literature: in practice, polynomial kernels are almost always applied to data that has been normalized to a unit sphere (unit $\ell_2$ norm). This led to a compelling question: If we know the data is on a sphere, can we build a better, more compact feature map?
The answer is yes, and it comes in the form of Spherical Random Fourier (SRF) features.
The Mathematical Obstruction and the SRF Solution
The standard tool for building explicit feature maps is Random Fourier Features (RFF), which relies on Bochner’s Theorem. This theorem states that a shift-invariant kernel is the Fourier transform of a probability distribution. By finding that distribution, you can sample from it to create your feature map.
However, the authors identified a mathematical obstruction: even though polynomial kernels on a sphere appear shift-invariant, their Fourier transforms can yield negative values. Because a valid probability distribution cannot have negative probabilities, Bochner’s Theorem cannot be applied directly.
To solve this, the authors developed the SRF approximation paradigm:
- Gaussian Approximation: They first approximate the polynomial kernel as a weighted sum of Gaussians.
- Positive Projection: To address the "negative probability" problem, they take the Fourier transform and simply clip any negative values to zero (a
max(0, ...)operation). - Numerical Integration: Because this clipped version lacks a simple closed-form formula, they use 1D numerical integration to find the optimal sampling distribution.
- Monte Carlo Sampling: Finally, they sample random frequencies from this new distribution to construct the compact feature map.
Key Insights: Breaking the Scaling Wall
The SRF approach yields several remarkable theoretical and practical insights:
- The "Higher is Better" Paradox: In most numerical approximations, higher-order terms (e.g., $x^{10}$ vs $x^2$) are notoriously harder to estimate. Remarkably, the authors prove that the error bound for SRF decays at a rate of $O(p^{-2.5})$. This means the approximation actually gets more accurate as the polynomial degree ($p$) increases.
- Computational Decoupling: The computational cost of generating SRF features does not depend on the polynomial degree $p$. This makes it significantly faster than methods like Tensor Sketch when dealing with high-order polynomials.
- Breaking Rank Deficiency: As shown in the figure above, previous methods often produce features that are highly correlated (low eigenvalue ratio). SRF features are much more diverse (higher rank), allowing them to achieve better classification accuracy with fewer dimensions.
Experimental Results
The authors evaluated SRF against state-of-the-art methods across several datasets, including USPS, Gisette, Adult, and the massive-scale ImageNet 2012 dataset.
Across the board, SRF consistently achieved lower Mean Squared Error (MSE) in kernel approximation compared to Random Maclaurin and Tensor Sketch. Furthermore, the variance in the approximation error was much lower for SRF, leading to more stable and reliable predictions.
Crucially, SRF was successfully scaled to ImageNet using a doubly stochastic gradient approach, achieving a Top-1 error of 44.4%. This proves that the unit-norm restriction does not hinder performance on real-world, large-scale tasks.
Limitations and Future Directions
While highly effective, the method is strictly designed for data on the unit sphere. If the magnitude (norm) of the data carries critical information, the authors suggest adding it back as an extra feature prior to normalization. Additionally, because of the frequency-domain clipping step, the resulting kernel requires a one-time numerical integration step rather than a neat analytical formula.
Looking forward, the authors suggest exploring adaptive sampling, where the distribution of the random features is dynamically tuned based on the actual distribution of the training data, potentially leading to even more compact and powerful feature maps.
Summary updated