Computing Maximum Entropy Distributions Everywhere

Damian Straszak, Nisheeth K. Vishnoi

Introduction

Maximum entropy (max-entropy) distributions are a cornerstone of statistical modeling and machine learning, providing the "least biased" estimation consistent with observed aggregate statistics, or marginal vectors. Formally, given a support set $\mathcal{X} \subseteq \mathbb{R}^m$ and a target marginal vector $x^\star$ in the convex hull of $\mathcal{X}$, the goal is to find a probability distribution $p$ that maximizes the Shannon entropy $H(p) = -\sum_{\alpha \in \mathcal{X}} p_\alpha \log p_\alpha$ subject to the constraint $\sum_{\alpha \in \mathcal{X}} p_\alpha \alpha = x^\star$.

While theoretically robust, the practical application of max-entropy models has historically faced two significant hurdles: bit complexity and stability. In "Maximum Entropy Distributions: Bit Complexity and Stability," Damian Straszak and Nisheeth K. Vishnoi address these challenges, proving that these distributions can be succinctly represented and remain stable even when the marginals approach the boundary of the feasible region.

The Challenge of the Boundary

The primary difficulty in computing max-entropy distributions lies in the size of the support set $\mathcal{X}$, which is often exponentially large (e.g., $2^m$). Traditional computational approaches rely on the Lagrange dual of the entropy maximization problem. However, previous bounds on the bit complexity of the dual variables—the number of bits required to represent the solution—were heavily dependent on the distance of the marginal vector $x^\star$ from the boundary of the marginal polytope $P = \text{conv}(\mathcal{X})$.

In real-world scenarios, empirical marginals often lie extremely close to this boundary. When $x^\star$ is near the boundary, previous complexity bounds exploded toward infinity, suggesting that the distributions might be computationally intractable or numerically unstable for practical data. This paper seeks to resolve whether max-entropy distributions remain feasible in these edge cases.

Methodological Framework

Straszak and Vishnoi shift the focus from combinatorial arguments to pure convex analysis and the geometric properties of the marginal polytope. Their approach centers on the Lagrange dual space, which reduces the problem from a variable for every state in the support to just $m$ variables (one for each constraint).

Unary Facet Complexity

The authors identify "unary facet complexity" as a critical metric. A polytope has low unary facet complexity if it can be defined by linear inequalities with small integer coefficients. This property is characteristic of many important combinatorial structures, including matroids, matchings, and submodular polytopes. By leveraging this property, the authors demonstrate that bit complexity can remain low regardless of the marginal vector's proximity to the boundary.

Geometric Dual Analysis and Truncation

The research introduces a technique to "truncate" optimal dual solutions. Instead of seeking the exact dual optimum, which might have high bit complexity, they show how to find a nearby solution that is nearly optimal but possesses a polynomial bit length. This is achieved through a refined analysis of the dual objective function's growth near the boundary, ensuring that the resulting distribution is a close approximation of the true max-entropy distribution.

Algorithmic Implementation

To prove the feasibility of computing these distributions, the authors employ the Ellipsoid Method. They establish that if one has access to a "counting oracle" for the support set $\mathcal{X}$, the max-entropy distribution can be computed in polynomial time. This provides a rigorous algorithmic guarantee for problems where counting is efficient.

Key Results

The paper provides several breakthrough results that bridge the gap between theory and practice:

  • Bit Complexity Bounds: For polytopes with low unary facet complexity, an $\epsilon$-optimal dual solution has a bit complexity of $poly(m, \log 1/\epsilon)$. Crucially, this bound is independent of the distance to the boundary of the polytope.
  • Polynomial Stability: The authors prove that the max-entropy distribution is robust. If the marginal vector $x^\star$ is perturbed by a small value $\delta$, the resulting distribution changes (in total variation distance) by at most $poly(m, \log 1/\delta)\sqrt{\delta}$. This ensures that the model is resistant to noise in the input data.
  • Algorithmic Applications: These theoretical guarantees extend to several specific problems, providing the first polynomial-time algorithms with guaranteed bit complexity for Matrix Scaling and calculating Brascamp-Lieb constants in rank-1 cases.

Limitations and Future Work

Despite these advances, the work identifies areas for further exploration. The stability result currently features a $\sqrt{\delta}$ dependence; improving this to a linear $\delta$ dependence remains an open question. Additionally, while the lower bounds established using high-facet-complexity polytopes (based on Alon-Vu constructions) show where bit complexity must fail, it is unclear if similar "bad" cases exist for simpler 0-1 polytopes. Finally, the reliance on a counting oracle means that for support sets where counting is #P-hard, the computational challenge persists.

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{straszak2017computing,
  author = {Damian Straszak and Nisheeth K. Vishnoi},
  title = {{Computing Maximum Entropy Distributions Everywhere}},
  booktitle = {Conference},
  year = {2017},
  doi = {10.48550/arxiv.1711.02036},
}

Loading related content...

Figure