Provably Communication-Efficient Federated Robust Matrix Completion and PCA

Robust low rank matrix completion (LRMC) and PCA find important applications in computer vision, recommender system design, and, most recently, in new approaches to parameter-efficient fine-tuning of large language models (LLMs). In many of these applications, the data is either available in a federated fashion, or it is available centrally, but we need to distribute it in order to speed up computing. In both settings, there is a need for communication-efficient solutions. In this work, we introduce a novel solution approach and prove that it is $r$-times more communication efficient than, and order-wise as fast as, the fastest existing robust LRMC solution, while tolerating the same number of outliers and having comparable sample complexity (order-wise). Here $r$ denotes the rank of the unknown low rank matrix to be recovered. Our proposed solution relies on a multi-block generalization of the recently introduced Alternating Gradient Descent and Minimization (AltGDmin) framework, combined with a new application of a mergeable quantile sketching algorithm, KLL, for federated computation of the global row thresholds needed for outlier support estimation. We prove that the resulting federated algorithm converges under the same assumptions, and with the same outlier tolerance and sample complexity, as its centralized counterpart. Experiments on simulated data and on real videos corroborate our claims.