论文阅读_Online_Distributed_Optimization_with_Efficient_Communication_via_Temporal_Similarity

论文阅读

Online Distributed Optimization with Efficient Communication via Temporal Similarity

题目：基于时间相似性的高效通信在线分布式优化

出处：CCFA-INFOCOM

时间：2023

作者：Juncheng Wang∗, Ben Liang∗, Min Dong†, Gary Boudreau‡, and Ali Afana‡
∗Department of Electrical and Computer Engineering, University of Toronto, Canada,
†Department of Electrical, Computer and Software Engineering, Ontario Tech University, Canada, ‡Ericsson Canada, Canada

摘要：

考虑网络系统中的在线分布式优化，其中由服务器辅助的多个设备协同最小化可能随时间变化的全局损失函数序列的积累。为了减少通信量，设备向服务器发送量化和压缩的本地决策，从而产生嘈杂的全局决策。因此，在优化性能和通信开销之间存在权衡。现有的工作分别优化了计算和通信。相比之下，我们通过鼓励决策序列中的时间相似性来控制通信开销，共同考虑计算和通信随时间的变化。我们提出了一种有效的算法，称为具有时间相似性的在线分布式优化(ODOTS)，其中局部决策是计算和通信感知的。此外，ODOTS使用了一种新颖的可调虚拟队列，通过改进的Lyapunov漂移分析完全消除了通常假设的Slater条件。ODOTS在优化目标和约束违反上都提供了可证明的性能界限。作为一个示例应用程序，我们应用ODOTS来实现高效通信的联邦学习。我们基于真实图像分类的实验结果表明，与目前最佳的凸损失函数和非凸损失函数相比，ODOTS具有更高的分类精度和更低的通信开销。

结论：

考虑网络系统在长期决策不相似约束下的在线分布式优化，以控制通信开销。我们提出了一种有效的ODOTS算法，通过一种新颖的可调虚拟队列来平衡优化的改进和随着时间的推移的通信成本。通过改进的Lyapunov漂移分析，我们证明了ODOTS同时从集中式每槽优化器和亚线性约束违反中实现了亚线性性能差距。当将ODOTS应用于联邦学习时，我们的实验结果表明，在提高测试准确性和减少通信开销方面，ODOTS比最先进的方法具有显著的性能优势。ODOTS尤其在通信预算紧张的系统中具有优势。

研究背景

分布式优化已经成为现代机器学习应用的基本工具，这需要大量的存储、计算和数据。它避免了任何单个服务器的负担过重，并且通过协调多个本地设备来处理机器学习任务，对故障具有鲁棒性。它还可以通过将数据保存在本地来减轻隐私问题。然而，将优化从中央服务器迁移到本地设备可能会导致它们之间的通信开销激增。这需要通信高效的分布式优化。大多数现有的关于通信高效分布式学习的工作都将计算和通信分开考虑，也就是说，诸如量化和压缩之类的通信设计是在机器学习模型参数已经确定之后进行的，例如通过标准梯度下降。然而，由于通信效率强烈依赖于所传输的信息，因此可以通过主动设计学习精度和通信的模型参数来进一步提高学习性能效率。换句话说，联合考虑计算和通信将更充分地考虑到它们之间的相互影响。

研究目的

针对大多数现有的工作都集中在离线优化上，不允许时变损失函数或考虑任何长期约束的问题，进行在线优化，我们计算一系列优化决策，以适应不可预测的系统动态。如何设计一个在线分布式优化算法，同时考虑计算和通信随时间的变化?

为了回答上述关键问题，我们必须解决几个挑战:

1)由于通信开销依赖于从设备传输到服务器的本地决策，因此在更新本地决策时，我们必须同时考虑它们的优化性能和通信成本。

2)有损量化大大降低了通信开销，但同时在优化决策中产生了错误，这些错误随着时间的推移在迭代计算过程中传播。

3)由于计算和通信之间的紧密耦合，我们必须适当平衡它们共同对优化性能和收敛速度的影响。

4)计算和通信都需要适当地制定和设计，以考虑环境随时间的不可预测的波动。

论文贡献

1 在线分布式优化问题，服务器通过汇总来自设备的量化和压缩的局部决策来计算一系列全局优化决策以最小化累积的全局损失。为了减少通信开销，通过强制执行平均长期决策不相似约束来鼓励设备上计算的本地决策序列的时间相似性。

2 ODOTS产生的局部决策能够适应损失函数的不可预测波动，同时考虑到决策不相似约束的违反，从而限制了通信开销。ODOTS通过一种新颖的可调虚拟队列实现了这一点，该队列需要改进的Lyapunov漂移分析技术。值得注意的是，这消除了对Slater条件的要求，该条件通常在现有的基于虚拟队列的在线优化算法中被假设。

3 分析了计算和通信之间的紧密耦合，以及它们对ODOTS优化性能和收敛速度的共同影响。对于设备上所有时变权值序列，ODOTS与集中式每时隙最优决策序列的性能差距为0 (max{T（1 +μ ）/ 2, T（3 +ν ）/4})，违反T时隙长期决策不相似约束的性能差距为0 (max{T3 +μ/ 4, T7 +ν/ 8})，其中μ表示集中式每时隙优化器的增长率和量化误差，ν表示时变权值的累积变化。

4 应用ODOTS来实现高效通信的联邦学习。实验结果表明，在不同的场景下，与现有的最佳方案相比，对于凸和非凸损失函数，ODOTS都能以更低的通信开销获得更高的测试精度。

相关工作

分布式优化中的通信效率

通信效率与分布式学习

在线凸优化与Lyapunov优化

论文方法

问题引入

考虑一个由N个本地设备和一台服务器组成的网络系统。系统以时隙方式工作，时间以t为索引。感兴趣的是一个具有全局损失函数$f_t(\mathbf{x})$在每时刻t的在线分布优化问题。它被定义为局部损失函数$f_t^n(\mathbf{x})$的加权平均值。w是权值，x是d维输入数据样本。

$$f_t(\mathbf{x})\triangleq\sum_{n=1}^Nw_t^nf_t^n(\mathbf{x})$$

有：

$$f_t^n(\mathbf{x})=\frac{1} {|\mathcal{D}_t^n|}\sum_{i=1}^{|\mathcal{D}_t^n|}l(\mathbf{x};\mathbf{u}_t^{n,i},v_t^{n,i})$$

在线分布式优化的目标是在服务器上计算一系列全局决策{xt}，使有限时间范围T内的累积全局损失最小化，即:

$$\min_{\{\mathbf{x}_t\}}\quad\sum_{t=1}^Tf_t(\mathbf{x}_t).$$

量化压缩

对于累积全局损失的分布式最小化，每个设备n生成其局部决策序列${x_t^n}$。服务器将本地决策${x_t^n}$从N个设备传输到服务器可能会导致大量通信开销。这可能是具有挑战性和耗时的。

未来高效通信，传输到服务器前对本地决策进行量化，生成量化决策：

$$\hat{x}_t^{n,i}=x_{\max}\cdot\mathrm{sign}(x_t^{n,i})\cdot\mathrm{map}(x_t^{n,i};x_{\max},s)$$

传递量化的局部决策需要有效的编码将$\hat{x}^{n}$转换为位流。（条件熵编码可以大大降低通信开销）。由于有损量化，服务器只能计算一个有噪声的全局决策$\hat{x}_{t+1}$，其中n代表全局量化误差（噪声）。

$$\mathbf{\hat{x}}_{t+1}=\sum_{n=1}^Nw_t^n\mathbf{\hat{x}}_t^n=\mathbf{x}_{t+1}+\mathbf{n}_{t+1}$$

${\hat{x}_{t+1}^n}$的有损传输可以很容易地与提出的算法及其性能分析相结合。

问题表示

核心目标：同时考虑全局损失最小化和局部决策通信开销。

直接建模时间相似性编码方案是具有挑战性的，因为它依赖于联合概率密度。论文通过重视信息源之间的差异来解决这个问题，并通过限制决策不相似的数量$|\mathbf{x}_t^n-\hat{\mathbf{x}}_{t-1}^n|^2$来控制通信开销(欧几里得范数）。

$$\begin{aligned}\mathbf{P1}:\quad\min_{\{\mathbf{x}_{t}^{n}\in\mathcal{X}\}}&\sum_{t=1}^{T}f_{t}(\hat{\mathbf{x}}_{t})\\ \mathrm{s.t.}&\frac{1}{N}\sum_{t=1}^{T}\sum_{n=1}^{N}g_{t}^{n}(\mathbf{x}_{t}^{n})\leq0\\ \end{aligned}$$ $$g_t^n(\mathbf{x})\triangleq\|\mathbf{x}-\hat{\mathbf{x}}_{t-1}^n\|^2-\epsilon$$

计算一个局部决策序列${x_t^n}$，以最小化有噪声全局决策序列$\hat{x}_{t}$产生的累积损失，同时保证平均长期决策不相似约束得到满足。由于损失和约束函数的时变，P1是一个在线优化问题。

每个时间的最优解（全局信息）为：

$$\mathbf{x}_t^{\text{ctr}}\in\arg\min\{f_t(\mathbf{x})|g_t^n(\mathbf{x})\leq0,\forall n\}.$$

论文的目标是开发一种有约束的在线分布式优化算法，以计算具有亚线性性能差距到$\mathbf{x}_t^{\text{ctr}}$的P1的在线分布式解序列，即以及亚线性约束违反。性能差距和约束违反的次线性性是重要的;这意味着在线分布式解在时间平均性能方面接近于$\mathbf{x}_t^{\text{ctr}}$，并且长期约束是渐近满足的。

Lyapunov优化与具体算法

在每个设备中引入虚拟队列（p1）：

$$Q_{t+1}^n=\begin{bmatrix}(1-\gamma^2)Q_t^n+\gamma\eta g_t^n(\mathbf{x}_t^n)\end{bmatrix}_+$$

其中γ∈(0,1)是虚拟队列上的调优因子，η > 0是约束函数上的加权因子，[a]+ = max{a, 0}是投影算子Qn t的作用类似于P1的拉格朗日乘法器或违反约束的积压队列。这个新的可调虚拟队列提供了Qn t的一个简单上界，它不需要通常假定的基于虚拟队列在线的Slater条件优化算法。为了克服不能再直接将虚拟队列上界转移到约束违反界技术困难，论文将使用一种新的改进的Lyapunov漂移分析技术来约束违反项。

将p1转化为局部优化：

$$\mathbf{P2}^n: \min_{\mathbf{x}\in\mathcal{X}} \langle\nabla f_t^n(\hat{\mathbf{x}}_t),\mathbf{x}-\hat{\mathbf{x}}_t\rangle+\alpha\|\mathbf{x}-\hat{\mathbf{x}}_t\|^2+\eta Q_t^ng_t^n(\mathbf{x})$$

与最初的P1相比，长期决策不相似约束被转化为控制$g_t^n(\mathbf{x}_t^n)$以维持队列稳定性。求解凸优化问题P2n的直观方法是最小化修正漂移+惩罚+违反项的上界，以权衡损失最小化和随时间的约束违反。对p2n求梯度=0并且投影到x上，就得到了最优解。ODOTS的局部决策更新是计算和通信感知的，即随着时间的推移，自动平衡优化的改进和通信的成本。

性能bound

本节为证明ODOTS在优化目标和时间决策不相似约束中都提供了强有力的性能保证（证明略）。特别是，ODOTS的独特设计需要新的分析技术来考虑噪声决策更新和可调虚拟队列的影响。

论文给每个器件n定义了一个修正的李雅普诺夫漂移

$$\Theta_t^n=\frac{1}{2\gamma}(Q_{t+1}^n-U)^2-\frac{1}{2\gamma}(Q_t^n-U)^2.$$

ODOTS与$\mathbf{x}_t^{\text{ctr}}$的性能差距的上限为

$$\begin{aligned}\sum_{t=1}^{T}(f_{t}(\hat{\mathbf{x}}_{t})-f_{t}(\mathbf{x}_{t}^{\mathrm{ctr}}))&\leq\frac{D^{2}T}{4\alpha}+2\gamma\eta^{2}G^{2}T+\frac{\eta^{2}G^{2}\Omega_{T}}{2\gamma^{3}}\\&+\alpha\big(R^{2}+\Lambda_{2,T}+2R(\Lambda_{T}+\Pi_{T})\big)\end{aligned}$$

ODOTS产生的约束违反的上界为

$$\begin{aligned}&\frac{1}{N}\sum_{t=1}^{T}\sum_{n=1}^{N}g_{t}^{n}(\mathbf{x}_{t}^{n})\leq\left(\frac{2\gamma^{2}T+2}{\gamma\eta^{2}}\right)^{\frac{1}{2}}\left(\frac{D^{2}T}{4\alpha}+2\gamma\eta^{2}G^{2}T\right.\\&+D(R+\delta)T+\alpha\big(R^{2}(1+\Xi_{T})+\Lambda_{2,T}+2R(\Lambda_{T}+\Pi_{T})\big)\bigg)^{\frac{1}{2}}\end{aligned}$$

最终的结论：

此处论文没有证明。但将参数带入即可得到论文的结果。

特别是，如果μ < 1且ν < 1，即系统变化在T上是次线性的，则性能差距和约束违反在T上都是次线性的。在动态不可预测的在线优化中，系统的次线性变化是实现次线性性能界限的标准必要条件(但通常是不足条件)。

实验与结果

论文在联邦学习中进行了实验。考虑一个具有N = 10个设备和一个服务器的FL系统。基于真实世界的图像分类数据集，用于凸和非凸损失函数，在流行的MNIST数据集上评估了。使用多项逻辑回归的交叉熵损失。

评估指标：

计算性能指标：

时间平均测试精度+ A(T)

时间平均训练损失+ f(T)

通信性能指标：

条件熵编码B(T)

时间平均决策不相似度g (T)

结果：

个人想法

这是一篇应用李雅普诺夫漂移优化的论文，让我对李雅普诺夫漂移优化有了一点新的认识。论文针对在线分布式优化，共同考虑计算和通信随时间的变化，对于每个时间槽t，构造一个虚拟队列，实现了一个高效的联邦学习。对于论文的证明过程，作者给出比较详细的论证过程，整体上比较清晰。在实验部分中，对其他模型的对比也比较明显。

引用内容（自用）：

ieeexplore：

@INPROCEEDINGS{10229086,
author={Wang, Juncheng and Liang, Ben and Dong, Min and Boudreau, Gary and Afana, Ali},
booktitle={IEEE INFOCOM 2023 - IEEE Conference on Computer Communications},
title={Online Distributed Optimization with Efficient Communication via Temporal Similarity},
year={2023},
volume={},
number={},
pages={1-10},
keywords={Performance evaluation;Costs;Federated learning;Computational efficiency;Servers;Noise measurement;Optimization},
doi={10.1109/INFOCOM53939.2023.10229086}}

google学术：

@inproceedings{wang2023online,
  title={Online distributed optimization with efficient communication via temporal similarity},
  author={Wang, Juncheng and Liang, Ben and Dong, Min and Boudreau, Gary and Afana, Ali},
  booktitle={IEEE INFOCOM 2023-IEEE Conference on Computer Communications},
  pages={1--10},
  year={2023},
  organization={IEEE}
}

Wang J, Liang B, Dong M, et al. Online distributed optimization with efficient communication via temporal similarity[C]//IEEE INFOCOM 2023-IEEE Conference on Computer Communications. IEEE, 2023: 1-10.