A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting (Q1656545): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: The sum of \(D\) small-bias generators fools polynomials of degree \(D\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Learning Kernel-Based Halfspaces with the 0-1 Loss / rank
 
Normal rank
Property / cites work
 
Property / cites work: Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5690490 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Central limit theorems for non-linear functionals of Gaussian fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new method of normal approximation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fluctuations of eigenvalues and second order Poincaré inequalities / rank
 
Normal rank
Property / cites work
 
Property / cites work: The number of eigenvalues of a tensor / rank
 
Normal rank
Property / cites work
 
Property / cites work: Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: The inverse Shapley value problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounding the average sensitivity and noise sensitivity of polynomial threshold functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Frechet distance between multivariate normal distributions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5365141 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3191611 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5538132 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the second eigenvalue of hypergraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Majority gates vs. general weighted threshold gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: An FPTAS for #Knapsack and Related Counting Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5689624 / rank
 
Normal rank
Property / cites work
 
Property / cites work: DNF sparsification and a faster deterministic counting algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Estimates of moments and tails of Gaussian chaoses / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Size of Weights for Threshold Gates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Gaussian Hilbert Spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Small PRG for Polynomial Threshold Functions of Gaussians / rank
 
Normal rank
Property / cites work
 
Property / cites work: The correct exponent for the Gotsman-Linial conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: Agnostically Learning Halfspaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Explicit Dimension Reduction and Its Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: On deterministic approximation of DNF / rank
 
Normal rank
Property / cites work
 
Property / cites work: Noise stability of functions with low influences: invariance and optimality / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5595902 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Theory of majority decision elements / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5655273 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pseudorandom Generators for Polynomial Threshold Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Lectures on Gaussian Approximations with Malliavin Calculus / rank
 
Normal rank
Property / cites work
 
Property / cites work: Central limit theorems for sequences of multiple stochastic integrals / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stein's method meets Malliavin calculus: a short survey with new estimates / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multivariate normal approximation using Stein's method and Malliavin calculus / rank
 
Normal rank
Property / cites work
 
Property / cites work: Perceptrons of large weight / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every linear threshold function has a low-weight approximator / rank
 
Normal rank
Property / cites work
 
Property / cites work: Halfspace matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Intersection of Two Halfspaces Has High Threshold Degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques / rank
 
Normal rank

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
    0 references
    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
    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
    0 references
    0 references
    0 references

    Identifiers