Generalization Error Analysis of Quantized Compressive Learning.

Xiaoyun Li, Ping LiNeurIPS 2019 · OpenReview

Abstract

Compressive learning is an effective method to deal with very high dimensional datasets by applying learning algorithms in a randomly projected lower dimensional space. In this paper, we consider the learning problem where the projected data is further compressed by scalar quantization, which is called quantized compressive learning. Generalization error bounds are derived for three models: nearest neighbor (NN) classifier, linear classifier and least squares regression. Besides studying finite sample setting, our asymptotic analysis shows that the inner product estimators have deep connection with NN and linear classification problem through the variance of their debiased counterparts. By analyzing the extra error term brought by quantization, our results provide useful implications to the choice of quantizers in applications involving different learning tasks. Empirical study is also conducted to validate our theoretical findings.

Introduction

In the era of "big data," high-dimensional datasets with massive feature counts ($d$) present significant storage and computational hurdles. Compressive Learning mitigates these challenges by employing Random Projections (RP) to map data into a lower-dimensional space ($k \ll d$) while preserving essential geometric structures, such as distances, as guaranteed by the Johnson-Lindenstrauss Lemma.

However, practical constraints in mobile computing or privacy-preserving systems often necessitate further compression. Quantized Compressive Learning (QCL) addresses this by applying scalar quantization (e.g., 1-bit or 3-bit) to the projected values. While the effects of Random Projections are well-studied, the combined impact of projection and quantization on generalization performance remained a theoretical gap. This paper provides a rigorous analysis of QCL across three fundamental models: Nearest Neighbor (NN) classification, linear classification, and least squares regression.

Theoretical Framework: Distortion vs. Debiased Variance

The research identifies a critical divergence in quantizer requirements based on the learning task. For Least Squares Regression, performance is primarily governed by the quantizer's distortion—the proximity of the quantized value to the original. Conversely, for Classification tasks (NN and Linear), performance is driven by the debiased variance of inner product estimates.

A key technical contribution is the analysis of the "corrected" variance of estimated inner products. Because quantization introduces bias, the authors focus on the variance of debiased estimators. Their findings suggest that if a quantizer provides a stable estimate of the angle between vectors, the resulting classifier generalizes better.

Debiased variance of inner product estimators for different quantizers.

The analysis highlights the efficacy of Lloyd-Max (LM) quantizers, which are optimized to minimize distortion for a given distribution. In linear classification, LM quantizers are shown to minimize variance specifically around the decision boundary ($\rho=0$). Furthermore, while quantization introduces an additional error term in finite-sample bounds that can appear to grow with $\sqrt{k}$, asymptotic analysis confirms that total error vanishes as the number of projections $k \to \infty$.

Empirical Validation

The theoretical results were validated using high-dimensional datasets from the UCI repository, including mass spectrometry data (arcene), text categorization (BASEHOCK), and face recognition (orlraws10P).

Summary of high-dimensional datasets used for empirical validation.

Experimental results confirmed that for regression, Test Mean Squared Error (MSE) follows the order of quantizer distortion: Full-precision < 5-bit LM < 3-bit LM < 3-bit Uniform. In classification tasks, the 1-bit LM quantizer—despite being the most aggressive compression—outperformed the 3-bit uniform quantizer in high-similarity regions, validating the "debiased variance" theory.

Conclusion

This work establishes the first comprehensive theoretical foundation for Quantized Compressive Learning. By linking generalization error to quantizer properties like debiased variance and distortion, it provides actionable insights for designing efficient learning systems. Future work may extend these findings beyond the unit sphere assumption and explore non-Gaussian random projections or asymmetric quantizer designs.

Summary updated

Abstract

Compressive learning is an effective method to deal with very high dimensional datasets by applying learning algorithms in a randomly projected lower dimensional space. In this paper, we consider the learning problem where the projected data is further compressed by scalar quantization, which is called quantized compressive learning. Generalization error bounds are derived for three models: nearest neighbor (NN) classifier, linear classifier and least squares regression. Besides studying finite sample setting, our asymptotic analysis shows that the inner product estimators have deep connection with NN and linear classification problem through the variance of their debiased counterparts. By analyzing the extra error term brought by quantization, our results provide useful implications to the choice of quantizers in applications involving different learning tasks. Empirical study is also conducted to validate our theoretical findings.
BibTeX
@inproceedings{li2019generalization,
  author = {Xiaoyun Li and Ping Li},
  title = {{Generalization Error Analysis of Quantized Compressive Learning.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=y7RiZnIrdsL},
}
Figure