Linear Regression with Heteroskedastic Errors

Abstract

We study the classic linear regression problem under the challenging setting of heteroskedastic noise. We study a model in which we have n sources that each observe linear measurements of an unknown d-dimensional vector β. Each source has an unknown and distinct variance for the error, and the goal is to estimate the parameter vector β, under the assumption that there exist sufficiently many sources with small error (specifically, m sources have variance at most 1). Our results show that β can be estimated to sub-constant error, as long as the number of small-error sources, i.e., m, is large enough. We prove two main results. First, we show that even with just one observation per source, under minimal assumptions on the linear measurements, β can be estimated to sub-constant error when m ≥ n^1- 1/4d. Second, we show that if we have access to two observations per source, under similar assumptions on the linear measurements, β can be estimated to sub-constant error when m ≥ n^5/6. Our results are related to the recent line of work on mean estimation with heteroskedastic variances, and more specifically, the subset of signals model used in this literature. To the best of our knowledge, our results provide the first sub-constant recovery guarantees for regression in this model.