Abstract
Kernel methods are prized for modeling non-linear relationships but face significant scaling challenges. While Random Fourier Features (RFFs) and the Nyström method are standard approximations, they are typically evaluated by feature count rather than memory footprint. We propose Low-Precision Random Fourier Features (LP-RFFs), demonstrating that trading numerical precision for higher-rank approximations yields superior generalization under strict memory budgets. LP-RFFs can match full-precision performance while using up to 10x less memory than standard RFFs and up to 460x less than the Nyström method.
The Memory Bottleneck in Kernel Approximation
The traditional comparison of kernel approximations focuses on the number of features ($m$). Under this metric, the Nyström method generally outperforms RFFs. However, in practical applications, the primary constraint is often the available memory (e.g., RAM).
As shown in the figure below, while Nyström is more accurate for a fixed number of features (a), RFFs actually achieve lower heldout error for a fixed memory budget (b). This discrepancy suggests that standard metrics like Frobenius or spectral norms (c, d) do not fully capture the generalization capabilities of an approximation under resource constraints.
Methods: Prioritizing Rank over Precision
The authors introduce a refined theoretical framework, the $(\Delta_1, \Delta_2)$-spectral approximation, to explain this phenomenon. They decouple approximation error into two components: $\Delta_1$, related to the rank of the approximation, and $\Delta_2$, related to noise or numerical precision. Their analysis proves that $\Delta_1$ is the dominant factor for generalization.
Consequently, it is more beneficial to have a high-rank, low-precision approximation than a low-rank, high-precision one. Low-Precision RFFs (LP-RFFs) implement this by quantizing features to low bit-widths (1 to 8 bits) using stochastic rounding. To maintain efficiency, quantization is performed "in the processor registers," ensuring that high-precision intermediate values do not consume main memory.
Empirical Results and the Failure of Standard Metrics
Evaluations on datasets like TIMIT, YearPred, and Census confirm that LP-RFFs are highly effective. A key finding is that standard error metrics often mislead. For instance, on the Census dataset, the Nyström method maintains a lower squared Frobenius norm error than RFFs, yet its generalization performance (Heldout MSE) degrades much faster as the norm increases.
Key results include:
- Memory Efficiency: LP-RFFs matched full-precision RFF accuracy with 3x to 10x less memory.
- Superiority over Nyström: LP-RFFs achieved equivalent performance with 50x to 460x less memory.
- Quantization Robustness: On TIMIT, 4-bit features were sufficient to match full-precision results, allowing for an 8x increase in feature count within the same memory footprint.
Conclusion
This work demonstrates that for kernel approximations, rank is more critical than precision. By embracing low-precision representations, LP-RFFs provide a powerful tool for scaling kernel methods to large datasets on commodity hardware. Future work includes extending these techniques to non-shift-invariant kernels and developing robust low-precision variants of the Nyström method.
Summary updated