Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms

Alessandro Epasto, Xin Lyu, Pasin Manurangsi
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:28058-28070, 2026.

Abstract

We study the computational cost of differential privacy in terms of memory efficiency. Specifically, we establish for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. We apply our framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream: we prove that any private algorithm requires almost $\widetilde{\Omega}(T^{1/3})$ space (where $T$ denotes the length of the stream) to achieve certain error rates in a promise variant of the problem, resolving an open problem in the literature (by Jain et al. 2023 and Cummings et al. 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-epasto26a, title = {Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms}, author = {Epasto, Alessandro and Lyu, Xin and Manurangsi, Pasin}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {28058--28070}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/epasto26a/epasto26a.pdf}, url = {https://proceedings.mlr.press/v306/epasto26a.html}, abstract = {We study the computational cost of differential privacy in terms of memory efficiency. Specifically, we establish for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. We apply our framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream: we prove that any private algorithm requires almost $\widetilde{\Omega}(T^{1/3})$ space (where $T$ denotes the length of the stream) to achieve certain error rates in a promise variant of the problem, resolving an open problem in the literature (by Jain et al. 2023 and Cummings et al. 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.} }
Endnote
%0 Conference Paper %T Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms %A Alessandro Epasto %A Xin Lyu %A Pasin Manurangsi %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-epasto26a %I PMLR %P 28058--28070 %U https://proceedings.mlr.press/v306/epasto26a.html %V 306 %X We study the computational cost of differential privacy in terms of memory efficiency. Specifically, we establish for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. We apply our framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream: we prove that any private algorithm requires almost $\widetilde{\Omega}(T^{1/3})$ space (where $T$ denotes the length of the stream) to achieve certain error rates in a promise variant of the problem, resolving an open problem in the literature (by Jain et al. 2023 and Cummings et al. 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
APA
Epasto, A., Lyu, X. & Manurangsi, P.. (2026). Keeping a Secret Requires a Good Memory: Unconditional Streaming Lower-Bounds for Differentially Private Algorithms. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:28058-28070 Available from https://proceedings.mlr.press/v306/epasto26a.html.

Related Material