Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

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^\topβ+\varepsilon_i, where \varepsilon_i\sim 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\le1 (larger m is easier). We obtain a polynomial-time estimator with rate \tilde{O}((nd^3/m^4)^{1/6}) when m\gg d^{3/4}n^{1/4}, as well as nearly-matching lower bounds. For d=O(1), our estimator achieves error o(1) when m\gg n^{1/4}, whereas L_1 regression and other traditional approaches require m\gg 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 \tildeΘ(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\sim N(0,I_d), m unknown samples are noiseless, and the rest have error \varepsilon_i\sim N(0,1). We conjecture that recovering β up to error \ll\sqrt{d/n} (or exactly) may have an information-computation gap between m=d+1 and m\sim d^{3/4}n^{1/4}, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.