  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 \textit{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.
