Correcting the bias in least squares regression with volume-rescaled
  sampling
  Consider linear regression where the examples are generated by an unknown
distribution on $R^d\times R$. Without any assumptions on the noise, the linear
least squares solution for any i.i.d. sample will typically be biased w.r.t.
the least squares optimum over the entire distribution. However, we show that
if an i.i.d. sample of any size k is augmented by a certain small additional
sample, then the solution of the combined sample becomes unbiased. We show this
when the additional sample consists of d points drawn jointly according to the
input distribution that is rescaled by the squared volume spanned by the
points. Furthermore, we propose algorithms to sample from this volume-rescaled
distribution when the data distribution is only known through an i.i.d sample.
