TY - JOUR
T1 - Blessing of massive scale
T2 - spatial graphical model estimation with a total cardinality constraint approach
AU - Fang, Ethan X.
AU - Liu, Han
AU - Wang, Mengdi
N1 - Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2019/7/1
Y1 - 2019/7/1
N2 - We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the ℓ-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.
AB - We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the ℓ-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.
UR - http://www.scopus.com/inward/record.url?scp=85054487884&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85054487884&partnerID=8YFLogxK
U2 - 10.1007/s10107-018-1331-z
DO - 10.1007/s10107-018-1331-z
M3 - Article
AN - SCOPUS:85054487884
SN - 0025-5610
VL - 176
SP - 175
EP - 205
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -