Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a differentially private algorithm for estimating monotone statistics that improves upon the standard subsample-and-aggregate approach. The key innovation is a refined algorithm that reduces sample complexity by a factor of *t* while increasing running time by a factor of exp(*t*), offering a tunable trade-off. The authors also provide a query-complexity lower bound, demonstrating the near-optimality of their algorithm, and showcase applications in private eigenvalue estimation, loss estimation, and high-dimensional parameter estimation.
Get an exponential speedup in runtime when privately estimating monotone statistics, at the cost of only a polynomial increase in sample complexity.
We study efficient differentially private algorithms for estimating monotone statistics, i.e., statistics that are monotone under the addition of new observations. The starting point for our investigation is subsample-and-aggregate: a classical paradigm that partitions the dataset into blocks, estimates the statistic on each block, and then privately aggregates the estimates.While practical and generically applicable, this approach is quite data-hungry. We improve upon this framework for the class of monotone statistics -- compared to subsample-and-aggregate, our algorithms save a factor of $t$ in sample complexity and pay a factor of $e^t$ in running time, where $t>0$ is a tunable parameter. We complement our results with a query-complexity lower bound, showing that our algorithms are essentially optimal for this task. As an application, we obtain improved results for private eigenvalue estimation, private loss estimation, and privately estimating a single parameter of a high-dimensional model, e.g., in linear regression.