Differentially Private Continual Release with Relative Error

Bo Li, Wei Wang, Peng YeICML 2026 · OpenReview

Introduction

Differential Privacy (DP) has established itself as the gold standard for protecting individual privacy in data analysis. Historically, the bulk of DP research has focused on the batch model, where a static dataset is analyzed to release a single result. However, real-world applications frequently operate on continuous data streams—such as a traffic application updating congestion levels minute-by-minute or a server continuously monitoring user activity. This paradigm is known as the continual release model.

In a continual release setting, a single individual's data can influence every output from the moment it enters the stream until the end of time. This cumulative "privacy leakage" presents a formidable challenge. Recent research demonstrated a discouraging theoretical limit: for fundamental tasks like finding the maximum sum across different categories, the error in a stream must be exponentially larger than in a batch setting if measured purely additively.

This paper investigates a critical question: Can we bypass this exponential barrier by changing how we measure error? By shifting the focus from purely additive error to relative error, the authors demonstrate that high accuracy is achievable in many streaming contexts, though they uncover a striking mathematical separation between adaptive and non-adaptive environments.

The Power of Relative Error

Instead of demanding a "purely additive error" (e.g., "the answer is off by exactly $\pm 100$"), the authors explore the use of a relative error metric (e.g., "the answer is off by $10\%$ plus a small constant"). In many practical scenarios, a $10\%$ error is perfectly acceptable if the true value is large, and it allows for significantly higher accuracy when the true value is small.

By allowing a small relative error ($\gamma$), the additive error ($\alpha$) can be slashed from exponential levels down to poly-logarithmic levels. This makes DP streaming vastly more practical for "sparse" settings where many cumulative sums remain small over time.

Methodology: Monitor-and-Update

The authors propose a robust framework based on a "monitor-and-update" strategy to maintain privacy without sacrificing utility:

  1. Monitoring: The algorithm maintains its current released answer as long as it remains "accurate enough." It utilizes the AboveThreshold mechanism—a standard DP tool—to check if the error has crossed a predefined threshold without unnecessarily depleting the privacy budget.
  2. Updating: Once the error exceeds the acceptable threshold, the algorithm performs a "batch" update. It uses the Laplace Mechanism for estimating sums or the Exponential Mechanism for selecting the best attribute.
  3. Privacy Budget Management: A key innovation is the dynamic management of the privacy parameter ($\epsilon$). By gradually decreasing the privacy parameter as the sums grow, the algorithm keeps the total error poly-logarithmic relative to the stream length ($T$) and the number of attributes ($d$).

For the specific task of MinSelect (picking the attribute with the smallest cumulative sum) in non-adaptive streams, the authors employ a sophisticated potential analysis to prove that the algorithm rarely needs to update, even if the "minimum" attribute fluctuates frequently.

The Adaptive vs. Non-Adaptive Divide

The most significant theoretical discovery in the paper is a fundamental "separation" in the MinSelect task based on the nature of the data stream.

  • Non-Adaptive Streams: When the data stream is fixed before the algorithm starts, the monitor-and-update approach successfully achieves low error.
  • Adaptive Streams: When an adversary (or the environment) picks the next data point based on the algorithm's previous answers, a large error becomes mathematically unavoidable.

The authors illustrate this adaptivity through a traffic analogy: if a city releases real-time traffic data, drivers will change their routes based on that exact data, which in turn alters the subsequent traffic patterns. This continuous feedback loop is precisely what makes adaptive streams fundamentally harder to privatize.

Key Results and Error Bounds

As a theoretical work, the paper relies on mathematical constructions rather than empirical datasets to prove its bounds. It maps out a comprehensive landscape of error limits for continual release tasks:

  • MaxSum, MinSum, and MaxSelect: These tasks achieve an additive error of roughly $O(\text{polylog}(d, T) / \epsilon\gamma)$ in both adaptive and non-adaptive settings. This represents a massive improvement over previous purely additive bounds.
  • MinSelect (Non-Adaptive): Achieves a similar poly-logarithmic error.
  • MinSelect (Adaptive): The authors prove a lower bound showing that the error must be at least $\tilde{\Omega}(\sqrt{d}/\epsilon)$ or $\tilde{\Omega}(T^{1/3}/\epsilon^{2/3})$. In this specific adversarial case, relative error provides no benefit over the purely additive setting.

Limitations and Future Directions

While the paper makes significant strides in DP continual release, the authors note a few limitations that pave the way for future research:

  1. Poly-logarithmic Gaps: Although the upper and lower bounds are "nearly matching," there remain small mathematical gaps (factors of $\log d$ or $\log T$) that future work could close.
  2. Non-Negative Inputs: The current algorithms assume data is non-negative (restricted to the range $[0, 1]$). If negative inputs are introduced, the relative error mathematical "trick" breaks down, and the exponential error barriers return.
  3. Expanding the Task List: Future research should explore whether the relative error framework can provide similar accuracy boosts for more complex streaming statistics beyond simple sums and selections.

Summary updated

Abstract

This work investigates several fundamental tasks, including $\mathsf{MaxSum}$, $\mathsf{MinSum}$, $\mathsf{MaxSelect}$, and $\mathsf{MinSelect}$, in the continual release model under differential privacy. Previous research has demonstrated that any algorithm for these tasks must admit a large purely additive error. We show that the error can be substantially reduced if a relative error term is allowed, provided that the input stream is generated non-adaptively. However, when input data records can be selected adaptively, we prove that a large error is inevitable for the task of selecting an attribute with a small cumulative sum, whereas small error bounds remain achievable for other tasks. This reveals a significant separation between non-adaptive and adaptive streams. We also complement our algorithms with nearly matching lower bounds.
BibTeX
@inproceedings{li2026differentially,
  author = {Bo Li and Wei Wang and Peng Ye},
  title = {{Differentially Private Continual Release with Relative Error}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=F5hjwtBmsV},
}
Figure