GLAD: Learning Sparse Graph Recovery
Authors: Harsh Shrivastava
Xinshi Chen
Binghong Chen
Guanghui Lan
Srinivas Aluru
Han Liu
Le Song
Venue:  (2020)
Keywords: Meta learning
automated algorithm design
learning structure recovery
Gaussian graphical models

Abstract: Recovering sparse conditional independence graphs from data is a fundamental problem in machine learning with wide applications. A popular formulation of the problem is an $\ell_1$ regularized maximum likelihood estimation. Many convex optimization algorithms have been designed to solve this formulation to recover the graph structure. Recently, there is a surge of interest to learn algorithms directly based on data, and in this case, learn to map empirical covariance to the sparse precision matrix. However, it is a challenging task in this case, since the symmetric positive definiteness (SPD) and sparsity of the matrix are not easy to enforce in learned algorithms, and a direct mapping from data to precision matrix may contain many parameters. We propose a deep learning architecture, GLAD, which uses an Alternating Minimization (AM) algorithm as our model inductive bias, and learns the model parameters via supervised learning. We show that GLAD learns a very compact and effective model for recovering sparse graphs from data.

Published as a conference paper at ICLR 2020
GLAD: LEARNING SPARSE GRAPH RECOVERY
Harsh Shrivastava' Srinivas Aluru!
Xinshi Chen?
Binghong Chen'
Guanghui Lan
Han Liu
Le Song
{ School of Computational Science & Engineering, "School of Mathematics, 3 School of Industrial and Systems Engineering aat Georgia Institute of Technology, *Computer Science Department at Northwestern University, AAn Financial Services Group
ABSTRACT
Recovering sparse conditional independence graphs from data is fundamental problem in machine learning with wide applications. A popular formulation the problem is an & regularized maximum likelihood estimation. Many convex optimization algorithms have been designed to solve this formulation to recover the graph structure. Recently, there is a surge of interest learn algorithms directly based on data, and in this case, learn to map empirical covariance to the sparse precision matrix. However, it is challenging task in this case, since the symmetric positive definiteness (SPD) and sparsity of the matrix are not easy to enforce in learned algorithms, and a direct mapping from data to precision matrix may contain many parameters. We propose deep learning architecture, GLAD, which uses Alternating Minimization (AM) algorithm as our model inductive bias, and learns the model parameters via supervised learning. We show that GLAD learns very compact and effective model for recovering sparse graphs from data.
INTRODUCTION
Recovering sparse conditional independence graphs from data is a fundamental problem in high dimensional statistics and time series analysis, and it has found applications in diverse areas. In computational biology, a sparse graph structure between gene expression data may be used to understand gene regulatory networks; in finance, sparse graph structure between financial time- series may be used to understand the relationship between different financial assets. A popular formulation of the problem is an & regularization log-determinant estimation of the precision matrix. Based on this convex formulation, many algorithms have been designed to solve this problem efficiently, and one can formally prove that under list of conditions, the solution of the optimization problem is guaranteed to recover the graph structure with high probability.
However, convex optimization based approaches have their own limitations. The hyperparameters. such as the regularization parameters and learning rate, may depend on unknown constants, and need to be tuned carefully achieve the recovery results. Furthermore, the formulation uses single regularization parameter for all entries in the precision matrix, which may not be optimal. It is intuitive that one may obtain better recovery results by allowing the regularization parameters to vary across the entries in the precision matrix. However, such flexibility will lead to quadratic increase in the number of hyperparameters, but it is hard for traditional approaches to search over a large number of hyperparameters. Thus, new paradigm may be needed for designing more effective sparse recovery algorithms.
Recently, there has been a surge of interest in new paradigm of algorithm design, where algorithms are augmented with learning modules trained directly with data, rather than preseribing every step of the algorithms. This is meaningful because very often family of optimization problems needs to be solved again and again, similar in structures but different in data. A data-driven algorithm may be able to leverage this distribution of problem instances, and learn algorithm which performs better than traditional convex formulation. In our case, the sparse graph recovery problem may also need be solved again and again, where the underlying graphs are different but have similar degree distribution, the magnitude of the precision matrix entries, etc. For instance, gene regulatory networks may be rewiring depending the time and conditions, and we want estimate them from gene

---

Published as a conference paper at ICLR 2020
expression data. Company relations may evolve over time, and we want to estimate their graph from stock data. Thus, we will also explore data-driven algorithm design in this paper.
Given task (e.g. optimization problem), an algorithm will solve it and provide solution. Thus we can view an algorithm as a function mapping, where the input is the task-specific information (i.e. the sample covariance matrix in our case) and the output is the solution (i.e. the estimated precision matrix in our case). However, it is very challenging to design a data-driven algorithm for precision matrix estimation. First, the input and output of the problem may be large. A neural network parameterization of direct mapping from the input covariance matrix to the output precision matrix may require as many parameters as the square of the number of dimensions. Second, there are many structure constraints in the output. The resulting precision matrix needs to be positive definite and sparse, which is not easy to enforce by a simple deep learning architecture. Third, direct mapping may result in model with lots of parameters, and hence may require lots of data to learn. Thus data-driven algorithm needs to be designed carefully achieve a better bias- variance trade-off and satisfy the output constraints.
In this paper, we propose a deep learning model 'GLAD' with following attributes:
Uses an unrolled Alternating Minimization (AM) algorithm as an inductive bias.
The regularization and the square penalty terms are parameterized as entry-wise functions of intermediate solutions, allowing GLAD to learn to perform entry-wise regularization update.
Furthermore, this data-driven algorithm is trained with collection of problem instances in supervised fashion, by directly comparing the algorithm outputs to the ground truth graphs.
In our experiments, we show that the AM architecture provides very good inductive bias, allowing the model learn very effective sparse graph recovery algorithm with small amount of training data. In all cases, the learned algorithm can recover sparse graph structures with much fewer data points from a new problem, and it also works well in recovering gene regulatory networks based on realistic gene expression data generators.
Related works, [Belilovsky et al. (2017) considers CNN based architecture that directly maps empirical covariance matrices to estimated graph structures. Previous works have parameterized optimization algorithms as recurrent neural networks or policies in reinforcement learning. For instance, Andrychowicz al. (2016) considered directly parameterizing optimization algorithm as an RNN based framework for learning to learn. Li & Malik (2016) approach the problem of automating algorithm design from reinforcement learning perspective and represent any particular optimization algorithm as a policy. Khalil et al. (2017) learn combinatorial optimzation over graph via deep Q-learning. These works did not consider the structures of sparse graph recovery problem. Another interesting line of approach is to develop deep neural networks based on unfolding an iterative algorithm Gregor & LeCun (20TO); Chen et al. (2018); Liu et al. (2018). Liu et al. (2018) developed ALISTA which is based on unrolling the Iterative Shrinkage Thresholding Algorithm (ISTA). (Sun al. (2016) developed 'ADMM-Net', which also developed for compressive sensing of MRI data. Though these seminal works were primarily developed for compressive sensing applications, they alluded to the general theme of using unrolled algorithms as inductive biases. We thus identify suitable unrolled algorithm and leverage its inductive bias to solve the sparse graph recovery problem.
SPARSE GRAPH RECOVERY PROBLEM AND CONVEX FORMULATION
Given m observations of d-dimensional multivariate Gaussian random variable X = [X,,...,Xa) the sparse graph recovery problem aims to estimate its covariance matrix Σ and precision matrix O* - - The ij-th component of O* is zero if and only if X; and X; are conditionally inde- pendent given the other variables (Xt ke Therefore, is popular to impose an & regularization for the estimation of O' to increase its sparsity and lead to easily interpretable models. Following Banerjee et al. (2008), the problem is formulated as the E reggullarieedd maximum likelihood estimation
e arg mingess. - log(det +) + tr (Ze) + p +1[@)]
(1)
where is the empirical covariance matrix based on m samples, S is the space of x symmetric
positive definite matrices (SPD), and ||0|l, = Eey, [0,, is the off-diagonal E regularizer with regularization parameter p. This estimator is sensible even for non-Gr non-Gausseee Gaussian X, since is minimizing an l pennalize log determinant Bregman divergence Ravikumar et al. (2011). The sparse precision matrix estimation problem in Eq. (I) is a convex optimization problem which can be solved by many algorithms. We give few canonical and advanced examples which are compared in our experiments:
2

---

Published as a conference paper at ICLR 2020
G-ISTA. G-ISTA is proximal gradient method, and updates the precision matrix iteratively Ob+1 < (0, Ex(E 0)²)), where [xx()],; == sign(X,;)( p)+. The step sizes Ç. is determined by line search such that ①x+1 SPD matrix Rolís et al. (2012).
ADMM. Alternating direction methods of multiplier (Boyd et al. 2011 transform the problem into an equivalent constrained form, decouple the -og-determinant term and the regularization term, and result in the following augmented Lagrangian form with a penalty parameter X:
- -log(det )) + tr(3)) + p | (3, θ Z) + 1 O Taking U := -// as the scaled dual variable, the update rules for the ADMM algorithm are
(3)
①k+1 + (- V (4/A)T)/2 /2, where Y = Σ/> ZB + Uk
(4)
Z +- 7p/2 Uk), Uk+1 Us Ox+1 Z
(5)
BCD. Block-coordinate decent methods Friedman et al. (2008) updates each column (and the corresponding row) of the precision matrix iteratively by solving a sequence of lasso problems. The algorithm is very efficient for large scale problems involving thousands of variables.
Apart from various algorithms, rigorous statistical analysis has also been provided for the optimal solution of the convex formulation in Eq. ① Ravikumar et al. (20TT) established consistency of the estimator θ in Eq. 11 in terms of both Frobenius and spectral norms, at rate scaling roughly as || O- O( ((d + 8) log d//m) with high probability, where is the number of nonzero entries in - This statistical analysis also reveal certain limitations of the convex formulation:
The established consistency is based on set of carefully chosen conditions, including the lower bound of sample size, the sparsity level of è*, the degree of the graph, the magnitude of the entries in the covariance matrix, and the strength of interaction between edge and non-edge in the precision matrix (or mutual incoherence on the Hessian r : Σ" @ Σ") In practice, it may be hard to problem to satisfy these recovery conditions.
Therefore, it seems that there is still room for improving the above convex optimization algorithms for recovering the true graph structure. Prior to the data-driven paradigm for sparse recovery, since the target parameter @* is unknown, the best precision matrix recovery method is to resort to surrogate objective function (for instance, equation D]. Optimally tuning the unknown parameter p is a very challenging problem in practice. Instead, we can leverage the large amount of simulation real data and design a learning algorithm that directly optimizes the loss in equation 9
Furthermore, since the log determiennnn estimator in Eq. (I) is NOT directly optimizing the recovery objective || O* e I|? there is also mismatch in the optimization objective and the final evaluation objective (refer to the first experiment in section [.1]). This increase the hope one may improve the results by directly optimizing the recovery objective with the algorithms learned from data.
3 LEARNING -DIVED ALGORITHM FOR GRAPH RECOVERY
In the remainder of the paper, we will present a data-driven method to learn an algorithm for precision matrix estimation, and we call the resulting algorithm GLAD (stands for Graph recovery Learning Algorithm using Data-driven training). We ask the question of
Given family of precision matrices, is it possible improve recovery results for sparse graphs by learning a data-driven algorithm?
More formally, suppose are given n precision matrices (()()) from family G of graphs and m samples (1-1 J==1 associated with each (1), These samples can be used to form n sample covariance matrices (50)) We are interested in learning an algorithm for precision matrix estimation by solving a supervised learning problem, min, n. (GLAAD (r()),, where a set of parameters in GLAD(-) and the output of CLAD,(E()) is expected to be good estimation of (1) in terms of an interested evaluation metric L. The benefit is that it can directly optimize the final evaluation metric which related the desired structure or graph properties of family of problems. However, it is a challenging task to design a good parameterization of GLAD, for this graph recovery problem. We will explain the challenges below and then present our solution.
3

---

Published as a conference paper at ICLR 2020
3.1 CHALLENGES IN DESIGNING LEARNING MODELS
In the literature learning data-driven algorithms, most models designed using traditional deep learning architectures, such as fully connected DNN or recurrent neural networks, But, for graph recovery problems, directly using these architectures does not work well due to the following reasons.
Samples
A
First, using a fully connected neural network is not practical. Since both the input and the output of graph recovery problems are matrices, the number of parameters scales at least quadratically in d. Such large number of parameters will need many input-output training pairs to provide decent estimation. Thus some structures need to be imposed in the network to reduce the size parameters and sample complexity.
Second, structured models such convolution neural networks (CNNs) have been applied to learn a mapping from Σ to @" (Belilovsky et al. 2017 Due to the struc- ture of CNNs, the number of parameters can be much smaller than fully connected networks. However, recovered graph should be permutation invariant with respect to the matrix rows/columns, and this constraint is very hard to be learned by CNNs, unless there are lots of samples. Also, the structure of CNN is bias imposed the model, and there is no guarantee why this structure may work.
Pon
Third, the intermediate results produced by both fully connected networks and CNNs are not interpretable, making it hard to diagnose the learned procedures and progressively output increasingly improved precision matrix estimators.
Graphs
Fourth, the SPD constraint is hard to impose in traditional deep learning architectures.
Figure 1:
A
recurrent unit Although, the above limitations do suggest list of desiderata when designing GLADcel1. learning models: Small model size; Minimalist learning: Interpretable architecture; Progressive improvement; and SPD output. These desiderata will motivate the design of our deep architecture using unrolled algorithms.
3.2
GLAD: DEEP LEARNING MODEL BASED ON UNROLLED ALGORITHM
To take into account the above desidcrata, we will use an unrolled algorithm as the template for the architecture design of GLAD. The unrolled algorithm already incorporates some problem structures, such as permutation invariance and interpretable intermediate results; but this unrolled algorithm does not traditionally have learning component, and is typically not directly suitable for gradient- based approaches. We will leverage this inductive bias in our architecture design and augment the unrolled algorithm with suitable and flexible learning components, and then train these embedded models with stochastic gradient descent.
GLAD model is based on reformulation of the original optimization problem in Eq. I with squared penalty term, and an alternating minimization (AM) algorithm for it. More specifically, we consider modified optimization with a quadratic penalty parameter X:
θ 2x arg minl log(det +) tr(īe) P 11 + - - (6)
and the alternating minimization (AM) method for solving it:
0 + - Y + $1), where Y 1 AM,
(7)
Z /// (
(8)
where 1//x (0) (0) max(10) p/ 0). The derivation of these steps are given in Appendix A We replace the penalty constants (p. A) by problem dependent neural networks, Pwn and Amn- These neural networks are minimalist terms of the number of parameters as the input dimensions are mere (3,2) 2} for {Pan Ann} } and outputs single value. Algorithm summarizes the update equations for our unrolled AM based model, GLAD. Except for the parameters in Prin. and Ann. the constant t for initialization is also learnable scalar parameter. This unrolled algorithm with neural network augmentation can be viewed as a highly structured recurrent architecture as illustrated in Figure [
There many traditional algorithms for solving graph recovery problems. We choose AM as basis because: First, empirically, we tried models built upon other algorithms including G-ISTA ADMM, etc, but AM-based model gives consistently better performances. Appendix C.10 & C.1
4

---

Published as a conference paper at ICLR 2020
discusses different parameterizations tried. Second, and more importantly, the AM-based architecture has a nice property of maintaining O 1 as a SPD matrix throughout the iterations as long as A < oo. Third, prove later in Section 4 the AM algorithm has linear convergence rate, allowing to use a fixed small number of iterations and still achieve small error margins.
3.3 TRAINING ALGORITHM
To learn the parameters in GLAD architecture, we will di- rectly optimize the recovery objective function rather than using log-determinant objective. A nice property of our deep learning architecture is that each iteration our model will output a valid precision matrix estimation. This allows us add auxiliary losses to regularize the intermediate results of our GLAD architecture. guiding it to learn parameters which can generate a smooth solution trajectory.
Algorithm I: GLAD
Function GLADcell (,, 6, Z,
À + Ann (IZ 011 ; :
Y Y+ 1-
θ } ( v Y I)
For all i do
Specifically, we will use Frobenius norm in our experiments, and design objective which has some resemblance to the discounted cumulative reward in reinforcement learning:
Pij = Pan ( Eijs Zij)
Zi 7p, (Qiz)
return θ Z,
min loss f
0
(4)
O*
Function GLAD (Σ):
θn t ( tI) -t]f[_]_____ An t
where (0() _ X( GLADcel1 (50, 1-11 2 Ak-1)
For k = 0 K - do
the output of the recurrent unit GLADcell at k-th iter- ation, K is number of unrolled iterations, and < 1 is discounting factor.
0++1; 7,
GLADDell (Ê, O₂, ZR, At)
return θx Z
We will use stochastic gradient descent algorithm to train the parameters f in the GLADcel 1. A key step the gradient computation is to propagate gradient through the matrix square root in the GLADcelL. 11. To do this efficiently, make use of the property of SPD matrix that X = 1/2 x /2 and the product rule of derivatives to obtain
dX =
+ x1/=d(xx/2)
(10)
The above equation is Sylvester's 's equation for /2x Since the derivative dXX for X is easy to obtain, then the derivative of d(2 can be obtained by solving the Sylvester's equation in (10
The objective function in equation should be understood in similar way as in Gregor & LeCun (2010); Belilovsky et al. (2017): Liu et al. 2018) where deep architectures are designed to directly produce the sparse outputs.
For GLAD architecture, collection of input covariance matrix and ground truth sparse precision matrix pairs are available during training, either coming from simulated or real data. Thus the objective function in equation Dis formed to directly compare the output of GLAD with the ground truth precision matrix. The goal is to train the deep architecture which can perform well for a family/distribution of input covariance matrix and ground truth sparse precision matrix pairs. The average in the objective function is over different input covariance and precision matrix pairs such that the learned architecture is able perform well over a family of problem instances.
Furthermore, each layer of our deep architecture outputs an intermediate prediction of the sparse precision matrix. The objective function takes into account all these intermediate outputs, weights the loss according to the layer of the deep architecture, and tries to progressively bring these intermediate layer outputs closer and closer to the target ground truth.
3.4 A NOTE ON GLAD ARCHITECTURE'S ' EXPRESSIVE ABILITY
We note that the designed architecture, is more flexible than just learning the regularization parameters. The component in GLAD architecture corresponding to the regularization parameters are entry-wist and also adaptive to the input covariance matrix and the intermediate outputs. GLAD architecture adaptively choose matrix of regularization parameters. This task will be very challenging if the matrix of regularization parameters are tuned manually using cross- validatii,,.. A recent theoretical work Sun al, (2018) also validates the choice of GLAD's design.
5

---

Published as a conference paper at ICLR 2020
4 THEORETICAL ANALYSIS
Since GLAD architecture is obtained by augmenting unrolled optimization algorithm by learnable components, the question is what kind of guarantees can be provided for such learned algorithm, and whether learning can bring benefits the recovery of the precision matrix. In this section, first analyze the statistical guarantee of running the AM algorithm in Eq. ( and Eq. ( for lc steps with fixed quadratic penalty parameter X, and then interpret implication for the learned algorithm. First, we need some standard assumptions about the true model from the literature Rothman et al. (2008):
will
Assumption 1. Let the set S [(i,)) 0 0, j}. Then card(S) S
Assumption 2.
Amin (Σ*) 2 El
(or equivalently Amax (0*) < 1/e1) Amnx((")) 62 and
upper bound on |E112 S cz.
The assumption 2 guarantees that O' exists. Assumption juutt upper bounds the sparsity of O and does not stipulate anything in particular about s. These assumptions characterize the fundamental limitation of the sparse graph recovery problem, beyond which recovery is not possible. Under these assumptions, we prove the linear convergence of AM algorithm (proof is in Appendix B).
log where is the l penalty, d is the dimension of problem and m is the number of samples, the Alternate Minimization algorithm has linear convergence rate for optimization objective defined in (6). The h iteration of the AM algorithm satisfies.
Theorem 1. Under the assumptions
& if
(V/ min( (d+s)*
J - -0 & <C2 -6x1 -
+ +Op
(log (logd)/m) d)/m
(11)
where 0 < Cx < 1 is a constant depending on X.
From the theorem, the Cx in the bound. We observe that at each stage k, an optimal penalty parameter A can be chosen depending on the most updated value Cx. An adaptive sequence of penalty parameters (A....., Ak) should achieve a better eтror bound compared to a fixed X. Since Cλ is a very complicated function of X, the optimal A is hard to choose manually.
that by optimizing the quadratic penalty parameter X, adjust
Besides, the linear convergence guarantee in this theorem is based on the sparse regularity parameter
p log However, choosing good p value in practice is tedious task as shown in our experiments.
In summary, the implications of this theorem are:
An adaptive sequence (Ai...., >x) should lead to an algorithm with better convergence than fixed X, but the sequence may not be easy to choose manually.
which make these Both and the optimal A depend on the corresponding error | - -
parameters hard preseribe manually.
Since, the AM algorithm has a fast linear convergence rate, we can run it for a fixed number of iterations K and still converge with reasonable error margin.
Our learning augmented deep architecture, GLAD, can tune these sequence of X and parameters jointly using gradient descent. Moreover, we refer a recent work by [unn et al.) (2018) where they considered minimizing the graphical lasso objective with general nonconvex penalty. They showed that by iteratively solving sequence of adaptive convex programs one can achieve even better error margins (refer their Algorithm & Theorem 3.5). In every iteration they chose an adaptive regularization matrix based on the most recent solution and the choice of nonconvex penalty. We thus hypothesize that nonconvex and problem dependent function. We choose P as a function depending on the most up-to- date solution (O,. Σ, 2x), and allow different regularizations for different entries of the precision matrix. Such flexibility potentially improves the ability of GLAD model recover the sparse graph.
further improve
margin if we make the penalty parameter p

---

Published as a conference paper at ICLR 2020
5 EXPERIMENTS
In this section, we report several experiments compare GLAD with traditional algorithms and other data-driven algorithms. The results validate the list of desiderata mentioned previously. Es- pecially, it shows the potential of pushing the boundary of traditional graph recovery algorithms by utilizing data. Python implementation (tested on P100 GPU) is available Exact experimental settings details are covered in Appendix C Evaluation metric. We use normalized mean square error (NMSE) and probability of success (PS) to evaluate the algorithm performance. NMSE is 10 10 (E| OP 1- T 10=11² and PS is the probability of correct signed edge-set recovery, ie., P (sign((r,) = sign( O ), (() E E((")], where E(e") is the true edge set. Notation. In all reported results, D stands for dimension d of the random variable, M stands for sample size and N stands for the number of graphs (precision matrices) that is used for training.
5.1 BENEFIT OF DATA-DRIVEN GRADIENT-BASED ALGORITHM
Inconsistent optimization objective. Tradi-
ADMM: D-100, M- 100
ADMM:
D=100, M-100
tional algorithms are typically designed to op- timize the f fi-penalized log likelihood. Since it
p=0.01
150-
375-
0-0.01
convex optimization, convergence to opti-
NASE
p-0.07
p=0.30
Objective 49
105-
p-0.10
mal solution is usually guaranteed. However, this optimization objective different from the example, it revealed in Figure 2 that, although the opti- mization objective always converges, errors of recovering true precision matrices measured by NMSE have very different behaviors given different regularity parameter p, which indicates the necessity of directly optimizing NMSE and hyperparameter tuning.
true error. Taking ADMM
Iterations
Iterations
Figure 2: Convergence of ADMM in terms NMSE and optimization objective. (Refer to Appendix
Expensive hyperparameter tuning. Although hyperpa- rameters of traditional algorithms can be tuned if the true precision matrices are provided as validation dataset, we want to emphasize that hyperparamter tuning by grid search is a tedious and hard task. Table shows that the NMSE values are very sensitive to both / and the quadratic penalty À of ADMM method. For instance, the optimal NMSE in this table is -9.61 when À 0.1 and p 0.03. However, it will increase by a large amount to -2.06 if p is only changed slightly to 0.01. There are many other similar observations in this table, where slight changes in parameters can lead to significant NMSE differences, which in turns makes grid-search very expensive. G-ISTA and BCD follow similar trends.
0.01
0.01
-2.51
-2.25
-2.06
-2.06
-2.69
0.03
-5.59
.9.05
9.48
.9.61
-9.41
0.07
-9.53
-7.58
-7.42
-7.38
-7.46
0.1
-9.38
-6.51
-6.43
-6.41
-6.50
0.2
-6.76
.4.68
.4.55
-4.47
.4.80
Table 1: NMSE results for ADMM.
For fair comparison against GLAD which is data-driven, in all following experiments, all hyper- parameters in traditional algorithms are fine-tuned using validation datasets, for which we spent extensive efforts (See more details in Appendix C.3 C.6p. In contrast, the gradient-based training of GLAD turns out to be much easier.
5.2 CONVERGENCE
A Ann (1 - 011 A) Pij = Pnn Pnnn (Oij Eij₁ Ziz)
We follow the experimental setting in (Rolfs et al., 2012 Mazumder & Agar-
Non-Linearlty: Hidden layers 'tanh' Final layer "sigmoid'
Num of layers
Num of layers 4 Hidden unit size
wal 2011 and perform synthetic experiments on multivariate Gaussians. Each off- diagonal entry of the precision matrix drawn from uniform distribution, i.c., O ~ 1). and then set to s, where s means the sparsity level. Finally, an appropriate multiple of the identity matrix was added to the current matrix, so that the resulting matrix had the smallest eigenvalue as 1 (refer to Appendix C.I).
2010) to generate data
Hidden unit size
Figure 3: Minimalist neural network architectures designed for CLAD experiments sections(5.2) 5.3 5.4 5.5). Refer Ap-
pendix (3.5 for further details about the architecture parameters.
zero with probability p
C.T). We use 30 unrolled steps for GLAD (Figure and compare
ccde: httohh//wwggooooo.oommommmoooo//

---

Published as a conference paper at ICLR 2020
it to G-ISTA, ADMM and BCD, All algorithms are trained/fnnttned using 10 randomly generated graphs and tested over 100 graphs.
Convergence results and average runtime of different algorithms Nvidia's ' PIO P100 GPUs are shown in Figure 4 and Table 2 respectively. GLAD consistently converges faster and gives lower NMSE. Although
Time/itr
D=25
D=100
ADMM
1.45
16.45
G-ISTA
37.51
41.47
the fine-tuned G-ISTA also has decent performance, the computation time in each iteration is much longer than GLAD because it requires line search steps. Besides, we could also see a progressive improvement of GLAD across its iterations.
GLAD
2.81
20.23
Table 2: ms per iteration.
100:
20 p
100;
100: M 500 ,D 100; M
p
100: M 100 p
100; M 500
ADMM
D-
ADNN GASTA
CHSTA
G-BIAA
G-STA
NMSE
GLAD
GLAD
GLAD
GLAD
GLAD
GLAD
-10
-10
-10
-10
-10
20 20
30 Iterations
20
40
70
40
40
Iterations
Iterations
Iterations
Iterations
Iterations
Figure 4: GLAD vs traditional methods. Left 3 plots: Sparsity level fixed as 0.1. Right plots: Sparsity level of each graph is randomly sampled as s ~ 24(0005, 0.15). Results are averaged over 100 test graphs where each graph is estimated 10 times using 10 different sample batches of size M. Standard error is plotted but not visible. Intermediate steps of BCD not evaluated because can only access the final output. Appendix C.4
sklearn Peckeeggg et al. (201 T) and C.5 explains the experiment setup and GLAD architecture.
5.3 RECOVERY PROBABILITY
As analyzed by Ravikumar et al. (201T). the recovery guarantee (such as in terms of Frobenius norm) of the l regularized log-determinant opti- mization significantly depends on the sample size and other conditions. Our GLAD directly optimizes the recovery objective based on data, and it has the potential of pushing the sample plexity limit. We experimented with this and found the results positive.
D 36: Graph grid
D 100: Graph grid
Prababiltty succaa
ADHM
ADMM
0.8
G-1SAA
G-ISTA
0.6
GLAD
366
GLAD
Probabatty
0.4
SCD
BCD
02
0.0
1000
3000
7030
10000
2000
3000
7000
1000
Number of samples 0og scale)
Number of samples 1log stalet
36: Graph random
1.0
100: Graph random
ADNN
ADMM
8.
GHSTA
0.8
G-5TA
GLAD
GLAD
RCD
We follow Ravikumar et al. 1 to
Probabiiig
grobabiitty
0.4
conduct experiments on GRID graphs,
0.
which satisfy the conditions required
7000
1500
200g
1000
6000
5000
7000
10000
1550
2000
3000
400g
5000
7000
20
in (Ravikumar al., [01T). Further- more, we conduct a more challenging task of recovering restricted but ran- domly constructed graphs (see Appendix C.7 for more details). The probability of success (PS) is non-zero only if the algorithm recovers all the edges with correct signs, plotted in Figure GLAD consistently outperforms traditional methods in terms of sample complexity as it recovers the true edges with considerably fewer number of samples.
Kumber of samples (log scalo)
Number samples (lg scale:
Figure 5: Sample complexity for model selection consistency.
5.4 DATA EFFICIENCY
Having a good inductive bias makes GLAD's architecture quite data-efficient compared to other deep learning models. For instance, the state-of-the-art 'DeepGraph' by |Belilovsky et al. is based on CNNs. It contains orders of magnitude more parameters than GLAD. Furthermore, it takes roughly 100, 000 samples, and several hours for training their DG-39 model. In contrast, GLAD learns well with less than 25 parameters, within 100 training samples, and notably less training time. Table 3 also shows that GLAD significantly outperforms DG-39 model in terms of AUC (Area under the ROC curve) by just using 100 training graphs, typically the case for real world settings. Fully connected DL models are unable to learn from such small data and hence are skipped the comparison.
8

---

Published as a conference paper at ICLR 2020
Table 3: AUC on 100 test graphs for
D=39; For experiment settings, refer Ta-
Mcthods
M=15
M=35
M=100
ble 1 of [Belilovsky et al. (2017). Gaus-
BCD
0.578:00000
0.639=0.007
0.704=0.006
DG-39
0.664.10.008
0.70610.006
0.75910.006
sian Random graphs with sparsity 0.05
DG-39-P
0.672+F0.008
0.740+00007
0.771=00006
were chosen and edge values sampled from
GLAB
0.788
0.811+0.003
0.878+0.0M
~ ~u(11,1) 1). (Refer appendix C.8)
5.5 GENE REGULATION DATA
The SynTReN (Van den Bulcke et al. 2006) is a synthetic gene expression data generator specifically designed for analyzing the sparse graph recovery algorithms. It models different types of biological interactions and produces biologically plausible synthetic gene expression data. Figure 6 shows that GLAD performs favourably for structure recovery in terms of NMSE the gene expression data. As the governing equations of the underlying distribution of the SynTReN are unknown, these experiments also emphasize the ability of GLAD handle non-Gaussian data.
Figure 7 visualizes the edge-recovery performance of GLAD models trained on a sub-network of true Ecoli bacteria data. We denote, TPR: True Positive Rate, FPR: False Positive Rate, FDR: False Discovery Rate. The number of simulated training/validation graphs were set to 20/20. One batch of M samples were taken per graph (details in Appendix (C.)). Although, GLAD was trained on graphs with D = 25, it was able to robustly recover a higher dimensional graph D) = 43 structure.
Appendix C.12
contains details of the experiments done on real E.Coli data. The GLAD model was trained using the SynTReN simulator.
Appendix explains our proposed approach to scale for larger problem sizes.
Figure 6: Performance on the SynTReN gener- ated gene expression data with graph as Erdos-renyi having sparsity p 0.05. Refer appendix for experiment details.
25 and
25 and M 25
D = 25 and 100
ABMM
ADMM G-STA
G-5TAA
G-1SAA
10-
NOMSE
Ieerat
Iterations
Figure 7: Recovered graph structures for a sub-network of the E. coli consisting of 43 genes and 30 interactions with increasing samples. In- creasing the samples reduces the fdr by discovering more true edges.
(a) True graph
(b) M=10, fdr=0.613, 1pr=0.913, 0.1-0.114
(c) M=100, fdr=0.236, (pr=0.986, fpr=0.024
6 CONCLUSION & FUTURE WORK
We presented a novel neural network, GLAD, for the sparse graph recovery problem based on an unrolled Alternating Minimization algorithm. We theoretically prove the linear convergence of AM algorithm as well as empirically show that learning can further improve the sparse graph recovery. The learned GLAD model able to push the sample complexity limits thereby highlighting the potential of using algorithms as inductive biases for deep learning architectures. Further development of theory is needed to fully understand and realize the potential of this new direction.
ACKNOWLEDGEMMEN
We thank our colleague Haoran Sun for his helpful comments. This research was supported in part through research cyberinfrastructure resources and services provided by the Partnership for an Advanced Computing Environment (PACE) at the Georgia Institute of Technology, Atlanta, Georgia, USA (PACE 2017). This research was also partly supported by XSEDE Campus Champion Grant GEO150002.

---

Published as a conference paper at ICLR 2020
REFERENCES
Marcin Andrychowiez, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pp. 3981-3989, 2016.
Onureena Banerjce, Laurent El Ghaoui, and Alexandre Aspremont. Model selection through sparse maximum likelihood estimation for multivariate gaussian binary data. Journal of Machine learning research, 9Mar):4485551 2008.
Eugene Belilovsky, Kyle Kastner, Gaël Varoquaux, and Matthew B Blaschko. Learning discover sparse graphical models. In Proceedings of the 34th International Conference on Machine Crurning-Volumme 70, pp. 440-448. JMLR. org, 2017.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning, 3(1):1-122, 2011.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of unfolded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
Jerome Friedman, Trevor Hastie, and Robert Tibshirami. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, ((3):432-441, 2008.
Karol Gregor and Yann LeCun. Learning fast upproximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 399-406. Omnipress, 2010.
Ravindran Kannan and Santosh Vempala. Randomized algorithms numerical linear algebra. Acta Numerica, 26:95-135, 2017.
Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pp. 6348 6358, 2017.
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv:1606.01885 2016
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Alista: Analytic weights good as learned weights in lista. 2018.
Zhaosong Lu. Adaptive first-order methods for general sparse inverse covariance selection. SIAM Journal on Matrix Analysis and Applications, 3144):2000 2010.
Daniel Marbach, James C Costello, Robert Küffner, Nicole M Vega, Robert J Prill, Diogo M Camacho, Kyle R Allison, Andrej Aderhold, Richard Bonneau, Yukun Chen, et al. Wisdom of crowds for robust gene network inference. Nature methods, 9(8):796, 2012.
Rahul Mazumder and Deepak K Agarwal. A flexible, scalable and efficient algorithmic framework for primal graphical lasso. arXiv preprint arXiv:1110.5508, 2011.
PACE. Partnership for an Advanced Computing Environment (PACE), 2017. URL http: Www pace wwreegattcchh....
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 2830. 2011.
Pradeep Ravikumar, Martin Wainwright, Garvesh Raskutti, Bin Yu, et al. High-dimensional covariance estimation by minimizing 11 Il-penalized log-determinant divergence. Electronic Journal of Statistics, 5:935-980, 2011.
10

---

Published as a conference paper at ICLR 2020
Benjamin Rolfs, Bala Rajaratnam, Dominique Guillot, Ian Wong, and Arian Maleki. Iterative thresholding algorithm for sparse inverse covariance estimation. In Advances in Neural Information Processing Systems, pp. 1574-1582, 2012.
Adam J Rothman, Peter Bickel, Elizaveta Levina, Ji Zhu, al. Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2:494-515, 2008.
Jian Sun, Huibin Li, Zongben Xu, et al. Deep admm-net for compressive sensing mri In Advances in neural information processing systems, pp. 10-18, 2016.
Qiang Sun, Kean Ming Tan, Han Liu, and Tong Zhang. Graphical nonconvex optimization via an adaptive convex relaxation. In International Conference Machine Learning, pp. 4817-4824, 2018.
Tim Van den Bulcke, Koenraad Van Leemput, Bart Naudts, Pict van Remortel, Hongwu Ma, Alain Verschoren, Bart De Moor, and Kathleen Marchal. Syntren: generator of synthetic gene expression data for design and analysis of structure learning algorithms. BMC bioinformatics, 7 (1):43, 2006.

---

Published as a conference paper at ICLR 2020
APPENDIX
A DERIVATION OF ALTERNATING MINIMIZATION STEPS
Given the optimization problem
X 2 == arg zes log(det )) + tn(ee) + || + 2 011
(12)
Alternttng Minimization is performing
0 < arg arg - 0) + (ie + 1 - 1
(13)
Best+
7AM
arg min 1 p | | 1 7 θ k++ |
(14)
ZESt
Taking the gradient of the objective function with respect to θ be zero, have - E X( Z) =
(15)
Taking the gradient of the objective function with respect to Z to be zero, we have p2) + A(Z +) = 0,
(16)
where
Zij 0, Zi < 0,
06 06 (Zi))
(17)
1-1,1
Zij 0.
Solving the above two equations, we obtain:
] (-Y+ Y + VTTY + 1) = arg min - log(det 0) + tr((i) + BES"
^ I| - 0
1 1
(18)
2
where Y E Z,
(19)
x
(+) = arg min tr( (r(Eo) + p ||] + 2 11 - 01| ZES
(20)
B LINEAR CONVERGENCE RATE ANALYSIS
Proof of Theorem
Theorem 1. Under the assumptions
if
V
log.d where p the L penalty, d is the m
dimension of problem and m is the number of samples, the Alternate Minimization algorithm has linear convergence rate for optimization objective defined in (6). The ksh iteration of the AM algorithm satisfies.
(V
O < < +Op
(logd)/m) min( (d+t) de
(II)
where 0 < Cx < 1 is constant depending X.
12

---

Published as a conference paper at ICLR 2020
We will reuse the following notations in the appendix: -Th= sample covariance matrix based on m samples,
(21)
p(O:p) = log(det )) -r(É=0)) p ||0f|
(22)
Gg = arg min ((O:p),
(23)
f(0, 2;p, == log(det 6) - tr(()) + p p|2 + z 2 11z - =
(24)
0x 2x == arg min (10.2;p.) A),
(25)
8,2
f(0) p; A) = f(0x, Zxi p)), (p) = min
(26)
8,ZEst-
Tp/A (0) = max -
(27)
The update rules for Alternating Minimization are:
AM e
) ( Y + 21), where Y 3 - ZAM;
(28)
k+1
Z AM +++ < (0++) )
(29)
Assumptions: With reference to the theory developed in Rothman et al. (008)), we make the following assumptions about the true model. (Or(-)) is used to denote bounded in probability.)
Assumption 1. Let the set S = ((1,j) : 01 # 0, & j). Then carl(S) S 8.
Assumption 2. Amin (Σ*) ) 2 E > 0 for equivalently Amax I 1/e1). Amax (E*) S E2 and an
upper bound on [112 S cg:
We now proceed towards the proof:
Lemma 2. For any x, U, k E R. k > 0, x x y.
x + k V 12² + h)2
1
(30)
(x y)}
1 + +1) 22 + 1)
Proof.
(Vx² + k v y22 + x)
(x² + k) + (y² + k) 2 x + k / +h
(31)
(x - y)
(x 7)2
(x v)² 2( 2(222 + lo 1p2 + (xy + k))
(32)
(x y)²
x² + K 1² + k- (zy k)) kk + (xy + k))
(x (V ky 12 + (wy + k))
(33)
k(s y))
1
(34)
(x
k / 12²
To + (xy + k))
2k
(35)
Vx2 // 1²
+ k (xy + k)
1
21
(36)
1
+ 1)(( +1)
Lemma 3. For any X,Y E Sd, >> 0, A(Y) = / Y + 1T satisfies the following inequality,
- ((X)) 5 1X-Yl1p
(37)
where 0 < a2 = 2(2Amaa (x)² +)) (V)2 + 1 1/2 < 1, Amaa (X) is the largest
eigenvalue of X in absolute value.
13

---

Published as a conference paper at ICLR 2020
Proof. First we factorize X using eigen decomposition, X = Dx Qx, where Qx and Dx are
orthogonal matrix and diagonal matrix, respectively. Then we have,
4 A(X) VoXD3 + / V CD& + nox - @x D& + - +x110 Similarly, the above equation holds for Y. Therefore,
10x.
(38)
4 110x- - V D3 + x [10r [[A(X) - 1 = Qxy D3 +
4
(39)
F
Qxlexy V D3 + 4 110x -QT D3 + 4
1Qx)2x
(40)
A
F
4 x 1 QxQT V D3 + 4 V DDz +
-x-0x00
x 11Q003
(41)
V D& + x - oT V Dj + 4 $10
(42)
X
X
where we define Q Qy Qx Similarly, we have,
|X - |X- = -11x=11000
(43)
= =||Dx xxx0
(44)
= =I|xx- -Q Dr@llF.
(45)
Then the i-th entry on the diagonal of Q BTDDQQ is Σラ= Dy Using the fact that Dx and Dy are diagonal, we have,
|X 1 = |Dx - DD
(46)
d d
= D - -
Dr OWI'+ + Σ (Dxa Σ 1=1
Dy
(47)
1=1 1=1
- -IDD Σ Dxu (Dxu - > D2
(48)
j=1
Σ fr + --:0-22 d d
- Dx
(49)
i=1
Σ> -Dxx- - -D
(50)
1=1
The last step makes use of -i=1 23: 1 and ΣØ=1 23: 1. Similarly, using 42
we have,
| - A | D3 x -11- Q7 VTV + 4 x 11
--Q
(51)
4 (V Di + x v Di + 4
(52)
Assuming ||X - Y > 0 (otherwise 37
trivially holds), using 52 and 50p. we have,
Σd
1 j=1 23,( / D2 + v D 33 + 2)2
[A(X)= A
(53)
1X-YI -
ΣL_ Σ/= (Dxu - Dr
DeS + /DR.3 $22
f,f=1,- dd Dx
m8x
(Dxu - D)
(54)
14

---

Published as a conference paper at ICLR 2020
Using lemma we have,
D + 1 x v DDi3 + 2)²
IA(X) 1|
max i-=1,- d. Dx
(55)
X - YII
(Dxi - =D²
1
max ij=1, d. Dys
(56)
Diu x
+ :1(
D2 + 1) x
1
1
(57)
( max, D& + 1) 3 max, Dijj + 1)
=1 1 - ( Amar (x)² + 1) 1/2
1)- - A man (X) + 1) 1)12/2
(58)
Therefore.
IA(X) - A(Y)
< 1 1 Amar (X)² + 1)-
- Amaz (m)= 1)-1/2
(59)
XX - YIl
1 Amaz (X)2+1) 112 Amaz (X) + +1)-1/2
(60)
Lemma 4. Under assumption O satisfy the following inequality.
2 the output of the k-th and (k + 1)-th AM step ZAM, Z and
2 F s 10 - āx11 sO, 2tm
sc 3/115
(61)
where 0 << Cx < 1 is a constant depending on X.
Proof. The first part easy to show, if we observe that in the second update step of AM a contraction under metric d( ((X,) Y) = ||X - Yll Therefore we have,
(). Mo/A is
Z
2
|| F 1n/2
(Gx) | F - @MAM - GA1
(62)
Next we will prove the second part. To simplify notation, we let A(X) = /XTXC X + $1. Using the first update step of AM
(7). we have,
+ AM k+1
66
=
1
Vit1 + Youn Va+z + 4 1)= - - V2 + v / V2 + 1 /1
(63)
2
r
- -YK+1 - 1s)) + +(y SVYTTT Yk-+ + 4 _1--- - v Ys 12 + -/
(64)
2
F
1
|| -V(+++1 - -Y3) + (A(Ve+1) - A((x))l
(65)
2
1
|| Yull+ 1
- A(K))l.
(66)
2
where Yk+1 = 1Σ
zM and Y2= A - 2x. The last derivation step makes use of the triangle
inequality. Using lemma 3 we have,
M - -6,11= - _/2 || YAll +
1 ||Y - -Yall-
(67)
2
Therefore
1M - -,/11 SCali - Yallr =Ga 1 / 12, 2,
(68)
F²
where
C^
1
01 = 1 - 1 >
4 7
A (2)+))++1)1173 2
+1)
~ (Y2)² + 1) +1)
(69)
2 2
= 1 - (AAmax (Vx+1)² + 44) 1/2 (AA (Ya)² + 44 < 1,
(70)
15

---

Published as a conference paper at ICLR 2020
Amax(X) is the largest eigenvalue of X in absolute value. The rest is to show that both Amaz (Yx) and Amaz (Y++1) are bounded using assumption For Amaz (Yk+)), we have,
1 E M
Amax (Y++1)
||
(71)
Σ
(72)
Z x 1| +
1
$ x x +
(73)
Combining 62 and 688)
we have,
k++
A k+1
- SC
ZA 5/ F
(74)
Therefore,
A
2
2 /311 .... S
ZAM 3311
(75)
5
Continuing with 73
we have,
Amarr (Y++1) <
7 +
Z E F
+
2
(76)
-
+
Z
2 +
2
(77)
A
F
X
+
L 11 + 2
2
F
(78)
Since ZA is the minimizer of a strongly convex function, its norm is bounded. And we also have so Amaz (Yk+1) is bounded above whenever co. For
Z ZZAM || bounded in Algorithm [
Amaz A), have,
1 - 5
Amax AYs) =
Z
(79)
7
2
< | +
7x
(80)
$ - + 2
|1
(81)
C2 < 1 is a constant only Therefore both Amaz (Yx) and Amaz (Y4+1) are bounded in (70 i.e. depending on X.
Theorem 1. Under the assumptions
& is
V log d where p the ln penalty, d is the m
dimension of problem and m is the number of samples, the Alternate Minimization algorithm has linear convergence rate for optimization objective defined in 16). The 1 iteration of the AM algorithu satisfies,
(V-
([((lg (logd)/m d)/m minn [d+s]] 2
OM - -00 & - -x +0p 1x1x+000(
(11)
where 0 Cx < 1 is constant depending A.
Proof. (1) Error between θ and θg
Combining the following two equations:
f(@,, Zxip, min f(O, Z: p. A) min f 7 0:p. -
min ((O:p) G(:g: p),
e.2
1 1 -
f(O, p; = G(O: + +(12]] ||@||)
we have:
0 0 (< G(@.;)) < || - -122),
16

---

Published as a conference paper at ICLR 2020
Note that by the optimality condition, v.f(@x, ()) 0, we have the fixed point equation
Σ /
Therefore, |6a||,
|x pdz
x and we have:
0 < p()x:p) ((Obip) < pd
(82)
Since og-Strongly convex, where og independent the sample covariance matrix E as hessian of G is independent of -..
0g
θ 1 65
(VG(0s;)), Go) & ((@x:p) G(@g:
(83)
2
Therefore,
رの - -0oll <V
2p Aog
2 o (od/
= pdj Adg
(84)
Proof. (2) Error between 2g and 0
Corollary 5 (Theorem 1. of Rothman et al.
2008 ). Let Og be the minimizer for the optimization
V log
objective g(0;p). p). Under Assumptions
&
if
m
=Op (V
|
-
(d + 8) log d
(85)
(3) Error between @ and 0
Under the conditions in Corollary 5 we use triangle inequality to combine the above results with
Corollary 5 and Lemma 4
A 00|
O AM - 62/1 + 0 - -6s/ +
|0g -0- 106--1/|
(86)
+0 (ndd /
Or (V
(d (d+ log
<Css MM AM
k- - 0x
(87)
<C AA
0x +0=
(v
(d + 8) log
(88)
m. mimmiin (dteld)
(log d)/m min( [a+t] A 2z)
<C AAM
O2
(89)
C EXPERIMENTAL DETAILS
This section contains the detailed settings used in the experimental evaluation section.
C.I SYNTHETIC DATASET GENERATION
For sections 5.I and 5.2 the synthetic data was generated based on the procedure described in Rolfs al. (2012). A d dimensional precision matrix O was generated by initializing x matrix with its off dhagnaa entries sampled i.i.d. from a uniform distribution O ~ (((11, These entries were then set zero based the sparsity pattern of the corresponding Erdos-Renyí random graph with certain probability p. Finally, an appropriate multiple of the identity matrix was added to the current matrix, that the resulting matrix had the smallest eigenvalue 1. In this way, O was ensured be
17

---

Published as a conference paper at ICLR 2020
D 100 and M 20
D = 100 and M = 100
D = 100 and M = 500
Josa Lic
conyy Jos
cary, Jos_ 110
Joss 120
-5.0
comy comyJons J15
-5.0
cary Kr9g 120
Joss LTc
comy comylnss
cony, Ir9q
NMSE
-7.5
Josa Lse
NMSE
-7.5
cony Jesc 15
NMSE
-7.5
cany Insc
-00.0
-10.0
110.0
12.55
-12.5
-22.5
-15.0 0
20 Iterations
40
-15.0 0
20
40
-15.0 0
20 Iterations
40
Iterations
Figure 8: Varying the number of unrolled iterations. The results are averaged over 1000 test graphs. The L variable is the number of unrolled iterations. We observe that the higher number of unrolled iterations better the performance.
well-conditioned, sparse and positive definite matrix. This matrix was then used in the multivariate Gaussian distribution (0, e "), to obtain M i.i.d samples.
C.2 EXPERIMENT DETAILS: BENEFIT OF DATA-DRIVER DRIVEN GRADIENT BASED ALGORITHM
The plots are for the ADMM method on the Erdos-Renyi Renyi graphs (fixed sparsity p = 0.1) with dimension D 100 and number of samples M 100. The results are averaged over 100 test graphs with 10 sample batches per graph. The std-err a/ /V1000 is shown. Refer appendix CC.1 for more details on data generation process.
Figure(2) 2):
C.3 EXPERIMENT DETAILS: EXPENSIVE HYPERPAR AMETERS TUNING
Table shows the final NMSE values for the ADMM method on the random graph (fixed sparsity p 0.1) with dimension D = 100 and number of samples M = 100. We fixed the initialization parameter of O, as f 0.1 and chose appropriate update rate a for A. It is important to note that the NMSE values are very sensitive to the choice of as well. These parameter values changed substantially for new problem setting. Refer appendix(C.) for more details on data generation process.
C.4 EXPERIMENT DETAILS: CONVERGENCE SYNTHETICC DATASETS
Figure(4) experiment details: Figure 4 shows the NMSE comparison plots for fixed sparsity and mixed sparsity synthetic Erdos-renyi graphs. The dimension was fixed D 100 and the number of samples vary as M [20. 100, 500]. The top row has the sparsity probability p 0.5 for the Pedos-Renyii random graph, whereas for the bottom row plots, the sparsity probabilities are uniformly sampled from (00005, 0.15). For finetuning the traditional algorithms, validation dataset of 10 graphs was used. For the GLAD algorithm, 10 training graphs were randomly chosen and the same validation set was used.
C.5
GLAD: ARCHITECTURE DETAILS FOR SECTION (5.2)
GLAD parameter settings: Prnn was a 4 layer neural network and Ann Both used 3 hidden units in each layer. The non-linearity used for hidden layers was tanh, while the final layer had sigmoid (a) the non-linearity for both, Prn and A,n (refer Figure 3.. The learnable offset parameter of initial Ou was set to t = 1. It was unrolled for L = 30 iterations. The learning rates were chosen to be around [0.01, 0.1] and multi-step LR scheduler was used. The optimizer used was 'adam'. The best nmse model was selected based on the validation data performance. Figure explores the performance of GLAD on using varying number of unrolled iterations L.
layer neural network.
C.6 ADDITIONAL NOTE OF
FINETUNING FOR TRADITIONAL METHODS
Fi shows the average NMSE values over 100 test graphs obtained by the ADMM algorithm on the synthetic data for dimension D 100 and = 100 samples as we vary the values of penalty parameter p and lagrangian parameter X. The offset parameter for Og was set / = 0.1. The NMSE
18

---

Published as a conference paper at ICLR 2020
Vary tho; Graph random
Vary rho; Graph random
Vary rho: Graph random
Probubiiity of suagess
90-0
biee C5
adiiin 11
gaine (1
1950 000.0000033
5890 24
8
Number of samples llog scale)
Namber of samples (log scale)
Number of samples flog scale)
Figure 9: We attempt to illustrate how the traditional methods very sensitive to the hyperparameters and it is a tedious exercise to finetune them. The problem setting is same as described in section(5.3). For all the 3 methods shown above, a reasonable setting. Now, we vary the L1 penalty term p and can observe that how sensitive the probability of success with even slight change of p values.
have already tuned the algorithm specific parameters to
values are very sensitive to the choice of as well. These parameter values changes substantially for a new problem setting. G-ISTA and BCD follow similar trends.
Additional plots highlighting the hyperparameter sensitivity of the traditional methods for model selection consistency experiments. Refer figure 9).
C.7 TOLERANCE OF NOISE: EXPERIMENT DETAILS
Details for experiments in fig Two different graph types were chosen for this experiment which were inspired from Ravikumar et al. (201I). In the 'grid' graph setting, the edge weight for different precision matrices were uniformly sampled from w ~ (0.11, 0.25). The edges within a graph carried equal weights. The other setting was more general, where the graph was random Erdos-Renyi graph with probability of an edge was = 0.05. The off-diagonal entries of the precision matrix were sampled uniformly from ~ 24[0.1, 0.4]. The parameter settings for GLAD were the same as described in Appendix C.5 The model with the best PS performance on the validation dataset was selected. train/validdtes= 10/100/=T11110000000000 graphs were used with 10 sample batches per graph.
C.8 GLAD: COMPARISON WITH OTHER DEEP LEARNING BASED METHODS
Table(3) shows AUC (with std-err) comparisons with the DeepGraph model. For experiment settings, refer Table of Belilovsky et al. (2017). Gaussian Random graphs with sparsity = 0.05 were chosen and edge values sampled from (((11,1) 1). GLAD was trained
only 10 graphs with 5 sample batches per graph. The dimension of the problem is D = 39. The architecture parameter choices of GLAD were the same described in Appendix C.5 and it performs consistently better
along all the settings by significant AUC margin.
C.9 SYNTREN GENE EXPRESSION SIMULATOR DETAILS
The SynTReN Van den Bulcke et al. 2006) is a synthetic gene expression data generator specifically designed for analyzing the structure learning algorithms. The topological characteristics of the synthetically generated networks closely resemble the characteristics of real transcriptional networks. The generator models different types of biological interactions and produces biologically plausible synthetic gene expression data enabling the development of data-driven approaches to recover the underlying network.
The SynTReN simulator details for section 5.5) For performance evaluation, a connected Erdos- Renyi graph was generated with probability as = 0.05. The precision matrix entries were sampled from G. ~ (0.11, 0.2) and the minimum eigenvalue was adjusted to 1 by adding an appropriate multiple of identity matrix. The SynTReN simulator then generated samples from these graphs by incorporating biological noises, correlation noises and other input noises. All these noise levels were sampled uniformly from ~ 400011, 0.1). The figure 6 shows the NMSE comparisons for fixed dimension D 25 and varying number of samples M [10, 25, 100). The number of training/validation graphs were set to 20/20 and the results are reported on 100 test graphs. In these
experiments, only 1 batch of M samples were taken per graph to better mimic the real world setting.
19

---

Published as a conference paper at ICLR 2020
Figure(7) visualizes the edge-recovery performance of the above trained GLAD models subnet- work of true Ecoli bacteria data. which contains 30 edges and D = 43 nodes. The Ecoli subnetwork graph was fed to the SynTReN simulator and M samples were obtained. SynTReN's noise levels were set to 0.05 and the precision matrix edge values were set to w = 0. 05. For the GLAD models, the training done the same settings the gene-data NMSE plots with D 25 and on corresponding number of samples M.
C.10 COMPARISON WITH ADMM OPTIMIZATION BASED UNROLLED ALGORITIIM
In order to find the best unrolled architecture for sparse graph recovery, we considered many different optimization techniques and came up with their equivalent unrolled neural network based deep model. In this section, we compare with the closest unrolled deep model based on ADMM optimization, (ADMMu), and analyze how it compares to GLAD. Appendix Cist down further such techniques for future exploration.
Unrolled model for ADMM: Algorithm 2 describes the unrolled model ADMMu updates. Pain was a 4 layer neural network and Ann was a 2 layer neural network. Both used 3 hidden units in each layer. The non-linearity used for hidden layers was Lanh, while the final layer had sigmoid (a) as the non-linearity for both .Pan and Ann- The learnable offset parameter of initial On was set to = 1. It was unrolled for L 30 iterations. The learning rates were chosen to be around [0.01, 0.1] and multi-step LR scheduler was used. The optimizer used was 'adam'.
Figure compares GLAD with ADMMu on the conver- gence performance with respect to synthetically gen- erated data. The settings were kept same as described in Figure 4 As evident from the plots, we see that GLAD consistently performs better than ADMMu. We had similar observations for other set of experiments as well. Hence, we chose AM based unrolled algorithm over ADMM's as it works better empirically and has less parameters.
Algorithm 2: ADMMu
Function ADMMu-Cell (É, O, U,
Ann -1 ,17,,
Y + x 2 +
+ 1 --Y++ VYTY + 1)
For all i do
Pij Prn (ijj. Eij, Zij. A)
Although, are not entirely confident but we hypothe- size the reason for above observations as follows. In the ADMM update equations 44 & 5. both the Lagrangian term and the penalty term are intuitively working to- gether as 'function' to update the entries Gij. Zzy. Observe that UR can be absorbed into Zμ and/or O and we expect our neural networks to capture this rela- tion. We thus expect CLAD to work at least as good as ADMMu. In our formulation of unrolled ADMMu (Algo- r the update step of U is not controlled by neural networks (as the number of parameters needed will be substantially larger) which might be the reason of it not performing as well as GLAD. Our empirical evaluations corroborate this logic that just by using the penalty term we can maintain all the desired properties and learn the problem dependent 'functions' with a small neural network.
Zi - May (Gij + Uis)
U
Z
return 0,2,U,
Function ADMMu (E): O, (E+ttT For k = 0 K - do
Ao +-
O Zx-1, Z,Z,,,1,UUU,,.,. UK+1, AR+1 Ob + AADMMu
ZZ Uk )k)
return θx, Z
C.11 DIFFERENT DESIGNS TRIED FOR DATA-DRIVEN ALGORITHM
We tried multiple unrolled parameterizations of the optimization techniques used for solving the graphical lasso problem which worked to varying levels of success. We list here few, in interest for helping researchers to further pursue this recent and novel approach of data-driven algorithm designing.
1. ADMM + ALISTA parameterization: The threshold update for Z can be replaced by ALISTA network Liu al. 2018). The stage I of ALISTA is determining W, which is trivial in our case as = I. So, we get W = I. Thus, combining ALISTA updates along with AM's we get an interesting unrolled algorithm for optimization problem.
20

---

Published as a conference paper at ICLR 2020
100; M
20
D
100;
M 100
100; M 500
0.0
0.0
0.0
ADMMu
ADMMU
ADMMu GLAD
-2.
GLAD
-2.
GLAD
-25
-5.0
NMSE
NMSE
NMSE
-7.5
-7.5
10.0
10.0
10.0
-225
-2255
-12.5
11.00
-15.0
-15.0
20
20
30
Iterations
Iterations
Iterations
Figure 10: Convergence on Erdos-random graphs with fixed sparsity (p= 0.1). All the settings are same the fixed sparsity case described in Figure X 'GLAD' consistently performs better than the ADMM based unrolled architecture 'ADMMU'.
We see that the AM based parameterization
G-ISTA parameterization: We parameterized the line search hyperparameter e as well as replaced the next step size determination step by a problem dependent neural network of Algorithm in Rolfs et al. (012)). The main challenge with this parameterization is to main the PSD property of the intermediate matrices obtained. Learning appropriate parameterization of line search hyperparameter such that PSD condition is maintained remains an interesting aspect to investigate. 3. Mirror Descent Net: We get similar set of update equations for the graphical lasso optimization. We identify some learnable parameters, use neural networks to make them problem dependent and train them end-to-end.
4. For all these methods we also tried unrolling the neural network as well. In our experience we found that the performance does not improve much but the convergence becomes unstable.
C.12 RESULTS ON REAL DATA
We use the real data from the 'DREAM 5 Network Inference challenge' (Marbach et al., 2012). This dataset contains 3 compendia that were obtained from microorganisms, some of which are pathogens of clinical relevance. Each compendium consists of hundreds of microarray experiments, which include wide range of genetic, drug, and environmental perturbations. We test our method for recovering the true E.coli network from the gene expression values recorded by doing actual microarray experiments.
The E.coli dataset contains 4511 genes and 805 associated microarray experiments. The true underly- ing network has 2066 discovered edges and 150214 pairs of nodes do not have edge between them. There is no data about the remaining edges. For our experiments, we only consider the discovered edges as the ground truth, following the challenge data settings. We remove the genes that have zero degree and then we get a subset of 1081 genes. For our predictions, we ignore the direction of the edges and only consider retrieving the connections between genes.
We train the GLAD model using the SynTReN simulator on the similar settings as described in Appendix C.9 Briefly, GLAD model was trained on D=50 node graphs sampled from Erdos-Renyi graph with sparsity probability ~ (0.01, 0.1). noise levels of SynTReN simulator sampled from U (0.01, 0.1) and ,, (0.1, 0.2)). The model was unrolled for 15 iterations. This experiment also evaluates GLAD's ability to generalize to different distribution from training as well as scaling ability to more number of nodes.
We can see that GLAD improves over the other competing methods in terms of Area Under the ROC curve (AUC). We understand that it challenging to model real datasets due to the presence of many unknown latent extrinsic factors, but we observe an advantage of using data-driven parameterized algorithm approaches.
We report the AUC scores for E.coli network in Table 4
C.13 SCALING FOR LARGE MATRICES
Methods
BCD
GISTA
GLAD 0.572
AUC
0.548
0.541
We have shown in our experiments that we can train GLAD on smaller number of nodes and get reasonable results for recovering graph structure with considerably larger nodes (AppendixC..2), Thus, in this section, focus scaling up on the inference/test part.
Table 4: GLAD vs other methods for DREAM network inference challenge real
E.Coli data.
21

---

Published as a conference paper at ICLR 2020
With the current GPU implementation. can can handle around 10,000 nodes for inference. For problem sizes with more than 100,000 nodes, we propose to use the randomized algorithm techniques given in Kannan & Vempala (2017). Kindly note that scaling up GLAD is ongoing work and just present here one of the directions that we are exploring. The approach presented helow is to give some rough idea and may contain loose ends.
Randomized algorithms techniques are explained elaborately Kannan & Vempala (2117). Specifi- cally, we will some of their key results
PI. (Theorem 2.1) We will use the length-squared sampling technique to come up with low-rank approximations
P2. (Theorem 2.5) For any large matrix A E Rmxx, we can use approximate it as A & CUR, where R U E R R R
P3. (Section 2.3) For any large matrix A E Rm*x, we can get its approximate SVD by using the property E E(R" R) A where a matrix obtained by of matrix A.
sampling of the rows
The steps for doing approximate AM updates, i.e. of equations 8 approximate yT = Rº R.
Using property P3, we can
E 1)VT
(90)
where V is the right singular vectors of R. Thus, we can combine this approximation with the sketch matrix approximation of Y = CUR to calculate the update in equation(7). Equation is just thresholding operation and can be done efficiently with careful implementation. We are looking in to the experimental as well as theoretical aspects of this approach.
We are also exploring an efficient distributed algorithm for GLAD. We are investigating into parallel MPI based algorithms for this task (https: http://ttoooor...// edweeddueeeeeeee hon//bbyyd/admm html is good reference point). We leverage the fact that the size of learned neural networks are very small, so that can duplicate them over all the processors. This is also interesting future research direction.
22


Reviews:
[{"review_id": "Syldaha4iH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": " The paper proposes a neural network architecture to address the problem of estimating a sparse precision matrix from data (and therefore inferring conditional independence if the random variables are gaussian).\n\nThe authors base their algorithm in the semidefinite relaxation by Banerjee et al. They add a regularization terms and penalization parameters, which they learn using neural networks. They consider an alternating minimization implementation similar to ADMM and the neural networks are only used to find the regularization parameters.\n\nIn order to learn the parameters, the training optimizes the regularization parameters that maximize the recovery objective function (meaning how far is the estimated precision matrices from the true given precision matrices) and doesn’t consider the sparsity. \n\nSomething that is not a priori obvious is the setting of using a family of precision matrices from a family of graphs and trying to learn an underlying precision matrix (by averaging them?). Further explanation of beginning of section 3 would be useful. \n\nSomething else that is not clear to this reviewer is the motivation for the loss (9). If the objective is to find the parameters that maximize the recovery objective without taking the sparsity into consideration then why not choose them that way in (1), why there should be learning involved? And what is the learning exactly pursuing? Is it trying to learn a way to combine the information from the different samples consistently? [I acknowledge this is probably a naive question, but maybe addressing this in section 3.3 will help understanding].\n\nI think the overall idea is interesting. Regularization parameters are usually problematic because it is not obvious how to choose them. Having an automatic, data-driven way to choose them is a useful algorithm design tool. The objective pursued in the choice of the loss function is a key concept of the paper and I believe it is not clearly explained. Explaining this point in a convincing way will improve the paper and my assessment from weak reject to strong accept. I suggest cutting the introduction to half and use that space to justify and explain sections 3 and 3.3 in depth.  \n\n---\nEdit: I thank the authors and reviewer 1 for their explanations. I changed my rating to accept. I think it would be useful for the readers to include some of these remarks in the paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "Skxon8paYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a new method for graph recovery, which is a more data-driven approach by deep learning. It makes an original approach to this problem. In-depth theoretical results are provided in supplementary material. Good attention is also paid to hyper-parameter tuning.\n\nHowever, some parts can be clarified and improved:\n\n- In the introduction a number of phrases should be clarified: \nit is not entirely clear what the meaning is of the input and output of the problem, input covariance and output precision matrix. In the part of related works, it is difficult to understand in this stage why RNN and deep Q-learning is related to the scope of the paper.\n\n- It is not clear whether section 2 contains new elements or whether the new contribution is entirely in section 3. \n\n- Please motivate the use of CNN in section 3.1. Why are convolutional layers important within this context?\n\n- eq (6): the methodology of this formulation can be better positioned with respect to the existing literature. It appears to be based on principles of synchronization and consensus (in the term ||Z - Theta||_F). Additional explanation and references are needed at this point.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlLQCOSKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an approach to data driven edge recovery for sparse gaussian mrfs. The authors propose an AM procedure for solving the l1 regularized maximum likelihood which can be unrolled and parameterized. This method is shown to converge faster at inference time than other methods and it is also far more effective in terms of training time compared to an existing data driven method. The authors provide a theoretical analysis which explains how the AM procedure should succeed and some insights on how it can potentially converge better using an adaptive model (motivating the learning part).\n\nExperiments:\nOverall the experiments demonstrate the method is superior. I have a few comments/concerns however:\n-Scalability to larger graphs. The graphs used here a relatively small. I would like to see how well this scales to larger graphs at least in principal if not experimentally. Is there any issues that make this difficult? For example more iterations might be needed for convergence and this becomes problematic for learning. Can this already compete  with large scale methods like BigQUIC.\n-Are the training graphs always the same distribution as the test graphs (e.g. in terms of the sparsity level)? It would be good to evaluate how well the model works when the training conditions differ to testing, since applying it to real data would require this gap.\n-Closely related to the above if I have understood correctly all the experiments including the gene networks are on synthetic data, it would be good however to see if synthetic data can help generalize to real data.\n- How many iterations are used to train the model? Is the number of iterations ever more at inference than training? It seems the NMSE is increasing after hitting a bottom I am wondering if that is related to mismatch in the number of iterations in test/train\n- (minor) the authors compare wall clock time per iteration in Table 2 however their method converges much faster, it would be good to also see the overall clock time for each method after some reasonable stopping crieria, to show how big the overall gain is. \n\nRelated Work:\nThe overview of sparse graph recovery for Gaussian random variables is good and concise. However I found the high level motivations given in Introduction/Sec 3 are similar (at times even the wording) to those of Belilovsky et al 2017 which introduced/motivate the data driven approach to this problem. Although this reference is used in the experimental section, it would be appropriate to clarify the difference/contribution compared to this work in the Intro, Sec3, and/or related work as a naive reading of the paper incorrectly suggests it is the first to consider a data driven approach to this problem.\n\n\nOther comments:\n- In equation (9) \\Theta^{*(i)} should there be an (i) index there, I suspect this is a typo but  if it is not can the authors explain how the target differs for different (i)\n- The data generating process described in Sec 5, how does it assure SPD, the described procedure (sampling off diagonal entries U(-1,1) then randomly setting zeros) does not appear to me to assure SPD without further constraints.\n- I appreciated Appendix C10/C11 the overview of other attempts to parametrize the inference procedure\n\nOverall I found this work relevant, the formulation well motivated, and potentially of high impact for the community working on inference of sparse conditional independence structure. I would give the score at the moment between weak accept and accept. There is a few points which I would like the authors to clarify or correct in their rebuttal and I would be happy to increase my score.\n\n-----Post Rebuttal\nThe authors have addressed my primary concerns and revised the text, I am thus increasing my score. I recommend the authors also itemize the main changes in the text from the initial manuscript as they are not easy to find right now using the openreview revision comparison system (which seems to be broken). For example its not clear if the results shown within text are in the new manuscript.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review:  The paper proposes a neural network architecture to address the problem of estimating a sparse precision matrix from data, which can be used for inferring conditional independence if the random variables are gaussian. The authors propose an Alternating Minimisation procedure for solving the l1 regularized maximum likelihood which can be unrolled and parameterized. This method is shown to converge faster at inference time than other methods and it is also far more effective in terms of training time compared to an existing data driven method.

Reviewers had good initial impressions of this paper, pointing out the significance of the idea and the soundness of the setup. After a productive rebuttal phase the authors significantly improved the readibility and successfully clarified the remaining concerns of the reviewers. This AC thus recommends acceptance. 
Decision: Accept (Poster)