次梯度算法硕士毕业论文

梯度的计算公式：gradu=aₓ（∂u/∂x）+aᵧ（∂u/∂y）+az（∂u/∂z）

梯度是一个向量（矢量），表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。

梯度是雅可比矩阵的一种特殊形式：

当m=1时函数的雅可比矩阵就是梯度，这个概念原是为场论设定的，任何场都可以用来理解梯度，后来被引用到数学中用来指明函数在指定点的变量率最快的方向和大小，是一种变化效率的数字抽象。

举一个降维的例子，在修建一个通向山顶的缆车时，从山顶到山底一条直线中间可能有山峰阻拦，一昧的修高山顶的到达站不仅不安全还会增加施工效率，在调整修建缆车的角度时的角度变化率就是梯度，角度太低了通不到山顶这个梯度方向角度就是零，方向导数就也是零。

一种基于随机梯度追踪技术的大数据二分类分布式优化方法，具体步骤为：设定二分类问题，获取训练样本数据、测试样本数据、样本特征；采用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次数。