In the classical setting of self-selection, the goal is to learn $k$ models, simultaneously from observations $(x^{(i)}, y^{(i)})$ where $y^{(i)}$ is the output of one of $k$ underlying models on input $x^{(i)}$. In contrast to mixture models, where we observe the output of a randomly selected model, here the observed model depends on the outputs themselves, and is determined by some known selection criterion. For example, we might observe the highest output, the smallest output, or the median output of the $k$ models. In known-index self-selection, the identity of the observed model output is observable; in unknown-index self-selection, it is not. Self-selection has a long history in Econometrics and applications in various theoretical and applied fields, including treatment effect estimation, imitation learning, learning from strategically reported data, and learning from markets at disequilibrium. In this work, we present the first computationally and statistically efficient estimation algorithms for the most standard setting of this problem where the models are linear. In the known-index case, we require poly$(1/\varepsilon, k, d)$ sample and time complexity to estimate all model parameters to accuracy $\varepsilon$ in $d$ dimensions, and can accommodate quite general selection criteria. In the more challenging unknown-index case, even the identifiability of the linear models (from infinitely many samples) was not known. We show three results in this case for the commonly studied $\max$ self-selection criterion: (1) we show that the linear models are indeed identifiable, (2) for general $k$ we provide an algorithm with poly$(d) \exp(\text{poly}(k))$ sample and time complexity to estimate the regression parameters up to error $1/\text{poly}(k)$, and (3) for $k = 2$ we provide an algorithm for any error $\varepsilon$ and poly$(d, 1/\varepsilon)$ sample and time complexity.
翻译:在典型的自我选择设置中, 目标是学习 $k 的模型, 同时从观察 $( x ⁇ ( i) }, y ⁇ ( i) }) 美元( $) 美元( 美元) 中, 美元( 美元) 是输入 $x ⁇ ( ( i) 美元 美元。 与混合模型相比, 我们观察随机选择模式的输出, 观察一个随机选择模式的输出, 观察的模型取决于产出本身, 并且由某种已知的选择标准标准标准 。 例如, 我们可能看到最高的产出, 最小的流产, 或美元模式的中值。 在已知的自我选择中, 美元( 美元) 预估的模型的身份是可见的; 在未知的常规时间里, 自我选择有很长的历史, 包括治疗效果估计, 模仿学习, 从战略上报告的数据到任何不精确的市场。 在这项工作中, 我们第一次用计算和统计上高效的估计 美元( 美元) 。 在已知的常识的模型中, 解的模型中, 显示的是所有常态的 标准 。