A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting (Q1656545): Difference between revisions
From MaRDI portal
Revision as of 07:10, 16 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting |
scientific article |
Statements
A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting (English)
0 references
10 August 2018
0 references
The first main contribution of the present paper is a multidimensional central limit theorem for \(r\)-tuples \((p_1(x),\ldots,p_r(x))\) of degree \(d\) polynomials with Gaussian input, which states that if each \(p_i\) has `small eigenvalues' (for a suitable definition), then the joint distribution of this \(r\)-tuple converges to a Gaussian distribution over \(\mathbb{R}^r\). The starting point of the proof is a central limit theorem in a well-known recent work combining Stein's method and Malliavin calculus (see, for example, [\textit{I. Nourdin} et al., Ann. Inst. Henri Poincaré, Probab. Stat. 46, No. 1, 45--58 (2010; Zbl 1196.60035)]). The proof also employs a geometry-preserving isomorphism between the space of symmetric tensors and multivariate Gaussian polynomials, allowing the authors access to tools and techniques from tensor algebra. A second main contribution is a decomposition theorem for low-degree multilinear polynomials with Gaussian input, showing that (up to some small error term) any such polynomial may be approximated by a polynomial which may be decomposed into a bounded number of multilinear polynomials which each have small eigenvalues (in the sense of the above central limit theorem). This result requires a careful balancing of the number of polynomials in the decomposition and the size of their eigenvalues. The above two results are applied to an approximate counting problem. Given a degree \(d\) polynomial \(p:\{-1,1\}^n\mapsto\mathbb{R}\) and an accuracy parameter \(\varepsilon>0\), the authors give a deterministic algorithm which outputs a value \(\tilde{v}\) such that \(|\tilde{v}-Pr(p(X)\geq0)|\leq\varepsilon\), where \(X\) is uniformly distributed over \(\{-1,1\}^n\). This algorithm runs in time \(O_{d,\varepsilon}(1)\cdot\text{poly}(n^d)\), better than previously known algorithms.
0 references
Gaussian chaos
0 references
central limit theorem
0 references
polynomials
0 references
Malliavin calculus
0 references
Stein's method
0 references
approximate counting
0 references
0 references
0 references
0 references
0 references
0 references