Linear Regression with Self-Selection Bias in Polynomial Time

Felix ZhouarXiv 2026 · arXiv

TL;DR

This paper presents the first polynomial-time algorithm for solving linear regression problems plagued by "maximum self-selection bias." By shifting the focus from response moments to the high-order moments of covariates, the author achieves a massive speedup over previous methods that were exponentially slow in the number of underlying models.

What Problem Does This Paper Address?

Imagine you are studying a housing market where "supply" and "demand" are two different linear models. You only ever see the actual transaction quantity, which is the minimum of supply and demand. Crucially, you don't know for any given house whether the price was limited by the seller (supply) or the buyer (demand). This is a classic example of self-selection bias.

In the general "unknown-index maximum self-selection" problem, we observe a feature vector $X$ and a response $Y_{max}$ that is the maximum of $k$ different hidden linear models: $Y_i = w_i^\top X + b_i + \xi_i$. The goal is to recover all $k$ regressors ($w_i$) and biases ($b_i$).

Selection bias occurs even with a known minimizer; vanilla OLS regression on the observed supply can lead to biased estimates.

Until now, the best algorithms for this problem were "exponentially expensive"—their running times grew explosively as the number of models ($k$) increased. This paper breaks that barrier, providing an algorithm that runs in polynomial time relative to all parameters ($n, k, 1/\epsilon$).

Methods

The author moves away from the traditional approach of exhaustively searching the regressor subspace. Instead, the paper introduces a multi-stage pipeline:

  1. Restricted Hermite Moments: The core discovery is that if you look only at samples where the response $Y_{max}$ is very large, the distribution of the covariates $X$ starts to look like a mixture of $k$ different groups, each pointing toward one of the regressors.
  2. Implicit Tensor Decomposition: Mathematically, these moments can be represented as high-order tensors. To avoid the "curse of dimensionality" (where a tensor's size grows to $n^d$), the algorithm uses iterative projections. This allows the algorithm to work with lower-dimensional "shadows" of these tensors.
  3. Observable-Operator Learning: Using techniques borrowed from hidden Markov model literature, the algorithm extracts unit vectors parallel to the regressors from the spectrum of these projected moments.
  4. Restricted Least Squares (RLS): Once the direction of a regressor is known, the algorithm uses a specialized version of Ordinary Least Squares to "refine" that direction into a precise estimate of the full vector and its bias.
  5. Moment Peeling: To find all $k$ models, the algorithm finds a few, "peels" their influence out of the data, and recurses on the remaining ones.
The main dependencies in the proof of the full recovery algorithm.

Datasets

This is a theoretical paper focused on algorithmic guarantees. It does not use empirical real-world datasets. Instead, it provides rigorous mathematical proofs for performance on the Gaussian self-selection model, where covariates and noise are assumed to follow Gaussian distributions.

Key Insights and Ideas

  • The Converse Intuition: Prior work focused on how $Y$ behaves given $X$. This paper realizes that conditioning on a large $Y$ forces $X$ to align with the "winning" regressor. As shown in Figure 2, as the response threshold $T$ grows, the covariate density concentrates sharply around the regressor directions.
  • Hermite Polynomials as a Scalpel: The use of Hermite moments is crucial because they are orthogonal under Gaussian measures. This allows the author to cleanly decompose the complex mixture of $k$ models into a sum of "rank-one tensors," which are much easier to solve.
  • Robustness to Irreducible Error: Unlike simpler mixture models, self-selection bias introduces "noise" that never goes away, even with infinite data. The algorithm is specifically designed to be robust to this irreducible bias by truncating the spectrum at the largest spectral gaps.
Conditioned on a large response, the density of the covariate angle concentrates around the regressor directions.

Key Results

  • Polynomial Efficiency: The algorithm achieves a running time and sample complexity of $\tilde{O}((nk/\epsilon)^{poly(B/\Delta)} \log(1/\delta))$. This is the first result to achieve polynomial dependence on $k$ for this problem.
  • Max-Affine Regression: As a corollary, the paper provides the first polynomial-time algorithm for max-affine regression (where noise is added after the maximum is taken), improving on previous $exp(k^2)$ bounds.
  • Improved Convergence: The "Restricted Least Squares" step acts as a local convergence routine that works even if the initial guess is only $O(1)$-distance away from the truth, a significant improvement over previous requirements for "inverse-polynomial" initialization.

Limitations and Future Work

  • Gaussian Assumption: The current proofs rely heavily on the properties of Gaussian distributions (e.g., Hermite orthogonality). Extending this to "heavy-tailed" or non-Gaussian distributions remains an open challenge.
  • Geometric Constraints: The algorithm requires "uncoveredness"—essentially, the regressors must be sufficiently separated and not "hidden" by one another.
  • Known Correlation: The model assumes the correlation ($\rho$) between the noises of different models is known. Future work could explore settings where this correlation must be estimated from the data.

Summary updated

Abstract

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.
BibTeX
@misc{zhou2026linear,
  author = {Felix Zhou},
  title = {{Linear Regression with Self-Selection Bias in Polynomial Time}},
  year = {2026},
  eprint = {2611.17228},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17228},
}
Figure