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. 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, a sparse graph structure between financial timeseries may be used to understand the relationship between different financial assets. A popular formulation of the problem is an 1 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 a 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 to achieve the recovery results. Furthermore, the formulation uses a 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 a quadratic increase in the number of hyperparameters, but it is hard for traditional approaches to search over a large number of hyperparameters. Thus, a new paradigm may be needed for designing more effective sparse recovery algorithms. Recently, there has been a surge of interest in a new paradigm of algorithm design, where algorithms are augmented with learning modules trained directly with data, rather than prescribing every step of the algorithms. This is meaningful because very often a 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 an algorithm which performs better than traditional convex formulation. In our case, the sparse graph recovery problem may also need to 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 on the time and conditions, and we want to estimate them from gene In our experiments, we show that the AM architecture provides very good inductive bias, allowing the model to learn very effective sparse graph recovery algorithm with a 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 et 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 our sparse graph recovery problem. Another interesting line of approach is to develop deep neural networks based on unfolding an iterative algorithm Gregor & LeCun (2010) ; ; . developed ALISTA which is based on unrolling the Iterative Shrinkage Thresholding Algorithm (ISTA). Sun et al. (2016) developed 'ADMM-Net', which is 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 a suitable unrolled algorithm and leverage its inductive bias to solve the sparse graph recovery problem. 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 is 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. Alternating Minimization is performing Taking the gradient of the objective function with respect to Θ to be zero, we have Taking the gradient of the objective function with respect to Z to be zero, we have where Solving the above two equations, we obtain: where B LINEAR CONVERGENCE RATE ANALYSIS m , where ρ is the l 1 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 k th iteration of the AM algorithm satisfies, where 0 < C λ < 1 is a constant depending on λ. We will reuse the following notations in the appendix: The update rules for Alternating Minimization are: Assumptions: With reference to the theory developed in Rothman et al. (2008), we make the following assumptions about the true model. (O P (·) is used to denote bounded in probability. ) We now proceed towards the proof: Lemma 2. For any x, y, k ∈ R, k > 0, x = y, Proof. where is the largest eigenvalue of X in absolute value. Proof. First we factorize X using eigen decomposition, X = Q X D X Q X , where Q X and D X are orthogonal matrix and diagonal matrix, respectively. Then we have, Similarly, the above equation holds for Y . Therefore, where we define Q := Q Y Q X . Similarly, we have, Then the i-th entry on the diagonal of ji . Using the fact that D X and D Y are diagonal, we have, The last step makes use of Similarly, using (42), we have, Assuming X − Y F > 0 (otherwise (37) trivially holds), using (52) and (50), we have, Using lemma (2), we have, Therefore, Lemma 4. Under assumption (2), the output of the k-th and where 0 < C λ < 1 is a constant depending on λ. Proof. The first part is easy to show, if we observe that in the second update step of AM (8), η ρ/λ is a contraction under metric d(X, Y ) = X − Y F . Therefore we have, Next we will prove the second part. To simplify notation, we let A(X) = X X + 4 λ I. Using the first update step of AM (7), we have, where The last derivation step makes use of the triangle inequality. Using lemma (3), we have, Therefore where Λ max (X) is the largest eigenvalue of X in absolute value. The rest is to show that both Λ max (Y λ ) and Λ max (Y k+1 ) are bounded using assumption (2). For Λ max (Y k+1 ), we have, Combining (62) and (68), we have, Therefore, Continuing with (73), we have, Since Z λ is the minimizer of a strongly convex function, its norm is bounded. And we also have Therefore both Λ max (Y λ ) and Λ max (Y k+1 ) are bounded in (70), i.e. 0 < C λ < 1 is a constant only depending on λ. m , where ρ is the l 1 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 k th iteration of the AM algorithm satisfies, where 0 < C λ < 1 is a constant depending on λ. Proof. (1) Error between Θ λ and Θ G Combining the following two equations: Note that by the optimality condition, ∇ z f ( Θ λ , Z λ , ρ, λ) = 0, we have the fixed point equation λ and we have: Since G is σ G -strongly convex, where σ G is independent of the sample covariance matrix Σ * as the hessian of G is independent of Σ * . Therefore, Proof. (2) Error between Θ G and Θ * Corollary 5 (Theorem 1. of Rothman et al. (2008)). Let Θ G be the minimizer for the optimization C EXPERIMENTAL DETAILS This section contains the detailed settings used in the experimental evaluation section.
A data-driven learning algorithm based on unrolling the Alternating Minimization optimization for sparse graph recovery.
{"src": "scitldr-AIC_train", "paper_id": "BkxpMTEtPB"}