Decentralized Time-Varying Optimization for Streaming Data via Temporal Weighting

技术摘要：基于时间加权的流数据去中心化时变优化

问题表述
本工作解决了动态环境中数据在网络智能体间顺序到达时的去中心化优化挑战。与将目标演化视为任意过程的传统静态优化或通用时变公式不同，本文采用了一种针对流数据的结构化、基于权重的公式。

系统由通过无向连通图连接的 $N$ 个智能体组成。在每个时间步 $t$，每个智能体 $n$ 观测到一个新数据样本并产生瞬时损失 $\ell_{n,t}(w)$。全局目标 $F_t(w)$ 定义为截至时间 $t$ 所有网络观测损失的时间加权平均：
$$F_t(w) \triangleq \sum_{i=1}^t a_i(t) F_i(w),$$
其中 $F_i(w)$ 是时间 $i$ 的平均瞬时损失，$a_i(t)$ 是满足 $\sum a_i(t) = 1$ 的时间权重。目标是利用去中心化算法跟踪时变最小化器 $w^*_t = \arg\min_w F_t(w)$，且受限于有限的通信和计算预算（即每个时间步固定数量的内部迭代次数 $E$）。

方法论
作者分析了应用于该流设置的去中心化梯度下降（DGD）。该算法在每个时间步运行两个阶段：

1. 目标更新：网络纳入新的时间加权目标 $F_{t+1}$。
2. 内部迭代：从上一次迭代开始，智能体在更新后的目标上执行 $E$ 步 DGD。更新规则为 $w^{(k+1)}_t = M w^{(k)}_t - \eta \nabla f_{t+1}(w^{(k)}_t)$，其中 $M$ 是混合矩阵，$\eta$ 是步长。

核心分析方法利用不动点算子理论。作者定义了时变 DGD 映射 $\phi_t(w) = Mw - \eta \nabla f_t(w)$。在强凸性和平滑性假设（假设 1）以及有界最小化器假设（假设 2）下，他们证明了 $\phi_t$ 是一个压缩映射。因此，对于任意冻结的时间 $t$，存在唯一的不动点 $\tilde{w}_t$，使得 $\tilde{w}_t = \phi_t(\tilde{w}_t)$。

跟踪误差（TE），定义为 $\|w_t - w^*_t\|$，通过三角不等式分解为两个不同的分量：

1. 不动点跟踪误差（FPTE）：当前迭代点 $w_t$ 与移动不动点 $\tilde{w}_t$ 之间的距离。该项捕捉了算法在有限的 $E$ 次迭代内收敛到当前目标的能力。
2. 偏差项：不动点 $\tilde{w}_t$ 与真实时变最优化器 $w^*_t$ 之间的距离。该项源于数据的去中心化和步长 $\eta$。

主要贡献与结果
本文推导了两种典型时间加权策略的显式跟踪误差界：

1. 均匀权重：所有过去样本被同等加权（$a_i(t) = 1/t$）。

   • 结果：不动点跟踪误差以 $O(1/t)$ 的速率衰减。
   • 渐近行为：总跟踪误差收敛到一个非零下限，该下限完全由偏差项（$\eta \kappa \Lambda G$）决定，取决于步长、条件数、网络拓扑和数据异质性。移动不动点的贡献随时间消失。

2. 指数折扣权重：较旧的样本按几何级数衰减（$a_i(t) \propto \gamma^{t-i}$）。

   • 结果：不动点跟踪误差不会消失；它产生一个由折扣因子 $\gamma$ 控制的非消失稳态下限。
   • 渐近行为：总跟踪误差收敛到一个下限，该下限包含偏差项以及一个与 $(1-\gamma)$ 成正比的不动点跟踪下限。由于新样本的持续流入且权重较重，导致有效目标以非消失速率持续演化，算法无法完全追上移动不动点。

在这两种情况下，分析表明，在恒定步长下，去中心化引入了额外的偏差下限，该下限与最优解处的梯度幅值成正比（反映了数据异质性）。如果智能体间的数据是同质的，则该偏差将消失。

意义
本文声称，通过从通用时变模型转向结构化的流数据视角，它提供了更清晰且更具可解释性的跟踪误差保证。具体而言：

• 它阐明了时间加权策略与渐近跟踪性能之间的权衡。
• 它证明了虽然均匀加权允许算法最终“追上”移动不动点（FPTE 消失），但折扣加权本质上限制了这种能力，导致永久性的跟踪下限。
• 它通过在具有二次损失的网络智能体上的数值模拟验证了这些理论发现，表明增加内部迭代次数（$E$）可以改善瞬态性能，但无法消除由去中心化和步长约束引起的渐近偏差下限。

这项工作被呈现为理解流数据去中心化学习基本限制的理论基础，区分了由算法滞后（FPTE）引起的误差和由网络/数据结构（偏差）引起的误差。