Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
Authors: Bo Li
Wei Wang
Peng Ye
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
online learning
Primary area: theory

Abstract: We revisit the problem of private online learning, in which a learner receives a sequence of $T$ data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [2021] established that every concept class $\mathcal{H}$ with finite Littlestone dimension $d$ is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an $O_{d}(\log T)$ mistake bound against an oblivious adversary. However, their approach yields a suboptimal $\tilde{O}\_{d}(\sqrt{T})$ bound against an adaptive adversary. In this work, we present a new algorithm with a mistake bound of $O_{d}(\log T)$ against an adaptive adversary, closing this gap. We further investigate the problem in the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of $\tilde{O}_d(\sqrt{T})$ for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.

Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings
Bo Li Wei Wang Peng Ye²
Guangzhou HKUST Fok Ying Tung Research Institute Deeparmennt of Computer Science and Engineering, HKUST bli bli@ust.. hk, weiwaêcse. ust.hk pyeacâconnect.. ust. hk
Abstract
We revisit the problem of private online learning, in which learner receives sequence of T data points and has to respond at each time-step a hypothesis. It is required that the entire stream of output hypotheses should satisfy differential privacy. Prior work of Golowich and Livni [202T] established that every concept class H with finite Littlestone dimension d is privately online learnable in the realizable setting. In particular, they proposed an algorithm that achieves an Oaloog 7) mistake bound against an oblivious adversary. However, their approach yields suboptimal Ōa(VT) bound against an adaptive adversary. In this work, we present a new algorithm with mistake bound of Ou 7') against an adaptive adversary, closing this gap. We further investigate the problem the agnostic setting, which is more general than the realizable setting as it does not impose any assumptions on the data. We give an algorithm that obtains a sublinear regret of Óa(VT) for generic Littlestone classes, demonstrating that they are also privately online learnable in the agnostic setting.
Introduction
Machine learning has demonstrated remarkable performance in various applications due to its capability of extracting informative patterns from vast amounts data. However, this success also raises critical privacy concerns, particularly in domains like healthcare or finance, where models often process sensitive personal data. As machine learning technologies continue to advance, ensuring the protection of individual privacy has become an urgent societal and technical challenge.
Differential privacy (DP) [Dwork et al. 2006b a the de facto privacy- vrieacyprreeervng technique that addresses these concerns by rigorously formalized privacy guarantees. To ensure that algorithm protects privacy, DP requires that its output distribution remains nearly indistinguishable when any single individual's 's data is modified, thereby limiting privacy leakage. The central challenge in differentially private learning lies in designing algorithms that satisfy the DP requirement while remaining effective.
To understand the statistical cost of DP learning, extensive research has studied probably approxi- mately correct (PAC) learning under DP. A line of works [Alon et al., 2019 Bun et al., 2020 Alon ct al. 2022] has established that private learnability is characterized by Littlestone dimension, combinatorial measure originally proposed by Littlestone 1988 to describe (non-private) online learnability. In other words, concept class is privately learnable and only it is online learnable.
Motivated by this compelling equivalence, Golooich and Livni [ pioneered the study of privately online learning generic concept classes and demonstrated that the equivalence includes private online learnability in the realizable setting. For any concept class H with Littlestone dimension d, their algo- rithm achieves an Oloo T)) mistake bound in T rounds against an oblivious adversary that generates
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the entire data stream prior to interacting with the learner. However, for an adaptive adversary-whiee dynamically adjusts each data point based on the learner's output history- their approach yields suboptimal (v(V mistake bound. While this upper bound is sufficient to preserve a qualitative equivalence between private and non-private online learning against an adaptive adversary, it leaves open whether adaptive adversaries inherently require higher error rates. Subsequent works [Cohen et al. 2024. Dmitriev et al., 2024 et al. 2024) confirmed that cost of S2log T') is unavoidable, yet whether Oz(log 7') is achievable for adaptive settings remains unresolved.
Another limitation of their algorithm is that it operates under the realizability assumption, which requires all the data be perfectly labeled by some h E H. However, this assumption does not hold in many real-world scenarios, as the labeling function may not belong to H. or even not exist due to noise in data generation. This necessitates the consideration of the agnostic setting, where no assumptions are made for the data. Notably, in both (non-prive) -oon-pii online learning and private PAC learning, Littlestone classes remain provably learnable in the agnostic setting [Ben-Davis et al., 2009 Bun et al. 2020 Ghazi et al. [222bb Beimel et al. [202T] Alon et al. [2020]. This raises compelling open question: Can this result be generalized to private online learning?
1.1 Our Contributions
Our first contribution is algorithm for private online learning in the realizable adaptive setting with a logarithmic mistake bound.
Theorem 1.1. Let H be a concept class with Littlestone dimension d. In the realizable setting, there exists (e, difffereeel private online learner for H with expected mistake bound of ( (logT" + log(1/6))/s) against any adaptive adversary.
This result improves upon the previous Õa(vT) upper bound established by Golowich and Livni [2021] and addresses an open question they posed. As noted, the logarithmic dependence 7 is optimal. However, same as their algorithm. our approach exhibits a doubly exponential dependence on d, which significantly worse than the non-private case [Ghazi et al. 2021b).
We next turn to the agnostic setting. For general Littlestone classes, we show that it is possible to achieve an Õa(VT) regret, which is comparable to the non-private case in terms of T.
Theorem 1.2. Let H be a concept class with Litlestone dimension d. Then there exists an (s, 6)- differentially private online learner for H. with an expected regret of O)d against any adaptive adversary in the agnostic setting. When the adversary oblivious, the regret can be further reduced to OVVdT log T") + Ox(T /32/)
+ Oa(T" /E2/3)
As previously discussed, the results Golowich and Livni [021 can be interpreted as an equivalence between non-private and private online learning in the realizable setting. The above conclusion generalizes this equivalence to the agnostic setting. Moreover, for an oblivious adversary, the resulting regret matches the best known non-private constructive algorithm (Hanneke et al., 202T) when E 2 (a(L//T1/4). Such "privacy free" phenomenon has been widely observed by previous works on private OPE (c.g., [As et al. 2023b 2024)). Our result can be viewed as extending this to the nonparametric setting where the class can be infinite (but has finite Littlestone dimension).
1.2 Related Work
The investigation of private learning in the PAC framework [Valiant 1984] was pioneered by Ka-
siviswanathan et al. [201I]. Following this, a series of studies aimed to characterize the Icarnability
and sample complexity of learning generic concept classes under DP [Beimel et al.) 2010 2019
Feldman and Xiao 2014 Beimel et al. 2016 Alon et al. 2019 Ghazi et al., 20 Alon et al.
2022]. Beimel et al. [019 demonstrated that, under pure DP, the sample complexity is tightly determined by a measure called the representation dimension. For approximate DP, it was found that the learnability is characterized by the Littlestone dimension [Alon al.) 2019 [un et al. 2020 Alon
jet al. 2022]. However, a substantial gap persists between the upper and lower bounds concerning
sample complexity [Alon et al. 2019 Ghazi al. 2021b).
Golowich and Livni
2021 ' work extended private learning to the online model. Building upon the method of Bun et al. 2020 for private PAC learning, they proposed algorithms that attain mistake

---

bounds sublinear in the time horizon T. For the lower bound, several works [Cohen et al. 2024 Dmitriev et al. 2024 Li et al. 2024] discovered that (log T) mistakes are necessary under DP. This finding highlights notable discrepancy between private and non-private settings, as the mistake bound does not grow with 7 without privacy [Littlestone 1988) Whether a stronger separation holds was questioned by [Sanyal and Ramponi [2022].
The problem of privately online learning generic concept classes is also closely related to private online prediction from experts (OPE), which has been extensively studied in the literature (Dwork et al. et al. 2023a b 2024). While DP-OPE algorithms can be directly applied to finite concept classes, they are not suitable for infinite concept classes with finite Littlestone dimension, which are the focus of this article. Another related problem is private online prediction studied by Kaplan et al.) [2023]. where the learner only releases a single bit representing the prediction result for the current data point. Under this weaker model, they achieved a better mistake bound compared to the results in [Golowich] and Livni 202T] (in the stronger online learning model) terms of the Littlestone dimension.
2010a Smith and Thakurta 2013. Jain and Thakurta 2014 Aggawal and Singh 2017| Asi
2
Preliminaries
We provide some background on online learning, differential privacy, and sanitization in this section.
2.1
Online Learning
Online learning can be modeled as a sequential game played between a learner and an adversary. Let H. S. {0, 1 be a concept class over some domain X' and T be an integer indicating the total number of rounds, both of which are known to the learner and the adversary. At each round t E [T], the learne outputs some hypothesis h, : X' - f0. 1} while at the same time the adversary selects an example
(fr, E X x {0. 1} and presents it to the learner The performance of the learner is measured by the regret, which is the difference between the number of mistakes made by the learner and by the optimal concept in H (in hindsight), defined as
T Σ (hr(xs) + mol
I min Σ (x)) # vr).
The above scenario referred to as the agnostic setting, where there are no restrictions on the data generated by the adversary. This is in contrast to the realizable setting, where there is some ht* E H such that y/+ = ht (Ize) for every & E [T]. In this case, the regret is also called the mistake bound, as simply counts the number of mistakes made by the learner. A learner is proper if it always outputs he E H. for every t E [T]. Otherwise we say the learner is improper.
We consider two variants of adversaries according to their ability of choosing examples: oblivious and adaptive adversaries. An oblivious adversary can only determine the entire data sequence before interacting with the learner. That is, the data are independent of the learner's 's internal randomness. In contrast, an adaptive adversary can decide (Ize, U1) after observing the learner's output history (hi...., 1.) Note that in the realizable setting, the adversary does not have to fix in advance an h² that labels all the data but just needs to ensure the set (xI,,1),..... vi)...., (æT, WT) is consistent with some ht E H at the end of the game. Clearly, an adaptive adversary is more powerful and makes it harder to design an effective learning algorithm.
A learner is considered effective if it always attains sublinear (i.e., oT")) expected regret. We say a concept class H. is online learnable if there exists such a learner for H. Without privacy, online learnability is characterized by the Littlestone dimension [Littlestone] 1988 Ben-David et al., 2009].
Definition 2.1 (Shattered Tree). An X'-valued tree of depth n is complete binary T of depth n (i.e. the number of vertices on any root-to-leaf path is n)) whose vertices are labeled by elements from X. Every vertex located the (-th layer of T can be identified by a binary sequence (V11 ... -/--1)
{0, 1 such that it can be reached by starting from the root, then moving to the left child if y = 0 and to right child if otherwise y44 = 1 at step i [t 1]. For every e [n]. detine Te: {0, 13a-
X
.at....,,t-)) 1) E {0, 1 to the label of the vertex it identifies. We say T is shattered by H. if for every (y1,...: Vn) E {0, 1)",, there exists E H. such that
be the mapping from every sequence
Vt E [n], ((TT(V)..... .... 1)) Vt-
3

---

Definition 2.2 (Littlestone Dimension). The Littlestone dimension of concept class H. over X, denoted by Ldim Ldim(H), is the largest d such that there is X'valued tree T of depth d shattered by H.
One can also view X' as a concept class over domain H by defining z(h) = h(x)) for any I E X and h E H. This class X' is called the dual class of H. The dual Littlestone dimension of H. denoted by Ldim" (H), is defined as the Littlestone dimension of the dual class X.
In the realizable setting, it was shown by Littlestone [988] that the best attainable mistake bound is exactly Ldim(H) (H) for deterministic Iearners The mistake bound is achieved by an algorithm called the Standard Optimal Algorithm (SDA) that makes at most Ldim(H) (H) mistakes any realizable sequence. Like the work of Golowich and Livni [202]], we will access the SOA as a black box and our algorithm only relies on the fact that the SOA has mistake bound of (H)
We next introduce the online prediction from experts (OPE) problem. In this problem, there are N experts. At each round I, the algorithm chooses an expert i E [N] while the adversary chooses a loss function 4 : [N] + [0. 1]. Then the function l, is released to the algorithm and a loss of (1))) is incurred. The regret of the algorithm is defined as
T Σ
min Σ (()) N
Similar to online learning, an oblivious adversary can only choose (f,,..., "ih...,,y., lx) at the very beginning while an adaptive adversary can choose &, after seeing (f1,..., h2-1)
2.2 Differential Privacy
We start by recalling the classical notion of differential privacy. Let 2 be some data domain ......... 2r) 2 and S' = (2f...., 24)) E z be two data sequences of length T. We say S and S' are neighboring if they differ in at most one entry, i.e., there exists some such that 2j = 2/g for all j E [7] (i).
(Z = X' x {0, }} in online learning). Let S = (Z1....,
Definition 2.3 (Differential Privacy). A randomized algorithm A is (e, -)differrettial private if for any pair of neighboring data sequences S, S' E z and any set O of outputs, we have
Pr(A(S) E 0) S e Pr(A(S') E +
The above standard definition of differential privacy cannot capture the scenario that the data sequence is adaptively generated by an adversary. We next rigorously define differential privacy in the presence of adaptive inputs following the formulation of Jain et al. [2023). Consider T'-round game played between an algorithm A and an adversary B, where A presents some fe to B and receives some data 2, from B at every round t. The adversary B can (adaptively) choose one special round t" E [2]. At
this round, B generates two data points z/-² and 2(1), Then (b) will be sent to A. where be {0, is some global parameter that is unknown to both A and B. Let (bb) denote H's view of the game,
including (hı,... . hr) and the internal randomness of B. To ensure privacy, we require that B is unlikely to tell the value of b, formalized as follows.
Definition 2.4 (Differential Privacy with Adaptive Inputs). A randomized algorithm A is (c, 6)- differentially private if for any adversary B and any set O of views, we have
Pr(ITA,B(O) E 0] S e Pr([TA.s(1) E 0] +
Following the common treatment of privacy parameters in private learning Dwork et al. [2014], Bun et al. 2020). we will assume throughout this article that e is at most some small constant (say, 0.1) and 8 is significantly smaller than the reciprocal of the time horizon (i.e., 5 = ( We say concept class H. is privately online learnable in the realizable (or agnostic) setting if there is an (e, diffferrrentllllly private algorithm that attains a sublinear expected mistake bound (or regret) with
E S 0.1 and = (1),
We next present some useful tools to achieve differential privacy. The first is the Above Threshod mechanism [Dwork et al. 2009). Given a sequence of sensitivity-11 data point, the AboveThreshod mechanism allows us to privately monitor whether the cumulative sum exceeds some threshold.
For randomized learners, the optimal expected mistake bound is equal to the randomized Littlestone dimension of H. Filmus al. 2023). which is between (dim(H))2 and Ldim(H).

---

Theorem 2.5 (Dwork et al. 2009 2014 D. Let T be the time horizon, be the privacy parameter, and T be some threshold value. There exists an (e, difffeeeren private algorithm
that at each round &. E (T' receives some b, E [0, 1] (may be chosen adaptively) and responds an
at E 1 such that with probability 3. we have:
For all at = T, holds that Ei b, 2 T 8(n (1n229))
2
For all 0t -, holds that Ei b, S 80n T+1(22/9)
For a dataset 8 = (ZI,..., )n), let (ounts(z) denote the number of occurrence of 2 in S, i.c., Counts(z) Eig(n) 1|2 z|. We can use the PrivateHlitogram algorithm to privately publish Counts. The problem was studied in the context of sanitization in [Beimel al., 2016 Bun et al.) 2019]. Here we adopt the algorithm from Alliabbarpour et al. [0244] as the resulting error bound is easier to work with.
Theorem 2.6 (Private Histogram |Aliabbarpour et al., 2024). ). Let S be a dataset over Z. There exists an (e, 87-differentially private algorithm that outputs function Counts Z - such that with probability we have
sup c Counts(=) S 8In(8/8) EE
2.3 Sanitization
Let S= "2i,...,,,,,, ) E X be dataset. For any E H. define Ps(h) = - h(x,). The task of sanitization is to estimate Ps for every h E H.
Definition 2.7 ([Blum et al.) [2033] Beimel al. 2016)). Let H be a concept class over X. An (a, -)santiitt for H takes input a dataset S E X and outputs a function Est H - [0, such that with probability
, it holds that SuPдEи [Et((h) Ps(h) a.
Note that in the above definition we only require the sanitizer to output a function rather than a sanitized dataset. But one can always use it to generate synthetic dataset by finding an S' such that (h) - Ss (h)l < for all h E H. With probability 1 3, such an S' is guaranteed to exist since the input S satisfies this property. By the triangle inequality, we have |Ps (h) Ps(h)) s 2a. Therefore, we can also assume sanitizer directly outputs a sanitized dataset with error 2o.
Sometimes we may want to sanitize labeled dataset S E (X' x {0. 1))² with respect to an extended class Hlabel = [falabel h E H} over X' x {0, 1}. where llabel : X x {0, 1 - {0, 1 is the predicate indicating whether h makes an error, i.e., I laleel (label((z, ((x, y)) = [[((r) # y]. The following lemma demonstrates that a sanitizer for H. can be converted to one for Hclabel
Lemma 2.8 (Bousquet et al. (0200). Suppose there is an (E. (e.)))diiferennially private (a, 8)-sanitizer for H with input size n. Then there exists an (O(e), 0(0))-differentially private (O(a), O(3)-- sanitizer for Hlabel with input size n as long as n > (n(1/3// for some constant C.
3 Realizable Online Learning
In this section, we present our realizable learner that achieves a logarithmic mistake bound against an adaptive adversary. For elarity, denote by H the given concept class and by d its Littlestone dimension. For a sequence S of length 1, we write SOA(S) to represent the hypothesis that the SOA will output at time-step
We start by reiterating the method of Golowich and Livni [022] and analyzing why it fails to provide a logarithmic mistake bound in the presence of adaptive adversary. Their algorithm creates forest consisting of sufficiently many binary trees depth and maintains a set of nodes called pertinent nodes. Initially, every leaf node is pertinent and is associated with an empty sequence. At each round, the learner randomly selects a pertinent node and inserts the input example into the sequence assigned to this node. After that, an update step is performed.
The update procedure follows the key idea of constructing tournament examples in Bunn et al. 2020) Let S and S₂ be two sequences associated with two pertinent sibling nodes. Once it becomes the
5

---

case that (OA(S:) & SOA(S2), the algorithm chooses some E such that (Z)) + SOA(S2) (a) and guesses its label y7 E {0, 1] randomly. Suppose the SOA predicts the label of incorrectly as 1 ij on S& (k E 1)). Then a new sequence is created by appending the pair (क, y) to Sa- The two sibling nodes are removed from the set of pertinent nodes while their parent becomes pertinent and is associated with the new sequence. The algorithm then recursively performs the update on their parent until reaching a node whose sibling is not pertinent.
Suppose the input sequence is fixed and let /t* E H. be the labeling function. They observed that the random insertion of the examples is equivalent to a random permutation on every layer of the forest. Based on this observation, they proved that among the hypotheses produced by running the SOA on the sequences assigned to pertinent nodes, with high probability there exists at least frequent one. They designed a mechanism that privately releases frequent hypothesis at each round with logarithmic cost.
Since the output hypothesis is frequent at every round, once the algorithm makes a mistake, with some positive probability the state of the SOA on some sequence will change and an update will be performed. Note that h (2) = ÿ with probability 1/2. Therefore, for every tree the SOA will output h at the root with probability roughly 1/22". As long the number of trees is sufficiently large, the algorithm is able to identify h* privately. As a result, the total number of mistakes can be bounded by the number of nodes in the forest.
In the presence of an adaptive adversary, there are two main obstacles in applying their algorithm:
The output at each round partially reveals the information about the random assignment of examples. This disqualifies their random permutation argument in proving the existence of frequent hypotheses as it requires the examples and the random insertion to be independent.
The labeling function h* H. is not fixed in advance. Then one cannot simply conclude that every tournament example is correct with probability 1/2.
In their work, they resort to a standard reduction Desa-BBianch and Lugosi 2006) that transforms a learner against an oblivious adversary to one against adaptive adversary. However, the reduction requires running a new instance from the beginning at each round, incurring a mistake bound of vT due to advanced composition [Dwork et al. 2010b] of approximate DP.
We next illustrate how we tackle these two challenges to obtain a logarithmic regret. We address the first one by lazy update technique and the second one by the uniform convergence argument.
Lazy update. Unlike their algorithm, which performs the update immediately, we delay the update until there are enough collisions (i.e., sibling nodes with sequences on which the SOA outputs differently) in one layer. Once the condition is met, we update the whole layer and proceed to the upper layer. We then perform a random permutation in order to leverage their argument. Since the randomness is independent of the examples in this process, their argument can be successfully applied.
Uniform convergence. Since the labeling function h² is not predetermined, we have to argue that the number of trees consistent with h is sufficiently large simultaneously for every h H that is consistent with the data we have seen so far. However, one cannot directly apply the union bound since there can be infinitely many feasible labeling functions. To circumvent this, we observe that the number of data points in the forest (including input data points and tournament examples we generate) bounded. We can then prove the result by classical uniform convergence argument (Vapnik and Chervonenkis 1971 over H.
We present our update subroutine in Algorithm We use the symbol 1. for the case that the SOA fails on a non-realizable sequence. In the s-th layer, there are N₂ sequences Si...., 5%, S%, where S and 5 (i E [N,/2) are considered as sibling sequences. In the update procedure, we will create sequence from every pair of sibling sequences by padding tournament example. The new sequence is then placed in random location in the next layer, i.e., Set.1
-7())
We next describe how the entire algorithm works. In the s-th layer, the algorithm maintains N. sequences and a list L,, of frequent hypotheses. We keep outputting a hypothesis from L,, and run an instance of AboveThreshor Threshold to inspect the number of mistakes. Once the number exceeds a particular threshold, we switch to the next frequent hypothesis with a new instance of Above Threshold. We also insert the data point received at each round into random sequence. After iterating over all

---

Algorithm 1: Update
Global Parameter: concept class H
Input: sequences Si....,,N, ,N
1 No+1 <- N./2.
2 Create S1+1 ..... N such that every St+1 is initialized as I.
Se+1
3 Let be random permutation over [[++1]]
4 for i 1....,,, ......,,.11... do
if 2 + I and S2 + and SOA -11 (Sag) then
Pick I; such that SOA + SOA (2)) and draw y from {0,
uniformly.
Sate (Sy, (Tt, (.)) where j E (2i 1,2i] is such that (ZA())) & ū:.
end
end
Output 51+1
Se+1
N.41
frequent hypotheses in L.s, we perform an update, invoke PrivateHlstogram to filter new frequent hypotheses out, and repeat the same procedure for 1.411- The details are presented in Algorithm 2
Algorithm 2: Realizable learner
Global Parameter: time horizon T, concept class H. privacy parameters E, 6, failure
probability 3, initial number of nodes No
Input: input sequence ((x1, y1 )n),--. ---- (FT-
1 d Lddim (H), 8 <- 0, Eg + e/2, N₂ +- No/2' for i E [d].
2 Create Sq...., NN, such that every S is initialized as 0.
3 Create a list To + (SOA(0)}
Initiate instance of AboveThreshon with privacy parameter en and threshold
No + 8(In (+1(6778)
5 for t= 1,.., do
Set hy to be the first element in Lg and output h, halt if Lg is empty.
Sample is uniformly from [N, /2].
8
if (OA(S5)
SOA(S2,) * 1 and S Sh. (S (Iz, )+
* then
end
11
Feed (xp) + yel to AboveThreshold and receive ag E [T, a,
then Halt the current while < d and L, is emply do
13
and remove the first element in Ly.
15
Feed Sf, . S%, Update and receive S No+1'
16
8 8 +
17
Create multiset
Vg - {SOA(())) : [N./2] and SOA(S) = SOA(S),) + 1}.
18
Run PrivateHistogram with privacy parameters (co/d, 8/d) on V, and obtain County,
Set L,, + (h County, (h) 2 3M,/4), where M, = 128 2 6-2" N.-
19
20
end
Initiate new instance of A Threshold with privacy parameter so and threshold
N₂ + 8(1a Tll((TT/))
50
end
end
not hard to see that the algorithm preserves privacy. For utility, note that PrivateHlisogram extracts all frequent hypotheses in layer and stores them in L,. Suppose h L, can be obtained
7

---

by running the SOA on M, pairs of sibling sequences. By the property of Above Threshlld,,,,, we will output h until it makes roughly N, mistakes. Since every data point is inserted uniformly at random. classical results of the coupon collector's 's problem ensure that at least M,/2 22 pairs are covered and (DA(S2))) (S).)) Once I.g is exhausted, we proceed the next layer by invoking the update subroutine. By leveraging the idea of Goloowich and Livni] (202T) and the uniform convergence argument, we can prove that for every E H. that is consistent with the data we have seen so far, after the update there are Ma+1 CM² /N s+1 (C' is some constant) pairs of sibling sequences that are still consistent with and, either they are already collisions or running the SOA on them gives the same hypothesis hg- This allows to act recursively until d, which indicates La contains all the possible labeling functions. Solving the recurrence relation gives No 20(2"), which yields the desired mistake bound.
become collisions (i.e., SOA(S + SDA
We formally state our results in the following theorem. A detailed proof is given in Appendix B Setting the failure probability 3 = 1/T directly yields Theorem
Theorem 3.1. Let H. be concept class with Littlestone dimension d. Algorithm 2 with parameter
No = 20 (2*) (In(T/3) + (1) is an (s, -efff-rifrrytliially private online learner that makes at most
2 (2*))) (log T 1og(1/3) log(1/8))
8
mistakes with probability 1 - B.
We remark that the SOA be replaced by any deterministic online learner with bounded number of mistakes, For classes that can be properly learned by a deterministic online learner (c.g., thresholds over finite domain), our algorithm can be made proper as well. However, there are simple examples suggesting that randomness is necessary for proper online learning (see, e.g., [Hanneke et al. (02T Hence, our algorithm is improper in general.
4 Agnostic Online Learning
In this section, we present our algorithms in the agnostic setting. We first give a simple proper learner with a suboptimal regret. Then we show how to improve the regret to Óa(vT) (but result in an improper learner).
4.1 A Simple Algorithm Using Sanitization
In our algorithm, we divide the entire sequence into batches of size B. After each batch, we invoke sanitizer for Hlabel to obtain synthetic examples. All the synthetic data partitioned into B disjoint subsequences, where each subsequence contains exactly one data point from each batch. Our prediction at each round is determined by running (non-private) online learner on one of the disjoint subsequences. The overall framework is depicted in Algorithm 3 Similar to the SOA, we write A(S) to denote the output distribution of A after inputting sequence S.
Theorem 4.1. Let A be a (non-private) proper online learner with expected regret R(T") for any time horizon T" and B be an (e, 8) differrential private (a, -a-aniizee for Hlabel with input size B. Then Algorithm 3 is an (s, ddifferrennll private proper online learner that attains an expected regret of O(B R(TBB) B) + aT)) against an adaptive adversary conditioned on some event E with
Pr[E] 2 11-T11 1-TBBB
We now leverage the sanitizer for generic Littlestone classes proposed by Ghazi al. 2021b The
original statement exhibits sample complexity of (d' /ea²), which was obtained by applying their private proper agnostic learner to the synthetic data generator proposed by [Bouquee et al. [2020] But we can save a factor of 1/a through a few tweaks to the algorithm and analysis:
The sample complexity of the private proper PAC (realizable) learner (Ghazi et al. 202 can be improved to Ó /sa) by replacing the uniform convergence argument in their proof with a weaker relative uniform convergence argument.
The discriminator of [Bousquet et al.) 2020] can be implemented using private agnostic empirical learner, which does not incur the Oa(L/a²) generalization cost.
8

---

Algorithm 3: A simple private online learner
Global Parameter: time horizon T, concept class H. batch size B Input: online learner A, sanitizer B for Hlabel input sequence ((01, v1), .....,... (XT,
1 Initialize S) ...... S Ø.
2 for f = 1, ,. do
Let b = [t/ be the batch index.
Draw i, uniformly from [B], output hy where he A(S)).
i (mod [3) then
Run B on ((zz-B+1 Vt- Vt-BB)))))..) 1+1).....
(#t, ve) and construct synthetic data ((zp-B+1 (/i-BB+,,//BB.. B/+B++)...... ..................... (o', v()), exit if fail.
Perform random permutation over BB-B+ B-1:8/111-- (--B-1)..... (2', v())
S + (S), (1/ 14-- Vi a+))) for every i E [B].
8
end
10 end
We provide detailed discussion in Appendix D and present the final result below.
Theorem 4.2 ( (Bousqqet et al. 2020] and [Ghazi et al. 2021b), Strengthened). Let H be a concept class with Littlestone dimension d and dual Littlestone dimension d² Then there exists an (s, 6)- differentially private (a, B) Sasiitzzee for H with sample complexity Ö /ea²).
combination of Theorem 4.1 Theorem 4.2
Lemma 2.8 and regret bounds for proper online
learning [Alon et al.
2021
Hanneke et al. 2021 1 yields the following regret bound for private online
[Bhaskar 2021 J. it implies that every Littlestone class is privately (and properly) online learnable in the agnostic setting.
learning. Since d' 22"
Corollary 4.3. Let H be a concept class with Littlestone dimension d and dual Listlestone dimension d'. Then there exists (c, difffeerrennl private proper online learner for H with expected regret of O(T3/4 (d dd /4) against an adaptive adversary.
4.2 Online Learning via Privately Constructing Experts
We have shown a private online learner with regret (a(74/4). However, even if we have a sanitizer with error 1/B optimizing the choice of B (i.e., B (T1333) gives Oal Oa(vTB+ + T/B) Oa(Te/3) regret, which is still significantly worse than the Oa(vT) bound in the non-private case.
To break this barrier, we exploit the approach of constructing experts, which was proposed by Ben+ David et al. [2009] for agnostic online learning. The idea is based on the fact that for any h E H. the SOA makes at most mistakes on a sequence relabeled by h. Hence one can enumerate the rounds at which the SOA makes mistakes and use the SOA to simulate the behavior of h on the entire input sequence. Then an Ö(VdT) regret can be achieved by creating (2)) O(Td) instances of the SOA as experts and running OPE algorithm [Littlestone and Warmuth 1994
Since the constructed experts heavily depend on the input data, directly employing the same method would violate privacy. Therefore, we again resort to the idea of sanitization. By incorporating the binary mechanism for continual observation [Dwork et al. 2010aa]. we can detect a concept makes more than Öa(VT) mistakes a time interval. We can enumerate the d endpoints that decide the intervals. Since we also have to enumerate which sanitized data points are fed to the SOA, the number of experts will grow by some amount, but remains adequate to run a private OPE algorithm.
An issue of the above construction is that the output hypothesis of the SOA may not belong to H. and its mistakes cannot be observed on sanitized data. Moreover, the structure the output hypotheses of the SOA is hard to characterize. We bypass this by replacing the SOA with the online leameer proposed by Hanneke et al. 2022]. Their online learner has slightly larger mistake bound of (dd) but the output is guaranteed to be the majority of very few concepts in H. Thus, we only have to sanitize moderately larger class. Now we have set of experts such that at least one them is no worse than the optimal h² E H by (v(T)). This allows us to run any private OPE algorithm to obtain a private online learner for H.

---

Note that we can further reduce the number of mistakes made by the experts if we have a sanitizer with a better dependence on a. Though we don't know the current sample complexity of sanitization can be improved, we can still refine the above result by an alternative approach. This is due to an observation that we only need to detect if expert already made a lot of mistakes rather than an accurate estimate of the number of mistakes. We design an algorithm for this problem with sample complexity (a(1/al.5) based on Bousquet et al. [2020] 's framework, thereby achieving better regret. We present below a simplified statement of our final result, which implies Theorem 1.2 by applying existing algorithms for private OPE (Jain and Thakurta 2014 Asi et al. 2024). The detailed
results and proofs can be found in Appendix
Theorem 4.4. Let H. be a concept class with Littlestone dimension d. Suppose there exists an (e, 8) differentially private algorithu for the OPE problem with N experts and time horizon T that has an expected regret of RlE, 8, T, .). Then there exists a (2z, 28) differentially private online learner for H with an expected regret of R(E, 6, N) + + /3 /22/3). Furthermore, if the regret bound for the OPE problem holds against an adaptive adversary, and the resulting regret bound for online learning H also holds against an adaptive adversary.
5 Discussion and Future Work
In this work, we study online learning under differential privacy. For the realizable setting, we propose an algorithm with an Oz(log 7) mistake bound against any adaptive adversary, which significantly improves the previous result of Golowich and Livni [221] and achieves an optimal dependence T. For the agnostic setting, rate as the non-private case in terms of 7 up to logarithmic factors.
method yields regret of O₂ (T),)), which achieves nearly the same
We discuss some potential future directions below.
Proper private online learning. Our optimal algorithms for realizable and agnostic settings are improper. For the realizable setting, it is known that a mistake bound of (p(polylog(TT) is attainable without privacy [Daskalakis and Golowich| 2022]. J. We ask if this is also possible under differential privacy. For the agnostic setting, our Algorithm has a suboptimal (a(7%/4) regret. We believe this can be improved to Ōa(v VT) and leave it as future work.
Dependence on d. All of our algorithms incur a doubly exponential dependence on d. We wonder the dependence can be improved polynomial in private PAC learning (Ghazi et al. 2021b P
this work, we assume the time horizon T known in advance. This requirement can be removed by the classical doubling trick splitting the input sequence into buckets lengtss 1, 2, 4, ... and running our algorithm on each bucket separately (with T 1,2,4, 4,8, .... This does not affect our regret bound for the agnostic setting but will increase the mistake bound of our realizable learner (Algorithm 2) Oa(log" T"). Whether mistake bound of Oa(log 7)) is still achievable without knowing in advance is an interesting question.
Unknown horizon
Acknowledgments and Disclosure of Funding
The research was supported in part by an NSFC grant 62432008, RGC RIF grant R6021-20. an RGC TRS grant T43-513/23N-2, RGC CRF grants C7004-22G, C1029-22G and C6015-23G, NSFC/RGC grant CRS_ TRS_HKUST601/22 and RGC GRF grants 16207922, 16207423, 16203824 and 16211122
References
Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 32-40, 2017.
Maryam Aliakbarpour, Rose Silver, Thomas Steinke, and Jonathan Ullman. Differentially private medians and interior points for non-pathological data. 15th Innovations Theoretical Computer Science Conference, pages 3:1-3:21, 2024. 2024.
"The realizable against oblivious adversary solved by Lyu 2025
10

---

Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Proceedings of the 51 Annual ACM Symposium on Theory of Computing. pages 852-860, 2019.
Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Proceedings of the 33rd Conference on Leurning Theory, volume 125, pages 11 19-1122 2020.
Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev, Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, pages 447-455, 2021.
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. Journal of the ACM, (9(4)1133, 2022.
Martin Anthony and Peter I., Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
Martin Anthony and John Shawe-Taylor. A result of Vapnik with applications. Discrete Applied Mathematics, 47(3):207-217, 1993.
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, volume 202, pages 1107-1120, 2023a.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. In Proceedings of the 36th Conference on Learning Theory, volume 195, pages 674-699 2023b.
Hilal Asi, Tomer Koren, Daogao Liu, and Kunal Talwar. Private online learning via lazy algorithms. In Advances Neural Information Processing Systems, volume 37, pages 112158-12218, 2024.
Amos Beimel, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. In Proceedings of the 7th International Conference on Theory of Cryptography, volume 5978, pages 437-454, 2010.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. Approxi- mate differential privacy. Theory of Computing, 12(1):1-61, 2016.
Amos Beimel, Kobbi Nissim, and Uni Stemmer. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research, 20(146):1-33, 2019.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples. Algorithmica, 83:177-215, 2021.
Shai Ben-David, Dávid Pâl, and Shai Shalev-Shwartz. Agnostic online learning. In Proceedings of the 22nd Conference on Learning Theory, 2009.
Siddharth Bhaskar. Thicket density. The Journal of Symbolic Logic, 06(1):100-12) 2021.
Avrim Blum, Katrina Ligett, and Aaron Roth, A learning theory approach to noninteractive database privacy. Journal of the ACM, 60(2):1-25, 2013.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the Vapnik- Chenkkk-hervonniis dimension. Journal of the ACM, 36(4):929 1989.
Olivier Bousquet, Roi Livni, and Shay Moran. Synthetic data generators sequential and private. In Advances in Neural Information Processing Systems, volume 33, pages 7114-7124, 2020.
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 634 649, 2015.
Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. Journal of Machine Learning Research, 10394) 2019.

---

Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, pages 389-402, 2020.
Nicolo Cesa-Bianchi Press, 2006.
Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions Information and System Security, 14(3):1-24, 2011.
Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, pages 493-507, 1952.
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 the 37th Conference on Learning Theory, volume 247, pages 1200-1222, 2024.
Kevin P. Costello. Concentration bounds for sums of random variables of per- mutations, Jan 2013. URL httts::/mathoverrfll http://rwnne//eeeioo/////1/11/1 sencentration-bournee storrssuss-ae of rand-rrado-- of prtpa//eeoe.errmtttttttoooo///2a
120257
Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizability to learning in games. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing, pages 846-859, 2022.
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 37th Conference Learning Theory, volume 247, pages 1398,, 2024.
Richard M Dudley. Central limit theorems for empirical measures. The Annals of Probability, 6(6): 899-929, 1978.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, pages 265-284, 2006b.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the 4lst Annual ACM Symposium on Theory of Computing. pages 381-390, 2009.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under con- tinual observation. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing. pages 715-724, 2010a.
Cynthia Dwork, Guy Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pages 51-60, 2010b.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, 11:44:111-407, 2014.
Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Proceedings of the 27th Conference on Learning Theory, volume 35, pages 1000-1019, 2014.
Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran. Optimal prediction using expert advice and randomized Littlestone dimension. In Proceedings of the 36th Conference on Learning Theory, volume 195, pages 773-836 2023.
12

---

Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Near-tight closure bounds for the Littlestone and threshold dimensions. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132, pages 686-696, 2021a.
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy, In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing. pages 183-196 2021b.
Noah Golowich and Roi Livni. Littlestone classes are privately online learnable. In Advances in Neural Information Processing Systems, volume 34, pages 1462--1177, 2021.
Alon Gonen, Elad Hazan, and Shay Moran. Private learning implies online learning: An efficient reduction. In Advances in Neural Information Processing Systems, volume 32, pages 8702-8712, 2019.
Steve Hanneke, Roi Livni, and Shay Moran. Online learning with simple predictors and combinato- rial characterization of minimax in 0/1 games. In Proceedings of 34th Conference on Learning Theory, volume 134, pages 2289-2314, 2021.
David Haussler. Decision theoretic generalizations the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-150, 1992.
Monika Henzinger, Roodabeh Safavi, and Salil Vadhan. Concurrent composition for differentially hbg/abs//// aaaaa///.1.... 2411100399
private continual mechanisms, 2025. https:// http///axvvv.vv httpaaavvvv...raaaa/
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association. 58(301):13-30, 1963.
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In Proceedings of the 40th International Conference Machine Learning, volume 202, pages 14654-14678, 2023.
Prateek Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differen- tially private learning. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 476-484, 2014.
Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer. Black-box differential privacy for interactive ML. Advances Neural Information Processing Systems, volume 36, pages 77313-77330 2023.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-883 826, 2011.
Michael J Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. Machine Learning, 17: 17:1,,, 1994.
Bo Li, Wei Wang, and Peng Ye. The limits of differential privacy in online learning. Advances in 2024.
Neural Information Processing Systems, volume 37, pages
Bo Li, Wei Wang, and Peng Ye. Private realizable-to-agnostt transformation with near-optimal sample complexity. In Proceedings of 38th Conference on Learning Theory, volume 291, pages 3700-3722, 2025.
Nick Littlestone.
Learning quickly when irrelevant attributes abound: new thresolt algorithm. Machine learning, 2(4):285-318, 1988.
Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-261 1994.
Xin Lyu. Composition theorems for interactive differential privacy. In Advances in Neural Information Processing Systems, volume 35, pages 9700-9712. 2022.
Xin Lyu. Private learning of littlestone classes, revisited, 2025. URLLhttpp : h/tp:///xxvvvr//// abs 2510.00076
13

---

Colin McDiarmid. On the method of bounded differences. In J.Editor Siemons, editor, Surveys in Combinatorics, 1989: Invited Papers the Tweifth British Combinatorial Conference, London Mathematical Society Lecture Note Series, pages 148-188. Cambridge University Press, 1989.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Anmual IEEE Symposium on Foundations of Computer Science, pages 94-103, 2007.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111-1555 2015.
Amartya Sanyal and Giorgia Ramponi. Open problem: Do you pay for privacy in online learning? In Proceedings of the 35th Conference on Learning Theory, volume 178, pages 5633-5637, 2022.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
Hans Ulrich Simon. General bounds the number of examples needed for learning probabilistic concepts. Journal of Computer and System Sciences, 52(2):239-22 254,, 1996.
Adam Smith and Abhradeep Thakurta. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems, volume 26, pages 2733-2741, 2013.
Michel Talagrand. Sharper bounds for gaussian and empirical processes. The Annals of Probability. 22:28-76, 1994.
Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publications Mathématiques de l'Institut des Hautes Etudes Scientifiques, 81:73-205, 1995.
Salil Vadhan and Tianhao Wang. Concurrent composition of differential privacy. In Theory of Cryptography: 19th International Conference, pages 582-604. Springer, 2021.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(1 11:44111142, 1984.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264-200, 1971.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We state our results for the realizable and agnostic settings in the abstract and introduction. They constitute our main contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
Complete proofs of all the results can be found in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
ic for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppi.ccppulli//uuuii wwwiiicgguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tp::///euis..eeeeee www.eeurii.ccpppuiieeeeeeee
Answer: [Yes]
Justification:
The research in this paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily theoretical and does not have direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
18

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not have such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswppteeeee whworee.wthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
19

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
20

---

The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- standad components.
Please refer to our LLM policy hattps://neurips... 200p://ee////oofeeeeee////////// for what should or should not be described.
21

---

A Additional Preliminaries
A.1 PAC Learning
Let P be distribution over domain X' and h be hypothesis, we write P(h) to denote Eg-r (x)] For an unlabeled dataset S E X", we write Ps denote the empirical distribution over S. Given two hypotheses h1 and h2, we define 11 @he as the hypothesis such that (h (22) = 1[ (x) * h2 for all x X. For two hypothesis classes H. and H2, define H1 @ Hz {hr + h2 h H1, h2 E H2)) The generalization disagreement between h and h2 with respect to P is defined
as disp(h1, h2) = P(h1 @ h2). The empirical disagreement between h and h2 defined as diss(h; (h1, h2) = disp, h.).
We then take into account the labels. For distribution P over X' x {0, 1]. The generalization error of hypothesis h with respect P is defined p (r(x.)) [h(x) # y]. Recall that ( v)) = I[h(x) A y), we have errp (h) = P(Ilabel), ). For a labeled dataset E (0,)),, the empirical error of h with respect to S is defined as (h) err (h).
We now introduce the PAC learning model. In this model, the learner takes as input a labeled dataset S with each element sampled from some unknown distribution P. Moreover, is guaranteed that there exists some h* E H that labels all the data points. The task of the leaner is to find a hypothesis that minimizes the generalization error.
Definition A.1 (PAC Learning [Valiant 1984)
An algorithm A is said to be (a,, 33)-AC learner
for concept class H with sample complexity n if for any distribution P over X' x {0, 1 such that Pr(ny)) [h* (z) y] for some h E H. it takes as input a dataset S ((x1, 91 .... (In, Bn)),
where every (z4, y/) is drawn i..d. from P. and outputs hypothesis h satisfying
Pr(errp(h) S a] 2 1--3.
where the probability is taken over the random generation of S and the random coins of A.
In contrast to PAC learning. the agnostic learning model [Haussler 1992. Kearns al. 1994 imposes no assumptions on the underlying distribution. The objective is to identify a hypothesis whose generalization error is close to that of the best one in H.
Definition A.2 (Agnostic Learning). An algorithm is said to be an (a, -ag-gnosttcc learner for concept class H. with sample complexity n if for any distribution over X' x {0. 1]. takes as input dataset 5 ((x1, 3/11 .1),.... (Zn, Bn)), where every (I,, yi) is drawn i.i.d. from P, and outputs hypothesis h satisfying
Pr(errp(h)
S inf errp(h") + a] 2 1-3, H*ER
where the probability is taken over the random generation of S and the random coins of A.
learner A is said to be proper if it always output some h H. Otherwise we say A is improper.
Definition A.3 (Growth Function). Let S (I1....,,Tn) En) be unlabeled dataset. The projection of H onto S is defined as
(S) = ((ri),, (In, h(xn))) h E H}.
The growth function of H is defined as (1x) maxsex* (S)).
Now we can define the Vapnik- Vapnik-Chervoneen Chervoneevvss (VC) dimension Vapnik and Chervonenkis 1971]. which characterizes the PAC and agnostic learnability of concept class.
Definition A.4. Let H be concept class over X. The VC dimension of H. denoted by VCdim(H), is the largest d such that (d) 2d.
Also, one can view X' as the concept class and H. as the domain. The dual VC dimension of 76 is then defined VCdim (H) VCdim(X').
The following Sauer's lemma [Sauer 1972] states that the growth function polynomially bounded as long as the class has finite VC dimension.
22

---

Lemma A.5 (Sauer's Lemma). Let H. be concept class with VC dimension dy. Then Il - 2" for any I dy and
dy
dv
(n)
dv
for all n > dy.
In this work, we may use the following technical lemma together with Sauer's lemma to derive sample complexity bounds.
Lemma A.6 (Shalee- Shwartz and Ben-David 2014). )) Let 2 and > Then: (2 + b.
4o In (2 25
The following realizable generalization result (Vapnik and Chervonenkis, 1971 Blumer et al., 1989 suggests that given sufficient examples, with high probability every pair of concepts with small empirical disagreement also has a small generalization disagreement.
Lemma A.7 (Realizable Generalization Bound), Let H be concept class with VC dimension dy and be a distribution over X. Suppose n dataset of size n, where each element in $ is drawn i... from P and
ni 2 C dy In(1/a) + In(133)
a
for some universal constant C (i.e.. C does not depend on H and P). Then with probability 1 over the random generation of S, we have for all h1, l12 E H:
disisp(h,, S a then diss(hi, h2) S 2a.
disg h2) S then disp(h1, h2) S 2a.
The above bound requires the disagreement to be small. This contrast to the following agnostic generalization bound, which provides an absolute upper bound on the difference between empirical error and generalization error. However, it incurs an extra factor of 1/a.
Lemma A.8 (Agnostic Generalization Bound Talagrand 1994)). Let H. be concept class with VC dimension dy and P be a distribution over X' [0,1}. Suppose S E (X x {0, 1))" a dataset of size n, where each element in S is drawn i.i.d. from P and
n 2 dy In(1/8)
2²
for some universal constant C. Then with probability 3 over the random generation of S, we have suPseM suPpexlerss(h) erry(h)] S a.
In PAC (and agnostic) learning. the output hypothesis is required to have low generalization error. In contrast, empirical learners produce hypotheses only with low empirical errors.
Definition A.9 (Empirical Learner Bun et al. 2015)). An algorithm A is said to be an (a, $)- PAC empirical learner concept class H with sample complexity n takes as input dataset S (X (0, 1})" such that min (r")(h") = 0. and outputs a hypothesis h satisfying
Pr(errs(h) S a] 2 11---
Similarly, algorithm AA is said to be (a., -agnostic empirical learner for concept class H. with sample complexity n it takes as input a dataset E (X' x {0, 1}}" and outputs a hypothesis satisfying
Pr(errs(h) < min errs(h() + a] B*ER
3.
When there privacy constraints, empirical learners can be trivially constructed. The following lemma shows that one can create private empirical learners from private learners.
Lemma A.10 Li et al. 2025). Based on [Bun et al. 2015)). Let A be an (e, ( (e.ff-diferenntialll private (a, 3) 3PC learner for with sample complexity n, where E S and n 2 1/E. Then there exists
(1, ((/==) differentially private (a, -PC empirical learner A' for H. with sample complexity (EE).. Moreover, if A is proper, then A' is also proper.
Remark. A similar result can be derived for transforming agnostic learners to agnostic empirical learners [Bun et al. 2019). However, this could be suboptimal terms of a since agnostic learning
requires ((VCdim H.) a examples [Simon
[996 even without privacy.
23

---

A.2
Concentration Inequalities
Lemma A.11 (Hoeffding's Inequality [Hoeftding 1963)). Let ZI...., Zn be independent bounded random variables with Z [a. b). Then
212 n(b a)²
Pr
21
21
S exp (Tn(b
for all 0.
Lemma A.12 (Mediarmid's Incquality for Permutations (McDiarmid 1989 Golowich and Livni
2021 Talagrand 1995 Costello| 2013)). Suppose f z" is some function such that
[ 2n) [2 3n]l for any sequences (ž1,..., 2n) and ( that
differ in at most one element. Let (21, 2n) ) E 2 be some fixed sequence and x be random permutation over [n], then we have
2r2
Pr (E))(
f(2x(1), ((= 2 S exp
9nc²
Lemma A.13 (Chernoff Bound, Sampling Without Replacement [Chernoff
1952 Hoeffding 1963
Let Zi....; Zn be random variables drawn without replacement from (Z1...., 2N) (N 2 n) and Z Ei= Zi denote their sum. Then for any t E (0, 1), we have
{0, 1
E
s (1- S exp (-
2
Lemma A.14 (Coupon Collector). Let XI...., Xm be i.i.d. drawn from the uniform distribution over [n]. Suppose 2 2n and 4 (n(133) < k S n, then
Pr[ltj E [K] 3i E [m]. X, = jhl > 1 3.
Proof. For any S S [k], we have
(1
|S| m
Pr[Vi [m], X, $ S]
I <exp(-m|Si/m)
n
Therefore,
Pr[Ki E [k] Bi [m], X; = j}l k/2]
=1 - Pr(3S [k] with |S| [k/2] s.t. vi [ma]. X, $ S]
k
21
exp(-m (k/21/m)
[k/21/
2 exp( (k))
21 B.
A.3 Closure Bounds Under Boolean Aggregation
The following notion of O-covering number was introduced by Rakhlin et al. 2015
Definition A.15 ([Rakhlin er al., (2015) Let T be an xa-uueed tree depth n and V a of (0, 1}- valued tree of depth n.. We say is 0-cover of H on T if for any h E H and yı...., Un (0, 1) there exists V E V such that
Vt E [ri]. h(TT 1)) Velvi ..... 1)-
The O-covering number of H. on T is defined as
(000 H.
min V O-cover 74 on
V
Also, define
(O,, n)
max T an X-valued tree of depth
N(0, H, 7).

---

They proved the following upper bound on the O-covering number for Littlestone classes, which can be seen as an analogy of the celebrated Sauer's lemma on trees.
Lemma A.16 (Rakhlin et al.) 2015)). Lei H be a concept class with Littlestone dimension d. Then we have (0, H, n) S 2" for any n S d and
Cn
(0 H. S
1
for all n >
The following fact directly follows from the definition of shattering on trees (for rigorous proof, [Ghazi et al.) [021a])-
Fact A.17. Let H. be a concepi class of Littlestone dimension d. Then (00, H, d) = 24
Let G: : {0, 13x - {0, 1} be a boolean funetion and Hı, Hy be hypothesis classes over domain
X. Define the hypothesis class G(Hl....., Hx)
G(HI. H4) (G ha) hi E Hi,...,, h2 E HaJ.
where
hx)(2) G(N) h& (x)))) for any x X. The following lemma bounds the VC dimension and the Littlestone dimension of G(H1,.... Hx). The upper bound on the VC dimension is by classical argument of Dudley 1978 (see [Alon al.) [020] for detailed explanation) that leverages Sauer's lemma to bound the growth function. The upper bound on the Littlestone dimension is due to [Ghazi al.) [0211]] in similar manner using Lemma A.16
Lemma A.18. Lel G : {0, 13 + {0, }} be a boolean function and Hi,... HA be k hypotheses classes over domain X. Let d max4e[M] Ldim(H:) and dy max4e[K] VCdim(H.)). Then have
Ldim(G(HH,...... H.x) Olod k)
and
VCdim(G(HH, H₂)) (kdy log k)-
An analogous argument also leads to the following bounds on the dual VC dimension and the dual Littlestone dimension. We include proof for completeness.
Lemma A.19, Let {0, 1 + {0, 1] be a boolean function and Hi...., Hi be k hypotheses classes over domain X. Let d' max4e(]] Ldim" (Hi) and di maxie(k] VCdim" (H,). Then have
Ldim"(G(HH.... H₂,)) = OKkd* log k)
and
VCdim (G(HI, H.s)) Okkd log k).
Proof. We bound the dual VC dimension first. Let
= (G 11) ..., G.,",.....
be dataset of size 2 di over G(H H2). Construct & datasets S , where S (h)..... hi') a dataset over H, for every i [k). By Sauer's lemma, we have (since the function (en/z)" is monotonically increasing when 1 _ < n)
S*
(vCcee) en (VCdmm
VCdim VH.i
dv.
Mx(S)) s
di
Then we can bound the size of projection of X' onto
[s) = -((G()),.... (.) (z)()).........))))))))))))))) G(h (T) x E X
(=) (,
: x XH
< (icce(caa.....ceoo.......t......
(Z) (zI...., xx)) E x < (((A)(())....,((((()) ()(x)) (1((2)).... (z),..,, E xb311
= 1Ix(S*) x...x (8*)
I (en/di.)hut
25

---

This implies (n) I (en/dz)) ) )ady, which is o(2") as + co. Therefore, G(H1,... Hz) has finite dual VC dimension. Denote it by Dv. taking DV gives 2 I (eD jkdi Solving the inequality yields D = Okkd log k).
We now bound the dual Littlestone dimension in a similar way. Let T be G(H1, ) > tree with depth n - d². Then there exists &o trees T ,..., such that T an Valval tree with depth for every [k], and
(1 ................................ (1-1) G(( (y Dh- 1), T. (yI.... . v)-1))
for all E [n] and (y1 (....... v1- E {0. 10.113-1. By Lemma A.16 we have
Ldim" (HH,
N(0,XX Ldii" (HH,
en
en
For every E [k), pick a O-cover V = ,......., ..... Dilv') of X T with size -V,, Construct
= (Vú.. i E [[V [|V*]]]
where Vi is f0, 1 J- valued tree such that
V (yn 11-1) G() (UI......t-1)......
Vh.da (y1, (y1....,B) 1)-
for all E [n] and ,t,..... E {0, 13 Then we have [V] S (en/d*)ket For any E X and (y1,... ,u.....9u)) E {0,1) 13", every [k] there exists Vidi V such that
WE [n], x< (T, (V1. vt-1)) V (y ......., 9t-11
since V a 0-cover X on T As a consequence, we have for all E [n]:
x (Te(y)...... - G(x((T (..................... M1 M1-1)) ...., (T, (y1, ,t, ,t--1))) =G(V, (yh..... y6 11-1), Vluck Jur ..-.)) Vifi (yl......34 9t-1)..
(yi,...
This means V is a O-cover of X' on T. The desired upper bound then implied by the same calculation for the dual VC dimension.
A.4 Other Tools for Privacy
One of the basic mechanisms for ensuring differential privacy is the Laplace mechanism. Definition A.20 (Laplace Distribution). A random variable has probability distribution Lap(b) if its probability density function is f(x) 2b exp( (xp(-(=//b),
Definition A.21 (Sensitivity). Let nh
+ R be function. We say f has sensitivity A if for any neighboring datasets S₁ and S2, we have [( f(S2) < A.
Lemma A.22 (Laplace Mechanism [Dwork et al. 2006b)). Let be a function with sensitivity A. The mechanism that takes as input dataset S E 2 and outputs f(S) + X with X ~ Lap(A/e) is (c, 0)- difffeerrttl private. Moreover, we have
In(1/3)
Pr X~Ian(A/a
X
> 1-
Given finite and score function q 3" R We say g has sensitivity A if q(-, has sensitivity A for all h E R. The exponential mechanism takes as input a dataset S E - and selects an element E with probability
exp(-e (SS,1)/2A)
ΣSER cxp(-E (S, f)/2A)
Lemma A.23 (McSherry and Talwar 2007). The exponential mechanism is (E, differreentllllll private. Moreover, with probability
3. outputs an E R. such that
2A
4(S, h) < min (S, JER
In (1(2))33).
26

---

B Proof of Theorem 3.1
We first prove the following important property of the subroutine Update.
Lemma B.1. Let H be a concept class with Littlesooee dimension and F be a subset of H. Let -i...., SN, be the input of Update (Algorithm [ such that [S < 28 for all i [N,]. Define
1 = EiE E [N./2] S and S2 are consistent with f}
and 1ę+1 similarly for the output Sht1, S
Suppose for every f E F, we have
{i E 13 SOA(S + SOA (SA)) 2 M.
Then for any < r1 S 2
6 and 12 > O, with probability at least
(-(c(Att+/ 2d
(oxp
2r1
(-
2r
eep
+ exp
M
9.N
it holds that for each f E F,, either
(M/2 r1)
Hi 18th SOA(SE))) # SOA(S S5+
12.
6N
or there exists some hy (depends on f) such that
(M/2 - -r1)²
Hi E 1 SOA(S = SOA(S?+1) = hool
6Ns+1
Proof. Let be the set of unlabelled data points occurred in any Sf....,$S i.e.,
No P= (x: (c,0) E 1)
1=1
Let Q= (ā. E [N++]]] Then we have |P| 2sN, and |Q| S N,/2. By Sauer's lemma, identify a subset G C F with | S (=m)² where m = (2d + 1/2) 2 (2s + 1/2) 2 IPUQ) such that for every f F, there exists some g E G such that f and g are consistent on both P and Q Hence, it suffices to first prove the conclusion for every E G, then apply a union bound over G.
Fix some g G and define the following set
Ug = (i E [Ns+1]: S4t) consistent with g}.
By Hoeffding's inequality, we have
2r
Pr Pr & M/2 - -r] exp
M
Note that according to our algorithm, U, only depends on the randomness of 7j 's and is independent of π. Consequently, the above probability is only taken over the randomness of yz
We then condition fixed set Ug with UU M/2 ri. Let ((SOA(S h i Ug denote the number of occurrence of / when running the SOA on s for all i E Ug. As consequence,
Σn Llg|. If maxx Ch
2Ual it follows that Σn cf < max ch Σn ch | Hence for
27

---

any i [N++1/2], we have
Pr(i I9 A SOA(S221) + SDA(S Ugl
Pr[S and 22 are consislent with g S0A(S + SOA(S U
ΣN ch
Nst1 Not1 -1
Σ
( - ch)
No+1 (N - 1)
h
1ug1 TOp--Ene ch
No+1 (N 1)
U
3.22
Therefore, can leverage Mediarmid's inequality for permutations (by setting f to be the function that counts i [N++1/2] such that i I and (OA(S * (SA 1)) to show
2r
Pr[l(i E r SOA(SEt1) * SOA(S - R r2 Ug) S exp
9N
where R =
(M/2-r1) No+1/2- 6.
1
< K[f].
3N
Now consider the case that max, ch 2 2 Then for any [Ns+ have
Let fi be the hypothesis such that Cha = max, Ch.
Pr[Stt]] and S are consistent with g A SDA() SOA(S ho Ugg
Cho
Cho 1
No+1 No+1
4|U 12 - 6|U,1
9N2+1
Ug
3N2 s+1 where the last inequality is because [Ug] > M/22 - r1 2 6. Similarly, we have
2r
Pr[li 15 SOA(S?t))) SOA( ho | R U exp
99
Putting what we have proved so far together, for every E G, it holds with probability at least
2r²
2r3
1- exexp
M
exp
9NN
that either
Hi + SDA(S # -SA(SS }}} > R 12 or there exists some ho such that
Hi 1 SOA(S = SOA S0A(S551)) ho}l > R - T2. Applying a union bound over G yields the desired result.
We then analyze the privacy of Algorithm 2
Lemma B.2. Algorithm is (e, diffferrrnttilll private.
Proof. During the entire procedure, we run many instances of AboveThheshorr on disjoint sequences.
Therefore by Theorem 2.5 putting them all together is still e e/2-differenntially private.
28

---

Now consider the multiple executions of PrivateHlitogram, Note that changing single input exam- ple (z,, y4) only changes most one S for every Then by Theorem 2.6 each PrivateHlistorram is (e/ /2d, ( -ilfeeferret private. Since we run PrivateHlistgrrm only once for every E [d] basic composition ensures the overall algorithm is (e, diffferrent private 3l
We now show the following utility guarantee using Lemma yields Theorem 3.1
B. Combining Lemma B.2 and B.3
Lemma B.3. Let H be concept class with Littlestone dimension d and No 20(22) ln(1/8)/6) be appropriately chosen. For any adaptive adversary generating the sequence (11,81),.... (IT, UT) in the realizable setting, Algorithm 2 makes at most
(20(2) (log T + 1og(118) + log(1/6))
mistakes with probability
Proof. First by Theorem 2.5 and the union bound, it holds with probability 1 1 3/3 that during the execution each instance of Above Threshol,, the number of mistakes made by the algorithm is within - a; T + a + 1], where is the threshold assigned to the instance and a 8(I Tln (0)) In particular, if the instance was created with layer number s, the number of mistakes made during the execution is within
No. 16(In T + In(6T/3))
+
60
We use Fg to denote the above event.
Then by Theorem 2.6 and the union bound, it holds with probability that
8dIn(8d/6)
sup County, (h) County, (h)l S Eo
NEH
for every [d]. We use Eg denote this event.
Moreover, consider an execution of Threshhre that eventually halts by returning a, We know that the algorithm keeps outputting h, h during the execution, where h is the first element 1n(3T/3) and be the collection of i, such that lu(x;) A y/- By Lemma it holds with 3 /T conditioned on E₁ that [1 n I'l 2 k/2. Let E3 be the event that this holds for all instances of Threshold that terminates by returning T. By the union bound, we have Pr[E3] E1] 2 1 - 3/3.
of Lg. Let / C [N,/2] be an index set with size (during the execution of this probability
Let F, be the set consisting of all h E H that is consistent with the data points received up to round t. That is,
F, {h E H h is consistent with (I1, M1)......... (F1, 3- Let f, denote the round which S St, were created. Define (t) to be the set
(i E [N./2] S and S are consistent with f}
at the end of round f. For every E (0, 1,....,, d), let FA,, denote the following event: for every
Fr, either
Ki E (t.,)) SOA(SS, + SOA(S 2 M,
there exists some ho such that
Hi E (t.)) SOA(S = SDA(S = -holl 2 M..
where M2 = 128 2 6-2" N, 128 2- 6-2 2
Since Sf..... ........ S0 are initialized 0. it follows that (to) [No/2] and SOA(S2 SOA(S2) ($2) SDA(O) for all i [No Therefore, E4,0 happens with probability We next bound
'The original statement of basic composition [Dwork et al. 2006a is for static dataset only. In this work we actually use stronger versions of (basic and advanced) composition that work for adaptive inputs Lyu 2022
Vadhan and Wang 2021 Henzinger et al. 2025
29

---

the probability of 14, conditioned on Ej U Eg U Eg and E,,s. If we set No d.24.0 In(8//8) then
E0
8d 8d1n(8d/6) - 32 6.2 No 2 = M,/4.
E0 By Eg, for every ʃ E Fr, that satisfies the second property of E1,., we have County, (ha) 2 3M which implies ha Ly. Observe that from round t t, + 1 to t ts+1 only insert data points that are realizable by Fe.... it follows that (t((++1) = (ta) for all E Feets. Thus by Es, we have for all f E Fr,t1 that
Ki E (t((s+1) SOA(S + SOA( M,/2
we set k: = M. 128 2-6-2 No 2- 2 4 1l(37/3). Also, is easy to see from our algorithm
that [S/| < 2s for all i [N,] since we will at most insert one data point from the input and one from Update for every 8. Now we have fulfilled the conditions Lemma B.T Setting M M /2
M/4 (this requires 11 M,/8 8 I M,/4- 6, which can be satisfied by letting No 2 26.2 +d).
and r2 M /3344N++ 1) gives
(M/2 )
M
6N. 6N
128N s+1
M
512N
16384 2-11222 N3 2-2s
512No 2 (a+1)
128 2-
No 2 (=++1)
M
As result, the event Es,5+1 holds with probability
e(4d + 1)NN
d
2r M
2r
exp
exp
2d
9N
M,
M
21
(7No)
exp
exp
16
72
3842N3
++1
8NN
2048N
=1 (7No)
exp
26.2*45
+ exp
81
224.2*+
No
21 2exp
+ ddln(7No))
224-2
8
21
3d
conditioned on Ei U Ez U Es and E4,s as long as
2exp
224-2*+d + dlln(7No)
No
No 2 221.2++d (dhn+ddl (nd//33)
3d
which, by Lemma A.6, can be established by requiring
+o No 2 4 22 +d dln (224.2*+d. 2d + (ddh7
Let E, E1o U .... U ELd, we have Pr[E, E1 U E. U Esl 1 3/3.
Summarizing what have proved so far gives PriE U Eg Eg J Ex] 1- 3 for some
No O (20(2))
log(1 (og(1/0) 15)
(og(TT/B)
We now condition on E, E2 U Eg U Es and bound the number of mistakes. Note that the size of Ly at round t t, can be bounded by
N₂/2
26-2"
3M, M./4
128
30

---

for [d] and by 1 v 26.2" /128 for = 0. Hence, the number of mistakes before reaches is at most
16(In + In(6T/8)) +1)
26.2"
N₂ +
Eo
128
20(2)) (log T + 1og(1133 log(1/00) (1/6))
Once the value of reaches d, event Eg indicates that (ta) z Ma for all f Fra- Notice that for every i E (f((t,, the SDA makes at least mistakes on S and S.. Therefore, the property that the SOA makes at most d mistakes any realizable sequence implies that SOA(S SOA(S%) = f. Then by E2, we have La- This means we can make at most
Na 16(In T In(67/3)) +1)
26.2"
log(1/5) (1g(1/)))
60
128
mistakes after to- Combining the bounds yields the desired result.
C Proofs for Section 4.1
C.1 Proof of Theorem
Proof. The privacy guarantee directly follows from post-processing property of DP and the fact that we run B disjoint batches. Let E denote the event that all executions of B succeed, we have Pr[E] 2 1 T/D 3. In the rest the proof we condition on E. Note that under event E, the input sequence is always valid synthetic sequence. Thus, the algorithm won't fail.
Assume without loss of generality T (mod B). Consider the b-th batch and fix St. St...., S. Since A is proper, the utility guarantee of B gives (note that the error rate is 2a since we require B to output a sanitized dataset, see our discussion after Definition 2.7
E
Σ
The # vil
Σ
E f.AA
[T(()))) vil]
B iml
B+1
B++1
bB
(SAA(S))
Σ
[lf(x;)) + vol
B
(=(b-1)B++
6B
< B
B(aA((S)
Σ
T((())) vil
Bc
1=1
(
Let Pt be the probability that A(S makes mistake on the last element of S (note that p itself is random variable). Since we perform a random permutation over the synthetic data sequence ((a1-1))441 f/ 1)8+))..... (x/. Vb))). we have
6B Σ
E 1
P
E
Tf( + vil
B
(1-+1))++1
Summing over all batches yields
T
B T/B Σ
[he
(x+) + vil
<
p
2aT.
1=1
31

---

Let (h) be the number of mistakes made by h E H on S ST/B+1, Note that S
ST/B41
S
ST/B+1
are disjoint subsequences ((r1 ((11:1)).... ..., (x'r,, v/))). ) We thus have
B
T/B
T min Σ (x() # vil
T/B
B
E
E
Σ
min m, (h*)
E
b=1
t=1
t= b=1
T/B
Pj
min m((h") EE
$ B. R(T/B),
where the last line is due to Lemma 4.1 of [Cesa-Bianchi and Lugosi 2006 (see also Lemma 11 of [Gonen al. 2019]) and the regret bound of A. Again by the utility guarantee B have
E
min MEEN 1=1
Σ (x)) + vol
2 E
min EE
I (1/)) * vo1 - 2aT.
1=1
Hence, the overall expected regret can be bounded by
E
(xx) * vol
min
Σ Ilh² (x+) + vil
he EEW
B
T/B
T
S
P
min ETEH
Σ
1[h + 3/1
+ 4aT
<B R(T/B) + 4al.
Moreover, since every h, is produced by A, Algorithm 3 is also proper.
C.2 Proof of Corollary
Proof. By Theorem 4.2 and Lemma 2.8 there exists (c, -ddifferrent private (a, B)-sanitizer for Hllabel with sample complexity (d /dd//aa" For any B < T', this translates sanitizer with a (dd Vd () and 8
1/T2, Then by Theorem 4.1 and the regret bound of proper online learner [Hanneke et al.) 2021 1 Alon et al. [021]. we obtain private online learner with
expected regret Ö(VdTB Ta VeB). Choosing B éf /=) gives the desired result.
D Sanitization with Better Sample Complexity
In this section, we discuss how to reduce the sample complexity of the sanitizer in GGaazi et al. (0211b by a factor of 1/a. We achieve this improvement two steps: first refine the sample complexity of the private proper PAC learner of Ghazi et al. (002b)) then make it applicable in the framework of Bousquet et al. [2020].
D.1 Refined Sample Complexity for Proper PAC Learning
The proof in Ghazi et al. 2021b utilizes the uniform convergence result (aka agnostic generalization) ensure that the empirical error of every f F (F some hypothesis class whose VC dimension is bounded by the Littlestone dimension of the given concept class H)) is close to its generalization error. This indeed an overkill - their proof only requires this to hold for hypotheses with low emor. Therefore, one could replace the uniform convergence bound by the following relative uniform convergence results.
Lemma D.1 (Relative Uniform Convergence (Anthony and Bartlett 1999 Anthhny Shawe- Shawe-Taylor 1993). ) Suppose H. is concept class over X with VC dimension dy and P is distribution
32

---

X' x 1.. Let S be a dataset of size n. where every data point in S is drawn i.i.d. from P For any
0 X. I, we have
2en"
dv
Aum
Pr[Sh E errp(h))) (1 Aherrs(h) + S
exp
dv
4(A 11
and
2en
dv
-Apm
Pr(Sh E H. cr))(h) (1 (h) + 14] S
exp
dy
4(A 1)
Such modification leads to the following result, which saves factor of 1/a.
Theorem D.2 (Ghazi et al. 2021b). Slightly Strengthened), Let H be concept class with Littlestone dimension Then there exists an (s, -differrnnnl private proper (a, 3)-PAC learner for H. with sample complexity (d% /Ea).
D.2 Sanitization via Proper PAC Learning
We now demonstrate how to construct sanitizer using proper PAC learner based on the sequential- fooling framework of [Bousquet al. 2020). The framework can be described as sequential game played between generator and discriminator, where the discriminator holds dataset S and the generator wants obtain an accurate sanitization of S. At each round f, the generator proposes a distribution Pt. The generator wins the game if P. and Ps are within error a with respect to H. Otherwise, the discriminator returns some E such that [P(h) Ps(h)] > a. Bousquet et al. 2020 proved that the generator can always win the game within Ódd /a²) rounds. They also showed how to simulate the discriminator using a private proper agnostic learner. Putting the two pieces together yields an algorithm for sanitization. In our construction, we will use the same generator and modify the discriminator so that proper PAC learner can be directly employed.
We first leverage a technique from [i ct al. 2025) to construct a private agnostic empirical learner directly using private PAC learner without incurring a generalization cost of Ó(VCdim /a?). Lemma D.3. Suppose there is an (s, 8) diffferrentill private proper (a, -PCC learner for H with sample complexity m. Then there exists an (O(s), ((0))-differentallyy private proper (O(a), (())- agnostic empirical learner for H with sample complexity
dv log(1/a) + log(1/3)
O
where dy is the VC dimension of H.
Applying the above lemma to the learner in Theorem D.2 leads to the following private proper agnostic empirical learner.
Corollary D.4. Let H be a concept class with Littlesoone dimension d. Then there exist an (E, 8) ( differentially private proper (a.B)-agnostic empirical learner for H with sample complexity (d8 /ea).
We now prove Lemma D.3 Given a dataset of size n and an index set I C [n], we write S to may abuse
denote the collection containing elements from S with indices in I. For simplicity, notation and write diss h2) for labeled dataset S. This means we ignore the labels and only calculate the disagreement on the feature portion of S. We illustrate the conversion in Algorithm
The following claim states the privacy guarantee of Algorithm The proof is nearly identical the proof of Lemma 15 in [Li et al. 2025].
Claim D.5. Suppose is (1, 1,8) diiffeferettially private and 1/n S & S 0.1. Then Algorithm (O(e), (())) differrliill private.
Proof. Let S and S2 be two neighboring datasets and O any subset of outputs. Without loss gen- erality, we assume Si and Sn differ in their first element, i.e., S = ((x1.))) y1) (I2, U2), (Kig Vn)) and S2 = ((1i, v1), (æ2, y2),-. .... (In, vn)). Let B denote Algorithm For any 7 S [m] of size
m [En] and k E {1, 2). define
Pa (I) Pr( E O the sampled indexed set is 1].
33

---

Algorithm 4: Agnostic empirical learner
Global Parameter:
concept class H. parameter
Input: private empirical PAC learner A for H. private dataset 5 = ((11, V1),.......... (Ii, yn)) Sample [nx] of size [Z] [en] uniformly at random.
2 Initialize R = 0.
3 For every possible labeling in (s') add to R an arbitrary h E H. that is consistent with the labeling.
4 Define q(S, h) = min {diss- (h, f) + efrs
5 Choose hgg E R using the exponential mechanism with privacy parameter e, score function g. and sensitivity parameter A = 1/n.
Let D be the dataset constructed by relabeling St with hu-
7 Output A(D)
Since is sampled uniformly, we have
Pr(B(SA) E = (m) IEQ
Σ PM(1),
where Q= (1 [1]
Fix an index set I and consider two cases: 1 and 1 & I. of I, then B(S1) and ((52) will construct the same set R. For every h R, there is some Sh. H such that dissg (h, fb.) errs, (fr) 9(S h), then we have
(( h)
min fain(dis gd (h, f) errs,
FEH
I dissy (h, fn) + errs, (fh)
s disg; (h, fú.) + crrs, (fr) + 1/n
S (S1 h) 1/n.
By symmetry, we also have (S1, h) (S2 h) 1 for every h E H. Let (x)h) denote event that
the hypothesis ho chosen by the exponential mechanism on S& h. It then follows by Lemma A.23 that
(r[E S ef Pr[E2(h)]
for any h. The post-processing property of DP immediately implics
(1) p2()).
Now suppose 1 I. Fix some i & I and let J = (1 u have
[i} and K = INJ. Since E I, we
s n = SK = S
whose size is exactly |K| m Let R and R be the set R constructed from S and Sy. Pick finite set U C H. such that for every labeling of S = S there is exactly one E U consistent with this labeling. For each h U, define
((()) (M/ Rf disgæ (h₂ 0}
and
(h) = {h' E Ry dissg (I) = 0).
Since the label set is {0, 1}. have < (h)),, h2 Ps (f), let ql (S1, be the score function calculated on S₁ with sampled index set and (S2 h2) that S2 with sampled index set J. Since there is some fh, H such that diss! (h1, fr,) errs, (fr,) = (((,,, we have
2. For any h E (f) and
r' (S2, b2) min (dissg (h2, f) + errs, (f)
disgy (h2, fh., ) errs, (fr.)
dissi (h1, fw.) 1/m errs, (fr.) 1/n
< (S,, h1) + 1/n + 1/m.
34

---

where the third line is because h1 and h2 agree on nigg which has size m - 1. Since (1/n)/2A
1/2 and (1/m)/2A n/2m - 1/2e, we have
exp(-Eq' (S2. /2) 2 (epp-=Eq'(0 (S) h4) + +
2 exp( expp (S, h2)/24)))) (05
2 exp( (S), /2)/ exp(-11),
where in the last inequality is because - 1. By symmetry, we also have
exp(-eq' (Si, /1)/2a)=>>) 2 exp(-eq/ (5 h2) exp(-1).
Then the fact that 1 | P2 - 2 gives
Σ
exp(-sq' (S), h1 /22) (2)
Σ
(x2 ha)/2A) exp(-1).
(N)
Summing over all 11 R2 yields
Σ
exp(-Eq' (Si, f)/2
Σ E hEU (A)
exp(-eq (sp(-ed(SS1,h1))/ (51,
SER
expl-eg'(Snn h2)/ exp(-1)
NEV
Σ
exp(- (S2, f)/2A).
2e
SER
Let (h1) be the dataset obtained by relabeling Sf with h1 and D2 (h2) be the one obtained by relabeling Sy with h2. Recall that hi and h2 agree on S nSS. which has size m n-1 1. We know that (h2) and D2 (hz) are neighboring datasets. Let E (h1) be the event of choosing hı when running on S1 with sampled index set and Eg (h2) be the event of choosing h2 when running on S2 with sampled index set J. Since A is (1, diffferreel private, we have
Pr[E] (h1) Pr[AA(D((()) (h,)) E E
expl-sy'(S,, (Si, h1) /2A)
EyENS (S Pr[[(((((h)) E OJ
(S,,
22e² E EjERy
(ePr(A(D)((a)) (h2)) E E
-2 Pr(Ey (h2)) (e (ePr[A(D)) (h2)) E 0) + 8).
Then we have the following relation between pi (1) and p2()):
(1( = Σ Σ
Pr(E)(hi) (h)) E
NEU h (1)
< Σ
Σ
2e 20 ( (eP) c +8)
heU hEEP (N)
= 46 p2)) + 4628.
Note that ErEquEr Eiepnly P2((1 (1)) U (i)) counts every p2(J) (J E Q and 1 $ J) exactly
|7] times. Therefore, have
Σ (1(
1
Σ
Σ
PI(I)
n - m
IEQUEI
rEQUle sE(n]{]
< Σ IEQ:IET LE[N]T/
Σ
(4 ( + 4620)
m
Σ
(2() + 442
n - m
JEQ-1EJ
(n-1) m 1
< 24
Σ
P2(J) 4628.
JEQ:14J
35

---

where the last line is due to
n2
(J
n m
n2
m
m
m
1
and
2sn
<
62
m
sm
2en
long as en and S 1/3. Finally, we have
Pr(B(S)) 0]
1
Σ
pi(1)
E PI(1)
Q1
TEQ:1ES
IEQAEI
e
Σ
P2( + 24
E
p2(J) + 4628.
(n-1)
m (m-1)
m
IEQ:11
JEQUEI
$ (e 2
(T) + 4e25 m
n
IEQ
Ole) Pr(B(S2) 0] + 0(5))
The utility guarantee of Algorithm is shown in the following claim.
Claim D.6. Suppose A is proper (a, 3)CPAC empirical learner for H. with sample complexity m = [En]. Then Algorithm 4 a proper (O(a), (3)) -agnostic empirical learner with sample complexity long where dy is the VC dimension of other words.
C(dy log(1/a) + log(1 ( a for some constant C and 2 1/E,
n = 0 m
dy log 1/aa) log(1/3)
EA
Proof. By Sauer's Lemma, we have [R] < ddn Then by Lemma A.23 with probability at least 1 - 3 the exponential mechanism chooses some ho such that
2 me
q(S,ho) min (S, In [n(()//)) I
min (S,,))s)) +
heRl
as long as
n 2 (In(1/B) + dv in(em/dy))
Since [en] < 2en, by Lemma A.6 the above holds if
m C dy log(1/a) + log (1/B)
a
argmin,ee There exists some E R such that dissr (h* h) = O. For such h, we have q(S, h) errs(h*). This implies q(S, ho) S crrs(h") + a, or equivalently, disgr (ho, fo) + errs(fo) I crrs(h") for some fo E H.
for some constant Ct Let h+
Since disgr (ho, disgr (b) < a because (rr)(fo) 2 errs(h*). Then by Lemma A.7 and the fact that the Chernoff bound more concentrated for sampling without replacement Hoeffding 1963 with
non-negative, we have errs(fo) errs(h*) a. Also. we have
probability at least 1 - B we have
disgr (h1, h2) & a = diss (h1, h2)) S 2a
simultaneously holds for all h, by E as long as
m C2 dy log (gg(1/)) + log log(1/3) (1/3)
a
36

---

for some constant C2. As a consequence, we have diss(ho, fo) - 2a.
Since D is labeled by has with probability 1 1 39 the output y = A(D) satisfies that disgr (g, hn) S Moreover, we have E H since A is proper. Hence, Algorithm is proper and diss (9, ha) S 2o.
By the triangle inequality and the union bound, we have
errs(g) s errs(fo) + diss(fo.g)
S errs(h") + a + diss ho) + diss .))
< errs(h") + 5a
with probability at least 33.
By Lemma A.10 there is (1, -(ff//))diifereettaal private proper (a. 5) PAC empirical learner A for H. with sample complexity O ( Then by Claim D.5| Algorithm is
Proof of Lemma D.3
(O(e), (6)) diff)rrrrreltlllllly private. Moreover, by Claim D.6 Algorithm 4 is proper (O(a), (3))-
agnostic empirical learner with sample complexity
m (m+ dv log + log (og(1
O
EQ
We now show how to construct the discriminator using proper agnostic empirical learner in the following lemma.
Lemma D.7. Given a dataset
and a public distribution Pt. Suppose for any F S HU(1 there is an (s/3, 8) differrentially private proper (a/10,3/3))a0 a/3)-ooostii empirical learner for F with sample complexity n and
C --C_m In(1/a3)
EQ
for some constant C. Then there exists an (e, (diffeeifertttliillll privale algorithm such that with probability B:
If it outputs some h E HU -1-1) H. then (h(h) Pi(h) 2 a/2.
if outputs "WIN" then [P)(h) P.(h) S for all H.
Proof. Let k = [10/a] and define
F; (h E HU -H) P.(h) E [(i - 1)/k,i/k]
for all i E [k). Construct score function ((S = - (maxNEF, Ps(A)) i/k). is easy to verify
that the sensitivity of is 1/n. By Lemma A.23 running the exponential mechanism with privacy parameter e/3 returns some E [k] such that ((,,)) & minseps q(S, i) + 2l(33//)/er with
probability 1 - 3/3. This implies
max Ps(h) - j/k 2 max hEF,
max Ps(h) - i/k - aa110 REF.
long
20 In (60/a3)
Z
60
We then construct dataset 5' by labeling all data points in S with and run the proper agnostic empirical learner for F, on S' find some hy E F, such that
errs (ho) S min errs (h) + a/10 kEF,
with probability 1 3/3. This equivalent Psshhn) 2 maxkeF, Pssh)) - a/10. We output ho Ps + X - j/k 2 3a/5 and output "WIN" otherwise, where X ~ Lap(3/s). Note that this step (e/3, 0)-differentially private, and we have
Pr[[X| a/10 > Pr[[X| < (ln(3/P)/en) -//3
37

---

given that
30 (3/3))
n
Ea
The privacy guarantee directly follows from basic composition. By the union bound, with probability 1 8. we output ho then
(ho)) 2 j/k X + 3a/5 2 Po(ho) a0110 + 3a/5 2 Po(ho) + aa/2.
Otherwise, for any i E [k] and h E F; we have
Ps(h) P.(h) - Ps(h) -i-
max Ps(f) - -i/k) 1/k: fEF:
max Ps(f) j/k + a + +// teF;
S Ps(ho) a/100 +1/h
3a/5- X 1/10
< 00//5t//1000/1000/00000000
S a.
The desired conclusion holds since H HU H) is symmetric.
The property of the generator used in [Bousquet et al. 2020 is described in the following lemma.
Lemma D.8 ([Bousquet al., 2020). ). Let H be a concept class with dual Littlestone dimension d'.
Suppose there is discriminator such that:
If it outputs some & E HU - H) then (h) P.(h) 2 a/2.
if oulputs "WIN" then Pp) P.(h)) S for all h H.
( az log
Then there exists a generator that makes the discriminator respond "WIN" within rounds.
Following the proof strategy of (Ghazi et al. 2021b), which strengthens the proof of [Bousquet et al. 2020 by applying the advanced composition theorem, are able to show Theorem 4.2
Proof of Theorem 4.2
We have Ldim (H U (1 - H() = Od) and Ldim (H - 70) = d' (see,
e.g.. Alon al. 2020 and [Bousquet et al. 2020 ). By Corollary D.4 for any F HU H)
there is an (&" 6773, 0' diifferrrenially private proper (a/10, 8' /3/3)-agnostic empirical learner for F with
sample complexity O(d" /E'a). Then we can use Lemma D.7 to construct an (5', -e".8")-iiffcrentiaal private discriminator, which with probability 1-3' either outputs "WIN" (hence, (Ps(h))PP:(H) < for all h H) some h E H U H) such that (h) (h) a/2.. Now the generator in Lemma D.8 By setting 3 = 3/T, we know that with probability - 3 the generator produces some Pt such that (h) - (h)) < for all h E H. To ensure the entire process is (c, -)dfferrrent private, by advanced composition (Dwork al. 2010b] it suffices
8' = 5/2T and e'
2 2T ln(2/8)
Hence, the overall sample complexity is Ō /T/a) O(d /c02)
E Online Learning via Privately Constructing Experts
E.1 Realizable Sanitization
We first define the notion of realizable sanitization.
38

---

Definition E.1 (Realizable Sanitization). We say an algorithm is an (a. -reallzbae sanitizer for H with imput size n if it takes imput a dataset S d and outputs function Est {0, 1 such that with probability B, for any h H:
If (s(h) 2 then Est(h) = 1.
If (h) then Est(h) O.
turns out that we can again leverage private proper agnostic empirical learners to construct a private realizable sanitizer. The following lemma shows that construct discriminator.
Lemma E.2. Given a private dataset S E X and a public function Qt H - {0,1}- Suppose for any F S H there is an (/4.8/2)-differts learner for F with sample complexity n and
private proper (a:/9, B -agnostic empirical
36 (4/3) n n
EO
Then there exists an (e, ddiiferreet private algorithm such that with probability 1 B:
if outputs (h, 0) for some H then
(h) & 4a/9 and Qc(h) 1.
If it outputs (h, for some h H then
(h( 2 50/9 and Qr(h) 0.
if oulputs "WIN" then for all h E Hi:
Ps(h) 2 = Q.(h) =1 and Ps(h) = 0 (h) =0
Proof. Let Ho = E H: Q 0} and So be the dataset obtained by labeling all data in S with private proper (a/9, / 4))agnoottic empirical learner for Ho on Sg and obtain hy E H. With probability -//4 4 we have
1. We run (f/A4.//2)-iifeeremnallll
crts, (ho) S min crrs, (h) + a/9. heHo
This is equivalent (hoh)) 2 maxREH. (h) 20/3, where Xo ~ Lap(4/sm) Note that this step is (e/4, 0)-differrentiall private, and we have
We output (ho. 1) and exit Ps + Xo 2
Xu| I a/9) 2 X < 4 ln44/))/en) 2 3/4.
we do not exit, then similarly let H41 = {h E H: Q+(h) = 1} and S1 be the dataset obtained by labeling all data in S with We run an (e/4, 8/)d/ed)ifffr private proper (a/9,994))aagnosti)i 4)agnosst empirical learner for Hi on S and obtain /1 H. With probability 1 - B/4 we have
errs, (11) S min errs, (h) + a/9.
NEW,
This is equivalent (s) minneR, Ps(h) + a/9. We output (h, 0) if Ps 5 where X; ~ Lap(4/en). Otherwise we output "WIN". Also, we have Pr[[X, S 2-
The privacy guarantee directly follows from basic composition. By the union bound, with probability 1 - 3 we have
(s(ho) 2 2a/3 - Xo 2 2a/3 a/9 5a/9
if we output (hg, 1). If we instead output (h1, 0), then
Ps(h S a/3 X, - a/3 + a/9 = 4a/9. Otherwise if we output "WIN", we have
(ssh)
< Ph())) + a < 2n/3 - +//9
< 2
< a
39

---

for all h E Ho and
Ps(h) 2 ()(11) a/9 a/ X1 a 2 a/ a/9 a/9 >
for all h E Hi as desired.
Given concept class X, define hypothesis class
Xm.a/2 {(1((11.... Tm) 2m
over H. where every predicate (21 (#1,..., Tmm) am / is defined
(#),..., Tm) =
h(x))) 2
a
2
The right-hand side can be seen boolean function of l(.1)....., h(Tm). Then Lemma A.18 provides an upper bound on the Littlestone dimension of Xm.o/2-
Claim E.3. Let be a concept class over X with dual Littlestone dimension d², Then the Littlestone dimension of X am/2 /2 is at most Ommd" logm).
can be shown that for any dataset S, the class Xm.a/2 contains a good realizable sanitization of as long as is sufficiently large.
Lemma E.4. Let H. be concept class over X with VC dimension dy. Set m = C'yy In(1/a)/ where C is some universal constant. For any dataset S over X, there exists (I1,..., E nm such that for all h H
If Ps(h) 2 5///9 then +. E M((;)) 2 ax/2.
. Ps(h) < 4a/9 then E h(z;) < ca/2.
Proof. Let Fı, Zim be i...d. drawn from Ps. By Lemma A.7 (or Lemma D.1 the desired property holds with probability 1/2. Hence there exists realization with the property.
Given the above result, one obtain a realizable sanitization by using any online learner (e.g., the SOA) to interact with the discriminator from Lemma E.2 This leads to the following theorem.
Theorem E.5. Let be concept class over with Littlestone dimension dual Littlestone d', and VC dimension dy. Then there exists an (e, -diffferreelllllly private (o,, -..--reellzzble sanitizer for H with sample complexity
ò σ V'vd'dy
L..
Proof. Set m as in Lemma E.4 Let D the Littlestone dimension of Xm,o and = D By Claim E.3
have 7 mm log m)). Run sequential game using the SOA for Xm,a/2 a/2 as the generator and the algorithm from Lemma E.2 with privacy parameter (E', 8') and success probability 1 1-B/T as the discriminator. By the union bound, with probability - 3 the discriminator succeeds for all rounds. Condition this event, if the discriminator outputs "WIN" some round t then can simply output Est = Q: and exit.
Thus, it suffices to prove that the discriminator always outputs "WIN" at some round under the above event. Suppose, for the sake contradiction, that produces a sequence ((1,, 11.71,, ")),..,,, (hT,, yr)). Then we have Q (he) * ye for all /. [T]. By Lemma E.4 there exists some = (#1, Fm) Xm,a/2 such that for all h E H:
. If (s) 5a/9 then Q(h) 1.
40

---

If (s) I 4a/9 then Q(h) 0.
Consequently, we have (hh,) yr for all E [T]. This means the entire sequence is realizable by o/. However, the SOA makes T = D + mistakes, a contradiction.
In order ensure the entire process is (s, ( diffferrentill private, by advanced composition [worrk
et al. 2010b], it suffices to set
8' = 6/2T and e'
2 2 ln(/6)
We now analyze the sample complexity. It depends on the sample complexity the learner used in Lemma E.2 Employing the one in Corollary re4russ in sample complexity of
d VT
d d
E'Or
80
80..
E.2
Constructing Experts
We first extends our realizable sanitizer to the sequential setting by the binary mechanism (Dwork ct al. 2010a| Chan et al., 2011], which is based on the following fact.
Fact E.6. Let > 1 be the time horizon. There exists set I S {(1,)) 1,r E (T] and S r) and universal constant C such that:
1
For every E [T], we have [((,r) E [
For any L, [T] and S there exists ==t <... tu < tut1 R++ for some u S C'nT such that (tr, t+41 E for every i E [u].
We describe the sequential realizable sanitizer in Algorithm 5 Note that it actually sanitizes larger hypothesis class Hm,1/2 + H. where
1m.1/2 = ((h1, hm E 7m)
is a hypothesis class over X' and the predicate (h1,..., hm) is defined as
1
(hi...., Am (z) =
(
2
2=1
Since the right-hand side the above is a boolean function and the operation ① also boolean function, the following claim then follows from Lemma A. and A9
Claim E.7. Let H be a concept class with Littlestone dimension d, dual Littlestone dimension d', and VC dimension dy. Then 1/m,1/2 dimension (mmdd log m)), and VC dimension O(mdy log.).
1/2 @ H has Littlestone dimension Omd m), dual Littlestone
In Algorithm the algorithm B is indeed series of realizable sanitizers with varying eters (n) for different input sizes n because we have to sanitize sequences with different lengths. Furthermore, assume for simplicity that an (a< -)-realizable sanitizer directly outputs syn- thetic dataset of size n rather than an estimation. This is done by first computing Est, then finding a dataset S" of size such that Ps. (f) > O for all f E Hm,1/2 @ H with Est(f) = 1. Note that with probability 1 B, the private dataset S satisfies this property and hence such S' exists. The lemma below summarizes the privacy and utility properties of Algorithm 5
param-
Lemma E.8. Let be an (c, -)diffferentially private (a(n), -rrreiziz sanitizer for Hm. ① H. with input size n and C the constant in Fact E.6 Then Algorithm is (C' e, C ChiT T 8)-
differentially private. Moreover, let A max, [T] (n).)). Then with probability 1 - CT3. for all
1 1 1 S we have
(--1+1)Ps... (f) ChTA Ps.. (f)
for all f Hm,1122 ② H. where St, (I))..,,,,).
41

---

Proof. The privacy guarantee directly follows from Fact E.6 and basic composition. Since | & CT. with probability least B all executions B succeed. For any 1 S < T, have
and
Si.r = (5) 12 St t--
for some 1 = 1 < ... < la < lat1
+ and u v C' 7.
Then for any ʃ E 1/ 1/2 + H such that (r 1+ 1)Ps) (1) 2 ClT there is some E [u]
such that (li+1 - 4:) (s. (f) 2 (li+1 (i)a(li+1 (2). This implies Psi Pa (
(since running B on St,4411-1 gives Est ( = 1) and hence Pst (f) > 0.
Algorithm 5: Sanitization for intervals
Global Parameter: time horizon T, hypothesis class Hm,1/2 2 + H Input: realizable sanitizer B for Hmm./2 @ H. data sequence (I1,..., ,T)
Let be the set in Fact E.6
2 for f 1....... T do
for = 1,1 1, 1,...:1. do
if (1, E / then
Si, - B(rt.....200
else
Find = < ... < tu tut1 t + for some C'In such that
(t;, tit1 - 1) E for every i E [u] as Fact E.6
Si (5) 12 -.... 1.-1)
end
end
end
We now present our construction experts. As illustrated in Algorithm 6 each expert indexed by .1,.... Ji, .. such that 1 S S i1 < j2 S i2 < ... jM I iM S T. The expert will keep the output unchanged from round i + 1 to round i4+1. After round ig-1, it changes the output by feeding sanitized data point z/,, to the online learner A and forcing A to make mistake. Note that for the expert, it suffices to receive (2% 11 Lig+1) at round ig+1 rather than in a real-time manner.
Algorithm 6: Expert
Global Parameter: time horizon T, concept class 7
Input: online learner A for H. indices .,....,4. iM, Ji...- jM, data sequence x-0 0.
1
S
2 for f , do
Output he A(S).
4
if in for some K E [M] then
SS S (S, (a') Jx. (()))a
end
7 end
As we discussed in Section 4.2 the structure of the classifiers outputted by the online learner AA cannot be too complex. Otherwise we have to sanitize huge hypothesis class and this may lead to an unacceptable error rate. Therefore, we exploit the online learner proposed by Hanneke et al. [20TT] whose output hypothesis each round sparse majority of concepts in H (i.e., Hm,,1/ for some m).
Lemma E.9 (Hanneke et al. 2021)). Let H be a concept class with Liulestone dimension d and dual VC dimension diy. There exists realizable online learner whose output hypothesis at each round is always in Hm,,1/ and has a mistake bound of M = Odd), where m O.
Theorem E.10. Let H be concept class with Liulestone dimension d, dual Littlesione dimension d', VC dimension dy, and dual VC dimension dtc Then there exists an (e, -differrentllll private algorithm that receives adaptively generated data sequence (I1....,IT) and constructs a set
42

---

Algorithm 7: Constructing experts
Global Parameter: time horizon T, concept class H. hypothesis class Hm,1/2
Input: online learner A for H with output in 1/2.122 data sequence (#1,....
S ji < in < S i2 < .... < jM Sim S T) 2 Initialize Expert(11 1....., J1. (MM for every (f1s...,, (M. E
J &- (MM....,,M.))............
3 Let B be Algorithm 5
4 for == 1...., T do
Feed 2, to B and receive 1...... S from B. foreach (d1,..., f., J............................... jM) E J do from Expert(i)...... iM .iii..............
Receive h2 h.
7
it't = ik for some & [M] then Feed S 141,ig to Ex.. M. Ji.... :.......))) .MM) (define in = 0)-
10
end
11
end
12 end
N ((TO o(TToa) experts such that with probability at least B. for any h E H. there exists an expert with oulpul (hi,..., hrr) such that
T
(1ee))) # h(z)) = -
(d' = 14/3
dv)
22/3
Hm.1/2 ① H has Littlestone dimension D O(md log dual Littlestone dimension D* O(md log m), and VC dimension Dv = O(mdy log m). By Theorem E.5 there exists an In/ClIT, ( pri- vate realliiiabe sanitizer for 1/2 @ H with input size where
Proof. Write Sir (z), (
).) (.,,...,3.))) By Claim E.7
D DDVD*DV
2/3
a<n) =
EN
Then by Lemma E.8 running Algorithm 5 with this sanitizer is (c, ddfieeriffr private and with probability we have
1+ 1)Ps, (f) C'TAA= Psp (f) >
for 1 rr < T and f Hm,,12 + H. where is the constant in Fact End
D DDVDD-Dv D
2/3
A max na(n) = 1/3 nE(T)
Set and M as in Lemma E.9 and use the online learner to construct Expert (Algorithm 6). Running Algorithm 7 gives a set of experts with size N = [J| O(TM) = O(T)()). Since the algorithm can be seen as post-processing of the output of Algorithm [5] The overall algorithm is also (e, 8) dif--)dffrreniillly private. Now suppose there exists some h E H such that
Σ mp daa (xt) + h(xx)] > [C'ITA] M
for every (i....., iM, J1, JM) E J. Note that Expert(11,.... .ill...,,MMMb. ....i,...,jai only changes its output after round t i,, then there is some in such that
g
mhe ia de wi (xx) h(x))) [CITTA] 2 ClnTA
for every (i, .2.... iM In. ... JM) J. This implies Ps (f 0 for
f = h dann Srm-fr =... h1 far.....
43

---

Let 54 = (2/ There is some J E [8'] such that
AM Sida. (x)z) h(rz;)) "
By induction, we can similarly identify 122 12.2 ................................ J's such that
I
M ts (xx) + h(xx)) = [C'TA]]
and
S (xz) * h( )
for every & E [M]. This means until round = i's. the online learner A used by
Expert(i)) Ji:-...--. :.......JMM.. JMM) received sequence of length M that is labeled by h and made a mistake on every data point. However, by our assumption, we have
Fi Jir (ae) Mxx))) O.
T
This contradicts Lemma that
E.9 Hence, for h E H. there exists (b1..... i .......MM' such
1
M J du (x+) + h(xx)]
O(log TAM)
1=1
Ö 1/33 mmd /
2/3
d
Ô 71/3 (di (d V
2/3
c
E,3 Incorporating Private OPE
Now we can run any private OPE algorithm over the experts constructed in Theorem E.10 We use
the following results from (Jain and Thakurta 2014) and [Asi al., 2024 for adaptive and oblivious adversaries, respectively.
Theorem E.11 ([Jain and Thakurta, 2014). ) For the OPE problem with experts, there exists an (s, 8) diiffereettllll private algorithm with an expected regret of
T log(L/))) log N
E
against any adaptive adversary. Theorem E.12 ([Asi al. 2024 ). For the OPE problem with N experts, there exists an (s, 6)- differentially private algorithm with an expected regret of
T/3 log N log (Tg(T/8)
/Tlog N
2/3
against any oblivious adversary.
Putting the above results and Theorem
E. 10 together yields the following regret bounds.
Corollary E.13. Let be concept class with Littlestone dimension d, dual Littlestone dimension d', VC dimension dy, and dual VC dimension di, Then there exists an (E, d)ffiffrrenttlllly private online learner for with an expected regret of
V (log(118)ul) T
+ + 1// 14/3 dv 1133
22/3
E
44

---

against any adaptive adversary. Moreover, if the adversary is oblivious, then there exists an (c, 6)- differentially private learner for H. with an expected regret of
o (V + +0 (T1/3 (d)))44/d dv )1/3
2/13
45


Reviews:
[{"review_id": "D5AZ8Iwmpm", "reviewer": "Reviewer_NrgB", "summary": "This work studies mistake/regret bounds for private online learning against adaptive adversaries. They improve over existing $O(\\sqrt{T})$ mistake bounds for private realizable online learning of finite Littlestone classes against adaptive adversaries and obtain $\\tilde{O}(\\sqrt{T})$ regret bounds for private agnostic online learning of finite Littlestone classes against adaptive adversaries.", "questions": "See notes above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper makes a significant contribution to understanding mistake/regret bounds for private online learning against adaptive adversaries. While the main algorithmic idea is structurally similar to that of Golowich and Livni, there are notable technical obstacles to improving their mistake bounds against adaptive adversaries, which this work overcomes. \n\nI unfortunately found this paper hard to read for a few reasons. To the author’s credit, they give a summary of of the online learning of Golowich and Livni and explain why it is insufficient for achieving the desired $O(\\log T)$ mistake bounds, but I don’t know how helpful this summary would be for those who are not already familiar with the algorithm. More importantly, the reader has to do some digging to find a formal theorem statement for the algorithm in Section 3, and then more digging to find the setting of parameter $N_0$, which I think is helpful for the reader to know while reading the pseudocode for Algorithm 2. It would be good to have a theorem statement in Section 3 with the parameters necessary for privacy and the stated mistake bounds specified. \n\nSome minor notes/typos: \n\nIn abstract - “each time step a hypothesis”\n\nTheorem 2.6 - “pirvate histogram”\n\n“incurring a mistake bound scales”\n\nAlgorithm 2 - “failuare” \n\nI think there’s a duplication issue with the citation for GGKM “Sample Efficient Proper PAC Learning with Approximate Differential Privacy”", "was_revised": true, "final_justification": "I have a positive appraisal of the paper and the authors addressed my concerns with presentation by committing to update the paper to improve clarity.", "rebuttal": "We thank the reviewer for the constructive comments and provide our detailed responses below.\n\n> they give a summary of the online learning of Golowich and Livni and explain why it is insufficient for achieving the desired $O(\\log T)$ mistake bounds, but I don’t know how helpful this summary would be for those who are not already familiar with the algorithm.\n\nWe include a description of Golowich and Livni's algorithm because our work builds upon their framework (specifically, constructing tournament examples). A detailed explanation will help clarify how and why our algorithm works against an adaptive adversary. We will revise the presentation to enhance accessibility for non-experts.\n\n> It would be good to have a theorem statement in Section 3 with the parameters necessary for privacy and the stated mistake bounds specified.\n\nThank you for your suggestion. We will include a formal theorem stating the privacy/utility guarantee of our algorithm and the choice of parameter $N_0$. \n\n> Some minor notes/typos:\n\nThank you for identifying the typos. We will correct them in the revision."}, {"review_id": "SPhCpPxmDc", "reviewer": "Reviewer_2ZzJ", "summary": "This submission studies differentially private online learning of Littlestone classes against an adaptive adversary. It builds on work of Golowich and Livni, who previously showed that classes with finite Littlestone dimension can be learned with mistake bound $O(\\log T)$ against an oblivious adversary, and with mistake bound $O(\\sqrt{T})$ against an adaptive adversary. This paper improves these results in two directions. First, it shows that in the realizable setting considered by Golowich and Livni, Littlestone classes can be learned with mistake bound $O(\\log T)$ against an adaptive adversary. Second, in the agnostic setting with an adaptive adversary, such classes can be learned with regret $O(\\sqrt{T})$.\n\nThe paper's realizable learner builds on the strategy of Golowich and Livni, but introduces two main refinements to address how their probabilistic analysis breaks in the presence of an adaptive adversary. The first idea is to apply lazy updates to ensure independence between examples revealed and the randomness used in their permutation argument. The second is to use uniform convergence to ensure accurate estimation for all functions in the target class, rather than just the ground truth labeling function.\n\nIn the agnostic setting, it provides two different algorithms that reduce private online learning to sanitization (a.k.a. private synthetic data generation). The first is a simple proper learner (albeit with suboptimal regret) that breaks the time horizon into batches, applies a sanitizer to each batch to produce synthetic examples, and runs a non-private online learner on the synthetic data. The second is an improper learner with improved regret that simulates the experts algorithm, evaluating experts using sanitization. These online learners can then be instantiated using the known private sanitizer of Ghazi et al. for Littlestone classes.", "questions": "* How close to proper can the algorithm handling the realizable case be made? E.g., by replacing SOA hypotheses with Hanneke-Livni-Moran's construction?\n\n* I understand you're space-constrained, but seeing as Section 4.2 reflects most of the paper's algorithmic novelty, I would have liked to have seen a more detailed description of that algorithm in the main body of the paper in place of the algorithm described in Section 3.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "(+) Resolves the main open questions left by Golowich and Livni. Note that there was no reason to believe a priori that the best achievable mistake bound/regret of DP online learning against an adaptive adversary should coincide with that of an oblivious adversary; indeed, there are related settings in which there is a separation.\n\n(+) The algorithms and analyses in Section 4 introduce some nice conceptual ideas that could be useful more generally.\n\n(-) Handling the realizable case requires overcoming some technical challenges from prior work, but is otherwise relatively incremental. This isn't necessarily a strength or a weakness, but the paper's technical contributions don't have that much to do with understanding the combinatorial structure of Littlestone classes, and more to do with developing and analyzing online learners.", "was_revised": true, "final_justification": "This is a solid submission and the authors convincingly addressed questions and comments raised in the initial reviews.", "rebuttal": "We thank the reviewer for the constructive comments and provide our detailed responses below.\n\n> How close to proper can the algorithm handling the realizable case be made? E.g., by replacing SOA hypotheses with Hanneke-Livni-Moran's construction?\n\nBy replacing the SOA with Hanneke-Livni-Moran's construction, we can obtain a learner whose output is always a majority vote of $O(d_V^\\star)$ hypotheses from the given class, where $d_V^\\star$ is the dual VC dimension.\n\nMore generally, the output space of our algorithm is exactly the output space of the deterministic online learner it invokes. Thus, how close to proper the algorithm can be made depends on how close to proper a deterministic online learner can be made. For classes that can be properly learned by a deterministic online learner (e.g., thresholds over a finite domain), the resulting private online learner is also proper. However, there are some classes that cannot be properly learned by a deterministic online learner (e.g., point functions). For these classes, our algorithm (Algorithm 2) is improper.\n\nAdditionally, our first algorithm for the agnostic setting (Algorithm 3) can also yield a proper learner. Though it works for all Littlestone classes, it incurs a large regret ($T^{3/4}$). We believe this can be improved and leave it as future work.\n\nWe will include the above discussion in the revision.\n\n> I understand you're space-constrained, but seeing as Section 4.2 reflects most of the paper's algorithmic novelty, I would have liked to have seen a more detailed description of that algorithm in the main body of the paper in place of the algorithm described in Section 3.\n\nThank you for your suggestion. We will allocate more space for Section 4.2 and provide a detailed description of our agnostic learner in the revision to better highlight our algorithmic contributions."}, {"review_id": "JJs5GZ2FIq", "reviewer": "Reviewer_9xHS", "summary": "This paper addresses private online learning in the adaptive setting, where an adversary can choose inputs based on the learner's previous responses. The authors achieve two main results that improve upon existing mistake bounds.\n1) Realizable Setting: The authors provide an algorithm with an O_d(log(T)) mistake bound for learning any concept class with Littlestone dimension d, which closes the gap to the known lower bound. Their approach builds on Golowich and Livni (2021) but introduces a key innovation: instead of releasing updates at every timestep (which accumulates privacy costs), they use \"lazy updates\" that defer computation until necessary, followed by random permutation to maintain the privacy analysis structure.\n2) Agnostic Setting: The authors develop a new algorithm achieving an O_d(√(T)) mistake bound. Their approach first constructs a private proper learner, then applies sanitization techniques for generic Littlestone classes from Ghazi et al. (2021) to improve the regret bound, though this results in an improper learner.", "questions": "Can you explain why in Algorithm 2, you don’t need to reinitialize SOA after a lazy update?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: \nThe results are foundational in our understanding of private online learning in the adaptive setting and improve upon previous works in this area by giving better upper bounds in the realizable setting and new results in the agnostic setting. \n\nWeaknesses: \nThe explanations in Sections 3 and 4 lack sufficient clarity and detail, which diminishes the correctness of the proposed techniques. The authors would benefit from reallocating space from the extensive Preliminaries section to provide a more detailed explanation of Algorithm 2 and its different components.\nWhile I understand the high-level approach of addressing the √(T) composition cost at each timestep through lazy updates, several technical concerns remain unaddressed. In the adaptive setting, don’t you have to re-initialize the SOA algorithm after every lazy update? Otherwise, the shared randomness across lazy updates could introduce correlations between historical predictions and current outputs, potentially creating exploitable patterns for adversaries.\nThis concern suggests that the privacy analysis extends beyond straightforward composition arguments and involves more nuanced considerations. However, Section 3 does not appear to address these subtleties, leaving important questions about their solution unresolved.", "was_revised": true, "final_justification": "The rebuttal has clarified my initial doubts, and provided the authors implement the suggested changes in their final version, I'm changing my original score to be more positive.", "rebuttal": "We thank the reviewer for the constructive comments and provide our detailed responses below.\n\n> The authors would benefit from reallocating space from the extensive Preliminaries section to provide a more detailed explanation of Algorithm 2 and its different components. \n\nThank you for your suggestion, we will elaborate on the details of Algorithm 2 to better explain it in Section 3 in the revision.\n\n> don’t you have to re-initialize the SOA algorithm after every lazy update?\n\nWe do not reinitialize the SOA. During the update, every $S_{i}^{s+1}$ is obtained by appending an example to some $S_{j}^s$ (as seen in line 7 of Algorithm 1). Hence, $SOA(S_{i}^{s+1})$ can be seen as feeding a new example to $SOA(S_{j}^s)$ rather than reinitializing it.\n\n> the shared randomness across lazy updates could introduce correlations between historical predictions and current outputs, potentially creating exploitable patterns for adversaries.\n\nWe believe this sentence and its subsequent description in this review is a misunderstanding, possibly caused by our (overly) concise writing due to the page limit. We present more technical details in Appendix B. We are confident that there is no mistake in our derivation. \n\nWhile correlations exist between historical predictions and current outputs, they do not compromise the correctness of our algorithm.\n\nThe correctness of our algorithm is based solely on the fact that a constant fraction of the sequences ($S_1^s,\\dots,S_{N_s}^s$) remain consistent with the input (Lemma B.1). We prove this through concentration bounds only over the permutation $\\pi$ and label $\\bar{y}_i$ in the update (Algorithm 1). Since they are generated during the update and are independent of any prior randomness, the correctness can be directly established.\n\nWe emphasize that shared randomness is crucial for achieving a small mistake bound -- without it, the only way to ensure privacy is by advanced composition (as in the work of Golowich and Livni (2021) ), which results in a $\\sqrt{T}$ mistake bound. The primary challenge in private online learning is how to effectively leverage shared randomness to mitigate privacy cost while achieving a small mistake bound.\n\n> the privacy analysis extends beyond straightforward composition arguments and involves more nuanced considerations. \n\nThe privacy analysis remains straightforward considering the following three facts:\n\n1. the AboveThreshold mechanism is private against an adaptive adversary.\n2. the PrivateHistogram is private and non-sequential (thus also private against an adaptive adversary).\n3. the composition theorem holds for an adaptive adversary.\n\nConsequently, the entire algorithm is private against an adaptive adversary. Note that the randomness involved in the update is only for utility purpose and does not affect the privacy analysis."}, {"review_id": "J56qaJZAVo", "reviewer": "Reviewer_Nyfq", "summary": "In online learning, a learner receives a sequence of $T$ data points from an adversary and has to respond at each time step with an hypothesis. A concept class $\\mathcal{H}$ is said to be privately online learnable if there is an online learner achieving sublinear regret, that is also differentially-private w.r.t. all the stream of returned hypotheses. Apart from the classical differences, agnostic VS realizable setting and proper VS improper learner, one can differentiate between an oblivious adversary, that chooses the entire sequence of data points at the beginning, and adaptive one that can determine the sequence online, after observing the learner’s outputs. The authors show (1) an algorithm improving the mistake bound presented by Golowich and Livni [2021] against an adaptive adversary (closing the gap between the oblivious/adaptive cases) in the realizable setting and (2) an algorithm achieving sublinear regret for classes with finite Littlestone dimension in the agnostic setting with an adaptive adversary.", "questions": "1) Can you justify the necessity of including the condition over the dual Littlestone dimension in Theorem 4.2/ Corollary 4.3? This condition (if I am not mistaken) is required also for the results in \"Sample-efficient proper PAC learning with approximate differential privacy\" and I would like to have an intuitive explanation.\n2) Do you believe it is possible to eliminate the $2^{2^{O(d)}}$  factor in the Littlestone dimension? Just, your opinion about it.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Positive points**:\nThe paper is generally well-written and easy to follow, even if quite dense. Studying differential privacy in online learning is an interesting topic and not generally an easy one. In Section 3, the realizable setting is analyzed: the authors first give an in-depth explanation of the reasons why the procedure by Golowich and Livni [2021] does not attain a regret that is logarithmic in $T$ and then propose an algorithm that efficiently addresses those limitations. I think that the analysis is interesting and sound and the algorithm makes use of known procedures as subroutines. In Section 4, the authors deal with the agnostic setting: in particular they show a simpler algorithm employing sanitization and a more complex one employing experts and sanitization and achieving a better regret bound with an improper learner.  It is interesting to see many techniques blended together to obtain those results. \n\n**Negative points**:\nAs mentioned, the paper is dense. Without a knowledge of many results in the literature, it becomes a bit hard to follow some passages, even if the authors do their best to sum everything up. Also, I noticed that the main result cited at the beginning is not referenced again in Section 3 and that can be confusing.\n\n**Minor comments**:\nTypo in algorithm 2: failuare -> failure. Typo in Theorem 2.6 Pirvate -> Private.\n\nAll the above comments motivate my score.", "was_revised": true, "final_justification": "My opinion about the work after the rebuttal stays positive. This is a solid paper that addresses interesting questions regarding differentially private online learning.", "rebuttal": "We thank the reviewer for the constructive comments and provide our detailed responses below.\n\n> Can you justify the necessity of including the condition over the dual Littlestone dimension in Theorem 4.2/ Corollary 4.3? This condition (if I am not mistaken) is required also for the results in \"Sample-efficient proper PAC learning with approximate differential privacy\" and I would like to have an intuitive explanation.\n\nOur derived bounds in Theorem 4.2/ Corollary 4.3 depend on the dual Littlestone dimension because our algorithm is based on sanitization. As proved in \"Sample-efficient proper PAC learning with approximate differential privacy\" (their Theorem 6.7), the sample complexity of sanitization grows at least polynomially in the dual Littlestone dimension. Below we provide an intuitive explanation for a special case of their result.\n\nConsider a domain $X=\\\\{0,1\\\\}^D$ and a class $H=\\\\{h_1,\\dots,h_D\\\\}$ where $h_i(x) = x_i$. The Littlestone dimension of $H$ is $\\log D$ and the dual Littlestone dimension is $D$. For this class, sanitizing a dataset is equivalent to privately estimating its $D$-dimensional mean, which requires $\\Omega(\\sqrt{D})$ samples (Steinke, T., & Ullman, J. (2015) ).\n\nSteinke, T., & Ullman, J. (2015). Between Pure and Approximate Differential Privacy. *ArXiv, abs/1501.06095*. Presented at the First Workshop on the Theory and Practice of Differential Privacy (TPDP ‘15), London, UK, April 2015.\n\n> Do you believe it is possible to eliminate the $2^{2^{O(d)}}$ factor in the Littlestone dimension? Just, your opinion about it.\n\nYes, we believe that this factor can be improved to polynomial in $d$, as in \"Sample-efficient proper PAC learning with approximate differential privacy\" for PAC learning.\n\n> **Negative points**: As mentioned, the paper is dense. Without a knowledge of many results in the literature, it becomes a bit hard to follow some passages, even if the authors do their best to sum everything up. Also, I noticed that the main result cited at the beginning is not referenced again in Section 3 and that can be confusing.\n>\n> **Minor comments**: Typo in algorithm 2: failuare -> failure. Typo in Theorem 2.6 Pirvate -> Private.\n\nThank you for pointing out these issues. We will fix the typos and reference our main result in Section 3 in the revision."}, {"review_id": "V13CaFlPBq", "reviewer": "Reviewer_r3aS", "summary": "The authors study the problem of online learning with differential privacy. They make the following contributions:\n1. In the realizable setting, they propose a differentially private algorithm that achieves a mistake bound of $O_d(\\log T)$ for an adaptive adversary, where $d$ is the Littlestone dimension of the hypothesis class and $T$ is the time horizon. This improves upon the previously known bound of $O_d(\\sqrt{T})$.\n2. In the agnostic setting, they propose a differentially private algorithm that achieves a regret bound of $\\tilde{O}_d(\\sqrt{T})$. However, the proposed algorithm is improper. They also propose a proper learner with a regret bound of $\\tilde{O}_d(T^{3/4})$.", "questions": "In many online learning scenarios, the time horizon $T$ is not known in advance. I noticed that several parameters—such as the threshold in Algorithm 2 and the number of experts in Section 4.2—depend explicitly on $T$. Is it possible to remove this dependency?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is well written, with ideas presented in a clear and concise manner. The authors address the important problem of ensuring differential privacy in online learning, considering both the realizable and agnostic settings. While the work builds on prior research—such as Golowich and Livni [2021] and Bun et al. [2020]—and employs established tools like SOA, AboveThreshold, and Sanitization, it introduces several clever ideas and novel arguments (e.g., Lazy Update and uniform convergence) to improve upon the existing results.", "was_revised": true, "final_justification": "The authors have answered my question adequately, and after going through their rebuttal, I have decided to keep my positive score.\nConcerns resolved:\n1. Doubling trick for unknown time horizon", "rebuttal": "We thank the reviewer for the constructive comments, and our detailed responses are listed below.\n\n> In many online learning scenarios, the time horizon $T$ is not known in advance. I noticed that several parameters—such as the threshold in Algorithm 2 and the number of experts in Section 4.2—depend explicitly on $T$. Is it possible to remove this dependency?\n\nYes, this dependency can be removed by the classical \"doubling trick\" -- splitting the input sequence into buckets of sizes $1,2,4,8,\\cdots$ and running our algorithm on each bucket separately (with parameter $T=1,2,4,8,\\cdots$). It can be shown that the resulting algorithm have the same regret bound while not requiring knowledge of the entire time horizon in advance [Cesa-Bianchi and Lugosi, 2006]. \n\nWe will include the above comment in the revision.\n\nNicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006."}]

Author rebuttal:

Meta-review: While there exist algorithms that achieve a mistake bound of $O(\sqrt{T})$ against an adaptive adversary in the realizable setting for private online learning of Littlestone classes over a time horizon $T$, there also exist algorithms that achieve a mistake bound of $O(\log T)$ against an oblivious adversary. This paper closes the gap by giving an algorithm that achieves a mistake bound of $O(\log T)$ against adaptive adversaries. All reviewers agree that this is an interesting result since it was not clear whether there exists a separation between the models. 

I would encourage the authors to address reviewer concerns and make improvements to the overall presentation, to strengthen the potential impact of the work
Decision: Accept (poster)