# A unified framework for learning with nonlinear model classes from arbitrary linear samples

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 66 references that are in the map.
- First posted on arXiv 25 Nov 2023.

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

- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Deep Neural Networks Are Effective At Learning High-Dimensional Hilbert-Valued Functions From Limited Data](https://mlsanity.com/paper/2012.06081/) (2020)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Leveraged volume sampling for linear regression](https://mlsanity.com/paper/1802.06749/) (2018)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples](https://mlsanity.com/paper/2203.13908/) (2022)
- [A coherence parameter characterizing generative compressed sensing with Fourier measurements](https://mlsanity.com/paper/2207.09340/) (2022)
- [Dimensionality reduction with subgaussian matrices: a unified theory](https://mlsanity.com/paper/1402.3973/) (2014)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Model-adapted Fourier sampling for generative compressed sensing](https://mlsanity.com/paper/2310.04984/) (2023)
- [A statistical perspective of sampling scores for linear regression](https://mlsanity.com/paper/1507.05870/) (2015)

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

- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Denoising guarantees for optimized sampling schemes in compressed sensing](https://mlsanity.com/paper/2504.01046/) (2025)
- [How many measurements are enough? Bayesian recovery in inverse problems with general distributions](https://mlsanity.com/paper/2505.10630/) (2025)
- [Infinite dimensional generative sensing](https://mlsanity.com/paper/2603.03196/) (2026)
- [Partially deterministic sampling for compressed sensing with denoising guarantees](https://mlsanity.com/paper/2604.04802/) (2026)

## Abstract (arXiv)

We study the fundamental problem of learning an unknown object from data using a prescribed model class. We introduce a unified framework that accommodates objects in arbitrary Hilbert spaces, general (possibly vector-valued) random linear measurements and general types of nonlinear models. We establish novel learning guarantees for this framework that explicitly relate the required amount of data to structural properties of the model class, yielding near-optimal generalization bounds. A central concept we introduce is the variation of a model class relative to a distribution of sampling operators, which quantifies how the model interacts with the measurement process. Combined with entropy integrals that capture the model's complexity, this forms the foundation of our guarantees. Our framework is sufficiently general to recover and unify various well-known problems, such as matrix sketching, compressed sensing with isotropic measurements and compressed sensing with generative models. In each case, existing results arise as direct corollaries of our theory. For compressed sensing with generative models, we also derive the first guarantees for arbitrary Lipschitz generative maps combined with general linear measurements. Overall, our work provides a unified perspective on learning from general data and introduces novel theoretical guarantees that consolidate, sharpen and extend existing results.