Separating Oblivious and Adaptive Differential Privacy under Continual Observation

Connor Wagaman; Marco Gaboardi; Mark Bun

arxiv: 2603.11029 · v2 · submitted 2026-03-11 · 💻 cs.CR · cs.DS

Separating Oblivious and Adaptive Differential Privacy under Continual Observation

Mark Bun , Marco Gaboardi , Connor Wagaman This is my paper

Pith reviewed 2026-05-15 13:17 UTC · model grok-4.3

classification 💻 cs.CR cs.DS

keywords differential privacycontinual observationobliviousadaptivestreaming algorithmsseparationcorrelated vector queries

0 comments

The pith

An (ε,0)-DP algorithm stays accurate for exponentially many steps under oblivious continual observation while every (ε,δ)-DP adaptive algorithm fails after a constant number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper resolves an open question by exhibiting the first explicit separation between differential privacy under continual observation in the oblivious versus adaptive settings. In the oblivious case an (ε,0)-DP algorithm based on the correlated vector queries problem maintains accuracy for a number of time steps exponential in the input dimension. In the adaptive case every (ε,δ)-DP algorithm loses accuracy after only a constant number of releases. This separation shows that the two models are not equivalent once the adversary can choose the data stream adaptively based on prior outputs.

Core claim

We present an (ε,0)-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps in the dimension of the input. On the other hand, we show that every (ε,δ)-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps, via a reduction from the correlated vector queries problem.

What carries the argument

Reduction to the correlated vector queries problem, which is solvable accurately for long streams under oblivious DP but hard under adaptive DP.

Load-bearing premise

The known hardness properties of correlated vector queries apply directly to the adaptive continual observation model.

What would settle it

Discovery of an adaptive (ε,δ)-DP algorithm that maintains accuracy for more than a constant number of time steps on correlated vector queries.

read the original abstract

We resolve an open question of Jain, Raskhodnikova, Sivakumar, and Smith (ICML 2023) by exhibiting a problem separating differential privacy under continual observation in the oblivious and adaptive settings. The continual observation (a.k.a. continual release) model formalizes privacy for streaming algorithms, where data is received over time and output is released at each time step. In the oblivious setting, privacy need only hold for data streams fixed in advance; in the adaptive setting, privacy is required even for streams that can be chosen adaptively based on the streaming algorithm's output. We describe the first explicit separation between the oblivious and adaptive settings. The problem showing this separation is based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017). Specifically, we present an $(\varepsilon,0)$-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps in the dimension of the input. On the other hand, we show that every $(\varepsilon,\delta)$-DP adaptive algorithm fails to be accurate after releasing output for only a constant number of time steps.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first explicit separation between oblivious and adaptive continual DP by lifting the SODA 2017 correlated vector queries hardness into the streaming model with concrete bounds.

read the letter

The main takeaway is that this work closes the ICML 2023 open question with a concrete problem and explicit accuracy bounds rather than an abstract existence argument. In the oblivious setting they construct an (ε,0)-DP algorithm that stays accurate for exponentially many steps in the dimension. In the adaptive setting they show every (ε,δ)-DP algorithm loses accuracy after only a constant number of releases. That separation is the new piece and it is useful because it clarifies when the stronger adaptive model actually costs accuracy in practice. The upper bound reuses standard techniques for non-adaptive streams, which is appropriate and keeps the construction clean. The lower bound reduces to the known hardness of correlated vector queries, so the citation pattern is solid and there are no free parameters or circular definitions. The soft spot is the embedding step that turns the static hardness into a continual adaptive stream. The reduction must ensure that adaptive choices based on prior outputs cannot dodge the hard instance and that per-step error bounds aggregate to a contradiction after O(1) steps. The stress-test note correctly flags that any slack in how the continual outputs map back to a single vector-query answer could weaken the constant bound. If the full proofs track the parameters tightly, the separation holds as stated; the abstract claims it does, but the details matter. This is for people working on streaming privacy and continual release algorithms. It deserves a serious referee because it supplies the missing explicit separation with usable bounds even if the adaptive reduction needs careful verification in review.

Referee Report

1 major / 1 minor

Summary. The paper resolves an open question of Jain et al. (ICML 2023) by exhibiting an explicit separation between oblivious and adaptive differential privacy under continual observation. It gives an (ε,0)-DP algorithm for the oblivious setting, based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017), that remains accurate for exponentially many time steps in the input dimension. It also shows that every (ε,δ)-DP adaptive algorithm loses accuracy after only a constant number of time steps.

Significance. If the reduction and construction are correct, the result is significant: it supplies the first concrete problem separating the two models in the continual-release setting and shows that adaptivity can force accuracy to collapse after O(1) releases while the oblivious case permits exponentially many. The work directly leverages an existing hardness assumption rather than introducing new parameters, which strengthens its technical contribution.

major comments (1)

[Adaptive lower bound] Adaptive lower-bound section: the reduction that embeds a static correlated-vector-query instance into an adaptive continual stream must explicitly track how per-step (ε,δ)-DP accuracy aggregates to violate the SODA 2017 lower bound after O(1) steps. The current sketch does not detail the error-parameter mapping or prove that an adaptive adversary (whose next input may depend on prior releases) cannot evade the hardness; this embedding is load-bearing for the claimed constant-step failure.

minor comments (1)

[Abstract] The abstract states the oblivious algorithm is accurate for 'exponentially many time steps in the dimension' but does not name the precise accuracy parameter or the exact exponential dependence; adding one sentence would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for highlighting the need for greater detail in the adaptive lower-bound argument. We agree that the current sketch requires expansion and will revise the manuscript to include a complete, self-contained proof of the reduction.

read point-by-point responses

Referee: Adaptive lower-bound section: the reduction that embeds a static correlated-vector-query instance into an adaptive continual stream must explicitly track how per-step (ε,δ)-DP accuracy aggregates to violate the SODA 2017 lower bound after O(1) steps. The current sketch does not detail the error-parameter mapping or prove that an adaptive adversary (whose next input may depend on prior releases) cannot evade the hardness; this embedding is load-bearing for the claimed constant-step failure.

Authors: We agree that the sketch in the adaptive lower-bound section is insufficiently detailed. In the revised version we will add a full proof that explicitly maps the per-step (ε,δ) privacy parameters to the aggregate accuracy loss after a constant number of releases, showing that the total error exceeds the SODA 2017 lower bound. We will also prove that an adaptive adversary cannot evade the hardness: because the underlying correlated-vector-query instance is fixed in advance and the lower bound applies to any input sequence, the adaptive choice of subsequent inputs (conditioned on prior releases) is still constrained by the (ε,δ)-DP guarantee, which forces the same accuracy degradation as in the non-adaptive case. revision: yes

Circularity Check

0 steps flagged

No circularity: separation via reduction to independently published hardness result

full rationale

The paper's central separation is obtained by exhibiting an explicit (ε,0)-DP oblivious algorithm that remains accurate for exponentially many steps and by reducing any accurate (ε,δ)-DP adaptive continual algorithm to a solver for the correlated vector queries problem. The latter hardness is taken from the external SODA 2017 publication of Bun, Steinke, and Ullman, whose proof is independent of the present work and externally verifiable. No equations, definitions, or ansatzes in the abstract or described derivation chain reduce the claimed separation to a fitted parameter, self-definition, or unverified self-citation chain. The overlapping authorship on the cited hardness result constitutes ordinary self-citation and does not trigger circularity under the stated criteria.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard differential privacy definitions and the hardness of a previously published problem; no new free parameters or invented entities appear in the abstract.

axioms (2)

domain assumption Standard definitions of (ε,δ)-differential privacy in oblivious and adaptive continual observation models
Invoked to define the two settings being separated.
domain assumption Hardness of the correlated vector queries problem from Bun, Steinke, and Ullman (SODA 2017)
The adaptive lower bound is based on this prior result.

pith-pipeline@v0.9.0 · 5498 in / 1250 out tokens · 47608 ms · 2026-05-15T13:17:17.631733+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We present an (ε,0)-DP algorithm for the oblivious setting that remains accurate for exponentially many time steps... every (ε,δ)-DP adaptive algorithm fails... based on the correlated vector queries problem of Bun, Steinke, and Ullman (SODA 2017)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.2... randomized response... Hoeffding... Theorem 3.3... reconstruction lemma... sign(sum y(j))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.