Academic Report
Title: Implementing the ADMM for big datasets: a case study of LASSO
Reporter: WANG Xiangfeng (East China Normal University)
Time: November 9, 2018 (Friday) PM 14:30-15:30
Location: A1101# room, Innovation Park Building
Contact: LIU Yongchao (tel:84708351-8141)
Abstract: The alternating direction method of multipliers (ADMM) has been extensively used in a wide variety of different applications. When large datasets with high-dimensional variables are considered, subproblems arising from the ADMM must be inexactly solved even though they may theoretically have closed-form solutions. Such a scenario immediately poses mathematical ambiguities such as how these subproblems should be accurately solved and whether the convergence can still be guaranteed. Although the ADMM is well known, it seems that these topics should be deeply investigated. In this paper, we study the mathematics of how to implement the ADMM for a large dataset scenarios. More specifically, we attempt to focus on the convex programming case where there is a quadratic function with extremely high-dimensional variables in the objective function of the model; thereby there is a huge-scale system for linear equations needing to be solved at each iteration of the ADMM. It is revealed that there is no need, indeed it is impossible, to exactly solve this linear system, and we attempt to propose an adjustable inexactness criterion to automatically and inexactly solve this linear system. We further attempt to identify the safe-guard number for the internally nested iterations that can sufficiently ensure this inexactness criterion if the linear system would be solved by a standard numerical linear algebra solver. The convergence, together with the worst-case convergence rate measured by the iteration complexity, is rigorously established for the ADMM with inexactly solved subproblems. Some numerical experiments for large datasets of the least absolute shrinkage and selection operator containing millions of variables are reported to show the efficiency of the mentioned inaccurate implementation of the ADMM.
The brief introduction to the reporter: Wang Xiangfeng, who graduated from the Department of Mathematics of Nanjing University in 2009, also received a Ph.D. in Science from the Department of Mathematics of Nanjing University in 2014. During his Ph.D. study, he received grants from the National Student Fund Committee to go to the University of Minnesota for joint training and to visit the Hong Kong Baptist University. After graduation, he joined the School of Computer Science and Software Engineering, East China Normal University. His main research interests are large-scale optimization algorithm design and theoretical analysis, and its application in machine learning (machine learning driven non-convex optimization, optimal transmission). He has published more than 20 papers in Mathematical Programming (MP), SIAM Journal on Scientific Computing(SISC), Mathematics of Operations Research(MOR) and other journals of mathematical programming and computational mathematics and IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI), IEEE Transactions on Signal Processing(TSP), Neurocomputing and other Journals of machine learning and signal processing applications.
