Spherical Random Features for Polynomial Kernels

Jeffrey Pennington, Felix X. Yu, Sanjiv KumarNeurIPS 2015 · OpenReview

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:

  1. Gaussian Approximation: They first approximate the polynomial kernel as a weighted sum of Gaussians.
  2. 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).
  3. Numerical Integration: Because this clipped version lacks a simple closed-form formula, they use 1D numerical integration to find the optimal sampling distribution.
  4. 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.
Comparison of eigenvalue ratios, MSE, and classification accuracy. SRF exhibits less rank deficiency and higher accuracy at lower dimensions.
  • 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.

Mean Squared Error comparison across different polynomial degrees (p=3, 7, 10, 20). SRF consistently demonstrates lower error and variance.

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

Abstract

Compact explicit feature maps provide a practical framework to scale kernel methods to large-scale learning, but deriving such maps for many types of kernels remains a challenging open problem. Among the commonly used kernels for nonlinear classification are polynomial kernels, for which low approximation error has thus far necessitated explicit feature maps of large dimensionality, especially for higher-order polynomials. Meanwhile, because polynomial kernels are unbounded, they are frequently applied to data that has been normalized to unit l2 norm. The question we address in this work is: if we know a priori that data is so normalized, can we devise a more compact map? We show that a putative affirmative answer to this question based on Random Fourier Features is impossible in this setting, and introduce a new approximation paradigm, Spherical Random Fourier (SRF) features, which circumvents these issues and delivers a compact approximation to polynomial kernels for data on the unit sphere. Compared to prior work, SRF features are less rank-deficient, more compact, and achieve better kernel approximation, especially for higher-order polynomials. The resulting predictions have lower variance and typically yield better classification accuracy.
BibTeX
@inproceedings{pennington2015spherical,
  author = {Jeffrey Pennington and Felix X. Yu and Sanjiv Kumar},
  title = {{Spherical Random Features for Polynomial Kernels}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HJVX3UZOZB},
}
Figure