Ising Model Selection Using $\ell_{1}$-Regularized Linear Regression: A Statistical Mechanics Analysis

The main contributions are summarized as follows. First, we obtain an accurate estimate of the typical sample complexity of $\ell_{1}$-LinR for Ising model selection for typical RR graphs in the paramagnetic phase, which, remarkably, has the same order as $\ell_{1}$-LogR. Specifically, for a typical RR graph $G\in\mathcal{G}_{N,d,K_{0}}$, using $\ell_{1}$-LinR with a regularization parameter $0<\lambda<\tanh\left(K_{0}\right)$, one can consistently reconstruct the structure with $M>\frac{c\left(\lambda,K_{0}\right)\log N}{\lambda^{2}}$ samples, where ${c\left(\lambda,K_{0}\right)=\frac{2\left(1-\tanh^{2}\left(K_{0}\right)+d\lambda^{2}\right)}{1+\left(d-1\right)\tanh^{2}\left(K_{0}\right)}}$. The accuracy of our typical sample complexity prediction is verified by its excellent agreement with experimental results. To the best of our knowledge, this is the first result that provides an accurate typical sample complexity for Ising model selection. Interestingly, as $\lambda\to\tanh\left(K_{0}\right)$, a lower bound $M>\frac{2\log N}{\tanh^{2}\left(K_{0}\right)}$ of the typical sample complexity is obtained, which has the same scaling as the information-theoretic lower bound $M>\frac{c^{\prime}\log N}{K_{0}^{2}}$ [11] for some constant $c^{\prime}$ at high temperatures (i.e., small $K_{0}$) since $\tanh\left(K_{0}\right)=\mathcal{O}\left(K_{0}\right)$ as $K_{0}\rightarrow 0$.

Second, we provide a computationally efficient method to precisely predict the typical learning performance of $\ell_{1}$-LinR in the non-asymptotic case with moderate $M,N$, such as precision, recall, and residual sum of square (RSS). Such precise non-asymptotic predictions of $\ell_{1}$-LinR for Ising model selection have been unavailable even for $\ell_{1}$-LogR [10, 16] and IS [14, 15], nor are they the same as previous asymptotic results of $\ell_{1}$-LinR assuming fixed $\alpha\equiv M/N$ [25, 26, 27, 28]. Moreover, although our theoretical analysis is based on a tree-like structure assumption, experimental results on two dimensional (2D) grid graphs also show a fairly good agreement, indicating that our theoretical result can be a good approximation even for graphs with many loops.

Third, while this paper mainly focuses on $\ell_{1}$-LinR, our method is readily applicable to a wide class of $\ell_{1}$-regularized $M$-estimators [19], including $\ell_{1}$-LogR [10] and IS [14, 15]. Thus, an additional technical contribution is providing a generic approach for precisely characterizing the typical learning performances of various $\ell_{1}$-regularized $M$-estimators for Ising model selection. Although the replica method from statistical mechanics is non-rigorous, our results are conjectured to be correct, which is supported by their excellent agreement with the experimental results. Additionally, several technical advances we propose in this paper, e.g., the entropy term computation by averaging over the Haar measure and the modification of EOS to address the finite-size effect, might be of general interest to those who use the replica method as a tool for performance analysis.

There has been some earlier works on the analysis of Ising model selection (also known as the inverse Ising problem) using the replica method [4, 5, 6, 7, 29] from statistical mechanics. For example, in [6], the performance of the pseudo-likelihood (PL) method [30] is studied. However, instead of graph structure learning, [6] focuses on the problem of parameter learning. Then, [7] extends the analysis to the Ising model with sparse couplings using logistic regression without regularization. The recent work [29] analyzes the performance of $\ell_{2}$-regularized linear regression but the techniques invented there are not applicable to $\ell_{1}$-LinR since the $\ell_{1}$-norm breaks the rotational invariance property.

Regarding the study of $\ell_{1}$-LinR (LASSO) under model misspecification, the past few years have seen a line of research in the field of signal processing with a specific focus on the single-index model [31, 32, 27, 33, 34]. These studies are closely related to ours but there are several important differences. First, in our study, the covariates are generated from an Ising model rather than a Gaussian distribution. Second, we focus on model selection consistency of $\ell_{1}$-LinR while most previous studies consider estimation consistency except [33]. However, [33] only considers the classical asymptotic regime while our analysis includes the high-dimensional setting where $M\ll N$.

As far as we have searched, there is no earlier study of $\ell_{1}$-LinR estimator for Ising model selection, though some are found for Gaussian graphical models [35, 36]. One closely related work [15] states that at high temperatures when the coupling magnitude is approaching zero, both logistic and ISO losses can be approximated by a quadratic loss. However, their claim is only restricted to the very small magnitude near zero while our analysis extends the validity range to the whole paramagnetic phase. Moreover, they evaluate the minimum number of samples necessary for consistently reconstructing “arbitrary” Ising models, which, however, seems much larger than that actually needed. By contrast, we provide the first accurate assessment of typical sample complexity for consistently reconstructing typical samples of Ising models defined over the RR graphs. Furthermore, [15] does not provide precise predictions of the non-asymptotic learning performance as we do.

Ising model is one special class of MRFs with pairwise potentials and each variable takes binary values [22, 23], which is one classical model from statistical physics. The joint probability distribution of an Ising model with $N$ variables (spins) $\boldsymbol{s}=\left(s_{i}\right)_{i=0}^{N-1}\in\left\{-1,+1\right\}^{N}$ has the form

where $Z_{\textrm{Ising}}\left(\boldsymbol{J}^{*}\right)=\sum_{\boldsymbol{s}}\exp\left\{\sum_{i<j}J^{*}_{ij}s_{i}s_{j}\right\}$ is the partition function and $\boldsymbol{J}^{*}=\left(J^{*}_{ij}\right)_{i,j}$ are the original couplings, respectively. In general, there are also external fields but here they are assumed to be zero for simplicity. The structure of Ising model can be described by an undirected graph $G=\left(\mathtt{V},\mathtt{E}\right)$, where $\mathtt{V}=\left\{0,1,...,N-1\right\}$ is a collection of vertices at which the spins are assigned, and $\mathtt{E}=\left\{\left(i,j\right)|J^{*}_{ij}\neq 0\right\}$ is a collection of undirected edges, i.e., $J^{*}_{ij}=0$ for all pairs of $\left(i,j\right)\notin\mathtt{E}$. For each vertex $i\in\mathtt{V}$, its neighborhood is defined as the subset $\mathcal{N}\left(i\right)\equiv\left\{j\in\mathtt{V}|\left(i,j\right)\in\mathtt{E}\right\}$.

The problem of Ising model selection refers to recovering the graph $G$ (edge set $\mathtt{E}$), given $M$ i.i.d. samples $\mathcal{D}^{M}=\left\{\boldsymbol{s}^{\left(1\right)},...,\boldsymbol{s}^{\left(M\right)}\right\}$ from the Ising model. While the maximum likelihood method has nice properties of consistency and asymptotic efficiency, it suffers from high computational complexity. To tackle this difficulty, several local learning algorithms have been proposed, notably the $\ell_{1}$-LogR estimator [10] and IS estimator [14]. Both $\ell_{1}$-LogR and IS optimize a regularized local cost function $\ell\left(\cdot\right)$ for each spin i.e., $\forall i\in\mathtt{V}$,

where $h_{\setminus i}^{\left(\mu\right)}\equiv\sum_{j\neq i}J_{ij}s_{j}^{\left(\mu\right)}$, $\boldsymbol{J}_{\setminus i}\equiv\left(J_{ij}\right)_{j(\neq i)}$, and $\left\|\cdot\right\|_{1}$ denotes the $\ell_{1}$ norm. Specifically, $\ell\left(x\right)=\log\left(1+e^{-2x}\right)$ for $\ell_{1}$-LogR and $\ell\left(x\right)=e^{-x}$ for IS, which correspond to the minus log conditional distribution [10] and the ISO [14], respectively. Consequently, the problem of recovering the edge set $\mathtt{E}$ is equivalently reduced to local neighborhood selection, i.e., recovering the neighborhood set $\mathcal{N}\left(i\right)$ for each vertex $i\in\mathtt{V}$. In particular, given the estimates $\boldsymbol{\hat{J}}_{\setminus i}$ in (2), the neighborhood set of vertex $i$ can be estimated via the nonzero coefficients, i.e.,

In this paper, we focus on one simple linear estimator, termed as the $\ell_{1}$-LinR estimator, i.e., $\forall i\in\mathtt{V}$,

which, recalling that $s_{i}^{\left(\mu\right)}\in\{-1,+1\}$, corresponds to a quadratic loss $\ell\left(x\right)=\frac{1}{2}\left(x-1\right)^{2}$ in (2). The neighorbood set for each vertex $i\in\mathtt{V}$ is estimated in the same way as (3). Interestingly, the quadratic loss used in (4) implies that the postulated conditional distribution is Gaussian and thus inconsistent with the true one, which is one typical case of model misspecification. Furthermore, compared with nonlinear estimators $\ell_{1}$-LogR and IS, the $\ell_{1}$-LinR estimator is more efficient to implement.

For simplicity and without loss of generality, we focus on spin $s_{0}$. With a slight abuse of notation, we will drop certain subscripts in following descriptions, e.g., $\boldsymbol{J}_{\setminus i}$ will be denoted as $\boldsymbol{J}$ hereafter which represents a vector rather than a matrix. The basic idea of the statistical mechanical approach is to introduce the following Hamiltonian and Boltzmann distribution induced by the loss function $\ell\left(\cdot\right)$

where $Z=\int d\boldsymbol{J}e^{-\beta\mathcal{H}\left(\boldsymbol{J}|\mathcal{D}^{M}\right)}$ is the partition function, and $\beta\left(>0\right)$ is the inverse temperature. In the zero-temperature limit $\beta\rightarrow+\infty$, the Boltzmann distribution (7) converges to a point-wise measure on the estimator (2). The macroscopic properties of (7) can be analyzed by assessing the free energy density $f({\cal D}^{M})=-\frac{1}{N\beta}\log Z$, from which, once obtained, we can evaluate averages of various quantities simply by taking its derivatives w.r.t. external fields [21]. In current case, $f({\cal D}^{M})$ depends on the predetermined randomness of ${\cal D}^{M}$, which plays the role of quenched disorder. As $N,M\to\infty$, $f({\cal D}^{M})$ is expected to show the self averaging property [21]: for typical datasets ${\cal D}^{M}$, $f({\cal D}^{M})$ converges to its average over the random data ${\cal D}^{M}$:

where $\left[\cdot\right]_{\mathcal{D}^{M}}$ denotes expectation over $\mathcal{D}^{M}$, i.e. $\left[\cdot\right]_{\mathcal{D}^{M}}=\sum_{\boldsymbol{s}^{\left(1\right)},...,\boldsymbol{s}^{\left(M\right)}}\left(\cdot\right)\prod_{\mu=1}^{M}P_{\textrm{Ising}}\left(\boldsymbol{s}^{\left(\mu\right)}|\boldsymbol{J}^{*}\right)$. Consequently, one can analyze the typical performance of any $\ell_{1}$-regularized M-estimator of the form (2) via the assessment of (8), with $\ell_{1}$-LinR in (4) being a special case with $\ell\left(x\right)=\frac{1}{2}\left(x-1\right)^{2}$.

Unfortunately, computing (8) rigorously is difficult. For practically overcoming this difficulty, we resort to the powerful replica method [20, 21, 22, 23] from statistical mechanics, which is symbolized using the following identity

The basic idea is as follows. One replaces the average of $\log Z$ by that of the $n$-th power $Z^{n}$ which is analytically tractable for $n\in\mathbb{N}$ in the large $N$ limit, and constructs an analytically continuable expression from $\mathbb{N}$ to $\mathbb{R}$, then takes the limit $n\to 0$ by using the expression. Although the replica method is not rigorous, it has been empirically verified from extensive studies in disorder systems [22, 23] and also found useful in the study of high-dimensional models in machine learning [39, 40]. For more details of the replica method, please refer to [20, 21, 22, 23].

Specifically, with the Hamiltonian $\mathcal{H}\left(\boldsymbol{J}|\mathcal{D}^{M}\right)$, assuming $n\in\mathbb{N}$ is a positive integer, the replicated partition function $\left[Z^{n}\right]_{\mathcal{D}^{M}}$ in (9) can be written as

where $h^{a}=\sum_{j}J_{j}^{a}s_{j}$ will be termed as local field hereafter, and $a$ (and $b$ in the following) is index variable of the replicas. The analysis below essentially depends on the distribution of $h^{a}$ but it is nontrivial. To resolve it, we take a similar approach as [7, 29] and introduce the following ansatz.

Ansatz 1 (A1): Denote $\Psi=\left\{j|j\in\mathcal{N}\left(0\right)\right\}$ and $\bar{\Psi}=\left\{j|j=1,...,N-1,j\notin\mathcal{N}\left(0\right)\right\}$ as the active and inactive sets of spin $s_{0}$, respectively, then for a typical RR graph $G\in\mathcal{G}_{N,d,K_{0}}$ in the paramagnetic phase, i.e., $\left(d-1\right)\tanh^{2}\left(K_{0}\right)<1$, the $\ell_{1}$-LinR estimator in (4) is a random vector determined by random realizations of $\mathcal{D}^{M}$ and obeys the following form

where $\bar{J}_{j}$ is the mean value of the estimator and $w_{j}$ is a random variable which is asymptotically zero mean with variance scaled as $\mathcal{O}\left(1\right)$.

The consistency of Ansatz 1 is checked in Appendix B. Under Ansatz 1, the local fields $h^{a}$ can be decomposed as $h^{a}=\sum_{j\in\Psi}\text{$\bar{J}_{j}$}s_{j}+h_{w}^{a}$ where $h_{w}^{a}\equiv\sum_{j}\frac{1}{\sqrt{N}}w_{j}^{a}s_{j}$ is the “noise” part. According to the central limit theorem (CLT), $h_{w}^{a}$ can be approximated as multivariate Gaussian variables, which, under the replica symmetric (RS) ansatz [21], can be fully described by two order parameters

where $C^{\backslash 0}\equiv\{C_{ij}^{\backslash 0}\}$ is the covariance matrix of the original Ising model without the spin $s_{0}$. Since the difference between $C^{\backslash 0}$ and that with $s_{0}$ is not essential in the limit $N\to\infty$, hereafter the superscript ^\0 will be discarded. As shown in Appendix A, for quadratic loss $\ell\left(x\right)=\frac{1}{2}(1-x)^{2}$ of $\ell_{1}$-LinR, the average free energy density (9) in the limit $\beta\rightarrow\infty$ can be computed as

where $\underset{}{\mathtt{Extr}}\left\{\cdot\right\}$ denotes the extremum operation w.r.t. relevant variables and $\mathcal{\xi},S$ denote the energy and entropy terms:

where $\alpha\equiv M/N,\chi\equiv\lim_{\beta\rightarrow\infty}\beta\left(Q-q\right)$, $\mathbb{E}_{s,z}(\cdot)$ denotes the expectation operation w.r.t. $z\sim{\cal N}(0,1)$ and $(s_{0},\boldsymbol{s}_{\Psi})\sim P_{\rm Ising}(s_{0},\boldsymbol{s}_{\Psi}|\boldsymbol{J}^{*})\propto e^{s_{0}\sum_{j\in\Psi}J^{*}_{j}s_{j}}$ [7]. For different losses $\ell\left(\cdot\right)$, the free energy results (13) only differ in the energy term $\mathcal{\xi}$, which in general is non-analytical (e.g., logistic loss for $\ell_{1}$-LogR) but can be solved numerically. Please refer to Appendix A.3 for more details.

In contrast to the case of $\ell_{2}$-norm in [29], the $\ell_{1}$-norm in (15) breaks the rotational invariance property, i.e., $\left\|w^{a}\right\|_{1}\neq\left\|Ow^{a}\right\|_{1}$ for general orthogonal matrix $O$, making it difficult to compute the entropy term $S$. To circumvent this difficulty, we employ an observation that, when considering the RR graph ensemble $\mathcal{G}_{N,d,K_{0}}$ as the coupling network of the Ising model, the orthogonal matrix $O$ diagonalizing the covariance matrix $C$ appears to be distributed from the Haar orthogonal measure [41, 42]. Thus, it is assumed that $I$ in (15) can be replaced by its average $\left[I\right]_{O}$ over the Haar-distributed $O$:

Ansatz 2 (A2): Denote $C\equiv\mathbb{E}_{\boldsymbol{s}}[\boldsymbol{s}\boldsymbol{s}^{T}]$, where $\mathbb{E}_{\boldsymbol{s}}[\cdot]=\sum_{\boldsymbol{s}}P_{\rm Ising}(\boldsymbol{s}|\boldsymbol{J}^{*})(\cdot),$ as the covariance matrix of spin configurations $\boldsymbol{s}$. Suppose that the eigendecomposition of $C$ is $C=O\Lambda O^{T}$, where $O$ is the orthogonal matrix, then $O$ can be seen as a random sample generated from the Haar orthogonal measure and thus for typical graph realizations from $\mathcal{G}_{N,d,K_{0}}$, $I$ in (15) is equal to the average $[I]_{O}$.

The consistency of Ansatz (A2) is numerically checked in Appendix C. Under Ansatz (A2), the entropy term $S$ in (14) can be alternatively computed as $\underset{n\rightarrow 0}{\lim}\frac{1}{N\beta}\frac{\partial}{\partial n}\log\left[I\right]_{O}$, as shown in Appendix A. Finally, under the RS ansatz, the average free energy density (9) in the limit $\beta\rightarrow\infty$ reads

where $z\sim\mathcal{N}\left(0,1\right)$, and $G\left(x\right)$ is a function defined as

and $\rho\left(\gamma\right)$ is the eigenvalue distribution (EVD) of the covariance matrix ${C}$, and $\mathtt{\varTheta}$ is a collection of macroscopic parameters $\mathtt{\varTheta}=\left\{\chi,Q,E,R,F,\eta,K,H,\text{$\left\{\bar{J}_{j}\right\}$ }_{j\in\Psi}\right\}$. For details of these macroscopic parameters and $\rho\left(\gamma\right)$, please refer to Appendix A and F, respectively. Note that in (20), apart from the ratio $\alpha\equiv M/N$, $N$ and $M$ also appear as $\lambda M/\sqrt{N}$ in the free energy result, which is different from previous results [7, 29, 39]. The reason is that, thanks to the $\ell_{1}$-regularization term $\lambda M\left\|\boldsymbol{J}\right\|_{1}$ , the mean estimates $\text{$\left\{\bar{J}_{j}\right\}$ }_{j\in\Psi}$ in the active set $\Psi$ and the noise $w$ in the inactive set $\bar{\Psi}$ essentially give different scaling contributions to the free energy density.

Although there are no analytic solutions, these macroscopic parameters in (20) can be obtained by numerically solving the corresponding equations of state (EOS) employing the physics terminology. Specifically, for the $\ell_{1}$-LinR estimator, the EOS can be obtained from the extremization condition in (20) as follows (for EOS of a general M-esimator and $\ell_{1}$-LogR, please refer to Appendix A.3):

where $\tilde{\varLambda}$ satisfying $E\eta=-\int\frac{\rho\left(\gamma\right)}{\tilde{\varLambda}-\gamma}d\gamma$ is determined by the extremization condition in (21) and $\mathtt{soft}\left(z,\tau\right)=\mathtt{sign}\left(z\right)\left(\left|z\right|-\tau\right)_{+}$ is the soft-thresholding function. Once the EOS is solved, the free energy density defined in (8) is readily obtained.

One important result of our replica analysis is that, as derived (see Appendix A.3) from the free energy result (20), the original high dimensional $\ell_{1}$-LinR estimator (4) is decoupled into a pair of scalar estimators, one for the active set and one for the inactive set, i.e.,

where $z_{j}\sim\mathcal{N}\left(0,1\right),j\in\bar{\Psi}$ are i.i.d. standard Gaussian random variables. The decoupling property asserts that, once the EOS (22) is solved, the asymptotic behavior of $\ell_{1}$-LinR can be statistically described by a pair of simple scalar soft-thresholding estimators (see Figs. 1(a) and 1(b)).

In the high-dimensional setting where $N$ is allowed to grow as a function of $M$, one important question is that what is the minimum number of samples $M$ required to achieve model selection consistency as $N\rightarrow\infty$. Though we obtain a pair of scalar estimators (23) and (24), there are no analytical solutions to EOS (22), making it difficult to derive an explicit condition. To overcome this difficulty, as shown in Appendix D, we perform a perturbation analysis of EOS (20) and obtain an asymptotic relation $H\simeq F$, Then, we obtain that for a RR graph $G\in\mathcal{G}_{N,d,K_{0}}$, given $M$ i.i.d. samples $\mathcal{D}^{M}$, the $\ell_{1}$-LinR estimator (4) can consistently recover the graph structure $G$ as $N\rightarrow\infty$ if

where $c(\lambda,K_{0})$ is a constant value dependent on the regularization parameter $\lambda$ and coupling strength $K_{0}$ and a sharp prediction (as verified in Sec. 5) is obtained as

For details of the analysis, including the counterpart of $\ell_{1}$-LogR, see Appendix D. Consequently, we obtain the typical sample complexity of $\ell_{1}$-LinR for Ising model selection for typical RR graphs in the paramagnetic phase. The result in (25) is derived for $\ell_{1}$-LinR with a fixed regularization parameter $\lambda$. Since the value of $\lambda$ is upper bounded by $\tanh\left(K_{0}\right)$ (otherwise false negatives occur as discussed in Appendix D), a lower bound of the typical sample complexity for $\ell_{1}$-LinR is obtained as

Interestingly, the scaling in (27) is the same as the information-theoretic worst-case result $M>\frac{c\log N}{K_{0}^{2}}$ obtained in [11] at high temperatures (i.e., small $K_{0}$) since $\tanh\left(K_{0}\right)=\mathcal{O}\left(K_{0}\right)$ as $K_{0}\rightarrow 0$.

In practice, it is desirable to predict the non-asymptotic performance of the $\ell_{1}$-LinR estimator for moderate $M,N$. However, the scalar estimator (23) for the active set (see Fig. 1(a)) fails to capture the fluctuations around the mean estimates. This is because in obtaining the energy term $\mathcal{\mathcal{\xi}}$ (16) of the free energy density (20), the fluctuations around the mean estimates $\text{$\left\{\bar{J}_{j}\right\}$ }_{j\in\Psi}$ are averaged out by the expectation $\mathbb{E}_{s,z}\left(\cdot\right)$. To address this problem, we replace $\mathbb{E}_{s,z}\left(\cdot\right)$ in (20) with a sample average by accounting for the finite-size effect, thus obtaining a modified estimator for the active set as follows

where $s_{0}^{\mu},s_{j,j\in\Psi}^{\mu}\sim P\left(s_{0},\boldsymbol{s}_{\Psi}|\boldsymbol{J}^{*}\right),\;z^{\mu}\sim\mathcal{N}\left(0,1\right),\mu=1...M$. The modified $d$-dimensional estimator (28) (see Fig. 1(c) for a schematic) is equivalent to the scalar one (23) (Fig. 1(a)) as $M\rightarrow\infty$ but it enables us to capture the fluctuations of $\{\hat{J}_{j}\}_{j\in\Psi}$ for moderate $M$. Note that due to the replacement of expectation with sample average in the free energy density (20), the EOS (22) also needs to be modified and it can be solved iteratively as sketched in Algorithm 1. The details are shown in Appendix E.1.

Consequently, for moderate $M,N$, the non-asymptotic statistical properties of the $\ell_{1}$-LinR estimator can be characterized by the reduced $d$-dimensional $\ell_{1}$-LinR estimator (28) (Fig. 1(c)) and scalar estimator (24) (Fig. 1(b)) using MC simulations. Denote $\{\hat{J}_{j}^{t}\},t=1,...,T_{\rm MC}$ as the estimates in $t$-th MC simulation, where $\{\hat{J}^{t}_{j}\}_{j\in\Psi}$ and $\{\hat{J}^{t}_{j}\}_{j\in\bar{\Psi}}$ are solutions of (28) and (24), and $T_{\rm MC}$ is the total number of MC simulations. Then, the $Precision$ and $Recall$ are computed as

where $\left\|\cdot\right\|_{0}$ is the $\ell_{0}$-norm indicating the number of nonzero elements. In addition, the RSS can be computed as $RSS=\sum_{j}\left|\hat{J}_{j}-{J}^{*}_{j}\right|^{2}=\frac{1}{T_{\rm MC}}\sum_{t=1}^{T_{\rm MC}}\sum_{j\in\Psi}\left|\hat{J}_{j}^{t}-K_{0}\right|^{2}+R$.