5 papers
Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
Alkis Kalavasis, Anay Mehrotra, Manolis Zampetakis +2
Coarse data arise when learners observe only partial information about samples; namely, a set containing the sample rather than its exact value. This occurs naturally through measu…
Language Generation with Infinite Contamination
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language and must eventually generate new, u…
Private Statistical Estimation via Truncation
Manolis Zampetakis, Felix Zhou
We introduce a novel framework for differentially private (DP) statistical estimation via data truncation, addressing a key challenge in DP estimation when the data support is unbo…
Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
Felix Zhou
We study the sublinear space continual release model for edge-differentially private (DP) graph algorithms, with a focus on the densest subgraph problem (DSG) in the insertion-only…
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases and Beyond
Alkis Kalavasis, Anay Mehrotra, Felix Zhou
We revisit the problem of estimating linear regressors with self-selection bias in dimensions with the maximum selection criterion, as introduced by Cherapanamjeri, Daskala…