When Edge Meets Learning: Adaptive Control for Resource-Constrained Distributed Machine Learning

2018年IEEE INFOCOM

人与人之间的差距不能一概而论…

0x00 Abstract

We analyze the convergence rate of distributed gradient descent from a theoretical point of view, based on which we propose a control algorithm that determines the best trade-off between local update and global parameter aggregation to minimize the loss function under a given resource budget. The performance of the proposed algorithm is evaluated via extensive experiments with real datasets, both on a networked prototype system and in a larger-scale simulated environment.

Key Words: Convergence Rate,Federated Learning, Resource Budget

0x01 INTRODUCTION

In this paper, we address the problem of how to efficiently utilize the limited computation and communication resources at the edge for the optimal learning performance.We consider a typical edge computing architecture where edge nodes are interconnected with the remote cloud via network elements, such as gateways and routers.

The frequency of global aggregation is configurable; one can aggregate at an interval of one or multiple local updates. Each local update consumes computation resource of the edge node, and each global aggregation consumes communication resource of the network. The amount of con- sumed resources may vary over time, and there is a complex relationship among the frequency of global aggregation, the model training accuracy, and resource consumption.

Main contributions:

We analyze the convergence rate of gradient-descent based distributed learning from a theoretical perspective, and obtain a novel convergence bound that incorporates non-i.i.d. data distributions among nodes and an arbitrary number of local updates between two global aggregations.
Using the above theoretical result, we propose a control algorithm that learns the data distribution, system dynamics, and model characteristics, based on which it dynamically adapts the frequency of global aggregation in real time to minimize the learning loss under a fixed resource budget.
Experiments

0x03 PRELIMINARIES AND DEFINITIONS

A.Loss Function

$F_i(w)= \frac{1}{|\mathcal{D_i}|}\sum_{j\in\mathcal{D_i}}f_j(w) \tag{1}\\$

$F(w)=\frac{\sum_{j\in\cup_i\mathcal{D_i}}f_j(w)}{|\cup_i\mathcal{D_i}|}=\frac{\sum_{i=1}^{N}D_iF_i(w)}{D} \tag{2}$

下标 $i$ 表示节点信息；没有下标的表示全局信息。

B.The Learning Problem

$w^*=argminF(w) \tag{3}$

找到权重的最优值，没有解析解，只能用梯度下降。

C.Distributed Gradient Descent

由联邦学习的特征可知，当本地一定轮数后，就会进行全局模型聚合。所以对节点上某次迭代来说，最后的模型要么就是单纯的本地训练模型，要么就是全局聚合的模型。

用 $\widetilde{w}_i(t)$ 表示第 $t$ 迭代获得模型参数：

$\begin{aligned} \widetilde{w}_i(t) = \left\{ \begin{array}{} w_i(t), \text{no aggregation is performed}\\ w(t),\text{aggregation is performed } \end{array} \right. \end{aligned}$

其中

$w_i(t)$ 是利用梯度下降计算：

$w_i(t) = \widetilde{w}_i(t-1) - \eta\nabla F_i(\widetilde{w}_i(t-1)) \tag{4}$

$w(t)$ 是带权聚合:

$w(t)=\frac{\sum_{i=1}^ND_iw_i(t)}{D} \tag{5}$

总共会执行 $T$ 次节点本地计算，每 $\tau$ 次聚合一次，所以整个训练过程会聚合 $\frac{T}{\tau}$ （为了方便，只考虑其为整数）,

The rationale behind Algorithm 1 is that when $\tau=1$ , i.e., when we perform global aggregation after every local update step, the distributed gradient descent (ignoring communication aspects) is equivalent to the centralized gradient descent, where the latter assumes that all data samples are available at a centralized location and the global loss function and its gradient can be observed directly. This is due to the linearity of the gradient operator.

0x04 PROBLEM FORMULATION

The notion of “resources” here is generic and can include time, energy, monetary cost etc. related to both computation and communication.

Therefore, a natural question is how to make efficient use of a given amount of resources to minimize the loss function of model training. For the distributed gradient-descent based learning approach presented above, the question narrows down to determining the optimal values of $T$ and $\tau$ , so that $F(w)$ is minimized subject to a given resource constraint for this learning task.

Formally, we define that each step of local update at all participating nodes consumes $c$ units of resource, and each step of global aggregation consumes $b$ units of resource,where $c≥0$ and $ b≥0$ are both real numbers.

For given $T$ and $\tau$ , the total amount of consumed resource is then $T(c+\frac{b}{\tau})$ . Let $R$ denote the total resource budget.

Further, the resource consumptions $c$ and $b$ can be time-varying in practice which makes the problem

even more challenging than (6) alone.

目标问题：

$\mathop{min}\limits_{\tau,T} F(w(T)) \tag{6}\\ s.t. T(c+\frac{b}{\tau}) \leq R$

0x05 CONVERGENCE ANALYSIS

A.Definitions

为了找出 $F(w(T))-F(w^*)$ 的上界，先引入一写定义：

$K=\frac{T}{\tau}$ ,表示整个训练过程有 $K$ 个间隔（interval）

$[k]\mathop{=}\limits^{def}[(k-1)\tau,k\tau]$ ，表示一个间隔

$v_{[k]}(t)$ :在区间 $k$ 的辅助参数向量

表示中心化梯度下降的，对集中式的梯度下降是研究比较多的，也是分布式梯度下降的性能天花板。

$v_{[k]}(t)=v_{[k]}(t-1)-\eta\nabla F(v_{[k]}(t-1)) \tag{7}$

此时的损失函数 $F(\cdot)$ 能够访问任何样本（解释了下图，为何 $F(v)$ 下降快）

观察上图：

在 $\tau$ 的整数倍(分割线处)，就会进行全局聚合，即 $\widetilde{w}_i((k-1)\tau)=w((k-1)\tau)$
在间隔界限上， $v_{[k]}((k-1)\tau)=w((k-1)\tau)$

这个图可以理解成为上帝视角，所以才能观测出连续的全局损失变化。

为了获得算法1的收敛界限需要分两步走：

获得每个间距 $[k]$ 的 $w(k\tau)$ 与 $v_{[k]}(k\tau)$ 的差距
将这个差距和 $v_{[k]}(t)$ 的收敛速度相结合，获得 $w(t)$ 的收敛速度

$v_{[k]}(t)$ 是集中式的梯度下降，收敛速度较容易获得，再加之某个时间段的积累差距，以此来估计 $w(t)$ 的速度

Lemma 1: $F(w)$ is convex, $\rho$ -Lipschitz, and $\beta$ -smooth.

$Proof$ : This is straightforward from Assumption 1, the definition of F(w), and triangle inequality.

Definition 1:(Gradient Divergence)

For any $i$ and $w$ , we define $\delta_i$ as an upper bound of $||\nabla F_i(w)-\nabla F(w)||$ ,i.e.,

$||\nabla F_i(w)-\nabla F(w)|| \leq \delta_i \tag{8}$

We also define $\delta = \frac{\sum_iD_i\delta_i}{D}$

B.Main Results

Theorem 1.

For any interval $[k]$ and $t\in[k]$ , we have

$||w(t)-v_{[k]}(t)|| \leq h(t-(k-1)\tau) \tag{9}$

where

$h(x)\mathop{=}\limits^{def} \frac{\delta}{\beta}((\eta\beta+1)^x-1)-\eta\beta x \tag{10}$

for any $x > 0$ . Furthermore, as $F (\cdot) $ is $\rho$ -Lipschitz, we have $F(w(t))-F(v_{[k]}(t))\leq\rho h(t-(k-1)\tau)$ .

$Proof$ ：数学归纳法，有空再细看

Theorem 2.

The convergence upper bound of Algorithm 1 after $T$ iterations is given by

$F(w(T))-F(w^*)\leq \frac{1}{T(\omega\eta(1-\frac{\beta\eta}{2})-\frac{\rho h(\tau)}{\tau\epsilon})} \tag{11}$

when the following conditions are satisfied:

$\eta\leq \frac{1}{\beta}$

$\omega\eta(1-\frac{\beta\eta}{2})-\frac{\rho h(\tau)}{\tau\epsilon} > 0$

$F(v_{[k]}(t))-F(w^*)\leq \epsilon$ for all $t$ and $k$ for which $v_{[k]}(t)$ is defined

$F(w(T))-F(w^*)\geq \epsilon$ Where $\epsilon >0$ and $\omega=min_k\frac{1}{||v_{[k]}((k-1)\tau)-w^*||}$

$Proof$ :没看。。。

0x06 CONTROL ALGORITHM

A.Approximate Solution to (6)

根据公式（6）和定理2,目标问题如下：

$\mathop{min}\limits_{\tau,T} \frac{1}{T(\omega\eta(1-\frac{\beta\eta}{2})-\frac{\rho h(\tau)}{\tau\epsilon})} \tag{12}\\ s.t. T\leq \frac{R\tau}{c\tau+b}$

当 $\eta$ 和 $\epsilon$ 设置的较小，能满足定理2的要求的时候，公式（12）可以转换成如下：

$\mathop{max}\limits_{\tau=1,2,3..} \frac{R\tau}{c\tau+b}(\omega\eta(1-\frac{\beta\eta}{2})-\frac{\rho h(\tau)}{\tau\epsilon}) \tag{13}\\ s.t. \text{Conditions 1, 3, 4 in Theorem 2}$

The optimal solution to (13) always satisfies condition 2 in Theorem 2, because $\tau=1$ (in which case $h(\tau) = 0$ ) yields the objective function to be positive and thus satisfying the condition.