Maximum likelihood thresholds of generic linear concentration models

Technical Summary: Maximum Likelihood Thresholds of Generic Linear Concentration Models

Problem Statement
The paper addresses the determination of the maximum likelihood threshold (MLT) for statistical models, specifically linear concentration models. The MLT of a model $M$ is defined as the minimum number of data points $d$ required such that, for almost all datasets of size $d$, a maximum likelihood estimate (MLE) exists within the model.

The authors focus on the case where $M$ is a linear concentration model $M_L$, consisting of all $n$-variate normal distributions whose inverse covariance matrix (concentration matrix) lies in a fixed linear subspace $L$ of $n \times n$ symmetric matrices ($S_n$). While the MLT for Gaussian graphical models (where $L$ is defined by zeroing specific off-diagonal entries) has been studied extensively using combinatorial and rigidity-theoretic methods, the behavior of generic linear concentration models (where $L$ is a generic subspace of a given dimension) had not been fully characterized. The central question is whether the MLT for a generic $L$ can be predicted by a simple dimension count or if it depends on more subtle structural properties.

Methodology
The authors employ a blend of algebraic geometry, semi-algebraic geometry, and convex analysis to resolve the existence of the MLE.

1. Characterization of MLE Existence: The paper begins by establishing Theorem 2.1, which provides three equivalent conditions for the existence of an MLE in $M_L$ given a sample covariance matrix $S$. Crucially, condition (3) states that an MLE exists if and only if there is no non-zero positive semidefinite (PSD) matrix $\Omega \in L$ such that $\text{Tr}(\Omega S) = 0$ (equivalently $\Omega S = 0$). This reduces the problem to analyzing the intersection properties of the subspace $L$ and the set of rank-$d$ PSD matrices.

2. Genericity and Topology: The authors define "generic" behavior using the Zariski topology on the Grassmannian $Gr(m, S_n)$, where $m = \dim(L)$. They utilize Lemma 3.2 and Lemma 3.4 to show that if a property fails for a semi-algebraic set $E$, and $E$ has empty Euclidean interior, then $E$ is contained in a proper Zariski-closed subset. This allows them to prove that certain "bad" behaviors (where the MLT deviates from the naive count) occur only on a lower-dimensional subset of the space of all linear subspaces.

3. Lower Bound Derivation: To establish a lower bound on the MLT, the authors analyze the conditions under which a "bad" dataset $S$ (one for which no MLE exists) can be constructed.

   • They define sets $Z(\Omega_0)$ and $Q(S_0)$ related to the column spans and kernels of matrices.
   • Using Lemma 3.11, they prove that for a generic $L$ with sufficiently high dimension, there exists a transverse intersection between $L$ and $Z(\Omega)$ for some PSD $\Omega$ of rank $n-d$.
   • Proposition 3.16 demonstrates that if $\dim(L) \geq dn - \binom{d}{2} + 1$, then for generic $L$, there exists an open neighborhood of rank-$d$ PSD matrices $S$ such that a non-zero $\Omega \in L \cap S_n^+$ exists with $\Omega S = 0$. By Theorem 2.1, this implies the MLE does not exist for these datasets.

4. Upper Bound Derivation: To establish the matching upper bound, the authors use algebraic dimension counting.

   • They define the set $B(m, d)$ of pairs $(L, S)$ where $L \cap Q(S) \neq \{0\}$.
   • Lemma 3.18 shows that if $\dim(L) \leq dn - \binom{d}{2}$, then $B(m, d)$ is a proper algebraic subset of the product space.
   • Proposition 3.22 concludes that for generic $L$ in this dimension range, the intersection $L \cap Q(S)$ is trivial for almost all $S$, implying the MLE exists.

5. Generic Completion Rank (GCR): The paper introduces the Generic Completion Rank (Definition 4.1), defined as the minimum $d$ such that the projection of rank-$d$ matrices onto $L$ is full-dimensional. They prove (Theorem 4.5) that GCR is always an upper bound on the MLT.

Key Contributions and Results

• Main Theorem (Theorem 3.23): The paper determines the exact MLT for a generic linear concentration model $M_L$ with $\dim(L) = m$. The threshold is the minimum integer $d$ satisfying:
  $$m \leq dn - \binom{d}{2}$$
  This result confirms that for generic subspaces, the MLT is determined solely by a naive dimension count, despite the MLT being a semi-algebraic concept that often depends on complex combinatorial structures in specific cases (like Gaussian graphical models).

• Geometric Characterization of Exceptions: The authors explicitly describe the geometric conditions under which a linear subspace $L$ fails to exhibit this generic behavior. These failures occur if:

  1. $L$ does not contain a PSD matrix of rank $n-d$ (Lemma 3.7).
  2. For every PSD $\Omega \in L$ of rank $n-d$, the intersection between $L$ and the variety $Z(\Omega)$ is non-transversal (Lemma 3.11).
     The paper notes that Gaussian graphical models often fail the MLT bound due to the second condition (non-transversality), whereas the first condition (lack of specific rank matrices) does not occur for them because they always contain diagonal matrices.

• Equivalence of MLT and GCR for Generic Models: Corollary 4.6 establishes that for a generic linear subspace, the Maximum Likelihood Threshold is equal to its Generic Completion Rank.

Significance
The paper claims significance in providing a baseline for understanding linear concentration models. While generic models are not typically used in practice (as real-world models usually have special structures, like sparsity in graphical models), understanding their behavior allows researchers to compare specific, structured models against this "naive" expectation.

The authors emphasize that their result is non-trivial because the MLT is a semi-algebraic concept; one might expect the threshold to depend on the specific geometry of $L$ rather than just its dimension. The proof demonstrates that over the real field, the "generic" case aligns perfectly with the algebraic dimension count, provided one accounts for the specific Zariski-closed subsets where this alignment breaks down.

The work also extends the concept of the Generic Completion Rank, previously defined for Gaussian graphical models, to arbitrary linear concentration models, showing it serves as a robust upper bound for the MLT in the general case. The paper concludes that while rigidity-theoretic ideas have successfully demystified MLTs for graphical models, the behavior of generic linear models is governed by simpler, dimension-based principles, with deviations arising only from specific geometric obstructions (non-transversal intersections).