Fully Decentralized (Attack-)Resilient Dynamic Low-Rank Matrix Learning

Iowa State University, Ames IA

Investigators

Abstract

This project designs (fully) decentralized Byzantine attack-resilient algorithms for low-rank (LR) matrix learning from “bad” (deliberately undersampled, missing, outlier-corrupted or nonlinear) data. In particular, we focus on two problems: LR column-wise compressive sensing and LR matrix completion. Efficient solutions to these problems can enable the design of fast and power-efficient mobile applications for recommendation system design, e.g., for Netflix content, and for storing compressed videos/images on the cloud. In many of these settings, there is no central coordinating node, each node can only communicate with its neighboring nodes. The project also supports the expansion of the co-PI’s CyMath program to a larger group of under-served grade and middle school students. CyMath is a Math tutoring program started in 2020 to provide sustained year-long support and extension to under-served K-12 students, with the eventual goal of raising a new generation of students who pursue, and thrive in, Engineering or other Math-intensive majors. This project develops provably accurate decentralized alternating projected gradient Descent (GD) based algorithms for batch and dynamic LR matrix learning from “bad” data. These involve factorizing the unknown n x q rank-r matrix X as X=UB where U and B are matrices with r columns and rows respectively. Here r << n, q (low-rank). The approach alternatively updates U and B by (a) one projected GD step on U keeping B fixed at its previous value, and (b) minimization, or GD, over B keeping U fixed at its most recent value. Here (a) means one GD step on U followed by projecting the output onto the space of matrices with orthonormal columns. The projection is critical for ensuring that the matrix norms stay bounded. This approach is both significantly faster and more communication-efficient than competing methods – convex relaxation, alternating minimization, or projected GD on X directly. However, the design of its efficient decentralized version is not straightforward. The reason is: (i) when using the UB factorization, the cost functions are non-convex; and (ii) the constraint set (set of n x r matrices with orthonormal columns) is not a convex set either. This precludes the use of ideas from the existing literature on efficient consensus algorithms for decentralized projected GD, almost all of which are designed to either solve unconstrained convex problems or problems with convex costs and constraint sets. This project also develops a novel solution framework for decentralized LR recovery that is resilient to Byzantine attacks. There has been some work on Byzantine-robust LR recovery in the centralized federated setting. However, LR recovery problems in fully decentralized adversarial environments have received little attention. These are more challenging because (i) existing decentralized results assume convex cost functions and constraints; and (ii) the design of attack-robust algorithms is much harder in a decentralized setting, e.g., median-of-means cannot be easily implemented without a central coordinating node. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.