针对联邦学习中通信带宽受限、计算资源不足及数据异构性等核心挑战,本文提出一种基于方差缩减的联邦对称交替方向乘子法(variance-reduced federated symmetric alternating direction method of multipliers,FedSADMM-VR)。该方法以对称交替方向乘子法为基本框架,引入周期通信策略以降低通信成本,并通过对线性化子问题引入方差缩减随机梯度进行非精确求解,从而有效降低本地计算复杂度与总通信成本。此外,算法在本地更新过程中对称地执行对偶变量更新,以缓解对偶变量滞后导致的信息偏差,增强模型在非独立同分布数据下的稳定性。理论分析表明,在非凸情形下,该算法无需有界梯度差异假设即可实现次线性收敛率。在合成数据、a9a、phishing与FEMNIST数据集上的实验表明,FedSADMM-VR在减少通信轮数的同时仍能保持有效的测试精度,并在非独立同分布数据环境下表现出较好的收敛稳定性。
To address the core challenges of limited communication bandwidth, insufficient computational resources, and data heterogeneity in federated learning, this paper proposes a variance-reduced federated symmetric alternating direction method of multipliers, termed FedSADMM-VR. Built upon the Symmetric ADMM framework, the proposed method introduces a periodic communication strategy to reduce communication overhead, and employs variance-reduced stochastic gradients to inexactly solve linearized subproblems, thereby effectively lowering both the local computational complexity and the overall communication cost. Furthermore, the algorithm performs symmetric dual variable updates during the local update process, which mitigates the information bias induced by dual variable staleness and enhances the stability of the model under non-independent and identically distributed data. Theoretical analysis establishes that, in the non-convex setting, the algorithm achieves a sublinear convergence rate without requiring the bounded gradient dissimilarity assumption. Experimental results on synthetic data and the a9a, phishing, and FEMNIST datasets demonstrate that FedSADMM-VR can maintain effective test accuracy while reducing the number of communication rounds, and exhibits relatively stable convergence behavior under non-independent and identically distributed data settings.
[1] McMahan B, Moore E, Ramage D, et al. Communication-efficient learning of deep networks from decentralized data [C]//Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017: 1273-1282.
[2] Sheller M J, Edwards B, Reina G A, et al. Federated learning in medicine: facilitating multiinstitutional collaborations without sharing patient data [J]. Scientific Reports, 2020, 10(1): 12598.
[3] Hard A, Rao K, Mathews R, et al. Federated learning for mobile keyboard prediction [PP/OL]. (2018-11-08)[2026-04-10]. https://arxiv.org/abs/1811.03604.
[4] Stich S U, Cordonnier J B, Jaggi M. Sparsified SGD with memory [C]//Advances in Neural Information Processing Systems, 2018, 31: 4452-4463.
[5] Di S, Tao D, Liang X, et al. Efficient lossy compression for scientific data based on pointwise relative error bound [J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(2): 331-345.
[6] Haddadpour F, Kamani M M, Mokhtari A, et al. Federated learning with compression: unified analysis and sharp guarantees [C]//Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021: 2350-2358.
[7] Defazio A, Bach F, Lacoste-Julien S. SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives [C]//Advances in Neural Information Processing Systems, 2014, 27: 1646-1654.
[8] Johnson R, Zhang T. Accelerating stochastic gradient descent using predictive variance reduction [C]//Advances in Neural Information Processing Systems, 2013, 26: 315-323.
[9] Nguyen L M, Liu J, Scheinberg K, et al. SARAH: a novel method for machine learning problems using stochastic recursive gradient [C]//International Conference on Machine Learning, 2017: 2613-2621.
[10] Li T, Sahu A K, Zaheer M, et al. Federated optimization in heterogeneous networks [J]. Proceedings of Machine Learning and Systems, 2020, 2: 429-450.
[11] Karimireddy S P, Kale S, Mohri M, et al. SCAFFOLD: stochastic controlled averaging for federated learning [C]//International Conference on Machine Learning, 2020: 5132-5143.
[12] Zhang X, Hong M, Dhople S, et al. FedPD: a federated learning framework with adaptivity to non-IID data [J]. IEEE Transactions on Signal Processing, 2021, 69: 6055-6070.
[13] Wang H, Marella S, Anderson J. FedADMM: a federated primal-dual algorithm allowing partial participation [C]//2022 IEEE 61st Conference on Decision and Control, 2022: 287-294.
[14] Zhou S, Li G Y. Federated learning via inexact ADMM [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(8): 9699-9708.
[15] Zhang X, Khalili M M, Liu M. Improving the privacy and accuracy of ADMM-based distributed algorithms [C]//International Conference on Machine Learning, 2018: 5796-5805.
[16] Zheng Z, Song L, Han Z, et al. A Stackelberg game approach to proactive caching in largescale mobile edge networks [J]. IEEE Transactions on Wireless Communications, 2018, 17(8): 5198-5211.
[17] Elgabli A, Park J, Ahmed S, et al. L-FGADMM: layer-wise federated group ADMM for communication efficient decentralized deep learning [C]//2020 IEEE Wireless Communications and Networking Conference, 2020: 1-6.
[18] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators [J]. SIAM Journal on Numerical Analysis, 1979, 16(6): 964-979.
[19] Peaceman D W, Rachford H H Jr. The numerical solution of parabolic and elliptic differential equations [J]. Journal of the Society for Industrial and Applied Mathematics, 1955, 3(1): 28-41.
[20] Driggs D, Tang J, Liang J, et al. A stochastic proximal alternating minimization for nonsmooth and nonconvex optimization [J]. SIAM Journal on Imaging Sciences, 2021, 14(4): 1932-1970.
[21] Wang J, Liu Q, Liang H, et al. Tackling the objective inconsistency problem in heterogeneous federated optimization [J]. Advances in Neural Information Processing Systems, 2020, 33: 7611-7623.
北大中文核心期刊