Byzantine-Resilient Federated Alternating Gradient Descent and Minimization for Partly-Decoupled Low Rank Matrix Learning

This work has two contributions. First, we introduce a provably secure (Byzantine-resilient) sample- and communication-efficient alternating gradient descent (GD) and minimization based algorithms for solving the federated low rank matrix completion (LRMC) problem. This involves learning a low rank (LR) matrix from a small subset of its entries. Second, we extend our ideas to show how a special case of our algorithms also solves another partly-decoupled vertically federated LR matrix learning problem, that is LR column-wise sensing (LRCS), also referred to as multi-task linear representation learning in the literature. Finally, we also show how our results can be extended for the LR phase retrieval problem. In all problems, we consider column-wise or vertical federation, i.e. each node observes a small subset of entries of a disjoint column sub-matrix of the entire LR matrix. For the LRMC problem, horizontal federation is equivalent since it is symmetric across rows and columns; while for the other two it is not. In all problems, the data at different nodes is heterogeneous (not identically distributed), making it harder to obtain provable guarantees.

Imagine you want to predict lung disease using chest X-rays collected from different hospitals. To protect patient privacy, each hospital trains a model locally and only shares updates. However, some hospitals might use unreliable or compromised systems that send incorrect updates. These issues, known as Byzantine failures, can harm the overall learning process.We developed a method called Byzantine Resilient Federated Alternating Gradient Descent that can still train accurate models even when several participants are Byzantine. It uses robust statistics and takes advantage of the low-rank structure in the data to learn in a sample efficient way.It works for many low rank matrix recovery problems. One useful example is a web-based recommender system that suggests movies to users based on their ratings and reviews. Our method also applies to compressed sensing, used in Magnetic Resonance Imaging to speed up scans. It also reduces training time by allowing large language models to be trained faster using multiple GPUs or servers.