Collaborative Algorithms for Online Personalized Mean Estimation
Authors: Mahsa Asadi
Aurélien Bellet
Odalric-Ambrym Maillard
Marc Tommasi
Venue: Accepted by TMLR ()

Abstract: We consider an online estimation problem involving a set of agents. Each agent has access to a (personal) process that generates samples from a real-valued distribution and seeks to estimate its mean. We study the case where some of the distributions have the same mean, and the agents are allowed to actively query information from other agents. The goal is to design an algorithm that enables each agent to improve its mean estimate thanks to communication with other agents. The means as well as the number of distributions with same mean are unknown, which makes the task nontrivial. We introduce a novel collaborative strategy to solve this online personalized mean estimation problem. We analyze its time complexity and introduce variants that enjoy good performance in numerical experiments. We also extend our approach to the setting where clusters of agents with similar means seek to estimate the mean of their cluster.

Published in Transactions on Machine Learning Research (12/2022)
Collaborative Algorithms for Online Personalized Mean Estimation
Mahsa Asadi
Hollahso@@gaillcom com com
Unio. Lille, Inria, CNRS, Centrale Lille UMR 9189 CRISIAL, F-59000 Lille, France
Aurélien Bellet
wurelten.bellet@iiine
Unio. Lille, Inria, CNRS, Centrale Lille UMR 9189 CRIStAL, F-59000 Lille, France
Odalric-Ambryy Maillard
alatric.meillard@@@nnraa.a
Unio. Lille, Inria, CNRS, Centrale Lille UMR 9189 CRISIAL, F-59000 Lille, France
Marc Tommasi
mare. mar.toommasi@irri..ff
Univ. Lille, Inria, CNRS, Centrale Lille UMR 9189 CRISIAL, F-59000 Lille, France
Reviewed on OpenReview:
https: // openreview. net/ form? id= Vápl NSZ22
Abstract
We consider an online cstimation problem involving set of agents. Each agent has access to a (personal) process that generates samples from a real-valued distribution and seeks to estimate its mean. We study the case where some of the distributions have the same mean, and the agents are allowed actively query information from other agents. The goal to design an algorithm that enables each agent to improve its mean estimate thanks to com- munication with other agents. The means well as the number of distributions with same mean unknown, which makes the task nontrivial. We introduce novel collaborative strategy to solve this online personalized mean estimation problem. We analyze its time complexity and introduce variants that enjoy good performance in numerical experiments. We also extend our approach to the setting where clusters agents with similar means seek to estimate the mean of their cluster.
1 Introduction
With the widespread of personal digital devices, ubiquitous computing and ToT (Internet of Things), the need for decentralized and collaborative computing has become more pressing. Indeed, devices are first of all designed to collect data and this data may be sensitive and/or too large to transmitted. Therefore, is often preferable keep the data on-device, where has been collected. Local processing on single device is a always possible option but Icarning in isolation suffers from slow convergence time when data arrives slowly. In that case, collaborative strategies can be investigated in order increase statistical power and accelerate learning. In recent years, such collaborative approaches have been broadly referred to federated learning (Kirrouz et al. 2021).
The data collected at each device reflects the specific usage, production patlerns and objective of the associ- ated agent. Therefore, we must solve a set of personalized tasks over heterogeneous data distributions, Even though the tasks are personalized, collaboration can play significant role reducing the time complexity and accelerating learning in presence of agents who share similar objectives. An important building block design collaborative algorithms is then to identify agents acquiring data. from the same (or similar) distri-

---

Published in Transactions on Machine Learning Research (12/2022)
bution. This is particularly difficult to do in online setting, in which data becomes available sequentially over time.
In this work, we explore this challenging objective in the context of a new problem: online personalized mean estimation. Formally, each agent continuously receives data from a personal o-sub-Gaussian distribution and aims to construct an accurate estimation of its mean as fast as possible. At each step, each agent receives a new sample from its distribution but is also allowed to query the current local average of another agent. To enable collaboration, we assume the existence of an underlying class structure where agents in the same class have the same mean value. We also consider relaxed assumption where the means of agents in class are close (but not necessarily equal). Such assumptions are natural in many real-world applications (Adi et al. 2020). A simple example is that of in different environments, monitoring parameters such as temperature in order to accurately estimate their mean (see for instance Mateo et al. 2013). Another example is collaborative filtering, where the goal is to estimate user preferences by leveraging the existence of clusters of users with similar preferences (Su Khoshgoftaar] 2009a). Crucially, the number of classes and their cardinality are unknown to the agents and must. be discovered in an online fashion.
We propose collaborative algorithms to solve this problem, where agents identify the class they belong to in an online fashion so as to better and faster estimate their own mean by assigning weights to other agents' estimates. Our approach is grounded in Probably Approximately Correct (PAC) theory, allowing agents to iteratively discard agents in different classes with high confidence. We provide a theoretical analysis of our approach by bounding the time required by an agent to correctly estimate its class with high probability, as well as the time required by an agent to estimate its mean the desired accuracy. Our results highlight the dependence settings our approach achieves nearly the same time complexity as oracle who would know the classes beforehand. Our numerical experiments on synthetic data are in line with our theoretical findings and show that some empirical variants of our approach can further improve the performance in practice.
the gaps between the true means of agents in different classes, and show that in some
The paper is organized as follows. Section Section the related work on federated learning and collaborative online learning. In Section B we formally describe the problem setting and introduce relevant notations. In Section
g we introduce our algorithm and its variants. Section 3 presents our theoretical analysis of the proposed algorithm in terms of class and mcan cstimation time complexity. Section D is devoted to illustrative numerical experiments. Section 7 extends our approach to the case where classes consist of agents with similar (but not necessarily equal) means and agents seek to estimate the mean of their class. We conclude and discuss perspectives for future work in Section g
2 Related Work
Over the last few years; collaborative eslimation and learning problems involving several agents with local datasets have been extensively investigated under the broad term of Federated Learning (FL) (Kairouz al., 2021). While traditional FL algorithms learn a global estimate for all agents, more personalized approaches
have recently attracted a lot of interest (see for instance Vanhaesebrouck et al.)
2017 Smith et al. 2017
Fallah et al. 2020 /attler et al. 2020 Hanzely et al. 2020; Marroq et al. 2021 and references therein)
With the exception of recent work on simple linear regression settings (Cheng et al. 2021), these approaches typically lack clear statistical assumptions on the relation between local data distributions and do not provide error guarantees with respect to these underlying distributions. More importantly, the above methods focus on the batch learning sctting and are not suitable for online learning.
In the online setting, the work on collaborative learning has largely focused on multi-armed bandits (MAB). Most approaches however consider single MAB instance which is solved collaboratively by multiple agents, Collaboration between agents can be implemented through broadcast messages to all agents (Hillel et al. 2013 Tao el al. (201)), via a server (Wang et al. 2020b), or relying only on local message exchanges over a et al.) 2019 Wang et al. 2020al Landgren et al., 2021 Madhushani et al. (021). Other approaches do not allow explicit communication but instcad consider
network graph (Sankararaman et al. 2019 Martinez-Rulle
collision model where agents receive no reward if several agents pull the same arm [Boursier & Perchet,
2019 Wang et al. 2020a). In any case, all agents aim at solving the same task.
2

---

Published in Transactions on Machine Learning Research (12/2022)
Some recent work considered collaborative MAB settings where the arm means vary across agents. Extending their previous work (Boursier & Perchet 2019) Boursier et al. (2020) consider the case where arm means can vary among players. Under their collision model, the problem reduces to finding a one-to-one assignment of agents to arms. In Shi & Shen (2021), the local arm means cach agent are IID random realizations of fixed global means and the goal is to solve the global MAB using only observations from the local arms with an algorithm inspired from traditional FL. Similarly, Karpov & Zhang (2022) extend the work of Tao let al. (2019) by considering different. local arm means for each agent with the goal to identify the arm with largest aggregated mean. (hii et al. (2021) introduce limited amount of personalization by extending the model of Shi & Shen (2021) to optimize a mixture between the global and local MAB objectives. [Rdda et al. (2022) further consider a known weighted combination of the local MAB objectives, and focus on the pure exploration setting (best arm identification) rather than regret minimization. A crucial difference with our work is that there is no need to discover relations between local distributions to solve the above problems.
Another related problem (2000) 2021) construct a similarity graph while solving the best arm identification problem, but consider only single agent. In contrast, work considers a multi-agent setting with personalized estimation tasks, and our approach discovers similarities across agents' tasks in an online manner.
identify a graph structure on top of the arms in MAB. Kocák & Garivier
3 Problem Setting
We consider a mean estimation problem involving A agents. The goal of each agent é [A] = (1, .A} is to estimate the mean Ma of a personal distribution V. over R. In this work, we assume that there exists a 2 0 such that each V/ is o-sub-Gaussian, i.e.:
AA e IR, logez-e, exp(A(x- pa)) x
This classical assumption captures a property of strong tail decay, and includes in particular Gaussian distributions (in that case, the smallest possible o² corresponds to the variance) as well as any distribution supported on a bounded interval (c.g., Bernoulli distributions).
We consider an online and collaborative setting where data points are received sequentially and agents can query each other to learn about their respective distributions. Agents should be thought of as different user devices which operate in parallel. Therefore, they all receive new sample and query another agent at cach time step.
Formally, we assume that time is synchronized between agents and at each time step t, each agent a receives a new sample wt from its personal distribution Pa with mean Pas which is used to update its local mean estimate Hh. = Ex=1 of It also chooses another agent I to query. As a response from querying agent I, agent a receives the local average of,, of agent / (i.e., the average of t independent samples from the personal distribution M) and stores it in its memory z',, along with the corresponding number of samples ni_1 = t. Each agent thus keeps memory [ m...)..... (F', n), of the last local averages (and associated number of samples) that it received from other agents. The information contained in this memory is used to compute an estimate pta of pa at each time t. Our goal is to design query and estimation procedure for each agent.
As described above, note that when an agent queries another agent at time I, it does not receive one sample from this agent (as c.g. in multi-armed bandits), but receives the full statistics of obscrvations of this agent up to time L. This is considerably much more information than in typical MAB settings, and naturally requires specific strategies.
The goal of cach agent to find a good estimate of its personal mean as fast as possible, without consideration for the quality of the estimates in earlier steps (i.e., we do not seek to minimize a notion of regret). In the online learning terminology, this is referred to as a pure exploration setting (like best arm identification in multi-armed bandits, sce Audibbrt et al.) 2010). Formally, we will mcasure the performance of an algorithm using the notion of (c, (0 -oooverrgeee in probability (Bertsckas & Tsitsiklis, 2002 Wasscrman 2013). which we recall below.
3

---

Published in Transactions on Machine Learning Research (12/2022)
Definition 1 (PAC-convergencc). An estimation procedure for agent is called (c.8)-connergent if there cpists Ta e N such that the probubility that the meon estimator Ita of agent is e-distant from the true meon for any time t > To is at least 1- ô:
P(vt> To IA4 - Mal s se)> 1-
(1)
While it is easy to design (c, (c.))-oonergee estimation procedure for a single agent taken in isolation, the goal of this paper is to propose collaborative algorithms where agents benefit from information from other agents by laking advantage of the relation between the agents' distributions. This will allow them to build up more accurate estimations in less time, i.., with smaller time complexity Ta-
Specifically, to foster collaboration between agents, we consider that the set of agents [A] is partitioned into equivalence classes that correspond to agents with the same mean In real scenarios, these classes may represent sensors in the same environment, objects with the same technical characteristics, users with the same behavior, ctc. This assumption makes it possible for an agent to design strategics to identify other agents in the same class and to use their estimates order to speed up the estimation of his/her own mean. Formally, we define the class of a as the set of agents who have the same mean as a.
Definition 2 (Similarity class). The similarity class of agent is given by:
Cu = = A..
where De, IMa - 141 is the gap belween the means of agent and agent. I.
The gaps (a, define the problem structure. We consider that the agents do not know the means, the gaps, even the number of underlying classes. Hence the classes {CoJaela] are completely unknown. This makes the problem quite challenging.
Remark 1 (Scalability). In large-scale systems, it may be impractical for agents to query all other agents and/or to maintain a memory size that is linear in the number of agents A. From a practical point of view, each agent can instead consider restricted subset of agents of veasonable size. This subset could be picked uniformly at random, be composed of neighboring nodes the network or in the physical world, or be based on prior knowledge on who is more likely to be in the same class (when available).
4 Proposed Approach
In this section, first introduce some of the key technical components used in our approach, and then present our proposed algorithm.
4.1 Main Concepts
In approach, each agent computes confidence intervals La,1 [= 3s(m",,), + Bs(n") for the mean estimators [<L [=,, that it holds in memory at time t. The generic confidence bound (s(n))) takes as input the number of samples nia seen for agent at time f, and 5 corresponds to the risk paramcter so that with probability at least d the true mean μ falls within the confidence interval Ia.--
Agent a will use these confidence intervals to assess whether another agent / belongs the class C. through the ovaluation of an optimistic distance defined below.
Definition 3 (Optimistic distance). The optimistic distance with agent I from the perspective of agent is defined as:
-1)===F -F,,l -- -n Bo(n"n).
(2)
The "optimistic" terminology is justified by the fact that (1) is, with high probability, a lower bound on the distance between the true means Pa and ir of distributions va and in- Recall that two agents belong to
II Section 7 will consider relaxed version of this assumption where classes consist ageett with similer (not necessarily
equal) means.
4

---

Published in Transactions on Machine Learning Research (12/2022)
Algorithm CoIME
Parameters: agent a, time horizon H, risk 6, weighting scheme a, and query strategy choose agent vI [A]: 22. 0, na.
C² - (1e [A]] a [
50} = [A]
f= H do
e [A]: Fa Fall V'a1 m
Perceive:
Receive sample r/e ~ Vaa
Fe st-1 x 1-1 nt
t x 7: ni
Query:
C² (LE [A] : (1) 50}
Query agent l= choose_ _gent(Ca to get of,1
F/ Zi,, n
Estimate:
C₁ - {LE [A] d' (1) s 0}
1l Eisc a'y x zy
end for
Output: N
the same class if the distance of their true mean is zero. Since these values are unknown, the idea of the above heuristic to provide proxy based observed data, and high probability confidence bounds. Tn particular, will adopt the Optimism in Face of Uncertainty Principle (OFU) (see Auer et al. 2002) and consider that two agents may be in the same class if the optimistic distance is zero or less. Hence, we define an optimistic notion of class accordingly.
Definition 4. The optimistic similarity class from the perspective of agent at time is defined
C. = [A]] d (1) sO..
Having introduced the above concepts, we can now present our algorithm.
4.2 Algorithm
The collaborative mean estimation algorithm we propose, called ColME, given in Algorithm (taking the perspective of agent a). For conciseness, we consider that (₂(0) +00. At each step f, agent performs three main steps.
In the Perceive step, the agent receives sample from its distribution and updates its local average together with the number of samples.
In the Query step, agent a selects another agent following a query strategy given as a parameter to the ColME algorithm. Agent a runs the choose agent function select another agent and asks for its current local estimate to update its memory. We propose two variants for the choose agent function:
Round-Robin: cycle over the set [A] of agents one by in fixed order.
Restrictet-Roun-RRobin Robid-Robin: like round-robin but ignores agents that are not in the set of optimistically similar agents Ct
Restricted-
The focus on round-robin-styy strategies is justified by the information structure our problem setting, which very different from classic bandits. Indoed, querying an agent at time produces an estimate computed on the observations collected by this agent so far. The choice of variant (Roun-Robin Restricied-Round-RRobbn will affect the class identification time complexity, we shall discuss later.
5

---

Published in Transactions on Machine Learning Research (12/2022)
Finally, in the Estimate step, agent a computes the optimistic similarity class C2 based available in- formation, and constructs its mean estimate as weighted aggregation of the local averages of agents that belong to Ca. We propose different weighting mechanisms:
Simple weighting, This is a natural weighting mechanism for aggregating samples:
naa
0
Ener 0,1
Soft weighting. This is heuristic weighting mechanism which leverages the intuition that the more the confidence intervals of two agents overlap, the more likely that they are in the same class. Moreover, the smaller the union of the agent means, the more confident we are that the agents are in the same class, In other words, we are not equally confident about all the agents that are selected for estimation, and this weighting mechanism incorporates this information:
a²,1 n/o Le,a Laiil
(Ta,a U Ia,i Zoof
n aaaaaaa a normalization factor.
where Zunft Execy Paaadad
Aggressive weighting. This is an extension of the previous soft weighting mechanism that is more selective. Not only does it consider the overlap and interscction of the agents' confidence intervals, but it also requires the size of the intersection to be larger than half the size of both confidence in- tervals from the two agents. Let us denote the binary value associated with this condition by Ea, = 1 ( (. (a(t Then
Haa n banl x Ea.1 Lao1 read Va, u Tnal Zuga
ni Wa Taaanlais is a normalization factor.
where Zagg = Execy
4.3 Baselines
We introduce two basclines that will be usod to put the performance of our approach into perspoctive, both theoretically and empirically.
Local estimation. Estimates are computed without any collaboration, using only samples received from the agent's 's own distribution, i.e. p F/.a-
Oracle weighting. The agent knows the true class C. via an oracle and uses the simple weighting a
Eic, "
5 Theoretical Analysis
In this section, provide theoretical analysis of our algorithm ColME for the query strategy Restricted- Round-Robin and the simple weighting schome. Specifically, we bound the time complexity in probability for both class and mean estimation. Below, we explain the key steps involved in our analysis and state our main results. All proofs can be found in the appendix.
A key aspect of our analysis to characterize when the optimistic similarity class (Definition 4 coincides with the true classes. We show that this is the case when two conditions hold. First, for a given agent a, we need the confidence interval computed by about agent to contain the true mean fe for all e A.

---

Published in Transactions on Machine Learning Research (12/2022)
Definition 5. We define the following events:
E
n [ - Mul Bo(n [[[A]
(3)
E. n E
(4)
We can guarantee that Eg holds with high probability via an appropriate parameterization of confidence intervals. We use the so-called Laplace method (Maillard 2019).
Lemma Let (0,1), E [A]. Setting B6(n) ov 2 x (1+ In 1/7())))) with 2(6) have:
8x
we
P(E,) 2 8
(5)
The second condition is that agent's memory about the local estimates of other agents should contain enough samples. Let denote by 18 (x:) the smallest integer such that x> Bo(n). Definition 6. From the perspective of agent and at time t, event Gt is defined os:
G
n nna na.1
(6)
[e[_]
[19 ( [13 2n) otherwise,
if
where
nay
with A, = minie[ancc. A..--
Note that the required number of samples is inversely proportional to the gaps between the means of agents in different classes. Having enough samples and knowing that the true means fall within the confidence bounds, we can show that the class-estimation rule d', indicates the membership of in Ca.
Lemma 2 (Class membership rule). Under F%, a G and vI e [A] and at time t: d' (1) > 0 = le [A](C.
Using the above lemma,, we obtain the following result for the time complexity of class estimation. Theorem (ColME class estimation time complexity). For any (0,1), employing Restricted Round- Robin query strategy, we have:
P(t Sa : C22 + Ca) 6 with Sa nn 1- Σ L[AANC.
1 (mng, Sm +
The dominating term in the class estimation time complexity Ça for agent is equal to the number n of samples required to distinguish agent a from the one who has smallest nonzero gap A, to o, which is of order 0(1/22) 2 There then an additional term A - since all others agents that are not in C. could require the same number samples. Finally, the last term in accounts for agents that require less samples and had thus been climinated before, which reflects the gain of using Restricted- Roeed--Rnnd-oooo Round-Robin. When have enough samples (at least (a), Theorem guarantees that correctly learn the class (Ca C.) with high probability. We build upon this result to quantify the mcan estimation time complexity of our approach.
query strategy
Theorem (ColME mean estimation time complexity). Given the risk parameter 8, using the Restricted- Round-Rohin Robin query strategy and simple weighting, the mean estimator ph, of agent a is (e, 4 coonvereet,, that is:
with Ta max(Sa, [ (c)
CCal
P(V1> To 1/ Hal s
(8)
7
C.
2
We Õ(-) hide constant and logarithmic terms.

---

Published in Transactions on Machine Learning Research (12/2022)
Several comments are in order. First, recall that collaboration induces bias in mean estimation before class estimation time. Because the problem structure is unknown, any collaborative algorithm that aggregate observations from different agents will suffer from this bias, but the bias vanishes as soon as the class is estimated and we outperform local estimation.
Then, to interpret the guarantees provided by Theorem 2 it is useful to compare them with the local estimation baseline, which has time complexity = has a time complexity of (mmx((11/))))) (1/2) C/al)).l)). ) In other words, it is faster than local estimation as long as the time Sa needed to correctly identify the class Ca is smaller than [187 (c)), that is precisoly when:
Inspecting @ we see that our approach
< Bo + +- (<[A]TCC))
Σ. 1 (0
This condition, which roughly amounts to e A., relates the desired precision of the solution e to the problem structure captured by the gaps (Aa.heea) between the true means through ( (see Definition 6). We will see in our experiments that our theory prodicts quite well whether an agent empirically benefits from collaboration.
Remarkably, our approach can be up to [Cal times faster than local estimation: this happens roughly when << <<a/lVCaa i.e., for large enough gaps or small enough e. In this regime, the speed-up achieved by our approach is nearly optimal. Indeed, the time complexity of the oracle weighting baseline introduced in Section 4.3 is precisely [0] |ai-11 ((1/e"(c)), just like our approach. Note that in a full information setting where agent a would know C. and would also have access to up-to-date samples from all agents at each step, the time complexity would be only slightly smaller, namely (+),
2
[c,]
Remark 2 (Frequency of communication). For simplicity, we consider that agents communicate each time they collect new sample, which is standard in the literature of collaborative learning (see for instance the collaborative MAB approaches discussed in Section D) However, different trade-ofJs between communication and data collection can be considered. In particular, it is struightforward to adapt the setting and our results to the case where each agent collects m samples belween each commumication: il amounts to mulliplying by m the number of observations in our confidence intervals and empirical estimates. This provides a way to reduce commmnnication, as well as to métigate privacy concerns by ensuring that only sufficiently aggregated quantities are exchanged (even in early rounds). Extensions to cases where the number of samples between each commeniccliin is random and/or orr varies across agents are left for fulure work.
6 Numerical Results
In this section, we provide numerical experiments on synthetic data to illustrate our theoretical results and assess the practical performance of our proposed algorithms
6.1 Experimental Setting
We consider A = 200 agents, a. time horizon of 2500 steps and a risk parameter 5 = 0.001. The personal distributions of agents are all Gaussian with variance o² 0.25 and belong to one of classes with means 0.2, 0.4 and 0.8. The class membership of each agent (and thus the value of its true mean) is chosen uniformly at random among the three classes. We thus obtain roughly balanced class sizes. While the evaluation presented in this section focuses this 3-class problem, in the appendix we provide additional results simpler 2-class problem (with means 0.2 and 0.8) where the benefits of our algorithm is even more significant.
We consider several variants of our algorithm ColME: we compare query strategies Hound-Robil and Restricted-Round-Fool with simple weighting, and also evaluate the use of soft and aggressive weight- ing schemes the Cestricted--Ronnd-eee case. This gives 4 variants of our algorithum: Round-Robin, RoundteeddRuud-RRobbbo
and Restrisive Coeeeetee--oonn--Roeee
Regarding competing approaches, recall that our setting is novel and rithms addressing the same problem. We can however compare against two baseline strategies. The Local
not aware of existing algo-
The code can be found at http:///tttiioooo////////aaaaaae

---

Published in Transactions on Machine Learning Research (12/2022)
0.030
1.0
reiridiedrcunddrooe
soft roft-restricte- rertieedd-uun--bbrr--
0.9
round-rotin
Error meaa estimaatin
0.025
restricted-ron
reuddd-rd---rrnn oracle
0.8
0.020
local
0.7-
0.015
0.6
0.010
0.5
0.4
0.005
1500
2500
0.000
1500
Time
Time
(a) Class estimation precision over all agents
(b) Error in mean estimation over all agents
Figure 1: Results across time on the 3-class problem (Gaussian distributions with true means 0.2, 0.4, 0.8). Thanks to our collaborative algorithrms Restricted-Round Robin,, Round- Roodd)),,,, agents are able to estimate their true class (Fig. [(a)] and thereby obtain accurate mean estimates much more quickly than using purely local estimation (Fig. 1(b)
-esressive-eesttritedd----ooe
baseline corresponds to the case of no collaboration. On the other hand, the Oracle baseline represents upper bound on the achievable performance by any collaborative algorithm it is given input the true class membership of cach agent and thus docs not need to perform class cstimation.
All algorithms are compared across 20 random runs corresponding to 20 different samples. In a given run, at each time step, each agent receives the same sample for all algorithms.
6.2 Class Estimation
We start by investigating the performance in class estimation. In this experiment, only Round-Robin and Seariittdd-RomdRRobbbil are shown since the different weighting schemes have no effect class estimation.
We first look at how well an agent estimates its true class Ca with its heuristic class C₂ across time. To measure this, we consider the precision at time t computed as follows:
C n Cal
precisiong:
(10)
[
We compute the average and standard deviation of 10 across runs, and then average these over agents. Figure [(a) shows how the precision of class estimation varies across time as agents progressively remove others from their heuristic class and eventually identify their true class. As can be seen clearly in Figure 3
in the appendix, the classes 0.2 and 0.8 are separated very early, quickly followed by 0.4 and 0.8 and finally, after sufficiently many samples have been collected, the pair with the smallest gap (0.4 and 0.2).
We also observe that Round-ood Robin and Restricted- Cnstrieted-RRondd-eee before classes are identified. This is in line with Theorem [ which shows that class estimation time mainly depends on n the time needed climinate the agent with smallest nonzero gap. This dominant term and the fact that querying an agent time i yields the full statistics of observations of this agent up time explain that the gain of Restricted-RRond-Roofh is small compared to vanilla Round-Robin.
only differ slightly in the last time steps
Table I shows statistics about the average, standard deviation and maximum time taken by an agent to correctly identify its class. As expected, agents from class 0.8 identify their class much faster as the gaps with respect to other classes are larger. Table [ also reports the probbbibyyyl class estimation time Ca of
given by our thcoretical analysis (Theorem 1]. This theoretical value is rather close to the maximum value we observe: although these values are not directly comparable, suggests that analysis captures the correct order of magnitude.

---

Published in Transactions on Machine Learning Research (12/2022)
Algorithm
class 0.2
class 0.4
class 0.8
avg/std
max
avg/std
max
avg/std
max
Round-Robin (RR)
1378 194
2150
1382 191
2159
407 40
662
Restricted-RR
1376 = 211
2163
1379 + 210
2245
373 a 55
931
Theoretical Restricted-RR (Go)
3878
3878
1085
Table 1: Empirical class estimation times of Round-Robin and Restricted-RRR on the 3-class problem (Gaus- sian distributions with true means 0.2, 0.4, 0.8). We report the average, standard deviation and maximum across agents and runs. We also report the high-probabilliy class estimation time Sa given by our theory.
6.3 Mean Estimation
We now turn our main objective: mean estimation. The error of an agent at time is evaluated as the absolute difference of its mean estimate with its true mean:
error ll1 Mal.
(11)
Similar to above, we compute the average and standard deviation of this quantity across runs, and then for each time step we report in Figure [(b] the average of these quantities across all agents for the different algorithms (Soff-Restricted-Rouurr Round- Robin, Aggressive-Restriited Round-Robin Robin, Round-Robin, Oracle, and Local).
Eittricted-Rounde
As expected, all variants of ColME suffer from mean estimation bias in the early steps (due to op- timistic class estimation). However, the estimated class of each agent gets more procise (see Fig- ure [(a)] agents progressively eliminate this bias and eventually learn estimates with similar error and variance as the Oracle baseline. On the other hand, Local does not have estimation bias (hence achieves smaller error on average in carly rounds) but cxhibits much higher variance, and its average crror con- verges very slowly towards zero. These results show the ability of our collaborative algorithms to con- struct highly accurate mean estimates much faster than without collaboration. We can also see that Rideestriceed-Roun--Booo
converge much quicker low error estimates than Restricted-Rone Settricted-Round-RRee Round-Robii This shows that proposed heuristic weighting schemes success- fully reduce the relative weight given to agents that actually belong to different classes well before they are identified as such with sufficient confidence. The aggressive weighting scheme is observed to perform best in practice.
and
In the appendix, we plot the error in mean estimation for each class separately and observe that agents with mcan 0.8 (i.c., in the class that is casiest to discriminate from others) are the fastest to reach highly accurate estimates, followed by those with mean 0.4, and finally those with mean 0.2.
Finally, quantitatively compare the convergence time of different algorithms with empirical measure inspired by our thcoretical PAC criterion (Definition 1 We define the empirical convergence time of an agent as the earliest time step where the estimation error of the agent always slays lower than some e:
(cnva min(7 N: Vt r, error", s s).
(12)
We denote by conv(s) the average of the above quantity across all runs and all agents.
Table 2 reports the average, standard deviation and maximum empirical convergence time across agents and runs for two values of (we also provide per-class tables in the appendix). These values were chosen to reflect the two different regimes suggested by theoretical analysis. Indeed, recall that theory gives criterion to predict whether our collaborative algorithms will outperform the Local bascline: this is the case when the desired accuracy of the solution e is small enough for the given problem instance (see Eq. g For the problem considered here, Eq. (9) gives that Restricted- CettriiceddRound--hee Goond-Robin will outperform Local for all agents as soon as c smaller than 0.049. We thus choose c= 0.01 as the favorable regime (where we should beat Local) and e 0.1 as the unfavorable regime. We provide the corresponding high-probability mean istimation times Fa of Restricted Restricted-Round- Robin and Local given by our theoretical analysis (Theorem
10

---

Published in Transactions on Machine Learning Research (12/2022)
Algorithm
co1v(0.1)
conv(0.01)
avg/std
avg/std
max
Round-Rabin (RR)
417 230
1239
916 427
2088
Restricted-RR
405 +: 227
1175
894 à 438
1925
Noft-Restricted-Rt
340
608 290
1432
Aggressiv--Retticteed Restricted-Ral
56 39
340
335 127
958
Local
41 + 39
289
4494 3943
28616
Oracle
5
19
98 63
303
Theoretical Restricted-Rit (Ta)
3878
33406
Theoretical Local (Ta)
885
100216
Table 2: Empirical convergence times (see Eq. 12 of different. algorithms on the 3-class problem (Gaussian distributions with true means 0.2, 0.4, 0.8) for a target estimation error of e 0.1 (unfavorable regime) and 0.01 (favorable regime). We report the average, standard deviation and maximum across agents and runs. We also report the probabbobability mean estimation times Ta given by our theory for Restricted- Round-Robin and Local. In line with our theory, we see that our approach largely outperforms the local estimation baseline in the favorable regime and remains competitive in the unfavorable regime.
The results Table 2 are consistent with our theory. All variants of our algorithms largely outperform Local for e 0.01 f while Local is better for e = 0.1 as agents can reach this precision using only their own samples faster than they can reliably estimate their class. Overall, CestriittedRRoundd-e
Round-Robin performs and Aggressive Reseriiv---eerieeee-R-Roouu
marginally better than Round-Robin, while Robin significantly outperform Round-Robin and Restricted Round-Robin in both cases. Note that Soft- Restricted-RoundRRobne and unfavorable regime, and get very close to the performance of the Oracle baseline in the favorable regime. These results again show the relevance our collaborative algorithms and heuristic weighting schemes. We observe that our theoretical results get looser as + 0, which is somewhat expected.
perform roughly the same Local in the
7 Extension to Imperfect Classes
So far we have assumed that two agents are in the same class their personal distributions have exactly the mean, which be restrictive for some usc-cases. In this section, show that we extend the problem setup and our approach to the case where two agents are considered to be in the same cluss if their meons are close enough and agents seek to estimate the mean of their class.
Formally, we define a new notion of similarity class paramcterized by a radius n, which generalizes our previous notion introduced in Definition
Definition 7. Given vj > 0, the rsimillrrity class of agent a is given by:
Cr, = (1e ( [A]: AA. s snn
where Ae,1 |Ma pul is the gap between the means of agent and agent I.
This notion of "imperfect" similarity class allows to capture situations where clusters of agents have similar (but not necessarily equal) means. Such discrepancies between the means of agents the same class may for instance stem from the presence of local measurement. bias (e.g., due to local variations in the environment, see Taghavi et al. 2016). They can also be used to model groups of agents with similar preferences, behavior, goals, in applications like collaborative filtering (Su & Khoshgoftaar 2009b).
We had to run Local for much larger time horizon 30000 steps
converge accuracy 0.01.
11

---

Published in Transactions on Machine Learning Research (12/2022)
In this context, it is natural to slightly redefine the estimation objective. Instead of estimating its personal mean Ma considered so far, each agent aims to estimate the mean of its class:
Pna
Cy.ol leC
Σ nt-
(13)
For instance, in the presence of (centered) local measurement bias, estimating the class mean (instead of the local mean) allows to debias the estimate.
Remark 3 (Non-separated clusters). We do not formally require that the n-similarity classes form seporaled clusters, in the sense that for three distinct agents a, L. [A] we may have simultaneousty e Cn,as Cra and Cy,a + C.,.- This happens when Da, 1), A S 7) and n < A., S 2n. In this case, the "class" " of an agent simply corresponds to a ball of radius di around its mean, which potentially overlaps with others and thus violates the transitivity property of equivalence closses. For consistency with the rest of the paper and with slight abuse of terminology, we continue to the term "class". Although the case of seporated clusters appears more natural, we note that our proposed approach will still work in the non-seperated setting, in the sense that agents will correctly eslimale the mean of their class as defined in Eq. 13
Based on the above, we can adapt the notion of optimistic similarity class (Definition and the condition on the number of samples required for this optimistic class to coincide with the true class (Definition 6 by incorporating 17.
Definition 8. The noptimisstcc similarity class from the perspective of agent at time t is defined as:
C/ = [A]: (1) n).
Definition From the perspective of agent a and at time t, event Gy is defined as:
G =n Le|A]
nggt na.
(14)
| ( ' 1 [33 )
ff otherwise,
where
"
with An, Al A..t-
Lemma 3 (Class membership rule). Under EA a G and VI [A] and at time t: d² > n = le [A]]C
We can see from the above that ruling out an agent from the optimistic class Cr requires more samples for larger 7,, which is expected as the size of the confidence interval needs to be smaller to make this decision reliably.
With these tools in place, we can use our collaborative mean estimation algorithm CoIME (Algorithm presented before, with only minor modifications: we simply need replace the notion of optimistic similarity class by the vevessoo of Definition 8 and compute the estimate ph,n at time using simple class-unije saissrm weighting scheme d', = ب to match the objective in Eq. 13 We refer to this algorithm as CoMMEE. Note that 1) becomes parameter of the algorithm, allowing to choose the desired radius for the class structure.
We can now state the class and mcan estimation complexity of n-CoMME. The proofs can be found in the appendix.
Theorem 3 (n-ColME class estimation time complexity). For any ò (0,1), employing Restricted-Round Robin query strategy, we have:
P(31> > C. Chaa + Cn,a)) 5 5
with C = ny + A-1- Σ [e(A]CCn
(15)
12

---

Published in Transactions on Machine Learning Research (12/2022)
Theorem 4 (n-ColME mean estimation time complexity). Given the risk parameter 8, using the Restricted- Round-Robin query stralegy and closs-uniform weighting (while employing Cr,a), the mean estimator Ph of agent a is (e, -converggen,, that is:
8 1
P(VI> Th. Uno Mnal S sc) >
with Ta- ma, (c) (Cy
(16)
4'
The class estimation result (Theorem 3) similar to its "perfect" class counterpart (Theorem except that it involves n-dependent quantitics. The mean estimation result (Theorem 4 differs slightly more from the perfect class case (Theorem 2 because the estimation objective (see Eq. 13 and weighting scheme are different. But most importantly, we see that for large enough gaps or small enough precision (similar to Eq. 9 we again achieve an optimal speed since the time complexity of an oracle weighting baseline that would know the true classes beforchand is (c) + -C,,,al- -1.
8 Conclusion
We have presented collaborative online algorithms where each agent learns the set (class) of agents who shares the same (or similar) objective and uses this knowledge to speed up the estimation of its personalized mcan. We have provided PAC-style guarantecs for the class and mcan cstimation time complexity of our algorithms. In addition, we have introduced a number of sample weighting mechanisms lo decrease the bias of the estimates the early rounds of learning, whose benefits are illustrated empirically.
Our work initiates the study of online, collaborative and personalized estimation and lcarning problems, which we believe to be promising area for future work. We outline a few interesting directions below.
Optimistic vs conservative. Instead of the optimistic approach taken in this work, one could try to design a more conservative algorithm where an agent incorporates the estimate of another agent only when it knows (with sufficient probability) that it belongs to the same class. This would avoid introducing bias in the estimation in early steps. However, a downside of such an approach is that agents would typically need some knowledge of the gaps between their true means order to determine when another agent can be considered be in the same class, which would be a big practical limitation.
Large-scale variants. While a simple way to scale up our approach to a large mumber of agents is have each agent focus restricted subset of other agents (see Remark [ an interesting direction to allow more exploration in large-scale systems could rely the idea of peer sampling (Jelasity et al. 2007), i.e., randomly sampling a few agents from time to time to discover potential new members of the class beyond the initial subset.
Handling data drift. We would like to extend our approach to handle data drift, where the means of agents can change over time, Here, one could try to adapt ideas from non-stationary bandits, such as sliding- window UCB (Garivier & Moulines 2011 or UCB strategies mixed with change-point detection algorithmss (Cao et al. 2019).
Privacy guarantees. In use cases where data is considered sensitive (e.g., personal data), important provide strong privacy guarantees to the agents. While our approach only requires agents to share aggregate quantities (see also Remark 2), these may still leak sensitive information. In future work, would like to use tools from differential privacy (Dwork & Roth 2013), such as the tree aggregation technique for sharing cumulative sums in an online way (Dwork et al. 2010 Chan et al. 2011), to provide formal privacy guarantecs and analyze the resulting trade-offs between privacy and utility.
Extensions to personalized learning tasks. Finally, the problem could be extended to cases where each agent aims to solve a personalized machine learning task (Vanhacscbrouck et al., 2017) basod on the data it receives online. In that case, structure in the distribution conditioned by the outputs of the learned models can be inferred, introducing interesting exploration-eexploittiion dilemma in the learning task.
13

---

Published in Transactions on Machine Learning Research (12/2022)
Acknowledgments
The authors thank the reviewers for their insightful comments that allowed to improve the paper. This work was funded part by Métropole Européenne de Lille (MEL), Inria, Université de Lille, and the I-SITE CLNE through the Al chair Apprenf number 1PLLOTE-1--004APPPPP
References
Erwin Adi, Adnan Anwar, Zubair Baig, and Sherali Zeadally. Machine learning and data analytics for the iot. Neural Computing and Applications, 32(20):16205 16233, 2020.
Jean- Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. COLT, 2010.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-2566 2002.
Dimitri P Bertsekas and John N Tsitsiklis. Introduction probability, volume 1. Athena Scientific Belmont, MA, 2002.
Etienne Bounsier and Vianney Perchet. Sic mmab: Synchronisation involves communication in multiplayer multi-armed bandits. In NewrIPS, 2019.
Etienne Boursier, Emilie Kaufmann, Abbas Mehrabian, and Vianney Perchet. A practical algorithm for multiplayer bandits when arm means vary among players. In AISTATS, 2020.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procodure with change detection for piecewise-stationary bandit. In ICML, 2019.
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transac- tions on Information Systems Security, 14(3):1-26, 2011.
Gary Cheng, Karan Chadha, and John Duchi. Federated asymptotics: model to compare federated learning algorithms. aixiv preprint arXiv:2108.03311 2021.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trendso in Theoretienl Computer Science, 9(3-4)2211440) 407, 2013.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, 2010.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning: A meta-learning approach. In NewrIPS, 2020.
Aurélien Garivier and Eric Moulines, On upper-confidence bound policies for switching bandit problems. In ALT, 2011.
Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized lederated learning. In NewrIPS, 2020.
Eshcar Hillel, Zohar Shay Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In NIPS, 2013.
Márk Jelasity, Spyros Voulgaris, Rachid Guerraoui, AnnieMarie Kermarree, and Maarten Van Steen. Gossip- based peer sampling. ACM Transactions Computer Systems (TOCS), 25(3):8 es, 2007.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafacl G. D'Oliveira, Hu- bert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben
14

---

Published in Transactions on Machine Learning Research (12/2022)
Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksan- dra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Scbastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakommma, Jianyu Wang, Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ Machine Learning, 14(1 2):1 210, 2021.
Nikolai Karpov and Qin Zhang. Collaborative best arm identification with limited communication on non-iid data. arXiv preprint arXiv:207. 08015, 2022.
Tomáš Kocák and Aurôlien Garivier. Best arm identification in spectral bandits. In IJCAI, 2020.
Tomáš Kocák and Aurélien Garivier. Epsilon best arm identification in spectral bandits. In IJCAI, 2021.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision making in multi-agent multi-armed bandits. Automatica, 125:109445, 2021.
Udari Madhushani, Abhimanyu Dubey, Naomi Ehrich Leonard, and Alex Pentland. One more step towards reality: Cooperative bandits with imperfect communication. In NeurIPS, 2021.
Odalric-Ambrym Maillard. Mathematics of statistical sequential decision making. PhD thesis, Université de Lille, Sciences et Technologies, 2019.
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated Multi- Task Learning under a Mixture of Distributions. In NewrIPS, 2021.
David Martinez-Rubio, Varun Kanade, and Patrick Rebeschini. Decentralized cooperative stochastic bandits. In Proc. of NIPS, 2019.
Fernando Matco, Juan José Carrasco, Abderrahim Sellami, Mónica Millán-Giraled Manuel Domínguez, and Emilio Soria-Olivas. Machine learning methods to forecast temperature in buildings. Expert Systems with Applications, 4064):1061-106, 2013.
Clémence Réda, Sattar Vakili, and Emilie Kaufmann. Near-optimal collaborative learning in bandits. In NewrlPS, 2022.
Abishek Sankararaman, Ayalvadi Ganesh, and Sanjay Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM Measurement and Analysis of Computing Systems, 3(3):1-35, 2019.
Felix Sattler, Klaus-Robert Müller, and Wojciech Samek. Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. 1EEE Transactions on Neural Networks and Learning Systems, 2020.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In AAAI, 2021.
Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi-armed bandits with personalization. In AIS- TATS, 2021.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. Tn NIPS, 2017.
Xiaoyuan Su and Taghi M. Khoshgoftaar. A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009, 2009a.
Xiaoyuan Su and Taghi M. Khoshgoftaar. A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009b.
Ehsan Taghavi, Ratnasingham Tharmarasa, Thia Kirubarajan, Yaakov Bar-Shalom, and Michael McDon- ald. practical bias estimation algorithm for multisensor-multiian tracking. IEEE Transactions on Aerospace and Flectronic Systems, 52((1:2-119 19, 2016.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In FOCS, 2019.
Paul Vanhacsebrouck, Aurélien Bellet, and Mare Tommasi. Decentralized collaborative learning of person- alized models over networks. In Proc. of ATSTATS, 2017.
Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 4120-4129. PMLR, 2020a.
Yuanhao Wang, Jiachen Hu, Xiaoyu Chen, and Liwei Wang. Distributed bandit learning: Near-optimal regret with efficient communication. In ICLR, 2020b.
Larry Wasserman. All of statistics: concise course in statistical inference. Springer Science & Business Media, 2013.
16

---

Published in Transactions on Machine Learning Research (12/2022)
Appendix A Proof of Lemma 1
Lemma 4. Let Ita be the mean value of t independent real-valued random variables with the true mean Pa and is o-sub suub-gaussian. For all de (0, 1), holds:
P Na 2 oo
2 (1+
(1+ II(VE++(++100))) s
(17)
2 (1+ /
P( Ha - 14 2 2 ov
In((t+ s
(18)
Proof. The two inequalities are proved the same way as a direct consequence Maillard (2019) Lemma 2.7 therein. Let YI,...,Y, Y, be a sequence of independent real-valued random variables where for each t, Y, has mean ys and is Gaussiann then for all 8 e (0, 1), it holds that
e E N, ECr- m.)
of )) ()((t++11)) 58. 2 Σ
aml
When all random variables have the same mean Ma and variance o, we have
P( N, Σo,, - (V)- 2 V 2t 1) In( Vt+ 1/6)) s 88,
s=1
Taking the average rather than the sum, iee. dividing both sides by we obtain that:
P(3 N, Σ
Pa
2 - o2 + } In(Vt++ 1/8)) s6,
8=1
1 Y P(36EN,
Σ m=1
Ma 2
01 + In In(V++ so.
And denoting 14 Ex-1 Y, 2, conclude
P(3 N, Ho 2
20 ov / t
21+ In([t+ I/o)) s8
2 [1
Lemma 1. Let (0, a e [A]. Setting Bb(n) = ov 2 have:
x (1 /
In with <(0) 8x we
P(Ea) 21 1 8"
(5)
Proof. Let us recall that F.,
F 141 S Bo(n Then AeNie[A]
n
(FF.) = TP F.a):
- P(3t IN E1 [A]: 1 mil (o(n())))
2 Σ P(31 N 1o - pi Bo(r(a)))
[[[A]
defining 7()) = 8x4
and using Lemma 4
2
1 )n((
P(Ea) 21 Σ
P(3te 3t N: 1 - M1 o
(1+
1ln(/ni ni + 1/>(6)))
[e[A]
n
n
Σ 70)) - 1- Σ 8
2
[<]] [c[1]] 8A
8
17

---

Published in Transactions on Machine Learning Research (12/2022)
Appendix B Proof of Theorem 1
In this section, we prove Theorem We first show Lemma 2 using two technical lemmas. We then prove
Lemma 7
which combined with Lemma 2 yields the main result (Theorem I Let us first remark that
d2,((1) (1) = l - -Fa,l Bo (n(aaaa)) (n,
= 1 - (F u1) (Ha mi)l Bs(r)aa)) Ba(1)a))
As consequence have
(2)((1) An, 1 Mal | Mil Bs(n)aa) Br (n
(19) (20)
(2,6(1) Da,l | Hal 1=2a Mil Bs(n BB (naa.).
Lemma 5. Under Ea, v [A], if & Ca then Vnla 2 vhay 1/5 A we have d' d', (1) 0.
Proof. Under Eu, we have 1=', ull (s(n'a)) and 1/ Mal 3s(n Since n' n also have
(s(n",,) $ (s((2).). Hence, using (0). d' (') D..1 236 23 233 (n 2 Da, (m. If I C. then Aa,1 = and since (n(r)))) we cannot ensure that D 4,3g (n > 0. I & C. then to ensure that d2,,(1) 2 A.,I- - 43,(n',,) > O, we need that And (n(,),)) and hence ny [35 (1+
Lemma 6. Under Ea, [Ie[A], VtEN, N, if I E C. then (1) S.
Proof. Again, recall that under Ey we have 1 -11 $ Bo and F "aal 3a(m', Hence, using 19 d' (2)(()) Aat* Bo(n'aa) Bo(n'a)) Ba(ria,) Bo(n)a)) Daj- If C. then A 0 and thus d()(()) s 0.
j
We now prove Lemma 2 which we restate here for convenience.
Lemma (Class membership rule). Under Et A G and vl [A] and time t: d²
(1) >0 = le [A]
Proof. From Lemma 6 directly have one implication. For the other one, if & C. because G2 holds, we
have e [A], n'a 2 n therefore we can apply Lemma and we directly have (1) > 0.
]
Lemma 7. Under Eg, and using Restricted-RRundd Robin algorithm, Gt holds when > Sa where
Ca nag +
Σ L[AASC.
1 1 Tnt -14A)))
Proof. According to Algorithm 1 C. = [A] and agent is eliminated from set C₁ time & if d()(()) F'a,- - -h - ( (m O. According to Lemma the time required to eliminate agent from the class C. is least n If agent is queried at time ni, -1, then using Restricted- Gound-Robie (or round robin), we are sure that it will be removed from C, for all larger than ni, 1 A.
Let us consider h being an agent such that n max na.- By definition, D., min Ana and n can be denoted by niaa.
In the case of round robin, we are sure that G will be true when 2 nia A. But using Restricted- Hound-Robing since the loop ignores agents not in C have that G holds when t> Ça where
iI extremely rare cases, the expression 1, ( could be an integer and should add get a strict inequality. But conciseness of the expression, omit the the definition of na
18

---

Published in Transactions on Machine Learning Research (12/2022)
naj - A1+A-
Σ Je[A]sC,
Finally, we the above lemmas prove Theorem 1 which we restate below for convenience.
Theorem (ColME class estimation time complexily). For any e (0,1), employing Cettriited-Rouude Robin query strategy, we have:
P(3t> So C2 * Ca) s J 8'
with La = niaa + 1-11
Σ (nn +n2 [e[A]sC.
(7)
Proof. From Lemmal and Lemma we deduce that if Ea holds and knowing that C. (LE [A] :
d2 s s
then Vt> Sax C. Ch. Hence, P (vv Sa. C. C²) P(Ea) 1 6/8 using Lemma
7
Appendix C Proof of Theorem 2
In this scction we detail the proof of Theorem 2 about the PAC mcan estimation propertics of the ColME strategy. We restate the theorem below for convenience.
Theorem (CoLME mean estimation time complexity). Given the risk parameter 6, using the Restricted- Round-Robin query strategy and simple weighting, the mean estimator pla of agent is (e. 4) -cooverrgn,,,, that is:
[1) Ca.
Caa
PPVL> Ta: :p: Mal s > 4
with Ta max(Sas
(8)
2
Proof. Let assume that time have C₁ C.. Therefore
Eie, Faa ma Enc, n/a
Σ LeC.
Remark that Eiec, "h is the sum of all ni, samples received by all agents / in Ca. In other words, pá is the estimation of Pe with Eic, nh, examples. Hence in order to have 1A4 Mal e when Es holds, we should have ((Eec. n(,)) e. Let us see at what time denoted by ne,a we have [ (c)] Eec. nar With Roaeed-Rooddoooodo we know that when Ch = Ca, then only members of C, are
Algorithm 13 using queried. Therefore,
Callee. Cal- -
[ (c) = ne,a (ne.a 1) .... (Mr.a - |Cal + 11
CCal.
2
[3 (c) (c)
Call-
ne,a
Cal
2
As summary, if Eg holds, then we have Vt ne,as C² C. implics that |p4 - Hal s c. Now, following Theorem have PP3) Ea C. * Ca) & Since Ta max Ga, me,a) Ca, then IP (3t IM4 14. 6) s
S+PEE. E.
+
Appendix D Proof of Theorem 3
The proof of Theorem 3 follows the same step as that of Theorem I up to replacing the 0 threshold by n, We only state the intermediate lemmas (which are adaptations of Lemmas and omit the detailed proof.
Lemma 8. Under E., vle [A], if Ca.a then Anlaa 2 nh, (135 (Aag"") have d' d')(1)) n.
19

---

Published in Transactions on Machine Learning Research (12/2022)
Lemma 9. Under Ea, VI [A], VteN, if Cn,a then d'),(1) S
Lemma 10. Under Fag and using Restricted-Roundd algorithm, n. holds when > So where
= A+
Σ [e[A]sCni
Appendix E Proof of Theorem 4
In this section we detail the proof of Theorem about the PAC mean estimation properties of the 7>ColMEE. strategy. We restate the theorem below for convenience.
Theorem 4 (n-ColME mean estimation time complexity). Given the risk parometer 8, using the Restricted- Round-Robin query strategy and class- uniform weighting (while employing Cr,a), the mean estimator pa of agent is (e, -cooverrge,,, that is:
P(Vt> > To Iny, Mnal s $() >
with 7/ 15 + Spp.a-11)
(16)
4"
Proof. Since t> To Sd at time we have C2 Cn,a Therefore
Eiecn.
E o L'a IeC
Cynal
Remark that p is not equivalent to the average of all the samples of agents in Cr.a" it the average of the mean values for each agent in Cr,a- Therefore, although some agents may have more samples than the others, all are assigned uniform weights. We would like to have |n - - S e. When Eg holds, we can rewrite this
Whh Mnnal= = CCnall teC
Σ Je.s - Mil s (C IeCo.
Σ Foa - --11-
Therefore, we need:
Σ F Mel (Cy,alx..
JeCo.a
A sufficient condition for the above inequality to hold to ensure that each term is bounded by
Vl Cr. FT'. si
(21)
This is achicvod when (s(n")) < for all I Cr Since we are using Restricted-Rounde Robbn and also that Cy Caja; the number of samples required for each agent in Cr,a are n'. n" -1, n -2, ..... n - G +1
where we consider the one with the maximum number of observations to have index 1 for notation simplicity (which corresponds to index a). For Eq. 21 to hold, it is thus sufficient to have:
(r) ni.a -Cnmll +1
(c) |Cr,al - naaa
Therefore To max((2 37 (e)
+ 1
As a summary, if E, holds, then we have TH Ct C implies that |p -Mnm-My, Now, following The- we have PP3/ > Co Cr + Cn,a s 8. Since Ti = max(C2,n, n²aa) ) 2 CY, then IP33/ > Th IA Myaal > >e) s F.
orem
Appendix F Additional Experimental Results
In this section we provide additional illustrative results better understand different aspects of our ColME algorithm.
20

---

Published in Transactions on Machine Learning Research (12/2022)
0.40
0.40
soft-restricted--rnn wwwpiiteeedrrodd---ooo
soffrrestrited-ronnd---r
0.35
0.35
aggresskevreiiibbeeroonrd
restricted-roun
restricted rouudrrrbr
0.30
round robin
0.30
round raind-rabin
0.25
0.25
oracle
local
local
0.20
Error moon
0.20
0.15
0.10
0.10
0.00
500
1000
1500
2000
2500
0.00
500
1000
1500
2000
2500
Time
Time
(a) First class (mean 0.2)
(b) Second class (mean 0.4)
soft restricted round-roorrrr
0.35
aggressive restricted round-rabin
Crer mest esimalionn
0.30
round-rebin
restricted-round round-rrbin
0.25
oracle
0,20
0.15
0.10
0.85
200
(c) Third class (mean 0.8)
Figure 2: Error in mean estimation for the 3-class problem (Gaussian distributions with true means 0.2, 0.4, 0.8). Note that the time scale is different for the third class to show the relevant details more clearly.
F.1 Per-Class behavior on the 3-class problem
For the 3-class problem described in the main text, we provide complementary figures to show the error in mean estimation in each class separatedy. These plots are shown in Figure 2 We can see that the average class identification time (represented by yellow dots) is different for different classes. For instance, as the gap between the class with mean 0.8 and the other two larger, this class requires less samples Indeed, the average class identification time is less than 400 for that class (Figure [cc) while is about t= 1400 for the other two (Figures ((a) 2(b). Therefore, agents from the class with mean 0.8 reach highly accurate estimate much faster than agents from other classes
ident ified.
We also show the class estimation precision across each pair of classes in Figure 3 We see that classes 0.2 and 0.8, who have the biggest gap, are separated first (Figure 3(b)), then 0.4 and 0.8 (Figure 3(c) and finally 0.2 and 0.4 (Figure 3(a)].
Finally, for mean estimation, we provide the per-class counterparts Table 2 in Tables 5 In line with previous results class estimation, agents of class 0.8 are the that converge faster to the desired mean estimation accuracy. Interestingly, observe that for 0.1, agents of class 0.2 converge almost as fast those from class 0.8: this is because they do not need to eliminate all agents from class 0.4 to reach this accuracy. This illustrates how our approach can naturally adapt to the gaps and desired estimation accuracy.
F.2 Results on 2-class problem
We experiment with a 2-class problem generated the same way as the 3-class problem considered in the main text, except that the means are chosen among (0.2, 0.8}. This makes the problem casier since the gap between the two classes corresponds the largest gap in the 3-class problem. The results shown in Figure reflect this: agents correctly identify their class and reach highly accurate mean estimates much faster than
21

---

Published in Transactions on Machine Learning Research (12/2022)
Precition class antimatiin 200-4404
restiidtedraanddteiinn
round-robin
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
restricee--oundrrrbii
0.5
5.00
1000
1500
2000
2500
500
1000
1500
2000
2500
(a) Class estimation precision for 0.2 0.4
(b) Class estimation prccision for 0.2 0.8
3.0
extimationn
0.9
0.8
0.6
restricte--ound-nonn robin
2000
(c) Class estimation precision for 0.4 vs 0.8
Figure 3: Class estimation precision across time for each pair of classes on the 3-class problem.
Algorithm
conv(0.1)
conv(0.01)
avg/std
max
avg/std
max
Round-Robin (RR)
289 i 92
594
1207 a 170
1782
Restricted-RR
271 77
568
1194 177
1857
Soll-Restrricted-RRR
111 3:
239
761 a 173
1379
Aggressive Aggresiive-Rettritted-- Restricted-RR
74 40
215
382 + 95
830
Local
40
288
4548 + 4075
28616
Oracle
=
15
100 + 63
246
Theoretical Restricted-RR (Ta)
3878
33406
Theoretical Local (ra)
885
100216
Table 3: Empirical convergence times (sce Eq. 12 for class 0.2 of different algorithms on the 3-class problem (Gaussian distributions with true means 0.2, 0.4, 0.8) for target estimation error of e = 0.1 (unfavorable regime) and e = 0.01 (favorable regime). We report the average, standard deviation and maximum across agents and runs. We also report the high-probability mean estimation times Ta given by our theory for MeturicceedRouun-RRoollll and Local.
in the 3-class problem. Consequently, the improvement compared to Local is even more significant and our approach almost matches the performance of Oracle. We omit the per-class figures as they are essentially the same as Figure 4(b)
22

---

Published in Transactions on Machine Learning Research (12/2022)
Algorithm
cO1v(0.1)
conv(0.01)
avg/std
avg/std
Round-Robin (RR)
721 160
1239
1232 181
2088
Restricted-RR
708 158
1175
1216 + 183
1925
Soft-Restricted-RRR
31
+ 188
1432
Regressive-Restriitee--..
42
340
420 92
832
Local
41 + 39
277
4482 3846
26488
Oracle
19
99 70
303
Theoretical Restricted- -R (Ta)
3878
33406
Theoretical Local (7x)
885
100216
Table 4: Empirical convergence times (sce Eq. 12 for class 0.4 of different algorithms on the 3-class problem (Gaussian distributious with true means 0.2, 0.4, 0.8) for target estimation error of = 0.1 (unfavorable regime) and e 0.01 (favorable regime). We report the average, standard deviation and maximum across agents and runs. We also report the high-probability mean estimation times Ta given by our theory for Cestricted-Roud--RRe and Local.
Algorithm
cO1v((.1)
cOnv(0.01)
avg/std
avg/std
max
Round-Robin (RR)
271 35
401
379 + 38
538
Restricted-RR
266 1: 31.25
384
342 +: 38
526
Soft-Restricted--RR
100 36
232
280 +: 78
958
Aggressive-Resttricee--ttt
57 a 24
172
222 4: 90
958
Local
41 39
289
4434
3883
27470
Oracle
6
17
95 + 56
208
Theoretical Restricted-RR (Ta)
1085
33406
Theoretical Local (Ta)
885
100216
Table 5: Empirical convergence times (see Eq. 12 for class 0.8 of different algorithms on the 3-class problem (Gaussian distributions with true means 0.2, 0.4, 0.8) for target estimation error of 0.1 (unfavorable regime) and 0.01 (favorable regime). We report the average, standard deviation and maximum across agents and runs. We also report the high-probability mean estimation times Ta given by our theory for Roiieed--ond---eee and Local.
0.0280
1.0
restricted round cenriceed-rouddeeee rabin Found-robin
soft restricted round robin
werssswweresrrictee-oorree restrictedrounn-rodd
Preasion in catimation
0.9
Bror micin estimation
0.0150
round-robin
0.0125
oracle
local
0.0100
0.7
0.0075
0.6
0.0050
0.0025
0.5
100
200
300
400
500
0.0000
500
1000
1500
2000
2500
Time
Time
Class estimation precision all agents
(b) Error estimation all agents
Figure 4: Results for the 2-class problem (Gaussian distributions with true means 0.2 and 0.8).
23


Reviews:
[{"review_id": "5qNTPNgWv7", "reviewer": "Reviewer_2AwD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written especially for the algorithm and analysis sections. The algorithm idea is articulated clearly and the theoretical analysis looks good to me. However, there are some aspects that need more improvement such as the motivation of the problem, the comparison of the complexity with other methods, and the trade-off between the communication and time complexity.\n\nI am confused about the motivation of querying other agents’ estimates just in order to estimate the mean well. Since the goal of each agent $a$ is just to estimate the mean $\\mu_a$ of distribution $\\nu_a$, what is the benefit/motivation for agent a to query the mean of other agents? I might be missing something here. But the time complexity of the proposed method is not better than that of a single agent algorithm who just uses $O(1/\\epsilon^2)$ data to concentrate its empirical mean to the true mean up to an error $\\epsilon$.  \n\nIf the goal is to estimate the mean in a distributed way, then the authors should comment and discuss more about the communication complexity and memory complexity of the proposed algorithm. For example, the communication complexity seems to be linear in the iteration number since the algorithm requires to ask another agent’s estimation at every iteration. Is the memory complexity $|A|^2$? In this case, I do not see the benefit of such a collaborative algorithm compared with aggregating all the data for one agent on the same server, since the time complexity and the communication complexity are the same.\n\nAlthough based on a rough calculation it seems to me that the time complexity in Theorem 2 is in the order of $O(1/\\Delta_a^2+1/\\epsilon^2)$ plus additional terms, it would be much better if the authors can provide a more specific instance dependent result in the theorem or the discussion, which will makes it much easier to interpret and compare the result. \n\nThe theoretical analyses are based on the simple weight scheme. However, according to the experimental results, it seems that the performance of the algorithm with the simple weight scheme is significantly worse than the other two heuristic weighting schemes proposed just for the experiments. This discrepancy between the theory and the empirical results makes the conclusion unclear whether the proposed algorithm works in more complicated real-world applications. The authors might need to conduct more experiments on different problems and with ablation study to show when these different schemes work in practice.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the mean estimation problem in an online fashion where multiple agents with the same or different means could collaborate with each other to improve their own estimation by incorporating others’ information. The authors propose an algorithm where each agent can use other agents’ information in an optimistic way by estimating the confidence interval of their estimation. The agent will choose another agent to query in a round robin way or restricted round robin way (only choose agents that are estimated to have the same mean). The authors provide a time complexity analysis of their algorithm when using a simple weighting scheme to sum the information within one group with the same mean. They also conducted experiments to show the performance of the algorithm with respect to the time complexity. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think more discussion on the motivation of the multi-agent setting, detailed instance-dependent complexity, and comparison with other methods are necessary to fully evaluate the contribution of the submission. A more comprehensive experimental study on the different weighting schemes and the querying strategies proposed in this paper would improve and strengthen the work. ", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "a1RW4tUXjj", "reviewer": "Reviewer_v3Wz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. The problem of personalized learning and estimation is timely and highly relevant. While several approaches have been proposed in the literature and evaluated empirically, relatively little work has taken a more formal and rigorous approach as in this paper.\n2. The paper is generally well-written (although see below for some minor suggestions/typos). \n3. The theoretical results appear to be correct and verify the intuition of what one might hope for in the particular model considered.\n\n## Weaknesses\n1. The details of the particular problem formulation proposed are not well-motivated, and several aspects seem disconnected from practice.\n* The paper uses federated learning to motivate the problem setting. One key tenet of federated learning is to preserve the privacy of each individual agent's data. The proposed setting and methods involve agents sharing their observations directly with other agents, which directly violates this tenet.\n* In the proposed formulation, each agent may request the data of only one other agent at each round. This assumption pins a particular communication-computation tradeoff (one observation = one communication). In distributed/decentralized estimation problems it is often useful to parameterize the formulation in such a way that one can explore different tradeoff regimes (e.g., if communication is either much more costly or much less costly than gathering new observations).\n\n\n2. The proposed approach is not scalable for several reasons. Primarily, it is assumed that the amount of memory at each agent is proportional to the total number of agents $A$. This is impractical in most large-scale systems.\n\nI don't think that either of the above are fatal weaknesses, given that this is an area which has not been widely studied and that the paper contains many useful insights. But it is worth acknowledging and discussing these, along with ways they might be addressed in future work.\n\n3. The experimental evaluation illustrates some of the ideas from the paper, but it could be improved. In my view the main contributions of the paper are the problem formulation, proposed approaches, and theoretical guarantees. The experiments should then serve to validate the theory. While the experiments illustrate trends that the theory suggests, they don't actually include a curve for each of the bounds provided in Theorems 1 and 2. It would be useful to include these to get a sense of how loose/tight the theory is. Since no theoretical guarantees are provided for the soft and aggressive heuristics, experiments could also be used to better illustrate their behavior. However, the current experiments focus on one particular setting (3 agents, with only one specific choice of means; and a two-agent example in the appendix), so they do not help identify extremes or edge cases, to understand if or when the heuristics may fail (gracefully, or not), or if they have any limitations. Also, there are no experiments provided for the more interesting/relevant setting of non-separated classes considered in Section 7.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of online collaborative personalized mean estimation, motivated federated learning systems. A particular problem formulation is considered where, at each round, each agent receives one random observation of the random variable centered at the parameter they wish to estimate, and they may also query the running-estimate mean of one other agent. A few strategies are studied, including round-robin and restricted round-robin for determining which other agent to query next, and three possibilities for how to aggregate and fuse information from other agents with the local observations to ultimately form an estimate of the mean of each agent. Theory is provided for two cases, one where agents are partitioned into equivalence classes and those agents within the same class have exactly the same mean, and a more relaxed case where agents simply aim to fuse their observations with those of other agents whose means are similar enough to their own. Experiments are also provided to illustrate the theory for the first case.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. The prior work of [Cheng et al. (2021)](https://arxiv.org/abs/2108.07313v3) also aims to formalize a related personalization problem, including characterizing bias-variance tradeoffs. While the formulation is certainly different, it would be good to cite and discuss the relationship to this work.\n\n2. In cross-device federated learning, typically agents (devices) communicate with a server, rather than communicating directly with each other, since device availability is sporadic. Could the proposed formulation and methods be adapted to this setting in a natural way? This could also be discussed as a possible direction for future work.\n\n3. This is not necessarily a requested change, but I find it surprising that round-robin and restricted round-robin perform so similarly in Figure 1. Is this expected? Wouldn't one expect restricted round-robin to be much better than round-robin? Please discuss.\n\n4. Section 6.2 currently states that\n> We can see that the classes 0.2 and 0.8 are separated very early, quickly followed by 0.4 and 0.8 and finally, after sufficiently many samples have been collected, the pair with the smallest gap (0.4 and 0.2).\n\nAlthough we can see points where precision increases, there is no evidence in Fig 1(a) to directly support the claims about which classes are being separated (even though the statement does align with what one would intuitively expect). Can additional evidence be provided to support the claim?\n\n5. For finite $A$, in the limit as $\\eta \\rightarrow 0$, the results in Section 7 should reduce to those in Section 5. Is that correct? It's not obvious to me that Theorem 4 reduces to that of Theorem 2, however (in particular, when there are two or more agents with exactly the same mean). Please discuss.\n\n6. By adopting the approach of optimism in the face of uncertainty, the results in the paper depend on first exactly estimating the equivalence class. In this case, the improvement in terms of $|\\mathcal{C}_a|$ is evident. In practice, if agent $a$ can carefully rule out those agents which are not in its equivalence class, so that $\\mathcal{C}_a^t$ is strictly a subset of $\\mathcal{C}_a$, then couldn't it still expect some improvement in its mean estimate, albeit not the greatest reduction in variance achievable? It would be nice to see some further discussion of this tradeoff, in particular, with an eye towards the large-scale setting, where one might hope to form accurate estimates without needing to communicate with every other agent in the system.\n\n7. Although the writing is clear for the most part, there are some parts of the paper that are awkward to read. The first sentence of the introduction is one example, where \"wide spreading\" should probably be \"widespread\" and \"pregnant\" seems unlikely to be the word that was intended here (maybe \"pressing\" or \"urgent\"?).", "broader_impact_concerns": "None noted.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BGyymutnXZ", "reviewer": "Reviewer_VN18", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths ###\n- Personalized mean estimation is a problem that sees increasing interest in the ML community. This paper studies a version of this problem.\n- The authors consider and compare empirically several policies to instantiate their framework, which collects local mean estimates over time and each round’s estimate is their weighted average.\n- The proofs seem to be correct and complete.\n\n### Weaknesses: ###\n- I find the use of the online setting here a bit odd. There is no notion of regret — the error that is being optimized is the absolute distance between the estimate of a given user and their true mean. The number of rounds in the analysis is only used as a proxy to the number of samples that the users have drawn. As long as the number of samples is high enough, their local estimates are accurate enough so that we can distinguish who is in the same class and use everyone’s samples for the final estimate. So it confused me that the problem is presented as an online learning problem with the updates being restricted to follow this pattern. I don’t particularly object to this version of the problem, but my concern is that if we remove the constraint that each user receives one sample at a time and they are allowed to query one other user at a time, then there are a lot of other settings and works to compare to. For example, if we are interested in personalized mean estimation in the centralized setting (everyone pools their data together) there are several works in the multitask learning literature to consider. Other work that seems relevant is in distributed clustering (with communication constraints even). I think it is fine to say that these are not related because the problem in this specific online form, but then I would expect the setting to be more motivated.\n- The techniques are very similar to general bandits where convergence depends on the confidence intervals and their overlap. This is a minor comment however, since a highly valuable technical contribution is not necessary.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes collaborative algorithms for personalized mean estimation in the online setting. Specifically, each user draws samples from a subgaussian distribution with the same parameter but potentially different means and aims to estimate their mean using data from their distribution but also leveraging data from other users who have the same (or close) mean. In each round, each user draws a sample from their distribution to update their local mean estimate, and then are allowed to query one user (to be chosen according to some policy) for their current local mean estimate and store it. Each user’s estimate for the round is a weighted average of their local mean and the local means of other users that they have queried in the past rounds. This paper explores two policies for choosing which user to query in each round and several policies for choosing the weighting scheme for the mean estimate of the round. \n\nThe paper provides a theoretical analysis for a certain choice of policies, which shows that for a given user, after a number of rounds that roughly corresponds to the number of samples required to distinguish between the user’s distribution from the one with the closest mean,  the user has a good estimate of their mean with high probability and they have identified the users that belong in the same class (i.e., share the same mean). This number of rounds, under some natural parameter regimes, is smaller than the time it would take for the user to estimate their mean on their own, by roughly the size of the class they belong to.\n\nAn extension of this result to relax the assumption of users from the same class sharing exactly the same mean is included. Finally, the paper shows empirically how these policies perform for simulated data.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The following is not crucial for my recommendation, but I would suggest motivating the setting more or adding a longer comparison with other settings of collaborative learning and distributed clustering. I actually think that phrasing the problem in terms of sample complexity and not convergence time might make the contributions easier to understand, but as I mentioned, motivating the online view might be equally satisfying.\n\nA small typo in page 7: “identity the class”->identify the class", "broader_impact_concerns": "This work does not have obvious ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of online collaborative personalized mean estimation. The problem formulation considered here is that at each round, each agent receives one random observation of the parameter they wish to estimate, and can also query the running-estimate mean of one other agent. The paper studies different strategies including round-robin and restricted round-robin for determining which other agent to query next, and three possibilities for how to aggregate and fuse information from other agents with the local observations to ultimately form an estimate of the mean of each agent. 

Overall the relevance of the problem studied by the paper was appreciated by the reviewers. The paper's results were deemed to be correct, accurate and useful by the reviewers. The reviewers' requests were also incorporated by the authors. Overall I am happy recommending an accept which was the unanimous recommendation by the reviewers. 

Decision: Accept (poster)