Learning (Very) Simple Generative Models Is Hard
January 01, 1970
Abstract
Motivated by the recent empirical successes of deep generative models, we study the computational complexity of the following unsupervised learning problem. For an unknown neural network \(F:\mathbb{R}^d\to\mathbb{R}^{d'}\), let \(D\) be the distribution over \(\mathbb{R}^{d'}\) given by pushing the standard Gaussian \(\mathcal{N}(0,\textrm{Id}_d)\) through \(F\). Given i.i.d. samples from \(D\), the goal is to output any distribution close to \(D\) in statistical distance.
We show under the statistical query (SQ) model that no polynomial-time algorithm can solve this problem even when the output coordinates of \(F\) are one-hidden-layer ReLU networks with \(\log(d)\) neurons. Previously, the best lower bounds for this problem simply followed from lower bounds for supervised learning and required at least two hidden layers and \(\poly(d)\) neurons [1], [2].
The key ingredient in our proof is an ODE-based construction of a compactly supported, piecewise-linear function \(f\) with polynomially-bounded slopes such that the pushforward of \(\mathcal{N}(0,1)\) under \(f\) matches all low-degree moments of \(\mathcal{N}(0,1)\).
1 Introduction↩︎
In recent years, deep generative models such as variational autoencoders, generative adversarial networks, and normalizing flows [3]–[5] have seen incredible success in modeling real world data. These work by learning a parametric transformation (e.g. a neural network) of a simple distribution, usually a standard normal random variable, into a complex and high-dimensional one. The learned distributions have been shown to be shockingly effective at modeling real world data. The success of these generative models begs the following question: when is it possible to learn such a distribution? Not only is this a very natural question from a learning-theoretic perspective, but understanding this may also lead to more direct methods to learn generative models for real data.
More formally, we consider the following problem. Let \(D\) be the unknown pushforward distribution over \(\R^d\) given by \(f(g)\), where \(g \sim \calN(0, \Id)\) is a standard normal Gaussian, and \(f\) is an unknown feed-forward neural network with non-linear (typically ReLU) activations. Such distributions naturally arise as the output of many common deep generative models in practice. The learner is given \(n\) samples from \(D\), and their goal is to output the description of some distribution which is close to \(D\).
When \(f\) is a one-layer network (i.e. of the form \(f(g) = \mathop{\mathrm{ReLU}}(W g)\)), there are efficient algorithms for learning the distribution [6], [7]. However, this setting is unsatisfactory in many ways, as one-layer networks lack much of the complex structure that makes these generative models so appealing in practice. Indeed, when the neural network only has a single layer, the resulting distribution is similar to a truncated Gaussian, and one can leverage techniques developed for learning from truncated samples. Notably, this structure disappears even with two-layer neural networks. Even in the two-layer case, despite significant interest, very little is known about how to learn \(D\) efficiently.
In fact, a recent line of work suggests that learning neural network pushforwards of Gaussians may be an inherently difficult computational task. Recent results of [1], [2] show hardness of supervised learning from labeled Gaussian examples under cryptographic asssumptions, and the latter also demonstrates hardness for all statistical query (SQ) algorithms (see Section 1.3 for a more detailed description of related work). These naturally imply hardness in the unsupervised setting (see Appendix 7). However, these lower bound constructions still have their downsides. For one, all of these constructions require at least three layers (i.e. two hidden layers), and so leave open the possibility that efficient learning is possible when the neural network only has one hidden layer. Additionally, the resulting neural networks in these constructions are quite complicated. In particular, the size of the neural networks in these hard instances, that is, the number of hidden nonlinear activations for any output coordinate, must be polynomially large. This begs the natural question:
Can we learn pushforwards of Gaussians under one-hidden-layer neural networks of small size?
1.1 Our Results↩︎
We demonstrate strong evidence that despite the simplicity of the setting, this learning task is already computationally intractable. We show there is no polynomial-time statistical query (SQ) algorithm which can learn the distribution of \(f(g)\), when \(g \sim \calN(0, \Id)\) and each output coordinate of \(f\) is a one-hidden-layer neural networks of logarithmic hidden size. We formally define the SQ model in Section 2; we note that it is well-known to capture almost all popular learning algorithms [8].
Theorem 1 (informal, see Theorem 3). For any \(d > 0\), and any \(C \geq 1\), there exists a family of one-hidden-layer neural networks \(\calF\) from \(\R^d\) to \(\R^{d^C}\) so that the following properties hold. For any \(f \in \calF\), let \(D_f\) denote the distribution of \(f(g)\), for \(g \sim \calN(0, \Id)\). Then, we have that:
For all \(f \in \calF\), \(\mathop{\mathrm{d_{\mathrm{TV}}}}(\calN(0, \Id), D_f) = \Omega (1)\),4
Every output coordinate of \(f\) is a sum of \(O(\log d / \log \log d)\) ReLUs, with \(\poly(d)\)-bounded weights.
Any SQ algorithm which can distinguish between \(D_f\) and \(\calN(0, \Id)\) with high probability for all \(f \in \calF\) requires \(d^{\omega (1)}\) time and/or samples.
In other words, there is a family of one-hidden-layer ReLU networks of logarithmic size whose corresponding pushforwards are statistically very far from Gaussian, yet no efficient SQ algorithm can distinguish them from a Gaussian. Note this implies hardness even of improperly learning such pushforwards: not only is it hard to recover the parameters of the network or output a network close to the underlying distribution \(D_f\), but it is hard to learn any distribution close to \(D_f\).
Since such networks are arguably some of the simplest neural networks with more than one layer, this suggests that learning even the most basic deep generative models may already be a very difficult task, at least without additional assumptions. Still, this is by no means the last word in this direction. Given the real world success of deep generative models, a natural and important direction is to identify natural conditions under which we can efficiently learn. We view our results as a first step towards understanding the computational landscape of this important learning problem, and our result provides evidence that (strong) assumptions need to be made on \(f\) for the pushforward \(f(g)\) to be efficiently learnable, even in very simple two-layer cases.
1.2 Our Techniques↩︎
Like many recent SQ lower bounds, ours follows the general framework which was introduced in [9] and builds on [8]. Here one considers the following “non-Gaussian component analysis” task. Let \(D\) be a known, non-Gaussian distribution \(D\) over \(\R\). Given a unit vector \(v\) in \(d\) dimensions, let \(P^D_v\) denote the distribution over \(\R^d\) whose projection along \(v\) is given by \(D\) and whose projection in all directions orthogonal to \(v\) is standard Gaussian. Given samples from some unknown distribution over \(\R^d\), the goal is to decide whether the unknown distribution is \(\calN(0,\Id_d)\) or \(P^D_v\) for some \(v\). [9] showed that if \(D\)’s moments match those of \(\calN(0,1)\) up to some degree \(m\), then under mild conditions, any SQ algorithm for this task requires at least \(d^{\Omega(m)}\) queries (Lemma 4).
Suppose one could exhibit a one-hidden-layer ReLU network \(f:\R^\ell\to\R\) such that the pushforward \(D = f(\calN(0,\Id))\) satisfied such properties. Then we can realize \(P^D_v\) as a pushforward as follows. Let \(U\) be a rotation mapping the first standard basis vector in \(\R^d\) to \(v\). Then consider the function \(F:\R^{\ell+d-1}\to\R^d\) mapping \(z\) to \(U\cdot (f(z_1,\ldots,z_\ell),z_{\ell+1},\ldots,z_{\ell+d-1})\). One can check that every output coordinate of \(F\) is computed by a one-hidden-layer ReLU network with size essentially equal to that of \(f\). By [9], we would immediately get the desired SQ lower bound.
The main challenge is thus to construct such a network whose pushforward matches the low-degree moments of \(\calN(0,1)\). It is not hard to ensure the existence of such \(f\) with essentially infinite weights (Corollary 2 and Lemma 6). It is much less clear whether this is possible with polynomially bounded weights, and this is our primary technical contribution. We design and analyze a certain ODE which defines a one-parameter family of perturbations to \(f\), such that the low-degree moments of the corresponding pushforwards remain unchanged over time. By evolving along this family over an inverse-polynomial time scale, we obtain a network with polynomially bounded weights whose pushforward matches the low-degree moments of \(\calN(0,1)\). We defer the details to Section 4.
1.3 Related Work↩︎
A full literature review on the theory of learning deep generative models is beyond the scope of this paper (see e.g. the survey of [10]). For conciseness we cover only the most relevant papers.
1.3.0.1 Upper bounds.
In terms of upper bounds, much of the literature has focused on a different setting, where the goal is to understand when first order dynamics can learn toy generative models [7], [11]–[15], which are much simpler than the ones we consider here. For learning pushforwards of Gaussians under neural networks with ReLU activations, algorithms with provable guarantees are only known when the network has no hidden layers [6], [7]. This is in contrast to the supervised setting, where fixed parameter tractable algorithms are known for learning ReLU networks of arbitrary depth [16].
A different line of work seeks to find efficient learning algorithms when the activations are given by low degree polynomials [11], [17], [18]. Arguably the closest to our work is [18], which gives polynomial-time algorithms for learning low-degree polynomial transformations of Gaussians, in a smoothed setting. It is a very interesting open question if similar smoothed assumptions can be leveraged to circumvent our lower bound when the activations are ReLU. Unfortunately, these papers heavily leverage the nice moment structure of low-degree Gaussian polynomials, and it is unclear how their techniques can generalize to different activations.
1.3.0.2 Lower bounds.
Much of the literature on lower bounds for learning neural networks has focused on the supervised setting, where a learner is given labeled examples \((x, f(x))\), and the goal is to output a good predictor. There are many lower bounds known in the distribution-free setting [19]–[23], however, these do not transfer over to our (unsupervised) setting. When \(x\) is Gaussian, the aforementioned work of [1] derives hardness for learning two-hidden-layer networks with polynomial size for all SQ algorithms, as well as under cryptographic assumptions (see also [2]). It is not hard to show (see Appendix 7) that this lower bound immediately implies a lower bound for the unsupervised problem. In the supervised setting, lower bounds are also known against restricted families of SQ [24]–[26], when there are adversarially noisy labels [27]–[30], and in discrete settings [31]–[37], but to our knowledge, these results do not transfer to our setting.
The literature on lower bounds for the unsupervised problem we consider here is much sparser. Besides [1], [2], we also mention the recent work of [38] that studies whether achieving small Wasserstein GAN loss implies distribution learning. A corollary of their results is cryptographic hardness for learning pushforwards of Gaussians under networks with constant depth and polynomial size, but only when the learner is given by a Lipschitz ReLU network discriminator. However, this does not rule out efficient algorithms which do not output such Lipschitz discriminators.
Finally, we remark that the family of hard distributions we construct can be thought of as a close cousin of the “parallel pancakes” construction of [9]. This and slight modifications thereof are mixtures of Gaussians which are known to be computationally hard to known both in the SQ model [9], [39] and under cryptographic assumptions [40], [41].
1.3.0.3 SQ lower bounds via ODEs.
We remark that in a very different context, [28] also used an ODE to design a moment-matching construction. While our approach draws inspiration from theirs, an important difference is that they use their ODE as a “size reduction” trick to construct a step function \(f:\R\to\brc{\pm 1}\) with a small number of linear pieces such that \(\E[g\sim\calN(0,1)]{f(g)g^k} = 0\) for all small \(k\), while we use our ODE as a “weight reduction” trick to construct a continuous neural network \(f:\R\to\R\) with bounded weights such that \(\E[g\sim\calN(0,1)]{f(g)^k} = \E[g\sim\calN(0,1]{g^k}\). The form of the moments \(\E[g\sim\calN(0,1)]{f(g)g^k}\) they consider is simpler than in our setting, and while they essentially run their ODE to singularity and use non-quantitative facts like the invertibility of a certain Jacobian, we only run our ODE for a finite horizon and need to carefully control the condition number of the Jacobian arising in our setting over this horizon (e.g. Lemma 12).
2 Technical Preliminaries↩︎
2.0.0.1 Notation.
We freely abuse notation and use the same symbols to denote probability distributions, their laws, and their density functions. Given a distribution \(A\) over a domain \(\Omega\) and a function \(f:\Omega\to\Omega'\), we let \(f(A)\) denote the pushforward of \(A\) through \(f\), that is, the distribution \(A'\) of the random variable \(f(z)\) for \(z\sim A\). Let \(p\star q\) denote the convolution of \(p\) and \(q\). Also, we use \(\norm{\cdot}_p\) to denote \(\ell^p\) norm, omitting the subscript when \(p = 2\). \(\sigma_{\min}(\cdot)\) denotes minimum singular value.
2.0.0.2 Neural networks.
Define \(\mathop{\mathrm{ReLU}}(z) \triangleq \max(0,z)\).
Definition 1 (One-hidden-layer ReLU networks). We say that \(g: \R^d\to\R\) is a one-hidden-layer ReLU network with size \(S\) and \(W\)-bounded weights* if there exist \(w_1,\ldots,w_S\in\R^d\), \(b_1,\ldots,b_S\in\R\), and \(s_1,\ldots,s_S\in\brc{\pm 1}\) for which \[g(x) = \sum^S_{i=1} s_i\mathop{\mathrm{ReLU}}(\iprod{w_i,x} + b_i) \;\;\forall \;x\in\R^d.\] and \(\norm{w_i}, |b_i| \le W\) for all \(i\in S\).*
Given \(f: \R^d\to\R^{d'}\) whose output coordinates are of this form, together with a distribution \(A\) over \(\R^d\), we say that \(f(A)\) is a one-hidden-layer ReLU network pushforward of \(A\) with size \(S\) and \(W\)-bounded weights.**
2.0.0.3 Statistical query lower bounds.
Here we review standard concepts pertaining to establishing statistical query lower bounds for unsupervised learning problems, as developed in [8].
Definition 2 (Distributional search problems). Let \(\calD\) be a set of probability distributions, let \(\calF\) be a set of solutions, and let \(\mathcal{Z}: \calD\to 2^{\calF}\) be a map that takes any \(D\in\calD\) to a subset of \(\calF\) corresponding to the valid solutions for \(D\). We say that \(\mathcal{Z}\) specifies a distributional search problem over \(\calD\) and \(\calF\): given oracle access to an unknown \(D\in\calD\), the goal of the learner is to output a valid solution from \(\mathcal{Z}(D)\).
Definition 3 (Statistical query oracles). Given a distribution \(D\) over \(\R^d\) and parameters \(\tau, t > 0\), a \(\mathrm{STAT}(\tau)\) oracle* takes in any query of the form \(f: \R^d\to[-1,1]\) and outputs a value from the interval \([\E[x\sim D]{f(x)} - \tau, \E[x\sim D]{f(x)} + \tau]\), while a \(\mathrm{VSTAT}(t)\) oracle takes in any query of the form \(f: \R^d\to[0,1]\) and outputs a value from the interval \([\E[x\sim D]{f(x)} - \tau, \E[x\sim D]{f(x)} + \tau]\) for \(\tau = \max(1/t, \sqrt{\Var[x\sim D]{f(x)} / t})\).*
Definition 4 (Pairwise correlation). Given distributions \(p,q\) over a domain \(\Omega\) which are absolutely continuous with respect to a distribution \(r\) over \(\Omega\), we let \(\chi^2_r(p,q)\) denote the pairwise correlation, that is \[\chi^2_r(p,q) \triangleq \int_\Omega p(x)q(x)/r(x) \, \mathrm{d}x - 1.\] Note that when \(p = q\), this is simply the chi-squared divergence between \(p\) and \(r\).
We say that a set of \(m\) distributions \(\calD = \brc{D_1,\ldots,D_m}\) is \((\gamma,\beta)\)-correlated relative to a distribution \(\mu\) over \(\R^d\) if \[|\chi_\mu(D_i,D_j)| \le \begin{cases} \gamma & \text{if} \;i\neq j \\ \beta & \text{if} \;i = j \end{cases}.\]
Definition 5 (Statistical dimension). Let \(\beta,\gamma>0\), let \(\mathcal{Z}\) be a distributional search problem over distributions \(\calD\) and solutions \(\calF\), and let \(N\) be the largest integer for which there exists a distribution \(\mu\) and a finite subset \(\calD_\mu\subseteq \calD\) such that for any \(f\in\calF\), \(\calD_f \triangleq \calD_\mu \backslash\mathcal{Z}^{-1}(f)\) is \((\gamma,\beta)\)-correlated relative to \(\mu\) and \(|\calD_f| \ge N\). We say that the statistical dimension* with pairwise correlations \((\gamma,\beta)\) of \(\mathcal{Z}\) is \(N\) and denote it by \(\mathrm{SD}(\mathcal{Z},\gamma,\beta)\).*
Lemma 1 (Corollary 3.12 from [8]). Let \(\mathcal{Z}\) be a distributional search problem over distributions \(\calD\) and solutions \(\calF\). For \(\gamma,\beta\), if \(N = \mathrm{SD}(\mathcal{Z},\gamma,\beta)\), then any statistical query algorithm for \(\mathcal{Z}\) requires at least \(N\gamma/(\beta-\gamma)\) queries to \(\mathrm{STAT}(\sqrt{2\gamma})\) or \(\mathrm{VSTAT}(1/(6\gamma))\).
2.0.0.4 Gaussians and truncated Gaussians.
Henceforth \(\E[g]{\cdot}\) will always denote \(\E[g\sim\calN(0,\Id)]{\cdot}\). Let \(\gamma_{\sigma^2}(x)\triangleq \frac{1}{\sigma\sqrt{2\pi}} e^{-x^2/(2\sigma^2)}\). Given \(S\subset\R\), we will use \(\gamma_{\sigma^2}(S)\) to denote \(\int^\infty_{-\infty} \gamma(x)\cdot \bone{x\in S}\, \mathrm{d}x\). When \(\sigma = 1\), we will omit the subscript \(\sigma^2\). We will also use \(\gamma^{(d)}(x)\) to denote the density of \(\calN(0,\Id_d)\).
Given \(m,i\in\mathbb{N}\), let \(m^{\Downarrow i} \triangleq m(m - 2)\cdots (m - 2i + 2)\). Also let \(m^{\Downarrow 0} = 1\). With this notation, we have the following expression for the moments of a truncated Gaussian.
Lemma 2. For any \(k\in\mathbb{N}\), define the polynomial \[p_k(x) \triangleq \sum^{\floor{(k-1)/2}}_{i=0} (k-1)^{\Downarrow i} x^{k - 1 - 2i}. \label{eq:evenoddpoly}\qquad{(1)}\] For any \(a\le b\), \[\E[g]{g^k\cdot \bone{a\le g \le b}} = \begin{cases} (k-1)!!\cdot \gamma([a,b]) - (p_k(b)\gamma(b) - p_k(a)\gamma(a)) & \text{if} \;k \;\text{even} \\ - (p_k(b)\gamma(b) - p_k(a)\gamma(b)) & \text{if} \;k \;\text{odd} \end{cases}\]
Corollary 1. For any \(c,d\in\R\) and \(k\in\mathbb{N}\) even, \[\E[g]{(cg+d)^k\cdot \bone{a \le g \le b}} = \sum^k_{i=0 \;\text{even}} \binom{k}{i}c^id^{k-i}(k-1)!!\gamma([a,b]) - \sum^k_{i=0} \binom{k}{i}c^id^{k-i}(p_i(b)\gamma(b) - p_i(a)\gamma(a)).\]
2.0.0.5 Hidden direction distribution.
Given a distribution \(D\) over \(\R\) and \(v\in\S^{d-1}\), let \(P^D_{v}\) denote the distribution over \(\R^d\) with density \[P^D_{v}(x) = D(\iprod{v,x})\cdot \gamma^{(d-1)}(x - \iprod{v,x}v),\] that is the distribution which is given by \(D\) in the direction \(v\) and is given by \(\calN(0,\Id - vv^{\top})\) orthogonal to \(v\).
2.0.0.6 Miscellaneous technical facts.
Given two distributions \(p,q\) over a domain \(\Omega\), \(d_{\mathrm{TV}}(p,q) = 1 - \int_\Omega \min(p(x), q(x)) \, \mathrm{d}x\).
If \(V\in\R^{n\times n}\) is a Vandermonde matrix with nodes \(z_1,\ldots,z_n\), that is, \(V_{i,j} = z_j^{i-1}\), and \(\brc{z_i}\) are \(\zeta\)-separated, then \(\sigma_{\min}(V) \ge \frac{1}{n}\cdot \Omega(\zeta)^{n-1}\).
Theorem 2 (Peano’s existence theorem, see e.g. Theorem 2.1 from [42]). For \(T,r>0\) and \(y_0\in\R^n\), let \(B\subset\R\times \R^n\) be the parallelepiped consisting of \((t,y)\) for which \(0 \le t \le T\) and \(\norm{y - y_0}_{\infty} \le r\). If \(f: B\to\R\) is continuous and satisfies \(|f(t,y)| \le M\) for all \((t,y)\in B\), then the initial value problem \[y'(t) = f(t,y) \qquad \text{and} \qquad y(0) = y_0\] has a solution over \(t\in[0,\min(T,r/M)]\).
3 Statistical Query Lower Bound↩︎
In this section we prove our main theorem:
Theorem 3. Let \(d\in\mathbb{N}\) be sufficiently large. Any SQ algorithm which, given SQ access to an arbitrary one-hidden-layer ReLU network pushforward of \(\calN(0,\Id_d)\) of size \(O(\log d / \log\log d)\) with \(\poly(d)\)-bounded weights, outputs a distribution which is \(O(1)\)-close in \(\mathop{\mathrm{d_{\mathrm{TV}}}}(\cdot)\) must make at least \(d^{\Omega(\log d / \log\log d)}\) queries to either \(\mathrm{STAT}(\tau)\) or \(\mathrm{VSTAT}(1/\tau^2)\) for \(\tau = d^{-\Omega(\log d / \log\log d)}\).
Our proof will invoke the following key technical result whose proof we defer to Section 4. Roughly, it exhibits a two-dimensional one-hidden-layer ReLU network \(f:\R\to\R\) with bounded weights under which the pushforward of \(\calN(0,1)\) matches the low-degree moments of \(\calN(0,1)\) to arbitrary precision, in addition to some other technical conditions that we need to formally establish our statistical query lower bound:
Theorem 4. Fix any odd \(m\) and \(\nu, \sigma < 1\). There is a one-hidden-layer ReLU network \(f^*:\R^2\to\R\) of size \(O(m)\) with weights at most \(m^{O(m)}\) for which the pushforward \(D\triangleq f^*(\calN(0,\Id))\) satisfies
\(|\E[x\sim D]{x^k} - \E[g\sim\calN(0,1)]{g^k}| < \nu\) for all \(k = 1,\ldots,m\)
\(\chi^2(D,\calN(0,1)) \le \exp(O(m)) / \sigma\)
\(\mathop{\mathrm{d_{\mathrm{TV}}}}(P^D_v, P^D_{v'}) \ge 1 - 2\sigma\log(1/\sigma) - m^{-\Omega(m)}\) for any \(v,v'\in\S^{d-1}\) satisfying \(|\iprod{v,v'}| \ge 1/2\).
The rest of the proof of our lower bound will then follow the framework introduced in [9] and subsequently generalized in [43]. Specifically, we will use the following two lemmas from these works:
Lemma 3 (Lemma 3.5 from [43]). There is an absolute constant \(c > 0\) such that the following holds. Let \(m\in\mathbb{N}\) and \(\nu > 0\). If a distribution \(D\) over \(\R\) is such that 1) \(\chi^2(D,\calN(0,1))\) is finite, and 2) \(|\E[x\sim D]{x^k} - \E[g\sim\calN(0,1)]{g^k}| \le \nu\) for all \(k = 1,\ldots, m\), then for all \(v,v'\in\S^{d-1}\) for which \(|\iprod{v,v'}| < c\), \[|\chi^2_{\calN(0,\Id_d)}(P^D_v, P^D_{v'})| \le |\iprod{v,v'}|^{m+1} \chi^2(D,\calN(0,1)) + \nu^2.\]
For any constant \(0 < C < 1/2\), there exists a set \(S\) of \(2^{d^C}\) unit vectors in \(\S^{d-1}\) such that any pair of distinct \(u,v\in S\) satisfies \(|\iprod{u,v}| < d^{C-1/2}\).
These can be used to prove the following generic statistical query lower bound:
Lemma 4. Let \(m\in\mathbb{N}\) and \(0 < C < 1/2\). Let \(D\) be a distribution over \(\R\) such that 1) \(\chi^2(D,\calN(0,1))\) is finite, and 2) \(|\E[x\sim D]{x^k} - \E[g\sim\calN(0,1)]{g^k}| \le \Omega(d)^{-(m+1)(1/4-C/2)}\sqrt{\chi^2(D,\calN(0,1))}\) for all \(k = 1,\ldots, m\).
Consider the set of distributions \(\brc{P^D_v}_{v\in\S^{d-1}}\) for \(d\ge m^{\Omega(1/C)}\). If there is some \(\epsilon > 0\) for which \(\tvd(P^D_v, P^D_{v'}) > 2\epsilon\) whenever \(|\iprod{v,v'}| \le 1/2\), then any SQ algorithm which, given SQ access to \(P^D_v\) for an unknown \(v\in\S^{d-1}\), outputs a hypothesis \(Q\) with \(\tvd(Q,P^D_v) \le \epsilon\) needs at least \(d^{m+1}\) queries to \(\mathrm{STAT}(\tau)\) or to \(\mathrm{VSTAT}(1/\tau^2)\) for \(\tau\triangleq O(d)^{-(m+1)(1/4 - C/2)}\cdot \sqrt{\chi^2(D,\calN(0,1))}\).
Proof. Let \(S\) be the set of \(2^{d^C}\) unit vectors from Fact [fact:packing]. In the notation of Definition 5, take \(\mu = \calN(0,\Id)\) and let \(\calD_\mu \triangleq \brc{P^D_v}_{v\in S}\). By Lemma 3, for any distinct \(v,v'\in S\) we have \[\chi_\mu(P^D_v, P^D_{v'}) \le |\iprod{v,v'}|^{m+1}\chi^2(D,\calN(0,1)) + O(\tau^2) \le \Omega(d)^{-(m+1)(1/2-C)}\chi^2(D,\calN(0,1)).\] On the other hand, if \(v = v'\in S\), then \(\chi_\mu(P^D_v, P^D_v) = \chi^2(D,\calN(0,1)) + O(\tau^2) \le 2\chi^2(D,\calN(0,1))\). So for \[\gamma\triangleq \Omega(d)^{-(m+1)(1/2-C)}\chi^2(D,\calN(0,1)) \qquad \text{and} \qquad \beta \triangleq 2\chi^2(D,\calN(0,1)),\] \(\calD_\mu\) is \((\gamma,\beta)\)-correlated with respect to \(\mu\).
Consider the distributional search problem \(\mathcal{Z}\) mapping any distribution \(P^D_v\) to the set of probability distributions which are \(\epsilon\)-close in total variation distance to \(P^D_v\). Because \(\tvd(P_v,P_{v'}) > 2\epsilon\) for distinct \(v,v'\in S\), for any distribution \(f\) over \(\R^d\) we have that \(|\mathcal{Z}^{-1}(f)| \le 1\). We conclude that \(\mathrm{SD}(\mathcal{Z},\gamma,\beta) \ge 2^{\Omega(d^C)}\). By Lemma 1, we conclude that any SQ algorithm for \(\mathcal{Z}\) requires at least \(2^{\Omega(d^C)}d^{-(m+1)(1/2-C)}\) calls to either \(\mathrm{STAT}(\tau)\) or \(\mathrm{VSTAT}(1/\tau^2)\). Note that because we are assuming that \(d \ge m^{\Omega(1/C)}\), we have \(2^{\Omega(d^{C/2})} \ge d^{m+1}\), so the total number of required queries is at least \(2^{\Omega(d^{C/2})} \ge d^{m+1}\) as claimed. ◻
We are now ready to prove Theorem 3:
Proof of Theorem 3. By Theorem 4 applied with odd \(m\in\mathbb{N}\) larger than some absolute constant and with \(\sigma\) a sufficiently small absolute constant, there exists a distribution \(D = f^*(\calN(0,\Id_2))\) over \(\R\) for \(f^*:\R^2\to\R\) of size \(O(m)\) with \(m^{O(m)}\)-bouned weights satisfying the hypotheses of Lemma 4 for \(\epsilon = 0.49\), and \(\chi^2(D,\calN(0,1)) \le \exp(O(m))\). As long as \(m \le d^{O(C)}\), we conclude that an SQ algorithm for learning any distribution from \(\brc{P^D_v}_{v\in\S^{d-1}}\) to total variation distance \(1/4\) must make at least \(d^{m+1}\) queries to \(\mathrm{STAT}(\tau)\) or \(\mathrm{VSTAT}(1/\tau^2)\) for \(\tau \triangleq O(d)^{-(m+1)(1/4-C/2)}\cdot \exp(O(m))\). By taking \(m = \Theta(\log d/ \log\log d)\), we ensure that \(m^{O(m)} \le \poly(d)\). By taking \(C\) in Lemma 4 to be \(C = 1/4\), we obtain the desired lower bound.
The proof of the theorem is complete upon noting that any distribution \(P^D_v\) can be implemented as a pushforward of \(\calN(0,\Id_{d+1})\) under a one-hidden-layer ReLU network \(F_v: \R^{d+1}\to\R^d\) of size \(O(\log d / \log\log d)\) with \(\poly(d)\)-bounded weights. Let \(U\in O(d)\) be a rotation mapping the first standard basis vector in \(\R^d\) to \(v\). Then for \(F_v(z_1,\ldots,z_{d+1}) \triangleq U(f^*(z_1,z_2),z_3,\ldots,z_{d+1})\) we have that \(F_v(\calN(0,\Id_{d+1})) = P^D_v\) as desired. Furthermore, note that every output coordinate of \(F_v(z_1,\ldots,z_{d+1})\) is a one-hidden-layer ReLU network of the form \(\alpha f^*(z_1,z_2) + \iprod{u,(z_3,\ldots,z_{d+1})}\) for some vector \((\alpha,u)\in\R^d\). Note that the size of this network is two plus that of \(f^*\), and its weights are also upper bounded by \(\poly(d)\), so \(F_v\)’s output coordinates are of size \(O(\log d / \log\log d)\) as desired. ◻
Theorem 1 was stated with output dimension polynomially bigger than input dimension, whereas in our construction, the output dimension (\(d\)) is less than the input dimension (\(d+1\)). One can get the former by a padding argument (i.e. by duplicating output coordinates) to give a generator with arbitrarily large polynomial stretch and such that the \(d^{\log d / \log\log d}\) lower bound still applies.
4 Moment-Matching Construction↩︎
In this section we prove Theorem 4, the main technical ingredient in the proof of Theorem 3.
4.1 Moment-Matching With Unbounded Weights↩︎
In this section, we make the simple initial observation that for one-hidden-layer networks with unbounded weights, it is easy to construct networks such that the pushforward of \(\calN(0,1)\) under these networks matches the moments of \(\calN(0,1)\) to arbitrary precision. The starting point for this observation is the following well-known moment-matching construction:
Lemma 5 (Lemma 4.3 from [9]). For any \(m\in\mathbb{N}\), there exist weights \(\lambda_1,\ldots,\lambda_m\ge 0\) and points \(h_1,\ldots,h_m\in\R\) for which
(Moments match) \(\sum^m_{i=1} \lambda_i h_i^k = \E[g]{g^k}\) for all \(k = 0,\ldots,2m-1\).
(Points symmetric about origin) \(h_1 \le \cdots \le h_m\) and \(h_i = -h_{m-i+1}\) for all \(1\le i\le m\).
(Weights symmetric) \(\lambda_1 \le \cdots \le \lambda_{\ceil{m/2}}\) and \(\lambda_i = \lambda_{m-i+1}\).
(Points bounded and separated) \(\Omega(1/\sqrt{m}) \le |h_i| \le O(\sqrt{m})\) for all \(1\le i \le m\) and \(\brc{h_i}\) are \(\Omega(1/\sqrt{m})\)-separated.
(Weights not too small) \(\min_i \lambda_i \ge e^{-cm}\) for an absolute constant \(c > 0\).
(Central point and weight) If \(m\) is odd, then \(h_{(m+1)/2} = 0\) and \(\lambda_{(m+1)/2} = \Theta(1/\sqrt{m})\).
This immediately implies that there exists a discontinuous piecewise linear function \(f:\R\to\R\) for which the pushforward \(f(\calN(0,1))\) matches the low-degree moments of \(\calN(0,1)\):
Corollary 2. For any \(m\in\mathbb{N}\), there is a partition of \(\R\) into disjoint intervals \(I_1,\ldots,I_m\), along with a choice of scalars \(h_1,\ldots,h_m\), such that the step function \(f:\R\to\R\) given by \(f(z) = \sum^m_{i=1} h_i \cdot \bone{z\in I_i}\) satisfies \(\E[x\sim f(\calN(0,1))]{x^k} = \E[g\sim\calN(0,1)]{g^k}\) for all \(k = 0,\ldots,2m - 1\).
Proof. Let \(\lambda_1,\ldots,\lambda_m,h_1,\ldots,h_m\) be as in Lemma 5. As \(\sum_i \lambda_i = 1\), there is a partition of \(\R\) into disjoint intervals \(I_1,\ldots,I_m\) for which \(\gamma(I_i) = \lambda_i\) for all \(1\le i \le m\). Note that \(\E[x\sim f(\calN(0,1))]{x^k} = \sum_i \lambda_i h_i^k\), so the claim follows by Part [dks:moment] of Lemma 5. ◻
By infinitesimally perturbing the step function \(f\) in Corollary 2, we can ensure that \(f(\calN(0,1))\) still approximately matches the low-degree moments of \(\calN(0,1)\) to arbitrary precision and that the linear pieces of \(f\) have finite slopes, though some slopes will now be arbitrarily large. Such a function \(f\) can thus be represented as a one-hidden-layer ReLU network, but the issue is that the weights of this network will be arbitrarily large. The key technical challenge that we overcome in this section is to design a more careful way of perturbing \(f\) so that the resulting piecewise linear function has polynomially bounded slopes yet is such that \(f(\calN(0,1))\) matches the low-degree moments of \(\calN(0,1)\).
4.2 Bump Construction↩︎
Before we describe our perturbation scheme, we make a slight modification to the construction in Corollary 2. In place of a step function, we will consider a certain sum of bump functions.
Definition 6 (Bump functions). Given \(w,\epsilon > 0\) and \(h\in\R\), define \(T^{w,h,\epsilon}: \R\to\R\) by \[T^{w,h,\epsilon}(z) = \begin{cases} \frac{h}{\epsilon}(z + \epsilon + w) & \text{if} \;z \in [-\epsilon-w,-w] \\ h & \text{if} \;z \in [-w,w] \\ -\frac{h}{\epsilon}(z - \epsilon - w) & \text{if} \;z\in [w,\epsilon+w] \\ 0 & \text{otherwise}. \end{cases}\] Given \(c\in\R\), define \(T^{w,h,\epsilon}_c:\R\to\R\) by \(T^{w,h,\epsilon}_c(z) = T^{w,h,\epsilon}(z - c)\).
As \(T^{w,h,\epsilon}_c\) is continuous piecewise-linear, it can be represented as a one-hidden-layer ReLU network. The following elementary fact makes explicit the relation between the parameters of a bump function and the parameters of the corresponding network implementing it.
Given \(w,\epsilon>0\) and \(h,c\in\R\), \(T^{w,h,\epsilon}_c\) can be implemented as a one-hidden-layer ReLU network with size \(4\) and \(W\)-bounded weights for \(W \le \frac{h}{\epsilon}\max(1,|c| + \epsilon+w)\).
Proof. For all \(z\in\R\), \(T^{w,h,\epsilon}_c(z)\) is equal to \[\begin{align} & \frac{h}{\epsilon}\left(\mathop{\mathrm{ReLU}}(z - c + \epsilon + w) - \mathop{\mathrm{ReLU}}(z - c + w) - \mathop{\mathrm{ReLU}}(z - c - w) + \mathop{\mathrm{ReLU}}(z - c - \epsilon - w)\right).\qedhere \end{align}\] ◻
We now show how to replace the step function in Corollary 2 with a sum of bump functions for which \(\epsilon = 0\). As this new function will be the basis for the perturbation scheme we introduce in the next section, we also provide some quantitative bounds for its parameters:
Lemma 6. For any odd \(m\in\mathbb{N}\) and \(0 < \nu < 1\), there exist centers \(c_1\le\cdots \le c_{m-1}\), widths \(w_1,\ldots,w_{m-1} > 0\), heights \(h_1\le\cdots\le h_{m-1}\in\R\), and parameter \(\overline{\epsilon} > 0\) for which the following holds. Define the function \(f:\R\to\R\) by \[f(z)\triangleq \sum^{m-1}_{i=1} T^{w_i,h_i,\epsilon}_{c_i}(z) \label{eq:infinitebump95def}\qquad{(2)}\] for any \(0 \le \epsilon < \overline{\epsilon}\) (see Figure 1). Then \(f\) satisfies
(Bumps are well-separated) For all \(1 \le i < m - 1\), \(c_i + m^{-3/2} \le c_{i+1}\).
(Moments match) \(\E[x\sim f(\calN(0,1))]{x^k} = \E[g]{g^k}\) for all \(k = 1,\ldots,2m-1\).
(Symmetricity) \(w_i = w_{m-i}\), \(h_i = -h_{m-i}\), and \(c_i = -c_{m-i}\) for all \(1 \le i < m\).
(Bounded and separated heights) \(\Omega(1/\sqrt{m}) \le |h_i| \le O(\sqrt{m})\) for all \(1 \le i < m\), and \(\brc{h_i}\) are \(\Omega(1/\sqrt{m})\)-separated.
(Intervals not too thin) \(\min_i \gamma([c_i - w_i,c_i+w_i]) \ge e^{-cm}\) for an absolute constant \(c > 0\).
(Bounded endpoints) \(|c_i| + w_i \le O(\log m)\) for all \(1 \le i < m\).
To prove Lemma 6, we will need the following modification of the construction in Lemma 5.
Lemma 7. For any odd \(m\in\mathbb{N}\), there exist weights \(\lambda_1,\ldots,\lambda_{m-1} \ge 0\) and points \(h_1,\ldots,h_{m-1}\in\R\) for which
(Sum of weights bounded away from 1) \(\sum^{m-1}_{i=1} \lambda_i = 1 - \Theta(1/\sqrt{m})\).
(Moments match) \(|\sum^{m-1}_{i=1} \lambda_i h^k_i - \E[g]{g^k}| < \nu\) for all \(k = 1,\ldots,2m-1\).
(Points symmetric about origin) \(h_1 \le \cdots \le h_{m-1}\) and \(h_i = -h_{m-i}\) for all \(1 \le i < m\).
(Weights symmetric) \(\lambda_1 \le \cdots \le \lambda_{(m-1)/2}\) and \(\lambda_i = \lambda_{m-i}\).
(Points bounded and separated) \(\Omega(1/\sqrt{m}) \le |h_i| \le O(\sqrt{m})\) for all \(1 \le i < m\), and \(\brc{h_i}\) are \(\Omega(1/\sqrt{m})\)-separated.
(Weights not too small) \(\min_i \lambda_i \ge e^{-cm}\) for an absolute constant \(c > 0\).
Proof. Because \(m\) is odd, we can take the weights and points to be given by Lemma 5 and remove the \((m+1)/2\)-th weight and point– recall that the \((m+1)/2\)-th point is 0 and thus does not contribute to \(\sum_i \lambda_i h^k_i\). The fact that \(\sum^{m-1}_{i=1} \lambda_i = 1 - \Theta(1/\sqrt{m})\) then follows from the fact that the \((m+1)/2\)-th weight from Lemma 5 is of order \(\Theta(1/\sqrt{m})\) by Part [dks:middle] of Lemma 5. The remaining parts of the lemma follow by the corresponding parts of Lemma 5. ◻
Proof of Lemma 6. Let \(\lambda_1,\ldots,\lambda_{m-1},h_1,\ldots,h_{m-1}\) be as in Lemma 7. As \(\sum_i\lambda_i = 1 - \Theta(1/\sqrt{m})\), we claim there exist intervals \(I_1,\ldots,I_{m-1}\) such that for any \(i < j\), all points in \(I_i\) are strictly smaller than all points in \(I_j\), such that \(\gamma(I_i) = \lambda_i\) for all \(i\), and such that the right endpoint of any \(I_i\) is at least \(m^{-3/2}\) smaller than the left endpoint of \(I_{i+1}\).
We can construct these intervals in an inductive fashion. First, let \(\gamma \triangleq 1 - \sum_i \lambda_i = \Theta(1/\sqrt{m})\). Let \(I_1 = [a_1,b_1]\) for \(a_1 < b_1 < 0\) such that \(\gamma(I_1) = \lambda_1\) and \(\gamma((-\infty,a_1]) = \gamma/m\). Given \(I_1,\ldots,I_i\) for \(1\le i < (m-1)/2\), if \(I_i = [a_i,b_i]\) is the right endpoint of \(I_i\), then let \(a_{i+1} > b_i\) be such that \(\gamma([b_i,a_{i+1}) = \gamma/m\), and define \(I_{i+1} = [a_{i+1},b_{i+1}]\) for \(b_{i+1} > a_{i+1}\) satisfying \(\gamma([a_{i+1},b_{i+1}]) = \lambda_{i+1}\). By construction, \[\gamma((-\infty,b_{(m-1)/2}]) = \sum^{(m-1)/2}_{i=1} \gamma(I_i) + \frac{m-1}{2}\cdot \frac{\gamma}{m} = \frac{1-\gamma}{2} + \frac{m-1}{2m}\cdot \frac{\gamma}{2} = \frac{1}{2} - \frac{\gamma}{2m},\] so by Gaussian anticoncentration and the fact that \(\gamma = \Theta(1/\sqrt{m})\), we conclude that \(b_{(m-1)/2} \le -\Omega(m^{-3/2})\). In the same way, we also conclude that because \(\gamma([b_i,a_{i+1}]) = \frac{\gamma}{m}\), we must have \(b_i - a_{i+1} \le - \Omega(m^{-3/2})\). Finally, for \(i = (m-1)/2 + 1,\ldots,m-1\), we can define \(I_i\) to be the reflection of \(I_{m-i}\) about the origin. Note that by our bounds on \(b_i - a_{i+1}\) for \(1 \le i \le (m-1)/2\) and on \(b_{(m-1)/2}\), all of the intervals are \(\Omega(m^{-3/2})\)-separated from each other as claimed. And by design, \(\gamma(I_i) = \lambda_i\) for all \(1\le i \le m - 1\).
While the lemma is stated in terms of \(\epsilon > 0\), let us first consider the following construction where \(\epsilon = 0\). We can take the centers \(c_1,\ldots,c_{m-1}\) in the lemma to be the centers of \(I_1,\ldots,I_{m-1}\), and \(w_1,\ldots,w_{m-1}\) to be half of the widths of \(I_1,\ldots,I_{m-1}\), in which case \(f \triangleq \sum^{m-1}_{i=1} T^{w_i,h_i,0}_{c_i}\) immediately satisfies Parts [boxes:separated] and [boxes:sym] of the lemma. Then the pushforward of \(\calN(0,1)\) under this choice of \(f\) is the distribution which with probability \(\gamma\) equals zero (when \(z\sim\calN(0,1)\) lies outside of \(I_1,\ldots,I_{m-1}\)) and otherwise takes the value \(h_i\) with probability \(\lambda_i\). Parts [boxes:moment], [boxes:bounded], and [boxes:thin] then follow from Lemma 7. Finally, note that \(a_1\) defined above is at most \(O(\log m)\) in magnitude because \(\gamma((-\infty,a_1]) = \gamma/m\) by Part [dks2:nottoosmall] of Lemma 7. This establishes Part [boxes:endpoints] of the lemma.
Finally, note that by taking \(\epsilon\) infinitesimally small (relative to \(\nu\)) but positive, the function \(f\) defined in ?? satisfies all of the parts of the lemma. ◻
Unfortunately the slopes in the piecewise linear function constructed in Lemma 6 are arbitrarily large if \(\nu\) is arbitrarily small. The issue still remains of how to get a continuous piecewise-linear function whose slopes are polynomially bounded so that the corresponding ReLU network has polynomially bounded weights. As we illustrate in the next subsection however, the \(\Omega(m^{-3/2})\) spacing between the “bumps” in the definition of \(f\) in Lemma 6 gives us sufficient room to carefully perturb \(f\) to achieve this goal.
4.2.1 Estimates for Bump Moments↩︎
For convenience, define \[M^{w,h,\epsilon}_{c,k} \triangleq \E[g]*{T^{w,h,\epsilon}_c(g)^k}.\] We conclude this subsection by collecting some useful bounds for this quantity. First, we give an explicit expression for these moments:
Lemma 8. For \(c,w,h,\epsilon > 0\) satisfying \(c - \epsilon - w \ge 0\), we have \[\begin{gather} M^{w,h,\epsilon}_{c,k} = h^k\gamma([c-w,c+w]) + \\ (k-1)!!\left(\frac{h}{\epsilon}\right)^k\sum^k_{i=0 \;\text{even}} \binom{k}{i} \Bigg[ (-c+\epsilon+w)^{k-i}\gamma([c-\epsilon-w,c-w]) + (c+\epsilon+w)^{k-i}\gamma([c+w,c+\epsilon+w]) \Bigg] \\ - \left(\frac{h}{\epsilon}\right)^k\sum^k_{i=0} \binom{k}{i} \Bigg[ (-c+\epsilon+w)^{k-i}\left(p_i(c-w)\gamma(c-w) - p_i(c - \epsilon-w)\gamma(c-\epsilon-w)\right) \\ + (-1)^i (c+\epsilon+w)^{k-i}\left(p_i(c+\epsilon+w)\gamma(c+\epsilon+w) - p_i(c+w)\gamma(c+w)\right) \Bigg] \end{gather}\] for all even \(k\).
We defer the proof of this to Appendix 5.1. The particular form for this expression is not too important; we will only use it to make clear that \(M^{w,h,\epsilon}_{c,k}\) is continuously differentiable with respect to \(\epsilon\) when \(\epsilon > 0\), and to obtain the following expression for the derivative of the moments with respect to \(h\):
Lemma 9. \[\frac{\partial M^{w,h,\epsilon}_{x,k}}{\partial h} = \frac{k}{h} M^{w,h,\epsilon}_{x,k}\]
Proof. This is immediate from Lemma 8. ◻
We will also need the following bound showing that \(M^{w,h,\epsilon}_{c,k}\) does not change too much in a neighborhood of \((h,\epsilon)\):
Lemma 10. For any \(w\ge 0\), \(c,h,h'\in\R\), \(\epsilon'\ge \epsilon\ge 0\), and even \(k\in\mathbb{N}\), \[|M^{w,h',\epsilon'}_{c,k} - M^{w,h,\epsilon}_{c,k}| \le h^k\left(|(h'/h)^k - 1| + \epsilon'-\epsilon\right).\] In particular, this implies that \(\left|\frac{\partial M^{w,h,\epsilon}_{c,k}}{\partial\epsilon}\right| \le h^k\).
Proof. Note that \(0 \le M^{w,h,\epsilon}_{c,k} \le h^k\gamma([c-\epsilon-w,c+\epsilon+w])\), so the first part of the lemma follows by \[\begin{align} \MoveEqLeft |M^{w,h',\epsilon'}_{c,k} - M^{w,h,\epsilon}_{c,k}| \\ &\le |{h'}^k - h^k| \gamma([c-\epsilon'-w,c+\epsilon'+w]) + h^k\gamma([c-\epsilon'-w,c-\epsilon-w]\cup[c+\epsilon+w,c+\epsilon'+w]) \\ &\le |{h'}^k - h^k| + h^k(\epsilon'-\epsilon) = h^k\left(|(h'/h)^k - 1| + \epsilon'-\epsilon\right), \end{align}\] where in the last step we used that \(\gamma([a,a+\eta]) \le \eta/2\) for any \(a\in\R\), \(\eta \ge 0\). The second part of the lemma then follows by taking \(h = h'\) and \(\epsilon'\to\epsilon\). ◻
4.3 ODE-Driven Perturbation↩︎
Denote the parameters of the function constructed in Lemma 6 by \(\brc{(h_i(0),w_i,c_i)}_{1\le i < m}\). We will also define \(\epsilon(0)\) to be some arbitrarily small positive quantity satisfying \(\epsilon(0) \le \overline{\epsilon}\) for the parameter \(\overline{\epsilon}\) from Lemma 6.
We will design an ordinary differential equation whose solution specifies a one-parameter family of functions \[f_t \triangleq \sum^{m-1}_{i=1} T^{w_i,h_i(t),\epsilon(t)}_{c_i} \label{eq:ftdef}\tag{1}\] that arise from gradually perturbing the function from Lemma 6. Roughly speaking, starting at \(h_i(0)\) and \(\epsilon(0)\) for all \(1\le i < m\), perturbing the function along this one-parameter family will correspond to keeping the widths \(w_i\) and centers \(c_i\) of the bumps fixed, increasing the \(\epsilon\) parameter of every bump at unit speed, and evolving the heights \(h_i(t)\) in such a way that the moments of the pushforward of \(\calN(0,1)\) under \(f_t\) remain constant in \(t\) for all \(0 \le t \le T\). We illustrate this evolution in Figure 2. Here \(T\) is some horizon which is at least inverse-polynomially large but smaller than \(m^{-3/2}\) so that the “edges” \(c_i \pm (\epsilon(t) + w_i)\) of the bumps don’t collide with each other (this is where we make crucial use of Part [boxes:separated] of Lemma 6). At the end of this horizon, we want to show that the heights will not have changed too much, whereas the bumps now have \(\epsilon\) parameter given by inverse-polynomially large \(T\). This will imply that \(f_T\) has polynomially bounded slopes as desired.
As the odd moments of \(f_0(\calN(0,1))\) vanish and the parameters \(\brc{(w_i,h_i(0),c_i)}_{1\le i < m}\) satisfy the symmetry properties from Part [boxes:sym] of Lemma 6, it is easy to ensure that the odd moments of \(f_t(\calN(0,1))\) also vanish: simply take \(h_i(t) = -h_{m-i}(t)\) for all \(1\le i \le m-1\).
We thus focus on evolving \((h_1(t),\ldots,h_{(m-1)/2}(t))\). For convenience denote this by \(\vec{h}(t)\). Define moment vector \(\mu:\R^{(m-1)/2}\times \R\to\R^{m-1}\) by \[\mu(\vec{h},\epsilon) \triangleq \brc*{\sum^{(m-1)/2}_{i=1} M^{w_i,h_i,\epsilon}_{c_i,2\ell}}_{1\le \ell \le (m-1)/2}.\] For any fixed \((\vec{h},\epsilon)\) in a small neighborhood of \((\vec{h}(0),\epsilon(0))\), we want to show there is a direction \(v\in\R^{(m-1)/2}\) such that the directional derivative of \(\mu\) in the direction \(w\triangleq (v_1,\ldots,v_{(m-1)/2},1)\) is zero. Note that the constraint that \[\nabla_w \mu(\vec{h},\epsilon) = \vec{0}\] specifies a system of linear constraints of the form \[\sum^{(m-1)/2}_{i=1} v_i \cdot \frac{\partial M^{w_i,h_i,\epsilon}_{c_i,2k}}{\partial h_i} = -\sum^{(m-1)/2}_{i=1} \frac{\partial M^{w_i,h_i,\epsilon}_{c_i,2k}}{\partial \epsilon} \;\;\forall \;1\le \ell \le (m-1)/2. \label{eq:system}\tag{2}\] Recalling Lemma 9, we can rewrite this as \[\sum^{(m-1)/2}_{i=1} v_i \cdot \frac{2k}{h_i} M^{w_i,h_i,\epsilon}_{c_i,2k} = -\sum^{(m-1)/2}_{i=1} \frac{\partial M^{w_i,h_i,\epsilon}_{c_i,2k}}{\partial \epsilon} \;\;\forall \;1\le \ell \le (m-1)/2. \label{eq:system2}\tag{3}\] To express this more compactly, define \(\vec{b}(\epsilon)\in\R^{(m-1)/2}\) and \(Z(\vec{h},\epsilon)\) by \[\vec{b}(\epsilon)_{\ell} \triangleq -\sum^{(m-1)/2}_{i=1} \frac{\partial M^{w_i,h_i,\epsilon}_{c_i,2\ell}}{\partial \epsilon} \qquad \text{and} \qquad Z(\vec{h},\epsilon)_{i,\ell} \triangleq M^{w_i,h_i,\epsilon_i}_{c_i,2\ell}. \label{eq:bZdef}\tag{4}\] Also define the matrices \(A(\vec{h}) \triangleq \mathop{\mathrm{diag}}(1/h_1,\ldots,1/h_{(m-1)/2})\) and \(B \triangleq \mathop{\mathrm{diag}}(2,4,\ldots,m-1)\). Then 2 is equivalent to \[v^{\top} \cdot A(\vec{h})Z(\vec{h},\epsilon)B = \vec{b}(\epsilon)^{\top}.\] Provided \(A(\vec{h})Z(\vec{h},\epsilon)B\) is invertible, the natural choice for \(v\) would thus be the vector given by \(v = B^{-1}Z(\vec{h},\epsilon)^{-\top}A(\vec{h})^{-1} \cdot \vec{b}(\epsilon)\). Therefore, defining \[w(t,\vec{h}) \triangleq \left(B^{-1}Z(\vec{h},\epsilon(0) + t)^{-\top} A(\vec{h})^{-1} \cdot \vec{b}(\epsilon(0) + t),1\right), \label{eq:wdef}\tag{5}\] we consider the following initial value problem \[\vec{h}'(t) = w(t,\vec{h}(t)) \qquad \text{and} \qquad \vec{h}(0) = (h_1(0),\ldots,h_{(m-1)/2}(0)). \label{eq:IVP}\tag{6}\] Note that if we had a solution \(\vec{h}(t)\) to 6 for \(t\in[0,T]\) for some horizon \(T\), then we would have \[\frac{\partial}{\partial t}\mu(\vec{h}(t),t) = \left(\frac{\partial}{\partial (\vec{h}(t),t)} \mu(\vec{h}(t),t)\right)\cdot \vec{h}'(t) = \nabla_{w(t)}\mu(\vec{h}(t),t) = \vec{0}, \label{eq:mainode}\tag{7}\] implying that the low-degree moments of \(f_t\) defined in 1 are constant in \(t\) as desired.
4.4 Existence and Boundedness of \(\vec{h}(t)\)↩︎
To carry out the strategy outlined in Section 4.3, we must establish that
A solution to the initial value problem 6 exists over a non-negligible horizon \(T\).
The entries of \(\vec{h}(t)\) do not explode in \(t\).
For both of these, we need to show that the matrix \(Z(\vec{h},\epsilon)\) is invertible or, more specifically, well-conditioned for \((\vec{h},\epsilon)\) in a neighborhood of \((\vec{h}(0),\epsilon(0))\). We first establish this at time \(t = 0\) by relating \(Z(\vec{h}(0),\epsilon(0))\) to a certain Vandermonde matrix and appealing to Fact [fact:vandermonde]:
Lemma 11. \(\sigma_{\min}(Z(\vec{h}(0),\epsilon(0))) \ge m^{-Cm}\) for an absolute constant \(C > 0\).
Proof. For convenience, in this proof we refer to \(Z(\vec{h}(0),\epsilon(0))\) as \(Z\). Note that \(Z_{i,\ell} = \gamma([c_i-w_i,c_i+w_i])\cdot h_i(0)^{2\ell} + \xi_{i,\ell}\) for some \(\xi_{i,\ell}\) which can be made arbitrarily small by taking \(\epsilon(0)\) to be arbitrarily small. We can thus write \(Z = \Lambda H + \Xi\) for \(\Lambda = \mathop{\mathrm{diag}}(\lambda_1 h_1(0)^2,\ldots,\lambda_{(m-1)/2} h_{(m-1)/2}(0)^2)\), \(H\in\R^{(m-1)/2\times (m-1)/2}\) given by \(H_{i,\ell} = h_i(0)^{2\ell-2}\), and \(\Xi\) a matrix consisting of arbitrarily small positive entries. So \(\sigma_{\min}(Z) \ge (\min_i \lambda_i h_i(0)^2)\cdot \sigma_{\min}(H) - \xi \ge (e^{-cm}/m) \cdot \sigma_{\min}(H) - \xi\) for arbitrarily small \(\xi > 0\), where in the last step we used Parts [boxes:bounded] and [boxes:thin] of Lemma 6.
Finally, note that \(H\) is a Vandermonde matrix with nodes \(h_1(0)^2,\ldots,h_{(m-1)/2}(0)^2\). As \(\brc{h_i(0)}\) are \(\Omega(1/\sqrt{m})\)-separated and lie within \([\Omega(1/\sqrt{m}),O(\sqrt{m})]\), \(\brc{h_i(0)^2}\) are \(\Omega(1/m)\)-separated. So by Fact [fact:vandermonde], \(\sigma_{\min}(H) \ge m^{-O(m)}\), concluding the proof. ◻
We can use Lemma 11 to deduce that for \((\vec{h},\epsilon)\) in a neighborhood of \((\vec{h}(0),\epsilon(0))\), \(Z(\vec{h},\epsilon)\) is also well-conditioned:
Lemma 12. Let \(C > 0\) be the absolute constant from Lemma 11. For any \((\vec{h},\epsilon)\) satisfying \(\norm{\vec{h} - \vec{h}(0)}_{\infty} \le m^{-C'm}\) and \(0 \le \epsilon - \epsilon(0) \le m^{-C'm}\) for sufficiently large absolute constant \(C'>0\), \(\sigma_{\min}(Z(\vec{h},\epsilon)) \ge m^{-Cm}/2\).
Proof. For convenience, in this proof we refer to \(Z(\vec{h},\epsilon)\) and \(Z(\vec{h}(0),\epsilon(0))\) by \(Z'\) and \(Z\) respectively. By Lemma 10, each entry of \(Z'\) differs from the corresponding entry of \(Z\) by at most \[(\max_i h_i^{m-1})\cdot \left(\Big|(1+m^{-C'm}/(\min_i h_i))^{m-1}-1\Big| + m^{-C'm} - \epsilon(0)\right).\] As \(\max_i h_i \le O(\sqrt{m})\) and \(\min_i h_i \ge \Omega(1/\sqrt{m})\) by Part [boxes:bounded] of Lemma 6, and \(\epsilon(0)\) can is an arbitrarily small positive quantity, the above is at most \(m^{-C''m}\) for some absolute constant \(C'' > 0\) which is increasing in \(C'\). So \(\norm{Z - Z'}_\mathsf{op}\le \norm{Z - Z'}_F \le (m-1)/2 \cdot m^{-C''m} \ll m^{-Cm}\) provided we take \(C'\) sufficiently large. ◻
To establish Property 1, we must first verify that \(w(t,\vec{h})\) is continuous:
Lemma 13. Let \(C' > 0\) be the absolute constant from Lemma 12. Then the function \(w(t,\vec{h})\) defined in 5 is continuous with respect to both \(t\) and \(\vec{h}\) for \(t\le m^{-C'm}\) and \(\norm{\vec{h} - \vec{h}(0)}_{\infty} \le m^{-C'm}\).
Proof. By our expression for \(M^{w,h,\epsilon}_{c,k}\) in Lemma 8 and the definition of \(\vec{b}(\epsilon)\) in 4 , \(\vec{b}(\epsilon(0) +t)\) is clearly continuous in \(t\) whenever \(t \ge 0\) (because \(\epsilon(0) > 0\)). Similarly, \(A(\vec{h}) Z(\vec{h},\epsilon(0) + t) B\) is clearly continuous with respect to \(\vec{h}\) and \(t\) whenever \(t \ge 0\) and \(h_i\neq 0\) for all \(i\). By Lemma 12, if \(t\le m^{-C'm}\) and \(\norm{\vec{h} - \vec{h}(0)}_{\infty} \le m^{-C'm}\) (which additionally implies that \(h_i \neq 0\) for all \(i\), by Part [boxes:bounded] of Lemma 6), then \(A(\vec{h}) Z(\vec{h},\epsilon(0) + t) B\) is invertible. We conclude that for such \(t,\vec{h}\), \(w\) is continuous. ◻
Lastly, we need to show that for any \((t,\vec{h})\) satisfying the hypotheses of Lemma 13, \(\norm{w(t,\vec{h})}_{\infty}\) is not too large, which will imply Property 1 above by Theorem 2 and Property 2 above by noting that \(\norm{\vec{h}'(t)}_{\infty} = \norm{w(t,\vec{h}(t))}_{\infty}\):
Lemma 14. Let \(C' > 0\) be the absolute constant from Lemma 12. If \(t\le m^{-C'm}\) and \(\norm{\vec{h} - \vec{h}(0)}_{\infty} \le m^{-C'm}\), then \(\norm{w(t,\vec{h})}_\infty \le m^{C'' m}\) for some absolute constant \(C'' > 0\).
Proof. By the second part of Lemma 10, every entry of \(\vec{b}(\epsilon(0) + t)\) is at most \[\frac{m-1}{2}\cdot (\max_i h_i)^{m-1} \le \frac{m-1}{2}\cdot \left(O(\sqrt{m}) + m^{-C'm}\right)^{m-1} \le m^{O(m)},\] where in the penultimate step we used Part [boxes:bounded] of Lemma 6 and our hypothesis on \(\vec{h}\). Note that \(\sigma_{\min}(Z(\vec{h},\epsilon(0)+t))\ge m^{-Cm}/2\) by Lemma 12, \(\sigma_{\min}(B) \ge 2\), and \(\sigma_{\min}(A(\vec{h})) \ge \min_i 1/h_i \ge \Omega(\sqrt{m})\) by Part [boxes:bounded] of Lemma 6 and our hypothesis on \(\vec{h}\). We conclude that \(B^{-1}Z(\vec{h},\epsilon(0)+t)^{-\top} A(\vec{h})^{-1} \cdot \vec{b}(\epsilon(0)+t)\) has \(L_\infty\) norm at most \(m^{C''m}\) for some absolute constant \(C'' > 0\), so \(\norm{w(t,\vec{h})}_\infty \le m^{C'' m}\) as claimed. ◻
We are now ready to put all of these ingredients together to prove the key lemma which will allow us to establish Theorem 4:
Lemma 15. Fix any odd \(m\in\mathbb{N}\) and any \(0 < \nu < 1\). There is a one-hidden-layer ReLU network \(f: \R\to\R\) of size \(O(m)\) with weights at most \(m^{O(m)}\) for which the pushforward \(D = f(\calN(0,1))\) satisfies \(|\E[x\sim D]{x^k} - \E[g\sim\calN(0,1)]{g^k}| < \nu\) for all \(k = 1,\ldots,m\).
Proof. Let \(B\) be the parallelepiped consisting of \((t,\vec{h})\) for which \(0\le t \le m^{-C'm}\) and \(\norm{\vec{h} - \vec{h}(0)}_{\infty} \le m^{-C'm}\). By Lemma 13, \(w\) is continuous over \(B\). By Lemma 14, \(\norm{w(t,\vec{h})}_{\infty} \le m^{C''m}\).
By Theorem 2 we conclude that the initial value problem in 6 has a solution \(\vec{h}(t)\) over \(t\in[0,T]\) for \[T = m^{-(C'+C'')m}. \label{eq:Tdef}\tag{8}\] Furthermore, because \(\norm{\vec{h}'(t)}_\infty = \norm{w(t,\vec{h}(t))}_\infty \le m^{C''m}\), we conclude that \(\frac{1}{T}\norm{\vec{h}(T)}_\infty \le m^{C''m}\). The slopes of the bumps \(T^{w_i,h_i(T),\epsilon(0)+T}_{c_i}\) are therefore bounded by \(m^{C''m}\).
For \((m-1)/2 < i \le m - 1\), define \(h_i(T) = -h_{m-i}(T)\) and consider the one-parameter family of functions \(f_t \triangleq \sum^{m-1}_{i=1} T^{w_i,h_i(t),\epsilon(0)+t}_{c_i}\). Because \(c_i = c_{m-i}\) and \(w_i = w_{m-i}\) for all \(1\le i < m\) by Part [boxes:sym] of Lemma 6, we conclude that the odd moments of \(f_T(\calN(0,1))\) all vanish. As for the even moments, because \(\frac{\partial}{\partial t}\mu(\vec{h}(t),t) = \vec{0}\) by 7 , we conclude that the even moments of \(f_T(\calN(0,1))\) up to degree \(m - 1\) agree with those of \(f_0(\calN(0,1))\). So because \(D_0 = f_0(\calN(0,1))\) satisfies \(|\E[x\sim D]{x^k} - \E[g\sim\calN(0,1)]{g^k}| < \nu\) for all \(k = 1,\ldots,m\) by Part [boxes:moment] of Lemma 6, we conclude that the same holds for \(f_T\).
Finally, as the endpoints of the intervals supporting the bumps are bounded by \(O(\log m)\), we conclude from Fact [fact:implementbox] that \(f_T \triangleq \sum^{m-1}_{i=1} T^{w_i,h_i(T),\epsilon(0)+T}_{c_i}\) can be implemented by a one-hidden-layer ReLU network of size \(O(m)\) with weights at most \(m^{O(m)}\). ◻
4.5 Proof of Theorem 4↩︎
So far in Lemma 15 we have constructed a pushforward distribution computed by a one-hidden-layer ReLU network with \(m^{O(m)}\)-bounded weights satisfying the first part of Theorem 4. In this subsection we slightly modify this construction to additionally satisfy the remaining two parts of Theorem 4. The proofs here are standard (see e.g. [9]) and we defer them to the appendix.
First, to ensure that the chi-squared divergence between the pushforward and \(\calN(0,1)\) is not too large, we simply convolve (a scaling of) the pushforward by a suitable Gaussian. The following lemma gives an estimate for the resulting chi-squared divergence:
Lemma 16. Let \(A\) be any distribution supported on an interval \([-R,R]\). Then for any \(0 < \sigma \le 1/2\), \(\chi^2(A\star\calN(0,\sigma^2),\calN(0,1)) \le e^{O(R^2)}/\sigma\).
We defer the proof of this to Appendix 5.2. Next, we verify that appropriately scaling and convolving by a Gaussian doesn’t alter the moments of a distribution whose low-degree moments match those of \(\calN(0,1)\):
Lemma 17. Let \(D\) be any symmetric distribution for which \(|\E[x\sim D]{x^k} - \E[g]{g^k}| < \nu\) for all \(1\le k < m\). For any \(c\in\R\) let \(c\cdot D\) denote the distribution obtained by rescaling \(D\) by a factor of \(c\). Then \(D' \triangleq \sqrt{1-\sigma^2}\cdot D \star \calN(0,\sigma^2)\) satisfies \(|\E[x\sim D']{x^k} - \E[g]{g^k}| < \nu\) for all \(1 \le k < m\).
We defer the proof of this to Appendix 5.3. Finally, we show that scaling the pushforward from Lemma 15 and convolving by a Gaussian yields a distribution satisfying the third part of Theorem 4:
Lemma 18. Let \(D = f(\calN(0,1))\) be from Lemma 15, and define \(D' \triangleq \sqrt{1-\sigma^2}\cdot D \star \calN(0,\sigma^2)\). Then for any \(v,v'\in\S^{d-1}\) satisfying \(|\iprod{v,v'}| \le 1/2\), \(d_{\mathrm{TV}}(P^{D'}_v,P^{D'}_{v'}) \ge 1 - 2\sigma\log(1/\sigma) - m^{-\Omega(m)}\).
We defer the proof of this to Appendix 5.4. We are now ready to complete the proof of Theorem 4.
Proof of Theorem 4. Let \(f\) be the function constructed in Lemma 15 and define \(f^*:\R^2\to\R\) by \(f^*(z_1,z_2) = \sqrt{1-\sigma^2} f + \sigma z_2\). Note that \(f^*(\calN(0,\Id))\) is exactly \(\sqrt{1-\sigma^2} f(\calN(0,1)) \star \calN(0,\sigma^2)\), so the three parts of Theorem 4 follow immediately from Lemmas 17, 16, and 18 respectively. ◻
4.5.0.1 Acknowledgments.
We thank Adam R. Klivans, Raghu Meka, and Anru R. Zhang for many illuminating discussions about learning generative models.
5 Deferred Proofs↩︎
5.1 Proof of Lemma 8↩︎
Proof. By Corollary 1, the contribution from the interval \(g\in[c-\epsilon-w,c-w]\) to \(\E[g]*{\left(T^{w,h,\epsilon}_c(z)\right)^k}\) is given by \[\begin{gather} \sum^k_{i=0 \;\text{even}} \binom{k}{i}\left(\frac{h}{\epsilon}\right)^i \left(\frac{h}{\epsilon}(-c+\epsilon+w)\right)^{k-i}(k-1)!! \gamma([c-\epsilon-w,c-w]) - \\ \sum^k_{i=0} \binom{k}{i}\left(\frac{h}{\epsilon}\right)^i \left(\frac{h}{\epsilon}(-c+\epsilon+w)\right)^{k-i}\left(p_i(c-w)\gamma(c-w) - p_i(c - \epsilon-w)\gamma(c-\epsilon-w)\right). \end{gather}\] Similarly, the contribution from the interval \(g\in[c+w,c+\epsilon+w]\) is given by \[\begin{gather} \sum^k_{i=0 \;\text{even}} \binom{k}{i}\left(\frac{-h}{\epsilon}\right)^i \left(\frac{h}{\epsilon}(c+\epsilon+w)\right)^{k-i}(k-1)!! \gamma([c+w,c+\epsilon+w]) - \\ \sum^k_{i=0} \binom{k}{i}\left(\frac{-h}{\epsilon}\right)^i \left(\frac{h}{\epsilon}(c+\epsilon+w)\right)^{k-i}\left(p_i(c+\epsilon+w)\gamma(c+\epsilon+w) - p_i(c+w)\gamma(c+w)\right). \end{gather}\] Finally, the contribution from the interval \(g\in[c-w,c+w]\) is given by \(h^k\cdot \gamma([c-w,c+w])\). ◻
5.2 Proof of Lemma 16↩︎
Proof. Let \(\wt{A} \triangleq A\star\calN(0,1)\). By definition, \(\wt{A}(x) = \int^\infty_{-\infty} A(s) \gamma_{\sigma^2}(x - s) \, \mathrm{d}s\). So \[1 + \chi^2(\wt{A},\calN(0,1)) = \int^\infty_{-\infty} \frac{1}{\gamma(x)} \left(\int^\infty_{-\infty}\int^\infty_{-\infty} A(s)A(t)\gamma_{\sigma^2}(x-s)\gamma_{\sigma^2}(x-t) \, \mathrm{d}s\mathrm{d}t\right) \mathrm{d}x. \label{eq:onepluschi}\tag{9}\] Note that for any \(s,t\in\R\), \[\begin{align} \frac{\gamma_{\sigma^2}(x-s)\gamma_{\sigma^2}(x-t)}{\gamma(x)} &= \frac{1}{\sigma^2\sqrt{2\pi}} \exp\left(\frac{-(x-s)^2 - (x-t)^2}{2\sigma^2} + x^2/2\right) \\ &= \frac{1}{\sigma^2\sqrt{2\pi}} \exp\left(-\frac{2-\sigma^2}{2\sigma^2}\left(x-\frac{s+t}{2-\sigma^2}\right)^2 + \frac{2st-(s^2+t^2)(1-\sigma^2)}{2\sigma^2(2-\sigma^2)}\right), \end{align}\] so \[\int^\infty_{-\infty} \frac{\gamma_{\sigma^2}(x-s)\gamma_{\sigma^2}(x-t)}{\gamma(x)} \,\mathrm{d}x = \frac{e^\frac{2st-(s^2+t^2)(1-\sigma^2)}{2\sigma^2(2-\sigma^2)}}{\sigma\sqrt{2 - \sigma^2}}.\] Eq. 9 thus becomes \[1 + \chi^2(\wt{A},\calN(0,1)) = \int^\infty_{-\infty}\int^\infty_{-\infty} A(s)A(t)\cdot \frac{e^\frac{2st-(s^2+t^2)(1-\sigma^2)}{2\sigma^2(2-\sigma^2)}}{\sigma\sqrt{2 - \sigma^2}} \,\mathrm{d}s \mathrm{d}t \label{eq:intst}\tag{10}\] As \(A\) is supported on \([-R,R]\), \[\frac{e^\frac{2st-(s^2+t^2)(1-\sigma^2)}{2\sigma^2(2-\sigma^2)}}{\sigma\sqrt{2 - \sigma^2}} \le e^{O(R^2/(1-\sigma^2))} \le e^{O(R^2)}.\] Substituting this into 10 , we find that \[\begin{align} 1 + \chi^2(\wt{A},\calN(0,1)) &\le \frac{e^{O(k)}}{\sigma\sqrt{2-\sigma^2}} \int\int A(s)A(t) \, \mathrm{d}s\mathrm{d}t = \frac{e^{O(R^2)}}{\sigma\sqrt{2-\sigma^2}} \le e^{O(R^2)}/\sigma. \qedhere \end{align}\] ◻
5.3 Proof of Lemma 17↩︎
Proof. As the convolution is still a symmetric distribution, the odd moments clearly vanish. For any even \(k < m\), \[\begin{align} \E[x\sim D']{x^k} &= \E[z\sim D,g \sim\calN(0,1)]*{(\sqrt{1-\sigma^2} z+\sigma g)^k} = \sum^{k/2}_{\ell=0} \binom{k}{2\ell} \sigma^{2\ell} (1 - \sigma^2)^{k/2-\ell} \E[z]{z^{2\ell}}\E[g]{g^{k-2\ell}} \\ &\le \E[g,g'\sim\calN(0,1)]{(\sqrt{1-\sigma^2} g' + \sigma g)^k} + \nu \sum^{k/2}_{\ell=0} \binom{k}{2\ell} \sigma^{2\ell} (1 - \sigma^2)^{k/2-\ell} = \E[g\sim\calN(0,1)]{g^k} + \nu, \end{align}\] where in the third step we used that \(\sqrt{1-\sigma^2}\cdot D\) matches the moments of \(\calN(0,1 - \sigma^2)\) up to degree \(m\) to error \(\nu\), and in the last step we used that \(\sqrt{1-\sigma^2} g' + \sigma g\) is distributed as a draw from \(\calN(0,1)\). We can show in an identical fashion that \(\E[x\sim D']{x^k} \ge \E[g]{g^k} - \nu\), completing the proof. ◻
5.4 Proof of Lemma 18↩︎
Proof. By Fact [fact:tvequiv], it suffices to upper bound \(\int_{\R^d} \min(P_v(z), P_{v'}(z)) \, \mathrm{d}z\). Let \(H\) denote the plane spanned by \(v,v'\). As the component in \(H\) of a sample from either \(P_v\) or \(P_{v'}\) is independent from the component in \(H^{\perp}\), and the latter is distributed as \(\calN(0,\Pi_{H^{\perp}})\), it suffices to bound \(\int_H \min(P_v(z), P_{v'}(z)) \, \mathrm{d}z\). Let \(x,y\) be orthogonal coordinates for \(H\) with \(v\) in the direction of the \(x\)-axis, and let \(x',y'\) be orthogonal coordinates for \(H\) with \(v'\) in the direction of the \(x'\)-axis. Let \(\theta\) be the angle between \(v,v'\). Then \[\begin{align} \int_H \min(P_v(z),P_{v'}(z))\, \mathrm{d}z &= \int^\infty_{-\infty} \int^\infty_{-\infty} \min(D'(x)\gamma(y), D'(x')\gamma(y')) \,\mathrm{d}x\mathrm{d}y \\ &= \int^\infty_{-\infty}\int^\infty_{-\infty} \min(D'(x)\gamma(y), D'(x')\gamma(y')) \csc\theta \, \mathrm{d}x\mathrm{d}x'. \label{eq:minint} \\ \end{align}\tag{11}\] For \(1 \le i \le m -1\), let \(D_i\) denote the distribution of \(\sqrt{1-\sigma^2} \cdot T^{w_i,\vec{h}_i(T),T}_{x_i}(g)\) for \(g\sim\calN(0,1)\) conditioned on \(g\in[x_i - w_i - T, x_i + w_i + T]\). Also let \(D_m\) denote the distribution which is a point mass at zero. Let \(D'_i \triangleq D_i\star\calN(0,1)\). Note that there is a distribution \(p\) over \([m]\) for which \(D' = \E[i\sim p]{D'_i}\). Then we can upper bound 11 by \[\max_{i,j\in[m]} \int^\infty_{-\infty}\int^\infty_{-\infty} \min(D'(x)_i\gamma(y), D'_j(x')\gamma(y')) \csc\theta \, \mathrm{d}x\mathrm{d}x' \label{eq:ubound}\tag{12}\] Note that for \(1\le i \le m - 1\), \(\Pr[x\sim D'_i]{|x - x_i| > a} \le \sigma + \xi_i\) for \(a\triangleq 2\sigma\sqrt{\log(1/\sigma)}\) and \(\xi_i \triangleq \frac{\gamma([x_i - w_i - T,x_i - w_i]\cup [x_i + w_i, x_i+ w_i + T])}{\gamma([x_i - w_i - T, x_i + w_i + T])}\). And for \(i = m\), \(\Pr[x\sim D'_m]{|x - x_i| > a} \le \sigma\) for \(x_m \triangleq 0\). So we get an upper bound on 12 of \[\sigma + \max_{i\in[m-1]} \xi_i + \max_{i,j\in[m]} \int^{x_i + a}_{x_i - a} \int^{x_j + a}_{x_j - a} \min(D'_i(x)\gamma(y), D'_j(x')\gamma(y')) \csc\theta \, \mathrm{d}x\mathrm{d}x'\] As \(D'_i\) is a convolution of \(D_i\) with \(\calN(0,\sigma^2)\), \(D'_i(x) \le \frac{1}{\sigma\sqrt{2\pi}}\) for all \(x\in\R\). And \(\gamma(y) \le 1/\sqrt{2\pi}\), so the above display is at most \[\sigma + \max_{i\in[m-1]} \xi_i + a^2\csc\theta / (2\pi\sigma) = \sigma + \max_{i\in[m-1]} \xi_i + \sigma\csc\theta\log(1/\sigma)/\pi.\] Note that if \(|\iprod{v,v'}| \le 1/2\), then \(\csc\theta / \pi\le 2/(\sqrt{3}\pi) \le 1\). Finally, to bound \(\xi_i\), first note that for any \(i\in[m-1]\), \(\gamma([x_i - w_i - T, x_i + w_i + T]) = \lambda_i\), and recall that \(\lambda_i \ge e^{-cm}\) for some absolute constant \(c > 0\). On the other hand, \(\gamma([x_i - w_i - T, x_i - w_i]) \le T/\sqrt{2\pi} = m^{-(C'+C'')m}/\sqrt{2\pi}\) by Gaussian anti-concentration and our choice of \(T = m^{-(C'+C'')m}\) in the proof of Lemma 15. So by taking the constants \(C', C''\) to be larger than \(c\), we conclude that \(\xi_i \le m^{-\Omega(m)}\) for all \(i\in[m-1]\). ◻
6 Hardness for Estimation in Wasserstein↩︎
We now show an analogous version of Theorem 3 under the Wasserstein-1 metric rather than total variation distance. We begin by observing that the ODE-based evolution does not move the pushforward at time zero, i.e. the distribution constructed in Lemma 6, too far away in Wasserstein distance over a time horizon of \(T\):
Lemma 19. Let \(f_0, f_T: \R\to\R\) denote the functions from Lemmas 6 and 15 respectively. Define \(D_0\triangleq f_0(\calN(0,1))\) and \(D_T \triangleq f_T(\calN(0,1))\). Then \(W_1(D,D') \le m^{-\Omega(m)}\).
Proof. Recall that \(w_1,\ldots,w_{m-1}\) denote the widths of the bumps in \(f_0,f_T\), \(x_1,\ldots,x_{m-1}\) denote the centers, and the heights and \(\epsilon\) parameters for the bumps in \(f_0,f_T\) are given by \(\brc{h_i(0)}_i,\epsilon(0)\) and \(\brc{h_i(T)}_i,\epsilon(0)+T\) respectively, for \(T = m^{-(C'+C'')m}\) and \(\epsilon(0)\) an arbitrarily small positive quantity. Also recall from the proof of Lemma 15 that \(|h_i(0) - h_i(T)| \le m^{-C'm}\) for all \(i\).
Now consider any \(g\in\R\). If \(g\in[x_i - w_i, x_i + w_i]\) for some \(i\), then \(|f_0(g) - f_T(g)| = |h_i(0) - h_i(T)| \le m^{-C'm}\). Furthermore, \[\Pr[g\sim\calN(0,1)]{g\in[x_i - \epsilon_i(0) - T - w_i, x_i - w_i] \cup [x_i + w_i, x_i + \epsilon_i(0) + T + w_i] \;\text{for some} \;i} \le O(mT)\] Finally, for all \(g\) that do not lie in any of the aforementioned intervals, i.e. that do not lie in the support of any bump from \(f_0\) or \(f_T\), note that \(f_0(g) = f_T(g) = 0\) by construction. We conclude that for any 1-Lipschitz function \(h:\R\to\R\), \[\begin{align} \abs*{\E[z\sim D]{h(z)} - \E[z\sim D']{h(z)}} &= \abs*{\E[g]{h(f_0(g)) - h(f_T(g))}} \\ &\le \E[g]{|f_0(g) - f_T(g)|} \le m^{-C'm} + O(mT) \le m^{-\Omega(m)} \end{align}\] as claimed. ◻
We can now show the analogue of Lemma 18 for Wasserstein distance:
Lemma 20. Let \(D = f(\calN(0,1))\) be from Lemma 15, and define \(D' \triangleq \sqrt{1 - \sigma^2}\cdot D\star\calN(0,\sigma^2)\) for \(\sigma \ll 1/\sqrt{m}\). Then for any \(v,v'\in\S^{d-1}\) satisfying \(|\iprod{v,v'}| \le 1/2\), \(W_1(P^{D'}_v, P^{D'}_{v'}) \ge \Omega(1/\sqrt{m})\).
Proof. Let \(f_0\) be the function from Lemma 6, and let \(A\) denote \(f_0(\calN(0,1))\). We begin by lower bounding \(W_1(P^{A}_v, P^{A}_{v'})\), which we will do by showing that with \(\Omega(1)\) probability, a sample \(x\) from \(P^{A}_{v''}\) will be distance \(\Omega(1/\sqrt{m})\) from the support of \(P^{A}_v\). As the distance from a point \(x\) to the affine hyperplane \(\Lambda_h \triangleq \brc{z: \iprod{z,v} = h}\) is \(|\iprod{v,x} - h|\), if \(x\) is of the form \(h' v' + v^{\perp}\) for some \(h'\in\R\), then \(x\) is at distance \[\abs*{h' \iprod{v',v} + \iprod{v^{\perp},v} - h}\] from the hyperplane. Note that \(P^{A}_v\) is supported on the hyperplanes \(\Lambda_{h_1},\ldots,\Lambda_{h_{m-1}}\) for \(h_1,\ldots,h_{m-1}\) from Lemma 6. And for \(x\sim P^{A}_{v'}\), \(h'\) takes on the value \(h_i\) with probability \(\lambda_i\) (where \(\brc{\lambda_i}\) are also from Lemma 6), while \(v^{\perp}\) is an independent draw from \(\calN(0,\Id - v'{v'}^\perp)\). We conclude that \(h'\iprod{v',v} + \iprod{v^\perp,v}\) is distributed as \(\calN(h'\iprod{v',v}, 1 - \iprod{v',v}^2)\). Therefore, the event that \(x\) is at distance \(\Omega(1/\sqrt{m})\) from the support of \(P^{A}_v\) is equivalent to the event that a sample from \(\calN(h'\iprod{v',v}, 1 - \iprod{v',v}^2)\) is \(\Omega(1/\sqrt{m})\)-far from every \(h_1,\ldots,h_{m-1}\). But note that because \(h_1,\ldots,h_{m-1}\) are \(\Omega(1/\sqrt{m})\)-separated, there is an absolute constant \(c > 0\) such that the union of the balls of radius \(c/\sqrt{m}\) around \(h_1,\ldots,h_{m-1}\) cover at most a constant fraction of the interval \([h'\iprod{v',v}-1, h'\iprod{v',v}+1]\). Because \(1 - \iprod{v',v}^2\ge 3/4\), a constant fraction of the mass of \(\calN(h'\iprod{v',v}, 1 - \iprod{v',v}^2)\) is located in this interval, concluding the proof that \(W_1(P^{A}_v, P^{A}_{v'}) \ge \Omega(1/\sqrt{m})\).
By Lemma 19 and the fact that scaling by \(\sqrt{1 - \sigma^2}\) and convolving by \(\calN(0,\sigma^2)\) incurs \(O(\sigma) = o(1/\sqrt{m})\) in Wasserstein, we conclude that \(W_1(P^{D'}_v, P^{A}_{v}) = W_1(D',A) = o(1/\sqrt{m})\) and similarly for \(W_1(P^{D'}_{v'}, P^{A}_{v'})\). So by triangle inequality for Wasserstein, \(W_1(P^{D'}_v, P^{D'}_{v'} = \Omega(1/\sqrt{m})\) as claimed. ◻
We conclude that in Theorem 4, the distribution \(D\) also satisfies the Wasserstein analogue of Part 3, i.e. \(W_1(P^D_v, P^D_{v'}) \ge \Omega(1/\sqrt{m})\) for any \(v,v'\in\S^{d-1}\) satisfying \(|\iprod{v,v'}| \ge 1/2\). We can now prove an analogue of Theorem 3 for Wasserstein:
Theorem 5. Let \(d\in\mathbb{N}\) be sufficiently large. Any SQ algorithm which, given SQ access to an arbitrary one-hidden-layer ReLU network pushforward of \(\calN(0,\Id_d)\) of size \(O(\log d / \log\log d)\) with \(\poly(d)\)-bounded weights, outputs a distribution which is \(O(\sqrt{\log\log d / \log d})\)-close in \(\mathop{\mathrm{d_{\mathrm{TV}}}}(\cdot)\) must make at least \(d^{\Omega(\log d / \log\log d)}\) queries to either \(\mathrm{STAT}(\tau)\) or \(\mathrm{VSTAT}(1/\tau^2)\) for \(\tau = d^{-\Omega(\log d / \log\log d)}\).
Proof. By Theorem 4 applied with sufficiently large odd \(m\) and sufficiently small \(\sigma\), together with the above consequence of Lemma 20, there exists a distribution \(D = f^*(\calN(0,\Id_2))\) over \(\R\) for \(f^*:\R^2\to\R\) of size \(O(m)\) with \(m^{O(m)}\)-bounded weights satisfying the hypotheses of Lemma 4 for \(\epsilon = O(1/\sqrt{m})\), and \(\chi^2(D,\calN(0,1)) \le \exp(O(m))\) (note that while Lemma 4 is stated for \(\mathop{\mathrm{d_{\mathrm{TV}}}}(\cdot)\), it is also true with \(\mathop{\mathrm{d_{\mathrm{TV}}}}(\cdot)\) replaced with Wasserstein-1). As long as \(m \le d^{O(C)}\), we conclude that an SQ algorithm for learning any distribution from \(\brc{P^D_v}_{v\in\S^{d-1}}\) to Wasserstein-1 distance \(O(1/\sqrt{m})\) must make at least \(d^{m+1}\) queries to \(\mathrm{STAT}(\tau)\) or \(\mathrm{VSTAT}(1/\tau^2)\) for \(\tau \triangleq O(d)^{-(m+1)(1/4-C/2)}\cdot \exp(O(m))\). By taking \(m = \Theta(\log d/ \log\log d)\), we ensure that \(m^{O(m)} \le \poly(d)\). We’re done by taking \(C\) in Lemma 4 to be \(C = 1/4\). ◻
7 Hardness From Supervised Learning↩︎
In this section we make rigorous the claim from the introduction that lower bounds for PAC learning neural networks from Gaussian labeled examples imply lower bounds for learning neural network pushforwards. Formally, consider the following distinguishing problem:
Definition 7 (Distinguishing labeled examples from Gaussian). For \(d\in\mathbb{N}\), let \(\mathcal{C}_d\) be some class of functions from \(\R^d\) to \(\R\). The learner is given \(\poly(d)\) many samples \((x_1,y_1),\ldots,(x_N,y_N)\) where \(x_1,\ldots,x_N\) are independent draws from \(\calN(0,\Id_d)\) such that one of the following is true: 1) there is some \(h\in\mathcal{C}\) for which \(y_i = h(x_i)\) for all \(i\in[N]\), or 2) every \(y_i\) is an independent sample from \(\calN(0,1)\). We say that an algorithm distinguishes between these two situations with constant advantage if the probability it outputs \(\mathsf{YES}\) (resp. \(\mathsf{NO}\)) under the former (resp. latter) is at least \(2/3\), where the probability is with respect to the randomness of the samples and internal randomness of the algorithm.
Here we make the simple observation that an oracle for distinguishing any given family of non-Gaussian pushforwards from \(\calN(0,\Id)\) (an easier task than actually learning pushforwards) immediately implies an algorithm for the distinguishing task in Definition 7.
Lemma 21. For \(d\in\mathbb{N}\), let \(\mathcal{C}_d\) be any function class from \(\R^d\to\R\) for which the indexing functions \(f^{[j]}\), given by \(f^{[j]}(x) = x_j\) for some \(j\in[d]\), are elements of \(\mathcal{C}\). Suppose that for any \(d_1,d_2 = \poly(d)\), there is a \(\poly(d)\)-time algorithm \(\calA\) for the following task. Let \(d_1,d_2=\poly(d)\), and let \(\calS\) be a known set of functions \(f: \R^{d_1} \to \R^{d_2}\) whose output coordinates are all elements of \(\mathcal{C}_{d_1}\) and such that for any \(f\in\calS\), \(\mathop{\mathrm{d_{\mathrm{TV}}}}(f(\calN(0,\Id_{d_1})),\calN(0,\Id_{d_2})) \ge 1/2\). Then \(\calA\) can distinguish with constant advantage whether it is given \(\poly(d)\) samples from \(f(\calN(0,\Id_{d_1}))\) for some \(f\in\calS\) versus samples from \(\calN(0,\Id_{d_2})\).
Under this hypothesis, there is a \(\poly(d)\)-time algorithm that solves the distinguishing problem of Definition 7 to constant advantage.
Proof. Note that in situation 1) of Definition 7, the joint distribution over \((x,y)\) is given by the pushforward \(f(\calN(0,\Id))\) where \(f:\R^{d+1}\to\R^{d+1}\) is as follows: the first \(d\) output coordinates are given by the \(d\) indexing functions \(f^{[1]},\ldots,f^{[d]}\), and the last output coordinate is given by \(h\). By taking \(\calS\) in the hypothesis to consist of such \(f\), we can thus apply the algorithm \(\calA\) to distinguish between the two situations in Definition 7 to constant advantage. ◻
Note that the contrapositive of the above lemma implies that any lower bound for the task in Definition 7 immediately implies a lower bound for learning pushforwards. While the aforementioned lower bounds of [1], [2], which apply when \(\mathcal{C}_d\) is the family of neural networks with at least two hidden layers and polynomially bounded size and weights, do not show hardness for the task in Definition 7, note that hardness for this task immediately implies hardness for PAC learning \(\mathcal{C}_d\) from Gaussian examples. Indeed, given an algorithm \(\calA\) that, given \((x_1,h(x_1)),\ldots,(x_N,h(x_N))\), outputs a predictor \(\wh{h}\) for which \(\E[g]{(h(g) - \wh{h}(g))^2}\) is small, one can easily solve the task in Definition 7 by running \(\calA\) and estimating the square loss of the predictor from some fresh samples. In situation 2) of Definition 7, because the labels are random, no predictor can achieve low square loss. So the algorithm which outputs \(\mathsf{YES}\) if and only if the empirical square loss on fresh samples is small will distinguish between the two situations with constant advantage.
In other words, showing hardness of Definition 7 for \(\mathcal{C}_d\) would be a stronger result than what is already shown in [1], [2]. Putting this and Lemma 21 together, we conclude that even this stronger hardness result would only imply hardness for learning pushforwards given by \(f\) whose output coordinates are functions in \(\mathcal{C}_d\) given by neural networks with at least two hidden layers and polynomially bounded size and weights. In contrast, in the present work, we show hardness for one hidden layer, logarithmic size, and polynomially bounded weights.