Differentially private continual release of histograms and related queries
Henzinger M, Sricharan AR, Steiner TA. 2025. Differentially private continual release of histograms and related queries. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 1990–1998.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA
;
Sricharan, A. R.;
Steiner, Teresa Anna

Department
Grant
Series Title
PMLR
Abstract
We study privately releasing column sums of a d-dimensional table with entries from a universe χ undergoing T row updates, called histogram under continual release. Our mechanisms give better additive ℓ∞-error than existing mechanisms for a large class of queries and input streams. Our first contribution is an output-sensitive mechanism in the insertions-only model (χ = {0, 1}) for maintaining (i) the histogram or (ii) queries that do not require maintaining the entire histogram, such as the maximum or minimum column sum, the median, or any quantiles. The mechanism has an additive error of O(d log2 (dq∗) + log T) whp, where q∗ is the maximum output value over all time steps on this dataset. The mechanism does not require q∗ as input. This breaks the Ω(d log T) bound of prior work when q∗ ≪ T. Our second contribution is a mechanism for the turnstile model that admits negative entry updates (χ = {−1, 0, 1}). This mechanism has an additive error of O(d log2(dK) + log T) whp, where K is the number of times two consecutive data rows differ, and the mechanism does not require K as input. This is useful when monitoring inputs that only vary under unusual circumstances. For d = 1 this gives the first
private mechanism with error O(log2 K + log T) for continual counting in the turnstile model, improving on the O(log2 n + log T) error bound by Dwork et al. (2015), where n is the number of ones in the stream, as well as allowing negative entries, while Dwork et al. (2015) can only handle nonnegative entries (χ = {0, 1}).
Publishing Year
Date Published
2025-05-01
Proceedings Title
The 28th International Conference on Artificial Intelligence and Statistics
Publisher
ML Research Press
Acknowledgement
MH: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. TAS: This work was supported by a research grant (VIL51463)
from VILLUM FONDEN.
Volume
258
Page
1990-1998
Conference
AISTATS: Conference on Artificial Intelligence and Statistics
Conference Location
Mai Khao, Thailand
Conference Date
2025-05-03 – 2025-05-05
eISSN
IST-REx-ID
Cite this
Henzinger M, Sricharan AR, Steiner TA. Differentially private continual release of histograms and related queries. In: The 28th International Conference on Artificial Intelligence and Statistics. Vol 258. ML Research Press; 2025:1990-1998.
Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2025). Differentially private continual release of histograms and related queries. In The 28th International Conference on Artificial Intelligence and Statistics (Vol. 258, pp. 1990–1998). Mai Khao, Thailand: ML Research Press.
Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Differentially Private Continual Release of Histograms and Related Queries.” In The 28th International Conference on Artificial Intelligence and Statistics, 258:1990–98. ML Research Press, 2025.
M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private continual release of histograms and related queries,” in The 28th International Conference on Artificial Intelligence and Statistics, Mai Khao, Thailand, 2025, vol. 258, pp. 1990–1998.
Henzinger M, Sricharan AR, Steiner TA. 2025. Differentially private continual release of histograms and related queries. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 1990–1998.
Henzinger, Monika, et al. “Differentially Private Continual Release of Histograms and Related Queries.” The 28th International Conference on Artificial Intelligence and Statistics, vol. 258, ML Research Press, 2025, pp. 1990–98.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2302.11341