Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

arXiv:2608.18402v1 Announce Type: cross 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 (X_i,Y_i) with labels Y_i=X_i^opeta+arepsilon_i, where arepsilon_isim N(0,sigma_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 sigma_i^2le1 (larger m is easier). We obtain a polynomial-time estimator with rate ilde{O}((nd^3/m^4)^{1/6}) when mgg d^{3/4}n^{1/4}, as well as nearly-matching lower bounds. For d=O(1), our estimator achieves error o(1) when mgg n^{1/4}, whereas L_1 regression and other traditional approaches require mgg 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 ildeTheta(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_isim N(0,I_d), m unknown samples are noiseless, and the rest have error arepsilon_isim N(0,1). We conjecture that recovering eta up to error llsqrt{d/n} (or exactly) may have an information-computation gap between m=d+1 and msim d^{3/4}n^{1/4}, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.

Source: arXiv cs.LG | 2026-08-20

Related