Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach

• 成果类型: Article; Proceedings Paper
• 署名作者: Fang, Ethan X.; Liu, Han; Wang, Mengdi
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Princeton University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1331-z
• 发表日期: 2019
• 页码: 175-205
• 关键词: Consistency

摘要

We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the 0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this blessing of massive scale phenomenon. Motivated by this result, we propose an efficient algorithm to solve the dual problem (which is concave) and prove that the solution achieves optimal statistical properties. Extensive numerical results are also provided.