TL;DR

• 核心思想：把去中心化 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) $$

聚合即可。

关于加入计算卸载，我目前的想法是这样的。

在这个框架中，我们考虑每一个时间 t，我们每一个设备要计算的东西有两个：当前模型在本地数据集上微调的梯度；接收一些模型，计算在本地数据集的 loss 用于聚合。

那么每一轮可以视为有这样一个任务队列：

• 每个设备的模型在本地微调
• 当设备 A 微调结束后，将微调后模型发送给计算图连接的设备 {B}，{B} 各自计算接收的模型在本地数据的损失。

当所有任务完成后，我们才能进行下一轮传递和训练。那么现在我们的目的就是通过计算卸载，缓解慢设备处理得慢的情况，加速训练。

于是我们先考虑第二个任务，也就是计算损失的这一部分。这里复用预先构建好的拓扑图以及不额外进行模型的传输，只使用原本构建的通信图。
于是第二个问题就是：将同一个模型 $m_k(s_i)$ 在不同的设备 $Dev = \{j | A_k^s(i, j) = 1\}$ 上，独立的计算 $q_k^{i, j}$ 变成共同的计算 $q_k^{i, j}$（实际上是计算 $loss_k^{i, j}$）

于是考虑能不能将慢设备上的一些任务分给快设备。
这个问题就变成了在同一时间有多个，设备持有相同的模型，要在各自设备的数据集上计算损失，我们需要对此找到一个方法，减少最大推理延迟和能量消耗的一个组合（通过超参数控制权重）。
为了保证联邦学习中数据隐私的问题，我们只能选择模型切割，并将中间特征值通过某个算法交给其他的设备进行进一步计算。
目前核心的问题，有三个：

1. 传递 Smashed Data 到其他设备计算 logits，是否可行？这符合 SL 的弱隐私假设。
2. 只考虑单个模型，在多个设备上计算 loss 的情况，怎么设置切割的深度以及如何复用原本效用的评估体系分配任务？
   • 对于切割深度一个简单的想法是设为超参数，一般取最中间的那一层作为切割。另一个想法是采用 SSIM 动态的评估中间特征和原始数据的相似度，动态的调整切割。（当然没法用在 LLM 上）
     • 可能不是很好扩展，只适用于 CV，还需要找一些相关的框架
     • 或者类似 DP-MORA 将决策权下放至每个终端设备，使其仅依据自身的本地多维训练配置独立决定切分层与资源需求，无需知晓其他设备的任何配置信息，但这样如何于效用进行耦合？
       • 其实交给协调器就 ok 了吧，似乎没有必要？
   • 继续使用效用估计，此时其实每个设备间的通信上界是可以预估了（最好是直连，最坏是经过 $s_i$ 转发，而转发双边的延迟和能耗都已知。并且计算量，如果在确定了切割深度和设备计算能力的条件下，也可以唯一的确定。于是可以定义新的效用 $v_k^{i, j, \xi} = \theta S^{latency}_k(s_i, s_j, \xi) + (1 - \theta) S^c_{energy}(s_i, s_j, \xi) + S^{local~latency~and~energy}_k(s_i, \xi)$，最后一项评估前面一半必要的本地推理的能耗和延迟。我们的目标就是构建一个新的图 $G$ 使得效用估计最好。
     • 由于 $v$ 不存在需要估计的情况，可以贪心的解决？这样只需要解决状态同步的问题即可。例如引入区块链抢任务？？或者预先就分配好任务？
     • 或者实际上 $v$ 也是需要实时估计的？？这样基于历史的无偏估计可能更符合这个扩展的叙事。
3. 由于有很多个模型，所以实际上一个设备要处理多个模型的计算，在一的基础上如何扩展到多任务的分配？变成最小化全局的延迟/能耗组合效用评估？
   • 考虑到 2 的想法，实际上还是贪心？

然后类似的，计算梯度微调，可以在 $s_i$ 和上一轮持有 $\hat m_k(s_i)$ 的设备上进行任务分配。效用是一致的，只是具体的计算有所变化。
这里最大的问题是：由于需要计算 loss，一定会把 label 也一并上传，这就破坏了隐私假设。必须要加入例如差分隐私的相关东西，例如 PixelDP。但是这样就牺牲了训练的精度。

• 可以计算 logits 后回传，计算 loss 后 BP 一层，接收继续 BP 到切分层，然后回传继续 BP？这样对通信要求就要多一点点了。不过最后的特征其实很少，所以影响不大？

实际上训练卸载收益很大，而计算 loss 的卸载收益不大，需要做实验验证。因为训练开销大，而 loss 计算开销小。并且就是为了减少计算量才选择计算 loss 的。

现在知道 $v_k^{i, j, \xi}$ 是可以精确计算的，全局下的最优应该是一个背包问题，难以计算最优解。

可以定义卸载图 $G_k((i, \xi), j) \in \{0, 1\}$，那么约束和目标是：

$$\begin{aligned} \max & \min_j \sum_{(i, \xi)} G_k((i, \xi), j) v_k^{i, j, \xi} \\ \text{s.t. } & \sum_{j} G_k((i, \xi), j) = 1 \\ \end{aligned} $$

但这样就和原来的：$\max \sum u$ 的方向不同了。

如果是 $\max \sum u$，那么问题就是简单的，全部分配到 $v$ 最小的就行。这就可能全部放到最优的那个设备上，导致超载。没法合理的优化整轮聚合的速度。

由于 $v_k^{i, j, \xi}$ 数量级是 $O(n^2 |D|)$ 的，非常大（其实也还好，所有有意义的完全可以直接计算）
一个朴素的想法是二分 + 反悔贪心？

可以实验三档对照：MILP 最优（小规模） + LST 舍入（中规模） + 启发式（大规模），用 LST 舍入代替二分 + 反悔贪心。

但是我觉得使用博弈论的方法可能更连贯？

现在是一个组内的协同，能不能变成全局协同？

新的问题是：

• 如果变成所有设备协同，那么必定是有些效用不能复用现有的信息，必须进行额外的估计。这是否合理？
• 如果需要变成全局协同，那么就不好有 LST 舍入的算法，大概是博弈或者启发式。
  • 如果是博弈？怎么做？
  • 启发式可能理论分析比较困难。直接在协调 Server 端抢任务？边界情况怎么办？

如果变成全局协同，在最终训练收敛后，全局收敛于同一个目标。

• Splitwise: Collaborative Edge–Cloud Inference for LLMs via Lyapunov-Assisted DRL (2025)
  明确将延迟、能耗、精度纳入统一奖励函数，和效用的建模类似。边缘-云 LLM 推理，注意力头/FFN 级细粒度切割。可能可以引入？采用的是 Lyapunov，一种凸优化方法。

• Li et al., "Adaptive Split Learning over Energy-Constrained Wireless Edge Networks" (2024)
  也可以 min 平均训练延迟，s.t. 长期能耗约束

效用评估的计算：无偏估计还是复用计算？

• 在单轮中，$v$ 其实是可以精确计算的，但是如果扩展到突破了邻居限制，那么就必须要估计
• 考虑到时变性，状态可能变化较大，可能还是需要估计？那继续使用原本的估计方法？

优化目标的精确形式：负载均衡还是总效用最大？

• 若目标是最小化每轮聚合的最大完成时间（makespan），这与 HAT-DFed 的"最小化累积能耗"目标有所冲突
• 若保留 HAT-DFed 的 $\max \sum v$ 语言，意味着允许某些设备过载、只要全局总效用高即可，可能没法优化每轮延迟。此时问题变得 naive，贪心选择最小的就好。

求解方法的选择：LST 舍入、博弈论还是贪心？

• LST 舍入（Dependent Rounding）需要中心协调器执行概率舍入，与 HAT-DFed 的去中心化设计存在张力；是否接受 coordinator 在任务分配中扮演更强角色？
• 若坚持完全分布式，博弈论（如势博弈 / 纳什均衡）是否更合适？但收敛速度和均衡效率是否有理论保证？怎么进行？
• 可不可以"无理论 bound 的分布式贪心 + 大规模实验"，还是必须要求近似比/均衡存在性证明？

全局协同 vs. 局部拓扑约束：是否值得突破 HAT-DFed 的邻居限制？

• 是否接受在任务卸载层引入一个逻辑全局视图（coordinator 维护全局设备负载状态），而保留 HAT-DFed 的模型交换拓扑不变？这会形成"双层拓扑"（模型交换用局部图，计算卸载用全局图），架构上是否优雅？
• 并且那么必定是有些效用不能复用现有的信息，必须进行额外的估计。这是否合理？

隐私论证深度？

• 直接引用 SplitFed 弱假设即可，还是需要量化 smashed data 反演风险？

模型设置：是否需要把 CNN 这种简单模型设置为 Transformer 还是什么

• Splitwise Collaborative Edge–Cloud Inference for LLMs via Lyapunov-Assisted DRL.pdf

• D，3 targets，SL