TL;DR ^tldr

• 核心思想：把去中心化 FL 的动态拓扑选择问题建模为 MAB（MAB Tiger Machine），用 UTC 算法做无偏估计 + DCMU 用 loss 评估重要性做模型聚合，并把能耗（数据传输 + 计算 + 模型传输）显式纳入效用函数。
• 关键设计：
  • DCMU 用 loss 而非 gradient 评估贡献度 —— gradient 计算贵、loss 是观测副产物，工程上务实，理论依据是 L-smooth 下 loss 与 gradient 的正相关。
  • UTC 的逆概率加权 + 偏置项 $1 - \frac{[\cdot]}{p}(1 - u)$ —— 既保证无偏估计，又强制算法去尝试没选过的链路。
  • CLinkSec 用零和博弈式的概率打擂选边 —— 有遗传算法的味道，是启发式但有结构。
• 我的开放问题：
  1. CLinkSec 不保证连通性 —— 极端情况下会不会形成连通块孤岛，块内沟通而块间隔绝？这是部署里的硬约束，论文没给保证。
  2. 能耗效用框架（数据 + 计算 + 模型传输）能不能扩展到推理阶段？把 offloading 消耗也算进效用，让训练-推理协同共用一套效用模型

系统分三层：中心云服务器（Coordinator） $\to$ 边缘服务器（Edge Server）$S = \{ s_i\}$ $\to$ 边缘设备（Edge Devices）${\mathcal D}(s_i) = { d_j^i }$。边缘服务器拥有从边缘设备采集的数据 $D(s_i)$。整个交流图可以划分为两个，三层的树形交流网络，和 edge dev 之间的交流网络。

对于三层系统：

• Coordinator 作为协调，获取状态，不参与计算。
• 模型数据主要在 server 间流通，流通由 coord 协调

• DFL

问题建模为

$$\min f({\mathcal M}) = \frac 1 n \sum_{i = 1}^n f_i (m(v_i); D(v_i)) $$

其中 $m(v_i)$ 表示参与者 $v_i$ 的模型，$D(v_i)$ 则是数据，$f_i$ 是损失函数。

每一轮通信，先训练旧模型：

$$m_k(v_i) = \tilde m_k(v_i) - \mu \nabla f_i(m(v_i); D(v_i)) $$

然后将训练后模型依据这一轮的图信息，将 $m_k$ 发放给出边连接的参与者，然后获取入边的模型，然后聚合这些模型：

$$\tilde m_{k + 1} = f_{agg}(m_k(v_i), \{ m_k(v_{j})\}_{A_k(j, i) = 1}) $$

• 能源建模

分为三部分：数据传输，计算能耗，模型传输

对于数据传输，定义 $\psi$ 表示设备的单位传输成本，那么在 serv 和 dev 的数据传输

$$E_{k}^{dt} (s_i) = \sum_{d_{ij} \in D(s_i)} \psi A_d^k(s_i, d_j^i) $$

其中 $A_d$ 表示的是 serv 和 dev 的连接状态，其 $\sim {\rm Bern}(\rho)$，也就是连接不是确定性的，而是以概率 $\rho$ 随机建立。主动的随机，那就是随机采样；被动的随机（网络波动），模拟的就是实际的不确定性。这里将两者统一了。

对于计算能耗，使用 $\tau$ 定义处理一个 sample 的计算能耗，那么对于 serv，有

$$E_k^{cp}(s_i) = |D_k(s_i)| \cdot \tau_i $$

对于 serv 间的通信，考虑到上行和下行，上行的限制更大。所以可以用单边模拟，定义一下数据传输的能耗

$$E_k^{mt}(s_i, s_j) = \sigma^{i, j} $$

将三者聚合：

$$E_k(G_k^s(A_k^s)) = \sum E_k^{dt}(s_i) + \sum E_k^{cp} (s_i) + \sum_{s_i, s_j \in S} E_k^{mt}(s_i, s_j) \cdot A_k^s(s_i, s_j) $$

那么我们的目标是：

$$\min_{f_{agg}, G_k^s(A_k^s)} - {\mathbb E}[F({\mathcal M_0, f_{agg}, G_k^s(A_k^s)})], \sum E_k(G_k^s(A_k^s)) $$

$$s.t. A_k^s \in \{0, 1\}^{N \times N}, k \in {\mathcal K} $$

$F$ 表示最终的准确率。

解决这个问题的困难主要有两个：

• F 的最大化和 E 的最小化
• $A_k^s$ 是动态计算的，怎么计算？

为此，重新建模了一个效用评价标准：

$$u_k^{i, j} = \alpha S_k^p(s_i, s_j) + (1 - \alpha) S_k^c (s_i, s_j) $$

其中 $S_k^p$ 评价模型表现，$S_k^c$ 评价能耗。

$$\begin{aligned} S_k^c(s_i, s_j) &= 1 - {\rm Softmax}(E_k^{cp}(s_j) + E_k^{dt}(s_j) + E_k^{mt}(s_i, s_j)) \\ S_k^p(s_i, s_j) &= P_k^i - P_{k - 1}^i \end{aligned} $$

其中 $P_k^i$ 表示 $k$ 轮的准确率，则 $S_k^p$ 评价的是训练的准确率提高程度。

那么问题就可以转变为了最大化：

$$\max \sum_k \sum_{i, j} A_k^s(s_i, s_j) u_k^{i, j} $$

限制新增一个 $\sum A_k^s (s_i, s_j) = \gamma \binom {|{\mathcal D}|}{2}$

可以尝试通过 01 背包的规约，证明这个问题是 NP-HARD 的。规约思路比较清晰，对于每一轮 $A_k^s$ 的设置，应当基于 $u_k$ 的分数，而 $u_k$ 只能选一定个数（由上述限制），那么就变成了一个 01 背包问题。

但是为什么呢？这里 $w_l$ 都为 $1$
我的理解是，计算 $A_k^s$ 需要的 $u_k^{i, j}$ 实际上在这一轮是不可知的，所以会出现没有办法进行贪心之类的情况。于是需要进一步规约问题，而这里的 01 背包实际上也算合理，用于强调其困难性。

所以重新建模：

$$\max {\mathbb E} \left[ \sum_k \sum_{i, j} A_k^s(s_i, s_j) u_k^{i, j}\right] $$

然后将 ${\mathbb E}$ 作用域 $A_k^s$ 上，问题变为：

$$\begin{aligned} &\max \sum_k \sum_{i, j} p_k(s_i, s_j) u_k^{i, j} \\ {\rm s.t.} & \sum p_k(s_i, s_j) = \gamma \cdot |{\cal E}^s| \end{aligned} $$

为什么就变成了 MAB 了呢？
因为 $u_k$ 需要根据前面的通信轮次估计，获取 Reward；每轮选择若干通信边，就是 Arm 的过程；目的是获取最大的奖励。这是一个动态变坏的
利用 MAB 就可以套用已有的 MAB 分析框架了，大大减少工作量。

整个算法分为两部分：UTC 和 DCMU

1. 初始化
2. $K$ 轮
3. 在 Coord 上跑 UTC，广播 $A_k^s$
4. 在 serv 上跑 DCMU，更新模型
5. 进入下一轮

• $\Delta$ UTC

补充：无偏估计（unbiased estimation）
如果一个估计的量 ${\mathbb E}[\hat X] = X$，那么对于 $X$ 的估计就是无偏估计
如果直接用观测到的效用作为估计值，一般来说，就会导致有偏估计
在这里的体现是，对于 $u_k^{i, j}$ 的观测， 只有在 $A_k^{i, j} = 1$ 的时候才可以被观测到，其他时候未知。注意到其观测的概率取决于 $p_k(s_i, s_j)$，那么自然的，可以利用逆概率加权的方法，获得一个无偏估计。
逆概率加权：
对于不同的样本，其被观测到的概率不一样，但是其在平均，也就是 ${\mathbb E}[u_k^{i, j}]$ 中是平均的。所以对于采样，除以其采样概率，可以平均的分配到单次采样中：
其中 $S$ 表示样本 $Y$ 是否被选择，$X$ 表示观测到的已知信息。

$$\begin{aligned} E\left[ \frac{S \cdot Y}{P(S=1|X)} \right] &= E\left[ E\left[ \frac{S \cdot Y}{P(S=1|X)} \bigg| X \right] \right] \\ &= E\left[ \frac{1}{P(S=1|X)} \cdot E[S \cdot Y | X] \right] \\ &= E\left[ \frac{1}{P(S=1|X)} \cdot P(S=1|X) \cdot E[Y | X] \right] \\ &= E[E[Y | X]] = E[Y] \end{aligned} $$

于是在该语境下，虽然利用无偏估计，我们可以写出：

$$\hat u_k^{i, j} = \frac {[A_k^s(s_i, s_j) = 1]}{p_{k - 1}(s_i, s_j)} u_k^{i , j} $$

但实际上应该是：

$$\hat u_k^{i, j} = 1 - \frac {[A_k^s(s_i, s_j) = 1]}{p_{k - 1}(s_i, s_j)} (1 - u_k^{i , j}) $$

最大的区别是，在没有采样的情况下，认为效用是 $1$，虽然带来了一定的偏差，但是：

• 保证了，$\hat u_k^{i, j}$ 是有界的 $\le 1$。
• 这迫使算法必须去尝试那些没选过的链路。

于是通过该效用的估计，我们可以启发式的更新每一个边连接选择的权值：

$$w_k(s_i, s_j) = w_{k - 1} (s_i, s_j) \exp(\eta\ \hat u_{k - 1}^{i, j}) $$

这个很自然的，如果效用为 $0$，那么降低权值，如果效用大于 $0$，那么增加权值。小的 $\eta$ 期望探索，而较大的 $\eta$ 期望使用更稳定的高效用的链路。依据这个权重，我们就可以设计 CLinkSec 算法了：

1. 将 $w_k$ 归一化为选择概率，通过 $\times \gamma |{\cal E}^s|$ 控制期望选择的边数，然后和 $1$ bound 一下，得到 $p_k(s_i, s_j)$
2. 不断随机化选择两条边，通过类似打擂的方式，将概率差拉开。定义 $good_i = \min(p_i, 1 - p_j), good_j = \min(p_j, 1 - p_i)$

$$(p_i, p_j) = \begin{cases} (p_i + good_i, p_j - good_j) & 以 \frac {good_i}{good_i + good_j} 的概率 \\ (p_i - good_j, p_j + good_j) & 以 \frac {good_j}{good_i + good_j} 的概率 \end{cases} $$

这个算法由于进行了一个类似零和博弈的环节，所以整体概率和为 $\gamma |{\cal E}|$，到最后，概率对抗后变成了若干 $0/1$，其中 $1$ 的边就是需要选择的边。

但是会不会存在整张图变成了若干个连通块，块内沟通，形成新的信息孤岛呢？
毕竟这个算法没有保证连通性。
我后面想了一下，这个其实要紧程度不大，因为在计算 $u$ 的过程中，默认为 $1$ 会促使其尽量选择没有选择过的通路，所以感性上理解，总是会联通通信的。

^69770a

这实际上是一种启发式的解决方法，还是很新颖的方式，感觉有遗传算法的味道，杂交编译，优胜劣汰。

• $\Delta$ DCMU

对于每个 serv，执行如下算法：

1. 根据 $A_k^d$ 连接收集 dev 的数据，并且计算数据传输的开销 $E_k^{dt}$
2. 本地训练，然后记录计算能耗 $E_k^{cp}$
3. 记录数据大小，随机采样本地数据 $D_k^{sa}(s_i)$，用于聚合部分。
4. 依据 $A_k^s$ 和最初说明的流程，传输和获取其他 serv 的模型
5. 计算来自其他 serv 模型的重要性
6. 依据重要性，聚合模型
7. 计算准确率，获取 $P_k$
8. 上传基本信息给 Coord，用于计算下一个计算图。

其中聚合的部分采用了和 FedAtt 不同的方法，虽然都是评估“相似性”的，其核心解决的问题类似。

以往的想法是，通过梯度来判断重要性，也就是：

$$|D^{sa}| \cdot \sqrt{\frac 1 {|D^{sa}|} \sum_{\xi \in D^{sa}} \| \nabla f(m, \xi) \|^2} $$

其理论依据还是 L-smooth & Lipschitz 连续性假设#^2cc141
顺便也可以说明，对于这类问题，损失和梯度的大小应该是正相关的。所以利用 loss 来拟合 $\nabla$ 是合理的。

那么可以定义：

$$\begin{aligned} loss_k^{i, j}(\xi) &= f_{\xi \sim D_k^{sa}(s_i)} (m_k(s_j), \xi) \\ k_k^{i, j} &= B \sqrt{ \cfrac 1 B \sum_{\xi} (loss_k^{i, j}(\xi))^2} \\ q_k^{i, j} &= \beta \cdot {\rm Softmax}(l_k^{i, j}) + (1 - \beta) \cdot {\rm Softmax}(|D_k^{s_j}|) \end{aligned} $$

其包含了两个部分，损失和数据多少。由于数据少的模型，样本少，自然方差大，其参考性就不足，否则可能导致偏差太大而破坏收敛性。对于为什么选择损失大的模型，理论支撑是重要性采样定理，也就是训练阶段，如果模型对许多“简单”样本已经表现良好，继续频繁采样这些样本会减慢进一步优化，所以需要通过优先采样对模型优化贡献更大的样本，加速 SGD 收敛。

于是，通过：

$$\hat m_{k + 1}(s_i) = \sum q_k^{i, j} m_k(s_j) $$

聚合即可。