in $\operatorname{poly}(sd\log(R/(r\varepsilon))$ time in
$O\left(\sum_{i=1}^{s}d_{i}^{2}\log(dR/r\varepsilon)\cdot L\right)$ bits of
communication where $L=O(\log(dR/r)$.

We explain our main algorithm (LABEL:alg:min-sum-convex-blackboard) to obtain
our guarantee of Theorem 5.1 for solving Section 5.1. Our algorithm’s inputs
are the functions $f_{i}$ (and their corresponding first-order oracles). All
parameters of this algorithm are set in the proof of Theorem 5.1. Before
explaining LABEL:alg:min-sum-convex-blackboard, we briefly review the
algorithm of [DJLPY22] and then describe the algorithm obtained by directly
adopting this in the blackboard model.

##### Overview of [DJLPY22].

This algorithm updates the variable $\mathbf{x}$ via updates inspired by
interior-point methods, following a central path parametrized by a parameter
$t$, with a barrier function over the set $\mathcal{K}$. Therefore, the ideal
iterates would follow the points

$\arg\min_{\mathbf{x}\in\mathbb{R}^{d}:\mathbf{A}\mathbf{x}=\mathbf{b}}\left\\{t\mathbf{c}^{\top}\mathbf{x}+\sum_{i=1}^{s}\phi_{i}(\mathbf{x}_{\textrm{i}})\right\\},$

with $t$ being updated, per the classical theory of interior point methods,
based on the complexity parameter of the self-concordance barrier
$\sum_{i=1}^{s}\phi_{i}$ defined over $\mathcal{K}$. However, the algorithm
does _not_ have an explicit closed-form expression for $\mathcal{K}$.
Therefore, as a proxy to $\mathcal{K}$, it maintains inner and outer set
approximations $\mathcal{K}_{\textrm{in}}$ and $\mathcal{K}_{\textrm{out}}$
respectively, satisfying
$\mathcal{K}_{\textrm{in,}i}\subseteq\mathcal{K}_{i}\subseteq\mathcal{K}_{\mathrm{out,}i}$
for each $i\in[s]$, and performs IPM-style updates with a barrier on
$\mathcal{K}_{\textrm{out}}$. Thus, this algorithm essentially alternates
between making progress on $\mathbf{x}$ or $t$ (per the IPM framework) and
updating the set approximation for $\mathcal{K}$ (using ideas from classical
cutting-plane methods).

##### Blackboard adaptation of [DJLPY22].

In the blackboard model adaptation of the above algorithm, each server would
run a copy of the above algorithm. The only step where communication happens
is in Step 3a: Before updating $\mathbf{x}$ to the currently set target point
$\mathbf{x}_{\textrm{out}}^{\star}$, each server checks for feasibility of
$\mathbf{x}_{\textrm{out}}^{\star}$; if there is potential infeasibility of
the $i^{\mathrm{th}}$ block $\mathbf{x}_{\textrm{out,}i}^{\star}$ (Step 2),
then server holding the oracle $\mathcal{O}_{i}$ sends the output of querying
$\mathcal{O}_{i}$ on $\mathbf{x}_{\textrm{out,}i}^{\star}$ to the blackboard,
while all other servers read this (for free, as allowed by the model).

The above framework, developed in [DJLPY22], would yield a communication
complexity of $\widetilde{O}(d_{\max}\cdot\sum_{i=1}^{s}d_{i}L)$ where
$d_{\max}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{i=1}^{s}d_{i}$, which
comes from scaling the oracle query complexity of [DJLPY22] by the worst-case
cost of communication (i.e., sending the hyperplane with the maximum $d_{i}$).
This $d_{\max}$ factor arises under the assumption that each subgradient
oracle has the same cost. However, this assumption does not align with our
communication complexity setting, where we charge for each subgradient oracle
call by the length of the vector it outputs.

##### Our modification.

To capture the above nuance, we consider a weighted version of oracle
complexity, which we denote by _oracle cost_. Given some arbitrary but fixed
weight vector $\mathbf{w}\in\mathbb{R}^{s}_{\geq 1}$, the oracle _cost_ is
$\sum_{i=1}^{s}w_{i}\cdot n_{i}$ where $n_{i}$ is the number of times the
$i$-th subgradient oracle queried.

Thus, one of our technical contributions is a more fine-grained analysis of
this technique by using a _weighted_ potential. (In terms of the algorithm,
the only change that happens is the rate of update to $t$, which we do at
$O\left(\tfrac{\eta}{\sum_{i=1}^{s}w_{i}d_{i}}\right)$ (as opposed to the
previous rate of $O\left(\tfrac{\eta}{\sum_{i=1}^{s}d_{i}}\right)$).) As a
result of this change in potential function, we can now conclude that the
total _cost_ of communication is $\sum_{i}w_{i}d_{i}L$, where we can choose
what $w_{i}$ are. This is in contrast with the previous result, which was
about the total _oracle_ complexity. As a result of this change, we now choose
$w_{i}=d_{i}$, which gives us the improved communication cost of
$\sum_{i=1}^{s}d_{i}^{2}L$. This is an improvement over the previous rate when
the largest $d_{i}$ is much larger than the rest. In the following subsection,
we go into more detail into the individual steps of LABEL:alg:min-sum-convex-
blackboard, which would help in understanding the analysis.

####  5.1.1 Details of Our Algorithm

Given the current outer approximating set $\mathcal{K}_{\textrm{out}}$, the
current central path parameter $t$, and some self-concordant barrier
$\varphi_{\mathrm{out,i}}$ defined on each set $\mathcal{K}_{\mathrm{out,}i}$,
we define the total barrier and the analytic center of
$\mathcal{K}_{\textrm{out}}\cap\\{\mathbf{A}\mathbf{x}=\mathbf{b}\\}$ with
respect to this barrier as

$\varphi_{\mathrm{out}}(\mathbf{x})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i=1}^{s}w_{i}\varphi_{\mathrm{out,i}}(\mathbf{x}_{i}),\text{
and
}\mathbf{x}_{\textrm{out}}^{\star}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\left\\{t\cdot\mathbf{c}^{\top}\mathbf{x}+\sum_{i=1}^{s}w_{i}\varphi_{\mathrm{out,i}}(\mathbf{x}_{i})\right\\}.$
(5.3)

As mentioned earlier, not knowing $\mathcal{K}$ explicitly forces us to
choose, as the constraint set, between its proxies $\mathcal{K}_{\textrm{in}}$
and $\mathcal{K}_{\textrm{out}}$; we choose $\mathcal{K}_{\textrm{out}}$ to
ensure that we do not miss a potential solution.

Having computed the current target $\mathbf{x}_{\textrm{out}}^{\star}$, we
move the current candidate $\mathbf{x}$ towards it via a Newton step, provided
certain conditions of feasibility and minimum progress are satisfied. If
either condition is violated, we first update either
$\mathcal{K}_{\textrm{in}}$, $\mathcal{K}_{\textrm{out}}$, or the parameter
$t$, then recompute $\mathbf{x}_{\textrm{out}}^{\star}$ and repeat the checks
until they are satisfied. In our Newton step update (Step 5), we normalize by
by the radius of the appropriate Dikin ellipsoid, which ensures the
feasibility of the updated $\mathbf{x}$ since, by self-concordance, the unit
radius Dikin ball lies inside the domain of the self-concordance barrier.

The conditions we check before moving our candidate $\mathbf{x}$ towards
$\mathbf{x}_{\textrm{out}}^{\star}$ are that
$\mathbf{x}_{\textrm{out}}^{\star}\in\mathcal{K}_{\textrm{in}}$ (Step 2) and
the central path parameter $t$ is large enough (Step 1). Recall that $t$
determines the suboptimality gap at the current candidate $\mathbf{x}$: so, if
$\mathbf{c}^{\top}(\mathbf{x}-\mathbf{x}_{\textrm{out}}^{\star})\leq
O(\frac{1}{t}{\sum_{i=1}^{s}w_{i}\nu_{i}})$, then we need to first update our
next goal along the central path by updating $t$. If we have already reached
an approximate optimum, which we verify by checking whether $t\geq
O(1/\varepsilon)$ in Step 1a, then the algorithm terminates by returning

$\mathbf{x}^{\mathrm{ret}}=\arg\min_{\mathbf{x}:\mathbf{A}\mathbf{x}=\mathbf{b}}\left\\{t\cdot\mathbf{c}^{\top}{\mathbf{x}}+\sum_{i=1}^{s}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})\right\\}.$

The point $\mathbf{x}^{\mathrm{ret}}$ is feasible because it is in
$\mathcal{K}_{\textrm{in}}$ by definition, and
$O(1/t_{\textrm{end}})=O(\varepsilon)$ ensures that it is an approximate
optimum for the original problem. Otherwise, following classical interior-
point method theory, we increase $t$ by a scaling factor of
$1+O(1/\sum_{i=1}^{s}w_{i}d_{i})$ in Step 1b to set the next “target
suboptimality”. We then recompute $\mathbf{x}_{\textrm{out}}^{\star}$ by
Equation 5.3. Since
$\mathbf{c}^{\top}\mathbf{x}>{\mathbf{c}}^{\top}{\mathbf{x}_{\textrm{out}}^{\star}}+O(1/t)$
is not guaranteed with the new $t$ and $\mathbf{x}_{\textrm{out}}^{\star}$,
the algorithm jumps back to the start of the main loop.

To check if $\mathbf{x}_{\textrm{out}}^{\star}\in\mathcal{K}_{\textrm{in}}$,
we check if
$\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\rangle+\eta\cdot\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}\leq
O(\nu_{i})$ for all $i\in[s]$ and for some constant $\eta>0$. Any point in the
domain of a self-concordant barrier satisfies the inequalities in Theorem A.12
and Theorem A.13, hence violating this condition implies that
$\mathbf{x}_{\textrm{out,}i}^{\star}$ is far from
$\mathcal{K}_{\textrm{in,}i}$, and as a result,
$\mathbf{x}_{\textrm{out}}^{\star}$ is potentially not (yet) a good candidate
to move $\mathbf{x}$ towards.

Therefore, to rectify the situation of
$\mathbf{x}_{\textrm{out}}^{\star}\notin\mathcal{K}_{\textrm{in}}$, we must
update either $\mathcal{K}_{\textrm{in,}i}$ or $\mathcal{K}_{\mathrm{out,}i}$
and compute a new $\mathbf{x}_{\textrm{out}}^{\star}$. To decide which option
to take, we query $\mathcal{O}_{i}$ at $\mathbf{x}_{\textrm{out,}i}^{\star}$:
if the oracle indicates that
$\mathbf{x}_{\textrm{out,}i}^{\star}\in\mathcal{K}_{i}$, then we incorporate
$\mathbf{x}_{\textrm{out,}i}^{\star}$ into $\mathcal{K}_{\textrm{in,}i}$ by
redefining
$\mathcal{K}_{\textrm{in,}i}=\textrm{conv}\left\\{\mathcal{K}_{\textrm{in,}i},\mathbf{x}_{\textrm{out,}i}^{\star}\right\\}$
to be the convex hull of the current $\mathcal{K}_{\textrm{in,}i}$ and
$\mathbf{x}_{\textrm{out,}i}^{\star}$ (Step 3(a)i). If, on the other hand,
$\mathbf{x}_{\textrm{out,}i}^{\star}\notin\mathcal{K}_{i}$, we choose to
update the outer set $\mathcal{K}_{\mathrm{out,}i}$. Then we redefine
$\mathcal{K}_{\mathrm{out,}i}=\mathcal{K}_{\mathrm{out,}i}\cap\mathcal{H}_{i}$
(Step 3(a)ii). In either case, the only communication that takes place is when
the server that queries the oracle sends the output of the oracle to the
blackboard for all other servers to read (and update their data). After
processing this update of the sets, the algorithm recomputes
$\mathbf{x}_{\textrm{out}}^{\star}$ and returns to the main loop since
updating the sets does not necessarily imply that the new
$\mathbf{x}_{\textrm{out}}^{\star}$ satisfies
$\mathbf{x}_{\textrm{out}}^{\star}\in\mathcal{K}_{\textrm{in}}$. Updating a
set only after checking the very specific condition
$\mathbf{x}_{\textrm{out,}i}^{\star}\notin\mathcal{K}_{\textrm{in,}i}$
dramatically reduces the number of calls to the separation oracle (since this
is the only part of the algorithm it is invoked) as compared to arbitrarily
checking all sets. Over the course of the algorithm, we gradually expand
$\mathcal{K}_{\textrm{in}}$ and shrink $\mathcal{K}_{\textrm{out}}$, until
they well approximate $\mathcal{K}$, and the algorithm’s final output is
approximately optimal.

Input.  A total of $s$ servers and a blackboard, with the $i^{\mathrm{th}}$
server storing indices $D_{i}\subseteq[d]$ where $d_{i}=|D_{i}|$ and a convex
function $f_{i}:\mathbb{R}^{d_{i}}\to\mathbb{R}$. Each server $i$ has access
to the subgradient oracle of $f_{i}$. An initial vector
$\theta^{(0)}\in\mathbb{R}^{d}$ and $R\in\mathbb{R}$ such that
$\|\theta^{(0)}-\theta^{\star}\|_{2}\leq R$.

Output.  A vector $\theta\in\mathbb{R}^{d}$ on all machines such that
$\sum_{i=1}^{s}f_{i}(\mathbf{\theta})\leq\sum_{i=1}^{s}f_{i}(\theta^{\star})+\varepsilon\cdot\mu
R.$

Initialize. Set initial parameters $m=\sum_{i=1}^{s}w_{i}d_{i}$,
$t=\frac{m\log m}{\sqrt{n}\|\mathbf{c}\|_{2}R}$,
$t_{\textrm{end}}=\frac{8m}{\varepsilon\|\mathbf{c}\|_{2}R}$, and
$\eta=\frac{1}{100}$. Reformulate the problem into Section 5.1 using Lemma
5.12. Find the initial $\mathcal{K}_{\textrm{in}}$ using Theorem 5.13. Modify
the program according to Lemma 5.14 and obtain initial feasible $\mathbf{x}$
with $\alpha=2^{16}\frac{m^{2.5}R}{r\varepsilon}$. Compute
$\mathbf{x}_{\textrm{out}}^{\star}$ (via Equation 5.3)

while true do

  1. 1

All servers check if
$\mathbf{c}^{\top}\mathbf{x}\leq\mathbf{c}^{\top}\mathbf{x}_{\textrm{out}}^{\star}+\frac{4m}{t}$,
and if true

    1. (a)

All servers check $t\geq t_{\textrm{end}}$; if true, they compute and return
$\arg\min_{\mathbf{x}:\mathbf{x}\in\mathcal{K}_{\textrm{in}},\mathbf{A}\mathbf{x}=\mathbf{b}}\left\\{t\cdot\mathbf{c}^{\top}\mathbf{x}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})\right\\}$

    2. (b)

All servers update $t$ to $t\cdot\left(1+\frac{\eta}{4m}\right)$

    3. (c)

All servers update $\mathbf{x}_{\textrm{out}}^{\star}$ (Equation 5.3) and
jumps to the start of the while loop

  2. 2

All servers find the smallest index $\mathsf{idx}$ such that
$\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\rangle+\eta\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}\geq
4\nu_{i}$

  3. 3

For all $i\in[s]$ do

    1. (a)

Each server $i$ checks if $i=\mathsf{idx}$; if so then query $\mathcal{O}_{i}$
at $\mathbf{x}_{\textrm{out,}i}^{\star}$ and send
$\mathcal{O}_{i}(\mathbf{x}_{\textrm{out,}i}^{\star})$ to the blackboard,
otherwise read the result of
$\mathcal{O}_{i}(\mathbf{x}_{\textrm{out,}i}^{\star})$ from blackboard.

      1. i.

If $\mathbf{x}_{\textrm{out,}i}^{\star}\in\mathcal{K}_{i}$ then set
$\mathcal{K}_{\textrm{in,}i}=\textrm{conv}\left\\{\mathcal{K}_{\textrm{in,}i},\mathbf{x}_{\textrm{out,}i}^{\star}\right\\}$

      2. ii.

Otherwise, set
$\mathcal{K}_{\mathrm{out,}i}=\mathcal{K}_{\mathrm{out,}i}\cap\mathcal{H}_{i}$

      3. iii.

Update $\mathbf{x}_{\textrm{out}}^{\star}$ and jump to the start of the while
loop

  4. 4

Set
$\delta_{\mathbf{x}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{\eta}{2}\cdot\frac{\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}},$where
$\|\mathbf{u}\|_{\mathbf{x},1}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i=1}^{s}\|\mathbf{u}\|_{\mathbf{x}_{\textrm{i}}}$

  5. 5

Set $\mathbf{x}\leftarrow\mathbf{x}+\delta_{\mathbf{x}}$

Return: Recover $\theta$ from $\mathbf{x}$ according to Lemmas 5.12 and 5.14.

Algorithm 12: Minimizing sum of convex functions in the blackboard model.

alg]alg:min-sum-convex-blackboard

###  5.2 An Overview of Our Analysis

We note that in LABEL:alg:min-sum-convex-blackboard, after initialization,
machines send a message to the blackboard only if the separation oracle is
queried; each such message encodes a halfspace in $\mathbb{R}^{d_{i}}$, which
can be encoded using $O(d_{i}\cdot L)$ bits. Therefore, the communication
complexity of LABEL:alg:min-sum-convex-blackboard can be bounded as
$\sum_{i=1}^{s}n_{i}d_{i}L$, where $n_{i}$ is the number of separation oracle
calls on $\mathcal{K}_{i}$.

In this section, we show that for given any weight vector
$\mathbf{w}\in\mathbb{R}_{\geq 1}^{s}$, the total cost of all separation
oracle queries is at most

$\sum_{i=1}^{s}w_{i}n_{i}\leq\sum_{i=1}^{s}w_{i}d_{i}\log(sdR/(\varepsilon
r)).$

Although we will simply use $w_{i}=d_{i}$ in this paper, we believe that the
use of other weights could be useful in other applications.

To analyze the oracle cost of LABEL:alg:min-sum-convex-blackboard, we define a
potential function that captures the changes in $\mathcal{K}_{\textrm{in,}i}$,
$\mathcal{K}_{\mathrm{out,}i}$, $t$, and $\mathbf{x}$ in each iteration. We
define
$\varphi_{\mathrm{out}}(\mathbf{x})=\sum_{i=1}^{s}w_{i}\varphi_{\mathrm{out,i}}(\mathbf{x}_{i})$
and use $\widehat{\varphi}_{\text{out}}$ to denote $\varphi_{\mathrm{out}}$
restricted to the set $\\{\mathbf{u}:\mathbf{A}\mathbf{u}=\mathbf{b}\\}$. We
further use $f^{*}$ to denote the Fenchel conjugate of the function $f$. Then
we define our potential as

$\Phi\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\underbrace{t\cdot\mathbf{c}^{\top}{\mathbf{x}}+\widehat{\varphi}_{\text{out}}^{*}(-t\mathbf{c})}_{\text{outer
potential
terms}}+\underbrace{\sum_{i\in[s]}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})}_{\text{inner
potential terms}},$ (5.4)

where
$\widehat{\varphi}_{\text{out}}^{*}(-t\mathbf{c})=\max_{\mathbf{A}\mathbf{u}=\mathbf{b}}-t\mathbf{c}^{\top}\mathbf{u}-\varphi_{\mathrm{out}}(\mathbf{u})=-\left(\min_{\mathbf{A}\mathbf{u}=\mathbf{b}}t\mathbf{c}^{\top}\mathbf{u}+\varphi_{\mathrm{out}}(\mathbf{u})\right).$
Following the choice of the barrier functions in [DJLPY22], we use the
universal barrier [LY21] for $\psi_{\textrm{in,}i}$ and the entropic
barrier[BE15, Che23]888 While [DJLPY22] uses a simple entropic barrier for the
entire $\mathcal{K}_{\textrm{out}}$, we are using a weighted sum of entropic
barriers on all $\mathcal{K}_{\mathrm{out,}i}$’s. for $\psi_{\textrm{out,}i}$.
In the subsequent sections, we study the changes in each of these potential
functions along with obtaining bounds on the initial and final potentials and
combine them to bound the algorithm’s separation oracle complexity.

####  5.2.1 Potential Change Upon Shrinking an Outer Set

Ideally, we want to show that the potential decreases uniformly after each
separation oracle query to $\mathcal{K}_{i}$. Formally, we want to use a self-
concordant barrier function satisfying the condition below, which we
conjecture holds for all self-concordant functions. In this paper, we prove
that the entropic barrier satisfies it (and use this fact in our analysis).

######  Conjecture 5.2.

Let $\phi$ be a self-concordant barrier. Denote $\phi_{\mathcal{S}}$ to be
$\phi$ restricted to the set $\mathcal{S}$. Given a bounded convex body
$\mathcal{K}$ and cost vector $\mathbf{c}$, define
$\mathbf{x}^{\star}=\arg\min\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})$,
and let hyperplane $\mathcal{H}$ contain a point $\mathbf{z}$ such that
$\|\mathbf{x}^{\star}-\mathbf{z}\|_{(\nabla^{2}\phi_{\mathcal{K}}(\mathbf{x}^{\star}))^{-1}}<0.01$.
Then

$\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}\cap\mathcal{H}}(\mathbf{x})\right\\}\geq\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})\right\\}+0.1.$

The analysis in [Vai89] suggests that the volumetric barrier might satisfy the
condition above. In this paper, we instead use a weighted version of the
entropic barrier on $\mathcal{K}_{\textrm{out}}$, which is easier to analyze
and implement. Before we prove that the entropic barrier satisfies the
conditions above, we first show how 5.2 implies the desired potential
decrease.

######  Lemma 5.3.

Consider the Cartesian product
$\mathcal{K}=\mathcal{K}_{1}\times\ldots\times\mathcal{K}_{s}$, where each
$\mathcal{K}_{i}$ is a bounded convex set associated with a self-concordant
barrier function $\varphi_{i}$ satisfying the inequality in 5.2. Given a
weight vector $\mathbf{w}_{\geq 1}\in\mathbb{R}^{n}$, and the cost vector
$\mathbf{c}$, we define the weighted barrier
$\varphi(\mathbf{x})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i=1}^{s}w_{i}\varphi_{i}(\mathbf{x}_{i})$
and the corresponding analytic center
$\mu\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{x}}\mathbf{c}^{\top}\mathbf{x}+\varphi(\mathbf{x})$.
Fix $i$, let
$\mathcal{K}_{i}^{\text{new}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{K}_{i}\cap\mathcal{H}$,
where $\mathcal{H}$ contains a point $\mathbf{z}$ such that
$\|\mathbf{z}-\mu_{i}\|_{(\nabla^{2}w_{i}\varphi_{i}(\mu_{i}))^{-1}}\leq
0.01$. We define $\mathcal{K}^{\text{new}}$ and $\varphi^{\text{new}}$
correspondingly. Then, for any $\mathbf{A}$ and $\mathbf{b}$, we have

$\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})\geq\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi(\mathbf{x})+0.1w_{i}$

###### Proof.

Let
$\mathbf{x}^{\star}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi(\mathbf{x})$.
Using the appropiate Lagrange multiplier $\mathbf{z}$, we can find
$\widehat{\mathbf{c}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathbf{c}+\mathbf{A}^{\top}\mathbf{z}$
such that

$\mathbf{x}^{\star}=\arg\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi(\mathbf{x}).$

These definitions of $\mathbf{x}^{\star}$ and $\widehat{\mathbf{c}}$ imply the
following connection:

$\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi(\mathbf{x})=\widehat{\mathbf{c}}^{\top}\mathbf{x}^{\star}+\varphi(\mathbf{x}^{\star})=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi(\mathbf{x}).$
(5.5)

Then, by the definition of $\varphi^{\text{new}}$, we have:

$\displaystyle\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})$
$\displaystyle=\min_{\mathbf{x}}\left\\{\widehat{\mathbf{c}}^{\top}\mathbf{x}+\sum_{j\neq
i}w_{j}\varphi_{j}(\mathbf{x}_{j})+w_{i}\varphi_{i}^{\text{new}}(\mathbf{x}_{i})\right\\}$
$\displaystyle\geq\min_{\mathbf{x}}\left\\{\widehat{\mathbf{c}}^{\top}\mathbf{x}+\sum_{j\neq
i}w_{j}\varphi_{j}(\mathbf{x}_{j})+w_{i}(\varphi_{i}(\mathbf{x}_{i})+0.1)\right\\}$
$\displaystyle=0.1w_{i}+\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi(\mathbf{x})$
$\displaystyle=0.1w+\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi(\mathbf{x})+\mathbf{z}^{\top}\mathbf{A}\mathbf{x}^{\star},$
(5.6)

where the second is by 5.2 applied to $\varphi_{i}$, the third step follows by
definition of $\varphi$, and the last step follows by Equation 5.5. Since our
desired bound is on
$\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})$,
we now define the minimizer

$\displaystyle\mathbf{x}^{\star,\mathrm{new}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x}).$
(5.7)

We may now observe the following upper bound on
$\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})$:

$\displaystyle\min_{\mathbf{x}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})$
$\displaystyle\leq\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\widehat{\mathbf{c}}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})$
$\displaystyle\leq\widehat{\mathbf{c}}^{\top}\mathbf{x}^{\star,\mathrm{new}}+\varphi^{\text{new}}(\mathbf{x}^{\star,\mathrm{new}})$
$\displaystyle=\mathbf{c}^{\top}\mathbf{x}^{\star,\mathrm{new}}+\varphi^{\text{new}}(\mathbf{x}^{\star,\mathrm{new}})+\mathbf{z}^{\top}\mathbf{A}\mathbf{x}^{\star,\mathrm{new}}$
$\displaystyle=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})+\mathbf{z}^{\top}\mathbf{A}\mathbf{x}^{\star,\mathrm{new}},$
(5.8)

where the first step is by restricting the set of minimization, the second
step uses the fact that
$\mathbf{x}^{\star,\mathrm{new}}\in\\{\mathbf{x}:\mathbf{A}\mathbf{x}=\mathbf{b}\\}$,
the third step uses the definition of $\widehat{\mathbf{c}}$, and the final
step is by plugging in the definition of $\mathbf{x}^{\star,\mathrm{new}}$
from Equation 5.7. Chaining Equation 5.6 and Equation 5.8 gives

$\displaystyle\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varphi^{\text{new}}(\mathbf{x})-\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}$
$\displaystyle\geq
0.1w_{i}+\mathbf{z}^{\top}\mathbf{A}(\mathbf{x}^{\star}-\mathbf{x}^{\star,\mathrm{new}})=0.1w_{i},$
(5.9)

where the second step is because the definitions of
$\mathbf{x}^{\star,\mathrm{new}}$ and $\mathbf{x}^{\star}$ imply that both
satisfy $\mathbf{A}\mathbf{x}=\mathbf{b}.$ ∎

Now, we show that the entropic barrier satisfies the condition in 5.2.

######  Lemma 5.4.

Given a bounded convex body $\mathcal{K}$ and a vector $\mathbf{c}$, let
$\phi$ be the entropic barrier and
$\mathbf{x}^{\star}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})$.
Let the halfspace $\mathcal{H}$ contain a point $\mathbf{z}$ such that
$\|\mathbf{z}-\mathbf{x}^{\star}\|_{(\nabla^{2}\phi(\mathbf{x}^{\star})^{-1}}\leq
t$, then

$\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}\cap\mathcal{H}}(\mathbf{x})\right\\}\geq\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})\right\\}-\log(1-1/e+t).$

###### Proof.

Let $\phi_{\mathcal{K}}$ be the entropic barrier, we note that the Fenchel
conjugate of $\phi_{\mathcal{K}}$, $\phi_{\mathcal{K}}^{*}(-\mathbf{c})$ is

$\phi_{\mathcal{K}}^{*}(-\mathbf{c})=-1\cdot\min_{\mathbf{x}}({\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})}).$

Recall that $\phi^{*}(\cdot)$ is the logarithmic Laplace transform of the
uniform measure on $\mathcal{K}$ [BE15], we have

$\phi_{\mathcal{K}}^{*}(-\mathbf{c})=\log\int_{\mathcal{K}}\exp(-\langle\mathbf{c},\mathbf{u}\rangle)d\mathbf{u}.$

Consider the distribution over $\mathbb{R}^{n}$, with following density
measure:

$p(\mathbf{x})=\exp(-\langle\mathbf{c},\mathbf{x}\rangle-\phi_{\mathcal{K}}^{*}(-\mathbf{c}))\cdot\mathbb{I}\\{\mathbf{x}\in\mathcal{K}\\}.$

Using Lemma A.24, we have $\mathbf{x}^{\star}=\mathbb{E}_{\mathbf{x}\sim
p}[\mathbf{x}]$, is the centroid of $p$. It is an established fact that (see
e.g.[BE15, Lemma 1])

$\mathbb{E}_{x\sim
p}[(\mathbf{x}-\mathbf{x}^{\star})(\mathbf{x}-\mathbf{x}^{\star})^{\top}]=\nabla^{2}\phi^{*}_{\mathcal{K}}(-\mathbf{c})=(\nabla^{2}\phi_{\mathcal{K}}(\mathbf{x}^{\star}))^{-1}.$

Then, by Grünbaum’s Theorem (Theorem A.22), we have we have

$\int_{\mathcal{K}\cap\mathcal{H}}p(\mathbf{x})d\mathbf{x}\geq 1/e-t,$

which implies that

$\int_{\mathcal{K}\cap\mathcal{H}}p(\mathbf{x})d\mathbf{x}=\frac{\int_{\mathcal{K}\cap\mathcal{H}}\exp(-\langle\mathbf{c},\mathbf{x})\rangle
d\mathbf{x}}{\phi_{\mathcal{K}}^{*}(-\mathbf{c})}\leq 1-1/e+t.$

Taking the logarithm of both sides, we get

$\phi^{*}_{\mathcal{K}\cap\mathcal{H}}(-\mathbf{c})-\phi^{*}_{\mathcal{K}}(-\mathbf{c})\leq\log(1-1/e+t).$

This finishes the claim:

$\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}\cap\mathcal{H}}(\mathbf{x})\right\\}-\min_{\mathbf{x}}\left\\{\mathbf{c}^{\top}\mathbf{x}+\phi_{\mathcal{K}}(\mathbf{x})\right\\}=-\phi^{*}_{\mathcal{K}\cap\mathcal{H}}(-\mathbf{c})+\phi^{*}_{\mathcal{K}}(-\mathbf{c})\geq-\log(1-1/e+t).$

∎

####  5.2.2 Potential Change Upon Increasing $t$

To capture the change in potential due to the update in $t$, we require a
technical result derived from properties of conjugates of self-concordant
barriers. To obtain this result, we use a helper result from [DJLPY22], and
based on this lemma, we prove a more general one in Lemma 5.6.

######  Lemma 5.5 (Lemma $4.2$ of [DJLPY22]).

Consider a $\nu$-self-concordant barrier
$\psi:\textrm{int}(\mathcal{K})\rightarrow\mathbb{R}$ over the interior of a
convex set $\mathcal{K}\subseteq\mathbb{R}^{d}$. Define

$\xi_{t\mathbf{c}}^{\psi}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\min_{\mathbf{x}}\left[t\cdot\langle\mathbf{c},\mathbf{x}\rangle+\psi(\mathbf{x})\right]\text{
and
}\mathbf{x}_{t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{x}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x}).$
(5.10)

Then for $0\leq h\leq\frac{1}{3\sqrt{\nu}}$, we have

$\min_{\mathbf{x}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+th\cdot\mathbf{c}^{\top}\mathbf{x}_{t}\geq\min_{\mathbf{x}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})\geq\min_{\mathbf{x}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+ht\cdot\mathbf{c}^{\top}{\mathbf{x}_{t}}-h^{2}\nu.$

######  Lemma 5.6.

Consider a $\nu$-self-concordant barrier
$\psi:\textrm{int}(\mathcal{K})\rightarrow\mathbb{R}$ over the interior of a
convex set $\mathcal{K}\subseteq\mathbb{R}^{d}$. Define

$\widehat{\mathbf{x}}_{t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x}).$
(5.11)

Then for $0\leq h\leq\frac{1}{3\sqrt{\nu}}$, we have

$\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+th\cdot{\mathbf{c}}^{\top}\widehat{\mathbf{x}}_{t}\geq\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})\geq\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+ht\cdot{\mathbf{c}}^{\top}{\widehat{\mathbf{x}}_{t}}-h^{2}\nu.$

###### Proof.

The first inequality holds for any function $\psi$ with the specified
definition of $\widehat{\mathbf{x}}_{t}$ and $\xi_{t(1+h)\mathbf{c}}^{\psi}$:

$\displaystyle\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})$
$\displaystyle\leq
t(1+h)\cdot\mathbf{c}^{\top}\text{$\widehat{\mathbf{x}}_{t}$}+\psi(\text{$\widehat{\mathbf{x}}_{t}$})=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+th\cdot\mathbf{c}^{\top}\widehat{\mathbf{x}}_{t},$

where the first inequality is by plugging in $\widehat{\mathbf{x}}_{t}$ into
$\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})$ and the second step by using the
definition of $\widehat{\mathbf{x}}_{t}$ from Equation 5.11. To prove the
second inequality, we use the self-concordance of $\psi$. First, using the
appropriate Lagrange multiplier $\mathbf{z}$, one can define
$\widehat{\mathbf{c}}:=\mathbf{c}+\mathbf{A}^{\top}\mathbf{z}$ to express
$\widehat{\mathbf{x}}_{t}$ as the minimizer of an unconstrained problem as
follows:

$\widehat{\mathbf{x}}_{t}=\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})=\arg\min_{\mathbf{x}}\xi_{t\text{$\widehat{\mathbf{c}}$}}^{\psi}(\mathbf{x}),\text{
for }\widehat{\mathbf{c}}:=\mathbf{c}+\mathbf{A}^{\top}\mathbf{z}.$ (5.12)

As a result, we may now apply Lemma 5.5, which gives

$\displaystyle\min_{\mathbf{x}}\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}(\mathbf{x})$
$\displaystyle\geq\min_{\mathbf{x}}\xi_{t\widehat{\mathbf{c}}}^{\psi}(\mathbf{x})+ht\cdot\widehat{\mathbf{c}}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu$
$\displaystyle=\xi_{t\widehat{\mathbf{c}}}^{\psi}(\text{$\widehat{\mathbf{x}}_{t}$})+ht\cdot\widehat{\mathbf{c}}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu$
$\displaystyle=\xi_{t\text{$\mathbf{c}$}}^{\psi}(\widehat{\mathbf{x}}_{t})+ht\cdot\text{$\mathbf{c}$}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu+\text{$(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}\widehat{\mathbf{x}}_{t}$},$
$\displaystyle=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+ht\cdot\mathbf{c}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu+(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}\widehat{\mathbf{x}}_{t},$
(5.13)

where the first and second steps are by Lemma 5.5 applied to
$\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}$ and the definition of
$\widehat{\mathbf{x}}_{t}$ from Equation 5.12, the third step is by using the
definition of $\widehat{\mathbf{c}}:=\mathbf{c}+\mathbf{A}^{\top}\mathbf{z}$,
and the final step is by applying the definition of $\widehat{\mathbf{x}}_{t}$
from Equation 5.11. We now define

${\mathbf{x}}_{t(1+h)}^{\mathrm{new}}=\arg\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x}).$

In the other direction, we have

$\displaystyle\min_{\mathbf{x}}\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}(\mathbf{x})$
$\displaystyle\leq\min_{\text{$\mathbf{A}\mathbf{x}=\mathbf{b}$}}\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}(\mathbf{x})$
$\displaystyle\leq\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}(\text{${\mathbf{x}}_{t(1+h)}^{\mathrm{new}}$})$
$\displaystyle=\xi_{t(1+h)\text{$\mathbf{c}$}}^{\psi}({\mathbf{x}}_{t(1+h)}^{\mathrm{new}})+(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}{\mathbf{x}}_{t(1+h)}^{\mathrm{new}},$
$\displaystyle=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})+(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}{\mathbf{x}}_{t(1+h)}^{\mathrm{new}},$
(5.15)

where the first step is by constraining the minimization set, the second step
is because, by definition of ${\mathbf{x}}_{t(1+h)}^{\mathrm{new}}$ from
Section 5.2.2, it satisfies $\mathbf{A}\mathbf{x}=\mathbf{b}$, the third step
is by replacing
$\widehat{\mathbf{c}}:=\mathbf{c}+\mathbf{A}^{\top}\mathbf{z}$, and the fourth
step is by definition of ${\mathbf{x}}_{t(1+h)}^{\mathrm{new}}$ in Section
5.2.2. Therefore, we have

$\displaystyle\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\psi}(\mathbf{x})$
$\displaystyle\geq\min_{\mathbf{x}}\xi_{t(1+h)\widehat{\mathbf{c}}}^{\psi}(\mathbf{x})-(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}{\mathbf{x}}_{t(1+h)}^{\mathrm{new}}$
$\displaystyle\geq\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+ht\cdot\mathbf{c}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu+(1+h)t\cdot\mathbf{z}^{\top}\mathbf{A}(\widehat{\mathbf{x}}_{t}-{\mathbf{x}}_{t(1+h)}^{\mathrm{new}}),$
$\displaystyle=\min_{\mathbf{A}\mathbf{x}=\mathbf{b}}\xi_{t\mathbf{c}}^{\psi}(\mathbf{x})+ht\cdot\mathbf{c}^{\top}\widehat{\mathbf{x}}_{t}-h^{2}\nu,$

where the first step is by rearranging Equation 5.15, the second step is by
Equation 5.13, and the final step is by the fact that both
$\widehat{\mathbf{x}}_{t}$ and ${\mathbf{x}}_{t(1+h)}^{\mathrm{new}}$ satisfy
$\mathbf{A}\mathbf{x}=\mathbf{b}$. This finishes the proof. ∎

To finally compute the potential change due to $t,$ we combine the result from
Lemma 5.6 with the bound guaranteed by Step 1 of LABEL:alg:min-sum-convex-
blackboard along with the self-concordance parameter of the volumetric
barrier. We may now compute the potential change due to change in $t$ in Step
1b.

######  Lemma 5.7.

When $t$ is updated to
$t\cdot\left[1+\frac{\eta}{4\sum_{i=1}^{s}w_{i}\nu_{i}}\right]$ in Step 1b of
LABEL:alg:min-sum-convex-blackboard, the potential $\Phi$ Equation 5.4
increases to $\Phi^{\textrm{(new)}}$ as follows:

$\Phi^{\textrm{(new)}}\leq\Phi+\eta+\eta^{2}.$

###### Proof.

From Equation 5.4, the change in potential by changing $t$ to $t\cdot(1+h)$
for some $h>0$ may be expressed as

$\Phi^{\textrm{(new)}}-\Phi=-\underbrace{\left(\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}\xi_{t(1+h)\mathbf{c}}^{\varphi_{\mathrm{out}}}(\mathbf{y})-\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}\xi_{t\mathbf{c}}^{\varphi_{\mathrm{out}}}(\mathbf{y})\right)}_{\text{Bounded
via
\lx@cref{creftype~refnum}{lem:EtChangeConstrained}}}+th\cdot\mathbf{c}^{\top}{\mathbf{x}}.$

We may now apply Lemma 5.6 in the preceding equation to obtain the following
bound.

$\Phi^{\textrm{(new)}}-\Phi\leq
th\cdot\mathbf{c}^{\top}{\mathbf{x}}-th\cdot\mathbf{c}^{\top}{\widehat{\mathbf{x}}_{t}}+h^{2}\nu.$

We see that $\widehat{\mathbf{x}}_{t}$ as defined in Equation 5.11 for
$\psi=\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}$ from LABEL:{eq:xoutstar-min}
is exactly identical to $\mathbf{x}_{\textrm{out}}^{\star}$ from Equation 5.3.
We can therefore apply the guarantee
$\mathbf{c}^{\top}\mathbf{x}\leq\mathbf{c}^{\top}{\mathbf{x}_{\textrm{out}}^{\star}}+\frac{4\sum_{i=1}^{s}w_{i}\nu_{i}}{t}$
(from Step 1 of LABEL:alg:min-sum-convex-blackboard) and
$h=\frac{\eta}{4\sum_{i=1}^{s}w_{i}\nu_{i}}$ and
$\nu=\sum_{i=1}^{s}w_{i}\nu_{i}$ to obtain

$\displaystyle\Phi^{\textrm{(new)}}-\Phi$ $\displaystyle\leq
th\cdot\frac{4\sum_{i=1}^{s}w_{i}\nu_{i}}{t}+h^{2}\nu=\eta+\left(\frac{\eta}{4\sum_{i=1}^{s}w_{i}\nu_{i}}\right)^{2}\nu\leq\eta+\eta^{2}.$

∎

####  5.2.3 Potential Change Upon Growing an Inner Set

Here, we state the technical lemma that describes the change in the universal
barrier potential when we add a point to the convex set.

######  Lemma 5.8 ([DJLPY22, Lemma 4.6]).

Given a convex set $\mathcal{K}\subseteq\mathbb{R}^{d}$ and a point
$\mathbf{x}\in\mathcal{K}$, let
$\psi_{\mathcal{K}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\log\mathrm{vol}(\mathcal{K}-\mathbf{x})^{\circ}$
be the universal barrier defined on $\mathcal{K}$ with respect to
$\mathbf{x}.$ Let $\mathbf{y}\notin\mathcal{K}$ be a point satisfying the
following condition for some scalar $\eta\leq 1/4$

$\langle\nabla\psi_{\mathcal{K}}(\mathbf{x}),\mathbf{y}-\mathbf{x}\rangle+\eta\|\mathbf{y}-\mathbf{x}\|_{\mathbf{x}}\geq
4d.$ (5.16)

Then, the universal barrier (cf. Definition A.21) defined on the set
$\mathrm{conv}\left\\{\mathcal{K},\mathbf{y}\right\\}$ with respect to
$\mathbf{x}$ satisfies the following inequality:

$\psi_{\mathcal{K},\textrm{new}}(\mathbf{x})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\psi_{\mathrm{conv}\left\\{\mathcal{K},\mathbf{y}\right\\}}(\mathbf{x})=\log\mathrm{vol}(\mathrm{conv}\left\\{\mathcal{K},\mathbf{y}\right\\}-\mathbf{x})^{\circ}\leq\psi_{\mathcal{K}}(\mathbf{x})+\log(1-1/e+\eta).$

####  5.2.4 Potential Change For the Update of $\mathbf{x}$

In this section, we quantify the amount of progress made in Step 4 of
LABEL:alg:min-sum-convex-blackboard by computing the change in the potential
$\Phi$ as defined in Equation 5.4.

######  Lemma 5.9.

Consider the potential $\Phi$ Equation 5.4. Denote by $\Phi^{\textrm{(new)}}$
the value of this potential after $\mathbf{x}$ takes the update step
$\delta_{\mathbf{x}}=\frac{\eta}{2}\cdot\frac{\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}$
as in Step 4. Assume the following guarantees

  * •

$\mathbf{c}^{\top}\mathbf{x}_{\textrm{out}}^{\star}+\frac{4\sum_{i=1}^{s}w_{i}\nu_{i}}{t}\leq\mathbf{c}^{\top}\mathbf{x}$.

  * •

$\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\rangle+\eta\cdot\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}\leq
4\nu_{i}$ for all $i\in[s]$.

Then the potential $\Phi$ incurs the following minimum decrease.

$\Phi^{\textrm{(new)}}\leq\Phi-\frac{\eta^{2}}{4}\sum_{i=1}^{s}w_{i}\frac{\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\leq\Phi-\frac{\eta^{2}}{4}.$

###### Proof.

The proof is similar to that of Lemma 4.7 in [DJLPY22], we include it here for
completeness. Taking the gradient of $\Phi$ with respect to $\mathbf{x}$ and
rearranging the terms gives

$t\mathbf{c}=\nabla_{\mathbf{x}}\Phi-\sum_{i=1}^{s}w_{i}\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),$
(5.17)

where we are overloading notation in
$\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})$ to mean the
$d$-dimensional vector equalling the appropriate entries at the $d_{i}$
coordinates corresponding to $\mathbf{x}_{\textrm{i}}$ and zero elsewhere. By
replacing $t\mathbf{c}$ with the expression on the right-hand side of the
preceding equation, we get

$\displaystyle\Phi^{\textrm{(new)}}-\Phi$
$\displaystyle=t\langle\mathbf{c},\mathbf{x}+\delta_{\mathbf{x}}\rangle+\sum_{i=1}^{s}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}+\delta_{\mathbf{x},i})-t\langle\mathbf{c},\mathbf{x}\rangle-\sum_{i=1}^{s}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})$
$\displaystyle=\langle\nabla_{\mathbf{x}}\Phi,\delta_{\mathbf{x}}\rangle+\sum_{i=1}^{s}w_{i}\underbrace{\left[\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}+\delta_{\mathbf{x},i})-\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})-\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\delta_{\mathbf{x},i}\rangle\right]}_{q_{\psi_{\textrm{in,}i}}(\mathbf{x}_{\textrm{i}})}.$
(5.18)

Note that in substituting Equation 5.17 above, we crucially use that
$\mathbf{x}_{\textrm{i}}$ are all disjoint vectors whose coordinates
completely cover those of $\mathbf{x}$. The term
$q_{\psi_{\textrm{in,}i}}(\mathbf{x}_{\textrm{i}})$ measures the error due to
first-order approximation of $\psi_{\textrm{in,}i}$ around
$\mathbf{x}_{\textrm{i}}$. Since each
$\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})$ is a self-concordant function
and
$\|\delta_{\mathbf{x},i}\|_{\mathbf{x}_{i}}\leq\|\delta_{\mathbf{x}}\|_{\mathbf{x},1}\leq\eta\leq
1/4$, this error is known to be small; more precisely, Theorem A.20 applies
and gives

$\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}+\delta_{\mathbf{x},i})-\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})-\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\delta_{\mathbf{x},i}\rangle\leq\|\delta_{\mathbf{x},i}\|_{\mathbf{x}_{\textrm{i}}}^{2}.$
(5.19)

Plugging in Equation 5.19 into Equation 5.18, we get

$\Phi^{\textrm{(new)}}-\Phi\leq\langle\nabla_{\mathbf{x}}\Phi,\delta_{\mathbf{x}}\rangle+\sum_{i=1}^{s}w_{i}\|\delta_{\mathbf{x},i}\|_{\mathbf{x}_{\textrm{i}}}^{2}.$
(5.20)

We now bound the two terms on the right hand side one at a time. Using the
definition of $\delta_{\mathbf{x}}$ (as given in the statement of the lemma)
and of $\nabla_{\mathbf{x}}\Phi$ from Equation 5.17 gives

$\displaystyle\langle\nabla_{\mathbf{x}}\Phi,\delta_{\mathbf{x}}\rangle$
$\displaystyle=\frac{\eta}{2}\frac{1}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\langle\nabla_{\mathbf{x}}\Phi,\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\rangle$
$\displaystyle=\frac{\eta}{2}\frac{1}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\left[\langle
t\mathbf{c},\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\rangle+\sum_{i=1}^{s}w_{i}\langle\nabla\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}}),\mathbf{x}_{\textrm{out},i}^{\star}-\mathbf{x}_{\textrm{i}}\rangle\right]$
$\displaystyle\leq\frac{\eta}{2}\frac{1}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\left[\langle
t\mathbf{c},\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\rangle+\sum_{i=1}^{s}w_{i}\left(4\nu_{i}-\eta\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{i}}\right)\right]$
$\displaystyle=\frac{\eta}{2}\frac{1}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\left[\langle
t\mathbf{c},\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\rangle+4\sum_{i=1}^{s}w_{i}\nu_{i}-\eta\sum_{i=1}^{s}w_{i}\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{i}}\right]$
$\displaystyle\leq\frac{\eta}{2}\frac{1}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}\cdot\left(-\eta\sum_{i=1}^{s}w_{i}\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{i}}\right)=-\frac{\eta^{2}}{2}\sum_{i=1}^{s}w_{i}\frac{\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}}.$
(5.21)

where the third step follows from the second assumption, and the fifth step
follows from the first assumption. To bound the second term Step 4 that

$\sum_{i=1}^{s}w_{i}\|\delta_{\mathbf{x},i}\|_{\mathbf{x}_{\textrm{i}}}^{2}=\frac{\eta^{2}}{4}\cdot\sum_{i=1}^{s}w_{i}\frac{\|\mathbf{x}_{\textrm{out,}i}^{\star}-\mathbf{x}_{\textrm{i}}\|_{\mathbf{x}_{\textrm{i}}}^{2}}{\|\mathbf{x}_{\textrm{out}}^{\star}-\mathbf{x}\|_{\mathbf{x},1}^{2}}.$
(5.22)

Hence, we may plug in Equation 5.21 and Equation 5.22 into Equation 5.20 to
get the desired result. ∎

####  5.2.5 Total Oracle Cost

Before we bound the communication complexity of the algorithm, we first bound
the total potential change throughout the algorithm.

######  Lemma 5.10.

Consider the potential function

$\Phi(t,\mathbf{x},\mathcal{K}_{\textrm{out}},\mathcal{K}_{\textrm{in}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}t\cdot\mathbf{c}^{\top}\mathbf{x}-\left(\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}t\cdot\mathbf{c}^{\top}\mathbf{y}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i})\right)+\sum_{i=1}^{s}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{i})$

as defined in Equation 5.4 associated with LABEL:alg:min-sum-convex-
blackboard. Let $\Phi_{\textrm{init}}$ be the potential at
$t=t_{\textrm{init}}$ of this algorithm, and let $\Phi_{\textrm{end}}$ be the
potential at $t=t_{\textrm{end}}$. Suppose at $t=t_{\textrm{init}}$ in
LABEL:alg:min-sum-convex-blackboard, we have, for some
$\mathbf{z}\in\mathcal{K}_{\textrm{in}}$, that
$\mathcal{B}_{m}(\mathbf{z},\bar{r})\subseteq\mathcal{K}_{\textrm{in}}$ with
$\bar{r}=r/\operatorname{poly}(m)$ and
$\mathcal{K}_{\textrm{out}}\subseteq\mathcal{B}_{m}(0,\bar{R})$ for
$\bar{R}=O(\sqrt{n}R)$. Then we have, under the assumptions of Theorem 5.1,
that

$\Phi_{\textrm{init}}-\Phi_{\textrm{end}}\leq
O\left(\sum_{i=1}^{s}w_{i}d_{i}\log\left(\frac{mR}{\varepsilon
r}\right)\right).$

###### Proof.

We bound the change in the potential term by term, starting with the following
terms depending on the current iterate $\mathbf{x}$, the current time step
$t$, and the current outer set $\mathcal{K}_{\textrm{out}}$:

$\Psi(t,\mathbf{x},\mathcal{K}_{\textrm{out}})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}t\cdot\mathbf{c}^{\top}\mathbf{x}-\left(\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}t\cdot\mathbf{c}^{\top}\mathbf{y}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i})\right).$
(5.23)

We introduce the notation
$\Psi_{\textrm{init}}:=\Psi(t_{\textrm{init}},\mathbf{x}(t_{\textrm{init}}),\mathcal{K}_{\textrm{out}}(t_{\textrm{init}}))$
and simplify it as follows.

$\displaystyle\Psi_{\textrm{init}}$
$\displaystyle=t_{\textrm{init}}\cdot\mathbf{c}^{\top}\mathbf{x}-\left(\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}t_{\textrm{init}}\cdot\mathbf{c}^{\top}\mathbf{y}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i})\right)$
$\displaystyle\leq
t_{\textrm{init}}\cdot(\mathbf{c}^{\top}\mathbf{x}-\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{y})-\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i})$
$\displaystyle\leq
o(m)-\min_{\mathbf{y}}\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i}),$
(5.24)

where the second inequality follows from our choice of $t_{\textrm{init}}$
implying $t\cdot\mathbf{c}^{\top}\mathbf{x}=o(m)$ for any
$\mathbf{x}\in\mathcal{K}_{\textrm{out}}$ and also because expanding the set
of minimization only decreases the minimum value; note that because of
$\psi_{\textrm{out,}i}$, the variable $\mathbf{y}$ is implicitly already
restricted to $\mathcal{K}_{\textrm{out}}$. We emphasize that
$\psi_{\textrm{out,}i}$ here is the barrier function on the
$\mathcal{K}_{\textrm{out}}$ at $t=t_{\textrm{init}}$. Let
$\mathbf{y}^{\star}_{i}$ be the analytic center of $\psi_{\textrm{out,}i}$:

$\mathbf{y}^{\star}_{i}=\arg\min_{\mathbf{y}}\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i}).$

Hence, we may rewrite $\Psi_{\textrm{init}}$ using Section 5.2.5 to obtain

$\Psi_{\textrm{init}}\leq
o(m)-\sum_{i=1}^{s}w_{i}\psi_{\textrm{out}}(\mathbf{y}_{i}^{\star}).$

To bound $\Psi_{\textrm{end}}$, we define:

$\mathbf{y}_{t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\arg\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}(t\cdot\mathbf{c}^{\top}\mathbf{y}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i}))$

Similar to $\Psi_{\textrm{init}}$, we define
$\Psi_{\textrm{end}}:=\Psi(t_{\textrm{end}},\mathbf{x}(t_{\textrm{end}}),\mathcal{K}_{\textrm{out}}(t_{\textrm{end}}))$.
Then, with this notation, we may use $\mathbf{y}_{t_{\textrm{end}}}$ to state
the following lower bound

$\displaystyle\Psi_{\textrm{end}}$
$\displaystyle=t_{\textrm{end}}\cdot\mathbf{c}^{\top}\mathbf{x}-\min_{\mathbf{A}\mathbf{y}=\mathbf{b}}(t_{\textrm{end}}\cdot\mathbf{c}^{\top}\mathbf{y}+\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{i}))$
$\displaystyle\geq
t_{\textrm{end}}\cdot(\mathbf{c}^{\top}\mathbf{y}_{\infty}-\mathbf{c}^{\top}\mathbf{y}_{t_{\textrm{end}}})-\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}(\mathbf{y}_{t_{\textrm{end}},i})).$
(5.28)

By LABEL:{lem:two-sided-ineq}, we may bound the difference
$\mathbf{c}^{\top}\mathbf{y}_{\infty}-\mathbf{c}^{\top}\mathbf{y}_{t_{\textrm{end}}}$
as follows:

$t_{\textrm{end}}\cdot(\mathbf{c}^{\top}\mathbf{y}_{\infty}-\cdot\mathbf{c}^{\top}\mathbf{y}_{t_{\textrm{end}}})\geq-\frac{\sum_{i=1}^{s}w_{i}\nu_{i}}{t_{\textrm{end}}}\cdot
t_{\textrm{end}}=-\sum_{i=1}^{s}w_{i}d_{i}.$

where we used Fact A.18 to deduce that the self-concordance parameter of
$\sum_{i=1}^{s}w_{i}\psi_{\textrm{out,}i}$ restricted to
$\mathbf{A}\mathbf{y}=\mathbf{b}$ is $\sum_{i=1}^{s}w_{i}\nu_{i}$ and each
$\psi_{\textrm{out,}i}$ is $O(d_{i})$ self-concordant. We now claim that

$\psi_{\textrm{out,}i}(\mathbf{y}_{t_{\textrm{end}},i})\leq\psi_{\textrm{out,}i}(\mathbf{y}^{\star}_{i})+O(d_{i}\log(dR/r)).$

Before proving this claim, we see that by combining Sections 5.2.5, 5.28,
5.2.5 and 5.2.5, that

$\Psi_{\textrm{init}}-\Psi_{\textrm{end}}\leq\sum_{i=1}^{s}w_{i}d_{i}\log(5dR/r)+o(m).$

We now show the claim in Section 5.2.5. In order to apply Fact A.19, we
consider the ray starting from by $\mathbf{y}^{\star}_{i}$ that passes through
$\mathbf{y}_{t_{\textrm{end}},i}$. Let $\mathbf{y}_{\textrm{bdry},i}$ to be
the point where the ray intersects with the set $\mathcal{K}_{\textrm{out}}$.
Note that there is a $s\in(0,1)$, such that

$\mathbf{y}_{t_{\textrm{end}},i}=\mathbf{y}^{\star}_{i}+s(\mathbf{y}_{\textrm{brdy},i}-\mathbf{y}^{\star}_{i}).$

We note that

$s=\frac{\|\mathbf{y}^{\star}_{i}-\mathbf{y}_{t_{\textrm{end}},i}\|}{\|\mathbf{y}_{\textrm{brdy},i}-\mathbf{y}^{\star}_{i}\|}\geq\frac{\|\mathbf{y}^{\star}_{i}-\mathbf{y}_{t_{\textrm{end}},i}\|}{2R}.$

By Lemma A.10, we have
$\|\mathbf{y}^{\star}_{i}-\mathbf{y}_{t_{\textrm{end}},i}\|\geq\frac{\bar{r}}{5d_{i}}$.
We finish the proof of Section 5.2.5 using Fact A.19.

Since the potential is a sum of universal barrier and entropic barrier terms,
we now need to bound the change in the universal barrier. The proof of this
change is identical to the corresponding proof in Lemma 4.8 of [DJLPY22], but
we include it next for completeness. Recall the definition of the universal
barrier terms
$\sum_{i\in[n]}w_{i}\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})$, where

$\psi_{\textrm{in,}i}(\mathbf{x}_{\textrm{i}})=\log\mathrm{vol}(\mathcal{K}_{\textrm{in,}i}^{\circ}(\mathbf{x}_{\textrm{i}})).$

Our computation follows a purely volume-based argument based on our
assumptions about the dimensions of the balls contained in and containing the
sets $\mathcal{K}_{\textrm{in}}$ and $\mathcal{K}_{\textrm{out}}$ and repeated
application of Fact A.8, as we now elaborate. Define $\mathcal{B}_{d}(0,r)$ to
be the $d$-dimensional Euclidean ball centered at the origin and with radius
$r$. We note by the radius assumption of Theorem 5.1 that
$\mathcal{K}_{\textrm{in,}i}\subseteq\mathcal{K}_{i}\subseteq\mathcal{B}_{d_{i}}(0,\bar{R})$
throughout the algorithm. By the assumption made in this lemma, we have at the
start of LABEL:alg:min-sum-convex-blackboard the inclusion
$\mathcal{B}_{d_{i}}(\mathbf{z}_{i},\bar{r})\subseteq\mathcal{K}_{\textrm{in,}i}$.
These two inclusion assumptions and Fact A.8 lead to the following bounds for
any $\mathbf{x}_{i}$.

$\psi_{\textrm{in,}i}^{\text{end}}(\mathbf{x}_{\textrm{i}})\geq\log(\mathrm{vol}(\mathcal{B}^{\circ}_{d_{i}}(0,\bar{R}))\text{
and
}\psi_{\textrm{in,}i}^{\text{init}}(\mathbf{x}_{\textrm{i}})\leq\log(\mathrm{vol}(\mathcal{B}_{d_{i}}^{\circ}(\mathbf{z}_{i},\bar{r}))).$

Combining Section 5.2.5, the fact that
$\mathrm{vol}(\mathcal{B}_{d}(0,r))\propto r^{d}$, Fact A.8, and summing over
all $i\in[s]$ gives

$\displaystyle\sum_{i\in[s]}w_{i}\left[\psi_{\textrm{in,}i}^{\text{init}}(\mathbf{x}_{\textrm{i}})-\psi_{\textrm{in,}i}^{\text{end}}(\mathbf{x}_{\textrm{i}})\right]$
$\displaystyle\leq\sum_{i\in[s]}w_{i}\log\left(\frac{\mathrm{vol}(\mathcal{B}_{d_{i}}(\mathbf{z}_{i},1/\bar{r}))}{\mathrm{vol}(\mathcal{B}_{d_{i}}(0,1/\bar{R}))}\right)=\sum_{i\in[s]}w_{i}d_{i}\log(\bar{R}/\bar{r})$
(5.33)

We finishes the proof by combining the inequality above and Section 5.2.5. ∎

######  Lemma 5.11 (Total oracle cost).

Suppose the inputs $\mathcal{K}_{\textrm{in}}$ and
$\mathcal{K}_{\textrm{out}}$ to LABEL:alg:min-sum-convex-blackboard satisfy
$\mathcal{K}_{\textrm{out}}\subseteq\mathcal{B}_{m}(0,\bar{R})$ with
$\bar{R}=O(\sqrt{n}R)$ and
$\mathcal{K}_{\textrm{in}}\supseteq\mathcal{B}(\mathbf{z},\bar{r})$ with
$\bar{r}=r/\operatorname{poly}(m)$. Then, when LABEL:alg:min-sum-convex-
blackboard terminates at $t\geq t_{\textrm{end}}$, it outputs a solution
$\mathbf{x}$ that satisfies

$\mathbf{c}^{\top}\mathbf{x}\leq\min_{\mathbf{x}\in\mathcal{K},A\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varepsilon\cdot\|\mathbf{c}\|_{2}R.$

Moreover, if the cost of the separation oracle on $\mathcal{K}_{i}$ is $w_{i}$
and $n_{i}$ is the number of times $\mathcal{O}_{i}$ is queried for all
$i\in[s]$, then the total cost of the separation oracle is at most
$O\left(\sum_{i}w_{i}d_{i}\log\left(\frac{mR}{\varepsilon r}\right)\right)$.
Namely,

$\sum_{i}^{s}w_{i}n_{i}\leq
O\left(\sum_{i}w_{i}d_{i}\log\left(\frac{mR}{\varepsilon r}\right)\right).$

###### Proof.

Let $\mathcal{N}_{\textrm{t}}$ be the number of times $t$ is updated;
$\mathcal{N}_{\textrm{in},i}$ the number of times
$\mathcal{K}_{\textrm{in,}i}$ is updated; $\mathcal{N}_{\textrm{out},i}$ the
number of times $\mathcal{K}_{\mathrm{out,}i}$ is updated;
$\mathcal{N}_{\mathbf{x}}$ the number of times $\mathbf{x}$ is updated, and
$\mathcal{N}_{\textrm{total}}$ the total number of iterations of the while
loop before termination of LABEL:alg:min-sum-convex-blackboard. Then,
combining Lemmas 5.3, 5.4, 5.7, 5.8 and 5.9 gives

$\Phi_{\textrm{end}}\leq\Phi_{\textrm{init}}-\sum_{i=1}^{s}0.1w_{i}\cdot\mathcal{N}_{\textrm{out},i}+\mathcal{N}_{\textrm{t}}\cdot(\eta+\eta^{2})+\sum_{i=1}^{s}\mathcal{N}_{\textrm{in},i}\cdot
w_{i}\log(1-1/e+\eta)+\mathcal{N}_{\mathbf{x}}\cdot\left(-\frac{\eta^{2}}{4}\right).$

The initialization step of LABEL:alg:min-sum-convex-blackboard chooses
$\eta=1/100$, $t_{\textrm{end}}=\frac{8m}{\varepsilon\|\mathbf{c}\|_{2}R}$,
and $t_{\textrm{init}}=\frac{m\log(m)}{\sqrt{n}\|\mathbf{c}\|_{2}R}$, and we
always update $t$ by a multiplicative factor of
$1+\frac{\eta}{4\sum_{i}w_{i}\nu_{i}}$ (see Step 1b); therefore, we have

$\mathcal{N}_{\textrm{t}}=O(\sum_{i}w_{i}\nu_{i}\log(mR/(\varepsilon r)).$

From LABEL:alg:min-sum-convex-blackboard, the only times the separation oracle
is invoked is when updating $\mathcal{K}_{\textrm{in}}$ or
$\mathcal{K}_{\textrm{out}}$ in Step 3(a)i and Step 3(a)ii, respectively.
Therefore, the cost of separation oracle on $\mathcal{K}_{i}$ is
$w_{i}n_{i}=w_{i}(\mathcal{N}_{\textrm{in},i}+\mathcal{N}_{\textrm{out},i})$.
Therefore, we have by applying the bound on
$\Phi_{\textrm{init}}-\Phi_{\textrm{end}}$ from Lemma 5.10 and the bound on
$\mathcal{N}_{\textrm{t}}$ from Section 5.2.5

$\sum_{i=1}^{s}w_{i}n_{i}=\sum_{i=1}^{s}w_{i}(\mathcal{N}_{\textrm{in}}+\mathcal{N}_{\textrm{out}})\leq
O(1)\cdot\left[\Phi_{\textrm{init}}-\Phi_{\textrm{end}}+\mathcal{N}_{\textrm{t}}\right]=O(\sum_{i=1}^{s}w_{i}d_{i}\log(mR/(\varepsilon
r)),$

which is the claimed separation oracle complexity. We now prove the guarantee
on approximation. Let $\mathbf{x}_{\text{output}}$ be the output of
LABEL:alg:min-sum-convex-blackboard and $\mathbf{x}$ be the point which
entered Step 1 right before termination. Note that the termination of
LABEL:alg:min-sum-convex-blackboard implies, by Step 1, that

$\mathbf{c}^{\top}\mathbf{x}_{\text{output}}\leq\mathbf{c}^{\top}\mathbf{x}+\frac{\nu}{t_{\textrm{end}}}\leq\mathbf{c}^{\top}\mathbf{x}_{\textrm{out}}^{\star}+\frac{4(n+m)}{t_{\textrm{end}}}\leq\min_{\mathbf{x}\in\mathcal{K},A\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varepsilon\cdot\|\mathbf{c}\|_{2}\cdot
R$

where the first step is by the second inequality in Lemma A.10 (using the
universal barrier) and the last step follows by our choice of
$t_{\textrm{end}}$ and the definition of $\mathbf{x}_{\textrm{out}}^{\star}$
and $\mathcal{K}_{\textrm{out}}\supseteq\mathcal{K}$. ∎

####  5.2.6 Proof of Theorem 5.1

We now use the results from the prior sections to complete our proof of
Theorem 5.1.

###### Proof of Theorem 5.1.

We apply Theorem 5.13 for each $\mathcal{K}_{i}$ separately to find a solution
$\mathbf{z}_{i}$. Then
$\mathbf{z}=(\mathbf{z}_{1},\dots,\mathbf{z}_{n})\in\mathbb{R}^{m+n}$
satisfies $\mathcal{B}_{m+n}(\mathbf{z},\bar{r})\subset\mathcal{K}$ with
$\bar{r}=\frac{r}{6d^{3.5}}$. Then, we modify the convex problem as in Lemma
5.14 with $\alpha=2^{16}\frac{m^{2.5}R}{r\varepsilon}$ and obtain the
following:

$\begin{array}[]{ll}\mbox{minimize}&\bar{\mathbf{c}}^{\top}{\bar{\mathbf{x}}}\\\
\mbox{subject to}&\bar{\mathbf{A}}\bar{\mathbf{x}}=\bar{\mathbf{b}},\\\
&\bar{\mathbf{x}}\in\bar{\mathcal{K}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathcal{K}\times\mathbb{R}_{\geq
0}^{m+n}\times\mathbb{R}_{\geq 0}^{m+n}\end{array}$

with

$\bar{\mathbf{A}}=[\mathbf{A}\mid\mathbf{A}\mid-\mathbf{A}],\bar{\mathbf{b}}=\mathbf{b},\bar{\mathbf{c}}=(\mathbf{c},\frac{\|\mathbf{c}\|_{2}s}{\sqrt{m+n}}\cdot\mathbf{1},\frac{\|\mathbf{c}\|_{2}s}{\sqrt{m+n}}\cdot\mathbf{1})^{\top}$

We solve the linear system
$\mathbf{A}\mathbf{y}=\mathbf{b}-\mathbf{A}\mathbf{z}$ for $\mathbf{y}$. Then,
we construct the initial $\overline{\mathbf{x}}$ by setting
$\overline{\mathbf{x}}^{(1)}=\mathbf{z}$,

$\overline{\mathbf{x}}^{(2)}_{i}=\begin{cases}\mathbf{y}_{i}&\text{if
}\mathbf{y}_{i}\geq 0,\\\ 0&\text{otherwise.}\end{cases}\quad\text{ and
}\quad\overline{\mathbf{x}}^{(3)}_{i}=\begin{cases}-\mathbf{y}_{i}&\text{if
}\mathbf{y}_{i}<0,\\\ 0&\text{otherwise}.\end{cases}$

Then, we run LABEL:alg:min-sum-convex-blackboard on the Section 5.2.6, with
initial $\overline{\mathbf{x}}$ set above,
$\bar{m}=3(m+n),\bar{n}=n+2,\bar{\varepsilon}=\frac{\varepsilon}{6\sqrt{n}s},\overline{\mathcal{K}}_{\textrm{in}}=\\{\mathbf{x}^{(1)}\in
B(\mathbf{z},\bar{r}),(\mathbf{x}^{(2)},\mathbf{x}^{(3)})\in\mathbb{R}_{\geq
0}^{2n}\\}$ and
$\widehat{\mathcal{K}}_{\textrm{out}}=\mathcal{B}_{\bar{m}}(\mathbf{0},\sqrt{n}R)$.
By our choice of $t_{\textrm{end}}$, we have

$\bar{t}_{\textrm{end}}=\frac{8\bar{m}}{\bar{\varepsilon}\|\bar{\mathbf{c}}\|_{2}\bar{R}}\leq\frac{48m}{\varepsilon\|\mathbf{c}\|_{2}R}.$

First, we check the condition that $\alpha\geq
48\bar{\nu}\bar{t}_{\textrm{end}}\sqrt{m+n}\frac{R^{2}}{r}\|\mathbf{c}\|_{2}$,
we note that

$48\bar{\nu}\bar{t}_{\textrm{end}}\sqrt{m+n}\frac{R^{2}}{r}\|\mathbf{c}\|_{2}\leq
27648\frac{m^{2.5}R}{\varepsilon r}\leq
2^{16}\frac{m^{2.5}R}{r\varepsilon}=\alpha.$

Let
$\bar{\mathbf{x}}_{output}=(\mathbf{x}_{output}^{(1)},\mathbf{x}_{output}^{(2)},\mathbf{x}_{output}^{(3)})$
be the output of LABEL:alg:min-sum-convex-blackboard. Then, let
$\mathbf{x}_{output}=\mathbf{x}_{output}^{(1)}+\mathbf{x}_{output}^{(2)}-\mathbf{x}_{output}^{(3)}$
as defined in Lemma 5.14. By Lemma 5.11, we have

$\min_{\mathbf{x}\in\mathcal{P}_{\textrm{in}}}\bar{\mathbf{c}}^{\top}\overline{\mathbf{x}}\leq\min_{\mathbf{x}\in\mathcal{P}}\mathbf{c}^{\top}\overline{\mathbf{x}}+\gamma$

where $\gamma=\bar{\varepsilon}\cdot\|\bar{\mathbf{c}}\|_{2}\cdot\bar{R}$.
Applying (3) of Lemma 5.14, we have

$\mathbf{c}^{\top}\mathbf{x}_{output}\leq\frac{\bar{\nu}+1}{\bar{t}_{\textrm{end}}}+\gamma+\min_{x\in\mathcal{K},A\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}\leq\min_{x\in\mathcal{K},A\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\varepsilon\cdot\|\mathbf{c}\|_{2}\cdot
R.$

The last inequality follows by our choice of $\bar{\varepsilon}$ and
$\bar{t}_{\textrm{end}}$, we have
$\gamma\leq\frac{\varepsilon}{2}\|\mathbf{c}\|_{2}R$ and
$\frac{\bar{\nu}+1}{\bar{t}_{\textrm{end}}}\leq\frac{\varepsilon}{2}\|\mathbf{c}\|_{2}R$.
Plug this $\bar{\varepsilon}$ in Lemma 5.11, it gives the claimed oracle cost.

∎

####  5.2.7 Proof of Main Result of Finite-Sum Minimization (Theorem 1.13)

See 1.13

###### Proof.

First, we reformulate the problem into Section 5.1 using Lemma 5.12. Then, we
apply Theorem 5.1 to the reduced problem to get the error guarantee. For the
communication complexity, we note that during initialization, each machine
sends the initial $\mathcal{K}_{\textrm{in,}i}$ it found, which takes
$O(\sum_{i=1}^{s}d_{i}L)$ bits of communication. Then, in the main loop, each
machine sends the output of the separation oracle, which takes
$O(\sum_{i=1}^{s}d_{i}^{2}\log(sd/\varepsilon)\cdot L)$ bits of communication
by setting $w_{i}=d_{i}$.

Finally, we show that it suffices to take the word length $L=O(\log(dR/r))$,
which is $O(\log(d))$ by our choice of $R$ and $r$. Recall that in the
algorithm, each message encodes the description of a halfspace $\mathcal{H}$,
which is described using two vectors $\mathbf{u},\mathbf{v}$ by
$\mathcal{H}=\\{\mathbf{x}:\mathbf{u}^{\top}(\mathbf{x}-\mathbf{v})\geq 0\\}$.
We describe these vectors in the relative scale of $r$. Lemma 5.3 shows that
if suffices to send $\mathbf{v}$ such that
$\|\mathbf{v}_{i}-\mu_{i}\|_{(\nabla^{2}w_{i}\varphi_{i}(\mu_{i}))^{-1}}\leq
0.01$. Using Corollary A.15, we know
$(\nabla^{2}w_{i}\varphi_{i}(\mu_{i}))^{-1}\succeq 4w_{i}R$, hence it suffices
to set word length of $\mathbf{v}$ to be $O(\log(dR/r))$. For $\mathbf{u}$, we
note that even if $\mathcal{H}$ cuts through $\mathcal{K}$, as long as the
radius of $\mathcal{K}$ is decreasing at rate of $1/d^{C}$ for some large
constant $C$, the algorithm still works. Therefore, it suffices to choose the
word length of $\mathbf{u}$ to be $O(\log(dR/r))$. ∎

###  5.3 Reductions and Initializations

######  Lemma 5.12.

Given the same setup of Theorem 1.13, there is an algorithm using
$O(sd\log(d))$ bits of communication, which reduces the original problem to
the following formulation,

$\begin{array}[]{ll}\mbox{minimize}&\mathbf{c}^{\top}\mathbf{x},\\\
\mbox{subject
to}&\mathbf{x}_{\textrm{i}}\in\mathcal{K}_{i}\subseteq\mathbb{R}^{d_{i}+1}\;\forall
i\in[s]\\\ &\mathbf{A}\mathbf{x}=\mathbf{b}.\end{array}$

where $\mathbf{x}=[\mathbf{x}_{i}]$ concatenates the $s$ vectors
$\mathbf{x}_{i}\in\mathbb{R}^{d_{i}}$. Denote
$\mathcal{K}=\mathcal{K}_{1}\times\mathcal{K}_{2}\times\dotsc\times\mathcal{K}_{s}$,
$\mathcal{K}$ satisfies the following properties:

  * convexity: Each $\mathcal{K}_{i}$ is convex and disjoint with each other.

  * outer radius $R$: For any $\mathbf{x}\in\mathcal{K}_{i}$, we have $\|\mathbf{x}_{i}\|_{2}\leq R$.

  * inner radius $r$: There exists a $\mathbf{z}\in\mathbb{R}^{d}$ such that $\mathbf{A}\mathbf{z}=\mathbf{b}$ and $\mathcal{B}(\mathbf{z},r)\subset\mathcal{K}$.

  * radius ratio: $R/r=O(1)$.

After the reduction, all the machines hold all the data — radii $R$ and $r$,
vectors $\mathbf{c},\mathbf{b},\mathbf{x}$, matrix $\mathbf{A}$ — and the
$i^{\mathrm{th}}$ machine holds the separation oracle $\mathcal{O}_{i}$ for
the $i^{\mathrm{th}}$ set $\mathcal{K}_{i}$.

###### Proof.

The reduction is standard by using using a change of variables and the
epigraph trick, but we include it here for completeness. Suppose each $f_{i}$
depends on $d_{i}$ coordinates of $\mathbf{\theta}$ given by
$\\{i_{1},\dots,i_{d_{i}}\\}\subseteq[d]$. Then, symbolically define
$\mathbf{x}_{i}=[x^{(i)}_{i_{1}};x^{(i)}_{i_{2}};\dots;x^{(i)}_{i_{d_{i}}}]\in\mathbb{R}^{d_{i}}$
for each $i\in[n]$. Since each $f_{i}$ is convex and supported on $d_{i}$
variables, its epigraph is convex and $d_{i}+1$ dimensional. So we may define
the convex set

$\mathcal{K}_{i}^{\textrm{unbounded}}=\left\\{(\mathbf{x}_{i},z_{i})\in\mathbb{R}^{d_{i}+1}:f_{i}(\mathbf{x}_{i})\leq
Lz_{i}\right\\}.$

Finally, we add linear constraints of the form $x^{(i)}_{k}=x^{(j)}_{k}$ for
all $i,j,k$ where $f_{i}$ and $f_{j}$ both depend on $\mathbf{\theta}_{k}$. We
denote these by the matrix constraint $\mathbf{A}\mathbf{x}=\mathbf{b}$. Then,
the problem is equivalent to

$\begin{array}[]{ll}\mbox{minimize}&\sum_{i=1}^{s}Lz_{i}\\\ \mbox{subject
to}&\mathbf{A}\mathbf{x}=\mathbf{b}\\\
&(\mathbf{x}_{i},z_{i})\in\mathcal{K}_{i}^{\textrm{unbounded}}\text{ for each
$i\in[n]$}.\end{array}$ (5.37)

Since we are given $\mathbf{\theta}^{(0)}$ satisfying
$\|{\mathbf{\theta}^{(0)}-\mathbf{\theta}^{*}}\|_{2}\leq D$, we define
$\mathbf{x}_{i}^{(0)}=[\mathbf{\theta}^{(0)}_{i_{1}};\dots,\mathbf{\theta}^{(0)}_{i_{d_{i}}}]$
and $z_{i}^{(0)}=f_{i}(\mathbf{\theta}^{(0)})/L$. Then, we can restrict the
search space $\mathcal{K}_{i}^{\textrm{unbounded}}$ to

$\displaystyle\mathcal{K}_{i}$
$\displaystyle=\mathcal{K}_{i}^{\textrm{unbounded}}\cap\\{(\mathbf{x}_{i},z_{i})\in\mathbb{R}^{d_{i}+1}:\|\mathbf{x}_{i}-\mathbf{x}_{i}^{(0)}\|_{2}\leq
D\text{ and }z_{i}^{(0)}-2D\leq z_{i}\leq z_{i}^{(0)}+2D\\}.$

One can then check that $\mathcal{K}_{i}$ is contained in a ball of radius
$5D$ centered at $(\mathbf{x}^{(0)}_{i},z_{i}^{(0)})$ and contains a ball of
radius $D$ centered at $(\mathbf{x}^{(0)}_{i},z_{i}^{(0)})$. The subgradient
oracle for $f_{i}$ translates to a separation oracle for $\mathcal{K}_{i}$. We
note that this reduction only requires the knowledge of $L$, $R$,
$\theta^{(0)}$, and the support $D_{i}$ for each $f_{i}$. By sending these
information to blackboard, each machine can apply this reduction on their own.
This takes $O\left(\sum_{i=1}^{s}d_{i}\log(d)\right)$ many bits of
communication. ∎

Now, we show how to construct an initial set $\mathcal{K}_{\textrm{in}}$ and
find a good initial point for LABEL:alg:min-sum-convex-blackboard by slightly
modifying the convex program above. These results first appeared in [DJLPY22],
which we slightly modify to suit our purpose.

######  Theorem 5.13 ([DJLPY22, Lemma 5.1]).

Suppose we have separation oracle access to a convex set $\mathcal{K}$
satisfying
$\mathcal{B}(\mathbf{z},r)\subseteq\mathcal{K}\subseteq\mathcal{B}(\mathbf{0},R)$
for some $\mathbf{z}\in\mathbb{R}^{d}$. Then, there is a randomized algorithm,
which in $O(d\log(R/r))$ separation oracle calls to $\mathcal{K}$, outputs a
point $\mathbf{x}$ such that
$\mathcal{B}\left(\mathbf{x},\frac{r}{6d^{3.5}}\right)\subseteq\mathcal{K}$.

To find a good initialization for LABEL:alg:min-sum-convex-blackboard, we need
to slightly modify the convex program, for which we simply invoke the
following result from [DJLPY22].

######  Lemma 5.14 ([DJLPY22, Lemma 5.6]).

Given a convex program
$\min_{\mathbf{A}\mathbf{x}=\mathbf{b},\mathbf{x}\in\mathcal{K}\subseteq\mathbb{R}^{d}}\mathbf{c}^{\top}\mathbf{x}$
with outer radius $R$ and some $\alpha>0$, we define
$\mathbf{c}_{1}=\mathbf{c},\mathbf{c}_{2}=\mathbf{c}_{3}=\frac{\alpha\|\mathbf{c}\|_{2}}{\sqrt{d}}\cdot\mathbf{1}$
and
$\mathcal{P}=\\{\mathbf{x}^{(1)}\in\mathcal{K},(\mathbf{x}^{(2)},\mathbf{x}^{(3)})\in\mathbb{R}_{\geq
0}^{2d}:\mathbf{A}(\mathbf{x}^{(1)}+\mathbf{x}^{(2)}-\mathbf{x}^{(3)})=\mathbf{b}\\}$.
We then define the modified convex program by

$\min_{(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\mathbf{x}^{(3)})\in\mathcal{P}}\mathbf{c}_{1}^{\top}\mathbf{x}^{(1)}+\mathbf{c}_{2}^{\top}\mathbf{x}^{(2)}+\mathbf{c}_{3}^{\top}\mathbf{x}^{(3)}.$

Given some $\mathcal{K}_{\textrm{in}}\in\mathcal{K}$ where inner radius $r$,
and an arbitrary $t\in\mathbb{R}_{\geq 0}$, we further define the function

$f_{t}(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\mathbf{x}^{(3)})=t(\mathbf{c}_{1}^{\top}\mathbf{x}^{(1)}+\mathbf{c}_{2}^{\top}\mathbf{x}^{(2)}+\mathbf{c}_{3}^{\top}\mathbf{x}^{(3)})+\psi_{\mathcal{P}_{\text{in}}}(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\mathbf{x}^{(3)})$

where $\psi_{\mathcal{P}_{\text{in}}}$ is some $\nu$ self-concordant barrier
for the set

$\mathcal{P}_{\text{in}}=\\{\mathbf{x}^{(1)}\in\mathcal{K}_{\textrm{in}},(\mathbf{x}^{(2)},\mathbf{x}^{(3)})\in\mathbb{R}_{\geq
0}^{2d}:\mathbf{A}(\mathbf{x}^{(1)}+\mathbf{x}^{(2)}-\mathbf{x}^{(3)})=\mathbf{b}\\}.$

Given
$\overline{\mathbf{x}}_{t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\mathbf{x}_{t}^{(1)},\mathbf{x}_{t}^{(2)},\mathbf{x}_{t}^{(3)})=\arg\min_{(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\mathbf{x}^{(3)})\in\mathcal{P}_{\textrm{in}}}f_{t}(\mathbf{x}^{(1)},\mathbf{x}^{(2)},\mathbf{x}^{(3)})$,
we denote
$\mathbf{x}_{\text{in}}=\mathbf{x}_{t}^{(1)}+\mathbf{x}_{t}^{(2)}-\mathbf{x}_{t}^{(3)}$.
Suppose
$\min_{\overline{\mathbf{x}}\in\mathcal{P}_{\textrm{in}}}\bar{\mathbf{c}}^{\top}\overline{\mathbf{x}}\leq\min_{\overline{\mathbf{x}}\in\mathcal{P}}\bar{\mathbf{c}}^{\top}\overline{\mathbf{x}}+\gamma$
and $\alpha\geq 48\nu t\sqrt{d}\cdot\frac{R}{r}\cdot\|c\|_{2}R$, then we have
that $\mathbf{A}\mathbf{x}_{\text{in}}=\mathbf{b}$,
$\mathbf{x}_{\text{in}}\in\mathcal{K}_{\textrm{in}}$, and
$\mathbf{c}^{\top}\mathbf{x}_{\text{in}}\leq\min_{\mathbf{x}\in\mathcal{K},\mathbf{A}\mathbf{x}=\mathbf{b}}\mathbf{c}^{\top}\mathbf{x}+\frac{\nu+1}{t}+\gamma$.
We denote $(\mathbf{c}_{1},\mathbf{c}_{2},\mathbf{c}_{3})$ by
$\overline{\mathbf{c}}$.

##  6 Lower Bounds

###  6.1 Lower Bound Primitives

We introduce two fundamental communication problems, the latter of which is an
$s$-player version of the first.

######  Problem 6.1.

Alice an Bob hold unit vectors $\mathbf{v}$ and $\mathbf{w}$ respectively in
$\mathbb{R}^{d}$. They would like to decide between (a)
$\left\langle\mathbf{v},\mathbf{w}\right\rangle=0$, and (b)
$|\left\langle\mathbf{v},\mathbf{w}\right\rangle|\geq\frac{\varepsilon}{d}$
under the promise that one of these conditions holds.

See 1.17

For each of these problems we prove a corresponding hardness hardness result.
For the two player version of the game we have the following communication
lower bound.

######  Lemma 6.2.

A protocol solving Problem 6.1 with probability at least $0.9$ requires at
least $\Omega(d\log\frac{1}{\varepsilon})$ communication for $r$-round
protocols when $r\leq
c\log\frac{1}{\varepsilon}/\log\log\frac{1}{\varepsilon}$ for an absolute
constant $c$.

While our argument requires a technical assumption on the number of rounds,
this can almost certainly be removed via a more careful analysis. Moreover, in
constant dimension our argument directly implies the bound above, with no
requirement on the number of rounds.

Given the lemma above we will show how to boost it to an $s$-player lower
bound.

See 1.18

We will prove these results below. Before presenting the proofs we give the
reductions to linear regression and linear programming.

###  6.2 Reduction to Linear Regression

We now present our lower bound for Problem 6.3 and will then return to
analyzing the communication complexity of the two problems above.

Our main interest is the following communication problem.

######  Problem 6.3.

Each of $s$ servers holds a matrix $\mathbf{A}^{(i)}$ and vector
$\mathbf{b}^{(i)}$ for $i=1,\ldots,s.$ Let $\mathbf{A}$ and $\mathbf{b}$ the
vertical stack of the the $\mathbf{A}^{(i)}$’s and $\mathbf{b}^{(i)}$’s
respectively. All entries are held to $L$ bits of precision. The coordinator
must produce a vector $\hat{\mathbf{x}}$ with

$\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|\leq
2\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|,$

where
$\mathbf{x}_{*}=\operatorname*{arg\,min}_{x}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|.$

######  Theorem 6.4.

A protocol that solves Problem 6.3 with at least $0.99$ probability requires
$\tilde{\Omega}(sd\log L)$ bits of communication provided that there are at
most $C\log L/\log\log L$ rounds of communication between the coordinator and
each server for an absolute constant $C$. Additionally, if $\mathbf{A}$ is
promised to have condition number at most $\kappa$ then assuming at most
$C\log\kappa/\log\log\kappa$ rounds per server, any protocol requires at least
$\tilde{\Omega}(sd\min(L,\log\kappa)$ communication.

###### Proof.

We reduce from Problem 1.17 above. To construct a linear system, the
coordinator first computes an orthonormal basis
$\mathbf{u}_{1},\ldots\mathbf{u}_{d-1}$ for $\mathbf{v}^{\perp}$ and then
rounds each vector to $L$ bits of precision to obtain
$\mathbf{u}_{1}^{\prime},\ldots,\mathbf{u}_{d-1}^{\prime}$. The coordinator
then forms a matrix with rows
$\alpha\mathbf{v}^{\prime},\mathbf{u}_{1}^{\prime},\ldots,\mathbf{u}_{d-1}^{\prime},$
where $\alpha<1$ is a small parameter that will be chosen later and where
$\mathbf{v}^{\prime}$ is $\mathbf{v}$ rounded to $L$ bits of precision. Each
server $i$ simply holds the vector $\mathbf{w}_{i}^{\prime}$ which is
$\mathbf{w}_{i}$ rounded to $L$ bits of precision. Let $\mathbf{A}$ denote
this matrix which is distributed across the servers. Also set $\mathbf{b}$ to
have all entries equal to $0$, except with a $1$ in the entry corresponding to
the row $\alpha\mathbf{v}^{\prime}$. We will show that the norm of an
approximate regression solution $\hat{\mathbf{x}}$ allows us to distinguish
between the two possibilities in Problem 1.17.

Suppose that for some $i$,
$|\left\langle\mathbf{w}_{i},\mathbf{v}\right\rangle|\geq\varepsilon^{\prime}:=\varepsilon/d.$
We lower bound the smallest singular value of $\mathbf{A}.$ Let $\mathbf{M}$
be the matrix with rows
$\mathbf{u}_{1},\ldots,\mathbf{u}_{d-1},\mathbf{w}_{i}.$ To lower bound the
smallest singular value of $\mathbf{M}$, let $\mathbf{x}$ be an arbitrary unit
vector and write $\mathbf{x}=\mathbf{x}_{1}+\mathbf{x}_{2}$ where
$\mathbf{x}_{1}$ is the projection of $\mathbf{x}$ onto $\mathbf{v}.$ Then
$\|\mathbf{M}\mathbf{x}\|\geq\|\mathbf{x}_{2}\|$ and also

$\displaystyle\|\mathbf{M}\mathbf{x}\|\geq|\left\langle\mathbf{x},\mathbf{w}_{i}\right\rangle|$
$\displaystyle=|\left\langle\mathbf{x}_{1},\mathbf{w}_{i}\right\rangle+\left\langle\mathbf{x}_{2},\mathbf{w}_{i}\right\rangle|$
$\displaystyle\geq|\left\langle\mathbf{x}_{1},\mathbf{w}_{i}\right\rangle|-\|\mathbf{x}_{2}\|$
$\displaystyle=|\left\langle\|\mathbf{x}_{1}\|\mathbf{v},\mathbf{w}_{i}\right\rangle|-\|\mathbf{x}_{2}\|$
$\displaystyle\geq\varepsilon^{\prime}\|\mathbf{x}_{1}\|-\|\mathbf{x}_{2}\|.$

Thus

$\|\mathbf{M}\mathbf{x}\|\geq\max(\|\mathbf{x}_{2}\|_{,}\varepsilon^{\prime}\|\mathbf{x}_{1}\|-\|\mathbf{x}_{2}\|)\geq\max(\|\mathbf{x}_{2}\|_{,}(\varepsilon^{\prime}/2)\|\mathbf{x}_{1}\|),$

since the maximum of two numbers is at least their average. Since
$\|\mathbf{x}_{1}\|^{2}+\|\mathbf{x}_{2}\|^{2}=1,$ this latter quantity is at
least $\varepsilon^{\prime}/3.$ This shows that
$\sigma_{\min}(\mathbf{M})\geq\varepsilon^{\prime}/3.$

Let $\mathbf{M}^{\prime}$ be matrix $\mathbf{M}$ with the rows rounded as
above. Note that all entries of $\mathbf{M}-\mathbf{M}^{\prime}$ are bounded
in absolute value by $2^{-L}$ so $\|\mathbf{M}-\mathbf{M}^{\prime}\|\leq
2^{-L}d.$ It follows that

$\sigma_{\min}(\mathbf{A})\geq\sigma_{\min}(\mathbf{M}^{\prime})\geq\varepsilon^{\prime}/3-2^{-L}d\geq\varepsilon^{\prime}/4,$

provided that we later choose $\log(1/\varepsilon)\leq L-\log(12d).$

Now let $\hat{\mathbf{x}}$ satisfy
$\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|^{2}\leq(1+\beta)\|\mathbf{M}\mathbf{x}_{*}-\mathbf{b}\|^{2}$
(we will later set $\beta=1$). Then we have

$(1+\beta)\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2}\geq\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|^{2}=\|\mathbf{A}(\hat{\mathbf{x}}-\mathbf{x}_{*})\|^{2}+\|\mathbf{A}x_{*}-\mathbf{b}\|^{2},$

and so $\|\mathbf{A}(\hat{\mathbf{x}}-\mathbf{x}_{*})\|\leq\sqrt{\beta}$. So
we get

$\sigma_{\min}(\mathbf{A})\|\hat{\mathbf{x}}\|\leq\|\mathbf{A}\hat{\mathbf{x}}\|\leq\|\mathbf{A}\mathbf{x}_{*}\|+\sqrt{\beta}\leq
1+\sqrt{\beta}.$

Hence
$\|\hat{\mathbf{x}}\|\leq\frac{4}{\varepsilon^{\prime}}(1+\sqrt{\beta}).$

Now suppose that $|\left\langle\mathbf{w}_{i},\mathbf{v}\right\rangle|=0$ for
all $i.$ Set $\eta=2^{-L}d$. In this case, we have

$\displaystyle\|\mathbf{A}(\alpha^{-1}\mathbf{v})-\mathbf{b}\|^{2}$
$\displaystyle=(\left\langle\mathbf{v},\mathbf{v}^{\prime}\right\rangle-1)^{2}+\sum_{i=1}^{d-1}\left\langle\alpha^{-1}\mathbf{v},\mathbf{u}_{i}^{\prime}\right\rangle^{2}+\sum_{i=1}^{s}\left\langle\alpha^{-1}\mathbf{v},\mathbf{w}_{i}^{\prime}\right\rangle^{2}$
$\displaystyle\leq\eta^{2}+\alpha^{-2}d\eta^{2}+\alpha^{-2}s\eta^{2}$
$\displaystyle=(\alpha^{-2}s+\alpha^{-2}d+1)\eta^{2}.$

Suppose that $\mathbf{x}_{*}$ is the least squares solution and that
$\|\mathbf{A}\hat{x}-b\|^{2}\leq(1+\beta)\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2}.$
Then

$\displaystyle(1+\beta)(\alpha^{-2}s+\alpha^{-2}d+1)\eta^{2}$
$\displaystyle\geq(1+\beta)\|\mathbf{A}(\alpha^{-1}\mathbf{v})-\mathbf{b}\|^{2}$
$\displaystyle\geq(1+\beta)\|\mathbf{A}\mathbf{x}^{*}-\mathbf{b}\|^{2}$
$\displaystyle\geq\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|^{2}$
$\displaystyle\geq(\left\langle\hat{\mathbf{x}},\alpha\mathbf{v}\right\rangle-1)^{2}.$

This implies that

$\|\hat{\mathbf{x}}\|\geq|\left\langle\hat{\mathbf{x}},\mathbf{v}\right\rangle|\geq\alpha^{-1}\left(1-\eta\sqrt{(1+\beta)(\alpha^{-2}s+\alpha^{-2}d+1)}\right).$

We can distinguish the two inputs using $\|\hat{x}\|$ as long as

$\frac{4}{\varepsilon^{\prime}}=\frac{4d}{\varepsilon}<\alpha^{-1}\left(1-\eta\sqrt{(1+\beta)(\alpha^{-2}s+\alpha^{-2}d+1)}\right).$

To make this happen we choose our parameters. Set $\beta=1$. The quantity in
parentheses is at least $1/2$ as long as $\eta\alpha^{-1}\sqrt{s+d}\leq 1/4.$
So it suffices for this to hold, along with
$\alpha^{-1}>\frac{8d}{\varepsilon}.$

There is an $\alpha$ that satisfies these bounds, as long as
$\frac{8d}{\varepsilon}<\eta^{-1}(s+d)^{-1/2}=\frac{2^{L}}{d}(s+d)^{-1/2}$
which holds when $\log\frac{1}{\varepsilon}\leq L-4\log(s+d).$ Given this
bound, we can then take $\alpha=O(\varepsilon/d)$ (say rounded to an
appropriate power of $2$ so that bit precision is unaffected), and take
$\varepsilon$ such that $\log\frac{1}{\varepsilon}\leq L-c\log(s+d)$ for an
abolute constant $c.$ Then Problem 1.17 that we reduced from, requires
$\Omega(sdL)$ communication by Theorem 1.18, provided that $L\geq 8(s+d)$, and
therefore so does Problem 6.3.

Finally we check the condition number of our hard instance. Note that we
always have
$\kappa(\mathbf{A})=\frac{\sigma_{\max}(\mathbf{A})}{\sigma_{\min}(\mathbf{A})}\leq\frac{\sqrt{2d+s}}{\alpha}=O(\frac{1}{\varepsilon}\operatorname{poly}(s+d)).$
Choosing

$\varepsilon\approx\min(\operatorname{poly}(s+d)/\kappa,L-c\log(s+d))$

gives the second statement of the theorem. ∎

###  6.3 Reduction to Linear Feasibility

######  Problem 6.5.

(Linear Feasibility) Each of $s$ servers holds a matrix $\mathbf{A}^{(i)}$ and
vector $\mathbf{b}^{(i)}.$ All entries are held to $L$ bits of precision. They
would like to decide whether there is an $\mathbf{x}$ satisfying
$\mathbf{A}\mathbf{x}\leq\mathbf{b}$.

See 1.16

###### Proof.

We give a simple reduction from Problem 1.17. Recall that in this problem, the
coordinator holds a vector $\mathbf{v}$ and the $s$ servers holds vectors
$\mathbf{w}_{1},\ldots,\mathbf{w}_{s}.$

Set $\eta=2^{-L}\lceil\sqrt{d}\rceil$. Let $v^{\prime}$ denote $v$ with each
entry rounded towards $0$ to $L$ bits of precision, and similarly for
$\mathbf{w}_{1}^{\prime},\ldots,\mathbf{w}_{s}^{\prime}.$ For our reduction,
each server $i$ sets $\mathbf{A}^{(i)}_{1}=\mathbf{w}_{i}^{\prime}$,
$\mathbf{A}^{(i)}_{2}=-\mathbf{w}_{i}^{\prime}$ and sets
$\mathbf{b}^{(i)}_{1}=\mathbf{b}^{(i)}_{2}=2\eta$, thereby creating the
constraint $|\left\langle\mathbf{w}_{i}^{\prime},\mathbf{x}\right\rangle|\leq
2\eta.$

The coordinator similarly adds rows corresponding to the constraints
$x_{j}\leq v^{\prime}_{j}$ and $-x_{j}\leq v^{\prime}_{j}$ for $j=1,\ldots,d$,
which simply amounts to the constraint $\mathbf{x}=\mathbf{v}^{\prime}.$

Suppose that $\left\langle\mathbf{w}_{i},\mathbf{v}\right\rangle=0$ for all
$i.$ Then

$|\left\langle\mathbf{v}^{\prime},\mathbf{w}_{i}^{\prime}\right\rangle|=|\left\langle\mathbf{v}^{\prime},\mathbf{w}_{i}^{\prime}\right\rangle-\left\langle\mathbf{v},\mathbf{w}_{i}\right\rangle|=|\left\langle\mathbf{v}-\mathbf{v}^{\prime},\mathbf{w}^{\prime}\right\rangle+\left\langle\mathbf{v}^{\prime},\mathbf{w}_{i}-\mathbf{w}_{i}^{\prime}\right\rangle|\leq\|\mathbf{v}-\mathbf{v}^{\prime}\|+\|\mathbf{w}_{i}-\mathbf{w}_{i}^{\prime}\|\leq
2\eta$

for all $i$ since $\|\mathbf{v}^{\prime}-\mathbf{v}\|\leq\eta$ and
$\|\mathbf{w}_{i}^{\prime}-\mathbf{w}_{i}\|\leq\eta$. This means that the
constraints are satisfied by taking $\mathbf{x}=\mathbf{v}^{\prime}.$

On the other hand, suppose that
$|\left\langle\mathbf{w}_{i},\mathbf{v}\right\rangle|\geq\varepsilon/d$ for
some $i.$ Then we must have $\mathbf{x}=\mathbf{v}^{\prime}$, but then

$|\left\langle\mathbf{x},\mathbf{w}_{i}^{\prime}\right\rangle-\left\langle\mathbf{v}^{\prime},\mathbf{w}_{i}^{\prime}\right\rangle|\leq
2\eta$

by the same calculation as above, which means that
$|\left\langle\mathbf{x},\mathbf{w}_{i}^{\prime}\right\rangle|\geq\varepsilon/d-2\eta.$
So the constraints are not satisfiable as long as $\varepsilon$ is chosen so
that $\varepsilon>4\eta d.$ Therefore a protocol that solves the linear
feasibility problem above can solve Problem 1.17 for $\varepsilon=O(\eta d)$,
which means it requires at least $\Omega(sdL)$ communication by Theorem 1.18.
∎

###  6.4 Proof of Theorem 1.18

####  6.4.1 Harmonic Analysis Setup

We will use a similar set of tools to [RK11]. To streamline the analysis, we
very briefly recall some facts about Fourier analysis on the sphere. We will
use the notation $L^{2}(\mathbb{S}^{d-1})$ to indicate the space of real-
valued square-integrable functions on $\mathbb{S}^{d-1}.$ This is a Hilbert
space with inner product given by

$\left\langle
f,g\right\rangle_{L^{2}}=\int_{\mathbb{S}^{d-1}}f(\mathbf{x})g(\mathbf{x})d\sigma_{d-1}(\mathbf{x}),$

where $\sigma_{d-1}$ is the rotationally invariant probability measure on
$\mathbb{S}^{d-1}.$

The fundamental fact from Fourier analysis that we use is that any $L_{2}$
function $f$ on the $\mathbb{S}^{d-1}$ can be decomposed into a sum of
spherical harmonics as

$f=\sum_{k}\Pi_{\mathcal{H}_{k}}f$

where $\mathcal{H}_{k}$ is the subspace consisting of spherical harmonics of
degree $k$ and $\Pi_{\mathcal{H}_{k}}$ is the orthogonal projection onto that
subspace. Any operator on $L^{2}(\mathbb{S}^{d-1})$ that commutes with
rotations has an eigen-decomposition with eigenspaces given by the
$\mathcal{H}_{k}$’s.

The space $\mathcal{H}_{k}$ contains a special class of axially-symmetric
functions known as the zonal spherical harmonics. The zonal spherical harmonic
$z_{k,\mathbf{v}}$ of degree $k$ and axis of symmetry
$\mathbf{v}\in\mathbb{S}^{d-1}$ is given by

$z_{k,\mathbf{v}}(\mathbf{x})=G_{k}^{(d/2-1)}(\left\langle\mathbf{x},\mathbf{v}\right\rangle),$

where $G_{k}^{(\alpha)}:[-1,1]\rightarrow\mathbb{R}$ is the so-called
Gegenbauer polynomial of degree $k$ with parameter $\alpha$. There are many
ways to define the Gegenbauer polynomials, for example by their generating
function [Sze62]:

$\frac{1}{(1-2xt+t^{2})^{\alpha}}=\sum_{k=0}^{\infty}G_{k}^{(\alpha)}(x)t^{k}.$
(6.1)

The Gegenbauer polynomials satisfy many interesting identities. We will use
the following identity for the derivative of $G_{k}^{(\alpha)}$ which follows
from differentiating Equation 6.1 [Sze62]:

$\frac{d}{dx}G_{k}^{(\alpha)}(x)=2\alpha G_{k-1}^{(\alpha+1)}(x).$ (6.2)

It is also simple to compute $G_{k}^{(\alpha)}(1)$ from Equation 6.1. Plugging
in $x=1$ gives

$(1-t)^{-2\alpha}=\sum_{k=0}^{\infty}G_{k}^{(\alpha)}(1)t^{k},$

so $G_{k}^{(\alpha)}(1)=(-1)^{k}\binom{-2\alpha}{k}$ by the generalized
binomial theorem. In particular we will use the following values below:

$\displaystyle G_{k}^{(1/2)}(1)$ $\displaystyle=1$ (6.3) $\displaystyle
G_{k}^{(3/2)}(1)$ $\displaystyle=\frac{(k+2)(k+1)}{2}.$ (6.4)

The zonal spherical harmonics $z_{k,\mathbf{v}}$ (in any dimension) are also
well-known to have the maximum sup-norm among the degree $k$ spherical
harmonics of fixed $L^{2}$ norm, with this maximum value achieved at
$\mathbf{v}.$ One way to see this is to recall that for an appropriate
normalizing constant $c_{k,d}$, the zonal spherical harmonic
$c_{k,d}z_{k,\mathbf{v}}$ satisfies the reproducing property $\left\langle
c_{k,d}z_{k,\mathbf{v}},f\right\rangle_{L^{2}}=f(\mathbf{v})$ for all
$f\in\mathcal{H}_{k}$ (see [Dai13] for example). Therefore for
$f\in\mathcal{H}(k)$ with $\|f\|_{L^{2}}=1$,

$|f(\mathbf{v})|=|\left\langle
c_{k,d}z_{k,\mathbf{v}},f\right\rangle_{L^{2}}|\leq\left\langle
c_{k,d}z_{k,\mathbf{v}},\frac{1}{\|z_{k,\mathbf{v}}\|_{L^{2}}}z_{k,\mathbf{v}}\right\rangle_{L^{2}}\leq\frac{1}{\|z_{k,\mathbf{v}}\|_{L^{2}}}z_{k,\mathbf{v}}(\mathbf{v}).$

As a particular consequence of this fact,

$\sup_{x\in[-1,1]}|G_{k}^{(n/2)}(x)|=G_{k}^{(n/2)}(1)\\\ $ (6.5)

for all natural numbers $n.$

We also recall the spherical Radon transform, also known as the Minkowski-Funk
transform $R:L^{2}(\mathbb{S}^{d-1})\rightarrow L^{2}(\mathbb{S}^{d-1})$,
which for a function $f$ on $\mathbb{S}^{d-1}$ is defined by

$Rf(x)=\int_{x^{\perp}}f(y)d\sigma_{x^{\perp}}(y),$

where $\sigma_{x^{\perp}}$ is the natural probability measure over
$x^{\perp}\cap\mathbb{S}^{d-1}.$ In other words, $Rf(x)$ is the average of $f$
over the spherical equator perpendicular to $x.$ The following computation of
eigenvalues is classical, and due to Funk [Fun11]. A similar formula holds in
all dimensions, but we will only need the result for $\mathbb{S}^{2}.$

######  Proposition 6.6.

The eigenfunctions of the spherical Radon transform
$R:L^{2}(\mathbb{S}^{2})\rightarrow L^{2}(\mathbb{S}^{2})$ are precisely the
spherical harmonics of degree $k$, and the associated eigenvalues are

$\mu_{k}=(-1)^{k/2}\frac{(k-1)!!}{k!!}$

for $k$ even, and $0$ for $k$ odd.

To simplify our computations later, we give a simple upper bound on the
eigenvalues of $R$ that follows immediately from the formula above.

######  Proposition 6.7.

Let $f_{k}$ be a unit spherical harmonic on $\mathbb{S}^{2}$ of degree $k$.
Then

$\mu_{k}^{2}\leq\frac{1}{k}.$

###### Proof.

By the formula above in Proposition 6.6, when $k$ is even,

$|\mu_{k}|=\frac{1}{2}\cdot\frac{3}{4}\cdot\frac{5}{6}\cdot\ldots\cdot\frac{k-1}{k},$

so

$\mu_{k}^{2}\leq\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{3}{4}\cdot\ldots\cdot\frac{k-1}{k}=\frac{1}{k},$

as desired. ∎

We will also make use of a local averaging operator $T_{\varepsilon}$. Similar
to the Radon transform we define $T_{\varepsilon}f(\mathbf{x})$ to be the
average of $f$ over the set
$\\{\mathbf{y}\in\mathbb{S}^{d-1}:\left\langle\mathbf{x},\mathbf{y}\right\rangle=1-\varepsilon\\}$
equipped with the probability measure that is invariant under rotations fixing
$\mathbf{x}.$

######  Proposition 6.8.

The eigenfunctions of $T_{\varepsilon}$ are the degree $k$ spherical
harmonics, and when $d=3$, the associated eigenvalues $\xi_{k}$ satisfy the
bound

$|1-\xi_{k}|\leq\min(\varepsilon k^{2},2).$

###### Proof.

It is clear that $T_{\varepsilon}$ commutes with rotations, so the
$\mathcal{H}_{k}$’s are the eigenspaces for $T_{\varepsilon}.$ We analyze the
eigenvalues of $T_{\varepsilon}$ by considering its action on the degree $k$
zonal spherical harmonic $z_{k,\mathbf{v}}=G_{k}^{(1/2)}(\left\langle
x,v\right\rangle)$.

Since $z_{k,\mathbf{v}}$ is known to be an eigenfunction of $T_{\varepsilon}$,
we must have

$\xi_{k}=\frac{T_{\varepsilon}z_{k,\mathbf{v}}(\mathbf{v})}{z_{k,\mathbf{v}}(\mathbf{v})}=\frac{G_{k}^{(1/2)}(1-\varepsilon)}{G_{k}^{(1/2)}(1)}=G_{k}^{(1/2)}(1-\varepsilon).$

To bound this, recall the identity Equation 6.2 which gives

$\frac{d}{dx}G_{k}^{(1/2)}(x)=G_{k-1}^{(3/2)}(x).$

By the Mean Value Theorem, along with Equation 6.5 this gives

$|G_{k}^{(1/2)}(1)-G_{k}^{(1/2)}(1-\varepsilon)|\leq\varepsilon\cdot\sup_{x}|\frac{d}{dx}G_{k}^{(1/2)}(x)|=\varepsilon\sup_{x}|G_{k-1}^{(3/2)}(x)|\leq\varepsilon
G_{k-1}^{(3/2)}(1)=\varepsilon\cdot\frac{k(k+1)}{2}.$

Therefore,

$|1-\xi_{k}|=|G_{k}^{(1/2)}(1)-G_{k}^{(1/2)}(1-\varepsilon)|\leq\varepsilon
k(k+1)=\frac{\varepsilon k(k+1)}{2}\leq\varepsilon k^{2}.$

Finally, recall that $|G_{k}^{(1/2)}(x)|$ attains it maximum on $[-1,1]$ at
$x=1.$ So,

$|1-\xi_{k}|=|G_{k}^{(1/2)}(1)-G_{k}^{(1/2)}(1-\varepsilon)|\leq|G_{k}^{(1/2)}(1)|+|G_{k}^{(1/2)}(1-\varepsilon)|\leq
2|G_{k}^{(1/2)}(1)|=2.$

∎

This allows us to bound the operator norm of $R-T_{\varepsilon}R$ which we
will use in the next section.

######  Proposition 6.9.

The operator norm of $R-T_{\varepsilon}R$ satisfies the bound

$\|R-T_{\varepsilon}R\|_{L^{2}\rightarrow L^{2}}\leq 2\varepsilon^{1/4}.$

###### Proof.

Both $R$ and $T_{\varepsilon}$ commute with rotations, and hence are
diagonalized by the spherical harmonics. The operator norm of
$R-T_{\varepsilon}R$ is bounded by its largest magnitude eigenvalue. The
eigenvalue of $R-T_{\varepsilon}R$ on the degree $k$ spherical harmonics is
$\mu_{k}(1-\xi_{k})$, which by Proposition 6.7 and Proposition 6.8 is bounded
in magnitude by

$\min(\varepsilon k^{2},2)k^{-1/2}=\min(\varepsilon
k^{3/2},2k^{-1/2})\leq(\varepsilon k^{3/2})^{1/4}(2k^{-1/2})^{3/4}\leq
2\varepsilon^{1/4}.$

∎

####  6.4.2 A Discrepancy Bound for 3D Inner Product

We define two distributions $\mathcal{D}_{0}$ and $\mathcal{D}_{\varepsilon}$
on $\mathbb{S}^{2}\times\mathbb{S}^{2}$ that we we will show are hard to
distinguish with low communication. We let $\mathcal{D}_{0}$ be the
rotationally invariant distribution over pairs of orthogonal vectors. To
describe $\mathcal{D}_{\varepsilon}$ we give the procedure for taking a
sample. First sample $(v,w_{0})$ from $\mathcal{D}_{0}$. Then sample $w$
uniformly from $\\{x:\left\langle x,w_{0}\right\rangle=1-\varepsilon\\}.$ The
pair $(v,w)$ is a sample from $\mathcal{D}_{\varepsilon}.$

To continue proving our lower bound, we recall the connection between
communication protocols and rectangles. If the universe for Alice’s and Bob’s
inputs is $\mathcal{X}$ and $\mathcal{Y}$ then a communication protocol using
$b$ bits of communication partitions $\mathcal{X}\times\mathcal{Y}$ into at
most $2^{b}$ combinatorial rectangles, i.e. sets of the form $A\times B$ where
$A\subset\mathcal{X}$ and $B\subseteq\mathcal{Y}.$ The information that Alice
and Bob learn from running the protocol is precisely the identity of the
rectangle that their (joint) input lies in. Randomized protocols with public
randomness can simply be thought of as samples from the space of deterministic
protocols — Alice and Bob still learn that their input lies in some rectangle.
For more details on the basic setup for communication lower bounds, we refer
the reader to [Rou+16].

One specific approach for showing a communication lower is a so-called
discrepancy bound over rectangles. To apply the technique, one chooses two
distributions $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ over inputs and then
shows for all $A\subset\mathcal{X}$ and $B\subseteq\mathcal{Y}$ the
probability of an input landing in $A\times B$ is roughly the same under both
distributions:

$|\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{0}}((x,y)\in
A\times
B)-\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{1}}((\mathbf{x},\mathbf{y})\in
A\times B))|\leq\alpha.$

It is a standard fact that a discrepancy bound of the form above, implies that
distinguishing $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ with constant advantage
requires $\Omega(\log(1/\alpha))$ communication. The proof is simple: For a
fixed deterministic protocol using at most $N$ bits of communication, let
$\tilde{\mathcal{D}}_{i}$ be the distribution over rectangles corresponding to
samples from $\tilde{\mathcal{D}}_{i}$. Each rectangle contributes at most
$\alpha$ to the total variation distance between $\tilde{\mathcal{D}}_{0}$ and
$\tilde{\mathcal{D}}_{1}$. There are at most $2^{N}$ rectangles, and so the
total variation distance between the distributions is at most
$2^{N}\cdot\alpha.$ The extension to randomized protocols is via Yao’s minimax
principle.

This discrepancy lower bound technique will give our lower bound for constant
$d$ after the following proposition. For large $d$, we will need to bootstrap
our rectangle lower bound to an information lower bound. This is reminiscent
of the main result in [BW16], however we will need a slightly stronger version
of this lower bound, specialized to our setting, which doesn’t seem to follow
from their result. We will therefore ultimately use the discrepancy lower
bound in a somewhat different way from what is typical.

######  Proposition 6.10.

Let $S,T\subset\mathbb{S}^{2}$ be measurable sets. The following discrepancy
bound holds:

$|\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{0}}\left((\mathbf{x},\mathbf{y})\in
S\times
T\right)-\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{\varepsilon}}\left((\mathbf{x},\mathbf{y})\in
S\times T\right)|\leq 2\varepsilon^{1/4}.$

###### Proof.

We first rewrite these probabilities in terms of $R$ and $T_{\varepsilon}.$
Let $\chi_{S}$ and $\chi_{T}$ be the characteristic functions of $S$ and $T$
respectively. We have

$\displaystyle\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{0}}((\mathbf{x},\mathbf{y})\in
S\times T)$
$\displaystyle=\int_{\mathbf{x}\in\mathbb{S}^{3}}\int_{\mathbf{y}\in
x^{\perp}}\chi_{S}(\mathbf{x})\chi_{T}(\mathbf{y})d\sigma_{\mathbf{x}^{\perp}}(\mathbf{y})d\sigma(\mathbf{x})$
$\displaystyle=\int_{\mathbf{x}\in\mathbb{S}^{3}}\chi_{S}(\mathbf{x})\int_{\mathbf{y}\in\mathbf{x}^{\perp}}\chi_{T}(\mathbf{y})d\sigma_{\mathbf{x}^{\perp}}(\mathbf{y})d\sigma(\mathbf{x})$
$\displaystyle=\int_{\mathbf{x}\in\mathbb{S}^{3}}\chi_{S}(\mathbf{x})(R\chi_{T})(\mathbf{x})$
$\displaystyle=\left\langle R\chi_{T},\chi_{S}\right\rangle_{L^{2}}.$

Similarly

$\operatorname{Pr\/}_{(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{\varepsilon}}\left((\mathbf{x},\mathbf{y})\in
S\times T\right)=\left\langle
T_{\varepsilon}R\chi_{T},\chi_{S}\right\rangle_{L^{2}}.$

By Cauchy-Schwarz along with Proposition 6.9 above,

$|\left\langle(R-T_{\varepsilon}R)\chi_{S},\chi_{T}\right\rangle_{L^{2}}|\leq
2\varepsilon^{1/4}\|\chi_{S}\|_{L_{2}}\|\chi_{T}\|_{L_{2}}\leq
2\varepsilon^{1/4},$

since $\|\chi_{S}\|_{L_{2}}$ and $\|\chi_{T}\|_{L_{2}}$ are both at most $1.$
∎

######  Remark 6.11.

The above argument only applies in dimension $3$ and higher. When $d=2$,
$\mu_{k}$ does not decay with $k$ and so we can not bound the $\min$ above
uniformly in $k$. This corresponds to the fact that the Radon transform is not
smoothing on $\mathbb{S}^{1}.$ Indeed for a function on $\mathbb{S}^{1}$ which
is symmetric about the origin, the Radon transform just performs a $90$ degree
rotation.

The following Proposition simply checks that samples
$(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{\varepsilon}$ are likely to have
inner product $\Omega(\varepsilon).$

######  Proposition 6.12.

Let $(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{\varepsilon}.$ With probability
at least $0.95$,
$|\left\langle\mathbf{v},\mathbf{w}\right\rangle|\geq\varepsilon/20$.

###### Proof.

By symmetry, we may assume that $\mathbf{v}=[1,0,0]$ and
$\mathbf{w}_{0}=[0,0,1]$ where $\mathbf{w}_{0}$ is as in the definition of
$\mathcal{D}_{\varepsilon}$ above. Let $\Pi$ be the projection onto the
$xy$-plane. Then
$\left\langle\mathbf{w},\mathbf{v}\right\rangle=\left\langle\Pi\mathbf{w},\mathbf{v}\right\rangle$.
Note that

$\|\Pi\mathbf{w}\|=\sqrt{1-\left\langle\mathbf{w},\mathbf{w}_{0}\right\rangle^{2}}=\sqrt{2\varepsilon-\varepsilon^{2}}.$

Letting $\theta$ be the angle that $\Pi w$ makes $\mathbf{v}$, we have

$|\left\langle\mathbf{v},\mathbf{w}\right\rangle|=\sqrt{2\varepsilon-\varepsilon^{2}}|\cos\theta|\geq\sqrt{\varepsilon}|\cos\theta|\geq\varepsilon|\cos\theta|.$

Note that $\theta$ is distributed uniformly over the unit circle, so with
probability $0.95$, $|\cos\theta|\geq\frac{1}{20}.$ ∎

####  6.4.3 Upgrading to Higher Dimensions

As discussed above, since we proved a discrepancy bound over rectangles,
previous work [BW16] immediately implies an information complexity lower bound
for the $3$-dimensional version of Problem 6.1. We will boost this result to
$d$ dimensions using a direct-sum type result from [BJKS04] by viewing a $d$
dimensional vector as a concatenation of $d/3$ $3$-dimension vectors. To
obtain a direct sum result in our setting, we need the information lower bound
on the input distribution $\mathcal{D}_{0}$. Our next goal is to obtain the
necessary information lower bound for public coin protocols. Then we will
borrow a “reverse-Newman” result to upgrade to an information lower bound for
private-coin protocols.

We recall some basic definitions. Given a protocol $\Pi$ depending on the
inputs and public randomness $R$, and an input distribution $\mathcal{D}$, the
(internal) information cost of the protocol is

$\text{IC}_{\mathcal{D}}(\Pi)=I(\Pi;\mathbf{x}|\mathbf{y},R)+I(\Pi;\mathbf{y}|\mathbf{x},R)$

where $(\mathbf{x},\mathbf{y})\sim\mathcal{D}.$ In other words this is the
amount that the players learn about each others’ inputs.

Below we will show that any protocol run on our input distribution
$\mathcal{D}_{0}$ must either consist mostly of large rectangles, or have high
internal information cost. This will be in tension with our discrepancy bound
above, which shows that having too many large rectangles is unhelpful.

In the proof of the next proposition we will use the following technical fact.

######  Claim 6.13.

Assign the natural rotationally invariant probability measure $\mu$ to sets of
equators through the north pole. Let $T$ be a measurable set of equators, and
let S be a measurable subset of $\mathbb{S}^{2}$. Suppose that each element of
$T$ intersects $S$ in a set of measure at least $\alpha$, with respect to the
rotationally invariant $1$-dimensional probability measure $\sigma_{1}$ along
equators. Let $\sigma_{2}$ be the spherical probability measure. Then
$\sigma_{2}(S)\geq 4\mu(T)\alpha^{2}$.

###### Proof.

Recall the well-known fact that the map $F$ given in cylindrical coordinates
by

$(r,\theta,z)\mapsto\left(\theta,z\right)$

from $\mathbb{S}^{2}$ to $[0,2\pi]\times[0,1]$ (equipped with Lebesgue
measure) is measure-preserving. Geometrically, $F$ projects the sphere
outwardly onto a circumscribing cylinder, and then unfolds this cylinder into
a rectangle. Note that $F$ maps great semi-circles through the north pole and
south pole onto vertical lines of the form $\\{\theta\\}\times[0,1].$ We make
the following easy subclaim.

Subclaim. Let $f:[-\pi/2,\pi/2]\rightarrow[-1,1]$ be the projection
$\theta\mapsto\sin\theta$ from the half-circle onto the $y$-axis. Let $Y$ be a
measurable subset of $[-\pi/2,\pi/2]$. Then $\lambda_{1}(f(Y))\geq
8\sigma_{1}(Y)^{2},$ where $\lambda_{1}$ is the Lebesgue measure, and
$\sigma_{1}$ is the probability measure on $\mathbb{S}^{1}.$

Intuitively, this says that to minimize the measure of the projection we
should push the mass to the top and bottom of the semicircle. To see this more
rigorously, first suppose that $Y\subseteq[0,\pi/2].$ Then we have

$\lambda_{1}(f(Y))=2\pi\int|\cos\theta|\chi_{Y}(\theta)d\sigma_{1}(\theta)\geq
2\pi\int_{\pi/2-2\pi\sigma_{1}(Y)}^{\pi/2}\cos\theta
d\sigma_{1}(\theta)=\int_{\pi/2-2\pi\sigma_{1}(Y)}^{\pi/2}\cos\theta
d\lambda_{1}(\theta)$

since cosine is decreasing on $[0,\pi/2].$ The latter integral evaluates to

$(1-\cos(2\pi\sigma_{1}(Y)))\geq\frac{4}{\pi^{2}}(2\pi\sigma_{1}(Y))^{2}=16\sigma_{1}(Y)^{2}$

To finish off the subclaim, for $Y\subseteq[-\pi/2,\pi/2],$ partition $Y$ into
$Y_{1}$ and $Y_{2}$ where $Y_{1}\subseteq[0,\pi/2]$ and
$Y_{2}\subseteq[-\pi/2,0).$ Then

$\lambda_{1}(f(Y))=\lambda_{1}(f(Y_{1}))+\lambda_{1}(f(Y_{2}))\geq
16(\sigma_{1}(Y_{1})^{2}+\sigma_{1}(Y_{2})^{2})\geq
8(\sigma_{1}(Y_{1})+\sigma_{1}(Y_{2}))^{2}=8\sigma_{1}(Y)^{2}.$

Given the subclaim and the stated conditions, we see that $F(S)$ intersects at
least a $\frac{1}{2}\mu(T)\cdot 2\pi$ measure of vertical lines each in a set
of measure at least $\frac{1}{2}\cdot 8\alpha^{2}.$ The claim follows from
Fubini’s Theorem. ∎

######  Proposition 6.14.

Let $\mathcal{D}_{0}$ be the rotationally invariant distribution over pairs of
orthogonal vectors on $\mathbb{S}^{2}$, and consider a deterministic protocol
run on pairs $(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{0}$. Let $I$ be the
internal information cost of the protocol on this distribution. With
probability at least $0.4$, $(\mathbf{v},\mathbf{w})$ is in a rectangle of
measure at least $2^{-60I}$.

###### Proof.

Fix a deterministic protocol, and let $R=S_{A}\times S_{B}$ be the
combinatorial rectangle that $(\mathbf{v},\mathbf{w})\sim\mathcal{D}$ lies in.

Let $E_{1}$ be the event that $\sigma_{1}(\mathbf{v}^{\perp}\cap S_{B})$ is at
least $2^{-10I}$ where $\sigma_{1}$ is the natural probability measure over
$\mathbf{v}^{\perp}\cap\mathbb{S}^{2}$. (In other words the event that the
equator orthogonal to Alice’s vector has large intersection with $S_{B}$.)
Note that $E_{1}$ occurs with probability at least $0.9$ (otherwise the
information cost of the protocol would be larger than $I$).

Let $E_{2}$ be the event

$\sigma_{1}\left(\\{\mathbf{u}\in\mathbf{v}^{\perp}\cap
S_{B}:\sigma_{1}(\mathbf{u}^{\perp}\cap S_{A})\geq
2^{-10I}\\}\right)\geq\frac{1}{2}\sigma_{1}(\mathbf{v}^{\perp}\cap S_{B}).$

In other words $E_{2}$ is the event that for a good fraction of
$\mathbf{u}\in(\mathbf{v}^{\perp}\cap S_{B})$, the orthogonal equator to
$\mathbf{u}$ has large intersection with $S_{A}$.

By the same reasoning as above,

$\operatorname{Pr\/}(\sigma_{1}(\mathbf{w}^{\perp}\cap S_{A})\geq
2^{-10I})\geq 0.9.$

For fixed $\mathbf{v}^{\prime}$ and $R^{\prime}=S_{A}^{\prime}\times
S_{B}^{\prime}$, let

$P_{\mathbf{v}^{\prime},R^{\prime}}=P_{\mathbf{w}}\left(\sigma_{1}(\mathbf{w}^{\perp}\cap
S_{A})\geq
2^{-10I}\big{|}\,\mathbf{v}=\mathbf{v}^{\prime}\,\,\text{and}\,\,(\mathbf{v}^{\prime},\mathbf{w})\in
R^{\prime}\right).$

By the statement two lines above, with probability at least $0.8$ over
$\mathbf{v}$ and $R$, $P_{\mathbf{v},R}\geq 1/2$. Also, conditioned on
$\\{\mathbf{v}=\mathbf{v}^{\prime},\text{and}\,(\mathbf{v}^{\prime},\mathbf{w})\in
R^{\prime}\\}$, $\mathbf{w}$ is distributed uniformly over
$(\mathbf{v}^{\prime})^{\perp}\cap S_{B}^{\prime}$. Conditioned on
$P_{\mathbf{v},R}\geq 1/2$ we have

$\displaystyle\operatorname{Pr\/}_{\mathbf{w}\sim\text{Unif}(R\cap\mathbf{v}^{\perp})}\left(\sigma_{1}(\mathbf{w}^{\perp}\cap
S_{A})\geq 2^{-10I}\right)\geq 1/2,$

which is equivalent to $E_{2}.$

Thus with probability at least $0.7$, events $E_{1}$ and $E_{2}$ hold
simultaneously. When this happens, $\mathbf{v}^{\perp}\cap S_{B}$ is large,
and at least half the points in that set have orthogonal equators that have
large overlap with $S_{A}$. So conditioned on $E_{1}$ and $E_{2}$, there is a
subset $U$ of $v^{\perp}\cap S_{B}$, such that $m(U)\geq 0.5\cdot 2^{-10I}$
and $\sigma_{1}(\mathbf{u}^{\perp}\cap S_{A})\geq 2^{-10I}$ for all
$\mathbf{u}$ in $U$.

We have found that most of the time $S_{A}$ has large overlap with a large
measure of the great circles passing through a fixed point. This means that
$S_{A}$ is typically large, as formalized by Claim 6.13. Applying the claim to
our situation gives

$m_{2}(S_{A})\geq\frac{1}{2}\cdot 4(0.5\cdot 2^{-10I})(2^{-10I})^{2}\geq
2^{-30I},$

with probability at least $0.7.$ (The extra factor of $1/2$ is because
antipodal points correspond to the same equator.) Symmetrically, the same
bound applies to $S_{B}$ and a union bound finishes the argument. ∎

The above argument is sufficient to get a lower bound for public coin
protocols, however we will need the analogous fact for private coin protocols.
To do this we use a “reverse-Newman” type result from [BG14] which gives a
slight improvement over an earlier result from [BBKLSV16]. This allows us to
replace our public-coin lower bound with a private-coin lower bound, albeit at
the cost of restricting the number of rounds.

######  Lemma 6.15.

Let $\mathcal{D}_{0}$ and $\mathcal{D}_{\varepsilon}$ be as above. Let
$\Pi=\Pi(x,y,R)$ be the transcript of a public coin protocol with coins $R$,
that distinguishes $\mathcal{D}_{0}$ from $\mathcal{D}_{\varepsilon}$ with
probability at least $0.9.$ Then when $(\mathbf{x},\mathbf{y})\sim D_{0}$ we
have
$I(\Pi;\mathbf{y}|\mathbf{x},R)+I(\Pi;\mathbf{x}|\mathbf{y},R)\geq\frac{1}{60}\log\frac{1}{15\varepsilon^{1/4}}.$

###### Proof.

We are considering public-coin protocols, so by Yao’s principle it suffices to
consider deterministic protocols. We have an $2\varepsilon^{1/4}$ discrepancy
bound on rectangles for $\mathcal{D}_{0}$ and $\mathcal{D}_{\varepsilon}$ by
Proposition 6.10. This implies that a protocol that succeed with probability
$0.9$ must have have probability at least $0.75$ of $(\mathbf{v},\mathbf{w})$
lying in rectangle of measure at most $15\varepsilon^{1/4}$, when
$(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{0}$.

To see this, say that a rectangle is small if it has measure at most
$15\varepsilon^{1/4}$ and large otherwise. Suppose that a sample
$(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{0}$ has probability at least $0.25$
of lying in a large rectangle. There are at most $1/(15\varepsilon^{1/4})$
large rectangles, so by the discrepancy bound, the probability that
$(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{\varepsilon}$ lies in a large
rectangle is at least
$0.25-1/(15\varepsilon^{1/4})\cdot(2\varepsilon^{1/4})=7/60.$ Now consider the
distributions $\tilde{\mathcal{D}}_{0}$ and
$\tilde{\mathcal{D}}_{\varepsilon}$ over rectangles induced by
$\mathcal{D}_{0}$ and $\mathcal{D}_{\varepsilon}.$ We bound their total
variation distance. Summing the absolute differences in probabilities for
$\tilde{\mathcal{D}}_{0}$ and $\tilde{\mathcal{D}}_{\varepsilon}$ over large
rectangles the gives at most
$1/(15\varepsilon^{1/4})\cdot(2\varepsilon^{1/4})=2/15$ The corresponding sum
over small rectangles is at most $(1-0.25)+(1-7/60)\leq 1.64.$ So the total
variation distance between $\tilde{\mathcal{D}}_{0}$ and
$\tilde{\mathcal{D}}_{\varepsilon}$ is at most $\frac{1}{2}(2/15+1.64)<0.9,$
which contradicts the protocol succeeding with $0.9$ probability.

Combining with Proposition 6.14 (and noting that $0.4+0.75>1$), we see that a
correct protocol with information cost $I$ on $\mathcal{D}$ must have
$2^{-60I}\leq 15\varepsilon^{1/4}$, from which the claim follows. ∎

As an easy consequence, we can construct a distribution
$\mathcal{D}_{\varepsilon}^{\prime}$ for which $\mathcal{D}_{0}$ and
$\mathcal{D}_{0}$ are hard to distinguish but where
$|\left\langle\mathbf{x},\mathbf{y}\right\rangle|\geq\varepsilon$ a.s. when
$(\mathbf{x},\mathbf{y})\sim\mathcal{D}_{\varepsilon}.$ This will be more
convenient below.

######  Proposition 6.16.

Define $\mathcal{D}_{\varepsilon}^{\prime}$ as the conditional distribution
$\mathcal{D}_{20\varepsilon}\bigg{|}\\{|\left\langle\mathbf{x},\mathbf{y}\right\rangle|\geq\varepsilon\\}.$
Let $\Pi=\Pi(\mathbf{x},\mathbf{y},R)$ be the transcript of a public coin
protocol with coins $R$, that correctly identifies $\mathcal{D}_{0}$ or
$\mathcal{D}_{\varepsilon}^{\prime}$ with probability at least $0.95.$ Then
when $(\mathbf{x},\mathbf{y})\sim D_{0}$ we have
$I(\Pi;\mathbf{y}|\mathbf{x},R)+I(\Pi;\mathbf{x}|\mathbf{y},R)\geq\frac{1}{60}\log\frac{1}{50\varepsilon^{1/4}}.$

###### Proof.

Suppose that we have a protocol that decides between $\mathcal{D}_{0}$ and
$\mathcal{D}_{\varepsilon}^{\prime}$ with probability $0.95.$ By Proposition
6.12 this protocol gives an algorithm to distinguish between $\mathcal{D}_{0}$
and $\mathcal{D}_{20\varepsilon}$ with probability at least $0.9$, since with
probability at least $0.95$ a sample $(\mathbf{x},\mathbf{y})$ from
$\mathcal{D}_{20\varepsilon}$ satisfies the condition
$|\left\langle\mathbf{x},\mathbf{y}\right\rangle|\geq\varepsilon.$ The claim
now follows from Lemma 6.15. ∎

We next state the version of the Reverse-Newman theorem that we use. This is
essentially Theorem 1.1 of [BG14] who states the result for single-round
protocols. [BBKLSV16] shows a similar (slightly weaker) result for one-round
protocols and then inductively generalizes to $r$-round protocols. The same
induction applies to the one-round protocol of [BG14].

######  Proposition 6.17.

An $r$-round private coin protocol with internal information cost $I$ on an
input distribution $\mu$ can be simulated by a public coin protocol with
information cost $I+O(r\log I).$

###### Proof.

Combine Theorem 1.1 of [BG14] with the inductive argument given in [BBKLSV16,
Section 3.2], replacing $c\log(2n\ell)$ with $\log I$. Note that by [BG14],
$\log I$ is an upper bound on the information revealed in each round $j$. This
is simply because the information revealed in round $j$ is bounded by the
total information revealed by the protocol, which we assume is $I.$ ∎

We also mention here a direct-sum technique due to [BJKS04] that we apply
below. The approach is to consider an “OR” of $d/3$ independent instances of
the three-dimensional inner product problem, and to show that a correct
protocol has high information cost on the input distribution
$\mathcal{D})^{d/3}$. The idea is that, given an instance of the three-
dimensional problem, Alice and Bob can then construct $d/3-1$ additional
instances consisting of pairs of orthogonal vectors thereby embedding their
single instance into a larger OR-instance. Moreover, their instance can be
inserted into any of the $d/3$ positions, ultimately leading to a $d/3$-factor
information cost increase for the OR-instance. To sample the additional pairs
of orthogonal vectors from $\mathcal{D}_{0}$ however, they need shared
information, namely one of the two vectors (then the other vector can be
sampled privately). So we actually need to argue that a correct protocol has
high external information cost on $\mathcal{D}_{0}$, when one of the two
vectors is revealed. This is simply the content of our previous lemma bounding
the internal information cost on $\mathcal{D}_{0}$.

####  6.4.4 Proof of Lemma 6.2

###### Proof of Lemma 6.2.

Our goal is to apply Theorem 5.6 of [BJKS04]. Actually, we will apply apply a
version of this theorem for protocols with at most $r$ rounds for which the
same proof applies.

We consider the following problem. Alice and Bob are given $d/3$ three-
dimension vectors $\mathbf{v}_{1}$,$\mathbf{v}_{2}$, $\ldots$,
$\mathbf{v}_{d/3}$ and
$\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{d/3}$. They must output $0$
if (a) $\left\langle\mathbf{v}_{i},\mathbf{w}_{i}\right\rangle=0$ for all $i$
and output $1$ if (b)
$|\left\langle\mathbf{v}_{i},\mathbf{w}_{i}\right\rangle|\geq\varepsilon$ for
exactly one $i.$ We show that this problem requires
$\Omega(d\log\frac{1}{\varepsilon})$ queries under the stated assumption on
the number of rounds. This will then immediately imply the lemma. To see this,
let $\mathbf{v}$ and $\mathbf{w}$ be the concatenations of the
$\mathbf{v}_{i}$’s and the $\mathbf{w}_{i}$’s. Then
$\mathbf{v}^{\prime}:=\frac{1}{\sqrt{d/3}}\mathbf{v}$ and
$\mathbf{w}^{\prime}:=\frac{1}{\sqrt{d/3}}w$ are unit vectors. In case (a),
$\left\langle\mathbf{v}^{\prime},\mathbf{w}^{\prime}\right\rangle=0$ while in
case (b),
$|\left\langle\mathbf{v}^{\prime},\mathbf{w}^{\prime}\right\rangle|\geq\frac{\varepsilon}{d/3}\geq\frac{\varepsilon}{d}.$
So a protocol to solve Problem 6.1 could in particular distinguish between
case (a) and case (b).

We use the notation of Theorem 5.6 in [BJKS04]. Let $f$ be the boolean
function above that Alice and Bob wish to compute. Let
$h:\mathbb{R}^{3}\times\mathbb{R}^{3}\rightarrow\\{0,1\\}$ be the boolean
function which is $0$ precisely when inputs are orthogonal. In the language of
[BJKS04], $f$ is OR-decomposable with primitive $h$ meaning that

$f(\mathbf{v},\mathbf{w})=h(\mathbf{v}_{1},\mathbf{w}_{1})\vee\ldots\vee
h(\mathbf{v}_{d/3},\mathbf{w}_{d/3}).$

To apply Theorem 5.6 of [BJKS04] we define a mixture of product distributions
$\zeta$ as follows. Let $D=(a,\mathbf{x})$ be a uniformly random sample from
$\\{0,1\\}\times\mathbb{S}^{2}.$ Roughly, $\mathbf{x}$ reveals the vector for
player $a.$ More formally, if $D=(0,\mathbf{x})$ for some $\mathbf{x}$, then
set $\mathbf{X}=\mathbf{x}$ and $\mathbf{Y}$ uniform over unit vectors
orthogonal to $\mathbf{x}.$ Similarly if $D=(1,\mathbf{x})$, then set
$\mathbf{Y}=\mathbf{x}$ and set $\mathbf{X}$ to uniform over unit vectors
orthogonal to $\mathbf{x}.$ Now let $\zeta$ be the distribution for which
$((\mathbf{X},\mathbf{Y}),D)$ is a sample from $\zeta.$

The distribution of inputs given by $\zeta^{d/3}$ is uniform over pairs of
orthogonal vectors in each coordinate, and hence in the language of [BJKS04],
this input distribution is a collapsing distribution for $f$999See [BJKS04]
for a detailed definition. Roughly this means that if we replace the
coordinate $i$ inputs from this distribution with a pair
$(\mathbf{v}_{i}^{\prime},\mathbf{w}_{i}^{\prime})$, then
$f(\mathbf{v},\mathbf{w})=h(\mathbf{v}_{i},\mathbf{w}_{i}).$. It then follows
from (the proof of101010The only difference is that we impose a restriction on
the number of rounds. But [BJKS04] proves their result by a simulation
argument that preserves the number of rounds, so the proof is unchanged.)
Theorem 5.6 in [BJKS04] that

$\text{CIC}_{\zeta^{d/3},\delta,r}(f)\geq\frac{d}{3}\text{CIC}_{\zeta,\delta,r}(h)$

where we define $CIC_{\zeta^{d/3},\delta,r}(f)$ to be the information
complexity of $f$ on the input distribution $\eta$ for $r$-round protocols
that succeed with probability at least $1-\delta$ on all valid inputs, given
that $D$ is observed. In other words $CIC_{\zeta^{d/3},\delta,r}(f)$ is the
minimum of $I(\mathbf{X},\mathbf{Y};\Pi|D)$ over all (private-coin) $r$-round
protocols with success probability at least $1-\delta$, when
$(D,(\mathbf{X},\mathbf{Y}))\sim\zeta.$

By our definition of $\zeta$, $D$ reveals one of the two vectors at random. So

$\text{CIC}_{\zeta,\delta,r}(h)=\min_{\Pi}\left(\frac{1}{2}I(\mathbf{X};\Pi|\mathbf{Y})+\frac{1}{2}I(\mathbf{Y};\Pi|\mathbf{X})\right),$

where the minimum is over $r$-round protocols that fail with probability at
most $\delta$. This latter quantity is simply half of the (internal)
information complexity for $r$-round protocols that solve the $3$-dimensional
version of Problem 6.1. Any public coin protocol that solves this problem with
at least $0.95$ probability can in particular distinguish between
$\mathcal{D}_{0}$ and $\mathcal{D}_{\varepsilon}^{\prime}$ with $0.95$
probability, and thus by Proposition 6.16, has information complexity at least
$\Omega(\log\frac{1}{\varepsilon})$ on $\mathcal{D}_{0}.$

Then by Proposition 6.17 any $r$-round private coin protocol with the same
parameters requires at least $\Omega(\log\frac{1}{\varepsilon})$ information
cost when $r\leq c\log(1/\varepsilon)/\log\log(1/\varepsilon)$ for an absolute
constant $c.$

We have therefore shown that $\text{CIC}_{\zeta,\delta,r}\geq
c\log\frac{1}{\varepsilon}$. The lemma follows from noting that communication
cost is at least information cost. ∎

####  6.4.5 From Two Players to $s$ Players

Our next task is to bootstrap our two-player lower bound to the $s$-player
version. We start with the following simple fact which follows from
symmetrizing our hard distributions. In this section we update our notation
for the distributions to refer to distributions on $\mathbb{R}^{d}.$

######  Proposition 6.18.

Let $\mathcal{D}_{0}$ be the rotationally invariant distribution over pairs of
orthogonal vectors in $\mathbb{R}^{d}.$ There is another distribution
$\mathcal{D}_{1}$ over pairs of vectors $(\mathbf{v},\mathbf{w})$ such that
for $(\mathbf{v},\mathbf{w})\sim\mathcal{D}_{1}$ we have
$|\left\langle\mathbf{v},\mathbf{w}\right\rangle|\geq\frac{\varepsilon}{\sqrt{d}}$
a.s. and distinguishing $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ with
probability at least $0.9$ requires $\Omega(d\log\frac{1}{\varepsilon})$
communication for any protocol with at most
$C\log\frac{1}{\varepsilon}/\log\log\frac{1}{\varepsilon}$ rounds.

###### Proof.

Let $\mathbf{U}$ be a (Haar-)random orthogonal transformation, and let
$\tilde{\mathcal{D}}_{0}$ and $\tilde{\mathcal{D}}_{1}$ be the hard instance
given by Lemma 6.2. Then symmetrize by setting
$\mathcal{D}_{i}=\mathbf{U}\tilde{\mathcal{D}}_{i}$ for $i=1,2.$ Note that
symmetrizing does not make the problem easier, as the players could accomplish
this on their own using shared randomness, and no communication. ∎

######  Lemma 6.19.

Suppose that there is a protocol for Problem 1.17 that succeeds with
probability at least $1-\delta$, uses at most $r$ rounds of communication
between the coordinator and each server, and uses total communication at most
$M$. Then there is an $r$-round protocol to solve the two player Problem 6.1
with probability at least $0.95-\delta$ and total communication $20M/s.$

###### Proof.

Let $\mathcal{P}$ be a protocol that solves the $s$-player game with the
parameters given above. Now we define $s$ two-player protocols
$\mathcal{P}_{1},\ldots\mathcal{P}_{s}$ that distinguish between
$\mathcal{D}_{0}$ and $\mathcal{D}_{1}.$

For protocol $\mathcal{P}_{k}$, Alice first samples $s-1$ i.i.d. vectors
$\mathbf{w}_{1},\ldots,\mathbf{w}_{k-1},\mathbf{w}_{k+1},\ldots,\mathbf{w}_{s}$
(one for each index other than $k$) orthogonal to her vector $\mathbf{v}$ from
the distribution that is invariant under rotations fixing $\mathbf{v}.$ Then
Alice simulates $s-1$ servers indexed by $i\in[s]\setminus\\{k\\}$ with server
$i$ holding $\mathbf{w}_{i}.$ Finally server $k$ is simply taken to be Bob.
Then the $s$-player protocol $\mathcal{P}$ is run on these servers. Note that
Alice can simulate communication with server $i\neq k$ using no communication,
and can simulate communication with server $k$ by exchanging messages with
Bob. By correctness of $\mathcal{P}$ each protocol $\mathcal{P}_{i}$ correctly
distinguishes between $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ with probability
at least $1-\delta.$

Suppose that Alice and Bob’s input comes from $\mathcal{D}_{0}.$ Conditioned
on $\mathbf{v}$, the random vectors
$\mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{s}$ all have the same
distribution. Thus there must be a $j$ such that $\mathcal{P}_{j}$ uses at
most $20M/s$ communication with probability at least $0.95$. To see this, let
$E_{i}$ be the expected communication of protocol $\mathcal{P}$ between the
coordinator and server $i$, when $v$ is uniform over the sphere, and
$\mathbf{w}_{1},\ldots,\mathbf{w}_{s}$ are drawn i.i.d. uniformly from
$\mathbf{v}^{\perp}.$ By linearity of expectation, $E_{1}+\cdots+E_{s}\leq M$,
so $E_{j}\leq M/s$ for some $j$. Then by Markov’s inequality $\mathcal{P}_{j}$
uses at most $20M/s$ communication with probability at least $0.9.$

We have constructed a two-player protocol $\mathcal{P}_{j}$ that is correct
and uses at most $10M/s$ communication on input distribution $\mathcal{D}_{0}$
with probability at least $0.9$. We use this to construct a protocol
$\mathcal{P}_{j}^{\prime}$ by terminating $\mathcal{P}_{j}$ early if
necessary. To run $\mathcal{P}_{j}^{\prime}$, Alice and Bob simply run
$\mathcal{P}_{j}$, while keeping track of the total communication used. If
sending the next message of $\mathcal{P}_{j}$ would put the total
communication above $10M/s$, then that player simply terminates the protocol
and outputs $1$. Now we argue that $\mathcal{P}_{j}^{\prime}$ is correct. On
the input distribution $\mathcal{D}_{0}$, $\mathcal{P}_{j}^{\prime}$ fails if
either $\mathcal{P}_{j}$ is terminated early, or $\mathcal{P}_{j}$ is
incorrect. By a union bound $\mathcal{P}_{j}$ fails on $\mathcal{D}_{0}$ with
probability at most $0.05+\delta.$ On $\mathcal{D}_{1}$,
$\mathcal{P}_{j}^{\prime}$ only fails if $\mathcal{P}_{j}$ fails which occurs
with probability at most $\delta.$ So $\mathcal{P}_{j}^{\prime}$ distinguishes
$\mathcal{D}_{0}$ from $\mathcal{D}_{1}$ with probability at least
$0.95-\delta.$

∎

######  Remark 6.20.

For constant $d$, this argument gives a communication lower bound of
$\Omega(s\log\frac{1}{\varepsilon})$ for solving Problem 1.17 with constant
probability. In this case we do not need to restrict the number of rounds
since Proposition 6.10 immediately implies an
$\Omega(\log\frac{1}{\varepsilon})$ lower bound for Problem 6.1 when $d=3$ (or
in fact when $d$ is any fixed integer greater than $2$).

Proof of Theorem 1.18. For two-player protocols with at most
$r=C\log\frac{1}{\varepsilon}/\log\log\frac{1}{\varepsilon}$ rounds we have a
communication lower bound of $\Omega(d\log\frac{1}{\varepsilon}$ from
Proposition 6.18 for distinguishing $mathcal{D}_{0}$ and $\mathcal{D}_{1}.$
Thus in the setup of Lemma 6.19 we must have
$20M/s\geq\Omega(d\log\frac{1}{\varepsilon})$ which implies that
$M\geq\Omega(sd\log\frac{1}{\varepsilon})$ as desired.

###  6.5 High-Precision Lower Bound

In this section we show the follow result for obtaining a solution to high
additive error precision. See 1.19

Our main observation is that a Gaussian least-squares problem is somewhat
sensitive to each individual row.

######  Proposition 6.21.

Consider a communication game between Alice and Bob, where Alice is given a
uniformly random vector $\mathbf{v}$ on the sphere $\mathbb{S}^{d-1}.$ Bob
would like to produce a vector $\hat{\mathbf{v}}$ with
$\|\mathbf{v}-\hat{\mathbf{v}}\|\leq\varepsilon.$

Any protocol that succeeds at this game with probability at least $0.1$ must
use at least $\Omega(d\log\frac{1}{\varepsilon})$ communication.

###### Proof.

It is a standard fact that there exists a $3\varepsilon$ packing of
$\mathbb{S}^{d-1}$ of size $N:=(c/\varepsilon)^{d-1}$ for an absolute constant
$c$. This follows from a volumetric argument for example (see e.g. [Ver18]).

Now consider the following game. Alice is given a random integer $i$ in
$\\{1,\ldots N\\}$ which Bob must learn with at least $0.1$ probability. This
game clearly requires $\Omega(\log N)$ communication. To see this, note that
it suffices to consider deterministic protocols by Yao’s principle. Any
deterministic protocol sending $m$ bits, forces Bob into choosing one of at
most $2^{m}$ outputs, so $2^{m}/N\geq 0.1$ which means that $m\geq\log(0.1N).$

On the other this game reduces to the game stated in the proposition. Alice
identifies the numbers $1,\ldots,N$ with points
$\mathbf{x}_{1},\ldots,\mathbf{x}_{N}$ in the packing. Given an index $i$,
Alice chooses the point $\mathbf{x}_{i}.$ Using shared randomness Alice and
Bob choose a Haar-random orthogonal transformation $U$. Then
$\mathbf{U}\mathbf{x}_{i}$ is uniform over $\mathbb{S}^{d-1}$ so Alice and Bob
may run the a protocol for the above problem, allowing Bob to find
$\hat{\mathbf{v}}$ with $\|\hat{\mathbf{v}}-Ux_{i}\|\leq\varepsilon.$ Then Bob
computes $\hat{x}_{i}=\mathbf{U}^{-1}\hat{\mathbf{v}}$ which satisfies
$\|\mathbf{x}_{i}-\hat{\mathbf{x}}_{i}\|\leq\varepsilon.$ Since
$\mathbf{x}_{1},\ldots,\mathbf{x}_{N}$ was a $3\varepsilon$ packing, this
allows Bob to recover $\mathbf{x}_{i}$ and hence $i$ as desired. The
proposition follows. ∎

We will show the following technical communication result and then apply it.

######  Lemma 6.22.

Consider a communication game between Alice and Bob where Alice is given a
(rotationally-invariant) random vector $\mathbf{v}\in\mathbb{R}^{d}$ with
$\|\mathbf{v}\|=\alpha\leq 1$, and both players see a matrix
$\mathbf{M}\in\mathbb{R}^{d\times d}$ and a vector
$\mathbf{w}\in\mathbb{R}^{d}.$ Suppose further that
$\mathbf{I}\preceq\mathbf{M}\preceq c\mathbf{I}$ for an absolute constant $c$
and that $\|\mathbf{w}\|\geq 1$. Define

$F(\mathbf{x})=F_{M,\mathbf{w}}(\mathbf{x})=\frac{\mathbf{x}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}^{\top}\mathbf{M}\mathbf{x}}\mathbf{M}\mathbf{x}.$

Alice would like to send a message to Bob from which Bob can produce
$\mathbf{y}\in\mathbb{R}^{d}$ with
$\|F(\mathbf{v})-\mathbf{y}\|\leq\varepsilon.$

Any communication protocol that succeeds with probability at least $0.9$
requires at least $\Omega(d\log\frac{\alpha}{\varepsilon d})$ communication.

###### Proof.

Let $S$ be the set of points $\mathbf{x}$ in $\alpha\mathbb{S}^{d-1}$ with
$\mathbf{x}^{\top}\mathbf{M}\mathbf{w}\geq\frac{\alpha}{10\sqrt{d}}$. Note
that

$\operatorname{Pr\/}(\mathbf{x}\in
S)=\frac{1}{2}\left(1-\operatorname{Pr\/}\left(|\mathbf{x}^{\top}\mathbf{M}\mathbf{w}|\leq\frac{\alpha}{10\sqrt{d}}\right)\right)\geq\frac{1}{4}.$

To see this, note that $\|\mathbf{M}\mathbf{w}\|\geq 1.$ Then by rotational
invariance

$\operatorname{Pr\/}\left(|\mathbf{s}^{\top}\mathbf{M}\mathbf{w}|\leq\frac{\alpha}{10\sqrt{d}}\right)\leq\operatorname{Pr\/}\left(|\mathbf{x}^{\top}\mathbf{e}_{1}|\leq\frac{\alpha}{10\sqrt{d}}\right)=\operatorname{Pr\/}\left(\frac{1}{\alpha^{2}}|\mathbf{x}^{\top}\mathbf{e}_{1}|^{2}\leq\frac{1}{100d}\right).$

The quantity $\frac{1}{\alpha^{2}}|\mathbf{x}^{\top}\mathbf{e}_{1}|^{2}$ is
distributed as $g_{1}^{2}/(g_{1}^{2}+\ldots+g_{d}^{2})$ where each $g_{i}$ is
a standard normal. Note that $g_{1}^{2}>1/10$ with probability at least $3/4.$
Also $g_{1}^{2}+\ldots+g_{d}^{2}\leq 2d$ with probability at least
$1-\exp(-cd)$ by Bernstein’s inequality for example (see [Ver18] for example).
So when $d$ is a large enough constant, the probability above is at most
$1/2.$ (The constants here are of course not close to optimal.)

For all $\mathbf{x}\in S$ we have

$\frac{\mathbf{x}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}^{\top}\mathbf{M}\mathbf{x}}\geq\frac{\alpha}{20\sqrt{d}(1+2\alpha^{2})}.$

Thus for $\mathbf{x}_{1},\mathbf{x}_{2}\in S$ we have

$\displaystyle\|F(\mathbf{x}_{1})-F(\mathbf{x}_{2})\|$
$\displaystyle=\|\frac{\mathbf{x}_{1}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}_{1}^{\top}\mathbf{M}\mathbf{x}_{1}}\mathbf{M}\mathbf{x}_{1}-\frac{\mathbf{x}_{2}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}_{2}^{\top}\mathbf{M}\mathbf{x}_{2}}\mathbf{M}\mathbf{x}_{2}\|$
$\displaystyle\geq\min\left(\frac{\mathbf{x}_{1}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}_{1}^{\top}\mathbf{M}\mathbf{x}_{1}},\frac{\mathbf{x}_{2}^{\top}\mathbf{M}\mathbf{w}}{1+\mathbf{x}_{2}^{\top}\mathbf{M}\mathbf{x}_{2}}\right)\|\mathbf{M}\mathbf{x}_{1}-\mathbf{M}\mathbf{x}_{2}\|$
$\displaystyle\geq\frac{\alpha}{10\sqrt{d}(1+C\alpha^{2})}\sigma_{\min}(M)\|\mathbf{x}_{1}-\mathbf{x}_{2}\|$
$\displaystyle\geq\frac{\alpha}{10\sqrt{d}(1+C\alpha^{2})}\|\mathbf{x}_{1}-\mathbf{x}_{2}\|.$
$\displaystyle:=\beta\|\mathbf{x}_{1}-\mathbf{x}_{2}\|$

Condition on $\mathbf{v}$ lying in $S$ which happens with at least $1/4$
probability. A protocol that solves the above communication problem allows Bob
to produce a vector $\mathbf{y}$ with
$\|F(\mathbf{v})-\mathbf{y}\|\leq\varepsilon.$ If $\hat{\mathbf{v}}$ is
another vector satisfying $\|F(\hat{\mathbf{v}})-\mathbf{y}\|\leq\varepsilon$,
then

$2\varepsilon\geq\|F(\mathbf{v})-F(\hat{\mathbf{v}})\|\geq\beta\|\mathbf{v}-\hat{\mathbf{v}}\|,$

so $\|\mathbf{v}-\hat{\mathbf{v}}\|\leq\frac{2\varepsilon}{\beta}.$

Thus with failure probability at most $\frac{3}{4}+\frac{1}{10}=0.85$ Bob can
produce a $\frac{2\varepsilon}{\beta}$ additive approximation
$\hat{\mathbf{v}}$ to Alice’s vector $\mathbf{v}$. However this latter
communication problem requires at least
$\Omega(d\log\frac{\beta}{\varepsilon})=\Omega(d\log\frac{\alpha}{\varepsilon
d})$ communication by Proposition 6.21.

∎

######  Proposition 6.23.

Consider the following communication game. Alice holds row $\mathbf{A}_{1}$ of
$\mathbf{A}$ which is uniform over $\alpha\mathbb{S}^{d-1}$ with
$\alpha=\sqrt{\frac{d}{s+d}}$. Bob holds $s-1$ independent rows
$\mathbf{A}_{2},\ldots,\mathbf{A}_{s}$, each with the same distribution as
Alice’s. Also $\mathbf{A}_{s+k}=\mathbf{e}_{k}$ for $k=1,\ldots,d.$ Set
$\mathbf{b}=\mathbf{e}_{s+1}$ so that
$\mathbf{A}^{\top}\mathbf{b}=\mathbf{e}_{1}.$ Alice and Bob would like to
compute $\hat{\mathbf{x}}$ with
$\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|\leq\varepsilon+\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|,$
with probability at least $0.95$. This communication game requires at least
$\Omega\left(d\log\frac{1}{\varepsilon(s+d)}\right)$ communication.

###### Proof.

First, observe that $\mathbf{A}$ is well-conditioned with high probability.
Indeed, with probability at least $\exp(-d)$ (which is at most $0.05$ for
$d\geq 3$), we have $I\leq\mathbf{A}^{\top}\mathbf{A}\leq cI$ for an absolute
constant $c.$ The first inequality always holds by construction of
$\mathbf{A}.$ The latter holds by standard concentration results for the top
singular value of a matrix with subgaussian rows (see, for example, [Ver18,
Section 4]). Note that
$\mathbf{x}_{*}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{b}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{e}_{1}.$

Note that $\hat{\mathbf{x}}$ satisfies
$\|\widehat{\mathbf{x}}-\mathbf{x}_{*}\|\leq 2\sqrt{\varepsilon},$ since

$\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|^{2}=\|\mathbf{A}(\hat{\mathbf{x}}-\mathbf{x}_{*})\|^{2}+\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2}\geq\|\hat{\mathbf{x}}-\mathbf{x}_{*}\|^{2}+\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2},$

and so under the stated conditions

$\|\hat{\mathbf{x}}-\mathbf{x}_{*}\|^{2}\leq\|\mathbf{A}\hat{\mathbf{x}}-\mathbf{b}\|^{2}-\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2}\leq(1+\varepsilon)^{2}-1^{2}\leq
3\varepsilon,$

where the inequality above uses
$\|\mathbf{A}\mathbf{x}_{*}-\mathbf{b}\|^{2}\leq\|\mathbf{b}\|^{2}=1.$