Research map / Learning theory and algorithms / Sample complexity
Optimal Linear Regression Without a Variance
Artin Tajdini, Jasper C.H. Lee, Jonathan Scarlett, Kevin Jamieson
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a black-box reduction that turns finite-variance linear regression procedures into ones that work under only a weak (finite alpha-moment, alpha in (1,2)) noise assumption, via empirical residual pruning.
Problem
High-probability linear regression when the noise has only a finite conditional alpha-moment for unknown alpha in (1,2), so variance is infinite, and covariates may also be heavy-tailed.
Approach
A black-box reduction based on empirical residual pruning converts any finite-variance regression procedure into a weak-moment procedure, agnostic to the unknown alpha.
Closest papers by meaning
- Efficient algorithms for linear regression with heteroskedastic errors (NeurIPS 2026 · similarity 0.88)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.88)
- Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (JMLR 2017 · similarity 0.87)
- Efficient Truncated Linear Regression with Unknown Noise Variance (NeurIPS 2021 · similarity 0.86)
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination (NeurIPS 2025 · similarity 0.86)
- Regularized least squares learning with heavy-tailed noise is minimax optimal (NeurIPS 2025 · similarity 0.85)
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.
