Privately Estimating Monotone Statistics in Polynomial Time

Computer Science > Cryptography and Security [Submitted on 27 May 2026] Privately Estimating Monotone Statistics in Polynomial Time Gavin Brown, Ephraim Linder, Mahbod Majid, Vikrant Singhal 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 this http URL 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. Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) Cite as: arXiv:2605.27912 [cs.CR]   (or arXiv:2605.27912v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2605.27912 Focus to learn more Submission history From: Ephraim Linder [view email] [v1] Wed, 27 May 2026 03:40:25 UTC (188 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-05 Change to browse by: cs cs.DS cs.LG References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)