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

Résumé technique : Calcul des intégrales gaussiennes et exponentielles dans $\mathbb{R}^n$

Énoncé du problème
Le document traite de la complexité computationnelle de l'approximation d'espérances de la forme :
$$E \exp \left( \sum_{i=1}^m \phi_i \right)$$
où $\phi_1, \dots, \phi_m: \mathbb{R}^n \to \mathbb{C}$ sont des fonctions à valeurs complexes, et l'espérance est prise par rapport à la mesure gaussienne standard ou à la mesure exponentielle symétrique sur $\mathbb{R}^n$. Les fonctions $\phi_i$ sont supposées dépendre de seulement quelques coordonnées du vecteur d'entrée $x = (\xi_1, \dots, \xi_n)$.

Le défi principal est que de telles intégrales sont généralement intraitables pour de grandes valeurs de $n$ et $m$. Le document se concentre sur les conditions sous lesquelles l'intégrale est « séparée de zéro » (c'est-à-dire non nulle et bornée loin de zéro par rapport à sa magnitude). Les auteurs soutiennent que si l'intégrale est séparée de zéro, elle devient susceptible d'une approximation efficace via la méthode d'interpolation (calcul des moments et utilisation des développements de Taylor du logarithme de la fonction de partition).

Méthodologie
Le document emploie une approche inductive pour analyser les dépendances entre les fonctions $\phi_i$, une méthode distincte des méthodes d'expansion de clusters courantes en physique statistique. La méthodologie centrale implique :

1. Interpolation et continuation analytique : Les auteurs introduisent un paramètre complexe $\lambda$ et considèrent la fonction $F(\lambda) = E \exp(\lambda \sum \phi_i)$. Ils visent à prouver que $F(\lambda)$ n'a pas de zéros dans un domaine spécifique contenant l'origine et $\lambda=1$. Si $F(\lambda)$ est non nulle et bornée dans un disque (ou un ensemble ouvert connexe) du plan complexe, le logarithme $\ln F(\lambda)$ est holomorphe.
2. Approximation par les moments : En établissant la propriété de non-annulation, les auteurs montrent que $F(1)$ peut être approximé avec une erreur relative $\epsilon$ en utilisant les $k$ premiers moments de la somme $\sum \phi_i$, où $k = O(\ln \ln M - \ln \epsilon)$ et $M$ est une borne sur la magnitude de l'espérance.
3. Preuve inductive de non-annulation : Les preuves pour les cas gaussien et exponentiel reposent sur une affirmation inductive spécifique. Ils supposent que le résultat est vrai pour $m-1$ fonctions et prouvent qu'il est vrai pour $m$ fonctions en :
   • Partitionnant les coordonnées en celles partagées par une fonction spécifique $\phi_m$ et celles qui ne le sont pas.
   • Définissant une fonction auxiliaire $\Psi$ représentant l'espérance sur les coordonnées non partagées.
   • Démontrant que $\Psi$ est lipschitzienne avec une constante suffisamment petite.
   • Appliquant un lemme (Lemmes 5.2 et 6.2) qui stipule que pour une fonction lipschitzienne $f$ avec une constante de Lipschitz $L$ suffisamment petite, $|E e^f| \ge \frac{1}{2} E |e^f|$. Cela garantit que l'espérance ne s'annule pas.

Résultats clés
Le document établit deux théorèmes principaux fournissant des conditions suffisantes pour que l'intégrale soit séparée de zéro, basées sur les constantes de Lipschitz des $\phi_i$ et la combinatoire de leurs dépendances de coordonnées.

• Théorème 1.2 (Mesure Gaussienne) :

  • Configuration : $\mu$ est la mesure gaussienne standard. Les fonctions $\phi_i$ sont 1-lipschitziennes dans la norme $\ell_2$.
  • Conditions :
    1. Chaque coordonnée $\xi_j$ est partagée par au plus $c$ fonctions ($c \ge 2$).
    2. Chaque fonction $\phi_i$ partage des coordonnées avec au plus $\Delta$ autres fonctions.
    3. $(c-1)\Delta \ge 4$.
  • Résultat : Pour $|\lambda| \le \frac{1}{10\sqrt{(c-1)\Delta}}$, l'espérance satisfait $|E \exp(\lambda \sum \phi_i)| \ge \frac{1}{2^m} E |\exp(\lambda \sum \phi_i)|$.
  • Complexité : Cela conduit à un algorithme de temps quasi-polynomial pour approximer l'intégrale avec une erreur relative $\epsilon$, nécessitant $k = O(\ln(m+n) - \ln \epsilon)$ moments.

• Théorème 1.3 (Mesure Exponentielle Symétrique) :

  • Configuration : $\mu$ est la mesure exponentielle symétrique (densité $\propto e^{-\sum |\xi_j|}$). Les fonctions $\phi_i$ sont 1-lipschitziennes dans la norme $\ell_1$.
  • Conditions :
    1. Chaque fonction $\phi_i$ dépend d'au plus $r$ coordonnées ($r \ge 9$).
    2. Chaque coordonnée $\xi_j$ est partagée par au plus $c$ fonctions ($c \ge 13$).
  • Résultat : Pour $|\lambda| \le \frac{1}{25(c-1)\sqrt{r}}$, l'espérance satisfait la même borne inférieure de non-annulation que dans le cas gaussien.
  • Complexité : De même, cela produit un algorithme d'approximation quasi-polynomial.

Applications
Le document démontre l'utilité de ces résultats dans deux domaines spécifiques :

1. Comptage de points entiers dans des polyèdres :
   Les auteurs appliquent le résultat gaussien (Théorème 1.2) pour approximer le nombre de points entiers dans un polyèdre $P \subset \mathbb{R}^n$. En utilisant une fonction de pénalité quadratique et la transformation de Hubbard-Stratonovich (astuce de la transformée de Fourier), ils convertissent le problème de comptage discret en une espérance sur une mesure gaussienne. Sous des conditions de parcimonie sur la matrice de contrainte (nombre limité d'entrées non nulles par ligne/colonne), ils fournissent un algorithme déterministe de temps quasi-polynomial pour approximer le compte, à condition que les paramètres de pénalité soient mis à l'échelle de manière appropriée.

2. Calcul de volume :
   Le résultat exponentiel (Théorème 1.3) est appliqué au calcul des volumes d'ensembles compacts $K_\Psi = \{x : \Psi(x) \le 1\}$, où $\Psi$ est une fonction continue et positivement homogène. Le volume est exprimé comme une intégrale de $e^{-\Psi(x)}$ par rapport à la mesure exponentielle. Le document note que ce cadre permet l'approximation efficace de volumes pour certains ensembles non convexes construits à partir de fonctions de support de corps convexes (par exemple, sommes de Minkowski), à condition que les fonctions respectent les contraintes de Lipschitz et de dépendance.

Signification et Revendications
Le document affirme fournir une nouvelle approche inductive qui produit des résultats plus forts concernant la combinatoire des dépendances par rapport à la méthode traditionnelle d'expansion de clusters. Plus précisément :

• Il ne nécessite pas que les fonctions $\phi_i$ soient lisses ou possèdent des dérivées d'ordre supérieur bornées, se reposant uniquement sur la continuité lipschitzienne.
• Il établit des bornes explicites sur la région « sans zéro » de la fonction de partition en termes des paramètres du graphe de dépendance ($c, \Delta, r$).
• Il jette un pont entre les concepts de la physique statistique (transitions de phase, fonctions de partition) et la complexité computationnelle, montissant que « rester loin des transitions de phase » (garantir que la fonction de partition est non nulle) permet une approximation déterministe efficace.
• Les auteurs positionnent ces résultats comme un outil pour aborder des problèmes de classe #P-hard (comme le comptage de points entiers) en trouvant des relaxations computationnellement efficaces qui sont exactes sous des régimes de mise à l'échelle ou d'approximation spécifiques.

Le document conclut que bien que les bornes supérieures sur la magnitude de l'intégrale soient directes, les bornes inférieures (garantissant que l'intégrale est séparée de zéro) constituent la composante critique qui permet les algorithmes d'approximation efficaces décrits.