Alternating GD & Minimization (AltGDmin) for Fast Communication-Efficient Federated Learning

This talk describes the Alternating Gradient Descent (GD) and Minimization (AltGDmin) algorithm which provides a faster and more communication-efficient solution for many optimization problems for which Alternating Minimization (AltMin) is a popular solution. Consider the class of problems in which the set of optimization variables, Z, can be split into two parts. AltGDmin is more efficient than both AltMin and GD for any problem for which (i) the minimization over one set of variables is much quicker than that over the other set; and (ii) the cost function is differentiable w.r.t. the latter. Often, the reason for (i) is that the problem is at least partly “decoupled” and each of the decoupled problems is quick to solve. Important examples of partly decoupled problems include low rank column-wise matrix sensing (LRCS), low rank matrix completion (LRMC), data clustering, and unlabeled sensing. LRCS is a lesser known LR recovery problem that finds applications in multi-task representation learning, few-shot learning and dynamic MRI. AltGDmin was introduced in our recent work as a provably fast, communication-efficient, and sample-efficient GD-based approach for solving the LRCS problem. In ongoing work, we have also obtained sample and iteration complexity guarantees for AltGDmin for solving the LRMC problem and argued that it is a sample- and communication-efficient. We also demonstrate the advantage (speed and generality) of AltGDmin over the existing state-of-the-art for LRCS-based compressive dynamic MRI.