Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
Abstract
We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive n pairs (Xi,Yi) with labels Yi=Xi⊤β+εi, where εi∼ N(0,σi2) and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples m for which σi2≤1 (larger m is easier). We obtain a polynomial-time estimator with rate Õ((nd3/m4)1/6) when m≫ d3/4n1/4, as well as nearly-matching lower bounds. For d=O(1), our estimator achieves error o(1) when m≫ n1/4, whereas L1 regression and other traditional approaches require m≫ n1/2. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution p, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows p. We introduce a (computationally inefficient) adaptive estimator that, so long as p is a mixture of k symmetric log-concave densities, achieves error comparable with the optimal estimator that knows p and has Θ̃(n/k) samples. For k=1, we show that Lq regression (with data-dependent q) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where Xi∼ N(0,Id), m unknown samples are noiseless, and the rest have error εi∼ N(0,1). We conjecture that recovering β up to error ≪√(d/n) (or exactly) may have an information-computation gap between m=d+1 and m∼ d3/4n1/4, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.
Related
- On the bias distribution of pseudo-linear regression algorithms for recursive identification
- Trace-Class Results for MCMC Algorithms for Student-t Regression Models
- Dynamic-Threshold Algorithms for the Continuous Quadratic Knapsack Problem: Reset Mechanisms and Complexity
- Adaptive Bandit Algorithms for Contextual Matching Markets
- Risk Equivalence between RKHS Regression and Sequence Models for Lipschitz Spectral Algorithms
BibTeX
@misc{compton2026algorithms,
title = {{Algorithms for adaptive and heteroskedastic linear regression at the computational threshold}},
author = {Spencer Compton and Tselil Schramm},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.18402},
eprint = {2608.18402},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.18402},
}
RIS
TY - UNPB
TI - Algorithms for adaptive and heteroskedastic linear regression at the computational threshold
AU - Spencer Compton
AU - Tselil Schramm
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2608.18402
UR - https://arxiv.org/abs/2608.18402
AB - We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive n pairs (X_i,Y_i) with labels Y_i=X_i^⊤β+ε_i, where ε_i∼ N(0,σ_i^2) and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples m for which σ_i^2≤1 (larger m is easier). We obtain a polynomial-time estimator with rate Õ((nd^3/m^4)^1/6) when m≫ d^3/4n^1/4, as well as nearly-matching lower bounds. For d=O(1), our estimator achieves error o(1) when m≫ n^1/4, whereas L_1 regression and other traditional approaches require m≫ n^1/2. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution p, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows p. We introduce a (computationally inefficient) adaptive estimator that, so long as p is a mixture of k symmetric log-concave densities, achieves error comparable with the optimal estimator that knows p and has Θ̃(n/k) samples. For k=1, we show that L_q regression (with data-dependent q) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where X_i∼ N(0,I_d), m unknown samples are noiseless, and the rest have error ε_i∼ N(0,1). We conjecture that recovering β up to error ≪√(d/n) (or exactly) may have an information-computation gap between m=d+1 and m∼ d^3/4n^1/4, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.
ER -