Safety
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases
arXiv:2504.07133v2 Announce Type: replace-cross Abstract: We revisit the problem of estimating k linear regressors with self-selection bias in d dimensions with the maximum selection criterion, as int
arXiv:2504.07133v2 Announce Type: replace-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 poly(d, k, 1/arepsilon) + (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.
Related
- Regression-Based Estimation of Causal Effects in the Presence of Selection Bias and Confounding
- Local Causal Structure Learning in the Presence of Latent Variables and Selection Bias
- Reducing the Filtering Effect in Public School Admissions: A Bias-aware Analysis for Targeted Interventions
Source: arXiv cs.LG | 2026-09-14