<p>It turns out that there is a simple answer: <span class="math-container">$O(k)$</span>-composable <span class="math-container">$\frac kd$</span> compressor (in expectation) just returns <span class="math-container">$k$</span> random coordinates. The proof is trivial and can be found in <a href="https://arxiv.org/abs/1809.07599" rel="nofollow noreferrer">Stich et al., &quot;Sparsified SGD with Memory&quot;, Section A.1</a></p>

CC BY-SA 4.0
2021-01-22T15:09:28.340Z
2021-01-22T15:09:28.340Z
Dmitry
<p><strong>Def.</strong> We call <span class="math-container">$C: \mathbb R^d \to \mathbb R^d$</span> a <em><span class="math-container">$\delta$</span>-compressor</em> (or contractor) if for all <span class="math-container">$x$</span>
<span class="math-container">$$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$</span>
Intuitively, <span class="math-container">$C(x)$</span> is not too far from <span class="math-container">$x$</span>. Note that <span class="math-container">$\delta$</span> can be pretty small, e.g. <span class="math-container">$\frac 1d$</span>.</p>
<p><strong>Def.</strong> For a fixed <span class="math-container">$n$</span> we say that function <span class="math-container">$f$</span> is <em><span class="math-container">$\alpha$</span>-composable</em> if there exist functions <span class="math-container">$g$</span> and <span class="math-container">$h$</span> such that for any <span class="math-container">$x_1, \ldots, x_n$</span> we can represent each of <span class="math-container">$f(x_1 + \ldots + x_n)$</span>, <span class="math-container">$g(x_1), \ldots, g(x_n)$</span> using <span class="math-container">$\alpha$</span> bits and
<span class="math-container">$$f(x_1 + \ldots + x_n) = h(g(x_1), \ldots, g(x_n))$$</span>
Intuitively, we have <span class="math-container">$n$</span> machines, we send <span class="math-container">$g(x_i)$</span> from each machine to the coordinator which computes the answer and sends it back to the machine. Moreover, for each machine (except of the coordinator) the total communication is <span class="math-container">$O(\alpha)$</span>. The definition above was my attempt to capture this intuition, so it's possible that it's not the best one.</p>
<p>For <span class="math-container">$\alpha$</span>-composability, we may also allow a polylogarithmic number of rounds to compute the answer. I.e. for <span class="math-container">$k  = polylog$</span> of all parameters we can have functions <span class="math-container">$h_1, g_1, \ldots, h_k, g_k$</span>, so that in <span class="math-container">$j$</span>-th round <span class="math-container">$g_j(x_i, h_0, \ldots, h_{j-1})$</span> are sent to coordinator, <span class="math-container">$h_j$</span> are sent back to the machines and <span class="math-container">$h_k$</span> must compute <span class="math-container">$f(x_1 + \ldots + x_n)$</span>.</p>
<p>In both definitions, functions can be randomized. In this case, the properties must hold in expectation. All <span class="math-container">$g$</span> are allowed to share randomness in any way.</p>
<p>For example, <a href="https://arxiv.org/abs/1903.04488" rel="nofollow noreferrer">&quot;Communication-efficient distributed SGD with Sketching
&quot;</a> describes a <span class="math-container">$\tilde O(k)$</span>-composable <span class="math-container">$\frac kd$</span>-compressor. The main idea is to use count sketch to find heavy hitters.</p>
<p><strong>Question</strong>: Does there exist a function with the following properties:</p>
<ul>
<li>It is a <span class="math-container">$\frac cd$</span>-compressor for some constant <span class="math-container">$c$</span>.</li>
<li>It is <span class="math-container">$\tilde O(1)$</span>-composable (<span class="math-container">$\tilde O(1)$</span> means polylogarithmic on all parameters)</li>
<li>It is Lipschitz, i.e. for some constant <span class="math-container">$L$</span> we have <span class="math-container">$\|C(x) - C(y)\| \le L \|x - y\|$</span> for all <span class="math-container">$x, y$</span>. For randomized function, we only need Lipschitz property with respect to <span class="math-container">$x$</span>, i.e. <span class="math-container">$\|C(x, \theta) - C(y, \theta)\| \le L \|x - y\|$</span> for all <span class="math-container">$x,y,\theta$</span>, where <span class="math-container">$\theta$</span> is a randomness-controlling parameter and in the inequality above it's the same for <span class="math-container">$x$</span> and <span class="math-container">$y$</span>.</li>
</ul>
<p>Some weaker results (e.g. good <span class="math-container">$\frac 1 {\sqrt d}$</span>-compressors) are also appreciated.</p>
<p><strong>My thoughts</strong>: It shouldn't be possible even when we weaken <span class="math-container">$\alpha$</span>-composability requirement to the following: &quot;For all <span class="math-container">$x$</span>, <span class="math-container">$f(x)$</span> can be stored using <span class="math-container">$\alpha$</span> bits&quot;. Intuitively, I expect that any such compressor must be of a heavy hitter type, and such compressors are not Lipschitz.</p>
<p>The composability definition essentially restricts possible solutions to linear sketches, and count sketch seems to be the only feasible solution, but, unfortunately, a corresponding compressor is not Lipschitz. However, if we allow multiple communication rounds, it's not that clear anymore.</p>
<p>Any ideas how to approach this are appreciated. I suspect we should leverage some communication complexity technique, but I don't know which one.</p>

CC BY-SA 4.0
2020-10-07T18:45:05.063Z
What is d here?
Zachary Vance
CC BY-SA 4.0
2020-10-07T18:45:45.577Z
Isn't d the dimension?   I apologise if I'm wrong,  //Wishes
William Martens
CC BY-SA 4.0
2020-10-07T18:52:01.697Z
@ZacharyVance, $d$ is the dimension.
Dmitry
<communication-complexity><dc.distributed-comp>
Lipschitz composable compressor
Dmitry
# Lipschitz composable compressor

(Asked by: username_0 on 2020-10-06)

**Def.** We call $C: \mathbb R^d \to \mathbb R^d$ a *$\delta$-compressor* (or contractor) if for all $x$
$$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$
Intuitively, $C(x)$ is not too far from $x$. Note that $\delta$ can be pretty small, e.g. $\frac 1d$.

**Def.** For a fixed $n$ we say that function $f$ is *$\alpha$-composable* if there exist functions $g$ and $h$ such that for any $x\_1, \ldots, x\_n$ we can represent each of $f(x\_1 + \ldots + x\_n)$, $g(x\_1), \ldots, g(x\_n)$ using $\alpha$ bits and
$$f(x\_1 + \ldots + x\_n) = h(g(x\_1), \ldots, g(x\_n))$$
Intuitively, we have $n$ machines, we send $g(x\_i)$ from each machine to the coordinator which computes the answer and sends it back to the machine. Moreover, for each machine (except of the coordinator) the total communication is $O(\alpha)$. The definition above was my attempt to capture this intuition, so it's possible that it's not the best one.

For $\alpha$-composability, we may also allow a polylogarithmic number of rounds to compute the answer. I.e. for $k = polylog$ of all parameters we can have functions $h\_1, g\_1, \ldots, h\_k, g\_k$, so that in $j$-th round $g\_j(x\_i, h\_0, \ldots, h\_{j-1})$ are sent to coordinator, $h\_j$ are sent back to the machines and $h\_k$ must compute $f(x\_1 + \ldots + x\_n)$.

In both definitions, functions can be randomized. In this case, the properties must hold in expectation. All $g$ are allowed to share randomness in any way.

For example, ["Communication-efficient distributed SGD with Sketching
"](https://arxiv.org/abs/1903.04488) describes a $\tilde O(k)$-composable $\frac kd$-compressor. The main idea is to use count sketch to find heavy hitters.

**Question**: Does there exist a function with the following properties:

* It is a $\frac cd$-compressor for some constant $c$.
* It is $\tilde O(1)$-composable ($\tilde O(1)$ means polylogarithmic on all parameters)
* It is Lipschitz, i.e. for some constant $L$ we have $\|C(x) - C(y)\| \le L \|x - y\|$ for all $x, y$. For randomized function, we only need Lipschitz property with respect to $x$, i.e. $\|C(x, \theta) - C(y, \theta)\| \le L \|x - y\|$ for all $x,y,\theta$, where $\theta$ is a randomness-controlling parameter and in the inequality above it's the same for $x$ and $y$.

Some weaker results (e.g. good $\frac 1 {\sqrt d}$-compressors) are also appreciated.

**My thoughts**: It shouldn't be possible even when we weaken $\alpha$-composability requirement to the following: "For all $x$, $f(x)$ can be stored using $\alpha$ bits". Intuitively, I expect that any such compressor must be of a heavy hitter type, and such compressors are not Lipschitz.

The composability definition essentially restricts possible solutions to linear sketches, and count sketch seems to be the only feasible solution, but, unfortunately, a corresponding compressor is not Lipschitz. However, if we allow multiple communication rounds, it's not that clear anymore.

Any ideas how to approach this are appreciated. I suspect we should leverage some communication complexity technique, but I don't know which one.

**Tags:** communication-complexity, dc.distributed-comp
> **Comments:**
> **username_1**: What is d here?  
> **username_2**: Isn't d the dimension?   I apologise if I'm wrong,  //Wishes  
> **username_0**: @ZacharyVance, $d$ is the dimension.  

---

## 1 answers

### Answer by username_0 on 2021-01-22. Score: 1 | Accepted answer

It turns out that there is a simple answer: $O(k)$-composable $\frac kd$ compressor (in expectation) just returns $k$ random coordinates. The proof is trivial and can be found in [Stich et al., "Sparsified SGD with Memory", Section A.1](https://arxiv.org/abs/1809.07599)


---

