Learning (Very) Simple Generative Models Is Hard
Authors: Sitan Chen
Jerry Li
Yuanzhi Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: generative models
statistical query
distribution learning
computational hardness
computational-statistical tradeoffs

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 $\textrm{poly}(d)$ neurons [Daniely-Vardi '21, Chen-Gollakota-Klivans-Meka '22].
    
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)$.

Learning (Very) Simple Generative Models Is Hard
Sitan Chen UC Berkeley si sitanc@berkeeey..oo edu
Jerry Li
Yuanzhi Li CMU yuanzhil@andres cmu edu
Microsoft Research jerr @mi wwwsoft.ooooooooooooooo com
Abstract
Motivated by the recent empirical successes of deep generative models, we study the computational complexity of the following unsupervised learning problem. For unknown neural network F Id Rdd let D be the distribution over IR" given by pushing the standard Gaussian N (0, Id,) through F. Given i.i.d. samples from D. the goal is output any distribution close D in statistical distance.
algorithm can solve this problem even when the output coordinates of F are one- see-hidddn-layye 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 [CGKM22, DV21J.
We show under the statistical query (SQ) model that no polynomial-ting
The key ingredient our proof is an ODE-based construction of compactly supported, piecewise-linear function with polynomially -bounddd slopes such that the pushforward of ((00, 1) under matches all low-degree moments of (00 1).
Introduction
In recent years, deep generative models such as variational autoencoders, generative adversarial net- works, and normalizing flows [GPAM+ 14, KW13, RM15] have seen incredible success in modeling real world data. These work by learning a parametric transformation (e-g. a neural network) of simple distribution, usually standard normal random variable, into 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.
beaming--heeortic
More formally. we consider the following problem. Let be the unknown pushforward distribution over Rd given by [g), where (O, 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 samples from D, and their goal to output the description of some distribution which is close to D.
When f is a one-layer network (i.e. of the form [g) ReLU(W g)), there are efficient algorithms for learning the distribution [WDS19, LLDD20]. 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 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, recent line of work suggests that learning neural network pushforwards of Gaussians may be an inherently difficult computational task. Recent results of [DV21, CGKM22] 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
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

detailed description of related work). These naturally imply hardness in the unsupervised setting (see supplement). 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 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 ~ (0, Id) and each output coordinate of f is one-hidden-layer neural network of logarithmic hidden size. We formally define the SQ model in Definition 2; we note that it is well-known to capture almost all popular learning algorithms [FGR* 17].
Theorem 1.1 (informal, see Theorem 3.1). For any d > O, and any C 2 1, there exists family of one-hidden-layer layer neural networks F from TR. to R. so that the following properties hold. For any F , let D denote the distribution of f(r g~ (O,Idd) Then, we have that:
For all f E F. (Tv(N D2) 221).)
Every outpul coordinate of f is sum of O(log d/ log log d) ReLUs, with (oly(d)-bounn) weights. Any SQ algorithum which can distinguish between D and N Id) with high probability for all f E FF requires d=(1) time and/or samples.
In other words, there is 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 recover the parameters of the network or output a network close to the underlying distribution Dy. but it is hard to learn any distribution close to Dy. In contrast, one ignores issues of computational efficiency, one can easily learn networks in this family with polynomial sample complexity via hypothesis selection, as there are only poly many parameters specifying any network this family.
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 very difficult task, at least without additional assumptions. Still. this is by means the last word in this direction. Given the real world success of deep generative models, a natural and important direction to identify natural conditions under which we can efficiently learn. We view our results as 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 [g) to be efficiently learnable, even very simple two-layer cases.
1.2
Our Techniques
Like many recent SQ lower bounds, ours follows the general framework which introduced in [DKS17] and builds on [FGR+17] 17]. Here one considers the following "non-Gaussian component analysis" task. We will consider family of distributions, parametrized by "hidden" direction v E gd which are Gaussian in every direction orthogonal to the hidden direction but which are very non-Gaussian along the hidden direction.
To formalize this, let D distribution D over R which is known to the learner and far in statistical distance from Gaussian. Given a unit vector in d dimensions, let P' denote the distribution over Rd 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 Rdd the goal is to
dry denotes total variation distance. A lower bound for Wasserstein distance also holds, see supplement.

---

decide whether the unknown distribution is (0, Ida) or P for some v. [DKSI7] showed that if D's moments match those of NV, 1) up to some degree m, then under mild conditions, any SQ algorithm for this task requires at least (m))) queries (Lemma 3.3).
Suppose one could exhibit a one-hidden-layer ReLU network f TR' + R such that the pushforward D D= D=N(N(0 Id)) satisfied such properties. Then we can realize Pe as pushforward as follows. Uet be rotation mapping the first standard basis vector in R to Then consider the function :: R + F mapping 2 to U (f (f.1....,2E)) 2t), 28+1...... 2(+d-1). One can check that every output coordinate of F' is computed by hrn--hddde-llyeer ReLU network with size essentially equal to that of f. By [DKS17], 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 (0, 1). is not hard to ensure the existence of such f with essentially infinite weights (Corollary 4.2 and Lemma 4.4). 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 hoverse-polynonee time scale, we obtain network with polynomially bounded weights whose pushforward matches the low-degree moments of (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 [GSW+21]), For conciseness we cover only the most relevant papers.
Upper bounds. In terms of upper bounds, much of the literature has focused on a different set- ting, where the goal is to understand when first order dynamics can learn toy generative mod- els [FFGT17, DISZ17, GHP+ 19, LLDD20, AZL21, JMGL22], 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 19 LLDD20]. This is in contrast to the supervised setting, where fixed parameter tractable algorithms are known for learning ReLU networks of arbitrary depth [CKM22].
A different line of work seeks to find efficient learning algorithms when the activations are given by low degree polynomials [FFGT17, LD20, CLLZ22]. Arguably the closest to our work is [CLLZ22), which gives polynomial-ting -itom algorithms for learning low-degree polynomial transformations of Gaus- sians, 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 unclear how their techniques can generalize to different activations.
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, fx)). and the goal is to output a good predictor. There are many lower bounds known in the distribution-fre free setting [BR92, Vu98, KS09, LSSS14 14, DV20], however, these do not transfer over to our (unsupervised) setting. When is Gaussian, the aforementioned work of [CGKM22] derives hardness for learning wwo-hidden-laye networks with polynomial size for all SQ algorithms,
well as under cryptographic assumptions (see also [DV21]) It is not hard to show (see supplement) that this lower bound immediately implies lower bound for the unsupervised problem. In the supervised setting, lower bounds are also known against restricted families of SQ [VW19. 19, GGJ CGJ+20, DKKZ20, SVWXI7J, when there are adversarially noisy labels [KK14, DKZ20, GGK20, SZB21], and in discrete settings [Va184, Kha95, AK95, Fe109, CGV15, DGKP20, AAK21J, 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 [DV21, CGKM221, we also mention the recent work of [CLLM22] 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 given by a Lipschitz ReLUU network discriminator. However, this does not rule out efficient algorithms which do not output such Lipschitz discriminators.
3

---

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 [DKS17]. This and slight modifications thereof are mixtures of Gaussians which are known to be computationally hard both in the SQ model [DKS17, 19] and under cryptographic assumptions [BRST21, GVV22J.
SQ lower bounds via ODEs. We remark that in a very different context, [DKZ20] also used an ODE to design a momentt-mtchiinn construction. While our approach draws inspiration from theirs, an important difference is that they use their ODE as a "size reduction" trick to construct step function f: RR- + {+1} with a small number of linear pieces such that Eg (yff(())) = 0 for all small k. while we use our ODE as a "weight reduction" trick to construct continuous neural network = (o [g*]. The form of the moments (0,,)((,1)) Eo 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 4.8).
f: R- + R with bounded weights such that (o)
2 Technical Preliminaries
We freely abuse notation and use the same symbols to denote probability distributions, their laws, and their density functions. Given a distribution A over domain Ω and function f : 52 - Ω2, we let (AA denote the pushforward of A through f. that is, the distribution A' of the random variable f(z) for z ~ A. Given distributions p, q for which p is absolutely continuous with respect to q, let x (p. q) denote their chi-squared divergence. Let p * denote the convolution of and q. Also, we use I| to denote e" norm, omitting the subscript when p = 2. o miin (-) denotes minimum singular value. Given an invertible matrix M, we use M to denote the matrix (M [M-)-- (M-) (MT
Henceforth EyH- will always denote Eg [-], where the dimensionality is implicit from context. Let a (3) A - =2=00) Given S C R. we use (S) denote _ (x)) 1 [ar E S] dr. ov2n
When 1, we omit the subscript o². We will also use (()) (xr) denote the density of (0, Id,).
Definition 1 sine-hideen-lyer ReLU networks). We say that g IR + R is a one- one-hidden-layer ReLU network with size S and W -ooudddddd weights if there exist ...,..., Wy E Rd. b1..... bs E R. and $1,...,88 85 E 1 for which g(x) = E' 8t ReLU (eLU(((;;at) x) + by) and [|w:]], [b: S W for all i e S.² Here (z) & max(0, 2). Given f aRd + Rd,, together with a distribution A over IR we say that f(A) is lae-hidden-layer ReLU network pushforward of A with size S and W W-bounded weights if each coordinate of f is of this form.
Fact 2.1 ([GMSR20D) V E Raxx is a Vandermonde matrix with nodes 21,...,, Zn. that is, Vi, = =j i-1 .andd {zi} are (-separated, then mmin 2 1 ()())=11
Theorem 2.2 (Peano's 's existence theorem, see e.g. Theorem 2.1 from [Har02]). For T,r > 0 and Uo E TR. les B C x The be the parallelepiped consisting of (1, y) for which 0 < S T and bl Ily vollss Sr. If f B > R is continuous and satisfies (f(t, u)1 S M for all (t,y) E B, then the initial value problem (v'(t) = ft., y) and y(0) = 3oo has a solution over t E [0. (immm.TT///M
Definition 2 (Statistical queries). Given distribution D over Rd and parameters T, t > 0, STAT(T) oracle lakes in any query of the form f Rad + [-1,1] and outputs value from [E p [ [xx)
t, E. (xx)] + r]. while a VSTAT(t) oracle takes in any query of the form f : Rd + [0, 1] and
outputs a value from (f - t, Bf + r) for T = max(1/tt (V
3 Statistical Query Lower Bound
Our main result is the following lower bound in this model for learning ReLU network pushforwards:
Theorem 3.1. Let d E N be sufficiently large. Any SQ algorithm which, given SQ access to an arbitrary one-hidden-layer ReLU network pushforward of A ( Ida) of size O(log d/ log log d) with poly(d)-bounded bouuned weights, outputs a distribution which is O(1)-close in dry (-) must make at least (loggd] d/ log d) queries to either STAT(T) or VSTAT f = d d- d/ log log.)
In practice think of S as the number of channels, e.g. in a deconvolution network.
4

---

Our proof will invoke the following key technical result whose proof we defer to Section 4. It exhibits a ane-hidden-laye ReLU network f R² + R with bounded weights under which the pushforward of (0, 1) matches the low low-degree moments of (0, 1) to arbitrary precision, in addition to some other technical conditions that we need to formally establish our statistical query lower bound: Theorem 3.2. Fix any odd m and V. a < 1. There is a one me-hidden-laye ReLU network f IR² - R of size (m) with weights at most m ((m) for which the pushforward D 2 (* Id)) satisfies
1. (E>DD=*) - Bgg-v(o. < v for all k- = m.....m
(D,, 1)) S exp(O(m))/o
3. drv(P?, PD) 2 1 - 20 log(1/o) - m Q(m) for any v, o' E gd-1 satisfying (u,,')) 2 1/2.
The rest of the proof of our lower bound will then follow the framework introduced in [DKS17] and subsequently generalized in [DK20]. First, given distribution 1) over IR. and E 36-1, let PP x)) (d(d11((
denote the distribution over gd with density (x)()) distribution which is given by D in the direction and is given by (o Id - vo ") orthogonal to v. We use the following generic statistical query lower bound about learning such distributions, a proof of which we include in the supplement for completeness.
(v, z)v), that is the
Lemma 3.3. Let E N and 0 < C < 1/2. Let D be a distribution such that 1) (D,,NN 1)) finite, and 2) [E>DD[** Eg~ < ((d) ((d))(m/-(//A-C13) (D,,NN for all k == =..,.., m.
Consider the set of distributions (PP) vegg 1 for d 2 m(10C) If there is some > 0 for which dP PP)) > 2c whenever (u,,")] I 1/2, then any SQ algorithm which, given SQ access to P. for an unknown E Sd-1, outputs a hypothesis Q with (r, S e needs at least d queries to STAT(T) or VSTAT(L/7²) f 2 O(d) (mm+) (m+1/(/4--//)) (X²(D.NNO,,)),
Proof of Theorem 3.1. By Theorem 3.2 applied with sufficiently large odd m and sufficiently small a, there exists distribution D f (0, Id2)) over I for f* R² - R of size ((m) with m ((m) bounded weights satisfying the hypotheses of Lemma 3.3 for = 0.49, and x (D,NN 1)) < (m)( (note that we can absorb the 1/a factor in Theorem 3.2 into exp(O(m)) because we I dC()), we conclude that SQ algorithm for
take cxp(--(m))) As long learning any distribution from {PP) Juggu-1 to total variation distance 1/4 must make at least d= queries to STAT((T) or VSTAT(L/7²) for 5 & O(d) (md))(m+))(044-- C/2) exp(O(m)). By taking m (log d/ log log d), we ensure that m ((m) < (d)y We're done by taking C in Lemma 3.3 to be C 1/4.
The proof of the theorem is complete upon noting that any distribution P.P can be implemented as a pushforward of N0, Idz+1) under -lye ReLUU network F, : [Rd+1 - R&d of size Ollog d/ log log d) with poly (d) -boundddd weights. Let U E O(d) be rotation mapping the first standard basis vector in IR to Then for have that (O, Id)-1)) ) = P.P as desired. Furthermore, note that every output coordinate of (1, is one- one-hidden-layer ReLU network of the form a (21, ( 22) + (u, (24+)).))44))
zd+1) U(f 22), Z3...., Ed41) we
for some vector (a. E IRd 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, 's output coordinates are of size Ollog d/ log log d). O Remark 3.4. Theorem 1.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 dlog d/ log log lower bound still applies.
4 Moment-Matching Construction
In this section we prove Theorem 3.2, the main technical ingredient in the proof of Theorem 3.1.
4.1 Moment-Matching With Unbounded Weights
We begin by making the simple observation that for one-hidden-layer networks with unhounded weights, it is easy to construct networks such that the pushforward of / (/(0, 1) under these networks
5

---

matches the moments of (0, 1). The starting point for this is the following standard construction. Roughly speaking. it gives a set of well-separated points on the real line and a distribution over them which matches low-order moments with (0,, 1).
Lemma 4.1 (Lemma 4.3 from [DKS17]). For any m N, there exist weights A1,..., ......,,. Z 0 and points Am E R. for which
1. (Moments match) Ees A = Eglgg1 1 for all lo O,..., 2m (note that the special case of
k O implies D Xi 0).
2. (Points symmetric about origin) h1 S... S hm and h; = - -mm it1 for all 1 isiS m.
3. (Weights symmetric) A S ...
S (m/227 and X; = Am-itt-
4. (Points bounded and separated) (L1/mm) S 1h1 S Olym) all 1 S S m and { are
Q11/ ( seeprrttd.
(Weights not too small) min; 2 e- for an absolute constant e. > 0.
6. (Central point and weight) If is odd, then h/m+11//2 = 0 and Amm+1//2 (1/
This immediately implies that there exists a discontinuous piecewise linear function f R R for which the pushforward (ON 1)) matches the low-degree moments of (O 1). The reason is that we can take / to be a step function which takes on values given by the positions of the points hi..... hm in Lemma 4.1. We can then take the steps to have lengths such that the probability that standard Gaussian input to f falls under the step given by some h; is precisely X (see Figure I).
Corollary 4.2. For any m E N, there is partition of R into disjoint intervals I,,..., Lm, along with a choice of sealars hi...., hm. such that the step function f R + given by f(z) =
E h; [[ I;] satisfies (os=)(((0.1)) = Egg=N((.1)) [g*]] ] for all l = 0...., 2m
Proof. Let {1.}, {h, be as in Lemma 4.1. As E, A 1, there are intervals E 11 U. L Lm for which ((,)) = >, As Ez= [2=] E, X the claim follows by Part of Lemma 4.1. O
By infinitesimally perturbing f in Corollary 4.2, we can ensure ((N 1)) still approximately matches the low-degree moments of (O, 1) to arbitrary precision and that the linear pieces of f have finite slopes, though some slopes will be arbitrarily large. The new function can thus be represented as one-hidden-layee ReLU network, but unfortunately its weights will be arbitrarily large. The key challenge in the sequel is to design better perturbation so the resulting f has polynomially bounded slopes yet is such that (WV 1)) matches the low-degres moments of A( 1).
4.2 Bump Construction
Before we describe our perturbation scheme, we slightly modify the construction in Corollary 4.2. In place of step function, we will consider certain sum of bump functions, illustrated in Figure 2. Definition (Bump functions). Given w, e > 0 and h, c E I,, define T M,e R - RR by
+ 4 w) (2
if = E [c if z E (c w. w. w|
w.c w)
Tuuske (2)
if = E (c wi w otherwise.
Because these are piecewise linear functions, we can implement them as one-hidden-layer ReLU networks:
Fact 4.3. Given w.e > and h e E R, Thws can be implemented as a one-hidden-layer ReLU network with size and W -bounded weights for W < lt max (1, , |c] + e w).
In the next lemma, we show that we can replace the construction in Corollary 4.2, given by step function, with sum of well-separated bumps with infnitesimally small e parameter. This will be the instance on which we will apply our perturbation scheme.
there are centers e1 S ..... Cm-1, widths wi.... Wm-- > O, heights h < ... < hm-1 E R, and parameter ē > 0 for which the following holds. Define the 1 Tw..b.. (2) (2) for any 0 S e E. Then f satisfies function f E.- + IR (see Figure 1) by f(2) & Em=1 Te
Lemma 4.4. For any odd m and

---

Figure Left: construction from Lemma 4.1 gives rise to step function Corollary 4.2. Right: removing central spike gives rise to sum of bumps in Lemma 4.4
(Bumps are well-separated) For all S m q + m m3/2 S Ci+1.
(Moments match) ((=, - || v for all 1,... 2m 1.
3. (Symmetricity) w; Wm-b h4 -hm-m and Cm-i for all < < m.
4. (Bounded, separated heights) 11(1//m) |h,1 0lym) for all S i m, and {hi}
Q/1/ seppparaee
(Intervals not too thin) min, r(le - Wi, cs + w.l) 2 e em for an absolute constant c
(Bounded endpoints) |cal + w; 5 O(log m) for all 1 S m.
Proof sketch, see supplement. The idea is that when m is odd, one of the points h, from Lemma 4.1 zero and does not contribute to the moments. We want to design for which f(N(0, 1)) is the mixture of point masses given by removing this point and its corresponding weight. We take f to have one linear piece for every one of the remaining point masses. By Part 6 of Lemma 4.1, these points have total weight 1 - (1/ mm). so by anticoncentration we can arrange these linear pieces to be m 3/2 -epaaraae satisfying Part 1. The remaining parts follow easily from Lemma 4.1. C
Unfortunately the slopes in the function constructed in Lemma 4.4 arbitrarily large if is arbitrarily small. The issue still remains of how to get a continuous piecewise-lineat function whose slopes are polynomially bounded that the corresponding ReLU network has polynomially bounded weights. As illustrate next however, the ((m-3/2) spacing between the bumps in the definition of f in Lemma 4.4 gives us sufficient "room" to carefully perturb f to achieve this goal.
4.2.1 Some Estimates for Bump Moments
For convenience, define M e R. [Trr We conclude this subsection by collecting some useful bounds for this quantity. As we verify the supplement, M. continuously differentiable c,k with respect to when Additionally, we have the following (see supplement):
Lemma 4.5. S......
= M.r.
Lemma 4.6. any w 2 G, R. 2 c 2 0, and even E N, we have the bound MM - -M < h (1(h/h)* 11 + e). In particular, this implies that
OM h.t
< h/.
Ut
4.3 ODE-Driven Perturbation
Denote the parameters of the function constructed in Lemma 4.4 by {(hx(0), Way (z) (a)) isicmm We also define (0) to be some arbitrarily small positive quantity satisfying <00) S for ē from Lemma 4.4.
We will design an ODE whose solution specifies one-parameter family of functions
ft h.
(I)
that arise from gradually perturbing the function from Lemma 4.4. Roughly speaking, starting at (0) and (0) for all < < m, perturbing function along this one-parameter family will correspond to keeping the widths and centers e; of the bumps fixed, increasing the parameter of every bump at unit speed, and evolving the heights (t) in such way that the moments of the pushforward of (0 1) under fo remain constant in for all 0 < t < T. We illustrate this evolution
7

---

in Figure 2. Here T is some horizon which is at least inverse- inverse-polynomine polynomially large but smaller than m -3/2 so that the "edges" C = (e(t) + w.) of the bumps don't collide with each other (this is where we make crucial use of Part of Lemma 4.4). At the end of this horizon, we want show that the heights will not have changed too much, whereas the bumps now have parameter given by inlynse-polynomially large T. This will imply that fr has polynomially bounded slopes as desired.
A(O)
M())
h(T)
<(
<07)
Figure 2: Evolution of one of the m 1 bumps constituting ft
As the odd moments of fo 1)) vanish and the parameters (O,, W;, hs)ss satisfy the symmetry properties from Part 3 of Lemma 4.4, it is easy to ensure that the odd moments of (O, 1)) also vanish: simply take ht(t) - --m-mm for all s i m 1.
We thus focus on evolving (t), ................................ hmm (1)-)))((t)). For convenience denote this by h(t). Define the moment vector μ 12(m-1//2 R + Rm-1 by
(m-1)/2
mh E) -
M 2
1)/5(m-1)/2
For any fixed (h, c) in a small neighborhood of (h(0), c(0)), we want to show there is a direction E (m/1222 such that the directional derivative of μ in the direction ف (V1,... ((m-1)/2; 1) is zero. The constraint that the directional derivative Ww c) vanishes specifies linear system in
(m-11)/2
aM c,22
[i (m-1)/2 OMMishee
Σ
14
Σ
0,,2
vISES (m - 1)/2.
De
Recalling Lemma 4.5, we can rewrite this as
(m
(m-11)/2
(m (m-11//2
28
Σ
U ha
vises (m 1)/2.
dc
To express this more compactly, define b(e) E (m and E(h,)) by
(m (m-1)/2
1)/2
aM hii
b(e), a
Σ
and 7(h,c)ie o,,2
Mwikeee
(3)
dc
1=1
Also define the matrices A(h) A diag(1 (ogg(1//1....... 1//m 11/2) and A diag(2, 4,..., m - 1). Then (2) is equivalent to oT A(hh) B)B = b(c) Provided A(h)Z(h, c) is invertible, the natural choice for v would thus be v = B 30h (hh))--A------ b((). Therefore, defining
w(1, h) A B B Z(h, (0) + Ahh)-AAh11 (b(e)(() + 1),1),
(4)
we consider the following initial value problem
ht(t) = wtt htt)
and
h(0) =
h (mm (0))
(5)
Note that if we had solution htt) to (5) for
[0, T] for some horizon T. then we would have
a कe (b(()),t) = o5 (b((), -h'(t) = (n()) t) = o,
a
(6)
implying that the low-degree moments of f. defined in (1) are constant in as desired.

---

4.4 Existence and Boundedness of h(t)
To carry out the strategy in Section 4.3, we must establish that (1) a solution to the initial value problem (5) exists over a non-negligible horizon T, and (2) the entries of h(t) do not explode in t.
For both of these, need to show that the matrix Z(h, is invertible or, more specifically, well- conditioned for (h, c) in a neighborhood of (h(0), (0)). We first establish this at time t = 0 by relating (h()),, (0)) to a certain Vandermonde matrix and appealing to Fact 2.1, see supplement: Lemma 4.7. amin (bh( ((0)) 2 m -C- for an absolute constant > 0.
Thus, for (h, <) in a neighborhood of (b(0), c(0)), (h, e) is well-conditioned (see supplement). Lemma 4.8. Let C be from Lemma 4.7. For any (b,,) c) satisfying ||h h( |< S m 3--C" Cm' and 0 S c c- c(0) S m C'm c'm for sufficiently large absolute constant C' > 0, Tmin (Z (h, c)) 2 m Co /2.
To establish Property (1), we must first verify that wit, h) is continuous (see supplement for proof):
Lemma 4.9. Ler C' > O be the absolute constant from Lemma 4.8. Then the function w(t. h) defined in (4) is continuous with respect to both t and h for t S m -C'm C'm and || h(0)llo S m C'm
Lastly, we must show that under the hypotheses of Lemma 4.9, ||w(t, h)ll is not too large. This implies Property (1) by Theorem 2.2 and Property (2) because [[h'(t) (t)ll = ||w[(t, h(t))
Lemma 4.10. Let C' > 0 be the absolute constant from Lemmna 4.8. If S m C'm m and l| h(0)]l I m -m,,, then [|w[t, h)lloc I m c for some absolute constant C" > 0.
Proof. By the second part of Lemma 4.6, every entry of b(e(0)+(() is at most " (max; h:)m < m-1 (0((m)) (m)+m= + -mmmm-1= I m m(m), where in the penultimate step we used Part of Lemma 4.4 and our hypothesis on h. Note that Gmin (2,, <(0) - +)) 2 m -Cm/2 by Lemma 4.8, Tmin (B) 2 2. and miin (A(h)) 2 min, 1/h, 22 by Part 4 of Lemma 4.4 and our hypothesis on h. We conclude that B- 1 Z (h, <00 + +t) A(h) b(e(O) + 6) has Loo norm most m C.C for some absolute constant C" > 0, so [| h)ll S c" as claimed.
We are now ready to put these ingredients together to prove the key lemma for showing Theorem 3.2: Lemma 4.11. Fix any odd m E NN and any 0 < V < 1. There is one-hidden-layer ReLU network f: > IR of size (m)) with weights at most m (m)) for which the pushforward = (ON 1))
satisfies E [x*] Eg-NNo,,))
v for all k = I...., m.
Proof. Define the parallelepiped B of pairs (t, h) for which 0 S m C'm and |h h())l < m C'm_ By Lemma 4.9, w is continuous over B. By Lemma 4.10, ||w b)lloo S m cm.mm
By Theorem 2.2, the initial value problem in (5) has solution h(t) over E [0, for T m (m Furthermore, because |lh (1)lo) ||vo(t, (())) S mmmmm conclude that F [[[(TT)) 5 <m m The slopes of the bumps T2. (T))) (T are therefore bounded by m."".
For (m - 1)/2 < i S m 1, define (T) = (T)) and consider the one-parameter family of functions f. A Σm 1 Te.: (())) Because G; = Cm-; and w: = Wm-i for all S < m by Part 3 of Lemma 4.4, we conclude that the odd moments of fx (N,, 1)) all vanish. As for the even moments, because 0 (((()))))) ()= = 0 by (6), we conclude that the even moments of (T 1)) up to degree m - 1 agree with those of (N 1)). So because Do = (o, 1)) satisfies [r<DD=* Eg-wo,. <
Dz
for S S m by Part 2 of Lemma 4.4, the same holds for fr-
As the endpoints of the intervals supporting the bumps are bounded by Ologmm), Fact 4.3 implies fr is one-hidden-layer network with size ((m) and m (o.0m(m)buudde weights.
4.5 Proof of Theorem 3.2
Having designed pushforward given by
network with satisfying the first part of Theorem 3.2, we now modify this to also satisfy the remaining two parts.
weights
To do this, we convolve suitable scaling of the pushforward by thin Gaussian. The following lemmas show that the moments continue to match, the chi-squared divergence between the result and (O, 1) is bounded, and the third part of Theorem 3.2 is satisfied (see supplement for proof):

---

Lemma 4.12. Let D be any symmetric distribution for which BE~ -Eglg"] < for all 1 I l m. For any E R let D denote the distribution obtained by rescaling D by factor of c. Then D' A o2 NO, o²) satisfies E [x*] ] Eg Ig < v for all
m.
Lemma 4.13. For any density A on [ R. R. and S 1/2, (A N 0² ") ), 1)) cO(R) /0. Lemma 4.14. Let D (O, 1)) be from Lemma 4,11, and define D' _ -1-o2 D 20(00 Then for any v, of E gd-1 satisfying (x,,')) & 1/2, drv(PP), PP') 2 1- - -2 log(1/o) m 9(())
Proof of Theorem 3.2. Let f be the function constructed in Lemma 4.11 and define f=; + I
by (2(1122) 22) = vI- of f(21) 022. Note that (", Id)) is exactly vI- vI-o"f(Nii f(N 1))
((0, o so the three parts of Theorem 3.2 follow immediately from Lemmas 4.12, 4.13, and 4.14 respectively.
Conclusion. this work we established that learning one-hidden-layer ReLU network pushfor- wards of logarithmic size is hard for efficient SQ algorithms. Given that SQ algorithms capture large family of efficient algorithms, this suggests that this basic learning problem, despite its simple description, is computationally intractable. Of course, our lower bound construction is worst case, and so it is unlikely to actually arise in practice. A natural open question, as mentioned previously, is come up with natural assumptions (for instance, smoothed analysis settings like in [CLLZ22]) that allow us to circumvent this lower bound, and to achieve efficient learning algorithms.
References
[AAK2I] Naman Agarwal, Pranjal Awasthi, and Satyen Kale. A deep conditioning treatment of neural networks. In Algorithmic Learning Theory, pages 249-305. PMLR, 2021.
[AK95] Dana Angluin and Michael Kharitonov. When woní membership queries help? Journal of Computer and System Sciences, 50(2):336-355, 1995.
[AZL.21] Zeyuan Allen-Zhu and Yuanzhi Li. Forward super-resolution: How can gans learn hierarchical generative models for real-world distributions. arXiv preprint arXiv:2106.02619, 2021.
[BLPR19] Sébastien Bubeck, Yin Tat Lec, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning. pages 831-840. PMLR, 2019.
[BR92] Avrim I. Blum and Ronald I. Rivest. Training 3-node neural network is np-complete. Neural Networks, 5(1):1 1992.
[BRST21] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous Iwe. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 694-707, 2021.
[CGKM22] Sitan Chen, Aravind Gollakota, Adam R Klivans, and Raghu Meka. Hardness of noise- free learning for two-hidden-layer neural networks. arXiv preprint 220hv:220..05258. 2022.
[CGV15] Aloni Cohen, Shafi Goldwasser, and Vinod Vaikuntanathan. Aggregate pseudorandom functions and connections learning. In Theory of Cryptography Conference, pages 61-89. Springer, 2015.
[CKM22] Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed-parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. IEEE, 2022.
[CLLM22] Sitan Chen, Jerry Li, Yuanzhi Li, and Raghu Meka. Minimax optimality (probably) doesn't imply distribution learning for gans. arXiv preprint arXiv:2201.07206, 2022.
[CL..722] Sitan Chen, Jerry Li, Yuanzhi Li, and Anru R Zhang. Learning polynomial transforma- tions. arXiv preprint arXiv:2204.04220 2022.
10

---

[DGKP20] Abhimanyu Das, Sreenivas Gollapudi, Ravi Kumar, and Rina Panigrahy. On the learnability of random deep networks. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 398-410. SIAM, 2020.
[DIZZ17] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint urXiv: (..0::1711..0111,, 2017.
[DK20] Ilias Diakonikolas and Daniel M Kane. Hardness of learning halfspaces with massart noise. arXiv preprint arXiv:2012.09720. 2020.
[DKK720] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning me-hidden-layer relu networks. In Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[DKS17] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of -igh-dimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-84. IEEE, 2017.
[DKZ20] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal sq lower bounds for agnostically learning halfspaces and relus under gaussian marginals. Advances in Neural Information Processing Systems, 33:13588 13586-13596, 2020.
[DV20] Amit Daniely and Gal Vardi. Hardness of learning neural networks with natural weights. Advances in Neural Information Processing Systems, 33:930-940, 2020.
[DV2]] Amit Daniely and Gal Vardi. From local pseudorandom generators to hardness of learning. In Conference Learning Theory, pages 1358-1394, PMLR, 2021.
[Fel09] Vitaly Feldman. On the power of membership queries in agnostic learning. The Journal of Machine Learning Research, 10:163-182, 2009.
[FFGT17] Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans: the lqg setting. arXiv preprint arXiv: 10793, 2017.
[7GR+17] Vitaly Feldman, Blena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1-37, 2017.
[GGJ+20] Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.
[GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147- 2158, 2020.
[GHP+19] 19] Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and loannis Mitliagkas. Negative momen- tum for improved game dynamics. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1802-1811. 1. PMLR, 2019.
[GMSR20] Spencer Gordon, Bijan Mazaheri, Leonard J Schulman, and Yuval Rabani. The sparse hausdorff moment problem, with application topic models. arXiv preprint arXiv:2007.08101, 2020.
[GPAM+ 14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[GSW+21] Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye. A review on gen- erative adversarial networks: Algorithms, theory, and applications. IEEE Transactions on Knowledge and Data Engineering, 2021.

---

[GVV22] Apama Gupte, Neckon Vafa, and Vinod Vaikuntanathan. Continuous Iwe is as hard as Iwe & applications learning gaussian mixtures. arXiv preprint arXiv:2204.02550 2022.
[Har02] Philip Hartman. Ordinary differential equations. SIAM, 2002.
[JMGL22] Samy Jelassi, Arthur Mensch, Gauthier Gidel, and Yuanzhi Li. Adam is better than normalized SGD: Dissecting how adaptivity improves GAN performance, 2022.
[Kha95] Michael Kharitonov. Cryptographic lower bounds for learnbiliity of boolean functions on the uniform distribution. Journal of Computer and System Sciences, 50(3):600-610, 1995.
[KK14] Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space. Approximation, Randomization, and Combinatorial Optimizationn Algorithums and Techniques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibbni-7Znnnn fuer Informatik, 2014.
[KS09] Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12, 2009.
[KW13] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 13Xiv: 14, 2013.
[LD20] Yuanzhi Li and Zehao Dou. Making method of moments great again? seain?-howw can gans learn distributions. arXiv preprint arXiv:2003. 044033, 2020.
[LLDD20] Qi Lei, Jason Lee, Alex Dimakis, and Constantinos Daskalakis. SGD learns one- layer networks in wgans. In International Conference on Machine Learning, pages 5799-5808. PMLR, 2020.
[LSSS14] Roi Livni, Shai Shalev-Shwarts and Ohad Shamir. On the computational efficiency of training neural networks. Advances in neural information processing systems, 27, 2014.
[RM15] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference on machine learning, pages 1530-1538, PMLR, 2015.
[SVWX17] Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. Advances neural information processing systems, 30, 2017.
[SZB21] Min Jae Song, Ilias Zadik, and Joan Bruna, On the cryptographic hardness of learning single periodic neurons. Advances in Neural Information Processing Systems, 34, 2021.
[Va184] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134- 1142, 1984.
[Vu98] Van Vu. On the infeasibility of training neural networks with small mean-squared eтror. IEEE Transactions on Information Theory, 44(7):2822-2900, 1998.
[VW19] Santosh Vempala and John Wilmes. Gradient descent for one-hidden neural networks: Polynomial convergence and sq lower bounds. In Conference on Learning Theory, pages 3113-3117. PMLR, 2019.
[WDS19] Shanshan Wu, Alexandros G Dimakis, and Sujay Sanghavi. Learning distributions generated by one-layer relu networks. Advances in neural information processing systems, 32, 2019.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See end of Section 1.1.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are present
in either the main body or the forthcoming supplement.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "jNfgWUREXiN", "reviewer": "Reviewer_wYoe", "summary": "The paper is concerned with the computational complexity of learning distributions $f(\\mathcal{N}(0, \\mathrm{Id}))$ in TV distance where $f$ is an unknown feed forward neural network with ReLU activations. What we already know about this problem: 1) When the network has 0 hidden layers, this can be efficiently solved; 2) Previous lower bounds show SQ lower bounds for 2 hidden layers and polynomially many hidden units. This paper improves on these lower bounds to show a SQ lower bound with 1 hidden layer and logarithmic number of hidden units.\n\nTheir proof technique follows now standard ideas introduced in DKS17. To show this SQ lower bound, it sufficies to show that there exists feed forward networks such that the pushforward distribution $f(\\mathcal{N}(0, \\mathrm{Id}))$ is an arbitrary distribution D in a direction v and standard Gaussian in all directions orthogonal to v. This is enough because DKS17 showed that if D’s moments match those of $\\mathcal{N}(0, 1)$ up to some degree $m$, then any SQ algorithm for this task requires at least $d^{m}$ queries. \n\nThe goal therefore is thus to construct a network whose pushforward matches the low-degree moments of $\\mathcal{N}(0, 1)$. Note that if we were not concerned with the norm of the weights used in the construction, this essentially follows from DKS17. They showed that there exists $m$ weights $\\lambda_i$ and $m$ points $h_i$ such that $\\sum \\lambda_i h_i$ matches the first $2m$ moments of $\\mathcal{N}(0, 1)$. We can partition the real line into intervals $I_i$ such that measure of $I_i$ is exactly the weight $\\lambda_i$. And therefore, the step function $f(z) = \\sum h_i . \\mathbb{1}[z \\in I_i]$ matches the first $2m$ moments of $\\mathcal{N}(0, 1)$, which can be simulated by feedforward network with unbounded weights.\n\nTherefore, the main challenge here is to simulating this distribution approximately with bounded weights. There are two main ideas for achieving this. Firstly,  instead of the step function, which do not have any gaps between the different jumps, we need to construct functions with gaps (of order $m^{-3/2}$) between their jumps (called bumps) so that the slope of these edges can be made small. This is illustrated in Figure 1 and proven in Lemma 4.4 (inspired by DKS17). \n\nSecondly, they need to show that the gap above is enough to decrease the slope. This is achieved by considering an ODE relating the moments $M(t)$ to the height $h(t)$ and slant parameter $\\epsilon(t)$. To ensure the moments do not change, they evolve $h(t)$ and $\\epsilon(t)$ in the direction with $0$ gradient (which keeps the moment constant). Both existence and bounded $h(t)$ follows from analysis the solutions of the ODE (and showing that certain matrix in the analysis is well conditioned).", "questions": "Other than the small typos above, I do not have any other questions.", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is written very nicely. It was easy to follow even though there is a lot of technical detail. I thank the authors for the effort they spent on this. Few (subjective) comments on the writing however:\n1. Line 76: \"Let D be a known, non-Gaussian distribution D over R.\" This does not read well.\n2. Lemma 4.1 does not mention sum lambda =1 but Corollary 4.2 uses this.\n3. Before 298-308, it will be helpful to briefly discuss the goal of this analysis. Maybe something like this: \"we would like to choose h(t), eps(t) such that the the low-degree moments of ft defined in (1) are constant in t as desired. We now discuss how to choose such h(t) and eps(t).\"\n4. It will be useful to clarify in the terminology section that $A^{-\\top} = (A^{\\top})^{-1}$.\n\nUnderstanding the computational complexity of learning distributions is an important problem. Without any assumptions, most of the learning problems are hard and therefore the constant struggle is to design assumptions which allow us to evade the hard instances and identify the easy instances. The hardness result from this work shows that we might need more assumptions (like smoothed analysis) for efficient learning.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_8SV8iWNVi_", "reviewer": "Reviewer_nCQE", "summary": "The authors consider the problem of learning a one hidden-layer generative model. A one hidden-layer generative model is a neural network with a hidden layer, ReLU activations, then an output layer that takes as input a sample of a standard Gaussian. The goal is to typically learn the parameters, though it also may be to describe the distribution in other ways.\n\nThe authors consider the statistical query (SQ) framework. Here an algorithm is allowed to make \"statistical queries,\" which are specified by a function f and return a good estimate of the value E_x[f(x)]. It is often possible to establish unconditional lower bounds in the SQ framework. The SQ framework doesn't directly imply hardness in other senses, though many standard learning algorithms can be adapted to the SQ framework. Thus hardness in this framework at the very least implies that a large class of algorithms can't be used for this problem.\n\nThe authors are able to establish that the problem of learning a one hidden-layer generative model is hard in the SQ framework. They start by using a known lower bound by [DKS17] that shows hardness of learning an n-dimensional distribution that is (1) a product distribution in the right basis and (2) the first coordinate in this basis has many moments that match a standard Gaussian and the remaining coordinates are standard Gaussians. The authors are able to construct a family of one hidden-layer generative models that match this description, which implied hardness of learning in the SQ framework.\n\nThe authors approach to creating the network is by perturbing an initial solution that may have a description size that is too large. This is described by a differential equation, which they show has a well defined solution.", "questions": "Are there any known information-theoretic bounds that show that there exist algorithms that use polynomial samples (but potentially exponential time) for solving this problem?\n\nHow important is the use of ReLU activations for the result? Is it straightforward to generalize to other activations?\n\n", "limitations": "The authors mentioned that hardness in the SQ framework does not exactly capture other notions of hardness and only (1) shows that a class of algorithms would not work for the problem and (2) only suggests hardness in other ways.\n\nAdditionally, the authors mention that their results only apply to worst case problems and leave open practical cases where learning is possible.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The paper solves an interesting problem. Learning generative models with just an output layer followed by ReLU activations is known to be solvable. Generative models with two hidden layers are known to be hard (though under different assumptions than this work). This work explores that natural missing case of networks with one hidden layer.\n\n(2) The paper method of designing the hard class of networks is quite rigorous and advanced and can potentially be useful in future work.\n\nWeaknessess:\n\n(1) The biggest weakness is the presentation. The intro is well written, however the subsequent sections can be quite dense and often become a list of lemmas. While some of the complexity is necessary, I believe the authors could do a better job to share their intuition about the result. Reading related work often describes the necessary background with more clarity.\n\nOne related work not cited is:\nVempala, Santosh, and John Wilmes. \"Gradient descent for one-hidden-layer neural networks: Polynomial convergence and SQ lower bounds.\" Conference on Learning Theory. PMLR, 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WGTnqEgF2e", "reviewer": "Reviewer_xmvR", "summary": "The authors study the family of distributions defined by pushing forward a standard Gaussian through a one-hidden-layer ReLU network with $\\mathcal{O}(\\log d / \\log \\log d)$ hidden units and $\\mathrm{poly}(d)$ bounded weights. They prove that under the statistical query (SQ) model, there exists a subfamily of such distributions that are arbitrarily pathological, in the sense that learning any approximating distribution is computationally expensive, namely requiring $d^{\\omega(1)}$ time and samples.\n\nThe authors achieve this by reducing the problem to distinguishing a standard $d$-dimensional Gaussian from a distribution that is a product of a 1D distribution whose first $k$ moments match the moments of a Gaussian along a linear subspace of $\\mathbb{R}^d$ and a standard $d-1$-dimensional Gaussian over the orthogonal complement. [1] previously showed this problem to be hard under the SQ model; thus, the main technical contribution of the authors is to show that the latter kind of distribution can be constructed as the pushforward of a small ReLU network.\n\n[1] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures. In IEEE FOCS 2017.", "questions": " - L201: Why can we absorb $\\sigma$ into the $\\exp(\\mathcal{O}(m))$ term?\n - Do the authors have an intuition regarding what assumptions are \"missing\" / what is \"too loose\" that allows the pathological behaviour? My initial guess is that it would be that $\\mathrm{poly}(d)$ bounded weights are still too flexible, allowing the models to \"overfit\" to the moment-based construction. As I understand, in practice, the weight distribution of models trained using MAP inference is usually heavily concentrated around 0. \n - As a follow-up: do the authors expect any part of their bound to be tight (within the \"class\" of worst-case bounds)? Why / why not?", "limitations": " ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\nThe authors study a very relevant problem: the computational hardness of learning an arbitrary distribution using simple generative models. Their results show that this is a hard problem without making further assumptions, even if the generative model is relatively simple. In particular, the bounds derived are much tighter than previous bounds across every parameter considered, and I believe it is a solid contribution to the literature.\n\nThe ODE-based construction to attain the desired mixture of bump functions used to construct the pathological distribution is elegant. However, I cannot judge how transferable this trick is to related problems, as I am not familiar enough with the literature.\n\nI carefully checked the proofs in the main text and skimmed the ones in the supplementary. Beyond what I believe are typos, I am confident that the results are correct.\n\n# Weaknesses\nThe paper is well-written, and I do not believe it has any significant flaws.\n\nTypos:\n - L51: \"networks\" -> \"network\"\n - L132: \"...which are known to be computationally hard to known both...\"\n - L202: Since the TVD is getting bounded, I believe the upper bound should be $\\epsilon$, not $C$, so the line should have $0.49$ instead of $1/4$.\n - L280 and L293: The order of the elements in the triplets is inconsistent.\n - Eq (2) and Eq below L301: The second lower indices should be $\\ell$s, not $k$s.\n - L362: first Eq should be $\\sqrt{1 - \\sigma^2}f(z_1) + \\sigma z_2$ ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UQdMd87h3os", "reviewer": "Reviewer_EJis", "summary": "This paper shows that under the statistical query (SQ) model, no polynomial-time algorithm can solve the unsupervised learning problem even when the output coordinates of F are one-hidden-layer ReLU networks with log(d) neurons.", "questions": "Questions:\n1. I would be interested to see a discussion on whether the lower bounds in this paper appear in real world examples. For instance, is it possible that the lower bounds in this paper occurs under conventional optimization with low probability? And what does the lower bound results in this paper have to say about the empirical success of deep generative models?", "limitations": "The authors acknowledge their limitations and proposes adequate scope for future work. There is no negative social impact that I am aware of.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. 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.\n\nWeakness:\n1. This paper should have more discussion about the significance of the lower bounds. Please see my questions below for more about this aspect.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept