On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds
Authors: David Woodruff
Fred Zhang
Samson Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
memory efficiency
sub-linear algorithm
communication lower bound
TL;DR: We provide memory-efficient, robust algorithms for online leearning with experts

Abstract: In the online learning with experts problem, an algorithm makes predictions about an outcome on each of $T$ days, given a set of $n$ experts who make predictions on each day. The algorithm is given feedback on the outcomes of each day, including the cost of its prediction and the cost of the expert predictions, and the goal is to make a prediction with the minimum cost, compared to the best expert in hindsight. However, often the predictions made by experts or algorithms at some time influence future outcomes, so that the input is adaptively generated. 

In this paper, we study robust algorithms for the experts problem under memory constraints. We first give a randomized algorithm that is robust to adaptive inputs that uses $\widetilde{O}\left(\frac{n}{R\sqrt{T}}\right)$ space for  $M=O\left(\frac{R^2 T}{\log^2 n}\right)$, thereby showing a smooth space-regret trade-off. We then show a space lower bound of $\widetilde{\Omega}\left(\frac{nM}{RT}\right)$ for any randomized algorithm that achieves regret $R$ with probability $1-2^{-\Omega(T)}$, when the best expert makes $M$ mistakes. Our result implies that the natural deterministic algorithm, which iterates through pools of experts until each expert in the pool has erred, is optimal up to polylogarithmic factors. Finally, we empirically demonstrate the benefit of using robust procedures against a white-box adversary that has access to the internal state of the algorithm.

On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds
David P. Woodruff
Fred Zhang UC Berkeley z0@berkeley.co edu
Samson Zhou Texas A&M University samsonzhou@@mail.co
CMU
dwoodruf@cs. cmu. edu
Abstract
In the online learning with experts problem, an algorithm makes predictions about outcome each of 7 days, given set of n experts who make predictions on each day. The algorithm is given feedback on the outcomes of each day, including the cost of its prediction and the cost of the expert predictions, and the goal is to make a prediction with minimum cost, compared hindsight. However, often the predictions made by experts or algorithms at some time influence future outcomes, so that the input is adaptively generated.
the best expert
In this paper, we study robust algorithms for the experts problem under memory con- straints. We first give randomized algorithm that is robust to adaptive inputs that R'T Ing
uses O RVT space for regret R when the best expert makes M = O
mistakes, thereby showing a smooth space-regret trade-off. We then show a space lower bound of 52
( (MM) for any randomized algorithm that achieves regret R with RT
probability 1 2 R(T)) Such an algorithm is useful for adaptive inputs, the failure probability is low enough to union bound over all computation paths. Our result implies that the natural deterministic algorithm, which iterates through pools experts until each expert in the pool has erred, optimal up to polylogarithmic factors. Finally, empirically demonstrate the benefit of using robust procedures against white-box adversary that has access to the internal state of the algorithm.
Introduction
Online learning with experts is fundamental problem in sequential prediction. On each of T days, an algorithm must make a prediction about an outcome, given set of n experts who make predictions on the outcome. The algorithm is then given feedback on the cost of its prediction and the expert predictions for the current day. In the discrete prediction with experts problem, the set possible predictions is restricted to finite set, and the cost is 0 if the prediction is correct, and otherwise. More generally, we assume the costs are restricted to be in a range [0, ) for some fixed parameter with lower costs indicating better performance. This process continues for the T days, after which the performance (total cost) of the algorithm is compared to the performance (total cost) of the best performing expert. In particular, the goal for the online learning with experts problem is minimize the regret, which is the amortized difference between the total cost of the algorithm and the total cost of the best performing expert, i.e., the expert that incurs the least overall cost.
well-known folklore algorithm for handling the discrete prediction with experts problem is the weighted majority algorithm [42]. The deterministic variant of the weighted majority algorithm simply initializes "weights" for all experts to 1, down-weights any incorrect expert on a given day, and selects the prediction supported by the largest weight of experts. The algorithm solves the discrete prediction with experts problem with (M + log n) total mistakes, where M is the number of mistakes made by the best expert, thus achieving total regret O (M log n.). More generally, large
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

body of literature has studied optimizations to the weighted majority algorithm, such as a randomized variant where the probability of the algorithm selecting each prediction is proportional to the sum of the weights of the experts supporting the prediction. The randomized weighted majority algorithm achieves regret Vlogn/ n/T) [42], which has been shown to be information -heooretihaoolllly optimal,
up constant. There have subsequently been many follow-ups the weighted and randomized weighted majority algorithms that achieve similar regret bounds, but improve in other areas. For example, on variety of structured problems, such as online shortest paths, follow the perturbed leader [38] achieves the same regret bound as randomized weighted majority but uses less runtime on each day. In addition, the multiplicative weights algorithm achieves the optimal v n (2T") regret, with tight leading constant [33]. However, these classic algorithms use a framework that maintains the cumulative cost of each expert, which requires the algorithm to store (2()) bits of information.
Memory bounds. Recently, [49] considered the online learning with experts problem when memory is a premium for the algorithm. On the hardness side, they showed that any algorithm achieving a target average regret R. requires Q2
n space, which implies that any algorithm achieving the (vlog regret must use near-linear space. On the other hand, when the number of mistakes M made by the best expert is small, i.c., M = O (RPT), [49] gave a randomized
information-theoreen
algorithm that uses Ō ( m space for arbitrary-order streams, thus showing that the hardness of their lower bound originates from a setting where the best expert makes large number of mistakes.
Subsequently, [47] considered the online learning with experts problem when the algorithm is limited to memory sublinear n. They introduced a general framework that achieves (T)) regret using o(n) memory, with trade-off parameter between space and regret that obtains On, (T44/) regret with O (Vn) space and On (T0.67) regret with (n.9 space.
Adaptive inputs. Up to now, the discussion has focused on oblivious setting, where the input to the algorithm may worst-case, but chosen independently of the algorithm and its outputs. The online learning with experts problem is often considered in the adaptive setting, where the input to the algorithm is allowed to depend on previous outputs by the algorithm, c.g., in financial markets, future stock quotes can depend on previous investment choices. Formally, we define the adaptive setting as a two-player game between an algorithm D and an adversary A that adaptively creates the input stream D. The game then proceeds in days and on the t-th day:
The adversary A chooses the outputs of all experts on day l as well as the outcome day t, depending on all previous stream updates and all previous outputs from the algorithm D. (2) The outputs (i.e., predictions) of all experts are simultancously given to the algorithm D, which updates its data structures, acquires fresh batch R, of random bits, and outputs predicted outcome for day t.
(3) The outcome of day revealed to D. while the predicted outcome for day by D is revealed to the adversary A.
The goal of A is to induce D to make many incorrect predictions possible throughout the stream. is clear that any deterministic algorithm for the online learning with experts problem will maintain the same guarantees in the adaptive model. Unfortunately, both the algorithms of [49] and [47] are randomized procedures that rely on iteratively sampling "pools" of experts, which can potentially be exploited by an adaptive adversary who learns the experts sampled in each pool. Interestingly, both the randomized weighted majority algorithm [42] and the multiplicative weights algorithm [33] are known to be robust to adaptive inputs.
1.1 Our Contributions
In this paper, we study the capabilities and limits of sublinear space algorithms for the online learning with experts problem on adaptive inputs.
Robust algorithms. Towards adaptive robustness, it is natural to study deterministic algorithms, since they retain the same guarantee under adaptive adversaries. As warm-up, we first provide simple deterministic algorithm that uses space Ô (nM) Consider an algorithm that iteratively [TT)
2

---

RT experts and running the deterministic majority algorithm on the experts in the pool, while removing any incorrect experts from the pool until the pool is completely depleted, at which point the next pool of O R.M experts is selected. The main intuition is that each pool can incur most O (logr) mistakes before is depleted and the best expert can only make M mistakes. By the time the pool has cycled through n.M experts, i.e., M times for each of the experts, then the best expert no longer makes any mistakes and will retained by the pool. Thus, the total number of mistakes made by the algorithm is 2M O (log n). On the other hand, for target average regret R. the mistake bound of the algorithm is required to be at most M + RT, so it suffices to set l = 0
selects the next pool of k = Ō R.M
RT
RT to achieve regret R. Since the algorithm runs deterministic majority on a pool of experts, then this algorithm uses Ō RT space. Formally, we show:
aM)
== δ PM RT
Theorem 1.1 (Simple deterministic algorithm; see Section 3.1). Suppose the best expert makes M 4M logn, There exists deterministic algorithm (Algorithm 2) that uses space mistakes and let R 2 T T,
B.M RT
and achieves an average regret of R.
The algorithm is simple, computationally efficient, and easy to implement. However, the drawback is that for M = (RRT), the algorithm requires space near-linear in the number of experts n, which is undesirable when is large. To address this issue, complement our deterministic algorithm with a randomized algorithm that is robust to adaptive inputs and allows for a different memory-regret trade-off:
Theorem 1.2 (Robust randomized algorithm). Let R >
64 log" and suppose the best expert makes T
RT mistakes. Then there exists an algorithm for the discrete prediction with at most M S 128 log
experts problem that uses Ô ("TT) space and achieves regret most R, with high probability.
This gives a trade-off between the space and regret, almost all the way to the information-theorrtie limit of R On (VI/T) for general worst-case input. However, it incurs a multiplicative space
overhead of Ö(VT) compared to the optimal algorithms for oblivious input. Thus we believe the complete characterization the space complexity of the discrete prediction with experts problem with adaptive input is natural open question resulting from our work.
Tight memory bounds for robust algorithms. It is natural to ask whether there exist robust algorithms that are more space-efficient than the straightforward deterministic approach. For example, [12] showed that any oblivious randomized algorithm with failure probability 2 2-Q(x2) will be robust against adaptive outputs in the discrete prediction with experts problem, so reasonable approach would be to boost the success probability of existing oblivious algorithms 1 2 2-9())) Unfortunately, we show this cannot work:
Theorem 1.3 (Memory lower bound for sigh-rrbability algorithms). For n = o(2T), any random- ized algorithm algorithm that achieves R regret with probability at least 1 - 2 for the discrete space when the best expert makes M mistakes. RT
prediction with experts problem must use Q nM
In particular, Theorem 1.3 shows that any deterministic algorithm must use Z (nAd) space, which taken together with the deterministic procedure above, resolves the deterministic streaming complexity of online learning with experts. We emphasize that Theorem 1.3 also shows that using the strategy of high-probability randomized algorithms to guarantee robustness against adaptive input does not work any better than a deterministic algorithm.
At a conceptual level, our lower bound in Theorem 1.3 shows that surprisingly, the number A of the mistakes made by the best expert is an intrinsic parameter that governs the abilities and limitations of robust algorithms in this model. Thus, even though M is not a parameter that may naturally be ascertained in practice, it nevertheless completely characterizes the complexity of the problem. On the other hand, for algorithmic purposes, it suffices to acquire a constant- factor approximation to M as input to the algorithm.
Another reason Theorem 1.3 is somewhat surprising is because as the number of mistakes M made by the best expert increases, then the algorithm is also permitted to make more mistakes and in some sense, the problem seems "easier". However, Theorem 1.3 shows this intuition not true the problem actually becomes more difficult as M increases.
3

---

Moreover, we give an alternative proof in the regime when M = Q(T).. The proof differs from the proof of Theorem 1.3. Instead, leverages the communication complexity of new set disjointness problem, recently proposed by [39]. The statement is technically weaker Theorem 1.3 and appears in the appendix; see Appendix E.
Empirical evaluations. Finally, we conduct experimental evaluations in Section 5 by comparing the natural deterministic algorithm to the randomized algorithm of [49] against white-box adversary who has access to the internal state of the algorithm, including any experts sampled and maintained by the algorithm. The deterministic algorithm iteratively selects pools of l = Ó n
TET experts, discarding any expert that has erred, and refreshing the pool with the next batch of experts once the pool is emptied. The randomized algorithm similarly discards erroneous experts from pool of k experts, but it repeatedly samples pools of experts rather than selecting the next pool of k experts. On average across the multiple trials for each setting, the randomized algorithm made several times more mistakes than the deterministic algorithm, ranging from 1.98x times more mistakes to 3.29x times more mistakes than the deterministic algorithm, thus demonstrating the importance of robust algorithms against adversarial inputs.
1.2
Related Work
The experts problem and memory bounds. The experts problem has been extensively studied [17], both in the discrete decision setting [42] and in the setting where costs are determined by various loss functions [35, 52-55J. Hence, the experts problem can be applied to many different applications,
such portfolio optimization [24, 23], ensemble boosting [32], and forecasting [37]. Given certain assumptions on the expert, such as assuming the experts are decisions trees [36, 50), threshold functions [43], or have nice linear structures [38], additional optimizations have been made to improve the algorithmic runtimes for the experts problem and more generally, existing work has largely ignored optimizing for memory constraints in favor of focusing time complexity regret guarantees, thus frequently using ((n) memory to track the performance of each expert.
Recently, [49] introduced the study of memory-regret trade-offs for the experts problem. For >> T, [49] showed that the space complexity of the problem is Ô (RTT) in the random- ooder streams,
KT space for arbitrary-order streams when the number of mistakes M made by the best expert is "small". Subsequently, [47] considered the online learning with experts problem for >>>>> ni, introducing a general space-regret trade-off framework that achieves o(T) regret using o(n) memory, including (T1/55) regret with (vπ) space and 0.667 regret with O (n9. space.
but also gave a randomized algorithm that uses Ō a
Concurrent and independent work. Concurrent to our work, [46] considered a variant of the problem where at each time, the algorithm selects expert instead of prediction. They then introduce an algorithm robust against an adaptive adversary who observes the specific expert chosen by the algorithm each time, well lower bounds for any algorithm robust such an adversary.
One way to ensure adversarial robustness is through deterministic algorithms. On that end, we achieve stronger lower bounds for deterministic algorithms, showing that there must be a dependency on the number M of mistakes made by the best expert, i.e., any deterministic algorithm achieving amortized regret R must use
nM
space. In fact, when the number of mistakes M made by the RT
T for amortized regret R, we give randomized upper bound that uses less space than this lower bound. By comparison, the lower bound of [46] shows that any algorithm achieving R amortized regret must use Ω (v R2) space, though their lower bound also applies to randomized algorithms.
best expert is sufficiently small, i.e., M = O Log?
Due to the difference in setting, our algorithmic techniques are quite different from those of [46]. We use recent idea of [34, 4, 10] to hide the internal randomness of our algorithm from the adversary whereas [46] rotates between groups of experts to prevent an adversary from inducing high regret by making specific expert bad immediately after it is selected.

---

2
Preliminaries
Xt-1), For any & S 7 and vector X2. .n), we let Xet denote (X Xst = (X,,.., Xx), and X_, (X1, X,-1, X " Xn).
Also, Xst and X²1 are defined simi- larly. Let e; denote the ith standard basis vector, and for any S. eg the vector that has a at index i E S and 0 everywhere else. For random variable X, let H (X) denote its entropy.
We write [n] for an integer n > 0 to denote the set {I,..., n). We write voly(n) to denote fixed polynomial in n. If an event occurs with probability at least poly(n.T)) we say the event occurs with high probability. We give additional technical preliminaries Appendix B.
Formal problem statement. In the online learning with experts problem, there are experts that each make predictions on each of days. The prediction are in {0, 1]. An algorithm uses the experts to output prediction for each day & E [T]. The actual outcome of the day t is then revealed, at which point the algorithm is penalized with a cost that if the prediction is correct, and otherwise.
This process continues for the T days. At the end, suppose that the best expert has incurred cost M. while the algorithm has incurred C. Then the performance of the algorithm is measured by the (average) regret R = max (-M.0))
Differential privacy. We use tools from differential privacy.
Definition 2.1 (Differential privacy, [30]). Given a privacy parameter & > and a failure parameter
ò E (0, 1), randomized algorithm A : X + y is (e, -diffeelire private if. for every pair of neighboring streams S and S' and for all E Y,
Pr (A(S) E EJ e Pr(A(S") E +
Theorem 2.2 (Private median, e.g., [34]). Given a database 'D E X", a privacy parameter & >> O and a failure parameter E (0, 1), there exists an (e, d)dfifferettially private algorithm PRIV MED that outputs an element x E X such that with probability at least 1 5, there are at least |S] m elements in S that are at least x, and al least 1S]
elements in S that are at most for
O log [X] 5
Theorem 2.3 (Advanced composition, e.g., [31]). Let 8' E (0, 1] and let 8 E [0, 1]. Any mecha- nism that permits k adaptive interactions with mechanisms that preserve (E, -dddffrifrrentiill privacy guarantees (E', kō + 8') d-differential privacy, where e'
= /2 In &
- 2k
Theorem 2.4 (Generalization of DP, e.g., [29, 9D. Let (0, E (0,e/4), and n 2
2² log 8
Suppose : X - 2 is an (e, -)differrettial private algorithm that curates a database of size and produces function h X - {0, 1}. Suppose 'D is distribution over X and S is a set of elements drawn independently and identically distributed from D. Then
Pr S S-D.heAIS A(S)
M(x
E [Mxx]] ZND
2 10e
< -
S
FES
3 Algorithms Against Adaptive Adversaries
In this section, we show that there exists algorithms for the discrete prediction with experts problem that is robust to adaptive outputs.
3.1 A Near-Optimal Deterministic Algorithm
We first present simple deterministic algorithm for uubitrary-order streams. The algorithm repeatedly selects pools of the next A Ö a.M) experts. While the pool non-empty, the algorithm runs the JET
deterministic majority algorithm on the algorithm and removes any incorrect experts from the pool.
Once the pool is empty, the next Ō n experts multiple times if necessary, where an expert can be added the pool again even if has
(MM) RT
experts are added to the pool, possibly cycling through all
been previously deleted from the pool. We give the formal algorithm and analysis in Appendix C.
5

---

Theorem 3.1 (Determistic algorithm), Among n experts in stream of length T, suppose the best expert makes M mistakes and let R² 4M log There exists a deterministic algorithm (Algorithm 2) that uses space Ô RT
T
and achieves an average regret of
In light of lower bound Theorem 1.3, it is evident that Theorem 3.1 is nearly optimal, up polyloga- rithmic factors, for deterministic algorithms, which are automatically adversarially robust. On the other hand, does not seem necessary that any adversarially robust algorithm must be deterministic. Indeed, we now give randomized adversarially robust algorithm with better space guarantees.
3.2 A Randomized Robust Streaming Algorithm
We first recall the following randomized algorithm for arbitrary-ordet streams with oblivious input, Le., non-adaptive input:
Lemma 3.2 (Algorithm for oblivious inputs; [49]). Let R
V
128 log" n and suppose the best expert T
makes most M I 1280 log" mistakes. Then there exists algorithm DISCPRED for the discrete RT space and achieves regret at most R, with high
R²T
prediction with experts problem that uses Ö
probability, i.e., probability al least poly(n.T))
The algorithm of Lemma 3.2 for constant probability proceeds by sampling pools of k Ō n experts and running majority vote on the pool, while iteratively deleting poorly performing experts until no experts remain in the pool, at which new pool of k experts is randomly sampled. The main intuition that either the pool of experts will perform well and achieve low regret, or the pool will be continuously re-sampled until the best expert is sampled multiple times, after which point it will not be deleted from the pool. Unfortunately, it not evident that this algorithm is robust to adaptive inputs because adversary can potentially learn the experts in each sampled pool and force the experts to make mistakes only on days which they are sampled by the algorithm. To boost the algorithm to high probability of success, we take the deterministic majority vote of O (logn) independent instances of the algorithm with constant success probability.
TT
Towards adaptive robustness, we use differential privacy to hide the internal randomness of the algorithm, and in particular, the identity of the experts that are sampled by each pool. We first run Õ(vT) copies of the algorithm and then output the private median of the Ö(VT) copies, guaranteeing roughly (o(TT):0) -ddmy,--)diiffeeettiaa differential privacy because we use Ö(VT) copies of the algorithm. Advanced composition, i.e., Theorem 2.3, then ensures (0(1), 1/ (/poly(r))-oifferennta diffferentia privacy, so that correctness then follows from the generalization properties of DP, i.e., Theorem 2.4.
We give our algorithm in full in Algorithm 1.
Algorithm 1 Randomized, robust streaming algorithm for the experts problem Input:
stream of length T with n experts and target regret R
Output: A sequence of predictions with regret R
1: Run m =0 O -o--=OTooloooo (VTlog(?Z) independent instances of DIscPRED with regret &
2: Run PRIVMED on the m instances with privacy parameter & O (vil and failure
probability polyin.
3: At each time / E [T). select the output of PRIVMED
Next, we show the correctness of our algorithm on adaptive inputs.
/ 22048log" log' and suppose the best expert T
Theorem 3.3 (Algorithm for adaptive inputs). Let R
makes most M <
1280 1280log2 n mistakes. Then there exists algorithum for the discrete prediction
RºT
with experts problem that uses δ RVT space and achieves regret at most R, with probability at least 1 poly(n,TT'

---

Proof. Suppose we run m O ( log(n()) independent instances of DISCPRED with regret R.
Note that for R. 2048 log'n we have
which is valid imput to DISCPRED in Lemma 3.2. By Lemma 3.2, each instance succeeds on arbitrary-order stream with probability least 1 - h/ppll((r) (,, T). By a union bound over the m instances, all instances succeed with probability T). In particular, each instance has regret at most R/4, that the total number
128 12g'
least 1 - 1/ooly of mistakes by each instance is at most M + RT /4. Thus, the total number of mistakes by all instances is at most (M RT/4).
To consider an adaptive stream, observe that PRIVMED called with privacy parameter O (iVoTog)(TT and failure probability 1. 1/poly(n, T). By Theorem 2.3, the mechanism permits T adaptive interactions and guarantees privacy O (1) with failure probability 1/poly T). By The- orem 2.4, we have that with high probability, if the output of the algorithm incorrect, then at least m/3 of the instances DISCPRED
also incorrect. Since the total number of mistakes by all instances is at most m. (M + RT/ /4), then the total number of mistakes by the algorithm is at most R²T
3 (M + RT/4) & M RT, since M
Hence, the algorithm achieves R regret with
1280 n
high probability.
space. Since use By Lemma 3.2, each instance of DISCPRED uses Ô (T))
O (TTlognTT) independent instances of DISCPRED, then the total space is Ô RVT
4 Lower Bound for Arbitrary-Order Streams
In this section, we provide space lower bound for randomized algorithms with a high probability of success. Together with Theorem 1.1, the lower bound completely characterizes the complexity of deterministic algorithms for the online learning with experts problem. We restate Theorem 1.3, give a proof sketch and defer the full analysis Appendix D.
Theorem 4.1 (Memory lower bound for high biigh--rbbbbiityy algorithms). For n = o(2 any random- ized algorithm algorithm that achieves R regret with probability at least 1 - 2-00(T) for the discrete space when the best expert makes M mistakes.
prediction with experts problem must use $2 nM
TET
Proof sketch of Theorem 4.1. We consider the communication problem of E-DIFFDIST. It combines n instances of the distributed detection problem given by [14]. This was also used by the prior work of [49] to prove space lower bounds for expert learning in random-order stream.
Specifically, for fixed T. the D-DIFDDITT problem with M consists of T players, who each hold bits, indexed from 1 to n. The players must distinguish between:
(1) the NO case D in which every bit for every player is drawn i.i.d. from a fair coin and
(2) the YES case D(n) in which index L [n] is selected arbitrarily and the L-th bit of each player is chosen i.i.d. from Bernoulli distribution with parameter (1 4), while all other bits for every player are chosen i.i.d. from a fair coin.
At high level, the proof proceeds in two steps:
First, we show that the --DIFDDIST problem can be reduced the expert prediction problem in the streaming setting.
(2) Second, we prove a communication complexity lower bound for DDIIFFISST against any protocol that succeeds with probability 1 2 -(T), which includes deterministic protocols.
The first step is straightforward. In the reduction, each player in an instance of =- DIFFFDIST corre- sponds to a day of the expert problem. The bit input held by each player correspond to the n expert predictions of each day. Therefore, in the NO case, each expert is correct roughly half of the days. In the YES case, there a single expert E [n] that correct on roughly 1/2 + 5 of the days (for 5 = 1/2 - M/T), while all other experts randomly guess each day. Suppose that there is streaming
7

---

algorithm for the expert prediction problem with average regret 8/2. Then roughly speaking, in the YES case, the algorithm is correct approximately on 1/2 + 6/2 of the days, while in the NO case where every expert is randomly guessing, the algorithm is correct on less than 1/2 + 6/2 of the days. This distinguishes the YES and NO case and thus solves E-DIFFDIST.
For the second step, show that solving the D-DIFFDIST problem with probability at least 1-2 1-2-6(7) requires (2n.M) total communication. We give a sketch of the argument below.
Observe that if the input is viewed as a T X n matrix, then DOO is product distribution across columns that can be written as Ç", where Ç is the distribution over a single column such that all entries of the column are ii.d. Bernoulli with parameter z.2 We view DNO as a hard distribution and applies an information complexity analysis. By a direct sum argument, it suffices to show that the single column problem, i.e., distinguishing between DNo and D (i.e., for n 1), requires (2(M) total communication.
Let (C1, C2....,,Cy be a single column drawn from the hard distribution- naabbbttionnmmmll...... the NO case where each player holds one i.i.d. Bernoulli with parameter 1/2. Let A be fixed protocol with success probability at least - exp( (T)). For all i < T. let M, denote the message sent from player P. to player P.+1 and Mci {M, :j < i). Let II II(C1, .r)) be the communication transcript of A given the input (C.) A standard information complexity argument [8] implies that the total communication is at least the information cost, defined as I(C Cr: II. Cr)), where I (X,, Y) denotes the mutual information between random variables X and Y.
The key step now
lower bound the information cost by ((M).. The main ideas are the following. For any i E [T], we say that (M, Mzx) is informative for i with respect to the input C' and the transcript (M1, M2. ......... Mr) ) if
Pr PC, = Mc.) Pr M,
M,, Mc.) 2c
(4.1)
for some constant c > 0. Otherwise, we say that M, is uninformative. Informally, an informative message Md reveals sufficiently large information about C₁ so that the mutual information (M,, C2 Mci) would be large. Let p4 be the probability that (M,, Mi) is informative. Intuitively, we need that Σ, Pt large, because then there would be sufficiently many informative messages, and so the information cost is high. To formalize this approach, we claim two key lemmas. First, by Lemma D.9
T
T Σ
(111; C1, Cz...,, Cr) = Σ (M Mcj) 20
Pj
5=1
Conceptually, this shows that the information cost is at least the expected number of informative messages. Furthermore, by Lemma 1.10, the latter is indeed high, and in particular, >; Pj 2 ((M). Much of the technical work is dedicated to prove these lemmas. This finishes the proof since the communication complexity is lower bounded by the information cost.
5 Experimental Evaluations
In this section, we perform experimental evaluations as a simple proof-of-concept demonstrating the importance of deterministic algorithms against adversarial input.
Experimental setup. We assume a white-box adversary with access to the internal state of the algorithm. We evaluate the natural deterministic algorithm that iteratively selects pools of RT experts, discarding any expert that has erred, and refreshing the pool with the next batch of k experts once the pool is emptied. As baseline, we compare to a randomized algorithm that repeatedly samples pools of k- Ô nM
experts, discarding any expert that has erred, and refreshing the pool with the next batch of sampled experts once the pool is emptied.
RFF
Provided that the best expert has not yet made M mistakes, the adversary simply compels the experts in each pool to err. Once all experts have made at least M mistakes, the adversary gives up and permits all subsequent predictions to be correct. It can be theoretically verified that against such an adversary, the deterministic algorithm is the optimal algorithm, in the sense that it achieves the smallest number of errors.
8

---

Experimental details. We first evaluate our experiments on the setting n 10000, M = 20, and T 1000 across various values of R E {0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35). For each setting of R, we ran the experiment 20 times, recording the runtime and number of errors by the algorithms in each repetition. We then computed the minimum, mean, and maximum number of errors by the randomized algorithm across all 20 repetitions. We then repeated the experimental setup for 10x larger setting of T, i.e., n = 10000, 64-bit operating system using AMD Ryzen 7 5700U CPU with 8.00 GB RAM and 8 cores with base clock 1.80 GHz.
20, and T' 1000. Our experiments were performed on a
Results. Our experiments show that the deterministic algorithm performs significantly better than the randomized algorithm. On average across the 20 trials for each setting, the randomized algorithm made several times more mistakes than the deterministic algorithm, ranging from 1.98x times more mistakes for the setting n = 100000, MM = 20, T 1000, R = 0.05 to 3.06x times more mistakes for the setting n 100000, M 10, 7 10000, algorithm over all trials, which occurred at the setting = 100000, M = 20, T 1000, R 0.05, the randomized algorithm made 1.9x times more mistakes than the deterministic algorithm. Meanwhile, the worst performance by a randomized algorithm over all trials, which occurred at the setting n = 100000, .M = 10, T = 10000, I = 0.25, the randomized algorithm made 3.29x times more mistakes than the deterministic algorithm. The average runtime each batch of 20 experiments for the setting of n = 100000, M = 20, = 1000, R = 0.05 while the average runtime 98 seconds for each batch of 20 experiments for the setting of n 100000, M = 10, T 10000, R = 0.3 was roughly 350 seconds. See Figure for summary.
0.3. Even the best performance by a randomized
98 seconds for
900
Range 8/75
10000
Range
#Vg. rend. etrs
det. cmr
700
8000
Adbal Number of taraa
Actual Number Errors
500
6000
4000
300
2000
130
0
0.03
0.10
0.15
0.20
0.2b
0.30
0,1
larget (Amar (ommmttaddddddmoommmmmmm Hagret
Target (Amort Dee)) Pagret
(a) 100000, M 20, T = 1000
(b) 100000, M 10, = 10000
Figure 1: Comparison of errors made by deterministic algorithm and average number of errors made by randomized algorithm across 20 repetitions for each trial, across various values of input target regret R. Minimum and maximum numbers of errors by randomized algorithm across each trial are also reported.
6 Conclusion
In this work, we provide robust streaming algorithms for learning with experts. We provide a deterministic algorithm parametrized by the number of mistakes made by the best expert. We also give randomized algorithm with a different space-regret trade-off, based on differential privacy. We complement our algorithms with a lower bound for high-probability success algorithms. This gives tight memory lower bound for deterministic algorithms. We then show the importance robust algorithmic design by empirically comparing the performance of the natural deterministic algorithm and the state-of -h- randomized algorithm when the inputs are adaptive.
We remark that our results do not rule out space-efficient robust algorithms that match the bounds of the oblivious randomized algorithm of [49] for constant probability success. We believe whether or not there exists such algorithm is fascinating question for future work.

---

Acknowledgments
David P. Woodruff and Samson Zhou were partially supported by Simons Investigator Award and by the National Science Foundation under Grant No. CCF-1815840, This work was done in part while Fred Zhang was Google Research, and Samson Zhou was Carnegie Mellon University, UC Berkeley, and Rice University.
References
[1] Miklós Ajtai, Vladimir Braverman, T.S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. Proceedings of the 41st ACM SIGMOD-SIGACT-SIIE Symposium on Principles of Databuse Systems (PODS), 2022.
[2] Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
A
[3] Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Coloring in graph streams via deterministic and adversarially robust algorithms. CoRR, abs/2211.106411, 2022. A
[4] Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS, pages 8:1-8:19, 2023. 1.2, A
[5] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48-77, 2002. A
[6] Dmitri Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD, pages 148-156, 2019. A
[7] Baruch Awerbuch and Robert D. Kleinberg. Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004. A
[8] Ziv Bar- Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. 4, B.5, B.6
[9] Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. 2.4
[10] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022. 1.2,
A
[11] Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense- sparse trade-offs. In 5th Symposium on Simplicity in Algorithum (SOSA @ @ODA), 2022.
[12] Omri Ben- Ben-Eliczer, Rajesh Jayaram. David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. SIGMOD Rec., 50(1):6-13, 2021. 1.1, A
[13] Allan Borodin and Ran EI- Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. A
[14] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communica- tion lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the Firty-eighth Annual ACM Symposium on Theory of Computing (STOC),
2016. 4
10

---

[15] Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems (NeurIPS), 2021. A
[16] Nicolò Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems (NIPS), 2013. A
[17] Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. 1.2, A
[18] Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022. A
[19] Yeshwanth Cherapanamjeri and Jelani Nelson. On adaptive distance estimation. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems, NeurIPS, 2020. A
[20] Yeshwanth Cherapanamjeri and Jelani Nelson. Uniform approximations for randomized hadamard transforms with applications. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 659-671, 2022. A
[21] Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. Robust algorithms on adaptive inputs from bounded adversaries. In 11th International Conference on Learning Representations, ICLR, Conference Track Proceedings, 2023. A
[22] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In International Conference Machine Learning, ICML, pages 41 12-4140, 2022. A
[23] Thomas M Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991. 1.2
[24] Thomas M. Cover and Erik Ordentlich. Universal portfolios with side information. IEEE Trans. Inf. Theory, 42(2))348- -333333,, 1996. 1.2
[25] Daniela Pucci de Farias and Nimrod Megiddo. Combining expert advice in reactive environ- ments. J. ACM, 5365)766 2006.
[26] Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: 22/3 regret. In Annual ACM Symposium on Theory of Computing (STOC), 2014. A
[27] Ofer Dekel, Ambuj Tewari, and Raman Arora. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012. A
[28) Itai Dinur, Uri Stemmer, David Woodruff, and Samson Zhou, On differential privacy and adaptive data analysis with bounded space. CORR, abs/2302.05707, 2023. A
[29] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the Forty- Seventh Anmual ACM on Symposium on Theory of Computing (STOC), 2015. 2.4
[30] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Third Theory of Cryptography Conference (TCC), 2006. 2.1
[31] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In
5 1hth Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010. 2.3
[32] Yoav Freund and Robert E Schapire. A decision- generalization of on-line learning and an application to boosting. Journal of Computer and System Cciences,
1997.
1.2
11

---

[33] Nick Gravin. Yuval Peres, and Balasubramanian Sivan. Tight lower bounds for multiplicative weights algorithmic families. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017. 1,
[34] Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversari- ally robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems (NeurIPS), 2020. 1.2, 2.2, A
[35] David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Tight worst-case loss bounds for predicting with expert advice. In European Conference on Computational Learning Theory (EuroCOLT), 1995. 1.2
[36] David P Helmbold and Robert E Schapire. Predicting nearly as well as the best pruning of a decision tree. Machine Learning, 27(1):51-68, 1997. 1.2
[37] Daniel A Herrmann. Prediction with expert advice applied to the problem of prediction with expert advice. Synthese, 200(4):1-24, 2022. 1.2
[38] Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems.
J. Comput. Syst. Sci., 71(3):291-307, 2005. 1, 1.2
[39] Akshay Kamath, Eric Price, and David P Woodruff. A simple proof of a new set disjointness with applications to data streams. In 36th Computational Complexity Conference (CCC), 2021. 1.1, E.4, E.5
[40] Robert D. Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Advances in Neural Information Processing (NIPS), 2004. A
[41] Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer. Adaptive data analysis with correlated observations. In International Conference on Machine Learning, ICML, pages 11483-11498, 2022. A
[42] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2):212-261, 1994. I, 1.2
[43] Wolfgang Maass and Manfred K Warmuth. Efficient learning with virtual threshold gates. Information and Computation, 141(1):66 83, 1998. 1.2
[44] H. Brendan McMahan and Avrim Blum. Online geometric optimization in the bandit setting against an adaptive adversary. /7th Annual Conference on Learning Theory, (COLT), 2004.
A
[45] Neri Merhav, Erik Ordentlich, Gadiel Seroussi, and Marcelo J. Weinberger. On sequential strategies for loss functions with memory. IEEE Trans. Inf. Theory, 48(7):1947-1958, 2002. A
[46] Binghui Peng and Aviad Rubinstein. Near optimal memory-regret tradeoff for online learning, 2023. 1.2
[47] Binghui Peng and Fred Zhang. Online prediction in sub-linear space. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023. 1, 1, 1.2,
[48] Chloé Rouyer, Yevgeny Seldin, and Nicolò Resa-Bianchi. An algorithm for stochastic and adversarial bandits with switching costs. In Proceeulings of the 38th International Conference
on Machine Learning (ICML), 2021. A
[49] Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2022. 1, 1, 1.1, 1.2, 3.2, 4, 6, D.I, D.I, D. D.3, D.I
[50] Fiji Takimoto, Akira Maruoka, and Vladimir Vovk. Predicting nearly as well as the best pruning of decision tree through dynamic programming scheme. Theor. Comput. Sci., (61 2001. 1.2
[51] Flemming Topsse. Bounds for entropy and divergence for distributions over a two-element set. J. Ineq. Pure & Appl. Math, 2(2):300, 2001. B.I
12

---

[52] Vladimir Vovk. Aggregating strategies. In Proceedings of the Third Annual Workshop on Computational Learning Theory (COLT), 1990. 1.2
[53] Vladimir Vovk. game prediction with expert advice. Comput. Syst. Sci., 56(2):153-173, 1998.
[54] Vladimir Vovk. Derandomizing stochastic prediction strategies. Machine Learning. 35(3):247-
282, 1999.
[55] Vladimir Vovk. Defensive prediction with expert advice. In 16th International Conference on Algorithmic Learning Theory (ALT), 2005. 1.2
[56] David Waje. Rounding dynamic matchings against an adaptive adversary. In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2020. A
[57] David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021. A
13

---

A Additional Related Work on Adaptive Inputs
Motivated by non-independent inputs and adversarial attacks, adaptive inputs have recently been considered in the centralized model [19, 41, 20, 21], in the streaming model [6, 12, 34, 57, 15, 18, 11, 3, 22, 4, 28], and in the dynamic model [56, 10]. In particular, algorithms robust to inputs that depend on the previous outputs by the algorithm, i..., black-box attacks, are also robust to situations which future inputs may be dependent on previous outputs. This is especially relevant in applications such forecasting, in which a prediction on day i can lead to series of actions that might impact outcomes and expert predictions on day i + and beyond.
Adaptive adversaries have received considerable attention in literature for online learning when the goal is simply to achieve the best possible regret [13, 17, 44J. Building off a line results on multi-armed bandit problems [5, 7, 40], the work of [45] first considered the experts setting against memory cenoor--bouned adaptive adversaries, giving an algorithm with regret O (T2/$). An early paper of [25] introduced family of algorithms for adaptive inputs, but provided guarantees using concepts not quite related to the standard definitions of regret. More recent works have explored online learning with additional considerations, such as alternative quantities to optimize [27]. additional switching costs [16, 26, 48], and feedback graphs [2]. The closest work to setting is the recent result by [47] showing that no algorithm using space sublinear in n can achieve regret sublinear in T when the input is chosen by adversary with access to the internal state of the algorithm, i.c. white-box adversary.
B
Additional Technical Preliminaries
B.1
Information Theory
For any p E [0, 1J. we slightly abuse notation and let H(p) = -p- -ppogg p- logg(1 - p) be the binary entropy function. The following is standard upper and lower bound of H()).
Lemma B.1 (Bound on the binary entropy function; see e.g. [51D) For E [0, 1J. the binary entropy
function satisfies
4p(1 p) s H(p) S 2(p(1-p)))/mmg
B.2 Communication Complexity
Definition B.2 (Mutual information). Let X and Y be a pair of random variables with joint distribution p(z, y). Then the mutual information is defined I(X;Y) == Ex.g p(z, 8) log p(a.y) for marginal distributions p(x) and p(y)-
p(z)n(s))
In multi-party communication problem of L players, each player is given I; E Xr They communi- cate according to fixed protocol to compute function f X₂ x ..... X X + y. A protocol II is called 8-error protocol for f if there exists function Hour such that Pr [oour (II y)) = f (a. y)] > 1-16. 8. For a (multi coalti--rrty) communication problem, we denote the transcript of all communication in protocol 1I E {0, 13*. The communication cost of a protocol, as result, is the bit length of the transcript. Let Rf) denote the minimum communication cost across all 8-error protocols for f.
Definition B.3 (Information cost). Let II be randomized protocol that produces random variable IIX Xr) as transcript on inputs X1...., XT drawn from a distribution p. Then the information cost of II with respect to is defined as I(X1,.... .x:: [[X...... Xx)).
Definition B.4 (Information complexity). The information complexity of a function f with respect to a distribution i and failure probability 8 the minimum information cost of a protocol for f with respect to μ. that fails with probability at most d on every input and denoted by (J),
Lemma B.5 (Information cost decomposition lemma, Lemma 5.1 in [8]). Let p. be mixture of product distributions and suppose is a protocol for inputs (Xi...., XT) n², Then T( Xx; [(X,...,. > Σn T(X Nr.....,,T.;; [[X1...., Xx)),, where Xij denotes the j-th component of X
Lemma B.6 (Information complexity lower bounds communication complexity; Proposition 4.3 [8].
For any distribution μ and error 8, Rs(f) 2 (f)
14

---

TE pools before the entire T pools to iterate through the C Proof of Theorem 3.1 and Formal Algorithm
We give formal description of our deterministic robust algorithm in pseudocode.
Algorithm 2 Deterministic algorithm for the experts problem
Input: A stream of length 7' with experts, upper bound M on the number of mistakes made by the best expert, and target regret R
Output: A sequence of predictions with regret R
k
inM logn
RT
2:
S x
3: while the stream persists do
4: if S is empty then
> We have cycled through all experts once
5:
5 + [n]
6:
Let be the first indices of S
7:
S S
8:
while P 0 do
For each following day, choose the outcome output by the majority of the experts in 10: Delete the incorrect experts on that day from P
9:
now prove the correctness and space complexity of Algorithm 2.
make at most log k < log mistakes RT log n because each time the algorithm makes mistake, at least half of the pool must be incorrect and deleted, so the size of the pool decreases by at least half with each mistake the algorithm mistakes. Note that k I for R > loglo so the
Proof of Theorem 3.1. We first remark that the algorithm
over the lifespan of each pool of size & == 2n. M
algorithm is well-defined.
Since each pool P has size k and there are experts, then there are at most 4n set S, which is initialized to is depleted. Thus, there are at most in
entire set of experts. Moreover, each time the algorithm has iterated through the entire set of experts, each expert must have made at least mistake. This is because expert is only deleted from the pool when it has made a mistake and since all experts have been deleted from P, then all experts have made at least mistake.
Since the best expert makes most M mistakes, then the best expert can deleted from the pool at most M times. In other words, the algorithm can cycle through the entire set of n experts at most M + times.
Hence, the total number of mistakes by the algorithm is at most
2n logn (M + +
S 4n k
4nRT
logn M
log M RT,
4n logn
so the algorithm achieves regret at most R. Since the algorithm selects subset of k 4n. experts, then the space complexity follows.
log
RT
D Proofs of the Lower Bounds for Arbitrary-Ordes Streams
In this section, we give space lower bounds for the experts problem on arbitrary-order streams. As warm-up, we first show in Section D.1 general space lower bound for randomized algorithms when the best expert makes "small" number of mistakes. We then give our main lower bound result Section D.2, showing that any deterministic algorithm achieving regret R must use space (nM when the best expert makes M mistakes.
D.1 Warm-up: Lower Bound for Accurate Best Expert
In this section, we show that any randomized algorithm that achieves regret R must use Ω a space, even when the best expert makes O RT) mistakes. In contrast, [49] give an Q Re lower bound:
space
15

---

Theorem D.1 (Memory lower bound; Theorem of [49]). Let R 0. 2/2 be fixed constants. i.e., independent of other input parameters. Any algorithm that achieves R regret for the experts problem with probability at least 1 p must use at least 92
RT
n
space.
Furthermore, this lower bound holds even when the costs binary, and expert predictions, as well as the correct answers, are constrained to be ii.d across the days, albeit with different distributions across the experts.
The proof of this lower bound exploits a construction where the best expert makes ((T) mistakes. Thus, it is not clear how the space complexity of the problem behaves when the best expert makes smaller number of mistakes, In fact, [49] also give an algorithm that uses Ô n space when the best expert makes O(RT) mistakes, bypassing the aforementioned lower bound.
We now prove that in this small mistake regime, this algorithm is tight. Towards this goal, we first define the e-DIFF problem that reduces to the experts problem. It was proposed by [49] to prove memory lower bounds for the expert problem in random order stream.
Definition D.2 (The E-DIFDDIST Problem). We have I players, each of whom holds bits, indexed from 1 to n. We must distinguish between two cases, which we refer to as "V = 0" and "V = 1". Let po be Bernoulli distribution with parameter 2. i.e. a fair coin, and let μr be Bernoulli distribution with parameter 2 + 8.
(NO Case, "V = -0") Every index for every player is drawn i.i.d. from a fair coin, i.e., Ho-
(YES Case, "V 1") An index L E [n] is selected arbitrarily- the L-th bit of each player is chosen i..dd from μ4. All other bits for every player are chosen i.i.d. from po-
Any protocol that successfully solves the e- E-DIFEDIST problem with constant probability greater than 2 must use at least f2 communication, a result due to [49]:
Lemma D.3 (Communication complexity of e- D-DIFDDIST; Lemma of [49]). The communication complexity of solving the e- D-DIFDISS problem with a constant probability, for any p E [0, 0.5),
The proof of Theorem D.1 by [49] uses n coin flips across each of the T players to form the n expert predictions over each of the T days. In the NO case, each expert will be correct on roughly T days, while in the YES case, a single expert will be correct on roughly T 2 + =T days, so that an algorithm with regret R O(e) will be able distinguish between the two cases. There is slight subtlety in the proof that uses a masking argument to avoid "trivial" algorithms that happen to succeed on a "lucky" input, but for the purposes of our proof in this section, the masking argument is not needed. then follows that the total communication is Ω n across the T players, so that any streaming T
algorithm must use at least ?
n bits of space. R=T
Suppose instead consider the e-DIFFDIST problem over RT players, representing RT days in the experts problem. Moreover, suppose we set & = @(1) in the E-DIFFDIST problem, so that in the NO case, each of the experts will be correct on roughly ier 2 days, while in the YES case, a single expert will be correct on roughly 2- + CRT days, for some constant C > O. Suppose we further pad all of the experts with incorrect predictions across an additional T RT days, so that the total number of days is T, but the number of correct expert predictions remains the same. Then an algorithm achieving regret O( R) will be able to distinguish between the two cases, so that the total communication is (H)) so that any streaming algorithm must use at least ? (x))) bits of space.
RT
Corollary D.4. Let R, p < 1/ be fixed constants, i.e., independent of other input parameters. Any algorithm that achieves R regret for the experts problem with probability at least p must use at least Q RT space even when the best expert makes as few as O RRT) mistakes. This lower bound holds even when the costs binary and expert predictions, well the correct answer, are constrained to be i.i.d. across the days, albeit with different distributions across the experts.
n
Proof. The claim follows from setting T = RT and R = +(1) in the proof of Theorem D.I.
16

---

D.2 Lower Bound for Deterministic Algorithms
We now prove our main space lower bound for deterministic algorithms (Theorem 1.3). We first set up some basic notations and introduce a hard distribution.
(n) Let T be any fixed positive integer. Let NO be the distribution over matrices A with size T such that all entries of the matrix are i..d. Bernoulli with parameter 2.2 i..,, each entry of A is 0 with probability and 1 with probability 3.2 Let D be the distribution over matrices M with size T such that there is randomly chosen column L E [m]. which is i.i.d. Bernoulli with parameter (1 - 3) and all other columns are i.i.d. Bernoulli with parameter 3.2 Let BIASDETECT, be the problem of detecting whether A is drawn from (n) Dio so that BIASDETECT, n is simply the DIFFDIIT problem with
Let be communication protocol for BIASDETECT, that correct with probability at least 1 1 1-cxp(-Q(TT) Since Dio is product distribution across columns, then it can be written Ç", where Ç the distribution over single column such that all entries of the column are i.i.d. Bernoulli with parameter 1. Let BIASDETECT, denote the problem of distinguishing between D and D on a single column, i.c., n = Using ((m) as the hard distribution, we have the following direct sum theorem.
Lemma D.5 (Direct sum for BIASDETECC), The information complexity of BIASDETECT, satisfies
IC ((())) ho 2-0(7) (BIASDETECT.) 2 n IC DCD) 2 errr (BIASDETECT)).
Proof. By definition, Wo = <" is a product distribution over n columns. The lemma follows from the standard direct sum lemma of information cost (Lemma B.5).
With the above direct sum theorem for BIASDETECT,, it now suffices to provide a single-coordings information cost lower bound against BIASDETECT, The proof delayed Section D.3.
Lemma D.6 (Single-coordine) information lower bound). Let E (0, 1) and TT be any protocol with error 8 = 2 ((T) for BIASDETECT;, We have that the information cost of II with respect
is at least
[(II(11, Cz,..., C2)...,Crr)CC C2...., 2 (M)),
(D.I)
where the bits C are i.i.d. single coordinates.
Combining Lemma D.6 with the direct sum theorem (Lemma D.5), we immediately get the following information complexity lower bound for BIASDETECT,;
Theorem D.7 (n-Coordinate information complexity lower bound), Let E (0. Then
IC "oo 22 ecry (BIASDETECT.)) = [(nM).
Proof. This follows by applying the direct sum theorem (Lemma D.5) to the single-coordinate bound Lemma D.6.
This implies that any algorithm with R regret and success rate at least 1 2 1-2-0(T) memory, where M the mistake bound on the best expert.
0(T) requires Ω (nM RT
Theorem D.8 (Memory lower bound for expert learning). Let R, M be fixed and independent of other impul parameters. Any streaming algorithm that achieves R regret for the experts problem with probability at least 2 2-2-((T) ((T) must use least Q aM space, for (2"). where the best expert makes M mistakes.
Proof. We now consider the problem BIASDETECT, on matrix of size RT n. Note that in the
NO case, at any fixed column i E [n], the probability that there are more than TπT M instances of
5
for M < RT is most exp(-c; RT'), for sufficiently small constant e₁ (0, 1). Thus, by
union bound, the probability that there exists an index E [n]] with more than 3RT M. instances of 0 is at most 2n RX))
2
17

---

Similarly in the YES case, the probability that there are fewer than ART M instances of 0 for
5
fixed i [n]] and for M !tT is at most 2 cxx)(-<2RT) for sufficiently small constant C2 (0, 1)
and so by a union bound, the probability that there exists an index E [n]] with fewer than 3RT instances of is at most 2n exp(
4 2
Hence, for n = o(2"), there exists a constant c E (0, such that any algorithm that achieves total regret at most RT with probability at least exp(-cT) can distinguish between the YES and NO cases with probability
exp( exp(-O(T)).
By Theorem D.7 and Lemma B.6, the total communication across the RT players must be least (nnM). Therefore, any streaming algorithm that achieves average R regret for the experts problem with probability at least - 2 (22) must use at least 12( n.M
space.
RT
D.3 Proof of the
Information Cost Lower Bound
We now show the single-coordinate lower bound of Lemma D.6.
Proof of Lemma D.6. Consider a protocol that is correct with probability 1 2 -- and let (C1,C2,... C2..... CT) ~ Ç be a single column drawn from the NO case, where each coordinate i..dd Bernoulli with parameter 1/2. For notational convenience, let IT IT(C,. Cr) denote the transcript given the input (C1, C2,... ... Cr). We consider the one-way message-passinn passing model, where each player P. holds the input C. For all < T, let M, denote the message sent from player P. to player P.+1-
By the chain rule of mutual information, the information cost of the transcript, the left-side of Equation D.1 that we need to bound, can be written as
IIII C1 C2....,,
Σ Ci, Mc
(D.2)
By the independence of une-way communication, we have (M,i C1, ,2....,,r Mz2) = I (M Mez).
(D.3)
Combining the two equalities above, the information cost equals
T I(IIC1, Cr) Σ CM, (
(D.4)
j=1
We now lower bound the right-side. First, we make the following definition. For any i E [7], we say that (M,, Mei) is informative for with respect to the input C' and the transcript II (MI..... Mr) if
[P((C, = 0 M., Mcx) Pr(C, = 1 M,, Mc))
(D.5)
for some constant > O; and uninformative otherwise. Intuitively, an informative index i with respect to (M, Mza) means that conditional on the past messages Mes. the message M, reveals much information about C.. Hence, in this case, I(M,, C2 Mei) would be large. Now for all i [T], let p; be the probability that (M,, Mz)) is informative (for i with respect to and IT).
Conceptually, we need to show that E; is large, since then there would be sufficiently many informative messages, and so the information cost in the left-side of Equation D.4 is high. We formalize this idea in the following lemma.
Lemma D.9. In the setting above, where e > 0 is a constant, the information cost can be lower bounded by
T Σ (MriC, 22 Ω j=1
T
C1, C,.,C,,,,..,))
Σ
Pj
(D.6)
j=1
Proof. We start by expanding the definition of the mutual information terms. For each E T, we have
I IM,; C2 Mzj) -H (C, M2a) H (C, Mg,Ma)
(D.7)
18

---

Since p; is the probability that M; is informative, then by assumption, the expected number of informative indices over the messages MI...., My is f(M) for some f(M) = (M). Thus by Markov's inequality. the probability that the number of informative indices is most 10f(M) o(M) with probability at least 9 Let S be the set of the uninformative indices so that |S| = 10 For the first term, notice that C2 and Maj are independent by one-way communication. Moreover, by definition Cj is Bernoulli with parameter 1/2. Therefore,
H[C, Mca) (I())) - H(1/2) =
For the second term,
either (M,, M&²) informative, which holds with probability Pj. and in this case, the conditional entropy is upper bounded by H (C; M,, M2, I H(1/2 + c/2);
or (M,, Mzj) is uninformative, and in this case, we trivially upper bound the conditional entropy by H (C, Mj, Mej) S 1;
Putting the observations together and using Equation D.7, it follows that
7 C Me²) = H (C3 Mez) - H (C₃ Mj, Mzj)
(pj H1112+111100 c/2) (1 pÿ) 1)
= Pj Pj H11/2+c/2)
2 Pj 1 - (1 (1-1))
where the last step uses the upper bound Lemma B.I. Then we have
1 (M Mej) 2 Pj [ (1 - (221//n))
2 2 P(p;),
where the last step follows since - (1 - 1/21 z²/100 for x E [0, 1]. Summing over
j = 1, .,, I' in Equation D.6 finishes the proof.
To prove the claimed information cost inequality Equation D.I, we show that Σ, P: = 52(M).
Lemma D.10. There exists constant y 0 such that
PJ 7 M. j=1
Σ
Proof. Suppose by way contradiction that Σ Pj = OM... Let be a protocol that sends (possibly random) messages M My on a random input C {0, 13T ~ Ç" drawn uniformly from the NO distribution, i.e., each coordinate of = CI...., CT is picked to be with probability and 1 with probability z. Moreover, suppose A is protocol that distinguishes between YES
instance and a NO instance with probability at least - <T T for some constant >> 0.
8
T 10f((M) = T (M). Let C' be an input that agrees with on the informative indices [T] \ S and is chosen arbitrarily uninformative indices S, so that C C, for i E [T] S.
By definition, each uninformative index only changes the distribution of the output by c1 factor. In particular, for e E (0, 1/2), the probability that the protocol A generates II on input C' is at least times the probability that the protocol A generates II on input C. However, since C' can differ from C" on S, then C can differ from C" on |S| = T 10f(M) = T o(M) indices.
(1-c)" 2
Now since each coordinate of C' is picked to be with probability 1/2 and with probability 1 then the probability that C' contains more than sufficiently large T. But then there exists a choice of C' that contains fewer than
M zeros at least 1 - TM - > 2//2 for
M 2 zeros such that
- Since C" contains fewer than 2 then C' is more A will also output TT with probability at least 2 likely to generated from YES instance and indeed YES instance will generate C' with probability
19

---

2-7. On the other hand, since II corresponds to transcript for which A will output NO, then the e-er probability that A is incorrect on C' is at least T, which contradicts the claim that A succeeds with probability 1 - =-T2=" Thus it follows that Σ Pj (2MM) desired.
Now combine Lemma D.9 and Lemma D.10. This implies that the information cost be lower bounded by
I(II; C12 C2...., Cr) 2
Σ j=1
Pj
2 n,,
(D.8)
for a constant y > 0. This completes the proof.
E An Alternative Proof in the Large Mistake Regime
We give another analysis of the information cost when M (((),, where M is the number of mistakes of the best expert.
Lemma E.1 (Single-Coordinate Information Cost Lower Bound), Let a E (0, 1) and 11 be any protocol with error å = 2- for BIASDETECT,, Suppose that the best expert makes M e'T mistakes for some constant c'. We have that the information cost II with respect to Ç is at least
T(T(C), Cr); Cr) , ((1-c)
(E.1)
where C. ( are i...d single coordinates.
Applying direct sum theorem (Lemma D.5), we get the following information complexity lower bound for BIASDETECT
Theorem E.2 (n-Coordinate Information Complexity Lower Bound), Let c (0, 1) and assume M = eT for some constant d' Then
IC DC),2 (BIASDETECT,) = ((1 - cc)
By an argument similar to Theorem D.8, have:
Theorem E.3 (Memory lower bound for expert learning). Let M cT for some constant é' Any streaming algorithm that achieves constant regrel for the experts problem with probability at least 1 2-2-0(2) must use least M()) space, where the best expert makes M mistakes.
For the purpose of proving Lemma E. we need some technical lemmas.
Lemma E.4 (Lemma 3.5 of (39]). Consider any communication protocol II where each player receives one bit and condition any fixed input b E [0,1)² Each player i be implemented such that, if the other players receive input b_p player't i only observes their inpul with probability d7v(II, I.
Lemma E.5 (Lemma 3.6 of [39]). C (0, 1), p (0, ( and % cloglejoj For set of
binary random variables Y1, Y2, ... Y& such that [,; Yj] = pk, there exists a set C [n] of size ck such that Pr(Y; V. S) k/76-1
Proof of Lemma E.I. Let (C1, C2....,, C,C,) C" be single column drawn from the NO case, where each coordinate is i.i.d. Bernoulli with parameter 1/2. Let M c'T for some constant c'. We consider the one-way message message-passing model, where for all i < T, M, denotes the message sent from player P. player P++1- suffices lower bound
T CI, - -
1=1
by the chain rule of mutual information. We claim that for any
I(I: ((I: I(TI; C,(C_,).
20

---

First, by data processing and the one-way nature of the protocol
T(TI: Cj(Ce;) =
for any j. Now we just need to show that
By chain rule of mutual information, write the right-hand side I(11; C3
= - [[Mss; + (MMsi C C-1)
CM T(M>ji CyMMssyMMMM C2j) Observe that Myj and Cj are independent, conditional on Mgj and Czj. Hence, MM,
and this proves the claim.
Let 1I be the distribution of the protocol transcript when the input is fixed to be E 10" and @ denote the binary XOR. Now we can bound
(II:C,, ... ,. (C) Σ ((;C,ICc)))
Σ (M;CCIC-))
11
Σ
Σ
df (I
bae 11,))
82T
be (0,1)) j=1
1
Σ
Σ
(T IT.)-
(E.2)
8T
Be (0.011) job,=0
Conditioned on an input b E {0, 1) let = [( 14 = 0} and assume for the sake of a contradiction that
Σ
dTv IT. = kp,
(E.3)
where p < 1-c Let P: dry (Ibber II,) for every player E [T]. Lemma E.4 implies that the protocol can be equivalently implemented such that if the other players receive b player i only looks at their input with probability p.. If the player does not look at their bit, then their message M, is independent of their input bit. Let Y; denote the indicator random variable for the event that player looks at their input this equivalent protocol.
It follows from our assumption (E.3) that if the input is 6, then E Eii, Yi] = E. = kp. By
the definition of Y, if for any set S, Y, for all E S, then all players in do not look at their input bits. Let Es denotes the event that Y, 0 for all i S, for some S C {i b, 0}. Then since the players S do not look at their input bits,
@ Es. I1, Es) 0. In particular, using this and the law of total probability, we get that
drv (Ibbay: [T.) = Pr(Es) drv (Tbees EEs, IT, Es) + Pr(Es) drv (Tbeee Eg, Es)
< Pr
(E.4)
By assumption, E [Eit, Yi] kp for < - Applying Lemma E.5, we obtain that there exists set [ (i b, = 0} with |S| = ck such that Pr(Es) 2 e k/ For any < (T <T 2)% < T 2, we have Pr(Es) > eδ, and so Pr(Es) < ed. By Eqn. (E.4), drv(Tlaess 11,)) < 1 - ed. Observe that @ es differs from b by having |S| = ck more 1's; and they have same value at all other coordinates. Recall that typical single-coordinate YES instance, there are T' M number of 1 I's, which is T/2 M more than typical NO instance. Now suppose this
21

---

gap T/2 M < ck; then solving BIASDETECT; is at most as hard as distinguishing and b @ es. Hence, we choose c' such that M cT > T ck, then the protocol II fails with probability greater than d. This is a contradiction.
Thus, for any b such that ck (i: = 0) T/2 M,
(1 [1-c]T]
Σ =
dIv bee; [Tp) s
From (B.2) and Jensen's 's inequality,
20 (l)
This finishes the proof.
22


Reviews:
[{"review_id": "zmWcjxXMye", "reviewer": "Reviewer_gy2q", "summary": "The paper studies the learning with experts problem with a focus on: 1) the trade-off between the memory usage and the regret; 2) robustness against an adaptive adversary who decides the experts’ predictions and the correct prediction on each time step, based on all previous stream updates and the player’s outputs. Below are the three main results:\n- A simple deterministic algorithm (thus robust to adaptive inputs) that iteratively run the majority vote algorithm on subsets of the experts of size $\\tilde O(\\frac{nM}{RT})$ where $n$ is the number of experts, $M$ the number of mistakes of the best expert, $T$ the number of time steps, and $R$ the regret target of the algorithm. The algorithm therefore uses $\\tilde O(\\frac{nM}{RT})$ space to achieve regret $R$.\n- A randomized algorithm that is robust against adaptive input, uses only $\\tilde O(\\frac{n}{R\\sqrt T})$ space, and has regret at most $R$, with probability at least $1-\\frac{1}{poly(n,T)}$. The algorithm runs copies of the random, memory-efficient learning with experts algorithm from [49] (it’s unclear if this algorithm is robust to adaptivity). Differential privacy is used to hide the randomness against the adaptive adversary.\n- A memory lower bound of $\\Omega(\\frac{nM}{RT})$ for any algorithm which achieves regret R with probability at least $1-2^{-\\Omega(T)})$ against an oblivious (i.e. not adaptive) adversary. In particular, this gives an $\\Omega(\\frac{nM}{RT})$ memory lower bound for all deterministic algorithms, showing that their simple deterministic algorithm is in fact optimal. \n", "questions": "- The paper proposes that the difficulty of the problem might depend on M, the number of mistakes made by the best experts, and that the space required increases as M increases. In addition, the guarantee for the random algorithm proposed holds only for small M. In the classical learning with experts problem, similar phenomenon is observed. For instance, for small M the regret is in fact $O(\\frac{1}{T}(\\sqrt{M\\log n}+\\log n)) (section 2.4 in [Cesa-Bianchi, N., & Lugosi, G. (2006)]). Is any connection between the classical setting and the variant considered here, in terms of the effect of small M?\n\nSome minor issues:\n- Line10 $R$ has not been introduced yet. It is also unclear what $M$ is at this point.\n- Line 36, the $O(M+\\log n)$ term seems to be the “total” regret not the average regret as in the rest of the paper, and it’s a bit confusing by saying it’s the regret.\n- line 73, the goal of the adversary stated here is a bit misleading. If my understanding is correct, the guarantees in the theorems are for the regret, not the number of mistakes made by the algorithm. \n- line 119 \"algorithm algorithm\" typo\n- the main theorems are stated twice (in section 1 and section 3), which is not necessary especially given the tight 9-page constraint\n- The notations big-O, O_n, and \\tilde{O} are not clearly defined. It could confusing which terms are suppressed.\n\n\nReferences:\n\nCesa-Bianchi, N., & Lugosi, G. (2006). Prediction, Learning, and Games. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511546921\n", "limitations": "Limitations have been addressed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The deterministic algorithm proposed is simple and achieves the optimal memory usage $O(nM/RT)$. In addition, it’s surprising to see that $M$, the number of mistakes made by the best expert, shows up both in the lower and upper bound of memory, implying that $M$ is an intrinsic parameter related to the robust variant of learning with expert problem. This might provide insights for other related problems. \n\nThe randomized algorithm shows differential privacy can be used to turn (potentially) non-robust algorithms to robust ones by hiding the internal randomness. This idea was explored in recent works [4, 10, 34], and it’s interesting to see its application for the expert problem.  \n", "weaknesses": "Most techniques in the proofs are already used in previous works. For example, the proof of the space lower bound is by a reduction to the communication problem of \\epsilon-DIFFDIST. Similar reduction is already used in the closely related work [49] to show memory lower bound for learning with experts problem with random-order stream. \n\nThe memory lower bound only seems to rule out using oblivious algorithms for adaptive adversaries. In particular, this does not prevent the existence of some algorithm that would have a standard inverse polynomial probability of failure for adaptive adversaries. The lower bound also asks the number of experts to be exponentially large in $T$ ($n\\geq 2^T$), which is also restrictive. It could be useful if the authors could expand on whether this is a reasonable regime for lower bounds.\n\nThe algorithms need to know $M$, the number of mistakes of the best expert, which in practice, one cannot expect to know a priori. Although a constant approximation is enough, it seems unclear whether this can lead to an oblivious algorithm in $M$.\n\nIn the experiment, the adversary uses a “greedy” strategy by compelling the experts in the pool that the algorithm uses to make mistakes (until all experts have made at least M mistakes). It would be nice to compare the deterministic and the random algorithms against more types of strategies for the adversary. (As already pointed out in the paper, for such “greedy” adversary, the deterministic algorithm is theoretically optimal.)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Most techniques in the proofs are already used in previous works. For example, the proof of the space lower bound is by a reduction to the communication problem of $\\epsilon$-DIFFDIST. Similar reduction is already used in the closely related work [49] to show memory lower bound for learning with experts problem with random-order stream. \n\nWe remark that although the communication problem itself is the same as [49], our lower bound statement and the corresponding techniques are completely different from [49], in order to handle a stronger lower bound for deterministic algorithms, parameterized by the number of mistakes made by the best expert. \n\nAt a high level, the proof of our main lower bound proceeds in two steps. First, we prove a communication complexity lower bound for  $\\epsilon$-DIFFDIST against any protocol that succeeds with probability $1-2^{-\\Theta(T)}$, which includes deterministic protocols. Second, we show that the $\\epsilon$-DIFFDIST problem can be reduced to the expert prediction problem in the streaming setting. Indeed, the second step was done previously by [49], but the first step forms the major technical contribution of our paper. \n\nNamely, we first view the input as a $T\\times n$ matrix and define a hard distribution that is a product distribution across columns that can be written as $\\zeta^n$, where $\\zeta$ is the distribution over a single column. By a direct sum argument, it suffices to show that the single column problem, i.e., distingushing $\\zeta$ from some other input distribution $\\zeta'$, requires $\\Omega(M)$ information cost and thus $\\Omega(M)$ total communication, where $M$ is the number of mistakes made by the best expert. We then define an informative message to be a message that reveals sufficiently large information about the input so that the mutual information would be large. \n\nWe show that there must exist $\\Omega(M)$ informative indices because otherwise we could modify the input $C$ drawn from $\\zeta$ on the uninformative indices and find an input $C'$ on which the algorithm cannot guarantee correctness with probability at least $1-\\exp(-\\Theta(T))$. Namely, we let $C'$ be an input that agrees with $C$ on the informative indices, and is chosen arbitrarily on uninformative indices. Thus, there must exist $\\Omega(M)$ informative indices and by the chain rule for mutual information, the total communication must be $\\Omega(M)$. \n\nWe emphasize these techniques are specifically catered for our lower bound against deterministic algorithms and thus have not been used in previous works. We believe our technique of modifying the input to agree on informative indices may be useful for other problems for proving lower bounds for deterministic protocols. \n\n> The memory lower bound only seems to rule out using oblivious algorithms for adaptive adversaries. In particular, this does not prevent the existence of some algorithm that would have a standard inverse polynomial probability of failure for adaptive adversaries. \n\nOur lower bound is against algorithms with exponentially low failure rate, including all **deterministic** algorithms. We believe this is a wide space for robust algorithm design that contains highly non-trivial candidates, making our results fairly strong. For example, the classic algorithm for the online mistake bound model is the deterministic weighted majority scheme, due to Littlestone and Warmuth (1994). The algorithm, though simple, is arguably not obvious.\n\n> The lower bound also asks the number of experts to be exponentially large in $T$ ($n\\ge 2^T$), which is also restrictive. It could be useful if the authors could expand on whether this is a reasonable regime for lower bounds.\n\nWe emphasize that our lower bound asks the number of experts to be sub-exponential in $T$, i.e., $n=o(2^T)$ rather than $n\\ge 2^T$. This is a **crucial difference** to what the reviewer is stating, and is actually a very **natural regime** of parameters. \n\n> In the experiment, the adversary uses a “greedy” strategy by compelling the experts in the pool that the algorithm uses to make mistakes (until all experts have made at least M mistakes). It would be nice to compare the deterministic and the random algorithms against more types of strategies for the adversary. (As already pointed out in the paper, for such “greedy” adversary, the deterministic algorithm is theoretically optimal.)\n\nOur experiments serve as a simple proof-of-existence of an adversary for which previous randomized algorithms fail catastrophically, demonstrating the need for an adversarially robust algorithm and the advantages of deterministic algorithms. \n\n> The paper proposes that the difficulty of the problem might depend on M, the number of mistakes made by the best experts, and that the space required increases as M increases. In addition, the guarantee for the random algorithm proposed holds only for small M. In the classical learning with experts problem, similar phenomenon is observed. For instance, for small M the regret is in fact $O(\\frac{1}{T}(\\sqrt{M\\log n}+\\log n)) (section 2.4 in [Cesa-Bianchi, N., & Lugosi, G. (2006)]). Is any connection between the classical setting and the variant considered here, in terms of the effect of small M?\n\nThank you for pointing this out! Yes, we are aware of this coincidence, but not of a formal connection."}, {"review_id": "b8nxtQhIB4", "reviewer": "Reviewer_Tz12", "summary": " This paper considers the problem of individual sequence prediction with a finite pool of experts, under memory constraints. While this problem was considered in previous works when the learner faces oblivious adversaries. The authors consider the case of adaptive adversaries that choose the experts costs in each round $t$ based on past information. They present two algorithms, the first algorithm is deterministic and the second is randomized. Both algorithms are adaptive the cumulative loss of the best expert. Finally, the authors provide space lower-bounds for any randomized algorithm, which along with the upper bound of their deterministic algorithm characterizes the space-regret trade-off for this problem. ", "questions": "* In the non-constrained setting, a refined analysis of the regret of the Hedge algorithm with an adequate parameter allows to have a regret of order $\\mathcal{O}\\left(\\sqrt{M\\log(n)/T}\\right)$ using the papers' notation (result corresponds to Corollary 2.4 in [1]). How do the upper bounds presented in this paper apply to algorithms with the last guarantees? \n\n[1] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.", "limitations": " ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": " The adaptability to cases where the best-performing expert has small losses and when the adversary takes the learner's previous decisions into account are desirable features in practice. The presented algorithms are intuitive and well explained ", "weaknesses": "* The algorithm requires prior knowledge of the number of mistakes by the best expert and a pre-specified target regret.  \n* In line 25 you announce that you are considering losses in $[0,\\rho]$, while you only consider $\\{0,1\\}$ losses.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The algorithm requires prior knowledge of the number of mistakes by the best expert and a pre-specified target regret. \n\nWe remark that the natural deterministic algorithm only requires a loose upper bound on the number of mistakes by the best expert. Moreover, it is not the focus of our paper. Our main result is the lower bound, which involves non-trivial input modification techniques surrounding our definition of informative indices, and shows that even though the number of mistakes made by the best expert is difficult to ascertain a priori, it nevertheless is a hidden parameter that governs the space complexity of the problem. \n\n> In line 25 you announce that you are considering losses in $[0,\\rho]$, while you only consider $0,1$ losses.\n\nNote that our lower bound works under the special case when all losses are binary. This implies the same lower bound holds when loss values are continuous.  Our randomized robust algorithm works for general costs $[0,\\rho]$ by using Algorithm 5 of Srinivas, Woodruff, Xu & Zhou (in line 1 of Algorithm 1 of our paper).\n\n> In the non-constrained setting, a refined analysis of the regret of the Hedge algorithm with an adequate parameter allows to have a regret of order $\\mathcal{O}(\\sqrt{M\\log(n)/T})$ using the papers' notation (result corresponds to Corollary 2.4 in [1]). How do the upper bounds presented in this paper apply to algorithms with the last guarantees?\n\nHedge works in the regime of memory size $\\Theta(n)$. In this setting, our determinstic algorithm (which works for online binary prediction) reduces to a simple algorithm due to Littlestone & Warmuth (see e.g., Fact 11.3 here: https://www.cs.cmu.edu/~anupamg/advalgos17/scribes/lec11.pdf). We get $M\\log n$ mistakes, up to a constant.  On the other hand, our randomized algorithm has total regret at least $\\sqrt T$ (up to logarithmic factors), due to the assumption that $R > \\sqrt{\\frac{\\log^2 n}{T}}$, where $R$ is the average regret. This can be achieved when we have $\\Omega(n)$ memory; hence, our randomized algorithm is not better than Hedge in this regime."}, {"review_id": "AFos1ymIbO", "reviewer": "Reviewer_BvCn", "summary": "The paper studies the experts problem in online learning under an additional memory constraint. Recent development on this setup gave algorithms with a sublinear memory usage (in $n$, the number of experts) and also a sublinear regret (in $T$, the time horizon). However, many of these results require the observtions to be oblivious, i.e., not adaptively chosen against the learner's actions.\n\nThis work gives new bounds on the memory-regret tradeoff when the adversary is adaptive, including (under certain parameter regimes):\n- A simple, deterministic algorithm that requires $\\tilde O\\left(\\frac{nM}{RT}\\right)$ space, where $M$ is the number of mistakes made by the best expert and $R$ is the desired regret. This is achieved by running the deterministic majority algorithm on repeatedly sample pools of experts.\n- A randomized algorithm that uses $\\tilde O\\left(\\frac{n}{R\\sqrt{T}}\\right)$ space. This builds on an algorithm of Srinivas, Woodruff, Xu and Zhou (STOC'22) (for the oblivious case) and uses tools from differential privacy to hide the random coins used by parallel copies of an algorithm.\n- To achieve regret $R$ with failure probability $2^{-\\Omega(T)}$, $\\Omega\\left(\\frac{nM}{RT}\\right)$ memory is needed. In particular, this lower bound holds against all deterministic algorithms. The lower bound is proved by a reduction from a communication problem, which was also used in a very similar context by Srinivas, Woodruff, Xu and Zhou (STOC'22).", "questions": "Regarding the second point in the \"Weaknesses\" section: Are there impossibility results showing the hardness of achieving regret $R \\ll M/T$?\n\nMinor comment:\n- Abstract, Line 10: It was not clear what $M$ is here (before reading through Line 13).", "limitations": "The main limitations are the assumptions on the problem parameters in order for the theoretical results to hold, and these have been clearly stated in the paper.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper presents progress on a natural and fundamental problem in sequential prediction. The paper is very nicely structured and enjoyable to read. The main paper contains a nice amount of technical ideas/details to understand the work.\n\nDespite the weaknesses discussed below, this work still seems a nice addition to the recent line of work on memory bounds for the experts problem, so I lean towards acceptance.", "weaknesses": "- The results are restricted to the discrete prediction setup (i.e., with binary outcomes, binary forecasts, and 0/1 loss), whereas some previous work along this line applies to the more general bounded-loss case. (Lines 25-26 mentions a setup with losses bounded in $[0, \\rho]$, but all the results of the paper are stated for the discrete case.)\n- Both the positive results (Theorems 3.1 and 3.3) require $RT \\gg M$ (at least by a $\\mathrm{polylog}(n)$ factor), i.e., the additional mistakes made by the algorithm needs to be much larger than that of the best expert.\n- The algorithms proposed in the paper are relatively simple (or simple modification to algorithms in the literature).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The results are restricted to the discrete prediction setup (i.e., with binary outcomes, binary forecasts, and 0/1 loss), whereas some previous work along this line applies to the more general bounded-loss case. (Lines 25-26 mentions a setup with losses bounded in $[0,\\rho]$, but all the results of the paper are stated for the discrete case.)\n\nNote that our lower bound works under the special case when all losses are binary. This implies the same lower bound holds when loss values are continuous. Our randomized robust algorithm works for general costs $[0,\\rho]$ by using Algorithm 5 of Srinivas, Woodruff, Xu & Zhou (in line 1 of Algorithm 1 of our paper).\n\n> Both the positive results (Theorems 3.1 and 3.3) require $RT\\gg M$ (at least by a $\\text{polylog}(n)$ factor), i.e., the additional mistakes made by the algorithm needs to be much larger than that of the best expert.\n\nOur main result shows that the regime $RT\\gg M$ is absolutely necessary. In other words, our lower bound in Theorem 1.3 shows that if $R\\ll M/T$, then any deterministic algorithm (or even randomized algorithm with failure probability $2^{-\\Omega(T)}$) requires linear space. \n\n> The algorithms proposed in the paper are relatively simple (or simple modification to algorithms in the literature).\n\nWe remark that we view our main result as the lower bound, which shows that even though the number of mistakes by the best expert is difficult to ascertain a priori, it nevertheless is a hidden parameter that governs the space complexity of the problem. Our proof requires non-trivial input modification techniques surrounding our notion of informative indices. \n\n> Regarding the second point in the \"Weaknesses\" section: Are there impossibility results showing the hardness of achieving regret $R\\ll M/T$?\n\nYes, our main result in Theorem 1.3 shows that if $R\\ll M/T$ or in other words $RT\\ll M$, then any deterministic algorithm (or even randomized algorithm with failure probability $2^{-\\Omega(T)}$) requires $\\Omega(n)$ space, i.e., essentially keeping all the experts, up to a constant factor. "}, {"review_id": "2TjKvBJuUy", "reviewer": "Reviewer_757a", "summary": "This paper studied the memory complexity of the expert learning problem against an *adaptive* adversary. It proved a lower memory bound for deterministic algorithm and gave an optimal deterministic algorithm matching this bound. It also proposed a randomized algorithm which uses less memory if the regret and best expert performance satisfies certain condition.", "questions": "I suggest the authors strengthen their results and rewrite the paper.", "limitations": "I think the results of the papers are somewhat exaggerated. For example, in the abstract the authors claimed the natural deterministic algorithm is almost optimal. I think this is quite misleading because better randomized algorithm could exist.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper studies an interesting and important question. It seems to be the first work to study the memory requirement against an adaptive adversary for learning from expert problem specifically.\n2. The paper has some interesting ideas, like the construction of the randomized algorithm and the proof of the lower bound, however, both of the writing and the results could be improved.", "weaknesses": "1. I believe your theorems are correct. However, some parts of your proof doesn't seem rigorous to me or could just be wrong. For example, in line 272, you claim \"at least $m/3$ of the instance\". I don't know where the constant $1/3$ comes from because you seem to be quite sloppy with the constants here (big O notation).\n\n\n\n2. The writing should be improved drastically. \\\n(1). There are some typos. For example, in line 36, the regret should be divided by $T$. In line 206, \"in $S$\" is typed twice. \\\n(2). The proof needs to be cleaned up. There are lots of repetitions and unnecessary parts. For example, the theorems and definitions of differential privacy in the main article is very confusing to me. I don't think you used anything related to differential privacy either in your proof. Instead, you could just apply Theorem 1.4 in Hassidim et. al.. In appendix, some theorems proved in other papers are reproved. Instead, you should've highlighted the difference. Many of your proofs are just rewriting what's in Ben-Eliezer et. al. and Srinivas's paper. \\\n(3). Some notations are not so consistent. For example, high probability is defined by poly in $n$, but in your theorems, it's poly in both $n$ and $T$. In line 25, you mentioned the range of cost function is $[0,\\rho]$ but in the problem you study is just $\\{0,1\\}$. \\\n(4). Many sentences are too long. Try to limit every sentence to less than three commas.\n\n\n\n3. I think stronger result should be obtained. All of your current results just come from directly applying a theorem for more general settings. For example, the randomized algorithm directly comes from the framework in Hassidim et. al.. It seems that by designing algorithm more specific to the expert learning problem, better bound could be achieved. Your proof for the deterministic lower bound also seems quite unnecessary. I think a much simpler proof, potentially without using randomness, should suffice to prove the lower bound for deterministic algorithms. Or I think better bound (indeed the current lower bound doesn't really tell much about randomized algorithms because the exponential dependent on $T$ in the probability), like the probability is poly in $T$ and $n$, should be obtained by the current proof method. In the proof of the lower bound, you should highlight what's new. It seems that a large part like the reduction has already been showed by previous work.\n\n\n\n4. You should at least compare the best randomized algorithm you derived, i.e., algorithm 1, with the deterministic algorithm in your experiments. Also why does the adversary have access to the internal randomness? Even the adaptive adversary doesn't have directly access to the random bits.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I believe your theorems are correct. However, some parts of your proof doesn't seem rigorous to me or could just be wrong. For example, in line 272, you claim \"at least $m/3$ of the instance\". I don't know where the constant $1/3$ comes from because you seem to be quite sloppy with the constants here (big O notation).\n\nThanks for the feedback, we will elaborate that with high probability, at least $m/3$ of the $m$ instances of the algorithm must be wrong if the private median of the $m$ independent instances is wrong. This is because the private median will likely select an output in between the $1/3$ and $2/3$ quantiles among the outputs of all the instances. \n\n> The writing should be improved drastically. \n\nAlgorithm 1 and  Theorem 3.3 builds upon the basic definition of private median, which in turns relies on a set of minimal preliminaries of differential privacy (DP). Otherwise, our algorithm's description would not be well-defined. We believe DP as a tool for algorithm design is not standard within the ML community, and thus we believe a basic introduction to it is necessary for our purpose. \n\nNote that our lower bound works under the special case when all losses are binary. This implies the same lower bound holds when loss values are continuous.  Our randomized robust algorithm works for general costs $[0,\\rho]$ by using Algorithm 5 of Srinivas, Woodruff, Xu & Zhou (in line 1 of Algorithm 1 of our paper).\n\nWe have fixed the mechanical errors and would be happy to  continue improving, if you may provide further suggestions.\n\n> I think stronger result should be obtained. All of your current results just come from directly applying a theorem for more general settings. For example, the randomized algorithm directly comes from the framework in Hassidim et. al.. It seems that by designing algorithm more specific to the expert learning problem, better bound could be achieved. Your proof for the deterministic lower bound also seems quite unnecessary. I think a much simpler proof, potentially without using randomness, should suffice to prove the lower bound for deterministic algorithms. Or I think better bound (indeed the current lower bound doesn't really tell much about randomized algorithms because the exponential dependent on $T$ in the probability), like the probability is poly in $T$ and $n$, should be obtained by the current proof method. In the proof of the lower bound, you should highlight what's new. It seems that a large part like the reduction has already been showed by previous work.\n\nWe agree that our randomized algorithm is straightforward from existing techniques from DP; however, prior to our work,  there was no known  connection from adaptive robust via DP to  online learning.\n\nWe are certain, on the other hand, that most of our lower bound techniques are novel, and we strongly disagree with the above statement of the reviewer regarding our main lower bound and do not see any evidence for the reviewer's claim. In particular, our core information-complexity argument, starting with the definition of \"informativeness\" (Eqn 4.1 and below) and using a non-trivial input modification technique depending on the protocol's success probability, does not follow from any existing techniques in the literature, e.g., in communication complexity, information complexity, or streaming lower bounds. We believe this technique may be of independent interest, and apply to proving deterministic (or high probability) lower bounds for other communication problems. \n\nWe do not know how to strenthen it to a inverse-polynomial failure rate. We are, of course, happy to hear more constructive suggestions towards this goal.\n\n> You should at least compare the best randomized algorithm you derived, i.e., algorithm 1, with the deterministic algorithm in your experiments. Also why does the adversary have access to the internal randomness? Even the adaptive adversary doesn't have directly access to the random bits.\n\nOur randomized algorithm relies upon the prior work of SWXZ22. We are not aware of an implementation of the algorithm therein, as it is somewhat sophisticated. We leave a more comprehensive experimental study to future work, as the focus of this paper is mostly theoretical. \n\nAssuming the adversary has access to the internal randomness is a setting known as the white-box adversarial model (proposed by https://dl.acm.org/doi/pdf/10.1145/3517804.3526228). Our experimental evaluations serve as a proof-of-concept that our deterministic algorithms can be useful in certain settings. "}]

Author rebuttal:
We thank the reviewers for their thoughtful comments and valuable feedback. In particular, our experiments show the importance of algorithms that are robust to adversarial input, demonstrating that the existing algorithms perform poorly against a simple attack while deterministic algorithms are a natural class of adversarially robust algorithms. On the other hand, we noticed that multiple reviewers focused on the simplicity of the algorithmic design. We would therefore like to refocus the discussion on the stronger lower bound for deterministic algorithms (and algorithms with failure probability $2^{-O(n)}$) presented in this paper, which we view as the main contribution of our paper and exhibits several noteworthy properties:
- Our lower bound requires a novel and technical argument to show that protocols with an exponentially small probability of failure for even a single column of an input from a hard distribution of the $\epsilon$-DIFFDIST problem must convey $\Omega(M)$ information, where $M$ is the number of mistakes made by the best expert. 
- Our lower bound shows that surprisingly, the number of mistakes made by the best expert is an intrinsic parameter that governs the complexity of the problem, regardless of whether it is known (or even approximated/bounded) a priori. 
- Our lower bound also shows that the natural deterministic algorithm is the optimal algorithm, thus resolving this general approach. 
 so it is important that our results completely resolve this avenue of attack. 

We also remark that we appreciate the positive remarks, such as

- The deterministic algorithm proposed is simple and achieves the optimal memory usage $O(nM/RT)$. (Reviewer gy2q)
- In addition, it’s surprising to see that $M$, the number of mistakes made by the best expert, shows up both in the lower and upper bound of memory, implying that $M$ is an intrinsic parameter related to the robust variant of learning with expert problem. This might provide insights for other related problems. (Reviewer gy2q)
- The randomized algorithm shows differential privacy can be used to turn (potentially) non-robust algorithms to robust ones by hiding the internal randomness. This idea was explored in recent works [4, 10, 34], and it’s interesting to see its application for the expert problem. (Reviewer gy2q)
- The adaptability to cases where the best-performing expert has small losses and when the adversary takes the learner's previous decisions into account are desirable features in practice. (Reviewer Tz12)
- The presented algorithms are intuitive and well explained. (Reviewer Tz12)
- The paper presents progress on a natural and fundamental problem in sequential prediction. (Reviewer BvCn)
- The paper is very nicely structured and enjoyable to read. (Reviewer BvCn)
- The main paper contains a nice amount of technical ideas/details to understand the work. (Reviewer BvCn)
- This work still seems a nice addition to the recent line of work on memory bounds for the experts problem. (Reviewer BvCn)
- The paper studies an interesting and important question. (Reviewer 757a)
- It seems to be the first work to study the memory requirement against an adaptive adversary for learning from expert problem specifically. (Reviewer 757a)
- The paper has some interesting ideas, like the construction of the randomized algorithm and the proof of the lower bound. (Reviewer 757a)

We provide our responses to the initial comments of each reviewer below.  We hope our answers resolve all initial questions and concerns raised by the reviewers and we will be most happy to answer any remaining questions during the discussion phase!

Meta-review: This is a clean paper that studies robust algorithms for the "learning with experts" problem under memory constraints. Robustness here means that the algorithm's input can be adaptively generated, depending on the experts' predictions in previous rounds. The paper pins the tradeoff between space complexity and regret for deterministic algorithms, but leaves the question for randomized algorithms open. The reviewers' questions were successfully addressed by the authors during the rebuttal phase.
Decision: Accept (poster)