A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems

Patrick Hytla, Tran T. A. Nghia, Duy Nhat Phan, Andrew Rice · 2025

Read A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems by Patrick Hytla, Tran T. A. Nghia, Duy Nhat Phan, Andrew Rice (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12733.txt.

Introduction

Hytla, Nghia, Phan, and Rice present an algorithm for federated matrix completion in twenty twenty-five. Matrix completion predicts missing entries in a table of data. It underlies recommendation systems and other applications. Standard methods store all data in one place, which raises privacy and scale concerns.

In the federated setting, user data stay spread across many clients. Their method blends a multiplier based framework with randomized block updates and proximal gradient steps. It handles nonconvex and nonsmooth problems with many blocks. The authors prove convergence and give a rate for reaching a near stationary point. Tests on MovieLens and Netflix data beat prior methods in speed and test accuracy. The work is the first with such guarantees for this setting.

Catalog record

CREATORPatrick Hytla, Tran T. A. Nghia, Duy Nhat Phan, Andrew Rice
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-12733

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Linearized Alternating Direction Multiplier Method for Federated Matrix Completion Problems Patrick Hytla, Tran T. A. Nghia, Duy Nhat Phan, Andrew Rice Abstract Matrix completion is fundamental for predicting missing data with a wide range of applications in personalized healthcare, e-commerce, recommendation systems, and social network analysis. Traditional matrix completion approaches typically assume centralized data storage, which raises challenges in terms of computational efficiency, scalability, and user privacy. In this paper, we address the problem of federated matrix completion, focusing on scenarios where user-specific data is distributed across multiple clients, and privacy constraints are uncompromising. Federated learning 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 matrix completion problems, a novel algorithmic framework that combines the Alternating Direction Method of Multipliers with a randomized block-coordinate strategy and alternating proximal gradient steps. Unlike existing federated approaches, FedMC-ADMM effectively handles multi-block 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 𝒪 ( K − 1 / 2 ) \mathcal{O}(K^{-1/2}) , leading to a communication complexity of 𝒪 ⁡ ( ϵ − 2 ) \mathcal{O}(\epsilon^{-2}) for reaching an ϵ \epsilon -stationary point. This work is the first to establish these theoretical guarantees for federated matrix completion in the presence of multi-block 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. 1 1 footnotetext: University of Dayton Research Institute, University of Dayton, 300 College Park, Dayton, 45469, Ohio, USA; emails: {patrick.hytla,duynhat.phan,andrew.rice}@udri.udayton.edu 2 2 footnotetext: Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA; email: [email protected] 3 3 footnotetext: Author names are listed in alphabetical order. Keywords— Federated learning, matrix completion, alternating direction multiplier method 1 Introduction Incomplete data is a common challenge across numerous domains, from personalized healthcare [ 40 ] and e-commerce [ 39 , 32 , 23 ] to content streaming platforms [ 13 , 20 ] , sensor networks [ 2 ] , social network analysis [ 22 ] , and image processing [ 27 ] . For instance, in recommendation systems, user preferences for items are partially observed, leading to what is known as the matrix completion (MC) problem [ 23 ] . Addressing this challenge is essential for enabling accurate predictions and informed decision-making across these diverse applications. In a centralized setting, given an incomplete data matrix M\in\mathbb{R}^{m\times n} with missing entries, the goal of the MC problem is to find factors U\in\mathbb{R}^{m\times r} and V\in\mathbb{R}^{r\times n} such that M\approx UV . This task is commonly formulated as the following optimization problem \min_{U\in\mathcal{U},V\in\mathcal{V}}\hskip 9.24994pt\frac{1}{2}\|\mathcal{P}(M-UV)\|_{F}^{2}+R_{1}(U)+R_{2}(V), where \mathcal{P}:\mathbb{R}^{m\times n}\to\mathbb{R}^{m\times n} is the linear operator defined by \mathcal{P}(Z)_{ij}=Z_{ij} , for Z\in\mathbb{R}^{m\times n} if M_{ij} is observed and 0 otherwise. The sets \mathcal{U} and \mathcal{V} are constraints, while R_{1} and R_{2} are regularizers that impose specific structures on variables U and V , respectively. However, centralized data collection and processing face several challenges. Traditional MC methods demand extensive storage for observed data and substantial computational resources, particularly when working with large-scale datasets, leading to high resource costs. Moreover, these approaches often rely on single machines or small clusters, limiting scalability and efficiency in handling complex datasets. Privacy concerns further complicate centralized methods, especially in applications such as recommendation systems, where protecting sensitive user data is paramount [ 5 ] . Clients are often reluctant to share personal information, yet traditional matrix completion approaches assume full access to user activity data, creating a significant obstacle to adoption in privacy-sensitive contexts. To address these challenges, we investigate the MC problem in the federated learning (FL) format. In this setting, we consider p clients, where the i -th client holds a private data matrix M_{i}\in\mathbb{R}^{m_{i}\times n} , with no overlap between the matrices held by different clients. A central server coordinates the clients to collaboratively solve the following optimization problem without requiring them to share raw data: \displaystyle\min_{\begin{subarray}{c}\mathbf{U},V\end{subarray}} \displaystyle F(\mathbf{U},V):=\frac{1}{p}\sum_{i=1}^{p}F_{i}(M_{i},U_{i}V)+R(V), (1) \displaystyle\text{subject to} \displaystyle U_{i}\in\mathcal{U}_{i}\text{ for }i\in\{1,\ldots,p\},\hskip 9.24994ptV\in\mathcal{V}, where F_{i}(M_{i},U_{i}V) represents the local loss function of client i , R(V) is a regularizer imposing structure on the global variable V , and \mathcal{U}_{i}\subseteq\mathbb{R}^{m_{i}\times r} and \mathcal{V}\subseteq\mathbb{R}^{r\times n} are constraints. Here, \mathbf{U}=[U_{1};\ldots;U_{p}] contains client-specific variables, while V is a global variable shared across all clients. For example, in federated recommendation systems, each client i may represent a different user group, where M_{i} is the incomplete user-item rating matrix, U_{i} is the user profiles for client i , and V is the shared item attributes, see Figure 1 . Figure 1: The typical scenario of federated recommendation systems. Each client has their own user profiles and shares the same items. Solving the federated MC problem ( 1 ) is challenging due to its nonconvexity, non-smoothness, and multi-block structure, particularly when balancing communication efficiency and privacy preservation. Recent advances in federated algorithms based on the Alternating Direction Method of Multipliers (ADMM) have demonstrated efficiency and scalability, achieving state-of-the-art performance [ 18 , 9 , 46 , 31 ] . Building on this, we propose FedMC-ADMM (Federated Matrix Completion with randomized ADMM and proximal steps), a novel framework to address the MC problem in FL. Our approach integrates a revised ADMM with randomized block-coordinate updates and proximal steps, enabling efficient handling of multi-block variables, nonsmooth regularizers, and inexact subproblem solutions at the clients. This is the first method to incorporate randomized block-coordinate ADMM with proximal steps for the federated MC problem. From a theoretical perspective, under mild assumptions, we establish subsequential convergences of the algorithm, proving that every limit point of the generated sequence is almost surely a stationary point of ( 1 ). Furthermore, our analysis demonstrates that FedMC-ADMM achieves a convergence rate of \mathcal{O}(K^{-1/2}) near a stationary point and requires at most \mathcal{O}(\epsilon^{-2}) communication rounds to reach an \epsilon -stationary point. These results are particularly challenging to achieve for the nonconvex federated MC problem due to the interplay of nonconvexity, non-smoothness, and multi-block structures. Finally, we validate the practical efficacy of FedMC-ADMM through numerical experiments on real-world datasets, including MovieLens 1M, MovieLens 10M, and Netflix. The results highlight the algorithm’s capability to provide privacy-preserving, efficient, and scalable solutions for the MC problem in FL settings. 2 Related Work To date, existing FL algorithms have yet to address the general federated MC problem ( 1 ), which involves the challenges of nonconvexity, non-smoothness, and multi-block structures considered in this work. Accordingly, we discuss related literature on matrix completion, federated matrix factorization, and federated learning. Traditional matrix completion methods are primarily designed for centralized settings, assuming full access to the data. These classical approaches rely on low-rank matrix factorization to impute missing entries [ 23 , 28 , 16 ] . However, privacy concerns in matrix completion have recently gained attention. For instance, [ 8 ] introduced private alternating least squares to achieve practical matrix completion with tighter convergence rates, while [ 43 ] proposed a differentially private approach based on low-rank matrix factorization. In the context of federated MC problems, [ 14 , 6 ] explored

Read the complete text