Local SGD Converges Fast and Communicates Little

Question:

Q:为什么SGD降低方差，可以提高收敛速率？

A:方差反应了梯度的波动，因此方差越小，说明梯度越集中，收敛就越快。

0x00 Abstract

受限于网络延迟和带宽限制，多节点的随机梯度下降很难实现收敛的线性加速；Local SGD可以实现，但是缺乏理论证明。
本文证明了Local SGD对凸优化问题的收敛速度，能达到SGD与节点数和批次大小的线性加速关系。通信轮数能减少到 $T^{1/2}$ （ $T$ 表示总轮数）。Local SGD也可用于异步参数更新。
Local SGD能用于大型深度学习模型的训练。

KEY WORDS: Local SGD,Theoretical, Speedup

0x01 Introduction

SGD的组成：

其中 $g_t$ 的期望就是函数 $f$ 对 $x_t$ 的求导( $f$ 是损失函数)。

parallel SGD：

用多个节点梯度的平均值，代替 $g_t$

每轮节点都要通信交换，通信成为瓶颈

Mini-batch parallel SGD:

增加计算-通信比

每次通信前，训练mini-batch次（增加分子）

当mini-batch太大时，性能会降低

This paper:

增加计算-通信比

降低通信频率（减少分母）

每个节点可以单独进行参数更新，经过一段时间全局更新一次

示例：one-hot SGD等

问题：

多久通信一次。（仍未解决）
理论上，采用平均值是否对凸优化函数有作用（即，K个节点是否比单节点快K倍）。（本论文）

贡献：

字母	含义	备注
$f_i$	单样本损失
$f$	损失函数	$L$ 光滑、 $\mu$ 强凸
$b$	mini-batch size
$K$	并行节点数
$H$	本地迭代周期	本地执行 $H$ 次，上传参数
$x^*$	最优解向量（权值）	$f^=f(x^)$
$T$	训练轮数	$[T]=\{0,1...,T\}$
$I_T$	聚合轮标记集合	$I_T \subseteq [T],T \in I_T$ , `if t in I,aggregation`
$\hat{x}_T$	经过 $T$ 轮的聚合参数

则本文有以下结论：

与Parallel SGD对比：减少 $H=O(\sqrt{T/(Kb)})$ 次聚合通信

与mini-batch SGD对比：实现了线性加速，但需要较少次的通信

增加计算-通信比：增加b、或H，当b和H较小时，可以起到线性加速，不能选择太大。

0x02 Local SGD

算法过程如下：

减少方差

方法	收敛速度 $O(t)$	备注
SGD	$\sigma^2/T$
Parallel SGD	$\sigma^2/(TK)$	$K$ 为并行度，相关的梯度，线性加速
Local SGD	？	需要证明 $K$ 个独立的梯度序列仍以 $\sigma^2/T$ 收敛