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

We theoretically analyze the typical learning performance of \ell_{1} -regularized linear regression ( \ell_1 -LinR) for Ising model selection using the replica method from statistical mechanics. For typical random regular graphs in the paramagnetic phase, an accurate estimate of the typical sample complexity of \ell_1 -LinR is obtained. Remarkably, despite the model misspecification, \ell_1 -LinR is model selection consistent with the same order of sample complexity as \ell_{1} -regularized logistic regression ( \ell_1 -LogR), i.e., M \mathcal{O}\left(\log N\right), where N is the number of variables of the Ising model. Moreover, we provide an efficient method to accurately predict the non-asymptotic behavior of \ell_1 -LinR for moderate M, N, such as precision and recall. Simulations show a fairly good agreement between theoretical predictions and experimental results, even for graphs with many loops, which supports our findings.