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

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.