Entropy, Optimization and Counting

Introduction

While there is a vast amount of literature concerning the computation of max-entropy distributions (see for example the survey ), previous (partial) results on computing max-entropy distributions required exploiting some special structure of the particular problem at hand. In theoretical computer science, interest in rigorously computing max-entropy distributions derives from their applications to randomized rounding and the design of non-trivial approximation algorithms, notably to problems such as the symmetric and the asymmetric traveling salesman problem (TSP/ATSP). For example, using a very technical argument, give an algorithm to compute the max-entropy distribution over spanning trees of a graph. This algorithm was then used by them to improve the approximation ratio for ATSP, and by to improve the approximation ratio for (graphical) TSP, making progress on two long-standing problems. Subsequently, the ability to compute max-entropy distributions over spanning trees has also been used to design efficient privacy preserving mechanisms for spanning tree auctions by . In another example, show how to compute max-entropy distributions over perfect matchings in a tree and use it to design approximation algorithms for a max-min fair allocation problem. The question of computing max-entropy distributions over perfect matchings in bipartite (and general) graphs, however, has been an important open problem. Recent applications of the ability to compute max-entropy distribution over perfect matchings in bipartite graphs include new approaches for TSP and ATSP, see and Section 4.

For counting problems, it is rare to obtain algorithms that can count exactly, notable exceptions being the problem of counting spanning trees in a graph or counting certain problems restricted to trees using dynamic programming. Most natural counting problems turn out to be $\#$P-hard including the problem to count the number of perfect matchings in a bipartite graph . The goal then shifts to finding algorithms that approximately count up to any fixed precision . Here the most successful technique has been the Markov chain Monte Carlo (MCMC) method which, when combined with the equivalence between approximate counting and sampling We note that MCMC methods efficiently sample (and count) given a fixed $\gamma,$ usually for $\gamma={1}$ corresponding to the uniform distribution. The goal in our problem is to find an ${\gamma}$ that maximizes the entropy. In fact, given a ${\gamma},$ problem specific MCMC methods can be used to generate a random sample from ${\mathcal{M}}$ according to the product distribution corresponding to $\gamma.$, leads to many approximate counting algorithms. The technique has been applied to many problems including counting perfect matchings in a bipartite graph , counting bases in a balanced matroid , counting solutions to a knapsack problem and counting the number of colorings in restricted graph families . However, the problem of obtaining approximate counting oracles for several problems remains open as well; perhaps a prominent example is that of (approximately) counting the number of perfect matchings in a general graph.

In combinatorics, max-entropy distributions are often referred to as hard-core or Gibbs distributions and have been intensely studied. While it is nice that the hard-core distribution has a product form, i.e., $p_{M}\propto\prod_{e\in M}\gamma_{e},$ the question of interest here is whether one can upper bound the $\gamma_{e}$s. Structurally, such a bound implies that hard-core distributions exhibit a significant amount of approximate stochastic independence. In an important result, proved such a bound for the hard-core distribution over matchings in a graph. This led to resolving several questions involving asymptotic graph and hypergraph problems. For instance results of prove that the fractional chromatic index of a graph asymptotically behaves as its chromatic index. However, the argument of is quite difficult and seems to be specific to the setting of matchings leaving it an interesting problem to understand under what conditions can one obtain upper bounds on $\gamma_{e}$s.

We first show that good enough succinct representations exist for max-entropy distributions. Subsequently, we give an algorithm that computes arbitrarily good approximations to max-entropy distributions given ${\theta}$ and access to a suitable counting oracle for ${\mathcal{M}}.$ Our algorithm is efficient whenever the corresponding counting oracle is efficient. Moreover, the counting oracle can be approximate and/or randomized. This allows us to leverage a variety of algorithms developed for several $\#$P-hard problems to give algorithms to compute max-entropy distributions. Consequently, we obtain several new and old results about concrete algorithms to compute max-entropy distributions. Interesting examples for which we can use pre-existing counting oracles to obtain max-entropy distributions include spanning trees, matchings in general graphs, perfect matchings in bipartite graphs (using the algorithm from ) and subtrees of a rooted tree. The consequence for perfect matchings in bipartite graphs makes the algorithmic strategies for TSP/ATSP mentioned earlier computationally feasible, see Section 4. In the reverse direction we show that if one can solve, even approximately, the convex optimization problem of computing the max-entropy distribution, one can obtain such counting oracles. This establishes an equivalence between counting and computing max-entropy distributions in a general setting. As a corollary, we obtain that the problem of computing max-entropy distributions over perfect matchings in general graphs is equivalent to the, hitherto unrelated, problem of approximately counting perfect matchings in a general graph.

Before we describe our results a bit more technically, we introduce some basic notation. For ${\mathcal{M}}\subseteq\{0,1\}^{m},$ let $P({\mathcal{M}})$ denote the convex hull of all ${\mathcal{M}}$ where each $M\in{\mathcal{M}}$ is thought of as a $0/1$ vector of length $m$, denoted $1_{M}.$ Thus, given a ${\theta},$ for the max-entropy program to have any solution, ${\theta}\in P({\mathcal{M}}).$ Since we are concerned with the case when ${\mathcal{M}}$ is given implicitly and may be of exponential size, we no longer hope to solve the max-entropy convex program directly since that may require exponentially many variables, one for each $M\in{\mathcal{M}}.$ Thus, we work with the dual to the max-entropy convex program. The dual has $m$ variables and, if ${\theta}$ is in the relative interior of $P({\mathcal{M}}),$ the optimal dual solution can be used to describe the optimal solution to the max-entropy convex program, which is a product distribution. In fact, we assume one can put a ball of radius $\eta$ around ${\theta}$ and it still remains in the interior of $P({\mathcal{M}}).$ Importantly, our algorithm requires access to a generalized counting oracle for ${\mathcal{M}},$ which given $\gamma$ can compute $\sum_{M\in{\mathcal{M}},\;M\ni e}\prod_{e^{\prime}\in M}\gamma_{e^{\prime}}$ for all $e\in[m]$ and also the sum $\sum_{M\in{\mathcal{M}}}\prod_{e\in M}\gamma_{e}.$ We also consider the case when the oracle is approximate (possibly randomized) and for a given $\varepsilon,$ can output the sums above up to a multiplicative error of $1\pm\varepsilon.$ The following is the first main result of the paper, stated informally here.

There is an algorithm which, given access to a generalized (approximate) counting oracle for ${\mathcal{M}}\subseteq\{0,1\}^{m},$ a ${\theta}$ which is promised to be in the $\eta$-interior of $P({\mathcal{M}})$ and an $\varepsilon>0,$ outputs a $\gamma$ such that its corresponding product probability distribution $p$ is such that $H(p)\geq(1-\nicefrac{{\varepsilon}}{{\eta}})H(p^{\star})$ and for every $e\in[m],$

Here, $p^{\star}$ is the max-entropy distribution corresponding to ${\theta}.$ The number of calls the algorithm makes to the oracle is bounded by a polynomial in the input size, $\ln\nicefrac{{1}}{{\eta}}$ and $\ln\nicefrac{{1}}{{\varepsilon}}.$

A useful setting for $\eta$ and $\varepsilon$ to keep in mind is $\nicefrac{{1}}{{m^{2}}}$ and $\nicefrac{{1}}{{m^{3}}}$ respectively. The bit-lengths of the inputs to the counting oracle are polynomial in $\nicefrac{{1}}{{\eta}}$ and, hence, the running time of our algorithm depends polynomially on $\nicefrac{{1}}{{\eta}}.$ If the generalized counting oracle is $\varepsilon$-approximate, the same guarantee holds. Note that for many approximate counting oracles, the dependence on $\varepsilon$ on their running time is a polynomial in $\nicefrac{{1}}{{\varepsilon}}.$ Hence, in this case the running time depends polynomially on $\nicefrac{{1}}{{\varepsilon}}.$ Finally, note that this result can be easily generalized to obtain algorithms for the problem of finding the distribution that minimizes the Kullback-Leibler divergence from a given product distribution subject to the marginal constraints, see Remark 2.12.

At a very high level, the algorithm in this theorem is obtained by applying the framework of the ellipsoid algorithm to the dual of the max-entropy convex program. While it is more convenient to work with the dual since it has $m$ variables two issues arise: The domain of optimization becomes unconstrained and the separation oracle requires the ability to compute (possibly exponential sums) over subsets of ${\mathcal{M}}.$ While the counting oracles can be adapted to compute exponential sums, the unboundedness of the domain of optimization is an important problem.

Given that counting algorithms for many problems are still elusive, one may ask if they are really necessary to compute max-entropy distributions. The final result of this paper answers this question in the affirmative and establishes a converse to Theorem 1.1.

There is an algorithm, which given oracle access to an algorithm to compute an $\varepsilon$-approximation to the max-entropy convex program for an $\eta$-interior point of $P({\mathcal{M}}),$ and a separation oracle for $P({\mathcal{M}}),$ can compute a number $Z$ such that

The number of calls made to the max-entropy oracle is polynomial in the input size and $\nicefrac{{1}}{{\varepsilon}}.$

This result can be extended to obtain generalized counting oracles, see Remark 2.12. For all polytopes of interest in this paper, separation oracles are known, see Section 3. Moreover, this result continues to hold even when the separation oracle is approximate, or weak. As a corollary, using a separation oracle for the perfect matching polytope for general graphs , we obtain that an algorithm to compute a good-enough approximation to the max-entropy distribution for any ${\theta}$ in the perfect matching polytope of a graph $G$ implies an FPRAS to count the number of perfect matchings in the same graph.

2 Technical Overview

The starting point for our results is the following dual to the max-entropy convex program:

where $1_{M}$ is the indicator vector for $M.$ When ${\theta}$ lies in the relative interior of $P({\mathcal{M}}),$ then strong duality holds between the primal and the dual. When $\theta$ lies on the boundary of $P({\mathcal{M}}),$ the infimum in the dual is not attained for any finite $\lambda.$ Hence, it follows from the first order conditions on the optimal solution pair $(p^{\star},{\lambda}^{\star})$ that $p^{\star}_{M}\propto e^{-{\langle{{\lambda}^{\star}},{1_{M}}\rangle}}$ for each $M\in{\mathcal{M}}$. Suppose we know that

${\lambda}^{\star}$ is bounded, i.e., $\|{\lambda}^{\star}\|\leq R$ for some $R,$ and

there is a generalized counting oracle that allows us to compute the gradient of the objective function $f({\lambda})\stackrel{{\scriptstyle\textup{def}}}{{=}}{\langle{{\lambda}},{{\theta}}\rangle}+\ln\sum_{M\in{\mathcal{M}}}e^{-{\langle{{\lambda}},{1_{M}}\rangle}}$ at a specified ${\lambda}.$ The gradient at ${\lambda},$ denoted $\nabla f({\lambda}),$ turns out to be a vector whose coordinate corresponding to $e\in[m]$ is

Then, using the machinery of the ellipsoid method, it follows relatively straight-forwardly that, for any $\varepsilon,$ we can compute a point ${\lambda}^{\circ}$ such that $f({\lambda}^{\circ})\leq f({\lambda}^{\star})+\varepsilon$ with at most a poly$(m,\ln\nicefrac{{1}}{{\varepsilon}},\ln R)$ calls to the counting oracle. Note that since the numbers fed into the counting oracle are of the form $e^{-\lambda_{e}},$ for each $e\in[m],$ the running time of the counting oracle depends polynomially on $R$ rather than $\ln R.$ Thus, we need $R$ to be polynomially bounded. Hence, the question is:

Using this, the $\eta$-interiority of ${\theta},$ and the fact that the diameter of $P({\mathcal{M}})$ is at most $\sqrt{m},$ it can then be shown that

Let us show how this immediately implies a bound on $R$ when ${\mathcal{M}}$ corresponds to all the spanning trees of a graph with no bridge. Suppose $T$ and $T^{\prime}$ are two trees such that $T^{\prime}$ is obtained from $T$ by deleting an edge $e$ and adding an edge $f,$ then,

Thus, unless the graph has a bridge, this implies $|\lambda^{\star}_{e}-\lambda^{\star}_{f}|\leq\frac{m^{2}\sqrt{m}}{\eta}$ for all $e,f\in G.$ However, attempting a similar combinatorial argument for perfect matchings in a bipartite graph, where we do not have this exchange property, the bound is worse by a factor of $2^{m}.$

Thus, the ellipsoid method can be used to obtain a solution ${\lambda}^{\circ}$ such that $f({\lambda}^{\circ})\leq f({\lambda}^{\star})+\varepsilon.$ Why should this approximate bound imply that the product distribution obtained using ${\lambda}$ is close in the marginals to ${\theta}$? The observation here is that $f({\lambda}^{\circ})-f({\lambda}^{\star})$ is the Kullback-Leibler (KL) divergence between the two distributions. This implies a bound of $\sqrt{\varepsilon}$ on the marginals using a standard upper bound on the total variation distance in terms of the KL-divergence.

In the case when we have access only to an approximate counting oracle for ${\mathcal{M}},$ things are more complicated. Roughly, the approximate counting oracle translates to having access to an approximate gradient oracle for the function $f(\cdot)$ and one has to ensure that ${\lambda}^{\star}$ is not cut-off during an iteration. Technically, we show that this does not happen and, hence, approximate counting oracles are equally useful for obtaining good approximations to max-entropy distributions.

Finally, note that the (projected-)gradient descent approach (see ) can also be shown to converge in polynomial time and, possibly, can result in practical algorithms for computing max-entropy distributions. In the case when the counting oracle is approximate, one has to deal with a noisy gradient and the solution turns out to be similar to the one in the ellipsoid method-based algorithm in the presence of an approximate counting oracle. In addition to a bound on $\|\lambda^{\star}\|,$ one needs to bound the $2\rightarrow 2$ norm of the gradient of $f.$ While we omit the details of the gradient descent based-algorithm, we show that $\|\nabla f\|_{2\rightarrow 2}$ is polynomially bounded, see Remark 2.9 and Theorem C.1 in Appendix C. This bound may be of independent interest.

We now give an overview of the reverse direction: How to count approximately given the ability to solve the max-entropy convex program for any point ${\theta}$ in the $\eta$-interior of $P({\mathcal{M}}).$ We start by noting that if we consider ${\theta}^{\star}\stackrel{{\scriptstyle\textup{def}}}{{=}}\frac{1}{|{\mathcal{M}}|}\sum_{M\in{\mathcal{M}}}1_{M},$ then the optimal value of the convex program is $\ln|{\mathcal{M}}|.$ Thus, given access to this vertex-centroid of $P({\mathcal{M}})$ one can get an estimate of $|{\mathcal{M}}|.$ However, computing $\theta^{\star}$ can be shown to be as hard as counting $|{\mathcal{M}}|,$ for instance, when ${\mathcal{M}}$ consists of perfect matchings in a bipartite graph, see . We bypass this obstacle and apply the ellipsoid algorithm on the following (convex-programming) problem

where $f_{{\theta}}({\lambda})$ is the function in (1) and where we have chosen to highlight the dependence on ${\theta}.$ The ellipsoid algorithm proposes a $\theta$ and expects the max-entropy oracle to output an approximate value for $\inf_{{\lambda}}f_{{\theta}}({\lambda}).$ This raises a few issues: First, given our result on optimization via counting, it is unfair to assume that we have such an oracle that works for all ${\theta},$ irrespective of the interiority of $\theta$ in $P({\mathcal{M}}).$ Thus, we allow queries to the oracle only when ${\theta}$ is sufficiently in the interior of $P({\mathcal{M}}).$ Note that our algorithm for computing the max-entropy distribution in our first theorem works under these guarantees. This requires, in addition, a separation oracle for checking whether a point is in the $\eta$-interior of $P({\mathcal{M}}).$ We construct such an $\eta$-separation oracle from a separation oracle for $P({\mathcal{M}}).$ The latter, given a point, either says it is in $P({\mathcal{M}})$ or returns an inequality valid for $P({\mathcal{M}})$ but violated by this point.

The second issue is that $\theta^{\star},$ our target point, may not be in the $\eta$-interior of $P({\mathcal{M}}).$ In fact, there may not be any point in the $\eta$-interior of $P({\mathcal{M}})$ when $\eta$ is $\nicefrac{{1}}{{{\rm poly}(m)}}.$ However, under reasonable conditions on $P({\mathcal{M}}),$ which are satisfied for all polytopes we are interested in, we can show that there is a point $\theta^{\bullet}$ in the $\eta$-interior of $P({\mathcal{M}}).$ This allows us to recover a good enough estimate of $|{\mathcal{M}}|.$ Thus (the way we apply the framework of ellipsoid algorithm), we are able to recover a point close enough to $\theta^{\bullet}$ by doing a binary search on the target value of $|{\mathcal{M}}|.$ As in the forward direction, because we assume that the max-entropy algorithm is approximate, we must argue that $\theta^{\bullet}$ is not cut-off during any iteration of the ellipsoid algorithm.

We conclude this overview with a couple of remarks. First, unlike our results in the forward direction, we cannot replace the ellipsoid method based algorithm by a gradient descent approach. The reason is that we only have a separation oracle to detect whether a point is in $P({\mathcal{M}})$ or not. Second, we can extend our result to show that, using a max-entropy oracle, one can obtain generalized approximate counting oracles, see Remark 2.12.

3 Organization of the Rest of the Paper

The rest of the paper is organized as follows. In Section 2, we formally define the objects of interest in our paper including the convex program for optimizing the max-entropy distribution and its dual. We also define counting oracles that are needed for solving the convex program. We then formally state our results and give a few lemmas stating properties about the optimal and near-optimal solution to the dual of the max-entropy convex program. In Section 3 we provide examples of some combinatorial polytopes to which our results apply. In Section 4, we show how certain algorithmic approaches for approximating the symmetric and the asymmetric traveling salesman problem are feasible as a result of one of the main results of this paper. In Section 5, we prove that there is an optimal solution to the dual of the max-entropy convex program that is contained in a ball of small radius around the origin. In Section 6, we use this bound on the optimal solution to show that counting oracles, both exact and approximate, can be used to optimize the convex program via the ellipsoid algorithm. In Section 7, we show the other direction of the reduction and give an algorithm that can approximately count given an oracle that can approximately solve the max-entropy convex program. Standard proofs are omitted from the main body and appear in Appendix A. In Appendix B we show how generalized counting oracles can be obtained via max-entropy oracles. Here, we also introduce the program for minimizing the KL-divergence with respect to a fixed distribution. Finally, in Appendix C, we give a bound on $\|\nabla f\|_{2\rightarrow 2}.$

Preliminaries

2 Combinatorial Polytopes, Separation Oracles, Counting Oracles and Interiority

The polytopes of interest arise as convex hulls of subsets of $\{0,1\}^{m}$ for some $m.$ For a set ${\mathcal{M}}\subseteq\{0,1\}^{m},$ the corresponding polytope is denoted by $P({\mathcal{M}}).$ Thus,

Another way to describe $P({\mathcal{M}})$ is to give a maximal set of linearly independent equalities satisfied by all its vertices, and to list the inequalities that define $P({\mathcal{M}}).$ Thus, $P({\mathcal{M}})$ can be described by $(A^{=},b)$ and $(A^{\leq},c)$ such that

While the former set cannot be more than $m,$ the latter set can be exponential in $m$ and we do not assume that $(A^{\leq},c)$ is given to us explicitly.

In fact, such an oracle is often termed a strong separation oracle. In our results that depend on access to a strong separation oracle, we can relax the guarantee to that of a weak separation oracle. We omit the details.

Counting Oracles. The standard counting problem associated to ${\mathcal{M}}$ is to determine $|{\mathcal{M}}|,$ i.e., the number of vertices of $P({\mathcal{M}}).$ We are interested in a more general counting problem associated to ${\mathcal{M}}$ where there is a weight $\lambda_{e}$ for each $e\in[m]$ and the weight of $M$ under this measure is $e^{-\lambda(M)}.$ A generalized exact counting oracle for ${\mathcal{M}}$ then outputs the following two quantities:

$Z^{{\lambda}}\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{M\in{\mathcal{M}}}e^{-\lambda(M)}$ and

for every $e\in[m],\;\;Z^{{\lambda}}_{e}\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{M\in{\mathcal{M}},\;M\ni e}e^{-\lambda(M)}.$

The oracle is assumed to be efficient, as in it runs in time polynomial in $m$ and bits needed to represent $e^{-\lambda_{e}}$ for any $e\in[m]$. To deal with issues of irrationality, it suffices to obtain the first $k$ bits of $Z^{{\lambda}}$ and $Z^{{\lambda}}_{e}$ in time polynomial in $k$ and $m$.

$(1-\varepsilon)Z^{\lambda}\leq\widetilde{Z}^{{{\lambda}}}\leq(1+\varepsilon)Z^{\lambda}$ and

for every $e\in[m],$ $(1-\varepsilon)Z^{\lambda}_{e}\leq\widetilde{Z}^{{\lambda}}_{e}\leq(1+\varepsilon)Z^{\lambda}_{e}.$

The running time is polynomial in $m$, $\nicefrac{{1}}{{\varepsilon}},$ $\log{\nicefrac{{1}}{{\alpha}}}$ and the number of bits needed to represent $e^{-\lambda_{e}}$ for any $e\in[m]$. For the sake of readability, we ignore the fact that approximate counting oracle may be randomized. The statements of the theorems that use randomized approximate counting oracles can be modified appropriately to include the dependence on $\alpha.$ Note that if the problem at hand is self-reducible, then having access to an oracle that outputs an approximation to just $Z^{\lambda}$ suffices. We omit the details and the reader is referred to a discussion on self-reducibility and counting in . Finally, it can be shown that, in our setting, the existence of a generalized (exact or approximate) counting oracle is a stronger requirement than the existence of a separation oracle.

Interior of the Polytope. The dimension of $P({\mathcal{M}})$ is $m-{\rm rank}(A^{=});$ the polytope restricted to this affine space is full dimensional. Since we work with polytopes that are not full dimensional, we extend the notion of the interior of the polytope $P({\mathcal{M}})$ and use the following definition.

For an $\eta>0,$ a point $\theta$ is said to be in the $\eta$-interior of $P({\mathcal{M}})$ if

We say that $\theta$ is in the interior of $P({\mathcal{M}})$ if $\theta$ is in the $\eta$-interior of $P({\mathcal{M}})$ for some $\eta>0.$

We are be interested in the case where $\eta\geq\frac{1}{{\rm poly}(m)}.$ Hence, it is natural to ask if for every $P({\mathcal{M}}),$ there is a point in its $\frac{1}{{\rm poly}(m)}$-interior. The following lemma, whose proof appears in Section 7, asserts that the answer is yes if the entries of $A^{\leq}$ and $c$ are reasonable (as is the case in all our applications).

At this point, if one wishes, one can look at Section 3 for some examples of combinatorial polytopes we consider in this paper.

3 The Maximum Entropy Convex Program

In this section we present the convex program for computing max-entropy distributions. Let $P({\mathcal{M}})$ be the polytope corresponding to ${\mathcal{M}}.$ While we do not care about whether we have an oracle for ${\mathcal{M}}$ in this section, the notion of interiority is important.

For any point $\theta\in P({\mathcal{M}}),$ by definition, it can be written as a convex combination of vertices of $P({\mathcal{M}}),$ each of which is indicator vector for some $M\in{\mathcal{M}}$. Each such convex combination is a probability distribution over $M\in{\mathcal{M}}.$ Of central interest in this paper is a way to find the convex combination that maximizes the entropy of the underlying probability distribution. Given $\theta,$ we can express the problem of finding the max-entropy distribution over the vertices of $P({\mathcal{M}})$ as the program in Figure 1.

For a point $\theta$ in the interior of $P({\mathcal{M}}),$ there exists a unique distribution $p^{\star}$ which attains the max-entropy while satisfying

As we observe soon, while $p^{\star}$ is unique, $\lambda^{\star}$ may not be. First, we record the following definitions about such product distributions.

The marginals of such a distribution are denoted by $\theta^{{\lambda}}$ and defined to be

The proof of this lemma relies on establishing that strong duality holds for computing the max-entropy distribution with marginals $\theta$ for the convex program in Figure 1. The dual of this program appears in Figure 2. Thus, if $\theta$ is in the interior of $P({\mathcal{M}}),$ then there is a $\lambda^{\star}$ such that $p^{\star}=p^{\lambda^{\star}}$ and $f_{\theta}(\lambda^{\star})=H(p^{\star}).$

Note that $\lambda^{\star}$ may not be unique and, finally, that an important property of the dual objective function is that $f_{\theta}$ does not change if we shift by a vector in the span of the rows of $A^{=}.$ This is captured in the following lemma whose proof appears in Appendix A.2.

$f_{\theta}(\lambda)=f_{\theta}(\lambda+(A^{=})^{\top}d)$ for any $d.$

4 Formal Statement of Our Results

Our first result shows that if one has access to an generalized exact counting oracle then one can indeed compute a good approximation to the max-entropy distribution for specified marginals.

where $\lambda^{\star}$ is the optimal solution to the dual of the max-entropy convex program for $({\mathcal{M}},\theta)$ from Figure 2. Assuming that the generalized exact counting oracle is polynomial in its input parameters, the running time of the algorithm is polynomial in $m$, $\nicefrac{{1}}{{\eta}},$ $\log\nicefrac{{1}}{{\varepsilon}}$ and the number of bits needed to represent $\theta$ and $(A^{=},b).$

The proof of this theorem follows from an application of the ellipsoid algorithm for minimizing the dual convex program. At a first glance, it may seem enough to show that $\|\lambda^{\star}\|\leq 2^{\frac{{\rm poly}(m)}{\eta}}$ since the number of iterations of the ellipsoid algorithm depends on $\log\|\lambda^{\star}\|$. Unfortunately, this is not enough since each call to the oracle with input $\lambda$ takes time polynomial in the number of bits needed to represent $e^{-\lambda_{e}}$ for any $e\in[m]$. We show the following theorem which provides a polynomial bound on $\|\lambda^{\star}\|$.

We specifically note that the proof of this theorem needs that $\lambda^{\star}$ satisfies $A^{=}\lambda^{\star}=0.$ Combinatorially, it is an interesting open problem to see one can get such a bound depending only on $\nicefrac{{1}}{{\eta}}.$ Next we generalize Theorem 2.6 to polytopes where only an approximate counting oracle exists, for example, the perfect matching problem in bipartite graphs. While we state this theorem in the context of deterministic counting oracles, it holds in the randomized setting as well.

Here $\lambda^{\star}$ is an optimal solution to the dual of the max-entropy convex program for $({\mathcal{M}},\theta).$ Assuming that the generalized approximate counting oracle is polynomial in its input parameters, the running time of the algorithm is polynomial in $m$, $\nicefrac{{1}}{{\eta}}$, $\nicefrac{{1}}{{\varepsilon}}$ and the number of bits needed to represent $\theta$ and $(A^{=},b).$

It can be shown that once we have a solution $\lambda^{\circ}$ to the dual convex program such that

as in Theorems 2.6 and 2.8, one can show that the marginals obtained from the distribution corresponding to $\lambda^{\circ}$ is close to that of $\lambda^{\star}$ (which is $\theta$), i.e., $\left\|\theta^{{{{\lambda}}^{\circ}}}-\theta\right\|_{\infty}\leq O(\sqrt{\varepsilon}).$ See Appendix A.2, and in particular Corollary A.5 for a proof.

We can also obtain proofs of Theorems 2.6 and 2.8 by applying the framework of projected gradient descent. (See Section 3.2.3 in for details on the gradient descent method.) For the gradient descent method to be polynomial time, one would need an upper bound on $\|\lambda^{\star}\|$ and $\|\nabla f\|_{2\rightarrow 2}.$ The first bound is provided by Theorem 2.7 and the second bound is proved in Theorem C.1 in Appendix C. We have chosen the ellipsoid method-based proofs of Theorems 2.6 and 2.8 since the ellipsoid method is required in the proof of Theorem 2.11.

Our final theorem proves the reverse: If one can compute good approximations to the max-entropy convex program for $P({\mathcal{M}})$ for a given marginal vector, then one can compute good approximations to the number of vertices in $P({\mathcal{M}}).$ First, we need a notion of a max-entropy oracle for ${\mathcal{M}}.$

An approximate max-entropy oracle for ${\mathcal{M}},$ given a ${\theta}$ in the $\eta$-interior of $P({\mathcal{M}}),$ a $\zeta>0$, and an $\varepsilon>0$, either

asserts that $\inf_{{\lambda}}f_{{\theta}}({\lambda})\geq\zeta-\varepsilon$ or

The oracle is assumed to be efficient, i.e., it runs in time polynomial in $m$, $\nicefrac{{1}}{{\varepsilon}},$ $\nicefrac{{1}}{{\eta}}$ and the number of bits needed to represent $\zeta.$

This is consistent with the algorithms given by Theorem 2.6 and 2.8.

There exists an algorithm that, given a maximal set of linearly independent equalities $(A^{=},b)$ and a separation oracle and an approximate optimization oracle for ${\mathcal{M}}$ as above, returns a $\widetilde{Z}$ such that $(1-\varepsilon)|{\mathcal{M}}|\leq\widetilde{Z}\leq(1+\varepsilon)|{\mathcal{M}}|.$ Assuming that the running times of the separation oracle and the approximate max-entropy oracle are polynomial in their respective input parameters, the running time of the algorithm is bounded by a polynomial in $m,$ $\nicefrac{{1}}{{\varepsilon}}$ and the number of bits needed to represent $(A^{=},b).$

Analogously, one can easily formulate and prove a randomized version of Theorem 2.11, we omit the details. As an important corollary of this theorem, if one is able to efficiently find approximate max-entropy distributions for the perfect matching polytope for general graphs, then one can approximately count the number of perfect matchings they contain. Both problems have long been open and this result, in particular, relates their hardness.

One may ask if Theorem 2.11 can be strengthened to obtain generalized approximate counting oracles from max-entropy oracles. The question is natural since Theorems 2.6 and 2.8 assume access to generalized counting oracles. The answer is yes and is provided in Theorem B.2 in Appendix B. It turns out that one needs access to a generalized max-entropy oracle, an oracle that can compute the distribution that minimizes the KL-divergence with respect to a fixed product distribution and a given set of marginals. These latter programs are shown, in Appendix B, to be no more general than max-entropy programs. In fact, analogs of Theorems 2.6 and 2.8 can be proved for min-KL-divergence programs rather than max-entropy programs, see Theorem B.5.

5 The Ellipsoid Algorithm

In this section we review the basics of the ellipsoid algorithm. The ellipsoid algorithm is used in the proofs of our equivalence between optimization and counting: Both in the proof of Theorems 2.6 and 2.8 and in the proof of Theorem 2.11. Consider the following optimization problem where $g(\cdot)$ is convex and $h_{i}(\cdot)$ are affine functions.

We assume that $g$ is differentiable everywhere and that its gradient, denoted by $\nabla g,$ is defined everywhere. In our application, for a polytope $P({\mathcal{M}})$ and a $\theta$ in the $\eta$-interior of $P({\mathcal{M}}),$ $g=f_{\theta},$ the objective function in the dual program of Figure 2. The $h_{i}(\cdot)$s are the constraints $A^{=}\lambda=0,$ where $(A^{=},c)$ is the maximal set of linearly independent equalities satisfied by the vertices of ${\mathcal{M}}.$ Thus, as noted in Lemma 2.5, we can restrict our search for the optimal solution to the set $K$ which is defined to be

Note that $0\in K.$ The ellipsoid algorithm can be used to solve such a convex program under fairly general conditions and we first state a version of it needed in the proof of Theorem 2.6. A crucial requirement is a strong first-order oracle for $g$ which is a function such that given a $\lambda,$ outputs $g(\lambda)$ and $\nabla g(\lambda).$ Since we are only interested in $\lambda\in K,$ and we are given the equalities describing $K$ explicitly, we assume that we can project $\nabla g(\lambda)$ to $K.$ By abuse of notation, we denote the latter also by $\nabla g(\lambda).$

The following theorem claims that if one is given access to a strong first-order oracle for $g$, one can use the ellipsoid algorithm to obtain an approximately optimal solution to the convex program mentioned above. This statement is easily derivable from (Theorem 8.2.1).

The number of calls to the strong first-order oracle for $g$ are bounded by a polynomial in $m$, $\log R$ and $\log{\nicefrac{{1}}{{\beta}}}.$

In our applications of this theorem, we in fact need the ellipsoid to be in an affine space of dimension possibly lower than $m.$ The definitions and the theorem continue to hold under such a setting.

Examples of Combinatorial Polytopes

If one wishes, one can keep the following combinatorial polytopes in mind while trying to understand and interpret the results of this paper.

The Spanning Tree Polytope. Given a graph $G=(V,E)$, let

where, for $S\subseteq V,$ $E(S)\stackrel{{\scriptstyle\textup{def}}}{{=}}\{e=\{u,v\}\in E:\{u,v\}\cap S=\{u,v\}\}$ and, for a subset of edges $H\subseteq E,$ $x(H)\stackrel{{\scriptstyle\textup{def}}}{{=}}\sum_{e\in H}x_{e}.$ Edmond also shows the existence of a separation oracle for this polytope. A generalized exact counting oracle is known for this spanning tree polytope via Kirchoff’s matrix-tree theorem, see .

The Perfect Matching Polytope for Bipartite Graphs. Given a bipartite graph $G=(V,E)$, let

It follows from a theorem of Birkhoff that, when $G$ is bipartite,

where, for $v\in V,$ $\delta(v)\stackrel{{\scriptstyle\textup{def}}}{{=}}\{e=\{u,v\}\in E\}.$ Here, it can be shown that all the facets, i.e., the defining inequalities, are one of the set of $2m$ inequalities $0\leq x_{e}\leq 1$ for all $e\in[m].$ The exact counting problem is #P-hard and while a (randomized) generalized approximate counting oracle follows from a result of Jerrum, Sinclair and Vigoda for computing permanents.

The Cycle Cover Polytope for Directed Graphs. Given a directed graph $G=(V,A),$ let

A cycle cover in $G$ is a collection of vertex disjoint directed cycles that cover all the vertices of $G.$ The corresponding cycle cover polytope is denoted by $P({\mathcal{M}}).$ This polytope is easily seen to be a special case of the perfect matching polytope for bipartite graphs as follows. For $G=(V,A),$ construct a bipartite graph $H=(V_{L},V_{R},E)$ where $V_{L}=V_{R}=V.$ For each vertex $v\in V$ we have $v_{L}\in V_{L}$ and $v_{R}\in V_{R}.$ There is an edge between $u_{L}\in V_{L}$ and $v_{R}\in V_{R}$ in $H$ if and only if $(u,v)\in A.$ Thus, there is a one-to-one correspondence between cycle covers in $G$ and perfect matchings in $H.$ Hence, the algorithm gives a generalized approximate counting oracle in this case as well.

The Perfect Matching Polytope for General Graphs. Given a graph $G=(V,E)$, let

A celebrated result of Edmonds states that

The separation oracle for this polytope is non-trivial and follows from the characterization result of Edmonds. A direct separation oracle was also given by Padberg and Rao . Coming up with a counting oracle for this polytope, even with uniform weights which counts the number of perfect matchings in a general graph, is a long-standing open problem.

New Algorithmic Approaches for the Traveling Salesman Problem

Here, for a vertex $v,$ $\delta^{+}(v)$ is the set of directed edges going out of it and $\delta^{-}(v)$ is the set of directed edges coming in to $v.$ Let $x^{\star}$ denote the optimal solution to this linear program. The authors of make the observation that $\theta_{uv}\stackrel{{\scriptstyle\textup{def}}}{{=}}\frac{n-1}{n}(x^{\star}_{uv}+x^{\star}_{vu})$ defined on the undirected edges is a point in the interior of the spanning tree polytope on $G$. The algorithm then samples a spanning tree $T$ from the max-entropy distribution with marginals as given by $\theta$ and crucially relies on properties of such a $T$ to obtain an $O\left(\frac{\log n}{\log\log n}\right)$-approximation algorithm for the ATSP problem.

Interestingly, there is another integral polytope in which $x^{\star}$ is contained. Consider the convex hull $P$ of all cycle covers of $G$, see Section 3. Then,

It is easy to see that $x^{\star}\in P$. Similar to the cycle cover algorithm of Frieze et al , the following is a natural algorithm for the ATSP problem.

Solve the subtour elimination LP for $G$ to obtain the solution $x^{\star}$.

Sample a cycle cover ${\mathcal{C}}$ from the max-entropy distribution with marginals $x^{\star}$.

Include in $H$ all edges in ${\mathcal{C}}$, i.e., $H\leftarrow H\cup\left(\cup_{C\in{\mathcal{C}}}C\right).$

Select one representative vertex $v_{C}$ in each cycle $C\in{\mathcal{C}}$ and delete all the other vertices.

Before analyzing the performance of this algorithm, a basic question is whether this algorithm can be implemented in polynomial time. As an application of Theorem 2.8 to the cycle cover polytope for directed graphs, it follows that one can sample a cycle cover from the max-entropy distribution in polynomial time and, thus, the question is answered affirmatively. The generalized (randomized) approximate counting oracle for cycle covers in a graph follows from the work of . The technical condition of interiority of $x^{\star}$ can be satisfied with a slight loss in optimality of the objective function. The analysis of worst case performance of this algorithm is left open, but to the best of our knowledge, there is no example ruling out that the Randomized Cycle Cover Algorithm is an $O(1)$-approximation. Similarly, the application of Theorem 2.8 to the perfect matching polytope in bipartite graphs makes the permanent-based approach suggested in for the (symmetric) TSP computationally feasible.

Bounding Box

In this section, we prove Theorem 2.7 and show that there is a bounding box of small radius containing the optimal solution ${\lambda}^{\star}$. We begin with the following lemma.

Proof: First, note that the supremum of the primal convex program over all ${\theta}$ is $\ln|{\mathcal{M}}|\leq m.$ Hence, from strong duality it follows that $f({\lambda}^{\star})\leq m.$ This implies that

Since $x\in P({\mathcal{M}})$, we have $x=\sum_{M\in{\mathcal{M}}}r_{M}{1}_{M}$ where $\sum_{M\in{\mathcal{M}}}r_{M}=1$ and $r_{M}\geq 0$ for each $M\in{\mathcal{M}}$. Multiplying (3) by $r_{M}$ and summing over $M$ we get

As a consequence, we obtain that $\langle{\lambda}^{\star},{\theta}\rangle-\langle{\lambda}^{\star},x\rangle\leq m,$ completing the proof of the lemma.

Recall that $A^{=}{x}=c$ denotes the maximal set of independent equalities satisfied by $P({\mathcal{M}})$. We now define the following objects. Let

be the ball centered around ${\theta}$ restricted to the affine space $A^{=}x=c$ of radius $\eta$. Since ${\theta}$ is in the $\eta$-interior of $P({\mathcal{M}}),$ we have that $B\subseteq P({\mathcal{M}})$. Let

be the ball centered around ${\theta}$ of radius $\frac{1}{\eta}$ in the same affine space and let

Proof: We first prove that $Q\subseteq\widetilde{Q}.$ Let $y\in Q$. The constraints $A^{=}y=c$ are clearly satisfied since $y\in Q$. For any $x\in B$,

Thus, $y\in\widetilde{Q}$. Now we show that $Q\subseteq\widetilde{Q}.$ Let $z\in\widetilde{Q}$. The constraints $A^{=}z=c$ are clearly satisfied since $z\in\widetilde{Q}$. Now consider

Thus, $z^{\prime}\in B$. Hence, we must have ${\langle{z-{\theta}},{{z}^{\prime}-{\theta}}\rangle}\leq 1.$ This implies that

Here we have used the fact that $A^{=}\lambda^{\star}=0,$ see Lemma 2.5. We now verify the second condition. Let $x\in B$. Then

where the last inequality follows from that fact that $x\in B\subseteq P({\mathcal{M}})$ and Lemma 5.1. Thus, $\widetilde{\lambda}\in Q$ and therefore, we must have $\|\widetilde{\lambda}-{\theta}\|\leq\nicefrac{{1}}{{\eta}}$. Therefore, $\|\nicefrac{{\lambda^{\star}}}{{m}}\|\leq\nicefrac{{1}}{{\eta}}$ proving Theorem 2.7.

Optimization via Counting

In this section, we prove Theorems 2.6 and 2.8. The proof of both the theorems rely on the bounding box result of Theorem 2.7 and employs the framework of the ellipsoid algorithm from Section 2.5.

We first use Theorem 2.13 to give a proof of Theorem 2.6. The algorithm assumes access to a strong first-order oracle for $P({\mathcal{M}}).$ We then present details of how to implement a strong first-order oracle using an generalized exact counting oracle. Suppose ${\lambda}^{\star}$ is the optimum of our convex program. Theorem 2.7 implies that for $\|{{\lambda}}^{\star}\|_{\infty}\leq\nicefrac{{m}}{{\eta}}.$ Thus, we may pick the bounding radius to $R\stackrel{{\scriptstyle\textup{def}}}{{=}}\nicefrac{{m}}{{\eta}}$ and it does not cut the optimal $\lambda^{\star}$ we are looking for. The only thing left to choose is a $\beta$ such that

This would imply that the solution ${{\lambda}}^{\circ}$ output by employing the ellipsoid method from Theorem 2.13 is such that

To establish a bound on $\beta,$ start by noticing that $\inf_{{\lambda}}f_{\theta}({\lambda})\geq 0.$ This follows from weak-duality and the fact that entropy is always non-negative. On the other hand we have the following simple lemma.

$\sup_{\|{\lambda}\|_{\infty}\leq R}f_{\theta}({\lambda})\leq(2m+1)R.$

Here we have used the fact that $|{\mathcal{M}}|\leq 2^{m}$ and that $\theta_{e}\in$ for each $e\in[m].$

Thus, $\beta$ can be chosen to be $\frac{\varepsilon}{(2m+1)R}.$ Hence, the running time of the ellipsoid method depends polynomially on the the time it takes to implement the strong first-order oracle for $f_{\theta}$ and $\log\frac{mR}{\varepsilon}.$

Since $f_{\theta}({\lambda})=\langle{\lambda},{\theta}\rangle+\ln\sum_{M\in{\mathcal{M}}}e^{-\lambda(M)}=\langle{\lambda},{\theta}\rangle+\ln Z^{\lambda},$ it is easily seen that

Hence, $\nabla f_{\theta}({\lambda})={\theta}-{\theta}^{\lambda}.$ Recall that the strong first-order oracle for $f_{\theta}$ requires, for a given ${\lambda},$ $f_{\theta}({\lambda})$ and $\nabla f_{\theta}({\lambda}).$ The generalized exact counting oracle for $P({\mathcal{M}})$ immediately does it as it gives us $Z^{\lambda}_{e}$ for all $e\in[m]$ and $Z^{\lambda}.$ This allows us to compute $f_{\theta}({\lambda})$ and $\nabla f_{\theta}({\lambda})$ in one call to such an oracle. In addition we also need time proportional to the number of bits needed to represent $\theta.$

Thus, the number of calls to the counting oracle by the ellipsoid algorithm of Theorem 2.13 is bounded by a polynomial in $m,$ $\log R$ and $\log\nicefrac{{1}}{{\varepsilon}}.$ Since each oracle call can be implemented in time polynomial in $m$ and $R$, Here we ignore the fact that $e^{-\lambda_{e}}$ can be irrational. This issue can be dealt in a standard manner as is done in the implementation details of all ellipsoid algorithms. See for details. this gives the required running time and concludes the proof of Theorem 2.6.

2 Proof of Theorem 2.8

Now we give the ellipsoid algorithm that works with a generalized approximate counting oracle and prove Theorem 2.8. Here, the fact that the counting oracle is approximate means that the gradient computed as in the previous section is approximate. Thus, this raises the possibility of cutting off the optimal $\lambda^{\star}$ during the run of the ellipsoid algorithm. We present the ellipsoid algorithm to check, given a $\theta$ and a $\zeta,$ whether $|f_{\theta}(\lambda^{\star})-\zeta|\leq\varepsilon$. The technical heart of the matter is to show that when $|f_{\theta}(\lambda^{\star})-\zeta|\leq\varepsilon,$ $\lambda^{\star}$ is never cut off of the successive ellipsoids obtained by adding the approximate gradient constraints. Moreover, in this case, once the radius of the ellipsoid becomes small enough, we can output its center as a guess for $\lambda^{\star}.$ Since the radius of the final ellipsoid is small and contains $\lambda^{\star}$, the following lemma, which bounds the Lipschitz constant of $f_{\theta},$ implies that the value of $f_{\theta}$ at the center of the ellipsoid is close enough to $f_{\theta}(\lambda^{\star}).$

which completes the proof. Here we have used the Cauchy-Schwarz inequality in the first and third inequalities and in the second inequality we have used the fact that $\theta\in^{m}.$

Proceeding to the ellipsoid algorithm underlying the proof of Theorem 2.8, we do a binary search on the optimal value $f_{\theta}({\lambda}^{\star})$ up to an accuracy of $\nicefrac{{\varepsilon}}{{8}}$. For a guess $\zeta\in(0,m]$, we check whether the guess is correct with the following ellipsoid algorithm. For ease of analysis, we assume that all oracle calls are answered correctly with probability $1.$ The failure probability can be adjusted to arbitrary precision with a slight degradation in the running time.

A $\theta$ which is guaranteed to be in the $\eta$-interior of $P({\mathcal{M}}).$

A maximally linearly independent set of equalities $(A^{=},b)$ for $P({\mathcal{M}}).$

A generalized approximate counting oracle for ${\mathcal{M}}.$

A guess $\zeta\in(0,m]$ (for $f_{\theta}(\lambda^{\star})).$

Let $E_{0}\stackrel{{\scriptstyle\textup{def}}}{{=}}E(B_{0},c_{0})$ be a sphere with radius $R=\nicefrac{{m}}{{\eta}}$ centered around the origin (thus, containing ${\lambda}^{\star}$ by Theorem 2.7) and restricted to the affine space $A^{=}x=0.$

Repeat until the ellipsoid $E_{t}$ is contained in a ball of radius at most $\frac{\varepsilon}{16\sqrt{m}}.$

Given the ellipsoid $E_{t}\stackrel{{\scriptstyle\textup{def}}}{{=}}E(B_{t},c_{t})$, set ${\lambda}_{t}\stackrel{{\scriptstyle\textup{def}}}{{=}}c_{t}.$

Compute $\zeta_{t}$ using the counting oracle such that $f_{\theta}({\lambda}_{t})-\nicefrac{{\varepsilon}}{{8}}\leq\zeta_{t}\leq f_{\theta}({\lambda}_{t})+\nicefrac{{\varepsilon}}{{8}}.$

Compute $\theta_{t}$ such that $\|{\theta}_{t}-{\theta}^{{\lambda}_{t}}\|_{1}\leq\nicefrac{{\varepsilon}}{{16R}}$ using the counting oracle.

Compute the ellipsoid $E_{t+1}$ to be the smallest ellipsoid containing the half-ellipsoid $\{{\lambda}\in E_{t}:\langle{\lambda}-{\lambda}_{t},{\theta}-{{\theta}_{t}}\rangle\leq 0\}$ restricted to the affine space $A^{=}x=0.$

Let $T=t$ and compute $\zeta_{T}$ using the counting oracle such that $f_{\theta}({\lambda}_{T})-\nicefrac{{\varepsilon}}{{8}}\leq\zeta_{T}\leq f_{\theta}({\lambda}_{T})+\nicefrac{{\varepsilon}}{{8}}$.

else return $f_{\theta}(\lambda^{\star})>\zeta$ and stop ($\zeta$ is not a good guess for $f_{\theta}(\lambda^{\star})$).

We first show that the algorithm can be implemented using a polynomial number of queries to the approximate oracle. Steps (3b), (3iiA) and (4) can be computed using oracle calls to the generalized approximate counting oracle for ${\mathcal{M}}$ to obtain $\widetilde{Z}^{{\lambda}_{t}}$ such that $(1-\nicefrac{{\varepsilon}}{{16}})Z^{{\lambda}_{t}}\leq\widetilde{Z}^{{\lambda}_{t}}\leq(1+\nicefrac{{\varepsilon}}{{16}})Z^{{\lambda}_{t}}.$ We set $\zeta_{t}=\langle{\lambda}_{t},{\theta}\rangle+\ln{\widetilde{Z}^{{\lambda}_{t}}}$. A simple calculation then shows that

since $f_{\theta}({\lambda}_{t})=\langle{\lambda}_{t},{\theta}\rangle+\ln{{Z}^{{\lambda}_{t}}}.$ Similarly using one oracle call to the counting oracle with error parameter $\frac{\varepsilon}{16R}$, we can compute

as needed in Step (3iiA) of the algorithm. Using Theorem 2.14, the number of iterations can be bounded by a polynomial in $m,\log\nicefrac{{R}}{{\varepsilon}}$. The analysis is quite standard and omitted. Each of the oracle call can be implemented in time polynomial in $m,R$ and $\nicefrac{{1}}{{\varepsilon}}$. We now show the following lemma which completes the proof of Theorem 2.8.

Let $\zeta^{\circ}$ be the smallest guess for which the ellipsoid algorithm succeeds in finding a solution and let ${\lambda}^{\circ}$ denote the corresponding solution returned. Then, $f_{\theta}({\lambda}^{\circ})\leq f_{\theta}({\lambda}^{\star})+\varepsilon$.

Since $\zeta^{\circ}$ is the smallest guess for which the algorithm succeeds in returning an answer, it fails for some $\zeta\in[\zeta^{\circ}-\nicefrac{{\varepsilon}}{{8}},\zeta^{\circ}]$. We show that $f_{\theta}({\lambda}^{\star})\geq\zeta-\nicefrac{{\varepsilon}}{{4}}$. This suffices to prove the theorem since

Suppose for the sake of contradiction that

We then show that ${\lambda}^{\star}$ must be in the final ellipsoid $E_{T}$ when the ellipsoid algorithm is run with guess $\zeta$. Let ${\lambda}_{t}$ be center of the ellipsoid $E_{t}$ in any iteration with guess $\zeta$. Let $\zeta_{t}$ be computed in Step (3b) such that

Since the algorithm does not return any answer with guess $\zeta$, we must have $\zeta_{t}>\zeta$. Thus,

where the last inequality follows from inequality (4). Let ${\theta}_{t}$ be computed in Step (3iiA) of the algorithm such that $\|{\theta}_{t}-{\theta}^{{\lambda}_{t}}\|_{1}\leq\frac{\varepsilon}{32R}$. But then

where the first inequality follows from convexity of $f$. Thus, ${\lambda}^{\star}$ satisfies the separating constraint put in Step (3iiB) of the algorithm. Therefore, it must be contained in the final ellipsoid $E_{T}$. Let ${\lambda}_{T}$ be the center of the ellipsoid $E_{T}$. Let $\zeta_{T}$ be computed such that $|\zeta_{T}-f_{\theta}({\lambda}_{T})|\leq\nicefrac{{\varepsilon}}{{8}}.$ Then

where we use Lemma 6.2. Therefore, the algorithm must have returned $\lambda^{\circ}={\lambda}_{T}$ as the feasible solution for guess $\zeta$ a contradiction. This completes the proof of Lemma 6.3.

Counting via Optimization

In this section we present the proof of Theorem 2.11. We start by phrasing the problem of estimating $|{\mathcal{M}}|$ as a convex optimization problem.

Let $g({\theta})$ denote the optimum of the max-entropy program of Figure 4 for ${\mathcal{M}}$ and a point $\theta$ in $P({\mathcal{M}}).$ If $\theta$ is in the interior of $P({\mathcal{M}}),$ then strong duality holds for this convex program and

see Lemma 2.3. By the concavity of the Shannon entropy, $g(\cdot)$ can be easily seen to be a concave function of $\theta.$ Recall that in the setting of Theorem 2.11, we have an access to an approximate max-entropy oracle which, given a $\theta$ in the $\eta$-interior of $P({\mathcal{M}}),$ a $\zeta>0$ as a guess for $g(\theta),$ and an $\varepsilon>0,$ either asserts that $g(\theta)\geq\zeta-\varepsilon$ or returns a $\lambda$ such that $f_{\theta}(\lambda)\leq\zeta+\varepsilon.$ The running time of this oracle is polynomial in $m,\nicefrac{{1}}{{\varepsilon}}$ and in the number of bits needed to represent $\zeta.$ Using this oracle, we hope to get an estimate on $|{\mathcal{M}}|.$ The starting point of the proof is the observation that the point that maximizes $g(\theta)$ when $\theta$ is in $P({\mathcal{M}})$ is

the vertex centroid of $P({\mathcal{M}}).$

$\sup_{{\theta}\in P({\mathcal{M}})}g(\theta)\leq\ln|{\mathcal{M}}|$ and $g(\theta^{\star})=\ln|{\mathcal{M}}|.$

Proof: For any ${\theta}$ in the interior of $P({\mathcal{M}})$, $g(\theta)$ is the entropy of some probability distribution over the elements in $|{\mathcal{M}}|$. A standard fact in information theory implies that the maximum entropy of any distribution over a finite set is obtained by the uniform distribution. The entropy of the uniform distribution on ${\mathcal{M}}$ is $\ln|{\mathcal{M}}|,$ hence, $g(\theta)$ can be upper bounded by $\ln{|{\mathcal{M}}|}$. On the other hand, the uniform distribution over ${\mathcal{M}}$ has marginals equal to $\theta^{\star}$ and, thus, $g(\theta^{\star})=\ln|{\mathcal{M}}|.$

Thus, if we could find $g(\theta^{\star}),$ then we can estimate $|{\mathcal{M}}|.$ Finding $g(\theta^{\star})$ is the same as solving the convex program

We use the framework of the ellipsoid method to approximately solve this convex program and find a point which gives us a good enough estimate to $g(\theta^{\star}).$ Note that, unlike the results in the previous section, the bounding box here is easily obtained since $\theta\in P({\mathcal{M}})\subseteq^{m}.$

2 The Interior of P⁡(ℳ)P({\mathcal{M}})

To check how close a candidate point $\theta$ is to $\theta^{\star},$ we use the max-entropy separation oracle provided to us. The main difficulty we encounter is that the running time of the max-entropy oracle with marginals $\theta$ is inverse-polynomially dependent on the interiority of the point $\theta.$ Note that interiority of $\theta$ is a pre-requisite for strong duality to hold and for a succinct representation of the entropy-maximizing probability distribution to exist as in Lemma 2.3. The reason we assume a max-entropy oracle that works only if $\theta$ is in the inverse-polynomial interior of $P({\mathcal{M}})$ is that such an oracle is the best we can hope for algorithmically and, indeed, Theorems 2.6 and 2.8 provide such an oracle. Without this restriction the proof of Theorem 2.11 is simpler, but the theorem itself is less useful as there may not exist a max-entropy oracle whose running time does not depend on the interiority of $\theta.$

The first issue raised by interiority is whether the point we are looking for, $\theta^{\star}$ may not be in the inverse-polynomial interior of $P({\mathcal{M}}).$ To tackle this, we show that there is a point ${\theta^{\bullet}}$ in the $\eta$-interior of $P({\mathcal{M}})$ for $\eta={\rm poly}(\varepsilon,\nicefrac{{1}}{{m}})$ such that $g({\theta^{\bullet}})\sim g(\theta^{\star})=\ln|{\mathcal{M}}|.$ Thus, instead of aiming for $\theta^{\star},$ the ellipsoid algorithm aims for ${\theta^{\bullet}}.$

Given an $\varepsilon>0$, there exists an $\eta>0$ and ${\theta^{\bullet}}$ such that ${{\theta^{\bullet}}}$ is in $\eta$-interior of $P({\mathcal{M}})$ and $g({\theta^{\bullet}})\geq\left(1-\frac{\varepsilon}{16m}\right)\ln|{\mathcal{M}}|\geq\ln|{\mathcal{M}}|-\frac{\varepsilon}{16}$. Moreover, $\eta$ is at least a polynomial in $\nicefrac{{1}}{{m}}$ and $\varepsilon.$

be a facet of $P({\mathcal{M}})$ where the inequality constraint is one of $(A^{\leq},c).$ Since the dimension of a facet is one less than that of a polytope, at least one of $z_{0},z_{1},\ldots,z_{r},$ say $z_{0},$ does not lie in $F$ and, hence, $A^{\leq}_{i}z_{0}<c_{i}.$ Therefore,

since all coefficients are $\nicefrac{{1}}{{k_{l}}}$-integral. Thus, the distance of $z_{0}$ from $F$ is at least

Henceforth, we assume that $k_{l},k_{u}={\rm poly}(m).$

where we used the fact that $\ln|{\mathcal{M}}|\leq m$.

3 A Separation Oracle for Interiority

Our final ingredient is a test for checking whether a point ${\theta}$ is in the inverse-polynomial interior of $P({\mathcal{M}}).$ We show that the separation oracle for $P({\mathcal{M}})$ can be used to give such a test. We state the result in generality for any polyhedron $P$. For any $\eta>0$, let

denote the set of $\eta$-interior points in $P$.

asserts that ${\theta}\in P_{\nicefrac{{\eta}}{{2m}}}$, i.e., ${\theta}$ is in the $\nicefrac{{\eta}}{{2m}}$-interior of $P$, or,

returns $a$ such that $\langle{a},{y}\rangle<\langle{a},{\theta}\rangle$ for each ${y}\in P_{\eta}$, or equivalently, a separating hyperplane which separates the $\eta$-interior of $P$ from ${\theta}$.

Proof: We use the the separation oracle for $P$ on a collection of a small number of points close to ${\theta}$ to deduce if ${\theta}$ is in the interior of $P$. Even if one of these points is not in $P$, we use a separating hyperplane for such a point to separate ${\theta}$ from the interior of $P$. First, we describe the procedure when $P$ is full dimensional. Let ${x}_{0},\ldots{x}_{m}$ form an $\eta$-regular simplex with center ${\theta}$, i.e.,

for each $i\neq j$. Such $x_{0},\ldots,x_{m}$ can be found by starting with a regular simplex and then translating and scaling it. Now, the algorithm applies the separation oracle for each of ${x}_{i}$. Suppose the separation oracle asserts that ${x}_{i}\in P$ for each $0\leq i\leq m$. In this case, we assert that ${\theta}\in P_{\nicefrac{{\eta}}{{2m}}}$. Observe that since each vertex of the simplex is in $P$, we must have that the whole simplex is in $P$. Since the simplex is regular where each edge is length $\eta$ and the center is ${\theta}$, there exists a ball of radius $\frac{\eta}{2m}$ centered at ${\theta}$ which is contained in the simplex and, hence, in $P$. Thus, ${\theta}$ is in $\frac{\eta}{2m}$-interior of $P$ as asserted.

Now, suppose that ${x}_{i}\notin P$ for some $i$ and let ${a}$ be the separating hyperplane, i.e., $\langle{a},{y}\rangle<\langle{a},x_{i}\rangle$ for each ${y}\in P$. Then consider the constraint $\langle{a},{y}\rangle<\langle{a},{\theta}\rangle$. We claim that it is satisfied by each ${y}\in P_{\eta}$. Let ${y}\in P_{\eta}$ and consider

Since $\|{\theta}-{x}_{i}\|\leq\eta$ and ${y}\in P_{\eta}$, we have that ${y}^{\prime}\in P$ which implies that $\langle{a},{y}^{\prime}\rangle<\langle{a},{x}_{i}\rangle$. But this implies that

which gives us the required separating hyperplane.

Now consider the case where $P$ is not full dimensional and let $r$ be the dimension of $P$. Recall that in this case we define interior of $P$ by restricting our attention to points in the affine space $\{x:A^{=}{x}=c\}$. We modify the algorithm to chose a $r$-dimensional simplex in this affine space and check whether each of the vertices of the simplex is in $P$. The analysis is identical in this case.

4 The Ellipsoid Algorithm for Theorem 2.11

Now we present the ellipsoid algorithm to approximately solve the convex program $\min_{{\theta}\in P({\mathcal{M}})}g({\theta})$ and prove Theorem 2.11. The starting ellipsoid is a ball of radius $\sqrt{m}$ that contains $^{m}$ which contains $P({\mathcal{M}}).$ Let us fix an $\varepsilon>0$ and apply Lemma 7.2 to obtain $\eta$ which is a polynomial in $\nicefrac{{1}}{{m}}$ and ${\varepsilon}$ and guarantees the existence of ${\theta^{\bullet}}$ in the $\eta$-interior such that $g({\theta^{\bullet}})\geq\ln|{\mathcal{M}}|-\frac{\varepsilon}{16}$. In the range $(0,\ln|{\mathcal{M}}|]$ we perform a binary search for the highest $\zeta$ such that the set