We revisit the problem of estimating $k$ linear regressors in $d$ dimensions under self‑selection bias using the maximum selection criterion, originally introduced by Cherapanamjeri, Daskalakis, Ilyas and Zampetakis at STOC'23. Our main contribution is an algorithm running in $\mathrm{poly}(d, k, 1/\varepsilon) + (k \log k)^{O(k)}$ time, which improves on the previous approaches of CDIZ23 and Gaitonde & Mossel. The key novelty is the first local‑convergence algorithm for self‑selection, answering a major open question raised by CDIZ23. To achieve this we reduce self‑selection to a statistical problem known as estimation under coarsening, where one only observes the partition block containing the true sample rather than the exact value. Coarsened observations appear in many real‑world settings such as human or algorithmic rounding, limited instrument precision, and delays in multi‑agent systems. Unlike prior work that considered only convex partitions, our reduction yields a non‑convex partition induced by the geometry of the self‑selection problem. By exploiting this geometry we design an estimator that sidesteps the non‑convexity, overcoming the limitations of earlier analytic techniques. This geometric perspective may also inspire efficient algorithms for other latent‑variable problems.
Review