An Efficient Hierarchical Block Coordinate Descent Method for Time-Varying Graphical Lasso

Abstract

Time-varying graphical LASSO (TVGL) aims to infer a sequence of graphs from time series data and has been widely used in many statistical inference problems. The existing algorithms usually suffer from high computational cost when solving large-scale TVGL problems. In this paper, we develop an efficient and scalable hierarchical block coordinate descent (HBCD) method for solving TVGL with smooth temporal difference prior. The proposed HBCD method contains both outer-loop and inner-loop BCD iterations. The outer loops seperate the original TVGL problem into a sequence of subproblems, which are variants of the static graphical LASSO problems. Then, we propose an efficient BCD method to solve the inner-loop subproblems. We provide theoretical analysis that indicates the linear convergence of our proposed method. Furthermore, numerical experiments on both synthetic and real datasets show that our method significantly outperforms the state-of-the-art algorithm in terms of both the required iterations and CPU time to reach the target precision.