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

该项目设计了（完全）分散的拜占庭攻击弹性算法，用于从“坏”（故意欠采样，缺失，异常损坏或非线性）数据中学习低秩（LR）矩阵。特别是，我们专注于两个问题：LR列式压缩感知和LR矩阵完成。对这些问题的有效解决方案可以使得能够设计用于推荐系统设计的快速且功率高效的移动的应用，用于Netflix内容，以及用于在云上存储压缩视频/图像。在许多这些设置中，没有中央协调节点，每个节点只能与其相邻节点通信。 该项目还支持将co-PI的CyMath计划扩展到更大的服务不足的年级和中学生群体。CyMath是一个数学辅导计划，始于2020年，为服务不足的K-12学生提供持续一年的支持和扩展，最终目标是培养新一代追求并在工程或其他数学密集型专业中茁壮成长的学生。该项目开发了可证明准确的分散式交替投影梯度下降（GD）算法，用于从“坏”数据中进行批量和动态LR矩阵学习。这些涉及将未知的n x q秩r矩阵X分解为X=UB，其中U和B分别是具有r列和r行的矩阵。这里r n，q（低秩）。该方法通过（a）在U上的一个投影GD步骤，保持B固定在其先前值，以及（B）在B上的最小化，或GD，保持U固定在其最近值，交替地更新U和B。这里（a）表示在U上的一个GD步骤，然后将输出投影到具有正交列的矩阵空间上。投影对于确保矩阵范数保持有界至关重要。 这种方法比竞争方法-凸松弛，交替最小化或直接在X上投影GD-更快，更有效。然而，其高效分散版本的设计并不简单。原因是：（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.