Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints
Authors: Xinmeng Huang
Donghwan Lee
Edgar Dobriban
Hamed Hassani
Venue: NeurIPS 2022 Accept (2022)
Keywords: Collaborative Estimation
Sparse Heterogeneity
Communication Constraint
Discrete Distributions

Abstract: In modern machine learning, users often have to collaborate to learn distributions that generate the data.  Communication can be a significant bottleneck. Prior work has studied homogeneous users---i.e., whose data follow the same discrete distribution---and has provided optimal communication-efficient methods. However, these methods rely heavily on homogeneity, and are less applicable in the common case when users' discrete distributions are heterogeneous.  Here we consider a natural and tractable model of heterogeneity, where users' discrete distributions only vary sparsely, on a small number of entries.  We propose a novel two-stage method named SHIFT: First, the users collaborate by communicating with the server to learn a central distribution; relying on methods from robust statistics.  Then, the learned central distribution is fine-tuned to estimate the individual distributions of  users.  We show that our method is minimax optimal in our model of heterogeneity and under communication constraints. Further, we provide experimental results using both synthetic data and $n$-gram frequency estimation in the text domain, which corroborate its efficiency.

Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints
Xinmeng Huang',
Donghwan Lee
Graduate Group in Applied Mathematics and Computational Science University of Pennsylvania
Philadelphia, PA 19104
{xinmengh, dsas upenn. edu
Edgar Dobriban
Hamed Hassani
Department of Statisties and Data Science
Department of Electrical and Systems Engineering
University of Pennsylvania
University of Pennsylvania Philadelphia, PA 19104 hassani@seas, upenn edu
Philadelphia, PA 19104
dobriban@tharton. upenn. edu
Abstract
In modern machine learning, users often have to collaborate to learn distributions that generate the data. Communication can a significant bottleneck. Prior work has studied homogeneous users-i.e.. whose data follow the same discrete aistribution-and has provided optimal communication-effinn ever, these methods rely heavily on homogeneity, and are less applicable in the common case when users' discrete distributions are heterogeneous. Here we consider natural and tractable model of heterogeneity, where users' discrete distributions only vary sparsely. on a small number of entries. We propose a novel two-stage method named SHIFT: First, the users collaborate by communicating with the server to learn a central distribution; relying on methods from robust statistics. Then, the learned central distribution is fine-tuned estimate the indi- vidual distributions of users. We show that our method minimax optimal our model of heterogeneity and under communication constraints. Further, provide experimental results using both synthetic data and n-gram frequency estimation in the text domain, which corroborate its efficiency.
methods. How-
Introduction
Research on learning from data distributed over multiple computational units (machines, users, devices) has grown in recent years, as data is commonly generated by multiple users, such as smart devices and wireless sensors. While many works focus on learning predictive models with distributed data, learning the data distribution itself is also increasingly popular [56] [ [4 [5] 60). In various
applications, it is often required to reconstruct the data distribution from scattered measurements. Examples include sensor networks and P2P (Peer2Peer) systems, load balancing and query processing
(see, egg., [41 61 (6) and references therein). In these scenarios, communication costs and bandwidth often bottlenecks
the performance of learning algorithms [22 5 29 17). The bottlenecks
become even more severe in federated analytics [31]. where many users coordinate with server to
learn central models, while communication via the wireless links is typically expensive and operates at low rates.
Equal Contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Estimation error BB[[p' p p[ of various methods when is sufficiently large: p is the test distribution, p' is the estimator, 8' 0'=7" - -' Ereryy p" p' is non-vanishing measure of heterogeneity. See Section 1.1 for other notations. Constants and logarithmic factors are omitted for clarity, The "data usage" column indicates whether the estimate is obtained for each cluster separately or by pooling data.
Method
Estimation Error
Data Usage
Bound Type
Unif. Group//Hash.
266
Separate
Upper
T
Unif. Group./Hash. 26
(118'112 T
Pool
Upper
||n'|l1/22 O
Localize-then-Refinn 15
Separate
Upper
24n
11 Eeer p 111/2
Localize-then-Refine 15
O
||011 +
Pool
Upper
2
(max(2".el 2
SHIFT (Theorem
+ T
Upper
maxx (2" .s]
SHIFT (Theorem
Ω
+
Lower
2"n
This method
[15
requires interactive communication protocols, while other methods are non-intenenn non-interactive.
This paper considers learning high-dimensional discrete distributions from user data in the distributed methods have been proposed, and their optimality under
setting. Many communication-efi
communication constraints has been established under various models (26] 6 27 2 14 15). How- ever, the key challenge of heterogeneity, i.e., that users' distributions can differ, is rarely considered. Heterogeneity is common, as users inevitably have unique characteristics [13]. Meanwhile, hetero- geneity can cause significant performance drop for learning algorithms designed only for i.i.d data
[37 34 20 59]. To use all the data, one needs learn some central structure, transferable to all individual users. Then one may locally learn the unique components for each user [21 53 16 [57.
To study this paradigm. we first need to introduce suitable model of heterogeneity. We consider, as an example, the heterogeneous frequencies of words across different texts, e.g.. news articles, books, plays (tragedies and comedies), viewed as users. Most words appear with almost the same probabilities in different texts, however, a few can have very different probabilities, such as "sorrowful" being common in tragedies and "convivial" being common in comedies. Motivated by this, formulate a model of sparse heterogeneity. Specifically, suppose that the discrete distributions of all users differ from an underlying central distribution in at most entries, where is much smaller than the dimension d. Sparse heterogeneity is relevant to applications such as recommendation systems 28
and medical risk scoring [50 43 40
However, given data generated by multiple distributions with sparse heterogeneity, previous works 2 either do not use all the data, or suffer from bias due to heterogeneity that does not vanish as the sample size increases. Here we propose a novel sparse heterogencity inspired collaboration and fine-tuning method (SHIFT) where we first collaboratively learn the central distribution, and then fine-tune the central estimate to individual distributions. Our method makes full use of heterogeneous data, leading to significant improvement in error rates compared to prior methods. See T an overview, explained in detail later.
1.1 Contributions
We consider the problem of learning d-dimensional distributions with s-sparse heterogeneity. We assume there are T clusters of user datapoints, and allow each datapoint to be transmitted with bits of information to the server. Our setting embraces heterogeneous data and thus significant generalization of the models from 226 27 2). Our technical contributions are as follows:
We propose the SHIFT method learn heterogeneous distributions with collaboration and tuning, in sample-efficient manner. Our method can in principle be used with an arbitrary robust estimate for the probability of each entry/coordinate. When entry-wise median and trimmed mean are used, we provide upper bounds on the estimation error of individual distributions in the &g and & norms. We show factor of min (T, d/ max (s. 2 improvement in sample complexity compared to previous works; showing the benefít

---

of collaboration (large T') and sparsity (small s), despite communication constraints and heterogeneity.
To justify the optimality of our method, we prove minimax lower bounds on the estimation errors for individual distributions in the &g and & norms, holding for all. possibly interactive, methods. These lower bounds, combined with our upper bounds, imply that our median- based method is minimax optimal.
We support our method with experiments on both synthetic and empirical datasets, showing a significant improvement over previous methods.
1.2 Related Works
Learning with heterogeneity. Learning with heterogeneity is commonly found in the broader context of multi-task learning [12 52 8l and federated learning 44] 44 47] where a central model or representation is learned from multiple heterogeneous datasets. These central representations can be useful for few-shot learning tasks [51
23 due to their ability to adapt to new tasks efficiently. In heterogeneous linear regression, [53 21 show improved sample complexities by assuming low dimensional central representation, compared to the i.i.d. setting [24] 36]. Related results are proved by [16] for personalized federated learning. (57) study bandit problem where the unknown parameter in each dataset equals a global parameter plus a sparse mestance-specinng term. We study a different setting: learning distributions with sparse heterogeneity under communication constraints.
Estimating discrete distributions 45 197. Under communication constraints, [26, 6 27 2 consider the non-interactive scenario and establish the minimax optimal rates, in terms of data dimension and communication budget, via potentially shared randomness, when all users' data is homogeneous. The optimality for the general interactive (blackboard) methods is developed by []] A few works study the estimation of sparse distributions. In particular, 3 consider s-sparse distributions and establish minimax optimal rates under communication and privacy constraints, which are further improved by localization strategies in [14]. Complementary minimax rates, [13] provides pointwise rates, governed by the half-norm of the distribution instead of its dimension. Our setting embraces heterogeneous data, and thus a generalization of the one studied in above works.
Estimating distributions under communication constraints.
has rich literature [10] [8
Robust estimation & learning. Robust statistics and learning study algorithms resilient to unknown data corruption 30 (2)). The median-of oe-nn method [32 33 39 partitions the data into subsets, computes an estimate from each, and takes their median. Similarly, some works study robustness from the optimization perspective, proposing to robustly aggregate gradients of the loss functions [8 44 [ (8). We adapt some analysis techniques from [39 (88) to the significantly different setting
of estimation with heterogeneity and communication constraints.
1.3 Notations
Throughout the paper, for an integer 2 1, we write [d] for both (1....,d .d) and {ei,..., ea) S Rd. where ej is the k-th canonical basis vector of gd For a vector by both [v]....., [vla and UI...., Ua. We denote ||v||, = (Ekeig) |u) for all p with ||vloo defined additionally as the number of non-zero entries. We let Pa {p- (pI.....Pa) E [0, 1] + Pa
1Rd, we refer the entries of
1} be the simplex of all d-dimensional discrete probability distributions. For p E Pa. we denote by BB, (p) the s-distinct neighborhood (p' Pa ||p" pllo S $). For random variable X, we denote i.i.d. copies of X by xlm), Given any index set I, we write [I] for its cardinality and Sachmannn-Lnddan asymptotic
Pi +
denote by [v]z the sub-vector ([v]))eE indexed by Z. We use the notations (2()). (-)) O() to hide constant factors, and use 52(-), Ō(-) to also hide logarithmic factors. We denote the categorical distribution with class probability vector p E Pa by Cat(p). We use and to indicate the intermediate estimate and the final estimate, respectively.
Problem Setup
We consider the problem of collaboratively learning distributions defined according to the following model of heterogeneity (see Figure for an illustration). There are T > clusters {C' A (xx*))
3

---

t E [TT) of user datapoints, each of which contains n. i..dd local datapoints. Each datapoint X is in one-hot format, i.e., X {er, e ea). and follows the categorical distribution Cat(p') where p' E Pa is unknown. Thus, user datapoints in the same cluster have an identical distribution p', while the distribution p' can vary, Le., be heterogeneous, across clusters t [7]. The datapoint X is encoded by its user into a message Y and then transmitted to central server. We assume that the message sent by each datapoint is encoded into no more than bits and can significantly smaller than log, d so that the communication is efficient. We also assume the server knows which cluster E [7] each Y belongs to, as well as the number of clusters T. This paper mainly addresses the communication bottleneck and does not involve privacy concerns.
The goal here is to collaboratively learn the distributions p' from the collection of messages (Y* (Y*')) ( JE( d' E [T]} despite beterogeneity. More precisely, we aim to design per-cluster estimators D (y E [T]} + Pa to minimize the &g errors
B - p'1l2) for all e [7].
We also study the widely-used & error metric (in addition to the & metric). When = 1, i.e., all user datapoints are homogeneous and there is single distribution learn, the problem reduces to the one studied by 226 6 27 1.
Model of heterogeneity. In heterogeneous set- tings, collaboration among the users is most ben- eficial if the local distributions related. We model this by assuming that the local distribu- tions are sparse perturbations of unknown central distribution p E Pa. The distribution p' of each cluster differs from p in at most $ 2 0 entries:
centralized server
output: p ,....p p
bits
x1
XT:
||p' - 15-1pl1o s, Vt E [T].
(I)
cluster C
cluster C
The central distribution p can be viewed as the central structure across heterogeneous clus- ters of datapoints. The level of heterogeneity controlled by the parameter When is much smaller than d, the local distributions differ from the center in small number of entries.
p'
p"
While motivated by word frequencies of dif- ferent texts, our model of sparse heterogeneity is also relevant for recommendation systems, where the high- nigh-dimensional item cem--peference vectors of users can vary sparsely 28 35 7 and medical risk scoring, where hospitals enjoy similar predicted results but with few systematic differences in diagnosis behavior, healthcare utilization, etc 50
Figure 1: Learning distributions with hetcrogeneity and communication constraints.
Algorithm
We introduce method for leveraging heterogeneous data improve per-cluster sample efficiency. We first discuss bashing-basel method to handle the communication constraint. Since communication between each user datapoint and the server is restricted to most > bits (where we may have 2 < d), the datapoint t needs to be encoded by an encoding function W X A [d] y. The b-bit constraint enforces ||] < 2b Then the encoded message you = W (Xtd) is sent the server, where it is decoded and used.
Under relatively sophisticated protocols, the design of encoding functions can be interactive [5] []. iee, depend previously sent messages. Here we adopt non-interactive encoding-decoding scheme, based on uniform hashing 3 [4] where W depends only on X and is independent of other messages. Specifically, each datapoint X is encoded via an independent random hash function ha [d] + [2*]. Upon receiving all messages, the server counts the empirical frequencies of all symbols, leading to hashed estimates b'. The communication scheme based uniform hashing

---

Algorithm SHIFT: Sparse Heterogeneity Inspired collaboration and Fine-Tuning
input:
individual hashed estimators b' ..... .....,',, b", threshold parameter
>> Stage I: Collaborative Learning
Estimate ba via robust statistical methods: b² < robust_cstine Doobuss_sstimatefPPP ((b' E :
(7T))
Stage II: Fine-
for ,,....d d do for = ,...., T do
[b'} [b*] k
[b']al S Va(b'la/n, else [b']
D' + Proijo.11
2"
end for end for output: estimates p ..... D
summarized below.
(Encoding) Send the message ytu 114 -11'' (X++) encoded by a hash function h [d] + [2%]
(Decoding) Count ((( kí E [n] ht (k) y and return [b'] Nt/nn.
It is easy to verify that E|b'] = [(2b 1)p' + 1 - b³: and thus the hashed estimate 5 is biased for p'. We also write b* = [(2 1)p + 1 for the mean of a hashed datapoint sampled from the central distribution. More details on the hashed estimator b' are given in Appendix A
3.1 The SHIFT Method
We now introduce the SHIFT method, which consists of two stages: collaborative learning and fine-tuning. The first stage estimates the central hashed distribution b' using all hashed estimates (b' :t [T]}. This is achieved via tools from robust statistics such as the median trimmed mean. The key insight here is that, since the heterogeneity is sparse, for each entry at which the individual distributions less mismatch with the central one, most datapoints (used to estimate that entry) sampled from the probability of the central distribution. Hence, to estimate those entries of the central distribution, we can treat the datapoints generated by heterogeneous users as corrupted, and leverage robust statistical methods to mitigate their influences.
In the second stage- finet-iintuunng---... we detect mismatched entries between individual hashed estimates I' and the central estimate 6*. Recall that the central and individual distributions differ in only few entries. For entries k E [d] such that [[b*]x [b']a] is below (o]]*)//)) for some threshold parameter o, we may expect that p pk- As result, the estimate [6*] of bg can be more accurate as it is learned collaboratively. Thus, assign [b*] as the final estimate [b'] of bj.
On the other hand, for the entries where the central and individual distributions differ, i.e., pt. + pi- the threshold is more likely to be exceeded. In this case, we keep the individual estimate [b'] as [b*]s- Finally, since the hashed distributions b' biased, we debias them in the final estimates of p' where Projjo.1f (-) indicates truncating the input with upper/lower bound and O. Our method does not require sample splitting, despite using two stages, leading to increased sample-efficieney. We remark that the SHIFT does not require the knowledge of the sparse heterogeneity s.
Knowledge transfer to new clusters. The collaboratively learned central distribution from Algorithm is adaptable to new clusters, with possibly few datapoints. This can be particularly beneficial for sample efficiency because most entries of the target distribution are well-estimated through collaborative learning. One can transfer those entries, and it suffices to estimate the few remaining entries, instead of the whole distribution. See Theorem for the details. The knowledge transfer utility further motivates the importance of collaborative learning.
5

---

3.2 The Median-Basse Bassd SHIFT
In this section, we provide statistical guarantees, the form of upper bounds on the error, for the median- SHIFT method, where babust_estimate(( ((b' E [T]}) in Algorithm is the entry-wise median. Specifically, we let
[b*] median [[b'} [2])), for each k E [d].
When there is ambiguity, write b median (b' hetry) We also provide results for the trimmed -eamndd-eea---e mmean-based SHIFT method, see Appendix D
By setting the threshold parameter in Algorithm as ((I(nn)), we prove the upper bounds on the final individual &g estimation errors as follows. The results for the & error are in Appendix C
Theorem 1. Suppose 2 2 In(n) and @(In(n)
Then, for the median-based SHIFT
method, for any t E [T].
max $}
E [[p'' pp' =
2 +
2
n2
When 2 2 (n)) and n = S2(2 min d/ max (2 }}}),, the rate further becomes
E || P = maxx s}
(2)
n
2
The upper bound in consists of two terms. The first term max(2",
s2)(2nn) / the dimension d, and is a factor d/ max 8} smaller compared to the rate dd/(2n) obtained by the minimax optimal method using only homogeneous datapoints (6). Thus, it brings significant benefit under sparse heterogeneity, i.e., when 8 < d. Meanwhile, the second, dimension-dependenn,, term d/ d2(2"I') T times smaller than d2)22n) since it depends on the total sample-size I'n used col- laboratively, despite heterogeneity. Therefore, our method shows factor of min d/max{(2 }}} improvement in sample efficiency, compared to previous work designed for homogeneous datapoints.
is independent of
For completeness, we also consider heuristic version of estimators of prior works 26 15 in
which all datapoints are pooled learn a global distribution T~1 E'Errr p', which then used by each cluster. While this uses all datapoints, inevitably introduces non-vanishing bias 0' p' 1 Every p" in estimating individual distributions, and can behave poorly when the bias is large. See Table for more details.
Finally, discuss results on knowledge transfer. The central estimator b is adaptable new cluster CT+1 in the following way. We adjust the fine-tuning procedure in Algorithm to
1b [b*] if [[b] [b*+*]l S ValTT++ and [b [b otherwise,
where n is the size of CT+1, We then show the following result.
Theorem 2. Let T be the hashed estimate of any cluster CT+1 with ñ datapoints such that n 2 ñ 2 2b+6 In(n) and ñ = O22 min(T, d/ max(2', ,{})). Let the threshold parameter be (In(n)). Then, the median based SHIFT method has error bounded by
max
d
E T+
121 =
2b
2
Similarly, one can see that adaptation to new clusters with the median-based SHIFT method achieves a factor of min (Tn/ñ, d/ max(2', x)} improvement in sample-efficiency compared to the case where the distribution of the new cluster is estimated from scratch (i.e. without any knowledge transfer).
3.2.1 Highlights of Theoretical Analysis
In this section, introduce the key analytical ideas behind the proof of Theorems I and Our analysis is novel compared to previous analyses for methods with homogeneous datapoints. The
"To be precise, we require O(I(n)) and 2 cln(n) for some absolute constant c. The analogous statement applies in Theorem 2

---

final individual estimation errors relate to the enror of estimating the central hashed distribution b". However, we only expect high accuracy at the center for entries at which the heterogeneity is mild. To quantify the influence of heterogeneity, for any 0 < " S 1, we define the set of w-well-aligned entries as
In = (k E [d] |B&l < <nT), where B - { E [T] by + Ubg Le., Ph + ph}
is the set of clusters whose distribution differs from p in the k-th entry. We aim to estimate the 17-well-all 7--well-aligned entries accurately by using robust statistical methods.
Further, we argue that there are few poorly-aligned entries, and they affect the final per-cluster error only mildly. By the pigeonhole principle, the number of entries that bounded by | - [[d] S 9 " Therefore, given an estimator by that is accurate for the ---well-aligned entries, the entries of b" can be estimated accurately except for at most s/n entries.
n-wwel-alignee is upper
The following technical lemma bounds the error for each entry & In.
Lemma 1. Suppose b. = median (b))))))) Then for any 0 < 1) S 1/5 and E Inp it holds that
B 1 b()
b (1 bj)
B[[["] l - [b*
+
T
Tn
n
Lemma provides an upper bound relating to the frequency |BxI/T of misalignment (smaller than
7). and a variance term (1 bg). This result cannot be obtained by directly applying the standard Chernoff or Hoeffding bounds to random variables distributed in (0. 1] as in previous works [T5] for two reasons: 1) the datapoints are heterogeneous, 2) the variance b7 (1 - bi) here can be small, compared to general random variables in [0, 1J. implying more concentration than follows from Hoeffding's 's inequality. To address these issues, we analyze the concentration of the empirical (1/2 + (Bll/T)-quaniieee inequality, which is variance- dependent [54], to obtain bounds relying on both the sample size Tn. and the variance by - b).)
to mitigate the influence of heterogeneity, and we also use Bernstein's 's
Also, the constant 1 1/5, controlling the heterogeneity, is not essential (we choose 1/5 for clarity). can be replaced with any number below 1/2 so that estimating the central probability distribution becomes possible, as the information conveyed by homogeneous datapoints dominates.
Lemma reveals that well-aligned entries of the central distribution are accurately estimated. Thus one can the central estimate for the entries where the central distribution p' aligns with the target distribution p'. The remaining entries, that are neither well-aligned nor satisfy P = pk- can be estimated by the individual estimator. We argue that properly chosen threshold parameter filters out the desired entries to be estimated individually with high probability, leading to Theorems [ and 2
While estimating p" is not our main goal, one can readily obtain from Lemma I the following bound on estimating p" by summing up the errors for all entries k E [d] = I, with r) max ig [B&]- Corollary MaciaaryTrevve reveals that the central distribution can be accurately estimated if the mismatching of distributions happens uniformly across all entries, i.e., each entry differs in O of clusters.
2b6-_1) be obtained by the debiasing operation from Algorithm 2 7 Suppose |B&l = O(sT/d) /d) for any k E [d]. with maxxe(d] BBa//T, the median-based SHIFT method enjoys
Corollary 1. Let 5 = Projjo.11
ElI p-1 =
(
s²
d
d
+
122nn
T
n2
4 Lower Bounds
To complement upper bounds, we now provide minimax lower bounds for estimating distributions under heterogeneity. Since our setting contains T heterogeneous clusters of datapoints, our minimax error metric slightly different from the one studied in 266 6 27 2). Using the lg error as the loss,
the lower bound metric is defined as
inf
sup p' PP
E ||p' - p²
(3)
(w* MEE
(p"
of (P)
7

---

Minimax (global)
10
Minimax (local)
Average &a crror
Ours (median)
Ours (trim, mean)
10-3
10
0.1
0.5
1.0
1.5
2.0
50
50
100
150
300
x10
T
Figure 2: Average & estimation error in synthetic experiment. (Left): Fixing 8 = 5, 30 and varying (Middle): Fixing = 5, 100, 000 and varying T. (Right): Fixing 7 = 30, 100, 000 and varying s. The standard error bars are obtained from 10 independent runs.
where the supremum is taken over all possible central distributions p Pa and individual distribu- tions {p' : [2]} in IB, (p") {p E Pa: |p p' I s), and the infimum is taken over all esti- mation methods pi that use all heterogeneous messages (Y''J w J) : [m], L' E (T]} encoded (possibly interactively) by any encoding functions {w j [nl, E [T]) with output in 22)). e.g., the random hashing maps. The measure (3) characterizes the best possible worst-case performance of estimating distributions under our model heterogeneity.
Since the supremum is taken over all distributions p'.''.... in Pa such that -p'lo" S for all p' = [7 we consider two representative cases therein: 1) The homogeneous case where =p* Pa. Then the setting essentially reduces to the single-cluster problem but with nT datapoints, and the goal here is to estimate p' leading to the lower bound (2ddTn) 2) The s/2 s/2-sparse case where | S s/2 and | S s/2 for all t [T]. Then it naturally holds that (p' E [T]} S (p*). By constructing independent priors for (p' E [T]] and p', one can show that only datapoints generated by p' itself are informative for estimating p'. In this case, we show the lower bound Q(max (2", 8) (2))) Combining the two cases, we find the following lower bound. The formal argument provided in Appendix
Theorem 3. For any cny-possibly interactive esttimatiinnnnn method, and for any t [T], we have
"max(2", s} d El p p'1 =
inf (Hot Det
sup P EP, (p (ET
2'n
2
By similar argument but with an additional (T' + 1)-st cluster of ń users, we obtain a lower bound for adapting to a new cluster.
Theorem 4. For any possibly interactive essiimationnni method, and a new cluster CT+1, we have
max (2b, (2b,)) 8}
d
inf (Wthibl) w WTILI 7 (p" Tp" #'((++1)C..('"))
sup p' E E
(5)
2bn
2
Theorem and combined with the upper bounds in Section 3 imply that method is minimax optimal up to logarithmic terms. We provide similar lower bounds for the ε₁ error Appendix E
Experiments
We test SHIFT on synthetic data as well as the Shakespeare dataset 11]. As a baseline method, we use the estimator based on uniform grouping in (26) that is minimax optimal under homogeneity. i.e.. in the single-task regime. We apply the baseline method both locally and globally. In the local case, the estimator pe for each cluster computed without datapoints from other clusters. In the global case, we pool data from all clusters, and compute estimators P =p' _....
.....: = pT. The performance
measure for estimating p². e [T'] is taken T >T |pp' 1.

---

k 2
b= 2
b=
b= 6
6 8
Unif. Group. (local)
640 6.0
1.2
40 0.40
14
Unif. Group. (global)
33 1.8
1733
0.081
13 0.037
SHIFT (median)
2.4
0.66
0.17
0.10
SHIFT (trimmed mean)
36 2.2
19 0.51
0.24
10 0.062
==
b=
b=4
b=6
b=8
Unif. Group. (local)
15000 21
3.9
720
180 180 0.39
Unif. Group. (global)
4400 + 5.7
100 1.4
38 38 0.35
23 - 0.090
SHIFT (median)
7300 + 9.6
180 2.1
53 1.0
20 + 0.18
SHIFT (trimmed mean)
5100 + 6.3
140 2.3
43 = 0.66
0.18
Table 2: Average by error for estimating distributions of k--rams in the Shakespeare dataset. Numbers are scaled by 10-5.
5.1 Synthetic Data
We set the uniform distribution, p" (1/d..... 1/d). as the central distribution. Appendix F we also experiment on the truncated geometric distribution and compare method with the localization- refinement method [15). Among the entries of p". we draw s entries uniformly at random and assign new values for them uniformly at random over [0, 1J. with re-normalization to preserve their sum. We repeat this procedure T times to obtain sparsely perturbed distributions p' .....p"
Pa- Then, i..d. datapoints X ..... Xt. ~ Cat(p') are generated for each cluster t [T]. We set the dimension to 300 and run the simulation by varying n, T, s. As we see from 2 the error of method depends s only when 2 < For this reason, we let 2 in experiments.
We run SHIFT with the entry-wise median and entry-wise trimmed mean as the robust estimate. We set the threshold parameter a In(n) and the trimming proportion
0.1. In Appendix F. we provide results for other choices the hyperparameters a, w and discuss a heuristic for choosing Figure illustrates that our method outperforms the baselines for most choices of n, 8. Specifically, as Theorem [ predicts, the & error of our method decreases as the number of clusters 7 increases. On the other hand, when the baseline methods applied globally, without considering heterogeneity, they show a bias that does not disappear as the sample size n or the number of clusters T' increases. This shows that the fine-tuning step in SHIFT is crucial for the estimation of heterogeneous distributions. Finally, the right panel of Figure 2 shows that our method is effective only when is small compared to the dimension d; which highlights the crucial role of sparse heterogeneity. When s is close to d, the distributions p ...... p" could be considerably different without any meaningful central structure, making collaboration less useful than local estimation.
5.2 Shakespeare Dataset
The Shakespeare dataset was proposed as benchmark for federated learning in [I]. The dataset consists of dialogues of 1,129 speaking roles in Shakespeare's 's 35 different plays. In our experiment, we study the distribution of k-grams (k-tuples of consecutive letters from the 26-letter English alphabet, Chapter 3 of (33) appearing in the dialogues. We consider each play cluster C and estimate the distribution pd E Pa. d 26 of k-grams. Since the ground-truie distribution p' is unknown, regard the empirical frequency as p'.
To verify the heterogeneity, we run the chi-squared goodness-of-iee test for each pair distributions from distinct clusters pd and p". Resulting p-values were essentially zero within machine precision, which suggests that the distributions of k-grams are strongly heterogencous. We also perform entry- wise tests comparing pp"; and [p"], for all u * E [T], E [d]. In total, 25.8% of the tests were rejected at the significance level of 5%. This again supports the hetcrogeneity.
We draw n = 20, 000 datapoints with replacement from each cluster and test SHIFT with communica- tion budgets E {2, 4, 6, 8). We set the fine-tuning threshold = 0.1, which we choose following the heuristic discussed in Appendix(F We repeat the experiment ten times by taking different datapoints and report the average Ea error of estimation in Table The standard deviations are small even over ten repetitions. SHIFT shows competitive performance on the empirical dataset, even though we do not rigorously know if the sparse heterogeneity model applics.
in(n) and the trimming proportion

---

Conclusion and Future Directions
We formulate the problem of learning distributions under sparse heterogeneity and communication constraints. We propose the SHIFT method, which first learns a central distribution, and then fine- tunes the estimate adapt individual distributions. We provide both theoretical and experimental results to show its sample-efficiency improvement compared to classical methods that target only homogeneous data. Many interesting directions remain to be explored, including investigating there is point-wise optimal method with rate depending on (p' L E [T]} and p"; and designing methods for other information constraints, such as local differential privacy constraints.
Acknowledgements
During this work. Xinmeng Huang was supported part by the NSF TRIPODS 1934960, NSF DMS 2046874 (CAREER), NSF CAREER award CIF-1943064; Donghwan Lee was supported in part by ARO W911NF-20- --000, DCIST, Air Force Office of Scientific Research Young Investigator Program (AFOSR-YO YIP) award #FA9550-20-1-01111
References
[1] J. Acharya, C. L. Canonne, and H. Tyagi. General lower bounds for interactive high-dimensional estimation under information constraints. arXiv: Data Structures and Algorithms, 2020.
[2] J. Acharya, C. L.. Canonne, and H. Tyagi. Inference under information constraints ii: Com- munication constraints and shared randomness. IEEE Transactions on Information Theory, 66:7856-7877, 2020.
[3] J. Acharya, P. Kairouz, Y. Liu, and Z. Sun. Estimating sparse discrete distributions under privacy and communication constraints. In International Conference on Algorithmic Learning Theory, 2021.
[4] I. Achituve, A. Shamsian, A. Navon, G. Chechik, and Fetaya. Personalized federated learning with gaussian processes. ArXiv, 10//2200,,1488) 2021.
[5] M. F. Balcan, A. Blum, S. Fine, and Y. Mansour. Distributed learning, communication complex- ity and privacy. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 26.1-26.22, 2012.
[6] L. P. Barnes, Y. Han, and A. Ozgur. Lower bounds learning distributions under communica- tion constraints via fisher information. arXiv: Information Theory, 2019.
[7] H. Bastani. Predicting with proxies: Transfer learning in high dimension. Management Science, 67:2964-2984, 2021.
[8] J. Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149-198, 2000.
[9] P. Blanchard, E. M. E. Mhamdi, R. Guerraoui, and J. Stainer. Byzantine-tolerant machine learning. ArXiv, abs/1703.02257, 2017.
[10] H. D. Brunk, R. E. Barlow, D. J. Bartholomew, and J. M. Bremner. Statistical inference under order restrictions the theory and application of isotonic regression. International Statistical Review, 41:395, 1972.
[11] S. Caldas, S. M.M.K K. Duddu, P. Wu, T. J., Konečný, H. B. McMahan, V. Smith, and A. Talwalkar. Leaf: benchmark for federated settings. arXiv preprint arXiv: 181.0118/, 2018.
[12] R. Caruana.
Multitask learning. Machine Learning, 28:41-75, 1997.
[13] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the commuuniaatonn-prvvcyyaacacc
trilemma.
H. Larochelle, M. Ranzato, R. Hadsell, F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 3312-3324. Curran Associates, Inc., 2020.
10

---

[14] W.-N. Chen, P. Kairouz, and A. Ozgür. Breaking the dimension dependence in sparse distribution estimation under communication constraints. arXiv preprint arXiv:2106.08597, 2021.
[15] W.-N. Chen, P. Kairouz, and A. Özgür. Pointwise bounds for distribution estimation under communication constraints, ArXiv, abs/2110.03189, 2021.
[16] L. Collins, H. Hassani, A. Mokhtari, and S. Shakkottai. Exploiting shared representations for personalized federated learning. ArXiv, abs/2102.07078, 2021.
[17] H. Daumé, J. M. Phillips, A. Saha, and S. Venkatasubramannian Efficient protocols for dis- tributed classification and optimization. ArXiv, abs//104. 2012.
[18] L. Devroye and L. Györfi. Nonparametric density estimation the view. Journal of the American Stufistical Association, 82:344, 1987.
[19] L. Devroye and G. Lugosi. Combinatorial methods in density estimation. In Springer series in statistics, 2001.
[20] E. Dobriban and Y. Sheng. Distributed linear regression by averaging. The Annals of Statistics, 2018.
[21] S. Du, W. Hu, M. Kakade, Lee, and Q. Lei. Few-shot learning via learning the representation, provably. ArXiv, 094444 2021.
[22] A. Garg, T. Ma, and H. L. Nguyen. On communication cost of distributed statistical estimation and dimensionality. In Advances Neural Information Systems, 2014.
[23] Goyal, D. K. Mahajan, A. K. Gupta, and Misra. Scaling and benchmarking superviee visual representation learning. 2019 IEEE/CVF International Conference Computer Vision (ICCV), pages 6390-6399, 2019.
[24] F. Grimberg, M.-A. Hartley, S. P. Karimireddy, and M. Jaggi. Optimal model averaging: Towards personalized collaborative learning. ArXiv, 0bs/2210.1199 2021.
[25] Hampel, M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust statistics: the approach based on influence functions, volume 196. John Wiley & Sons, 2011.
[26] Y. Han, P. Mukherjee. A. Özgür, and T. Weissman. Distributed statistical estimation of high- dimensional and nonparametric distributions. 2018 IEEE International Symposium on Informa- tion Theory (ISIT), pages 506-510, 2018
[27] Y. Han, A. Özgür, and T. Weissman. Geometric lower bounds for distributed parameter estimation under communication constraints. IEEE Transactions on Information Theory, 17:248-8263. 2021.
[28] L. Hu, Jian, Cao, Gu. Q. Chen, and A. Amirbekyan. Hers: Modeling influential contexts with heterogeneous relations for sparse and cold-start recommendation. In The Thirty-Thirt AAAI Conference on Artificial Intelligence 2019.
[29] X. Huang, Chen, Yin, and K. Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[30] P. J. Huber. Robust statistics. Wiley Series in Probability and Mathematical Statistics, 1981.
[31] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. B. Charles, G. Cormode, Cummings, R. G. L. D'Oliveira, S. Y. E. Rouayheb, D. Evans,
J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, Javidi, G. Joshi, M. Khodak, J. Konecný, A. Korolova, F. Koushanfar, O. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. X. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q Yang, F. X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 2021.

---

[32] M. Lerasle and R. I. Oliveira. Robust empirical mean estimators. arXiv: Statistics Theory, 2011.
[33] J. Leskovec, A. Rajaraman, and D. Ullman. Mining of massive data sets. Cambridge university press, 2020.
[34] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of fedavg on non-iid data. ArXiv, abs/1907.00 02999,, 2020.
[35] T. Liu, Z. Wang, J. Tang, S. Yang, G. Y. Huang, and Z. Liu. Recommender systems with heterogeneous side information. The World Wide Web Conference, 2019.
[36] A. Maurer, M. Pontil, and Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17:81:1-81:32, 2016.
[37] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, 2017.
[38] S. Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, 2015.
[39] Minsker and N. Strawn. Distributed statistical estimation and rates of convergence in normal approximation. ArXiv, 2019.
[40]
Mullainathan and Z. Obermeyer. Does machine learning automate moral hazard and error? The American Economic Review, 10765):47-480,, 2017.
[41] R. D. Nowak. Distributed em algorithms for density estimation in sensor networks. International Conference on Acoustics, Speech, and Signal Processing, 2003.
[42] M. Qian, L. Hong, Y. Shi, and S. Rajan. Structured sparse regression for recommender systems. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015.
[43] J. Chionero-Candela M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset Shift in Machine Learning. MIT Press, 2009.
[44] A. Shamsian, A. Navon, E. Fetaya, and Chechik. Personalized federated learning using hypernetworks. In International Conference on Machine Learning, 2021.
[45] B. W. Silverman, Density estimation for statistics and data analysis. 1986.
London: Chapman Hall,
[46] V. Slavov and P. R. Rao. gossip- approach for internet-scale cardinality estimation of xpath queries over distributed semistructured data. The International Journal on Very Large Data Bases, 2013.
[47] V. Smith, C.-K. Chiang, M. Sanjabi, and A. S. Talwalkar. Federated multi-task learning. In Advances in neural information processing systems, 2017.
[48] I.. Su and N. H. Vaidya. Fault-tolerant multi-agent optimization: Optimal iterative distributed algorithms. In Proceedings of the 2016 ACM Symposium Principles of Distributed Computing, 2016.
[49] L. Su and N. H. Vaidya. Non-bayesian learning in the presence of byzantine agents. In International Symposium on Distributed Computing, pages 414-427, 2016.
[50] A. Subbaswamy and S. Saria. From development to deployment: dataset shift, causality, and shift-stable models in health ai. Biostatistics, 2019.
[51] C. Sun, A. Shrivastava, S. Singh, and A. K. Gupta. Revisiting unreasonable effectiveness of data in deep learning era. 2017 IEFE International Conference on Computer Vision (ICCV), pages 843-852, 2017.
12

---

[52] S. Thrun and L. Y. Pratt. Learning to learn: Introduction and overview. In Learning to Learn. Springer, 1998.
[53] N. Tripuraneni, C. Jin, and M. Jordan. Provable meta-learning linear representations. In International Conference Machine Learning. 2021.
[54] J. V. Uspensky. Introduction to mathematical probability. McGraw-Hill Book Company, 1937.
[55] R. Vershynin. High-Dinmesiooal Probability. 2018.
[56] D. Wang, Shi, Y. Zhu, and Z. Han. Federated analyties: Opportunities and challenges. IEEE Network, 2022.
[57] K. Xu and H. Bastani. Learning across bandits in high dimension via robust statistics. ArXiv, abs/21 1112112.1422 14233, 2021.
[58] D. Yin, Y. Chen, K. Ramchandran, and P. L. Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. ArXiv,
2018
[59] K. Yuan, S. A. Alghunaim, and X. Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. arXiv preprint (rxxi:2105.0800 2021.
[60] K. Yuan, Y. Chen, X. Huang, Y. Zhang, P. Pan, Y. Xu, and W. Yin. Decentlam: Decentralized momentum sgd for large-batch deep training. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
[61] M. Zhou, H. T. Shen, X. Zhou, W. Qian, and A. Zhou. Effective data density estimation in ring-based p2p networks. International Conference on Data Engineering, 2012.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "oxhKa6TztL", "reviewer": "Reviewer_yqYc", "summary": "The paper proposes a federated algorithm for efficiently estimating local data distributions with hashed messages to reduce communication costs, provided that there exists a central/global distribution such that the local ones differ from the global one in a number of bins/entries much smaller than the support size. The approach relies on a robust estimate of the global mass of an entry and it is shown to be minimax optimal wrt the estimation error of the local distributions when using the median estimator. The key intuition behind the approach is that the entries that vary the less between users are probably those that are homogeneous.\nAn empirical analysis both on synthetic and real datasets illustrate in which settings the method improves on global and local baselines, in particular when the communication budget b is sufficiently large. ", "questions": "1. Why does the encoding function $W^{t, j}$ depend also on the data point? In which cases is this function not given per user?\n2. How difficult would it be to extend the current results to continuous distributions?", "limitations": "The principal limitation of the work is in not considering privacy of the studied system. Even if it is out of the scope of the paper, it would be helpful to mention possible tools when working with sensitive data.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written. I cannot judge the novelty of the results as I am not familiar with the literature on distributed learning of discrete distributions.\n\nI have a few minor comments on the presentation:\n1. In the introduction, a good motivation is given for federated learning but not for learning data distributions in this context. It would be interesting to report some practical examples where it is more useful to estimate the local data distributions instead of local predictors, as the former has probably a higher privacy cost than the latter. Providing a stronger motivation would allow to better asses the impact of the contributions.\n2. It should be made clear from the beginning that only the problem of learning discrete distributions is tackled in the current work.\n3. When citing the works on federated multi-task learning, the following seminal work should be cited as well:\n- Smith, Virginia, et al. \"Federated multi-task learning.\" Advances in neural information processing systems 30 (2017).\n\nSpecific remarks and typos:\n1. line 28: Is performance drop observed in terms of time convergence or accuracy?\n2. line 79: What is it meant by shared randomness here?\n3. line 189: $n = \\Omega()$ -> $\\alpha = \\Omega()$?\n4. line 243: rest -> remaining\n5. line 269: What is it meant as prior in this context?\n6. line 304: sparsity -> sparse heterogeneity\n7. Figure 2: Why does the error of the proposed approach with the median estimator improve between s = 200 and s = 300?", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SLC0xttmo7n", "reviewer": "Reviewer_d6ap", "summary": "This paper proposed a new method for collaborative learning of categorical distribution when the data between users are heterogenous but only sparsely different in a few entries. The methods are composed of two steps: 1. collaborative learning of centralized hashed distribution by robust estimation over multiple agents; 2. fine tuning for each user, which is executed through threshold plus projection. The theoretical part of the paper shows the methods work well when there are lots of users and the difference are sparse. Futher, it states the median-based method is minimax optimal", "questions": "1. In theorem 1, how to interpret the notation $n=\\Omega(2^b \\ln(n))$ that has variable $n$ at both sides? $\\tilde{O}(\\cdot)$ there hide logarithmic factors with respect to which variables (should be datapoints $n$)? how to choose $\\alpha$ in practice?\n\n2. The proposed algorithm seems to be one-shot, i.e. processing all data at once. While in the reviewer's experience, the learning scenario is more common to be iterative or online style. That is the users or agents may continuously send one or multiple data to the central server. Is it worth to modify the algorithm to be caple of accepting the stream data or just iteratively updating the style? Or can authors provide more application cases when this batch-style processing is preferred?\n\n3. In the proof of proposition 2, it states that \".., it holds for $q=1, 2, \\mathbb{E}\\\\|x-x^\\star\\\\|^q_q$ = ...\". The first line of proof wrote \n\"$\\mathbb{E}\\\\|x-x^\\star\\\\|^q_q = \\sum_{k\\in[d]} \\mathbb{E} [|{\\rm Proj}(...) - {\\rm Proj}(...)|^q]$\", i.e., expanding to each entry. Why does it hold for $q=2$ case?\n", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The idea of the methods and the problem setting don't sound very novel to me. But the proof and theoretical part look \n\nQuality: The proof is mainly built upon the classical statistical framework, which looks solid to me.\n\nClarity:  From motivation to setup, from algorithm description to theoretical analysis, from notation to experiment setting, the paper is written in a good shape so that I think the readers can quickly grasp the core idea and technique.\n\nSignificance: I felt the scope of usage and problem setting are more or less limited. But I am conservative on this opinion since I may miss some important applications in practice.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0YGVv5k2Vdz", "reviewer": "Reviewer_6d3k", "summary": "The paper considers the estimation of d-dimensional distributions in a decentralized setting. Agents collaborate by sending messages to a central server, but their messages are limited to k bits and $2^k << d$. This setting was already studied by several authors, but the originality here is to allow sparse heterogeneity among agents.\n\nThe assumption is that there are $T$ distinct  but unknown d-dimensional distributions, and each agent is associated with one of the $T$ distributions. The set of agents is therefore partitioned into $T$ classes and, as far as I understand, the classes are known to the central server. Each class is characterized by a (small) set of components that have a distribution specific to it. All agents have exactly n samples drawn from their distribution. They send n messages. The ith message is a binary hash of the ith sample of length $k$.\n\nThe approach is the following. After receiving all messages, the server first performs a robust estimation of each component of the distributions, considering all the messages sent by all agents. Then it estimates for each cluster the components that are specific to a cluster and replace the global estimate by an estimate computed with the messages received by all agents in the same cluster.\n\nThe main results state that this 2 steps procedure is an upper and a lower bound on the estimation error (the l2 norm of the difference of the estimation and the true distribution) for each class. The upper bound contains a term that can be $T$ times smaller because of the collaboration across classes (possible for the estimation of the non-specific components). Another term depends on the sparsity value s rather than the dimension d for the specific components.\n\nWhile the proof can be a bit technical, the result is not surprising. The proof has essentially to control the weight of the errors due to the decoding of the hash functions in the restricted communication setting.\n\n", "questions": "1. In the main text the authors use the notation $n = \\Omega(2^b ln(n))$ which is clearly false (in the common acceptation of this asymptotic notation $\\Omega$, the Landau notation). In the appendix, it is written that $n$ should be larger than $2^{b+6} ln(n)$. It should be written like that in the main text.\n\n   But more importantly, the proof itself in appendix C1 starts considering  two cases that also misuse the Landau notation (Using $O$ and $\\Omega$).\n\n2. The setting should be more precise about the central server's knowledge of the problem and the agents. In particular, is the central server able to identify the cluster membership of the clients, the value of $T$, of $s$,...?\n\n3. In the lower bound part, two extreme cases are considered (homogeneous and s/2-sparse) and I don't understand why the lower bound can be expressed as the sum of these two cases (and not for instance the max of the two...)  \n", "limitations": "As explained above, the setting should be more precise about the central server's knowledge because it induces some limitations. ", "rating": 7, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n# Strengths\n- The setting is interesting and extends known results\n- There are original contributions in the proof\n- some experiments give an empirical evaluation of the proposed algorithm\n\n# Weaknesses\n1. The statement of the main theorems are not clear enough in the main text\n2. I also recommend clarifications in the exposition of the setting\n3. I have not understood the approach used in the lower bound\n\n\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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept