Seminar • Algorithms and Complexity • Can SGD Select Good Fishermen?

Please note: This seminar will take place in DC 1304 and online.

Felix Zhou, PhD student
Theory Group, Yale University

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 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). Note that the observed model depends on the outputs themselves and is determined by some known selection criterion.

We revisit the problem of estimating k linear regressors with maximum self-selection bias in d dimensions, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC'23]. Our main result is a poly(d,k,1/ε)+k^O(k) time algorithm for this problem, which yields an improvement in the running time of the algorithms of [CDIZ23] and Gaitonde & Mossel [GM24]. This is achieved by providing the first local convergence algorithm for self-selection, thus resolving the main open question of [CDIZ23].

Based on joint work with Alkis Kalavasis and Anay Mehrotra.

To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.