We consider the randomized communication complexity of the distributed
$\ell_p$-regression problem in the coordinator model, for $p\in (0,2]$. In this
problem, there is a coordinator and $s$ servers. The $i$-th server receives
$A^i\in\{-M, -M+1, \ldots, M\}^{n\times d}$ and $b^i\in\{-M, -M+1, \ldots,
M\}^n$ and the coordinator would like to find a $(1+\epsilon)$-approximate
solution to $\min_{x\in\mathbb{R}^n} \|(\sum_i A^i)x - (\sum_i b^i)\|_p$. Here
$M \leq \mathrm{poly}(nd)$ for convenience. This model, where the data is
additively shared across servers, is commonly referred to as the arbitrary
partition model.
We obtain significantly improved bounds for this problem. For $p = 2$, i.e.,
least squares regression, we give the first optimal bound of
$\tilde{\Theta}(sd^2 + sd/\epsilon)$ bits.
For $p \in (1,2)$,we obtain an $\tilde{O}(sd^2/\epsilon +
sd/\mathrm{poly}(\epsilon))$ upper bound. Notably, for $d$ sufficiently large,
our leading order term only depends linearly on $1/\epsilon$ rather than
quadratically. We also show communication lower bounds of $\Omega(sd^2 +
sd/\epsilon^2)$ for $p\in (0,1]$ and $\Omega(sd^2 + sd/\epsilon)$ for $p\in
(1,2]$. Our bounds considerably improve previous bounds due to (Woodruff et al.
COLT, 2013) and (Vempala et al., SODA, 2020).

本研究探讨了分布式 l_p 回归问题的随机通信复杂度，得到了比以前更好的上下界，并在最小二乘回归和其他一些情况中给出了优化算法。

通信的任意分区模型中的 $l_p$ 回归

$\ell_p$-Regression in the Arbitrary Partition Model of Communication

In this work we derive the performance achievable by a network of distributed
agents that solve, adaptively and in the presence of communication constraints,
a regression problem. Agents employ the recently proposed ACTC
(adapt-compress-then-combine) diffusion strategy, where the signals exchanged
locally by neighboring agents are encoded with randomized differential
compression operators. We provide a detailed characterization of the
mean-square estimation error, which is shown to comprise a term related to the
error that agents would achieve without communication constraints, plus a term
arising from compression. The analysis reveals quantitative relationships
between the compression loss and fundamental attributes of the distributed
regression problem, in particular, the stochastic approximation error caused by
the gradient noise and the network topology (through the Perron eigenvector).
We show that knowledge of such relationships is critical to allocate optimally
the communication resources across the agents, taking into account their
individual attributes, such as the quality of their data or their degree of
centrality in the network topology. We devise an optimized allocation strategy
where the parameters necessary for the optimization can be learned online by
the agents. Illustrative examples show that a significant performance
improvement, as compared to a blind (i.e., uniform) resource allocation, can be
achieved by optimizing the allocation by means of the provided
mean-square-error formulas.

本文研究了分布式代理网络解决回归问题的性能及其在通信约束下的自适应能力，采用 ACTC 扩散策略，在邻居代理之间交换的信号中使用随机差分压缩算子进行编码。提供了均方估计误差的详细特征描述，揭示了压缩损失与分布式回归问题的基本属性之间的定量关系，以及优化资源分配的重要性，提出了在线学习的优化参数分配策略，并给出实例验证。