Research map / Learning theory and algorithms / Sample complexity
Batch List-Decodable Linear Regression via Higher Moments
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 a polynomial-time SoS-based algorithm for list-decodable linear regression with batches that works at smaller batch sizes n=Õ(α^{-δ}) and achieves error O(α^{-δ/2}/√n) with an O(1/α)-sized list, using an iterative residual-regression scheme, an SoS Marcinkiewicz-Zygmund inequality, and a cross-candidate pruning step.
Problem
List-decodable linear regression from batches where most batches are adversarial: achieving a small list containing an accurate regressor requires batch sizes of order 1/α in prior work with error O(σ/√(αn)).
Approach
Uses higher-order moments of the batch-averaged estimator Z_B = (1/n)Σ yX, certified via an SoS version of the Marcinkiewicz-Zygmund inequality, to feed an SoS list-decodable mean estimator; iterates by regressing residuals y - β^T X over a list and prunes the list with a cross-candidate consistency test.
Key results
- Achieves batch size n=O(k^2 Q^{2/k} α^{-6/k}) for any integer k, with error O(kQ^{1/k} σ α^{-3/k}/√n) and an O(1/α)-sized list, versus n=Ω(1/α) and error O(σ/√(αn)) in prior work.
- Total batches m = Õ(((kd)^{O(k)}/α + α^{-3}) log(R/σ)), polynomial time.
- Gives an SoS proof of the Marcinkiewicz-Zygmund inequality.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use higher-moment SoS information with the iterative batch algorithm | List-decodable linear regression with batches · List-decodable linear regression with batches | minimum batch size: n=\Omega(1/\alpha) -> n=O(k^2 Q^{2/k} \alpha^{-6/k}) | Helped |
| Use higher-moment SoS information with the iterative batch algorithm | List-decodable linear regression with batches · List-decodable linear regression with batches | estimation error: O(\sigma/\sqrt{\alpha n}) -> O \left( kQ^{1/k} \sigma \alpha^{-3/k}/\sqrt n \right) | Helped |
| Use higher-moment SoS information with the iterative batch algorithm | List-decodable linear regression with batches · List-decodable linear regression with batches | list size: O(1/\alpha^{2}) -> O(\alpha^{-1}) | Helped |
Limitations
- Requires SoS-certifiable bounds on degree-Θ(1/δ) moments of covariates, a stronger assumption than prior work.
- Runtime and sample complexity grow as (kd)^{O(k)}; reaching the lowest batch-size regime needs super-constant k and quasi-polynomial time.
- Assumes Gaussian label noise and Gaussian-like covariates such as strongly log-concave distributions.
Experimental setup
Metrics: l2 estimation error of regressor list size minimum batch size
Baselines: Das et al. 2023 batch list-decodable linear regression
Builds on: Das et al. 2023 batch list-decodable linear regression SoS list-decodable mean estimation robust linear regression iterative method
Closest papers by meaning
- Efficient List-Decodable Regression using Batches (ICML 2023 · similarity 0.94)
- Statistical Query Lower Bounds for List-Decodable Linear Regression (NeurIPS 2021 · similarity 0.89)
- List-decodable Linear Regression (NeurIPS 2019 · similarity 0.88)
- Linear Regression using Heterogeneous Data Batches (NeurIPS 2024 · similarity 0.86)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.84)
- Agnostic Sample Compression Schemes for Regression (ICML 2024 · similarity 0.82)
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.