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.

In this work we develop a communication-efficient Byzantine-resilient algorithm for vertically federated multi-task linear representation learning, also known as low rank column-wise compressive sensing (LRCS). Our algorithm is a geometric median based resilient modification of the alternating gradient descent (GD) and minimization (altGDmin) algorithm. In case of vertically federated LRCS, the data at the different nodes is not identically distributed (heterogeneous data setting) making it harder to solve than the horizontal case which involves homogeneous data at different nodes. Under a simple heterogeneity bound on the model parameters, and a sample complexity bound that is worse than the optimal by a factor of r (r is the rank of the unknown matrix to be recovered), we are able to show that, with high probability (w.h.p.), the subspace distance between the estimate provided by our algorithm and the span of the true unknown Low Rank (LR) matrix decays exponentially with iterations until it reaches the heterogeneity bound. To our best knowledge, our result is the first LR matrix recovery result that provides a Byzantine resilient solution in the heterogenous data setting. Ideas developed here should be extendable to other heterogenous federated LR recovery problems such as LR matrix.

This work introduces a Byzantine resilient solution for learning low-dimensional linear representation. Our main contribution is the development of a provably Byzantine-resilient AltGDmin algorithm for solving this problem in a federated setting. We argue that our solution is sample-efficient, fast, and communicationefficient. In solving this problem, we also introduce a novel secure solution to the federated subspace learning meta-problem that occurs in many different applications.

This work studies the problem of reliably estimating a subspace in a federated setting, when some nodes' outputs can be compromised by Byzantine attacks. Typically, the subspace of interest is the principal subspace of an unknown symmetric matrix. Each node has access to data that can be used to estimate this matrix and its principal subspace. This meta-problem occurs in various applications; two important examples are federated PCA, and the spectral initialization step of iterative solutions to various low-rank (LR) matrix recovery problems in federated settings. We introduce a novel solution framework called Subspace- Median to solve this problem in a provably Byzantine-resilient, and communication-efficient fashion.

This work considers two related learning problems in a federated attack-prone setting – federated principal components analysis (PCA) and federated low rank column-wise sensing (LRCS). The node attacks are assumed to be Byzantine which means that the attackers are omniscient and can collude. We introduce a novel provably Byzantine-resilient communication-efficient and sample-efficient algorithm, called Subspace-Median, that solves the PCA problem and is a key part of the solution for the LRCS problem. We also study the most natural Byzantine-resilient solution for federated PCA, a geometric median based modification of the federated power method, and explain why it is not useful. Our second main contribution is a complete alternating gradient descent (GD) and minimization (altGDmin) algorithm for Byzantine-resilient horizontally federated LRCS and sample and communication complexity guarantees for it. Extensive simulation experiments are used to corroborate our theoretical guarantees. The ideas that we develop for LRCS are easily extendable to other LR recovery problems as well.

Recent advancements in federated learning have inspired the emergence of federated reinforcement learning, wherein multiple agents learn a policy in a federated manner without sharing trajectories. However, one of the key challenges in federated learning lies in dealing with adversarial attacks, such as Byzantine attacks. This work addresses this challenge by introducing the GM-FedREINFORCE algorithm, which extends the REINFORCE method-an established policy gradient technique-and provides robust theoretical guarantees on its convergence even in the face of adversarial attacks. We do this by replacing the mean step of GD by Geometric median. Remarkably, our algorithm remains effective when less than half of the agents are under attack, ensuring robust learning. To validate our theoretical claims, we conducted empirical experiments on benchmark RL environments with both discrete and continuous action spaces. Specifically, we employed the Cart-Pole environment to evaluate discrete action spaces and the Cart-Pole Swing-Up environment to assess continuous action spaces. Our experimental results confirm the effectiveness of our algorithm, showcasing its ability to successfully learn policies even under Byzantine attacks.