# Sketching Datasets for Large-Scale Learning (long version)

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2020.

## Built on by (most cited first, 6 of 6)

- [CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity](https://mlsanity.com/paper/2309.13307/) (2023)
- [Asymmetric compressive learning guarantees with applications to quantized sketches](https://mlsanity.com/paper/2104.10061/) (2021)
- [Fitting large mixture models using stochastic component selection](https://mlsanity.com/paper/2110.04776/) (2021)
- [Batch-less stochastic gradient descent for compressive learning of deep regularization for image denoising](https://mlsanity.com/paper/2310.03085/) (2023)
- [Effective regions and kernels in continuous sparse regularisation, with application to sketched mixtures](https://mlsanity.com/paper/2507.08444/) (2025)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)

## Abstract (arXiv)

This article considers "compressive learning," an approach to large-scale machine learning where datasets are massively compressed before learning (e.g., clustering, classification, or regression) is performed. In particular, a "sketch" is first constructed by computing carefully chosen nonlinear random features (e.g., random Fourier features) and averaging them over the whole dataset. Parameters are then learned from the sketch, without access to the original dataset. This article surveys the current state-of-the-art in compressive learning, including the main concepts and algorithms, their connections with established signal-processing methods, existing theoretical guarantees -- on both information preservation and privacy preservation, and important open problems.