# Sample-Efficient Linear Regression with Self-Selection Bias

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 22 Feb 2024.

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

- [List-Decodable Linear Regression](https://mlsanity.com/paper/1905.05679/) (2019)
- [List Decodable Learning via Sum of Squares](https://mlsanity.com/paper/1905.04660/) (2019)
- [Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models](https://mlsanity.com/paper/2012.07774/) (2020)
- [EM Converges for a Mixture of Many Linear Regressions](https://mlsanity.com/paper/1905.12106/) (2019)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments](https://mlsanity.com/paper/1912.07629/) (2019)
- [Statistical Query Lower Bounds for List-Decodable Linear Regression](https://mlsanity.com/paper/2106.09689/) (2021)
- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [What Makes A Good Fisherman? Linear Regression under Self-Selection Bias](https://mlsanity.com/paper/2205.03246/) (2022)
- [Junta correlation is testable](https://mlsanity.com/paper/1904.04216/) (2019)
- [Max-Linear Regression by Convex Programming](https://mlsanity.com/paper/2103.07020/) (2021)
- [Estimation of Standard Auction Models](https://mlsanity.com/paper/2205.02060/) (2022)

## Abstract (arXiv)

We consider the problem of linear regression with self-selection bias in the unknown-index setting, as introduced in recent work by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [STOC 2023]. In this model, one observes m i.i.d. samples (xℓ,zℓ)ℓ=1m where zℓ=maxi∈ [k]xℓTwi+ηi,ℓ, but the maximizing index iℓ is unobserved. Here, the xℓ are assumed to be N(0,In) and the noise distribution ηℓ~ D is centered and independent of xℓ. We provide a novel and near optimally sample-efficient (in terms of k) algorithm to recover w1,ldots,wk∈ ℝn up to additive ℓ2-error varepsilon with polynomial sample complexity tildeO(n)· mathsfpoly(k,1/varepsilon) and significantly improved time complexity mathsfpoly(n,k,1/varepsilon)+O(log(k)/varepsilon)O(k). When k=O(1), our algorithm runs in mathsfpoly(n,1/varepsilon) time, generalizing the polynomial guarantee of an explicit moment matching algorithm of Cherapanamjeri, et al. for k=2 and when it is known that D=N(0,Ik). Our algorithm succeeds under significantly relaxed noise assumptions, and therefore also succeeds in the related setting of max-linear regression where the added noise is taken outside the maximum. For this problem, our algorithm is efficient in a much larger range of k than the state-of-the-art due to Ghosh, Pananjady, Guntuboyina, and Ramchandran [IEEE Trans. Inf. Theory 2022] for not too small varepsilon, and leads to improved algorithms for any varepsilon by providing a warm start for existing local convergence methods.