Efficient algorithms for linear regression with heteroskedastic errors

We study the classical problem of linear regression under heteroskedastic noise, where observations arise from multiple sources with unknown and potentially unequal variances. Specifically, we consider a setting with $n$ sources, each providing a linear measurement of an unknown $d$-dimensional parameter vector ${\beta }^{\ast }$, where each source is associated with an unknown noise variance. We focus on the classic "subset-of-signals” model, where one assumes that $m$ of the sources have a relatively low noise, formally, with variance of at most 1. Our goal is to accurately estimate ${\beta }^{\text{*}}$ despite the presence of high-variance sources. We show that if $m$ is sufficiently large, it is possible to recover ${\beta }^{\ast }$ with sub-constant error. Specifically, we prove a recovery error bound of $\tilde{O}\left(\frac{\sqrt{nd}}{m}\right)$, significantly improving upon previously known results for this setting.