Felix Zhou

The question of whether we can obtain a poly(d, 1/ERR, k) time algorithm is still open, so jump right in!

(7/7)

We make a conceptual connection to learning with coarsened samples.
Through this connection, we derive an SGD-based algorithm with poly(d, 1/ERR) + k^O(k) running time.

(6/7)

Gaitonde and Mossel improved this to poly(d) * (log(k)/ERR)^O(k) time, also using a moment-based algorithm.

(5/7)

Surprisingly, Cherapanamjeri, Daskalakis, @aifi.bsky.social, and Zampetakis recently designed a moment-based algorithm with poly(d) * exp(k/ERR) running time to recover the k-linear regression parameters up to error ERR in ambient dimension d.

(4/7)

Inference under selection biases has been extensively studied, starting with the works of Roy, Heckman, Willis and Rosen, and Fair and Jaffee.

Despite this extensive history, efficient algorithms for
estimation under self-selection was not known.

(3/7)

Self-selection bias occurs when data is systematically selected rather than randomly sampled:
Assuming individuals choose the profession for which they are most successful, we would only observe the maximum of k outcomes.

(2/7)

Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond 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 Zamp...

"What makes a good fisherman as opposed to other professions?"
This question can be formulated as a k-linear regression problem with self-selection bias.

Alkis, @anaymehrotra.bsky.social, and I design faster local convergence algorithms for this problem:
arxiv.org/abs/2504.07133

(1/7)