Network-GIANT 的收敛性分析：一种基于近似海森矩阵的全分布式优化算法

《IEEE Transactions on Control of Network Systems》：On Convergence Analysis of Network-GIANT: An Approximate Hessian-Based Fully Distributed Optimization Algorithm

　　本文对一种近期开发的近似牛顿法完全分布式优化方法（称为Network-GIANT，灵感来源于具有混合线性-二次收敛特性的联邦学习算法GIANT）进行了详细的收敛性与性能分析，该方法适用于L-光滑、μ-强凸的局部损失函数。实证研究表明，Network-GIANT在保持与其一阶分布式对应方法相同通信复杂度（每迭代）的情况下，相比基于梯度的对应方法以及多种现有的二阶分布式算法，能够取得更快的线性收敛特性。我们首先显式地刻画了Network-GIANT的全局线性收敛速率，该速率可表示为一个依赖于L、μ以及底层无向图一致矩阵谱范数（σ）的3×3矩阵的谱半径。我们给出了步长参数η的一个显式上界，在此上界以下，该谱半径被保证小于1。此外，我们推导了一个基于混合线性-二次不等式的最优性间隙范数上界，并在海森近似误差γ<μ的条件下，严格证明了局部渐近收敛速率为1?η(1?γ/μ)，从而从理论上解释了network-giant更快收敛速率的原因。我们使用缩减的covtype数据集在多种图结构上（包括异构数据分布）进行二分类逻辑回归的数值实验，以验证上述理论结果。>