Constant matters: Fine-grained Complexity of Differentially Private Continual Observation

Hendrik Fichtenberger, Monika Henzinger, Jalaj Upadhyay, Shirley, Morgan

Abstract

Differential privacy (DP) under continual observation is a critical framework for processing data streams. While the binary tree mechanism has been the standard approach, its error is characterized by jagged spikes and asymptotic bounds that hide significant constants. This work introduces a fine-grained error analysis using a novel lower-triangular matrix factorization. We demonstrate that our mechanism achieves a smoother, monotonic error that is approximately 4.5x smaller than the binary tree mechanism, providing tight, explicit constants for various streaming applications.

Introduction

In the continual release model, data arrives as a stream, and a privacy-preserving answer (such as a running count) must be provided after every new item. While the "binary tree mechanism" is the standard tool for this, it has two major drawbacks for practitioners:

  1. Jagged Error: The error is highly non-smooth; it depends on how many "dyadic intervals" are summed at a given time step, leading to unpredictable spikes that make the output hard to interpret.
  2. Unknown Constants: Theoretical bounds usually hide constants (e.g., $O(\log^{1.5} T)$), making it difficult to know if the algorithm will actually be accurate enough for a specific real-world use case, like monitoring disease incidence or ECG signals.

The authors aim to find a scalable mechanism with a smooth additive error and a tight, fine-grained error bound.

Methodology: The Matrix Mechanism for Streams

The authors leverage the matrix mechanism, a technique typically used for static datasets, and adapt it for streaming data. In the matrix mechanism, one defines a workload matrix $M$ that represents the queries of interest. To preserve privacy, noise is added to the data. The challenge in the streaming setting is that the mechanism must be "online"—it cannot use future data to answer current queries.

Lower-Triangular Factorization

This requirement translates to a constraint on the factorization of $M$: it must be decomposed into $M = LR$, where both $L$ and $R$ are lower-triangular matrices. This ensures the mechanism only uses past and current data. The authors derive a new, explicit factorization based on trigonometric identities and Toeplitz operators that achieves a near-optimal cb-norm.

Gaussian Noise and Privacy

Unlike the original binary tree mechanism which often uses Laplace noise, this work utilizes Gaussian noise to achieve $(\epsilon, \delta)$-differential privacy. This choice allows for tighter error bounds in many applications and facilitates the derivation of explicit constants.

Key Insights: Smoothness and Optimality

A primary contribution of this work is the demonstration that smoothness is a feature. In the standard binary tree mechanism, the error at time $t$ depends on the number of set bits in the binary representation of $t$. This leads to a "jagged" error profile where accuracy fluctuates wildly between adjacent time steps.

The proposed mechanism (blue) provides a much smoother and lower error compared to the jagged spikes of the standard binary tree mechanism (orange).

In contrast, the proposed factorization results in an error that is a monotonic, smooth function of the number of updates. This predictability is crucial for downstream applications like trend analysis or anomaly detection, where sudden spikes in noise could be mistaken for real signal changes. Furthermore, the authors show that the classic binary tree mechanism is suboptimal by a factor of roughly $\pi \log_2(e) \approx 4.5$ in terms of additive error.

Broad Applicability and Results

The paper evaluates the proposed mechanism using synthetic data streams, including Bernoulli streams and Zipfian distributions. In experiments, the proposed mechanism's signal-to-noise ratio (SNR) was consistently about 3x better than the binary tree mechanism for sparse streams.

Furthermore, the authors demonstrate that their "fine-grained" approach extends to a wide variety of problems, providing concrete upper bounds on error that are tight up to a very small additive gap when compared to known lower bounds.

Table 1: Summary of concrete error bounds for various applications under continual observation.

Conclusion and Future Work

This paper moves beyond asymptotic analysis to provide precise, actionable bounds for differentially private continual observation. By optimizing the constants and ensuring error smoothness, the authors bridge the gap between theoretical DP research and practical engineering needs. While a small gap remains between the theoretical upper bounds and the best-known lower bounds, this work significantly improves the state-of-the-art for practical streaming DP. Future work could aim to close this gap entirely or extend the analysis to pure $\epsilon$-DP settings.

Summary updated

Abstract

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate γ₂-factorization norm is a lower bound for these parameters and asked whether a stronger lower bound that replaces approximate γ₂ norm with the γ₂ norm holds. We answer the question of Linial and Shraibman in the negative by exhibiting a 2ⁿ×2ⁿ Boolean matrix with γ₂ norm 2^Ω(n) and randomized communication complexity O(log n). As a corollary, we recover the recent result of Chattopadhyay, Lovett, and Vinyals (CCC '19) that deterministic protocols with access to an Equality oracle are exponentially weaker than (one-sided error) randomized protocols. In fact, as a stronger consequence, our result implies an exponential separation between the power of unambiguous nondeterministic protocols with access to Equality oracle and (one-sided error) randomized protocols, which answers a question of Pitassi, Shirley, and Shraibman (ITSC '23). Our result also implies a conjecture of Sherif (Ph.D. thesis) that the γ₂ norm of the Integer Inner Product function (IIP) in dimension 3 or higher is exponential in its input size.
BibTeX
@inproceedings{fichtenberger2023constant,
  author = {Hendrik Fichtenberger and Monika Henzinger and Jalaj Upadhyay and Shirley, Morgan},
  title = {{Constant matters: Fine-grained Complexity of Differentially Private Continual Observation}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=SYCXOukbrJ},
}
Figure