# Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

arXiv: https://arxiv.org/abs/2608.18402 · HTML: https://mlsanity.com/paper/2608.18402/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 94 references that are in the map.
- First posted on arXiv 19 Aug 2026.

## Builds on (most cited first, 7 of 7)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Model Repair: Robust Recovery of Over-Parameterized Statistical Models](https://mlsanity.com/paper/2005.09912/) (2020)
- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [Performance of the empirical median for location estimation in heteroscedastic settings](https://mlsanity.com/paper/2501.16956/) (2025)
- [Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers](https://mlsanity.com/paper/2604.04228/) (2026)

## Abstract (arXiv)

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^topβ+varepsiloni, where varepsiloni~ 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 tildeO((nd3/m4)1/6) when mgg d3/4n1/4, as well as nearly-matching lower bounds. For d=O(1), our estimator achieves error o(1) when mgg n1/4, whereas L1 regression and other traditional approaches require mgg 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 tildeTheta(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 varepsiloni~ N(0,1). We conjecture that recovering β up to error ll√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.