Research map / Learning theory and algorithms / Kernels and regression theory
A Unified Framework for Learning with Nonlinear Model Classes from Arbitrary Linear Samples
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a unified learning framework for arbitrary nonlinear model classes from general random linear measurements, with sample complexity governed by model-class variation and entropy integrals, recovering compressed sensing and generative-model results.
Problem
Learning an unknown object in a Hilbert space from random linear measurements using a nonlinear model class, with guarantees on how much data is needed as a function of the model class and sampling distributions.
Approach
Introduces the variation of a model class relative to a distribution of sampling operators; combined with entropy integrals of the model's complexity, it yields near-optimal sample complexity bounds for empirical least squares with arbitrary linear measurements (possibly vector-valued, multimodal, nondegenerate rather than isotropic), and gives the first guarantees for arbitrary Lipschitz generati
Key results
- Main theorem: with m ≳ Φ(S(ΔU); Ā)·[(entropy integral)^2 + log(2/ε)] measurements, E||x−x̌||² ≲ inf_u ||x−u||² + θ²ε + γ²/α + ||e||²/α (up to β/α factor on the approximation term).
- For sparse vectors under isotropic sampling, the framework recovers the m ≳ μ(A)·s·(polylog) measurement condition, with the union-of-subspaces corollary reducing quadratic s-scaling to near-linear.
- For generative models, the paper gives the first recovery guarantees for arbitrary Lipschitz (positively homogeneous) maps with general measurements, with measurement condition linear in latent dimension k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the convex-hull assumption (iii) with a suitable finite set W | Compressed sensing with isotropic vectors · Sparse recovery | measurement condition dependence on sparsity s: quadratically in s -> linearly in s | Helped |
Limitations
- Entropy integrals are not explicit for general model classes and must be estimated case by case.
- Crude worst-case bounds depend on ambient dimension N rather than intrinsic complexity.
- Guarantees are local to a chosen point x*, and some bounds require a truncated estimator (θ-truncation).
Experimental setup
Metrics: expected squared recovery error sample complexity
Builds on: compressed sensing with isotropic vectors compressed sensing with generative models leverage score sampling Christoffel sampling
Closest papers by meaning
- Compressed Sensing using Generative Models (ICML 2017 · similarity 0.88)
- On the Power of Compressed Sensing with Generative Models (ICML 2020 · similarity 0.87)
- Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples (ICML 2024 · similarity 0.86)
- Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data (ICLR 2024 · similarity 0.85)
- On the Benefits of Active Data Collection in Operator Learning (ICML 2025 · similarity 0.84)
- Improved Active Learning via Dependent Leverage Score Sampling (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.