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

Abstract

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. Although this paper mainly focuses on ${\ell }_1$-LinR, our method is readily applicable for precisely characterizing the typical learning performances of a wide class of ${\ell }_1$-regularized $M$-estimators including ${\ell }_1$-LogR and interaction screening.

arXiv commentAccepted to NeurIPS 2021. Camera-ready version with supplementary materials

References in corpus (20)

• High-dimensional graphs and variable selection with the Lasso
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Inverse statistical problems: from the inverse Ising problem to data science
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Inverse Ising inference using all the data
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The Bethe approximation for solving the inverse Ising problem: a comparison with other inference methods
• Generalisation error in learning with random features and the hidden manifold model
• Pseudolikelihood Decimation Algorithm Improving the Inference of the Interaction Network in a General Class of Ising Models
• Bethe-Peierls approximation and the inverse Ising model
• Which graphical models are difficult to learn?
• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Statistical Mechanics of High-Dimensional Inference
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• A statistical physics approach to learning curves for the Inverse Ising problem
• Learning of couplings for random asymmetric kinetic Ising models revisited: random correlation matrices and learning curves
• Statistical mechanics of the inverse Ising problem and the optimal objective function
• Learning performance in inverse Ising problems with sparse teacher couplings
• Structure Learning in Inverse Ising Problems Using ${\ell }_2$-Regularized Linear Estimator