Computing Gaussian and exponential integrals in ${\Bbb R}^n$

Technical Summary: Computing Gaussian and Exponential Integrals in $\mathbb{R}^n$

Problem Statement
The paper addresses the computational complexity of approximating expectations of the form:
$$E \exp \left( \sum_{i=1}^m \phi_i \right)$$
where $\phi_1, \dots, \phi_m: \mathbb{R}^n \to \mathbb{C}$ are complex-valued functions, and the expectation is taken with respect to either the standard Gaussian measure or the symmetric exponential measure on $\mathbb{R}^n$. The functions $\phi_i$ are assumed to depend on only a few coordinates of the input vector $x = (\xi_1, \dots, \xi_n)$.

The primary challenge is that such integrals are generally intractable for large $n$ and $m$. The paper focuses on conditions under which the integral is "separated from zero" (i.e., non-zero and bounded away from zero relative to its magnitude). The authors argue that if the integral is separated from zero, it becomes amenable to efficient approximation via the interpolation method (computing moments and using Taylor expansions of the logarithm of the partition function).

Methodology
The paper employs an inductive approach to analyze the dependencies among the functions $\phi_i$, distinct from the cluster expansion methods common in statistical physics. The core methodology involves:

1. Interpolation and Analytic Continuation: The authors introduce a complex parameter $\lambda$ and consider the function $F(\lambda) = E \exp(\lambda \sum \phi_i)$. They aim to prove that $F(\lambda)$ has no zeros in a specific domain containing the origin and $\lambda=1$. If $F(\lambda)$ is non-zero and bounded within a disc (or connected open set) in the complex plane, the logarithm $\ln F(\lambda)$ is holomorphic.
2. Moment Approximation: By establishing the non-vanishing property, the authors show that $F(1)$ can be approximated within a relative error $\epsilon$ using the first $k$ moments of the sum $\sum \phi_i$, where $k = O(\ln \ln M - \ln \epsilon)$ and $M$ is a bound on the magnitude of the expectation.
3. Inductive Proof of Non-Vanishing: The proofs for the Gaussian and exponential cases rely on a specific inductive claim. They assume the result holds for $m-1$ functions and prove it for $m$ functions by:
   • Partitioning the coordinates into those shared by a specific function $\phi_m$ and those that are not.
   • Defining an auxiliary function $\Psi$ representing the expectation over the non-shared coordinates.
   • Demonstrating that $\Psi$ is Lipschitz continuous with a sufficiently small constant.
   • Applying a lemma (Lemmas 5.2 and 6.2) which states that for a Lipschitz function $f$ with a small enough Lipschitz constant $L$, $|E e^f| \ge \frac{1}{2} E |e^f|$. This ensures the expectation does not vanish.

Key Results
The paper establishes two main theorems providing sufficient conditions for the integral to be separated from zero, based on the Lipschitz constants of $\phi_i$ and the combinatorics of their coordinate dependencies.

• Theorem 1.2 (Gaussian Measure):

  • Setup: $\mu$ is the standard Gaussian measure. Functions $\phi_i$ are 1-Lipschitz in the $\ell_2$ norm.
  • Conditions:
    1. Each coordinate $\xi_j$ is shared by at most $c$ functions ($c \ge 2$).
    2. Each function $\phi_i$ shares coordinates with at most $\Delta$ other functions.
    3. $(c-1)\Delta \ge 4$.
  • Result: For $|\lambda| \le \frac{1}{10\sqrt{(c-1)\Delta}}$, the expectation satisfies $|E \exp(\lambda \sum \phi_i)| \ge \frac{1}{2^m} E |\exp(\lambda \sum \phi_i)|$.
  • Complexity: This leads to a quasi-polynomial time algorithm to approximate the integral with relative error $\epsilon$, requiring $k = O(\ln(m+n) - \ln \epsilon)$ moments.

• Theorem 1.3 (Symmetric Exponential Measure):

  • Setup: $\mu$ is the symmetric exponential measure (density $\propto e^{-\sum |\xi_j|}$). Functions $\phi_i$ are 1-Lipschitz in the $\ell_1$ norm.
  • Conditions:
    1. Each function $\phi_i$ depends on at most $r$ coordinates ($r \ge 9$).
    2. Each coordinate $\xi_j$ is shared by at most $c$ functions ($c \ge 13$).
  • Result: For $|\lambda| \le \frac{1}{25(c-1)\sqrt{r}}$, the expectation satisfies the same non-vanishing lower bound as in the Gaussian case.
  • Complexity: Similarly yields a quasi-polynomial approximation algorithm.

Applications
The paper demonstrates the utility of these results in two specific domains:

1. Integer Point Counting in Polyhedra:
   The authors apply the Gaussian result (Theorem 1.2) to approximate the number of integer points in a polyhedron $P \subset \mathbb{R}^n$. By utilizing a quadratic penalty function and the Hubbard-Stratonovich transformation (Fourier transform trick), they convert the discrete counting problem into an expectation over a Gaussian measure. Under sparsity conditions on the constraint matrix (bounded non-zero entries per row/column), they provide a deterministic quasi-polynomial algorithm to approximate the count, provided the penalty parameters are scaled appropriately.

2. Volume Computation:
   The exponential result (Theorem 1.3) is applied to computing the volumes of compact sets $K_\Psi = \{x : \Psi(x) \le 1\}$, where $\Psi$ is a continuous, positively homogeneous function. The volume is expressed as an integral of $e^{-\Psi(x)}$ against the exponential measure. The paper notes that this framework allows for the efficient approximation of volumes for certain non-convex sets constructed from support functions of convex bodies (e.g., Minkowski sums), provided the functions satisfy the Lipschitz and dependency constraints.

Significance and Claims
The paper claims to provide a new inductive approach that yields stronger results regarding the combinatorics of dependencies compared to the traditional cluster expansion method. Specifically:

• It does not require the functions $\phi_i$ to be smooth or to have bounded higher derivatives, relying only on Lipschitz continuity.
• It establishes explicit bounds on the "zero-free" region of the partition function in terms of the dependency graph parameters ($c, \Delta, r$).
• It bridges statistical physics concepts (phase transitions, partition functions) with computational complexity, showing that "staying far from phase transitions" (ensuring the partition function is non-zero) enables efficient deterministic approximation.
• The authors position these results as a tool for tackling #P-hard problems (like integer point counting) by finding computationally efficient relaxations that are exact under specific scaling or approximation regimes.

The paper concludes that while the upper bounds on the magnitude of the integral are straightforward, the lower bounds (ensuring the integral is separated from zero) are the critical component that enables the efficient approximation algorithms described.