# On Model Selection Consistency of Lasso for High-Dimensional Ising Models

arXiv: https://arxiv.org/abs/2110.08500 · HTML: https://mlsanity.com/paper/2110.08500/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 54 references that are in the map.
- First posted on arXiv 16 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Inverse statistical problems: from the inverse Ising problem to data science](https://mlsanity.com/paper/1702.01522/) (2017)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Scalable Approximations for Generalized Linear Problems](https://mlsanity.com/paper/1611.06686/) (2016)
- [A statistical physics approach to learning curves for the Inverse Ising problem](https://mlsanity.com/paper/1705.05403/) (2017)
- [Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysis](https://mlsanity.com/paper/2102.03988/) (2021)
- [Learning performance in inverse Ising problems with sparse teacher couplings](https://mlsanity.com/paper/1912.11591/) (2019)
- [Structure Learning in Inverse Ising Problems Using ℓ2-Regularized Linear Estimator](https://mlsanity.com/paper/2008.08342/) (2020)

## Built on by (most cited first, 1 of 1)

- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)

## Abstract (arXiv)

We theoretically analyze the model selection consistency of least absolute shrinkage and selection operator (Lasso), both with and without post-thresholding, for high-dimensional Ising models. For random regular (RR) graphs of size p with regular node degree d and uniform couplings θ0, it is rigorously proved that Lasso textitwithout post-thresholding is model selection consistent in the whole paramagnetic phase with the same order of sample complexity n=Omega(d3logp) as that of ℓ1-regularized logistic regression (ℓ1-LogR). This result is consistent with the conjecture in Meng, Obuchi, and Kabashima 2021 using the non-rigorous replica method from statistical physics and thus complements it with a rigorous proof. For general tree-like graphs, it is demonstrated that the same result as RR graphs can be obtained under mild assumptions of the dependency condition and incoherence condition. Moreover, we provide a rigorous proof of the model selection consistency of Lasso with post-thresholding for general tree-like graphs in the paramagnetic phase without further assumptions on the dependency and incoherence conditions. Experimental results agree well with our theoretical analysis.