A theoretical preprint reports that allowing a constant relative error can substantially reduce the additive error needed for differentially private continual release. Its proposed algorithms achieve polylogarithmic additive error for four tasks—MaxSum, MinSum, MaxSelect and MinSelect—except for MinSelect when the input stream is adaptive. In that case, the paper states that allowing relative error does not improve the best achievable additive error.
That split is the central finding. The analysis treats non-adaptive input streams and adversarially adaptive streams as different regimes, and reports the relative-error benefit across several tasks in the first regime while retaining a hard lower bound for adaptive MinSelect.
Two ways to measure error
Continual release asks a mechanism to keep producing answers as a stream advances. The accuracy target has two parts: relative error γ and additive error α, with the guarantee required uniformly at every round t and with failure probability β. The paper compares this target with purely additive-error guarantees.
The formal input is a stream of T vectors in [0, 1]^d: T records, each with d attributes whose values lie between zero and one. The analysis covers both streams fixed independently of the release process and streams whose later records may be generated adaptively.
The proposed mechanisms use a threshold test to monitor output error. While the current answer remains valid, it is left unchanged; when the answer becomes inaccurate, the mechanism launches a batch update. This update pattern supplies the paper’s continual-release framework.
Where the bounds improve
At a high level, the proposed algorithms achieve polylog(d, T) additive error when a constant relative error is allowed, covering the studied tasks except MinSelect with adaptive inputs. The result is an asymptotic guarantee: the notation hides polylogarithmic factors and constants rather than reporting an observed error rate.
Table 1 describes the upper and lower bounds as nearly tight and suppresses polylogarithmic dependence on d, T, 1/ε, 1/δ and 1/γ. It states that the MaxSum, MinSum and MaxSelect bounds apply to both non-adaptive and adaptive stream regimes. The authors still acknowledge gaps in those factors.
For a general estimator, the displayed pure-DP error bound is O(log(T/β)/(εγ)). Under approximate DP, the displayed bound is O((log(T/β)/ε)√(log(1/δ)/γ)). The theorem covers adaptive continual release for a nonnegative function whose one-step increase is at most one.
The symbols make the result conditional rather than a single prediction: γ is the relative-error parameter, β is the failure probability, and δ appears in the approximate-DP expression. These are scaling laws, not measurements from an empirical data set.
For MaxSelect, the pure-DP bound is O(log(dT/β)/(εγ)), while the approximate-DP bound is O((log(dT/β)/ε)√(log(1/δ)/γ)). The theorem provides adaptive continual-release (ε, δ)-privacy and (γ, α, β)-accuracy.
MinSelect has a separate theorem for non-adaptive streams. It provides (ε, δ)-privacy and (γ, α, β)-accuracy, with an additive-error bound combining logarithmic factors in d, T, γ and β with an inverse dependence on ε; approximate DP adds a factor tied to log(1/δ).
The adaptive exception
MinSelect changes the picture when input records are selected adaptively. The paper’s lower bound says that relative error does not improve the best achievable additive error in that regime, leaving a large additive lower bound close in form to the purely additive one.
The proof reduces private consensus-column sign identification to MinSelect, using zero-sum attributes in a generated stream. That construction transfers the difficulty of the private identification problem into the continual-release task.
For non-adaptive lower bounds, the paper constructs streams with small coordinate sums. In those streams, the relative-error term is negligible, so additive lower bounds transfer to the relative-plus-additive setting.
Assumptions that narrow the result
The improvement is tied to nonnegative inputs. The main formal setting uses vectors in [0,1]^d, while the appendix states that for inputs in [−1,1], an additive-error lower bound continues to hold even when relative error is allowed. The result therefore is not a general guarantee for signed inputs.
The study’s results are asymptotic theoretical guarantees, not empirical error estimates from a data set. The supplied analysis describes symbolic streams and theoretical matrices rather than participants or an empirical sample.
Other qualifications remain. The authors say the upper and lower bounds retain poly-logarithmic gaps, and some lower bounds rely on sufficiently large parameters and restrictions on δ. Those conditions limit how directly the asymptotic expressions can be read as finite performance claims.
What the paper leaves open
The authors identify closing the remaining poly-logarithmic gaps and determining whether relative-error improvements extend to other continual-release tasks as future directions. For now, the contribution is a set of mathematical privacy and accuracy guarantees, with the strongest separation appearing between non-adaptive streams and adaptive MinSelect.
Paper data and sources
Original title: Differentially Private Continual Release with Relative Error
Authors: Bo Li, Wei Wang, Peng Ye
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text