{"id":"arxiv/2608.18402","url":"https://arxiv.org/abs/2608.18402","tags":["math.ST","cs.DS","cs.LG"],"score":0,"title":"Algorithms for adaptive and heteroskedastic linear regression at the computational threshold","domain":"math.ST","source":"arxiv","authors":["Spencer Compton","Tselil Schramm"],"reviews":0,"subject":"math.ST","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}