# Optimal Communication for Classic Functions in the Coordinator Model and
Beyond

Hossein Esfandiari
Google Research
<EMAIL_ADDRESS>Praneeth Kacham
CMU
<EMAIL_ADDRESS>Vahab Mirrokni
Google Research
<EMAIL_ADDRESS>David P. Woodruff
CMU
<EMAIL_ADDRESS>Peilin Zhong
Google Research
<EMAIL_ADDRESS>
In the coordinator model of communication with $s$ servers, given an arbitrary
non-negative function $f$, we study the problem of approximating the sum
$\sum_{i\in[n]}f(x_{i})$ up to a $1\pm\varepsilon$ factor. Here the vector
$x\in\mathbb{R}^{n}$ is defined to be $x=x(1)+\cdots+x(s)$, where $x(j)\geq 0$
denotes the non-negative vector held by the $j$-th server. A special case of
the problem is when $f(x)=x^{k}$ which corresponds to the well-studied problem
of $F_{k}$ moment estimation in the distributed communication model. We
introduce a new parameter $c_{f}[s]$ which captures the communication
complexity of approximating $\sum_{i\in[n]}f(x_{i})$ and for a broad class of
functions $f$ which includes $f(x)=x^{k}$ for $k\geq 2$ and other robust
functions such as the Huber loss function, we give a two round protocol that
uses total communication $c_{f}[s]/\varepsilon^{2}$ bits, up to
polylogarithmic factors. For this broad class of functions, our result
improves upon the communication bounds achieved by Kannan, Vempala, and
Woodruff (COLT 2014) and Woodruff and Zhang (STOC 2012), obtaining the optimal
communication up to polylogarithmic factors in the minimum number of rounds.
We show that our protocol can also be used for approximating higher-order
correlations. Our results are part of a broad framework for optimally sampling
from a joint distribution in terms of the marginal distributions held on
individual servers.

Apart from the coordinator model, algorithms for other graph topologies in
which each node is a server have been extensively studied. We argue that
directly lifting protocols from the coordinator model to other graph
topologies will require some nodes in the graph to send a lot of
communication. Hence, a natural question is the type of problems that can be
efficiently solved in general graph topologies. We address this question by
giving communication efficient protocols in the so-called personalized CONGEST
model for solving linear regression and low rank approximation by designing
_composable sketches_. Our sketch construction may be of independent interest
and can implement any importance sampling procedure that has a _monotonicity_
property.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Our Techniques
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Exponential Random Variables
  3. 3 Sampling from Additively-Defined Distributions
  4. 4 A Two Round Protocol for Sum Approximation
    1. 4.1 The coordinate $i^{*}$ is sampled
    2. 4.2 Computing the set PL
      1. 4.2.1 Contribution from Large servers
      2. 4.2.2 Contribution from Small servers
      3. 4.2.3 Contribution from Remaining Servers
      4. 4.2.4 Algorithm to compute $\hat{x}_{i}$
    3. 4.3 Higher-Order Correlations
  5. 5 Lower Bounds
    1. 5.1 Lower Bound for Sum Approximation
    2. 5.2 $F_{k}$ Estimation Lower Bound for 1-round Algorithms
  6. 6 Neighborhood Propagation via Composable Sketches
  7. 7 Composable Sketches for Sensitivity Sampling
    1. 7.1 $\ell_{p}$ Sensitivity Sampling
    2. 7.2 Sketch Creation
    3. 7.3 Merging Sketches
      1. 7.3.1 Proof Outline
      2. 7.3.2 Formal Proof
    4. 7.4 Neighborhood Propagation
    5. 7.5 Applications to $\ell_{p}$ Regression
    6. 7.6 Low Rank Approximation
  8. A Gap in the analysis of [29]
  9. B Huber Loss Function
    1. B.1 Super-additivity
    2. B.2 Bounding $c_{f}[s]$
  10. C Derandomizing Exponential Random Variables using Nisan’s PRG

##  1 Introduction

In modern applications data is often distributed across multiple servers and
communication is a bottleneck. This motivates minimizing the communication
cost for solving classical functions of interest. A standard model of
distributed computation is the coordinator or message-passing model, in which
there are $s$ servers, each with an input, and a coordinator with no input.
All communication goes through the coordinator, who decides who speaks next.
This models arbitrary point-to-point communication up to a multiplicative
factor of $2$ and an additive $\lceil\log_{2}(\text{\\# of servers})\rceil$
bits per message, since the coordinator can forward a message from server $i$
to server $j$ provided $i$ indicates which server should receive the message.
The coordinator model is also useful in distributed functional monitoring
[14]. Numerous functions have been studied in the coordinator model, such as
bitwise operations on vectors [38], set-disjointness [3], graph problems [42],
statistical problems [42], and many more.

In the coordinator model, we measure the efficiency of a protocol by looking
at the following: (i) the overall number of bits of communication required by
the protocol and (ii) the number of rounds of communication in the protocol.
In each round of communication, each of the servers sends a message to the
coordinator based on their input and messages from the coordinator in previous
rounds. Based on the messages received from all the servers in this round and
earlier rounds, the coordinator sends a possibly distinct message to each of
the servers. Thus, in a protocol with one round, each of the servers sends a
message to the coordinator based _only_ on their inputs and the coordinator
has to compute the output based only on these messages. We additionally assume
that all the servers and the coordinator have access to a shared source of
randomness which they can use to sample shared random variables.

We revisit classical entrywise function approximation, which includes the
$F_{k}$ moment estimation as a special case. Surprisingly, despite the
simplicity of the coordinator model and the optimal bounds known for such
functions in related models such as the streaming model, the optimal
communication complexity of computing or approximating such functions in the
coordinator model is open. In the $F_{k}$ moment estimation problem there are
$s$ players, the $j$-th of which holds a non-negative vector111If the vectors
are allowed to have negative entries, then there is an $\Omega(n^{1-2/k})$ bit
lower bound on the amount of communication when $k>2$ [5].
$x(j)\in\mathbb{R}^{n}$, and the goal is to, with constant probability, output
a $(1+\varepsilon)$-multiplicative approximation to
$\|x\|_{k}^{k}=\sum_{j=1}^{n}|x_{i}|^{k}$, where $x=\sum_{j=1}^{s}x(j)$. A
large body of work has studied $F_{k}$-moment estimation in a stream,
originating with work of Alon, Matias, and Szegedy [2].

In the coordinator model, Cormode et al. [14] initiated the study of this
problem and gave a protocol achieving
$\tilde{O}(n^{1-2/k}\operatorname{poly}(s/\varepsilon))$ bits of total
communication for $k\geq 2$, where we use $\tilde{O}$ to suppress
polylogarithmic factors in $n$. They optimize their bound for $k=2$ and
achieve a quadratic dependence on $s$. They also achieve protocols for
$k\in\\{0,1\\}$ with a linear dependence on $s$. We note that their algorithms
hold in the more general distributed functional monitoring framework. The
upper bound was improved by Woodruff and Zhang to
$\tilde{O}(s^{k-1}/\varepsilon^{\Theta(k)})$ bits in [40], which showed that a
polynomial dependence on $n$ is not needed for $k>2$. Unfortunately the
$1/\varepsilon^{\Theta(k)}$ multiplicative factor is prohibitive, and Kannan,
Vempala, and Woodruff [29] claimed an improved bound of
$\tilde{O}((s^{k-1}+s^{3})/\varepsilon^{3})$ bits. However, there appears to
be a gap in their analysis which is not clear how to fix [30]. We describe
this gap in Appendix A. Their algorithm for general function approximation can
be used to obtain an algorithm which uses $\tilde{O}(s^{k}/\varepsilon^{2})$
bits of communication. Thus the current state of the art is a
$\min(\tilde{O}(s^{k-1}/\varepsilon^{\Theta(k)}),\tilde{O}(s^{k}/\varepsilon^{2}))$
upper bound from [40, 29] and the $\Omega(s^{k-1}/\varepsilon^{2})$ lower
bound of [40]. Even if the work of [29] can be fixed, it would not match the
existing lower bounds, and an important open question is:

Question 1: What is the complexity of $F_{k}$-estimation in the coordinator
model?

As $F_{k}(x)=\sum_{i=1}^{n}|x_{i}|^{k}$ is just one example of an entrywise
function $\sum_{i=1}^{n}f(x_{i})$ for a non-negative function
$f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$, it is natural to ask
what the complexity of approximating $\sum_{i=1}^{n}f(x_{i})$ is in terms of
$f$. Indeed, a wide body of work originating with that of Braverman and
Ostrovsky [9] does exactly this for the related data stream model. In the
coordinator model, Kannan, Vempala, and Woodruff [29] attempt to characterize
the complexity of $f$ by defining a parameter they call $c_{f,s}$, which is
the smallest positive number for which $f(y_{1}+\cdots+y_{s})\leq
c_{f,s}(f(y_{1})+\cdots+f(y_{s}))$ for all $y_{1},\ldots,y_{s}\geq 0.$

For general functions $f$, they give a protocol which uses
$O(s^{2}c_{f,s}/\varepsilon^{2})$ bits of communication up to polylogarithmic
factors. Assuming that the function $f$ is super-additive, i.e.,
$f(y_{1}+y_{2})\geq f(y_{1})+f(y_{2})$ for all $y_{1},y_{2}\geq 0$, their
upper bound can be further improved to $O(sc_{f,s}/\varepsilon^{2})$. They
also give an $\Omega(c_{f,s}/\varepsilon)$ communication lower bound.

We note that a number of interesting entrywise functions have been considered
in optimization contexts, such as the M-Estimators (see, e.g., [17]), and a
natural such estimator is the Huber loss function $f(x)=x^{2}/(2\tau)$ for
$|x|\leq\tau$, and $f(x)=|x|-\tau/2$ otherwise. It is not hard to show
$c_{f,s}=s$ for the Huber loss function, and so the best known upper bound is
$\tilde{O}(s^{2}/\varepsilon^{2})$ bits while the lower bound is only
$\Omega(s/\varepsilon)$. Given the gap between the upper and lower bounds, it
is unclear if the parameter $c_{f,s}$ captures the complexity of approximating
the sum $\sum_{i}f(x_{i})$. We observe that the communication complexity of
the problem is better captured by a new parameter $c_{f}[s]$ defined as the
smallest number for which

$\displaystyle
f(y_{1}+\cdots+y_{s})\leq\frac{c_{f}[s]}{s}(\sqrt{f(y_{1})}+\cdots+\sqrt{f(y_{s})})^{2}\quad\text{for
all}\quad y_{1},\ldots,y_{s}\geq 0.$ (1)

Since, $(\sqrt{f(y_{1})}+\cdots+\sqrt{f(y_{s})})^{2}\geq
f(y_{1})+\cdots+f(y_{s})$, we obtain $c_{f}[s]\leq c_{f,s}\cdot s$ and using
the Cauchy-Schwarz inequality, we can show that $c_{f,s}\leq c_{f}[s]$. We
consider the following question:

Question 2: What is the complexity of entrywise function approximation in the
coordinator model? Can one characterize the complexity completely in terms of
$c_{f}[s]$?

Beyond the coordinator model, a number of works have looked at more general
network topologies, such as [15, 13]. One challenge in a more general network
topology and without a coordinator is how to formally define the communication
model. One of the most popular distributed frameworks in the past few decades
is the CONGEST model [36]. In this model, each server is a node in the network
topology and in each round it can send and simultaneously receive a possibly
distinct message of bounded size222Usually $O(\log n)$ bits where $n$ is the
number of nodes in the graph. to and from its neighbors, as defined by the
edges in the network, which is an unweighted undirected graph. Given the
restriction on the size of the messages that can be sent in each round,
efficiency of a protocol in this model is in general measured by the number of
rounds required by an algorithm.

Efficient CONGEST algorithms have been developed for shortest paths [23, 25],
independent sets [31, 21], matchings [1, 4], minimum spanning trees [28, 22],
and so on. A related distributed computation model is the on-device public-
private model [19] that provides a framework for distributed computation with
privacy considerations.

It is not hard to see that one cannot estimate $F_{k}$ of the sum of vectors
as efficiently in the CONGEST model as one can in the coordinator model with
$s$ servers, even if one has a two-level rooted tree where each non-leaf node
has $s$ children. Indeed, the root and the $s$ nodes in the middle layer can
have no input, at which point the problem reduces to the coordinator model
with $s^{2}$ servers, and for which a stronger $\Omega((s^{2})^{k-1})$ lower
bound holds [40] and hence the average communication per node in the tree must
be $\Omega(s^{2k-4})$ bits, as opposed to an average of $O(s^{k-2})$ bits per
server in the coordinator model with $s$ servers. A natural question is which
functions can be estimated efficiently with a more general network topology.
Inspired by connections between frequency moment algorithms and randomized
linear algebra (see, e.g., [41]), we study the feasibility of communication
efficient algorithms for various linear algebra problems in this setting.

We assume that each server $v$ in the graph holds a matrix
$A_{v}\in\mathbb{R}^{n_{v}\times d}$. Accordingly, we restrict the size of
messages in each round to be $\operatorname{poly}(d,\log n,\log\max_{v}n_{v})$
bits where $n$ is the number of nodes in the graph.

We define a generalization of the CONGEST model called the “personalized
CONGEST model”. In this model, given a distance parameter $\Delta$, we would
like, after $\Delta$ communication rounds, for each node to compute a function
of all nodes reachable from it in at most $\Delta$ steps, which is referred to
as its $\Delta$-hop neighborhood. Note that taking $\Delta$ to be the diameter
of the graph, we obtain the CONGEST model. Such personalized solutions are
desired in several applications such as recommendation systems and online
advertisements. For instance, in an application that wants to recommend a
restaurant to a user, the data from devices in a different country with no
relation to that particular user may not provide useful information and may
even introduce some irrelevant bias. Distributed problems with personalization
have been studied in a line of work [37, 11, 19]; however, to the best of our
knowledge none of the prior work studies linear algebraic problems.

Ideally one would like to “lift” a communication protocol for the coordinator
model to obtain algorithms for the personalized CONGEST model. However,
several challenges arise. The first is that if you have a protocol in the
coordinator model which requires more than $1$-round, one may not be able to
compute a function of the $\Delta$-hop neighborhood in only $\Delta$ rounds.
Also, the communication may become too large if a node has to send different
messages for each node in say, its $2$-hop neighborhood. Another issue is that
in applications, one may be most interested in the maximum communication any
node has to send, as it may correspond to an individual device, and so cannot
be used for collecting a lot of messages and forwarding them. More subtly
though, a major issue arises due to multiple distinct paths between two nodes
$u$ and $v$ in the same $\Delta$-hop neighborhood. Indeed, if a server is say,
interested in a subspace embedding of the union of all the rows held among
servers in its $\Delta$-hop neighborhood, we do not want to count the same row
twice, but it may be implicitly given a different weight depending on the
number of paths it is involved in.

Distributed algorithms for problems in randomized linear algebra, such as
regression and low rank approximation, are well studied in the coordinator
model [8, 10, 29, 20, 7], but they do not work for communication networks with
a general topology such as social networks, mobile communication networks, the
internet, and other networks that can be described by the CONGEST model. Hence
we ask:

Question 3: For which of the problems in numerical linear algebra can one
obtain algorithms in the personalized CONGEST model?

###  1.1 Our Results

To answer Question 2, we give a two round protocol for approximating
$\sum_{i}f(x_{i})$ for non-negative functions which have an “approximate-
invertibility” property.

######  Definition 1.1 (Approximate Invertibility).

We say that a function $f$ satisfies approximate invertibility with parameters
$\theta,\theta^{\prime},\theta^{\prime\prime}>1$ if all the following
properties hold: (i) _super-additivity_ : $f(x+y)\geq f(x)+f(y)$ for all
$x,y\geq 0$, (ii) for all $y\geq 0$, $f(\theta^{\prime}y)\geq\theta\cdot
f(y)$, and (iii) for all $y\geq 0$,
$f(y/4\cdot\sqrt{\theta}\cdot\theta^{\prime})\geq f(y)/\theta^{\prime\prime}$.

The super-additivity and the fact that $f(y)\geq 0$ for all $y$ implies that
$f(0)=0$. We note that any increasing convex function $f$ with $f(0)=0$
satisfies the super-additivity property and hence it is not a very strong
requirement. It is satisfied by $f(x)=x^{k}$ for $k\geq 1$ and the Huber loss
function with any parameter. For such functions, we prove the following
theorem:

######  Theorem 1.2 (Informal, Theorem 4.15).

Let there be $s$ servers with the $j$-th server holding a non-negative
$n$-dimensional vector $x(j)$, and define $x=x(1)+\cdots+x(s)$. Given a
function $f$ which satisfies the approximate invertibility property with
parameters $\theta,\theta^{\prime},\theta^{\prime\prime}>1$, our two round
protocol approximates $\sum_{i}f(x_{i})$ up to a $1\pm\varepsilon$ factor with
probability $\geq 9/10$. Our protocol uses a total communication of
$O_{\theta,\theta^{\prime},\theta^{\prime\prime}}(c_{f}[s]/\varepsilon^{2})$
bits up to polylogarithmic factors in the dimension $n$.

For $f(x)=x^{k}$, we see that $c_{f}[s]=s^{k-1}$ and can take $\theta=2$,
$\theta^{\prime}=2^{1/k}$ and $\theta^{\prime\prime}=2\cdot 8^{k/2}$. Hence
our algorithm uses $s^{k-1}/\varepsilon^{2}$ bits of total communication up to
multiplicative factors depending on $k$ and $\log n$, thus matching the known
lower bounds from [40]. We additionally show that any one round algorithm must
use $\Omega(s^{k-1}/\varepsilon^{k})$ bits of communication and hence our
protocol achieves the optimal communication bounds using the fewest possible
number of rounds, thus resolving Question 1 completely. We summarize the
results for $F_{k}$-moment estimation in Table 1.

$F_{k}$ estimation algorithm | Upper Bound | Lower Bound
---|---|---
2-round algorithm |  $\tilde{O}(s^{k-1}/\varepsilon^{2})$ (Corollary 4.16) |  $\Omega(s^{k-1}/\varepsilon^{2})$ [40]
1-round algorithm |  $\tilde{O}(s^{k-1}/\varepsilon^{\Theta(k)})$ [40] |  $\tilde{\Omega}(s^{k-1}/\varepsilon^{k})$ (Theorem 5.3)
Table 1: Upper and lower bounds on the total communication for $F_{k}$
approximation in the coordinator model. As mentioned, the claimed
$\tilde{O}(\varepsilon^{-3}(s^{k-1}+s^{3}))$ upper bound for $F_{k}$ in [29]
has a gap.

We can also use our protocol to approximate “higher-order correlations”
studied by Kannan, Vempala and Woodruff [29]. In this problem, each server $j$
holds a set of non-negative vectors $W_{j}$ and given functions
$f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ and
$g:\mathbb{R}^{k}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$, the correlation
$M(f,g)$ is defined as

$\displaystyle
M(f,g,W_{1},\ldots,W_{k})\coloneqq\sum_{i_{1},\ldots,i_{k}\,\text{distinct}}f\left(\sum_{j}\sum_{v\in
W_{j}}g(v_{i_{1}},\ldots,v_{i_{k}})\right).$ (2)

Kannan, Vempala and Woodruff [29] note that this problem has numerous
applications and give some examples. Our protocol for estimating
$\sum_{i}f(x_{i})$ in the coordinator model extends in a straightforward way
to the problem of estimating higher-order correlations. We show the following
result:

######  Theorem 1.3 (Informal, Theorem 4.17).

Let there be $s$ servers with the $j$-th server holding a set of
$n$-dimensional non-negative vectors $W_{j}$. Given a function $f$ that has
the approximate invertibility property with parameters
$\theta,\theta^{\prime},\theta^{\prime\prime}>1$ and a function
$g:\mathbb{R}^{k}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$, our randomized two
round protocol approximates $M(f,g,W_{1},\ldots,W_{k})$ up to a
$1\pm\varepsilon$ factor with probability $\geq 9/10$. The protocol uses a
total of
$O_{\theta,\theta^{\prime},\theta^{\prime\prime}}\left({c_{f}[s]}\operatorname{poly}(k,\log
n)/\varepsilon^{2}\right)$ bits of communication.

Our algorithm for approximating $\sum_{i}f(x_{i})$ in the coordinator model is
inspired by a one round protocol for sampling from an “additively-defined
distribution” in the coordinator model, which can also approximate the
sampling probability of the index that was sampled. This protocol lets us
sample, in one round, from very general distributions such as the leverage
scores. Our result is stated in the following theorem.

######  Theorem 1.4 (Informal, Theorem 3.2).

Given that each server $j$ has a non-negative vector $p(j)\in\mathbb{R}^{n}$,
define $q_{i}\coloneqq\sum_{j}p_{i}(j)$. There is a randomized algorithm which
outputs FAIL with probability $\leq\frac{1}{\operatorname{poly}(n)}$ and
conditioned on not outputting FAIL, it outputs a coordinate $\hat{i}$ along
with a value $\hat{q}$ such that for all $i\in[n]$

$\displaystyle\operatorname{Pr\/}[\hat{i}=i\ \text{and}\ \hat{q}\in(1\pm
O(\varepsilon))\frac{q_{i}}{\sum_{i}q_{i}}]=(1\pm
O(\varepsilon))\frac{q_{i}}{\sum_{i}q_{i}}\pm\frac{1}{\operatorname{poly}(n)}.$

The algorithm uses one round and has a total communication of
$O(s\operatorname{polylog}(n)/\varepsilon^{2})$ words.

For Question 3, in the personalized CONGEST model, we show how to compute
$\Delta$-hop subspace embeddings, approximately solve $\ell_{p}$-regression,
and approximately solve low rank approximation efficiently. For example, for
$\ell_{p}$-subspace embeddings and regression, we achieve
$\tilde{O}(\Delta^{2}nd^{p/2+2}/\varepsilon^{2})$ words of communication,
which we optimize for $p=2$ to $\tilde{O}(\Delta^{2}nd^{2})$ communication,
where $n$ is the total number of nodes in the graph. Our algorithms are also
efficient in that each node sends at most $\tilde{O}(\Delta\cdot
d^{\max(p/2+2,3)})$ communication to each of its neighbors in each of the
rounds, which we optimize to $\tilde{O}(\Delta\cdot d^{2})$ for $p=2$. That
is, the maximum communication per server is also small. We remark that in a
round, the information sent by a node to all its neighbors is the same.
Finally, our protocols are efficient, in that the total time, up to
logarithmic factors is proportional to the number of non-zero entries across
the servers, up to additive poly$(d/\varepsilon)$ terms. Our results hold more
broadly for sensitivity sampling for any optimization problem, which we
explain in Section 1.2. Our results in the CONGEST model are summarized in
Table 2.

Problem | Per node Communication in each round
---|---
$\ell_{p}$ subspace embeddings ($p\neq 2$) |  $\tilde{O}_{\Delta}(d^{\max(p/2+2,3)}\varepsilon^{-2})$ (Theorem 7.5)
$\ell_{p}$ regression ($p\neq 2$) |  $\tilde{O}_{\Delta}(d^{\max(p/2+2,3)}\varepsilon^{-2})$ (Section 7.5)
$\ell_{2}$ subspace embeddings |  $\tilde{O}_{\Delta}(d^{2}\varepsilon^{-2})$ (Theorem 7.5)
$\ell_{2}$ regression |  $\tilde{O}_{\Delta}(d^{2}\varepsilon^{-2})$ (Section 7.5)
Rank-$k$ Frobenius LRA |  $\tilde{O}_{\Delta}(kd\varepsilon^{-3})$ (Section 7.6)
Table 2: Per node communication in each of the $\Delta$ rounds to solve the
problems over data in a $\Delta$ neighborhood of each node in the CONGEST
model

###  1.2 Our Techniques

##### Sampling from “Additively-Defined” Distributions.

At the heart of our results for approximating
$\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}f(\sum_{j=1}^{s}x_{i}(j))$ is a general
technique to sample from an “additively-defined” distribution using only one
round of communication. To obtain our tightest communication bounds, our
algorithm for approximating $\sum_{i=1}^{n}f(x_{i})$ does not use this
protocol in a black-box way, but the techniques used are similar to the ones
used in this protocol. In this setting, the $j$-th server holds a non-negative
vector $p(j)\in\mathbb{R}^{n}_{\geq 0}$ and the coordinator wants to sample
from a distribution over $[n]$ with the probability of sampling $i\in[n]$
being proportional to $q_{i}=p_{i}(1)+\cdots+p_{i}(s).$

Additionally if the coordinate $i$ is sampled by the coordinator, the
coordinator also needs to be able to estimate the probability with which $i$
is sampled. This is an important requirement to obtain (approximately)
unbiased estimators in applications involving importance sampling. If the
coordinator just wants to sample from the distribution, it can run the
following simple protocol: first, each server $j$ samples a coordinate
$\mathbf{i}_{j}$ from its local distribution, i.e.,
$\operatorname{Pr\/}[\mathbf{i}_{j}=i]=p_{i}(j)/\sum_{i}p_{i}(j)$. Each server
sends the coordinate $\mathbf{i}_{j}$ along with the quantity
$\sum_{i}p_{i}(j)$ to the coordinator. The coordinator then samples a random
server $\mathbf{j}$ from the distribution
$\operatorname{Pr\/}[\mathbf{j}=j]=(\sum_{i}p_{i}(j))/\sum_{j^{\prime}}(\sum_{i}p_{i}(j^{\prime}))$
and then takes $\mathbf{i}_{\mathbf{j}}$, i.e., the coordinate sent by the
server $\mathbf{j}$, to be the sample. We note that

$\displaystyle\operatorname{Pr\/}[\mathbf{i}_{\mathbf{j}}=i]=\sum_{j}\operatorname{Pr\/}[\mathbf{j}=j]\operatorname{Pr\/}[\mathbf{i}_{j}=i]=\sum_{j}\frac{\sum_{i^{\prime}}p_{i^{\prime}}(j)}{\sum_{j}\sum_{i^{\prime}}p_{i^{\prime}}(j)}\cdot\frac{p_{i}(j)}{\sum_{i^{\prime}}p_{i^{\prime}}(j)}=\frac{\sum_{j}p_{i}(j)}{\sum_{j}\sum_{i^{\prime}}p_{i^{\prime}}(j)}=\frac{q_{i}}{\sum_{i^{\prime}}q_{i^{\prime}}}.$

Hence the distribution of $\mathbf{i}_{\mathbf{j}}$ is _correct_. But notice
that there is no easy way for the coordinator to estimate the probability of
sampling $\mathbf{i}_{\mathbf{j}}$ since it may not receive any information
about this coordinate from the other servers. Therefore, to obtain the
probability with which $\mathbf{i}_{\mathbf{j}}$ was sampled, the coordinator
needs another round of communication, which we wish to avoid.

We will now give a protocol that can also approximate the sampling
probabilities with only one round of communication. The protocol we describe
here is a simpler version of the full protocol in Section 3. Consider the
following way of sampling from the distribution in which $i$ has a probability
proportional to $q_{i}$. Let $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ be
independent standard exponential random variables. Let
$i^{*}=\operatorname*{arg\,max}_{i\in[n]}\mathbf{e}_{i}^{-1}q_{i}=\operatorname*{arg\,max}_{i\in[n]}\mathbf{e}_{i}^{-1}(p_{i}(1)+\cdots+p_{i}(s)).$
By standard properties of the exponential random variable, we have
$\operatorname{Pr\/}[i^{*}=i]=\frac{\sum_{j}p_{i}(j)}{\sum_{j}\sum_{i^{\prime}}p_{i^{\prime}}(j)}=\frac{q_{i}}{\sum_{i^{\prime}}q_{i^{\prime}}}.$

Hence, the random variable $i^{*}$ also has the _right_ distribution. The
advantage now is that we can additionally show that with a high probability,
$\sum_{i}\mathbf{e}_{i}^{-1}\left(\sum_{j}p_{i}(j)\right)\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}\sum_{j}p_{i^{*}}(j).$
In other words, if we define $s$ vectors $r(1),\ldots,r(s)$, one at each of
the servers, such that $r_{i}(j)=\mathbf{e}_{i}^{-1}p_{i}(j)$ and define
$r=\sum_{j=1}^{s}r(j)$, then the coordinate $r_{i^{*}}$ is a $1/(C\log^{2}n)$
$\ell_{1}$ _heavy hitter_ , as in $r_{i^{*}}\geq\|r\|_{1}/(C\log^{2}n)$.

Suppose a deterministic sketch matrix $S\in\mathbb{R}^{m\times n}$ is an
$\alpha$-incoherent matrix for $\alpha=\varepsilon/(4C\log^{2}n)$. Here we say
that a matrix $S$ is $\alpha$-incoherent if all the columns of $S$ have unit
Euclidean norm and for any $i\neq i^{\prime}\in[n]$, $|\langle
S_{*i},S_{*i^{\prime}}\rangle|\leq\alpha$. Nelson, Nguyen and Woodruff [35]
give constructions of such matrices with $m=O(\log(n)/\alpha^{2})$ rows and
show that for any vector $x$, $\|x-S^{\top}Sx\|_{\infty}\leq\alpha\|x\|_{1}.$

Now suppose that each server $j$ computes the vector $S\cdot r(j)$ and uses
$O(\operatorname{polylog}(n)/\varepsilon^{2})$ words of communication to send
the vector $S\cdot r(j)$ to the coordinator. The coordinator receives the
vectors $S\cdot r(1),\ldots,S\cdot r(s)$ and computes the vector $S\cdot
r=S\cdot r(1)+\cdots+S\cdot r(s)$ and can then compute a vector
$r^{\prime}=S^{\top}Sr$ satisfying
$\|r-r^{\prime}\|_{\infty}\leq\alpha\|r\|_{1}.$

Conditioned on the event that $\|r\|_{1}\leq(C\log^{2}n)\cdot r_{i^{*}}$, as
$\alpha$ is set to be $\varepsilon/(4C\log^{2}n)$, we obtain that
$r^{\prime}_{i^{*}}=(1\pm\varepsilon/4)\cdot r_{i^{*}}$ and for all $i\neq
i^{*}$, we have $r^{\prime}_{i}\leq r_{i}+(\varepsilon/4)\cdot r_{i^{*}}$.
Using properties of exponential random variables, we can also show that with
probability $\geq 1-O(\varepsilon)$,
$\max_{i}r_{i}\geq(1+\varepsilon)\cdot\text{second-max}_{i}\,r_{i}$.
Conditioned on this event as well, we obtain that for all $i\neq i^{*}$,
$r^{\prime}_{i}<r_{i^{*}}(1-\varepsilon/4)\leq r^{\prime}_{i^{*}}$. Hence the
largest coordinate in the vector $r^{\prime}$ is exactly $i^{*}$ and the value
$r_{i^{*}}$ can be recovered up to a $1\pm\varepsilon/4$ factor. Overall, the
coordinator can find a coordinate $\hat{i}$ and a value
$\hat{q}=\mathbf{e}_{\hat{i}}\cdot(r_{\hat{i}})^{\prime}$ such that for all
$i\in[n]$,

$\displaystyle\operatorname{Pr\/}[\hat{i}=i\ \text{and}\
\hat{q}\in(1\pm\varepsilon/4)q_{i}]=\frac{q_{i}}{\sum_{i^{\prime}}q_{i^{\prime}}}\pm
O(\varepsilon).$ (3)

Thus this procedure lets us sample from a distribution close to that of the
desired distribution while at the same time lets us approximate the
probability of the drawn sample. In Section 3, we give a protocol, which
instead of using incoherent matrices, uses an “$\ell_{1}$ sampling-based”
algorithm to compute the coordinate $i^{*}$ and approximate the value
$q_{i^{*}}$. We end up obtaining a sample $\hat{i}\in[n]$ and a value
$\hat{q}$ for which

$\displaystyle\operatorname{Pr\/}[\hat{i}=i\,\text{and}\,\hat{q}=(1\pm\varepsilon)\frac{q_{i}}{\sum_{i^{\prime}}q_{i^{\prime}}}]=(1\pm\varepsilon)\frac{q_{i}}{\sum_{i^{\prime}}q_{i^{\prime}}}\pm\frac{1}{\operatorname{poly}(n)}.$
(4)

Additionally, computing the coordinate $\hat{i}$ does not require $\Omega(n)$
time at the coordinator using the protocol in Section 3.

##### Function Sum Approximation.

Our aim is to obtain an algorithm which approximates the sum
$\sum_{i=1}^{n}f(x_{i})=\sum_{i=1}^{n}f(\sum_{j=1}^{s}x_{i}(j))$ up to a
$1\pm\varepsilon$ factor for a non-negative, super-additive function $f$. The
protocol described above for sampling from additively-defined distributions
shows that correlating randomness across all the servers using exponential
random variables is a powerful primitive in this context.

In the function sum approximation problem, each server holds a non-negative
vector $x(1),\ldots,x(s)$, respectively, and the coordinator wants to
approximate $\sum_{i}f(x_{i})=\sum_{i}f(\sum_{j}x_{i}(j))$. Suppose that each
server $j$ defines a vector $p(j)\in\mathbb{R}^{n}$ such that
$p_{i}(j)=f(x_{i}(j))$. Then the above described protocol can be used to
sample approximately from the distribution in which $i$ has probability
$(1\pm\varepsilon)\frac{f(x_{i}(1))+\cdots+f(x_{i}(s))}{\sum_{i^{\prime}}\sum_{j}f(x_{i^{\prime}}(j))}\pm\frac{1}{\operatorname{poly}(n)}.$
Using super-additivity and the definition of the parameter $c_{f}[s]$, we
obtain that the above probability is at least
$(1\pm\varepsilon)\frac{f(x_{i})}{c_{f}[s]\cdot\sum_{i^{\prime}}f(x_{i^{\prime}})}\pm\frac{1}{\operatorname{poly}(n)}.$
This distribution is off by a multiplicative $c_{f}[s]$ factor from the
distribution we need to sample coordinates from in order to estimate
$\sum_{i}f(x_{i})$ with a low variance. Thus, we need
$O(c_{f}[s]/\varepsilon^{2})$ samples from the above distribution, and this
overall requires a communication of $O(s\cdot c_{f}[s]/\varepsilon^{4})$ bits,
which is more than the total communication required by the protocol of [29].

Additionally, when the coordinate $i$ is sampled, the protocol lets us
estimate $f(x_{i}(1))+\cdots+f(x_{i}(s))$, but the quantity we want to
construct an estimator for is the value $f(x_{i}(1)+\cdots+x_{i}(s))$, which
requires an additional round of communication and defeats the point of
obtaining a protocol that can approximate the sampling probability in the same
round. Overall, a protocol based on this procedure requires $O(s\cdot
c_{f}[s]\cdot\operatorname{polylog}(n)/\varepsilon^{4})$ bits of communication
and two rounds of communication.

Thus, we need a different technique to obtain algorithms which can approximate
$\sum_{i}f(x_{i})$ more efficiently. We continue to use exponential random
variables to correlate the randomness across the servers but instead heavily
use the max-stability property to design our protocol. Let
$\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ be independent standard exponential
random variables. The max-stability property asserts that for any
$f_{1},\ldots,f_{n}\geq 0$, the random variable
$\max(f_{1}/\mathbf{e}_{1},\ldots,f_{n}/\mathbf{e}_{n})$ has the same
distribution as $(\sum_{i=1}^{n}f_{i})/\mathbf{e}$ where $\mathbf{e}$ is also
a standard exponential random variable. Now using the _median_ of
$O(1/\varepsilon^{2})$ independent copies of the random variable
$(\sum_{i=1}^{n}f_{i})/\mathbf{e}$, we can compute an approximation of
$\sum_{i=1}^{n}f_{i}$ up to a $1\pm\varepsilon$ factor with high probability.
Thus, in the coordinator model, if there is a protocol that can find the value
of the random variable $\max_{i}f(x_{i})/\mathbf{e}_{i}$, then we can use it
to compute a $1\pm\varepsilon$ approximation to $\sum_{i}f(x_{i})$ by running
the protocol for $O(1/\varepsilon^{2})$ independent copies of the exponential
random variables. From here on, we explain how we construct such a protocol.

Given the exponential random variables $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$,
define
$i^{*}\coloneqq\operatorname*{arg\,max}_{i\in[n]}\mathbf{e}_{i}^{-1}f(x_{i}).$
As mentioned above we would like to find the value of
$\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$. The “heavy-hitter” property we used
previously shows that with probability $\geq
1-\frac{1}{\operatorname{poly}(n)}$,

$\displaystyle\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\max_{i}\mathbf{e}_{i}^{-1}f(x_{i}).$
(5)

This is the main property that leads to a communication efficient algorithm
that can identify the max coordinate $i^{*}$ and the value $x_{i^{*}}$. From
here on, condition on the above event.

Note that we are shooting for a protocol that uses at most
$O(c_{f}[s]\cdot\operatorname{polylog}(n))$ bits of total communication and
succeeds in computing the value $\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$ with a
probability $\geq 1-\frac{1}{\operatorname{poly}(n)}$. Fix a server $j\in[s]$.
Consider the random variable $\mathbf{i}$ which takes values in the set $[n]$
according to the distribution
$\operatorname{Pr\/}[\mathbf{i}=i]={\mathbf{e}_{i}^{-1}f(x_{i}(j))}/{\sum_{i\in[n]}\mathbf{e}_{i}^{-1}f(x_{i}(j))}.$
Since the server $j$ knows all the values,
$x_{1}(j),x_{2}(j),\ldots,x_{n}(j)$, it can compute the above probability
distribution and can sample $N$ (for a value to be chosen later) independent
copies $\mathbf{i}_{1},\ldots,\mathbf{i}_{N}$ of the random variable
$\mathbf{i}$. Let
$\textnormal{{{SC}}}_{j}\coloneqq\set{\mathbf{i}_{1},\ldots,\mathbf{i}_{N}}$333We
use the notation $\textnormal{{{SC}}}_{j}$ since it denotes the “Sampled
Coordinates” at server $j$. be the set of coordinates sampled by server $j$.
Server $j$ then sends the set $\textnormal{{{SC}}}_{j}$ along with the values
$x_{i}(j)$ for $i\in\textnormal{{{SC}}}_{j}$. Note that the coordinator can
compute $f(x_{i}(j))$ since it knows the definition of the function $f$. The
total communication from all the servers to the coordinator until this point
is $O(s\cdot N)$ words.

Now define $\textnormal{{{SC}}}\coloneqq\bigcup_{j}\,\textnormal{{{SC}}}_{j}$
to be the set of coordinates that is received by the central coordinator from
all the servers. We will first argue that $i^{*}\in\textnormal{{{SC}}}$ with a
large probability if the number of sampled coordinates at each server
$N=\Omega(c_{f}[s]\cdot\operatorname{polylog}(n)/s)$. To prove this, we use
the fact that $\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$ is significantly large
since we conditioned on the event in (5), and then apply the definition (1) of
the parameter $c_{f}[s]$.

Conditioned on the event that the coordinate $i^{*}\in\textnormal{{{SC}}}$, a
simple algorithm to determine the value of
$\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$ would be for the coordinator to query
the value of $x_{i}(j)$ for all $i\in\textnormal{{{SC}}}$ from all the servers
$j$. Unfortunately, this requires a total communication of $\Omega(s\cdot
c_{f}[s]\cdot\operatorname{polylog}(n))$ bits since the set SC could have a
size as large as $s\cdot N=\Omega(c_{f}[s]\cdot\operatorname{polylog}(n))$. As
we are aiming for a protocol that uses about
$O(c_{f}[s]\cdot\operatorname{polylog}(n))$ bits of total communication, the
coordinator cannot ask for the values of all the coordinates in the set SC.

If the coordinator finds a smaller subset
$\textnormal{{{PL}}}\subseteq\textnormal{{{SC}}}\subseteq[n]$444We use PL to
denote that these set of coordinates have “Probably Large” values of
$\mathbf{e}_{i}^{-1}f(x_{i})$. that contains $i^{*}$, with a size
$|\textnormal{{{PL}}}|$ of about $\operatorname{polylog}(n)$, the coordinator
can then query for $x_{i}(j)$ for $i\in\textnormal{{{PL}}}$ for all $j$ using
only a communication of
$O(s\cdot\operatorname{polylog}(n))=O(c_{f}[s]\cdot\operatorname{polylog}(n))$
bits since $c_{f}[s]\geq s$.

From here on condition on the event that $i^{*}\in\textnormal{{{SC}}}$. To
find such a small subset PL, our strategy is to construct $\hat{x}_{i}$ for
each $i\in\textnormal{{{SC}}}$ so that the following properties are
simultaneously satisfied with probability $\geq
1-\frac{1}{\operatorname{poly}(n)}$: (i) for all $i\in\textnormal{{{SC}}}$,
$\hat{x}_{i}\leq x_{i}$ and (ii)
$\mathbf{e}_{i^{*}}^{-1}f(\hat{x}_{i^{*}})\geq\alpha\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
for some value $\alpha<1$. Define
$\textnormal{{Est}}_{i}\coloneqq\mathbf{e}_{i}^{-1}f(\hat{x}_{i})$ for
$i\in\textnormal{{{SC}}}$. If the constructed values $\hat{x}_{i}$ for
$i\in\textnormal{{{SC}}}$ satisfy these two properties, we have that
$\textnormal{{Est}}_{i}\leq\mathbf{e}_{i}^{-1}f(x_{i})$ for all $i$ and
$\textnormal{{Est}}_{i^{*}}\geq\alpha\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
by monotonicity of $f$.

Recall that we conditioned on the event
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
which then implies that the number of coordinates $i$, with
$\textnormal{{Est}}_{i}\geq\textnormal{{Est}}_{i^{*}}$ is at most
$(C\log^{2}n)/\alpha$. Now, if we define PL to be the set of coordinates
$i\in\textnormal{{{SC}}}$ with the $C\log^{2}n/\alpha$ largest values, then we
have that $i^{*}\in\textnormal{{{PL}}}$. The coordinator can then determine
$\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$ after a second round of communication
from the servers in which it asks for the values of $x_{i}(j)$ from all the
servers $j$ only for the coordinates $i\in\textnormal{{{PL}}}$.

Fix a coordinate $i\in\textnormal{{{SC}}}$. We will briefly describe how
$\hat{x}_{i}$ is computed by the coordinator using only the information it
receives in the first round of communication from the servers. We say
$x_{i}(j)$ is the _contribution_ of server $j$ to $x_{i}$. If $i\neq i^{*}$,
then we can safely ignore the contribution from any number of servers to
$x_{i}$ when we are trying to construct the estimator $\hat{x}_{i}$. However,
the coordinator does not know what $i^{*}$ is and cannot arbitrarily drop the
contribution from servers when trying to compute the estimator $\hat{x}_{i}$.

We first define two disjoint subsets of servers $\textnormal{{Large}}_{i}$ and
$\textnormal{{Small}}_{i}$: we put $j\in\textnormal{{Large}}_{i}$ if the
probability of the coordinate $i$ being sampled at $j$ is _very high_ and we
put $j\in\textnormal{{Small}}_{i}$ if the probability is _very low_. Since the
probability of $i$ being sampled at the servers in $\textnormal{{Large}}_{i}$
is very large, we can union bound over all $i\in[n]$ and all servers
$j\in\textnormal{{Large}}_{i}$ and assume that it does happen, and can
therefore estimate the contribution of all the servers in
$\textnormal{{Large}}_{i}$ exactly.

We then argue that the contribution from all the servers
$j\in\textnormal{{Small}}_{i}$ can be “ignored”: by ignoring the contribution
of a set of servers $S_{i}$, we mean that
$\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}-\sum_{j\in S_{i^{*}}}x_{i^{*}}(j))$ is a
significant portion of $\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$. Note that we
only need to care about how excluding the contribution of $S_{i^{*}}$ to
$x_{i^{*}}$ affects our ability in obtaining $\hat{x}_{i^{*}}$ which satisfies
the above property and we need not care about the effects of excluding the
contribution to $x_{i}$ from the set of servers $S_{i}$ for all other $i\neq
i^{*}$ since we are only trying to underestimate such $x_{i}$.

We then need to estimate the contribution to $x_{i}$ from the “intermediate”
servers, i.e., those that are neither Large nor Small. We bucket the servers
$j$ based on the values $\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ and
$\mathbf{e}_{i}^{-1}f(x_{i}(j))/\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ (the
probability that a given sample at server $j$ is equal to $i$). We show that
the _size_ of a bucket is enough to approximate the contribution from all the
servers in the bucket towards $x_{i}$ and argue that if the size is not very
large, then the contribution from the bucket can be ignored in the sense
described above. Of course, the coordinator can not determine the size of a
bucket but given that a server $j$ sampled the coordinate $i$, the coordinator
can compute which bucket the server $j$ belongs to. We show that when the size
of the bucket is large enough, the number of servers in the bucket that sample
the coordinate $i$ is concentrated enough that we can estimate its size. We
thus identify which buckets have a large size based on the number of servers
in the bucket that sample $i$, and for each bucket that we identify as large,
we approximate the size up to constant factor. This can then be used to
approximate the contribution of the bucket to $x_{i}$, and hence obtain the
estimator $\hat{x}_{i}$.

This wraps up our protocol for computing
$\max_{i}\mathbf{e}_{i}^{-1}f(x_{i})$, with a high probability, and using a
total of $O(c_{f}[s]\cdot\operatorname{polylog}(n))$ bits of total
communication across two rounds. Running this protocol concurrently for
$O(1/\varepsilon^{2})$ copies of the exponential random variables, we can then
obtain a $1\pm\varepsilon$ approximation to $\sum_{i}f(x_{i})$ with high
probability.

##### The Personalized CONGEST Model.

We focus on constructing $\ell_{2}$-subspace embeddings, though the arguments
here are analogous for $\ell_{p}$-subspace embeddings by using the
$\ell_{p}$-sensitivities instead of the leverage scores, defined below. Recall
that given an $n\times d$ matrix $A$, we say that a matrix $M$ is $1/2$
subspace embedding for $A$ if for all vectors $x$, $\|Mx\|_{2}^{2}=(1\pm
1/2)\|Ax\|_{2}^{2}$. Subspace embeddings have numerous applications in
obtaining fast algorithms for problems such as linear regression, low rank
approximation, etc.

Our main technique is to use the _same_ uniform random variables across all
the servers to _coordinate_ the random samples across all the servers in a
useful way. For simplicity, assume that there is a node $\alpha$ connected to
$s$ neighbors (servers) such that the $j$-th neighbor holds a matrix
$A^{(j)}\in\mathbb{R}^{n_{j}\times d}$, which does not have any duplicate
rows. Further assume that we want to compute a subspace embedding for the
matrix $A$ obtained by the union of the rows of the matrices $A^{(j)}$, i.e.,
if a row $v$ is present in say both $A^{(1)}$ and $A^{(2)}$, it appears only
once in the matrix $A$.

Given a matrix $A$, we recall the standard definition of the leverage scores
for each of the rows of $A$, as well as the standard construction to obtain a
subspace embedding from the leverage scores. If $v$ is a row of the matrix
$A$, define the leverage score $\tau_{A}(v)$ of v to be:
$\tau_{A}(v)\coloneqq\max_{x:Ax\neq 0}\frac{|\langle
v,x\rangle|^{2}}{\|Ax\|_{2}^{2}}$. For convenience, we define $\tau_{A}(v)=0$
if $v$ is not a row of the matrix $A$. One has that the sum of the leverage
scores of all the rows in a matrix $A$ is at most $d$. Now construct the
$n\times n$ random diagonal matrix $\mathbf{D}$ as follows: for each $i\in[n]$
independently set $\mathbf{D}_{i,i}$ to be $1/\sqrt{p_{i}}$ with probability
$p_{i}=\min(1,q_{i})$ where $q_{i}\geq C\tau_{A}(a_{i})\log d$ and $a_{i}$ is
the $i$-th row of $A$, and set it to $0$ otherwise. We note that since
$\sum_{i\in[n]}\tau_{A}(a_{i})\leq d$, the random matrix $\mathbf{D}$ has at
most $O(d\log d)$ nonzero entries with a large probability. One can now show
that if $C$ is large enough, then with probability $\geq 99/100$, the matrix
$\mathbf{D}A$ is a $1/2$ subspace embedding for $A$. We note that the matrix
$\mathbf{D}A$ has at most $O(d\log d)$ nonzero rows with a large probability.
This algorithm is known as _leverage score sampling_.

Going back to our setting, we want to implement leverage score sampling on the
matrix $A$ which is formed by the union of the rows of the matrices
$A^{(1)},\ldots,A^{(s)}$, i.e., we only count a row once even if it appears on
multiple servers. As in the coordinator model where we used the same
exponential random variables across servers, a key idea we use in the CONGEST
model is _correlated randomness_. This time, for each possible row $v$ that
could be held by any server, all the servers choose the same threshold $h(v)$
uniformly at random from the interval $[0,1]$. We treat $h(\cdot)$ as a fully
random hash function mapping row $v$ to a uniform random number from the
interval $[0,1]$.

Each server $j$ now computes the $\ell_{2}$ leverage score of each of the rows
in its matrix $A^{(j)}$. Note if $v$ is held by two different servers $j\neq
j^{\prime}$, then it could be that
$\tau_{A^{(j)}}(v)\neq\tau_{A^{(j^{\prime})}}(v)$.

Server $j$ sends all its rows $v$ that satisfy $h(v)\leq
C\tau_{A^{(j)}}(v)\log d$ to node $\alpha$. Additionally, assume that the
server sends the value $\tau_{A^{(j)}}(v)$ along with the row $v$. Since
$h(v)$ is picked uniformly at random from the interval $[0,1]$, the
probability that a row $v$ is sent to the node $\alpha$ by the $j$-th server
is $\min(1,C\tau_{j}(v)\log d)$. Hence, each server is implementing leverage
score sampling of its own rows and sending all the rows that have been sampled
to node $\alpha$.

Now we note that if $v$ is a row of the matrix $A^{(j)}$, then
$\tau_{A^{(j)}}(v)\geq\tau_{A}(v)$ which directly follows from the definition
of leverage scores. For any $v$ that is a row of the matrix $A$, we have
$\tau_{A}(v)\leq\max_{j\in[s]}\tau_{A^{(j)}}(v)$. Since $h(v)$ is same across
all the servers, then the probability that a row $v$ of the matrix $A$ is sent
to the node $\alpha$ is exactly, $\min(1,\max_{j\in[s]}C\tau_{A^{(j)}}(v)\log
d)$. For all the rows $v$ that are received by node $\alpha$, it can also
compute $\min(1,\max_{j\in[s]}C\tau_{A^{(j)}}(v)\log d)$ since it also
receives the values $\tau_{A^{(j)}}(v)$ from all the servers that send the row
$v$. Now using the fact that $\tau_{A}(v)\leq\max_{j\in[s]}\tau_{A^{(j)}}(v)$
for all rows $v$ of $A$, the union of rows that are received by the node
$\alpha$ correspond to a leverage score sampling of the matrix $A$. Since the
node $\alpha$ can also compute the probability that each row it receives was
sampled with, it can appropriately scale the rows and obtain a subspace
embedding for the matrix $A$. In the above procedure, each server $j$ sends at
most $O(d\log d)$ rows and therefore the subspace embedding constructed by the
node $\alpha$ for matrix $A$ has at most $O(sd\log d)$ rows.

Even though we described a procedure to compute a subspace embedding of the
union of neighboring matrices at a single node $\alpha$, if the nodes send the
rows that are under the threshold $h(v)$ to all their neighbors, this
procedure can simultaneously compute a subspace embedding at each node for a
matrix that corresponds to the union of neighbor matrices of that node. This
solves the $1$-neighborhood version of the more general $\Delta$-neighborhood
problem we introduced.

Now consider how we can compute a subspace embedding for the distance $2$
neighborhood matrix. Note that we cannot run the same procedure on
$1$-neighborhood subspace embeddings to obtain $2$-neighborhood subspace
embeddings. We again use the monotonicity of leverage scores. Consider the
node $\alpha$ and the matrix $A$ as defined before. Let $v$ be a row that it
receives from one of its neighbors in the first round. Suppose the node
$\alpha$ can compute $\tau_{A}(v)$, the leverage score of $v$ with respect to
the matrix $A$. Now the node $\alpha$ forwards the row $v$ to its neighbors if
$h(v)\leq C\tau_{A}(v)\log d$. Suppose $\beta$ is neighbor of the node
$\alpha$. Thus, after the second round, the rows received by $\beta$ then
correspond to performing a leverage score sampling of the distance-$2$
neighborhood matrix for the node $\beta$ and it can then compute a subspace
embedding for that matrix!

Now the main question is how can the node $\alpha$ compute the leverage scores
$\tau_{A}(v)$? By definition of a subspace embedding, we note that if $M$ is a
subspace embedding for $A$, then $M$ can be used to approximate $\tau_{A}(v)$.
Since we already saw that the node $\alpha$ can compute a subspace embedding
for the $1$-neighborhood matrix, it can also approximate $\tau_{A}(v)$ for all
the rows $v$ that it receives. However an issue arises where we are using the
set of rows that $\alpha$ receives in the first round themselves to
approximate their leverage scores and therefore their sampling probabilities
in the second round. This leads to correlations and it is unclear how to
analyze leverage score sampling with such correlations. To solve for this
issue, we use two independent hash functions $h_{1}(\cdot)$ and
$h_{2}(\cdot)$. Using the sample of rows received by the node $\alpha$ when
the $1$-neighborhood procedure from above is run using hash function
$h_{1}(\cdot)$, it computes a subspace embedding for the matrix $A$ and then
uses this subspace embedding to approximate the leverage scores of the rows
that it receives when the $1$-neighborhood procedure run using hash function
$h_{2}(\cdot)$. The node $\alpha$ then uses these approximate leverage scores
to decide which of the rows that it received are to be forwarded to its
neighbors. This decouples the probability computation and the sampling
procedure and the proof of leverage score sampling goes through.

This procedure is similarly extended to compute subspace embeddings for the
$\Delta$-neighborhood matrices at each node in the graph. In each round, we
use a fresh subspace embedding and use it to compute approximate leverage
scores and filter out the rows and then forward them to the neighbors. This
way of decorrelating randomness is similar to the sketch switching method for
adversarial streams in [6], though we have not seen it used in this context.

This general procedure of collecting data from neighbors, _shrinking_ the
collected data and transferring the data to all the neighbors is called “graph
propagation”. Any procedure such as ours above which can handle duplicates can
be readily applied in this framework so that each node in the graph can
simultaneously learn some statistic/solve a problem over the data in its
neighborhood.

##  2 Preliminaries

###  2.1 Notation

For a positive integer $n$, we use the notation $[n]$ to denote the set
$\set{1,\ldots,n}$. For two non-negative numbers $a$ and $b$ and a parameter
$0<\varepsilon<1$, we use $a=(1\pm\varepsilon)b$ if $(1-\varepsilon)b\leq
a\leq(1+\varepsilon)b$. Given a vector $x\in\mathbb{R}^{n}$ and $k\geq 1$,
$\|x\|_{k}=(\sum_{i}|x_{i}|^{k})^{1/k}$ denotes the $\ell_{k}$ norm of the
vector $x$. We use the notation $F_{k}(x)$ for $\|x\|_{k}^{k}$. Given a matrix
$A$, $\left\|A\right\|_{F}$ denotes the Frobenius norm defined as
$(\sum_{i,j}A_{ij}^{2})^{1/2}$ and for an index $i$, $A_{i}$ denotes the
$i$-th row of matrix $A$. We use the notation $\tilde{O}(f)$ to hide the
factors that are polylogarithmic in the parameters of the problem such as the
dimension or $1/\varepsilon$ where $\varepsilon$ is an accuracy parameter,
etc. For a parameter $k$, we use the notation $O_{k}(f)$ to hide the
multiplicative factors that depend purely on $k$.

###  2.2 Exponential Random Variables

We use the following properties of exponential random variables extensively
throughout the paper.

  1. 1.

If $\mathbf{e}$ is a standard exponential random variable, then
$\operatorname{Pr\/}[\mathbf{e}\geq C\log n]=1/n^{C}$ and
$\operatorname{Pr\/}[\mathbf{e}\leq t]\leq t$ for any $C,t\geq 0$.

  2. 2.

If $f_{1},\ldots,f_{n}\geq 0$ are arbitrary and
$\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ are standard exponential random
variables, then $\max_{i}\mathbf{e}_{i}^{-1}f_{i}$ has the same distribution
as $\mathbf{e}^{-1}(\sum_{i}f_{i})$. This property is referred to as “max-
stability”. This shows that with probability $\geq
1-1/n^{C},\max_{i}\mathbf{e}_{i}^{-1}f_{i}\geq(\sum_{i}f_{i})/C\log n$.

  3. 3.

In the same setting, if
$i^{*}=\operatorname*{arg\,max}_{i}\mathbf{e}_{i}^{-1}f_{i}$, then
$\operatorname{Pr\/}[i^{*}=i]=f_{i}/\sum_{j}f_{j}$.

  4. 4.

Let $\mathbf{e}_{1},\ldots,\mathbf{e}_{t}$ are $t$ independent standard
exponential random variables. If $t=\Omega(1/\varepsilon^{2})$, then

$\displaystyle\operatorname{Pr\/}[(1-\varepsilon)\ln(2)\leq\textnormal{median}(\mathbf{e}_{1},\ldots,\mathbf{e}_{t})\leq(1+\varepsilon)\ln(2)]\geq
9/10.$

Hence for any $F>0$,
$\textnormal{median}(F/\mathbf{e}_{1},\ldots,F/\mathbf{e}_{t})\cdot\ln(2)\in[(1-\varepsilon)F,(1+\varepsilon)F]$
with probability $\geq 9/10$.

We use the following lemma extensively which shows that with a probability
$\geq 1-1/\operatorname{poly}(n)$,
$\sum_{i}\mathbf{e}_{i}^{-1}f_{i}\leq(C\log^{2}n)\max_{i}\mathbf{e}_{i}^{-1}f_{i}$.

######  Lemma 2.1.

Given any $f_{1},\ldots,f_{n}\geq 0$, let $F=\sum_{i=1}^{n}f_{i}$. With
probability $\geq 1-1/\operatorname{poly}(n)$,

$\displaystyle\frac{\max
f_{i}/\mathbf{e}_{i}}{\sum_{i=1}^{n}f_{i}/\mathbf{e}_{i}}\geq\frac{1}{C\log^{2}n}.$

###### Proof.

Condition on the event that $1/n^{3}\leq\mathbf{e}_{i}\leq 3\log n$ for all
$i$. The event has a probability of at least $1-2/n^{2}$ by a union bound. Let
the event be denoted $\mathcal{E}$. Conditioned on $\mathcal{E}$, we have
$\max_{i}f_{i}/\mathbf{e}_{i}\leq n^{3}F$. Now consider the interval
$I=[F/(Cn\log n),n^{3}F]$. The values $f_{i}/\mathbf{e}_{i}$ that are smaller
than $F/(Cn\log n)$ contribute at most $F/(C\log n)$ to the sum
$\sum_{i=1}^{n}f_{i}/\mathbf{e}_{i}$.

Partition the interval $I$ into $I_{1},\ldots,$ such that
$I_{j}=[2^{j-1}(F/(Cn\log n)),2^{j}(F/(Cn\log n)))$. Note that there are at
most $O(\log n)$ such intervals. We will use the fact that conditioned on
$\mathcal{E}$, the random variables $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ are
still independent.

Let $\mathbf{X}_{j}$ be the number of indices $i$ such that
$f_{i}/\mathbf{e}_{i}\in I_{j}$. We have

$\displaystyle\sum_{i}f_{i}/\mathbf{e}_{i}\leq\frac{F}{C\log
n}+\sum_{j=0}^{O(\log n)}2^{j}\mathbf{X}_{j}\frac{F}{Cn\log n}.$

Let $\mathbf{Y}_{ij}=1$ if $f_{i}/\mathbf{e}_{i}\geq 2^{j-1}(F/(Cn\log n))$
and $\mathbf{Y}_{ij}=0$ otherwise. Note that
$\mathbf{X}_{j}\leq\sum_{i=1}^{n}\mathbf{Y}_{ij}$ and that for a fixed $j$,
the random variables $\mathbf{Y}_{ij}$ are mutually independent given
$\mathcal{E}$. We have

$\displaystyle\operatorname{Pr\/}[\mathbf{Y}_{ij}=1\mid\mathcal{E}]=\operatorname{Pr\/}\left[\mathbf{e}_{i}\leq\frac{Cn\log
n}{2^{j-1}}\frac{f_{i}}{F}\mid\mathcal{E}\right]\leq\frac{2Cn\log
n}{2^{j-1}}\frac{f_{i}}{F}$

since the p.d.f. of the exponential distribution is bounded above by $1$ and
$\operatorname{Pr\/}[\mathcal{E}]\geq 1/2$. By linearity of expectation,
$\operatorname{E\/}[\sum_{i}\mathbf{Y}_{ij}\mid\mathcal{E}]\leq 2Cn\log
n/(2^{j-1})$. By Bernstein’s inequality, we get

$\displaystyle\operatorname{Pr\/}[\sum_{i}\mathbf{Y}_{ij}\geq(\operatorname{E\/}[\sum_{i}\mathbf{Y}_{ij}\mid\mathcal{E}]+t)\mid\mathcal{E}]\leq\exp\left(-\frac{t^{2}/2}{2Cn\log
n/(2^{j-1})+t/3}\right).$

Setting $t=2Cn\log n/(2^{j-1})+6\log n$, we obtain that

$\displaystyle\operatorname{Pr\/}[\sum_{i}\mathbf{Y}_{ij}\geq(\operatorname{E\/}[\sum_{i}\mathbf{Y}_{ij}\mid\mathcal{E}]+t)\mid\mathcal{E}]\leq\frac{1}{n^{2}}.$

We union bound over all $j$ and obtain that for all $j$,

$\displaystyle\mathbf{X}_{j}\leq\frac{2Cn\log n}{2^{j-1}}+6\log n.$

Additionally, we note that if $\mathbf{X}_{j}\neq 0$, then $2^{j}(F/(Cn\log
n))\leq 2\max_{i}f_{i}/\mathbf{e}_{i}$. Now,

$\displaystyle\sum_{i}f_{i}/\mathbf{e}_{i}\leq\frac{F}{C\log
n}+\sum_{j:\mathbf{X}_{j}\neq 0}2^{j}\mathbf{X}_{j}\frac{F}{Cn\log n}$
$\displaystyle\leq\sum_{j:\mathbf{X}_{j}\neq 0}\left(\frac{2Cn\log
n}{2^{j-1}}\frac{2^{j}F}{Cn\log n}+(6\log
n)\max_{i}f_{i}/\mathbf{e}_{i}\right)$ $\displaystyle\leq O(F\log
n)+O(\log^{2}n)\max_{i}f_{i}/\mathbf{e}_{i}.$

As $\max_{i}f_{i}/\mathbf{e}_{i}\geq F/(3\log n)$ with probability $\geq
1-1/n^{2}$ conditioned on $\mathcal{E}$, we get that with probability $\geq
1-1/\operatorname{poly}(n)$,

$\displaystyle\frac{\max_{i}f_{i}/\mathbf{e}_{i}}{\sum_{i}f_{i}/\mathbf{e}_{i}}\geq\frac{1}{C\log^{2}n}.$

If
$\max_{i}f_{i}/\mathbf{e}_{i}\geq(\sum_{i}f_{i}/\mathbf{e}_{i})/C\log^{2}n$,
we obtain that for any parameter $T\geq 1$,

$\displaystyle|\\{i\mid
f_{i}/\mathbf{e}_{i}\geq(1/T)\max_{i}f_{i}/\mathbf{e}_{i}\\}|\leq TC\log^{2}n$

which shows that there are only a small number of indices for which
$f_{i}/\mathbf{e}_{i}$ is comparable to $\max_{i}f_{i}/\mathbf{e}_{i}$.

##  3 Sampling from Additively-Defined Distributions

Consider the setting of $s$ servers with a coordinator. Assume that the $j$-th
server has a non-negative vector $p(j)\in\mathbb{R}^{n}$ and the coordinator
wants $N$ independent samples from the distribution supported on $[n]$ with
the probability of $i\in[n]$ being

$\displaystyle q_{i}\coloneqq\frac{\sum_{j}p_{i}(j)}{\sum_{i,j}p_{i}(j)}.$ (6)

For each sample, we would ideally also want an estimate to the probability of
obtaining that sample. The sampling probabilities are necessary to scale the
statistics appropriately to obtain unbiased estimators. A simple one round
algorithm for sampling from such a distribution is for all the servers $j$ to
send the value $\sum_{i}p_{i}(j)$ and an index $i$ with probability
proportional to $p_{i}(j)$. The coordinator then picks a server $j$ with
probability proportional to $\sum_{i}p_{i}(j)$ and chooses the index $i$ that
the server $j$ sampled. Note that the coordinate $i$ sampled this way has the
desired distribution. While this sampling procedure only requires one round of
communication, note that the coordinator does not have the value
$\sum_{j}p_{i}(j)$ nor even a way to estimate it. Hence if the index $i$ was
sampled by the coordinator, it is not clear how to compute (or even
approximate) $q_{i}$ without further rounds of communication. If another round
of communication is allowed, the coordinator can send the sampled coordinate
$i$ to all the servers which in turn report the values $p_{i}(j)$ from which
the coordinator can compute $q_{i}$ exactly.

Using exponential random variables, we show that there is a protocol using
which the coordinator can sample a coordinate $i$ and approximate the
probability $q_{i}$ with only one round of communication.

Let $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ be independent exponential random
variables that all the servers (and the coordinator) sample using the shared
randomness. Each server $j$ locally computes $\mathbf{e}_{i}^{-1}p_{i}(j)$.
Let
$i^{*}\coloneqq\operatorname*{arg\,max}_{i}\mathbf{e}_{i}^{-1}\sum_{j}p_{i}(j)$.
As we have seen, the probability distribution of $i^{*}$ is exactly as in (6)
and the advantage now is that with probability $\geq
1-1/\operatorname{poly}(n)$,

$\displaystyle\frac{\mathbf{e}_{i^{*}}^{-1}\sum_{j}p_{i^{*}}(j)}{\sum_{i,j}\mathbf{e}_{i}^{-1}p_{i}(j)}\geq\frac{1}{C\log^{2}n}.$

We can further show the following lemma which is helpful to isolate the max
coordinate $i^{*}$.

######  Lemma 3.1.

Let $f_{1},\ldots,f_{n}\geq 0$. and
$i^{*}=\operatorname*{arg\,max}_{i\in[n]}\mathbf{e}_{i}^{-1}f_{i}$ where
$\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ are independent standard exponential
random variables. We have for all $i\in[n]$ that

$\displaystyle\frac{f_{i}}{\sum_{i^{\prime}}f_{i^{\prime}}}\geq\operatorname{Pr\/}\left[i^{*}=i\
\text{and}\
\mathbf{e}_{i^{*}}^{-1}f_{i^{*}}\geq(1+\varepsilon)\max_{i^{\prime}\neq
i^{*}}\mathbf{e}_{i}^{-1}f_{i^{\prime}}\right]\geq\frac{f_{i}}{(1+\varepsilon)\sum_{i^{\prime}}f_{i^{\prime}}}.$

###### Proof.

Fix $i\in[n]$. The probability in the theorem statement is equivalent to the
probability of
$\mathbf{e}_{i}^{-1}f_{i}\geq(1+\varepsilon)\max_{i^{\prime}\neq
i}\mathbf{e}_{i^{\prime}}^{-1}f_{i^{\prime}}$. The probability is clearly at
most $f_{i}/\sum_{i^{\prime}}f_{i^{\prime}}$.

By min-stability of exponential random variables, $\max_{i^{\prime}\neq
i}\mathbf{e}_{i^{\prime}}^{-1}f_{i^{\prime}}$ is distributed as
$\mathbf{e}^{-1}\sum_{i^{\prime}\neq i}f_{i^{\prime}}$. Note that the
exponential random variable $\mathbf{e}$ is independent of $\mathbf{e}_{i}$.
By standard arguments,

$\operatorname{Pr\/}[\mathbf{e}_{i}^{-1}f_{i}\geq\mathbf{e}^{-1}(1+\varepsilon)\sum_{i^{\prime}\neq
i}f_{i}^{\prime}]=\frac{f_{i}}{f_{i}+(1+\varepsilon)\sum_{i^{\prime}\neq
i}f_{i^{\prime}}}\geq\frac{f_{i}}{(1+\varepsilon)\sum_{i^{\prime}}f_{i^{\prime}}}.\qed$

Thus, $\mathbf{e}_{i^{*}}^{-1}\sum_{j}p_{i^{*}}(j)$ in addition to capturing a
_significant_ portion of the interval $\sum_{i,j}\mathbf{e}_{i}^{-1}p_{i}(j)$
is also at least a $1+\varepsilon$ factor larger than the second largest
value. We use these properties to prove the following theorem:

######  Theorem 3.2.

Given that each server $j$ has a non-negative vector $p(j)\in\mathbb{R}^{n}$,
define $q_{i}\coloneqq\sum_{j}p_{i}(j)$. Algorithm 1 outputs FAIL only with
probability $O(\varepsilon)$ and conditioned on not failing, for all $i\in[n]$

$\displaystyle\operatorname{Pr\/}[\hat{i}=i\ \text{and}\ \hat{q}\in(1\pm
O(\varepsilon))\frac{q_{i}}{\sum_{i}q_{i}}]=(1\pm
O(\varepsilon))\frac{q_{i}}{\sum_{i}q_{i}}\pm 1/\operatorname{poly}(n).$

The algorithm uses only one round and has a total communication of
$O(s\operatorname{polylog}(n)/\varepsilon^{2})$ words.

###### Proof.

All the random variables used in the proof are as defined in the algorithm.
The algorithm fails to sample if $\max_{i}\mathbf{X}_{i}\leq S/(2C\log^{2}n)$
or if $\mathbf{X}_{(1)}\leq(1+\varepsilon/2)\mathbf{X}_{(2)}$. Let
$\mathcal{E}$ denote the event that
$\max_{i}\mathbf{e}_{i}^{-1}q_{i}\geq\sum_{i}\mathbf{e}_{i}^{-1}q_{i}/4C\log^{2}n$
and $(\max_{i}\mathbf{e}_{i}^{-1}q_{i})\geq(1+\varepsilon/4)\cdot\text{second-
max}_{i}\,\mathbf{e}_{i}^{-1}q_{i}$. We now bound
$\operatorname{Pr\/}[\mathcal{E}\mid\lnot\text{FAIL}]$. By Bayes’ theorem, we
have

$\displaystyle\operatorname{Pr\/}[\mathcal{E}\mid\lnot\text{FAIL}]=\frac{\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}]\operatorname{Pr\/}[\mathcal{E}]}{\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}]\operatorname{Pr\/}[\mathcal{E}]+\operatorname{Pr\/}[\lnot\text{FAIL}\mid\lnot\mathcal{E}]\operatorname{Pr\/}[\lnot\mathcal{E}]}.$

We have $\operatorname{Pr\/}[\mathcal{E}]\geq
1/(1+\varepsilon/4)-1/\operatorname{poly}(n)$ from the above lemma. Let
$\mathcal{E}^{\prime}$ denote the event that
$\max_{i}\mathbf{e}_{i}^{-1}q_{i}\geq\sum_{i}\mathbf{e}_{i}^{-1}q_{i}/C\log^{2}n$
and $(\max_{i}\mathbf{e}_{i}^{-1}q_{i})\geq(1+\varepsilon)\cdot\text{second-
max}_{i}\,\mathbf{e}_{i}^{-1}q_{i}$. We note that
$\mathcal{E}^{\prime}\subseteq\mathcal{E}$ and that
$\operatorname{Pr\/}[\mathcal{E}^{\prime}]\geq
1/(1+\varepsilon)-1/\operatorname{poly}(n)$. Now,

$\displaystyle\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}]\geq\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}^{\prime}]\operatorname{Pr\/}[\mathcal{E}^{\prime}\mid\mathcal{E}]\geq\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}^{\prime}]\operatorname{Pr\/}[\mathcal{E}^{\prime}].$

Condition on $\mathcal{E}^{\prime}$ and let
$i^{*}=\operatorname*{arg\,max}\mathbf{e}_{i}^{-1}q_{i}$. By a Chernoff bound,
since $S\geq O(C^{2}\log^{5}n/\varepsilon^{2})$ we get that with probability
$\geq 1-1/\operatorname{poly}(n)$

$\displaystyle\mathbf{X}_{i^{*}}\geq
S\frac{\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}(1-\varepsilon/5)>\frac{S}{2C\log^{2}n}.$

Additionally, for all other indices $i$, we get by a Bernstein bound that

$\displaystyle\operatorname{Pr\/}[\mathbf{X}_{i}\geq
S\frac{\mathbf{e}_{i}^{-1}q_{i}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}+\frac{\varepsilon}{8}\frac{S}{C\log^{2}n}]\leq
1/\operatorname{poly}(n).$

Taking a union bound over all the indices $i\neq i^{\prime}$, we get that with
probability $\geq 1-1/\operatorname{poly}(n)$ for all $i\neq i^{\prime}$,

$\displaystyle\mathbf{X}_{i}<S\frac{\mathbf{e}_{i}^{-1}q_{i}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}+\frac{\varepsilon}{4}\frac{S}{C\log^{2}n}\leq
S\frac{\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}(1/(1+\varepsilon)+\varepsilon/8)\leq\frac{1-\varepsilon/5}{1+\varepsilon/2}S\frac{\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}$

when $\varepsilon$ is a small enough constant. Hence
$\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}^{\prime}]\geq
1-1/\operatorname{poly}(n)$ and we get

$\displaystyle\operatorname{Pr\/}[\lnot\text{FAIL}\mid\mathcal{E}]\geq(1-1/\operatorname{poly}(n))(1/(1+\varepsilon)-1/\operatorname{poly}(n)).$

Now similarly, we show that
$\operatorname{Pr\/}[\text{FAIL}\mid\lnot\mathcal{E}]$ is large. Condition on
$\lnot\mathcal{E}$ and again let $i^{*}=\max_{i}\mathbf{e}_{i}^{-1}q_{i}$. If
$\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}/\sum_{i}\mathbf{e}_{i}^{-1}q_{i}\leq
1/4C\log^{2}n$, then again by Bernstein’s bound, we get
$\max_{i}\mathbf{X}_{i}<S/(2C\log^{2}n)$ with probability $\geq
1-1/\operatorname{poly}(n)$. Suppose
$\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}/\sum_{i}\mathbf{e}_{i}^{-1}q_{i}>1/4C\log^{2}n$
but
$\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}/\sum_{i}\mathbf{e}_{i}^{-1}q_{i}<(1+\varepsilon/4)\cdot\text{second-
max}_{i}\,\mathbf{e}_{i}^{-1}q_{i}$. By using a Chernoff bound, we get
$\mathbf{X}_{(1)}<(1+\varepsilon/2)\mathbf{X}_{(2)}$ with a probability $\geq
1-1/\operatorname{poly}(n)$. Hence,
$\operatorname{Pr\/}[\text{FAIL}\mid\lnot\mathcal{E}]\geq
1-1/\operatorname{poly}(n)$. Thus, overall

$\displaystyle\operatorname{Pr\/}[\mathcal{E}\mid\lnot\text{FAIL}]=1-1/\operatorname{poly}(n).$

Now, conditioned on $\lnot\text{FAIL}$ and $\mathcal{E}$, with probability
$\geq 1-1/\operatorname{poly}(n)$, $\hat{i}=i^{*}$ and

$\displaystyle\mathbf{Y}_{\hat{i}}/S=\mathbf{Y}_{i^{*}}/S=(1\pm\varepsilon/2)\frac{\mathbf{e}_{i^{*}}^{-1}q_{i^{*}}}{\sum_{i}\mathbf{e}_{i}^{-1}q_{i}}$

and hence, $\hat{q}=(1\pm\varepsilon/2)q_{i^{*}}/\sum_{i}q_{i}$. Finally,

$\displaystyle\operatorname{Pr\/}[\hat{i}=i\mid\lnot\text{FAIL}]$
$\displaystyle=\operatorname{Pr\/}[\hat{i}=i\mid\lnot\text{FAIL},\mathcal{E}]\operatorname{Pr\/}[\mathcal{E}\mid\lnot\text{FAIL}]+\operatorname{Pr\/}[\hat{i}=i\mid\lnot\text{FAIL},\lnot\mathcal{E}]\operatorname{Pr\/}[\lnot\mathcal{E}\mid\lnot\text{FAIL}]$
$\displaystyle=\operatorname{Pr\/}[i^{*}=i\mid\mathcal{E}]\pm
1/\operatorname{poly}(n)$ $\displaystyle=\frac{q_{i}}{\sum_{i}q_{i}}(1\pm
O(\varepsilon))\pm 1/\operatorname{poly}(n),$

where the last inequality is from the previous lemma. ∎

Input: Each server has a nonnegative vector $p(j)\in\mathbb{R}^{n}$ and a
parameter $\varepsilon$

Output: Samples approximately from the distribution with the probability of
$i$ being $\sum_{j}p_{i}(j)/\sum_{i,j}p_{i}(j)$

1 All the servers agree on independent exponential random variables
$\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ using public randomness

2 $S\leftarrow O(\varepsilon^{-2}\log^{5}n)$

3 For each $j=1,\ldots,s$, the $j$-th server samples $2S$ independent copies
of the random variable $\mathbf{i}$ defined by
$\operatorname{Pr\/}[\mathbf{i}=i]=\mathbf{e}_{i}^{-1}p_{i}(j)/\sum_{i}\mathbf{e}_{i}^{-1}p_{i}(j)$

4 Each server $j$ communicates $\sum_{i}p_{i}(j)$,
$\sum_{i}\mathbf{e}_{i}^{-1}p_{i}(j)$ and the $2S$ sampled coordinates to the
coordinator

5

6The coordinator, using the communication from the servers, samples $2S$
independent copies of the random variable $(\mathbf{j},\mathbf{i})$ defined by
$\displaystyle\operatorname{Pr\/}[(\mathbf{j},\mathbf{i})=(j,i)]=\frac{\mathbf{e}_{i}^{-1}p_{i}(j)}{\sum_{i,j}\mathbf{e}_{i}^{-1}p_{i}(j)}$

7 $\mathbf{X}_{i}\leftarrow$ The number of times $(*,i)$ is sampled in the
first $S$ trials

8 $\mathbf{Y}_{i}\leftarrow$ The number of times $(*,i)$ is sampled in the
second $S$ trials

9 $\mathbf{X}_{(1)},\mathbf{X}_{(2)}\leftarrow$ top two among
$\mathbf{X}_{1},\ldots,\mathbf{X}_{n}$

10 if  _$\mathbf{X}_{(1)} <S/(2C\log^{2}n)$ or
$\mathbf{X}_{(1)}\leq(1+\varepsilon/2)\mathbf{X}_{(2)}$_ then

11 return _FAIL_

12 end if

13$\hat{i}\leftarrow\operatorname*{arg\,max}_{i}\mathbf{Y}_{i}$

14
$\hat{q}\leftarrow\mathbf{e}_{\hat{i}}(\mathbf{Y}_{\hat{i}}/S)\sum_{i,j}\mathbf{e}_{i}^{-1}p_{i}(j)/\sum_{i,j}p_{i}(j)$

return _$(\hat{i},\hat{q})$_

Algorithm 1 Sampling from General Distributions

As the above theorem shows, Algorithm 1 can sample approximately from very
general “additively-defined” distributions. As a simple application, we show
that it can be used to obtain a leverage score sample from the deduplicated
matrix. In this setting, each server $j$ has a matrix $A^{(j)}$ with $d$
columns. Assume that each row $a_{i}$ of the matrix $A^{(j)}$ is associated
with a tag $t_{i}$. Assume that across all the servers, a tag $t$ is always
associated with the same row. Let $A$ be the matrix formed by the rows that
correspond to distinct tags across the servers. For example, suppose a pair of
row and tag $(a,t)$ is present in the servers $1$, $2$ and $3$. In this
deduplicated case, the matrix $A$ has only one copy of the row $a$. Suppose
server $1$ has a pair $(a,1)$ and server $2$ has a pair $(a,2)$ i.e., the same
row is associated with different tags at different servers, then the matrix
$A$ has both the copies of the row. We want to sample rows of $A$ from the
associated $\ell_{2}$ leverage score distribution. For a row $a$ of the matrix
$A$, the leverage score of $a$ with respect to $A$ is defined as

$\displaystyle\tau_{A}(a)\coloneqq\max_{x}\frac{|\langle
a,x\rangle|^{2}}{\|Ax\|_{2}^{2}}.$

If the row $a$ is not in the matrix $A$, we define $\tau_{A}(a)=0$. An
important property of the leverage score distribution is that $\sum_{a\in
A}\ell_{A}(a)=\text{rank}(A)\leq d$ since $A$ has $d$ columns. Given a tag
$t$, let $a_{t}$ be the row associated with the tag $t$. As the matrix $A$ is
formed by the “union” of all the matrices $A^{(1)},\ldots,A^{(t)}$, for any
$x$ we have $\|Ax\|_{2}^{2}\geq\|A^{(j)}x\|_{2}^{2}$. Hence if $a$ is a row of
the matrix $A^{(j)}$, then $\tau_{A^{(j)}}(a)\geq\tau_{A}(a)$. Let the tags be
drawn from a set $T$. Each server $j$ can now define a $|T|$-dimensional
vector $p(j)$ such that for each $t\in T$

$\displaystyle p_{t}(j)=\tau_{A^{(j)}}(a_{t}).$

Here we note that if the tag $t$ is not present in the matrix $A^{(j)}$, we
have $p_{t}(j)=0$. We now have for any tag $t$,

$\displaystyle\frac{\sum_{j=1}^{s}p_{t}(j)}{\sum_{j=1}^{s}\sum_{t\in
T}p_{t}(j)}=\frac{\sum_{j=1}^{s}\tau_{A^{(j)}}(a_{t})}{\sum_{j=1}^{s}\sum_{t\in
T}\tau_{A^{(j)}}(a_{t})}\geq\frac{\tau_{A}(a_{t})}{\sum_{j=1}^{s}\text{rank}(A^{(j)})}\geq\frac{\tau_{A}(a_{t})}{s\cdot\text{rank}(A)}.$

Here, we used the monotonicity of leverage scores which directly follows from
the definition. Such a sampling distribution is an $s$-approximate leverage
score distribution and has numerous applications such as computing subspace
embeddings [39]. This application shows that Algorithm 1 can sample from
useful distributions and importantly give approximations to the probabilities
of the samples using only one round of communication.

While this very general sampling procedure can be used to construct a subspace
embedding for the deduplicated matrix in the coordinator model, it is unclear
how to extend these algorithms to more general topologies to obtain algorithms
in the personalized CONGEST model in which we want the protocols to have
additional nice properties as discussed in the introduction. In later
sections, we define the concept of composable sketches and how they are useful
to obtain protocols in the personalized CONGEST model.

##  4 A Two Round Protocol for Sum Approximation

Recall that we say a non-negative function $f$ satisfies “approximate
invertibility” with parameters
$\theta,\theta^{\prime},\theta^{\prime\prime}>1$ if the following hold:

  1. 1.

for all $x_{1},x_{2}\geq 0$, it holds that $f(x_{1})+f(x_{2})\leq
f(x_{1}+x_{2})$ which additionally implies that $f(0)=0$,

  2. 2.

for all $x$, $f(\theta^{\prime}x)\geq\theta f(x)$, and

  3. 3.

for all $x$, $f(x/(4\cdot\sqrt{\theta}\cdot\theta^{\prime}))\geq
f(x)/\theta^{\prime\prime}$.

Note that plugging $x=f^{-1}(z)$ in the second property above, we get
$\theta^{\prime}f^{-1}(z)\geq f^{-1}(\theta z)$. We now define
$\varepsilon_{1}\coloneqq 1/\theta^{\prime\prime}$ and
$\varepsilon_{2}\coloneqq 1-1/\theta^{\prime\prime}$. We can show that for all
values of $0\leq x_{2}\leq x_{1}$, if $f(x_{2})\leq\varepsilon_{1}f(x_{1})$,
then $f(x_{1}-x_{2})\geq(1-\varepsilon_{2})f(x_{1})$. This essentially shows
that if $f(x_{2})$ is very small as compared to $f(x_{1})$, then
$f(x_{1}-x_{2})$ can not be very small when compared to $f(x_{1})$. These
properties make the function $f$ “approximately invertible”, meaning that good
approximations for $f(x)$ will let us approximate the preimage $x$ as well. We
say that a function $f$ that satisfies the above properties is “approximately
invertible” with parameters $\theta,\theta^{\prime},\theta^{\prime\prime}$.

Note that for an integer $s\geq 1$, we defined $c_{f}[s]$ to be the smallest
number such that for all $x_{1},\ldots,x_{s}\geq 0$,

$\displaystyle
f(x_{1}+\cdots+x_{s})\leq\frac{c_{f}[s]}{s}\left(\sqrt{f(x_{1})}+\cdots+\sqrt{f(x_{s})}\right)^{2}.$

Using the Cauchy-Schwarz inequality, we additionally have

$f(x_{1}+\cdots+x_{s})\leq c_{f}[s]\left(f(x_{1})+\cdots+f(x_{s})\right)$

for all $x_{1},\ldots,x_{s}\geq 0$. We show that the parameter $c_{f}[s]$ as a
function of $s$ cannot grow arbitrarily. Consider arbitrary integers $s,t\geq
1$. The following lemma shows that $c_{f}[s\cdot t]\leq c_{f}[s]\cdot
c_{f}[t]$ which implies that the function $c_{f}[s]$ is upper bounded by a
polynomial in $s$ with a degree that depends only on $c_{f}[2]$.

######  Lemma 4.1.

For any $x_{1},x_{2},\ldots,x_{s\cdot t}\geq 0$,

$\displaystyle f(x_{1}+\cdots+x_{s\cdot t})\leq\frac{c_{f}[s]\cdot
c_{f}[t]}{s\cdot t}\left(\sqrt{f(x_{1})}+\cdots+\sqrt{f(x_{s\cdot
t})}\right)^{2}.$

###### Proof.

By definition of $c_{f}[s]$, we obtain

$\displaystyle f(x_{1}+\cdots+x_{s\cdot t})$
$\displaystyle\leq\frac{c_{f}[s]}{s}\left(\sqrt{f(x_{1}+\cdots+x_{t})}+\sqrt{f(x_{t+1})+\cdots+f(x_{2\cdot
t})}+\cdots+\sqrt{f(x_{(s-1)\cdot t+1}+\cdots+f(x_{s\cdot t}))}\right)^{2}.$

Now we use $c_{f}[t]$ to expand the internal terms, to get

$\displaystyle f(x_{1}+\cdots+x_{s\cdot
t})\leq\frac{c_{f}[s]}{s}\frac{c_{f}[t]}{t}\left(\sqrt{f(x_{1})}+\cdots+\sqrt{f(x_{s\cdot
t})}\right)^{2}.$

By definition of $c_{f}[s\cdot t]$, we obtain $c_{f}[s\cdot t]\leq
c_{f}[s]\cdot c_{f}[t]$. ∎

The above lemma upper bounds the growth of the parameter $c_{f}[s]$. We now
lower bound the growth and show that $c_{f}[s]$ must grow at least linearly in
the parameter $s$.

######  Lemma 4.2.

If $s\geq t$, then $c_{f}[s]\geq c_{f}[t]\cdot s/t$.

###### Proof.

Let $x_{1},\ldots,x_{t}\geq 0$ be arbitrary.

$\displaystyle f(x_{1}+\cdots+x_{t})$
$\displaystyle=f(x_{1}+\cdots+x_{t}+\underbrace{0+\cdots+0}_{s-t})$
$\displaystyle\leq\frac{c_{f}[s]}{s}\left(\sqrt{f(x_{1})}+\cdots+\sqrt{f(x_{t})}+\underbrace{\sqrt{f(0)}+\cdots+\sqrt{f(0)}}_{s-t}\right)^{2}$
$\displaystyle\leq\frac{c_{f}[s]}{s}(\sqrt{f(x_{1})}+\cdots+\sqrt{f(x_{t})})^{2}$

where we used $f(0)=0$ in the last inequality. Hence by definition of
$c_{f}[t]$, we get $c_{f}[t]/t\leq c_{f}[s]/s$ from which we obtain that
$c_{f}[s]\geq c_{f}[t]\cdot s/t$. ∎

Using the above properties, we obtain that $c_{f}[s]\leq
c_{f}[2^{\lceil\log_{2}(s)\rceil}]\leq(c_{f}[2])^{\lceil\log_{2}(s)\rceil}\leq
c_{f}[2]\cdot s^{\log_{2}c_{f}[2]}$ which shows that $c_{f}$ only grows at
most _polynomially_ in the number of servers $s$ and the degree of growth is
upper bounded $\log_{2}c_{f}[2]$. For example, if $f(x)=x^{k}$, then we can
show $c_{f}[2]=2^{k-1}$ from which we obtain that $c_{f}[s]\leq(2s)^{k-1}$ for
all the values of $s$.

In addition, if $c_{f}[t]\geq c_{f}[s]/\alpha$ for some value $\alpha$, using
the second property above, we obtain $c_{f}[s]\geq c_{f}[t]\cdot
s/t\geq(c_{f}[s]/\alpha)\cdot(s/t)$ which implies $t\geq s/\alpha$. Thus if
$c_{f}[t]$ is “comparable” to $c_{f}[s]$, then $t$ is “comparable” to $s$ as
well. This is a property that we critically use in the analysis of our
algorithm.

### Protocol Description and Analysis

We now recall the overview of the algorithm we presented in the introduction
and define some notation that we use throughout our analysis. All the servers
together with the coordinator use the shared randomness and sample standard
exponential random variables $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ and the
goal of the coordinator is to compute

$\displaystyle\max_{i}\mathbf{e}_{i}^{-1}f(x_{i}).$

Define
$i^{*}\coloneqq\operatorname*{arg\,max}_{i}\mathbf{e}_{i}^{-1}f(x_{i})$. We
have seen that the median of $O(1/\varepsilon^{2})$ independent copies of the
random variable $\max_{i}\mathbf{e}_{i}^{-1}f(x_{i})$ can be used to compute a
$1\pm\varepsilon$ approximation to $\sum_{i}f(x_{i})$ with high probability.
Throughout the analysis, we condition on the event that

$\displaystyle\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\max_{i}\mathbf{e}_{i}^{-1}f(x_{i}).$

We have seen that this event holds with probability $\geq
1-1/\operatorname{poly}(n)$ over the exponential random variables. Now fix a
server $j\in[s]$. The server $j$ samples $N$ independent copies of the random
variable $\mathbf{i}$ supported in the set $[n]$ and has a distribution
defined as

$\displaystyle\operatorname{Pr\/}[\mathbf{i}=i]=\frac{\mathbf{e}_{i}^{-1}f(x_{i})}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})}.$

Let $\textnormal{{{SC}}}_{j}$ denote the set of coordinates that are sampled
by the server $j$. The server $j$ then sends the set $\textnormal{{{SC}}}_{j}$
along with (i) the sum $\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ and (ii) the
values $x_{i}(j)$ for $i\in\textnormal{{{SC}}}_{j}$ to the coordinator using
$O(N)$ words of communication.

The coordinator defines the set
$\textnormal{{{SC}}}\coloneqq\bigcup_{j}\textnormal{{{SC}}}_{j}$ as the union
of the sets of coordinates that are sampled at different servers. We will
first show that the coordinate $i^{*}\in\textnormal{{{SC}}}$ with a large
probability if $N$ is large enough.

###  4.1 The coordinate $i^{*}$ is sampled

######  Lemma 4.3.

If $N\geq(C_{\ref{lma:i-star-is-sampled}}\log^{3}n)\cdot c_{f}[s]/s$ for a
universal constant $C_{\ref{lma:i-star-is-sampled}}$ large enough, then the
coordinate $i^{*}\in\textnormal{{{SC}}}$ with a probability $\geq 1-1/n^{4}$.

###### Proof.

Let
$q_{i^{*}}(j)=\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}(j))/\sum_{i\in[n]}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
be the probability that the random variable $\mathbf{i}=i^{*}$ (note that the
random variable $\mathbf{i}$ has a different distribution at each server) and
$p_{i^{*}}(j)$ be the probability that $i^{*}\in\textnormal{{{SC}}}_{j}$. We
have

$\displaystyle p_{i^{*}}(j)=1-\left(1-q_{i^{*}}(j)\right)^{N}.$

If $q_{i^{*}}(j)=(4\log n)/N$, then $p_{i^{*}}(j)\geq
1-(1-q_{i^{*}}(j))^{N}\geq 1-\exp(-q_{i^{*}}(j)N)\geq 1-\exp(-4\log n)\geq
1-1/n^{4}$ which implies that
$i^{*}\in\textnormal{{{SC}}}_{j}\subseteq\textnormal{{{SC}}}$ with probability
$\geq 1-1/n^{4}$ and we are done. Otherwise,

$\displaystyle
p_{i^{*}}(j)=1-(1-q_{i^{*}}(j))^{N}\geq\frac{Nq_{i^{*}}(j)}{4\log
n}(1-1/n^{4})$ (7)

using the concavity of the function $1-(1-x)^{N}$ in the interval $[0,4\log
n/N]$.

Since each of the servers samples the coordinates independently, the
probability that $i^{*}\in\textnormal{{{SC}}}$ is
$1-(1-p_{i^{*}}(1))(1-p_{i^{*}}(2))\cdots(1-p_{i^{*}}(s))\geq
1-\exp(-\sum_{j}p_{i^{*}}(j))$. So, showing that the sum
$\sum_{j}p_{i^{*}}(j)$ is large implies that $i^{*}$ is in the set SC with a
large probability. Assume that for all $j$, $q_{i^{*}}(j)<4\log n/N$ since
otherwise we already have that the coordinate $i^{*}\ \in\textnormal{{{SC}}}$
with probability $\geq 1-1/n^{4}$. Now using (7)

$\displaystyle\sum_{j}p_{i^{*}}(j)\geq\frac{N}{8\log
n}\sum_{j}q_{i^{*}}(j)=\frac{N}{8\log
n}\sum_{j}\frac{\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}.$

We will now give a lower bound on the the sum in the above equation using the
following simple lemma and the definition of the parameter $c_{f}[s]$.

######  Lemma 4.4.

Let $a_{1},\ldots,a_{s}\geq 0$ and $b_{1},\ldots,b_{s}>0$ be arbitrary. Then,

$\displaystyle\sum_{j\in[s]}\frac{a_{j}}{b_{j}}\geq\frac{(\sum_{j\in[s]}\sqrt{a_{j}})^{2}}{\sum_{j}b_{j}}.$

###### Proof.

We prove the lemma by using the Cauchy-Schwarz inequality. Since we assume
that $b_{j}>0$ for all $j$, we can write

$\displaystyle\sum_{j\in[s]}\sqrt{a_{j}}=\sum_{j\in[s]}\sqrt{\frac{a_{j}}{b_{j}}}\sqrt{b_{j}}.$

Using the Cauchy-Schwarz inequality, we get

$\displaystyle\sum_{j\in[s]}\sqrt{a_{j}}=\sum_{j\in[s]}\sqrt{\frac{a_{j}}{b_{j}}}\sqrt{b_{j}}\leq\sqrt{\sum_{j\in[s]}\frac{a_{j}}{b_{j}}}\sqrt{\sum_{j\in[s]}b_{j}}.$

Squaring both sides and using the fact that $\sum_{j\in[s]}b_{j}>0$, we get

$\displaystyle\sum_{j\in[s]}\frac{a_{j}}{b_{j}}\geq\frac{(\sum_{j\in[s]}\sqrt{a_{j}})^{2}}{\sum_{j\in[s]}b_{j}}.$

Letting $a_{j}=\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}(j))$ and
$b_{j}=\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ in the above lemma, we get

$\displaystyle\sum_{j}\frac{\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}\geq\frac{\mathbf{e}_{i^{*}}^{-1}(\sum_{j\in[s]}\sqrt{f(x_{i^{*}}(j))})^{2}}{\sum_{j}\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}.$

Using the definition of $c_{f}[s]$, we obtain

$\displaystyle\left(\sum_{j\in[s]}\sqrt{f(x_{i^{*}}(j))}\right)^{2}\geq\frac{s}{c_{f}[s]}(f(x_{i^{*}}(1)+\cdots
x_{i^{*}}(s)))=\frac{s}{c_{f}[s]}f(x_{i^{*}}).$

Using the super-additivity of the function $f$, we get

$\displaystyle\sum_{j}\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))=\sum_{i}\mathbf{e}_{i}^{-1}\sum_{j}f(x_{i}(j))\leq\sum_{i}\mathbf{e}_{i}^{-1}f(\sum_{j}x_{i}(j))=\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}).$

Since we conditioned on the event that
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$,
we get

$\displaystyle\sum_{j}\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

We therefore have

$\displaystyle\sum_{j}\frac{\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}\geq\frac{s}{c_{f}[s]}\frac{\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})}{(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})}\geq\frac{s}{C\log^{2}n\cdot
c_{f}[s]}.$

Thus, if $N\geq(32C\log^{3}n)\cdot c_{f}[s]/s$, then $\sum_{j}p_{i^{*}}(j)\geq
4\log n$ which implies that $i^{*}$ is in the set SC with probability $\geq
1-1/n^{4}$. Letting $C_{\ref{lma:i-star-is-sampled}}\coloneqq 32C$, we have
the proof. ∎

When $N\gg c_{f}[s]\log^{3}n/s$ as is required by the above lemma, the set
$\textnormal{{{SC}}}=\bigcup_{j}\textnormal{{{SC}}}_{j}$ may have a size of
$\Omega(c_{f}[s]\log^{3}n)$ which is quite large. Conditioned on the event
that $i^{*}\in\textnormal{{{SC}}}$, we now want to compute a small subset
$\textnormal{{{PL}}}\subseteq\textnormal{{{SC}}}$ such that
$i^{*}\in\textnormal{{{PL}}}$ with a large probability.

###  4.2 Computing the set PL

Recall we condition on the event that

$\displaystyle\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$

and that $i^{*}\in\textnormal{{{SC}}}$. As we noted in the introduction, we
proceed by constructing an estimator $\hat{x}_{i}$ for each
$i\in\textnormal{{{SC}}}$ that satisfies the following properties with a
probability $1-1/\operatorname{poly}(n)$:

  1. 1.

For all $i\in\textnormal{{{SC}}}$, $\hat{x}_{i}\leq x_{i}$ and

  2. 2.

$\mathbf{e}_{i^{*}}^{-1}f(\hat{x}_{i^{*}})\geq\alpha\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
for some $\alpha<1$.

Fix an index $i\in[n]$. In the remaining part of this section, we will
describe a quantity that the coordinator can approximate to obtain
$\hat{x}_{i}$ which satisfies the above properties.

####  4.2.1 Contribution from Large servers

We define $\textnormal{{Large}}_{i}$ to be the set of servers $j$ such that

$\displaystyle
q_{i}(j)=\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}\geq\frac{4\log
n}{(c_{f}[s]\log^{3}n)/s}.$

Note if $i\in\textnormal{{{SC}}}_{j}$, then the coordinator can determine if
$j\in\textnormal{{Large}}_{i}$ since it has access to both the values
$\mathbf{e}_{i}^{-1}f(x_{i}(j))$ and $\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$.
We have the following lemma:

######  Lemma 4.5.

If $N\geq(c_{f}[s]\log^{3}n)/s$, then with probability $\geq 1-1/n^{3}$, for
all the coordinates $i$ and servers $j\in\textnormal{{Large}}_{i}$, we have
$i\in\textnormal{{{SC}}}_{j}$. In other words, with a large probability, all
the coordinates $i$ are sampled at all the servers that are in the set
$\textnormal{{Large}}_{i}$.

###### Proof.

Recall that $\textnormal{{{SC}}}_{j}$ denotes the set of coordinates that are
sampled at server $j$. Consider a fixed $i\in[n]$. If
$j\in\textnormal{{Large}}_{i}$, then the probability that $i$ is sampled at
server $j$ is $1-(1-q_{i}(j))^{N}\geq 1-(1-4\log
n/(c_{f}[s]\log^{3}n/s))^{N}\geq 1-\exp(-4\log n)\geq 1-1/n^{4}$ using
$N\geq(c_{f}[s]\log^{3}n)/s$. By a union bound over all the servers $j$ that
are Large for $i$, we have the proof. ∎

Thus with a large probability, for each $i\in[n]$, the contribution to
$x_{i}=\sum_{j}x_{i}(j)$ from servers $j\in\textnormal{{Large}}_{i}$ can be
computed exactly by the coordinator after it receives the samples from the
servers.

####  4.2.2 Contribution from Small servers

We now define $\textnormal{{Small}}_{i}$ to be the set of servers $j$ for
which

$\displaystyle
q_{i}(j)=\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}\leq\frac{\varepsilon_{1}}{c_{f}[s]\cdot(C\log^{2}n)}.$

We have

$\displaystyle\sum_{j\in\textnormal{{Small}}_{i}}\mathbf{e}_{i}^{-1}f(x_{i}(j))\leq\sum_{j\in\textnormal{{Small}}_{i}}\frac{\varepsilon_{1}\sum_{i^{\prime}}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}}(j))}{c_{f}[s]\cdot(C\log^{2}n)}\leq\frac{\varepsilon_{1}\cdot(C\log^{2}n)\cdot(\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}))}{c_{f}[s]\cdot(C\log^{2}n)}=\frac{\varepsilon_{1}\cdot(\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}))}{c_{f}[s]}$

where we used the fact that

$\sum_{j\in\textnormal{{Small}}_{i}}\sum_{i^{\prime}}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}}(j))=\sum_{i^{\prime}}\sum_{j\in\textnormal{{Small}}_{i}}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}}(j))\leq\sum_{i^{\prime}}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}})\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

By definition of the parameter $c_{f}[s]$, we then obtain that

$\displaystyle\mathbf{e}_{i}^{-1}f(\sum_{j\in\textnormal{{Small}}_{i}{}}x_{i}(j))\leq
c_{f}[s]\cdot\mathbf{e}_{i}^{-1}\sum_{j\in\textnormal{{Small}}_{i}{}}f(x_{i}(j))\leq\varepsilon_{1}\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$

which then implies

$\displaystyle\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}-\sum_{j\in\textnormal{{Small}}_{i^{*}}{}}x_{i^{*}}(j))\geq(1-\varepsilon_{2})\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$
(8)

Hence we can ignore the contribution of the servers in
$\textnormal{{Small}}_{i}$ when computing $\hat{x}_{i}$.

####  4.2.3 Contribution from Remaining Servers

From the above, we have for each coordinate $i\in[n]$, we can compute the
contribution of servers $j\in\textnormal{{Large}}_{i}$ exactly and ignore the
contribution of servers in $\textnormal{{Small}}_{i}$ while still being able
to satisfy the required properties for $\hat{x}_{i}$. We will now show how to
estimate the contribution of servers $j$ that are neither in
$\textnormal{{Large}}_{i}$ nor in $\textnormal{{Small}}_{i}$. Note that for
such servers, the value
$q_{i}(j)=\mathbf{e}_{i}^{-1}f(x_{i}(j))/\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
lies in the interval

$\displaystyle\left[\frac{\varepsilon_{1}}{c_{f}[s]\cdot(C\log^{2}n)},\frac{4s}{c_{f}[s]\log^{2}n}\right].$

We now partition555We do not require it and so are not too careful about
ensuring that the intervals we use are disjoint. the above interval into
intervals with lengths geometrically increasing by a factor of
$\sqrt{\theta}$. Let
$P_{\text{start}}=\frac{\varepsilon_{1}}{c_{f}[s]\cdot(C\log^{2}n)}$ and we
partition the above interval into intervals
$[P_{\text{start}},\sqrt{\theta}P_{\text{start}}],[\sqrt{\theta}P_{\text{start}},(\sqrt{\theta})^{2}P_{\text{start}}],\ldots,$
and so on. We note that there are at most

$\displaystyle A=O\left(\frac{\log(s/\varepsilon_{1})}{\log\theta}\right)$ (9)

such intervals in the partition.

Let $I^{(a)}_{i}$ denote the set of servers $j$ such that
$q_{i}(j)\in[(\sqrt{\theta})^{a}P_{\text{start}},(\sqrt{\theta})^{a+1}P_{\text{start}}]$.
If $|I^{(a)}_{i}|$ is large enough, then the number of servers $j$ in
$I^{(a)}_{i}$ at which the coordinate $i$ is sampled is “concentrated” which
can then be used to estimate $|I^{(a)}_{i}|$. But observe that even having an
estimate of $|I^{(a)}_{i}|$ is insufficient since we cannot directly estimate
$\sum_{j\in I^{(a)}}x_{i}(j)$ only given $|I^{(a)}_{i}|$ as the servers in the
set $I^{(a)}_{i}$ may have quite different values for
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$. So we further partition the servers
based on the value of $\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$. We first give
a lower bound on the values $\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ that we
need to consider.

######  Lemma 4.6.

If the server $j\notin\textnormal{{Small}}_{i}\cup\textnormal{{Large}}_{i}$
and
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))\leq\frac{\varepsilon_{1}(1-\varepsilon_{2})\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j))}{4Cs^{2}}$,
then the contribution from all those servers can be ignored.

###### Proof.

Let $\textnormal{{Ignore}}_{i}$ be the set of servers $j$ that are neither in
$\textnormal{{Large}}_{i}$ nor in $\textnormal{{Small}}_{i}$ and have
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))\leq\frac{\sum_{i,j}\varepsilon_{1}(1-\varepsilon_{2})\mathbf{e}_{i}^{-1}f(x_{i}(j))}{4Cs^{2}}$.
By definition, we have

$\displaystyle\sum_{j\in\textnormal{{Ignore}}_{i}}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
$\displaystyle\leq\sum_{j\in\textnormal{{Ignore}}_{i}}\frac{4s}{c_{f}[s]\log^{2}n}\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
$\displaystyle\leq\frac{4s\cdot|\textnormal{{Ignore}}_{i}|}{c_{f}[s]\log^{2}n}\frac{\varepsilon_{1}(1-\varepsilon_{2})\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j))}{4Cs^{2}}.$

Using the definition of $c_{f}[s]$ and the Cauchy-Schwarz inequality, we then
obtain

$\displaystyle\mathbf{e}_{i}^{-1}f(\sum_{j\in\textnormal{{Ignore}}_{i}}x_{i}(j))$
$\displaystyle\leq\frac{c_{f}[s]}{s}\cdot|\textnormal{{Ignore}}_{i}|\cdot\sum_{j\in\textnormal{{Ignore}}_{i}}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
$\displaystyle\leq\frac{4|\textnormal{{Ignore}}_{i}|^{2}}{\log^{2}n}\frac{\varepsilon_{1}(1-\varepsilon_{2})\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j))}{4Cs^{2}}.$

Since
$\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j))\leq(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i}^{*})$
and $|\textnormal{{Ignore}}_{i}|\leq s$, we get

$\displaystyle\mathbf{e}_{i}^{-1}f(\sum_{j\in\textnormal{{Ignore}}_{i}}x_{i}(j))\leq\varepsilon_{1}(1-\varepsilon_{2})\mathbf{e}_{i^{*}}^{-1}f(x_{i}^{*}).$

Taking $i=i^{*}$, we get
$\mathbf{e}_{i^{*}}^{-1}f(\sum_{j\in\textnormal{{Ignore}}_{i^{*}}}x_{i^{*}}(j))\leq\varepsilon_{1}(1-\varepsilon_{2})\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
and therefore using (8) we obtain that

$\displaystyle\mathbf{e}_{i^{*}}^{-1}f(\sum_{j\in\textnormal{{Ignore}}_{i^{*}}}x_{i^{*}}(j))\leq\mathbf{e}_{i^{*}}^{-1}\varepsilon_{1}f(x_{i^{*}}-\sum_{j\in\textnormal{{Small}}_{i^{*}}}x_{i^{*}}(j))$

from which we then get

$\displaystyle\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}-\sum_{j\in\textnormal{{Small}}_{i^{*}}}x_{i^{*}}(j)-\sum_{j\in\textnormal{{Ignore}}_{i^{*}}}x_{i^{*}}(j))\geq(1-\varepsilon_{2})^{2}\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

Thus the contribution from the servers in the set
$\textnormal{{Ignore}}_{i^{*}}$ can be ignored as we can make
$\mathbf{e}_{i^{*}}^{-1}f(\hat{x}_{i^{*}})$ large even without them. ∎

So we only have to focus on the servers for which the quantity
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ lies in the interval

$\displaystyle\left[\frac{\varepsilon_{1}(1-\varepsilon_{2})}{4Cs^{2}}\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j)),\max_{j}\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))\right].$

Now define
$F_{\text{start}}\coloneqq\frac{\varepsilon_{1}(1-\varepsilon_{2})}{4Cs^{2}}\sum_{i,j}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
and partition the above interval into intervals
$[F_{\text{start}},(\sqrt{\theta}F_{\text{start}})]$,
$[(\sqrt{\theta})F_{\text{start}},(\sqrt{\theta})^{2}F_{\text{start}}]$,
$\ldots$, and so on. Note that there are at most

$\displaystyle
B=O\left(\frac{\log(s^{2}/\varepsilon_{1}(1-\varepsilon_{2}))}{\log\theta}\right)$
(10)

such intervals. Let $I^{(a,b)}_{i}$ for $a=0,1,\ldots,A-1$ and
$b=0,1,\ldots,B-1$ be the set of servers $j$ for which

$\displaystyle\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}\in[(\sqrt{\theta})^{a}P_{\text{start}},(\sqrt{\theta})^{a+1}P_{\text{start}}],$

and

$\displaystyle\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))\in[(\sqrt{\theta})^{b}F_{\text{start}},(\sqrt{\theta})^{b+1}F_{\text{start}}].$

If the set $|I^{(a,b)}_{i}|$ is large, then the number of servers $j\in
I^{(a,b)}_{i}$ at which $i$ is sampled is concentrated which can then in turn
be used to approximate $|I^{(a,b)}_{i}|$. But if $|I^{(a,b)}_{i}|$ is too
small, then we cannot obtain a good approximation using the number of servers
in the set $I^{(a,b)}_{i}$ that sample $i$. In the following lemma, we show
that the contribution from servers in the sets $I^{(a,b)}_{i}$ needs to be
considered only if $|I^{(a,b)}_{i}|$ is large. Let $\textnormal{{Bad}}_{i}$
denote the set of tuples $(a,b)$ for which

$\displaystyle c_{f}[|I^{(a,b)}_{i}|]\leq\frac{c_{f}[s]}{c_{f}[A\cdot
B]\cdot(A\cdot B)\cdot(\sqrt{\theta})^{a+1}/(1-\varepsilon_{2})^{2}}.$ (11)

Let $\textnormal{{Good}}_{i}$ be the set of all the remaining tuples $(a,b)$.
We first note that the coordinator cannot determine if a particular tuple
$(a,b)$ is in the set $\textnormal{{Bad}}_{i}$. Using the properties of
$c_{f}[s]$, we get that if $(a,b)\in\textnormal{{Good}}_{i}$, then

$\displaystyle|I_{i}^{(a,b)}|\geq\frac{s}{c_{f}[A\cdot B]\cdot(A\cdot
B)\cdot(\sqrt{\theta})^{a+1}/(1-\varepsilon_{2})^{2}}.$

######  Lemma 4.7.

The contribution from servers
$j\in\bigcup_{(a,b)\in\textnormal{{Bad}}_{i}}I^{(a,b)}_{i}$ can be ignored.

###### Proof.

By definition of the set of servers $I^{(a,b)}_{i}$,

$\displaystyle\sum_{j\in I^{(a,b)}_{i}}\mathbf{e}_{i}^{-1}f(x_{i}(j))$
$\displaystyle\leq\sum_{j\in
I_{i}^{(a,b)}}(\sqrt{\theta})^{a+1}P_{\text{start}}\sum_{i^{\prime}\in[n]}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}}(j))$
$\displaystyle\leq(\sqrt{\theta})^{a+1}P_{\text{start}}\sum_{i^{\prime}\in[n]}\mathbf{e}_{i^{\prime}}^{-1}\sum_{j\in
I_{i}^{(a,b)}}f(x_{i^{\prime}}(j))$
$\displaystyle\leq(\sqrt{\theta})^{a+1}P_{\text{start}}\sum_{i^{\prime}\in[n]}\mathbf{e}_{i^{\prime}}^{-1}f(x_{i^{\prime}})$
$\displaystyle\leq(\sqrt{\theta})^{a+1}P_{\text{start}}\cdot(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

By definition of the parameter $c_{f}$, we have

$\displaystyle\mathbf{e}_{i}^{-1}f\left(\sum_{(a,b)\in\textnormal{{Bad}}_{i}}\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)\right)$ $\displaystyle\leq c_{f}[A\cdot
B]\left(\sum_{(a,b)\in\textnormal{{Bad}}_{i}}\mathbf{e}_{i}^{-1}f(\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j))\right)$ $\displaystyle\leq c_{f}[A\cdot
B]\sum_{(a,b)\in\textnormal{{Bad}}_{i}}c_{f}[|I^{(a,b)}_{i}|]\sum_{j\in
I^{(a,b)}_{i}}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ $\displaystyle\leq c_{f}[A\cdot
B]\sum_{(a,b)\in\textnormal{{Bad}}_{i}}c_{f}[|I^{(a,b)}_{i}|]\cdot(\sqrt{\theta})^{a+1}P_{\text{start}}\cdot(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$
$\displaystyle\leq c_{f}[A\cdot
B]\sum_{(a,b)\in\textnormal{{Bad}}_{i}}c_{f}[|I^{(a,b)}_{i}|]\cdot(\sqrt{\theta})^{a+1}\cdot\frac{\varepsilon_{1}}{c_{f}[s]\cdot(C\log^{2}n)}\cdot(C\log^{2}n)\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

Using (11), we get

$\displaystyle\mathbf{e}_{i}^{-1}f\left(\sum_{(a,b)\in\textnormal{{Bad}}_{i}}\sum_{j\in
I_{i}^{(a,b)}}x_{i}(j)\right)\leq(1-\varepsilon_{2})^{2}\varepsilon_{1}\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

Taking $i=i^{*}$, we get that

$\displaystyle\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}-\sum_{j\in\textnormal{{Small}}_{i^{*}}}x_{i^{*}}(j)-\sum_{j\in\textnormal{{Ignore}}_{i^{*}}}x_{i^{*}}(j)-\sum_{(a,b)\in\textnormal{{Bad}}_{i}}\sum_{j\in
I^{(a,b)}_{i^{*}}}x_{i^{*}}(j))\geq(1-\varepsilon_{2})^{3}\cdot\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

Thus the contribution from the servers in the set $I^{(a,b)}_{i}$ for tuples
$(a,b)\in\textnormal{{Bad}}_{i}$ can be ignored. ∎

Now we show that the coordinator can compute $\hat{x}_{i}$ by essentially
approximating the following quantity:

$\displaystyle
x_{i}-\sum_{j\in\textnormal{{Small}}_{i}}x_{i}(j)-\sum_{j\in\textnormal{{Ignore}}_{i}}x_{i}(j)-\sum_{(a,b)\in\textnormal{{Bad}}_{i}}\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)$
$\displaystyle=\sum_{j\in\textnormal{{Large}}_{i}}x_{i}(j)+\sum_{(a,b)\in\textnormal{{Good}}_{i}}\sum_{j\in
I_{i}^{(a,b)}}x_{i}(j).$

####  4.2.4 Algorithm to compute $\hat{x}_{i}$

We will go on to give an algorithm that can approximate $\hat{x}_{i}$ given
the samples that the coordinator receives in the first round. We have already
seen that given an index $i$, all the servers in the set
$\textnormal{{Large}}_{i}$ sample the coordinate $i$ with a large probability
and therefore we can compute the quantity
$\sum_{j\in\textnormal{{Large}}_{i}}x_{i}(j)$ exactly with high probability.
We have also seen that the contribution from servers that are in the set
$\textnormal{{Small}}_{i}$ and in the set $\textnormal{{Ignore}}_{i}$ can be
ignored.

The main remaining contribution to $x_{i}$ that is to be accounted is from
tuples $(a,b)\in\textnormal{{Good}}_{i}$. An important issue we need to solve
for is the fact that the coordinator cannot determine if a given tuple $(a,b)$
is in the set $\textnormal{{Good}}_{i}$ or in $\textnormal{{Bad}}_{i}$. We
will show that if $(a,b)\in\textnormal{{Good}}_{i}$, then $i$ is sampled at
many servers in the set $I^{(a,b)}_{i}$ and depending on the _absolute_ number
of servers in $I^{(a,b)}_{i}$ that sample $i$, we mark a tuple $(a,b)$ as
“probably good for $i$”. We argue that, with high probability, all tuples
$(a,b)\in\textnormal{{Good}}_{i}$ are marked “probably good for $i$” and that
for the tuples $(a,b)$ in $\textnormal{{Bad}}_{i}$ that are marked “probably
good for $i$”, we will still obtain good approximations for $|I^{(a,b)}_{i}|$.

The following lemma shows why approximating $|I_{i}^{(a,b)}|$ is enough to
approximate the contributions of the servers in the set $I^{(a,b)}_{i}$.

######  Lemma 4.8.

The value $|I^{(a,b)}_{i}|$ can be used to approximate $\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)$ up to a factor of $\theta^{\prime}$.

###### Proof.

For all servers $j\in I^{(a,b)}_{i}$, by definition, we have

$\displaystyle(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}}\leq\mathbf{e}_{i}^{-1}(f(x_{i}(j)))\leq(\sqrt{\theta})^{a+b+2}P_{\text{start}}F_{\text{start}}$

which further implies using the monotonicity of $f$ that

$\displaystyle
f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})\leq
x_{i}(j)\leq
f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b+2}P_{\text{start}}F_{\text{start}})\leq\theta^{\prime}f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}}).$

Now we note

$\displaystyle\frac{\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)}{\theta^{\prime}}\leq|I^{(a,b)}_{i}|\cdot
f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})\leq\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j).$

We will then show that the expected number of servers in the set
$I^{(a,b)}_{i}$ that sample $i$ can be used to obtain an approximation for
$|I^{(a,b)}_{i}|$.

######  Lemma 4.9.

Let $p_{i}(j)\coloneqq 1-(1-q_{i}(j))^{N}$ denote the probability that the
coordinate $i$ is among the $N$ coordinates sampled at server $j$. For any
tuple $(a,b)$,

$\displaystyle|I^{(a,b)}_{i}|\cdot\frac{(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})}{\sqrt{\theta}}\leq\sum_{j\in
I^{(a,b)}_{i}}p_{i}(j)\leq|I^{(a,b)}_{i}|\cdot(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}).$

###### Proof.

Using monotonicity and concavity of the function $1-(1-x)^{N}$ in the interval
$[0,1]$, for all $j\in I^{(a,b)}_{i}$, we have

$\displaystyle(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})\geq
p_{i}(j)\geq\frac{(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})}{\sqrt{\theta}}.$

Summing the inequalities over all $j\in I^{(a,b)}_{i}$ gives the proof. ∎

If $\sum_{j\in I^{(a,b)}_{i}}p_{j}$ is large enough, we obtain using a
Chernoff bound that the number of servers in $I^{(a,b)}_{i}$ at which $i$ is
sampled is highly concentrated around the mean $\sum_{j\in
I^{(a,b)}_{i}}p_{j}$ and using the above lemmas, we can obtain an estimate for
$|I^{(a,b)}_{i}|$ and therefore estimate $\sum_{j\in I^{(a,b)}_{i}}x_{i}(j)$.
We will follow this approach to approximate $\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)$. Let $\mathbf{X}^{(a,b)}_{i}$ be the number of servers
in $j\in I^{(a,b)}_{i}$ that sample the coordinate $i$. By linearity of
expectation, we have $\operatorname{E\/}[\mathbf{X}^{(a,b)}_{i}]=\sum_{j\in
I^{(a,b)}_{i}}p_{j}$. We will now use the following standard concentration
bounds.

######  Lemma 4.10.

Let $\mathbf{Y}_{j}$ for $j\in[t]$ be a Bernoulli random variable with
$\operatorname{Pr\/}[\mathbf{Y}_{j}=1]=p_{j}$. Let
$\mathbf{Y}_{1},\ldots,\mathbf{Y}_{t}$ be mutually independent and
$\mathbf{X}=\mathbf{Y}_{1}+\cdots+\mathbf{Y}_{t}$. Then the following
inequalities hold:

  1. 1.

If $\sum_{j}p_{j}\geq 100\log n$, then

$\displaystyle\operatorname{Pr\/}[\mathbf{X}=(1\pm
1/3)\sum_{j=1}^{t}p_{j}]\geq 1-1/n^{3}.$

  2. 2.

For any values of $p_{1},\ldots,p_{t}$,

$\displaystyle\operatorname{Pr\/}[\mathbf{X}<2\sum_{j=1}^{t}p_{j}+4\log n]\geq
1-1/n^{4}.$

###### Proof.

To prove the first inequality, we use the multiplicative Chernoff bound. We
have

$\displaystyle\operatorname{Pr\/}[\mathbf{X}=(1\pm
1/3)\sum_{j=1}^{t}p_{j}]\leq
2\exp\left(-\frac{\sum_{j=1}^{t}p_{j}}{27}\right).$

If $\sum_{j=1}^{t}p_{j}\geq 100\log n$, then the RHS is at most $1/n^{3}$. To
prove the second inequality, we use the Bernstein concentration bound. We get

$\displaystyle\operatorname{Pr\/}[\mathbf{X}\geq 2\sum_{j=1}^{t}p_{j}+4\log
n]\leq\exp\left(-\frac{(\sum_{j}p_{j}+4\log
n)^{2}}{\sum_{j}p_{j}+(\sum_{j}p_{j}+4\log n)/3}\right)\leq\exp(-4\log n)\leq
1/n^{4}.$

We note that if $\sum_{j}p_{j}\geq 100\log n$, then with probability $\geq
1-1/n^{3}$, we have $\mathbf{X}=(1\pm 1/3)\log n\geq 66\log n$ and if
$\sum_{j}p_{j}\leq 30\log n$, then with probability $\geq 1-1/n^{4}$, we have
$\mathbf{X}<64\log n$. Thus the value of $\mathbf{X}$ can be used to separate
the cases of $\sum_{j}p_{j}\geq 100\log n$ or $\sum_{j}p_{j}\leq 30\log n$
with high probability.

Now we show that if $(a,b)\in\textnormal{{Good}}_{i}$ and $N$ is large enough,
then $\sum_{j\in I^{(a,b)}_{i}}p_{j}\geq 100\log n$.

######  Lemma 4.11.

If $(a,b)\in\textnormal{{Good}}_{i}$ and the number of samples $N$ at each
coordinator satisfies

$\displaystyle N\geq O\left(\frac{c_{f}[s]}{s}\cdot\frac{c_{f}[A\cdot
B]\cdot(A\cdot
B)\cdot\sqrt{\theta}\cdot\log^{4}n}{\varepsilon_{1}(1-\varepsilon_{2})^{2}}\right),$

then either $(\sqrt{\theta})^{a+1}P_{\text{start}}\geq 4\log n/N$ or
$\sum_{j\in I^{(a,b)}_{i}}p_{j}\geq 100\log n$.

###### Proof.

Assume $(\sqrt{\theta})^{a+1}P_{\text{start}}<4\log n/N$. By concavity of the
function $1-(1-x)^{N}$ in the interval $[0,1]$,

$\displaystyle
1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}\geq\frac{N(\sqrt{\theta})^{a+1}P_{\text{start}}}{4\log
n}(1-1/n^{4}).$

For $(a,b)\in\textnormal{{Good}}_{i}$, we then obtain

$\displaystyle\sum_{j\in I^{(a,b)}_{i}}p_{j}$
$\displaystyle\geq|I^{(a,b)}_{i}|\cdot\frac{N(\sqrt{\theta})^{a+1}P_{\text{start}}}{4\log
n\sqrt{\theta}}(1-1/n^{4})$ $\displaystyle\geq\frac{s}{c_{f}[A\cdot
B]\cdot(A\cdot
B)\cdot(\sqrt{\theta})^{a+1}/(1-\varepsilon_{2})^{2}}\frac{N(\sqrt{\theta})^{a+1}\varepsilon_{1}}{4C\log^{3}n\cdot
c_{f}[s]\cdot\sqrt{\theta}}\cdot(1-1/n^{4})$ $\displaystyle\geq 100\log
n.\qed$

With a high probability, for all coordinates $i$ and all servers $j$ in the
set $I^{(a,b)}_{i}$ for some $a$ with
$(\sqrt{\theta})^{a+1}P_{\text{start}}\geq 4\log n/N$, the coordinate
$i\in\textnormal{{{SC}}}_{j}$. So the contribution from such servers can be
computed exactly akin to the servers in the set $\textnormal{{Large}}_{j}$.

Now consider all the tuples $(a,b)\in\textnormal{{Good}}_{i}$ with
$(\sqrt{\theta})^{a+1}P_{\text{start}}<4\log n/N$. The above lemma shows that
$\sum_{j\in I^{(a,b)}_{i}}p_{j}\geq 100\log n$. Thus, if we mark all the
tuples $(a,b)$ with $\mathbf{X}^{(a,b)}_{i}\geq 66\log n$ as “probably good
for $i$”, then with a probability $\geq 1-1/n^{2}$, all the tuples $(a,b)$ in
$\textnormal{{Good}}_{i}$ are marked as “probably good for $i$” and any tuple
$(a,b)\in\textnormal{{Bad}}_{i}$ marked as “probably good for $i$” satisfies

$\displaystyle\mathbf{X}^{(a,b)}_{i}\leq 2.5\sum_{j\in I^{(a,b)}_{i}}p_{j}.$

We now consider the following algorithm for computing $\hat{x}_{i}$ using
which we then compute $\textnormal{{Est}}_{i}$:

  1. 1.

Let $\mathbf{S}_{i}=\\{j\mid i\in\textnormal{{{SC}}}_{j}\\}$ be the set of all
the servers that sample the coordinate $i$.

  2. 2.

Let $\hat{x}_{i}\leftarrow 0$ denote our initial estimate for $x_{i}$.

  3. 3.

Let
$\mathbf{L}_{i}=\\{j\in\mathbf{S}\mid\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}>\frac{4s}{c_{f}[s]\log^{2}n}\\}$.
This corresponds to the servers in $\textnormal{{Large}}_{i}$ that have
sampled $i$. With high probability, $\mathbf{L}_{i}=\textnormal{{Large}}_{i}$.
Note that we know the value $x_{i}(j)$ for all $j\in\mathbf{L}_{i}$.

  4. 4.

Update $\hat{x}_{i}\leftarrow\hat{x}_{i}+\sum_{j\in\mathbf{L}_{i}}x_{i}(j)$.

  5. 5.

Update $\mathbf{S}_{i}\leftarrow\mathbf{S}_{i}\setminus\mathbf{L}_{i}$.

  6. 6.

Let
$\mathbf{Sm}_{i}=\\{j\in\mathbf{S}_{i}\mid\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}<\frac{\varepsilon_{1}}{c_{f}[s]\cdot(C\log^{2}n)}\\}$.
Corresponds to the servers in $\textnormal{{Small}}_{i}$ that have sampled $i$
and therefore the contribution from these servers can be ignored.

  7. 7.

Update $\mathbf{S}_{i}\leftarrow\mathbf{S}_{i}\setminus\mathbf{Sm}_{i}$.

  8. 8.

For each $a=0,1,\ldots,A-1$ and $b=0,1,\ldots,B-1$, set
$\mathbf{S}^{(a,b)}_{i}\leftarrow\\{j\in\mathbf{S}_{i}\mid j\in
I^{(a,b)}_{i}\\}$. Note that since for all $j\in\mathbf{S}_{i}$, we know the
value of $x_{i}(j)$ and therefore we can compute the set
$\mathbf{S}^{(a,b)}_{i}$.

  9. 9.

For all tuples $(a,b)$ with $(\sqrt{\theta})^{a+1}P_{\text{start}}>4\log n/N$,
with high probability $\mathbf{S}^{(a,b)}_{i}=I^{(a,b)}_{i}$ and we update
$\hat{x}_{i}\leftarrow\hat{x}_{i}+\sum_{j\in\mathbf{S}^{(a,b)}_{i}}x_{i}(j)$.

  10. 10.

For all other tuples $(a,b)$, if $|\mathbf{S}^{(a,b)}_{i}|\geq 66\log n$, we
mark $(a,b)$ as “probably good for $i$” and ignore the rest of the tuples.

  11. 11.

For all tuples $(a,b)$ marked as “probably good for $i$”, we update

$\displaystyle\hat{x}_{i}\leftarrow\hat{x}_{i}+\frac{(2/5)|\mathbf{S}_{i}^{(a,b)}|}{1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}}f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}}).$

  12. 12.

Compute $\textnormal{{Est}}_{i}\coloneqq\mathbf{e}_{i}^{-1}f(\hat{x}_{i})$.

Using all the lemmas we have gone through till now, we will argue that for all
$i\in\textnormal{{{SC}}}$, $\hat{x}_{i}\leq x_{i}$ with a high probability,
which proves that $\textnormal{{Est}}_{i}$ is upper bounded by
$\mathbf{e}_{i}^{-1}f(x_{i})$. We then prove $\textnormal{{Est}}_{i^{*}}$ is
large.

######  Lemma 4.12.

With probability $\geq 1-1/n$, for all $i\in[n]$, $\hat{x}_{i}\leq x_{i}$
which implies $\textnormal{{Est}}_{i}\leq\mathbf{e}_{i}^{-1}f(x_{i})$.

###### Proof.

Consider a fixed $i$. We will argue about contributions from different types
of servers to $\hat{x}_{i}$ separately. By Lemma 4.5, we have
$\mathbf{L}_{i}=\textnormal{{Large}}_{i}$ with probability $\geq 1-1/n^{3}$
and the contribution $\sum_{j\in\textnormal{{Large}}_{i}}x_{i}(j)$ to $x_{i}$
is estimated correctly. We deterministically exclude all the servers in
$\textnormal{{Small}}_{i}$ and therefore we do not overestimate the
contribution of $\sum_{j\in\textnormal{{Small}}_{i}}x_{i}(j)$ to $x_{i}$.

Now consider the tuples $(a,b)$ for $a=0,1,\ldots,A-1$ and $b=0,1,\ldots,B-1$.
If $a$ is such that $(\sqrt{\theta})^{a+1}P_{\text{start}}\geq 4\log n/N$, we
again have $\mathbf{S}^{(a,b)}_{i}=I^{(a,b)}_{i}$ with a large probability
similar to the analysis of Lemma 4.5 and therefore we estimate the
contribution of such servers to $x_{i}$ exactly.

If $(\sqrt{\theta})^{a+1}P_{\text{start}}<4\log n/N$ and
$(a,b)\in\textnormal{{Good}}_{i}$, then Lemma 4.11 shows that $\sum_{j\in
I^{(a,b)}_{i}}p_{j}\geq 100\log n$. We then obtain using Lemma 4.10 that
$66\log n\leq|\mathbf{S}^{(a,b)}_{i}|\leq(4/3)\sum_{j\in I^{(a,b)}_{i}}p_{j}$
with a large probability. Using Lemma 4.9, we get that

$\displaystyle\frac{|\mathbf{S}_{i}^{(a,b)}|}{(4/3)(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})}\leq|I^{(a,b)}_{i}|.$

Using Lemma 4.8, we then obtain that

$\displaystyle\frac{|\mathbf{S}_{i}^{(a,b)}|}{(4/3)(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})}f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})$
$\displaystyle\leq|I^{(a,b)}_{i}|f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})\leq\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j).$

Hence, the contribution of tuples $(a,b)\in\textnormal{{Good}}_{i}$ is not
overestimated. If $(a,b)\in\textnormal{{Bad}}_{i}$ and $(a,b)$ is marked
“probably good for $i$”, then using Lemma 4.10, we get

$\displaystyle|\mathbf{S}_{i}^{(a,b)}|\leq\frac{5}{2}\sum_{j\in
I^{(a,b)}_{i}}p_{j}$

and using the same series of steps as above, we get

$\displaystyle\frac{|\mathbf{S}_{i}^{(a,b)}|}{(5/2)(1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N})}f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})$
$\displaystyle\leq|I^{(a,b)}_{i}|f^{-1}(\mathbf{e}_{i}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})\leq\sum_{j\in
I^{(a,b)}_{i}}x_{i}(j)$

which again shows that the contribution of tuples $(a,b)$ in
$\textnormal{{Bad}}_{i}$ but are marked “probably good for $i$” is also not
overestimated. Overall we get that with a probability $\geq 1-O(1/n^{2})$,
$\hat{x}_{i}\leq x_{i}$. Using a union bound we have the proof. ∎

We now show that $\textnormal{{Est}}_{i^{*}}$ is large with a large
probability.

######  Lemma 4.13.

With probability $\geq 1-1/n^{2}$,

$\displaystyle\textnormal{{Est}}_{i^{*}}\geq\frac{(1-\varepsilon_{2})^{2}}{\theta^{\prime\prime}}\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}}).$

###### Proof.

By Lemma 4.5, $\mathbf{L}_{i^{*}}=\textnormal{{Large}}_{i^{*}}$ and therefore
the contribution to $x_{i^{*}}$ from the servers in
$\textnormal{{Large}}_{i^{*}}$ is captured by $\hat{x}_{i^{*}}$. We argued
that contribution to $\hat{x}_{i^{*}}$ from servers in
$\textnormal{{Small}}_{i^{*}}\cup\textnormal{{Ignore}}_{i^{*}}$ can be
ignored.

Now consider the tuples $(a,b)$ for $a=0,1,\ldots,A-1$ and $b=0,1,\ldots,B-1$.
If $(\sqrt{\theta})^{a+1}P_{\text{start}}\geq(4\log n)/N$, then
$\mathbf{S}^{(a,b)}_{i^{*}}=I^{(a,b)}_{i^{*}}$ with probability $\geq
1-1/n^{3}$ and therefore the contribution from the servers in
$I^{(a,b)}_{i^{*}}$ is captured exactly by $\hat{x}_{i^{*}}$. If
$(a,b)\in\textnormal{{Bad}}_{i^{*}}$, then we argued in Lemma 4.7 that we need
not capture the contribution from those servers. So any contribution from
servers in $\textnormal{{Bad}}_{i^{*}}$ marked as “probably good for $i^{*}$”
will only help in increasing $\hat{x}_{i^{*}}$.

Now consider $(a,b)\in\textnormal{{Good}}_{i^{*}}$ with
$(\sqrt{\theta})^{a+1}P_{\text{start}}<4\log n/N$. By Lemma 4.11, with a large
probability

$\displaystyle|\mathbf{S}_{i^{*}}^{(a,b)}|\geq\frac{2}{3}\sum_{j\in
I^{(a,b)}_{i^{*}}}p_{j}.$

By Lemma 4.9, we get

$\displaystyle|\mathbf{S}_{i^{*}}^{(a,b)}|\geq\frac{2}{3}|I^{(a,b)}_{i^{*}}|\frac{1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}}{\sqrt{\theta}}.$

Now, using Lemma 4.8, we get

$\displaystyle|\mathbf{S}_{i^{*}}^{(a,b)}|\cdot
f^{-1}(\mathbf{e}_{i^{*}}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})\geq\frac{2}{3\cdot\theta^{\prime}}\cdot\frac{1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}}{\sqrt{\theta}}\sum_{j\in
I^{(a,b)}_{i^{*}}}x_{i^{*}}(j)$

which then implies

$\displaystyle\frac{(2/5)|\mathbf{S}_{i^{*}}^{(a,b)}|\cdot
f^{-1}(\mathbf{e}_{i^{*}}(\sqrt{\theta})^{a+b}P_{\text{start}}F_{\text{start}})}{1-(1-(\sqrt{\theta})^{a+1}P_{\text{start}})^{N}}\geq\frac{4}{15\cdot\theta\cdot\sqrt{\theta}}\sum_{j\in
I^{(a,b)}_{i^{*}}}x_{i^{*}}(j).$

Thus, overall, with high probability, we have

$\displaystyle\hat{x}_{i^{*}}$
$\displaystyle\geq\sum_{j\in\textnormal{{Large}}_{i^{*}}}x_{i^{*}}(j)+\frac{4}{15\cdot\theta\cdot\sqrt{\theta}}\sum_{(a,b)\in\textnormal{{Good}}_{i^{*}}}\sum_{j\in
I^{(a,b)}_{i^{*}}}x_{i^{*}}(j).$

We therefore have

$\displaystyle\textnormal{{Est}}_{i^{*}}\coloneqq\mathbf{e}_{i^{*}}^{-1}f(\hat{x}_{i^{*}})\geq\frac{(1-\varepsilon_{2})^{3}}{\theta^{\prime\prime}}\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$

assuming for all $x$, $f(x/(4\cdot\theta\cdot\sqrt{\theta}))\geq
f(x)/\theta^{\prime\prime}$. ∎

######  Theorem 4.14.

Assume we are given a super-additive nonnegative function $f$ that satisfies
the “approximate invertibility” property with parameters
$\theta,\theta^{\prime},\theta^{\prime\prime},\varepsilon_{1}$ and
$\varepsilon_{2}$. Let $s\geq 1$ be the number of servers. Define
$A=O(\log(s/\varepsilon_{1})/\log\theta)$ and
$B=O(\log(s^{2}/\varepsilon_{1}(1-\varepsilon_{2}))/\log\theta)$. Let
$\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ be independent standard exponential
random variables shared across all the servers. Then there is a 2-round
protocol in the coordinator model which uses a total communication of

$\displaystyle O\left({c_{f}[s]\cdot\frac{c_{f}[A\cdot B]\cdot(A\cdot
B)\cdot\sqrt{\theta}\log^{4}n}{\varepsilon_{1}(1-\varepsilon_{2})^{2}}}+s\cdot\frac{\log^{2}n\cdot\theta^{\prime\prime}}{(1-\varepsilon_{2})^{3}}\right)$

words of communication and with probability $\geq 1-1/\operatorname{poly}(n)$
computes $\max_{i}\mathbf{e}_{i}^{-1}f(x_{i})$.

###### Proof.

First we condition on the event that
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i})\leq(C\log^{2}n)\cdot\max_{i}\mathbf{e}_{i}^{-1}f(x_{i})$
which holds with probability $\geq 1-1/\operatorname{poly}(n)$. Note that the
randomness used in sampling is independent of the exponential random
variables. Define
$i^{*}\coloneqq\operatorname*{arg\,max}_{i}\mathbf{e}_{i}^{-1}f(x_{i})$.

Let $N=O((c_{f}[s]/s)\cdot c_{f}[A\cdot B]\cdot(A\cdot
B)\cdot\sqrt{\theta}\log^{4}n/(\varepsilon_{1}(1-\varepsilon_{2})^{2}))$. Let
each server $j$ sample $N$ coordinates independently from its local
distribution:

$\displaystyle\operatorname{Pr\/}[\mathbf{i}=i]=\frac{\mathbf{e}_{i}^{-1}f(x_{i}(j))}{\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))}.$

Let $\textnormal{{{SC}}}_{j}$ be the set of coordinates sampled by the server
$j$. Now, each server $j$ sends the set $\textnormal{{{SC}}}_{j}$ along with
the values $x_{i}(j)$ for $i\in\textnormal{{{SC}}}_{j}$ to the coordinator.
Additionally, each server also sends the value
$\sum_{i}\mathbf{e}_{i}^{-1}f(x_{i}(j))$ to the coordinator. Note that this
requires a total communication of $O(N\cdot s)$ words of communication.

Now, the coordinator computes
$\textnormal{{{SC}}}=\bigcup_{j}\textnormal{{{SC}}}_{j}$. By Lemma 4.3, we
have $i^{*}\in\textnormal{{{SC}}}$ with probability $\geq
1-1/\operatorname{poly}(n)$. Now the coordinator computes $\hat{x}_{i}$ and a
value $\textnormal{{Est}}_{i}$ for each $i\in\textnormal{{{SC}}}$ using the
algorithm described above. Lemma 4.12 shows that with a probability $\geq
1-1/\operatorname{poly}(n)$, for all $i\in\textnormal{{{SC}}}$, we have
$\textnormal{{Est}}_{i}\leq\mathbf{e}_{i}^{-1}f(x_{i})$ and Lemma 4.13 shows
that with probability $\geq 1-1/\operatorname{poly}(n)$, we have
$\textnormal{{Est}}_{i^{*}}\geq\frac{(1-\varepsilon_{2})^{3}}{\theta^{\prime\prime}}\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$.
Using a union bound, all these events hold with probability $\geq
1-1/\operatorname{poly}(n)$. Condition on all these events.

Let PL be the set of coordinates $i\in\textnormal{{{SC}}}$ with the
$O(C\log^{2}n\cdot\theta^{\prime\prime}/(1-\varepsilon_{2})^{3})$ largest
values of $\textnormal{{Est}}_{i}$. We have $i^{*}\in\textnormal{{{PL}}}$
since we conditioned on all the above events. Now the coordinator queries
sends the set PL to _each_ server $j$ and asks for the values $x_{i}(j)$ for
$i\in\textnormal{{{PL}}}$. Then the servers all send the requested information
in the second round of communication. Note that the total communication
required is $O(s\cdot|\textnormal{{{PL}}}|)$ words. Since $i^{*}$ in PL, we
obtain that

$\displaystyle\max_{i\in\textnormal{{{PL}}}}\mathbf{e}_{i}^{-1}f(\sum_{j\in[s]}x_{i}(j))=\mathbf{e}_{i^{*}}^{-1}f(x_{i^{*}})$

and the coordinator can compute this value after receiving the required
information from the servers in the second round of communication. This proves
the theorem. ∎

We can run the protocol in the above theorem concurrently using
$O(1/\varepsilon^{2})$ independent copies of the exponential random variables
and then obtain a $1\pm\varepsilon$ approximation for $\sum_{i}f(x_{i})$ with
a probability $\geq 99/100$. We note that the overall protocol requires two
rounds and a total communication of
$O_{\theta,\theta^{\prime},\theta^{\prime\prime}}\left(\frac{c_{f}[s]}{\varepsilon^{2}}\operatorname{polylog}(n)\right)$
words of communication.

######  Theorem 4.15.

Let $f$ be a non-negative, increasing, super-additive function that satisfies
the “approximate invertibility” properties with the parameters
$\theta,\theta^{\prime},\theta^{\prime\prime}$. Let there be $s$ servers and
each of the servers holds a non-negative vector
$x(1),\ldots,x(s)\in\mathbb{R}^{n}$ respectively. Define
$A=O(\log(s\cdot\theta^{\prime\prime})/\log\theta)$ and
$B=O(\log(s^{2}\cdot(\theta^{\prime\prime})^{2})/\log\theta)$. Given
$\varepsilon<1/n^{c}$ for a small constant $c$, there is a two round protocol
that uses a total of

$\displaystyle O\left(\frac{c_{f}[s]}{\varepsilon^{2}}\cdot{c_{f}[A\cdot
B]\cdot(A\cdot
B)\cdot\sqrt{\theta}\cdot(\theta^{\prime\prime})^{3}\cdot\log^{4}n}+\frac{s}{\varepsilon^{2}}\cdot{\log^{2}n\cdot(\theta^{\prime\prime})^{4}}\right)$

words of communication and with probability $\geq 9/10$ computes a
$1\pm\varepsilon$ for the quantity $\sum_{i}f(x_{i})$.

###### Proof.

For $k\in[O(1/\varepsilon^{2})]$ and $i\in[n]$, let $\mathbf{e}^{(k)}_{i}$ be
an independent standard exponential random variable. Let
$i^{*}(k)\coloneqq\operatorname*{arg\,max}_{i\in[n]}(\mathbf{e}_{i}^{(k)})^{-1}f(x_{i})$.
By a union bound, the following hold simultaneously with probability $\geq
1-1/\operatorname{poly}(n)$:

$\displaystyle\text{for all }k,\
\sum_{i}(\mathbf{e}_{i}^{(k)})^{-1}f(x_{i})\leq(C\log^{2}n)\cdot(\mathbf{e}_{i^{*}{(k)}}^{(k)})^{-1}f(x_{i^{*}{(k)}})$

and

$\displaystyle\ln(2)\cdot\text{median}_{k}\,(\mathbf{e}_{i^{*}(k)}^{(k)})^{-1}f(x_{i^{*}(k)})=(1\pm\varepsilon)\sum_{i\in[n]}f(x_{i}).$

We condition on these events. Now concurrently for each $k$, we use the
exponential random variables
$\mathbf{e}^{(k)}_{1},\ldots,\mathbf{e}^{(k)}_{n}$ and run the protocol in
Theorem 4.14 to obtain the value of
$(\mathbf{e}_{i^{*}(k)}^{(k)})^{-1}f(x_{i^{*}(k)})$ with probability $\geq
1-1/\operatorname{poly}(n)$. We union bound over the success of the protocol
for all $k$ and obtain that with probability $\geq 9/10$, we can compute the
exact value of

$\displaystyle\ln(2)\cdot\text{median}_{k}\,(\mathbf{e}_{i^{*}(k)}^{(k)})^{-1}f(x_{i^{*}(k)})$

which then gives us a $1\pm\varepsilon$ approximation of
$\sum_{i\in[n]}f(x_{i})$. The communication bounds directly follow from
Theorem 4.14. ∎

We obtain the following corollary for estimating $F_{k}$ moments.

######  Corollary 4.16.

Let $k>2$ be arbitrary. In the coordinator model with $s$ servers that each
hold a non-negative vector $x(j)\in\mathbb{R}^{n}$, there is a randomized two
round protocol that uses a total of
$\tilde{O}_{k}(s^{k-1}\operatorname{polylog}(n)/\varepsilon^{2})$ bits of
communication and approximate $\sum_{i}(\sum_{j\in[s]}x_{i}(j))^{k}$ up to a
$1\pm\varepsilon$ factor with probability $\geq 9/10$.

###### Proof.

For the function $f(x)=x^{k}$, we have $c_{f}[s]=s^{k-1}$ by a simple
application of the Holder’s inequality. We additionally note that $x^{k}$ is
“approximately invertible” with parameters $\theta=2$,
$\theta^{\prime}=2^{1/k}$, and $\theta^{\prime\prime}=2\cdot 8^{k/2}$.
Therefore $\varepsilon_{1}$ and $1-\varepsilon_{2}$ can be taken as $1/(2\cdot
8^{k/2})$. We now have $A,B=O(k+\log s)$ so that $c_{f}[A\cdot B]\cdot(A\cdot
B)=(k+\log s)^{k}$. From the above theorem, we therefore obtain that there is
a two round protocol that computes a $1\pm\varepsilon$ approximation of
$\sum_{i\in[n]}(\sum_{j\in[s]}x_{i}(j))^{k}$ with probability $\geq 9/10$ and
uses a total communication of

$\displaystyle O\left(\frac{s^{k-1}}{\varepsilon^{2}}\frac{(k+\log
s)^{k}}{8^{3k/2}}\operatorname{polylog}(n)\right)$

words of communication. ∎

###  4.3 Higher-Order Correlations

Kannan, Vempala, and Woodruff [29] also study the problem of approximating
higher order correlations and list a few applications of the problem in their
paper. In this problem, there are $s$ servers and the $j$-th server holds a
set of $n$-dimensional vectors $W_{j}$. Given a parameter $k$, and functions
$f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$, $g:\mathbb{R}_{\geq
0}^{k}\rightarrow\mathbb{R}_{\geq 0}$, the coordinator wants to approximate

$\displaystyle
M(f,g,W_{1},\ldots,W_{s})\coloneqq\sum_{i_{1},i_{2},\ldots,i_{k}\,\text{distinct}}f\left(\sum_{j}\sum_{v\in
W_{j}}g(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k}})\right)$

As they mention, for each server $j$, we can create a vector $w(j)$ with
$r=\binom{n}{k}k!$ components (one for each tuple $(i_{1},\ldots,i_{k})$ with
distinct values of $i_{1},i_{2},\ldots,i_{k}\in[n]$) defined as

$\displaystyle[w(j)]_{(i_{1},i_{2},\ldots,i_{k})}\coloneqq\sum_{v\in
W_{j}}g(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{k}}).$

Now running the function sum approximation protocol on the vectors
$w(1),\ldots,w(s)$ with the function $f$, we can compute a $1\pm\varepsilon$
approximation for $M(f,g)$ using a total of

$\displaystyle
O_{\theta,\theta^{\prime},\theta^{\prime\prime}}\left(\frac{c_{f}[s]}{\varepsilon^{2}}\cdot\operatorname{polylog}(r)\right)=O_{\theta,\theta^{\prime},\theta^{\prime\prime}}\left(\frac{c_{f}[s]}{\varepsilon^{2}}\cdot\operatorname{poly}(k,\log
n)\right)$

words of communication. The main issue in implementing this algorithm is that
all the servers have to realize the $r=\binom{n}{k}k!$ dimensional vectors
$w(j)$ which end up occupying $O(n^{k})$ space which is prohibitive when $n$
is large. Using a simple trick, we can show that to execute the protocol in
Theorem 4.15 can be implemented without using $O(n^{k})$ space.

We first solve for the issue of sharing $O(n^{k})$ exponential random
variables across all the servers. In Appendix C, we show that the exponential
random variables used in the protocol need not be independent but can be
generated using Nisan’s Pseudorandom Generator (PRG) [34]. The seed for
Nisan’s PRG needs to be only of length $O(k^{2}\log^{2}(n/\varepsilon))$ and
hence the shared randomness across the servers is only of this size.

The main reason we need the vectors $w(j)$ is so that the server $j$ can
sample independent copies of the random variable
$(\mathbf{i}_{1},\ldots,\mathbf{i}_{k})$ with probability distribution

$\displaystyle\operatorname{Pr\/}[(\mathbf{i}_{1},\ldots,\mathbf{i}_{k})=(i_{1},\ldots,i_{k})]=\frac{(\mathbf{e}_{(i_{1},\ldots,i_{k})})^{-1}[w(j)]_{(i_{1},\ldots,i_{k})}}{\sum_{i_{1}^{\prime},\ldots,i_{k}^{\prime}}(\mathbf{e}_{(i_{1}^{\prime},\ldots,i_{k}^{\prime})})^{-1}[w(j)]_{(i_{1}^{\prime},\ldots,i_{k}^{\prime})}}$

where $\mathbf{e}_{(i_{1},\ldots,i_{k})}$ is an independent standard
exponential random variable. But we note that to sample from this
distribution, the protocol does not need $O(n^{k})$ space. Consider the
lexicographic ordering of the tuples $(i_{1},\ldots,i_{k})$ with all
$i_{1},\ldots,i_{k}$ distinct. The algorithm goes over the tuples in the
lexicographic orders, computes the value of
$(\mathbf{e}_{(i_{1},\ldots,i_{k})})^{-1}[w(j)]_{(i_{1},\ldots,i_{k})}$ by
generating the random variable $\mathbf{e}_{(i_{1},\ldots,i_{k})}$ using
Nisan’s PRG and then uses a _reservoir sampling_ algorithm to sample a tuple
form the above defined distribution. This entire process can be accomplished
using a constant amount of space and hence implementing the function sum
approximation protocol on the vectors $w(1),\ldots,w(s)$ can be accomplished
without using $\Theta(n^{k})$ space at each of the servers. Hence we have the
following theorem:

######  Theorem 4.17.

Let there be $s$ servers each holding an arbitrary set of $n$-dimensional non-
negative vectors $W_{1},\ldots,W_{s}\subseteq$ respectively. Given a function
$f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ that satisfies the
“approximate invertibility” property with parameters
$\theta,\theta^{\prime},\theta^{\prime\prime}>1$ and a function
$g:\mathbb{R}^{k}_{\geq 0}\rightarrow\mathbb{R}^{k}_{\geq 0}$, there is a
randomized two round protocol that approximates $M(f,g,W_{1},\ldots,W_{s})$ up
to a $1\pm\varepsilon$ factor with probability $\geq 9/10$. The protocol uses
a total of

$\displaystyle O\left(\frac{c_{f}[s]}{\varepsilon^{2}}\cdot{c_{f}[A\cdot
B]\cdot(A\cdot B)\cdot\sqrt{\theta}\cdot(\theta^{\prime\prime})^{3}\cdot
k^{4}\log^{4}n}+\frac{s}{\varepsilon^{2}}\cdot{k^{2}\log^{2}n\cdot(\theta^{\prime\prime})^{4}}\right)$

words of communication, where
$A=O(\log(s\cdot\theta^{\prime\prime})/\log\theta)$ and
$B=O(\log(s^{2}\cdot(\theta^{\prime\prime})^{2})/\log\theta)$

##  5 Lower Bounds