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.
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