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

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

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.

Comparison of RFF and Nyström approximations on the TIMIT dataset across different metrics: (a) number of features, (b) memory budget, (c) squared Frobenius norm, and (d) spectral norm.

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.

Heldout MSE vs. Squared Frobenius norm on the Census dataset, illustrating how standard norm metrics can fail to predict generalization performance.

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

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