Sample-Efficient Linear Regression with Self-Selection Bias

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.