一种用于联邦矩阵补全问题的线性化交替方向乘子法

《IEEE Transactions on Neural Networks and Learning Systems》：A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems

针对联邦矩阵补全中数据分散和隐私保护的挑战，本文提出FedMC-ADMM算法，结合ADMM与随机块坐标策略，有效处理多块非凸和非光滑优化问题。理论分析表明其收敛速度为O(K^(?1/2))，通信复杂度为O(?^?2)，并在MovieLens和Netflix数据集上验证了算法在收敛速度和测试精度上的优势。

　　

摘要：

矩阵补全（Matrix Completion, MC）在预测缺失数据方面具有重要意义，其应用范围涵盖了个性化医疗、电子商务、推荐系统以及社交网络分析等多个领域。传统的矩阵补全方法通常假设数据存储是集中式的，这在计算效率、可扩展性和用户隐私方面存在挑战。在本文中，我们探讨了联邦式矩阵补全（Federated Matrix Completion）的问题，特别关注用户特定数据分布在多个客户端上的场景，并且需要在不牺牲隐私的前提下进行处理。联邦学习（Federated Learning, FL）提供了一个有前景的框架，通过支持在分布式数据集上进行协作学习来应对这些挑战，而无需共享原始数据。我们提出了FedMC-ADMM算法来解决联邦式矩阵补全问题，该算法结合了交替方向乘子法（Alternating Direction Method of Multipliers, ADMM）、随机块坐标策略以及交替近端梯度步骤。与现有的联邦学习方法不同，FedMC-ADMM能够有效处理多块非凸和非光滑优化问题，在保护用户隐私的同时实现高效计算。我们分析了该算法的理论特性，证明了其收敛性，并确定了其收敛速率为O(K^-1/2)，从而使得通信复杂度降低到O(?^-2)，最终能够收敛到?-稳定点。这是首次在存在多块变量的情况下为联邦式矩阵补全问题建立这些理论保证。为了验证我们的方法，我们在实际数据集（包括MovieLens 1M、10M和Netflix）上进行了广泛的实验，结果表明FedMC-ADMM在收敛速度和测试准确性方面均优于现有方法。