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

该项目设计了(完全)去中心化拜占庭攻击弹性算法，用于从“坏”(故意欠采样、丢失、离群值损坏或非线性)数据中学习低阶(LR)矩阵。特别是，我们重点研究了两个问题：LR列压缩感知和LR矩阵补全。对这些问题的有效解决方案可以使设计快速和节能的移动应用程序用于推荐系统设计，例如Netflix内容，以及用于在云上存储压缩视频/图像。在许多这样的设置中，没有中央协调节点，每个节点只能与其相邻节点通信。该项目还支持将联合国际的CyMath方案扩大到更多未得到充分服务的年级和中学生群体。CyMath是一个数学辅导项目，始于2020年，旨在为服务不足的K-12学生提供持续一年的支持和延伸，最终目标是培养在工程或其他数学密集型专业学习并茁壮成长的新一代学生。该项目开发了基于分布式交替投影梯度下降(GD)的可证明准确的算法，用于从“坏”数据中批量和动态学习LR矩阵。这涉及将未知的n x q秩r矩阵X分解为X=UB，其中U和B分别是具有r列和r行的矩阵。这里r n，q(低阶)。该方法通过以下方式交替地更新U和B：(A)在U上的一个投影GD步骤将B保持在其先前的值不变，以及(B)在B上最小化或Gd，将U保持在其最近的值不变。这里(A)表示在U上执行一个GD步，然后将输出投影到具有正交列的矩阵空间上。该投影对于确保矩阵范数保持有界是至关重要的。这种方法比其他方法--凸松驰法、交替最小化或直接将GD投影到X上--更快，也更高效。然而，其高效的去中心化版本的设计并不简单。原因是：(I)当使用UB因式分解时，代价函数是非凸的；以及(Ii)约束集(具有正交列的n×r矩阵的集合)也不是凸集。这排除了现有文献中关于分散投影GD的有效共识算法的思想的使用，几乎所有的算法都被设计用于解决无约束凸问题或具有凸代价和约束集的问题。该项目还为分散的LR恢复开发了一个新的解决方案框架，该框架对拜占庭攻击具有弹性。在集中式联合环境下，已经有一些关于拜占庭健壮的LR恢复的工作。然而，在完全分散的对抗性环境中的LR恢复问题几乎没有受到关注。这些更具挑战性，因为(I)现有的分散结果假设成本函数和约束是凸的；以及(Ii)在分散设置下，攻击稳健算法的设计要困难得多，例如，如果没有中央协调节点，平均中值无法轻松实施。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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 gradientDescent (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.