2020/12/03 by Antoine Dedieu, Miguel Lázaro-Gredilla, Dedieu, Antoine +3
Computer Science · Mathematics · #Advanced Graph Neural Networks #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2012.01744
openalex publication_date 2020/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of learning the underlying graph of a sparse Ising\nmodel with p nodes from n i.i.d. samples. The most recent and best\nperforming approaches combine an empirical loss (the logistic regression loss\nor the interaction screening loss) with a regularizer (an L1 penalty or an L1\nconstraint). This results in a convex problem that can be solved separately for\neach node of the graph. In this work, we leverage the cardinality constraint L0\nnorm, which is known to properly induce sparsity, and further combine it with\nan L2 norm to better model the non-zero coefficients. We show that our proposed\nestimators achieve an improved sample complexity, both (a) theoretically, by\nreaching new state-of-the-art upper bounds for recovery guarantees, and (b)\nempirically, by showing sharper phase transitions between poor and full\nrecovery for graph topologies studied in the literature, when compared to their\nL1-based state-of-the-art methods.\n