---
tags: AI分享
---

# 联邦学习（Federated Learning）

[TOC]

[Kairouz P, McMahan H B, Avent B, et al. Advances and open problems in federated learning[J]. arXiv preprint arXiv:1912.04977, 2019.](https://arxiv.org/pdf/1912.04977)

## 0 综述

### 0.1 联邦学习背景

#### 0.1.1 定义

联邦学习（FL）是一种机器学习设置方式，其中许多客户端（例如，移动设备或整个组织）在中央服务器（例如，服务提供商）的协调下**共同训练**模型，同时保持训练数据的去**中心化及分散性**。

#### 0.1.2 问题的引出

- **Google gboard**


### 0.2 问题与挑战

#### 0.2.1 数据

- 数据分布不均衡

- NON-IID（非独立同分布）

- 非独立 输入法项目中，样本受到地区影响
- 非同分布 $(x,y) \sim \mathcal{P}_i(x,y)\not= P_j$，将${P}_i(x,y)$重写为$P_i(y|x)P_i(x)$和$P_i(x|y)P_i(y)$，来描述他们的区别

- 特征分布倾斜：$\mathcal{P}(y|x)$相同，$\mathcal{P}_i(x)$不同；
（笔迹识别中，不同人的笔迹不同，用户在书写同一个单词时也可能有着不同的笔画宽度、斜度等。）

- 标签分布倾斜：$\mathcal{P}(x|y)$相同，$\mathcal{P}(y)$不同；当客户端与特定的地理区域绑定时，标签的分布在不同的客户端上是不同的。
（对于不同医院的医疗设备，侧重的病症不同；一个人的脸只在出现在全球的几个地方；对于手机设备的键盘，某些特定人群使用某些表情，而其他人不使用。）

- 标签相同特征不同：$\mathcal{P}(y)$相同，$\mathcal{P}(x|y)$不同；由于文化差异，天气影响，生活水平等因素，对于相同的标签$y$，对于不同的客户端可能对应着差异非常大的特征$x$。
（不同医疗设备的采样的特征不同；冬季停放的被大雪覆盖汽车的图像只会出现在某些地区。同样的品牌在不同的时间和不同的时间尺度上看起来也会有很大的不同：白天和晚上、季节效应、自然灾害、时尚设计潮流等等。）

- 特征相同标签不同：$\mathcal{P}_i(x)$相同，$\mathcal{P}(y|x)$不同；相同的特征，标准不同，所指代实体不同。由于个人偏好，训练数据项中的相同特征向量可能具有不同的标签。
（例如，反映情绪或单词联想的标签有着个人和地区差异。点头表示 yes/no）

#### 0.2.2 工程

- 大量不可靠设备
- 有限的通信带宽

### 0.3 概念与分类

#### 0.3.1 集中式分布式 vs.跨孤岛 vs. 跨设备

| | 数据集中式的分布式学习 | 跨库的联邦学习 | 跨设备的联邦学习 |
| ------------ | -------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------- |
| 设置 | 在大型但“扁平”的数据集上训练模型。客户端是单个群集或数据中心中的计算节点。 | 在数据孤岛上训练模型。客户是不同的组织（例如，医疗或金融）或地理分布的数据中心。 | 客户端是大量的移动或物联网设备 |
| 数据分布 | 数据被集中存储，可以在客户端之间进行混洗和平衡。任何客户端都可以读取数据集的任何部分。 | 数据在本地生成，并保持分散化。每个客户端都存储自己的数据，无法读取其他客户端的数据。数据不是独立或相同分布的。 | 与跨数据孤岛的数据分布一样 |
| 编排方式 | 中央式编排 | 中央编排服务器/服务负责组织培训，但从未看到原始数据。 | 与跨数据孤岛编排方式一样 |
| 广域通讯 | 无（在一个数据中心/群集中完全连接客户端）。 | 中心辐射型拓扑，中心代表协调服务提供商（通常不包含数据），分支连接到客户端。 | 与跨数据孤岛的广域通讯方式一样 |
| 数据可用性 | 所有客户端都是可用的 | 所有客户端都是可用的 | 在任何时候，只有一小部分客户可用，通常会有日间或其他变化。 |
| 数据分布范围 | 通常 1-1000 个客户端 | 通常 2-1000 个客户端 | 大规模并行，最多 $10^{10}$ 个客户端。 |
| 主要瓶颈 | 在可以假设网络非常快的情况下，计算通常是数据中心的瓶颈。 | 可能是计算和通信量 | 通信通常是主要的 瓶颈，尽管这取决于任务。通常，跨设备联合计算使用 wi-fi 或更慢的连接。 |
| 可解决性 | 每个客户端都有一个标识或名称，该标识或名称允许系统专门访问它。 | 与数据集中式的分布式学习一样 | 无法直接为客户建立索引（即不对用户进行标记）。 |
| 客户状态 | 有状态的-每个客户都可以参与到计算的每一轮中，不断地传递状态。 | 有状态的-每个客户都可以参与到计算的每一轮中，不断地传递状态。 | 高度不可靠-预计有 5％或更多的客户端参与一轮计算会失败或退出（例如，由于违反了电池，网络或闲置的要求而导致设备无法使用）。 |
| 客户可靠性 | 相对较少的失败次数 | 相对较少的失败次数。 | 无状态的-每个客户在一个任务中可能只参与一次，因此通常假定在每轮计算中都有一个从未见过的客户的新样本。 |
| 数据分区轴 | 数据可以在客户端之间任意分区/重新分区。 | 固定分区。能够根据样本分区（横向）或者特征分区（纵向）。 | 根据样本固定分区（横向）。 |

#### 0.3.2 联邦学习 vs 去中心化学习

| | 联邦学习 | 完全去中心化（点对点）学习 |
| -------- | ---------------------------------------------------------------------------- | -------------------------- |
| 编排方式 | 中央编排流程服务器或服务负责组织训练，但从未看到原始数据。 | 没有集中的编排流程。 |
| 宽域通信 | 中心辐射型拓扑，中心代表协调服务提供商（通常不包含数据），分支连接到客户端。 | 对等拓扑，带有动态连接图。 |

#### 0.3.3 模式三分类

[Yang Q, Liu Y, Chen T, et al. Federated machine learning: Concept and applications[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(2): 1-19.](https://arxiv.org/pdf/1902.04885.pdf)

- **横向联邦学习**

- 特征共享的联邦学习

- **纵向联邦学习**

- 样本共享的联邦学习

- **迁移联邦学习**

### 0.4 有效性

#### 0.4.1 联邦平均算法


#### 0.4.2 收敛性证明

- IID（独立同分布）情况：
$M$个无状态客户端参与每一轮 T，在每一轮中，每个客户端可以计算$K$个样本的梯度 $z_1,...,z_K$从$\mathcal{P}$中 IID 采样得到，客户端每个 mini-batch 与整个训练数据集分布相同，定义随机优化问题：

$$
\min\limits_{x\in\mathbb{R}}F(x):=\mathop{\mathbb{E}}\limits_{z\thicksim \mathcal{P}}[f(x;z)]
$$

对 $f$ 的不同假设会产生不同的保证

- 凸目标

假设$H-smooth$，确保对于所有$z,f(\cdot;z)$的可微性，则对于任意$x,y$有

$$
||\bigtriangledown f(x,z)-\bigtriangledown f(y,z)|| \leq H||x-y||
$$

对于所有的$x$，设置随机梯度$\bigtriangledown_x f(x;z)$的 bound：

$$
\mathop{\mathbb{E}}\limits_{z\thicksim P}||\bigtriangledown_x f(x;z)-\bigtriangledown F(x)|| \leq \sigma^2
$$

Baseline1：考虑$M$个客户端，每个客户端分别计算$K$个 mini-batch 上的梯度上界：

$$
\mathcal{O}\left(\frac{H}{T^{2}}+\frac{\sigma}{\sqrt{T K M}}\right)
$$

Baseline2：考虑 1 个客户端，连续执行$KT$步：

$$
\mathcal{O}\left(\frac{H}{(T K)^{2}}+\frac{\sigma}{\sqrt{T K}}\right)
$$

最优“统计”项$(\sigma / \sqrt{T K M})$，和最优“优化”项$(H/ (TK)^2)$。

- 非凸目标
（略）

- 讨论 Non-IID（非独立同分布）的情况：

$N$个客户端都拥有自己的本地数据分布$\mathcal{P}_i$和本地目标函数：

$$
f_{i}(x)=\underset{z \sim \mathcal{P}_{i}}{\mathbb{E}}[f(x ; z)]
$$

其中$f(x;z)$为模型$x$对于样本$z$的损失。我们通常希望最小化：

$$
F(x)=\frac{1}{N} \sum_{i=1}^{N} f_{i}(x)
$$

请注意，当$\mathcal{P}_i$是同分布的时候就是 IID 的设定。

### 0.5 平台

- [Federated AI Technology Enabler (FATE) 微众银行](https://github.com/FederatedAI/FATE)