math.STNov 12, 2026

Linear Regression with Self-Selection Bias in Polynomial Time

Authors: Felix Zhou

Organizations: Yale University

Abstract

We revisit the problem of estimating kk linear regressors with self-selection bias in nn 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 poly(n,k,1/ε)\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 kk. 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 kk. Prior works exhaustively search over a kk-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)(\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.

Figures & tables

Explore similar work

CardsList
  1. Learning-Enabled Estimation: Tight Characterizations under Sample Selection Biases

    Sep 29, 2026Vikram Kher, Jane H. Lee, Anay Mehrotra +1Selection Bias