Maximum Entropy Distributions: Bit Complexity and Stability.

Damian Straszak, Nisheeth K. Vishnoi

Abstract

Maximum entropy distributions with discrete support in $m$ dimensions are fundamental to machine learning, statistics, and theoretical computer science. Despite their widespread use, two critical questions have remained unresolved: whether these distributions admit succinct descriptions (polynomial-size bit complexity) when the support is exponentially large, and whether they remain stable under perturbations of the marginal vector. This paper resolves both questions by establishing a ${\rm poly}(m, \log 1/\varepsilon)$ bound on the bit complexity of $\varepsilon$-optimal dual solutions. We demonstrate that these distributions are both computationally feasible and robust, even when marginal vectors approach the boundary of the marginal polytope. Our results provide a unified framework for polynomial-time algorithms in matrix scaling, Brascamp-Lieb constant computation, and combinatorial counting.

Introduction

In many scientific and engineering contexts, we seek to model a probability distribution over a large discrete set (e.g., all possible matchings in a graph or all $m$-bit strings) such that the distribution matches certain observed statistics, known as the marginal vector. The Principle of Maximum Entropy suggests that the most appropriate distribution is the one that is "least biased"—having the highest entropy—while satisfying these constraints.

While the structural properties of these distributions are well-understood, their computational and robustness properties have faced significant theoretical hurdles. Specifically, if the support set is of size $2^m$, can we represent the resulting distribution using a number of bits polynomial in $m$? Furthermore, if our observed marginals are slightly noisy, does the resulting distribution change drastically? This paper provides the first rigorous proof that max-entropy distributions are both succinct and stable.

The Challenges of Scale and Boundaries

The maximum entropy problem is typically solved via its Lagrange dual. While the primal problem involves a variable for every element in the support (potentially billions), the dual problem only requires $m$ variables. However, the "succinctness" of the distribution depends on the bit complexity of these $m$ dual variables.

Previous research provided bounds on bit complexity that were effective only when the marginal vector was strictly in the interior of the marginal polytope. In practice, however, marginal vectors derived from empirical data often lie near the boundary. The authors prove that empirical means are actually highly likely to lie near these boundaries, making previous interior-only bounds practically insufficient. This paper addresses this gap, providing bounds that hold universally across the entire polytope.

Technical Innovation: Unary Facet Complexity

The authors introduce the concept of Unary Facet Complexity to bridge the gap between geometry and bit complexity. They show that if the polytope defining the possible marginals can be described by linear inequalities with small integer coefficients, the dual solution remains well-behaved.

The proof relies on a sophisticated geometric analysis:

  • Basis Selection: Identifying a favorable basis for the dual space that prevents coefficients from exploding.
  • Truncation: Demonstrating that dual coefficients can be truncated without significant loss of optimality.
  • Polyhedral Geometry: Proving that for any optimal solution, even one far from the origin, there exists a "short" vector in the dual space that achieves nearly the same objective value.

Key Results

1. Bit Complexity and Succinctness

The primary result is a proof that for any marginal vector, an $\varepsilon$-optimal dual solution can be represented using ${\rm poly}(m, \log 1/\varepsilon)$ bits. This ensures that max-entropy distributions are succinct even when the underlying support is exponential. This holds for very general support sets with no restriction on the marginal vector.

2. Stability of Distributions

The paper establishes a direct link between bit complexity and stability. It proves that if the marginal vector is perturbed by a distance $\delta$, the resulting change in the distribution (measured in Total Variation distance) is bounded by roughly ${\rm poly}(m, \log 1/\delta)\sqrt{\delta}$. This result confirms that max-entropy models are robust against noise in the input data, a crucial property for generalization in machine learning.

3. Algorithmic Unified Framework

These theoretical bounds lead to practical algorithmic improvements across several domains:

  • Matrix Scaling: The work provides the first polynomial bit complexity bounds for the $(r, c)$-matrix scaling problem that depend only on input size and desired precision.
  • Brascamp-Lieb Constants: It enables a polynomial-time algorithm for computing these constants in the rank-1 case, a problem significant in geometric analysis.
  • Combinatorial Counting: The results facilitate the efficient computation of continuous relaxations used to count complex combinatorial objects like matroids and spanning trees.

Conclusion and Future Work

By providing rigorous bounds on bit complexity and stability, this research puts maximum entropy distributions on a firm mathematical footing. These distributions are shown to be not just theoretically elegant, but also computationally robust and efficient models for high-dimensional data.

Several open questions remain. The authors note a gap in the stability bound, suggesting it might be possible to improve the dependence from $\sqrt{\delta}$ to a linear $\delta$. Additionally, while they provide a lower bound showing some polytopes require high bit complexity, it remains to be seen if such "bad" examples exist in the 0-1 regime where all vertices of the polytope are binary.

Summary updated

Abstract

Maximum entropy distributions with discrete support in $m$ dimensions arise in machine learning, statistics, information theory, and theoretical computer science. While structural and computational properties of max-entropy distributions have been extensively studied, basic questions such as: Do max-entropy distributions over a large support (e.g., $2^m$) with a specified marginal vector have succinct descriptions (polynomial-size in the input description)? and: Are entropy maximizing distributions stable under the perturbation of the marginal vector? have resisted a rigorous resolution. Here we show that these questions are related and resolve both of them. Our main result shows a ${\rm poly}(m, \log 1/\varepsilon)$ bound on the bit complexity of $\varepsilon$-optimal dual solutions to the maximum entropy convex program -- for very general support sets and with no restriction on the marginal vector. Applications of this result include polynomial time algorithms to compute max-entropy distributions over several new and old polytopes for any marginal vector in a unified manner, a polynomial time algorithm to compute the Brascamp-Lieb constant in the rank-1 case. The proof of this result allows us to show that changing the marginal vector by $\delta$ changes the max-entropy distribution in the total variation distance roughly by a factor of ${\rm poly}(m, \log 1/\delta)\sqrt{\delta}$ -- even when the size of the support set is exponential. Together, our results put max-entropy distributions on a mathematically sound footing -- these distributions are robust and computationally feasible models for data.
BibTeX
@inproceedings{straszak2017maximum,
  author = {Damian Straszak and Nisheeth K. Vishnoi},
  title = {{Maximum Entropy Distributions: Bit Complexity and Stability.}},
  booktitle = {Conference},
  year = {2017},
  doi = {10.48550/arxiv.1711.02036},
}
Figure