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 " 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.
