# Asymmetric compressive learning guarantees with applications to quantized sketches

arXiv: https://arxiv.org/abs/2104.10061 · HTML: https://mlsanity.com/paper/2104.10061/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 20 Apr 2021.

## Builds on (most cited first, 13 of 13)

- [Efficient Machine Learning for Big Data: A Review](https://mlsanity.com/paper/1503.05296/) (2015)
- [Sketching for Large-Scale Learning of Mixture Models](https://mlsanity.com/paper/1606.02838/) (2016)
- [Compressive Statistical Learning with Random Feature Moments](https://mlsanity.com/paper/1706.07180/) (2017)
- [Compressive K-means](https://mlsanity.com/paper/1610.08738/) (2016)
- [Statistical Learning Guarantees for Compressive Clustering and Compressive Mixture Modeling](https://mlsanity.com/paper/2004.08085/) (2020)
- [Sketching Datasets for Large-Scale Learning (long version)](https://mlsanity.com/paper/2008.01839/) (2020)
- [Instance Optimal Decoding and the Restricted Isometry Property](https://mlsanity.com/paper/1802.09905/) (2018)
- [Quantized Compressive K-Means](https://mlsanity.com/paper/1804.10109/) (2018)
- [Signal Reconstruction from Modulo Observations](https://mlsanity.com/paper/1812.00557/) (2018)
- [Representation and Coding of Signal Geometry](https://mlsanity.com/paper/1512.07636/) (2015)
- [Compressive Learning for Semi-Parametric Models](https://mlsanity.com/paper/1910.10024/) (2019)
- [Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines](https://mlsanity.com/paper/2004.06560/) (2020)
- [Features and Kernels for Audio Event Recognition](https://mlsanity.com/paper/1607.05765/) (2016)

## Abstract (arXiv)

The compressive learning framework reduces the computational cost of training on large-scale datasets. In a sketching phase, the data is first compressed to a lightweight sketch vector, obtained by mapping the data samples through a well-chosen feature map, and averaging those contributions. In a learning phase, the desired model parameters are then extracted from this sketch by solving an optimization problem, which also involves a feature map. When the feature map is identical during the sketching and learning phases, formal statistical guarantees (excess risk bounds) have been proven. However, the desirable properties of the feature map are different during sketching and learning (e.g. quantized outputs, and differentiability, respectively). We thus study the relaxation where this map is allowed to be different for each phase. First, we prove that the existing guarantees carry over to this asymmetric scheme, up to a controlled error term, provided some Limited Projected Distortion (LPD) property holds. We then instantiate this framework to the setting of quantized sketches, by proving that the LPD indeed holds for binary sketch contributions. Finally, we further validate the approach with numerical simulations, including a large-scale application in audio event classification.