An interesting and somewhat counterintuitive feature: we get better private streaming algorithms by actually making the input larger!

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)