# Mean Nystr"om Embeddings for Adaptive Compressive Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 21 Oct 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [FMA: A Dataset For Music Analysis](https://mlsanity.com/paper/1612.01840/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [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)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Instance Optimal Decoding and the Restricted Isometry Property](https://mlsanity.com/paper/1802.09905/) (2018)

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

- [Controlling Wasserstein Distances by Kernel Norms with Application to Compressive Statistical Learning](https://mlsanity.com/paper/2112.00423/) (2021)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Sketch and shift: a robust decoder for compressive clustering](https://mlsanity.com/paper/2312.09940/) (2023)
- [Compressive Meta-Learning](https://mlsanity.com/paper/2508.11090/) (2025)

## Abstract (arXiv)

Compressive learning is an approach to efficient large scale learning based on sketching an entire dataset to a single mean embedding (the sketch), i.e. a vector of generalized moments. The learning task is then approximately solved as an inverse problem using an adapted parametric model. Previous works in this context have focused on sketches obtained by averaging random features, that while universal can be poorly adapted to the problem at hand. In this paper, we propose and study the idea of performing sketching based on data-dependent Nystr"om approximation. From a theoretical perspective we prove that the excess risk can be controlled under a geometric assumption relating the parametric model used to learn from the sketch and the covariance operator associated to the task at hand. Empirically, we show for k-means clustering and Gaussian modeling that for a fixed sketch size, Nystr"om sketches indeed outperform those built with random features.