A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems.

Abstract

Matrix completion (MC) is fundamental for predicting missing data with a wide range of applications in personalized healthcare, e-commerce, recommendation systems, and social network analysis. Traditional MC approaches typically assume centralized data storage, which raises challenges in terms of computational efficiency, scalability, and user privacy. In this article, we address the problem of federated MC, focusing on scenarios where user-specific data is distributed across multiple clients, and privacy constraints are uncompromising. Federated learning (FL) provides a promising framework to address these challenges by enabling collaborative learning across distributed datasets without sharing raw data. We propose FedMC-ADMM for solving federated MC problems, a novel algorithmic framework that combines the alternating direction method of multipliers (ADMM) with a randomized block-coordinate strategy and alternating proximal gradient steps. Unlike existing federated approaches, FedMC-ADMM effectively handles multiblock nonconvex and nonsmooth optimization problems, allowing efficient computation while preserving user privacy. We analyze the theoretical properties of our algorithm, demonstrating subsequential convergence and establishing a convergence rate of $\mathcal {O}(K^{-1/2})$ , leading to a communication complexity of $\mathcal {O}(\epsilon ^{-2})$ for reaching an $\epsilon $ -stationary point. This work is the first to establish these theoretical guarantees for federated MC in the presence of multiblock variables. To validate our approach, we conduct extensive experiments on real-world datasets, including MovieLens 1M, 10M, and Netflix. The results demonstrate that FedMC-ADMM outperforms existing methods in terms of convergence speed and testing accuracy.