Efficient Federated Low Rank Matrix Completion
This work addresses efficient matrix recovery in distributed environments, offering incremental improvements in communication and speed for federated learning applications.
The authors tackled the problem of low rank matrix completion in a federated setting by developing AltGDmin, a gradient descent-based method, which they proved to be the most communication-efficient and among the fastest solutions, with the second-best sample complexity among iterative approaches.
In this work, we develop and analyze a Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. LRMC involves recovering an $n \times q$ rank-$r$ matrix $\Xstar$ from a subset of its entries when $r \ll \min(n,q)$. Our theoretical guarantees (iteration and sample complexity bounds) imply that AltGDmin is the most communication-efficient solution in a federated setting, is one of the fastest, and has the second best sample complexity among all iterative solutions to LRMC. In addition, we also prove two important corollaries. (a) We provide a guarantee for AltGDmin for solving the noisy LRMC problem. (b) We show how our lemmas can be used to provide an improved sample complexity guarantee for AltMin, which is the fastest centralized solution.