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

Apr 6, 2025

Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases

We revisit the problem of estimating kk linear regressors with self-selection bias in dd dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a poly(d,k,1/ε)+(klog⁡k)O(k)\mathrm{poly}(d, k, 1/\varepsilon) + (k \log k)^{O(k)} time algorithm for this problem that improves upon the running time of the algorithms by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23] and Gaitonde and Mossel [GM24, arXiv]. We achieve this by providing the first local convergence algorithm for self-selection, thus resolving one of the main open questions of Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23]. To obtain this algorithm, we reduce self-selection to a seemingly unrelated statistical problem called estimation under coarsening [FKKT21, COLT'21]. Coarsening occurs when one does not observe the exact value of the sample but only some set (from a partition of the sample space) containing the exact value. Inference from coarse samples arises in various real-world applications, including rounding by humans and algorithms, limited precision of instruments, and lag in multi-agent systems. The coarse estimation problem arising in our reduction is induced by a non-convex partition, whereas previous works on coarsening exclusively studied convex partitions. The resulting estimation algorithm relies on the geometry of the self-selection problem to bypass non-convexity. This geometric approach, in turn, enables us to overcome the limitations of previous analytic approaches and could have applications for designing efficient algorithms for other latent-variable problems.
Aug 19, 2026

Algorithms for adaptive and heteroskedastic linear regression at the computational threshold

We study finite-sample linear regression in the presence of varied and unknown label noise, focusing on the heteroskedastic and adaptive linear regression models. Heteroskedastic linear regression models settings where the labels are of varying quality. We receive nn pairs (Xi,Yi)(X_i,Y_i) with labels Yi=Xi⊤β+εiY_i=X_i^\topβ+\varepsilon_i, where εi∼N(0,σi2)\varepsilon_i\sim N(0,σ_i^2) and the variances are unknown to the estimator. One natural measurement of the difficulty of this problem is the number of samples mm for which σi2≤1σ_i^2\le1 (larger mm is easier). We obtain a polynomial-time estimator with rate O~((nd3/m4)1/6)\tilde{O}((nd^3/m^4)^{1/6}) when m≫d3/4n1/4m\gg d^{3/4}n^{1/4}, as well as nearly-matching lower bounds. For d=O(1)d=O(1), our estimator achieves error o(1)o(1) when m≫n1/4m\gg n^{1/4}, whereas L1L_1 regression and other traditional approaches require m≫n1/2m\gg n^{1/2}. In adaptive linear regression, the errors are drawn i.i.d. from an unknown distribution pp, and our goal is to design a generic estimator that performs nearly as well as the best custom estimator that knows pp. We introduce a (computationally inefficient) adaptive estimator that, so long as pp is a mixture of kk symmetric log-concave densities, achieves error comparable with the optimal estimator that knows pp and has Θ~(n/k)\tildeΘ(n/k) samples. For k=1k=1, we show that LqL_q regression (with data-dependent qq) gives a polynomial-time estimator. Finally, to study the computational limits of both problems, we introduce the planted linear regression problem, where Xi∼N(0,Id)X_i\sim N(0,I_d), mm unknown samples are noiseless, and the rest have error εi∼N(0,1)\varepsilon_i\sim N(0,1). We conjecture that recovering ββ up to error ≪d/n\ll\sqrt{d/n} (or exactly) may have an information-computation gap between m=d+1m=d+1 and m∼d3/4n1/4m\sim d^{3/4}n^{1/4}, as is suggested by our near-matching polynomial-time estimator and statistical query (SQ) lower bound.
Sep 29, 2026

Learning-Enabled Estimation: Tight Characterizations under Sample Selection Biases

When can we learn from biased samples? We study regression when outcomes are observed only after passing through selection filters that depend on both covariates and outcomes themselves, a ubiquitous challenge spanning clinical trials with patient dropout, labor markets with self-selection, and auctions with strategic entry. Ignoring such selection yields systematically biased conclusions with real-world consequences. This challenge has a long history in econometrics and statistics, starting with Heckman's seminal two-stage model and followed by numerous generalizations. While these works provide various sufficient conditions for identification, a complete characterization of when such regression is possible has remained elusive. In this work, we provide a characterization for when regression is possible in the presence of sample selection bias. Our results establish the minimal assumptions required on the functional forms of selection processes under which regression remains possible, which are particularly relevant in modern settings where selection mechanisms are increasingly complex and opaque. As a corollary of our characterization, we show that there are settings where the regression function can be identified even when the selection filter itself cannot. This observation already goes beyond the ``estimate selection filter, then debias regression'' paradigm that is followed by virtually all existing approaches. Under natural strengthenings of our identification conditions, we also establish finite-sample estimation guarantees with explicit convergence rates and provide oracle-efficient algorithms. This yields the first general-purpose estimation method for this broad class of selection problems. Finally, we explore the implications of our results for several well-studied econometric settings with complex selection mechanisms such as auctions with entry costs and labor markets.