次梯度算法硕士毕业论文

一种基于随机梯度追踪技术的大数据二分类分布式优化方法，具体步骤为：设定二分类问题，获取训练样本数据、测试样本数据、样本特征；采用one‑hot编码将训练样本数据和测试样本数据扩展成向量数据，得到训练样本向量数据和测试样本向量数据；将训练样本向量数据进行智能体分配，结合梯度跟踪策略与随机平均梯度策略，建立带未知参数的分布式随机梯度跟踪策略S‑DIGing的问题模型；求解未知参数；将测试样本向量数据代入分布式随机梯度跟踪策略S‑DIGing的问题模型中进行二分类验证，并输出所述二分类问题对应的分布式随机梯度跟踪策略S‑DIGing的问题模型。极大降低了策略的复杂度和计算量，从而使S‑DIGing策略能够很好地处理大规模问题。响优化算法的收敛速度的问题，提出一种时延情形下的分布式Push-sum次梯度优化算法，该方法在权矩阵不具有正对角线元素时仍适用，并应用系统扩维的方法将有时延优化问题转化为无时延优化问题。在时延和次梯度有界且有向切换网络周期强连通的条件下，证明了所提出的分布式Push-sum次梯度优化算法的收敛性。研究表明：存在通信时延时的算法收敛速度比无时延时的收敛速度要慢，并具有较大的收敛误差。最后，通过数值仿真验证了研究的结论。

之前被论文里的 FedSGD 和 FedAvg (两个都是非常重要的算法)搞混，现在对他们总结一下。

FederatedSGD (or FedSGD)是指只有一个batch(a single batch)和Epoch数为1的算法。 令 B 和 E 分别对应与本地客户(lcoal client)的Batch-Size和Epoch数，那么FedSGD对应于 B=∞ 和 E=1 。 直观理解：传统的SGD算法可以看成是梯度更新速度最快的优化算法，因为每一个sample就更新一次梯度了，这里也是一样，FedSGD是应用FL时梯度或模型更新速度最快的算法，它只要求每个local client计算一次平均梯度就可以上传到central server进行加权平均了，所以它需要的 computation power 是最少的(the lowest)。这也是论文把他当做基线(baseline)的原因。

由此可知，只要 B≠∞ 和 E≠1 ，那么此时的算法就叫做 FedAvg 。而 FedAvg(FederatedAveraging ) 算法是指local client先在本地计算多次梯度并且更新权值，这时的计算成本是提升的。

或者说，该等式使得从原先的 上传梯度值( ) 模式变成了 上传模型( ) 模式了。

这就引出了上图的下半部分，即每个local client可以先在本地多次迭代更新模型 ，然后再上传到server上执行averaging step 即当我们使用 FedAvg 算法时，假设在 时刻，每个local client的模型为 (注意如果不加右上角的 则代表 时刻的全局模型)，则在 Epoch=E ， Batchsize=B 时，local client k的模型更新为 意思是模型 在将模型上传到server前本地更新了 次。 接着有 和 。 最后将在 时刻的全局模型 赋值给每个local client作为 时刻的新模型

有意思的是 ，可以把 FedAvg 算法看成是I/O过程中的缓冲机制(Buffer)，与其一点一点往上传，还不如收集多一点再网上传，这样可以有效减小I/O次数。