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$).
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:
- 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.
- 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.
- 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.
- 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.
- 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.
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.
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