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 $(\mathbf{x}_{\ell},z_{\ell})_{\ell=1}^m$ where
$z_{\ell}=\max_{i\in [k]}\{\mathbf{x}_{\ell}^T\mathbf{w}_i+\eta_{i,\ell}\}$,
but the maximizing index $i_{\ell}$ is unobserved. Here, the
$\mathbf{x}_{\ell}$ are assumed to be $\mathcal{N}(0,I_n)$ and the noise
distribution $\mathbf{\eta}_{\ell}\sim \mathcal{D}$ is centered and independent
of $\mathbf{x}_{\ell}$. We provide a novel and near optimally sample-efficient
(in terms of $k$) algorithm to recover $\mathbf{w}_1,\ldots,\mathbf{w}_k\in
\mathbb{R}^n$ up to additive $\ell_2$-error $\varepsilon$ with polynomial
sample complexity $\tilde{O}(n)\cdot \mathsf{poly}(k,1/\varepsilon)$ and
significantly improved time complexity
$\mathsf{poly}(n,k,1/\varepsilon)+O(\log(k)/\varepsilon)^{O(k)}$. When
$k=O(1)$, our algorithm runs in $\mathsf{poly}(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
$\mathcal{D}=\mathcal{N}(0,I_k)$. 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.

在未知指数设定下，考虑具有自我选择偏差的线性回归问题，我们提供了一种新颖且在样本使用效率上接近最优的算法，用于从样本中恢复权重并实现多项式样本复杂性和显著提高的时间复杂性，同时还扩展了关于最大线性回归的问题解决，提供了现有局部收敛方法的良好起点。