Sketching Datasets for Large-Scale Learning (long version)

Abstract

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.

References in corpus (9)

• The Sliding Frank-Wolfe Algorithm and its Application to Super-Resolution Microscopy
• Orthogonal Random Features
• Random Projections for $k$-means Clustering
• Orthogonal Matching Pursuit with Replacement
• The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem
• Quantized Compressive K-Means
• Breaking the waves: asymmetric random periodic features for low-bitrate kernel machines
• Compressive Learning for Semi-Parametric Models
• Compressive Classification (Machine Learning without learning)

Cited by in corpus (2)

• Asymmetric compressive learning guarantees with applications to quantized sketches
• Fitting large mixture models using stochastic component selection