Better Bounds for the Distributed Experts Problem
Authors: David Woodruff
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: distributed algorithms
learning with experts
communication complexity
reinforcement learning
Primary area: learning theory

Abstract: In this paper, we study the distributed experts problem, where $n$ experts are distributed across $s$ servers for $T$ timesteps. The loss of each expert at each time $t$ is the $\ell_p$ norm of the vector that consists of the losses of the expert at each of the $s$ servers at time $t$. The goal is to minimize the regret $R$, i.e., the loss of the distributed protocol compared to the loss of the best expert, amortized over the all $T$ times, while using the minimum amount of communication. We give a protocol that achieves regret roughly $R\gtrsim\frac{1}{\sqrt{T}\cdot\text{poly}\log(nsT)}$, using $\mathcal{O}\left(\frac{n}{R^2}+\frac{s}{R^2}\right)\cdot\max(s^{1-2/p},1)\cdot\text{poly}\log(nsT)$ bits of communication, which improves on previous work.

Published as a conference paper at ICLR 2026
BETTER BOUNDS FOR THE DISTRIBUTED EXPERTS PROBLEM
David P. Woodruff Cameegie Mellon University dwoodruff andrew. cmu. edu
Samson Zhou
Texas A&M University
samsonzhoul gma com
ABSTRACT
In this paper, we study the distributed experts problem, where n experts are distributed across servers for T timesteps. The loss of each expert each time is the lp norm of the vector that consists of the losses of the expert at each of the 8 servers at time I. The goal is to minimize the regret R, i.e., the loss of the distributed protocol compared to the loss of the best expert, amor- tized over the all T' times, while using the minimum amount of communica- tion. We give a protocol that achieves regret roughly R Z polloyl us- ing O ( R2 R2)) max(s!-2/p, 1) poly log(nsT)) bits of communication, which improves on previous work.
INTRODUCTION
Many modern applications require sequential decisions based on predictions from large set of distributed experts. For example, hyperparameter optimization or model selection, each expert corresponds to different architectures or pre-trained models evaluated across separate datasets, and the algorithm must dynamically choose which to deploy. In recommendation systems, experts en- code distinct ranking functions, with feedback only from selected actions, while in reinforcement learning, experts correspond to policies trained on separate environments. Across these applica- tions, the decision-maker must aggregate information from multiple sources and adapt to evolving losses in distributed systems. This setting is formalized by the online prediction with expert ad- vice problem, where experts incur losses each step over rounds, and the algorithm selects an expert based on observed history to minimize cumulative regret, defined relative to the best ex- pert in hindsight. Classical algorithms, including the Exponential Weights Algorithm (EWA) and
(v
Multiplicative Weights Update (MWU), achieve optimal regret O
log
in the full-information
setting (Arora al., 2012), while EXP3 attains near-optimal regret O
n log
in the bandit set-
ting (Auer et al., 2002). As the number n experts and prediction rounds grow, running these algorithms centrally becomes computationally expensive, motivating the study of scalable models. Prior work has explored streaming approaches (Srinivas et al., 2022; Peng & Zhang, 2023; Woodruff' al., 2023; Peng & Rubinstein, 2023; Aamand al., 2023; Braverman al., 2026), which process expert losses sequentially while maintaining only compact summaries of historical data.
In this work, we consider a complementary challenge: distributed online learning with experts. Here, expert costs are partitioned across s servers, and a central coordinator aims to implement low-regret algorithm while minimizing communication with the servers. This distributed formula- tion arises naturally in large-scale online optimization and hyperparameter tuning across multiple datasets, or in settings where each server holds private subset data. For example, each expert may correspond puted as sum of per-server losses, as in the HPO-B benchmark (Pineda-Arango et al., 2021). Other aggregation functions, such as the maximum loss across servers, also be relevant when indi- vidual server costs are constrained, highlighting the ficxibility the framework to accommodate different practical objectives.
model trained on the aggregated data across servers, with the total loss com-

---

Published as a conference paper at ICLR 2026
Our focus is understanding the tradeoff between communication and regret in distributed on- line learning with experts. Unlike memory-constrained streaming approaches, the coordinator can maintain full information
all experts, so the primary challenge is minimizing communication. We study this in the message-pan message-passing model, where the coordinator communicates privately with each server in sequential rounds. Prior work has largely focused many applications such as risk-sensitive optimization, robust model selection, and distributed con- trol-require general e losses with p Different values of p balance robustness and penalization of large deviations: for minimizes the maximum loss, intermediate values like &y moderately penal- ize large deviations, and values near & emphasize outlier robustness. For example, Ey loss exten- sively studied in streaming settings due to connections with entropy (Harvey et al., 2008; Woodruff & Zhou, 2021). We therefore develop algorithms that achieve near-optimal regret for general Ep losses while keeping communication provably low.
l loss (Jia et al., 2025), but
1.1 DISTRIBUTED ONLINE LEARNING WITH EXPERTS THE COORDINATOR MODEL
We consider the distributed online learning with experts problem in the coordinator (message- passing) model. There are servers, denoted [s] = {1. 2, ......... s). At each round E [T]. each server j E [s] receives a local loss vector (41 (i.......... cumulative regret of the algorithm while using minimal communication between servers.
E R". The goal is to minimize the
Online learning with experts. In the online learning with experts problem, there are n experts who make predictions across a time horizon of length T. For each time t E [T], an algorithm selects an expert é, [n] and then observes the loss vector (L), Lu (!),, incurring loss Li, (l). The total loss of the algorithm is Eeery Li, (1), and the best expert i" incurs Eiem L(( The regret of the algorithm is defined by
(1) - 54 (E|T]
R= T
(E|T]
which the algorithm aims to minimize. In the distributed setting, the losses Li(t) are not given explicitly. Instead, the loss of each is computed across servers via the Lp loss L,(t)
(Ejety (P) 1/P where p 2 1 is fixed and known in advance. This distributed formulation captures scenarios where expert evaluations are partitioned across multiple servers or datasets.
Communication complexity. Since the losses [,( are not explicitly given, the servers must col- lectively execute a distributed protocol II. Each server has private randomness, and all share pub- lic randomness. In the coordinator model, servers communicate only with the coordinator; in the saaaaggg model, direct cevverto-seeves communication provides at most constant-factor improvement, so we treat the two interchangeably. We assume II is sequential and round-based: in each round, the coordinator interacts with a subset of servers and waits for responses. The protocol is self-delimiting
servers know when round concludes. Let II(r) denote the transcript of round r, with [[(()) its communication cost. The total communication is Σ, [[(r)). Designing proto- cols that balance total communication with low regret is the central challenge in distributed online learning with experts.
1.2 OUR CONTRIBUTIONS
In this paper, we study the distributed online learning with experts problem. As a warm-up. up. we show that there exists distributed protocol that achieves nearly optimal regret of O 1/p communication Ô (nT + sT):
log
with
Theorem 1.1. Let and j E [s]. There exists an algorithm that achieves expected regret at most O s//p with high probability, uses total communication at most O (sT) + nT polylog(nsTT) bits.
be fixed constants and suppose ((j.t E [a, for all E
T.
[n]
log n
and
T
By comparison, the work of Jia et al. (2025) only achieved distributed protocols for general & losses for the broadcast/blackkoard model, where servers can publicly broadcast information that
2

---

Published as a conference paper at ICLR 2026
is visible other servers and the communication cost of a protocol is then the total length of the broadcast messages. This setting is "easier" than the message- message-passing model since sending the same message to all servers in setting would incur communication multiplicative overhead. Thus the techniques are fundamentally different. For instance, the lp loss algorithm by Jia et al. (2025) for the broadcast model walks through all servers to find the server j [s] with the largest loss for each expert i E [n]. While each server j only needs to send values larger than the previously broadcast losses for each expert in the broadcast model, resulting in roughly total communication Ô (s + m2),
such an approach would require O (ns) communication in our setting.
On the other hand, Jia et al. (2025) achieved a distributed protocol for the SUM problem in the message- passsnng model, i.e., & loss, with Ô (nIT O (T') total communication, for regret
logn
However, because l loss is additive across servers, then standard techniques
such as sampling a number of losses to be communicated, with probability proportional to their magnitudes, can work for l loss but fail work for sub-additive or superadditive losses such as 4p losses. In contrast, Theorem 1.1 is able to achieve optimal regret across all Ep losses.
We remark that Jia et al. (2025) assumed the losses are normalized so that the total loss for a single expert on a single time is at most 1. By comparison, if each server is permitted to have loss (a, b] by our ussumption, then all experts have loss ((s'/r), which accounts for the difference in their stated bounds and our referenced bounds. We can parameterize Theorem 1.1 to obtain a more general communication-regg
trade-off as follows:
Theorem 1.2. Let b > a > be fixed constants and suppose t(j.t) E [a, for all E [T], i E [n]] and j E [s]. Let R 2 VT. Then there exists an algorithm that achieves expected regret at most O (Rs (Rs'/v/logn) and with high probability, uses total communication at most (**t) polylog(ns7) bits.
We emphasize that seeking regret R 2 vT is standard, because it is 1 possible to achieve regret R < /T (Cover, 1966).
im-
In contrast to Theorem 1.2, Jia et al. (2025) achieved distributed protocol for the SUM problem, i..., l loss, with Ö ( ) O (Ts) total communication, for regret R. Thus not only does Theo- rem 1.2 improve on the result of Jia et al. (2025) for general lp losses, but it also improves upon the O (T') dependency in the result of Jia et al. (2025) to parameterization across general regret R. For example, with regret R = 0 (1), the protocol of Jia et al. (2025) still has dependency O (Ts) while our protocol has dependency O (s), which is substantially less for large time horizons T. We summarize this discussion in Figure 1.
Reference
Loss function
Communication cost (bits)
Jia et al. (2025)
t loss
(#
Ts) polylog(nsT))
Theorem 1.2
Ep loss
polyyog(nssT)
Fig. 1: Our work is the first to study tp loss in the coordinator model; for the special case of p 1, we obtain better coggrttcommunicatioon tradeoffs for regret R.
We enable the handling of é, losses is to embed lp into loo through the use of exponential random variables, similar to the blackboard protocol of Jia et al. (2025). However, the servers cannot easily find the maximum in the coordinator model, so we require careful analysis of subsampling and thresholding to ensure that we find the maximum without too many servers sending low values. Additionally, the variance of the resulting estimator unbounded, so we utilize a geometric mean estimator. These novelties form the basis of our main algorithmic contribution. Although similar approaches have been used in other contexts such as norm estimation in the streaming model (Li, 2008; Woodruff & Zhou, 2021), this is the first time these techniques have been applied to online learning in the distributed setting, to the best of our knowledge. As a result, we can handle L, losses, which previous works cannot handle (Jia et al., 2025). We provide more details in Section 3 and Section 4. Finally, we remove the assumption that the losses are between a range of constants (a, b).
3

---

Published as a conference paper at ICLR 2026
Theorem 1.3. Suppose we have ((j.t) & 1 for all t [T). There exists algorithm that achieves expected regret most O (Rs /log n) and with high probability, uses total communication at polylog(nsT) bits.
most (+ta) maxx(s!217))
Finally, to complement our theoretical results, we conduct number of empirical evaluations as simple proof-of-concept. These results appear in Section
Algorithmic and technical novelties. The major challenge is that Ep losses are significantly more nuanced than & losses. Observe that since l loss is additive, then the total loss the sum of the individual losses. Thus, it is natural to sample individual losses with probability proportional to their magnitude. For l losses, may be possible perform some more nuanced sampling, but it is not clear how to efficiently perform sampling in distributed models across all of the experts. To overcome this barrier, we embed lp losses into an lo framework using random exponential scalings, such that the largest scaled contribution approximates the original Ep loss. However, due to the probability density function of exponential random variables, the resulting distribution has unbounded variance and thus we geometric mean of an independent number of random scalings to acquire an unbiased estimator with bounded variance. We then interface these estimated losses with multiplicative weights update (MWU) algorithm for the purpose of online learning. Notably, the use of a geometric mean estimator to reduce variance of estimators using exponential random variables is both algorithmic and technical novelty for the distributed online learning with experts problem that we believe may have independent interest to other applications. In principle, the geometric mean estimator could be potentially replaced by other variance-reduction techniques; the design of such algorithms is an interesting direction for future work.
PRELIMINARIES
We briefly discuss a number of relevant preliminaries necessary for our algorithms and analysis. We first recall the following standard formulation of Chernoff bounds for concentration inequalities. Theorem 2.1 (Chernoff Bounds).
X1, X2, 12...... Xx, be independent Bernoulli random variables T with Pr [X; = 1] Pi and Pr [X, = 0] = 1 Pt- Define X = -im X, and let μ. = E[X] =
E Ps. Then for any 5 > 0, we have Pr (IX - 141 2 5p) 1 2 2cxp
We next define an exponential random variable.
Definition 2.2 (Exponential random variable). An exponential random variable with rate parameter is a continuous random variable X with probability density function (PDF) given by:
dx (0,
x 2 0,
fx(x)
I < 0.
We show the following max stability property of exponential random variables. Lemma 2.3. [Max stability of exponential random variables] Let X; = fix for E [n], where
c.
el,...,e, en are independent exponential rundom variables with rate 1. Then maxte]m] to oy
dis-
llf tributed as elpp where e is an exponential random variable with rate 1.
Finally, we recall the multiplicative weights update (MWU) algorithm. For v roughly + following guarantees are known on the MWU algorithm in Algorithm 1:
J the
Theorem 2.4. For a set of experts with the second moment of the loss bounded by at most on each of rounds, the multiplicative weights update (MWU) algorithm achieves expected regret plog T
3 WARM-UP: SIMPLE ALGORITHM
We present a simple distributed algorithm that achieves near-optimal regret, using at most O (sT) + nT' polylog(nsT) total bits of communication. The intuition for the algorithm is follows.
4

---

Published as a conference paper at ICLR 2026
Algorithm Multiplicative weights update algorithm
Input: Learning rate 7, losses {L,(t)} } for all times t [T], experts E [m]
Output: Sequence of experts to play on each day
I: wi; <-0 0 for all i [n]
2: for each time E [7) do
3: for each [n] do
4: U; - w; + (t))
5: end for
6: Sample E [n] with probability proportional to exp(-1jug
7:
end for
Suppose for all experts
E [n] and times 1 E [7], we have the loss of i at time 4, 7,(1) =
Ejew 4(j, t)P) 1/p Then by setting wz = Evece [t),,, we can run the standard Multiplicative
Weights Update (MWU) framework with weights wy (t) by playing expert with probability propor- tional to exp(-nnx(t)) for fixed learning rate 17 0. Unfortunately, we do not have the losses {L:(t)). Instead, for time E [T], each expert E [rd]. and each server j E [s], we generate an ex- ponential random variable t) By the max-stability property of exponential random variables, c.f., Lemma 2.3, we have
(E)E))&())))) 1/P
1/P
4(I1)) (e.(,
max jE(N
el/p
where is another exponential random variable. Note that the right-hand side is exactly the Ep loss i on time f. Moreover, can compute the expected value of .मp so that if the servers can simply send the maximum of the scaled losses f.(..) then we can compute an unbiased estimate to the (e(().)))\/>>
Ep loss (Eyeto) t())))))) 1/P
Unfortunately, there two challenges with this approach. First, the servers do not know how to send the maximum. Second, the variance of the resulting random variable unbounded. To handle the first issue, we first show that with high probability, the maximum is above some threshold that is roughly s//P and moreover, there is only small number of scaled losses that above this threshold. Hence, we can upper bound the total amount of communication. To address the second issue, number these estimators, which lowers the variance to a small amount. We again remark that this pipeline serves as our main algorithmic contribution over previous works such as Jia al. (2025); the algorithm appears in full in Algorithm 2, where (t) is the geometric mean estimator for the loss (t( of expert time and (t( is the resulting weight for expert input MWU.
standard estimator (Li, 2008) that takes the geometric mean of constant
We first recall the following fact about probability density functions for polynomials of random variables.
Fact 3.1. Suppose a random variable X has probability density function f(z), with support on the non-negative reals. Then the random variable X-1/p has probability density function pe p-1 (z ").
We now compute the expectation and upper bound the variance of our geometric mean estimator.
Lemma 3.2. [Expectation and variance of geometric mean estimator] Let p 0 be fixed and
R 2 3p be an integer. Let eB be independent exponential random variables with rate 1. Let 1/B
Zo = -o. for all b [B), and let (Ihe
[3] Zb be their geometric mean. Then there exists
universal constant C3.2 E (0, 2B such that E [2]- C3.2 and EE [ 3B
We now show a structural property showing how estimates s,(t) to losses Lę(t) =
(Ejejo t(j.t)p) 1/p that are roughly unbiased and have small second moment facilitate an im- plementation of the MWU algorithm with bounded regret.

---

Published as a conference paper at ICLR 2026
Algorithm 2 Distributed protocol with near-optimal regret
Input: Losses ()) for all times t [T], experts i [n], servers E [s]. Lp loss parameter p
Output: Sequence of experts to play on each day
B
2: for each time E [T'] do
3: for each E [n]] do
4:
for each server j E [s] do
5:
Let (e(i.t) be the loss of expert on server j at time t
6:
Let e (j, t) be independent exponential random variables for all b [B] for b E [B]
7:
qi (j,t) + (6j.))
>Lemma 3.2
G.4))
8:
if qi (6) (J, Z (og(sT)))
3//
then
9:
Send qi
(b) tj to coordinator
10:
end if
11:
end for
12:
end for
13:
for each E [ni] do
(t) [bE [max)e(s] di (i.t) 1/B
(t( + w:(l
si())
16: end for
Play MWU on {w,(t)}
18: end for
Le(l) and this random variable has second moment most p for all i E [n] and t [T) Suppose the multiplicatiive weights update (MWU) algorithm is executed with loss sequences (t) instead of L,(t), for all E [n]] and t E [T). Then the sequence of resulting on the sequence of losses (Ta(4))e(w))eeer)
Lemma 3.3. Suppose E sc(1)
choices achieves expected regret O
p ing
Unfortunately, we cannot immediately apply Lemma 3.3 because we do not have sx(t) (t). Namely, the case where maxyels] qi ordinator. Fortunately, show this only holds with probability poly(n2) due to the distribution of exponential random variables. As result, the overall regret is only changed by lower-order terms.
(b) (j,t) I0U log(n then the value not sent to the co-
1/r
Without loss of generality, we set the fixed constants b > a > to be [1, our proofs easily generalize to intervals (a, bj. Using standard concentration inequalities, e.g., Theorem 2.1, we now upper bound the expected regret of our simple algorithm and the total communication of our warm- up distributed protocol.
Lemma 3.4. Suppose ((j,t) t) E [1,5) for all t [T], í [m] and [s). Then the expected regret of Algorithm 2 is at most O 11/p
log
Lemma 3.5. Suppose t) for all E [T] [n] and j E [s]. Then with high probability, the total communication of Algorithm is at most O (sT) + nT polylog(nsT)) bits.
Combining Lemma 3.4 and Lemma 3.5, we have Theorem 1.1.
COMMUNICATION-REGII TRADE-OFF
In this section, parameterize warm-up algorithm to achieve communication regrett trade- off. Namely, we show that the goal is to achieve regret R, then there exists distributed protocol polylog(nsT) bits.
that uses total communication at most R

---

Published as a conference paper at ICLR 2026
The algorithm is quite similar Algorithm 2. The main difference is that now at each time, each server is sampled to run the previous protocol. That is, with probability p. each server independently performs the same protocol as before. Otherwise, with probability We remark that the coordinator can also know the outcome these events by using public random- ness, that the coordinator does not need to speak each server determine whether the server was sampled. The algorithm appears in full in Algorithm 3.
2, the server does not speak.
Algorithm Distributed protocol with communication--eget regrett trade-off'
Input: Target regret R, losses {L,(i, ()) for all times E [T), experts [n], and servers ý E [s].
Lp loss parameter p Output: Sequence of experts to play on each day B
o nºT
2: for each time E [T] do
3: With probability - 0. the servers do not send anything and the weights {ur(()) are not updated
4: Otherwise, with probability do the following:
5: for each [n] do
6:
for each server j E [s] do
7:
Let ((().t) be the loss of expert on server j at time
Let e (b) (j) be independent exponential random variables for all à E [B]
8:
9:
qi
(b)
(j,t) Ca.2te 19 (1A))a/>
for E [
D.Lemma 3.2
10:
if (j, Z 100 (og then
3/0
11:
end q;
Send
(b) (j. to coordinator
12:
13:
end for
14:
end for
for each i [ni] do
81(1) + [Ibε[1] maxxEe ( 1/B
16:
17:
(t) + wt(t 1) + st(t)
end for
19:
Play MWU on {w,(t)}
20:
end for
We first show the following property of exponential random variables.
Fact 4.1. Let be exponential random variable with rate 1. Then for all 2, have
Pr [ E (xr, 2x]
E Ii Tm
We now analyze the expectation and upper bound the variance of our communication--egeee trade-off protocol, using the properties of exponential random variables.
Lemma 4.2. We have E s((()) = (t) + poly(n7y and E [ss(t))]] < O (TR2) 3B (L.(t))²
Again, remark that do not have the idealized expectation of E si(t) maxje(4) & (j.t)
(t(t) because
t) may not be sent to the coordinator if it is less than log(neT)) which changes the resulting expectation calculation. However, since this event only occurs with probability poly(n7) then the resulting claim follows. We then upper bound the regret and the total communication of Algorithm follows:
Lemma 4.3. Suppose t,(it) 11.5 all [T], E [n]] and [s]. The expected regret of Algorithm 3 is at most O (Rs /lo
Lemma 4.4. Suppose ((j.t) E [1, for E [T], the total communication is at most g2
[n] and E [s]. Then with high probability, polylog(nsT) bits.
7

---

Published as a conference paper at ICLR 2026
Putting together Lemma 4.3 and Lemma 4.4, we have Theorem 1.2.
5 FULL ALGORITHM
In this section, we build on our previous algorithms to present our main result, which achieves regret roughly A while using ( ( -max(s 1//r, 1) polylog(ns(") total bits of communication. Unlike the previous sections, we do not require each loss to within an interval (a, bj where > a > fixed constants. Algorithm 4 differs from previous algorithms in that it permits the servers to communicate more aggressively by sending smaller values, in particular the values larger than smaller threshold. However, this can only happen when server appropriately sampled.
Algorithm 4 Distributed protocol for the experts problem
Input: Target regret Rt losses {Li(j,t) t)} for all times & E [7], experts E [ni] and servers j E [s].
Lp loss parameter p
Output: Sequence of experts to play on each day
1: B
22 2 + RºT max(s! 1-2p 1), A + [10 log(ns7)))
2: for each time E (T' do
3: With probability
o. the servers do not send anything and the weights (w;(t)) are not
updated
4: Otherwise, pick an integer with probability 2
(b) 5: All servers send values q, (j. that at least 100-(2") log(nsT) the coordinator
3/P
>emmma 3.2
6: Let 9; (j,t) g: G.O
if received by the coordinator, or set to zero otherwise
Co.
7: for each E [n]] do
1/B
8:
st)
[[
max
qi ( ((..t)
1/v
9: Let a" 2 0 be the smallest non-negative integer such that s;(1) 2 (
if (1) and a" S then
11:
(t) + w.(t 1) 2 - s:(t)
end if
13:
end for
Play MWU on (w;(t)}
15:
end for
We first consider the expectation and variance of Algorithm 4. We use properties of exponential random variables to show that up to a small perturbation, the expected valued of s,(t) is precisely the loss (t) of expert time t. We similar argument for the second moment of st).
Lemma 5.1. Suppose 4i (b) (j,() Z
100TT for all b E [B]. Then we have E 81(() L.(1) +
poly(nT) and IE ((((0)]] < s/P RºT.
Next, we upper bound the regret and total communication of Algorithm 4 as follows: Lemma 5.2. Suppose we have (,(i,)) 1) S for all E (T). The expected regret of Algorithm is at
most O (R (P vlogn).
Lemma 5.3. Suppose we have t(j.t) S for all t E [T). Then with high probability, the total communication for Algorithm is at most n R
max 22pp polylog(nsI) bits.
Putting together Lemma 5.2 and Lemma 5.3, we have main result:
Theorem 1.3. Suppose we have &gGi t) & for all i E (T). There exists an algorithm that achieves expected regret most O (Rs /log n) and with high probability, uses total communication at most max(2112/pp polylog(nsT)) bits.
8

---

Published as a conference paper at ICLR 2026
6 EMPIRICAL EVALUATIONS
In this section, we perform experimental evaluations our distributed protocol, comparing it to both the standard offline MWU algorithm and the previous protocol of Jia et al. (2025). Specifically, we study the HPO-B dataset (Pineda-Arane et al., 2021), which is benchmark designed evalu- ate and compare the performance of hyperparameter optimization (HPO) algorithms across various machine learning tasks. We conducted our empirical evaluations using Python 3.1 on 64-bit op- erating system with an Intel(R) Core(TM) i7-3770 processor, featuring 4 cores, base clock speed of 3.4 3.4GHz, and 16GB of RAM. The dataset includes a diverse set of datasets and learning tasks, such as classification and regression, to assess the effectiveness, efficiency, and computational cost of differ- ent HPO methods. To support transparency and facilitate reproducibility of our results, we provide complete implementation of all algorithms, experimental setups, and data pre- processing routines, which are available at https: : / ///gtttuuuu com/ a ammonnzhon di wwiuutudddeee eepeedddexxxetts....
As a black-box benchmark for hyperparameter optimization, we treat the various models in the HPO-B benchmark as distinct experts in the distributed experts problem, with different datasets assigned to different servers. Each search step, which is random search for all model classes, can be viewed as one day in the distributed experts scenario. The cost vector represents the normalized negative accuracy of the models on the different datasets during a search step. We thus compared our simple distributed protocol from Algorithm 2 against MWU and against the algorithm of Jia al. (2025). Our results in Figure 2a show that for p 1, the total communication increases as the threshold increases; however, the trend is reversed for < 1. Figure 2b shows that our algorithm surprisingly has better reward than the MWU algorithm; we believe the latter is an issue of fine-tune fine-tuning the learning rate of MWU. Finally, Figure 2c shows that for the special case of p = 1, our algorithm achieves better communication than the algorithm Jia al. (2025). Additionally, Figure 2c exhibits the communication-regre trade-off as expected from our theoretical analysis.
KPNAIS SCMLL PALRE
(a) Communication vs.
(b) Reward vs.
(c) Communication vs. Regret
Conclusion. In this paper, we studied the distributed online learning with experts problem in the coordinator model, where each expert's loss is implicitly defnedd across s servers. We introduced the first protocol for general e, losses, achieving regret R Z (TT'oly with communication 11-2/5 1)- poly log(nsT)). For the important special case where nonzero server losses are bounded, our protocol attains regret O (Rs n) using total communication -polylog(ns7),, improving on prior bounds (Jia et al., 2025), which only handle 1. A key technical contribution lies in our algorithmic framework for é, losses, which are significantly more nuanced than 41 By embedding Ep losses into an foo structure using random exponential scalings, we reduce the problem tracking the largest scaled contribution the loss across all experts. To control the unbounded variance inherent in exponential random variables, we introduce a geometric mean estimator over independent scalings, yielding an unbiased estimate with provably bounded variance. This estimator is both an algorithmic and technical novelty, and it may have broader applicability beyond distributed online learning with experts. While the geometric mean is highly effective, alternative variance-reductio techniques could also be explored, representing a promising and fruitful direction for future work. Finally, our results highlight the fundamental tradcoff between communication and regret in distributed online learning with general lp losses. Extending these techniques to other structured loss functions, such as submodular objectives or too (max) losses, presents exciting avenue for further advancing distributed sequential decision-making.
O A
(abe)) R

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
David P. Woodruff is supported in part Office of Naval Research award number N000142112647, and Simons Investigator Award. Samson Zhou supported in part by NSF CCF-2335411. Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph E. Powe Junior Faculty Enhancement Award.
REFERENCES
Anders Aamand, Justin Y. Chen, Huy Lê Nguyen, and Sandeep Silwal. Improved space bounds for learning with experts. CoRR, abs/2303.01 453, 2023.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta- algorithm and applications. Theory Comput., 8(1):121-164, 2012.
Sepehr Assadi and Chen Wang. Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC, pp. 1237-1250, 2020. 13
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multi- armed bandit problem. SIAM J. Comput., (2(1))48-777 2002.
Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, and Samson Zhou. Online learning with limited information in the sliding window model. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, 2026.
George W Brown. Iterative solution of games by fictitious play. Act, Anal. Prod Allocation, 13(1): 374, 1951. 12
Kenneth L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. J. ACM, 42(2):488 499, 1995. 12
Thomas M Cover. Behavior of sequential predictors of binary sequences. Number 7002 in Stanford Electronics Laboratories Technical Report. Stanford University, Systems Theory, 1966. 3, 12
Michael S. Crouch, Andrew McGregor, Gregory Valiant, and David P. Woodruff. Stochastic streams: Sample complexity space complexity. In 24th Annual European Symposiun Algorithms, ESA, pp. 32:1-32:15, 2016. 13
Yuval Dagan and Ohad Shamir. Detecting correlations with little memory and communication. In Conference On Learning Theory, COLT, pp. 1145-1198, 2018. 13
Yoav Freund and Robert E Schapire A decision-theoreete generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1): 1997. 12
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999. 12
Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630-653 2007. 12
Sumegha Garg, Ran Raz, and Avishay Tal. Extractor- based space lower bounds for learning- In Proceedingy of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 990-1002, 2018. 13
Sumegha Garg, Ran Raz, and Avishay Tal. Time-space lower bounds for two-pass learning. In 34th Computational Complexity Conference, CCC, pp. 22:1-22:39, 2019. 13
Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. Sketching and streaming entropy via approximation theory. In 49th Annual IEEÉ Symposium on Foundations of Computer Science, FOCS, pp. 499. 2008. 2
10

---

Published as a conference paper at ICLR 2026
Zhihao Jia, Qi Pang, Trung Tran, David Woodruff, Zhihao Zhang, and Wenting Zheng. Communi- cation bounds for the distributed experts problem. arXiv preprint arXiv:2501.031132 2025. 2, 5,9
Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for online decision problems. J. Comput, Syst. Sci., ((3):291-307)) 2005. 12
Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceed- ings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1067- 1080, 2017. 13
Ping Li. Estimators and tail bounds for dimension reduction in la (0 < S 2) using stable random projections. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 10-19, 2008. 3,5
David Liau, Zhao Song, Eric Price, and Ger Yang. Stochastic multi-armed bandits in constant space. In International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 386-394, 2018. 13
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2):
212-261, 1994. 12
H. Brendan McMahan. follow-the-regulaiin
and mirror descent: Equivalence theorems and 1.1 regularization. In Proceedings of the Fourleenth International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 525-533, 2011. 12
Binghui Peng and Aviad Rubinstein. Near optimal memory-regres tradeoff for online learning. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1171-1194, 2023. 1, 13
Binghui Peng and Fred Zhang. Online prediction in sub-linear space. Proceedings of the 2023 ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 1611-1634, 2023. 1, 13
Sebastian Pineda-Arango. Hadi S. Jomaa, Martin Wistuba, and Josif Grabocka. HPO-B: A large- scale reproducible benchmark for black-box HPO based on openml. In Joaquin Vanschoren and Sii-Kit Yeung (eds.), Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2021. 1,9
Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):25233: 1995. 12
Ran Raz. A time-space lower bound for a large class of learning problems. In 58th IEEE Anmual Symposium on Foundations of Computer Science, FOCS, pp. 732-742, 2017. 13
Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. J. ACM, 66:1):3 2019. 13
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 1158-1171, 2022. 13
David Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators, In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS 2021, pp. 1183-1196, 2021. 2, 3
David P. Woodruff, Fred Zhang, and Samson Zhou. On robust streaming for learning with experts: Algorithms and lower bounds. Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems, NewrIPS, 2023.
11

---

Published as a conference paper at ICLR 2026
A RELATED WORKS
In this section, we provide brief outline of previous literature on the learning with experts problem. In Appendix A. I, we first describe a number of significant contributions to the problem in the central setting, where all experts and their predictions restrictions on the memory bounds of the algorithm. Since all information is central, there are also no communication restrictions, unlike the setting we study. We then outline previous works for the learning with experts problem in big data models in Appendix A.2.
available
algorithm, and there are no
A.I CLASSIC LEARNING WITH EXPERTS
The problem of online learning with experts has a rich history with extensive connections to rein- forcement learning and optimization. Early attempts to understand the problem first assumed the existence of a "perfect expert" one whose predictions are always correct. A folklore "halving" algorithm achieves at most log, n mistakes given experts in this setting by retaining the set of experts who have not yet made a mistake and predicts based on a majority vote, eliminating all disagreeing experts for each incorrect prediction.
Randomized weighted majority. However, the assumption of a perfect expert is often unrealis- tic. The deterministic weighted majority algorithm relaxes this by assigning weights to each expert, predicting based on the weighted majority, and reducing the weights of incorrect experts multiplica- tively by (1 --e) E) for fixed any parameter E (0, 1). Quantitatively, the number of mistakes by
x loz"). where m² the number of mistakes made by the best expert (Littlestone & Warmuth, 1994). In fact, simple exam- ple with two experts who always pick different outcomes at each time can force any deterministic algorithm to be incorrect on every time, while each expert is only incorrect on half of the times. Hence, no deterministic algorithm can do better than a multiplicative- facto of two compared to the best expert, i.e., no deterministic algorithm can achieve sublinear regret.
the deterministic weighted majority algorithm
most 2(1 + +)mm + O logn)
To overcome the worst-case limitations of deterministic algorithms, Littlestone and Warmuth in- troduced the randomized weighted majority (Littlestone & Warmuth, 1994). Instead of predicting based on a strict weighted majority, randomized weighted majority predicts according to a proba- bility distribution over the experts, where the probability of choosing an expert is proportional to their weight. When an expert makes mistake, their weight is again decreased multiplicatively by (1 - E). so that the algorithm makes a total of (1 + E)m= + log n.
mistakes, which translates
to O logn) regret for = (V log n T
and is known to be asymptotically optimal (Cover,
1966).
Other randomized variants. Besides these fundamental approaches, a variety of other algo- rithms have been developed, each with separate benefits. For example, the well-known Multi- plicative Weights Update (MWU) framework generalizes the weight update rule and can accommo- date various loss functions (Brown, 1951). Notably, MWU has applications boosting algorithms like AdaBoost (Freund & Schapire, 1997) and approximately solving zero-sum games (Freund & Schapire, 1999), and it can also efficiently approximate a wide class of linear and semi-definite pro- grams (Clarkson, 1995), leading to fast approximations for various NP-complete problems such as the traveling salesperson problem, scheduling problems, and multi-commmdity flow (Plotkin al., 1995; Garg & Könemann, 2007).
Building upon the "Follow the Leader" principle, which naively selects the expert with the lowest cumulative loss so far, Follow the Perturbed Leader (FTPL) introduces an element of randomness by adding perturbations to the cumulative losses of experts before making a selection (Kalai & Vempala, 2005). This randomization proves beneficial in avoiding worst-case scenarios often en- countered by deterministic algorithms, leading to asymptotically optimal regret bounds similar to randomized weighted majority and MWU. Moreover, for some structured problems, FTPL is more computationally efficient than MWU. In contrast, Follow the Regularized Leader (FTRL) incor- porates regularization term into the decision process (McMahan, 2011) 1), which penalizes drastic
12

---

Published as a conference paper at ICLR 2026
changes, promoting stability against noise, and offers flexibility incorporate prior knowledge by choosing the regularization function.
A.2 LEARNING WITH EXPERTS IN BIG DATA SETTINGS
We remark that all of the algorithms discussed in Appendix A.1 require storing the performance of all experts across all times throughout the duration of the algorithm. However, in many real-world applications, the number of experts and the time horizon 7 can be substantial, so that storing and processing all expert performances can be computationally demanding, either requiring significant memory or communication. As result, a line of recent work has focused on developing online learning with experts algorithms that operate with memory usage that is sublinear in the number of experts n.
Learning with experts on data streams.
Srinivas et al. (2022) showed that any algorithm us- implying that in order to achieve the optimal O log regret, the space used must be roughly linear, i.e., S Ô (n). Srinivas et al. (2022) also initially proposed an algorithm for online learning with experts in the random-order model, achieving Ô
ing S total space must achieve regret Ö
( nf
xT space for regret Rt. Subsequent work by Peng & Zhang (2023); Peng & Ru- H²
binstein (2023) refined these bounds, culminating in Peng & Rubinstein (2023)'s algorithm with
Ô VnT regret using polylogarithmic space in the arbitrary-order model.
Multi-armed bandits. Space complexity has also been studied for multi-armed bandits, a related reinforcement learning problem with arms having fixed reward distributions, but only feedback for a single arm is given on each time. Liau et al. (2018) showed that achieving near-optimal regret re- quires only constant space. However, this approach is not immediately applicable to the our setting, due to the adversarial nature of expert predictions, unlike the static rewards in bandits, and because expert algorithms observe all "arms" each day. Thus, expert and bandit algorithms are not directly comparable. Assadi & Wang (2020) showed that (2(k) space is necessary to identify the top k arms in a streaming bandit model. These results indicate that the experts problem is inherently harder than bandits, as low-regret bandit solutions can have constant space complexity.
Learning in streams. There is also significant research on the tradeoff's between space and sample complexity for statistical learning and estimation in the i.i.d. streaming model, including studies on matrix row inference (Raz, 2017; Garg et al., 2018; 2019) and parity learning (Kol et al., 2017; Raz, 2019). Another line of active work studies specific streaming learning problems such as correlation finding (Dagan & Shamir, 2018), collision probability estimation, graph connectivity, and rank esti- mation (Crouch et al., 2016). However,
work the experts problem does not assume any data distribution and focuses on prediction rather than inference. Thus, these works differs significantly from our goal of proving general space complexity bounds for expert algorithms while maintaining competitive regret against the best expert.
B MISSING PROOFS
B.1 MISSING PROOFS FROM SECTION 2
Lemma 2.3. [Max stability of exponential random variables] Let X; fnr for E [m], where
C1....,e Ca are independent exponential random variables with rate 1. Then maxte(1] fo is dis-
[fflle tributed as elpp, where e is an exponential random variable with rate 1.
Proof. Let X max ft 1/.
Then for any > 0, we have
Pr [X < 4 = Pr X < [2)
f
Pr
< t2
e
13

---

Published as a conference paper at ICLR 2026
exp (-I.. ..?)
exp t 11
By comparison, if |/ cl/y>
where e is an exponential random variable with rate 1, then
Pr = Y < exp exp (-t- [[f(]))
Hence, max
follows the same distribution as el/p
|lf
1/p
B.2 MISSING PROOFS FROM SECTION 3
Lemma 3.2. |Expectation and variance of geometric mean estimator] Let p >> O be fixed and
R 2 3p be an integer. Let e be independent exponential random variables with rate 1. Let
1/B
Zu = J/y for all b E [B), and let Z = [I B
Zo be their geometric mean. Then there exists
a universal constant C3.2 E (0, 2B] such that I C3.2 and
[ 3
Proof. The probability density function for an exponential random variable with rate is f(x) e Thus by Fact 3.1, the probability density function for each term Zp is pz pz- e and similarly, the probability density function for each term 1/BB in the geometric mean is p(x)
Bpa Bp-1 -= By Therefore, we have Pr
gup that for B
E
7
1/8
Pr
1/B dt 2
0
Pr
Z//B
dt +
Pr ////B
z)
dt
< 1 +
BBp dl
S +
dt 2.
Since [Z]
I1
B
E
/ then we have E [2] S 2B, Moreover, the probability density func-
tion for each term ////8 in the geometric mean satisfies p(x) Bpæ -p-1. By for all [] 1].
Bp 20
E
1/B
p(() ddl
p(t) dt
1/2
1
min
p(() .
2
rE[t.1]
Bp e -2 = 2(11,
min
2
(E[t.]]
so that E 1////
(1) is bounded away from 0. Thus, E [2] equals some constant C3.2 E (0, (0,
By similar reasoning, we have
E|Z
E|
2/ R
Pr
Z 1Z2 t
dt
Pr
23 2/ > t
dt +
Pr 7
2/R
1|
dt
0
14

---

Published as a conference paper at ICLR 2026
BBp/2 dt
1
dl S 3.
13/2
Hence, we have E [za]
1 b=
B
E
so that E Z [0,33].
Lt(t) and this random variable has second moment at most for all E [n) and . Suppose the multiplicative weights update (MWU) algorithm executed with loss sequences s,(t) instead of Lt(t) for all i E [m)] and t E (T). Then the sequence of resulting
Lemma 3.3. Suppose st(t)
choices achieves expected regret O (velgy plogn
on the sequence of losses (enn,ett)
Proof. For each E [T), let wy = (Wi,1..... Wt,n) ) be the vector of expert weights maintained by MWU. Then the probability distribution pa satisfies pt Σド=1 we.," After observing the loss
estimates s,) 2 O, the weights are updated w/+1, W exp(-ns(tt)). By assumption, have that (1) is an unbiased estimate of [t) independent of MWU, and thus for every realization of Pt and each i, t, we have
E (t)
Pt.
Lt)),,
E
st(t)
Pt S p.
For 20
y²
E 10) Pr < nL.(t) t
For W, = =, 1 and L, (L1 (t)
[t)t)) and summing over i with weights wt
E [W+11 Fi]
Σ Wr nsi(() Pt S Wi(1 np: Le + n2²p).
Iterating and taking expectations,
E [Wr+1] $ II nB lp. L.] + 12)))
For any expert i*, wT-1,-- exp( (-17 Ee 34-
S WT+1, hence
T
E, 86- (2)
S
(1 nj E [pr Li] + 17²p) p)-
Taking logarithms and using In + u) Su
EE
11 E. (1) (1)
Inn Σ Epr Lu] + 12 PT.
By Jensen's 's inequality,
Ine Ihe
<InB -1
Combining the two inequalities gives
Σ Le((1) < Inn - 7) Σ E Elp L.] + iTTTT
1
which rearranges
Σ E lp Li] Lo Inn + mpT.
"
Thus, the loss of MWU is at most In + +mpI. Choosing
In and normalizing by time horizon of
=
gives a regret bound of at most (Velggu plogn
15

---

Published as a conference paper at ICLR 2026
Lemma B.1. Let q; (b) (i, (), for j [8] be as defined in Lemma 2.3, and suppose Li(1) s/v Then
max 9: (j.t) 100log(nsT) JElo]
(8)
Pr
81/p
poly(nST)
(b) (j.t) )) distributed as C3.2 L.(t), where
Proof. By Lemma 2.3 and Lemma 3.2, ma 9: is an exponential random variable with rate 1. Thus
( (i,t) 100 l00ss)))
100 log(nss))
Pr
max q; [c([]]
31/p
Pr
C/2ee/PL,(t
s1/p
S/D
Pr
100 Li()) log(ns())
Since L,(t) 2 s//9, we have
C3.2
(100ggg)))))
Pr
S exp
100 Ls(() log(nsT)
3.2
poly(nsT))
Lemma 3.4. Suppose ((j.t) E [1.5] for all [2]. i [m] and j [s). Then the expected regret
of Algorithm is most O 8//P
logn
Proof. Since the loss on each server is in the range [1, 5), then the loss L;(1) on each expert on each La(t) for
day is at most O (s)/P). By Lemma 2.3, we have that st()) has the same distribution as e#7p an exponential random variable e. By Lemma 3.2, s(() is an unbiased estimate of L;(t) + poly(n7) with second moment O (s1/P). Thus by Lemma 3.3, the expected regret of Algorithm 2 is at most
O
8
Jogn
poly(n?)
T = O 8
1/p
log
Lemma 3.5. Suppose Liii 1) E for all L E [T] i [n] and E [s). Then with high probability, the total communication of Algorithm is at most (sT) nT polylog(nsT) bits.
Proof. Consider Algorithm 2. Observe that time E [T], server j [s] will communicate 3/PP
an expert [n] only if 9; (i,)) 2 100 log(sT:) By assumption, we have t(j,t) < 5 for all
(j,t)
E.(i for b E [B], then for fixed b E [B], Ce G. server j E [s] will use communication only (c: (1 s 500 (nss)) or equivalently,
t E [T], [n] and [s]. Since (0))) (j,t)
(j, (j, s 500P (nT" Since (e!") (j, ()) is an independent exponential random variable with rate
1, then we have
500 500log(ns()) 81/p
log" (n'')
Pr ())
()) Now for fixed [n]. Yi.... Ys denote indicator random variables for whether q; (j. t) triggers a message from the server to the coordinator. In other words, Y, if server j sends message due to and Y, = otherwise. Then we have
Yi +... + Ys] S (nsT).
By standard
Pr [Yi + Chernoff bounds, c.f., Theorem 2.1.
have
that
21 (nsT)) (na7ym By union bound over all [B], E [m). 1 E [T], it follows that the total number of samples sent to the coordinator is at most nZ polylog(ns7).
On the other hand, the coordinator needs to syne with every server for all t [T], inducing
O (sT) communication. Hence, with high probability, the overall communication is at most
O (sT) + nT polylog(nsT).
16

---

Published as a conference paper at ICLR 2026
B.3 MISSING PROOFS FROM SECTION 4
Fact 4.1. Lel e be an exponential random variable with rate 1.
Then for all a > 2, we have
Pr 1 (x, 2x]]] [+=
Proof. By Fact 3.1, the probability density function for is p(z)
= z2
1/0,
We have
2z
2x
Pr E (a,
2xr
p(x) dx
e -- dr.
x²
Note that for x > 2, we have e/1" E (22 11. Hence,
1
2x
1
1
Pr
(x,, 2x²
dx
x x²
I
2x
2x
and
1 E (x,
22
1
1
Pr
2x.
dr
c
2x
2x
4x
4x
Lemma 4.2. We have E s((1) L.(l) + poly(nT) and (si(1)) S SO 3 (L.(1))2
Proof. Let @ be the probability of sampling each time & [T]. Observe that with probability 1 2.
we have 8; (l) = 0. Otherwise, we continue as before.
Let C, Cla-nig eB be independent random variables. Then by Lemma 2.3, we have
1/B7
E
87 (1)
e E
1
max 9 (i.1)
(b)
0
jE(S)
b=1
1/B
1
L,(t)
0
C3.25 1/P
1
II
13
Li(t)
1/B
Ca.ethv
0
Lt(t)
1
B
E
C3.2
el/Bp
I+(1),
where the last equality follows by the definition of C3.2 (E Similarly, we have
[m( in Lemma 3.2.
B
(L((1)2
1/B
(s((t))2
p-
E
II
e
(Ca.2ye
2/p
1/B
1
(L,(1)²
E
0
(Cs.ppe
2/v
B
(I,(1))²
1
E
0
h=1
(Cs.2)
C6b
2/Bp
B
By Lemma 3.2, we have Ca. (1) and E
3B.
Moreover, we set @ TRZ. so that
1
B/Br
Therefore.
(s((1))² < TR² 3 00) (L.()),
17

---

Published as a conference paper at ICLR 2026
as desired.
Lemma 4.3. Suppose (j 5or all [T], e [n] and j [s]. The expected regret of Algorithm 3 is at most O (Rs" /r nl
Proof. Since the loss on each server is in the range [1,5], then the loss [t) on each expert on each day is at most O (ss//r By Lemma 5.1, we have that E (t) = L,(t) + poly(uT) and
E (t)(t))
O (TR)) 3 (L,(t))² Thus by Lemma 3.3, the expected regret of Algorithm 3 is + poly(uT)
at most O [Rs / 3 log T.
T O (R 2 log
Lemma 4.4. Suppose Lij, 1) E [1,
for all E [T], E [n] and j E [s]. Then with high probability,
the total communication is at most
a++ R2
polylog(nsT) bits.
Proof. Consider Algorithm 3. Observe that time E [T]. server j [s] will communicate
an expert E [n] only first it is sampled with probability and then qi (j, Z 100log(nsT)
A/P
By assumption, we have t(j.t) I 5 for all t E [T], E [n] and j [s]. Since q, "
4(j0) for E [B]. then for a fixed b E [B]. server j E [s] will use communication only
(g.)))P
(e) (e:") (j.())/P < log(naT)) or equivalently, if e (j, t) < 500" (oT" Since (e) (j. ()) is an
st/y
independent exponential random variable with rate 1, then we have
Pr[ (I)))/
Pr (c
500log(nsT) 81/2
log"(nT)
Now for a fixed E [n], let Yi...., Ys denote indicator random variables for whether 4 (j. t) triggers message from the server to the coordinator. In other words, Y, if server j sends message due to and Y = otherwise. Then for each j [s). we have
E E S log log"(nT)
since the event of probability must occur first. Then by linearity of expectation, we have
+V + Y.) S e log" log"(ns)).
Similarly, we have that over all times and over all experts, the total expected amount of communi- cation due to these events is at most O (e: nT. (ng)()) Recall that Algorithm sets @ I T By standard Chernoff bounds, c.f., Theorem 2.1, it follows that the total number of samples sent to a the coordinator is at most R polylog(nsT), with high probability. On the other hand, the coordi- nator needs syne with every server for all selected days, in the server does not communicate anything. This process induces F2 volylog(ns77) communication with high probability, by a sim- ilar Chernoff bound argument. Therefore, with high probability, the total communication is at most n polylog(nss]) as claimed.
R
B.4 MISSING PROOFS FROM SECTION 5
Lemma 5.1. Suppose 1.) (j,1) 2 100VT for all b E [B]. Then we have 8:(l) L.(I) +
poly(nT) and E (si(t))) < 2/p RRT.
Proof. Let be the smallest integer such that (t) 2 (3=r) (1r))/11 Observe that we have a* with probability e.- = -f+ Moreover, we require that a² S set (I) wx(l - 2" (())) Consider hypothetical process P where gf (b) (j, t) is reported by all servers if a" < We shall ultimately show that P holds with high probability so that the expected regret is also slightly affected by the actual process.
18

---

Published as a conference paper at ICLR 2026
Now, in this process, st) is nonzero with probability Bax. Lemma 2.3,
Recall that B
3
Then by
B
1/B
E
(1)
E
Oa+
max di jE
[i,
2a
b=1
1/B
E
max di (t)
bml
1/B
E
max di SE(S)
(b)
(1.1)
Li(t)
1/B
B
C3.2el/9
Le(1)
B
IE
C3.2
cl/Bp
L,(t),
where the last equality follows by the definition of C3.2 (E [)( in Lemma 3.2. Similarly,
2/B
E
(s((1))
E
2a
max qi jE
(b)
(i,1)
B
2/8
E
max q: (j.t)
Du 6ml
JE[s]
We have
II
qj jELs
max
( (i.t)
1/B
20
1/v
20
1/v
(3)
We also have Pa-
2 Therefore,
2/87
E
(si(t))
max 9: jE(o)
(6)
(i.t)
Pa
2/p
<
E
20
(2 )1
2/P 2/p
0
Now, for p 2, have (1-211-2/2
and
RT max(st-2/0,) RT. that
(t)) < RTT.
1-2/r Similarly, for p 2, we have e RºT max(s!-2/22
that 1-2/1 22/v R²T
R²T
[(>TT))]]]
E
5
21p
Since 2a < then follows that E (s((1))22)
< 221p RPT, as desired.
We upper bound the regret of Algorithm Lemma 5.2. Suppose have (z(j,t) 5 for all E [T) The expected regret of Algorithm 4 is most O RR Alggn)
19

---

Published as a conference paper at ICLR 2026
Proof. Since the loss each server is most 1, then the loss (,( each expert each day is at most O (s!/M). By Lemma 5.1, we have that E s;({t) L;(t) + poly(nT) and E (s:(t)) 1
/2/r R.T. Thus by Lemma 3.3, the expected regret of Algorithm 4 is at most O (Rs Vlogn) + poly[n2) T O (Rs M)
It remains to upper bound the total communication of Algorithm 4.
Lemma 5.3. Suppose we have L((itt S 1 for all E [T]. Then with high probability, the total communication for Algorithm is at most
R max(s" 12/p/ polylog(nsT) bits.
Proof. Consider Algorithm and a fixed a E [A]. At time E [T], server j E [s] will com-
municate with expert [m] only if it is first selected with probability 24 and then q; (b) (j.t) 2
g//2
By assumption, we have 4(j,t) t) for all t E [T]. [n]. and [s].
100-(2")t/P log(nsT)) (og
Since (h (j.t) (c, G/o)//
((0 for b E [B], for a fixed & E [B], server j E [s] will communicate
only if (c, (j,t))uP 100-(2")4/2 log(neT)) or equivalently, if c, ee,"(,
(j)t)= S
"00""2"-Jo""(00 Since
s//p
(e) (b) ()) is independent exponential random variable with rate 1, we have
Pr (e( (i,)))
100 (20) log(nsT)
s//P
2a log (nT)
Now, for fixed i E [n]. let Yi...., Ys denote indicator random variables indicating whether (b) li (j. t) triggers message from the server the coordinator. other words, Y, server j sends message due to i, and Y3 = 0 otherwise. Then, for each j E [s), we have
E E S log" (nI) Iog"(nI)
since the event with probability must first By linearity of expectation, have
EY Y.J S e (nsT))
Similarly, over all times and experts, the total expected communication due to these events is at most O (o- nT log" (nss)) Recall that Algorithm sets ø²T max(s 1-2pp 1). By standard Chernoff bounds, in Theorem 2. the total number of samples sent the coordinator is at most R polyloggnss")) -max(s" 1-2p/ 1), with high probability. On the other hand, the coordinator must sync with every server for all selected days in case the server does not communicate anything. This process induces से polylog(ns?)) max(s1 1-1p/ 1) communication with high probability, by similar Chernoff bound argument. Thus, with high probability, the total communication is at most nts) max(s"12//p_) polylog(ns7)). desired. R
20


Reviews:
[{"review_id": "falBAkdftz", "reviewer": "Reviewer_xgxY", "summary": "The paper considers the distributed best-expert problem where there are n experts and s servers. Losses are a matrix L in R^{n x s}, where each column sits on a server, and the Lp norm of a row corresponds to an expert's loss. The goal is to design a distributed online protocol that minimizes regret with respect to the best fixed expert in hindsight, and experiences bounded communication costs per-round. \n\nThey make use of the following facts. 1) Taking the maximum across a row of L, where each component is divided by an appropriately scaled exponential random variable, allows one to construct an unbiased estimate of the Lp norm of the row. 2) Since this is a maximum, communication costs can be preserved by omitting components that do not a meet a threshold while still exactly computing (1), so long as all components are not thresholded. Moreover, there is a threshold that ensures a polylog number of samples are sent for each expert, and a vanishingly small probability of failure. 3) By repeating this experiment O(1/p) times, one can reduce the variance of this estimate at the cost of a small amount of bias. \n\nPutting these facts together allows one to execute the multiplicative weights algorithm on a centralized server that receives n*polylog(...) samples per-step via the procedure above, and an addition O(s) communication to check that all servers are done communicating. \n\nNext, they parameterize this algorithm to achieve a trade-off between regret and communication in a very trivial way. With some probability, the servers can be made to skip the protocol all-together. By sharing randomness, this brings communication complexity down to zero on those rounds, while maximizing regret, and increasing the variance of the loss estimates. For a target regret bound R, they show this protocol requires (n + s)(polylog(...))/R^2 communication complexity. Finally, they employ one more trick, where the threshold selected in step (2) is allowed to be scaled down according to an appropriately chosen distribution to improve the dependency on s even further. \n\nEmpirical evaluations are given on a hyperparameter tuning task, showing improved communication costs  over Jia et al.", "questions": "Fig 1 seems like it is underselling the improvement for small p. For p = 1, does this work attain communication complexity, (n /(s R^2)) polylog(...) through theorem 1.3? Or am I mistaken? \n\nThe prose in Section 5 claims that losses need not be bounded, and yet the Lemmas assume l_i(j, t) <= 1. Can the authors explain? \n\nDo the authors think there might exist a more natural protocol that avoids having all servers go silent on some rounds? While the theory works out, this seems artificial. \n\n\"We remark that the choices of the losses being within the range [1, 5] in the statement of Theorem 1.1 are arbitrary\" => I think at some point the manuscript was updated to actually state Theorem 1.1 with arbitrary interval [a,b].\n\nThere are minor typos in the appendix involving misaligned hat symbols. See bottom of page 16, top of page 17. Please proof-read and fix.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Strength #1: The paper is extremely well written, communicating complicated ideas in an incremental fashion. The main ideas of the theory are presented in a manner that allow the proofs to be checked easily. \n\nStrength #2: The paper improves upon previous work by a) generalizing to arbitrary p-norms, b) attaining the regret-sensitive rate s/R^2 on the dependency on the number of servers, and c) giving an algorithm that improves the dependence on number of servers by a factor max(s^{1-2/p})\n\nStrength #3: I found the approach in the warm-up algorithm to be very elegant, and did a good job of setting up the more technical details of the later algorithms.", "weaknesses": "Weakness #1: The trick to trade-off communication with regret is somewhat artificial, requiring that all servers are silent on some rounds. While the theory works out, I wonder if there is a more natural algorithm that would yield further improvement.\n\nWeakness #2: This is largely a theory paper exploring communication-regret trade-offs in expert learning. It may be a little outside the primary areas of interest for ICLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5phmwwM4MW", "reviewer": "Reviewer_6CRv", "summary": "This paper studies the distributed experts problem in the message-passing model, where the losses for each expert are distributed across multiple servers. The authors introduce a novel distributed protocol that achieves improved communication-regret trade-offs for general $\\ell_p$ losses. Specifically, for any $R \\geq 1/\\sqrt{T}$, they design an algorithm attaining regret $\\mathcal{O}(R s^{1/p} \\sqrt{\\log n})$\nusing \n$\n\\mathcal{O}\\left( \\frac{n+s}{R^2} \\cdot \\max(s^{1-2/p}, 1) \\, \\mathrm{polylog}(nsT) \\right)\n$\nbits of communication. This work extends beyond prior results, which were restricted to $\\ell_1$ bounded losses.", "questions": "- The paper states that it is information-theoretically impossible to achieve regret smaller than $O(1/\\sqrt{T})$, yet later compares its communication performance to [1] at $R = O(1)$. Could the authors clarify this apparent inconsistency and explain how their claimed improvement holds for the achievable regime $R \\ge 1/\\sqrt{T}$?\n\n- What are the practical or theoretical motivations for studying $\\ell_p$ losses with $p > 1$ in this setting? Since the $\\ell_1$ loss decomposes naturally across servers, it would be helpful to better understand scenarios where $\\ell_p$ losses provide clear advantages.\n\n - The paper does not provide matching lower bounds on communication complexity. Can the authors comment on whether such bounds are known, or how close their algorithms might be to optimal in this regard?\n\n[1]  Zhihao Jia, Qi Pang, Trung Tran, David Woodruff, Zhihao Zhang, and Wenting Zheng. Communication bounds for the distributed experts problem. arXiv preprint 2025", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "-  This is the first work to analyze distributed experts in the coordinator model for general $\\ell_p$ losses.\n    \n- The embedding of $\\ell_p$ losses into $\\ell_\\infty$ through exponential random variables, combined with a geometric mean estimator for variance reduction, represents a technically sophisticated and creative approach.\n    \n- The presentation of three successive algorithms (Algorithms 2--4), a warm-up, a parameterized version that achieves regret-communication tradeoff, and the final algorithm, which does not require the losses to be bounded, offers a clear conceptual progression\n    \n- The proofs are rigorous, clearly presented, and appear technically correct.", "weaknesses": "- The authors state that it is information-theoretically impossible to achieve regret smaller than $O(1/\\sqrt{T})$, but then compare their method to the algorithm of [1] for $R = O(1)$, claiming improved communication in that regime. This causes confusion as $R = O(1)$ is not achievable. Instead, taking $R \\ge 1/\\sqrt{T}$ seems to reproduce the communication cost of [1], showing no improvement compared to [1]. The claimed improvement in communication complexity should be either removed or clarified.\n\n-  It is unclear why the $\\ell_p$ loss is preferable to the additive $\\ell_1$ loss, which naturally decomposes across servers and simplifies communication. The paper would benefit from a stronger motivation for why handling these types of losses is relevant.\n    \n- The paper lacks formal communication lower bounds, making it unclear whether the proposed protocols are optimal or merely improve upon previous works.\n\n[1]  Zhihao Jia, Qi Pang, Trung Tran, David Woodruff, Zhihao Zhang, and Wenting Zheng. Communication bounds for the distributed experts problem. arXiv preprint 2025", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dXqfvwTfgB", "reviewer": "Reviewer_zz4T", "summary": "The paper considers learning with experts but in a distributed setting where there are $s$ servers and each of $n$ experts has a 'partial' loss at each server. The total loss of an expert is the $\\ell_p$ norm of the $s$-dimensional loss vector over the $s$ servers. Over a sequence of $T$ days, there is a decision maker communicating with the servers which each day has to play an expert with the goal of minimizing the regret compared to the best expert in hindsight. With unlimited communication between the servers, the decision maker can learn the full loss vector and use a standard regret minimizing algorithm, so the interesting question that the paper considers is tradeoffs between regret and communication. Improving upon previous work, they show that (ignoring polylog factors), there is an  algorithm which achieves (normalized) regret $R$ using $O(n/R^2+s/R^2)\\max(s^{1-2/p},1)$ bits of communication.\n\nThe techniques used in the paper are based on sampling. Instead of all servers communicating the partial loss of an expert, they scale the losses by ($1/p$ powers of) iid exponential random variables and only send the loss of an expert if it exceeds some threshold. The idea is that the maximum of such scaled variables can be turned into an unbiased estimator for the $\\ell_p$-norm and additionally, by the thresholding hopefully only a small number of servers will actually have to send an input. \n\\paragraph{Strengths}\nI found the paper to be quite well motivated, since the problem feels motivated from both a theoretical and practical perspective. I think that the algorithmic ideas in the paper are nice and appear to be a natural approach for the problem.", "questions": "Please address the two concerns under weaknesses. \n\nA couple of more minor comments:\n\nAbstract: Do you mean $R\\lesssim$?\n\nl105: $[1,5]$ is $[a,b]$ in the theorem\n\nTheorem 2.1: The bound should be $\\exp(-\\mu\\delta^2/3)$\n\nIs the max stability property your own result? \n\nl327: Shared randomness seems like an unstated model assumption. You should probably discuss this earlier.\n\nAlgorithm 3: What does it play with probability $1-\\rho$ when it continues to the next time?\n\\newpage\n\n\\section{Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams}", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "I found the paper to be quite well motivated, since the problem feels motivated from both a theoretical and practical perspective. I think that the algorithmic ideas in the paper are nice and appear to be a natural approach for the problem.", "weaknesses": "My main concern about the paper is that there are some important steps in the proof where I have doubts about the correctness of the argument. \n\n(1) This is probably my most important concern and is about the important lemma 3.3. The proof is quite sketchy. It is stated that a conditional expectation (l755) equality holds for all realizations of $p_t$. Realizations of what? I assume of $p(t)$, but what is $p(t)$? I assume the probability vector of playing each expert at time $t$ because then the equation in l755 seems to make sense. However, on the next page, it is shown that $\\textbf{E}[C_t \\mid p_t]=\\textbf{E}[C'_t \\mid p_t]$ and then concluded that  $\\textbf{E}[C_t]=\\textbf{E}[C'_t]$. The conclusion seems wrong, because the $p_t$ are realizations of different random variables in the first equation, namely those obtained from running the algorithm with $\\hat s_i(t)$ as opposed to $L_i(t)$. So it seems that the paper has proved something like \n$\\textbf{E}[C_t \\mid X=p_t]=\\textbf{E}[C'_t \\mid Y=p_t]$\nfor two different variables $X,Y$, but I don't think this implies that $\\textbf{E}[C_t]=\\textbf{E}[C'_t]$\n\n(2) You claim in line 305 that the probability that the max is not send the the paper $1-1/poly(nT)$, but I don't see where you prove this. I can only find the places where you prove an upper bound on the number of values sent to the coordinator.  It's possible that I just missed it, so in that case, you can just point out to me where you prove it.\n\nThese concerns are the reason for my low score. It is however possible that I'm missing something, so if the authors can satisfactorily address the above concerns, I would be very happy to update the score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N68JMbiCKT", "reviewer": "Reviewer_g7FC", "summary": "The paper presents a regret bound for a distributed online convex optimisation task.   The setup is that each expert sees a loss vector of length s, where s is the number of servers, and performance is evaluated by the Lp norm of this vector and so requires communication amongst the servers.  Regret is wrt the best expert.  The motivation primarily comes from hyperparameter optimisation, where each expert corresponds to a choice of hyperparameters and each server to a different dataset on which an ML model is evaluated.  The novelty lies mainly in the extension to Lp norms with p>1.", "questions": "See comments re weaknesses above.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is well written, and the analysis appears to be sound (I did not carefully check all of the proofs).", "weaknesses": "I found the HPO motivation given for this work unconvincing.  Communication between servers is not really the main bottleneck - sending a few values takes little bandwidth and can be carried out quickly.  Synchronisation seems more of an issue.   It would have been much better to have presented a proper comparison against state of the art hyperparameter optimisation methods in the empirical evaluation section.  That said, the main contribution is probably the theoretical analysis.  I don't see much interesting new maths techniques being introduced, so the contribution is mainly covering Lp loss with p>1.   But online convex optimisation is a mature area these days, with a large literature, and the present work seems like a small extension of previous work and a relatively minor contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)