Privately Estimating Monotone Statistics in Polynomial Time
Provides improved private estimation for monotone statistics, benefiting applications like eigenvalue estimation and linear regression.
The paper develops efficient differentially private algorithms for estimating monotone statistics, achieving a factor of t improvement in sample complexity over subsample-and-aggregate at the cost of e^t runtime, and proves near-optimality via a query-complexity lower bound.
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.