High-Dimensional Ising Model Selection via L1-Regularized Logistic Regression

⚠️ Curated Limitations & Negative Results

• Population Fisher Mutual Incoherence and Degree-Cubed Scaling: Theorem 1 requires the population Fisher information matrix Q*_r = E_{theta*}[eta(X; theta*) X_{\r} X_{\r}^T] to satisfy the l_infinity mutual incoherence bound |||Q*_{S^c S} (Q*_{SS})^{-1}|||_infty <= 1 - alpha (Equation 13) and requires n = Omega(d^3 log p) samples and theta*_min = Omega(1/d) when transferring incoherence from Q* to the sample Fisher matrix Q^n (whereas n = Omega(d^2 log p) suffices under sample Fisher incoherence in Proposition 1).
• Binary Pairwise Ising Model Scope: The explicit analysis in Theorems 1 and Proposition 1 is formulated for zero-field pairwise binary Ising models X_s in {-1, +1} (Section 2.1, Equation 1), with extensions to general multi-state discrete Markov random fields discussed only at a high level.
• Primary-Source Typographical Notes in Ravikumar, Wainwright, & Lafferty (2010, arXiv:0804.4202v1): Verified six self-correcting typographical details during full-text inspection and numerical verification: (1) Section 2.3 (p. 5, Equation 3) defines N_pm(r) := {sign(theta*_{rt}) t | t in N(s)} with s in place of r, while p. 6 writes theta_{\s} in line 15 and theta_hat_{su} != 0 in Equation (8) in place of theta_{\r} and theta_hat_{ru} != 0; (2) Section 3.1 (p. 7, Equation 9) writes Q*_r := E_{theta*}{nabla^2 log P_{theta*}[X_r | X_{\r}]} omitting the minus sign of the negative log-likelihood ell(theta) (whereas Equation 10 gives the positive-definite Fisher information matrix E_{theta*}[eta(X; theta*) X_{\r} X_{\r}^T]); (3) Section 3.2 (p. 8, Theorem 1, Equation 16) and Section 4 (p. 11, Proposition 1, Equation 26) write the success event P[G_hat(lambda_n) = G(p, d)] on the LHS with the failure-rate upper bound O(exp(-K n / d^3 - 3 log p)) -> 0 and O(exp(-n lambda_n^2 - log p)) -> 0 on the RHS (where the union-bound failure probability P[G_hat != G] has +3 log p / +log p in the exponent, as in Lemma 2 Eq. 30, Lemma 4 Eq. 32, and Lemma 6 Eq. 42, so P[G_hat = G] = 1 - O(exp(-K n / d^3 + 3 log p)) -> 1); (4) Section 3.3 (p. 9, Equation 21) writes 'if theta_hat_i != 0' in place of 'if theta_hat_{rt} != 0'; (5) Section 4.2 (p. 12, Equation 35) writes [W^n_{S^c} - R^n_{S^c}] - Q^n_{S^c S} (Q^n_{SS})^{-1} [W^n_S - R^n_S] with minus signs before R^n_{S^c} and R^n_S when eliminating (theta_hat_S - theta*_S) from Equations (33a)-(33b) (whereas substituting (Q^n_{SS})^{-1}[W^n_S - lambda_n z_hat_S + R^n_S] gives +R^n_{S^c} and +R^n_S, leaving the triangle-inequality bound in Equations 36-37 identical); and (6) Section 5.2 (p. 15, bottom display) writes T_1 = Q*_{S^c S} (Q*_{SS})^{-1} [Q^n_{SS} - Q*_{SS}] (Q^n_{SS})^{-1} with [Q^n_{SS} - Q*_{SS}] in place of [Q*_{SS} - Q^n_{SS}] (which flips only the overall sign of T_1 and leaves |||T_1|||_infty unchanged).
• All 25 pages of Ravikumar, Wainwright, & Lafferty (2010, Annals of Statistics 38(3):1287-1319, arXiv:0804.4202v1) were read. Constructed numerical checks in research/discovery/high-dimensional-ising-model-selection-l1-logistic-regression-boundaries.py verify (1) exact identity (error 2.22e-16) between the negative conditional log-likelihood (Eq. 5) and the rescaled logistic objective (Eqs. 6-7), zero population score E_{theta*}[W^n] = 0 (error 1.39e-17), and exact equality between eta(u; theta*) (Eq. 11) and Var_{theta*}(X_r | X_{\r}); and (2) exact primal-dual witness KKT stationarity (residual 5.55e-17), strict dual feasibility |z_hat_{S^c}| = 0.236248 < 1, signed support recovery, exact Taylor remainder dual witness identity (error 0.0), and the four-term sample-to-population incoherence decomposition (error 4.34e-19).