Shyam Narayanan

collaborators

2 papers

cs.LG2024

Sample-Efficient Private Learning of Mixtures of Gaussians

Hassan Ashtiani, Mahbod Majid, Shyam Narayanan

We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $k d^{2} + k^{1.5} d^{1.75} + k^{2} d$ samples suffice to learn a mix…

cs.DS2024

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

Shyam Narayanan, VÃ¡clav RozhoÅ, Jakub TÄtek +1

Suppose we have a memory storing $0$ s and $1$ s and we want to estimate the frequency of $1$ s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a bloc…