  We consider the problem of heteroscedastic linear regression, where, given
$n$ samples $(\mathbf{x}_i, y_i)$ from $y_i = \langle \mathbf{w}^{*},
\mathbf{x}_i \rangle + \epsilon_i \cdot \langle \mathbf{f}^{*}, \mathbf{x}_i
\rangle$ with $\mathbf{x}_i \sim N(0,\mathbf{I})$, $\epsilon_i \sim N(0,1)$, we
aim to estimate $\mathbf{w}^{*}$. Beyond classical applications of such models
in statistics, econometrics, time series analysis etc., it is also particularly
relevant in machine learning when data is collected from multiple sources of
varying but apriori unknown quality. Our work shows that we can estimate
$\mathbf{w}^{*}$ in squared norm up to an error of
$\tilde{O}\left(\|\mathbf{f}^{*}\|^2 \cdot \left(\frac{1}{n} +
\left(\frac{d}{n}\right)^2\right)\right)$ and prove a matching lower bound
(upto log factors). This represents a substantial improvement upon the previous
best known upper bound of $\tilde{O}\left(\|\mathbf{f}^{*}\|^2\cdot
\frac{d}{n}\right)$. Our algorithm is an alternating minimization procedure
with two key subroutines 1. An adaptation of the classical weighted least
squares heuristic to estimate $\mathbf{w}^{*}$, for which we provide the first
non-asymptotic guarantee. 2. A nonconvex pseudogradient descent procedure for
estimating $\mathbf{f}^{*}$ inspired by phase retrieval. As corollaries, we
obtain fast non-asymptotic rates for two important problems, linear regression
with multiplicative noise and phase retrieval with multiplicative noise, both
of which are of independent interest. Beyond this, the proof of our lower
bound, which involves a novel adaptation of LeCam's method for handling
infinite mutual information quantities (thereby preventing a direct application
of standard techniques like Fano's method), could also be of broader interest
for establishing lower bounds for other heteroscedastic or heavy-tailed
statistical problems.
