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

-cross Abstract: We revisit the problem of estimating $k$ linear regressors with self-selection bias in $d$ dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a $\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.