Randomized Distributed Mean Estimation: Accuracy vs Communication

Introduction

In particular, we consider a star network topology with a single server at the centre and $n$ nodes connected to it. All nodes send an encoded (possibly via a lossy randomized transformation) version of their vector to the server, after which the server performs a decoding operation to estimate the true mean

The purpose of the encoding operation is to compress the vector so as to save on communication cost, which is typically the bottleneck in practical applications.

To better illustrate the setup, consider the naive approach in which all nodes send the vectors without performing any encoding operation, followed by the application of a simple averaging decoder by the server. This results in zero estimation error at the expense of maximum communication cost of $ndr$ bits, where $r$ is the number of bits needed to communicate a single floating point entry/coordinate of $X_{i}$.

The distributed mean estimation problem was recently studied in a statistical framework where it is assumed that the vectors $X_{i}$ are independent and identicaly distributed samples from some specific underlying distribution. In such a setup, the goal is to estimate the true mean of the underlying distribution . These works formulate lower and upper bounds on the communication cost needed to achieve the minimax optimal estimation error.

In contrast, we do not make any statistical assumptions on the source of the vectors, and study the trade-off between expected communication costs and mean square error of the estimate. Arguably, this setup is a more robust and accurate model of the distributed mean estimation problems arising as subproblems in applications such as reduce-all operations within algorithms for distributed and federated optimization . In these applications, the averaging operations need to be done repeatedly throughout the iterations of a master learning/optimization algorithm, and the vectors $\{X_{i}\}$ correspond to updates to a global model/variable. In these applications, the vectors evolve throughout the iterative process in a complicated pattern, typically approaching zero as the master algorithm converges to optimality. Hence, their statistical properties change, which renders fixed statistical assumptions not satisfied in practice.

For instance, when training a deep neural network model in a distributed environment, the vector $X_{i}$ corresponds to a stochastic gradient based on a minibatch of data stored on node $i$. In this setup we do not have any useful prior statistical knowledge about the high-dimensional vectors to be aggregated. It has recently been observed that when communication cost is high, which is typically the case for commodity clusters, and even more so in a federated optimization framework, it is can be very useful to sacrifice on estimation accuracy in favor of reduced communication .

While the above already improves upon the state of the art, the improved results are in fact obtained for a suboptimal choice of the parameters of our method (constant probabilities $p_{ij}$, and node centers fixed to the mean $\mu_{i}$). One can decrease the MSE further by optimizing over the probabilities and/or node centers (see Section 6). However, apart from a very low communication cost regime in which we have a closed form expression for the optimal probabilities, the problem needs to be solved numerically, and hence we do not have expressions for how much improvement is possible. We illustrate the effect of fixed and optimal probabilities on the trade-off between communication cost and MSE experimentally on a few selected datasets in Section 6 (see Figure 1).

2 Outline

In Section 2 we formalize the concepts of encoding and decoding protocols. In Section 3 we describe a parametric family of randomized (and unbiased) encoding protocols and give a simple formula for the mean squared error. Subsequently, in Section 4 we formalize the notion of communication cost, and describe several communication protocols, which are optimal under different circumstances. We give simple instantiations of our protocol in Section 5, illustrating the trade-off between communication costs and accuracy. In Section 6 we address the question of the optimal choice of parameters of our protocol. Finally, in Section 7 we comment on possible extensions we leave out to future work.

Three Protocols

The objective of this work is to study the trade-off between the (expected) number of bits that need to be communicated, and the accuracy of $Y$ as an estimate of $X$.

In this work we focus on encoders which are unbiased, in the following sense.

We say that encoder $\alpha$ is unbiased if ${\bf E}_{\alpha}\left[\alpha(X_{i})\right]=X_{i}$ for all $i=1,2,\dots,n$. We say that it is independent, if $\alpha(X_{i})$ is independent from $\alpha(X_{j})$ for all $i\neq j$.

A trivial example of an encoding protocol is the identity function: $\alpha(X_{i})=X_{i}$. It is both unbiased and independent. This encoder does not lead to any savings in communication that would be otherwise infeasible though.

We now formalize the notion of accuracy of estimating $X$ via $Y$. Since $Y$ can be random, the notion of accuracy will naturally be probabilistic.

The mean squared error of protocol $(\alpha,\gamma)$ is the quantity

To illustrate the above concept, we now give a few examples:

If $\gamma$ is the averaging function, i.e., $\gamma(Y_{1},\dots,Y_{n})=\frac{1}{n}\sum_{i=1}^{n}Y_{i},$ then

The next example generalizes the identity encoder and averaging decoder.

and hence the MSE of $(\alpha,\gamma)$ is zero.

We shall now prove a simple result for unbiased and independent encoders used in subsequent sections.

If the encoder $\alpha$ is unbiased and independent, and $\gamma$ is the averaging decoder, then

Note that ${\bf E}_{\alpha}\left[Y_{i}\right]=X_{i}$ for all $i$. We have

where (*) follows from unbiasedness and (**) from independence. ∎

One may wish to define the encoder as a combination of two or more separate encoders: $\alpha(X_{i})=\alpha_{2}(\alpha_{1}(X_{i}))$. See for an example where $\alpha_{1}$ is a random rotation and $\alpha_{2}$ is binary quantization.

A Family of Randomized Encoding Protocols

We shall define support of $\alpha$ on node $i$ to be the set $S_{i}\overset{\text{def}}{=}\{j\;:\;Y_{i}(j)\neq\mu_{i}\}$. We now define two parametric families of randomized encoding protocols. The first results in $S_{i}$ of random size, the second has $S_{i}$ of a fixed size.

With each pair $(i,j)$ we associate a parameter $0<p_{ij}\leq 1$, representing a probability. The collection of parameters $\{p_{ij},\mu_{i}\}$ defines an encoding protocol $\alpha$ as follows:

Enforcing the probabilities to be positive, as opposed to nonnegative, leads to vastly simplified notation in what follows. However, it is more natural to allow $p_{ij}$ to be zero, in which case we have $Y_{i}(j)=\mu_{i}$ with probability 1. This raises issues such as potential lack of unbiasedness, which can be resolved, but only at the expense of a larger-than-reasonable notational overload.

In the rest of this section, let $\gamma$ be the averaging decoder (Example 2). Since $\gamma$ is fixed and deterministic, we shall for simplicity write ${\bf E}_{\alpha}\left[\cdot\right]$ instead of ${\bf E}_{\alpha,\gamma}\left[\cdot\right]$. Similarly, we shall write $MSE_{\alpha}(\cdot)$ instead of $MSE_{\alpha,\gamma}(\cdot)$.

We now prove two lemmas describing properties of the encoding protocol $\alpha$. Lemma 3.1 states that the protocol yields an unbiased estimate of the average $X$ and Lemma 3.2 provides the expected mean square error of the estimate.

The encoder $\alpha$ defined in (1) is unbiased. That is, ${\bf E}_{\alpha}\left[\alpha(X_{i})\right]=X_{i}$ for all $i$. As a result, $Y$ is an unbiased estimate of the true average: ${\bf E}_{\alpha}\left[Y\right]=X$.

Due to linearity of expectation, it is enough to show that ${\bf E}_{\alpha}\left[Y(j)\right]=X(j)$ for all $j$. Since $Y(j)=\frac{1}{n}\sum_{i=1}^{n}Y_{i}(j)$ and $X(j)=\frac{1}{n}\sum_{i=1}^{n}X_{i}(j)$, it suffices to show that ${\bf E}_{\alpha}\left[Y_{i}(j)\right]=X_{i}(j)$:

Let $\alpha=\alpha(p_{ij},\mu_{i})$ be the encoder defined in (1). Then

It suffices to substitute the above into (3). ∎

2 Encoding Protocol with Fixed-size Support

Here we propose an alternative encoding protocol, one with deterministic support size. As we shall see later, this results in deterministic communication cost.

Let $\sigma_{k}(d)$ denote the set of all subsets of $\{1,2,\dots,d\}$ containing $k$ elements. The protocol $\alpha$ with a single integer parameter $k$ is then working as follows: First, each node $i$ samples $\mathcal{D}_{i}\in\sigma_{k}(d)$ uniformly at random, and then sets

Note that due to the design, the size of the support of $Y_{i}$ is always $k$, i.e., $|S_{i}|=k$. Naturally, we can expect this protocol to perform practically the same as the protocol (1) with $p_{ij}=k/d$, for all $i,j$. Lemma 3.4 indeed suggests this is the case. While this protocol admits a more efficient communication protocol (as we shall see in Section ), protocol (1) enjoys a larger parameters space, ultimately leading to better MSE. We comment on this tradeoff in subsequent sections.

As for the data-dependent protocol, we prove basic properties. The proofs are similar to those of Lemmas 3.1 and 3.2 and we defer them to Appendix A.

The encoder $\alpha$ defined in (1) is unbiased. That is, ${\bf E}_{\alpha}\left[\alpha(X_{i})\right]=X_{i}$ for all $i$. As a result, $Y$ is an unbiased estimate of the true average: ${\bf E}_{\alpha}\left[Y\right]=X$.

Let $\alpha=\alpha(k)$ be encoder defined as in (4). Then

Communication Protocols

Having defined the encoding protocols $\alpha$, we need to specify the way the encoded vectors $Y_{i}=\alpha(X_{i})$, for $i=1,2,\dots,n$, are communicated to the server. Given a specific communication protocol $\beta$, we write $\beta(Y_{i})$ to denote the (expected) number of bits that are communicated by node $i$ to the server. Since $Y_{i}=\alpha(X_{i})$ is in general not deterministic, $\beta(Y_{i})$ can be a random variable.

The communication cost of communication protocol $\beta$ under randomized encoding $\alpha$ is the total expected number of bits transmitted to the server:

Given $Y_{i}$, a good communication protocol is able to encode $Y_{i}=\alpha(X_{i})$ using a few bits only. Let $r$ denote the number of bits used to represent a floating point number. Let $\bar{r}$ be the the number of bits representing $\mu_{i}$.

In the rest of this section we describe several communication protocols $\beta$ and calculate their communication cost.

Represent $Y_{i}=\alpha(X_{i})$ as $d$ floating point numbers. Then for all encoding protocols $\alpha$ and all $i$ we have $\beta(\alpha(X_{i}))=dr$, whence

2 Varying-length

We will use a single variable for every element of the vector $Y_{i}$, which does not have constant size. The first bit decides whether the value represents $\mu_{i}$ or not. If yes, end of variable, if not, next $r$ bits represent the value of $Y_{i}(j)$. In addition, we need to communicate $\mu_{i}$, which takes $\bar{r}$ bitsThe distinction here is because $\mu_{i}$ can be chosen to be data independent, such as , so we don’t have to communicate anything (i.e., $\bar{r}=0$). We thus have

where $1_{e}$ is the indicator function of event $e$. The expected number of bits communicated is given by

In the special case when $p_{ij}=p>0$ for all $i,j$, we get

3 Sparse Communication Protocol for Encoder (1)

We can represent $Y_{i}$ as a sparse vector; that is, a list of pairs $(j,Y_{i}(j))$ for which $Y_{i}(j)\neq\mu_{i}$. The number of bits to represent each pair is $\lceil\log(d)\rceil+r$. Any index not found in the list, will be interpreted by server as having value $\mu_{i}$. Additionally, we have to communicate the value of $\mu_{i}$ to the server, which takes $\bar{r}$ bits. We assume that the value $d$, size of the vectors, is known to the server. Hence,

Summing up through $i$ and taking expectations, the the communication cost is given by

In the special case when $p_{ij}=p>0$ for all $i,j$, we get

A practical improvement upon this could be to (without loss of generality) assume that the pairs $(j,Y_{i}(j))$ are ordered by $j$, i.e., we have $\{(j_{s},Y_{i}(j_{s}))\}_{s=1}^{k}$ for some $k$ and $j_{1}<j_{2}<\dots<j_{k}$. Further, let us denote $j_{0}=0$. We can then use a variant of variable-length quantity to represent the set $\{(j_{s}-j_{s-1},Y_{i}(j_{s}))\}_{s=1}^{k}$. With careful design one can hope to reduce the $\log(d)$ factor in the average case. Nevertheless, this does not improve the worst case analysis we focus on in this paper, and hence we do not delve deeper in this.

4 Sparse Communication Protocol for Encoder (4)

We now describe a sparse communication protocol compatible only with fixed length encoder defined in (4). Note that subset selection can be compressed in the form of a random seed, letting us avoid the $\log(d)$ factor in (8). This includes the protocol defined in (4) but also (1) with uniform probabilities $p_{ij}$.

In particular, we can represent $Y_{i}$ as a sparse vector containing the list of the values for which $Y_{i}(j)\neq\mu_{i}$, ordered by $j$. Additionally, we need to communicate the value $\mu_{i}$ (using $\bar{r}$ bits) and a random seed (using $\bar{r}_{s}$ bits), which can be used to reconstruct the indices $j$, corresponding to the communicated values. Note that for any fixed $k$ defining protocol (4), we have $|S_{i}|=k$. Hence, communication cost is deterministic:

In the case of the variable-size-support encoding protocol (1) with $p_{ij}=p>0$ for all $i,j$, the sparse communication protocol described here yields expected communication cost

5 Binary

If the elements of $Y_{i}$ take only two different values, $Y_{i}^{min}$ or $Y_{i}^{max}$, we can use a binary communication protocol. That is, for each node $i$, we communicate the values of $Y_{i}^{min}$ and $Y_{i}^{max}$ (using $2r$ bits), followed by a single bit per element of the array indicating whether $Y_{i}^{max}$ or $Y_{i}^{min}$ should be used. The resulting (deterministic) communication cost is

6 Discussion

In the above, we have presented several communication protocols of different complexity. However, it is not possible to claim any of them is the most efficient one. Which communication protocol is the best, depends on the specifics of the used encoding protocol. Consider the extreme case of encoding protocol (1) with $p_{ij}=1$ for all $i,j$. The naive communication protocol is clearly the most efficient, as all other protocols need to send some additional information.

However, in the interesting case when we consider small communication budget, the sparse communication protocols are the most efficient. Therefore, in the following sections, we focus primarily on optimizing the performance using these protocols.

Examples

In this section, we highlight on several instantiations of our protocols, recovering existing techniques and formulating novel ones. We comment on the resulting trade-offs between communication cost and estimation error.

We start by recovering an existing method, which turns every element of the vectors $X_{i}$ into a particular binary representation.

If we set the parameters of protocol (1) as $\mu_{i}=X_{i}^{min}$ and $p_{ij}=\frac{X_{i}(j)-X_{i}^{min}}{\Delta_{i}}$, where $\Delta_{i}\overset{\text{def}}{=}X_{i}^{max}-X_{i}^{min}$ (assume, for simplicity, that $\Delta_{i}\neq 0$), we exactly recover the quantization algorithm proposed in :

Using the formula (2) for the encoding protocol $\alpha$, we get

This exactly recovers the MSE bound established in [10, Theorem 1]. Using the binary communication protocol yields the communication cost of $1$ bit per element if $X_{i}$, plus a two real-valued scalars (11).

If we use the above protocol jointly with randomized linear encoder and decoder (see Example 3), where the linear transform is the randomized Hadamard transform, we recover the method described in [10, Section 3] which yields improved $MSE_{\alpha}=\frac{2\log d+2}{n}\cdot\frac{1}{n}\sum_{i=1}^{n}\|X_{i}\|^{2}$ and can be implemented in $\mathcal{O}(d\log d)$ time.

2 Sparse Communication Protocols

Now we move to comparing the communication costs and estimation error of various instantiations of the encoding protocols, utilizing the deterministic sparse communication protocol and uniform probabilities.

For the remainder of this section, let us only consider instantiations of our protocol where $p_{ij}=p>0$ for all $i,j$, and assume that the node centers are set to the vector averages, i.e., $\mu_{i}=\frac{1}{d}\sum_{j=1}^{d}X_{i}(j)$. Denote $R=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{d}(X_{i}(j)-\mu_{i})^{2}$. For simplicity, we also assume that $|S|=nd$, which is what we can in general expect without any prior knowledge about the vectors $X_{i}$.

The properties of the following examples follow from Equations (2) and (10). When considering the communication costs of the protocols, keep in mind that the trivial benchmark is $C_{\alpha,\beta}=ndr$, which is achieved by simply sending the vectors unmodified. Communication cost of $C_{\alpha,\beta}=nd$ corresponds to the interesting special case when we use (on average) one bit per element of each $X_{i}$.

In this case, the encoding protocol is lossless, which ensures $MSE=0$. Note that in this case, we could get rid of the $n(\bar{r}_{s}+\bar{r})$ factor by using naive communication protocol.

This protocol order-wise matches the $MSE$ of the method in Remark 3. However, as long as $d>2^{r}$, this protocol attains this error with smaller communication cost. In particular, this is on expectation less than a single bit per element of $X_{i}$. Finally, note that the factor $R$ is always smaller or equal to the factor $\frac{1}{n}\sum_{i=1}^{n}\|X_{i}\|^{2}$ appearing in Remark 3.

This protocol communicates on expectation single bit per element of $X_{i}$ (plus additional $\bar{r}_{s}+\bar{r}$ bits per client), while attaining bound on $MSE$ of $\mathcal{O}(r/n)$. To the best of out knowledge, this is the first method to attain this bound without additional assumptions.

If we choose $p=\frac{d-\bar{r}_{s}-\bar{r}}{dr}$, we get

This alternative protocol attains on expectation exactly single bit per element of $X_{i}$, with (a slightly more complicated) $\mathcal{O}(r/n)$ bound on $MSE$.

This protocol attains the MSE of protocol in Example 4 while at the same time communicating on average significantly less than a single bit per element of $X_{i}$.

Using the deterministic sparse protocol, there is an obvious lower bound on the communication cost — $n(\bar{r}_{s}+\bar{r})$. We can bypass this threshold by using the sparse protocol, with a data-independent choice of $\mu_{i}$, such as , setting $\bar{r}=0$. By setting $p=\epsilon/d(\lceil\log d\rceil+r)$, we get arbitrarily small expected communication cost of $C_{\alpha,\beta}=\epsilon$, and the cost of exploding estimation error $MSE_{\alpha,\gamma}=\mathcal{O}(1/\epsilon n)$.

Note that all of the above examples have random communication costs. What we present is the expected communication cost of the protocols. All the above examples can be modified to use the encoding protocol with fixed-size support defined in $\eqref{eq:randomized_protocol_2}$ with the parameter $k$ set to the value of $pd$ for corresponding $p$ used above, to get the same results. The only practical difference is that the communication cost will be deterministic for each node, which can be useful for certain applications.

Optimal Encoders

Here we consider $(\alpha,\beta,\gamma)$, where $\alpha=\alpha(p_{ij},\mu_{i})$ is the encoder defined in (1), $\beta$ is the associated the sparse communication protocol, and $\gamma$ is the averaging decoder. Recall from Lemma 2 and (8) that the mean square error and communication cost are given by:

Having these closed-form formulae as functions of the parameters $\{p_{ij},\mu_{i}\}$, we can now ask questions such as:

Given a communication budget, which encoding protocol has the smallest mean squared error?

Given a bound on the mean squared error, which encoder suffers the minimal communication cost?

Let us now address the first question; the second question can be handled in a similar fashion. In particular, consider the optimization problem

where $B>0$ represents a bound on the part of the total communication cost in (13) which depends on the choice of the probabilities $p_{ij}$.

Note that while the constraints in (15) are convex (they are linear), the objective is not jointly convex in $\{p_{ij},\mu_{i}\}$. However, the objective is convex in $\{p_{ij}\}$ and convex in $\{\mu_{i}\}$. This suggests a simple alternating minimization heuristic for solving the above problem:

Fix the probabilities and optimize over the node centers,

Fix the node centers and optimize over probabilities.

These two steps are repeated until a suitable convergence criterion is reached. Note that the first step has a closed form solution. Indeed, the problem decomposes across the node centers to $n$ univariate unconstrained convex quadratic minimization problems, and the solution is given by

The second step does not have a closed form solution in general; we provide an analysis of this step in Section 6.1.

Note that the upper bound $\sum_{i,j}(X_{i}(j)-\mu_{i})^{2}/p_{ij}$ on the objective is jointly convex in $\{p_{ij},\mu_{i}\}$. We may therefore instead optimize this upper bound by a suitable convex optimization algorithm.

An alternative and a more practical model to (15) is to choose per-node budgets $B_{1},\dots,B_{n}$ and require $\sum_{j}p_{ij}\leq B_{i}$ for all $i$. The problem becomes separable across the nodes, and can therefore be solved by each node independently. If we set $B=\sum_{i}B_{i}$, the optimal solution obtained this way will lead to MSE which is lower bpunded by the MSE obtained through (15).

Let the node centers $\mu_{i}$ be fixed. Problem (15) (or, equivalently, step 2 of the alternating minimization method described above) then takes the form

Let $S=\{(i,j)\;:\;X_{i}(j)\neq\mu_{i}\}$. Notice that as long as $B\geq|S|$, the optimal solution is to set $p_{ij}=1$ for all $(i,j)\in S$ and $p_{ij}=0$ for all $(i,j)\notin S$.We interpret $0/0$ as and do not worry about infeasibility. These issues can be properly formalized by allowing $p_{ij}$ to be zero in the encoding protocol and in (6.1). However, handling this singular situation requires a notational overload which we are not willing to pay. In such a case, we have $MSE_{\alpha,\gamma}=0.$ Hence, we can without loss of generality assume that $B\leq|S|$.

While we are not able to derive a closed-form solution to this problem, we can formulate upper and lower bounds on the optimal estimation error, given a bound on the communication cost formulated via $B$.

Consider problem (6.1) and fix any $B\leq|S|$. Using the sparse communication protocol $\beta$, the optimal encoding protocol $\alpha$ has communication complexity

and the mean squared error satisfies the bounds

where $R=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{d}(X_{i}(j)-\mu_{i})^{2}=\frac{1}{n}\sum_{i=1}^{n}\|X_{i}-\mu_{i}1\|^{2}$. Let $a_{ij}=|X_{i}(j)-\mu_{i}|$ and $W=\sum_{i,j}a_{ij}$. If, moreover, $B\leq\sum_{(i,j)\in S}a_{ij}/\max_{(i,j)\in S}a_{ij}$ (which is true, for instance, in the ultra-low communication regime with $B\leq 1$), then

Setting $p_{ij}=B/|S|$ for all $(i,j)\in S$ leads to a feasible solution of (6.1). In view of (13), one then has

where $R=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{d}(X_{i}(j)-\mu_{i})^{2}=\frac{1}{n}\sum_{i=1}^{n}\|X_{i}-\mu_{i}1\|^{2}$.

If we relax the problem by removing the constraints $p_{ij}\leq 1$, the optimal solution satisfies $a_{ij}/p_{ij}=\theta>0$ for all $(i,j)\in S$. At optimality the bound involving $B$ must be tight, which leads to $\sum_{(i,j)\in S}a_{ij}/\theta=B$, whence $\theta=\tfrac{1}{B}\sum_{(i,j)\in S}a_{ij}$. So, $p_{ij}=a_{ij}B/\sum_{(i,j)\in S}a_{ij}$. The optimal MSE therefore satisfies the lower bound

where $W\overset{\text{def}}{=}\sum_{(i,j)\in S}a_{ij}\geq\left(\sum_{(i,j)\in S}a_{ij}^{2}\right)^{1/2}=(nR)^{1/2}$. Therefore, $MSE_{\alpha,\gamma}\geq\left(\frac{1}{B}-1\right)\frac{R}{n}$. If $B\leq\sum_{(i,j)\in S}a_{ij}/\max_{(i,j)\in S}a_{ij}$, then $p_{ij}\leq 1$ for all $(i,j)\in S$, and hence we have optimality. (Also note that, by Cauchy-Schwarz inequality, $W^{2}\leq nR|S|$.) ∎

2 Trade-off Curves

To illustrate the trade-offs between communication cost and estimation error (MSE) achievable by the protocols discussed in this section, we present simple numerical examples in Figure 1, on three synthetic data sets with $n=16$ and $d=512$. We choose an array of values for $B$, directly bounding the communication cost via (18), and evaluate the $MSE$ (2) for three encoding protocols (we use the sparse communication protocol and averaging decoder). All these protocols have the same communication cost, and only differ in the selection of the parameters $p_{ij}$ and $\mu_{i}$. In particular, we consider

uniform probabilities $p_{ij}=p>0$ with average node centers $\mu_{i}=\frac{1}{d}\sum_{j=1}^{d}X_{i}(j)$ (blue dashed line),

optimal probabilities $p_{ij}$ with average node centers $\mu_{i}=\frac{1}{d}\sum_{j=1}^{d}X_{i}(j)$ (green dotted line), and

optimal probabilities with optimal node centers, obtained via the alternating minimization approach described above (red solid line).

In order to put a scale on the horizontal axis, we assumed that $r=16$. Note that, in practice, one would choose $r$ to be as small as possible without adversely affecting the application utilizing our distributed mean estimation method. The three plots represent $X_{i}$ with entries drawn in an i.i.d. fashion from Gaussian ($\mathcal{N}(0,1)$), Laplace ($\mathcal{L}(0,1)$) and chi-squared ($\chi^{2}(2)$) distributions, respectively. As we can see, in the case of non-symmetric distributions, it is not necessarily optimal to set the node centers to averages.

As expected, for fixed node centers, optimizing over probabilities results in improved performance, across the entire trade-off curve. That is, the curve shifts downwards. In the first two plots based on data from symmetric distributions (Gaussian and Laplace), the average node centers are nearly optimal, which explains why the red solid and green dotted lines coalesce. This can be also established formally. In the third plot, based on the non-symmetric chi-squared data, optimizing over node centers leads to further improvement, which gets more pronounced with increased communication budget. It is possible to generate data where the difference between any pair of the three trade-off curves becomes arbitrarily large.

Finally, the black cross represents performance of the quantization protocol from Example 4. This approach appears as a single point in the trade-off space due to lack of any parameters to be fine-tuned.

Further Considerations

In this section we outline further ideas worth consideration. However, we leave a detailed analysis to future work.

We can generalize the binary encoding protocol (1) to a $k$-ary protocol. To illustrate the concept without unnecessary notation overload, we present only the ternary (i.e., $k=3$) case.

Let the collection of parameters $\{p^{\prime}_{ij},p^{\prime\prime}_{ij},\bar{X}^{\prime}_{i},\bar{X}^{\prime\prime}_{i}\}$ define an encoding protocol $\alpha$ as follows:

It is straightforward to generalize Lemmas 3.1 and 3.2 to this case. We omit the proofs for brevity.

The encoder $\alpha$ defined in (21) is unbiased. That is, ${\bf E}_{\alpha}\left[\alpha(X_{i})\right]=X_{i}$ for all $i$. As a result, $Y$ is an unbiased estimate of the true average: ${\bf E}_{\alpha}\left[Y\right]=X$.

Let $\alpha=\alpha\left(p^{\prime}_{ij},p^{\prime\prime}_{ij},\bar{X}^{\prime}_{i},\bar{X}^{\prime\prime}_{i}\right)$ be the protocol defined in (21). Then

We expect the $k$-ary protocol to lead to better (lower) MSE bounds, but at the expense of an increase in communication cost. Whether or not the trade-off offered by $k>2$ is better than that for the $k=2$ case investigated in this paper is an interesting question to consider.

2 Preprocessing via Random Rotations

Following the idea proposed in , one can explore an encoding protocol $\alpha_{Q}$ which arises as the composition of a random rotation, $Q$, applied to $X_{i}$ for all $i$, followed by the protocol $\alpha$ described in Section 3. Letting $Z_{i}=QX_{i}$ and $Z=\frac{1}{n}\sum_{i}Z_{i}$, we thus have

With this protocol we associate the decoder $\gamma(Y_{1},\dots,Y_{n})=\frac{1}{n}\sum_{i=1}^{n}Q^{-1}Y_{i}.$

This approach is motivated by the following observation: a random rotation can be identified by a single random seed, which is easy to communicate to the server without the need to communicate all floating point entries defining $Q$. So, a random rotation pre-processing step implies only a minor communication overhead. However, if the preprocessing step helps to dramatically reduce the MSE, we get an improvement. Note that the inner expectation above is the formula for MSE of our basic encoding-decoding protocol, given that the data is $Z_{i}=QX_{i}$ instead of $\{X_{i}\}$. The outer expectation is over $Q$. Hence, we would like the to find a mapping $Q$ which tends to transform the data $\{X_{i}\}$ into new data $\{Z_{i}\}$ with better MSE, in expectation.

where $\bar{x}=\tfrac{1}{d}\sum_{j}x(j)$ and $1$ is the vector of all ones. Further, for simplicity assume that $p_{ij}=p$ for all $i,j$. Then using Lemma 3.2, we get

It is interesting to investigate whether choosing $Q$ as a random rotation, rather than identity (which is the implicit choice done in previous sections), leads to improvement in MSE, i.e., whether we can in some well-defined sense obtain an inequality of the type

This is the case for the quantization protocol proposed in , which arises as a special case of our more general protocol. This is because the quantization protocol is suboptimal within our family of encoders. Indeed, as we have shown, with a different choice of the parameter we can obtained results which improve, in theory, on the rotation + quantization approach. This suggests that perhaps combining an appropriately chosen rotation pre-processing step with our optimal encoder, it may be possible to achieve further improvements in MSE for any fixed communication budget. Finding suitable random rotations $Q$ requires a careful study which we leave to future research.

References

Appendix A Additional Proofs

In this section we provide proofs of Lemmas 3.3 and 3.4, describing properties of the encoding protocol $\alpha$ defined in (4). For completeness, we also repeat the statements.

The encoder $\alpha$ defined in (1) is unbiased. That is, ${\bf E}_{\alpha}\left[\alpha(X_{i})\right]=X_{i}$ for all $i$. As a result, $Y$ is an unbiased estimate of the true average: ${\bf E}_{\alpha}\left[Y\right]=X$.

Since $Y(j)=\frac{1}{n}\sum_{i=1}^{n}Y_{i}(j)$ and $X(j)=\frac{1}{n}\sum_{i=1}^{n}X_{i}(j)$, it suffices to show that ${\bf E}_{\alpha}\left[Y_{i}(j)\right]=X_{i}(j)$:

Let $\alpha=\alpha(k)$ be encoder defined as in (4). Then

It suffices to substitute the above into (22). ∎