Beijing-Saint Petersburg Mathematics Colloquium (online)
To Join Zoom Meeting: https://zoom.com.cn/j/63400804700?pwd=WTZEdlcrSzhodlBEejE5M2JkTG1BUT09
Meeting ID: 634 0080 4700
Password: 023440
Abstract
We propose and study a distributed and secure algorithm for computing dominant (or truncated) singular value decompositions (SVD) of large and distributed data matrices. We consider the scenario where each node privately holds a subset of columns and only exchanges “safe” information with other nodes in a collaborative effort to calculate a dominant SVD for the whole matrix. In the framework of alternating direction methods of multipliers (ADMM), we propose a novel formulation for building consensus by equalizing subspaces spanned by splitting variables instead of equalizing themselves. This technique greatly relaxes feasibility restrictions and accelerates convergence significantly, while at the same time yielding simple subproblems. We design several algorithmic features, including a low-rank multiplier formula and mechanisms for controlling subproblem solution accuracies, to increase the algorithm's computational efficiency and reduce its communication overhead. More importantly, unlike many existing distributed or parallelized algorithms, our algorithm preserves the privacy of locally-held data; that is, none of the nodes can recover the data stored in another node through information exchanged during communications. We present convergence analysis results, including a worst-case complexity estimate, and extensive experimental results indicating that the proposed algorithm, while safely guarding data privacy, has a strong potential to deliver a cutting-edge performance, especially when communication costs are high.
Bio
Dr. Xin Liu, professor of the Academy of Mathematics and Systems Science (AMSS), Chinese Academy Sciences (CAS). He got his bachelor degree from the School of Mathematical Sciences, Peking University in 2004, and PhD from the University of Chinese Academy of Sciences in 2009, under the supervision of Professor Ya-xiang Yuan. His research interests include the optimization problems over the Stiefel manifold, linear and nonlinear eigenvalue problems, nonlinear least squares and distributed optimization. Dr. Xin Liu is the principal investigator of four NSFC (National Science Foundation of China) grants including the Excellent Youth Grant. He was granted the Jingrun Chen Future Star Program from AMSS in 2014, the Science and Technology Award for Youth from The Operations Research Society of China (ORSC) in 2016, and the Fifth Chinese Society for Industrial and Applied Mathematics (CSIAM) Young Scholar Prize in 2020. He serves as an associate editor of “Mathematical Programming Computation”, “Asia-Pacific Journal of Operational Research”, “Journal of Computational Mathematics” and “Operations Research Transactions”.
