Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation

Jian Zhang, Avner May, Tri Dao, Christopher Ré

Abstract

Kernel methods are powerful tools for non-linear modeling but face significant scaling challenges on large datasets due to high memory requirements. We investigate training kernel approximation methods under strict memory budgets. By defining a refined measure of kernel approximation error, we show that generalization performance is more closely tied to the rank of the approximation than to traditional metrics like Frobenius or spectral norms. We propose Low-Precision Random Fourier Features (LP-RFFs) to build high-rank approximations within limited memory. Our results show that LP-RFFs can match the performance of full-precision methods while using 3x-10x less memory than standard RFFs and up to 460x less than the Nyström method.

The Scaling Bottleneck in Kernel Methods

Kernel methods typically require approximating the kernel matrix to handle large-scale data. Popular techniques like Random Fourier Features (RFFs) and the Nyström method are effective but introduce a memory bottleneck. Storing a high number of features (e.g., 100,000) in 32-bit floating-point precision can easily exceed the memory capacity of modern hardware.

Furthermore, researchers have traditionally evaluated these approximations using the Frobenius or spectral norms of the error matrix. This paper argues that these metrics are poor predictors of actual test performance. Instead, we propose a refined error metric based on $(\Delta_1, \Delta_2)$-spectral approximation, which highlights that generalization is primarily driven by the rank of the approximation matrix rather than its precision.

Low-Precision RFFs (LP-RFFs)

To achieve high-rank approximations without excessive memory use, we introduce LP-RFFs. By quantizing RFFs to low bit-widths (1–8 bits) using a stochastic rounding scheme, we can store significantly more features in the same memory footprint. This "noisy" but high-rank approach proves superior to "clean" but low-rank alternatives like the Nyström method.

The theoretical foundation of this work shows that quantization noise has a negligible impact on generalization as long as it remains smaller than the regularization parameter $\lambda$. Practically, features are quantized immediately upon computation in the processor registers to avoid intermediate memory bloat, allowing for massive scaling on standard hardware.

Key Results and Insights

The empirical evaluation across benchmarks like TIMIT, YearPred, and CovType demonstrates the efficiency of LP-RFFs.

Performance comparison on the TIMIT dataset across features, memory, and norm metrics.

As shown in the figures above:

  • Memory Efficiency: RFF-based methods achieve lower heldout error for a given memory budget compared to the Nyström method (Plot b).
  • Rank vs. Norm: While Nyström features often show lower error in terms of Frobenius or spectral norms (Plots c and d), they require significantly more memory to reach the same level of generalization as RFFs. This supports the "Rank > Norm" insight.
  • Optimal Precision: The best balance between feature count and precision is typically found between 2 and 8 bits under a fixed memory budget.

On the challenging TIMIT speech recognition task, LP-RFFs matched full-precision RFF performance with 10x less memory and outperformed the Nyström method by a factor of up to 460x in memory efficiency.

Conclusion

LP-RFFs provide a practical path toward scaling kernel methods to massive datasets under hardware constraints. By prioritizing rank over precision, we can achieve state-of-the-art generalization with a fraction of the memory. Future work includes hardware-level implementations to fully leverage bit-level operations and exploring low-precision quantization for other kernel approximation techniques.

Summary updated

Abstract

We investigate how to train kernel approximation methods that generalize well under a memory budget. Building on recent theoretical work, we define a measure of kernel approximation error which we find to be more predictive of the empirical generalization performance of kernel approximation methods than conventional metrics. An important consequence of this definition is that a kernel approximation matrix must be high rank to attain close approximation. Because storing a high-rank approximation is memory intensive, we propose using a low-precision quantization of random Fourier features (LP-RFFs) to build a high-rank approximation under a memory budget. Theoretically, we show quantization has a negligible effect on generalization performance in important settings. Empirically, we demonstrate across four benchmark datasets that LP-RFFs can match the performance of full-precision RFFs and the Nystr\"{o}m method, with 3x-10x and 50x-460x less memory, respectively.
BibTeX
@inproceedings{zhang2019low,
  author = {Jian Zhang and Avner May and Tri Dao and Christopher Ré},
  title = {{Low-Precision Random Fourier Features for Memory-Constrained Kernel Approximation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=PTajVq81-_M},
}
Figure