On Model Selection Consistency of Lasso for High-Dimensional Ising Models
Xiangming Meng, Tomoyuki Obuchi, Yoshiyuki Kabashima
Abstract
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 $\theta_0$, it is rigorously proved that Lasso without post-thresholding is model selection consistent in the whole paramagnetic phase with the same order of sample complexity $n=\Omega{(d^3\log{p})}$ as that of $\ell_1$-regularized logistic regression ($\ell_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.
BibTeX
@InProceedings{pmlr-v206-meng23a,
title = {On Model Selection Consistency of Lasso for High-Dimensional Ising Models},
author = {Meng, Xiangming and Obuchi, Tomoyuki and Kabashima, Yoshiyuki},
booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics},
pages = {6783--6805},
year = {2023},
editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem},
volume = {206},
series = {Proceedings of Machine Learning Research},
month = {25--27 Apr},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v206/meng23a/meng23a.pdf},
url = {https://proceedings.mlr.press/v206/meng23a.html},
abstract = {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 $\theta_0$, it is rigorously proved that Lasso without post-thresholding is model selection consistent in the whole paramagnetic phase with the same order of sample complexity $n=\Omega{(d^3\log{p})}$ as that of $\ell_1$-regularized logistic regression ($\ell_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.}
}