02/02/2021

Sample-Efficient L0-L2 Constrained Structure Learning of Sparse Ising Models

Antoine Dedieu, Miguel Lázaro-Gredilla, Dileep George

Keywords:

Abstract Paper Similar Papers

Abstract: We consider the problem of learning the underlying graph of a sparse Ising model with p nodes from n i.i.d. samples. The most recent and best performing approaches combine an empirical loss (the logistic regression loss or the interaction screening loss) with a regularizer (an L1 penalty or an L1 constraint). This results in a convex problem that can be solved separately for each node of the graph. In this work, we leverage the cardinality constraint L0 norm, which is known to properly induce sparsity, and further combine it with an L2 norm to better model the non-zero coefficients. We show that our proposed estimators achieve an improved sample complexity, both (a) theoretically, by reaching new state-of-the-art upper bounds for recovery guarantees, and (b) empirically, by showing sharper phase transitions between poor and full recovery for graph topologies studied in the literature, when compared to their L1-based state-of-the-art methods.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38947847
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 2:56 
 0
 0
 0
 0
 5:06 
 0
 0
 0
 0
 15:08 
 0
 1
 0
 0
 3:31 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 4:53 
 0
 0
 0
 0
 13:08 
 0
 0
 0
 0
 14:47 
 0
 0
 0
 0
 15:05 
 0
 0
 0
 0
 11:06 
 0
 0
 0
 0
 3:16 
 0
 0
 0
 0
 13:46 
 0
 0
 0
 0
 18:45 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 13:18 
 0
 0
 0
 0
 19:10 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 7:56 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 13:33 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 14:55 
 0
 0
 0
 0
 12:14 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 4:47 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 14:26 
 0
 0
 0
 0
 14:43 
 0
 0
 0
 0
 11:20 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 11:07 
 0
 0
 0
 0
 8:42 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 14:16 
 0
 0
 0
 0
 12:57 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 6:58