Sample-Efficient L0-L2 Constrained Structure Learning of Sparse Ising Models
Authors: Antoine Dedieu, Miguel Lázaro-Gredilla, Dileep George7193-7200
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Industry | Antoine Dedieu, Miguel L azaro-Gredilla, Dileep George Vicarious AI {antoine, miguel, dileep}@vicarious.com |
| Pseudocode | Yes | DFO algorithm: The DFO algorithm starts from an initialization w(1) and performs the following updates (for t 1) w(t+1) S w(t) 1 D f(w(t)); k; θ , until some convergence criterion is met. ... Continuation heuristic (1) Initialize ˆw(k1) by solving Problem (12) without the cardinality constraint. (2) For i = 2, . . . r, set θ = 2 ˆw(ki 1) 1. Set ˆw(ki) as the output of the DFO algorithm initialized with ˆw(ki 1), for ki and the above value of θ. |
| Open Source Code | Yes | Our code is available at https://github.com/antoine-dedieu/ structure learning sparse ising models |
| Open Datasets | No | We simulate n independent realizations from an Ising model with the above connectivity matrices. |
| Dataset Splits | Yes | We additionally generate a validation set of the same size than the training set, using the same W . |
| Hardware Specification | Yes | All the experiments were run on an Amazon Web Service c5.9 instance with 3.6GHz Xeon Platinum 8000 processor, 72GB of RAM. |
| Software Dependencies | No | The paper mentions using 'Python s scikit-learn package' and the 'SPGL1 algorithm (van den Berg and Friedlander 2008) using the software provided (van den Berg and Friedlander 2019)' but does not provide specific version numbers for these software dependencies. |
| Experiment Setup | Yes | For L1 LR: 'More precisely, we compute a family of estimators for a decreasing geometric sequence of 20 parameters λ1, . . . , λ20 with common ratio 0.5. We start from λ1 = 2 Xy for which the solution of Problem (5) is 0.' For L1Constr LR and L0-L2 LR: 'We use a stopping criterion ϵ = 10 3 and a maximum number of Tmax = 300 iterations.' |