A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length

Introduction

We say that such an $F$ is a pseudorandom generator of seed length $s$ that fools degree-$d$ polynomial threshold functions with respect to the Gaussian distribution to within $\epsilon$. In this paper, we develop a new such generator whose seed length is $O(\epsilon^{-o(1)})$ for any fixed $d,n$.

There have been a number of previous papers dealing with the question of finding pseudorandom generators for polynomial threshold functions with respect the the Gaussian distribution or the Bernoulli distribution (i.e. uniform over $\{-1,1\}^{n}$). Several early works in this area showed that polynomial threshold functions of various degrees could be fooled by arbitrary $k$-wise independent families of Gaussian or Bernoulli random variables. It should be noted that a $k$-wise independent family of Bernoulli random variables can be generated from a seed of length $O(k\log(n))$. Although, any $k$-wise independent family of Gaussians will necessarily have infinite entropy, it is not hard to show that a simple discretization of these random variables leads to a generator of comparable seed length. These results on fooling polynomial threshold functions with $k$-independence are summarized in Table 1.1 below.

Unfortunately, it is not hard to exhibit $k$-wise independent families of Bernoulli or Gaussian random variables that fail to $\epsilon$-fool the class of degree-$d$ polynomial threshold functions for $k=\Omega(d^{2}\epsilon^{-2})$, putting a limit on what can be obtained through mere $k$-independence.

There have also been a number of attempts to produce pseudorandom generators by using more structure than limited independence. In , Meka and Zuckerman develop a couple of such generators in the Bernoulli case. Firstly, they make use of pseudorandom generators against space bounded computation to produce a generator of seed length $O(\log(n)+\log^{2}(\epsilon^{-1}))$ in the special case where $d=1$. By piecing together several $k$-wise independent families, they produce a generator for arbitrary degree PTFs of seed length $2^{O(d)}\log(n)\epsilon^{-8d-3}$. In , the author develops an improved analysis of this generator allowing for a seed length as small as $O_{c,d}(\log(n)\epsilon^{-11-c})$.

For the Gaussian case, the author developed a generator of seed length $2^{O_{c}(d)}\log(n)\epsilon^{-4-c}$ in . This generator was given essentially as an average several random variables each picked independently from a $k$-wise independent family of Gaussians. The analysis of this generator was also improved in , obtaining a seed length of $O_{c,d}(\log(n)\epsilon^{-2-c})$. In this paper, we improve on this bound further. We make use of a slight modification of the above generator, by using unequal weights in our averaging process and obtain a seed length of $O_{c,d}(\log(n)\epsilon^{-c})$.

2 Outline of Paper

In Section 2, we will introduce some conventions that we will use throughout the paper, and review some basic results on polynomials of Gaussians.

Unfortunately, a generic polynomially will not necessarily be approximately linear. We fix this by evaluating the polynomial near a random input. In particular, if we consider $p(\epsilon X_{1}+\sqrt{1-\epsilon^{2}}X_{2})$ for a fixed random Gaussian $X_{2}$, the resulting polynomial in $X_{1}$ is likely to be approximately linear. Such an analysis will work for a sufficiently non-singular polynomial (i.e. a polynomial whose derivative is unlikely to be small). Not all polynomials are non-singular, but as we will show in Section 4, any polynomial can be written in terms of non-singular polynomials.

In Section 5, we use this theory to develop a sequence of iteratively more detailed generators eventually leading to one that satisfies our requirements. Using the ideas above, we show in Proposition 8 that for $X$ a true $n$-dimensional Gaussian and $Y$ a $k$-wise independent family of Gaussians that $\epsilon Y+\sqrt{1-\epsilon^{2}}X$ produces a PRG that fools degree-$d$ PTFs to within $O_{d,k}(\epsilon^{k})$. Iteratively replacing the $X$ involved by such a generator, we obtain a PRG (see Proposition 9) given by

Background

We will use the notation $O_{a}(N)$ to denote a quantity whose absolute value is bounded above by $N$ times some constant depending only on $a$. Throughout this paper, the variables $X,X_{1},\ldots$ will be used to denote multidimensional Gaussian random variables unless stated otherwise.

We recall here the definition of a polynomial threshold function:

Another important definition will be the following:

Note that any $k$-wise independent family of Gaussians is a $k$-design. Also note that applying any orthogonal transformation to a $k$-design yields another $k$-design. Throughout this paper we will use the variables $Y,Y_{1},Y_{i},\ldots$ to denote $k$-designs for some $k$ unless otherwise specified.

2 Polynomials of Gaussians

We recall some basic facts about polynomials of Gaussians. We begin by recalling the $L^{t}$-norm of a function.

We now recall some basic distributional results about polynomials evaluated at random Gaussians.

Where the probability is over $X$, a standard $n$-dimensional Gaussian.

We will make use of the hypercontractive inequality. The proof follows from Theorem 2 of .

If $p$ is a degree-$d$ polynomial and $t>2$, then

In particular this implies the following concentration bound:

If $p$ is a degree-$d$ polynomial and $N>0$, then

Apply the Markov inequality and Lemma 2 with $t=(N/2)^{2/d}$. ∎

3 Orthogonal Polynomials

We recall that the orthogonal polynomials form an orthonormal basis of the set of polynomials with respect to the Gaussian inner product. Thus any polynomial can be written uniquely as a linear combination of orthogonal polynomials

be the sum of the terms in the above decomposition consisting of orthogonal polynomials of degree exactly $k$. Furthermore, we let

Where $\partial_{X_{i}}$ above denotes the directional derivative in the $X_{i}$ direction for $X_{i}$ a random Gaussian.

Polynomial Approximation of Expectations

In this Section, we prove the following Proposition, which says that the expectation of a threshold function of a polynomial $p$, that is approximately linear can be approximated by a polynomial in the coefficients of $p$.

Where above $|q|$ denotes the largest absolute value of a coefficient of $q$. Furthermore, using the same notation, $|R|\leq\log(\epsilon^{-1})^{O_{d,m,k}(1)}.$

In order to expand upon the intuition behind Proposition 4, we begin by sketching the proof in the case that $m=d=1$. In this case we may write $q(x)=ax+b$. It is then the case that

The key idea is to evaluate the above by making the change of variables $y=(1+a)x+b.$ The above is then equal to

For small $a$ and $b$, we may approximate the integrand above by a degree $k-1$ Taylor polynomial in $a$ and $b$ introducing an error on the order of $|q|^{k}$ in the process. Integrating then yields a polynomial in $a$ and $b$ plus a small error. The proof of Proposition 4 is a straightforward generalization of this idea, though we will see some technical difficulties arising from the more complicated change of variables, and the necessity of keeping better track of errors.

where $\phi(x)=(2\pi)^{-m/2}e^{-\frac{|x|_{2}^{2}}{2}}$. Up to an error of $O_{m,N}(\epsilon^{N})$, we may ignore the integral outside of the range where $|x|_{2}\leq\log(\epsilon^{-1})$. Note furthermore, that in this range, for $\epsilon$ and $|q|$ sufficiently small, we have

Again, if $\epsilon$ and $|q|$ are sufficiently small, then

and thus $M$ maps the ball of radius $3\log(\epsilon^{-1})$ to itself. For $|x|\leq 3\log(\epsilon^{-1})$, we have that $|q^{\prime}(x)|$ is bounded by $O_{d,m}(|q||x|^{d-1})$. For $|q|$ a sufficiently small multiple of $\epsilon^{1/(2k)}$, this is strictly less than $1/2$. Thus $M$ is a contraction mapping and thus has a unique fixed point. On the other hand, $M(x)=x$ if and only if $p(x)=y$. Therefore, for such $y$, we have a unique inverse. We may now write our expectation as

Our plan is now to compute this integral by making the change of variables $y=p(x)$. We know from the above that in the domain of interest there is a function $p^{-1}$, which by the Inverse Function Theorem is necessarily smooth. Thus,

We may Taylor expand $\phi(x)$ about $x=y$ to obtain an expression

where $T_{k,y}$ is a polynomial of degree less than $k$ with coefficients of size $O_{m,k}(1)$. Similarly, we may write $|\textrm{Jac}(p(x))|$ as a polynomial in $x$ and $q$ that is equal to $1+O_{d,m}(|q|(1+|x|)^{d(d-1)}).$ We may therefore Taylor expand its inverse as

where $S_{k}$ is a polynomial of degree at most $k(d+1)$ and coefficients of size $O_{d,m,k}(1)$.

Putting the above together, we have that:

Where above $R_{y}(q)$ is some polynomial in $q$ of degree $O_{d,m,k}(1)$ with coefficients dependent on $y$ and of size at most $\log(\epsilon^{-1})^{O_{d,m,k}(1)}$. By absorbing the terms of $R_{y}$ of degree at least $k$ into the error, we may assume that $R$ has degree strictly less than $k$. Therefore, we have that

we have by Equation (1) that (noting that the domain of integration has volume at most $(4\log(\epsilon^{-1}))^{m}$)

We can use Proposition 4 to analyze a simple form of our generator.

Let $p$ be a degree-$d$ polynomial that can be written in the form $p(x)=h(q_{1}(x),\ldots,q_{m}(x))$ for some function $h$ and some polynomials $q_{i}$ of degree at most $d$. Let $f(x)=\textrm{sgn}(p(x))$ be the corresponding polynomial threshold function. Suppose that for each $i$ that $q_{i}(x)=x_{i}+r_{i}(x)$ for some polynomial $r_{i}$. Let $\epsilon>0$ be a real number and $k$ be an even integer. Let $X$ be a random Gaussian and $Y$ a $kd$-design that is independent of $X$. Then

We may rewrite $X$ as $(X_{0},X_{1})$, where $X_{0}$ is the Gaussian given by the first $m$ coordinates of $X$ and $X_{1}$ consists of the remaining coordinates. We let $Q(x_{0},x_{1},y)$ be the vector-valued polynomial given by

Upon fixing values for $Y$ and $X_{1}$ we let $q^{Y,X_{1}}(X_{0})$ be the vector valued polynomial given by

Where $g$ above is given by $g(x)=\textrm{sgn}(h(\sqrt{1-\epsilon^{2}}x))$, and $R$ is the appropriate polynomial given by Proposition 4. Since the expectation of $R(q^{X_{1},Y})$ is determined the moments $Y$ up to degree $kd$, this expectation is determined up to an error of

We note that $|q^{X_{1},Y}|=O_{d,m}(|q^{X_{1},Y}|_{2})=O_{d,m,k}(|q^{X_{1},Y}|_{k}).$ Therefore the error above is

Where the second to last line above is by Lemma 2 and the fact that $Y$ is a $kd$-design. ∎

Non-Singular Sets

Given a sequence of polynomials $(q_{1},\ldots,q_{m})$, we say that they form an $(\epsilon,c,N)$-non-singular set if

For every monomial $\prod x_{i}^{a_{i}}$ appearing in $h$, we have that $\sum a_{1}\deg(q_{i})\leq d$

Furthermore, we say that a polynomial $p$ has an $(\epsilon,c,N)$-non-singular decomposition of size $m$ if $p$ has a decomposition $(h,q_{1},\ldots,q_{m})$ with $|q_{i}|_{2}\leq 1$ for all $i$ and so that $(q_{1},\ldots,q_{m})$ is an $(\epsilon,c,N)$-non-singular set.

The key fact about these decompositions that we will need is the following structure theorem.

Let $p$ be a degree-$d$ polynomial, and let $\epsilon,c,N>0$. Then there exists a degree-$d$ polynomial $p_{0}$ with $|p-p_{0}|_{2}=O_{c,d,N}(\epsilon^{N})|p|_{2}$ so that $p_{0}$ has an $(\epsilon,c,N)$-non-singular decomposition of size $O_{c,d,N}(1)$.

This follows from the proof of the Diffuse Decomposition Theorem of . ∎

The PRG

In this Section, we will prove a sequence of increasingly more powerful results for PRGs. We begin by showing that if our polynomial has a non-singular decomposition that $\epsilon Y+\sqrt{1-\epsilon^{2}}X$ is an appropriate generator.

Let $d,k$ be integers and $\epsilon>0$. Let $p$ be a degree-$d$ polynomial with an $(\epsilon,1/10,k)$-non-singular decomposition of size $m$. Let $f$ be the corresponding polynomial threshold function. Let $X$ be a Gaussian, and $Y$ a $10kd$-design independent of $X$. Then

First we assume that $\epsilon$ is sufficiently small given $d,m$ and $k$, for otherwise there is nothing to prove.

It suffices to show that the expectation of $f\left(\epsilon Y+\sqrt{1-\epsilon^{2}}X\right)$ is determined to within $O_{d,m,k}(\epsilon^{k})$ by the low order moments of $Y$.

Let $p$ have the $(\epsilon,1/10,k)$-non-singular decomposition $(h,q_{1},\ldots,q_{m})$. Write $\sqrt{1-\epsilon^{2}}X$ as $\sqrt{\epsilon}X_{1}+\sqrt{1-\epsilon-\epsilon^{2}}X_{2}$ for $X_{1}$ and $X_{2}$ independent Gaussians. Let $\epsilon X_{0}+\sqrt{\epsilon}X_{1}=\sqrt{\epsilon+\epsilon^{2}}Z$ for $X_{0}$ an independent Gaussian, and $W=\epsilon X_{0}+\sqrt{1-\epsilon^{2}}X$. Consider each of the $q_{i}$ as functions of $Z$ and $X_{2}$. Thinking of $X_{2}$ as fixed let $q_{i}^{X_{2}}(Z)=q_{i}(X_{2},Z)$. Notice that

Where $\partial_{X_{i}}^{Z}$ above denotes the directional derivative of with respect to $Z$ in the direction of $X_{i}$. Thus, since $\left|\left(q_{i}^{X_{2}}\right)^{[\geq 2]}\right|_{2}^{2}$ is given by a polynomial in $X_{2}$, we have by Corollary 3 that with probability $1-O_{d,m,k}(\epsilon^{k})$ that $\left|\left(q_{i}^{X_{2}}\right)^{[\geq 2]}\right|_{2}\leq\epsilon\log(\epsilon^{-1})^{d}$ for all $i$. Similarly, we may show that with this same probability that $\left|\left(q_{i}^{X_{2}}\right)^{}\right|_{2}\leq\sqrt{\epsilon}\log(\epsilon^{-1})^{d}$ for all $i$. For $X_{2}$ fixed, let $L_{i}:=\left(q_{i}^{X_{2}}\right)^{}.$

By non-singularity this means that with probability $1-O_{d,m,k}(\epsilon^{k})$ we have

On the other hand, the left hand side of the above is

Thus for $\epsilon$ sufficiently small, we have with probability at least $1-O_{d,m,k}(\epsilon^{k})$ over the choice of $X_{2}$ that

If this is the case, then the product of the singular values of the matrix with rows given by the gradients of the $L_{i}$ is at least $\epsilon^{m/2+1/10}$. Since none of the singular values can be larger than $O_{m}(\epsilon^{1/2}\log(\epsilon^{-1})^{d})$, this implies that all of the singular values of this matrix are at least $\epsilon^{1/4}$. Thus if the $q_{i}$ are replaced by a appropriate linear combinations of their old values (with coefficients at most $\epsilon^{-3/4}$) we can ensure that the $\partial L_{i}(Z)$ are orthonormal. By making an appropriate change of variables for $Z$, we may assume that $L_{i}(Z)=Z_{i}$. Removing the degree- harmonic part of $q_{i}^{X^{2}}$, we may assume that $q_{i}^{X_{2}}(Z)=Z_{i}+r_{i}(Z)$ with $|r_{i}|_{2}=O_{m}(\epsilon^{1/4}\log(\epsilon^{-1})^{d})$.

To summarize, with probability at least $1-O_{d,m,k}(\epsilon^{k})$ over the choice of $X_{2}$, there is an orthogonal change of variables for $Z$, and a sequence of polynomials $q_{i}^{\prime},r_{i}$ with $q_{i}^{\prime}(Z)=Z_{i}+r_{i}(Z)$ and $|r_{i}(Z)|_{2}=O_{m}(\epsilon^{1/4}\log(\epsilon^{-1})^{d})$ so that $p(Z,X_{2})$ has a decomposition into the $q_{i}^{\prime}$. Applying Proposition 5, we find that with probability $1-O_{d,m,k}(\epsilon^{k})$ over $X_{2}$ we have that:

Taking an expectation over $X_{2}$ completes our proof. ∎

Next we use Theorem 6 to extend Proposition 7 to arbitrary polynomial threshold functions.

Let $f$ be a degree-$d$ polynomial threshold function. Let $\epsilon>0$ and $k$ be an integer. Let $X$ be a random Gaussian and $Y$ a $10kd$-design independent of $X$. It is the case that

Let $f=\textrm{sgn}(p(x))$ for some degree-$d$ polynomial $p$ with $|p|_{2}=1$. By Theorem 6, there exists a degree-$d$ polynomial $p_{0}$ so that $|p-p_{0}|_{2}=O_{d,k}(\epsilon^{2kd+k})$ so that $p_{0}$ has an $(\epsilon,1/10,k)$-non-singular decomposition of size $m=O_{d,k}(1)$. Since $\epsilon Y+\sqrt{1-\epsilon^{2}}X$ is a $2d$-design, we have by the Markov bound that with probability $1-O_{d,k}(\epsilon^{k})$ that

Note that the polynomials $p_{0}\pm\epsilon^{kd}$ also have $(\epsilon,1/10,k)$-non-singular decompositions of size $m$. Therefore, we have by the above, Proposition 7 and Lemma 1 that

And the other direction of the inequality follows analogously. ∎

Iterating applying Proposition 8 yields the following:

It is not hard to get rid of the $X$ in the above generator

Let $f(x)=\textrm{sgn}(p(x))$ for $p$ a degree-$d$ polynomial with $|p|_{2}=1$.

Assume that $X$ and $Y$ are independent and let

It is not hard to show that since $Y$ is a $2d$-design that

The other direction of the inequality holds analogously. ∎

For $d,k$ positive integers and $\epsilon>0$, there exists an explicit pseudorandom generator, $Y$ of seed length $O_{d,k}(\log(n)\epsilon^{-1})$ so that for $X$ an $n$-dimensional Gaussian, and $f$ any degree-$d$ polynomial threshold function in $n$ variables, then

then $Y$ can be generated from seed length

and has statistical distance at most $O(\epsilon^{k})$ from $Z$. Thus

Changing the value of $\epsilon$ appropriately, we have that

Let $d$ be a positive integer and $c,\epsilon>0$. There exists an explicit pseudorandom generator $Y$ with seed length $O_{c,d}(\log(n)\epsilon^{-c})$ so that for any degree-$d$ polynomial threshold function in $n$ variables, and $X$ an $n$-dimensional Gaussian,

Acknowledgements

This research was done with the support of an NSF postdoctoral fellowship.

References