Prediction with Expert Advice under Local Differential Privacy
Authors: Ben Jacobsen
Kassem Fawaz
Venue: ICLR 2026 Poster (2026)
Keywords: privacy
differential privacy
online learning
online linear optimization
local differential privacy
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: Two locally-DP online learning algorithms that improve on the privacy and utility of the classical baseline at minimal cost.

Abstract: We study the classic problem of prediction with expert advice under the constraint of local differential privacy (LDP). In this context, we first show that a classical algorithm naturally satisfies LDP and then design two new algorithms that improve it: RW-AdaBatch and RW-Meta. For RW-AdaBatch, we exploit the limited-switching behavior induced by LDP to provide a novel form of privacy amplification that grows stronger on easier data, analogous to the shuffle model in offline learning. Drawing on the theory of random walks, we prove that this improvement carries essentially no utility cost. For RW-Meta, we develop a general method for privately selecting between experts that are themselves non-trivial learning algorithms, and we show that in the context of LDP this carries no extra privacy cost. In contrast, prior work has only considered data-independent experts. We also derive formal regret bounds that scale inversely with the degree of independence between experts. Our analysis is supplemented by evaluation on real-world data reported by hospitals during the COVID-19 pandemic; RW-Meta outperforms both the classical baseline and a state-of-the-art \textit{central} DP algorithm by 1.5-3$\times$ on the task of predicting which hospital will report the highest density of COVID patients each week.

Published as a conference paper at ICLR 2026
PREDICTION WITH EXPERT ADVICE UNDER LOCAL DIF- FERENTIAL PRIVACY
Ben Jacobsen
Kassem Fawaz
Department of Computer Sciences University of Wisconsin Madison bjacobsen 3@wisc edu
Department of Electrical and Computer Engineering University of Wisconsin Madison
k kfwazž wi sc. edu
ABSTRACT
We study the classic problem of prediction with expert advice under the constraint local differential privacy (LDP). In this context, we first show that a classical algorithm naturally satisfies LDP and then design two new algorithms that improve it: RW-AdaBatch and RW-Meta. For RW-AdaBatch, we exploit the limited- switching behavior induced by LDP to provide novel form of privacy amplification that grows stronger on easier data, analogous to the shuffle model in offline learning. Drawing on the theory of random walks, we prove that this improvement carries essentially no utility cost. For RW-Meta, we develop general method for privately selecting between experts that are themselves non-trivial learning algorithms,, and we show that in the context of LDP this carries no extra privacy cost. In contrast, prior work has only considered data-independent experts. We also derive formal regret bounds that scale inversely with the degree of independence between experts. Our analysis is supplemented by evaluation on real-world data reported by hospitals during the COVID-19 pandemic; RW-Meta outperforms both the classical baseline and a state-of-the central DP algorithm by 1.5-3x on the task of predicting which hospital will report the highest density of COVID patients each week.
INTRODUCTION
Many practical algorithmic and organizational problems, from routing data to allocating scarce resources, involve repeated predictions about the future state of system. Prediction from Expert Advice (Cesa- Basaa-Binnch & Lugosi 2006) is a flexible framework developed in the online learning literature that can be used model these problems
iterative game between a player and the environment: at each time step / = ,,...,77 T, the player receives suggestions from each of n 'experts' (which might correspond to literal human advisors, complex algorithms, static actions like "always do X"),, and must decide whose advice to follow. Nature then reveals a vector representing the gain associated with each expert's suggested action, and the player receives reward based on the action they actually took. The player's goal is to maximize their reward over the course of the entire game.
Our focus will be on privacy-critical instances of this problem where expert suggestions correspond to predictions about human behavior, such as medical diagnosis (Morino et al.] 2015), human mobility (Xu al.) 2015). residential energy usage Devaine al.] (2013) or public health (Altieri et al. (0211. The motivating concern is that if we optimize purely for accuracy in this context, then our algorithm might inadvertently leak sensitive data through outputs, similar to batch learning (Shokri al.) 2017 Carlini et al., (023). Here, 'data' refers to a sequence of vectors representing the gain of each possible action at a single time step, which are sensitive because they measure the accuracy of predictions about human behavior.
The algorithms that we study will all satisfy (non inon-interactive (Smith et al. 2017) local differential privacy (LDP) (Yang al. 2023); assume that noise is added to each gain vector before is shared, and our aim is to design new algorithms that use this noisy data as efficiently as possible. In contrast, prior works have almost exclusively approached this problem by designing algorithms that satisfy
It is more common to describe the problem in terms of minimizing loss. Using gain instead will be notationally convenient later on, and guarantees about one be converted to the other by flipping signs.

---

Published as a conference paper at ICLR 2026
central DP (CDP) J Jain et al. 2012 Thakurta & Smith 2013 Agarwal & Singh 2017 Kairouz et al. 2021 Asi et al. 2023). ). That is, they assume that sensitive data is shared freely with a trusted central curator, and investigate how the curator introduce noise into their analysis to protect privacy. We are interested in the local model because it eliminates the need for a trusted curator, which can better enable applications in highly-sensitive domains like those mentioned above. A secondary advantage of LDP that it is easy to implement in practice, requiring only the ability to sample independent randomness wherever data is generated, unlike approaches based on secure aggregation that generally require multiple rounds of interaction and/or the implementation of sophisticated cryptographic algorithms Damie al. (2025).
The first algorithm one might think of in this setting is to sum all of the noisy gain vectors seen so far and choose the expert that appears to have done the best historically. Indeed, this approach is implicit in [Agarwal & Singh (2017 4.1), and is actually identical to an earlier algorithm from the non-private literature by Devroye et al. (2013). The latter algorithm, which we refer to as RW-FTPL, (short for Random-Wall Follow-the-Perturbee-- Perturbed-Leader was designed to switch its prediction only small number times in expectation. This concept of limited switching motivated our first contribution:
Contribution 1: Stability under LDP. We prove Theorem 1 which provides tight and easily computable characterization of the switching behavior of RW-FTPL. This allows us to answer questions like "What is the largest integer B such that, with probability at least a, RW-FTPL will not change its prediction in the next B steps?". Using this tool, we propose a new algorithm, RW- AdaBatch, which modifies RW-FTPL to adaptively batch data together whenever we can guarantee with high probability this our predictions won't I change as a result.
RW-AdaBatch is fully invariant to permutations within certain (random, data-dependent) subse- quences of its input, and we develop novel proof techniques to show that this translates to amplified CDP guarantees for its outputs, la the local-to-centra amplification of the popular shuffle model Er lingsson et al. (0119). This privacy amplification naturally grows stronger when data is "easy" in the sense that there same output as RW-FTPL, at each time step with high probability, meaning that the only cost we pay for this privacy amplification a small multiplicative increase worst-case regret bounds that can be controlled as hyperparameter. The analytic lower bounds that we prove for the degree of amplification have no simple closed form, but they can be computed numerically. We visualize them in Figure I alongside empirical Monte Carlo simulations that validate their tightness.
clear best expert at some time step. By construction, it also produces the
Contribution 2: Private Learning in Dynamic Environments. In the non-pun con-private literature, 'experts" are often taken to themselves be non-trivial learning algorithms. But in a private context, there is an important gap between simply identifying the best expert (e.g. determining that M is a good model for the spread of a disease) and actually acting their advice (e.g. fitting M to historical data and using its predictions to allocate medical resources). When experts are data-dependent, the second step can itself violate privacy.
Prior work avoids this problem by implicitly assuming that experts are data-independent and therefore consume no privacy budget, but this significant limitation in practice. To overcome this limitation, we propose RW-Meta, which employs a highly-efficient noise-sharing scheme to both select between multiple data-dependent experts and act on their suggestions at no additional privacy cost beyond that of RW-FTPL. In section 4 we show that this can lead to dramatic improvements in practice, outperforming even CDP baselines by more than 1.5x on a prediction task involving data reported by hospitals during the COVID-19 pandemic. In [hheoemm 3] we prove formal regret bounds for RW-Meta with respect to the best-data-depender
expert. These bounds scale with the leading eigenvalue of a certain matrix related to the empirical covariance of the experts, which can be thought of as representing the difficulty of the learning task.
2 BACKGROUND AND RELATED WORK
2.1 RELATED WORK
The study of online learning with DP was initiated in 2010 by the papers of Dwork al. (2010) and Chan et al. (201T), which examined the problem of privately updating a single counter. Later work has gone on to apply their framework wide range of tasks, including more complicated
2

---

Published as a conference paper at ICLR 2026
Table 1:
Regret and privacy guarantees for our algorithms and prior work with T' time steps and experts. CDP, GCDP, and GLDP stand for central DP, Gaussian central DP and Gaussian local DP.
Algorithm
Privacy Guarantee
Asymptotic Regret
Regret Definition
Agarwal & Singh 2017
e, 5.6-CDP
/Tlog
Vn logt.9g
Best static action in hindsight
RW-FTPL (Dvrroye et al.
2013
H-GLDP
log
Best static action in hindsight
1
RW-AdaBatch with parameter or
GeGLDP; Amplified GCDP
log
Best static action hindsight
RW-Meta with m learners
H-GLDP
Tum log
Best learner in hindsight
statistics (Perrier al. 2018 Bolot et al., 2013) Wang al. 2021 ). online convex optimization Jain
jet al. 2012] Kairouz et al. 2021 Choquette- Chhue et al. 2023 3 2024), and the partial information (or
"bandit') setting (Thakurta & Smith [2013: Hannun et al. 2019 Azize & Basu 2024). Despite the
advantages of LDP described in the introduction, we are only aware of a single existing LDP experts
algorithm, by Gao et al. (024). While their work shares motivation with ours, the federated context
and stochastic adversaries they consider lead to substantial technical differences in our results.
2024) and Agarwal Singh (2017). Like us. [s. ct al. (2023) exploit the limited-switching behavior of a classical online
Within the central model, the works most similar ours are Asi et 2023
learning algorithm Po develop private experts algorithms. Their focus on the high-dimensional regime, where the gap between local and central DP is most pronounced (Edmonds et al. 20199] Duchi
ctt al. (2013). Their work has gone on to inspire a flurry of work establishing connections between privacy and limited switching for both the experts problem and online convex optimization (Asi et al.
2024 Agarwal et al. 2023a b). which our RW-AdaBatel algorithm contributes to.
In contemporancous work, Saha et al. (2025) extend Asi et al. (2233) to propose new algorithms for expert advice in dynamic environments, motivated by the same concerns that led us to design RW-Meta. The algorithm for oblivious adversaries in (ahaa et al. (225)) works by constructing exponentially large set of candidate experts to pass to the high- nigh-dimensional CDP algorithm of Asi et al. (2023). In contrast, the performance guarantees of RW-Meta smaller set of carefully chosen candidate experts, leading to qualitatively different notion of regret and linear (rather than exponential) runtime dependence issues, we do not include their algorithm in our empirical evaluation. Instead, our primary (CDP) baseline is the FTPL algorithm from Agarwal & Singh/ (2017). which remains state-of-the oo-the-artttttttt in the low-dimensional regime that we target, where 7' 2 n/e"
defined with respect
T. Because of these computational
2.2 PRELIMINARIES
Given vector E RR, we denote its ttth element with the subscript Uk, and its hthh smallest element using parentheses as in ((k). We use the term 'leader' to refer to the index of U(n). and the term "gap' to refer to the quantity ((n) ((n-))- For two random variables X and Y. we say that X is stochastically larger than Y. denoted X 2st Y. if for all we have P x 2 P|Y > x... We use and yp to denote the standard Gaussian CDF and PDF respectively.
We treat prediction with expert advice as a special case of online linear optimization (Abernethy et al. 2014). At each time step E (T), we choose an action xi from the action set X, which in our case the n--dimensional probability simplex. We then observe the gain vector Je E G S [0, 1)"h and receive reward (Ie, gt).. Static regret is defined as the difference between the total reward we ultimately receive and the reward of the best single action in hindsight, i.c. max Σr= - (Et.gt). Our utility analysis uses the oblivious adversary model, which means that gain vectors can take on arbitrary fixed values but can't 't depend on the realized values of the noise we add for privacy (but note that our LDP guarantees still hold even against adaptive adversaries (Denisov et al. 2022
Shrinking Dartboard, by Geulen et al. (010)) regularization--asal antecedent the perturhation-hased algorithm of Devroye 2013) that we build
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 RW-FTPL(Devroye et al., 2013)
Algorithm 2 RW-AdaBatch
Require: Noise scale 17, dimension n
Require: Scale 7,, dimension n, tolerance a
Sample G ~ (O, In)
Sample G ~ -O( (0,,7 IT)
for t = ,,..,, do
Initialize empty buffer, set delay to for t = ,, do
Play z; arg m (2: G)
Get gt (g,, In) (Unobserved) receive reward (rt, 9t) Update G + G+
Play x; = arg max,ex (2, G)
Get g: ~ (g. (gg..1 nf and add to buffer (Unobserved) receive reward (24,, 9t) if delay is O then
Move data from buffer to G Set new delay using Corollary
else
Decrement delay
To define privacy, we say that two sequences of gain vectors 92.......... and I1. 92..... ........ Ir are adjacent if there is at most one index such that 9: * g/- randomized mechanism M is said to satisfy central DP (CDP) (Dwork et al. 2014) if for for all adjacent sequence g, g'. the distributions of M(g...... 9T) and Migh..... [r) satisfy a formal notion of indistinguishability which we define shortly. In the non-interactive (Smith et al. 2017) local (Yang et al.) 2023) setting that we study, we instead imagine that . is applied separately to each data point as a preprocessing step, and algorithm only gets access the sequence
(.o))........p. Satisfying LDP then requires indistinguishability between the distributions of M((:)) and M(g.)
To define indistinguishability. we make use of f-DP (Dong et al. 2019), modern DP variant based on hypothesis testing. Given two distributions P, Q. we define the tradeoff function T(P, Q)= : [0, > [0, so that T(P, (a) is the minimum false negative rate achievable false positive rate when distinguishing P from Q. A mechanism M operating on individual data points is then said to satisfy f-DP T( M( [')) Z f for all g, o G. As special case, we define the Gaussian tradeoff functions G = (0, 1),, and say that mechanism satisfies u-Gaussian DP (μ-GDP) it satisfies -DP This definition can be naturally satisfied by locally injecting Gaussian noise with scale calibrated to the sensitivity of our gain vectors, defined as A = g. llg 02 S vn. which is in fact what of the algorithms we consider will do.
We also make occasional use of the traditional definition of approximate DP for comparison with prior work: a mechanism operating on individual data points said to satisfy (s, 6)-DP if, for all g, of E G and all measureable events S, we have that P[M(g) E S] S (IMM()" E +
PREDICTION WITH EXPERT ADVICE UNDER LDP
The classical algorithm that inspired approach was introduced by Devroye al. (203)) under the name 'Prediction by random-walk perturbations. We will refer to it as RW-FTPL for brevity. Given
a symmetric distribution DD the algorithm begins by sampling 2g..... 2T sid N( n7 I.). At each ( time step, it chooses 2, = arg max ix) (G.-1 + St-1)s, where S. = It 2t and G, Ei=09.. Is. Here, S, is an element of symmetric random walk, giving the algorithm its name.
When analyzing the privacy guarantees of the algorithm, it is helpful to view the decision rule from a different perspective. Define ÿ. = Si + 2t, with go 0. RW-FTPL can be reformulated as a post-proces set-processsing of these noisy gain vectors, which by our assumptions satisfy (local) GDP with privacy parameter j = A/n. Using tools from convex analysis(Lee) 2018). it can also be shown that its expected static regret is at most (n + ?,) /2T log n. In the absence of additional structure on G.
such as sparsity, this regret bound is weaker than the non-private baseline by a factor of Vn In recent work, [Bhatt& & Kostinal (2025) prove matching lower bounds showing that this rate is asymptotically optimal when gain vectors perturbed with additive Gaussian noise.
4

---

Published as a conference paper at ICLR 2026
3.1 STABILITY UNDER LDP: RW- AWAAABBTTCH
The RW-FTPL algorithm was not originally designed with privacy in mind: the authors' goal was to create low-regret algorithm which changes its prediction only a small number of times in expectation. Intuitively, this limited-switching means that RW-FTPL is almost invariant to permutations of nearby data points. RW-AdaBatch modifies RW-FTPI. to be truly permutation-invarian over many data- dependent intervals. This gives data points that fall within large intervals a "crowd' to hide in, amplifying privacy a la the shuffle model (Erlingsson et al., 2019) while still producing the same outputs with high probability. The amplification naturally grows stronger when data is "easy" in the sense that G2 has non-zero gap. Omitted proofs are the appendix.
3.1.1 UTILITY ANALYSIS.
We show that the expected regret of RW-AdaBatch is at most (1 + ax/2) times greater than the expected regret of RW-FTPL, where a is a small constant given to the algorithm as parameter. Our main tool for proving this result is the following theorem on Gaussian random walks, which establishes conditions under which RW-FTPL's prediction will remain stable with high probability:
Theorem 1. Let TO,T1 I1...,, R be a Gaussian random walk with zo = v and F++1 - 2x (0, I.). If
has gap k2 then the probability that the leader changes at any point during the random walk is at most 24(-)2233 + 2 (T [3() ((-3),, where B k//n///2/
Vlog(2n - 2). The same is true if u has gap k + K. and we wish to bound the probability that the gup ever dips below K.
Corollary 1. The computeDelan subroutine presented in subsection A.6 A.6 selects the largest batch size B, such that the probability of RW-FTPL changing its prediction in the next time-steps can be bounded above by a /loo n/ nt(t +t B.) using Theorem I
Corollary 2. For any a > if RW-AdaBatch chooses batch sizes using the ComputeDelay subroutine with parameter a, then its expected regret is at most (1 + 2 + V2 log
Corollary I follows because ComputeDe ay directly solves the relevant optimization problem with a root-finding subroutine. [orolllary 2 follows because the expected regret of RW-AdaBatch can be decomposed into the regret of RW-FTPL plus the additional regret incurred when batching leads the algorithms to make different predictions. Different predictions only occur when the leader changes within a batch, and so coCCoollrry 1| lets us upper bound the regret from a particular batch over the interval [t, t + B,) by B,ay/log n/ (t + B,). For each time step E [t, t B,), this gives us amortized regret of /loo n/ B,) S a logn/T. Summing over all time steps in all batches shows that the extra expected regret over the entire input is at most v //2x// log ni and adding the base regret of RW-FTPL. along with the fact that (1) + 2)) 2 2/2 for 1) >> 0 yields the corollary.
3.1.2 PRIVACY ANALYSIS.
RW-AdaBatch offers the same local privacy guarantee as RW-FTPL, i.e. μ = A/1j. Ex-post, a point that falls in a batch of size B enjoys a stronger central-DP guarantee of /1/VB. To compute the ex-ante privacy amplification of RW- AW-AdaBatch, we would like exactly characterize the distribution of containing batch sizes any given point. This turns out to be intractable, and so we instead construct a proxy distribution and prove that it stochastically smaller than the true containing batch size for given point, independent of the data. The final privacy guarantees we derive have no closed form, but they can be efficiently computed; we visualize them in FFguure
The key reduction behind our argument is as follows: for any t and B, there exists some threshold such that RW-AdaBatch will always choose batch of size greater than B + 1 if observes a gap greater than before time f. Let's say that a gap is 'small' if it is less than x and 'large' otherwise. We observe that whenever St falls inside a batch of size + or less, the gap must have been small during at least one of the last B time steps. By contrapositive, the gap being large at all of those time steps is a sufficient condition for 9t to fall in a batch of size greater than B + 1. Crucially, this condition depends only on the distribution of the gaps, which makes it much easier to analyze than the full joint distribution over batch sizes. We lower bound the probability of this condition being satisfied by proving the following theorem, which is stated formally in the appendix:
5

---

Published as a conference paper at ICLR 2026
Theorem 2 (Informal). Let K be the random variable representing the size of the gap at time t in the execution of RW-AdaBatch. Then K is stochastically smallest when G;-1 =
The proof of Theorem 2 involves studying integrals over level sets of the "gap' function with respect to the Gaussian measure. When n = 2. these sets are convex and the proof is straightforward. For > 2 the proof is highly non-trivial and we defer it to the appendix. For our purposes, the important thing is that we can write down formula for the CDF and PDF of the gap in this worst case scenario:
((x)((2 =) dx Fx(E) 1 n /
- [x(e) n(n - 1) ((x))(p -))( dr
This allows us to compute a lower bound the probability that the gap at time - will be at least k + We then return to Theorem Ioto upper bound the probability that the gap will drop below within time steps given that was initially k k k. Integration over all possible values of k then gives us lower bound on the probability that the gap is at least for all B steps, from which we derive a probability distribution which is provably stochastically smaller than the true containing batch size of 9.- From here, [eemma lets translate stochastically smaller distribution on batch sizes into lower bound on tradeoff functions, which is stated in terms of Gaussian mixture distributions. This tradeoff function lacks simple closed form, but[Lemma 2 allows
evaluate it numerically.
Let 81 ~ P and 82 ~ Q for some distributions P Set Q over the non-negative real numbers. Then ((81, st), (81,N(11 sf) 2 ([ >2) (82, (1,,N(11,,
Lemma 1.
Lemma 2 (Joint Concavity of Tradeoff Functions (Wang et al.) 2024).. Let Pw, Qu be two mix- ture distributions, each with m components and shared weights w. Then: T(P (w)( 2 Em W&T (Po, (o)(ar(t, c)) =: ((t,c), where oss(,,) = P x Lps
[ (X) > +CPPx Lp
_b =
the type error of the log likelihood ratio test between Po and Qo with parameters and e, and att, Eb= wbau(t,c).
In our case, all of the components correspond to continuous distributions and so we can ignore the c parameter. This characterization is sufficient to compute Figure I| which visualizes the amplified tradeoff curves using the bounds proved above. In the appendix, we show how this can be losslessly converted into curve of (e, 6) guarantees using Proposition 2.13 from Dong al. (2019).
3.2 PRIVATE LEARNING IN DYNAMIC ENVIRONMENTS: RW-META
Recall that static regret is defined with respect to the single best expert in hindsight. To make static regret guarantees more meaningful in dynamic environments, we would like use experts that are themselves non-trivial learning algorithms, capable of adapting to trends in the private data. This is straightforward in the non-private context, where the term 'expert' is already understood to include such learners. The new challenge in the private setting is that, even though existing private algorithms are capable of privately selecting the best data-dependent expert, we could still violate privacy by acting on the chosen expert's 's advice unless the expert itself also satisfies DP.
Prior work (including the oblivious algorithm of Saha et al. (2025) sidesteps this problem by only considering simple experts whose predictions fixed independently of the data and therefore consume no privacy budget. A naïve alternative approach is to divide our privacy budget, allocating a small portion each of m data-dependent experts, but this will generally lead each expert's error growing like /m. To overcome this dilemma, we propose RW-Meta, a new algorithm for privately selecting between and acting on the advice of data-dependent experts, solely through post-processing of the same noisy gain-vecton used by RW-FTPL. As a result, the error of each expert is constant with respect to m, improving significantly on the naïve baseline, and the algorithm as whole satisfies μ- G-LLPP by the post procepsroessing invariance of DP Dwork et al. (2014).
3.2.1 UTILITY ANALYSIS
We refer to data-dependend experts as 'learners' and the algorithm selecting between them as the 'meta-learmer" We model learners functions J1y-..,Be Im Rm,.0 - X. At time step I, each learner

---

Published as a conference paper at ICLR 2026
Algorithm 3 RW-Meta
Require: Noise scale 17, learners fm
Sample (()) ~ 1f Initialize E t- I for ,,..., do
Set 2- Σ - ITETII
Decorrelate our base estimate of learner gains
Set Set max(2t, (2t, Ama (E))
Sample yt ~ NO TT T- Σx)
Choose jr f- arg max, maxx(GGm (G + we)s
# Choose learner using the decorrelated estimate
for i E [m] do
Lift f l:(00 ............. (1-1) E R.
Get Dr ((tt,)1(n)
(Unobserved) receive reward (t)). Set X, +- [21,t1-..,, Im,t] E Rmxn
Update (m)) t- ((m) + Xi9t
# Update our base estimate
Update Σ E/
Record its new covariance matrix
suggests an action Fz. J.. -1-1). and the meta-learner chooses js E [m]] (by restricting learners to all rely on the same noisy gain vectors J. we avoid the issue of learners leaking sensitive information). The meta-learner then receives the gain associated with the action suggested by the chosen learner at this time step, i.c. ( .tt.. Our goal is to minimize the regret of the meta-learner with respect to the best single learner hindsight.
The starting observation for our method is that the value (It. 3t) is an unbiased estimate for the gain of learner i time t. Specifically, let X₂ E R m be the matrix whose ith row 24,5. Then we have that Dt a- Xt9: ( Σt). where G( RW-FTPL, our algorithm able to maintain a Gaussian vector centered on the true gain of each leamner but with the inconvenient wrinkle that the covariance matrix is now data- dependent.
(i))
- Xegt and Σ, r7² Σ X,X?" So, like
To dissolve this issue, we introduce a decorrelation step to the algorithm by defining a new matrix M Σ. -/- (I' Ix")TT" At each time step, we then sample a new Gaussian vector y/s with mean zero and covariance matrix max(2t, Amax 12) -
max,(G, (-) 1 and choose j: arg max, (G(") + v:),- Since our algorithm is invariant to additive noise with covariance I1", this lets us reduce to the scaled identity matrix covariance case, from which we derive the following theorem:
Theorem 3. The expected regret of RW-Meta with respect the best learner at most
max (V2, Mmmaz
)1)) + V2 2T o( /T T'T'mTmoooo log
The best case scenario here is when all learners suggest different actions at each time step, in which and we obtain a tighter bound of O VTn log m). The worst case occurs when the learners are divided into cliques of size m/2. 2. In both cases the regret bound is with respect the best learner, which may be much better than the best action. Comparing the best-case bound to the regret of RW-FTPL illustrates that RW-FTPL can be seen as special case of RW-Meta where m n, all learners suggest different actions, and learner suggestions never change over time.
case Amar (0naa(E/// (Ei/
EMPIRICAL EVALUATION
RW-Ada ---ddBatch. On the basis of Theorem 2]
we expect that the worst case for privacy occurs when all means are equal. To evaluate the privacy loss in this case, simulate 1000 runs of RW-AdaBatch on a stream of all-zero data with = 10, 000. We then use the empirical PMF of containing batch sizes for each point estimate its true tradeoff function. Our results are visualized in Figure I
Our results indicate that the analytic bounds are reasonably but not perfectly tight. The looseness primarily arises in the moderate FPR regime. This is because in bounding the probability that the
7

---

Published as a conference paper at ICLR 2026
1.0
Baseline
(A) t=400
10-1
(A) t=2000
False Negative Rate
(A) t=10000
(E) t-400
10-2
0.6
(E) t=2000
(E) 100000
delta
10--
Baseline
(A) t= 400
(A) t= 2000
10
(A) t= 10000
0.2
(E) 400
(E) 2=00
0.0
10
(E) t- 10000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.5
1.0
1.5
2.0 epsilon
2.5
3.0
3.5
4.0
False Positive Rate
Figure 1: Equivalent representations of worst-case privacy amplification for RW-AdaBatch with parameters f 1, = 25, A = vn, a 0.01. The baseline corresponds to the Gμ tradeoff curve, solid lines correspond to the Analytic upper bound, and dash-dotted lines correspond to Empirical Monte Carlo simulations. The analytic bound is fairly tight, particularly for small 6/low FPR.
leader changes, assume that the deterministic part of the gap will shrink the fastest possible rate, but this is overly conservative in the oblivious adversary model. As a result, we underestimate the probability of selecting very large batch sizes. Meanwhile, the low FPR behavior of the algorithm is largely driven by the probability of seeing small batch sizes, where our bound is much tighter.
RW-Meta. We evaluate the performance of RW-Meta with real-world data from the COVID-19 pandemic. Specifically, we use data from the United States Department of Health and Human Services (HHS 2024 containing weekly reports from thousands of hospitals from mid-2020 through 2023. For each state, our task is to predict which hospitals will report the highest density of COVID patients in each week. Because we are interested in preserving the privacy of individual patients and not the hospitals themselves, we modify the basic adjacency definition in suusecctio 2.2 to define two sequences as adjacent if they differ only in a single individual's participation at a single time step. For example, if every hospital in a state had at least 10 beds, then we would compute sensitivity for that week as v2/10 /10 reflecting the possibility that someone might have not have gotten sick, or they might have chosen to go to a different hospital. our dataset, the minimum number of beds ranges between 4.3 and 14.6, with the result that sensitivity is kept manageably low throughout.
Altieri et al. (202T). we consider models that first forecast the exact proportion of COVID cases in each hospital and then make a final prediction by taking the argmax of their forecast. The gain of a learner is the true proportion of COVID patients in the hospital they select. Our evaluation uses 13 learners consisting of rolling Gaussian regression algorithms with window sizes of 8/16/32/64 and weak/mediun//trong regularization, as well as the basic RW-FTPL algorithm. We use Gaussian regression models because they are popular for medical forecasting and their theoretical assumptions match the additive Gaussian noise we use to protect privacy. The range of hyperparameters we consider was chosen manually through exploratory analysis with disjoint slice of the dataset, guided by the goal of maximizing variety across learners. We evaluate our algorithm on data from three states (New Mexico, Pennsylvania, and California), which were chosen to cover a diverse range of population sizes while being geographically large enough to decorrelate different hospitals.
Following
We remove any hospitals that did not appear to participate in the DHHS'ss data sharing program. defined as reporting fewer than 100 suspected cases over the 3 year period. This left us with data from 24, 146, and 293 hospitals in each state respectively, covering the 148 weeks between August 9th, 2020, and June 4th, 2023. We evaluate our algorithm under four different privacy levels: no privacy (μI = oc), low privacy (μ = 1), medium privacy (p = 0.5) and high privacy (u = 0.25).
Because we are not aware of any existing LDP experts algorithms for oblivious adversaries, we compare RW-Meta against the state-of-the-ard private experts algorithm Agarwal & Singh (2017). This comparison must be caveated because their algorithm satisfies CDP and was not designed for dynamic environments; our goal is not to prove that one algorithm is superior, but rather to
Also available at https://osf.ion/zt9
8

---

Published as a conference paper at ICLR 2026
1 inf
4=1
14 0.5
== 0.25
60
RW-FTPL
Gain (NM)
Agarwal
40
(Min Noise)
Agarwal (Min Regret)
20
RW-Meta
0
Linear Models
Gain of Best Action
60
Gain (PA)
40
0
Gain (CA)
40
20
0
100 Time
100
Time
Time
Time
Figure 2: Results of empirical evaluation on COVID-19 19 hospitalization data, averaged over 100 iterations. Rows correspond to states while columns correspond to privacy levels. The shaded orange regions enclose the maximum and minimum gain of the 12 rolling regression learners, and the dotted black lines represent the maximum cumulative COVID density of any single hospital in the given state. Static regret can be interpreted as the distance between learner's 's total gain and the dotted line, while the regret of RW-Meta corresponds to its distance from the top of the orange envelope. Note that all plots share the same and y axis.
contextualize the costs of satisfying local vs. central DP and the potential benefits of moving beyond the paradigm of iata-inddepeddet experts. We consider two choices of parameters for their algorithm: choosing the minimum noise scale required to still satisfy μ-GCDP (Min Noise), and choosing the noise scale optimize worst-case bounds regret subject to privacy constraints (Min Regret).
Results. We repeat our evaluation 100 times and report average results, which are visualized in Figure 2 and summarized numerically in Table 2 Averages are reported alongside 95% confidence intervals based on the central limit theorem with Bonferroni correction. Across all settings, we find that RW-Meta consistently outperforms all other algorithms, followed by Min Noise. This is because RW-Meta is able to consistently achieve negative static regret at low and moderate privacy levels, which is essentially impossible match using data-independent experts, regardless of noise scale.
Separately, we find that RW-Meta performs around 90% as well as the best linear model in each setting on average. Which exact linear model performs best varies considerably, however. For instance, the learner with window size 8 and strong regularization is the best performing learner in the high privacy setting for the Pennsylvania dataset, but only middle of the pack for New Mexico (where the best learner instead has window size of 64). Across different privacy levels, the variation even larger. This heterogeneity highlights the appeal of using meta- meta-learning, as eliminates the need to commit to single set of parameters in advance.
Conclusion. We have presented two algorithms for the fundamental problem of prediction with expert advice, both of which satisfy LDP. In static environments, our RW-AdaBatch algorithm is costless upgrade over the classical algorithm we build off of, improving the privacy of its outputs with provably insignificant impact on utility. In dynamic environments, our RW-Meta algorithm uses novel, preneerirr technique to dynamically adapt to shifts in the imput data, and we show that be won no additional privacy cost. Our theoretical
the resulting improvements in performance results are supplemented by an empirical evaluation showing that our algorithms can achieve high performance in real-world, privacy-critical prediction task.

---

Published as a conference paper at ICLR 2026
Table 2: Average gain learners
Agarwal (Min Noise)
Agarwal (Min Regret)
Privacy Level
RW-Mcta
Best Linear Model
New Mexico
μ
40.14 10.30
26.48
13.38 10.38
43.91
36.87 +0.36
22.83 +0.37
13.41
+0.39
40.69
#0.26
0.5
31.19 +0.55
19.56 +0.42
13.25 =0.40
34.14 #0.49
0.25
22.46 +1.04
15.58 +0.43
13.38
+0.43
25.85 #1.26
Pennsylvania
J = DO
43.70 #0.41
27.42
15.51
#0.37
48.61
40.32 +0.50
23.55 +0.44
15.38
+0.37
44.30 +0.39
0.5
34.71 +0.68
20.03 +0.44
15.64 +0.40
38.06 +0.57
/ 0.25
25.44 +0.87
16.09 +0.42
15.35 +0.38
28.73 +0.82
California
J
59.36 +0.47
31.12
16.68 +0.36
66.23
J
55.62 0.47
25.09 0.51
16.91 0.34
61.16 +0.29
0.5
47.43 + 0.81
22.14 0.48
16.82 0.41
54.21 +0.56
0.25
33.34 1 1.30
17.93 0.41
16.84 0.35
38.43 11.30
4.1 REPRODUCIBILITY STATEMENT
Full proofs of all of our theoretical contributions are provided in the appendix, including clear statements of all necessary assumptions. For our empirical evaluation, we provide a reference to the dataset we use (DHHS) 2024), which is available httts:://sf..oo/zz2y and describe all data pre- rre-processing steps section 4 In subsectiio A.3 we describe the hardware and software used to carry out our experiments as well as specific implementation choices that improve the efficiency of our algorithms, and (sbseetton A.6 provides explicit pseudo-code for the main subroutine of RW-AdaBatch. We provide containerized scripts for reproducing all of our experimental results at http://sshhbbb.oooobrcccccssssep
REFERENCES
Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. Conference on learning theory, pp. 807-823. PMLR, 2014.
Robert J Adler and Jonathan E Taylor. Gaussian inequalities. Random Fields and Geometry, pp. 49 49,64,220 2007.
Naman Agarwal and Karan Singh. The price of differential privacy online learning. In Interna- tional Conference on Machine Learning, pp. 32-40. PMLR, 2017.
Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Thakurta. Differentially private and lazy online convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4599 4632. PMLR, 2023a.
Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Guha Thakurta. Improved differentially private and lazy online convex optimization. arXiv preprint arXiv:2312.11534 2023b.
Nicholas Altieri, Rebecca I. Barter, James Duncan, Raaz Dwivedi, Karl Kumbier, Xiao Li, Robert Netzorg, Briton Park, Chandan Singh, Yan Shuo Tan, al. Curating a covid-19 data repository and forecasting county-level death counts in the united states. 2021.
Theodore W Anderson. The integral of symmetric unimodal function symmetric convex set and some probability inequalities. Proceedings of the American Mathematical Society, 6(2): 170-176, 1955.
10

---

Published as a conference paper at ICLR 2026
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. In The Thirty Sixth Anmual Conference on Learning Theory, pp. 674-699. PMLR, 2023.
Hilal Asi, Tomer Koren, Daogao Liu, and Kunal Talwar. Private online learning via lazy algorithms. Advances in Neural Information Processing Systems, 17:112158-11221 2024.
Achraf Azize and Debabrota Basu. Concentrated differential privacy for bandits. In 2024 IEEE Conference Secure and Trustworthy Machine Learning (Sa'TML), pp- 78-109. IEEE, 2024.
Alankrita Bhatt and Victoria Kostina. Prediction with expert advice under additive noise. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
David Blackwell. Comparison of experiments. In Proceedings of the second Berkeley symposium mathematical statisties and probability, volume 2. pp. 93 103. University of California Press, 1951.
Jean Bolot, Nadia Fawaz, Shannugavelayutham Muthukrishnan, Aleksandar Nikolov, and Nina Taft. Private decayed predicate sums streams. In Proceedings of the 16th International Conference on Database Theory. pp. 284-295, 2013.
Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Schwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 5253-5270, 2023.
Nicolo Desa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 1424,1124,, 2011.
Christopher A Choquette-Chove Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Privacy amplification for matrix mechanisms. arXiv preprint arXiv:23 /0. 15526, 2023.
Christopher A Choquette-Choo, Choo, Arun Ganesh, Ryan McKenna, H Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach private training. Advances in Neural Information Processing Systems, 36, 2024.
Mare Damie, Florian Hahn, Andreas Peter, and Jan Ramon. How securely shuffle? survey about secure shufflers for crivacy-rreeerving computations. arXiv preprint WxXiv2250700148: 2025.
Sergey Denisov, H Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators adaptive streams. Advances in Neural Information Processing Systems, 35:5910-5924, 2022.
Marie Devaine, Pierre Gaillard, Yannig Goude, and Gilles Stoltz. Forecasting electricity consumption by aggregating specialized experts: A review of the sequential aggregation of specialized experts, with an application to slovakian and french country-wide one-day- (half-) hourly predictions. Machine Learning, 90(2):231-260, 2013.
Lue Devroye, Gábor Lugosi, and Gergely Neu. Prediction by random-walk perturbation. In Confer- ence on Learning Theory, pp. 460-473. PMLR, 2013.
DHHS. Covid- 19 reported patient impact and hospital capacity by facility, 2024. Accessed: 2024-11- 20. Available at larchive.org
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. arXiv preprint 1rX.v:1905.02238.. 2019.
John C Duchi, Michael Jordan, and Martin J Wainwright. Local privacy, data processing incqualities, and statistical minimax rates. arXiv preprint arXiv: /302.3203 2013.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the sorty-second ACM symposium on Theory of computing. pp. 715-724, 2010.
11

---

Published as a conference paper at ICLR 2026
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends@ Theoretical Computer Science, ((3-4):211 407, 2014.
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mecha- nisms in local and central differential privacy, 2019. URL blttps://axxiv.oqq//
08339
Úlfar Erlingsson, Vitaly Feldman, llya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2468- 2479. SIAM, 2019.
Fengyu Gao, Ruiquan Huang, and Jing Yang. Federated online prediction from experts with differ- ential privacy: Separations and regret speed-ups. 2024. URL httpa::/arxxww.rr//// 2409.19099
Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In COLT, pp. 132-143. Citeseer, 2010.
Awni Hannun, Brian Knott, Shubho Sengupta, and Laurens van der Maaten. multi-party contextual bandits. arXiv preprint arXiv:1910.05299 2019.
Charles Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathamiel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Kérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy, Nature, (85(:)8))77772777-288823
September 2020. doi: 10.1038/s4 15888444486-000-6449999
URL
Naoise Holohan and Stefano Braghin. Secure random sampling in differential privacy. In Com- puter Security-ESORICS 2021: 26th European Symposium on Reseurch in Computer Security, Darmstadr, Germany, October 4-8, 2021, Proceedings, Part II 26, pp. 523-542 Springer, 2021.
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Conference Learning Theory, pp. 24-1. JMLR Workshop and Conference Proceedings, 2012.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pp. 5213-5225. PMLR, 2021.
Andrew V Knyazev. Toward the optimal preconditioned eigensolver: Locally optimal block pre- conditioned conjugate gradient method. SIAM journal on scientific computing, 23(2)5117-541, 2001.
Chansoo Lec. Analysis of perturbation techniques in online learning. PhD thesis, 2018.
Satya N Majumdar, Amab Pal, and Grégory Schehr. Extreme value statistics of correlated random variables: a pedagogical review. Physics Reports, 840:1-32, 2020.
Albert W Marshall and Ingram Olkin. Majorization in multivariate distributions. The Annals of Statistics, 2(6): 120- 1974.
Ilya Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM conference on Computer and communications security, pp. 650-661, 2012.
Kai Morino, Yoshito Hirata, Ryota Tomioka, Hisashi Kashima, Kenji Yamanishi. Norihiro Hayashi, Shin Egawa, and Kazuyuki Aihara. Predicting disease progression from short biomarker series using expert advice algorithm. Scientific reports, 5(1):8953, 2015.
The mpmath development team. mpmath: a Python library for subitrary-precissinn flaating-point point arithmetic (version 1.3.0), 2023. http: http::/mpmat /tmp///tthhh/////m/ttm///a///tht org//
12

---

Published as a conference paper at ICLR 2026
Victor Penrier, Hassan Jameel Asghar, and Dali Kaafar. Private continual release of real-values data streams, arXiv preprint arXiv:1811.03199 2018.
Aadirupa Saha, Vinod Raman, and Hilal Asi. Tracking the best expert privately. arXiv preprint arXiv:2503.09889 2025.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium Security and Privacy (SP), pp. 58-77, 2017. doi: 10.1 109/S...00...355
Abhradeep Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26, 2013.
Pauli Virtanen, Ralf Gommers, Travis F. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Îlhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020. doi: 1..1038/44192-009--00
Chendi Wang, Buxin Su, Jiayuan Ye, Reza Shokri, and Weijie Su. Unified enhancement of privacy bounds for mixture mechanisms via f-differential privacy. Advances in Neural Information Processing Systems, 36, 2024.
Tianhao Wang, Joann Qiongna Chen, Zhikun Zhang, Dong Su, Yueqiang Cheng, Zhou Li, Ninghui Li, and Somesh Jha. Continuous release of data streams under both centralized and local differential privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 1237-1253, 2021.
Jie Xu, Dingxiong Deng, Ugur Demiryurek, Cyrus Shahabi, and Mihaela Van der Schaar. Mining the situation: Spatiotemporal traffic prediction with big data. IEEE Journal of Selected Topics in Signal Processing. 944)7702-715, 2015.
Mengmeng Yang. Taolin Guo. Tianqing Zhu, Ivan Tjuawinata, Jun Zhao, and Kwok-Yan Lam. Local differential privacy and its applications: comprehensive survey, Computer Standards & Interfaces, pp. 103827, 2023.
A APPENDIX
A.1 COMPLEXITY ANALYSIS
In the worst case, RW-AdaBatch requires us to find the root of smooth monotonic function at each time step. Crucially, however, the size of the problem is constant and does not depend on or T. and so the asymptotic complexity of RW-AdaBatch is only O We describe some of our practical techniques for improving the efficiency of this step in the following section.
RW-Meta algorithm requires 0mm² + mn) memory to store the predictions of the learners at each round as well as the Σ matrix. Similarly, we require O(m" + mn) operations per iteration to compute n and X, It is also necessary to choose specific technique to compute Amax > in our implementation, we use the LOBPCG algorithm, which enjoys linear convergence and requires solving 3 3 eigenproblem each iteration (Knyazev) 2001). We can control the total number of iterations by warm-starting with the leading cigenvector of the previous iteration, which is guaranteed to be within (mm) of the new maximum eigenvalue.
13

---

Published as a conference paper at ICLR 2026
A.2 PARAMETER CHOICE
All three of the algorithms we study require choosing noise scale 7/. This can be done by computing the minimum noise scale required to guarantee privacy, i.e. 1 = A/u, which typically works well on realistic data. To optimize worst-case performance for RW-FTPL or RW-AdaBatch, one can instead choose 7 max( p/)..
In our early design process, we investigated several different choices of a for RW-AdaBatch and found that it seemed to have little practical impact the behavior of RW-AdaBatch. This is not necessarily surprising - the random variables we are trying to control all have sub-Gat Sab-Gansiinn tails, resulting in failure probabilities that are exponentially tiny for most batch sizes. We take 0.01 for simplicity in our experiments.
A.3 IMPLEMENTATION DETAILS
All experiments are carried out on laptop running Ubuntu 22.04 with an intel 15-1135G7 CPU and 16GB of RAM. We implement our algorithms using Python 3.10. numpy 2.0.0 (Harris et al. 2020). scipy 1.14.0 (Virtanen et al., 2020), and mpmath 1.3.0 (mpmath development team 2023).
Although RW-FTPL is computationally straightforward, Both RW-Meta and RW-AdaBatch include non-trivial computations as subroutines which must be implemented efficiently. We briefly describe our implementation choices here.
In the case of RW-Meta, we use the LOBPCG algorithm as implemented in scipy to find the leading eigenvalue of Σ; at each iteration, with the leading eigenvector from the previous round as initial guess. We find that at the problem sizes we consider, this step is not significant bottleneck (taking about 2ms per iteration), and we therefore do not pursue any further optimizations.
In the case of Att-dhatthh, we take advantage the fact that the bound from Theorem I is a monotonic function of 3 by pre-computing many input/output pairs. To avoid issues with floating point precision when computing extreme values of the Gaussian PDF/CDF, we use the mpmath library for this task, which supports arbitrary precision arithmetic and numerical integration. We then interpolate the result with monotonic cubic spline, which can be used to closely approximate the required value of [3 necessary achieve given failure probability 5. In practice, the discrete nature of the choice of batch size means that the small differences between the true inverse function and the interpolated approximation are insignificant, while the corresponding speed-up is dramatic.
Finally, prior work has shown that straightforward DP implementations are often vulnerable to attacks that take advantage of the idiosyncrasies of floating point numbers, leading to catastrophic privacy failures (Mironov) 2012). We therefore employ the secure random sampling method of Holohan & Braghin (021) which renders these attacks computationally prohibitive.
A.4 LIMITATIONS AND FUTURE WORK
A.4.1 APPLICABILITY OF LOCAL DP
The primary limitation of our work is that satisfying local DP sometimes requires adding unrcasonably large amounts of noise, particularly when gain vectors high-dimensional. To guarantee low regret, our approach requires gain vectors with sensitivity smaller than their literal dimension, or else a silo-like setting where several sensitive values can be averaged locally before being sent to the algorithm, but this may not always be achievable in practice.
A.4.2 EXTENSION TO MORE COMPLEX LEARNING PROBLEMS
While the experts problem is flexible enough to represent many real world tasks, is also interesting from theoretical perspective because it is one of the most fundamental problems in online learning. This naturally raises the question of whether the methods developed in this work can be extended to more complicated learning problems.
With respect to metalearning, RW-Meta fundamentally requires linear gain function to compute unbiased estimates for the gain of each leamer. So, while it can be extended to online linear
14

---

Published as a conference paper at ICLR 2026
optimization problems beyond prediction with expert advice, it is not clear that the same method could be generalized to the larger class of online convex optimization.
Mcanwhile, RW-AdaBatch relies the property that the maximum of linear function over polyhedral set always attained at one of those points. It would therefore difficult to extend it to settings like online linear optimization over the sphere where the action set lacks this structure. On the other hand, the same property holds for maximums of convex functions over polyhedral sets, and so it is possible that the ideas behind RW-AdaBatch could be extended some instances of online convex optimization.
A.5 PROOF OF HEOREM
The formal statement of Theorem is as follows:
Let oo, 21,...,357 JB Rn be Gaussian random walk with vo - 1 and Ft-1
(0, In). If v has gap then probability that the leader chunges at any point during the random walk is at most 2 (- + + (3( (--B)}, where B = k//n/BB) / /log(2n - 2). The same is true v has gap + and wish to bound the probability that the gap ever dips below
The proof processes:
theorem requires the following fundamental results about the extrema Gaussian
Lemma 3. Let 2 (O0 n²), and let Ei=1 24. Then:
max St Sat [Spl
Proof. Instead of considering the discrete random walk. consider the continuous analogue in one-dimensional Brownian motion over [0, B) with scale y,. The maximum value attained by the discrete random walk is most large the maximum value attained by the Brownian motion. The latter is known follow half-normal distribution with scale n//B (see e.g. Section 3 of Majumdar et al. (2020)), which is also the distribution of SSp].
We additionally need the well-known Borell-TIS inequality, which states that the maximum of Gaussians concentrates closely around its expected value (Adler & Taylor 2007
Lemma 4 (Borell-TIS), Let {ft} be centered Gaussian process on T. Denote [[fll supter fe and or suPteT Ct. Then for any 2
P(I
E[IlI|| + u) & exp 207
Finally, we have the following standard upper-bound on the expected maximum of Gaussians based on momeent-gnneatinng functions:
Lemma 5. Let 21...., 2n be (not-necessarily independent) random variables such that
of). Let = max, 24. Then:
B S max /
log
(5)
Proof. We have that:
exp(tE(2]) < Blee2
x Σ E(e
1E(n]
Σ exp(a?t2/2) /2)
(E(n)
I n exp(max o²
Taking log of both sides and choosing minimize the upper bound gives the desired result. n
15

---

Published as a conference paper at ICLR 2026
Now: suppose that given time step, the gap of G is k. Our goal is to bound the probability that our algorithm's 's output will change in the next time steps. Because the algorithm is maximizing a linear objective function, it will always output one of the vertices of the probability simplex. Without loss of generality, assume that the current time step O and that the current leader has index 1, and write S = > (ge); Then the following a necessary condition for our algorithm's prediction change:
max max St.j > k: + min St,1 j>1 LE[B]
Lemma 3 3ttllls us that each maximum over is stochastically smaller than half-normal distribution with scale 7 and by symmetry the minimum the right hand side is stochastically larger than negative half-normal. We can write a half-normal random variable as the maximum of a Gaussian random variable and its negation, and so Lemma 5 lets bound the expectation of the left-hand side with /B log(2n 2). Denote this quantity E. Then, assuming that E, Lemma 4 along with the independence of each coordinate to upper bound the probability of our event with:
p(min St. =)P St.j k =2) dz 1J21
1
E-
u2 2BT²²
2Φ
+
1
exp
du
1/V B
nVB"
nvB
Here, the first term represents the probability that the current leader dips below the expected maximum value of the remaining actions, and the second term represents the probability that one of those n 1 actions manages to overtake the current leader regardless. Using the definition of the Gaussian
PDF, rewrite the second term as:
(-E k)²
1
1
2u + (E -k) du
exp
4B1²²
BVB"
n/2B
(-(B-
4Bm1 (-(ETp"))
-1)
(K-E)/WNVBB)
exp
soy) dy
V2
(E-R)/(ovBB)
1
(E (=(E-k)p
k)2
k E
E ーード k
exp
V2
4B12
2B 2B
Write 3= (k- E)/(n222/B
(B)).
Then the entire upper bound be simplified as:
2Φ
[--3)]
which proves the theorem.
A.6 COMPUTEDELAY SUBROUTINE
This appendix contains the explicit computation used by RW-AdaBatch to compute the size of the next batch:
Algorithm Subroutine to compute delays
Require: Noise scale 7) gap k, dimension n, tolerance a
E. < / /log(2r 2n 2)
(B) = 2Φ
B-k BVB
/2F
U2(B) = 2/TT
B-B
n/2B
U2(B) = B-B
E
B-k
+
E
7/2B
n/2B
&BB) ay ++
log
B - (indRcot(U((B U2(UU, (B))
return Flocr(()))
16

---

Published as a conference paper at ICLR 2026
A.7 PROOF OF THEOREM 2
The formal statement of Theorem 2 is as follows:
Let Se {o E IR V(()) - 1()-1) { and let 7 denote the standard Gaussian measure RR Then for any vector p R", ("({)) ?"(S -1).
The set Sg is invariant under permutations and shifts in the I direction, and so assume without loss of generality that #n 2 #2 2 2 an O. It is casiest to begin by finding the measure of the complement of our set, which union of disjoint sets where element is the leader and the gap greater than E. This measure is given by:
f(H) 7" ((S - )))
Σ
pl pb) II 1 ptj) dx jti
Our strategy to show that the partial derivative of f with respect to μ1 is non non-negative. To do so, we can use the fact that each of our disjoint sets is invariant under shifts in the I direction, and so the gradient each summand with respect to j must be orthogonal I. So, we can write our partial derivative as:
p( - -1)y(( - - -.))
D(x - 5 - -11) 1
II
1=2
p( p1)p(z (pp(==0 m1)
II 8f,,1
4(x & -1,,-,, 12)de
Combining like terms, this gives us:
Σ
s(x 10-m))pps ui) exp Ex 2 _
(exp(- - exp(-sm1)
Φ - 115) dx jf1,
II
Then, since NI μ4 and O, the term inside the brackets is non-negative. Therefore, as a sum of integrals of products of non-negative values, the whole expression is nen-negative.
From here, the fact that Sg is closed under permutations means that, if μ4 μ4, for some i, then they have the same partial derivative. So, we can explicitly construct path from any arbitrary μ to the origin along which (() is non-increasing: first reduce /41 until it equals μ2, then reduce both until they equal μ3. and so on. This construction shows that the function is globally optimized at 0. as desired.
O
Remark 1. In the special case where n 2, S. is convex set and the statement can be proved directly using Anderson's theorem (Anderson) 1955) or its extension by Marshall and Olkin for Schur-concave sets (Marshall & Olkin 1974). When n > 2, however, the set is neither convex nor Schur concave, necessitating the more explicit analysis here.
The informal statement of the theorem in the main text follows from this result together with the assumption of an oblivious adversary. The fact that the adversary is oblivious corresponds the order of quantifiers in the formal theorem statement: first we choose an arbitrary vector p. and only afterwards do observe the size of the gup. This is the only context in which the adversurial model is relevant for privacy all of our LDP guarantees hold in both models (Denisov et al.) 2022).
Remark 2.
A.8 PROOF OF LEMMA
The proof follows from theorem by Blackwell (1951), reproduced as Theorem 2.10 in Dong et al.) (2019), which states that T(P, Q) < T(P,, Q") if there exists a randomized algorithm proc such that proc(p)c))))ppp P' and pQ) Q'. We will construct such algorithm.
17

---

Published as a conference paper at ICLR 2026
Suppose receive the random imput (82, Q (b, for some priori unknown b. We first choose 81 FF (FQ(s2)). Since 82 Q, we have that FQ(s2) Uni 1) and therefore
$1 P. Then, since P 2st Q, we have that Fp" 2 Fo and therefore 81 82. So, sample
NO, of >5) and release the tuple (81, + P x (b, sf). which completes the proof. I1
A.9 CONVERSION TO e; 5-DP
We prove the following corollary to the privacy analysis in subsection 3.1
Corollary For all ε > 0, RW-AdaBatch satisfies (e, 1 e a(E) - ((E)))DP, with a and B defined as in Lemma
The proof relies on the Proposition 2.13 from Dong et al. (211 which we reproduce here:
Lemma 6 (Primal Dual). Let be a symmetric trade-off fractiofffunttion. A mechanism is f-DP if and only if it is (e, DD for all 2 0 with 5(E) = 1+ f" (-E"), where:
f"(
sup yr f(x) -ocKC
(8)
the convex conjugate of f.
In case, f is only defined on [0, 1], so we let f(x) 00 for of [0, 1] and the supremum is effectively taken over 0 S æ S 1.
To find the convex conjugate, given y. To that end, define (a) = ya- ((A)) Then we have that f" = hy(a"), where a" inf [0, 1] E (a))
need to find the specific value att) that optimizes ya(tt B(t) for
We have that att) is differentiable with respect to t, so we can compute that:
d (ya(l)
di (a(((() = di
- Σ 3o()(()
b=1
m
d
m
y
Wb
dt
(t
Σ
whb
dt
Bt(t)
b=1
m
lvb
tvb
1
y
wb
4p
+
2vb
H
vb
LVb
Wbb
l 40
f
2vb
Define:
t/b 1
2b
11
2vb
Then the expression simplifies to:
m
Viwwyel 22 + H/VD///)))) + Σ (((6))
Viwno(Zzn) [ yexp
(T 11
112
2b
Vb
2b
Vbwrsp(zz) + yxp(((tt))
P
Setting this equal to and using the fact that 4p, w. 0, we obtain that:
y veep(-tx () + = 0
in(-y)
18

---

Published as a conference paper at ICLR 2026
Denote this last quantity ty. From this it follows that f*(y) hyy(a(ty)) and therefore that our mechanism satisfies E, D())-DP for all & > and:
8(E) = - e att-e=) B(t-ct) =1 -- a(()) 3(E)
as desired.
A.10 PROOF TIEEOREM 3
formally analyze regret of RW-Meta using the convex analysis framework of Lee (2018). Let M maxxex (zz G) be the baseline potential function, and for any set of distributions {Di }. define the smoothed potential function M,(G) EzwD, M z). Finding the expected regret of any randomized FTPL-style algorithm can be reduced to finding the regret of the deterministic algorithm which plays Ez-D, [arg max M (G++2) v M, at each time step i, which by Lemma 3.4 in Lee 2018 satisfies the following equality:
T
Regret =
(M((Gi-1) (G
penalty
+ D us. (Ge, Gr-1))
M(GT) Mr
MGrr))My(Gr (GT)
divergence penalty
underestimation penolty
Where f(y) f(x) (Vf(x) x) the Bregman divergence, which is a measure of how quickly the gradient of f changes. Intuitively, the overestimation penalty represents the error that results when we fool ourselves into believing an action is better than really by adding too much noise, and the divergence penalty represents the error that comes from always playing step behind the real objective function. Because we add zero-mean noise, the underestimation penalty is always negative by Jensen's inequality, and prove low regret it suffices upper bound the first. two terms.
For the overestimation penalty, we use the convexity of M to bound:
M.(G.-1) ---
(
S (EEN)(O.)) --/{)=>)
From which it follows by telescoping that the entire sum is upper bounded by:
E E2~N(0.1) (2/,)
/ log(m) m, Amari Ejy)
Where the last step follows from Lemma 5 (018) to bound:
For the divergence penalty, we Lemma 3.14 in Lee
22
Dy, (Gi, G(-1)
From which it follows that the sum can be upper bounded by v 22 m ΣT= / giving us our final regret bound of:
2 Too
Σイ +
1/2
max /2,
Aman
/2
/ 2T logm
(9)
2T
19

---

Published as a conference paper at ICLR 2026
A.11 HEURISTIC PRIVACY ANALYSIS OF RW-ADABATCH
The mixture-distrriutiion method of privacy analysis developed in Wang et al. (2024) and used in the analysis of RW-AdaBatch leads very tight bounds, but this comes at the cost of being highly complex and difficult to interpret. To help build some intuition, this appendix derives a heuristic estimate for the asymptotic level of privacy amplification provided by RW-AdaBatch. We make the following simplifying assumptions:
1. The variance of the noisy cumulative gain vector is very large, i.c. try² > 1, and so the deterministic component of the gap is insignificant compared to the stochastic component. This allows us to simplify our equations by dividing everything through by 7, and so we will also assume WLOG that 17 =1
2. Potential batch sizes are relatively small, i.e. B, < t, and so we can simplify the target failure probability & oo/log n/(( + B,) ~ ar/loggn/t.
3. We approximate the distribution of containing batch sizes for time with the distribution of batch sizes induced by the gap at time We believe this is a reasonable heuristic for sufficiently large (intuitively, if the gap is large at time / and Assumptions and 2 hold, then we expect the gap the preceding few time steps to be essentially the same size), and allows us to sidestep much of the complexity in the derivation of our rigorous lower bounds on privacy amplification presented in subsection 3.1
4. Initially, will assume that n 2, and therefore that the gap itself follows half-normal distribution. After establishing bounds in this setting, we" 'll return to consider the case of general n.
Under these assumptions, consider the event that t falls in batch of size less than B + 1. Under Assumption 3, this is equivalent to the gap at time being smaller than the threshold computed by RW-AdaBatch when it selects batch sizes. We will compute that threshold. In the notation of subsection A.5 we have E Plugging these quantities into Lemma 4 and letting & represent the size of the gap at time t, we get:
2B log 2n 2). and by Assumption 2 we have 6, a /lg n/T.
(k: Ey²
exp
avlogn/t
(10)
2B
(k E)2 < 2B(log(1/a) + log(t/ logn))
(11)
k k< - B /2 a//a) + log(t/ logn)
(12)
Next, under Assumptions 1 and we have that k |a|. where = 20). So, we can upper- bound the probability that our event occurs with the small-ball inequality Pll=/ 2t s a] S V2x giving us:
2a
B 2t
Plbatch size < <B+1=11
22/V28
2og 2n - 2) + 2llog(//a) aa) + log(t/ log
(13)
I n
1 (2n 2) + 12lo log(t/ (ollgg////gg//))) l)
(14)
Finally, if point falls a batch of size B + 1, then its post-hoe privacy level is / = p 1/VB. This means that the expression above can also be interpreted as an upper-bound on the probability that the amplification ratio r := /1/p²' for point / is less than VB. Rearranging, we can derive the following bound for the amplification ratio that holds with probability at least 7
22xt nt
(15)
2 log log(2n 2nn 2) + /2 /ogg(1/a) log(t/ logn)
726 log(1/a) + log(t))
=
(16)
20

---

Published as a conference paper at ICLR 2026
And so in the special case where 2, that the quantiles of the privacy amplification provided by RW-AdaBatch grow like t/ tolo(()). Importantly, however, this bound is only pointwise and not uniform over all quantiles simultaneously.
The case general n > 2 is more complicated because the gap no longer follows a nice, analytically- tractable distribution. However, we use the fact that ((x) I 1 to derive very loose upper-bound on Equation by:
Fe;e;)) = -
((z) - -E) dr
(17)
2 n1
((x) - -)) dx
(18)
-c0
(1 - Fx(e;2))
(19)
This allows us to convert a 7 bound on any monotonic function the gap when n into
1 ny/2 bound when n >> 2. Plugging this into the bound on the amplification ratio above, get:
r r= 0 n² (log - 1og(1/a) + logt)
26
(20)
Showing that the degree of amplification remains almost linear in f, but potentially with a slower rate that depends on the number of experts.
A.11.1 LIMITATIONS OF HEURISTIC ANALYSIS
Although we believe this analysis is helpful for building intuition, we caution against using it as replacement for the more rigorous bounds derived in subsection 3.1
Firstly, this is because Assumptions 1-3 discard several factors which are asymptotically irrelevant but potentially meaningful realistic problem sizes. Assumption in particular difficult rigorously justify, although it seems to hold reasonably well in practice.
Secondly, the bounds derived above are only meaningful if = w(1/vT) This is an issue because there will still often meaningful risk of selecting very small batch size even when t fairly large- - in particular, this is almost certain to happen every time the leader changes. So while it might be possible make heuristic statements like "With probability about 0.9, your post-hoe privacy level will be at least as good as 0.1", the risk that we'll Il get unlucky and observe = 1 instead makes this sort guarantee meaningfully weaker than actually offering a privacy guarantee of μ 0.1 from the beginning.
In the language of f-DP, our heuristic should convey a fairly good idea for what the moderate-FPR region of the tradcoff curve looks like while giving inflated impression of the privacy guarantee in the low-FPR regime. This can be contrasted with the true lower bounds we compute analytically, which over-pessimistic in the moderate-FPP regime but quite accurate in the (often-more-critich) regime when a is small.
21


Reviews:
[{"review_id": "4h2pzRceTL", "reviewer": "Reviewer_7KQP", "summary": "This paper studies prediction with expert advice under local differential privacy. That is, a learner aims to minimize the regret when the gains provided are noisy. It introduces two algorithms RW-AdaBatch, which modifies Random-Walk Follow-the-Perturbed-Leader (RW-FTPL) to adaptively batch inputs when predictions are unlikely to change, and RW-Meta, a meta-learner that privately selects among data-dependent experts using shared Gaussian noise.", "questions": "1) RW-AdaBatch’s privacy amplification is demonstrated analytically but not empirically. Have the authors simulated or estimated the effective $\\epsilon$-$\\delta$ improvement to validate the theoretical claim?\n\n1) RW-Meta assumes that all learners observe the exact same privatized data stream. In more realistic scenarios, learners might instead see partially correlated noisy versions of the same underlying data. Could the authors comment on whether their analysis could extend to this setting, and how such correlated noise would affect both privacy and regret guarantees?\n\n2) RW-Meta maintains and updates full covariance matrices across learners. Up to what number of learners $m$ is this tractable in practice? What are realistic values of $m$? Could approximate or sparse updates mitigate the cost?\n\n3) The evaluation focuses solely on a COVID-19 hospital dataset with one prediction task, which feels somewhat artificial. Can the authors explain why this setup meaningfully represents real online decision problems under local privacy, or discuss how their methods might generalize to more natural data streams?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Extends the prediction-with-expert-advice framework to the local DP regime.\n- RW-AdaBatch builds on RW-FTPL, showing that when its predictions stay stable, several updates can be grouped together. This  effectively mixes them like shuffling does in batch privacy, hence, gains privacy at little extra cost.\n- Introduces a new LDP setting where the meta-learner selects among data-dependent experts sharing the same privatized data stream. \n- In RW-Meta, the idea of reusing noise across learners is interesting.", "weaknesses": "- The work’s strength is theoretical rather than practical. Local-DP assumptions are hard to satisfy in realistic online settings, and the empirical evaluation is limited in scale and scope.\n- The novelty seems to be low. RW-AdaBatch’s batching idea is a reformulation of existing privacy-amplification and RW-Meta reuses known post-processing principles rather than introducing a fundamentally new privacy mechanism.\n- RW-Meta’s design involves maintaining and updating full covariance matrices across all learners, which is feasible for small ensembles but would scale poorly if the number of learners grows, limiting practical flexibility.\n- The COVID-19 hospital experiment is limited (three states, one task), lacks baselines under equal conditions, and provides little sense of how privacy actually trades off against accuracy.\n- The paper is dense and somewhat hard to follow. Intuitions such as why batching helps or how covariance correction works are found in the proofs rather than illustrated clearly in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Ob86lCkXCe", "reviewer": "Reviewer_J3Gx", "summary": "This paper studies the classical problem of prediction with expert advice under local differential privacy (LDP) constraints. The authors show that an existing algorithm naturally satisfies LDP. Moreover, the authors extend this algorithm to two new ones, named RW-AdaBatch and RW-Meta. RW-AdaBatch leverages the limited switching behavior of the existing algorithm to achieve adaptive privacy amplification while incurring a minimal cost to utility. RW-Meta extends the classical algorithm to data-dependent experts, which themselves are online learning algorithms. Finally, the authors complement their theoretical results with experiments on real-world data reported by hospitals during the COVID-19 pandemic.", "questions": "See weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper studies an important problem at the intersection of privacy and online learning\n- The theoretical results seem to be novel, and the experimental results are strong.", "weaknesses": "My biggest issue with this paper is its lack of clarity regarding the significance of its results. While I don't doubt that results and proofs are novel, I am having a hard time seeing what these results improve upon in private online learning. \n\nFor example, a regret bound of $\\frac{\\sqrt{T}}{\\eps}$  under local DP can be derived from Theorem 4.1 in [1] by doing the same analysis except using the full-information multiplicative weights algorithm instead of EXP2.  In light of this, what are the main contributions of your work? Do you obtain a better privacy-utility tradeoff than this? Is your algorithm more efficient than running MWU on the noisy loss vectors? Do your algorithms obtain better central privacy-utility tradeoffs? More generally, why should I run your algorithm over just MWU on the noisy loss vectors?\n\nIn addition, as there are no closed-form privacy guarantees, it was not clear to me how the proposed algorithms will be practically useful. That is, how should a practitioner translate their desired privacy guarantee to the correct hyperparameters in the proposed algorithms? It would be great if the authors could walk me through how to do this.  \n\n[1] Agarwal, Naman, and Karan Singh. \"The price of differential privacy for online learning.\" International Conference on Machine Learning. PMLR, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "GCWW292zN8", "reviewer": "Reviewer_1cZk", "summary": "The work studied the problem of prediction from expert advice under local differential privacy constraints. Building on random-walk follow-the-perturbed-leader (RW-FTPL), the authors first showed that the perturbation in RW-FTPL can imply LDP guarantee. Based on it, they designed the RW-AdaBatch algorithm to achieve privacy amplification. And they also designed RW-Meta algorithm for dynamic environments by adopting a noise-sharing scheme. They provided stability,  theoretical privacy and utility analysis for RW-FTPL and regret guarantee for RW-Meta. Finally, they also provided empirical results on the COVID-19 task to show the advantages of their methods.", "questions": "1. Why is the description for RW-FTPL from lines 188-192 different from Algorithm 1? \n2. The final step in Algorithm 2: set a new delay using Theorem 1. It is unclear to me how to set it. Can you explain more about it?\n3. What does \"Ada\"  mean in \"RW-AdaBatch\"? Could you please give some explanation for it?\n4.  What is the advantage of RW-AdaBatch compared with RW-FTPL? And from your Table 1, the regret of RW-AdaBatch is worse than RW-FTPL where $\\alpha>0$?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The paper investigated an interesting problem of prediction from expert advice in online learning under differential privacy.\n2. The paper provided some theoretical analysis and guarantees.\n3. The authors implement their methods on real data.", "weaknesses": "1. The statement of writing and notation is confusing. For example, the paper mixed the statements of LDP and CDP. In the title, the authors used LDP, but in many places, they claim CDP. For the privacy parameter, somewhere $\\epsilon$ is used, and somewhere $\\mu$ is used.\n2. Lacks direct numerical comparisons with recent LDP online learning works [1].\n3. See more in the Questions part.\n\n[1]. Cheng, Duo, Xingyu Zhou, and Bo Ji. \"Follow-the-Perturbed-Leader for Adversarial Bandits: Heavy Tails, Robustness, and Privacy.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "tGQY2HAamj", "reviewer": "Reviewer_M68M", "summary": "This paper studies the problem of online prediction with expert advice under local DP constraints. It introduces two algorithms, RW-AdaBatch and RW-Meta, and provides theoretical analyses of the proposed methods. The paper also includes experimental results on a real-world dataset.", "questions": "- In Line 151, the authors state that the LDP guarantees still hold even against adaptive adversaries. Does the algorithm also remain valid in the adaptive setting? If so, what is the utility in this case?\n- Why is there no experimental comparison with Asi et al. (2023)? From Line 103, the authors mention that Asi et al. (2023) studies the high-dimensional regime. Could you further what this means and why it makes direct comparison difficult?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper studies a relevant problem.\n- The proposed methods are supported by formal regret bounds and empirical experiments on real-world data.", "weaknesses": "- From Table 1, the proposed algorithms appear to improve over RW-FTPL only by a small constant factor, which does not seem significant.\n- The paper lacks a regret lower bound for the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)