Private online learning and prediction for Littlestone classes

Private online learning and prediction for Littlestone classes Amartya Sanyal Department of Computer Science

arXiv:2610.06822v1 [cs.LG] 5 Oct 2026

University of Copenhagen amsa@di.ku.dk

Abstract We study differentially private online learning and jointly private online prediction against oblivious realisable adversaries. Online learning releases a hypothesis before observing each example, whereas online prediction releases only a prediction for the current instance. For every class of finite Littlestone dimension d ≥ 2, every (ε, δ)-private online learner incurs Ω(min{(d/ε)(log T )2/3 , d/δ}) expected mistakes on some deterministic realisable stream of length T , provided 0 < ε ≤ 1, 0 ≤ δ ≤ min{ε2 , 1/4}, and T ≥ (d/ε)2 . We also prove an Ω(min{(log(2T ))2/3 , 1/δ}) lower bound for point functions on a three-element domain at ε = 1/100 and 0 ≤ δ ≤ 1/4. For private prediction, every nonempty class of finite Littlestone c(d+1)2

dimension d admits an (ε, δ)-jointly private predictor with at most 22 ε−2 log2 (2/(εδ)) expected mistakes, independently of T , for 0 < ε ≤ 1, 0 < δ < 1/10, and an absolute constant c > 0. Thus, for fixed d ≥ 2 and ε, at δ = Θ(1/ log T ), private learning requires Ω((log T )2/3 ) expected mistakes, whereas private prediction admits O((log log T )2 ). The same separation holds for point functions on three elements at ε = 1/100.

1

Introduction

In realisable online learning, given a hypothesis class H, a learner predicts the labels of a sequence of examples consistent with one unknown h ∈ H. It is well known that if the class H has Littlestone dimension Ldim (H) = d, then the Standard Optimal Algorithm makes at most d mistakes on any stream, independently of the horizon T [Lit88]. Additionally, this bound is also known to be tight; thus Littlestone dimension tightly characterises the mistake bound for realisable online learning. Private online learning Under differential privacy, there exist algorithms with mistake bounds logarithmic in T for fixed privacy parameters [GL21, Lyu26]. Whether this dependence on the horizon is necessary was posed as an open question in [SR22]. Subsequent lower bounds have shown that this logarithmic dependence may be necessary, but only for certain algorithms [DSS24], hypothesis classes [CLN+ 24], or ranges of δ, (δ ≤ ε/T in [LWY24]). This raises the following question: Question. How many mistakes must an arbitrary private online learner make on a fixed hypothesis class for every value of δ? We make progress on this question in the range of δ left open by prior work, up to order 1/ log T . We prove a lower bound polynomial in log T , first for point functions on three elements and then for every class of finite Littlestone dimension at least two. Our argument starts with a simpler class, point functions on a three-element domain: POINT3 = {f1 , f2 , f3 } ,

fj : {1, 2, 3} → {0, 1} , 1

fj (x) = 1 {x = j} .

Result

Point domain

DP Learner

Lower bound

[DSS24]

{1, 2, 3}

Concentrated

Ω (log T )

[CLN 24]

{0, . . . , T }

All

Ω (log T )

[LWY24]

{1, 2, 3}

All

Theorem A

{1, 2, 3}

All

Ω (log log T )   2/3 Ω (log T )

+

Table 1: Lower bounds for expected total mistakes of private online learners on POINT3 at δ = 1/(log T ). [DSS24, LWY24]’s results also extend to other Littlestone classes. [CLN+ 24] considers point functions on {0, . . . , T }, a domain that grows with T . The [LWY24] entry follows by setting T ′ = ⌊ε log T ⌋, applying their theorem to the first T ′ rounds, and filling the remaining rounds with dummy points.

This class has Littlestone dimension one and a single mistake suffices without privacy. The main point is that f1 and f2 agree at point 3 but disagree at point 1; thus one mistake at 1 suffices. We first prove a lower bound for this problem with online DP in Theorem A and then extend this to every class of Littlestone dimension at least two in Theorem B. Theorem A. For ε0 = 1/100 and 0 ≤ δ ≤ 1/4, every (ε0 , δ)-differentially private online learner of POINT3 has a realisable stream of length T on which 



E [MT ] = Ω min (log (2T ))

2/3

1 , δ



.

 At δ = Θ(1/ log T ), Theorem A improves the Ω (log log T ) [LWY24, see Table 1 caption] to

Ω (log T )2/3 for arbitrary private learners on POINT3 . Table 1 compares our bound to existing bounds for this range of δ. As shown in Figure 1, a gap remains to the O (log T ) upper bound [GL21, LWY24] for this range of δ. For polynomially small δ, the Ω (log T ) lower bound of [LWY24] is stronger and tight. When δ ≥ (log T )−2/3 , Theorem A matches the O (1/δ) upper bound using the name-and-shame variant of SOA [DSS24]. General Littlestone Classes: Our next result gives a lower bound linear in d, for every class with d ≥ 2, while retaining the polylogarithmic dependence on T that we show for POINT3 . Theorem B. Let H have finite Littlestone dimension d ≥ 2. For 0 < ε ≤ 1, 0 ≤ δ ≤ min ε2 , 1/4 , and T ≥ (d/ε)2 , every (ε, δ)-differentially private online learner of H has a deterministic realisable stream of length T on which 

d d E [MT ] = Ω min (log T )2/3 , ε δ 





.

Intuitively, a shattered Littlestone tree supplies d successive stages in the non-private setting, at each of which a learner can be forced to make a mistake. In our setting, the tree supplies Θ(d) phases, each instantiating the hard construction underlying Theorem 1. Following a single path through the tree keeps the entire stream realisable, while the mistake contributions from successive phases add. The construction is visualised in Figure 3. For fixed d and ε, this is, to our knowledge, the first lower bound polynomial in log T that applies to every such class and every private learner when δ = Θ (1/ log T ). Private online prediction The lower bounds above show that private online learning can require a number of mistakes growing polynomially with log T . We next consider the slightly easier problem 2

[LWY24] Other upper bounds: [GL21, LWY25, Lyu26] [AFKT23, BF26] E [MT ]

log T

[LW

(log T )2/3

Y24 ]

Theorem 1 (Ours)

[D SS 24

]

δ 0 δ ≤ T −a

e−(log T )

3/4

e−(log T )

2/3

(log T )−1 (log T )−2/3

1/4

Figure 1: Expected total mistakes E [MT ] for POINT3 at ε = 1/100. Solid curves are upper bounds and dashed curves are lower bounds; grey shading marks the open gap. of private online prediction. Here, the algorithm observes xt , releases only its prediction for xt , and then observes yt . For point functions, [CLN+ 24] already gives a prediction mistake bound independent of the horizon T and polylogarithmic in 1/δ, but the corresponding question remains open for general classes. Question. Does every class of finite Littlestone dimension admit an (ε, δ)-jointly private online predictor whose expected mistake bound is independent of T and polylogarithmic in 1/δ, on every fixed realisable stream? We answer this question affirmatively. Intuitively, in online learning, the learner releases a hypothesis at every round. Its predictions at informative points are therefore visible even on rounds when it receives a dummy example. The learner receives informative examples only occasionally, but its released hypotheses reveal predictions at those points throughout the stream. This makes the prediction setting harder for the adversary. In the prediction setting, the privacy guarantee excludes the prediction at the round where the neighbouring streams differ. In online learning, the hypothesis released at that round does not depend on the current example, since it is released before that example is observed. Below, we show that every class of finite Littlestone dimension admits an expected mistake bound independent of T , with polylogarithmic dependence on 1/δ. Theorem C. Let H be nonempty with finite Littlestone dimension d. For 0 < ε ≤ 1 and 0 < δ < 1/10, there is an (ε, δ)-jointly differentially private online predictor such that, on every fixed realisable stream of length T , c(d+1)2

E [MT ] ≤

22

ε2

log2

2 , εδ

where c > 0 is an absolute constant. For every fixed class of finite Littlestone dimension d ≥ 2, Theorems B and C separate private online learning from   private online prediction. At fixed ε and δ = Θ (1/ log T ), the  former re 2/3 quires Ω (log T ) expected mistakes on some stream, whereas the latter admits O (log log T )2 expected mistakes on every realisable stream. The same separation also holds for POINT3 by Theorem A.

3

1.1

Problem setting and preliminaries

Setting Let H ⊆ {0, 1}X be a nonempty binary hypothesis class and let T ≥ 1 be the time horizon. Write Sr = (xr , yr ) ∈ X × {0, 1} for the labelled example at round r, and S = (S1 , . . . , ST ) for the input stream. The stream S is fixed independently of the algorithm’s randomness. This is the oblivious setting in online learning. In this work, we use replacement adjacency: two streams S, S ′ of the same length are neighbouring if they differ in at most one labelled example. Definition 1 (Online learning game). For each round r = 1, . . . , T : 1. The randomised learner A releases a predictor hr : X → {0, 1}. 2. The learner observes (xr , yr ). The predictors released by the learner need not belong to H. We say the learner incurs a mistake when its prediction ŷr = hr (xr ) is incorrect, i.e., when ŷr ̸= yr . Definition 2 (Differentially private online learning). Write A (S) = (h1 , . . . , hT ) for the learner’s complete output. For ε ≥ 0 and 0 ≤ δ < 1, the learner is (ε, δ)-DP if, for every pair of neighbouring streams S, S ′ and every measurable output event E, P [A (S) ∈ E] ≤ eε P A S ′ ∈ E + δ. 



We next consider the slightly weaker online prediction model. Definition 3 (Online prediction game). For each round r = 1, . . . , T : 1. The predictor observes xr and then releases a bit ŷr . 2. The predictor observes yr . Definition 4 (Jointly differentially private online prediction). Let Ŷ (S) = (ŷ1 , . . . , ŷT ) and write Ŷ−i (S) for this vector with coordinate i removed. For ε ≥ 0 and 0 ≤ δ < 1, the predictor is (ε, δ)-jointly differentially private if, for every i ∈ {1, . . . , T }, every pair of streams S, S ′ agreeing outside round i, and every measurable output event E, h

i

h

i

P Ŷ−i (S) ∈ E ≤ eε P Ŷ−i S ′ ∈ E + δ.

The stream is said to be realisable by H if there is a single f ∈ H such that f (xr ) = yr for every P r. In either model, the total number of mistakes is MT = Tr=1 1 {ŷr ̸= yr }, where 1 {E} is the indicator of an event E. On a fixed stream, the expectation E [MT ] is computed over the algorithm’s randomness. We write d = Ldim (H) (see Definition 6) and call H a Littlestone class when d < ∞. Our main lower bound argument uses the following simple class. Definition 5 (Three-point class). On the instance space {1, 2, 3}, let POINT3 = {f1 , f2 , f3 } ,

fj : {1, 2, 3} → {0, 1} ,

fj (x) = 1 {x = j} .

The class POINT3 has Littlestone dimension one: both labels are possible at each point, but prescribing label one leaves only one hypothesis. The hypotheses f1 , f2 agree at point 3 and disagree at point 1. In our arguments, we choose a bit B ∈ {0, 1} uniformly, independently of the learner’s randomness. Then we denote (3, 0) as the dummy example and (1, B) is the informative example. Every stream consisting of these two examples is realisable: f1 realises it when B = 1, and f2 when B = 0. Finally, all logarithms are natural unless another base is specified. Terms involving 1/δ are interpreted as +∞ when δ = 0. Constants hidden by O, Ω, and Θ are absolute unless stated otherwise. 4

1.2

Technical ideas

Lower bound for private online learning. For POINT3 , earlier work [DSS24] used the concentration assumption that the learner with high probability predicts the same label at point 1 in an all-dummy stream. Then, the adversary inserts informative examples with the opposite label, which causes the learner to incur mistakes whenever it outputs its preferred label. Privacy constrains how these insertions change the output distribution. This allows the adversary to place informative examples where mistakes are likely. Our goal is to force mistakes without this concentration assumption. We instead sample a uniformly random bit B at the beginning and use it as the label for every informative example. On the dummy stream, the prediction at point 1 is independent of B, even if the predictions keep changing (i.e. no concentration or similar prior). Therefore, the first insertion of (1, B) causes a mistake with probability 1/2 because the hypothesis is released before the example arrives. However, this also reveals B to the learner. The main challenge is therefore to control how much the learner’s predictions reveal about B before subsequent informative examples. Writing Yr = hr (1), we track Var (E [B | Y1:r ]), the variance of the posterior probability that B = 1. This measures the mean squared deviation of the posterior probability of B = 1 from its prior value of 1/2. If this variance can be kept small during rounds where informative examples are shown, then the learner is forced to err on a constant fraction of these examples in expectation. We construct the entire stream of length T in L = log3 T recursive stages agnostic of the learning algorithm. At each stage, we choose a uniformly random third of the remaining interval. If we choose the middle third, we insert an informative example at a uniformly random position in the first third with probability p. We then recurse inside the chosen third. This gives Lp/3 informative examples in expectation. We compare an insertion in the first third, which may affect middle-third predictions, with a counterfactual insertion in the last third, which cannot affect those predictions. See Figure 2 for a visualisation of the construction and the effect of the counterfactual insertion. Here we track a second variance: how the effect of an informative point insertion on the output distribution varies with the location of the insertion. Our proof accounts for two competing effects. First, as mentioned above, we continue the recursion inside a uniformly chosen third. By standard variance decomposition, the average variance over insertion locations within that third equals the original variance minus the variance between thirds. We use this decrease to control the information revealed about B. Second, new insertions can add to the variance, but privacy limits this increase. Accounting for both effects over the recursion controls how well the released predictions can identify B before subsequent informative examples. The posterior variance Var (E [B | Y1:r ]) before a possible
2 + Lp3 + Lpδ . Choosing p as a sufficiently small constant informative insertion is at most O p n o  n o times min L−1/3 , 1/(Lδ) keeps this variance small and yields Ω (Lp) = Ω min (log T )2/3 , 1/δ expected mistakes. We extend the lower bound to general Littlestone classes by roughly applying the same construction at nodes along a path down a shattered tree (see Figure 3). Upper bound for private prediction. For private prediction, we first construct a short private sequence of predictors that, with high probability, contains at least one with few mistakes on the full stream. The first difficulty is to bound the number of bad predictors in this list even when the hypothesis class is infinite. Using the idea of essential hypotheses [Lyu26], we create multiple short lists of predictors with the useful property that predictors can be added to these lists online using only earlier mistakes. We then use a private selection mechanism to choose a frequently appearing predictor among these lists. A contradiction argument (Lemma 3) then shows that the number of bad predictors is bounded independently of T .

5

The next challenge is to use these candidates privately online. Each candidate can be computed from the observed prefix once its predecessor has made enough mistakes. However, switching immediately to a new candidate can be privacy-violating. Unlike online learning, in online prediction, only the prediction at the current point is released. Thus, on dummy examples where the old and new predictors agree, the learner can switch its internal predictor while continuing to give the same answer that it would have given before the switch. We use a private replacement mechanism based on the Mirror mechanism [CLN+ 24] with increasing delays before each switch to implement this in a private manner. The key property is that, while the latest available candidate has made few mistakes, later candidates cannot change the current predictions. Since these mistakes are precisely what is needed to compute the next candidate, we can ignore that candidate until enough mistakes are made or for the rest of the game if this never happens. The resulting online predictor has a mistake bound Q, independent of T , that holds with probability at least 1 − δ. However, this bound alone only guarantees Q + δT expected mistakes. We therefore need one additional step to get the bound in expectation. We combine our predictor with a subsampled SOA algorithm [DSS24], whose expected mistakes are O (d/δ). Intuitively, this algorithm runs a competition between the two predictors and guarantees that the combined predictor competes with the better one in expectation, up to a constant factor and an additive term independent of T (Lemma 13). This removes the remaining dependence on T .

1.3

Related work

Private online learnability for every class of finite Littlestone dimension was first shown in [GL21]. Against oblivious adversaries, their realisable mistake bound has logarithmic dependence on T for fixed privacy parameters, but doubly-exponential dependence on the Littlestone
dimension d. e d9.5 log T log (1/δ) /ε , also against More recently, [Lyu26] obtained the high-probability bound O e (log T log (1/δ)). oblivious adversaries. On POINT3 at fixed ε, they give O In contrast to oblivious adversaries, adaptive adversaries may choose using the learner’s  examples  O(d) 2 previous outputs. In this setting, [LWY25] gives a mistake bound O 2 (log T + log (1/δ)) /ε . For POINT3 at fixed ε, this is O (log (T /δ)), and hence O (log T ) whenever δ ≥ T −a for fixed a > 0. The same work also establishes sublinear regret for general Littlestone classes in the agnostic setting, where the labels need not be realisable. Our work does not consider the agnostic or the adaptive setting but rather focuses on the oblivious setting with realisable streams. Recent works on lower bounds for private counting have also used similar techniques to obtain polylogarithmic lower bounds. [HL26] used the same variance decomposition and recursion, while [BDL26] used a related argument to accumulate noise along a tree. The main difference in this regard between our work and theirs is the probability event to which these arguments are applied. Importantly, continual counting with ℓ∞ error is known to be related to our problem of online learning via a reduction from private counters to private online learners for point functions [DSS24, CLN+ 24]. Thus, online-learning lower bounds imply counting lower bounds, with weaker parameters. The counting lower bounds do not, however, directly imply our online-learning lower bound. Online prediction under joint differential privacy releases only the answer to the current query, and + does not require this answer to hide the current example.  For general Littlestone classes, [KMM 23] e d2 ε−2 log2 (1/δ) log2 (T /β) with probability at least 1 − β. Their result gives the mistake bound O allows adaptive inputs and satisfies the stronger challenge-privacy definition of that work. Our guarantee concerns oblivious streams and joint privacy, and removes the dependence on T . For point  2 + −2 functions on any domain, [CLN 24] gives O ε log (1/δ) prediction mistakes, independently of the horizon T . However, their result does not apply to every hypothesis class with finite Littlestone

6

dimension. To the best of our knowledge, our result is the first horizon-independent guarantee with polylogarithmic dependence on 1/δ for every class of finite Littlestone dimension.

2

Lower Bounds for Online Learning

2.1

Lower bound for POINT

We first prove the lower bound for POINT3 . Our strategy is to place informative examples at randomly chosen positions in the stream and show that the learner errs on a constant fraction of them in expectation. Theorem 1. For ε = 1/100, 0 ≤ δ ≤ 1/4, and every (ε, δ)-differentially private online learner of POINT3 , there is a realisable stream of length T on which 

E [MT ] ≥ c min (log (2T ))

2/3

1 , , δ 

where c > 0 is an absolute constant. Proof of Theorem 1. For T = 1, 2, use (1, B) at the first round, where B is a fair bit, and leave any remaining round dummy. The expected number of mistakes at the first round is 1/2, so some fixed choice of B gives the claimed bound after decreasing c if necessary. We henceforth assume T ≥ 3. We first describe the adversary’s strategy for a parameter p ∈ (0, 1]. The adversary initialises a stream of length T consisting entirely of dummy examples (3, 0) and samples a bit B ∈ {0, 1} uniformly at random. Then, starting from the dummy stream, the adversary proceeds in L = ⌊log3 T ⌋ stages, starting with the interval A0 = (0, 3L ] and leaving all later rounds dummy. In each stage, the adversary partitions the remaining interval into three equal parts and chooses one of the thirds uniformly at random. If the middle third is chosen, then with probability p, the adversary replaces a uniformly chosen dummy example in the first third with an informative example (1, B); otherwise, it does nothing. The adversary then proceeds to the next stage by restricting to the chosen interval and repeating the process. See Figure 2(a) for an illustration and Algorithm 1 for a formal description. The expected number of informative examples in the stream is Lp/3. The online learner releases a hypothesis hr at each round r ∈ {1, . . . , T }; let Yr = hr (1). For each t, consider running the online learner on the stream constructed by the adversary after the first t stages above with no subsequent h insertions. Conditionali on the adversary’s choices of 1 thirds through stage t, define Vt (r) = E (E [2B − 1 | Y1 , . . . , Yr ])2 , with Vt (0) = 0, to measure how much the learner’s outputs through round r reveal about B. Let At = (at , bt ] be the interval remaining after t stages, and define It = Vt (at ) + 2 (Vt (bt ) − Vt (at )) . Here E [It ] averages over the adversary’s choices of thirds. The following lemma shows that, if E [It ] is small, the learner makes mistakes on a constant fraction of the informative examples inserted at stage t + 1, in expectation. 

Lemma 1. The expected number of mistakes contributed by stage t + 1 is at least p6 1 − 1

p

Here t ∈ {0, . . . , L} counts completed recursive stages, and r ∈ {1, . . . , T } indexes the learner’s rounds.

7



E [It ] .

(a) Recursive construction

(b) Comparing first and last third

Choose a third uniformly. 1/3 1/3

Adversary can plan (1, B) in the first third First Middle Last

1/3

(1, B)

At+1

probability p

selected third

dummy points

(1, B) may affect

next recursive stage

Counterfactual insertion

1/3

1/3

1/3

(1, B) Unaffected by later insertion

Choose again, uniformly. Repeat for L = ⌊log3 T ⌋ stages.

analysis only

Learner rounds r

Figure 2: In (a), we recurse inside a uniformly chosen third. If we choose the middle third, we insert an informative example at a uniformly random position in the first third with probability p; otherwise, we make no insertion. In (b), we compare this insertion with a counterfactual insertion in the last third. The first may affect the middle-third predictions (vertical marks), whereas the counterfactual insertion cannot, since those predictions are made before the example arrives. An immediate consequence of Lemma 1 is that, if E [It ] ≤ 1/4 for every 0 ≤ t < L, the expected number of mistakes on informative examples is at least Lp/12. We next show that 

E [It ] ≤ C p2 + tp3 + tpδ



(1)

n

for a universal constant C. Then, choosing p = c0 min L−1/3 , 1/ (δL) c0 > 0 ensures that E [It ] ≤ 1/4 for every 0 ≤ t < L and E [MT ] ≥

o

for a sufficiently small

 n o Lp = Ω min L2/3 , 1/ (δ) . 12

It remains to prove (1). So far, we have not used the fact that the online learner is differentially private. Fix the adversary’s choice of the thirds through stage t and b ∈ {0, 1}. Let P∅b denote the distribution of Y = (Y1 , . . . , YT ), conditional on B = b, when the learner runs on the stream constructed through stage t, with no further insertions. For s ∈ At where At := (at , bt ], let Psb denote the corresponding distribution after additionally replacing the dummy example at round s with (1, b), leaving all other entries unchanged. For each fixed realisation of the earlier insertions, the streams defining P∅b and Psb differ only at round s. For every y with P∅b (y) > 0, define ℓbs (y) to be Psb (y)/P∅b (y) clipped to [e−ε , eε ]. Differential privacy gives Psb − P∅b ℓbs ≤ 2δ. 1

We now define two quantities Wt and Dt to measure the variance of this ratio within one stage At and the difference between the average ratios of the first and last thirds of At , respectively: h

i

Wt = E Vars∈At (ℓB s ) ,

Dt = E

 B

B

2 

B

B

ℓA1t − ℓA3t

.

Here the expectation is over the joint distribution of (B, Y ) and ℓA1t , ℓA3t are the averages of ℓB s 1 3 over s ∈ At and s ∈ At , respectively. Compare an insertion in the first third with a hypothetical 8

insertion in the last third, as illustrated in Figure 2(b). The latter cannot affect predictions in the middle third, since the learner has not yet received that example. The quantity Dt measures the squared difference between the effects of these two insertions. Suppose the middle third is chosen, so bt+1 is its right endpoint. For any two round indices at ≤ u ≤ v ≤ bt+1 , comparing the reduction in the best expected squared error for estimating 2B − 1 before and after the insertion gives Vt+1 (v) − Vt+1 (u) ≤ 2 (Vt (v) − Vt (u)) + 8p2 Dt + 16pδ. Inserting with probability p multiplies the first-versus-last difference by p, giving p2 Dt after squaring. The pδ term accounts for clipping. Averaging over the three choices and using the definition of It gives the first inequality in Lemma 2. On the other hand, a large Dt means that a substantial part of the variance in Wt comes from the differences between the thirds. Restricting to within a third removes this between-third variation, and therefore reduces the variance within a third. Variance decomposition gives 3 h i Dt 1X E Vars∈Aj (ℓB ) ≤ Wt − . s t 3 j=1 6

We must also account for the possible insertion when the middle third is chosen. Using privacy again and convexity of variance, the increase is at most p times the variance of the ratios on the insertion branch, plus the clipping error δ. These ratios lie in [e−ε , eε ], so their variance is at most (eε − e−ε )2 /4. Averaging over the three choices gives E [Wt+1 | J≤t ] −

3 h i p (eε − e−ε )2 δ p+δ 1X E Vars∈Aj (ℓB ) ≤ · + ≤ , s t 3 j=1 3 4 3 3

where the last inequality uses (eε − e−ε )2 ≤ 4. Combining these bounds gives the second inequality in the following lemma. See the proof of Lemma 2 for the full details. Lemma 2. For every 0 ≤ t < L E [It+1 | J≤t ] ≤ It + 20p2 Dt + 20pδ Dt p + δ + . 6 3 where J≤t denotes the adversary’s choices of thirds through stage t. E [Wt+1 | J≤t ] ≤ Wt −

(2) (3)

Now multiplying (3) above by 120p2 , adding it to (2), and taking an expectation on both sides gives E [It+1 ] ≤ E [It ] + 120p2 (E [Wt ] − E [Wt+1 ]) + 40p3 + 60pδ Summing this inequality for t = 0, . . . , m − 1, where 1 ≤ m ≤ L, and using I0 = 0, W0 ≤ 1, and Wm ≥ 0, gives   E [Im ] ≤ 120p2 + 40mp3 + 60mpδ ≤ 120 p2 + mp3 + mpδ . This completes the proof of (1) with C = 120 and hence of Theorem 1.

9

x0 1

0

unused subtree

x1

0

1

(x1 , 0) (x0 , 0) (z1 , 1)

0 (x2 , 0) (x0 , 0) (z2 , 1)

x2

1

0

(x2 , 1) (x0 , 0) (z2 , 0)

x4

x5

c0 (log n)2/3 ε expected mistakes ≥

(x1 , 1) (x0 , 0) (z1 , 0)

x3

(x3 , 0) (x0 , 0) (z3 , 1)

d − 1 blocks on one path

1 (x3 , 1) (x0 , 0) (z3 , 0)

x6

x7

h⋆ Figure 3: A shattered Littlestone tree with d − 1 hard blocks along a root-to-leaf path after the initial zero edge. Each block applies the POINT3 construction from Theorem 1 using the parent point xi as its informative point and x0 as its shared dummy. The point zi is the unused third point of this construction and never appears in the stream (as in Theorem 1). The informative label B is the label of the edge.

2.2

Lower bound for general Littlestone classes

We now extend the lower bound to general Littlestone classes. The main idea is to apply the two-label construction at successive nodes of a shattered tree, following [DSS24, LWY24]. Theorem 2. Let H ⊆ {0, 1}X have finite Littlestone dimension d ≥ 2, and let T ≥ 1. Suppose that 0 < ε ≤ 1 and 0 ≤ δ ≤ min ε2 , 1/4 . For every (ε, δ)-differentially private online learner of H, there is a deterministic realisable stream of length T on which (

d εT E [MT ] ≥ c min T, log 2 + ε d 



2/3

d , δ

)

,

where c > 0 is an absolute constant. Proof sketch. We give the proof in the regime T ≥ (d/ε)2 , δ ≤

ε . The full proof, covering all (log T )2/3

parameter ranges, is given in Section 6. Take a depth-d tree shattered by H and follow the zero (left) edge at its root x0 . The remaining subtree has depth d − 1, and every hypothesis realising one of its paths agrees on (x0 , 0). We use this as the dummy example throughout. Divide the horizon into k = d − 1 phases of length n = ⌊T /k⌋, leaving any unused rounds dummy. See Figure 3 for an illustration. We use the  following consequence of Section 2.1; see Lemma 5 for the extension to general ε. When n ≥ max 2, ε−2 and δ ≤ ε/ (log n)2/3 , for any informative point x ̸= x0 , every (ε, δ)-private online learner has a deterministic stream of length n consisting only of the dummy example and (x, b) for one fixed bit b, on which its expected mistakes on informative examples are at least c0 (log n)2/3 . ε Our choices of n and the parameter regime above satisfy these conditions. At the current node x, both labels are available. Fix the input from earlier phases and temporarily fill all later rounds 10

with dummy examples. The original learner induces an (ε, δ)-private learner on the current phase: replacing one example in the phase replaces only one example in the full stream. We fix only the input prefix and average over the learner’s randomness. Apply the preceding bound at x to choose a hard phase and its label b, then follow the edge labelled b. Repeat for all k phases. Figure 3 illustrates these phases along a path in the shattered tree. The phases are chosen using the learner’s distribution, so the entire stream is fixed before the learner runs. Their labels follow one path in the shattered tree, making the stream realisable. Moreover, replacing the temporary dummy suffix with later phases cannot change earlier predictions. Adding the expected mistakes over the phases gives c0 k c1 d (log n)2/3 ≥ (log T )2/3 , ε ε √ where the last inequality uses k ≥ d/2 and n ≥ T . This implies the stated bound in the parameter regime considered. E [MT ] ≥

3

Private predictor for Littlestone classes

Let H ⊆ {0, 1}X be nonempty with Littlestone dimension d < ∞. Fix 0 < ε ≤ 1 and 0 < δ < 1/10. In this section, we consider the online prediction setting with joint DP, as described in Section 1.1. Let S = ((xt , yt ))Tt=1 be a fixed labelled stream and M (U ; S1:r ) be the mistakes of a prediction sequence U on its first r rounds. Our main result of this section is the following. Theorem 3. There is an (ε, δ)-JDP online predictor satisfying c(d+1)2

E [M (A; S)] ≤

22

ε2

log2

2 εδ

on every fixed realisable stream of any length, where c > 0 is an absolute constant. Proof. If d = 0, a fixed hypothesis in H predicts without mistakes. Assume d ≥ 1, and consider a realisable stream S. Intuitively, in online learning, the learner releases a hypothesis at every round. Its predictions at informative points are therefore visible even on rounds when it receives a dummy example. In online prediction, only the prediction at the current point is released. Thus, on dummy examples where the old and new predictors agree, the learner can change its internal predictor while continuing to give the same answer. Changes in its predictions at informative points are not visible through these outputs. We use this freedom to delay the effect of a new candidate on the released predictions. Additionally, to bound the mistakes from these delays, we also need to bound how many candidates are used. The proof proceeds in three steps. First, we construct a short private sequence of candidates containing one with few mistakes on the whole stream, with high probability. Both the length of the sequence and the mistake bound are independent of T . Each new candidate can be computed from a bounded number of mistakes of the preceding candidates. Second, we use these candidates for private online prediction. Simply switching when a new candidate is computed may reveal when its predecessor made mistakes. Our replacement rule returns the common prediction when the old and new predictors agree, and privately delays the use of the new candidate on disagreement rounds. We choose the delays so that a candidate cannot affect the predictions before it can be computed. The resulting mistake bound depends on the number of candidates and the delays, both independent of T . 11

In the third step, we convert this high-probability guarantee into an expected mistake bound. Step 1: construct a private sequence containing a good candidate. We adapt the essentialhypothesis construction of [Lyu26] to obtain the following guarantee. Lemma 3. The offline algorithm in Algorithm 2, run with privacy parameters (ε/4, δ/8) and failure probability β = δ, is (ε/4, δ/8)-differentially private and returns binary functions h0 , . . . , hN . Then, on every fixed realisable stream, 

P



min M (hj ; S) < K ≥ 1 − δ,

0≤j≤N

O (d2 ) 2 2 where h0 is public and N, K are positive integers satisfying N ≤ 2O(d ) , K ≤ 2 ε log εδ .

We explain the construction and its mistake guarantee here, using the lemmas proved in Section 7.1. For a function h, let BK (h, S) contain the first K labelled examples on which h makes a mistake, or all such examples if there are fewer. Call the batch full when it contains K records. To compute hj+1 , the algorithm only needs BK (h0 , S), . . . , BK (hj , S). Thus, once BK (hj , S) becomes full, we can compute the next candidate using the observed examples and the state from the preceding batches. For a nonempty class G ⊆ H and an integer p ≥ 1, let Cp (G) be its set of essential hypotheses (Definition 9) and let ρp (G) ∈ {0, . . . , d} be its decomposition dimension (Definition 8). These notions are due to [Lyu26]. The important property is that each of these essential hypotheses agrees with some function in 2 G on any given set of at most p instances and |Cp (G)| ≤ pd 2d . The main property of decomposition dimension is that, if ∅ = ̸ F ⊆ G and p′ ∈ {p, 2p}, then ρp′ (F ) ≤ ρp (G), and if equality holds, then Cp′ (F ) ⊆ Cp (G). Thus restricting the class cannot increase its decomposition dimension, even when p is doubled, and if the dimension is unchanged, its essential hypotheses can only shrink. With the parameters specified before Algorithm 2, the algorithm maintains k groups of labelled examples from S. Figure 4 illustrates how a mistake batch updates their stored samples and candidate lists. Starting with a public function h0 , it constructs the next candidate hj by forming the mistake batch BK (hj−1 , S) and assigning each example independently to a uniformly chosen group. Each group stores a uniformly chosen sample of up to n of the examples it receives, along with all its earlier samples. The stored samples define the class Gi ⊆ H for group i: a hypothesis belongs ℓ to Gi if it makes at most aℓ n mistakes on every stored sample, where aℓ = 18 − 32(d+1) , 0 ≤ ℓ ≤ d. The realising hypothesis remains in every Gi , so these classes are nonempty. Initially ℓ = 0, and group i’s candidate list is Cp (Gi ). We select a hypothesis using the number of lists in which it appears. The highlighted copies of hj in Figure 4 represent the same function appearing in different groups’ lists. Changing one group’s data can change its entire list, but changes each such count by at most one. A private sparse selection algorithm (Fact 3) uses these counts to choose a hypothesis appearing in many lists or return ⊥. If it returns a hypothesis, this becomes hj . If it returns ⊥ and ℓ < d, the algorithm increments ℓ and retries using the same stored samples. Then, we show in Lemmas 6 and 7 that with probability at least 1 − δ, for every successfully selected function hj , at least k/2 groups contain hj in their lists when it is selected and store full samples of n examples from every full mistake batch processed during the run. Condition on this event and suppose, towards a contradiction, that every candidate makes at least K mistakes. Every batch is then full. On the same event, Lemma 9 ensures that the algorithm makes N successful selections whenever every mistake batch is full. Thus, under our assumption, it

12

Mistake batch uniform assignment

Bj = BK (hj−1 , S)

k groups

Essential hypotheses

S1

Gi = {h ∈ H : errA (h) ≤ aℓ ∀A ∈ Si }

(x3 , y3 ), . . .

Cp (G1 ) hj

(x7 , y7 ), . . .

(x7 , y7 )

.. .

h(2)

.. .

(x41 , y41 )

Sk

.. .

(x31 , y31 ), . . .

Private selection

Select (Fact 3)

hj

Cp (Gk ) hj

(x41 , y41 ), . . . earlier

h(1)

h(6)

h(7)

new next batch: BK (hj , S)

Figure 4: Si collects group i’s retained samples. Each mistake batch contributes one coloured oval (denoted A) of ≤ n points. errA (h) is the mistake count on A, divided by n. The list Cp (Gi ) contains the essential hypotheses of Gi .

produces h1 , . . . , hN . We obtain a contradiction by counting the distinct pairs (i, h) for which h appears in group i’s list at some point during the run. Denote their number by P . Upper bound on P . Let s be the uniform upper bound on candidate-list sizes fixed by the 2 algorithm’s parameters. The bound |Cp (G)| ≤ pd 2d , together with the parameter choices before 2 Algorithm 2, gives s = 2O(d ) . Consider one group and follow its candidate list as the algorithm runs. Using the properties of essential hypotheses and decomposition dimension, Lemma 8 shows that the group’s decomposition dimension cannot increase and, whenever it stays unchanged, the new candidate list is a subset of the previous list. Therefore, all functions appearing during a period of constant dimension already belong to its first list, and there can be at most s of them. New functions can enter only when the decomposition dimension decreases. Since this dimension starts at most d and never becomes negative, there are at most d decreases, and hence at most d + 1 such periods. Therefore, at most (d + 1)s distinct functions can appear in this group’s lists over the entire run. Summing over the k groups gives P ≤ k(d + 1)s. Lower bound on P . Consider one of the first N − 1 selected functions, say hj . The return arrow in Figure 4 represents its next batch, BK (hj , S), consisting entirely of examples on which hj is wrong. As established above, at least k/2 groups whose lists contained hj when it was selected store a full sample of n examples from this batch. This sample prevents hj from ever appearing in any of those groups’ lists again. Indeed, suppose that hj later belonged to Cp (Gi ) for one such group. Since p is chosen to be at least n, the stated property of essential hypotheses gives a function g ∈ Gi agreeing with hj on every instance in the stored sample. The function g would therefore make n mistakes on that sample, contradicting the requirement that it make at most aℓ n < n mistakes. Because the sample is retained and the threshold can only decrease, this argument applies at every later stage. Each of the first N − 1 selections thus removes at least k/2 pairs counted in P , and no pair can be removed again at a later selection. Hence P ≥ (N − 1)k/2. Combining the two bounds gives (N − 1)

k ≤ P ≤ k(d + 1)s, 2

which contradicts the choice N = 2(d + 1)s + 2. Thus, with probability at least 1 − δ, some candidate makes fewer than K mistakes. The privacy guarantee along with specific parameter choices are proved in Section 7.1.

13

Step 2: using the candidates online. The candidates can be computed as their preceding mistake batches become full. However, the private candidate sequence does not protect the rounds when this happens. We therefore need a prediction rule in which a candidate cannot affect the output before the batches needed to compute it become full. We use a private replacement algorithm Rep (Definition 10), based on the Mirror mechanism of [CLN+ 24]. Given two sequences of binary predictions U, V , it returns their common prediction whenever they agree. On disagreement rounds, it initially follows U . We test privately whether V is correct sufficiently often on the initial disagreements, and use Mirror to delay when an accepted candidate may affect the predictions. Write W = Rep(U, V, D), where D controls the delay. Lemma 11 gives the following two properties with probability one: (i) If V makes less than K mistakes on S1:r , then W makes at most M (W ; S1:r ) ≤ K + 2D. (ii) If U made at most D/4 mistakes before round t, then no replacement occurs and Wt = Ut . The first property bounds the mistakes of the combined predictor when the new candidate is good. The second prevents a new candidate from changing the output while the preceding predictor has made few mistakes. Choose D0 > 4K and set Dj = 9j D0 . First suppose that all candidates h1 , . . . , hN are available, and define A0 = h0 and Aj = Rep(Aj−1 , hj , Dj ) for 1 ≤ j ≤ N . The difficulty is that computing the next candidate depends on mistakes of hj , whereas replacement depends on mistakes of Aj . The first property connects these two mistake counts. The increasing delays then allow us to apply the second property and show that later candidates cannot change the predictions before they can be computed. Computing the predictions online. Suppose 0 ≤ m < N where hm has fewer than K mistakes before round t. The first property above gives M (Am ; S1:s−1 ) ≤ K + 2Dm for every s ≤ t. Since Dm ≥ D0 ≥ 4K, we have K + 2Dm ≤ Dm /4 + 2Dm = Dm+1 /4. The second property therefore shows that Am+1 has the same predictions as Am on every round through t. Their mistake counts are therefore equal until t. If m + 1 < N , then, for every s ≤ t, M (Am+1 ; S1:s−1 ) = M (Am ; S1:s−1 ) ≤ Dm+1 /4 ≤ Dm+2 /4. Then using the second property again shows that Am+2 has the same predictions as Am+1 on every round through t. Repeating this argument shows that, whenever M (hm ; S1:t−1 ) < K, the predictors Am , . . . , AN agree on every round through t. Algorithm 3 uses this agreement property to implement AN online. It computes successive candidates as their preceding mistake batches become full and predicts using Am , where hm is the last candidate computed. We denote this online predictor by A. Mistake bound for A By Lemma 3, with probability at least 1 − δ, some candidate hj makes fewer than K mistakes on the whole stream. Using the first property, we then have that Aj makes at most K + 2Dj mistakes. Since M (hj ; S) < K, using the above argument we have that Aj , . . . , AN predict identically on the whole stream. The online predictor A therefore makes at most B := K + 2 · 9N D0 O (d2 ) 2 log 2 from Lemma 3 into B, and using the mistakes. Substituting N ≤ 2O(d ) and K ≤ 2 ε

εδ

replacement mechanism’s parameter choice, gives O d2

P [M (A; S) ≤ B] ≥ 1 − δ,

B≤

22

( )

ε2

log2

2 . εδ

(4)

The additional factor ε−1 log(2/(εδ)) arises from the choice of D0 used to obtain the replacement mechanism’s privacy and delay guarantees. 14

Privacy guarantee of A We first analyse the predictor AN defined using the entire candidate sequence. Lemma 3 gives an (ε/4, δ/8)-differentially private candidate sequence. Each of the N replacement mechanisms is (ε/(4N ), δ/(8N ))-jointly differentially private on its input stream (Ut , Vt , yt )Tt=1 . The composition argument in Lemma 12 therefore gives (ε/2, δ/4)-joint differential privacy for AN . The online predictor A has exactly the same predictions as AN on every stream. Thus the same privacy guarantee holds for A, independently of the event used to prove the mistake bound. Step 3: an expected mistake bound independent of T . The high-probability guarantee from Step 2 leaves an event of probability at most δ on which A may make as many as T mistakes. It therefore only gives EM (A; S) ≤ B + δT . We remove this dependence on T by combining A with another private predictor whose expected mistakes are bounded, albeit by a worse quantity. This other predictor is the Name and Shame SOA algorithm of [DSS24], which we denote by F and run independently of A. It predicts using SOA on the examples retained so far and, after each prediction, retains the new labelled example with probability δ/4. It is easy to see (Fact 5) that F is (0, δ/4)-jointly DP and satisfies EM (F; S) ≤ 4d/δ. Our second technical ingredient is a private comparison rule that combines the two predictors to get a best-of-both-worlds type mistake bound. The algorithm (Algorithm 4) returns their common prediction when they agree; otherwise, it favours the predictor thatwas correct on more of the previous disagreement rounds. Let C = CombineD (A, F), where D = Cε−2 log(2/δ) for a sufficiently large absolute constant C. Lemma 13 shows EM (C; S) ≤ 3E min {M (A; S), M (F; S)} + 2D. Let E = {M (A; S) ≤ B}. On E, the minimum in this bound is at most B; on E c , it is at most M (F; S). Since the stream is fixed and F runs independently of A, the event E is independent of M (F; S). Therefore, EM (C; S) ≤ 3B + 3P(E c ) EM (F; S) + 2D ≤ 3B + 3δ ·

4d + 2D = 3B + 12d + 2D. δ 2 2c(d+1)

2 Substituting the bound on B from Step 2 and our choice of D gives EM (C; S) ≤ 2 ε2 log2 εδ for an absolute constant c. Finally, Lemma 14 in Section 7.3 proves that C is (ε, δ)-jointly differentially private, completing the proof.

4

Open problems and discussion

In this work, we proved two main results  for Differentially Private Online Learning. The first  result Theorem 2 shows a lower bound of Ω d log2/3 T for private online learning of a hypothesis class H with d = Ldim (H) ≥ 2, for fixed 0 < ε ≤ 1, δ = O (1/ log T ), and sufficiently large T . The primary ingredient of this proof is a similar lower bound for the POINT3 class, which was left open in previous works [DSS24, LWY24]. This leaves several questions open. At δ = Θ(1/ log T ), the first is to close the gap between the O(log T ) upper bound [LWY25] and our Ω((log T )2/3 ) lower bound for fixed d, ε. Our lower bound construction is agnostic of the algorithm of the online learner unlike those of previous works [DSS24, LWY24]. One interesting direction is to see if the lower bound can be improved by using a construction that is adaptive to the algorithm of the online learner. Our second result Theorem 3 shows an upper bound that is independent of T in the private prediction setting. In this work, we did not optimise the dependence on the Littlestone dimension. It is perhaps possible to achieve a dependence that is polynomial in the Littlestone dimension. Extension to the agnostic setting as well as learning under stochastic adversaries under smooth distributions is also an interesting direction for future work. 15

5

Proof of the lower bound for POINT

Theorem 1. For ε = 1/100, 0 ≤ δ ≤ 1/4, and every (ε, δ)-differentially private online learner of POINT3 , there is a realisable stream of length T on which 

E [MT ] ≥ c min (log (2T ))

2/3

1 , , δ 

where c > 0 is an absolute constant. We use the notation of Section 2.1: r indexes the learner’s rounds, t counts completed stages of the adversary, and Yr = hr (1). Write Y≤r = (Y1 , . . . , Yr ). Algorithm 1 below gives the construction when T is a power of three but the result easily extends to arbitrary T . Apply the construction to the first 3L rounds, where L = ⌊log3 T ⌋, and leave the remaining rounds dummy. Algorithm 1 Adversary for POINT3 Require: T ≥ 3 a power of three, p ∈ (0, 1]. 1: Draw B uniformly from {0, 1}; set Sr ← (3, 0) for all r;set A0 ← (0, T ] and L ← log3 T . 2: for t = 0, . . . , L − 1 do 3: Partition At into three equal consecutive subintervals A1t , A2t , A3t . 4: Draw Jt+1 uniformly from {1, 2, 3}. 5: if Jt+1 = 2 then 6: Draw a round s uniformly from A1t . 7: With probability p, replace Ss by (1, B). 8: end if J 9: Set At+1 ← At t+1 . 10: end for 11: return (S1 , . . . , ST ). 

Lemma 1. The expected number of mistakes contributed by stage t + 1 is at least p6 1 −

p



E [It ] .

Proof of Lemma 1. Fix J≤t , and condition on an informative example being inserted at a round s ∈ A1t at stage t + 1. The predictions through round s have the distribution used to define Vt (s): the learner predicts before receiving the example at s, and every example inserted at a later stage occurs after s. Write ms = E[2B − 1 | Y≤s ]. Given these predictions, the probability of incorrectly predicting B is at least (1 − |ms |)/2. Consequently, p √ 1 − Vt (s) 1 − It 1 − E|ms | P(Ys ̸= B) ≥ ≥ ≥ . 2 2 2 The last two inequalities use Cauchy–Schwarz and Vt (s) ≤ Vt (bt ) ≤ It . An informative example is inserted at this stage with probability p/3. Averaging over its location and over J≤t , and using concavity of the square root, gives the desired bound:  p p  p p 1 − E It ≥ 1 − EIt . 6 6 Lemma 2. For every 0 ≤ t < L E [It+1 | J≤t ] ≤ It + 20p2 Dt + 20pδ Dt p + δ + . 6 3 where J≤t denotes the adversary’s choices of thirds through stage t. E [Wt+1 | J≤t ] ≤ Wt −

16

(2) (3)

Proof of Lemma 2. Fix J≤t and write At = (at , bt ], A1t = (at , c1 ], A2t = (c1 , c2 ], A3t = (c2 , bt ]. Recall the distributions P∅b and Psb defined in Section 2.1. Let Q and Qs be their joint distributions with the fair bit B, so Q(B = b, Y = y) = 12 P∅b (y) and Qs (B = b, Y = y) = 12 Psb (y). For j ∈ {1, 2, 3}, P let Rj = |Ajt |−1 s∈Aj Qs be the joint distribution after inserting an informative example at a t uniformly chosen round in the jth third. We first bound the error introduced by clipping the likelihood ratios. Conditional on B and the earlier insertions, adding an example at s changes one labelled example. Averaging the privacy inequalities over this randomness shows that they also hold for Qs and Q. Clipping their ratio to [e−ε , eε ] therefore gives ∥Qs − QℓB s ∥1 ≤ 2δ, (5) B ∥Rj − QℓAj ∥1 ≤ 2δ. t

B B Here QℓAj denotes the measure with density ℓAj relative to Q. Indeed, the mass above eε Q is at t t most δ, and the deficit below e−ε Q is at most e−ε δ. Throughout, using ε = 1/100 gives |ℓB s −1| ≤ 1/8 ε and e ≤ 5/4.

Bounding the increase in It . Let Vt+ (r) be Vt (r) computed under P = (1 − p)Q + pR1 , the distribution when the middle third is chosen. We show that, for 0 ≤ u ≤ v ≤ c2 , Vt+ (v) − Vt+ (u) ≤ 2 (Vt (v) − Vt (u)) + 8p2 Dt + 16pδ.

(6)

The increment Vt+ (v) − Vt+ (u) is the reduction in the minimum expected squared error for estimating 2B − 1 when we observe predictions through round v, rather than only through round u. Write Z = 2B − 1, mr = EQ [Z | Y≤r ], f = EP [Z | Y≤v ], choosing values in [−1, 1] on histories of probability zero. Let H = (Z − mu )2 − (Z − f )2 be the improvement in squared error when we replace mu by f . Since mu is an available estimate at round u, while f is the best estimate at round v under P , Vt+ (v) − Vt+ (u) ≤ EP H. We compare this improvement with the one under Q. An insertion in the last third cannot affect predictions through round v ≤ c2 . Since H depends only on B and these predictions, ER3 H = EQ H. Also, |H| ≤ 4, so applying (5) to R1 and R3 gives EP H = EQ H + p (ER1 H − ER3 H) ≤ EQ H + pEQ

h B

B



i

ℓA1t − ℓA3t H + 16pδ.

Each clipping bound contributes at most p · 4 · 2δ. Moreover, |H| ≤ 4|f − mu |. Using 4p|ab| ≤ 8p2 a2 + b2 /2 and the definition of Dt , we get h i  i 1 B ℓA1t − ℓA3t H ≤ 8p2 Dt + EQ (f − mu )2 . 2 The last term is cancelled by the squared-error comparison under Q. Indeed, conditioning on Y≤v and using 2ab ≤ 2a2 + b2 /2 gives

pEQ

h B

h

EQ H = EQ 2(mv − mu )(f − mu ) − (f − mu )2

i

h i 1 h i ≤ 2EQ (mv − mu )2 − EQ (f − mu )2 . 2

17

Combining the bounds therefore yields h

i

Vt+ (v) − Vt+ (u) ≤ 2EQ (mv − mu )2 + 8p2 Dt + 16pδ. Since mr = EQ [Z | Y≤r ] and mu is determined by Y≤u , for u ≤ v we have EQ [mv mu ] = EQ [Zmu ] = EQ [m2u ]. The first equality conditions on Y≤v , and the second on Y≤u . Expanding the square therefore gives EQ [(mv − mu )2 ] = EQ [m2v ] + EQ [m2u ] − 2EQ [mv mu ] = EQ [m2v ] − EQ [m2u ] = Vt (v) − Vt (u). This proves (6). Choosing the first or last third leaves the stream distribution unchanged. In the middle case, the insertion occurs after round at , so Vt+ (at ) = Vt (at ), and 







It+1 = Vt (at ) + Vt+ (c1 ) − Vt+ (at ) + 2 Vt+ (c2 ) − Vt+ (c1 ) . Apply (6) to the increments across the first and middle thirds. Averaging this bound with It+1 = 2Vt (c1 ) − Vt (at ) in the first case and It+1 = 2Vt (bt ) − Vt (c2 ) in the last case gives 2 5 (Vt (c2 ) − Vt (at )) + (Vt (bt ) − Vt (c2 )) + 8p2 Dt + 16pδ 3 3 ≤ It + 8p2 Dt + 16pδ ≤ It + 20p2 Dt + 20pδ.

E[It+1 | J≤t ] ≤ Vt (at ) +

The second inequality uses the nonnegativity of both increments and the definition of It . Bounding the change in Wt . For nonempty S ⊆ At , write W (S) = EQ [Vars∈S (ℓB s )], so that B W (At ) = Wt . Let ℓAt denote the average over the whole interval. Variance decomposition across the three thirds gives Wt =

3 3 3 1X Dt 1X 1X B B W (Ajt ) + EQ (ℓAj − ℓAt )2 ≥ W (Ajt ) + . t 3 j=1 3 j=1 3 j=1 6

The stream distribution stays the same when the first or last third is chosen. When the middle third is chosen, the possible insertion changes it to P . Let W + (A2t ) be the corresponding variance. We show that W + (A2t ) ≤ W (A2t ) + p + δ. (7) For s ∈ A2t , let R1,s be the distribution obtained from R1 by additionally inserting (1, B) at s, and let ℓ⋆s be its ratio relative to R1 , clipped to [e−ε , eε ]. The comparison distribution relative to P is Ps+ = (1 − p)Qs + pR1,s . Clipping each component ratio and then taking their mixture gives the ratio ⋆ (1 − p)QℓB s + pR1 ℓs ⋆ us = = (1 − θ)ℓB s + θℓs , P 1 where θ = pR P . The weight θ depends on B and the released predictions, but not on the candidate insertion round s. Convexity of variance therefore gives

h

i

h

i

EP Vars∈A2t (us ) ≤ (1 − p)W (A2t ) + p ER1 Vars∈A2t (ℓ⋆s ) ≤ W (A2t ) + p. The last inequality follows from the bounds on the clipped ratios. Let ℓ+ s be the actual clipped ratio + + Ps /P . Applying (5) to both component comparisons gives ∥Ps − P us ∥1 ≤ 2δ. Since us already 18

lies in the clipping interval, projecting Ps+ /P onto that interval cannot increase its distance from us , so EP |ℓ+ s − us | ≤ 2δ. For any two families us , vs ∈ [7/8, 9/8], |Vars (us ) − Vars (vs )| ≤

1 Es |us − vs |. 2

Applying this inequality with vs = ℓ+ s , and averaging over P , proves (7). Combining the variance decomposition with (7) yields E[Wt+1 | J≤t ] =

6

W (A1t ) + W + (A2t ) + W (A3t ) Dt p + δ ≤ Wt − + . 3 6 3

Proof of the lower bound for general Littlestone classes

Definition 6 (Littlestone dimension). Consider a complete binary tree whose internal nodes are labelled by points of X , with the two edges leaving each node labelled zero and one. The tree is shattered by H if every root-to-leaf path is realised by some f ∈ H: at each node on the path, f assigns the label of the edge followed by that path. The depth is the number of internal nodes on each root-to-leaf path. The Littlestone dimension Ldim (H) is the largest depth of a tree shattered by H, or infinity if such depths are unbounded. Without privacy, a class of Littlestone dimension d admits a learner making at most d mistakes on every realisable stream [Lit88]. In this section, we extend the informative-mistake bound of Theorem 1 to general ε and apply it at successive nodes of a shattered tree. Lemma 4. Fix distinct points x0 , x, let N ≥ 1, and suppose that 0 ≤ δ ′ ≤ 1/4. For every (ε0 , δ ′ )-private online learner, where ε0 = 1/100, there is a distribution over streams of length N consisting only of (x0 , 0) and (x, B), with B a fair bit. If K counts informative examples and X counts mistakes on those examples, then, writing µ = EK, n

o

n

o

a min (log (2N ))2/3 , 1/δ ′ ≤ µ ≤ A min (log (2N ))2/3 , 1/δ ′ ,

(8)

EX ≥ µ/4, where a, A > 0 are absolute constants. Proof. Use the construction from Section 2.1, with (x0 , 0) as the dummy example and (x, B) as the informative example. For N ≥ 3, set L = ⌊log3 N ⌋ and apply Algorithm o 1 to the first 3L rounds, n −1/3 ′ leaving the remaining rounds dummy. Choose p = a0 min L , 1/ (δ L) for a sufficiently small absolute constant a0 > 0. The proof of Theorem 1 gives EIt ≤ 1/4 for every t < L. Thus µ = Lp/3, and Lemma 1 gives EX ≥ Lp/12 = µ/4. Comparing L with log (2N ) proves the bounds on µ. For N = 1, 2, use one informative example with a fair label at the first round and fill any remaining round with the dummy example. Then µ = 1 and EX = 1/2, giving the same bounds after adjusting the constants a, A. We recall two properties of differential privacy under replacement adjacency. Fact 1 (Group privacy). Let M be (ε, δ)-differentially private and let q ≥ 1 be an integer. If S, S ′ differ in at most q positions, then, for every measurable output event E, P [M (S) ∈ E] ≤ eqε P M S ′ ∈ E + δ 



q−1 X j=0

19

ejε .

Proposition 1. Fix z⋆ ∈ X × {0, 1} and γ ∈ [0, 1]. Given an (ε, δ)-private online learner, independently retain each input example with probability γ and otherwise feed z⋆ to the learner, without removing the round. Releasing the learner’s predictors gives a (log (1 + γ (eε − 1)) , γδ)private online learner. Proof. Fix neighbouring streams and all retention decisions except at the changed round. For an output event E, let a, b, u be its probabilities when that round contains the first stream’s example, the second stream’s example, or z⋆ , respectively. Privacy gives a ≤ eε min {b, u} + δ. Since min {b, u} ≤ b and min {b, u} ≤ (1 − γ) u + γb, we obtain (1 − γ) u + γa ≤ [1 + γ (eε − 1)] [(1 − γ) u + γb] + γδ. Averaging over the remaining retention decisions proves the claim. Lemma 5. Fix distinct points x0 , x, let n ≥ 1, and suppose that 0 < ε ≤ 1 and 0 ≤ δ ≤ min ε2 , 1/4 . For every (ε, δ)-private online learner, there are a bit b and a deterministic stream of length n consisting only of (x0 , 0) and (x, b) such that the number X of mistakes on informative examples satisfies   1 2/3 1 EX ≥ c min n, [log (2 + εn)] , . (9) ε δ 

In particular, if n ≥ max 2, ε−2 and δ ≤ ε/ (log n)2/3 , then the same stream satisfies 

EX ≥

c′ (log n)2/3 . ε

(10)

Here c, c′ > 0 are absolute constants. Proof. Write ε0 = 1/100 and first suppose that ε ≤ ε0 and n ≥ 1/ε. We replace each auxiliary example with q copies. Starting these copies at a uniformly chosen position lets us compare the mistakes on later copies with the auxiliary mistake at the first copy. Choose q = ⌊ε0 /ε⌋ , w = n . Each round of the auxiliary learner uses a block of 2w rounds of the original learner. 16q, N = 2w Independently in each block, choose U uniformly from {1, . . . , w} and feed dummy examples before position U . Release the original learner’s predictor at U as the auxiliary predictor. Then receive the auxiliary example and place q copies at positions U, . . . , U + q − 1. All other positions in the block and any rounds after the N blocks are dummy. For fixed offsets, replacing one auxiliary example changes at most q original examples. Group privacy gives (ε0 , δq )-privacy, where δq = δ

q−1 X

ejε ≤ eε0 qδ ≤ eε0 ε20 < 10−3 .

j=0

The same guarantee holds after averaging over the offsets. Apply Lemma 4 with δ ′ = δq , and let µ be its expected informative count. We next compare mistakes on the copies with the auxiliary mistake. Fix the preceding input and an informative label, and let α be the auxiliary mistake probability. Since the prediction at U precedes the first copy, α is also the mistake probability at a uniformly chosen position U when the whole block is dummy. For 0 ≤ j < q, the windows {1, . . . , w} and {1 + j, . . . , w + j} differ by j positions at each end. Since each error probability lies in [0, 1], shifting the window reduces its

20

average by at most j/w. Group privacy therefore bounds the mistake probability on the copy at U + j, averaged over U , from below by e−qε (α − j/w) − δq . Summing over the copies and informative auxiliary examples, and using the auxiliary mistake bound µ/4, gives     qµ 1 −ε0 1 EX ≥ qµ e − δq ≥ − , 4 32 5 where we used (q − 1)/(2w) ≤ 1/32. Since q = Θ(1/ε) and N = Θ(εn), (8) and δq ≤ eε0 qδ give (9). For n < 1/ε, repeat (x, B) for all n rounds, where B is a fair bit. Comparing with the all-dummy stream by group privacy, using nε < 1 and nδ ≤ ε0 , gives 



EX ≥ n e−1 /2 − eε0 ≥ n/8. Averaging over B gives a deterministic stream. For ε0 ≤ ε ≤ 1, apply Proposition 1 with r = (eε0 − 1)/(eε − 1). The auxiliary learner is (ε0 , rδ)-private. As the prediction is done before deciding whether to retain, expected mistakes on retained informative examples equal r times the auxiliary informative mistakes. Lemma 4 therefore gives 

n

EX = Ω min r (log (2n))2/3 , 1/δ

o

.

Since r = Θ(1/ε) on this range and log(2 + εn) ≤ 2 log(2n), this proves (9). All input choices can be made before running the original learner, and every resulting stream uses only the dummy example and informative examples with one fixed label. Averaging over these choices therefore gives a deterministic stream with the same lower bound on expected informative mistakes.  √ Finally, suppose that n ≥ max 2, ε−2 and δ ≤ ε/ (log n)2/3 . Then εn ≥ n, so log (2 + εn) ≥ √ 2/3 1 ≤ n ≤ εn and 1/δ ≥ ε−1 (log n)2/3 . Thus each term in the minimum in (9) 2 log n. Also, (log n) is at least 2−2/3 ε−1 (log n)2/3 , which proves (10). Theorem 2. Let H ⊆ {0, 1}X have finite Littlestone dimension d ≥ 2, and let T ≥ 1. Suppose that 0 < ε ≤ 1 and 0 ≤ δ ≤ min ε2 , 1/4 . For every (ε, δ)-differentially private online learner of H, there is a deterministic realisable stream of length T on which (

d εT E [MT ] ≥ c min T, log 2 + ε d 



2/3

d , δ

)

,

where c > 0 is an absolute constant. Full proof of Theorem 2. Take a depth-d tree shattered by H and follow the zero (left) edge at its root x0 . The remaining subtree has depth d − 1, and is shattered by the hypotheses assigning label zero to x0 . Use (x0 , 0) as the dummy example throughout. Divide the horizon into k = min {d − 1, T } phases of length n = ⌊T /k⌋, leaving any unused rounds dummy. At the current node x ̸= x0 , both labels are available. Fix the input from earlier phases and temporarily fill all later rounds with dummy examples. Restricting the original learner’s output to the current phase defines an (ε, δ)-private learner on that phase: replacing one example in the phase replaces only one example in the full stream. We fix only the input prefix and average over the learner’s randomness. 21

Apply Lemma 5 at x to choose a deterministic hard phase and its label b, then follow the edge labelled b. Repeat for all k phases. These choices use the learner’s distribution, so the entire stream is fixed before the learner runs. The labels follow one path in the shattered tree, making the stream realisable. Moreover, replacing the temporary dummy suffix with later phases cannot change earlier predictions. Adding the expected mistakes over the phases gives 1 1 E [MT ] ≥ c2 k min n, [log (2 + εn)]2/3 , . ε δ 



If T < d, then k = T and n = 1, giving the required Ω (T ) bound. Otherwise, k = d − 1, so d ≤ k ≤ d, 2

T T ≤n≤ . 2k k

In particular, kn ≥ T /2 and k/δ ≥ d/ (2δ). For the logarithmic term, n ≥ T / (2d) gives log (2 + εn) ≥ 12 log (2 + εT /d). Comparing the three terms proves the stated bound.

7

Proof of the private prediction bound

As in Section 3, let H be nonempty with d = Ldim(H) < ∞, and fix 0 < ε ≤ 1 and 0 < δ < 1/10. Theorem 3. There is an (ε, δ)-JDP online predictor satisfying c(d+1)2

E [M (A; S)] ≤

22

log2

ε2

2 εδ

on every fixed realisable stream of any length, where c > 0 is an absolute constant. If d = 0, a fixed hypothesis in H predicts without mistakes. For d ≥ 1, we give the details of the three-step proof in Section 3.

7.1

Constructing a private candidate sequence

In this subsection, ε, δ and β denote the privacy parameters and failure probability supplied to the offline algorithm. For Lemma 3, substitute (ε/4, δ/8) for the privacy parameters and β = δ. We assume d ≥ 1, 0 < ε ≤ 1, and 0 < δ, β < 1/10. Recall that BK (h, S) consists of the first K examples on which h makes a mistake, or all such examples if there are fewer than K. (

BK (h, S) =

(t, xt , yt ) : h(xt ) ̸= yt ,

t X

)

1 {h(xr ) ̸= yr } ≤ K .

r=1

We recall irreducibility, decomposition dimension, and essential hypotheses from [Lyu26, Definitions 4.1–4.3]. Here, the ambient bound d = Ldim(H) is fixed and p ≥ 1 is an integer. For a sequence Q of labelled examples, let G|Q denote the functions in G consistent with Q. Set Ldim(∅) = −1 and ( 0, Ldim(G|(x,0) ) = Ldim(G), SOAG (x) = 1, otherwise. Definition 7 (Irreducibility). A class G is k-irreducible if, for every x1 , . . . , xk ∈ X , 

Ldim G|((xj ,SOAG (xj )))k

j=1

22



= Ldim(G).

Definition 8 (Decomposition dimension). A decomposition tree for ∅ = ̸ G ⊆ H is a finite binary tree whose internal nodes query instances and whose two outgoing edges are labelled zero and one. Let Gv contain the functions consistent with the path to node v, and write qv = Ldim(Gv ). The tree is (p, d)-valid if every node satisfies depth(v) ≤ p(2d−qv +1 − 1) and every leaf also satisfies depth(v) ≤ p(2d−qv − 1),

Gv is p2d−qv -irreducible.

Define the decomposition dimension by ρp (G) =

min

max

T : (p,d)-valid v∈Leaves(T )

Ldim(Gv ).

A tree attaining this minimum is optimal. Definition 9 (Essential hypotheses). Let Optp,d (G) be the optimal decomposition trees. The set of essential hypotheses is Cp (G) =

\

{SOAGv : v ∈ Leaves(T ), Ldim(Gv ) = ρp (G)} .

T ∈Optp,d (G)

Set Cp (∅) = ∅. We write ρp (G) for the decomposition dimension denoted by DDimp,d (G) in [Lyu26]. The following fact collects the properties used in Section 3; see [Lyu26, Section 4] for details. Fact 2. For each nonempty G ⊆ H and integer p ≥ 1, the essential hypotheses Cp (G) and decomposition dimension ρp (G) ∈ {0, . . . , d} satisfy: 2

(P1) |Cp (G)| ≤ pd 2d . (P2) If h ∈ Cp (G), then on any set of at most p instances, some g ∈ G agrees with h. (P3) If ∅ ̸= F ⊆ G and p′ ∈ {p, 2p}, then ρp′ (F ) ≤ ρp (G). Equality implies Cp′ (F ) ⊆ Cp (G). T T Moreover, if ∅ ̸= F ⊆ i Gi and ρ2p (F ) = ρp (Gi ) for every i, then i Cp (Gi ) ̸= ∅. (P4) If ρp (G) = 0, then G is finite and Cp (G) = G. It is important to note that elements of Cp (G) need not belong to G. We also use the following private selection guarantee that follows from the private sparse sampling algorithm in [Lyu26, Lemma 3.1]. Fact 3. Given k lists C1 , . . . , Ck , each of size at most s, there is a mechanism Selecta,b that is (a, b)-differentially private under replacement of one list. With probability at least 1 − β ′ , its output satisfies both of the following: 1. A returned function belongs to at least 3k/5 lists. 2. If some function belongs to at least 9k/10 lists, the output is not ⊥. It suffices that k ≥ (C/a) log (k(s + 1)/(β ′ b)). The algorithm for constructing the candidate sequence stores samples in k groups and uses their candidate lists. Let C0 , C1 be sufficiently large absolute constants. Set l

m



n = C0 (d + 1)6 , 



s = 2d n 

k = C1 N 2 n + ε−1 log ε0 =

ε , 8N (N + d + 1)

d

2

2d ,

100N n , εδβ

N = 2 (d + 1) s + 2,



δ0 =

K = 2kn,

δ . 8eN (N + d + 1)

23

Here n is the sample size, s bounds each list size, and K is the mistake-batch size. Each selection call uses privacy parameters (ε0 , δ0 ). At level 0 ≤ ℓ ≤ d, use the error threshold aℓ = 1/8 − ℓ/(32(d + 1)) and list parameter pℓ = 2ℓ n. For a stored sample A and a full batch B, define errA (h) =

1 X 1 {h (x) ̸= y} , n (t,x,y)∈A

errB (h) =

1 X 1 {h (x) ̸= y} . K (t,x,y)∈B

The sample error is divided by n even when A has fewer than n records. Fix a public function h0 . Let Si collect the samples retained by group i, and write Gℓi = {h ∈ H : errA (h) ≤ aℓ for every A ∈ Si } . These classes are defined using the current sample collections. The counter ℓ records the total number of unsuccessful selections and is not reset between batches. Each batch uses fresh assignment and sampling randomness. Algorithm 2 A private sequence of candidates Require: The complete stream S. Ensure: Functions h0 , . . . , hN . 1: ℓ ← 0; Si ← ∅ for each i ∈ [k]. 2: for j = 1, . . . , N do 3: Bj ← BK (hj−1 , S). 4: Assign each record of Bj independently and uniformly to a group, obtaining Bj,1 , . . . , Bj,k . 5: For each i, append a uniform min {n, |Bj,i |}-subset of Bj,i to Si . 6: loop
7: z ← Selectε0 ,δ0 Cpℓ (Gℓ1 ), . . . , Cpℓ (Gℓk ) . 8: if z ̸= ⊥ then hj ← z; exit the loop. 9: if ℓ = d then return (h0 , . . . , hj−1 ), padded with h0 to length N + 1. 10: ℓ ← ℓ + 1. 11: return h0 , . . . , hN .

On a realisable stream, the realising hypothesis belongs to every Gℓi , so these classes are nonempty. There are at most N + d + 1 calls to Select: at most N succeed, while each failure increases ℓ or stops the algorithm when ℓ = d. Lemma 6. With probability at least 1 − β/2, there is one set I ⊆ [k], with |I| ≥ 0.99k, such that the following holds for every full batch Bj . Every group i ∈ I receives at least n records, and its stored sample A satisfies 1 sup errA (h) − errBj (h) ≤ . 64 (d + 1) h∈H Proof of Lemma 6. Condition on the past before a full batch Bj is processed. Call a group unsuccessful for Bj if it receives fewer than n records or its stored sample fails the error bound in the lemma. A group receives 2n records in expectation. Conditional on receiving at least n, its stored sample is a uniformly chosen n-element subset of Bj . Since VC (H) ≤ d, a Chernoff bound and uniform convergence for sampling without replacement bound the probability that a group is unsuccessful by 1/ (1000N ), provided n ≥ C (d + 1)2 (d log (d + 1) + log (1000N )) . Our choice of n satisfies this inequality. 24

Let Zj count the unsuccessful groups, so E[Zj | past] ≤ k/(1000N ). To bound Zj , use the following equivalent sampling rule. Give each record an independent uniform random number in [0, 1], and retain the n smallest numbers within each group. Changing one record’s assignment or random number changes Zj by at most two. Bounded differences over the K = 2kn independent record choices gives     β ck k ≤ | past ≤ exp − 2 , P Zj > 100N N n 2N where the last inequality follows from the choice of k. A union bound over at most N batches shows that, with probability at least 1 − β/2, every full batch has at most k/ (100N ) unsuccessful groups. Let I contain the groups that are successful in every full batch. Then |I| ≥ 0.99k. Lemma 7. With probability at least 1 − β/2, every call to Select in Algorithm 2 satisfies the following: a returned function belongs to at least 3k/5 input lists, and if the output is ⊥, no function belongs to 9k/10 input lists. Proof of Lemma 7. Every input list has size at most s, because ℓ ≤ d. Apply Fact 3 to each call with failure probability β/ (2 (N + d + 1)). Its required inequality is k≥

C 2k (s + 1) (N + d + 1) log , ε0 βδ0

which holds for sufficiently large C1 . Apply the guarantee conditional on the preceding calls. A union bound over at most N + d + 1 calls proves the lemma. Lemma 8. On every realisable stream and for every run of Algorithm 2, each group’s decomposition dimension is nonincreasing. If it is unchanged between two consecutive list constructions, the new list is contained in the previous list. Every list has size at most s. Proof of Lemma 8. Each update replaces a group’s class by a nonempty subclass and either preserves or doubles pℓ . The comparison property in Fact 2 therefore shows that the decomposition dimension cannot increase. When it is unchanged, the new list is contained in the previous one. Since pℓ ≤ 2d n, 2 the size bound in the same fact gives |Cpℓ (Gℓi )| ≤ pdℓ 2d ≤ s. Lemma 9. Fix a realisable stream and random choices for which both guarantees in Lemmas 6 and 7 hold. If every batch processed by Algorithm 2 is full, the algorithm makes N successful selections, producing h1 , . . . , hN . ′ Proof of Lemma 9. Let I be the set from Lemma 6. For i, i′ ∈ I and ℓ < d, take h ∈ Gℓ+1 i . If A is ′ a sample stored by group i , let A be the sample stored by group i from the same batch B. The sampling guarantee gives

errA′ (h) ≤ errB (h) +

1 1 1 ≤ errA (h) + ≤ aℓ+1 + = aℓ . 64(d + 1) 32(d + 1) 32(d + 1)

Hence Gℓ+1 ⊆ Gℓi′ for every i, i′ ∈ I with the current stored samples. If selection fails while ℓ < d, i write R = max ρpℓ (Gℓi ), R′ = max ρ2pℓ (Gℓ+1 i ). i∈I

i∈I

By Fact 2 and the preceding inclusions, R′ ≤ min

If R′ = R, choose a group attaining R′ . Its new class is contained in every old class and has the same decomposition dimension 25

ℓ i∈I ρpℓ (Gi ) ≤ R.

as all of them. By the common-function property in Fact 2, some function belongs to every Cpℓ (Gℓi ), i ∈ I. It belongs to at least 0.99k lists, contradicting Lemma 7. Therefore R′ < R. The maximum decomposition dimension over I initially is at most d, and each unsuccessful selection with ℓ < d decreases it by at least one. Adding samples cannot increase it either, by Lemma 8. Thus, if ℓ reaches d, every group in I has decomposition dimension zero. Its list then equals its class, by Fact 2, and contains the realising hypothesis. It belongs to at least 0.99k lists, so selection cannot fail when ℓ = d. Thus the algorithm completes N successful selections. Lemma 10. Algorithm 2 is (ε, δ)-differentially private under replacement of one record of S. Proof of Lemma 10. Use the equivalent sampling rule from the proof of Lemma 6. Independently for each batch number j and original timestamp t, draw a group assignment and a uniform random number. Fix these choices and average only over the randomness of Select. Let S, S ′ differ at one timestamp. Compare a selection call on the two streams after the same preceding selection answers. The preceding candidates and the count ℓ of unsuccessful selections are then the same. For a fixed candidate, changing one stream record changes its first-K-mistake batch at at most two timestamps: the changed timestamp itself, and possibly one other timestamp entering or leaving the batch. Common records receive the same group assignments and sampling numbers. Thus at most two groups’ samples differ in each batch. Across at most N batches, the stored samples differ in at most 2N groups. By Fact 3 and group privacy (Fact 1), each selection call is (2N ε0 , 2N e2N ε0 δ0 )differentially private with respect to the original stream. Composing over at most N + d + 1 calls gives parameters   2N (N + d + 1) ε0 , 2N (N + d + 1) e2N ε0 δ0 . By the choices of ε0 , δ0 , these are at most (ε/4, δ/4). Averaging over the assignment and sampling randomness preserves privacy and the final returned sequence is a post-processing of the selection answers. We restate Lemma 3 with the target parameters of Section 3. Lemma 3. The offline algorithm in Algorithm 2, run with privacy parameters (ε/4, δ/8) and failure probability β = δ, is (ε/4, δ/8)-differentially private and returns binary functions h0 , . . . , hN . Then, on every fixed realisable stream, 

P



min M (hj ; S) < K ≥ 1 − δ,

0≤j≤N

O (d2 ) 2 2 where h0 is public and N, K are positive integers satisfying N ≤ 2O(d ) , K ≤ 2 ε log εδ .

Proof of Lemma 3. By Lemmas 6 and 7 and a union bound, both guarantees hold with probability at least 1 − β. Condition on this event and let I be the set in Lemma 6. Every selected function belongs to at least 3k/5 − k/100 ≥ k/2 lists of groups in I. If every candidate made at least K mistakes, every batch would be full, and Lemma 9 would give N successful selections. The counting argument in Step 1 of Section 3 then gives (N −1)k/2 ≤ k(d+1)s, contradicting N = 2(d + 1)s + 2. Thus some candidate has fewer than K mistakes. The parameter choices give 2 2O (d ) 2 O(d2 ) s, N ≤ 2 , K≤ log . ε εδβ Each hj is computed using only BK (h0 , S), . . . , BK (hj−1 , S). Together with Lemma 10, substituting (ε/4, δ/8) and β = δ proves the lemma. 26

7.2

Using the candidates online

For the remainder of this section, we use the notation and parameter assumptions of Section 3. The candidates from Step 1 can be computed as their preceding mistake batches become full. To use them privately, we delay when a new candidate can affect the predictions. We use the private delay mechanism Mirror of [CLN+ 24, Lemmas 23–24]. A round is active when its input bit is 1. Fact 4. For 0 < a ≤ 1, 0 < b < 1/10 and an integer D ≥ 1, there is an (a, b)-jointly private mechanism Mirror (a, b, D) that receives an activity bit and returns ⊥ or ⊤ on each round. For every value of its randomness, it returns ⊥ on every inactive round and on the first D active rounds. It returns ⊤ on every active round after the first D + Ca−2 log2 (2/b) active rounds, for an absolute constant C. Definition 10 (Replacement mechanism). Let 0 < a ≤ 1, 0 < b < 1/10, and let D be an integer with D ≥ Ca−2 log2 (4/b) for a sufficiently large absolute constant C. Given two fixed prediction sequences U = (ut ) and V = (vt ), run Mirror(a/2, b/2, D) from Fact 4 on the bits ∆t = 1 {ut ̸= vt }. Write µt for its response at round t. Let c count the rounds on which vt = yt among the first D disagreements, or among all disagreements if there are fewer than D. Independently of Mirror, draw ξ from the Laplace distribution of scale 4/a, conditioned on |ξ| ≤ D/8, and set acc = 1 {c + ξ ≥ D/2}. Define Rep(U, V, D, a, b) by ( vt , if µt = ⊤ and acc = 1, Wt = ut , otherwise. Mirror returns ⊥ on the first D disagreement rounds, so the acceptance decision is used only after all labels entering c have arrived. Thus the replacement is online whenever U, V are. Both predictors receive the original examples and labels, and neither receives the replacement’s outputs. For the parameters in the main proof, choose a sufficiently large absolute constant C and set &

32N N2 D0 = C K + 2 log2 ε δ

!'

,

Dj = 9j D0 ,

1 ≤ j ≤ N,

(11)

and a = ε/(4N ), b = δ/(8N ). Then D0 > 4K, and every D ≥ D0 satisfies the lower bound in Definition 10. The notation Rep(U, V, D) in the main text suppresses a, b. Lemma 11. For every integer D ≥ D0 , every fixed pair of prediction sequences U, V , and every value of the replacement mechanism’s randomness, its output W = Rep(U, V, D, a, b) from Definition 10 satisfies: (i) If M (V ; S1:r ) < K, then M (W ; S1:r ) ≤ K + 2D. (ii) If M (U ; S1:t−1 ) ≤ D/4, then Wt = Ut . Proof. At a disagreement round, exactly one of U and V is correct. In particular, every round counted by c is a mistake of U . For (i), a mistake on a round where ∆t = 0 is also a mistake of V . The first 2D disagreement rounds contribute at most 2D additional mistakes. If the prefix contains no further disagreements, this already proves the bound. Otherwise, among the first D disagreement rounds, fewer than K ≤ D/4 are mistakes of V . Consequently c > 3D/4 and c + ξ > 5D/8 > D/2, so acc = 1. By Fact 4, the choice 27

D ≥ Ca−2 log2 (4/b), with a sufficiently large constant, ensures that µt = ⊤ on every disagreement round after the first 2D. The replacement then predicts vt , and any further mistake is a mistake of V . Therefore M (W ; S1:r ) ≤ M (V ; S1:r ) + 2D < K + 2D. For (ii), if ∆t = 0, the two predictors agree and the replacement returns their common bit. If at most D disagreement rounds have occurred up to and including round t, then µt = ⊥, so the replacement returns ut . Otherwise, the first D disagreement rounds all lie in S1:t−1 . Since U has made at most D/4 mistakes on that prefix, c ≤ D/4. The noise satisfies |ξ| ≤ D/8, and hence c + ξ ≤ 3D/8 < D/2. Thus acc = 0, and again the prediction is ut . Run Algorithm 2 with privacy parameters (ε/4, δ/8) and failure probability β = δ. First suppose that all candidates are available and define A0 = h0 ,

Aj = Rep(Aj−1 , hj , Dj , a, b),

1 ≤ j ≤ N.

Each replacement uses independent randomness, also independent of the candidate procedure. Write Aj,t for the prediction of Aj at round t, and use the same random choices in the online implementation. Claim 1. Let 0 ≤ m < N . If BK (hm , S1:t−1 ) is not full, then Am , Am+1 , . . . , AN agree on every round through t. This holds for every stream and every value of the randomness. Proof. For 0 ≤ j ≤ N and any prefix with M (hj ; S1:r ) < K, we have M (Aj ; S1:r ) ≤ K + 2Dj .

(12)

For j = 0 this follows from A0 = h0 . For j ≥ 1 it is Lemma 11(i), since Dj ≥ D0 ≥ 4K. Fix m, t as in the claim. Since the batch is not full, M (hm ; S1:s−1 ) < K for every s ≤ t. We prove by induction on j = m + 1, . . . , N that Aj and Aj−1 agree at every round s ≤ t. For j = m + 1, (12) and 4K ≤ D0 ≤ Dm give M (Am ; S1:s−1 ) ≤ K + 2Dm ≤ Dm+1 /4. Lemma 11(ii) now shows agreement at round s. For j > m + 1, the induction hypothesis says that Aj−1 and Am agree through t, so Aj−1 makes at most Dm+1 /4 ≤ Dj /4 mistakes before round s. Lemma 11(ii) completes the induction. We store the observed examples and the predictions of each Aj . When a new candidate hj becomes available, we run its replacement rule on the earlier examples, using the stored predictions of Aj−1 and the random choices fixed above. This determines how Aj would have predicted on those rounds and allows it to continue on the next round. To compute successive candidates, Algorithm 2 keeps its stored samples and its current value of ℓ. Algorithm 3 Using the candidates online 1: m ← 0; A0 ← h0 . 2: for t = 1, . . . , T do 3: while m < N and M (hm ; S1:t−1 ) ≥ K do 4: Obtain hm+1 from Algorithm 2, resuming it if needed. 5: Run the replacement defining Am+1 on S1:t−1 as described above. 6: m ← m + 1. 7: Receive xt ; compute A0,t , . . . , Am,t in order and predict Am,t . 8: Receive yt and update all initialised replacements.

All batches count mistakes on the entire stored prefix, including rounds before the candidate was computed. 28

At the end of the while loop, either m = N or the batch of hm is not full. Claim 1 therefore shows that the current prediction equals that of AN , and that reconstructing a replacement preserves its earlier predictions. All computations use only previous labels and the current instance. Denote this online predictor by A. The high-probability mistake bound (4) follows from Step 2 of Section 3, using the parameter choice in (11). We now prove the privacy guarantee. Lemma 12. A is (ε/2, δ/4)-jointly differentially private. Proof. Fix neighbouring streams that differ at round i. Reveal all candidate functions and acceptance bits, and each Mirror response sequence with coordinate i omitted. We use the following composition argument because each replacement receives predictions from the preceding one. Suppose earlier mechanisms have released some functions or bits and some sequences of answers with coordinate i omitted. Fix these outputs. A later mechanism forms its input at round t from the original record at t, the released functions or bits, and the earlier mechanisms’ answers at that same round. Its inputs outside i are therefore fixed and identical on the two streams. The input at i can have different conditional distributions. If the later mechanism’s privacy inequality holds for every pair of possible inputs at i, it also holds after averaging over those conditional distributions. Adaptive composition then adds the privacy parameters. For a jointly private sequence, omit output i. The omitted answer may enter the later mechanism at round i, but it cannot be copied directly to another round. For one replacement rule, regard (ut , vt , yt )Tt=1 as its input stream. Replacing one record changes the number of labels favouring the second predictor among the first D disagreements by at most two. The untruncated Laplace noise of scale 4/a therefore makes the acceptance decision (a/2, 0)differentially private. Truncating this noise to [−D/8, D/8] changesits distribution  intotal variation a/2 by q = exp (−aD/32). The truncated decision is consequently a/2, 1 + e q -differentially 



private. For D ≥ Ca−2 log2 (4/b) with a sufficiently large constant, 1 + ea/2 q ≤ b/2. Mirror independently contributes (a/2, b/2)-joint privacy. We apply this argument to the definition of AN with all candidates available. First obtain the candidate sequence, which is (ε/4, δ/8)-differentially private by Lemma 10. For each j = 1, . . . , N , process the acceptance test and Mirror instance of its replacement rule. Their input at round t is (Aj−1,t , hj (xt ) , yt ). Once the candidates and earlier acceptance decisions are fixed, the first component is determined by xt and the earlier round-t Mirror responses. Thus the composition argument applies and each replacement adds (a, b). The predictions outside i are determined by these releases and the unchanged instances, so their privacy parameters are (ε/4, δ/8) + N (a, b) = (ε/2, δ/4). The online predictor A has exactly the same predictions as AN on every stream when they use the same random choices, by Claim 1 and the implementation above. It therefore has the same privacy guarantee.

7.3

An expected mistake bound independent of T

To remove the δT term in EM (A; S) ≤ B + δT , we combine A with an independent subsampled SOA predictor, as in Step 3. Fact 5. Fix 0 < γ ≤ 1 and start with an empty retained sample R. On round t, predict SOAH|R (xt ); after observing yt , retain (xt , yt ) independently with probability γ. If no hypothesis is consistent with R, use a fixed public function. This predictor is (0, γ)-jointly differentially private and has at most d/γ expected mistakes on every realisable stream.

29

This is the subsampled-SOA argument of [DSS24, discussion following Theorem 1]. Run the Name and Shame SOA predictor F from Fact 5 independently of A, retaining each labelled example with probability δ/4. It is (0, δ/4)-jointly differentially private and satisfies EM (F; S) ≤ 4d/δ.   We combine A and F using Algorithm 4, with D = Cε−2 log(2/δ) for a sufficiently large absolute constant C. Write C = CombineD (A, F) for the resulting predictor. Algorithm 4 Combining A with the independent predictor F 1: c1 , c2 ← 0. 2: for t = 1, . . . , T do 3: Receive xt and predictions ut , vt from A, F.

(D + c1 )2 . (D + c1 )2 + (D + c2 )2 5: Predict ut with probability pt , and vt otherwise. 6: Receive yt and supply it to both A and F. 7: c1 ← c1 + 1 {ut ̸= vt , ut = yt }. 8: c2 ← c2 + 1 {ut ̸= vt , vt = yt }. 9: end for 4:

pt ←

Each choice uses a fresh uniform draw, independent across rounds and of both predictors. When their predictions agree, the rule returns their common bit. The same rule defines CombineD (U, V ) for arbitrary binary prediction sequences U = (ut ) and V = (vt ), with ut , vt supplied before predicting and yt afterwards. When these sequences are generated by predictors, both receive the true labels but never the comparison rule’s outputs. Lemma 13. For the chosen D, CombineD is (ε/2, δ/2)-jointly private on streams of triples (ut , vt , yt ), receiving ut , vt before predicting and yt afterwards. For every fixed pair of prediction sequences U, V and labels, EM (CombineD (U, V ); S) ≤ 3 min {M (U ; S), M (V ; S)} + 2D, where the expectation is over the comparison rule’s randomness. Proof. Fix U, V and the labels, and let m be the total number of mistakes of either prediction sequence. Rounds on which this sequence is wrong contribute at most m mistakes. On the k-th disagreement round on which it is correct, its counter nis k − 1 and the oother counter is at most m. The probability of a mistake is therefore at most min 1, (D + m)2 /k 2 . Thus (D + m)2 EM (CombineD (U, V ); S) ≤ m + min 1, k2 k≥1 (

X

)

≤ 3m + 2D,

where the last inequality follows by splitting the sum at D + m and using k>D+m k −2 ≤ 1/(D + m). Choosing the sequence with fewer mistakes proves the mistake bound. For privacy, fix two neighbouring streams of triples that differ at round i. Let P, Q be the laws of their outputs with coordinate i omitted. Changing one triple changes each counter by at most one, and all later updates agree. Since the counters depend only on the input triples, the outputs are independent on each fixed stream. Only disagreement rounds after i contribute to privacy loss. On such a round, write a = D + c1 , b = D + c2 , and use a′ , b′ for the neighbouring stream. The probabilities of choosing the first predictor are p = a2 /(a2 + b2 ) and q = (a′ )2 /((a′ )2 + (b′ )2 ). P

30

We have a, b, a′ , b′ ≥ D and |a − a′ | , |b − b′ | ≤ 1. Each squared count, and their sum, changes in 4 4 logarithm by at most 2/D. Hence log pq ≤ D , log 1−p 1−q ≤ D . Also, (p − q)2 = q (1 − q)



(ab′ − ba′ ) (ab′ + ba′ ) (a2 + b2 ) a′ b′

2

≤

64 , (a + b)2

using |ab′ − ba′ | ≤ a + b, a/a′ + b/b′ ≤ 4, and a2 + b2 ≥ (a + b)2 /2. Let Zt be the log-likelihood ratio of this round’s output under the first stream. If n disagreements precede this round, then a + b = 2D + n. The inequalities log x ≤ x − 1 and x (log x)2 ≤ (x − 1)2 for x > 0 give |Zt | ≤  64 64 4 2 D , E [Zt ] ≤ (2D+n)2 , E Zt ≤ (2D+n)2 . Distinct disagreement rounds have distinct values of n, and because n≥0 (2D + n)−2 ≤ 1/D, the full log-likelihood ratio L = t Zt satisfies E [L] ≤ 64 64 8 D , Var (L) ≤ D , |Zt − E [Zt ]| ≤ D .. Bernstein’s inequality, with λ = log (2/δ), gives P

P



64 + P L > D

s



128λ 16λ  δ + ≤ . D 3D 2

For the chosen D, the threshold is at most ε/2 when C is sufficiently large. Therefore, every output event E satisfies P (E) ≤ eε/2 Q(E) + δ/2. Exchanging the two streams proves (ε/2, δ/2)-joint privacy. The expected mistake bound for C was proved in Step 3 of Section 3. We finish by proving privacy. Lemma 14. The predictor C in Algorithm 4 is (ε, δ)-jointly differentially private. Proof. Fix neighbouring labelled streams differing at round i. By Lemma 12 and Fact 5, the two underlying prediction sequences, with coordinate i removed, together satisfy (ε/2, δ/2) privacy. Conditional on these outputs, every comparison triple outside i is fixed and identical on the neighbouring streams. The guarantee of Lemma 13 holds for every two choices of the missing triple, and hence for their conditional distributions. The composition argument in the proof of Lemma 12 therefore adds (ε/2, δ/2), giving (ε, δ)-joint privacy for the final predictor.

Acknowledgement The authors acknowledge Daniil Dmitriev, Vikrant Singhal, and Prathamesh Dharangutte for discussions in various stages of this work. The author claims all responsibility for the content of this paper. Repeated interactions withAI (ChatGPT 5.6) along with prior incomplete results from the √ authors were used to derive an initial weaker version of Theorem 1 with log T dependence. The current results used AI for completing algebraic arguments, drawing tikz figures, checking for missing definitions, reading and understanding prior work, particularly [Lyu26, CLN+ 24], and for proof reading proofs.

31

References [AFKT23] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Near-optimal algorithms for private online optimization in the realizable regime. In Proceedings of the 40th International Conference on Machine Learning. 2023. [BDL26]

Konstantina Bairaktari, Markus Engelund Dahl, and Kasper Green Larsen. The binary tree mechanism is optimal for differentially private continual counting. arXiv preprint, 2026.

[BF26]

Mark Bun and William Fang. Privately learning decision lists and a differentially private winnow. In Proceedings of the 37th International Conference on Algorithmic Learning Theory. 2026.

[CLN+ 24]

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Proceedings of Thirty Seventh Conference on Learning Theory. 2024.

[DSS24]

Daniil Dmitriev, Kristóf Szabó, and Amartya Sanyal. On the growth of mistakes in differentially private online learning: A lower bound perspective. In Proceedings of the Thirty-Seventh Conference on Learning Theory. 2024.

[GL21]

Noah Golowich and Roi Livni. Littlestone classes are privately online learnable. In Advances in Neural Information Processing Systems. 2021.

[HL26]

Charlie Harrison and Ethan Leeman. Tight lower bounds for differentially private continual counting. arXiv preprint, 2026.

[KMM+ 23] Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer. Black-box differential privacy for interactive ML. In Advances in Neural Information Processing Systems. 2023. [Lit88]

Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm. Machine Learning, 1988.

[LWY24]

Bo Li, Wei Wang, and Peng Ye. The limits of differential privacy in online learning. In Advances in Neural Information Processing Systems. 2024.

[LWY25]

Bo Li, Wei Wang, and Peng Ye. Private online learning against an adaptive adversary: Realizable and agnostic settings. In Advances in Neural Information Processing Systems. 2025.

[Lyu26]

Xin Lyu. Private learning of Littlestone classes, revisited. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing. 2026.

[SR22]

Amartya Sanyal and Giorgia Ramponi. Open problem: Do you pay for privacy in online learning? In Proceedings of Thirty Fifth Conference on Learning Theory. 2022.

32

Related documents

• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning#609724
• Private online learning and prediction for Littlestone classes#1218385
• Adversarial Online Classification with a Preview#790262
• Adaptive and oblivious statistical adversaries are equivalent#1155022
• Stabilizing updates in differentially private stochastic gradient descent with buffered rejection.#150196