Tracking The Best Expert Privately
Authors: Hilal Asi
Vinod Raman
Aadirupa Saha
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Online Learning
Primary area: social_aspects->privacy
TL;DR: We provide the first private online algorithms for minimizing dynamic regret under stochastic, oblivious, and adaptive adversaries.

Abstract: We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three natural types of adversaries, stochastic with shifting distributions, oblivious, and adaptive, and designs algorithms with sub-linear regret for all three cases. In particular, under a shifting stochastic adversary where the distribution may shift $S$ times, we provide an $\epsilon$-differentially private algorithm whose expected dynamic regret is at most $O\left( \sqrt{S T \log (NT)} + \frac{S \log (NT)}{\epsilon}\right)$, where $T$ and $N$ are the time horizon and number of experts, respectively. For oblivious adversaries, we give a reduction from dynamic regret minimization to static regret minimization, resulting in an upper bound of $O\left(\sqrt{S T \log(NT)} + \frac{S T^{1/3}\log(T/\delta) \log(NT)}{\epsilon ^{2/3}}\right)$ on the expected dynamic regret, where $S$ now denotes the allowable number of switches of the best expert. Finally, similar to static regret, we establish a fundamental separation between oblivious and adaptive adversaries for the dynamic setting:  while our algorithms show that sub-linear regret is achievable for oblivious adversaries in the high-privacy regime $\epsilon \le \sqrt{S/T}$,  we show that any $(\epsilon, \delta)$-differentially private algorithm must suffer linear dynamic regret under adaptive adversaries for $\epsilon \le \sqrt{S/T}$. Finally, to complement this lower bound, we give an $\epsilon $-differentially private algorithm that attains sub-linear dynamic regret under adaptive adversaries whenever $\epsilon \gg \sqrt{S/T}$.

Tracking the Best Expert Privately
Hilal Asi Vinod Raman
*2
Aadirupa Saha"
Abstract
1. Introduction
Online learning with experts a fundamental problem in machine learning, where an online algorithm interacts with an adversary for T rounds (Cesa-Bianchi & Lugosi, 2006). In the general form of the problem with N ex- perts, at each round I, the environment chooses loss vector E [N] + [o, 1], upon which the learner chooses an expert Jj E [N] from the pool of N experts. In the classical setting of online learning, we measure the loss of the learning algo- rithm compared to the loss of the "best-expert" in hindsight, denoted as the (static) regret
We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three nat- ural types of adversaries, stochastic with shift- ing distributions, oblivious, and adaptive, and designs algorithms with sub-linear regret for all three cases. In partieular, under shift- ing stochastic adversary where the distribution may shift S' times, we provide an e-differentially private algorithm whose expected dynamic re- gret is at most O (VSTT (oT) + (TT where T and N are the time horizon and number of experts, respectively. For obliv- ious adversaries, we give a reduction from dynamic regret minimization to static regret minimization, resulting in an upper bound of O ( (VSTlog(NT) + ST2/3 log(T/)) log(T/))log(VT) log(NT)) ca/a
T
RT = Σ ((J))) min
40*).
E
However, comparing against single fixed expert can often be unrealistic in practical applications. Even the best fixed expert may perform poorly on average over the entire loss se- quence, especially when loss sequences dynamically change over time or undergo significant distributional shifts, as is common in stochastic settings. This limitation motivates the concept of dynamic regret (Herbster & Warmuth, 1998; Wei et al., 2016). which provides more flexible and robust benchmark. Unlike static regret, which evaluates against the best fixed expert, dynamic regret compares against a sequence of changing experts, enabling the model to adapt to evolving environments. In particular, the dynamic regret is
the expected dynamic regret, where S now de- notes the allowable number of switches of the best expert. Finally, similar to static regret, we estab- lish a fundamental separation between oblivious and adaptive adversaries for the dynamic setting: while our algorithms show that sub-linear regret is achievable for oblivious adversaries in the high- privacy regime < VS/T. we show that any (s, 8) -iddifferentially private algorithm must suffer linear dynamic regret under adaptive adversaries for < V.TT. Finally, to complement this lower bound, we give an E-differentially private algo- rithm that attains sub-linear dynamic regret under adaptive adversaries whenever > VS/T.
T
T
DR = Σ ((J))
min EE....JEEEN
subject the constraint that the sequence {ii} does not switch too often. Intuitively, dynamic regret measures how well the algorithm competes against the best possible se- quence of decisions that could adapt to changes, constrained by a limited number of switches between experts. This notion particularly relevant for real-world applications like financial markets, where optimal strategies vary with market conditions, recommendation systems, where user preferences evolve over time.
'Equal contribution 'Apple 'Dppartment of Statistics, Univer- sity of Michigan, Ann Arbor. Work done while interning at Apple "University of Illinios, Chicago. The majority of the work done while the author was with Apple Research. Correspondence to: Vinod Raman <vkraman& umu.ch.duu>.
By inspecting definitions, it is clear that minimizing dy- namic regret is harder than static regret. This difficulty manifests even if one measures dynamic regret against se- quenees of experts with single switch. As result, exist-
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Tracking the Best Expert Privately
ing algorithms for minimizing dynamic regret modify the
and number of distribution shifts, respectively. We also give lower bound of ( ST log(N)) log(N/S)) for this setting, demonstrating the near-optimality of this algorithm. Key to our algorithm is the sparse-vectors vector-technique which we deploy in order to identify a new shift in the distribution without paying a large cost in privacy.
standard Multiplicative Weights Algorithm (Littlestone & Warmuth, 1994) to explicitly account for the fact that they are being evaluated against sequences of experts that switch.
While dynamic regret in online learning offers a more prac- tical approach to modeling non-stationary environments, its applicability in sensitive real-world scenarios often re- quires additional considerations, particularly around privacy. In many online learning problems, the loss functions used to guide expert selection are derived from sensitive data, such as user interactions, medical information, or financial records. Ensuring that the learning process does not in- advertently reveal private details about the data is crucial for maintaining trust and complying with legal and ethical standards. This challenge motivates the integration of dif- ferential privacy into online learning from experts in the dynamic setting.
Oblivious adversaries. We develop a new algorithm for the oblivious setting through a reduction from private online prediction in the dynamic setting to the static setting. Apply- ing this reduction with existing algorithms for private predic- tion in the static setting (Asi et al., 2023b), we obtain up- per bound of O (VTSTog (NT) + ST1/3 (og(T/8) log NTT) on the expected dynamic regret.
62/3
Adaptive adversaries. We establish a separation between oblivious and adaptive adversaries in the dynamic setting. To this end, we show that any (e. 8) didiferrential private algorithm must suffer linear dynamic regret (T(T) under adaptive adversaries for ε S VS/T. In contrast, our upper bounds for oblivious adversaries show that sub-linear regret is still possible for ε s VS/T. Finally, we provide a new algorithm that obtain sub-linear regret for E > /S/T. This establishes & ~ S/T as a critical sharp threshold for learning under adaptive adversaries in the dynamic setting, where learning becomes infeasible for E S VS/T but attainable for larger values of
However, existing work on private online learning (Jain et al., 2012a; Smith & Thakurta, 2013; Jain & Thakurta, 2014a; Agarwal & Singh, 2017a; Asi et al., 2023b; 2024) limited to the static setting. As a result, existing privacy- preserving algorithms struggle to adapt to non-stationary environments, where the optimal expert may shift over time, leading to suboptimal performance.
Our work addresses this gap by initiating the study of pri- vate online prediction from experts in the dynamic setting. We formally define this problem and study it with respect to three natural types of adversaries. We develop new al- gorithms and lower bounds for each of these adversaries, demonstrating the near-optimality of our algorithms in sev- eral settings, and the hardness of the dynamic setting com- pared to the well-studied static setting.
1.2. Related Works
Private Online Learning and Prediction with Expert Advice. Differentially private online learning was first stud- ied by Dwork et al. (2010a) in the context of continual observations. Jain et al. (2012b) extend these results to online convex programming by using gradient-based al- gorithms to achieve differential privacy. Following this work, Guha Thakurta & Smith (2013) privatize the Follow- Lae-AAproximate-Leaaee
1.1. Our Contributions
In this work, we initiate and systematically study the prob- lem of tracking the best expert privately through the lens of online prediction with dynamic regret guarantees. We present a comprehensive study of the problem for three different types of adversaries: 1. Shifting stochastic adver- saries where the losses are sampled from distributions that may shift over time, 2. Oblivious adversaries which choose the loss functions before the interaction with the algorithm, and 3. Adaptive adversaries, the most powerful type of ad- versary, which can choose their loss functions as a function of the interaction with the learning algorithm. We highlight the following key results:
template to obtain sharper guar- antees for online convex optimization. For prediction with expert advice, Dwork et al. (2014) and Jain & Thakurta (2014b) give private online learning algorithms with re-
More recently, (Agarwal gret bounds of O (Tlog(N)
6
& Singh, 2017b) study private online linear optimization and achieve regret bounds that scale like O(VT) + O Using this result, they show that for the setting of predic- tion with expert advice, it is possible to obtain a regret bound that scales like O (T + log(N) log T) improving upon the work by Dwork et al. (2014) and Jain & Thakurta (2014b). For large N, this upper bound was further improved to O (VTlog((N) + T1/3 log(()) and (V (VTlog(N) + Iog(1))(N) by Asi et al. (2023b) and
Shifting stochastic adversaries. We design an E- differentially private algorithm with an expected dynamic regret bound of O (VST [T)) + Slog(TN)) where T, N, and represent the time horizon, number of experts,
2

---

Tracking the Best Expert Privately
Table Summary of our bounds on the dynamic regret for different settings of the adversary. We omit logarithmic factors in 7 and 1/6.
Upper Bound
Lower Bound
Shifting Stochastic
1Sg N + N
Vog N 8 S/og(N/S)
Oblivious
log N + ST log
VSTllog N
Slog(N/SS
2273
Adaptive
187 N Slog
VST VSTlog N
8 (= T
Asi et al. (2024) respectively, under oblivious adversary. Recent work also study private prediction with expert advice in the realizable setting where there is a zero-loss expert (Asi et al., 2023a).
and dynamic regret for the setting of prediction with expert advice (Adamskiy et al., 2012; Daniely et al., 2015). In fact, for prediction with expert advice, it is known that the dynamic regret can be upper bounded by the adaptive regret, and hence adaptive regret minimization is sufficient for dynamic regret minimization (Luo & Schapire, 2015). In this paper, we use this con- nection between adaptive and dynamic regret minimization to derive bounds on the dynamic regret under stochastic adversaries under privacy constraints.
et al., 2012;
Asi et al. (2023b) also study private prediction with expert advice under stochastic and adaptive adversaries. Under stochastic adversary, they reduce private online learning to private offlin learning and give an (c, diffferrrett private online learning algorithm with expected regret ((yTloog + log )). Under adaptive adversaries, (Asi et al., 2023b) prove a lower bound - any (e, didffffrrential private online algorithm with E S - cannot achieve sub- linear regret under an adaptive adversary. This result estab- lished a separation between the achievable regret bounds under oblivious and adaptive adversaries.
2. Preliminaries
Let N NN denote the number of experts and f: [M] + [0, 1] denote an arbitrary loss function that maps an expert to a bounded loss. For an abstract sequence 21..... Zn, we abbreviate it as Zi:n For a measurable space (X)), we let AX' denote the set of all probability measures on X'. For N E N, we also let AN denote the set of all distributions over {1.....N} We let Laplace(A) denote the Laplace dis- tribution with mean zero and scale À such that its probability density function is fa fxx 2x exp (=x) -Finally, we let [N] = [l,...,,N for N E E.
Non-private Dynamic and Adaptive Regret Minimiza- tion. In the context of prediction with expert advice, dy- namic regret minimization is also known as tracking the best expert (Littlestone & Warmuth, 1994; Herbster & Warmuth, 1998; Gyorgy et al., 2012; Bousquet & Warmuth, 2002; Vovk, 1997). This setting was first introduced by Herbster & Warmuth (1998; 2001), who noted that static regret is only meaningful for stationary environments. Following this work, there has been significant interest in obtaining dy- namic regret bounds for various settings. For example, Wei al. (2016) study dynamic regret bounds in non- stationary stochastic environments, while Zinkevich (2003); Hall & Willett (2013) have studied dynamic regret for online op- timization problems. Other works have also focused on obtaining first- and second-order dynamic regret bounds (Zhang et al., 2018; Lu & Zhang, 2019) and obtaining guar- antees for dynamic regret for stochastic and oblivious ad- versaries simultaneously (Luo & Schapire, 2015). Most relevant to this paper the work by Lu & Zhang (2019), who provide simple modification to the standard Multi- plicative Weights Algorithm (Littlestone & Warmuth, 1994) that obtains near optimal dynamic regret under an oblivious adversary.
2.1. Prediction with Expert Advice and Static Regret
In the classical problem of online prediction with expert advice, learning algorithm A plays a sequential game against an adversary over T E N rounds. In full gen- erality, the adversary first picks a sequence of functions fi, f2...., such that ft [N] [N]-- - [0, 1] for all & [7]. Then, in each round & E [T', the learner, us- ing the history of the game, selects (potentially randomly) expert J, E [N]. Finally, the adversary reveals the loss function & := fe(-,J1a-1) and the learner suffers the loss (J.)... The goal of the learner is to adaptively select experts JI...., Jr E [N] such as to minimize its expected (static)
regret
T
A closely related notion to dynamic regret is adaptive re- gret (Littlestone & Warmuth, 1994; Hazan & Seshadhri, 2007). Here, the goal is obtain sublinear regret within every contiguous sub-interval of the time horizon. Several works have established deep connections between adaptive
Ra(fir, := EA
Σ
fJJ,,
min j [
Σ ,t0"",,a011 J1o-1))
3

---

Tracking the Best Expert Privately
where the expectation is taken only with respect the ran- domness of the learning algorithm.
A weakening of the adaptive adversary is oblivious adversary. This adversary must first pick sequence of loss vectors fi,... ,, &T independently of J1.T and then con- struct the sequence of functions fe, feg...., such that St, (h- 1) = ((i))) We define the worst-case expected regret under an oblivious adversary as
2.2. Dynamic Regret
Motivated by concerns of distribution shift, there has been significant interest in minimizing stronger notion of ex- pected regret termed expected dynamic regret (Herbster & Warmuth, 1998). Unlike expected (static) regret, where the goal is to compete against the best fixed expert in hindsight, dynamic regret measures the performance of the player against a comparison sequence of experts Jı.T E [N] To make the problem tractable, we constrain the comparison se- quence of experts to have most S switches, where S E N is known to the player before the game begins. Namely, sequence of T experts J1.T E if 1 # 5.) S S. Then,
DR (T,N,S) = sup DRa Sey, N,S). E1...
Finally, the shifting stochastic adversary is the weakest of the three. Here, the adversary must first pick sequence of S distributions DI...., ........2 Ds E ([0, 1]x) and a sequence of S - time points 1,,,.., 1.-.,,,s1111 E [T - 1]. The adver- sary draws loss functions f1..... lr such that l, D, iff É [La, (s+1) and constructs functions Sea fe2...., Sty. Abusing some notation by omitting the dependence on 11:511 the worst-case expected regret under a stochastic adversary is
[N] has at most S switches
T-1 C(T, = { jur E [M]T
Σ Hiti + jel S sss s}.
DR (T, N,S) == sup B DRa(Je)...... Ser: N,S)
the set of all T-length expert sequences with at most S switches. For sequence of functions fi, .2.,.., . fr, we can now define the expected dynamic regret for algorithm A by comparing its cumulative loss to that of the best fixed sequence of experts in S):
Dr.s
Note that in the definition of (T, the same is used to constrain both the number of distributions that the adversary can pick and the number of switches in the comparison sequence of experts.
(RA(Fi,,N,S) = EA
Σ SelJe,Ja--)
Analogous versions of worst-case expected (static) regret under adaptive, oblivious, and shifting stochastic adversaries follow by placing the same restrictions on how fi,..., fr can be chosen. As an example, the worst-case expected (static) regret under an adaptive adversary will be written as Radur (T, = sur (J N). Without privacy concerns, the worst-case expected regret O(VTlog N) for all three types of adversaries and can be obtained by running single algorithm, the Multiplicative Weights Al- gorithm (MWA) (Littlestone & Warmuth, 1994). Likewise, the worst-case expected dynamic regret under stochastic, oblivious. and adaptive adversaries is also known to be e Tog N), and achieved by modifying MWA to en- sure that the probability of playing any expert never drops too low (where "low" depends on S and T') (Herbster & Warmuth, 1998; Wei al., 2016).
min EC(TS)
E Idlltt
We make few remarks about the definition of dynamic regret. First, note that (JETT, N) = DRA(S N)O). Second, (fiTT N, S1) < DRA(fi,,,, for S < S2, meaning that as 5 gets larger, the set of comparison sequence of experts S) gets larger, making minimizing dynamic regret harder. Lastly, we stress that while dynamic regret restricts the number of switches in the comparison sequence of experts, the player is not restricted in the num- ber of switches it can make. This is crucial for being able to obtain sublinear expected dynamic regret.
By placing restrictions on how f2.f2..... fr can be chosen, one gets different types of adversaries leading to different definitions of worst-case expected dynamic regret. In this paper, we consider three adversaries: (1) shifting stochastic, (2) oblivious, and (3) adaptive.
2.3. Differential Privacy
We adopt the notion of differential privacy for prediction with expert advice from Asi et al. (2023b). Consider an abstract space Z and consider function E [N] Z + [0, 1]. Every E 2 now induces a loss function f( 2) E [0, 1J Accordingly, stochastic, oblivious, and adaptive adversaries can be equivalently defined in terms of picking
The strongest of the three is the adaptive adversary. For an adaptive adversary, no restrictions are placed the adversary can pick any sequence of functions f1, f2..... fr leading to the worst-case expected dynamic regret being defined as
21...., 27 E 2T and a function : [N] x Z - [o, 1]. For completeness sake, we make this explicit below.
DR D (T, == sup DRA(FIT,N, N.S).

---

Tracking the Best Expert Privately
A stochastic adversary under dynamic regret now picks sequence of 5 distributions D...... Ds E 2, sequence of times points f,,.. ,,...., (5-1. and a function é: [N] 2
max returns
arg max ( + Zz where Z ~ Laplace(2/E). sE[K]
[0, 1]. The loss function at time point t E [t.. (x+) is ob- tained by sampling 2 < DD and outputring & = {(:, =)) An oblivious adversary selects a sequence 21,...,, 2r and a function e [N] x + [0, 1] before the game be- gins. The loss function at time t E [T] is then defined as & 2() Finally an adaptive adversary picks sequence 21....;2T E z and a sequence of function l : [N] [N][-1 x 2 + [0, 1]. The loss function at time t E [T], is then defined by (1a-1,1 where JA--1 are the random variable representing the actions of the player. Note that give an input 21:7, stochastic and oblivious adversaries are fully parameterized by a function é: [N] x Z + [0, 1J, while adaptive adversaries are pa- rameterized by a sequence of functions l1 : er such that 4: [N] x [Nj--1 2- [0, 1].
z
Lemma 2.3 ((Dwork & Roth, 2014), claim 3.9). The report- noisy-max algorithm is E-differentialy private.
Sparse vector technique. We recall the sparse-vector technique (Dwork & Roth, 2014). Given an input 2im X", the algorithm takes a stream of queries 91-92..... 92.-...-9h x + R in online manner and aims to identify queries whose value is above zero. We assume that each qi is 1- sensitive, that is, (g:(1 gi (#1.n)) S 1 for neighboring datasets Ti:m, z'., that differ in a single element. We have the following guarantee.
Lemma 2.4 ((Dwrrk & Roth, 2014), Theorem 3.24). Let Fi.n E X" be an input dataset. For 3 > O, there is an e-differentially private algorithm (Above Threshold) that halts at time k E [T 1] such that for a = 8(logT +lgg(288)) with probability at least 1 - 3,
With this equivalent representation in mind, we are now ready to define our notion of differential privacy. A dataset as sequence of elements 21....; :, 27. Two datasets, 21:T and z/.77. are neighboring if they differ exactly at one time J1,...,,J Jr be the sequence of random variables denoting the experts played by A when interacting with the adversary Adv that is given inputs F1.7.
point /' E [T]. Let A Adv(zi:r)
For all t < k, (((1i:))) S a;
(x(w)))) a or T +
Definition 2.1 (Adaptive Differential Privacy). A random-
To facilitate the notation for using Above Threshold in our algorithms, we assume that it has the following components:
ized algorithm A is (c, -)diifferentially private against adap- tive adversaries, if for all neighboring data sets 21.r, 21.r E 2T, any potentially adaptive adversary Adv, and all events E [ [N]", we have that
1. InitializeSparseVee(e,,, 3): initializes new instance of Above Threshol with privacy parameter e, and failure probability parameter (3. This returns an instance (data structure) Q that supports the following test-above- threshold function.
P [A Adv(ZIT) E EJ S EPA Adv(=1.T) E E +
If 8 = 0, we say that A is e-differentially private.
2. Q. Thrr)) tests if the query is above thresh- old. In that case, the algorithm stops and does not accept more queries.
The following mechanisms will also be useful building blocks to several of our algorithms.
Laplace Mechanism. Let X' be arbitrary set and n E N. Suppose f x - R is query with sensitivity A
3. SVT-based Algorithm for Stochastic Adversaries
(i.e. for all pairs of datasets Iim, 2'.n E X that differ in
exactly one index, we have that |f [x(1_))) - f((( < A). Then, for every E, the Laplace mechanism M x - IR is defined as M(1 (* + Z, where Lap( e.
We begin our algorithmic contribution by studying the stochastic setting, where we develop an SVT based al- gorithm that obtains VST + S/e dynamic regret against stochastic adversaries. The starting point of our algorithm is lazy algorithm of (Asi al., 2023b) for private prediction from experts with static regret. We show in Section 3.1 that this algorithm obtains near-optimal adaptive regret (Hazan & Seshadhri, 2007), that is, it obtains regret V for any sub-interval of size w for a stochastic adversary. Then, we present our main algorithm in Section 3.2, which obtains near-optimal dynamic regret against stochastic adversaries.
Lemma 2.2 (Dwork & Roth, 2014), Theorem 3.6). The Laplace Mechanism is E-differentially private.
Report-Noisy-Max Mechanism. The report-noisy-max mechanism is differentially private algorithm that aims to select the item with the highest count. More specifically, given an input dataset Zim E X and K count queries "1, CKK n -> IR that are 1-sensitive, ropsrt-noisy-
5

---

Tracking the Best Expert Privately
3.1. Optimal Adaptive Regret for Stationary Environment
Algorithm 2 SVT-based algorithm
Require: Privacy parameter E, failure probability 3
8 1,
In this section, we consider the simple stochastic setting where all losses are samples for a fixed distribution P. We present that version of the existing algorithm of (Asi et al., 2023b) obtains a stronger guarantee than the original paper proved: it obtains near-optimal adaptive regret for stochastic adversaries, meaning that it obtains v regret for any sub-
2: Start new instance of Algorithm 1 from 4 with privacy
parameter c/2
3: Q = InitiaizeeSparseeeeeee/...
4: while t < 7''oo do
5: Receive new loss &
Use Algorithm to play jt
interval of size w.
7: Define a
16(2 log T (2)g(2 and Reg..
Algorithm 1 Limited Updates for Online Optimization with
16 (TT loR(T) 9 9 w log (TN/B)
Stochastic Adversaries
For each w S t ti define query
Require: Privacy parameter E
1: Set ju E [N]
du
2(i min JE[N]
Σ
4 aa-1
2: for 1 to T do
3: if't 2 for some integer f 2/ then
4: Run report-noisy- procedure get
9:
if Q. TestAAbTThr(('') is true for some w then
10:
1
je. arg min JE(N)
Σ 401)+ i=t/2
11:
t,
12:
Go to line 2 and restart a new instance of Algo- rithm
where Zo(i) Laplace(2/))
13:
end if
5:
else
14:
end while
6: Let jr. Jc-1
7: end if
The following theorem summarizes the dynamic regret guar- antees of Algorithm 2. We defer the proof to Appendix B.2.
8: Receive be [N] + [0.
9: Pay cost (e(e))
10: end for
Theorem 3.2 (Upper bounds for Expected Dynamic Regret for Shifting Stochastic Adversaries). Let A denote Algo- rithm 2 when run with and B = 1/T. Then algorithm A is e-differentially private and has expected dynamic regret DR (TN upper bounded by
The following theorem states the adaptive regret guarantees of Algorithm We defer the proof to Appendix B.I.
Theorem 3.1. Let l,. br: : [N] + [0, 1] be sampled i...d from distribution P. Then, for any t [T] and E [T - t). Algorithm 1 is d-diffrrentially private and has with probability 1 3,
o O (STlog(NT) + Slog(NT) log(T)
Proof. (sketch) The privacy proof follows directly from the guarantees of SVT mechanism and Algorithm as each user is used in the instantiation of both Algorithm I and SVT with parameters e/2.
16 (Ng/3333) log(T))
Σ 4()
Σ JE[N]
min
$
E
+ 9V w log Wlgg(TN/B).
The utility proof follows from two main ingredients, which we prove in Lemma B.3 and Lemma B.4. The first shows that if the distribution shifts at most S times, then SVT will return true at most times with high probability. The second result shows that as long SVT has not restarted the instantiation of the internal algorithm, its regret in any sub-interval (adaptive regret) will be small. Building on these two lemmas, we can prove an upper bound on the dynamic regret (see Appendix B.2 for full details).
3.2. Optimal Dynamic Regret for Shifting Stochastic Adversaries
In this section, we develop our main algorithm for the stochastic setting. Our algorithm is based on iteratively run- ning the algorithm for the stationary setting (Algorithm I). algorithm
Moreover, to adapt shifting distributions, uses the sparse-vectes vector-technique to test whether the under- lying distribution of the losses has changes. To this end, we use SVT to test whether the regret of the internal algorithm is too large, indicating a shift in the distribution. We present the full details in Algorithm 2.
Lower bound for shifting adversary. We can extend the lower bound of the static setting (Asi et al., 2023b) to our dynamic setting. Indeed, the static setting has lower bound
6

---

Tracking the Best Expert Privately
of log(N)/s on the expected regret. We can construct an adversary which splits the rounds to S phases, where in each phase it uses the static lower bound over disjoint subset of the experts of size N/S. Given the independence of these phases, this implies that the regret in each phase is lower bounded by log(N//S)/s. Summing over all S phases, we get that the dynamic regret is lower bounded by S log(NNS))f Finally, note that in the most common setting of parameters where S - T < NI-P for some constant p > O, this lower bound becomes (SS (o)) matching our upper bound.
ee : E ? [0, 1] such that E(()) ((e(()) for all E & and passes & to A, which then updates itself. We claim that: (1) B's s expected dynamic regret is at most R (2, (NT)2S) and (2) B is (s, diffferrrnt private.
We start by proving Claim (1). Observe that
[ 18== c=0
T No+1 S SNS+1
Σ
S (NT))2
c=0
Therefore, by the guarantees of A, we have that
T
4. Upper bounds for Oblivious Adversaries
Σ
((B
min cEE'
(NT)2S).
To obtain our upper bounds on expected dynamic regret against oblivious adversaries, we reduce private dynamic regret minimization to private static regret minimization. That is, our main result is a conversion of a private on- line learning algorithm minimizing static regret to a private online learning algorithm minimizing dynamic regret. By doing so, we are able to leverage the recent results by Asi et al. (2024), who obtain the best-known expected (static) regret guarantees for private online learning under oblivious adversaries.
By definition of the meta loss vectors, we have that
T
E
e (e()
min
Σ ((e(()) S RA(T. (NT)2s).
EEE
Let jir E [NT be the minimizer of Σ (i.) such that o² = Et= ( # jt) S S. Let 12......... (2x)) be the time points where the switches in jir occur. Observe that there exists expert ex E & which plays expert j between time points ti1 and t for every i E [e*]. Accord- ingly, we have that et (t) = jž for all t E [T] and
Theorem 4.1 (Private Static Regret
Pri- vate Dynamic Regret). Let s E (0, Suppose there exists an differrinel private algorithm A whose worst-case expected regret under oblivious adversary is at most (T.N). Then, there exists an (e, 8)-differentiallyy private algorithm B such that DR ST) S RA (NT)
E Σ (J -
Σ 400 S (T. (NT)28).
completing the proof of Claim (1).
Proof. Let d, E (0, 1). Fix the time horizon T E N, the number of experts N E N, and the number of switches Se N. Suppose there exists an (e, diddifffrenttillyy private algorithm A whose worst-case expected regret under oblivious adversary is at most ubl (T, N)..
We now prove Claim (2). Consider two neighboring se- quences of loss functions f1,...,yy by and C,...., fr which differ at exactly one time point L'. Consider the sequence of meta loss vectors f,,..., fr and E construct and pass to A had it been run on f,..... br and E,....,y er respectively. Observe that fi....,4y by and Ey , tions that differ only at time point t'. Hence, the out- puts of A when run l,,..., Ey and & .,...., &y are (e, indistinguishable. The proof complete after noting that the outputs of B is the result of post-processing the output of A since the outputs of the meta- meta-experts are fixed, and do not depend on the observed loss sequence.
er that B would
Consider the following algorithm B. Let [T]ge be the set of all strictly increasing tuples of size at most c. Before the game beings, first constructs the class of meta-experts & such that
are also neighboring sequence of loss func-
E= ==URetneduee the E JTe41 [N]c+1] ) c=0
where the expert etsee [T] + [N] plays expert ji from time point 1 to t; for every i E [c + 1]. where to 1 and fc+1 = T. Then, B initializes A with the set of meta experts E. In each round E [7], B queries A, receives a (potentially random) meta-cxpert E, E E from A, and plays the expert J, E [N] played by the meta-expert E, on round t. That is, Jj := (t). After observing the true loss vector l, : [N] + [0, 1), B computes a meta-loss vector
We now provide concrete upper bounds on the expected dynamic regret under oblivious adversaries by instantiating Theorem 4. 1 with existing private algorithms from literature. First, we recall the regret guarantee of the private online learning algorithm from Asi et al. (2024).
Proposition 4.2 (Upper bound on Expected Regret for Oblivious Adversaries (Asi et al., 2024)). Fix 8, (0,
7

---

Tracking the Best Expert Privately
There exists an (s, (differrrrr private algorithm A such that
regret under oblivious adversaries is sublinear in the time horizon T. However, this is not the case under adaptive adversaries: for any & S V every (e. -ddifferrenti pri- vate online learning algorithm must suffer expected regret which grows linearly with T. In this section, we prove qualitatively similar, but quantitatively stronger separation between private expected regret minimization under oblivi- ous dynamic adversaries and adaptive dynamic adversaries.
R R (T,N,)) = (VTlogN+ N+ ( T1/3 (og( log N
22/3
Instantiating Theorem 4.1 with the algorithm guaranteed by Proposition 4.2 then gives the following Corollary.
Corollary 4.3 (Upper bounds for Expected Dynamic Regret for Oblivious Adversaries). Fix e, ô E (0, 1). There exists an (e, diifferrnetl private algorithm B such that
5.1. Lower Bounds for Adaptive Adversaries
Our first result is lower bound which roughly shows that when & E o( f),, sublinear expected dynamic regret is not possible under adaptive adversaries. Our lower bound construction builds upon the lower bound construction by Asi et al. (2023b) for expected (static) regret under adaptive adversaries. Namely, if there are S switches, then our lower bounds follows by using S different copies of the lower bound construction from Asi et al. (2023b) for adaptive adversaries.
DR ( S) = 0 o ST (NT(
(N)
ST log (og(T)
e2/3
We highlight that Corollary 4.3 provides the first known upper bounds expected dynamic regret under oblivious adversaries and differential privacy. Unfortunately, unlike our algorithms in Sections 3 and 5, the algorithm obtaining the upper bound in Corollary 4.3 is not efficient as it requires constructing a set of experts that is exponential in the time horizon. In Section 5, we give an efficient e-differentially private algorithm whose expected dynamic regret is at most under an adaptive adver- sary. Clearly, the same upper bound holds for oblivious adversaries. However, this upper bound is weaker than the one we get in Corollary 4.3.
Theorem 5.1 (Lower bound on Expected Dynamic Regret for Adaptive Adversaries). Let S 2 0, T be sufficiently large, and N 2 2T (e, J)dffferrent private, then
5. Let & S 1 and 8 S (S+1))
If A is T3
O VST 1o + 8 logg( (TT)(NT)
DR DR NT, = Ω min (T.
S
T,
"Elog s )2)
Theorem 5.1 roughly implies that when E S V / every (e, 8)-differentially private online learner must suffer ex- pected dynamic regret S?(T)) under an adaptive adversary. This is in stark contrast to Theorem C.2 which shows that sublinear expected dynamic regret is still possible when S v & under an oblivious adversary. The proof of Theo- rem 5.1 can be found in Appendix D.
We end this section by noting that efficient dynamic regret minimizing algorithms for oblivious adversaries do exist if one does not care about privacy. Unfortunately, unlike for static regret, privatizing existing dynamic regret minimiz- ing algorithms is not as straightforward. As an example, Lu & Zhang (2019) give an efficient non-private algorithm for minimizing dynamic regret by projecting the distribu- tions over experts obtained after the multiplicative weights update into clipped simplex. This ensures that the prob- ability of any playing any particular expert is sufficiently lower bounded. Unfortunately, this clipping operation is challenging under privacy constraints as now we have to privatize each gradient separately instead of privatizing the sum of gradients via the Binary Tree Mechanism (Dwork al., 2010a) Oa). We leave whether one achieve the upper bound in Corollary 4.3 via an efficient algorithm as open question.
5.2. Upper bounds for Adaptive Adversaries
Our second result is an upper bound which shows that sublin- ear expected dynamic regret under an adaptive adversary is possible as long as = w(y $). To do so, we modify an ex- isting efficient (non-private) algorithm for regret minimiza- tion under adaptive dynamic adversaries. Namely, we design private version of Algorithm 2 from Lu & Zhang (2019) by adding independent Laplace noise to the loss vectors before using them to update the distribution over the experts. For completeness sake, we include this modified algorithm below. Let ÂN := {w E AN min, w(j) Z NT } denote the clipped simplex, & AN + Rgo denote the negative Shannon entropy function d(w) = Σラ w(j) log w(j), and Do(-Il-) : AN x An + R>o denote the Bregman divergence with respect to Φ, defined as Do ||w2) ==
5. Dynamic Regret for Adaptive Adversaries
Under expected (static) regret, Asi et al. (2023b) prove a separation between oblivious and adaptive adversaries. In particular, for every S w there exists (E differ- entially private online learning algorithm whose expected
8

---

Tracking the Best Expert Privately
((w) ((w2) (w0 w2 V (1w)))
Existing techniques for obtaining private online learning algorithms under static regret rely privatizing existing (non-private) lazy algorithms that do not switch their played experts too often (Asi et al., 2023e; 2024). Unfortunately, it is reasonable that such lazy algorithms cannot obtain good dynamic regret, as switching which expert is played is cru- cial to "tracking" the best expert. We will make sure to add discussion of this the camera-ready version.
Algorithm 3 Private Online Learner for Adaptive Adver-
saries
1: Input: >> 0,
2: Initialize: wi(1) N for [N]
3: fort 1,2..... T do
4: Draw expert Jr we
5: Observe loss vector & and suffer loss (Jt).
6: Sample Ze(t) Laplace(?) and define (1)
Impact Statement
E((t)= + (z) for all i e [N]
7: Update W4-1 =
arg min migmin WEÂN (w, nla)
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
(w(l)
8: end for
Theorem 5.2 (Upper bound on Expected Dynamic Regret for Adaptive Adversaries). Let A denote Algorithm 3 when run with E (0,1) and = EV T/ogENTTY Then A is E-differentially private and has
References
Adamskiy, D., Koolen, W. M., Chernov, A., and Vovk, V. closer look adaptive regret. In Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23, pp. 290- 304. Springer, 2012.
VSTTlgg 1.5 (NT) + Slog(NT)
1 N, =0
8
Agarwal, N. and Singh, K. The price of differential privacy for online learning. In Proceedings of the 34th Inter- national Conference on Machine Learning, pp. 32 32-40, 2017a.
The proof of Theorem 5.2 follows by combining techniques from Lu & Zhang (2019) and Agarwal & Singh (2017a) 7a), and is deferred to Appendix C.
Agarwal, N. and Singh, K. The price of differential pri- vacy for online learning. In International Conference on Machine Learning, pp. 32-40. PMLR, 2017b.
6. Discussion
In this paper, we provide the first private online learning algorithms for dynamic regret minimization against three types of adversaries: switching stochastic, oblivious and adaptive. We highlight important directions of future work.
Asi, H., Feldman, V., Koren, T., and Talwar, K. Near- optimal algorithms for private online optimization in the realizable regime. Proceedings of the 40th International Conference on Machine Learning, 2023a.
Optimal bounds for Oblivious Adversaries. In Section 4, we provided an upper bound of the
Asi, H., Feldman, V., Koren, T., and Talwar, K. Private online prediction from experts: Separations and faster rates. Proceedings of the Thirty Sixth Annual Conference on Computational Learning Theory, 2023b.
O (v (og(o)(NT) s/1/3 (6)(T)5) expected dynamic regret under an oblivious adversary. We leave open whether one can prove a matching lower bound or an improved upper bound.
Asi, H., Feldman, V., Koren, T., and Talwar, K. Private online prediction from experts: Separations and faster rates. In The Thirty Sixth Annual Conference Learning Theory, pp. 674 779.699. PMLR, 2023c.
Efficient algorithms for Oblivious Adversaries. Unlike for stochastic and adaptive adversaries, our algorithm for oblivious adversary is not efficient - constructs a set of experts that is exponential the time horizon T. This moti- vates the design of efficient algorithms for dynamic regret minimization under oblivious adversaries with matching or current attempts
Asi, H., Koren, T., Liu, D., and Talwar, K. Private online learning via lazy algorithms. arXiv preprint arXiv:2406.0366 2024.
better regret bounds. Unfortunately, at designing efficient private algorithms against oblivious adversaries have been unsuccessful, as it is not clear how to privatize existing efficient non-prin private algorithms for dy- namic regret. Perhaps central to the difficulty is the tension between lazy updating and obtaining small dynamic regret.
Bousquet, O. and Warmuth, M. K. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3(Nov):363-396 2002.
Cesa-Bianche N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.

---

Tracking the Best Expert Privately
Cesa-Bianchi, N., Gaillard, P., Lugosi, G., and Stoltz, G. Mirror descent meets fixed share (and feels regret). Advances in Neural Information Processing Systems, 25, 2012.
Jain, and Thakurta, A. (Near) dimension independent risk bounds for differentially private learning. In Proceed- ings of the 31st International Conference Machine Learning, pp. 476-484, 2014a.
Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405-1411. PMLR, 2015.
Jain, P. and Thakurta, A. G. (near) dimension independent risk bounds for differentially private learning. In Inter- national Conference Machine Learning, pp. 476-484. PMLR, 2014b.
Duchi, C. Information theory and statistics. Lecture Notes for Statisties 311EEE 377, Stanford University, 2019. URL http:/ wttptttaaa.......eeeeeeeeeeeeeee edu/class/ pdf. Accessed May
Jain, P., Kothari, P., and Thakurta, A. Differentially pri- vate online learning. In Proceedings of the Twenty Fifth Annual Conference Computational Learning Theory, 2012a.
2019.
Jain, P., Kothari, P., and Thakurta, A. Differentially pri- vate online learning. In Conference on Learning Theory, pp. 24-1. JMLR Workshop and Conference Proceedings, 2012b.
Dwork, C. and Roth, A. The algorithmic foundations of dif- ferential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 & 4):211 1 407, 2014.
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. Dif- ferential privacy under continual observation. In Proceed- ings of the forty-second ACM symposium Theory of computing, pp. 715-724, 2010a.
Kairouz, P., Oh, S., and Viswanath, The composition the- orem for differential privacy. In International conference machine learning, pp. 1376 1385. PMLR, 2015.
Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and computation, 108(2):212- 261, 1994.
Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science, pp. 51-60. IEEE, 2010b.
Lu, S. and Zhang, L. Adaptive and efficient algorithms for tracking the best expert. arXiv preprint 1909.02187, 2019.
Dwork, C., Roth, A., al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-40) 2014.
Luo, H. and Schapire, R. E. Achieving all with no pa- rameters: Adanormalhedge. In Conference on Learning Theory, pp. 1286-1304. PMLR, 2015.
Guha Thakurta, A. and Smith, A. (nearly) optimal algo- rithms for private online learning in full-information and bandit settings. Advances in Neural Information Process- ing Systems, 26, 2013.
Smith, A. and Thakurta, A. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems 26, 2013.
Gyorgy, A., Linder, T., and Lugosi, G. Efficient tracking of large classes of experts. IEEE Transactions Informa- tion Theory, 58(11):6709-6725 2012.
Vovk, V. Derandomizing stochastic prediction strategies. In Proceedings of the tenth annual conference on Computa- tional learning theory, pp. 32-44, 1997.
Hall, E. and Willett, R. Dynamical models and tracking regret in online convex programming. In International Conference on Machine Learning, pp. 579-587. PMLR, 2013.
Wei, C.-Y., Hong, Y.TT., and Lu, C.-J. Tracking the best ex- pert in non-stationary stochastic environments. Advances in neural information processing systems, 29, 2016.
Hazan, E. and Seshadhri, C. Adaptive algorithms for online decision problems. In Electronic colloquium on compula- tional complexity (ECCC), volume 14, 2007.
Zhang, L., Lu, S.,, and Zhou, Z.-H. Adaptive online learning in dynamic environments. Advances in neural informa- tion processing systems, 31, 2018.
Herbster, M. and Warmuth, M. K. Tracking the best expert. Machine learning, 32(2):151-178; 1998.
Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928 936, 2003,
Herbster, M. and Warmuth, M. K. Tracking the best linear predictor. Journal of Machine Learning Research, 1(281- 309):10-1162, 2001.
10

---

Tracking the Best Expert Privately
A. Privacy Properties
Lemma A.1 (Basic Composition (Corollary 3.15 in (Dwork et al., 2014))). Let X, V1 ",,..., be arbitrary sets and N. Let A2, ..... Ar be a sequence of randomized algorithms where A X + Y1 and A, : V1-1."" X" + Ve for all 2.,....,T. If for every t [T] and every V1:1-1 E V1 x 3/2
1, we have that A x Vr, defined
E-diiferrntiialy private, then the overall algorithm A X + 311 x 322
A(rim)) (Ai(z11m)) (I1sm) T1
AT (1 A2(A1 (1::)), ...,, ;1m))...,,1:.)
satisfies ET -d-differential privacy.
Lemma A.2 (Basic Composition (Corollary 3.15 in (Dwork et al., 2014))). Let 2,,,,,/,, ...,..,,. ,T be urbilrary sets and E N. Let A2, .... Ar be a sequence of randomized algorithms where A1 X + Y1 and Ae Vi.... Vi-1, 2 + V4. for all = 2.3..... ,T If for every t E [T] and every V1:-11 1 E V1 x 3/2 x ... x V 1, we have that A Ao( is E--iiferentially private, then the overall algorithm A: X + 31 x V/2 x ... x Vr, defined as
A(rI.)) = A2 2 ( A2 (2)m)) 21,) 211))
satisfies TT --differential privacy.
Lemma A.3 (Advanced Composition (Dwork et al., 2010b; Kairouz et al., 2015)). Let X, (0......... Yr be arbi-
trary sets and N. Let AI, AT be a sequence of randomized algorithms where Ai x 7 V1 and
A Di,...,Yi-111 X + for all 2,3..... ...,, T. ffr every t E [T] and every yıa-1 E 31 3/2
x),-1, ,. we have
that A is E, d-ifferrnntillly private, then for every 8' >> 0, the overall algorithm A X + V1 x 3/2 x Vr. defined as
A(rum) = (Ai Ao slmm) A 21:)), .... x klm))
satisfies (E', 82) d'dddffferential privacy, where
T
T
3
1 8
2
+
E
log
2
Post-processing and group privacy will also be useful.
Lemma A.4 (Post Processing (Proposition 2.1 in (Dwork et al., 2014))). Let X,Y, Z be arbitrary sets and n E N. Let A: n > y and B: y + 2 be randomized algorithms. If A is (c, ddifferrrrey private then the composed algorithm
A A: x + Z is also (s, -1iffffrrrett private.
B. Missing Proofs for Section 3
B.1. Proof of Theorem 3.1
The proof of Theorem 3.1 is based on the following two lemmas. The first lemma concentration result which shows that the average loss of each expert in each sub-interval is close to its expectation.
Lemma B.1. Let .1,...,eT [N] + [0, 1] be sampled i.i.d. from distribution P. Then with probability 1 - 3, for all j E [N], t E [T] and w E [T t).
40) WKE- [(()) 2w log(TN/B).
The second lemma proves that the static regret of the algorithm with respect to the population minimizer is small.
Lemma B.2. Let fi....,4 ly [N] + [0, 1] be sampled i.i.d. from distribution P. Then, with probability 1 3, that for all E [T] and w E [T t]
16 1olo(NNT/) (NT/3) log(T) + 7 w log (TN/B)
4.1 - min B((()] Σ
<
JENN

---

Tracking the Best Expert Privately
Building on Lemma B.I and Lemma B.2, we now proceed to prove Theorem 3.1.
Proof. (of Theorem 3.1)
The privacy follows immediately from the guarantees of the report-noisy- max mechanism (Lemma 2.3): indeed, the algorithm uses the data only through the invocation of the report-noisy-mat algorithm. Moreover, note that each data-point & is used single instantiation the report-noisy-me mechanism.
Now we proceed to prove utility. Using Lemma B.1 and Lemma B.2, we have
++
++
Σ 4(j))
min
Σ 40) =
Σ & w min
B[EG)]] +
w min B(e()]
min
Σ e,())
JE 2
SE[M]
JEIN]
jE[N]
xmt
16 lollo( 33) log
14
TV w (ogg3(/(333))) + max NE|N
wB[(()] - Σ 4(()
1=0
16 log( ( log (T)
9 w log(N/8),
where the second inequality follows Lemma B.2 and the third incquality follows from Lemma B.I.
Now, it remains to prove our two lemmas. We begin with the proof of Lemma B.1.
Proof. (of Lemma B. Fix j E [N]. / E (7). and w E [T- - 4). Since 4(j) E [0, 1], Hoeffding's inequality [(Duchi, 2019),
Corollary 4.1.10] implies that
1+110
B TEN
P
Σ
40) - wLEs))(((i)] > 2w log((N/11
Taking union bound over all j, t, proves the claim.
Finally, we prove Lemma B.2.
Proof. (of Lemma B.2) First, concentration of Laplace random variables [(Dwork & Roth, 2014), Fact 3.7] implics that [Z)(j)) $ //)g(NT/ for all j E [N] and with probability least B. Let j* arg minje[N] B({(j). Then, Lemma B.1 implies that for all = 2f, we have
4(J + /log(TN//B)
Ee-p(e(ie)
Σ
(t/2)
1/2
i=/2
2 (T
< (t/2)
Σ 4(j*) +(())) Z((ti) -z(ii)
+
Vi
1=1/2
8 (log(NT/B)
2Vlog(TN/B)
(t/2)
to
Vi
1=//2
8 (lgg(N))3) Aoog(TN/B)
{E<p((((")]]
Vi
where the second inequality follows from the definition of je in the algorithm. Based on the lazy structure of the algorithm. this implies that for all t (T).
16 (og(NT/8)
4 4/2log(TN/B)
ExP p((..) < p[(-)]
18
Vi
12

---

Tracking the Best Expert Privately
Now, we get that
Σ 4(i)) - min B((()
&
Σ 2(5.)
B[(G))]
+
Σ
B(GGAD]
min BI(G))
MEIM
JE(M]
1=t
i=to
Av Ao2log(TN/3) 16 16Tog(NT/3)
4(i)) E(((A:))
vl
16 log NT/3) log
4Gi)) E[(())]
6
For the first term, note that for W; = (,()) - E(e(i)), the sequence
} is bounded difference martingale. We can use
Azuma's inequality [(Duchi, 2019), Corollary 4.2.4] to get that
P
Σ
4Gi) - > v Wolg(11/)) 33
This proves the claim.
B.2. Proof of Theorem 3.2
For our analysis, we build on the following two lemmas. The first shows that if SVT identifies an above threshold query, then there must have been distribution shift with high probability.
Lemma B.3, Fix Then there is a distribution shift in the range [t,, t++1] with probability 1 2,8.
Proof. Assume towards a contradiction that there is no distribution shift in the range [t,, tt-]. Based on Theorem 3.1, we know that Algorithm had near-optimal adaptive regret if the distribution does not change, that is, for all w S f.41 1 we have
Σ 4+1-
4G)
min JE[N]
Σ
4.)) - Reg..
f++1 8
However, as SVT identifies an above threshold query time 1,+1, the guarantee of SVT (Lemma 2.4) imply that there < 4+1 such that qh -a, implying that
f Σ
Σ
lali)
min JE[N] t.+1
405) 2 Reg,.. + 1.
Therefore, get contradiction.
Our second lemma shows that long SVT did not identify above threshold query, the adaptive regret of the internal algorithm will be small. Lemma B.4. Fix and let 14 1/2 E [li, 4+41 - 1]. Letting w = 1/2 C1. we have with probability 1 - B
(a(i))
min JE(N]
(() Reg.. + 2a 1.
Proof. Note that SVT did not identify above threshold query at time tyy; otherwise would have = t,+1. Therefore, setting w t/2 f,. the guarantees of the SVT mechanism for the query qui imply that qui S and therefore
a(ii))
min JE(N]
4() Reg.. 2a 1.
This proves the claim.
13

---

Tracking the Best Expert Privately
Now are ready to prove Theorem 3.2.
The privacy proof follows directly from the guarantees of SVT mechanism and Algorithm 1, each user is used in the instantiation of both Algorithm and SVT with parameters e/2.
Now we proceed to prove utility. Based on Lemma B.3, for a shifting stochastic adversary with S shifts, the algorithm restarts its internal procedure at most & 8 times. Let ti,...,ty denote these times. Note that the dynamic regret the algorithm
T Eut + j4n1 SS $
max 1 5 11.0f
Σ 10014400
465 - 4((7)
t=1
t=4
1it + J J be the number of switches in { that the adversary makes inside the range [t,, 1.41 We will prove that for all i with high probability
Let L; 441 and Eimt
(16log(NT/3) (1
40i)) 401) < + 1)L, ()) (S; +)
2a +1)
(I)
Using inequality (1), we prove the theorem. Indeed, get that the dynamic regret is upper bounded by
T
$ 4+1
Σ -10-) = ΣΣ ((+)) (e(it)
1=1 t=1,
166 (16)) log(T)
(S: V(S 11)4 1) (S,
+ 22
E
$
16 (olog(NN/)) B) log(T) + 2a +
9
Σ (8, + 11 log(TNN/3)
L, + 28
1=1
1=1
(olog(NN//B)) log (T)
< 99/2ST log logg + 2S
+ +2a +
(B)[NT/B)
0o (oSooog(T// S
where the last inequality follows since 16(2 log (2g8())))) It remains prove inequality (1). We fix i without loss
of generality. Let .i....,fs. Es, [ti, te] denote the switching times of the sequence of experts {jtt inside the range [t tz]. and let -f, Ji,s, denote the set of different experts in this range. Using Lemma B.4, get
42 Σ 4(1 - (+(t)
8
Σ
4(11) (((T..)
81+1 fa
9 (Te41 - (,) + 16 loggNTT33) log(T')
<
Σ
+ 2a + 1
( (Nog) log(T) 2a + +1)
(66 (16log(NT))
< 9 S + 1V (t2 - (1) log(TN/B)) (S1 + 1)
This proves that with probability (VST ST log(TN/33) + Slog(T N/8) log(T)
- -B we have that the dynamic regret upper bounded by Picking B = 1/T gives the upper bound on expectation as the dy-
namic regret is always bounded by T'
C. Proof of Theorem 5.2
We first review a folklore result which states that for online learning algorithms which do not depend on the realizations of its past plays, expected regret under adaptive adversaries is at most the expected regret under oblivious adversaries.
14

---

Tracking the Best Expert Privately
Theorem C.I (Exercise 4.1 in Cesa- Bianchi & Lugosi (2006)). Let A: ((0, 1 + A[[N]) be any (randomized) online learning algorithm which maps sequence loss vectors distribution over experts. That is, for any sequence loss functions . &T, the prediction of A on round E [T] only depends on the loss vectors .1...., Lt-1. Then,
ada (T S RA (T,
As consequence of Theorem C.1 and the fact that distributions constructed by Algorithm 3 do not depend on the realizations of it past plays, it is without loss of generality consider oblivious dynamic adversary.
To that end, we first prove the following result.
Theorem C.2. Fix sequence of loss functions li,.... er. Algorithm 3, when run with e, > 0 is e-differentially private and satisfies
T Σ (J...
=0(1los'(
yglog" (yTo) T
Slog(NT)
S (log(NT)
E
min (IrEC(T,S))
Σ (((ie) <0
22
"
The following lemma about Laplace vectors will be useful. Lemma C.3 (Norms of Laplace Vectors (Fact C.I in (Agarwal & Singh, 2017b))). If Zi.... Zx (Lap(A)) then
P(3 E [T] 1 2 10x log (NT)) S T
We equipped to prove Theorem C.2. Our proof of utility will closely follow Theorem in Lu & Zhang (2019) but account for the fact that the loss vectors used to update the algorithm now contain large negative entries.
Proof. (of utility in Theorem C.2). Let l,...., lr be the sequence of losses chosen by the oblivious adversary. Let be the sequence of Laplace random vectors sampled in Line 6 of Algorithm 3. Observe that Z, (Laplace(!))
Zr 7.....,
for all / E [T]. Let F be the event that there exists at E [T] such that | 2 (NT)) Then, by Lemma C.3, we know that P(F) < #.
Fix any sequence of experts ju. E C(T,S). Observe that
T
T -
(J))
&OOLEE ST.
Hence, we have that
T
T Σ 1=1
E
(JJ.)
((ii))
< E Σ 4JJ) - F400) pC +1. 1
Using the facts that E [Z = 0, the randomness in Z, is independent of that of Algorithm 3, and Jr, being a function of only the past loss vectors E,, 11..... 1 is independent of Zt, we have that
T
T
E
Σ
(J..)
Σ (G))
=
Σ (J.))
> F..
now suffices to upper bound E
Σ (.(J)) - -t, &00) To do so, we follow the proof of Theorem Lu
Zhang (2019) and modify it where necessary to account for the fact that |lêelloo S 4loo under the event F Let R C [T - 1] be the subset of time points such that for every E R, we have that je+1 * Je. Note that R| S S by definition. Split [T] into [R] + disjoint intervals [i,, i2),...............). [1 111+2) with i and i|Rl+2 T 1 such that for every
15

---

Tracking the Best Expert Privately
E [ + 1J, we have that Jr, Js,+1 +1
-1-1-1- Fix [|/2] 1J. note that the expected regret in the s'tl th
interval is
1+41-1
E
(wr, E,) - E((it) FC
Define the one-hot vectors G1, Cr such that
= 1
Then, we can write
E
(we, Ee)
Pe(ie)
pe
=
Σ
(we cc. Ri) pr
(2)
1=
Further define è E AN such that
8 ) +
ēt(): =
NT
Decompose the right hand side of Equation (2) as
T++1 1
b -1
E
(we c2, Ei) FC = E
(w) ē, Ee)
F
+ E
Σ
(ē)
c,, Ex) FC
t
Using Holder's inequality and the fact that |1Ealloo <
4log NT
we can bound
45log NT
(ē. - (c) S lēe - eellal16/ S
Plugging this in, then have that
R b0+1
4$ log NT
(J.))
Σ ((i pd
E
Σ
(wo ēx Ec) Fc
8
Decompose (w,- - Ł, [v) as
(wi - éq Ee) = (w) w Ea) + (wi+1 - 2x, Ee)
By the proof of Lemma in Lu & Zhang (2019), we have that
(w) wet1, (e) S n11eel12..
Thus, under event FS, we have that
10n log NT
(w) - w(+1 81)
22
16

---

Tracking the Best Expert Privately
Thus, can write
T Σ (
10nT NT
4,5 4og N7
E Σ (JJ)
S
(w041 - Ee, E,, F
g²
8
and it suffices to bound the first term on the right hand side. We can do so by following the same steps as Page 17-18 of Lu & Zhang (2019). Namely, under the event F", define convex function on the clipped simplex:
(w, nli) (=
Do(w(lue).
The update rule in Algorithm 3 can now be written as:
W++1 = arg min (w).
weÂv
By first order optimality, we have that
(we+1 ēe, vf(w++1) S O.
This gives us that
n/wt+1 Ee, R.) S (ē: W1+1, Vo(wer) Vo(w:)).
Thus, we can write
1
(Wi+1 E,) <
(é,. - - (ww)) - (wi+1. volwe+1) Vo(w:))
"
17
" (ēr. vo(w++1) vo(w)) 1 DD((w+1llue)
"1
$ (E,. Vo(w++1) vo(w))-
The first equality by definition of the Bregman divergence and the last inequality is due the fact that Bregman divergence is always non-negative. Summing over the interval, we have that
++
641-1
(we+1 - 2t, 2c, Fd
(2,, vo(wE+1) - vo(w)))
t=
t=
(e Vo(wi...) volw,,))
1)
N
Wi,1 (j)
E, (j)
log
wi (i)
j=1
N
NT
ē, log
1 J=1
5
log NT
Y
17

---

Tracking the Best Expert Privately
Thus, overall, have that
T
T
(RR)
log NT
10yT NT
4S 4olog NT
E
Σ ((J))
Σ
pC <
"
1=1
25 log NT
10nT log' NT
48 1ologNT NT
To complete the proof, recall that
T
T
(J))
Σ
4lit)
SE E
Σ
(J,)
Σ
Fe
+
1=1
1=1
and hence
E
((J))
Σ
4(i
25 log NT
10t/ log" NT
4$ log NT
+
22
The upper bound in Theorem 5.2 follows after picking 7) = =VV (Tg((N))
Proof. (of privacy in Theorem C.2) Let f1...., br and ...... fr be two sequences of neighboring loss vectors. Suppose they differ at time step t'. Observe that the plays of Algorithm are a post-processing of the noisy losses f...... . & and ....... Ey. The distribution of the noisy losses between the two neighboring sequences remained unchanged except on round f. However, since each loss vector has sensitivity by the Laplace mechanism and Lemma 2.2, we know that the output distribution for the noisy loss vector in round t' is e-differentially private. Thus, the overall algorithm is also e-differentially private.
Theorem 5.2 in the main text follows by composing Theorem C.1 and Theorem C.2.
D. Proof of Theorem 5.1
Before we prove Theorem 5.1, we recap the lower bound from Asi et al. (2023b).
Proposition D.1 (Lower bound on Expected Regret for Adaptive Adversaries (Asi et al., 2023b)). Let T be sufficiently large and N 2 2T. Let e < 1 and ō I H If A is (e, diffferrentll private, then
adep (T.N) 12 min (T.
log T)
As mentioned in the preliminaries, an adaptive adversary for A for time horizon T' is simply sequence of functions fi, fe.....ff fr such that at time point t E [T], the function ft [N] x [N]-1 + [0. 1] maps the past plays of the learning [0, 1j Likewise, an online learning algorithm A for time horizon T a function ([0, 1 [N])* - AN. which at time point E [T]. takes the past loss vectors f 4--1, own past plays Jt....,J--1 and outputs a distribution AN. We will use these representations of adaptive adversary and algorithm to prove lower bound on expected dynamic regret for adaptive adversaries.
algorithm Jj,.... J to a loss vector [e(;;J1::
Proof. (of Theorem 5.1) Fix $ 2 0 and suppose without loss of generality that S divides T. Let T' T Lete S and 8 = 3 Let A be any (s, difffernntt private online learning algorithm. Then, by Proposition D.I, there exists a sequence functions f1. f2....; fr such that
541
18

---

Tracking the Best Expert Privately
2 min (T' (elog T'y2 ))
A
E Esb ][E[N]
min
where Jr is the random variables denoting the prediction of A on round E [T]. However, now observe that we can use Proposition D.I again starting on round = T + with respect to the new internal state of A on round f + after fixing .I...., Jrr That is, by fixing JI,..., JT,, the algorithm A induces a new online learning algorithm. A [001] [N])* + AN such that on input (41. (bxs (10, 1] [N])* we have that
i (n): = A((S())) JT). (12 (1)
J...... (1T
(Ln: in)).
By post-processing, we have that Á is also (e, differeefrlllltiallly private. Note that Á random as is a function of JI..... Jr. Nevertheless, Proposition D.1 guarantees the existence of sequence of functions fI, fe...... fi for A such that
2T
2T
Tog ))
E A
Σ 71
T T (Jr, JT min
Σ [] 41
fi-r JT Jr 2 Ω min T
where now JT.+1..... .... J2T the random variables denoting the prediction of A. Recall that f1, f2..... ..... fri is function of the realized values of Ji...., Jr and hence are fixed once one specifies JJ..... Jr.. Jr. Thus, we can define fr+41..... f2r such that for every E [ 1 2 and any j1:-1 E [N]'-1, we have that fe(:)11e-1) == f--r (+ f1+4111),, where J2, ST is the aforementioned strategy of the adversary when one fixes J1 = j1,..., JT = fr. Now, observe that fr--1..... fer are not random and can be computed by the adversary before the game begins. Moreover, by construction, we have that
EA
Σ
2
Σ
fe(J,,
min
Σ
2
Σ
T
2 20(2min
(22min min (T', (E log Tyyz (e
(
Farr EC(2T',
(1---))7++1
Repeating this same argument S times gives a sequence of functions f1, fa..... fr, defining the strategy of the adaptive adversary, such that
S+1
T Σ
EA
Σ
min Hi EC(TS) s= ((1-1)]++
Σ
Σ
flli, J1a-1)
> Ω (S (S 1)min
T''
(Elog Tr)2
==1
(1
S
= min
T,
(elog s-1 )2
This completes the proof.
19


Reviews:
[{"review_id": "s3f17ieaGf", "reviewer": "Reviewer_8ayK", "summary": "This paper studies differentially private online learning in the context of tracking the best expert, a problem where an algorithm dynamically selects from a set of experts to minimize cumulative loss over time. The authors develop differentially private algorithms for this problem under three types of adversaries: Shifting Stochastic Adversaries, where the data distribution changes up to S times;Oblivious Adversaries, which determine loss sequences independently of the algorithm. Adaptive Adversaries, which choose loss sequences based on the learner’s decisions. The paper provides upper and lower bounds on the dynamic regret of private algorithms in these settings and highlights fundamental limitations when learning privately against adaptive adversaries.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address their concerns below and hope they will reevaluate their score accordingly. \n\n> Is it possible to design an efficient algorithm that attains same-order regret bounds in this setting?\n\nThis is a good question and an important direction of future work. First, we note that despite its inefficiency, this result is important on its own because *it is the first known upper bound for oblivious adversaries and it establishes a separation in the achievable rates between oblivious and adaptive adversaries*. Unfortunately, our current attempts at designing efficient private algorithms against oblivious adversaries have been unsuccessful, as it is not clear how to privatize existing efficient non-private algorithms for dynamic regret. Perhaps central to the difficulty is the tension between lazy updating and obtaining small dynamic regret. Existing techniques for obtaining private online learning algorithms under static regret rely on privatizing existing (non-private) lazy algorithms that do not switch their played experts too often [1, 2]. Unfortunately, it is reasonable that such lazy algorithms cannot obtain good dynamic regret, as switching which expert is played is crucial to ``tracking\" the best expert. We will make sure to add a discussion of this in the camera-ready version.  \n\nThat said, we do note that our algorithm against adaptive adversaries is efficient and also gives guarantees in the oblivious settings. \n\n[1] Asi, Hilal, et al. \"Private Online Learning via Lazy Algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 112158-112183.\n\n[2] Asi, Hilal, et al. \"Private online prediction from experts: Separations and faster rates.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.", "claims_and_evidence": "The claim presented in this paper appears to be clear and correct.", "methods_and_evaluation_criteria": "The privacy and utility guarantees of the algorithms have been rigorously proven.", "theoretical_claims": "The proof appears to be correct.", "experimental_designs_or_analyses": "Not applicable; the proof appears to be correct.", "relation_to_broader_scientific_literature": "The paper contributes to differential privacy and online learning.", "essential_references_not_discussed": "The paper appears to have sufficient references.", "other_strengths_and_weaknesses": "Strength:\n* The authors provide algorithms for three types of adversaries: shifting stochastic, oblivious, and adaptive.\n* The results for each setting are equipped with upper and lower bounds.\n\n\nWeakness:\n* The algorithm for the oblivious adversary setting is not computationally efficient, as it relies on maintaining an exponentially large set of meta-experts.", "other_comments_or_suggestions": "The paper is clearly written and well-structured. I don't have other comments.", "questions_for_authors": "The algorithm for oblivious adversaries is not computationally efficient and requires an exponential number of meta-experts. Is it possible to design an efficient algorithm that attains same-order regret bounds in this setting?\n\n## update after rebuttal\nSince my question has been answered, I will keep my positive score and vote to accept.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vUnRtBj7EP", "reviewer": "Reviewer_fdak", "summary": "The paper studies the dynamic regret in online learning with differential privacy. The paper considers three adversaries: shifting distributions, oblivious, and adaptive. This paper provides both lower bound and upper bound for three different adversaries. Finally, similar to static regret, This paper establishes a fundamental separation between oblivious and adaptive adversaries for the dynamic setting.\n\n## update after rebuttal\nI maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly. \n\n> Authors may give details of the proof for differential privacy of algorithms...\n\nWe will make sure to include theorems about basic privacy mechanisms and their privacy/utility guarantees in the camera-ready version. That said, we do prove the privacy guarantees for all our algorithms.  For example, on lines 332-334 in the right column, we provide the proof of the privacy guarantee in Theorem 4.1. Similar privacy proofs for the other Theorems can be found in the Appendix. \n\n> Authors may provide experiments\n\nThis paper is theoretical in nature as we aim at rigorously understanding fundamental limits in the context of dynamic regret minimization. While empirical validation can be valuable, our contributions stand independently as theoretical results that advance understanding in this area. Future work may explore experimental verification, but our primary goal here is to establish a solid theoretical foundation.\n\n> (Q1) Can these results be extended to the bandit setting?\n\nYes, we do think that some of these results can be extended to the bandit setting, especially the results for stochastic and adaptive adversaries. With regards to oblivious adversaries, more care needs to be taken as one often uses unbiased estimates of the true loss under bandit feedback. This can cause issues in the privacy analysis as the sensitivity of the unbiased estimator can be large. \n\n> (Q2) Is this a typo...\n\nYes, we thank the reviewer for catching this typo. We will make sure to fix it in the camera-ready version.", "claims_and_evidence": "In general, the claims are supported by sufficient evidence. The theoretical results seem sound, even though I could not understand all the proofs related to the privacy of algorithms.", "methods_and_evaluation_criteria": "The performance measure, the Dynamic regret and $\\varepsilon$-differentially private, makes sense as it is the measure that is studied in the most similar works.", "theoretical_claims": "I checked the general soundness and read a small part of the proofs, but I couldn’t read all of them given the length of the supplementary material.", "experimental_designs_or_analyses": "The paper does not include experiments.", "relation_to_broader_scientific_literature": "This paper is the first to systematically incorporate dynamic regret minimization into private online learning, bridging an important gap. Previous research on private online learning had largely focused on the static regret case.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1. By handling shifting stochastic, oblivious, and adaptive adversaries, the authors offer a comprehensive picture, including how much privacy “costs” in each scenario.\n2. The paper provides both upper bound and lower bound for dynamic regret in private online learning settings.\n\nWeaknesses:\n1. Authors may give details of the proof for differential privacy of algorithms. For example, post-processing is a crucial step in demonstrating an algorithm’s privacy. Please either include a relevant theorem in the paper or cite papers.\n2. Authors may provide experiments.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Can these results be extended to the bandit setting?\n2. Is this a typo: 283-284: arg max -> arg min?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OFa3LbJSRL", "reviewer": "Reviewer_QJL2", "summary": "This work studies the online private learning problem, in the setting of online prediction with experts. The main focus is the relaxed notion of dynamic regret, where the best expert of the baseline can change at most S times. The main result considers three different models of the adversary: shifting stochastic, oblivious and adaptive. For all three settings author prove upper bounds and show lower bounds in shifting stochastic and adaptive regimes. The latter indicates a separation between oblivious and adaptive online learning.\n\nThe paper uses different proof techniques: SVT-based algorithm for shifting adversary, reduction from static regret for oblivious adversary and privatization of non-private dynamic regret algorithm for adaptive adversary. For the lower bounds, authors reduce existing lower bounds for static regret.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and finding our techniques to be broad and interesting. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly. \n\n> Computational inefficiency\n\nThis is a good question and an important direction of future work. First, we note that despite its inefficiency, this result is important on its own because *it is the first known upper bound for oblivious adversaries and it establishes a separation in the achievable rates between oblivious and adaptive adversaries*. Unfortunately, our current attempts at designing efficiency private algorithms against oblivious adversaries have been unsuccessful, as it is not clear how to privatize existing efficient non-private algorithms for dynamic regret. Perhaps central to the difficulty is the tension between lazy updating and obtaining small dynamic regret. Existing techniques for obtaining private online learning algorithms under static regret rely on privatizing existing (non-private) lazy algorithms that do not switch their played experts too often [1, 2]. Unfortunately, it is reasonable that such lazy algorithms cannot obtain good dynamic regret, as switching which expert is played is crucial to ``tracking\" the best expert. We will make sure to add a discussion of this in the camera-ready version.  \n\nThat said, we do note that our algorithm against adaptive adversaries is efficient and also gives guarantees in the oblivious settings. \n\n[1] Asi, Hilal, et al. \"Private Online Learning via Lazy Algorithms.\" Advances in Neural Information Processing Systems 37 (2024): 112158-112183.\n\n[2] Asi, Hilal, et al. \"Private online prediction from experts: Separations and faster rates.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n> Tightness of the result for oblivious and adaptive adversary\n\nThis is an important point of our work and we will clarify it in our final version. First, note that our bounds for oblivious adversaries are not tight as can be seen from Table 1 in the paper. As for adaptive adversaries, the bounds are tight in the following sense. Assume we ask the question of what is the best privacy (smallest $\\varepsilon$) we can guarantee while being able to learn anything useful (e.g. obtain sublinear regret)? Our upper and lower bounds provide tight answer for this question: indeed, the lower bound implies that sublinear regret requires $\\varepsilon = \\Omega(\\sqrt{S/T})$ and our upper bound (theorem 5.2) shows that the dynamic regret is sublinear whenever $\\varepsilon = \\Omega(\\sqrt{S/T})$. This shows that our setting has $\\varepsilon \\ge \\sqrt{S/T}$ as a fundamental threshold for learning. \n\n> Comments about lack of clarity and typos\n\nWe will fix these comments in the final version. More specifically, we will add the missing $\\log(T)$ factor in theorem 3.1 and rewrite Lemma A.3 more clearly. We will also revise Section 2 by removing comments regarding ``abuse of notation\" and be more explicit with our definitions. \n\n>  $\\log(N/S) \\gg \\log(N)$\"\n\nThe reviewer is right. When we wrote that $S \\ll N$, we meant that $S$ is actually polynomial smaller than $N$ in the sense that $S = O(N^{1-\\delta})$. We will clarify this in the final version.\n\n> (Q1) Extension of the lower bound of  (Asi et al., 2024)\n\nThe family or algorithms used in the lower bound proof of (Asi et al. 2024) are those that are lazy, in the sense that they do not switch their played expert frequently. While this is suitable for static regret, for dynamic regret, we do want to switch experts since we are competing with a sequence of switching experts. That said, it could be extended, but it would likely not be as meaningful. \n\n> (Q2) Small $N$ regime \n\nOur focus in this work was on the high-dimensional regime where $N$ is large. However, we agree with the reviewer and believe the small $N$ regime is also of interest. Our algorithms work in that setting but are probably sub-optimal. Similarly to the static regret setting, we believe that versions on the binary tree mechanism are going to be optimal for small $N$. These algorithms usually have a worse dependence on $N$ ($N$ instead of $\\log N$) but a much better dependence on $T$. We leave this question for future research.\n\n\n> (Q3) what is $j_t$ in Lemma A.2?\n\nLemma A.2 proves certain properties about Algorithm 1 and uses notation from that algorithm ($j_t$ was defined in Algorithm 1). We will clarify this in the paper.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Line 309, right column: it is claimed that when $S \\ll N$, we have that $\\log (N / S) = \\Omega (\\log N)$, which is not true generally. Consider, e.g., $N = S \\log S \\gg S$, but $\\log N / S = \\log \\log S \\ll \\log N$.", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "This work extends the literature on private online learning. Results connect private online learning with static regret to dynamic regret formulation. Authors use three different techniques of establishing upper bounds in this setting.", "essential_references_not_discussed": "Not to the best of my knowledge.", "other_strengths_and_weaknesses": "Strengths: The techniques used for providing upper bounds are broad and interesting. The result for the shifting adversary is nearly-optimal.\n\nWeaknesses:\n1. Upper bound for oblivious adversary is computationally inefficient.\n2. It is hard to understand the tightness of the result for oblivious and adaptive adversary.", "other_comments_or_suggestions": "1. In Theorem 3.1, there should be additional $\\log T$ factor in the first term.\n2. Section 2 is not clearly written, ‘abuse of notation’ mentioned 3 times on the same page.\n3. Formulation of Lemma A.3 is unclear, please rewrite.", "questions_for_authors": "1. Lower bound for oblivious adversary is the same as the shifting stochastic one. However, authors use the result of (Asi et al., 2024) to prove upper bound for oblivious adversary. This paper also contains lower bound (for certain class of algorithms). Is this lower bound extendable to dynamic regret?\n2. Authors often assume 'high-dimensional' regime $T < N$ or $N > T/S$. I think there should be more discussion on what would change if $N$ is small.\n3. What is $j_t$ in Lemma A.2?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uCHgoIus4b", "reviewer": "Reviewer_Mg7a", "summary": "The authors develop differentially private algorithms for prediction with expert advice under dynamic regret (tracking the best expert) across three adversary types: stochastic with shifting distributions, oblivious, and adaptive. They achieve sub-linear regret bounds for all cases, notably providing explicit regret guarantees against shifting stochastic and oblivious adversaries.\n\n---After Rebuttal---\n---\nThe author fails to explain how to achieve sublinear dynamic regret in a very simple example even in the discussion stage. Consider the following 2 loss vectors when $S=1$: \n\n\n(a)  $l_t(1)=1-l_t(2) = 0$ for all $t<=T/2$;   $l_t(1)=1-l_t(2) = 1$ for all $t>T/2$;  \n\n(b)  $l_t(1)=1-l_t(2) = 1$ for all $t<=T/2$;   $l_t(1)=1-l_t(2) = 0$ for all $t>T/2$;  \n\nNote that, for each of these 2 loss vectors, we can find a sequence of $\\\\{j^*_t\\\\}$ suffering $0$ \"loss\".\n\n \nThen, since expert 1 and expert 2 are symmetric, we consider choosing expert 1 with at least 50% probability at $t=1$. Then the remaining strategy of the agent is to consider when to jump to expert 2. However, the problem is that if the agent jump to expert 2 before $t=T/2$, then the agent will inevitably suffer O(T) regret in the worst case after $t=T/2$  (i.e., in case (b)) . If the agent insists on staying in expert 1 before $t=T/2$, the agent will also suffer O(T) regret in the worst case (i.e., in cases (b) ) . \n\nSimilarly, we can get a similar conclusion if the agent chooses expert 2 with at least 50% probability at $t=1$ due to symmetry, and the worst case is case (a).\n\n**Therefore, I have every reason to believe that the theory of this article is wrong, and hence I adjust the score to 1 and will defend this decision unless someone can point out a logical loophole in the above.**\n\n(The authors can \"edit\" their own reply in the remaining rebuttal time to face this simple example directly instead of proposing an indirect answer to evade it.)\n\n---Update 2---\n---\n\nNow, I realize that the above example is not a counter-example because the agent can switch experts more than $S$ times. I believe the writing of the paper should be largely modified. Especially, many \"abuse of notation\" in the problem statement would confuse the reader. In line 162, the \"comparison sequence\" is very confusing without pre-definition.\nI will increase the score as long as I can see the detail plan for increasing the clarity of the paper.\n\n---Update 3---\n---\n\nThank you for the detailed response. I am looking forward to the revised version if accepted. I have increased the score to 3 as I promised, and this score is conditional on the author revising their paper as in their latest response.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address the reviewer's concerns and questions below and hope that they will reevaluate their score accordingly.\n\n> No experimental results\n\nWe acknowledge the reviewer’s concern regarding the lack of experiments. However, our work is intentionally theoretical, aimed at understanding fundamental rates and limits of private learning from experts. Theoretical contributions often provide key insights that guide future empirical research. While experimental validation is certainly valuable, we believe that our results are meaningful in their own right and align with the norms of theoretical research in this area.\n\n> There is a lot of work on adversarial bandit in the literature. The author should pick a typical algorithm, such as Exp3 [1], to explain why it can or cannot be adapted to the current setting of dynamic regret with DP.\n\nWe note that our work focuses on the setting of experts where we have *full-information* rather than the setting of bandits. There are many papers that study our problem (dynamic experts under *full-information* feedback) in the non-private setting which we discuss in our related work section. We will add a discussion on the challenges in privatizing these existing algorithms. We briefly mention one challenge here with regards to the modified multiplicative weights algorithm of (Lu and Zhang (2019)). Their algorithm basically applies the same update as multiplicative weights and then projects to the clipped simplex. Unfortunately, this clipping operation is challenging for privacy as now we have to privatize each gradient separately instead of privatizing the sum of gradients via the binary tree mechanism. We will discuss this more carefully in the final version.\n\nLu, Shiyin, and Lijun Zhang. \"Adaptive and efficient algorithms for tracking the best expert.\" arXiv preprint arXiv:1909.02187 (2019).\n\n> Motivation for dynamic regret\n\nDynamic regret is stronger notion than static regret that compares the performance of the algorithm to a sequence of changing experts (rather than a fixed expert). This is extremely important in scenarios where there is a distribution shift which results in a new optimal expert. For example, in recommendation systems, the user's preferences might change over time. \n\nTo highlight the importance of dynamic regret, lets consider the following example. Consider the setting of two experts, where the first $T/2$ losses are such that $\\ell_t(1) = 0$ and $\\ell_t(2)=1$, and for the last $T/2$ losses we have $\\ell_t(1) = 1$ and $\\ell_t(2) = 0$. For this sequence of losses, a simple algorithm that gets $0$ static regret is one that plays expert $1$ for all rounds. However, the dynamic regret of this algorithm is $T/2$ because the optimal strategy for dynamic regret would play expert $1$ for $T/2$ rounds before switching to expert $2$. For this sequence of losses, one can generalize this argument to the Multiplicative Weights (MW) algorithm, which would obtain sublinear static regret, but linear dynamic regret since MW would wait roughly $T/2 - \\sqrt{T}$ rounds before switching to expert $2$. This shows a scenario where an algorithm aimed at static regret suffers suboptimal dynamic regret. \n\n> Definition of dynamic regret\n\nAs for the reviewer's example and question about the definition, we first clarify that the definition of expected regret in Lines 145 to 152 is the definition of *static regret* which does not involve any switching. The definition for *dynamic regret* is provided in lines 175-181 and the constraint on the number of switches $S$ is made explicit in the definition of regret here. Note that our definition of dynamic regret  (lines 175 - 181) crucially relies on limiting the number of changes in the set of best experts we compare to ($S$ upper bounds this). Indeed, we mention in line 161 in the paper that \"To make the problem tractable, we constrain the comparison sequence of experts to have at most $S$ changes\". *This is crucial as otherwise we end up having linear regret, which is exactly what is happening in the reviewer's example.*\n\nWhen $S=0$, dynamic regret becomes equivalent to static regret since the sequence of comparison experts must consist of a single expert. When $S=1$, we allow to compare our algorithm to sequences of experts than change at most once, e.g. as in the example above, expert $1$ for the first $T/2$ rounds and expert $2$ for the last $T/2$ rounds. The larger $S$ is, the stronger is the notion of the regret. However, as $S$ becomes too large, it becomes hard to provide meaningful guarantees on the regret. \n\nWe will add more clarification and intuitions regarding the parameter $S$ and its importance for the dynamic setting in the introduction.", "claims_and_evidence": "The claims presented in this paper are strictly based on theoretical bounds; notably, the paper does not include any experimental validation to support these theoretical findings.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not check the correctness of any proofs.", "experimental_designs_or_analyses": "Notably, the paper does not include any experimental evaluation, which I consider to be a notable weakness.", "relation_to_broader_scientific_literature": "This paper investigates three distinct adversarial bandit frameworks with dynamic regret under differential privacy constraints: stochastic adversaries with shifting distributions, oblivious adversaries, and adaptive adversaries. By systematically addressing these settings and analyzing their dynamic regret, this work makes a comprehensive contribution to the research community.", "essential_references_not_discussed": "There is a lot of work on adversarial bandit in the literature. The author should pick a typical algorithm, such as Exp3 [1], to explain why it can or cannot be adapted to the current setting of dynamic regret with DP.\n\n[1] Part three of Bandit Algorithms, Tor Lattimore and Csaba Szepesv ́", "other_strengths_and_weaknesses": "Table 1 is particularly valuable as it clearly outlines the lower bounds for the three settings. Although the upper bounds achieved by the authors' algorithms do not yet match all of these lower bounds, the results offer important insights and guidance for future research directions.", "other_comments_or_suggestions": "See \"Questions For Authors\"", "questions_for_authors": "I find it difficult to gain intuitive insight into why dynamic regret is considered in this context. While static regret for adversarial bandits has been extensively studied in the literature, dynamic regret remains relatively under-explored. It would be helpful if the author could provide a clearer, more intuitive technical insight for analyzing dynamic regret, particularly highlighting scenarios where it may become suboptimal in terms of dynamic regret for the algorithms that aim at static regret.\n\nAdditionally, it would be very helpful to justify the technical insight if the authors can explain the following example: Let number of experts be 2. Let's consider a set $L=\\\\{0,1\\\\}^T$ that represents a set of loss functions. Particularly, for any $v \\in L$, it implies a sequence of loss functions (or say vectors) $\\mathcal{l}_t(1)=v_t$ and $\\mathcal{l}_t(2)=1-v_t$ for any $t=1,\\dots,T$.\n\nThen, it looks like no matter how your agent chooses each $J_t$ at each time $t$, the expected regret must be $O(T)$  in the worst case (i.e., in one of the loss vector of the above set $L$ ) . I understand that this may not be true due to the limitation of switching times $S$; however, your definition of expected regret in Lines 145 to 152 of the second column does not explicitly depend on $S$ (particularly for $j^*$). I believe this definition needs to be revised.\n\nCan the authors explain the above and write the intuition behind them in the Introduction section? I think this will greatly increase the readability of the paper. Especially explain the case when $S=0$ or $S=1$ in the above example.\n\n\nAlthough my current score is negative, I am very happy to increase my score if the author can satisfactorily address these questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of differentially private bandits under dynamic regret with up to S shifts. 
All reviewers agree that the paper is technically sound and is a nice addition to the literature, though no one is overly excited and the contributions are rather expected extensions than insightful new techniques.

For oblivious adversaries, the algorithm is computationally infeasible.
Another major limitation is the assumption that the number of switches is known a-piori to the learner. Most of the difficulty in the bandit literature with respect to S-switch regret has been in adapting to unknown S.
Decision: Accept (poster)