The Price of Differential Privacy under Continual Observation

Palak JainSofya RaskhodnikovaSatchit SivakumarAdam D. Smith

article2023ICML71 citations

Proves that fundamental tasks like MaxSum and SumSelect require polynomial error in the stream length under continual observation, establishing tight lower and upper bounds that reveal an exponential separation between continual release and standard batch differential privacy.

Listen

Modern data systems increasingly collect sensitive information as a continuous stream rather than in a single batch, requiring frequent updates to public dashboards, machine learning models, and real-time recommendations. While differential privacy is widely deployed to protect individual privacy in static settings, repeatedly releasing updated outputs over a stream makes privacy significantly more challenging because each individual's record can influence outputs across multiple time steps. The article evaluates the fundamental accuracy limits of differentially private algorithms operating in this continual release framework and investigates whether the arrival of adaptive data—where incoming inputs depend on previously published outputs—imposes an additional accuracy penalty.

To establish these limits, the analysis introduces a theoretical reduction technique called sequential embedding, which translates known hardness bounds from static batch environments into continual stream settings. The authors evaluate two fundamental tasks: MaxSum, which tracks the maximum aggregate value across multiple attributes, and SumSelect, which identifies the specific attribute achieving that maximum. The study examines both pure and approximate differential privacy, as well as zero-concentrated differential privacy, over a stream horizon and across varying data dimensions. In parallel, the article formalizes a game-theoretic model of adaptive adversaries using cryptographic simulation techniques to analyze algorithms against dynamic data streams.

First, the analysis proves a substantial separation between batch and continual release models: while batch algorithms can solve these tasks with near-constant error, any continually updated private algorithm suffers worst-case error that scales polynomially with stream length (proportional to the cube root of the time horizon under approximate privacy and the square root under pure privacy). Second, the article demonstrates that simple baseline mechanisms—specifically, a binary tree noise-addition mechanism and periodic recomputation—match these lower bounds up to logarithmic factors across all parameter regimes. Third, the study reveals that operating under adaptive input streams causes no asymptotic increase in worst-case error compared to oblivious streams, showing that existing private streaming protocols remain robust against adaptive feedback.

These findings have critical operational and policy implications for engineering privacy-preserving streaming architectures. Organizations deploying private real-time analytics cannot assume that algorithms will achieve the low, logarithmic error rates seen in simple summation tasks; complex aggregation and model selection inherently incur polynomial error growth over long time horizons. Consequently, system designers must anticipate higher error margins or shorter deployment horizons when tracking high-dimensional statistics under continual observation.

For practical implementation, technical teams should select the optimal mechanism based on the stream duration and dimension: periodic recomputation is optimal for high-dimensional streams over moderate time horizons, whereas binary-tree noise mechanisms perform best when the number of monitored attributes is low. Furthermore, because the derived error bounds represent fundamental theoretical limits under event-level privacy, future research and pilot evaluations should investigate whether specialized data structures or alternate privacy definitions can mitigate error accumulation in long-running streaming pipelines.

correlation analysis data stream differential privacies differential privacy continual observation event-level privacy

Jain et al (2023).pdf

Paper: Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams, Sergey Denisov et al. (2022). Its analysis of differential privacy for adaptive streams and continual-release mechanisms provides a direct foundation for the source’s treatment of adaptive inputs and streaming accuracy limits.

No sufficiently relevant recommendations were found.

Cover for The Price of Differential Privacy under Continual Observation

Abstract

We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sequence of T inputs and must output a sequence of T outputs, one for each input, that approximates some function of the inputs while maintaining differential privacy for the entire sequence, even for inputs that arrive later. The standard approach to achieving differential privacy in the continual release model is to use the binary tree mechanism of Chan, Shi, and Song (2010) and Dwork, Naor, Pitassi, and Roth (2010), which gives an additive error of O(log T) for counting queries. We show that the binary tree mechanism is optimal for counting queries in the continual release model, up to constant factors in the error, by proving a lower bound of Ω(log T). Our lower bound is the first to show that the binary tree mechanism is optimal for any class of queries in the continual release model. Our techniques also yield lower bounds for the related problems of differentially private streaming and pan-private algorithms for counting queries. Our lower bound for the continual release model is based on a new method for analyzing the privacy of mechanisms that use correlated randomness, which may be of independent interest.

Topics

correlation analysis data stream differential privacies engineering game-theoretic model genetic selection individual privacy machine learning mode selection optimal mechanism

Keywords

differential privacy continual observation event-level privacy continual release algorithms group privacy empirical risk minimization exponential mechanism Gaussian noise

1. Introduction
1.1. Our Contributions
1.2. Discussion and Open Questions
1.3. Organization of Paper
2. Definitions
2.1. Continual Release with Nonadaptively Chosen Inputs
2.2. Problem Definitions
3. Lower Bounds for MaxSum
3.1. 1-way Marginal Queries in Batch Model
3.2. Proof Sketch of Theorem 3.1
4. Lower Bounds for SumSelect
4.1. Proof sketch of Theorem 4.1
5. Continual Release with Adaptively Chosen Inputs
5.1. Model Definition
5.2. Summary of Upper Bounds for Adaptive Inputs
Acknowledgments
References
A. Differential Privacy
A.1. ρ-zCDP
B. Further Related Work
C. Proofs Omitted from Section 3
D. Proofs Omitted from Section 4
D.1. Proof of Theorem 4.1
E. Details Omitted from Section 5
E.1. Formal Statements
E.2. Algorithms based on the Binary Tree Mechanism
E.3. Algorithms that Recompute at Regular Intervals
F. Useful Concentration Inequalities

Knowls

Knowl 1 — Continual-release lower bounds for MaxSum
theoretical result
For a stream of $T$ records $x_i\in\{0,1\}^d$ , define the running coordinate sums $S_j(t)=\sum_{i=1}^t x_i[j]$ and $\operatorname{MaxSum}_d(x_{1:t})=\max_{j\in[d]}S_j(t)$ . A mechanism has error at most $\alpha$ if, with probability at least $2/3$ , every output estimates the corresponding prefix maximum to additive error at most $\alpha$ .

For sufficiently large $T$ and $\epsilon\in(0,1]$ , every event-level $(\epsilon,\delta)$ -DP mechanism for obliviously chosen inputs obeys the following lower bounds. For approximate privacy with $\delta>0$ and $\delta=o(\epsilon/T)$ ,
$\alpha=\Omega\!\left(\min\left\{\frac{T^{1/3}}{\epsilon^{2/3}\log^{2/3}(\epsilon T)},\frac{\sqrt d}{\epsilon\log d},T\right\}\right).$
For pure privacy ( $\delta=0$ ),
$\alpha=\Omega\!\left(\min\left\{\sqrt{T/\epsilon},\frac d\epsilon,T\right\}\right).$
The batch counterpart has error $O(1/\epsilon)$ , so continual release can require error polynomial in the time horizon or dimension even for this low-sensitivity statistic.
Knowl 2 — Continual-release lower bounds for SumSelect
theoretical result
For $T$ records $x_i\in\{0,1\}^d$ , let $S_j(t)=\sum_{i=1}^t x_i[j]$ . The function $\operatorname{SumSelect}_d$ returns an index maximizing $S_j(t)$ , with ties resolved by choosing the smallest index. Its error at time $t$ is the objective deficit $\max_j S_j(t)-S_{a_t}(t)$ , where $a_t$ is the selected index; accuracy bounds this deficit simultaneously over all prefixes with probability at least $2/3$ .

For sufficiently large $d,T$ and $\epsilon\in(0,1]$ , every event-level private mechanism for obliviously chosen inputs has, under approximate privacy with $0<\delta=o(\epsilon/T^2)$ ,
$\alpha=\widetilde\Omega\!\left(\min\left\{\frac{T^{1/3}\log^{2/3}d}{\epsilon^{2/3}},\frac{\sqrt d}{\epsilon},T\right\}\right).$
Under pure privacy,
$\alpha=\Omega\!\left(\min\left\{\sqrt{\frac{T}{\epsilon}\log\!\left(2+\frac{\sqrt d}{\epsilon T}\right)},\frac d\epsilon,T\right\}\right) =\widetilde\Omega\!\left(\min\left\{\sqrt{\frac{T\log d}{\epsilon}},\frac d\epsilon,T\right\}\right).$
The batch error is $O(\log(d)/\epsilon)$ . Thus the continual-release cost is not limited to estimating the maximum value: privately identifying a near-best coordinate can also require polynomial error.
Knowl 3 — Continual release with adaptively chosen inputs
definition
In the adaptive-input model, a mechanism receives a record $x_t$ and returns $a_t$ at each of $T$ steps. An adversarial process may choose each next record $x_{t+1}$ from the previous records and outputs, $(x_{1:t},a_{1:t})$ , but cannot see the mechanism's internal randomness. A mechanism is $(\alpha,T)$ -accurate for a function $f$ if, for every such adversary, with probability at least $2/3$ its error on every prefix is at most $\alpha$ .

Event-level privacy is defined by a challenge game. At one adversarially chosen step $t^*$ , the adversary supplies two candidate records $x^{(L)}_{t^*},x^{(R)}_{t^*}$ ; a hidden bit selects which one the mechanism receives. The adversary chooses all other records adaptively and sees the interaction transcript and its own randomness. The mechanism is $(\epsilon,\delta)$ -DP in this model when the adversary's views for the two hidden-bit choices are $(\epsilon,\delta)$ -indistinguishable for every adversary. The paper also defines adaptive $\rho$ -zCDP by requiring those views to be $\rho$ -close in Rényi divergence.
Knowl 4 — Sequential embedding reductions for continual-release lower bounds
model/method
Sequential embedding converts a single continual-release instance into a way to solve multiple batch problems on the same sensitive dataset. The reduction first streams the batch dataset into the continual mechanism, then appends data-independent filler records in stages. Each stage makes a different target statistic dominate, so the mechanism's output at a selected checkpoint reveals the answer to a separate batch subproblem. Because neighboring batch datasets produce neighboring constructed streams, the reduction preserves the mechanism's $(\epsilon,\delta)$ privacy; post-processing decodes the checkpoint outputs.

For $\operatorname{MaxSum}_d$ , a batch dataset $y$ of $n$ binary $d$ -vectors is followed by fillers that successively make each coordinate the largest running sum. At checkpoint $2jn$ , the $j$ th marginal satisfies $q_j(y)=\operatorname{MaxSum}_d(x_{1:2jn})/n-j$ . Thus a continual mechanism with error $\alpha$ yields an $(\epsilon,\delta)$ -DP batch algorithm estimating all one-way marginals to error $\alpha/n$ , using a stream of length $2dn$ .

For $\operatorname{SumSelect}_{dk}$ , the batch task is to select the largest-sum coordinate separately in each of $k$ disjoint blocks of $d$ coordinates. A single continual run on a constructed stream of length $4kn$ uses staged fillers to force the selected index into the target block at each checkpoint. It yields a batch solver with normalized selection error $\alpha/n$ without running $k$ private mechanisms on the same records. Applying batch lower bounds to these reductions gives the continual-release lower bounds.
Knowl 5 — Adaptive-input binary-tree mechanisms
algorithm
For $d$ -dimensional binary records, a binary-tree mechanism privately tracks all coordinate sums. It builds a binary tree over the $T$ time steps; each node stores the vector sum of the records in its interval plus independent coordinate-wise Gaussian noise. At time $t$ , the prefix $[1:t]$ is partitioned into at most $\lceil\log_2 t\rceil+1$ disjoint tree intervals, whose stored vectors are added. The mechanism outputs the maximum coordinate of that noisy vector for $\operatorname{MaxSum}_d$ , or its maximizing coordinate for $\operatorname{SumSelect}_d$ . For $\rho$ -zCDP, the node noise has variance $d(\lceil\log_2 T\rceil+1)/(2\rho)$ per coordinate; a non-power-of-two horizon can be padded to the next power of two.

These mechanisms remain private and accurate against adaptively chosen inputs. For either task, the $\rho$ -zCDP error is $O\!\left(\sqrt{d\log T\log(dT)/\rho}\right)$ . A pure-DP variant uses Laplace noise and has error $O\!\left(d\log(d)\log^3(T)/\epsilon\right)$ . Converting the zCDP guarantee to $(\epsilon,\delta)$ -DP gives a tree-based error of $O\!\left(\sqrt{d\log(dT)\log(1/\delta)\log T}/\epsilon\right)$ .
Knowl 6 — Adaptive-input mechanisms by periodic recomputation
algorithm
A second construction recomputes a private estimate at regular checkpoints and repeats the latest estimate until the next checkpoint. If there are $m$ checkpoints, the recomputation interval is on the order of $T/m$ . For a scalar function of $\ell_2$ -sensitivity at most $1$ , each checkpoint adds Gaussian noise with variance $m/(2\rho)$ , giving an adaptive-input $\rho$ -zCDP mechanism with error $O\!\left(\min\{(T\log T/\rho)^{1/3},T\}\right)$ . For a scalar function of $\ell_1$ -sensitivity at most $1$ , Laplace noise and pure-DP composition give error $O\!\left(\min\{\sqrt{T\log T/\epsilon},T\}\right)$ . The $T$ term is achieved by the trivial mechanism that ignores the data.

For $\operatorname{SumSelect}_d$ , each checkpoint instead runs a private exponential-mechanism selection and reuses that index until the next checkpoint. The resulting zCDP error is $O\!\left(\min\{T^{1/3}\log^{2/3}(dT)/\rho^{1/3},T\}\right)$ , and the pure-DP error is $O\!\left(\min\{\sqrt{T\log(dT)/\epsilon},T\}\right)$ . Taking the better of these recomputation bounds and the binary-tree bounds yields the paper's adaptive-input upper bounds, matching the lower-bound rates up to logarithmic factors. For approximate DP, the zCDP results convert using $(\epsilon,\delta)=(\rho+2\sqrt{\rho\log(1/\delta)},\delta)$ .
Knowl 7 — Simulation-based privacy analysis for adaptive streams
model/method
Privacy proofs for adaptively chosen streams cannot generally compare two fixed neighboring streams: after the challenge record changes, later records may diverge as the adversary reacts to outputs. Adaptive composition alone is also insufficient for a continual mechanism that may reuse randomness across time. The paper instead proves privacy directly for the adversary's view using a simulation argument.

The simulator interacts with the adversary without knowing which challenge record was used. It reproduces the mechanism's outputs online, while sending only the challenge-dependent computations to an ideal private mechanism. For the binary-tree construction, only the $O(\log T)$ tree-node sums whose intervals contain the challenge step need that ideal mechanism; all other node sums can be simulated from the visible stream and fresh noise. The adversary's simulated view is identically distributed to its real view, and is post-processing of the ideal mechanism's responses. Its privacy therefore follows from the ideal mechanism's guarantee and composition, even when the adversary's subsequent inputs depend on previous outputs.
Knowl 8 — The lower bounds do not depend on causal uncertainty
theoretical result
The continual-release lower bounds for $\operatorname{MaxSum}_d$ and $\operatorname{SumSelect}_d$ hold even for offline algorithms that receive the entire length- $T$ stream before producing outputs. The hardness therefore does not arise only because a streaming algorithm lacks information about future records: privacy together with the requirement to provide accurate answers across all prefixes is sufficient for the stated lower bounds.

Coverage note — The final lower bounds, their sequential-embedding basis, the adaptive privacy definition, and both upper-bound constructions are included. Proof-only packing details and auxiliary concentration inequalities are omitted because they do not add standalone contributed results.

References

1.Agarwal, N. and Singh, K. The price of differential privacy for online learning. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 32–40. PMLR, 06–11 Aug 2017.
2.Apple. Learning with privacy at scale, 2017.
3.Bafna, M. and Ullman, J. The price of selection in differential privacy. In Kale, S. and Shamir, O. (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 151–168. PMLR, 07–10 Jul 2017.
4.Bassily, R., Smith, A. D., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 464–473. IEEE Computer Society, 2014. doi: 10.1109/FOCS.2014.56.
5.Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Leonardi, S. and Gupta, A. (eds.), STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pp. 1671–1684. ACM, 2022. doi: 10.1145/3519935.3520064.
6.Ben-Eliezer, O., Jayaram, R., Woodruff, D. P., and Yogev, E. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, pp. 63–80, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371087. doi: 10.1145/3375395.3387658.
7.Ben-Eliezer, O., Eden, T., and Onak, K. Adversarially robust streaming via dense-sparse trade-offs. In Bringmann, K. and Chan, T. (eds.), 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, pp. 214–227. SIAM, 2022a. doi: 10.1137/1.9781611977066.15.
8.Ben-Eliezer, O., Jayaram, R., Woodruff, D. P., and Yogev, E. A framework for adversarially robust streaming algorithms. J. ACM, 69(2):17:1–17:33, 2022b. doi: 10.1145/3498334.
9.Bolot, J., Fawaz, N., Muthukrishnan, S., Nikolov, A., and Taft, N. Private decayed predicate sums on streams. In Proceedings of the 16th International Conference on Database Theory, ICDT ’13, pp. 284–295, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 9781450315982. doi: 10.1145/2448496.2448530.
10.Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Hirt, M. and Smith, A. D. (eds.), Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pp. 635–658, 2016. doi: 10.1007/978-3-662-53641-4_24.
11.Bun, M., Ullman, J., and Vadhan, S. Fingerprinting codes and the price of approximate differential privacy. SIAM Journal on Computing, 47(5):1888–1938, 2018.
12.Cardoso, A. R. and Rogers, R. Differentially private histograms under continual observation: Streaming selection into the unknown. In Camps-Valls, G., Ruiz, F. J. R., and Valera, I. (eds.), International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pp. 2397–2419. PMLR, 2022.
13.Chan, T. H., Shi, E., and Song, D. Private and continual release of statistics. IACR Cryptol. ePrint Arch., 2010: 76, 2010.
14.Chan, T. H., Shi, E., and Song, D. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011. doi: 10.1145/2043621.2043626.
15.Cheu, A. and Ullman, J. R. The limits of pan privacy and shuffle privacy for learning and estimation. In Khuller, S. and Williams, V. V. (eds.), STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pp. 1081–1094. ACM, 2021. doi: 10.1145/3406325.3450995.
16.Cohen, E., Lyu, X., Nelson, J., Sarlos, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 4112–4140. PMLR, 2022.
17.Denisov, S., McMahan, H. B., Rush, J., Smith, A. D., and Thakurta, A. G. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In NeurIPS, 2022.
18.Duchi, J., Jordan, M., and Wainwright, M. Local privacy and statistical minimax rates. In IEEE Symposium on Foundations of Computer Science, FOCS ’13, pp. 429–438, Berkeley, CA, USA, 2013.
19.Durfee, D. and Rogers, R. M. Practical differentially private top-k selection with pay-what-you-get composition. In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alche-Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 3527–3537, 2019.
20.Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ’06, pp. 486–503, St. Petersburg, Russia, 2006a.
21.Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265–284. Springer, 2006b.
22.Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differential privacy under continual observation. In Schulman, L. J. (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 715–724. ACM, 2010a. doi: 10.1145/1806689.1806787.
23.Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, S. Pan-private streaming algorithms. In Yao, A. C. (ed.), Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pp. 66–80. Tsinghua University Press, 2010b.
24.Dwork, C., Rothblum, G. N., and Vadhan, S. P. Boosting and differential privacy. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pp. 51–60. IEEE Computer Society, 2010c. doi: 10.1109/FOCS.2010.12.
25.Dwork, C., Naor, M., Reingold, O., and Rothblum, G. N. Pure differential privacy for rectangle queries via private partitions. In Iwata, T. and Cheon, J. H. (eds.), Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pp. 735–751. Springer, 2015. doi: 10.1007/978-3-662-48800-3_30.
26.Edmonds, A., Nikolov, A., and Ullman, J. R. The power of factorization mechanisms in local and central differential privacy. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy, J. (eds.), Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pp. 425–438. ACM, 2020. doi: 10.1145/3357713.3384297.
27.Fichtenberger, H., Henzinger, M., and Ost, W. Differentially private algorithms for graphs under continual observation. In Mutzel, P., Pagh, R., and Herman, G. (eds.), 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pp. 42:1–42:16. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2021. doi: 10.4230/LIPIcs.ESA.2021.42.
28.Ghazi, B., Kumar, R., Nelson, J., and Manurangsi, P. Private counting of distinct and k-occurring items in time windows. In Kalai, Y. T. (ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pp. 55:1–55:24. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, 2023. doi: 10.4230/LIPIcs.ITCS.2023.55.
29.Hardt, M. and Talwar, K. On the geometry of differential privacy. In Proceedings of the 42nd Annual ACM Symposium on the Theory of Computing, STOC ’10, pp. 705–714, New York, NY, USA, 2010. ACM.
30.Hardt, M., Ligett, K., and McSherry, F. A simple and practical algorithm for differentially private data release. In Bartlett, P. L., Pereira, F. C. N., Burges, C. J. C., Bottou, L., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 25, pp. 2348–2356, 2012.
31.Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algorithms via differential privacy. J. ACM, 69(6):42:1–42:14, 2022. doi: 10.1145/3556972.
32.Hay, M., Rastogi, V., Miklau, G., and Suciu, D. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow., 3(1):1021–1032, 2010. doi: 10.14778/1920841.1920970.
33.Hay, M., Machanavajjhala, A., Miklau, G., Chen, Y., and Zhang, D. Principled evaluation of differentially private algorithms using DPBench. In Ozcan, F., Koutrika, G., and Madden, S. (eds.), Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pp. 139–154. ACM, 2016. doi: 10.1145/2882903.2882931.
34.Jain, P., Kothari, P., and Thakurta, A. Differentially private online learning. In Mannor, S., Srebro, N., and Williamson, R. C. (eds.), Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 24.1–24.34, Edinburgh, Scotland, 25–27 Jun 2012. JMLR Workshop and Conference Proceedings.
35.Kairouz, P., Mcmahan, B., Song, S., Thakkar, O., Thakurta, A., and Xu, Z. Practical and private (deep) learning without sampling or shuffling. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5213–5225. PMLR, 18–24 Jul 2021.
36.Kaplan, H., Mansour, Y., Nissim, K., and Stemmer, U. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Malkin, T. and Peikert, C. (eds.), Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pp. 94–121. Springer, 2021.
37.Kasiviswanathan, S. P. and Smith, A. D. On the ’semantics’ of differential privacy: A Bayesian formulation. J. Priv. Confidentiality, 6(1), 2014. doi: 10.29012/jpc.v6i1.634.
38.Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. D. What can we learn privately? SIAM J. Comput., 40(3):793–826, 2011. doi: 10.1137/090756090.
39.McKenna, R. and Sheldon, D. R. Permute-and-Flip: a new mechanism for differentially private selection. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 193–203. Curran Associates, Inc., 2020.
40.McSherry, F. and Talwar, K. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, pp. 94–103, USA, 2007. IEEE Computer Society. ISBN 0769530109. doi: 10.1109/FOCS.2007.41.
41.Mironov, I., Naor, M., and Segev, G. Sketching in adversarial environments. SIAM J. Comput., 40(6):1845–1870, 2011. doi: 10.1137/080733772.
42.Perrier, V., Asghar, H. J., and Kaafar, D. Private continual release of real-valued data streams. In 26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24-27, 2019. The Internet Society, 2019.
43.Qiao, G., Su, W., and Zhang, L. Oneshot differentially private top-k selection. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8672–8681. PMLR, 18–24 Jul 2021.
44.Renyi, A. On measures of entropy and information. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, pages 547–561, Berkeley, Calif., 1961. University of California Press, abs/2101.10836, 1961.
45.Song, S., Little, S., Mehta, S., Vinterbo, S. A., and Chaudhuri, K. Differentially private continual release of graph statistics. CoRR, abs/1809.02575, 2018.
46.Steinke, T. and Ullman, J. R. Tight lower bounds for differentially private selection. In Umans, C. (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 552–563. IEEE Computer Society, 2017. doi: 10.1109/FOCS.2017.57.
47.Talwar, K., Thakurta, A., and Zhang, L. Nearly optimal private LASSO. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 3025–3033, 2015.
48.Thakurta, A. G. and Smith, A. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Burges, C. J. C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
49.Ullman, J., 2021. Personal communication.
50.Xiao, X., Wang, G., and Gehrke, J. Differential privacy via wavelet transforms. IEEE Trans. Knowl. Data Eng., 23(8):1200–1214, 2011. doi: 10.1109/TKDE.2010.247.
51.Yang, T., Andrew, G., Eichner, H., Sun, H., Li, W., Kong, N., Ramage, D., and Beaufays, F. Applied federated learning: Improving google keyboard query suggestions. CoRR, abs/1812.02903, 2018.
52.Yu, D., Naik, S., Backurs, A., Gopi, S., Inan, H. A., Kamath, G., Kulkarni, J., Lee, Y. T., Manoel, A., Wutschitz, L., Yekhanin, S., and Zhang, H. Differentially private fine-tuning of language models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.

Citation

MLA

Jain, P., et al. “The Price of Differential Privacy Under Continual Observation”. International Conference on Machine Learning, vol. 202, 2023, pp. 14654–78, https://proceedings.mlr.press/v202/jain23b.html.

APA

Jain, P., Raskhodnikova, S., Sivakumar, S., & Smith, A. (2023). The Price of Differential Privacy under Continual Observation. International Conference on Machine Learning, 202, 14654–14678. https://proceedings.mlr.press/v202/jain23b.html

Chicago

Jain, P., S. Raskhodnikova, S. Sivakumar, and A. Smith. 2023. “The Price of Differential Privacy Under Continual Observation”. International Conference on Machine Learning 202: 14654–78. https://proceedings.mlr.press/v202/jain23b.html.

Harvard

Jain, P. et al. (2023) “The Price of Differential Privacy under Continual Observation”, International Conference on Machine Learning. PMLR, pp. 14654–14678. Available at: https://proceedings.mlr.press/v202/jain23b.html.

Vancouver

1. Jain P, Raskhodnikova S, Sivakumar S, Smith A (2023) The Price of Differential Privacy under Continual Observation. In: International Conference on Machine Learning. PMLR, pp 14654–14678

BibTeX

@InProceedings{pmlr-v202-jain23b,
  title = 	 {The Price of Differential Privacy under Continual Observation},
  author =       {Jain, Palak and Raskhodnikova, Sofya and Sivakumar, Satchit and Smith, Adam},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {14654--14678},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/jain23b/jain23b.pdf},
  url = 	 {https://proceedings.mlr.press/v202/jain23b.html},
  abstract = 	 {We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of $T$ inputs and produces, after receiving each input, an output that is accurate for all the inputs received so far. We provide the first strong lower bounds on the error of continual release mechanisms. In particular, for two fundamental problems that are closely related to empirical risk minimization and widely studied and used in the standard (batch) model, we prove that the worst case error of every continual release algorithm is $\tilde \Omega(T^{1/3})$ times larger than that of the best batch algorithm. Previous work shows only a $\Omega(\log T)$ gap between the worst case error achievable in these two models. We also formulate a model that allows for adaptively selected inputs, thus capturing dependencies that arise in many applications of continual release. Even though, in general, both privacy and accuracy are harder to attain in this model, we show that our lower bounds are matched by the error of simple algorithms that work even for adaptively selected inputs.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

The Price of Differential Privacy under Continual Observation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Continual-release lower bounds for MaxSum

Knowl 2 — Continual-release lower bounds for SumSelect

Knowl 3 — Continual release with adaptively chosen inputs

Knowl 4 — Sequential embedding reductions for continual-release lower bounds

Knowl 5 — Adaptive-input binary-tree mechanisms

Knowl 6 — Adaptive-input mechanisms by periodic recomputation

Knowl 7 — Simulation-based privacy analysis for adaptive streams

Knowl 8 — The lower bounds do not depend on causal uncertainty

References

Citation

BibTeX

Access the Paper