Research map / Learning theory and algorithms / Sample complexity
Coresets for Multiple $\ell_p$ 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.
Constructs coresets of size independent of the number of responses m for multiple lp regression (strong and weak), via a partition-by-sensitivity Lewis-weight sampling argument, and applies them to Euclidean power means and spanning coresets for lp subspace approximation.
Problem
Coresets for multiple lp regression with m response vectors typically need size growing with m (log m or linear in m) for strong coresets; it is unknown whether size can be made independent of m.
Approach
Generalize the active lp regression "partition by sensitivity" argument to multiple scales and remove the m-dependence by allowing a small failure rate per column and handling the few bad columns via Markov's inequality and the subspace embedding property; for weak coresets with embedding G, use iterative closeness-of-solutions argument.
Key results
- Strong coresets of size O~(eps^-2 d) for 1<=p<2 and O~(eps^-p d^{p/2}) for p>2, independent of m, with matching lower bound Omega(eps^-p d^{p/2}) for p>2.
- Weak coresets of size O~(eps^-1 d) for 1<p<2 (nearly tight, matching Omega(d/eps) from spanning coreset lower bound), and O~(eps^{1-p} d^{p/2}) for p>2.
- Euclidean power means: uniform sample of Theta~(eps^-2), Theta~(eps^-1), Theta~(eps^{1-p}) for p=1, 1<p<2, p>2 respectively; spanning coresets of size O~(eps^-1 k) for 1<p<2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Construct a strong coreset independently of the number of responses | Multiple ℓp regression, p < 2 · Multiple ℓp regression | sample complexity: \tilde O(\varepsilon^{-2}d) | Helped |
| Construct a strong coreset independently of the number of responses | Multiple ℓp regression, p > 2 · Multiple ℓp regression | sample complexity: \tilde O(\varepsilon^{-p}d^{p/2}) | Helped |
| Use a weak coreset for multiple responses with an embedding | Multiple ℓp regression · Multiple ℓp regression with embedding | sample complexity: \frac{O(d)}{\eps \delta^2}\bracks*{(\log d)^2\log \frac{d}{\eps} + \log\frac{1}{\delta}}\parens*{\log\log\frac1\eps}^2 | Helped |
| Use uniform sampling with the proposed power-means algorithm | Euclidean power means, p = 1 · Euclidean power means | uniform sample complexity: \tilde\Theta(\varepsilon^{-2}) | Helped |
| Use uniform sampling with the proposed power-means algorithm | Euclidean power means, 1 < p < 2 · Euclidean power means | uniform sample complexity: \tilde\Theta(\varepsilon^{-1}) | Helped |
| Use uniform sampling with the proposed power-means algorithm | Euclidean power means, p > 2 · Euclidean power means | uniform sample complexity: \tilde\Theta(\varepsilon^{1-p}) | Helped |
| Use the proposed spanning coreset construction | ℓp subspace approximation, 1 < p < 2 · ℓp subspace approximation | coreset size: \tilde O(\eps^{-1}k) | Helped |
| Use the proposed spanning coreset construction instead of the previous best bound | ℓp subspace approximation, 1 ≤ p < 4 · ℓp subspace approximation | coreset size: O(\eps^{-1} k^2 \log(k/\eps)) | Helped |
Surprising findings
- For p>2, multiple lp regression is provably harder than single-response regression for strong coresets (lower bound eps^-p d^{p/2} exceeds the single-response eps^-2 d^{p/2} separation only in eps-dependence).
Limitations
- Weak coreset bounds have polynomial dependence on failure probability delta unless additional assumptions hold.
- Strong coreset bound for p>2 has a gap between upper bound eps^-2 d^{p/2} and lower bound eps^-p d^{p/2}.
- Spanning coreset for p>2 remains open, with a gap to the lower bound.
Experimental setup
Metrics: sample complexity (number of nonzero rows of sampling matrix
Baselines: Lewis weight sampling active lp regression coresets uniform sampling for Euclidean power means
Builds on: Lewis weight sampling active lp regression Dvoretzky's theorem
Closest papers by meaning
- Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.85)
- Robust Sparsification via Sensitivity (ICML 2025 · similarity 0.85)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.84)
- The Space Complexity of Approximating Logistic Loss (NeurIPS 2024 · similarity 0.84)
- Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.83)
- High-Dimensional Geometric Streaming for Nearly Low Rank Data (ICML 2024 · 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.