Mahsa Asadi

Aurélien Bellet
email: aurelien.bellet@inria.fr

Maillard

Marc Tommasi
email: marc.tommasi@inria.fr

Collaborative Algorithms for Online Personalized Mean Estimation

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.

Introduction

With the widespread of personal digital devices, ubiquitous computing and IoT (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 be transmitted. Therefore, it is often preferable to keep the data on-device, where it has been collected. Local processing on a single device is a always possible option but learning in isolation suffers from slow convergence time when data arrives slowly. In that case, collaborative strategies can be investigated in order to increase statistical power and accelerate learning. In recent years, such collaborative approaches have been broadly referred to as federated learning [START_REF] Peter Kairouz | Advances and open problems in federated learning[END_REF].

The data collected at each device reflects the specific usage, production patterns and objective of the associated agent. Therefore, we must solve a set of personalized tasks over heterogeneous data distributions. Even though the tasks are personalized, collaboration can play a significant role in reducing the time complexity and accelerating learning in presence of agents who share similar objectives. An important building block to design collaborative algorithms is then to identify agents acquiring data from the same (or similar) distribution. This is particularly difficult to do in an online setting, in which data becomes available sequentially over time.

1

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 σ-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 a relaxed assumption where the means of agents in a class are close (but not necessarily equal). Such assumptions are natural in many real-world applications [START_REF] Adi | Machine learning and data analytics for the iot[END_REF]. A simple example is that of in different environments, monitoring parameters such as temperature in order to accurately estimate their mean (see for instance [START_REF] Mateo | Machine learning methods to forecast temperature in buildings[END_REF]. 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 to the desired accuracy. Our results highlight the dependence on the gaps between the true means of agents in different classes, and show that in some settings our approach achieves nearly the same time complexity as an 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 paper is organized as follows. Section 2 discusses the related work on federated learning and collaborative online learning. In Section 3, we formally describe the problem setting and introduce relevant notations. In Section 4, we introduce our algorithm and its variants. Section 5 presents our theoretical analysis of the proposed algorithm in terms of class and mean estimation time complexity. Section 6 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 8.

Related Work

Over the last few years, collaborative estimation and learning problems involving several agents with local datasets have been extensively investigated under the broad term of Federated Learning (FL) [START_REF] Peter Kairouz | Advances and open problems in federated learning[END_REF]. While traditional FL algorithms learn a global estimate for all agents, more personalized approaches have recently attracted a lot of interest (see for instance [START_REF] Vanhaesebrouck | Decentralized collaborative learning of personalized models over networks[END_REF][START_REF] Smith | Federated multi-task learning[END_REF][START_REF] Fallah | Personalized federated learning: A meta-learning approach[END_REF][START_REF] Sattler | Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints[END_REF][START_REF] Hanzely | Lower bounds and optimal algorithms for personalized federated learning[END_REF]Marfoq et al., 2021, and references therein). With the exception of recent work on simple linear regression settings [START_REF] Cheng | Federated asymptotics: a model to compare federated learning algorithms[END_REF], 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 setting 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 a single MAB instance which is solved collaboratively by multiple agents. Collaboration between agents can be implemented through broadcast messages to all agents [START_REF] Hillel | Distributed exploration in multi-armed bandits[END_REF][START_REF] Tao | Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits[END_REF], via a server (Wang et al., 2020b), or relying only on local message exchanges over a network graph [START_REF] Sankararaman | Social learning in multi agent multi armed bandits[END_REF][START_REF] Martínez-Rubio | Decentralized cooperative stochastic bandits[END_REF]Wang et al., 2020a;[START_REF] Peter Landgren | Distributed cooperative decision making in multi-agent multi-armed bandits[END_REF][START_REF] Madhushani | One more step towards reality: Cooperative bandits with imperfect communication[END_REF]. Other approaches do not allow explicit communication but instead consider a collision model where agents receive no reward if several agents pull the same arm [START_REF] Boursier | Sic -mmab: Synchronisation involves communication in multiplayer multi-armed bandits[END_REF]Wang et al., 2020a). In any case, all agents aim at solving the same task. Some recent work considered collaborative MAB settings where the arm means vary across agents. Extending their previous work [START_REF] Boursier | Sic -mmab: Synchronisation involves communication in multiplayer multi-armed bandits[END_REF], [START_REF] Boursier | A practical algorithm for multiplayer bandits when arm means vary among players[END_REF] 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 of each 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, [START_REF] Karpov | Collaborative best arm identification with limited communication on non-iid data[END_REF] extend the work of [START_REF] Tao | Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits[END_REF] by considering different local arm means for each agent with the goal to identify the arm with largest aggregated mean. Shi et al. (2021) introduce a limited amount of personalization by extending the model of Shi & Shen (2021) to optimize a mixture between the global and local MAB objectives. [START_REF] Réda | Near-optimal collaborative learning in bandits[END_REF] 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 is to identify a graph structure on top of the arms in MAB. [START_REF] Kocák | Best arm identification in spectral bandits[END_REF]2021) construct a similarity graph while solving the best arm identification problem, but consider only a single agent. In contrast, our work considers a multi-agent setting with personalized estimation tasks, and our approach discovers similarities across agents' tasks in an online manner.

Problem Setting

We consider a mean estimation problem involving A agents. The goal of each agent a ∈ [A] = {1, 2, . . . , A} is to estimate the mean µ a of a personal distribution ν a over R. In this work, we assume that there exists σ ≥ 0 such that each ν a is σ-sub-Gaussian, i.e.:

∀λ ∈ R, log E x∼νa exp(λ(x -µ a )) ≤ 1 2 λ 2 σ 2 .
This classical assumption captures a property of strong tail decay, and includes in particular Gaussian distributions (in that case, the smallest possible σ 2 corresponds to the variance) as well as any distribution supported on a bounded interval (e.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 a new sample and query another agent at each time step.

Formally, we assume that time is synchronized between agents and at each time step t, each agent a receives a new sample x t a from its personal distribution ν a with mean µ a , which is used to update its local mean estimate xt a,a = 1 t ∑ t t ′ =1 x t ′ a . It also chooses another agent l to query. As a response from querying agent l, agent a receives the local average xt l,l of agent l (i.e., the average of t independent samples from the personal distribution ν l ) and stores it in its memory xt a,l along with the corresponding number of samples n t a,l = t. Each agent a thus keeps a memory [(x t a,1 , n t a,1 ), . . . , (x t a,A , n t a,A )] 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 µ t a of µ a at each time t. Our goal is to design a query and estimation procedure for each agent.

As described above, note that when an agent queries another agent at time t, it does not receive one sample from this agent (as e.g. in multi-armed bandits), but receives the full statistics of observations of this agent up to time t. This is considerably much more information than in typical MAB settings, and naturally requires specific strategies.

The goal of each 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, see [START_REF] Audibert | Best arm identification in multi-armed bandits[END_REF]. Formally, we will measure the performance of an algorithm using the notion of (ϵ, δ)-convergence in probability [START_REF] Dimitri | Introduction to probability[END_REF][START_REF] Wasserman | All of statistics: a concise course in statistical inference[END_REF], which we recall below.

Definition 1 (PAC-convergence). An estimation procedure for agent a is called (ϵ, δ)-convergent if there exists τ a ∈ N such that the probability that the mean estimator µ t a of agent a is ϵ-distant from the true mean for any time t > τ a is at least 1 -δ:

P(∀t > τ a ∶ |µ t a -µ a | ≤ ϵ) > 1 -δ. ( 1
)
While it is easy to design (ϵ, δ)-convergent 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 taking advantage of the relation between the agents' distributions. This will allow them to build up more accurate estimations in less time, i.e., with smaller time complexity τ a .

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.1 In real scenarios, these classes may represent sensors in the same environment, objects with the same technical characteristics, users with the same behavior, etc. This assumption makes it possible for an agent to design strategies to identify other agents in the same class and to use their estimates in 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 a is given by:

C a = {l ∈ [A] ∶ ∆ a,l = 0},
where ∆ a,l = |µ a -µ l | is the gap between the means of agent a and agent l.

The gaps {∆ a,l } a,l∈ [A] define the problem structure. We consider that the agents do not know the means, the gaps, or even the number of underlying classes. Hence the classes {C a } a∈ [A] 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 a restricted subset of agents of reasonable size. This subset could be picked uniformly at random, be composed of neighboring nodes in 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).

Proposed Approach

In this section, we first introduce some of the key technical components used in our approach, and then present our proposed algorithm.

Main Concepts

In our approach, each agent a computes confidence intervals I a,l = [x t a,l -β δ (n t a,l ), xt a,l + β δ (n t a,l )] for the mean estimators [x t a,1 , . . . , xt a,A ] that it holds in memory at time t. The generic confidence bound β δ (n t a,l ) takes as input the number of samples n t a,l seen for agent l at time t, and δ corresponds to the risk parameter so that with probability at least 1 -δ the true mean µ l falls within the confidence interval I a,l .

Agent a will use these confidence intervals to assess whether another agent l belongs to the class C a through the evaluation of an optimistic distance defined below.

Definition 3 (Optimistic distance). The optimistic distance with agent l from the perspective of agent a is defined as:

d t a,δ (l) = |x t a,a -xt a,l | -β δ (n t a,a ) -β δ (n t a,l ). (2)
The "optimistic" terminology is justified by the fact that d t a,δ (l) is, with high probability, a lower bound on the distance between the true means µ a and µ l of distributions ν a and ν l . Recall that two agents belong to the same class if the distance of their true mean is zero. Since these values are unknown, the idea of the Algorithm 1 ColME Parameters: agent a, time horizon H, risk δ, weighting scheme α, and query strategy choose_agent ∀l ∈

[A]: x0 a,l ← 0, n 0 a,l ← 0 C 0 a ← {l ∈ [A] ∶ d t a,δ (l) ≤ 0} = [A] for t = 1, . . . , H do ∀l ∈ [A]: xt a,l ← xt-1 a,l , n t a,l ← n t-1 a,l Perceive: Receive sample x t a ∼ ν a xt a,a ← xt-1 a,a × t-1 t + x t a × 1 t , n t a,a ← t Query: C t a ← {l ∈ [A] ∶ d t a,δ (l) ≤ 0} Query agent l = choose_agent(C t a ) to get xt l,l xt a,l ← xt l,l , n t a,l ← t Estimate: C t a ← {l ∈ [A] ∶ d t a,δ (l) ≤ 0} µ t a ← ∑ l∈C t a α t a,l × xt a,l
end for Output: µ H a above heuristic is to provide a proxy based on observed data and high probability confidence bounds. In particular, we will adopt the Optimism in Face of Uncertainty Principle (OFU) (see [START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF] 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 a at time t is defined as:

C t a = {l ∈ [A] ∶ d t a,δ (l) ≤ 0}.
Having introduced the above concepts, we can now present our algorithm.

Algorithm

The collaborative mean estimation algorithm we propose, called ColME, is given in Algorithm 1 (taking the perspective of agent a). For conciseness, we consider that β δ (0) = +∞. At each step t, agent a performs three main steps.

In the Perceive step, the agent receives a 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 to select another agent l 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 one in a fixed order.

• Restricted-Round-Robin: like round-robin but ignores agents that are not in the set of optimistically similar agents C t a .

The focus on round-robin-style strategies is justified by the information structure of our problem setting, which is very different from classic bandits. Indeed, querying an agent at time t produces an estimate computed on the t observations collected by this agent so far. The choice of variant (Round-Robin or Restricted-Round-Robin) will affect the class identification time complexity, as we shall discuss later.

Finally, in the Estimate step, agent a computes the optimistic similarity class C t a based on available information, and constructs its mean estimate as a weighted aggregation of the local averages of agents that belong to C t a . We propose different weighting mechanisms:

Simple weighting. This is a natural weighting mechanism for aggregating samples:

α t a,l = n t a,l ∑ l∈C t a n t a,l .
Soft weighting. This is a 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:

α t a,l = n t a,l |I a,a ∩ I a,l | |I a,a ∪ I a,l | × 1 Z soft ,
where

Z soft = ∑ i∈C t a n t a,i |Ia,a∪Ia,i| |Ia,a∩Ia,i|
is a normalization factor.

Aggressive weighting. This is an extension of the previous soft weighting mechanism that is more selective. Not only does it consider the overlap and intersection of the agents' confidence intervals, but it also requires the size of the intersection to be larger than half the size of both confidence intervals from the two agents. Let us denote the binary value associated with this condition by E a,l = 1 {|Ia,a∩I a,l |>min{β δ (n t a,l ),β δ (n t a,a )}} . Then

α t a,l = n t a,l |I a,a ∩ I a,l | |I a,a ∪ I a,l | × E a,l Z agg ,
where

Z agg = ∑ i∈C t a n t a,i |Ia,a∪Ia,i|×Ea,i |Ia,a∩Ia,i|
is a normalization factor.

Baselines

We introduce two baselines that will be used to put the performance of our approach into perspective, both theoretically and empirically.

Local estimation. Estimates are computed without any collaboration, using only samples received from the agent's own distribution, i.e. µ t a = xt a,a .

Oracle weighting. The agent knows the true class C a via an oracle and uses the simple weighting α t a,l =

n t a,l ∑ l∈Ca n t a,l
.

Theoretical Analysis

In this section, we provide a theoretical analysis of our algorithm ColME for the query strategy Restricted-Round-Robin and the simple weighting scheme. 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 is 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 a about agent l to contain the true mean µ l for all l ∈ A.

Definition 5. We define the following events:

E t a = ⋂ l∈[A] |x t a,l -µ l | ≤ β δ (n t a,l ), (3)
E a = ⋂ t∈N E t a . ( 4
)
We can guarantee that E a holds with high probability via an appropriate parameterization of confidence intervals. We use the so-called Laplace method [START_REF] Maillard | Mathematics of statistical sequential decision making[END_REF].

Lemma 1. Let δ ∈ (0, 1), a ∈ [A]. Setting β δ (n) = σ √ 2 1 n × (1 + 1 n ) ln( √ n + 1/γ(δ)) with γ(δ) = δ 8×A , we have: P(E a ) ≥ 1 - δ 8 . ( 5
)
The second condition is that agent's a memory about the local estimates of other agents should contain enough samples. Let us denote by ⌈β -1 δ (x)⌉ the smallest integer n such that x > β δ (n). Definition 6. From the perspective of agent a and at time t, event G t a is defined as:

G t a = ⋂ l∈[A] n t a,l > n ⋆ a,l , ( 6
)
where n ⋆ a,l = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ ⌈β -1 δ ( ∆ a,l 4 )⌉ if l ∉ C a , ⌈β -1 δ ( ∆a 4 )⌉ otherwise, with ∆ a = min l∈[A]/Ca ∆ a,l .
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 t a,δ (l) ≤ 0 indicates the membership of l in C a . Lemma 2 (Class membership rule). Under E t a ∧ G t a and ∀l ∈ [A] and at time t: d t a,δ (l) > 0 ⇐⇒ l ∈ [A]/C a .
Using the above lemma, we obtain the following result for the time complexity of class estimation.

Theorem 1 (ColME class estimation time complexity). For any δ ∈ (0, 1), employing Restricted-Round-Robin query strategy, we have:

P(∃t > ζ a ∶ C t a ≠ C a ) ≤ δ 8 , with ζ a = n ⋆ a,a + A -1 -∑ l∈[A]∖Ca 1 {n ⋆ a,a >n ⋆ a,l +A-1} . ( 7
)
The dominating term in the class estimation time complexity ζ a for agent a is equal to the number n ⋆ a,a of samples required to distinguish agent a from the one who has smallest nonzero gap ∆ a to a, which is of order Õ(1/∆2 a ). 2 There is then an additional term of A -1 since all others agents that are not in C a could require the same number of samples. Finally, the last term in (7) accounts for agents that require less samples and had thus been eliminated before, which reflects the gain of using Restricted-Round-Robin query strategy over Round-Robin. When we have enough samples (at least ζ a ), Theorem 1 guarantees that we correctly learn the class (C a = C t a ) with high probability. We build upon this result to quantify the mean estimation time complexity of our approach.

Theorem 2 (ColME mean estimation time complexity). Given the risk parameter δ, using the Restricted-Round-Robin query strategy and simple weighting, the mean estimator µ t a of agent a is (ϵ, δ 4 )-convergent, that is:

P(∀t > τ a ∶ |µ t a -µ a | ≤ ϵ) > 1 - δ 4 , with τ a = max(ζ a , ⌈β -1 δ (ϵ)⌉ |C a | + |C a | -1 2 ). (8)
Several comments are in order. First, recall that collaboration induces a 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 ⌈β -1 δ (ϵ)⌉ = Õ(1/ϵ 2 ). Inspecting (8), we see that our approach has a time complexity of Õ(max{1/∆ 2 a , 1/ϵ 2 |C a |}). In other words, it is faster than local estimation as long as the time ζ a needed to correctly identify the class C a is smaller than ⌈β -1 δ (ϵ)⌉, that is precisely when:

ϵ < β δ (n ⋆ a,a + A -1 - ∑ l∈[A]/{Ca} 1 {n ⋆ a,a >n ⋆ a,l +A-1} ). (9)
This condition, which roughly amounts to ϵ < ∆ a , relates the desired precision of the solution ϵ to the problem structure captured by the gaps {∆ a,l } l∈ [A] between the true means through {n ⋆ a,l } l∈ [A] (see Definition 6). We will see in our experiments that our theory predicts quite well whether an agent empirically benefits from collaboration.

Remarkably, our approach can be up to |C a | times faster than local estimation: this happens roughly when ϵ < ∆ a / √ |C a |, i.e., for large enough gaps or small enough ϵ. 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

⌈β -1 δ (ϵ)⌉ |Ca| + |Ca|-1 2 = Õ(1/ϵ 2 |C a |)
, just like our approach. Note that in a full information setting where agent a would know C a 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

⌈β -1 δ (ϵ)⌉
|Ca| . Remark 2 (Frequency of communication). For simplicity, we consider that agents communicate each time they collect a new sample, which is standard in the literature of collaborative learning (see for instance the collaborative MAB approaches discussed in Section 2). However, different trade-offs between communication and data collection can be considered. In particular, it is straightforward to adapt the setting and our results to the case where each agent collects m samples between each communication: it amounts to multiplying by m the number of observations in our confidence intervals and empirical estimates. This provides a way to reduce communication, as well as to mitigate 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 communication is random and/or varies across agents are left for future work.

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.3

Experimental Setting

We consider A = 200 agents, a time horizon of 2500 steps and a risk parameter δ = 0.001. The personal distributions of agents are all Gaussian with variance σ 2 = 0.25 and belong to one of 3 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 on this 3-class problem, in the appendix we provide additional results on a 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 Round-Robin and Restricted-Round-Robin with simple weighting, and also evaluate the use of soft and aggressive weighting schemes in the Restricted-Round-Robin case. This gives 4 variants of our algorithm: Round-Robin, Restricted-Round-Robin, Soft-Restricted-Round-Robin and Aggressive-Restricted-Round-Robin.

Regarding competing approaches, we recall that our setting is novel and we are not aware of existing algorithms addressing the same problem. We can however compare against two baseline strategies. The Local baseline corresponds to the case of no collaboration. On the other hand, the Oracle baseline represents an upper bound on the achievable performance by any collaborative algorithm as it is given as input the true class membership of each agent and thus does not need to perform class estimation. Table 1: Empirical class estimation times of Round-Robin and Restricted-RR on the 3-class problem (Gaussian 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-probability class estimation time ζ a given by our theory.

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.

Class Estimation

We start by investigating the performance in class estimation. In this experiment, only Round-Robin and Restricted-Round-Robin are shown since the different weighting schemes have no effect on class estimation.

We first look at how well an agent a estimates its true class C a with its heuristic class C t a across time. To measure this, we consider the precision at time t computed as follows:

precision C t a = |C t a ∩ C a | |C t a | . ( 10
)
We compute the average and standard deviation of (10) across runs, and then average these over all agents. Figure 1(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-Robin and Restricted-Round-Robin only differ slightly in the last time steps before classes are identified. This is in line with Theorem 1, which shows that class estimation time mainly depends on n ⋆ a,a , the time needed to eliminate the agent with smallest nonzero gap. This dominant term and the fact that querying an agent at time t yields the full statistics of observations of this agent up to time t explain that the gain of Restricted-Round-Robin is small compared to vanilla Round-Robin.

Table 1 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 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 ϵ = 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 τ a 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.

with respect to other classes are larger. Table 1 also reports the high-probability class estimation time ζ a of Restricted-Round-Robin given by our theoretical analysis (Theorem 1). This theoretical value is rather close to the maximum value we observe: although these values are not directly comparable, it suggests that our analysis captures the correct order of magnitude.

Mean Estimation

We now turn to our main objective: mean estimation. The error of an agent a at time t is evaluated as the absolute difference of its mean estimate with its true mean:

error t a = |µ t a -µ a |. ( 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 1(b) the average of these quantities across all agents for the different algorithms (Soft-Restricted-Round-Robin, Aggressive-Restricted-Round-Robin, Restricted-Round-Robin, Round-Robin, Oracle, and Local).

As expected, all variants of ColME suffer from mean estimation bias in the early steps (due to optimistic class estimation). However, as the estimated class of each agent gets more precise (see Figure 1(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 early rounds) but exhibits much higher variance, and its average error converges very slowly towards zero. These results show the ability of our collaborative algorithms to construct highly accurate mean estimates much faster than without collaboration. We can also see that Soft-Restricted-Round-Robin and Aggressive-Restricted-Round-Robin converge much quicker to low error estimates than Restricted-Round-Robin. This shows that our proposed heuristic weighting schemes successfully 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.

In the appendix, we plot the error in mean estimation for each class separately and observe that agents with mean 0.8 (i.e., in the class that is easiest 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, we quantitatively compare the convergence time of different algorithms with an empirical measure inspired by our theoretical 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 stays lower than some ϵ:

conv a (ϵ) = min{τ ∈ N ∶ ∀t ≥ τ, error t a ≤ ϵ}. ( 12
)
We denote by conv(ϵ) 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 our theoretical analysis. Indeed, recall that our theory gives a criterion to predict whether our collaborative algorithms will outperform the Local baseline: this is the case when the desired accuracy of the solution ϵ is small enough for the given problem instance (see Eq. 9).

For the problem considered here, Eq. ( 9) gives that Restricted-Round-Robin will outperform Local for all agents as soon as ϵ is smaller than 0.049. We thus choose ϵ = 0.01 as the favorable regime (where we should beat Local) and ϵ = 0.1 as the unfavorable regime. We provide the corresponding high-probability mean estimation times τ a of Restricted-Round-Robin and Local given by our theoretical analysis (Theorem 2).

The results in Table 2 are consistent with our theory. All variants of our algorithms largely outperform Local for ϵ = 0.01,4 while Local is better for ϵ = 0.1 as agents can reach this precision using only their own samples faster than they can reliably estimate their class. Overall, Restricted-Round-Robin performs marginally better than Round-Robin, while Soft-Restricted-Round-Robin and Aggressive-Restricted-Round-Robin significantly outperform Round-Robin and Restricted-Round-Robin in both cases. Note that Soft-Restricted-Round-Robin and Aggressive-Restricted-Round-Robin perform roughly the same as Local in the unfavorable regime, and get very close to the performance of the Oracle baseline in the favorable regime. These results again show the relevance of our collaborative algorithms and heuristic weighting schemes. We observe that our theoretical results get looser as ϵ → 0, which is somewhat expected.

Extension to Imperfect Classes

So far we have assumed that two agents are in the same class if their personal distributions have exactly the same mean, which can be restrictive for some use-cases. In this section, we show that we can extend the problem setup and our approach to the case where two agents are considered to be in the same class if their means are close enough and agents seek to estimate the mean of their class.

Formally, we define a new notion of similarity class parameterized by a radius η, which generalizes our previous notion introduced in Definition 2.

Definition 7. Given η > 0, the η-similarity class of agent a is given by:

C η,a = {l ∈ [A] ∶ ∆ a,l ≤ η},
where ∆ a,l = |µ a -µ l | is the gap between the means of agent a and agent l.

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 in the same class may for instance stem from the presence of local measurement bias (e.g., due to local variations in the environment, see [START_REF] Taghavi | A practical bias estimation algorithm for multisensor-multitarget tracking[END_REF]. They can also be used to model groups of agents with similar preferences, behavior, or goals, in applications like collaborative filtering (Su & Khoshgoftaar, 2009b),

In this context, it is natural to slightly redefine the estimation objective. Instead of estimating its personal mean µ a as considered so far, each agent a aims to estimate the mean of its class:

µ η,a = 1 |C η,a | ∑ l∈Cη,a µ l . ( 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 η-similarity classes form separated clusters, in the sense that for three distinct agents a, l, i ∈ [A] we may have simultaneously i ∈ C η,a , i ∈ C η,l and C η,a ≠ C η,l . This happens when ∆ a,i ≤ η, ∆ l,i ≤ η and η < ∆ a,l ≤ 2η. In this case, the "class" of an agent simply corresponds to a ball of radius η around its mean, which potentially overlaps with others and thus violates the transitivity property of equivalence classes. For consistency with the rest of the paper and with an slight abuse of terminology, we continue to use the term "class". Although the case of separated clusters appears more natural, we note that our proposed approach will still work in the non-separated setting, in the sense that agents will correctly estimate the mean of their class as defined in Eq. 13.

Based on the above, we can adapt the notion of optimistic similarity class (Definition 2) and the condition on the number of samples required for this optimistic class to coincide with the true class (Definition 6) by incorporating η. Definition 8. The η-optimistic similarity class from the perspective of agent a at time t is defined as:

C t η,a = {l ∈ [A] ∶ d t a,δ (l) ≤ η}. Definition 9.
From the perspective of agent a and at time t, event G t η,a is defined as:

G t η,a = ⋂ l∈[A] n t a,l > n η a,l , (14)
where

n η a,l = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ ⌈β -1 δ ( ∆ a,l -η 4 )⌉ if l ∉ C a , ⌈β -1 δ ( ∆η,a-η 4 )⌉ otherwise, with ∆ η,a = min l∈[A]/Cη,a ∆ a,l . Lemma 3 (Class membership rule). Under E t a ∧ G t η,a and ∀l ∈ [A] and at time t: d t a,δ (l) > η ⇐⇒ l ∈ [A]/C η,a .
We can see from the above that ruling out an agent l from the optimistic class C η,a requires more samples for larger η, 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 ColME (Algorithm 1) presented before, with only minor modifications: we simply need to replace the notion of optimistic similarity class by the η-version of Definition 8, and compute the estimate µ t η,a at time t using a simple class-uniform weighting scheme α t a,l = 1 |C t η,a | to match the objective in Eq. 13. We refer to this algorithm as η-ColME. Note that η becomes a parameter of the algorithm, allowing to choose the desired radius for the class structure.

We can now state the class and mean estimation complexity of η-ColME. The proofs can be found in the appendix. Theorem 3 (η-ColME class estimation time complexity). For any δ ∈ (0, 1), employing Restricted-Round-Robin query strategy, we have:

P(∃t > ζ η a ∶ C t η,a ≠ C η,a ) ≤ δ 8 , with ζ η a = n η a,a + A -1 - ∑ l∈[A]∖Cη,a 1 {n η a,a >n η a,l +A-1} . ( 15
)
Theorem 4 (η-ColME mean estimation time complexity). Given the risk parameter δ, using the Restricted-Round-Robin query strategy and class-uniform weighting (while employing C η,a ), the mean estimator µ t a of agent a is (ϵ, δ 4 )-convergent, that is:

P(∀t > τ η a ∶ |µ t η,a -µ η,a | ≤ ϵ) > 1 - δ 4 , with τ η a = max(ζ η a , β -1 δ (ϵ) + |C η,a | -1). ( 16
)
The class estimation result (Theorem 3) is similar to its "perfect" class counterpart (Theorem 1) except that it involves η-dependent quantities. 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 beforehand is β -1 δ (ϵ) + |C η,a | -1.

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 mean. We have provided PAC-style guarantees for the class and mean estimation time complexity of our algorithms. In addition, we have introduced a number of sample weighting mechanisms to decrease the bias of the estimates in the early rounds of learning, whose benefits are illustrated empirically.

Our work initiates the study of online, collaborative and personalized estimation and learning problems, which we believe to be a 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 in order to determine when another agent can be considered to 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 number of agents is to have each agent focus on a restricted subset of other agents (see Remark 1), an interesting direction to allow more exploration in large-scale systems could rely on the idea of peer sampling [START_REF] Jelasity | Gossipbased peer sampling[END_REF], 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 slidingwindow UCB [START_REF] Garivier | On upper-confidence bound policies for switching bandit problems[END_REF] or UCB strategies mixed with change-point detection algorithms [START_REF] Cao | Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit[END_REF].

Privacy guarantees. In use cases where data is considered sensitive (e.g., personal data), it is important to 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, we would like to use tools from differential privacy [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF], such as the tree aggregation technique for sharing cumulative sums in an online way [START_REF] Dwork | Differential privacy under continual observation[END_REF][START_REF] Hubert Chan | Private and continual release of statistics[END_REF], to provide formal privacy guarantees 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 [START_REF] Vanhaesebrouck | Decentralized collaborative learning of personalized models over networks[END_REF] based on the data it receives online. In that case, a structure in the distribution conditioned by the outputs of the learned models can be inferred, introducing an interesting exploration-exploitation dilemma in the learning task.

P(∃t ∈ N, µ t a -µ a ≥ σ √ 2 t (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ , ( 17
) P(∃t ∈ N, µ a -µ t a ≥ σ √ 2 t (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ . ( 18
)
Proof. The two inequalities are proved in the same way as a direct consequence of [START_REF] Maillard | Mathematics of statistical sequential decision making[END_REF], Lemma 2.7 therein. Let Y 1 , . . . , Y t be a sequence of independent real-valued random variables where for each s ≤ t, Y s has mean µ s and is σ s -sub-Gaussian, then for all δ ∈ (0, 1), it holds that

P(∃t ∈ N, t ∑ s=1 (Y s -µ s ) ≥ 2 t ∑ s=1 σ 2 s (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ .
When all random variables Y s have the same mean µ a and variance σ, we have

P(∃t ∈ N, t ∑ s=1 (Y s -µ a ) ≥ √ 2tσ 2 (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ,
Taking the average rather than the sum, i.e. dividing both sides by t we obtain that:

P(∃t ∈ N, t ∑ s=1 ( Y s t - µ a t ) ≥ √ 2 t σ 2 (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ, P(∃t ∈ N, t ∑ s=1 Y s t -µ a ≥ √ 2 t σ 2 (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ .
And denoting µ t a = ∑ t s=1 Ys t , we conclude

P(∃t ∈ N, µ t a -µ a ≥ σ √ 2 t (1 + 1 t ) ln( √ t + 1/δ)) ≤ δ . Lemma 1. Let δ ∈ (0, 1), a ∈ [A]. Setting β δ (n) = σ √ 2 1 n × (1 + 1 n ) ln( √ n + 1/γ(δ)) with γ(δ) = δ 8×A , we have: P(E a ) ≥ 1 - δ 8 . (5) Proof. Let us recall that E a = ⋂ t∈N ⋂ l∈[A] |x t a,l -µ l | ≤ β δ (n t a,l ). Then P(E a ) = 1 -P( Ēa ), = 1 -P(∃t ∈ N, ∃l ∈ [A] ∶ |x t a,l -µ l | > β δ (n t a,l )), ≥ 1 -∑ l∈[A] P(∃t ∈ N ∶ |x t a,l -µ l | > β δ (n t a,l )).
defining γ(δ) = δ 8×A and using Lemma 4

P(E a ) ≥ 1 -∑ l∈[A] P(∃t ∈ N ∶ |x t a,l -µ l | > σ 2 n t a,l × (1 + 1 n t a,l ) ln( √ n t a,l + 1/γ(δ))), ≥ 1 -∑ l∈[A] γ(δ) = 1 -∑ l∈[A] δ 8A = 1 - δ 8 .

Appendix B Proof of Theorem 1

In this section, we prove Theorem 1. We first show Lemma 2 using two technical lemmas. We then prove Lemma 7, which combined with Lemma 2, yields the main result (Theorem 1). Let us first remark that

d t a,δ (l) = |x t a,a -xt a,l | -β δ (n t a,a ) -β δ (n t a,l ), = |(x t a,a -µ a ) -(x t a,l -µ l ) + (µ a -µ l )| -β δ (n t a,a ) -β δ (n t a,l ).
As a consequence we have

d t a,δ (l) ≤ ∆ a,l + |x t a,a -µ a | + |x t a,l -µ l | -β δ (n t a,a ) -β δ (n t a,l ). ( 19
) d t a,δ (l) ≥ ∆ a,l -|x t a,a -µ a | -|x t a,l -µ l | -β δ (n t a,a ) -β δ (n t a,l ). ( 20
) Lemma 5. Under E a , ∀l ∈ [A], if l / ∈ C a then ∀n t a,l ≥ n ⋆ a,l = ⌈β -1 δ ( ∆ a,l 4 )⌉ we have d t a,δ (l) > 0.
Proof. Under E a , we have |x t a,l -µ l | ≤ β δ (n t a,l ) and |x t a,a -µ a | ≤ β δ (n t a,a ). Since n t a,a ≥ n t a,l , we also have β δ (n t a,a ) ≤ β δ (n t a,l ). Hence, using (20),

d t a,δ (l) ≥ ∆ a,l -2β δ (n t a,a ) -2β δ (n t a,l ) ≥ ∆ a,l -4β δ (n t a,l ). If l ∈ C a then ∆ a,l = 0 and since β δ (n t a,l ) > 0 we cannot ensure that ∆ a,l -4β δ (n t a,l ) > 0. If l / ∈ C a then to ensure that d t a,δ (l) ≥ ∆ a,l -4β δ (n t a,l ) > 0, we need that ∆ a,l 4 > β δ (n t a,l ) and hence n ⋆ a,l = ⌈β -1 δ ( ∆ a,l 4 )⌉. 5 Lemma 6. Under E a , ∀l ∈ [A], ∀t ∈ N, if l ∈ C a then d t a,δ (l) ≤ 0.
Proof. Again, recall that under E t a , we have |x t a,l -µ l | ≤ β δ (n t a,l ) and |x t a,a -µ a | ≤ β δ (n t a,a ). Hence, using (19), d t a,δ (l) ≤ ∆ a,l + β δ (n t a,a ) + β δ (n t a,l ) -β δ (n t a,a ) -β δ (n t a,l ) = ∆ a,l . If l ∈ C a then ∆ a,l = 0 and thus d t a,δ (l) ≤ 0.

We can now prove Lemma 2, which we restate here for convenience.

ζ a = n ⋆ a,a -1 + A -∑ l∈[A]∖Ca 1 {n ⋆ a,a >n ⋆ a,l -1+A} . Proof. According to Algorithm 1, C 0 a = [A]
ζ a = n ⋆ a,a -1 + A -∑ l∈[A]∖Ca 1 {n ⋆ a,a >n ⋆ a,l -1+A} .
Finally, we use the above lemmas to prove Theorem 1, which we restate below for convenience.

Appendix C Proof of Theorem 2

In this section we detail the proof of Theorem 2, about the PAC mean estimation properties of the ColME strategy. We restate the theorem below for convenience.

Theorem 2 (ColME mean estimation time complexity). Given the risk parameter δ, using the Restricted-Round-Robin query strategy and simple weighting, the mean estimator µ t a of agent a is (ϵ, δ 4 )-convergent, that is:

P(∀t > τ a ∶ |µ t a -µ a | ≤ ϵ) > 1 - δ 4 , with τ a = max(ζ a , ⌈β -1 δ (ϵ)⌉ |C a | + |C a | -1 2 ). (8

Appendix E Proof of Theorem 4

In this section we detail the proof of Theorem 4, about the PAC mean estimation properties of the η-ColME strategy. We restate the theorem below for convenience.

Theorem 4 (η-ColME mean estimation time complexity). Given the risk parameter δ, using the Restricted-Round-Robin query strategy and class-uniform weighting (while employing C η,a ), the mean estimator µ t a of agent a is (ϵ, δ 4 )-convergent, that is: Remark that µ t a is not equivalent to the average of all the samples of agents in C η,a : it is the average of the mean values for each agent in C η,a . Therefore, although some agents may have more samples than the others, all are assigned uniform weights. We would like to have |µ t η,a -µ η,a | ≤ ϵ. When E a holds, we can rewrite this as A sufficient condition for the above inequality to hold is to ensure that each term is bounded by ϵ:

P(∀t > τ η a ∶ |µ t η,a -µ η,a | ≤ ϵ) > 1 - δ 4 ,
∀l ∈ C η,a ∶ |x t a,l -µ l | ≤ ϵ (21)
This is achieved when β δ (n t a,l ) < ϵ for all l ∈ C η,a . Since we are using Restricted-Round-Robin and also that C t η,a = C η,a , the number of samples required for each agent in C η,a are n t a,1 , n t a,1 -1, n t a,1 -2, . . . , n t a,1 -|C η,a |+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:

β -1 δ (ϵ) < n t a,a -|C η,a | + 1 β -1 δ (ϵ) + |C η,a | -1 < n t a,a

  Error in mean estimation over all agents

Figure 1 :

 1 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 algorithms (Soft-Restricted-Round-Robin, Aggressive-Restricted-Round-Robin, Restricted-Round-Robin, Round-Robin), agents are able to estimate their true class (Fig. 1(a)) and thereby obtain accurate mean estimates much more quickly than using purely local estimation (Fig. 1(b)).

  µ l | ≤ |C η,a | × ϵ,

  Proof. From Lemma 7 and Lemma 2, we deduce that if E a holds and knowing thatC t a = {l ∈ [A] ∶ d t a,δ (l) ≤ 0} then ∀t > ζ a , C a = C t a . Hence, P(∀t > ζ a , C a = C t a ) ≥ P(E a ) ≥ 1 -δ/8 using Lemma 1.

	Theorem 1 (ColME class estimation time complexity). For any δ ∈ (0, 1), employing Restricted-Round-
	Robin query strategy, we have:
	P(∃t > ζ a ∶ C t a ≠ C a ) ≤	δ 8	l∈[A]∖Ca a,a + A -1 -∑ , with ζ a = n ⋆	1 {n ⋆ a,a >n ⋆ a,l +A-1} .	(7)

)

  Proof. Let us assume that at time t we have C t a = C a . Therefore is the sum of all n t a,l samples received by all agents l in C a . In other words, µ t a is the estimation of µ a with ∑ l∈Ca n t a,l examples. Hence in order to have |µ t a -µ a | ≤ ϵ when E a holds, we should have β(∑ l∈Ca n t a,l ) ≤ ϵ. Let us see at what time denoted by n ϵ,a we have ⌈β -1 (ϵ)⌉ = ∑ l∈Ca n t a,l . With Algorithm 13 using Restricted-Round-Robin, we know that when C t a = C a , then only members of C a are queried. Therefore,⌈β -1 (ϵ)⌉ = n ϵ,a + (n ϵ,a -1) + ⋅ ⋅ ⋅ + (n ϵ,a -|C a | + 1) = |C a |n ϵ,a -|C a | -1 2 |C a |, As a summary, if E a holds, then we have ∀t ≥ n ϵ,a , C t a = C a implies that |µ t a -µ a | ≤ ϵ. Now, following Theorem 1, we have P(∃t > ζ a ∶ C t a ≠ C a ) ≤ δ 8 . Since τ a = max(ζ a , n ϵ,a ) ≥ ζ a , then P(∃t > τ a ∶ |µ t a -µ a | > ϵ) ≤ Under E a , ∀l ∈ [A], ∀t ∈ N, if l ∈ C η,a then d t a,δ (l) ≤ η. Lemma 10. Under E a , and using Restricted-Round-Robin algorithm, G t η,a holds when t > ζ η a where

	Lemma 9. ζ η a = n η a,a -1 + A -	∑ l∈[A]∖Cη,a	1 {n η a,a >n η a,l -1+A} .
		µ t a = ∑ l∈Ca	xt a,l α t a,l =	∑ l∈Ca ∑ l∈Ca n t xt a,l n t a,l a,l	.
	Remark that ∑ l∈Ca	xt a,l n t a,l n ϵ,a =	⌈β -1 (ϵ)⌉ |C a |	+	|C a | -1 2	.
	δ 8 + P( Ēa ) = δ 4 .

  with τ η a = max(ζ η a , β -1 δ (ϵ) + |C η,a | -1). (16)Proof. Since t > τ η a > ζ η a , at time t we have C t η,a = C η,a . Therefore

	µ t a = ∑	xt a,l α t a,l =	∑ l∈Cη,a	xt
	l∈Cη,a

a,l |C η,a | .

  Therefore τ η a = max(ζ η a , β -1 δ (ϵ) + |C η,a | -1). As a summary, if E a holds, then we have ∀t ≥ τ η a , C t η,a = C η,a implies that |µ t η,a -µ η,a | ≤ ϵ. Now, following Theorem 3, we have P(∃t > ζ η

	δ 8 + P( Ēa ) = δ 4 .	a ∶ C t η,a ≠ C η,a ) ≤ δ 8 . Since τ η a = max(ζ η a , n η ϵ,a ) ≥ ζ η a , then P(∃t > τ η a ∶ |µ t a -µ η,a | > ϵ) ≤

In Section 7, we will consider a relaxed version of this assumption where classes consist of agents with similar (not necessarily equal) means.

We use Õ(⋅) to hide constant and logarithmic terms.

The code can be found at https://github.com/llvllahsa/CollaborativePersonalizedMeanEstimation

We had to run Local for a much larger time horizon of 30000 steps for all runs to converge to accuracy ϵ = 0.01.

In extremely rare cases, the expression β -1 δ ( ∆ a,l 4 ) could be an integer and we should add 1 to get a strict inequality. But for conciseness of the expression, we omit the +1 in the definition of n ⋆ a,l .

Acknowledgments

The authors thank the reviewers for their insightful comments that allowed to improve the paper. This work was funded in part by Métropole Européenne de Lille (MEL), Inria, Université de Lille, and the I-SITE ULNE through the AI chair Apprenf number R-PILOTE-19-004-APPRENF.

Appendix A Proof of Lemma 1

Lemma 4. Let µ t a be the mean value of t independent real-valued random variables with the true mean µ a and is σ-sub-gaussian. For all δ ∈ (0, 1), it holds:

Appendix D Proof of Theorem 3

The proof of Theorem 3 follows the same step as that of Theorem 1, up to replacing the 0 threshold by η. We only state the intermediate lemmas (which are adaptations of Lemmas 5-6-7) and omit the detailed proof.

Lemma 8. Under E a , ∀l ∈ [A], if l / ∈ C η,a then ∀n t a,l ≥ n η a,l = ⌈β -1 δ ( ∆ a,l -η 4

)⌉ we have d t a,δ (l) > η.

Appendix F Additional Experimental Results

In this section we provide additional illustrative results to better understand different aspects of our ColME algorithm.

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 separately. 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 is larger, this class requires less samples to be identified. Indeed, the average class identification time is less than t = 400 for that class (Figure 2(c)), while it is about t = 1400 for the other two (Figures 2(a)-2(b)). Therefore, agents from the class with mean 0.8 reach a highly accurate estimate much faster than agents from other classes.

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 of Table 2345. In line with previous results on class estimation, agents of class 0.8 are the ones that converge faster to the desired mean estimation accuracy. Interestingly, observe that for ϵ = 0.1, agents of class 0.2 converge almost as fast as 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 a 2-class problem

We experiment with a 2-class problem generated in 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 easier since the gap between the two classes corresponds to the largest gap in the 3-class problem. The results shown in Figure 4 reflect this: agents correctly identify their class and reach highly accurate mean estimates much faster than 20 Table 3: Empirical convergence times (see 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 a 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 τ a given by our theory for Restricted-Round-Robin 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). 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 a 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 τ a given by our theory for Restricted-Round-Robin and Local.


I Radić

M Donner

T Yatribi

Y Erraach

F López-I-Gelats

J Manuel-I-Martin

F El Hadad- Gauthier

Factors influencing innovative circular business models in the Mediterranean olive oil value chain

Introduction

The production of olive oil generates vast quantities of waste (wood, branches, leaves) and by-products (olive pomace, olive mill wastewater, olive stones) [START_REF] Roselló-Soto | Emerging opportunities for the effective valorisation of wastes and by-products generated during olive oil production process: Non-conventional methods for the recovery of high-added value compounds[END_REF][START_REF] Berbel | Review and analysis of alternatives for the valorisation of agro-industrial olive oil by-products[END_REF] that imply risks of natural resource depletion, phytotoxic effects, and water pollution (Azbar et al., 2004, Paraskeva and[START_REF] Paraskeva | Technologies for olive mill wastewater (OMW) treatment: a review[END_REF]. Such risks can influence the environmental protection and resilience to climate change crisis and water scarcity, being some of the core Mediterranean challenges1 . Thus, the enterprises involved in olive oil production are facing multiple stimuli for a transition towards circular business models and better waste management, pushed institutionally by the regulations (and especially regarding water), societal demands, and resource scarcity. Waste and by-products from olive oil production should not only be considered from a mere 'management or treatment' point of view. Still, they can offer opportunities to be valorised, i.e. to be converted into new valueadded and marketable ingredients and products, potentially leading to additional farmers' incomes and a more sustainable and environmentally resilient olive oil value chain. Business models explain the way an enterprise works and "articulate the logic, the data and other evidence that support a value proposition for the customer, and a viable structure of revenues and costs for the enterprise delivering that value" [START_REF] Teece | Business models, business strategy and innovation[END_REF]. Circular business models are a subcategory of business models, which incorporate circular economy principles as guidelines, aiming to fully close product or material loops [START_REF] Bocken | A review and evaluation of circular business model innovation tools[END_REF][START_REF] Donner | A new circular business model typology for creating value from agro-waste[END_REF], proposing the creation of value from waste or providing functionality instead of products [START_REF] Bocken | A literature and practice review to develop sustainable business model archetypes[END_REF]. [START_REF] Suchek | Innovation and the circular economy: A systematic literature review[END_REF] suggest business model innovation as one of the topics in their future research agenda for circular economy advance research. The objective of this work was to understand the factors that influence enterprises to switch to circular business models by valorising olive waste and by-products (for food and non-food applications). We aimed at enterprises from the olive oil sector, either involved in olive oil production or specifically creating value from olive waste and by-products, utilizing multifunctionality of the olive tree and enhancing alternative performance within and beyond the traditional patterns for value creation. Our hypothesis was that these enterprises are influenced by a set of internal and external success factors and barriers.

Methods

The methodological approach for this study was qualitative content analysis. Firstly an online search for olive oil company websites was performed to mark the ones with indications of waste or by-product valorisation, which resulted in a database of 41 enterprises of interest. Snowball sampling was employed to get referrals from COLIVE project partners and experts in the olive oil sector to contact the enterprises. The criteria for selecting the enterprises were the diversity of countries and their contexts; diversity of types of initiatives (but, e.g. specialized in waste valorisation vs. non-specialized, family business vs. cooperative, small -large-scale); and business model elements -i.e. the diversity of resources and value propositions. The search resulted in ten cases of entrepreneurial initiatives from the following Mediterranean countries: Tunisia (2), Morocco (1), France (1), Spain (1), Italy (2), Greece (3). For each case, as a preparation, the data available online was compiled (website, videos, articles), and further, semi-structured interviews were conducted with the responsible persons from the enterprises. For the two cases in Tunisia, a field visit was done. Interviews were conducted in English, French, Spanish and Italian language. The essential data of each case was synthesized as follows: name and type of initiative, country and region, principal or side activity, context and background of the enterprise, type of resource valorised, valorisation pathway, and outputs (products) including the enabling and hindering factors and socio-institutional context. The specific focus was on enabling and hindering factors, socio-institutional context, and the role of public policies.

Results

Results indicate that two types of enabling and hindering factors influencing the implementation of circular business models exist, internal and external factors. The principal internal enabling success factors are an environmental concern, resource availability, knowledge about waste valorising technologies and markets, and long-term presence in the sector. The olive oil enterprises can be characterised by their involvement in the circular economy, caring for the environment, especially in the context of water, its scarcity and toxicity of wastewater, and whose enterprise managers are convinced that for the continuation of their activity, there is a need for more sustainable practices, and logistics (territorial synchronized collection of waste has to be well organized and the proximity between the waste generation site and waste valorisation site has a crucial role). The external factors enabling successful implementation of circular business models are legislation and public subsidies, the consumers' role, and circular economy embeddedness in the territorial agenda. Legislative obligations, in particular for the treatment of wastewater and regional norms for the preservation of landscapes, are another push for enterprises to adopt circular economy principles. Two important hindering factors or challenges for the enterprises are both strong managerial implication (internal factor) and (financial) support from experts, policy and decision-makers (external factor). Firstly, even though the olive oil sector urgently needs subsidies for investments in waste valorising activities, the enterprises do not have any specific support measures. The role of waste management activities is recognized but not supported in practice. Secondly, the much-needed collaboration between enterprises and research centres or universities is rather complicated.

Conclusion

Utilizing waste and by-products from the olive oil-producing activity is a long-lasting practice, considering that soap and pomace oil are produced for centuries already. The pioneers in the field are now well-established enterprises showing success also in further innovation in circular business models. The entrepreneurial initiatives involved in olive oil waste and by-product valorisation are using multiple olive tree resources, employing different valorisation pathways, and are an example of an alternative performance of existing olive tree resources both in the olive plantation field and in the processing facilities, providing alternative resource use, and enhancing the economic and environmental resilience of the olive oil value chain. The sustainable image of an enterprise and its resilience over time is often a driving factor for a further transition towards sustainable and circular business models to keep the promise to clients for engagement in environmental sustainability. The enterprises implementing circular economy business models are driven by a commitment to the environment, in particular, because of the unused high amounts and partly environmentally harmful residues [START_REF] Donner | Innovative circular business models in the olive oil sector for sustainable mediterranean agrifood systems[END_REF]. Mainly in the countries of the north side of the Mediterranean region, legislative obligation, particularly for the treatment of wastewater and regional norms for the preservation of landscapes, is undoubtedly a push for enterprises to engage with a circular economy transitioning towards circular business models. A common feature observed among all the cases is territorial embeddedness as a motivation for implementing circular activities and as a success factor. The most critical discrepancy among the cases regards external support and partnerships. Despite the positive trends among businesses, olive waste and by-product valorisation, especially for higher added-value applications, is not yet well-established. The question is why. The knowledge transfers from the research level to the implementation in the field and the articulation of needs for research from the enterprises' side represent challenging tasks. More public-private partnerships or multi-stakeholder collaborations, e.g. via joint projects, are needed for further shifting to a circular economy.

https://www.iamm.ciheam.org/en/about/ciheam/strategic_agenda_2025/challenges