AAAIJan, 2024

FedNS: 快速草图牛顿算法用于联邦学习

PDF
TL;DR提出了一种名为 Federated Newton Sketch 方法（FedNS）的算法，通过通信 sketched square-root Hessian 来逼近中心化的 Newton's 方法，以此解决了 Hessian 矩阵的通信复杂性问题，实现了快速收敛率，并首次达到了超线性收敛率。
newton-type federated learning algorithmslinear convergencecommunication complexityfederated newton sketch methods (fedns)super-linear convergence rates
发现论文，激发创造
  • FedNew: 一种通信高效且隐私保护的联邦学习牛顿型方法

    本研究介绍了一种名为 FedNew 的新型框架，通过引入两级框架、替换传统方法中需要从客户端传输 Hessian 信息的环节等方式解决了低通信效率、低隐私性等问题，并使用随机量化等方式将通信开销显著降低，在实际数据集上的实验显示出了优于现有方法的性能。

    Jun, 2022

  • FedNL: 将牛顿类方法应用于联邦学习

    本研究提出了一族 Federated Newton Learn 方法，它不仅能够使用于广义线性模型，还可应用于压缩本地 Hessians 等通用收缩压缩算子，具有隐私增强和通信效率等优点，并以实验证明了其与关键基线相比具有卓越的通信复杂度。

    Jun, 2021

  • FedZeN：通过增量 Hessian 估计实现超线性零阶联邦学习

    本研究使用增量 Hessian 估计器在协同训练集中设计第一个估计全局目标曲率的零阶联邦学习算法，以达到超线性收敛，通过在 Stiefel 流形中对随机搜索方向进行采样以提高性能。我们通过使用同步的伪随机数生成器以一种通信高效和隐私保护的方式，在中央服务器上构建梯度和 Hessian 估计器。我们对我们的算法进行了理论分析，命名为 FedZeN，证明了具有高概率的局部二次收敛和全局线性收敛的零阶精度。数值模拟验证了超线性收敛速率，并表明我们的算法优于文献中可用的零阶联邦学习方法。

    Sep, 2023

  • Newton Sketch：一种具有线性二次收敛率的线性时间优化算法

    该研究提出了一种随机化的二阶优化方法 ——Newton Sketch，使用随机投影或子采样 Hessian 实现近似牛顿步。对于自共轭函数，该算法证明具有超线性收敛和指数高概率，与条件数和相关问题独立的收敛和复杂度保证。对于适当的初始化，即使在没有自共轭的情况下，也可以保证类似的保证对于强凸和光滑的目标。我们还描述了将我们的方法扩展到具有自共轭屏障的凸约束程序。我们讨论和说明了其应用于线性程序，带有凸约束的二次程序，逻辑回归和其他广义线性模型以及半定规划的扩展问题。

    May, 2015

  • Newton-Sketch 和子采样 Newton 方法的研究

    本文研究了在解决变量数量和数据点数量都很大的有限和最优化问题的 Newton 法的背景下，两种数据空间维数缩减方法：Hessian 子采样和随机 Hadamard 变换。通过一系列数字实验和 Hessian 子采样方法的复杂性分析，揭示了使用共轭梯度方法相对于随机梯度迭代方法的优势。

    May, 2017

  • SHED：一种基于增量 Hessian 特征向量共享的联邦学习牛顿类算法

    本研究提出了 SHED 算法，这是一种专门用于加速异构场景中的联邦学习的通信受限牛顿型算法，具有对非独立同分布数据分布的鲁棒性，处理了代理通信资源的异构性，并实现了超线性收敛。

    Feb, 2022

  • 大规模分布式学习中的拟牛顿更新

    开发了具有卓越统计分析、计算和通信效率的分布式拟牛顿（DQN）框架，无需 Hessian 矩阵倒置或通信，在小数次迭代下提供了统计效率的结果，强调与现有方法的差别在于对统计学性质的调查。

    Jun, 2023

  • FetchSGD: 基于草图技术的高效通信联邦学习算法

    本文介绍了一种名为 FetchSGD 的算法，该算法通过使用 Count Sketch 压缩模型更新，并利用 Sketch 合并性从众多工作者中组合模型更新来克服联合学习中的通信瓶颈和因稀疏客户参与而导致的收敛问题。我们证明了 FetchSGD 具有良好的收敛性能，并通过训练两个残差网络和一个 Transformer 模型来证明其实证效果。

    Jul, 2020

  • FAGH：使用近似的全局 Hessian 加速联邦学习

    本文提出了一种加速联邦学习训练的近似全局 Hessian 方法（FAGH），通过利用近似全局 Hessian 的曲率加速全局模型的收敛，从而减少通信轮次和训练时间，并在训练和测试损失以及测试准确率方面优于几种最先进的联邦学习训练方法。

    Mar, 2024

  • RSN：随机子空间牛顿法

    本研究提出了一种基于随机化草图的随机牛顿法，可以解决具有巨大维度的特征空间的学习问题，并通过开发全局线性收敛理论，证明了其有效性。

    May, 2019