# Privately Estimating Monotone Statistics in Polynomial Time

arXiv: https://arxiv.org/abs/2605.27912 · HTML: https://mlsanity.com/paper/2605.27912/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 59 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 6 of 6)

- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Differentially Private Hypothesis Testing with the Subsampled and Aggregated Randomized Response Mechanism](https://mlsanity.com/paper/2208.06803/) (2022)
- [Resampling methods for private statistical inference](https://mlsanity.com/paper/2402.07131/) (2024)
- [High-Dimensional Private Linear Regression with Optimal Rates](https://mlsanity.com/paper/2505.16329/) (2025)
- [On Privately Estimating a Single Parameter](https://mlsanity.com/paper/2503.17252/) (2025)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)

## Abstract (arXiv)

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 et 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.