Research map / Learning theory and algorithms / Sample complexity
Agnostic Sample Compression Schemes for Regression
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.
Gives the first bounded-size agnostic sample compression schemes for real-valued regression under l_p loss: approximate schemes for general classes via boosting, linear-size exact schemes for linear regression under l1 and l_inf, and an impossibility result for exact schemes with p in (1,inf).
Problem
Whether bounded-size sample compression schemes exist for agnostic real-valued regression under l_p losses, where prior work only showed negative results for exact linear regression under l_2.
Approach
A boosting-based approximate compression for general real-valued classes with cut-offs that vary per point (the pointwise loss of an optimal regressor), and for linear regression a reduction to realizable SVM classification on a discretized label grid; for l1 and l_inf, exact compression follows from LP extreme-point/support-vector arguments.
Key results
- Approximate agnostic compression for general real-valued classes of size O~((1/beta^2) fat(F,c*alpha/p) fat*(F,c*alpha/p)) for any l_p loss, independent of sample size.
- Exact agnostic compression of size d+1 for l1 linear regression and d+2 for l_inf linear regression in R^d, via linear programs.
- Approximate compression of size O(d log(p/alpha)) for bounded l_p linear regression with p in [1,inf); exact constant-size compression is impossible for p in (1,inf).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dedicated linear-regression compression construction instead of the general function-class construction | Agnostic linear regression · Agnostic ℓp linear regression, p∈[1,∞) | compression size: \mathcal{O}\lr{d^2\cdot\mathrm{Polylog}\lr{d,p,\frac{1}{\alpha}}} -> \mathcal{O}\lr{d\cdot\log\lr{\frac{p}{\alpha}}} | Helped |
| Use exact compression under ℓ₁ loss | Agnostic linear regression · Agnostic ℓ₁ linear regression | compression size: d+1 | Helped |
| Use exact compression under ℓ∞ loss | Agnostic linear regression · Agnostic ℓ∞ linear regression | compression size: d+2 | Helped |
| Require exact rather than approximate compression for ℓp linear regression with 1<p<∞ | Agnostic linear regression · Agnostic zero-dimensional linear regression, 1<p<∞ | compression size: k(m) < \log(m) | Hurt |
Surprising findings
- Exact agnostic compression exists for l1 and l_inf linear regression despite the known impossibility for l2 linear regression.
- Exact constant-size compression is impossible for every l_p loss with p in (1,inf), not just l_2.
Limitations
- General approximate compression size is exponential in the fat-shattering dimension (via dual fat-shattering bound).
- Exact impossibility proof for p in (1,inf) is only fully given for zero-dimensional regression with a bound of log(m); the stronger Omega(m) bound is left as a remark.
- Open whether l2 loss admits approximate compression of size polynomial in fat-shattering dimension.
Experimental setup
Baselines: Attias et al. (2023) exact l2 linear regression impossibility
Builds on: realizable regression boosting (weak-to-strong for l_infinity) agnostic binary classification compression fat-shattering dimension Warmuth sample compression conjecture
Closest papers by meaning
- Unlabelled Sample Compression Schemes for Intersection-Closed Classes and Extremal Classes (NeurIPS 2022 · similarity 0.88)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.84)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
- Debiased Distribution Compression (ICML 2024 · similarity 0.84)
- Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.83)
- The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm (NeurIPS 2026 · similarity 0.83)
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.