Sketching Datasets for Large-Scale Learning (long version)
This is an incremental survey paper that addresses the problem of handling massive datasets for researchers and practitioners in machine learning and signal processing.
The paper surveys compressive learning, an approach for large-scale machine learning where datasets are compressed into sketches using nonlinear random features before performing tasks like clustering or classification, without needing the original data. It covers concepts, algorithms, theoretical guarantees on information and privacy, and open problems, but does not present new experimental results or concrete numbers.
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.