A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
type: Item
instance of: scholarly article
title: A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
zbMATH Open document ID: 1398.60040
author: Anindya De
author: Rocco A. Servedio
publication date: 2018-08-10T00:00:00Z
review text: 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.
reviewed by: Fraser Daly
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 6916290
zbMATH Keywords: Gaussian chaos
zbMATH Keywords: central limit theorem
zbMATH Keywords: polynomials
zbMATH Keywords: Malliavin calculus
zbMATH Keywords: Stein's method
zbMATH Keywords: approximate counting
MaRDI profile type: Publication
full work available at URL: s00440-017-0804-y
OpenAlex ID: W2757708033
cites work: The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Learning Kernel-Based Halfspaces with the 0-1 Loss
cites work: Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
cites work: Q5690490
cites work: Central limit theorems for non-linear functionals of Gaussian fields
cites work: A new method of normal approximation
cites work: Fluctuations of eigenvalues and second order Poincaré inequalities
cites work: The number of eigenvalues of a tensor
cites work: Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
cites work: Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
cites work: The inverse Shapley value problem
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
cites work: The Frechet distance between multivariate normal distributions
cites work: Q5365141
cites work: Q3191611
cites work: Q5538132
cites work: On the second eigenvalue of hypergraphs
cites work: Majority gates vs. general weighted threshold gates
cites work: An FPTAS for #Knapsack and Related Counting Problems
cites work: Q5689624
cites work: DNF sparsification and a faster deterministic counting algorithm
cites work: Estimates of moments and tails of Gaussian chaoses
cites work: On the Size of Weights for Threshold Gates
cites work: Gaussian Hilbert Spaces
cites work: A Small PRG for Polynomial Threshold Functions of Gaussians
cites work: The correct exponent for the Gotsman-Linial conjecture
cites work: Agnostically Learning Halfspaces
cites work: Explicit dimension reduction and its applications
cites work: On deterministic approximation of DNF
cites work: Noise stability of functions with low influences: invariance and optimality
cites work: Q5595902
cites work: Theory of majority decision elements
cites work: Q5655273
cites work: Pseudorandom generators for polynomial threshold functions
cites work: Lectures on Gaussian Approximations with Malliavin Calculus
cites work: Central limit theorems for sequences of multiple stochastic integrals
cites work: Stein's method meets Malliavin calculus: a short survey with new estimates
cites work: Multivariate normal approximation using Stein's method and Malliavin calculus
cites work: Perceptrons of large weight
cites work: Every linear threshold function has a low-weight approximator
cites work: Halfspace matrices
cites work: The Intersection of Two Halfspaces Has High Threshold Degree
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
DOI: 10.1007/S00440-017-0804-Y
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article; zbMATH DE number 6916290