Introduction
In probabilistic modeling, researchers and practitioners often begin with "local" information—such as marginal distributions or conditional probability tables derived from noisy observations or expert intuition. A fundamental question immediately arises: Is this local data actually consistent with any global joint distribution?
For example, if data for three variables suggests that $X$ and $Y$ usually disagree, $Y$ and $Z$ usually disagree, and $X$ and $Z$ usually disagree, no valid joint distribution can satisfy all three conditions simultaneously.
Historically, determining the consistency of marginals was treated as a distinct challenge from standard "model-based" inference tasks, such as finding the Most Probable Explanation (MAP). This paper bridges that gap, establishing a formal computational equivalence between "pure data" marginal problems and graphical model inference.
The Four Marginal Challenges
Beyond simple consistency checking, the authors tackle three related data-centric challenges:
- Closest Consistency: If the observed data is inconsistent due to noise, what is the minimal adjustment required to make it consistent?
- Small Support: Can we find a consistent joint distribution that assigns non-zero probability to only a small (polynomial) number of outcomes? This minimizes "randomness" and is particularly useful in game theory and specific data-fitting scenarios.
- Maximum Entropy: Among all possible consistent distributions, which one is the "most random" (highest entropy)?
Methodology: The Ellipsoid Method and LP Duality
To connect these problems to inference, the authors employ a powerful technique from combinatorial optimization: polynomial-time reductions via the Ellipsoid method.
First, the consistency problem is framed as a Linear Program (LP). The "primal" version of this LP is computationally intractable because it requires one variable for every possible joint assignment (e.g., $2^n$ variables for $n$ binary nodes). However, by converting this to a "dual" LP, the number of variables shrinks to match the number of given marginals, while the number of constraints becomes exponential.
Solving an LP with exponential constraints using the Ellipsoid method requires a "separation oracle"—a subroutine that can quickly check if a candidate solution violates any constraints. The authors' breakthrough insight is proving that finding a violated constraint in this dual LP is mathematically identical to performing MAP Inference in a Markov network.
Essentially, a MAP inference engine can be "plugged in" as the separation oracle to solve these data-centric marginal problems. The reduction works by constructing "fictitious" Markov networks where the log-potentials are derived from the dual variables of the consistency problem.
Key Results and the Reduction Hierarchy
The paper provides a comprehensive hierarchy of reductions, proving that algorithmic progress in inference automatically yields progress for pure data problems.
As illustrated in the reduction hierarchy:
- Consistency, Closest Consistency, and Small Support all reduce to MAP Inference in polynomial time for any arbitrary graph class $\mathcal{G}$.
- Maximum Entropy reduces to the Generalized Partition problem (calculating the normalizing constant of a distribution).
Furthermore, the authors prove a significant result regarding succinctness: for any consistent set of $m$ marginal values, there exists a witnessing joint distribution with a support size of at most $m+1$. This guarantees that the "proof" of consistency can always be represented efficiently.
Implications and Limitations
Because these results are not tied to a specific algorithm, they offer broad generality. If a faster method for MAP inference on a specific class of graphs is discovered, solving marginal problems for that class becomes faster immediately. Conversely, if a marginal consistency problem is proven NP-hard for a certain graph class, MAP inference for that class must also be NP-hard.
While theoretically profound, the paper focuses on computational complexity rather than production-ready implementations. The reductions rely on the Ellipsoid method, which is notoriously slow in practice compared to other LP solvers like Interior Point methods. Additionally, the theoretical reduction assumes access to a perfect MAP oracle, whereas practical applications often rely on approximate MAP inference algorithms. Future work will need to explore how these approximations impact the accuracy of consistency checks.
Summary updated