Speaker:Namrata Vaswani

Title

AltGDmin: Alternating GD & Minimization for Fast Federated Low Rank Matrix Learning 

Abstract

We introduce a novel algorithmic framework called Alternating gradient descent (GD) & Minimization (AltGDmin) that provides a time-, communication-, and sample- efficient solution framework for solving various low rank matrix learning problems in federated settings. AltGDmin factorizes the unknown low rank (LR) matrix as X = U B where U and B are tall and broad matrices with r columns and rows respectively. After a spectral initialization for U, it alternates between a minimization step for updating B and a (projected) GD step for updating U. AltGDmin is efficient for classes of optimization problems that are decoupled for B; this means that subsets of columns of B depend only on subsets of the observed/measured/sketched data. Two examples of this type of problems are LR column-wise sensing (LRCS) and LR matrix completion.   

In this talk we will focus on LRCS which involves recovering an n x q rank-r matrix X, with rank r << n,q, from column-wise sketches y_k := A_k x_k, for  k=1,2…q. Each y_k is an m-length vector with m < n. For this problem, per iteration, AltGDmin is as fast as projected GD because the minimization over B decouples column-wise. At the same time, we can prove exponential error decay for it with a sample complexity of only order (n r^2) times a log factor, which we are unable to for projected GD. Also, it is private and can also be efficiently federated with a memory/communication cost of only nr per node, instead of nq for projected GD. In follow-up work, we have demonstrated the practical power (speed and accuracy) of AltGDmin over existing approaches for accelerated dynamic MRI.  

(This talk is based on joint work with my former and current students Seyedehsara Nayer and Silpa Babu) 

About Namrata Vaswani

 Namrata Vaswani received a Ph.D. from the University of Maryland, College Park in 2004 and a B.Tech from IIT-Delhi in India in 1999. Since Fall 2005, she has been with the Iowa State University where she is currently the Anderlik Professor of Electrical and Computer Engineering. Her research interests lie in data science, with a particular focus on Statistical Machine Learning and Signal Processing. She also directs the CyMath program at Iowa State in which graduate students volunteer to provide school-year-long math tutoring to under-served K-12 students.  

Vaswani has served as an Associate Editor or Area Editor for multiple IEEE journals: IEEE Transactions on Information Theory, IEEE Transactions on Signal Processing, and the Signal Processing Magazine. She has also guest-edited special issues for Proceedings of the IEEE and the IEEE Journal of Selected Topics in Signal Processing. Vaswani is a recipient of the 2014 IEEE Signal Processing Society Best Paper Award, the Iowa State Early Career Engineering Faculty Research Award (2014), the Iowa State Mid-Career Achievement in Research Award (2019). She is a Fellow of the IEEE since 2019.