CIF: Small: Efficient and Secure Federated Structure Learning from Bad Data

该项目开发安全的分布式算法，用于有效地解决医学成像和机器学习中出现的一大类优化问题。重要的例子包括加速磁共振成像(MRI)、产品推荐系统、计算机视觉(例如，遮挡去除或视频编辑)和生物信息学(未标记数据的分组)。重点放在快速的算法上，这些算法只需要传输少量数据，并且在数据稀缺的情况下运行良好。在所有现代应用中，算法速度是一个重要的关注点。在MRI中，它对于(接近)实时应用是必不可少的，例如介入性MRI或动态识别和纠正伪影，例如，如果患者在第一次扫描期间咳嗽，则重新扫描。样本效率对于加速MRI扫描或从极少数可用产品中了解用户对产品的评级至关重要。该项目还通过CyMath计划支持早期数学教育，该计划让热爱数学的研究生为三年级学生提供课后数学辅导支持。这个项目引入了一种新的解决方案框架，称为交替梯度下降(GD)和最小化，它为许多优化问题提供了更快、更高效的解决方案，其中交替最小化(Altmin)是一种流行的解决方案。特别是，对于任何在一个变量集上的最小化比在另一个变量集上的最小化要快得多的问题，它是有用的。从一个集合的仔细初始化开始，AltGDmin交替更新变量，对于较快的集合使用最小化，对于另一个集合使用梯度下降(GD)。通常，在某些变量上极小化速度快的原因是优化问题相对于这些变量是解耦的。这种分离还有助于在联合设置中保证每次迭代的通信效率和隐私。对一组变量使用最小化也有助于确保在每次算法迭代中有足够的误差衰减。这意味着，对于某些问题，例如低秩列侦听，AltGDmin在每次迭代中几乎与(因式分解)GD一样快且通信效率高，而收敛速度几乎与Altmin一样快。这使得它总体上比这两种类型的解决方案都要快。推导出特定问题的正确性保证。这些都决定了迭代复杂度和样本复杂度的理论界。要获得这些结果，需要开发新的证明技术，这可能是独立的兴趣。原因是AltGDmin既不是一种Altmin方法，也不是一种针对任何变量子集的标准GD算法。拜占庭弹性(安全)AltGDmin算法的设计和分析正在针对各种低级别和其他结构、恢复问题进行研究。该项目由计算机和信息科学局(CEISE)的计算和通信基金会(CCF)部门和既定的激励竞争研究计划(EPSCoR)联合资助。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project develops secure distributed algorithms for efficiently solving a large class of optimization problems that occur in medical imaging and machine learning. Important examples include accelerated magnetic resonance imaging (MRI), product recommender systems, computer vision (e.g., occlusion removal or video editing), and bioinformatics (grouping of unlabeled data). The focus is on algorithms that are fast, require communicating only small amounts of data, and work well in the data-scarce regime. Algorithm speed is an important concern in all modern applications. Within MRI, it is essential for (near) real-time applications such as interventional MRI or on the fly identification and correction of artifacts, e.g., re-scanning if the patient coughs during the first scan. Sample efficiency is critical for accelerating the MRI scan, or for learning user ratings of products from very few available ones. The project also supports Early Math education via the CyMath program, a program in which Math-loving graduate students provide after-school Math tutoring support for students as young as third graders. This project introduces a novel solution framework called alternating gradient descent (GD) and minimization that provides a faster and more communication-efficient solution for many optimization problems for which alternating minimization (AltMin) is a popular solution. In particular, it is useful for any problem for which the minimization over one set of variables is much quicker than that over the other set. Starting with a careful initialization for one set, AltGDmin alternately updates the variables using minimization for the quicker set and gradient descent (GD) for the other set. Often, the reason that the minimization is fast over some variables is that the optimization problem is decoupled with respect to these variables. This decoupling also helps guarantee per-iteration communication-efficiency and privacy in federated settings. The use of minimization for one set of the variables is also what helps ensure sufficient error decay in each algorithm iteration. This implies that, for certain problems such as low rank column-wise sensing, AltGDmin is almost as fast and as communication-efficient per iteration as (factorized) GD, while converging almost as quickly as AltMin. This makes it faster overall than both types of solutions. Problem-specific correctness guarantees are derived. These determine the theoretical bounds on the iteration complexity and the sample complexity. Obtaining these results requires the development of novel proof techniques that may be of independent interest. The reason is AltGDmin is neither an AltMin approach nor a a standard GD algorithm for any subset of variables. The design and analysis Byzantine resilient (secure) AltGDmin algorithms is being studied for various low rank, and other structure, recovery problems.This project is jointly funded by the Computing and Communications Foundations (CCF) division of the Computer and Information Sciences Directorate (CISE) and the Established Program to Stimulate Competitive Research (EPSCoR).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.