Optimization Online


Blessing of Massive Scale: Spatial Graphical Model Estimation with a Total Cardinality Constraint

Ethan Fang(xingyuan***at***princeton.edu)
Han Liu(hanliu***at***princeton.edu)
Mengdi Wang(mengdiw***at***princeton.edu)

Abstract: We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the l0-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.

Keywords: graphical models, l0-constraint method, nonconvex optimization, high-dimensional data, computational complexity

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 11/18/2015
Entry Accepted: 11/18/2015
Entry Last Modified: 11/18/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society