# What Makes A Good Fisherman? Linear Regression under Self-Selection Bias

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 71 references that are in the map.
- First posted on arXiv 6 May 2022.

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

- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [Efficient Statistics, in High Dimensions, from Truncated Samples](https://mlsanity.com/paper/1809.03986/) (2018)
- [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)
- [Computationally and Statistically Efficient Truncated Regression](https://mlsanity.com/paper/2010.12000/) (2020)
- [Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation](https://mlsanity.com/paper/1906.09255/) (2019)
- [Classification with Strategically Withheld Data](https://mlsanity.com/paper/2012.10203/) (2020)
- [Test-optional Policies: Overcoming Strategic Behavior and Informational Gaps](https://mlsanity.com/paper/2107.08922/) (2021)
- [Discrete Choice Models for Nonmonotone Nonignorable Missing Data: Identification and Inference](https://mlsanity.com/paper/1607.02631/) (2016)
- [Estimation of Standard Auction Models](https://mlsanity.com/paper/2205.02060/) (2022)

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

- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Classification Under Strategic Self-Selection](https://mlsanity.com/paper/2402.15274/) (2024)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Statistical Query Lower Bounds for Learning Truncated Gaussians](https://mlsanity.com/paper/2403.02300/) (2024)
- [Learning High-dimensional Gaussians from Censored Data](https://mlsanity.com/paper/2504.19446/) (2025)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)
- [Mean Testing under Truncation beyond Gaussian](https://mlsanity.com/paper/2605.01335/) (2026)

## Abstract (arXiv)

In the classical setting of self-selection, the goal is to learn k models, simultaneously from observations (x(i), y(i)) where y(i) is the output of one of k underlying models on input x(i). In contrast to mixture models, where we observe the output of a randomly selected model, here the observed model depends on the outputs themselves, and is determined by some known selection criterion. For example, we might observe the highest output, the smallest output, or the median output of the k models. In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics and applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly(1/varepsilon, k, d) sample and time complexity to estimate all model parameters to accuracy varepsilon in d dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied max self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general k we provide an algorithm with poly(d) exp(poly(k)) sample and time complexity to estimate the regression parameters up to error 1/poly(k), and (3) for k = 2 we provide an algorithm for any error varepsilon and poly(d, 1/varepsilon) sample and time complexity.