We study mistake bounds for differentially private online learning and online prediction under oblivious realizable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension d. First we prove that every (ε,δ)-private online learner has a deterministic realizable stream of length T on which the mistake bound is at least M_T = Ω(d/ε · log(T)^(2/3)). In particular this is the first non-trivial lower bound in the range 1/T < δ < 1/log T left open in earlier works. Second we prove that for every class of Littlestone dimension d there exists an (ε,δ)-jointly private predictor with at most 2^(2^(c·d²))·ε^(-2)·log²(2/(εδ)) expected mistakes independently of T for some absolute constant c > 0. Thus for every fixed class of finite Littlestone dimension when δ = Θ(1/log T) private learning requires Ω((log T)^(2/3)) expected mistakes whereas private prediction admits O((log log T)²).
Problem setting and privacy definitions
In realisable online learning a learner predicts the labels of a sequence of examples consistent with one unknown hypothesis h drawn from a hypothesis class H. 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, and this bound is tight; Littlestone dimension thus characterises the mistake bound for realisable online learning.
Under differential privacy the learner releases a hypothesis before observing each example, whereas in online prediction the learner only makes predictions without releasing a hypothesis. Previous work has shown algorithms with mistake bounds logarithmic in T for fixed privacy parameters, but whether this dependence on the horizon is necessary was posed as an open question. Subsequent lower bounds have shown that this logarithmic dependence may be necessary only for certain algorithms hypothesis classes or ranges of δ. This paper makes progress on this question in the range of δ left open by prior work, up to order 1/log T.
Two models are considered. In the online learning game for each round r = 1 the randomised learner releases a predictor h_r: X → {0,1}, then observes (x_r,y_r). The learner incurs a mistake when its prediction y^_r = h_r(x_r) is incorrect. In differentially private online learning the learner is (ε,δ)-DP if for every pair of neighbouring streams S,S' differing in at most one labelled example and every measurable output event E ℙ[A(S) ∈ E] ≤ e^ε ℙ[A(S') ∈ E] + δ. In the online prediction game the predictor observes x_r and then releases a bit y^_r, then observes y_r. Jointly differentially private online prediction requires that for every i ∈ {1,…,T}, every pair of streams agreeing outside round i, and every measurable output event E ℙ[Ŷ_{-i}(S) ∈ E] ≤ e^ε ℙ[Ŷ_{-i}(S') ∈ E] + δ.
Lower bound for point functions
The main technical building block uses the three-point class POINT_3 = {f_1,f_2,f_3} on the instance space {1,2,3} where f_j(x) = 1{x = j}. This class has Littlestone dimension one: both labels are possible at each point but prescribing label one leaves only one hypothesis. The hypotheses f_1 and f_2 agree at point 3 but disagree at point 1.
The adversary's strategy samples a uniformly random bit B at the beginning and uses 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. Therefore the first insertion of (1,B) causes a mistake with probability 1/2 because the hypothesis is released before the example arrives. The main challenge is to control how much the learner's predictions reveal about B before subsequent informative examples.
The entire stream of length T is constructed in L = ⌊log_3 T⌋ recursive stages. At each stage the remaining interval is partitioned into three equal parts and one third is chosen uniformly at random. If the middle third is chosen an informative example (1,B) is inserted at a uniformly random position in the first third with probability p; otherwise no insertion is made. The expected number of informative examples in the stream is L · p/3.
Two competing effects are tracked. First the average variance over insertion locations within the chosen third equals the original variance minus the variance between thirds, which is used to control the information revealed about B. Second new insertions can add to the variance but privacy limits this increase. Choosing p as a sufficiently small constant times min{L^(-1/3), 1/(Lδ)} keeps the variance small and yields Ω(min{(log T)^(2/3), 1/δ}) expected mistakes.
Lower bound for general Littlestone classes
The lower bound extends to every class of finite Littlestone dimension d ≥ 2. The main idea is to apply the two-label construction at successive nodes of a shattered tree, following earlier work. Take a depth-d tree shattered by H and follow the zero (left) edge at its root x_0. The remaining subtree has depth d-1 and every hypothesis realising one of its paths agrees on (x_0,0).
The horizon is divided into k = d-1 phases of length n = ⌊T/k⌋, leaving any unused rounds dummy. Each block applies the POINT_3 construction using the parent point x_i as its informative point and x_0 as its shared dummy. Following a single path through the tree keeps the entire stream realizable while the mistake contributions from successive phases add. For fixed d and ε when δ = Θ(1/log T) this is the first lower bound polynomial in log T that applies to every such class and every private learner. The expected mistake bound is Ω(min{d/ε · (log T)^(2/3), d/δ}).
Upper bound for private prediction
We next consider the slightly easier problem of private online prediction. Here the algorithm observes x_t releases only its prediction for x_t and then observes y_t. The question whether every class of finite Littlestone dimension admits an (ε,δ)-jointly private online predictor whose expected mistake bound is independent of T and polylogarithmic in 1/δ is answered affirmatively.
The construction first creates a short private sequence of predictors that with high probability contains at least one with few mistakes on the full stream. Using the idea of essential hypotheses multiple short lists of predictors are created with the property that predictors can be added to these lists online using only earlier mistakes. A private selection mechanism then chooses a frequently appearing predictor among these lists.
A private replacement mechanism based on the Mirror mechanism with increasing delays before each switch implements 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 only the prediction at the current point is released. Switching internally to a new predictor while continuing to give the same answer avoids privacy violation.
Combining the predictor with a subsampled SOA algorithm removes the remaining dependence on T. The resulting guarantee: for every class of finite Littlestone dimension d when 0 < ε ≤ 1 and 0 < δ < 1/100 there exists an (ε,δ)-jointly differentially private online predictor such that on every fixed realizable stream of length T M_T ≤ (2^(2^(c·(d+1)²)) / ε²) · log²(2/(εδ)) expected mistakes independently of T, for some absolute constant c > 0.
Separation between learning and prediction
The lower bounds show that private online learning can require a number of mistakes growing polynomially with log T. We compare this to private online prediction where the expected mistake bound is independent of T with polylogarithmic dependence on 1/δ. The separation is strict: for fixed d ≥ 2 and δ = Θ(1/log T) private learning requires Ω((log T)^(2/3)) expected mistakes on some stream whereas private prediction admits O((log log T)²) expected mistakes on every realizable stream. The same separation holds for point functions on three elements.
This means that the horizon T matters for private online learning but not for private online prediction. The gap grows with T: as T increases the learning bound grows like (log T)^(2/3) while the prediction bound stays essentially constant. The intuition is that in online learning the hypothesis released at every round is visible to the adversary including at informative points while in online prediction only the prediction at the current round is released making the adversary's task easier.
Technical overview of the lower bound construction
The lower bound for POINT_3 avoids the concentration assumption that earlier work used. Previous approaches assumed the learner with high probability predicts the same label at point 1 in an all-dummy stream then inserted informative examples with the opposite label causing mistakes whenever it outputs its preferred label. Privacy constrained how these insertions changed the output distribution.
This paper instead samples a uniformly random bit B at the beginning and uses 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). 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 to control how much the learner's predictions reveal about B before subsequent informative examples.
The proof tracks two variances. The first measures how much the learner's outputs through round r reveal about B: V_r = 𝔼[(𝔼[2B−1 ∣ Y_1,…,Y_r])²]. The second measures how the effect of an informative point insertion on the output distribution varies with the location of the insertion. By standard variance decomposition the average variance over insertion locations within the chosen third equals the original variance minus the variance between thirds. Privacy limits the increase from new insertions. Choosing p as a sufficiently small constant times min{L^(-1/3), 1/(Lδ)} keeps the variance small and yields the desired lower bound.
Technical overview of the upper bound construction
The upper bound for private prediction first constructs 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 multiple short lists of predictors are created with the useful property that predictors can be added to these lists online using only earlier mistakes.
A private selection mechanism then chooses a frequently appearing predictor among these lists. A contradiction argument shows that the number of bad predictors is bounded independently of T. 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. A private replacement mechanism based on the Mirror mechanism with increasing delays before each switch implements 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 the algorithm can ignore that candidate until enough mistakes are made or for the rest of the game if this never happens. Combining the predictor with a subsampled SOA algorithm removes the remaining dependence on T and yields the claimed mistake bound independent of T.
Implications for differentially private online learning
The separation between private online learning and private online prediction has several implications. First it settles the question of how many mistakes an arbitrary private online learner must make on a fixed hypothesis class for every value of δ in the range previously left open 1/T < δ < 1/log T. The lower bound is polynomial in log T, specifically Ω((log T)^(2/3)) when δ = Θ(1/log T).
Second the result provides a horizon-independent guarantee for private prediction with polylogarithmic dependence on 1/δ. This means that for very long streams the prediction problem becomes easier than the learning problem the mistake bound does not grow with T.
Third the same separation holds for point functions on three elements and for every class of finite Littlestone dimension at least two. This suggests that the phenomenon is general and not specific to a particular hypothesis class.
Proof structure for the lower bound
The proof of the lower bound for POINT_3 proceeds in several steps. After handling the base case T = 1,2 the adversary samples a bit B uniformly at random and initialises a stream of length T consisting entirely of dummy examples (3,0). Then the adversary proceeds in L = ⌊log_3 T⌋ stages starting with the interval A_0 = (0,3^L] and leaving all later rounds dummy.
In each stage the remaining interval is partitioned into three equal parts and one third is chosen uniformly at random. If the middle third is chosen an informative example (1,B) is inserted at a uniformly random position in the first third with probability p; otherwise nothing is done. The adversary then proceeds to the next stage by restricting to the chosen interval and repeating the process.
The variance V_r = 𝔼[(𝔼[2B−1 ∣ Y_1,…,Y_r])²] measures how much the learner's outputs through round r reveal about B. 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. Two quantities are tracked: W_r measures the variance of the likelihood ratio within one stage and D_r measures the squared difference between the average ratios of the first and last thirds of the current stage.
Privacy constraints are incorporated by considering the distribution of the learner's output conditional on B = b when running on the stream constructed through stage t with no further insertions, and the distribution after additionally replacing the dummy example at round s with (1,b). Differential privacy gives ‖P_s^b − P_∅^b ℓ_s^b‖_1 ≤ 2δ. The proof then relates the decrease in variance to the privacy parameter and shows that choosing p = c_0 · min{L^(-1/3), 1/(Lδ)} for a sufficiently small c_0 > 0 ensures that 𝔼[I_t] ≤ 1/4 for every 0 ≤ t < L, which yields Ω(min{(log T)^(2/3), 1/δ}) expected mistakes.
Proof structure for the upper bound
The upper bound for private prediction combines several components. First a short private sequence of predictors is constructed with the property that with high probability at least one predictor has few mistakes on the full stream. Using the idea of essential hypotheses multiple short lists are created where predictors can be added online using only earlier mistakes. A private selection mechanism chooses a frequently appearing predictor among these lists.
A contradiction argument shows that the number of bad predictors is bounded independently of T. The online use of these candidates employs a private replacement mechanism based on the Mirror mechanism with increasing delays before each switch. The key insight is that in online prediction only the prediction at the current point is released, so on dummy examples where the old and new predictors agree the learner can switch internally while continuing to give the same answer.
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 the algorithm can ignore that candidate until enough mistakes are made or for the rest of the game if this never happens. Combining with a subsampled SOA algorithm removes the remaining dependence on T and yields the claimed bound.
Related work
Private online learnability for every class of finite Littlestone dimension was first shown with logarithmic dependence on T for fixed privacy parameters but doubly-exponential dependence on the Littlestone dimension. More recently a high-probability bound of Õ(d^9.5 · log T · log(1/δ)/ε) was obtained against oblivious adversaries. On POINT_3 at fixed ε these give Õ(log T · log(1/δ)) and Õ(log T) respectively.
Against adaptive adversaries mistake bounds grow doubly-exponentially in d. For POINT_3 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 labels need not be realizable.
Recent works on lower bounds for private counting have used similar techniques to obtain polylogarithmic lower bounds. Importantly continual counting with ℓ_∞ error is related to our problem of online learning via a reduction from private counters to private online learners for point functions. Online-learning lower bounds imply counting lower bounds with weaker parameters but the converse does not hold.
Online prediction under joint differential privacy releases only the answer to the current query without requiring this answer to hide the current example. For general Littlestone classes one work gives Õ(d^2 · ε^(-2) · log²(1/δ) · log²(T/β)) with probability at least 1−β. Their result allows adaptive inputs and satisfies the stronger challenge-privacy definition. Our guarantee concerns oblivious streams and joint privacy and removes the dependence on T. For point functions on any domain another work gives O(ε^(-2) · log²(1/δ)) prediction mistakes independently of the horizon but their result does not apply to every hypothesis class with finite Littlestone dimension.
Conclusion
This paper settles the question of how many mistakes an arbitrary private online learner must make on a fixed hypothesis class for every value of δ in the range 1/T < δ < 1/log T previously left open. The lower bound is polynomial in log T specifically Ω((log T)^(2/3)) when δ = Θ(1/log T). An upper bound for private prediction shows that the expected mistake bound can be independent of T with polylogarithmic dependence on 1/δ specifically O((log log T)²) for fixed d and δ = Θ(1/log T). The separation between learning and prediction is strict and grows with the time horizon T. The same separation holds for point functions on three elements and for every class of finite Littlestone dimension at least two. All proofs are for the oblivious setting with realisable streams.