# Near Optimal Heteroscedastic Regression with Symbiotic Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 25 Jun 2023.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Making Deep Neural Networks Robust to Label Noise: a Loss Correction Approach](https://mlsanity.com/paper/1609.03683/) (2016)
- [Orthogonal Statistical Learning](https://mlsanity.com/paper/1901.09036/) (2019)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Orthogonal Machine Learning: Power and Limitations](https://mlsanity.com/paper/1711.00342/) (2017)
- [Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow](https://mlsanity.com/paper/1506.03382/) (2015)
- [Globally-convergent Iteratively Reweighted Least Squares for Robust Regression Problems](https://mlsanity.com/paper/2006.14211/) (2020)
- [Massively Scaling Heteroscedastic Classifiers](https://mlsanity.com/paper/2301.12860/) (2023)
- [Phase Transitions for Detecting Latent Geometry in Random Graphs](https://mlsanity.com/paper/1910.14167/) (2019)
- [Coordinated Double Machine Learning](https://mlsanity.com/paper/2206.00885/) (2022)
- [Orthogonal Statistical Learning with Self-Concordant Loss](https://mlsanity.com/paper/2205.00350/) (2022)

## Built on by (most cited first, 3 of 3)

- [Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances](https://mlsanity.com/paper/2312.02417/) (2023)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [Active Query Synthesis for Preference Learning](https://mlsanity.com/paper/2605.26072/) (2026)

## Abstract (arXiv)

We consider the problem of heteroscedastic linear regression, where, given n samples (xi, yi) from yi = langle w*, xi rangle + εi · langle f*, xi rangle with xi ~ N(0,I), εi ~ N(0,1), we aim to estimate 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 w* in squared norm up to an error of tildeOleft(|f*|2 · left(frac1n + left(fracdnright)2right)right) and prove a matching lower bound (upto log factors). This represents a substantial improvement upon the previous best known upper bound of tildeOleft(|f*|2· fracdnright). Our algorithm is an alternating minimization procedure with two key subroutines 1. An adaptation of the classical weighted least squares heuristic to estimate w*, for which we provide the first non-asymptotic guarantee. 2. A nonconvex pseudogradient descent procedure for estimating 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.