Most Neural Networks Are Almost Learnable
Authors: Amit Daniely
Nathan Srebro
Gal Vardi
Venue: NeurIPS 2023 poster (2023)
Keywords: learning neural networks
computational complexity
random networks
TL;DR: We present an additive PTAS for learning random constant-depth neural networks

Abstract: We present a PTAS for learning random constant-depth networks. We show that for any fixed $\epsilon>0$ and depth $i$, there is a poly-time algorithm that for any distribution on $\sqrt{d} \cdot \mathbb{S}^{d-1}$ learns random Xavier networks of depth $i$, up to an additive error of $\epsilon$. The algorithm runs in time and sample complexity of $(\bar{d})^{\mathrm{poly}(\epsilon^{-1})}$, where $\bar d$ is the size of the network. For some  cases of sigmoid and ReLU-like activations the bound can be improved to $(\bar{d})^{\mathrm{polylog}(\epsilon^{-1})}$, resulting in a quasi-poly-time algorithm for learning constant depth random networks.

Most Neural Networks Are Almost Learnable
Amit Daniely
Nathan Srebro TTI-Chicago nat eewiiitticcee. edu
Hebrew University and Google
amit frit.daaneel dedddanneel@eee www................... www.jaa...............mo..o ac..il
Gal Vardi
TTI-Chicago and Hebrew University galvardi@ttic.esd
Abstract
We present PTAS for learning random constant-depth networks, We show that for any fixed > 0 and depth there poly-time algorithm that for any distribution on Vd- gd-1 learns random Xavier networks of depth i, up to an additive error of E. The algorithm runs time and sample complexity of (d)paly(c")) where d the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to (d) polyyoog) resulting in a quasi-poly-tinm algorithm for learning constant depth random networks.
Introduction
One of the greatest mysteries surrounding deep learning is the discrepancy between its phenomenal capabilities in practice and the fact that despite a great deal of research, polynomial-timm algorithms for learning deep models are known only for very restrictive cases. Indeed, state of the art results are only capable dealing with two-layer networks under assumptions on the input distribution and the network's ss weights. Furthermore, theoretical study shows that even with very naive architectures, learning neural networks is worst-case computationally intractable.
In this paper, we contrast the aforementioned theoretical state of affairs, and show that, perhaps surprisingly, even though constant-depth networks are completely out of reach from worst-case perspective, most of them are not as hard as one would imagine. That is, they are distribution-fre learnable in polynomial time up to any desired constant accuracy. This is the first polynomial time approximation scheme (PTAS) for learning neural networks of depth greater than 2 (see the related work section for more details). Moreover, we show that the standard SGD algorithm on ReLU network can be used as PTAS for learning random networks. The question of whether learning random networks can done efficiently was posed by Daniely et [15] and our work provides positive result in that respect.
In bit more detail, we consider constant-depth random networks obtained using the standard Xavier initialization scheme 22 26 and any input distribution supported the sphere vd gd-1, For
Lipschitz activation functions, our algorithm runs in time (d)poly(e "), where d the network's ss size including the d input components, and is the desired accuracy. While this complexity is polynomial for constant e, we also consider the special cases of sigmoid and ReLU-like activations, where the bound can be improved to (d) polyyoogg(
The main technical idea in our work is that constant-depth random neural networks with Lipschitz activations can be approximated sufficiently well by low-degree polynomials. This result follows by analyzing the network obtained by replacing each activation function with its polynomial approxima- tion using Hermite polynomials. It implies that efficient algorithms for learning polynomials can be
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

used for learning random neural networks, and specifically that we can use the SGD algorithm on ReLU networks for this task.
1.1 Results
In this work, we show that random fully-connected feedforward neural networks can be well- approximated by low-degree polynomials, which implies a PTAS for learning random networks. We start by defining the network architecture. We will denote by a R - R the activa- tion function, and will assume that is L-Lipschitz. To simplify the presentation, we will also assume that it is normalized in the sense that Ex~V(o.1)0 p(X))², namely, the error when approximating with degree-n polynomial, and note that lim (=(n) = O. We will consider fully connected networks of depth i and will use do = d denote the input dimension and dj...., dg denote the number of neurons in each layer. Denote also d = Ej=o dy. Given weight matrices
= 1. Define (n
mil)dag(p)=n 1101
W = (W W E Rddxdo xdo x... Rd
and x E Io define To 1p
(x) x. Then for S i we define recursively
Φ xx) W 1 (x),
V w (x) - ( (x)
We will consider random networks in which the weight matrices are random Xavier matrices 122 26). That is, each entry in W is centered Gaussian of variance - This choice is motivated by the fact that it is a standard practice to initialize the network's weights with Xavier matrices, and furthermore, ensures that the scale across the network is the same. That is, for any example x and a neuron n, the second moment of the output of n (w.r.t. the choice W) is 1.
Our main result shows that V can be approximated, up any constant accuracy via constant degree polynomials (the constant will depend only e, the depth i, and the activation σ). We will = 1}. Here, and throughout the paper, ||x]| stands {x E d |||||
consider the input space $d-1 for the normalized Euclidean norm ||
2
Theorem 1.1. For every i and n such that ea (n) S there is a constant D = D(n, o) such that if di..... di-1 Z the following holds. For any weights W, there is a degree ni-1 polynomial Pw such that for any distribution D on 5d-1
14 (L + 113
E W.
Tp Pw (x) 144 (T. (1)
(x) W.
S
x
n
Furthermore, the coefficients of Pw are bounded by (2d)an(
Since constant degree polynomials are learnable in polynomial time, Theorem 1.] limplies a PTAS for learning random networks of constant depth. In fact, as shown ( constant degree polynomials with polynomial coefficients are efficiently learnable via SGD on ReLU networks starting from standard Xavier initialization. Thus, this PTAS can be standard SGD on neural networks. To be
more specific, for any constant e > there is an algorithm with (d) (( sample complexity that is guaranteed to return hypothesis whose loss is at most in expectation.
((14))))) (f-1))
time and
For some specific activations. such as the sigmoid (x) erf(z) = v See e 1² à dt, or the ReLU- like activation (xx) = f erf(() + 1dl we have that e, (n) approaches to 0 exponentially fast (see Lemma A.4 4 in the appendix). In this case, we get get quasi-polynomial time and sample complexity (t-1))
11
lng
of (d)
Corollary 1.2. For every constants e, and a there a constant D, a univariate-polle pooyyooiil p and polynomial-time time algorithm A such that if di..... d D the following holds. For any distribution

---

D on Sa-1, if is the output of A upon seeing plda..... d,) examples from D. thei 1 W (x) h((x) Se.
EE
hn W x>
Furthermore, A can be taken to be SGD on a ReI.U network starfing from Xavier initialization.
1.2 Related Work
Learning neural networks efficiently. Efficiently learning classes of neural networks has attracted much interest in recent years. Several works established polynomial-timg algorithms for learning one- hidden-layer neural networks with certain imput distributions (such as the Gaussian distribution) under the assumption that the weight matrix of the hidden layer is non non-degenerate [27] 34 19, 20 [ 32
4 For example, Awasthi al. 4 showed such result for non-degenerate one-hidden-laye ReLU networks with bias terms under Gaussian inputs, and also concluded that one-hidden-layy layer networks can be learned efficiently under the amoothed-annlystt framework. Efficient algorithms for learning one-hidden-layer ReLU networks with Gaussian inputs were also shown in Diakonikolas et al. [8]. Diakonikolas and Kane [17.. These results do not require non-degenerate weight matrices, but they require that the output layer weights are all positive, as well as a sub-linear upper bound on the number of hidden neurons. Chen et al. g recently showed an efficient algorithm for learning one-hidden-layer ReLU networks with Gaussian inputs, under the assumption that the number of hidden neurons is a constant. Note that all of the aforementioned works consider only one-hidden layer networks. Chen et al. (7] gave an algorithm for learning deeper ReLU networks, whose complexity polynomial in the input dimension but exponential the other parameters (such as the number of hidden units, depth, spectral norm of the weight matrices, and Lipschitz constant of the overall network). Finally, several works established algorithms for learning neural networks, whose complexity is exponential unless we impose strong assumptions the norms of both the inputs and the weights [23 30 33 24
Hardness of learning neural networks. As we discussed in the previous paragraph, efficient algorithms for learning ReLU networks known only for depth-2 networks and under certain assumptions on both the network weights and the input distribution. The limited progress in learning ReLU networks can be partially understood by an abundance of hardness results.
Learning neural networks without any assumptions on the input distribution or the weights is known to be hard (under cryptographic and average-case hardness assumptions) already for depth-2 ReLU networks 28 3 11. For depth-3 networks, hardness results were obtained already when the input distribution is Gaussian B 6]. All of the aforementioned hardness results are for improper learning, namely, they do not impose any restrictions on the learning algorithm or on the hypothesis that it returns. For statistical query (SQ) algorithms, unconditional superpolynomial lower bounds were obtained for learning depth-3 networks with Gaussian inputs (). and superpolynomial lower bounds for Correlational SO (CSQ) algorithms were obtained already for learning depth-2 2 networks with Gaussian inputs [25 18]
The above negative results suggest that assumptions on the input distribution may not suffice for obtaining efficient learning algorithms. Since in laee-ddden-lleerr networks efficient algorithms exist when imposing assumptions
both the input distribution and the weights, natural question is whether this approach might also work for deeper networks. Recently, Daniely et al. [13] gave a hardness result for improperly learning depth-3 ReLU networks under the Gaussian distribution even when the weight matrices are non-degenerate. This result suggests that learning networks of depth larger than 2 might require new approaches and new assumptions. Moreover, [15] showed hardness of learning depth-3 networks under the Gaussian distribution even when a small random perturbation is added to the network's 's parameters, namely, they proved hardness in the proothed-annlyyee framework. While adding a small random perturbation to the parameters does not seem to make the problem computationally easier, they posed the question of whether learning random networks, which roughly correspond to adding a large random perturbation, can be done efficiently. The current work gives a positive result in that respect.
Daniely and Vardi [1] studied whether there exist some "natural" properties of the network's weights that may suffice to allow efficient distribution-free learning, where "natural" property is any property
The leftmost expectation denoted E, is over the examples provided to A, as well as the internal randomness A.
3

---

that holds w.h.p. in random networks. More precisely, they considered a setting where the target network is random, an adversary chooses some imput distribution (that may depend on the target network), and the learning algorithm needs to learn the random target network under this input distribution. They gave a hardness result for improper learning (within constant accuracy) this setting. Thus, they showed that learning random networks is hard when the input distribution may depend on the random network. Note that in the current work, we give positive result in a setting where we first fix input distribution and then draw random network. Finally, learning deep random networks was studied Das et al. [6, Agarwal et al. M. where the authors showed hardness of learning networks of depth (log(d) (d) in the SQ model.
2 Proof of Theorem 1.1
2.1 Notation
We recall that for vectors x E Rd we use the normalized Euclidean norm ||x||
Σ and take the unit sphere 3d-1 {x E RR |x|| = 1} w.r.t this norm as our instance space. Inner products will also be normalized: for x, d we denote (x, y) سسم For E E2 and a closed set A C Rd we denote d(x, A) := mAn |x x'I. Unless otherwise specified, random scalar is assumed be a standard normal, random vector in Rd is assumed be a centered Gaussian vector with covariance matrix 3 and random matrix is assumed to be a Xavier matrix. For f RR + R. we denote | = Ex (X). We denote the Kronecker delta by 8ij. i.e. dij = 1 if and 0 otherwise.
2.2 Some Preliminaries
We will use the Hermite Polynomials 29
which are defined via the following recursion formula.
1 (x)
x
hn (x)
Am ( ho(z) = hn = (1)
Vn+++
The Hermite polynomials are the sequence of normalized orthogonal polynomials w.r.t. the standard Gaussian measure. That is, it holds that
X EA((X),((X) 8ay
More generally, if (X, Y) is a Gaussian vector with covariance matrix (0 ?) then
E hx()))y())) Susp
(2)
x
We will use the fact that
h1, Vnhn-1
(3)
and that for even n
EX"
(n- 1)!! x
(4)
Let Ei a,h, be the representation of the activation function a in the basis of the Hermite polynomials. We will also use the dual activation (pp) -im at as defined in 14 We note that o is defined in [-1,1] 1] and satisfies (11) ||o 1.
2.3 Defining a Shadow Network
In order to approximate v w via a polynomial, we will use a "shadow network" that is obtained by replacing the activation with a polynomial approximation of it. We will show that for random networks we can approximate each activation sufficiently well with low-degree Hermite polynomials. Recall that σ = Ea =0= a;h; is the representation of a in the basis of the Hermite polynomials. Define
On EEL Liz a,h;, We have (n) = -00 -iin+1 of and hence on (m) Σn a,h;

---

We next define a shadow network. For x E R we let W (x) X. For 1 S j S i we define recursively
T (x) = (p (x)) = on (
(xx)
for S sjSi-i and f W
(x)
w Wi (x). We will prove the following theorem, which implies
Theorem 1.1
Theorem 2.1. Fix i and let be large enough so that co (n) S 2' There is constant D D(n,i,
such that if dj...., d 2 D then for any x E gd-1
T W (x) - w (x)) 1 11 (L+ (c)(
Since Eg (n) is the error in the approximation of single activation with degree-n polynomial, it is natural to expect that the above bound will depend on &g (n). To see why Theorem 2.1 (together with Lemma A.3 which bounds Ear (n)) implies Theorem 1.1 note that t (x) is polynomial of degree ni-1, This implies Theorem I.1 except the requirement that the coefficients of the polynomial polynomially bounded. To deal with this, define
c im (x) W
if all entries in W are at most Σj=o dj
t W (x)
10
otherwise
As we show next mimmi
Hence, in the theorem we can replace ti by hh.n which has polynomially bounded coefficients. See Appendix A.3 and A.4 for the proofs.
E
1 1p (x) T (x)
Lemma 2.2. For every and n there is constant D such that if di,..... di- 2 D then for any E Sd-1, Ew
4 w
(x)
th
i. w
xx) <e
Lemma 2.3. th w
computes polynomial whose sum of coefficients is at most (2d) (2d)
2.4 Proof of Theorem 2.1 for depth-two networks
We will first prove Theorem 2.1 for depth-2 networks (i.c. for 2). We will prove Lemma 2.5 below which implies that for every there is such that for any E gd-1
Ew V (x)
vil (x) I e. We will then prove Lemma 2.6 that together with Lemma 2.5
will show that E
222 (x) - 22 (x) S thus proving Theorem 2.1 for i = 2. We will start w
however with the following lemma that will be useful throughout (see Appendix A.5 for the proof).
Lemma 2.4. Fix
R, x.y Rd and Xavier matrix W E Rd2xd, Let (X,Y) be
||x||² (x,y) lyl
centered Gaussian vector with covariance matrix
(xx
Then
B (I((w)) g(Wy)ll V [S(Wx) - 3(Wy)l - -
Lemma 2.5. Fix x E 5d Let E Bddxd be a Xavier matrix. Then
[lo()) (WV)l s (n) W
E
Proof. By Lemma 2.4 we have
[Wx) (Wx)ll S
[llo(Wx)) am (Wx)] B(o((()) ( -xx)x)
5

---

Now, the above equals to
2
1
1
af +
(1 (d)))
1 (
+c6(1))
V1
(n)
i=0
1=n+1
2
V1- -
(1 c(())
v1 (n)
2 2/1 - co (n) + (
2 - (m))
V2 vI- V1-
(2)
Lemma 2.5 implies that Ew
(x) I [x(x)) S /26 Thus, given e 0, for suf- (x) 1 (x)) S c. The following lemma therefore implies that
1 -/-1
ficiently large n. Ew
4 1. 1V
Ew 2m (x)
w (x)
I v 220 (n) and thus implies Theorem 2.1 for depth two networks.
Lemma 2.6. For any E S
E Wi
Tiin (x)
w (xx) -
(x)
v 1.-1 (x) v 1 (x)
Proof. By Lemma 2.4 we have
E
(x)
16 (30
E
W (x " (x)
W
W
w
E
X²
V xx~>[ xx>((o.)) (0.1 (ix) 3 (x0)
|| | 1.m (xx(xx) w (x)
2.5
Proof of Theorem 2.1 for General Networks
For x E jid:-1 we denote 4p Ww: = (W''x and u 1 (x) o. (W'x). Lemma 2.5 can be roughly
phrased
(x x') and (||x|| = 1) = w (x) = (x))
In order to prove Theorem 2.1 for general networks we will extend it by replacing the strict equality conditions with softer ones. That is, we will show that
(x x') and (||x|| 2 1) and ([]x'|| 1) (x) Wy (x')
(5)
This will be enough to prove Theorem 2.1 for general networks. Indeed, the conditions ||x|| ~ 1 and [|x|]| are valid w.h.p. via simple probabilistic argument. Thus, Eq. (5) implies that
x=x (w)(x) z (x'))x)
(6)
Now, for 5d-1 Eq. (6) implies that Ww L (x'). Using Eq. 6 again get that V W L0 w (x) ss yp o o wi (x'). Using 3 more times we we get that V o w (x) ss Vn W Miy (x'), or in other words that wi-1(x) se vi-1." (x)). As we will show "x" stands for
sufficiently strong approximation, which guarantees that E, || (x) hence Lemma 2.6 implies Theorem 2.1
v -i-1
i-1 pi-1*(x)]| S and

---

To prove Eq. (5) we first prove Lemma 2.7 which softens the requirement that x x'. That is, it shows that
(x=x)) x') and (||x ||x'| 1) w (xx')')
The second condition which requires that ||x|| ||x||| is softened via Lemmas 2.8 and 2.9
Lemma 2. 10 then wraps the two softenings together, and shows that Eq. 5 is valid. Finally, in
section 2.5. we use Lemma 2.10 to prove Theorem 2.1
Lemma 2.7. Fix x, +
Sdh 1 with || S e. Ler W Rd be Xavier matrix. Then
2L3
E (, = (n)
V 1- 1- (1)
Proof. We have
|l(Wx)) on (x + v))ll llo(x) (Wx) + |Ion( on (W(( v))l
By Lemma
2.5 we have Ew lo Jn (W))l 1 (2) It remains to bound
Ew
(Wxx on (W (x + v)]l. By Lemma 2.4 We have
(Wx) - on (W vv)ll - / E (xn(() - oY(2))2
E W
V x x,y
where (X, Y) is a centered Gaussian vector with correlation matrix () p)
for p = (x,
1 e. Finally, we have
E X,Y
- ())
E X.Y
Σ (()(()))n;;())
1 1 (n)
Y=0
0:aj E (ha()) - - -x)
1 - (n)
X.Y
1=0 f=0
Eq. 2
af 2p')
1 En (n)
t=0
(ō(1) a()))
1 (n)
In Lemma A.1 we show that L.i-shhchit Hence the above is most
21 1- (x)
We next give a lemma that allows us to "almost jointly project" pair of points X1, X2 E Rd on closed set A C I&d, without expanding the distance too much. See Appendix A.6 for the proof.
Lemma 2.8. Let A C Rd closed set and fix X1, X2 E Rdd, There are x1, X2 E A such that
[x x & A), ||x2 - xell S 2d( A) and ||X
x2 S 3 x1 X2ll
Lemma 2.9. x, + Rd be vectors such that |x|| = 1 and ||vl| S e < 1. Ler W E Rd2xd. be a Xavier matrix. Then
E (lo( - o (W(( v))ll < Te
and
R W
Ja (Wx) on (W < 2 (9(4n 1/
6= X(n)e
v, |x+
Proof.
Fix a centered Gaussain vector (X, Y) with covariance matrix
+ V, v,
Let Z Y X. Note that Var(Z) < e², By Lemma 2.4 we have
v)) < (((o(X)-a - o(X 2)P 5 &VIEEZ Le
7

---

We now prove the second part. In Lemma
A.2
we show that [11(2) - h2(2 + 8)1 S 2" maa( [z], +
yl. 1) Therefore,
a,s
(0n(2) + +11l=
(xx
(n) [h((x) 121 v)
< y
2' max((a] 1/x + +l' 1)
| m
max([2]" |a y1", 1)
Hence, E(on(X) on + Z))²
2 E z max(1x Th X + 1)²
2 V Z / max X 4m |X + 2|4n,11 1)
22n+2 v 74 X
X + am +1
Eq.
22n+2 v| / 1+ (4n
+
X 4m)
2 /ed 1 //31 e) (4n 1)!!
22n+2 /3 /3 2 (4n 1)!!
Lemma 2.4 now implies that
E (Wx) (W (o.
v))ll
2 (9(4n 1)11)
Lemma 2.10. Let x, v Rdi be vectors such that ||v|| I |||x|| - 11 s 8 s 1/2 and
|||x + vll - 1| S 5. Let W E Rd2xds be a Xavier matrix. Then
6L
E W lo(
on ( v))1 218 (n) V (- + 22(1))
Proof. By Lemma
2.8 there are vectors x', v' such that ||x'|| ||x' + v'll and
xx x'
26,
||x +
x' vll s 28, and || s 3||v
Now, we have, by Lemmas 2.7 and 2.9
E (o(Wx) on (W vv)l
<
E
(Wo)))) oWx')ll + [o(x')) o (W +v'ill
W
W
+ I + v)) on (W v))l
612
2L5 + (2) + V
c 22(1)
c (n)
2.5.1 Concluding the proof of Theorem 2.1
Define
0
11 V le (x)lll 8 1 - -|| (x)]lI > 8 for some j <
Vi W (x, 8)
0x,
Vri IT
(x)
otherwise
and
0
1 I w (x)]l > 8 or |
||
(x)]l > 8 for some <
i (x, 8)
W
y i (x) W
otherwise
8

---

We have
E
w w
(x)
wenn (x)
I E W
Ve 11
(x)
w (x, 63
+ E
1 1
w (x. 8)
(x, 6)
W
v
+
mm W
(x, 8)
i (x)
Theorem
2.1 now follows from Lemmas
2.11 and 2.12 below, together with Lemma 2.6
Lemma 2.11. Let be large enough that co (n) S and let ó (e)(x))
22+2A(m)) Then,
Ve W (x. - wi "x
[x. 5) - 12 (L + 1)² (c)(
Proof. We will prove the result by induction on i. The case i = 0 is clear as To 10: (x. 6) = -u " (x. 8).
Fix i > O. For every 8 < and n we have by Lemma 2.10
V' (x, 6) - u (xx Wi
E
I 2L + (2) +
61
| 18
(x, 5) w/ "xx, + 2A(1)6
ca(1)
Taking expectation over W
Wi-1 we get
E of
Vi (xx 6) " 5)
2L8 + 2e0
61
| ( (x, 8) / (x, 0) + +2(n1)
1 ca (n)
Jensen inequaltt
218 + (m)
6L2
1 (x, 8) / v (x. 0)
10
+ 22(1)
1- (n)
Vealm 6< 2X
(n) + 1 VI- co (n)
61
E
(x, - w (x, 6)
w
18.
(m) S
4V + / 12B 1
w 6)
1 10 1.1 (x, 83
Induction hypothesis
4neo(n) + T.V 12 12. (L. - 1)2 (c- (n))
IA
(L+ 1)V 12 12 (L 1)3 (co(n))²
12- (L+)))((c..))) (n))
Lemma 2.12. Fix i, n. and E > There is a constant such that if di,..... di-1 2 then
E
Ti (x)
V (x, 1)/|
+
E W
v in
W (x,
5)
v (x)
Sc
W
Proof sketch (see Appendix (..pendi(A.71pp
[A7 for the formal proof). Let Bi, be the event that for some j < i,
|1 - 1 w (x) ||| > 5 or | -| (x)]ll > We have
Tp (x) (x) v (x, 6)| W
|||
v w
(x)
1
S S
E w
v (x)l
/Pr(Brs)
Similarly,
w (x) w
w (x, 5 V
6)/l
||
I w
(x)) (x)
| /Pr(BB))
Now, the lemma follows by proving that Fe constant (independent of do...., d:), and that for every 6, e', and n, there constant D such that if dd,...,dh1 > D then Pr(B.,) é..
||
I w (xx
l| and Ey
( (x) are bounded by a
D

---

3 Conclusion and Future work
One of the prominent approaches for explaining the success of neural networks trying show that they are capable of learning complex and "deep" models. So far this approach has relatively limited success. Despite that significant progress has been made to show that neural networks can learn shallow models, so far, neural networks were shown to learn only "toy" deep models (e.g. 21 2 IO] 3I). Not only that, but there are almost no known rich families of deep models that are efficiently learnable by some algorithm (not necessarily gradient methods neural networks). Our paper suggests that random neural networks might be candidate models. To take this approach further, natural next step, and central open question that arises from our work, of an algorithm that learns random networks in time that is polynomial both in and the network size. This question is already open for depth-two ReLU networks with two hidden neurons. We note that as implied by [I], such a result, even for a single neuron, will have to go beyond polynomial approximation of the network, and even more generally, beyond kernel methods.
show the existence
Our result requires a lower bound D for the network's width, where D is a constant. We conjecture that this requirement can be relaxed, and leave it future work. Additional open directions are: (i) the analysis of random convolutional networks, (ii) achieving time and sample complexity of (d)o(e")) for random networks of any constant depth (and not only for depth two), and (iii) finding PTAS for random networks of depth (1).
Acknowledgments and Disclosure of Funding
The research described in this paper funded by the European Research Council (ERC) under the European Union's Horizon 2022 research and innovation program (grant agreement No. 10104171 1), and the Israel Science Foundation (grant number 2258/19). This research was done as part of the NSF-SSmons Sponsored Collaboration on the Theoretical Foundations of Deep Learning.
References
[1] N. Agarwal, P. Awasthi, and S. Kale. A deep conditioning treatment of neural networks. In Algorithmic Learning Theory, pages 249-305. PMLR, 2021.
[2] Z. Allen-Zhu and Y. Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:1905.10337, 2019.
[3] B. Applebaum, B. Barak, and A. Wigderson. Public-key cryptography from different assump- tions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171-180, 2010.
[4] Awasthi, A. Tang, and A. Vijayaraghavan. Efficient algorithms for learning depth-2 neural networks with general relu activations. Advances in Neural Information Processing Systems, 34:13485-13498 2021.
[5] A. Bakshi, R. Jayaram, and D. P. Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR, 2019.
[6] S. Chen, A. Gollakota, A. R. Klivans, and R. Meka. Hardness of noise-free learning for two-hidden-layer neural networks. arXiv preprint arXiv:2202.05255 2022.
[7] S. Chen, A. R. Klivans, and R. Meka. Learning deep relu networks is fixed- fixed-paranenn parameter tractable. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 696-707. IEBE, 2022.
[8] Chen, Z. Dou, S. Goel, A. R. Klivans, and R. Meka. Learning narrow onc-hiddenn-laer relu networks, arXiv preprint 2tt.:2334.10524, 2023.
[9] A. Daniely. Sgd learns the conjugate kernel class of the network. NIPS, 2017.
[10] A. Daniely and E. Malach. Learning parities with neural networks. In NIPS, 2020.
10

---

[11] A. Daniely and S. Shalev-Shwartz. Complexity theoretic limitations on learning dnf"s. In Conference on Learning Theory, pages 815-830, 2016.
[12] A. Daniely and G. Vardi. Hardness of learning neural networks with natural weightss. In NIPS, 2020.
[13] A. Daniely and G. Vardi. From local pseudorandom generators to hardness of learning. In Conference on Learning Theory, pages 1358-1394, PMLR, 2021.
[14] A. Daniely, R. Frostig, and Y. Singer. Toward deeper understanding of neural networks: The power of initialization and a dual view expressivity. In NIPS, 2016.
[15] A. Daniely, N. Srebro, and G. Vardi. Computational complexity of learning neural networks: Smoothness and degeneracy. arXiv preprint arXiv:2302.07426, 2023.
[16] A. Das, S. Gollapudi, R. Kumar, and R. Panigrahy. On the learnability of deep random networks. arXiv preprint arXiv: 190409304066 2019.
[17] I. Diakonikolas and D. M. Kane. Small covers for near-7ero sets of polynomials and learning latent variable models. In 2020 IEEE 6/ Annual Symposium on Foundations of Computer Science (FOCS), pages 184-1999 1944195.10 IEEE, 2020.
(18) I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and sq lower bounds for pac learning me-hiddeenllaer relu networks. In Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[19] R. Ge, Lee, and T. Ma. Learning meehidden--aaye neural networks with landscape design. arXiv preprint 17I.i:1711.0000 2017.
[20] R. Ge, R. Kuditipudi, Z. Li, and X. Wang. Learning two-layer neural networks with symmetric inputs. arXiv preprint TeXiv:8810.0672 2018.
[21] B. Ghorbani, Mei, Misiakiewicz, and A. Montanari. Limitations of lazy training of two-layers neural network. In Advances in Neural Information Processing Systems, pages 9108-9118, 18, 2019.
[22] X. Glorot and Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[23] S. Goel and A. R. Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference Learning Theory, pages 1470-1499. PMLR, 2019.
[24] S. Goel, V. Kanade, A. Klivans, and J. Thaler. Reliably learning the relu in polynomial time. In Conference on Learning Theory, pages 1004-1042. PMLR, 2017.
[25] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. arXiv preprint arXiv:2006. 1201 2020.
[26] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[27] M. Janzamin, H. Sedghi, and A. Anandkumar. Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv: 0400000887,, 2015.
[28] A. R. Klivans and A. A. Sherstov. Cryptographic hardness for learning intersections of halfs- paces. In FOCS, 2006.
[29] R. O'Doneell. Analysis of boolean funtionn. Cambridge University Press, 2014.
[30] S. Vempala and J. Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds. In Conference on Learning Theory, pages 3115-3117. PMLR, 2019.
11

---

[31] G. Yehudai and O. Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904.000 00687, 2019.
[32] X. Zhang, Y. Yu, Wang, and Q. Gu. Learning one-hidden-layer relu networks via gradient descent. In The 22nd international conference on artificial intelligence and statistics, pages 1524-1534. PMLR, 2019.
[33] Y. Zhang, J. D. Lee, and M. Jordan. 11-regularized neural networks are improperly learnable in polynomial time. In International Conference Machine Learning, pages 993- 993-1001. PMLR, 2016.
[34] K. Zhong, Z. Song, P. Jain, P. L. Bartlett, and I. S. Dhillon. Recovery guarantees for one-hidden- layer neural networks. In International conference on machine learning, pages 4140-4149. PMLR, 2017.
12

---

A Missing proofs
A.1 Some Technical Lemmas
Lemma A.l. o is L-Lipschitz then is L -ippschhit in [-1,1] 1]
Proof. As shown in 14 (ō)' = 0². Hence, for E [-1, 1],
(()(()) = (p)
110'11
S L
Lemma A.2. (2)((:) h, v)1 2" max([x],, Jar vl. lol
Proof. It is not hard to verify by induction on Eq. I that
[/n(z)] & 2n/ max(1,/21")
This implies that for & E [x, x + yl (x) - hn x + y)l
I,,(E)
Eq
/n2m/2 max( |rl, | + yl. 1)
2" max((x]), + yl. lyy
A.2 Bounds on (n)
By Eq.
3 if differentiable k times then we have ((k)
dl Eish V (T- a
Hence, for
k S n
(n (n+1= k!!
i! k))
(n+ + 1 (911-k)) k)!
(n + 1)! |octs1p
co(n)= Σ af
Σ
a s
(7)
(n + 1)!
i=n+1
i=++1
Lemma A.3. For any L-Lipschitz we have co (n) < L
Proof.
By Eq. for = we get
(n) n n
1
||0'11
2
11
Lemma A.4. For the sigmoid activation ozx) 1od e-
o dt we have co (n) 2-
Proof. We have a (A) = 1-10---( ( - + Indeed, is not hard to verify it for A 1 and le 2. For k > 2 have via induction that
(x)+1)(2)
(-1)*-1 V 1)! (x) xha- 1x)] -
Bq.
(-1)* [ (x) - Vk 1h ( c
Eg.
(-1)*Vilhu (x)e
Hence, (1)0 S 1 (k 1)th (z)), and now Eq. implies that for any & S n +
(n 1 k)!
(n k)DE!
(n)
(n + 1)! (k: 1)!
(n + 1)tk
k(*)')
Taking & [++1 conclude that (n) 2-
13

---

A.3 Proof of Lemma 2.2
Let A be the event that there is an entry in W that greater than Σj dz. We have
E o
(x) E
+ im
(x)
LA]
V / fx VPr(A)
Now, it is not hard to verify that E
(x)
is polynomial in Σj d3 while Pr(A) con- Thus, if
W
verges to 0 exponentially fast in Σjzod.
d is large enough then
Bw (x) $ W <c
(x)
Wp
A.4 Proof of Lemma 2.3
We assume that $5 W
T... ob wi otherwise n. W (x) Ek boc and he(ar) Ek Cjack. Hence,
0, in which case the lemma is clear. Write Via induction Eq. L we have legal S 2
ag cla.uc
Σラ == aj
2
j=0
ag 12
Σグ= az
"
1=0
2
Eー== a3
j=0
f=0
2
Now, let M, be the maximal sum of coefficients of any polynomial computed by output neuron of up We next show by induction that M, I (2d)2<i_ x* This will conclude the proof as it will imply that the sum of the coefficients of the polynomial computed by & is at most w
(2d)² I 22d < (2d)an=" For j = 0 we have Mo = 1. For j 2 we we have
M, $ K=
bel ((a)2 2 n+1 .2 M(d) (12))
By the induction hypothesis we have
M, S (2d) Et (2m) n*
A.5 Proof of Lemma
2.4 2.4
We have
Jensen Incquality
E W
I[(()) s(Wy)
E ll x(Wx)11
d2
E ((((())),) ,(Wy))))
d2
W
1=1
Now, the lemma follows from the fact that {((Wx), (W (Wy) are independent centered Gaussian
|x|2
(x,y)
vectors with covariance matrix
(x,y)
|yll
14

---

A.6 Proof of Lemma 2.8
Let PA R2 + A a function such that for any x E R2, [x(xx) - x|| - d(xx, A). Assume w.l.o.g.
that ||x PA(x1)] I || - (x
Case I: ||x₂ - (A(x2)) I |x] - xxll
Simply define X; PA(x:). We have
||x| x1 || ||x| Pa(xi)ll, - (x2--x21 ||x2 (x2)l
and
||x] - x211 s <1P1(x))= - x +| - -x((x)] s 33
X2
Case
II: [x] x2 S X2- (x(x))]
Define X1 = x2 = (x)). We have
||*] - x = ||x| Pa(x))ll, || - x2ll & 0f|x1 X2ll
and
Xx- - X22 < X2 x1 ll + |xx Pa(x))l S2 PA(x2)l
A.7
Proof of Lemma 2.12
Let Bi be the event that for some
i, -1 || (x)ll > 8 or
1| (x) >
We have
v in (x) 6)
(x,
E w
||| cp [x (xx
1 1B,8
E
(s0)
Pr((B.))
w
Similarly,
bm (x)
u (x, 53 = V
E
(xx) (x)
the lemma now follows from the following two claims.
Claim 1. Bw wi ( (x)) do....,de .d)).
and Eew || (x)
2
are bounded by constant (independent of
Proof. We have
E
v w (x)
=
(x)
W
20)
2L
w
y w
(x)
200 + 21. - (x))l
2
By induction on i, this implics that E
vi w
(x)
is bounded by a constant that depends only on
and J. (but not on di...., de). For Eye-
y
(x)
we have
(x)
=
E
of
w viin (x)))
W
Hence, Ew: vi (x)
an even polynomial
degree S 2n. The polynomial w
depends only on on therefore enough show that for any and Ey /vi (xx
2k
is bounded,
15

---

by a bound that is independent of do d₁. We will show that via induction on i. For = 0 this is
26
trivial as
(xx
1. Fix 1. We have
W
Eg= d
2k Yo (x)
E
E
W.
W
di
Jensen incquality
((wipt))(()))
S
IF
Σ
24
di wi
j=1
E on
w
Ti (x)))) w
w
The last expression is an even polynomial in | [xx=l"(())l) n. By the induction hypothesis we conclude that Ew in (x) independent from do....,44 di-
(x)ll- The polynomial depends only on 2k and
is bounded by bound that is
Claim 2. For every 8, i and n, there is a constant D such that if di,...., di-1 D then pr(Bi,s) <''.
Proof. We will prove the lemma by induction on i. For i this is immediate as Pr(Br,s) 0. Fix i 22 2. Let be small enough so that if |||||| - 1| S then
E 2 (w x) - 1/ and w
5
E of (w x) -1 -1|=
and
E Eo x) [x) < 1 and Bo T x) (x)
<1
x
we have
Pr(Br.s Pr (r( Pr
By Chebyshev inequality, Pr( b for sufficiently large d:-1. By the induction hypothesis, Pr(B(-1,8)) < 5 for sufficiently large d1....,d4-2
16


Reviews:
[{"review_id": "zsnX5eM7rl", "reviewer": "Reviewer_mRGU", "summary": "This work presents a polynomial-time approximation scheme (PTAS) for learning random Xavier networks of depth $i$ up to a fixed additive error of $\\epsilon$ with respect to any distribution on the hypersphere. For a fixed $\\epsilon$, the time and sample complexity is polynomial w.r.t. $\\bar{d}$, the total parameter size of the neural network. The work also provides improved bounds for $\\bar{d}^{polylog(\\epsilon^{-1})}$ for special activation functions such as sigmoid.\n\nPrior work has several limitations, mainly that most consider only one hidden-layer-layer networks. The most comparable work is Chen et al. [7] which provides an algorithm for learning deeper than one layer ReLU networks, yet while the complexity is polynomial in $\\bar{d}$, it is exponential in paramaters such as the number of hidden units, depth, spectral norm of the weight matrices, and Lipschitz constant. In fact, there are a plethora of negative results regarding hardness of learning. This work avoids these hardness results by fixing an input distribution and then drawing a random weights of the network.\n\nThe main idea of the paper is to approximate the activation function sufficiently close to the original by replacing it with a polynomial approximation using Hermite polynomials (Theorem 1.1).  The paper calls this a \"shadow network\" and requires that the shadow network's coefficients are polynomially bounded. Given the extensive work on learning polynomials efficiently, the authors can leverage these algorithms, such as SGD on learning polynomial approximations, to obtain a PTAS for learning random networks to a sufficiently small error.", "questions": "- Regarding constant $D(n,i,\\sigma)$: It is not entirely clear to me what $D$ explicitly is with respect to the parameters of $n,i,\\sigma$. Since $D$ is a lower bound to the number of neurons in each layer, this quantity seems highly relevant and would be helpful to make explicit in the main explicit theorem (like Theorem 2.1). My question is the following: how does the lower bound $D$ compare to prior work?  How would the results change if you do not have an explicit constant $D$ and assume $D := \\min(d_1, ..., d_{i-1})$? Would such guarantee exist given the current techniques and what would the guarantees be w.r.t. this new $D$?\n- L140: When defining Hermite polynomials, is $\\delta_{ij}$ defined? I think this is missing and should be added to Section 2.1.\n- L144: When defining dual activation, $a_i$ is undefined yet. Maybe reordering the definition so that dual activation comes after defining $\\sigma$ with Hermite polynomials would be clearer.", "limitations": "See Questions. Other than that, the authors are clear with the limitations and comparison to prior work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This work studies an important problem of learning deeper-than-two-layers neural networks efficiently. Given the high theoretical relevance of the problem regarding the effectiveness of deep learning, the significance of studying such problem is justified. \n- I find the presentation of the paper quite clear, though it may be helpful in describing prior work and results on learning polynomial approximations using Hermite polynomials. Otherwise, the related work and comparison is to prior work are clear.\n- The main result provides a PTAS that is distribution-free in its input distribution. Prior work did not get such flexible results and this work achieves this in part by incorporating a common initiailization method (random Xavier networks) and studying \"average-case\" results instead of worst-case instances.\n\n", "weaknesses": "I do not see any notable weaknesses. I have some questions, which may be seen as weaknesses, that I will list below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review.\n\nRegarding the questions:\n1. This is a good question. In our result, we need a lower bound $D$ on the width which is of the form $L^{n^i}$, where $L$ is the Lipschitz constant of the activation function. We also conjecture that the theorem is correct with respect to any constant. Prior work considered significantly different settings, but a lower bound on the width is usually not required. We will discuss it in the final version.\n2. Right. We will add it.\n3. We will reorder.\n"}, {"review_id": "prKOcyp34l", "reviewer": "Reviewer_JZMD", "summary": "The work shows that there is a PTAS for learning a random xavier feedforward network. They show rigorously that the algorithm runs in time and sample complexity $d^{t}$ where $t = poly(\\frac{1}{\\varepsilon})$. This is quite an impressive result since it is a distribution-free result in terms of the input $x$. Furthermore, a corollary of this result is that it shows that SGD can learn these networks.", "questions": "1. The abstract mentions Xavier networks - shouldn't this only be feedforward networks? Or is it easy to extend to other kinds?\n2. I understand that $\\epsilon_{\\sigma}(n)$ refers to the error when approximating the activation by a polynomial of degree $n$. I would like to see a few lines explaining the intuition behind this quantity and why it is important.\n3. The input space is restricted to be **on** the unit sphere. Can this be relaxed to handle $\\lVert x \\rVert \\leq 1$?\n4. Theorem 1.1 is stated as \"For any weights $W$\", but the bound takes an expectation over $W$. Is it on average or \"for any\"?\n5. The notation can be cleaned up. For example in Line 66, consider saying $d^t$ where $t = \\mathcal{O}(dots)$\n6. Why does Corollary 1.2 consider $\\epsilon, i$ as constants? Isn't it just for any $\\epsilon, i$? Is it possible to indicate the dependence on $i$ in the bound?\n7. Is the claim of Corollary 1.2 that SGD can be used to approximate a Xavier network starting from a Xavier network on average? I understand that this is non-trivial, but I am not able to get a good intuition as to why this is important.\n8. I feel line 113-116 provides excellent motivation for the work. I would recommend the authors to highlight it in the introduction.\n9. $\\delta_{ij}$ is the dirac-delta function?\n10. In Lemma 2.7, it says fix $W$ and then takes $\\mathbb{E}_W$. I don't understand this.\n11. Is the application of Jensen's Inequality in line 233 obvious? $\\psi$ isn't convex as a function of all the $W$'s right? Or is the expectation only with respect to the last layer's weights?\n12. I think the work is good, but presentation can be improved. I would recommend moving the proofs to the appendix and highlighting intuition and explaining the result regarding SGD in more detail.", "limitations": "I feel the authors should include a more detailed limitations section where they address some of the concerns I have listed above as questions (if relevant).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This is a technically challenging and impressive result.\n2. Typically, learnability results for Neural Nets are restricted to 2-layer shallow networks. To extend the result to constant depth networks is quite impressive even if they are only random.", "weaknesses": "1. The paper can be better written. While the technical content is good, I feel there could be more intuition and better presentation. Proofs could be moved the appendix and detailed proof sketches could be included.\n2. Since the PTAS is for learning random networks, it's practical value is questionable.\n3. I found certain aspects of the theory hard to understand - I have included them in the review as questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review. We will improve the writing according to the outlined suggestions. \n\nWe next address the reviewer’s questions:\n\n- *“The abstract mentions Xavier networks - shouldn't this only be feedforward networks? Or is it easy to extend to other kinds?”:*\nOur techniques are not limited to feedforward networks, and we are certain that they can be used to derive similar results for more architectures. This is mostly left for future work.\n\n- *“I understand that $\\epsilon_\\sigma(n)$ refers to the error when approximating the activation by a polynomial of degree  $n$. I would like to see a few lines explaining the intuition behind this quantity and why it is important”:*\nIn the proof we essentially replace the activation by its polynomial approximation. Thus, it is natural to expect that our bound will depend on the extent to which the activation can be approximated by a polynomial. We will add an explanation to the final version.\n\n- *“The input space is restricted to be on the unit sphere. Can this be relaxed to handle $\\lVert x \\rVert \\le 1$?”:*\nWe can relax this requirement and assume that the inputs are close to the unit sphere. This will result in an additional factor in the bounds.\n\n- *“Theorem 1.1 is stated as ‘For any weights $W$’, but the bound takes an expectation over \n$W$. Is it on average or ‘for any’?”:*\nThe polynomial $p_W$ is defined for any $W$, and the bound is valid in expectation.\n\n- *“Why does Corollary 1.2 consider $\\epsilon, i$ as constants? Isn't it just for any $\\epsilon, i$? Is it possible to indicate the dependence on $i$ in the bound?”:*\nThe dependence on the constant can be derived from Theorem 1.1. We write the corollary to emphasize that our main theorem implies a PTAS. \n\n- *“Is the claim of Corollary 1.2 that SGD can be used to approximate a Xavier network starting from a Xavier network on average? I understand that this is non-trivial, but I am not able to get a good intuition as to why this is important”:*\nThe importance is that this implies that standard training algorithms can learn most neural networks. Thus, this can be seen as a partial explanation for the success of NN, which is a central open question these days.\n\n- *“I feel line 113-116 provides excellent motivation for the work. I would recommend the authors to highlight it in the introduction”:*\nWill do. Thanks!\n\n- *“$\\delta_{ij}$ is the dirac-delta function?”:*\nIt is the Kronecker delta. We will clarify this.\n\n- *“In Lemma 2.7, it says fix $W$ and then takes $E_W$. I don't understand this”:* \nIt should be replaced with “let $W$ be a Xavier matrix”.\n\n- *“Is the application of Jensen's Inequality in line 233 obvious?”:* \nIt follows from the concavity of the square root function.\n"}, {"review_id": "w8h7DMko9m", "reviewer": "Reviewer_PwvA", "summary": "The paper proves that a sufficiently wide neural network which is randomly sampled according to Xavier initialization can be learned in polynomial time (in the network size) up to an additive error $\\epsilon$ if the numbers of layers, the Lipschitz-constant of the activation function, and $\\epsilon$ are fixed constants.", "questions": "- The result seems to assume realizability of the data, that is, it assumes that the ground truth is actually represented by a Xavier-initialized neural network. Did I understand this correctly and can you say anything about the non-realizable setting (where the data can be anything, but you compare yourself only against the error of a best-possible neural network)?\n- How much of a restriction is it to restrict the input data to the boundary of the sphere?\n- For sigmoid and \"ReLU-like\" activation functions, you prove a better dependence on $\\epsilon$. Can you obtain something similar for the actual ReLU activation function? If not, what are the obstacles?", "limitations": "Generally the authors state all mathematical assumptions in a proper way. However, I think two limitations should be discussed earlier / in more detail:\n\n- The issue with the minimum width $D$ (see weaknesses) should be mentioned in the abstract already and pointed out during the introduction. It seems to be an actual important restriction of the validity of the result.\n\n- There is an issue with the sequence of drawing the random objects of the instance, as the authors point out themselves in lines 123 - 125. As previous work shows, the result can only hold with this particular sequence. While this is of course implicitly captured by the sequence of expectations in Thm. 1.1, I think the authors should point this out when they state Thm. 1.1 already, and not only hidden in the related work part.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- According to the authors, this is the first positive learnability result of this type for arbitrary deep neural networks. This seems to be a major milestone in learning theory for deep networks.\n- The obtained learning algorithm is actually SGD on ReLU networks, so exactly what people use in practice.", "weaknesses": "- The paper is crazily technical already in the main part, not even taking into account the appendix. Within the limited time available for a NeurIPS review, it is impossible to verify mathematical correctness. I tend to believe that this is inherent to the result and not the authors' fault, but I wonder if NeurIPS is actually the right venue to publish such a result. Maybe the authors should submit to a journal instead, where reviewers have enough time to verify mathematical correctness. If submitting to NeurIPS, I think the emphasis should be much more on providing intuitions of the proofs than on technical details.\n- The result is only valid if the network is sufficiently wide enough. Looking through the proof it seems that the required depth $D$ depends with a double-factorial on $n$, which in turn depends on the desired precision $\\epsilon$. This will be astronomically large for any reasonable value of $\\epsilon$. I do not think that any practical neural network can be so wide.\n- Obviously also all other constants seem to be huge / high exponential dependicies on the fixed quantities. But I think this is fine for a theoretical result, it does not concern me as much as the lower bound on the width mentioned above.\n\nMinor comments:\n\n- line 26: I think it would be good to define what you mean by \"ReLU-like\" already here.\n- line 39: you should say that p is a polynomial.\n- line 47: it is confusing to call the neuron n, because n denotes the degree of the polynomials to approximate sigma.\n- line 60: I find this sentence grammatically weird \"Thus, those PTAS can be standard SGD on neural networks\". What do you mean here?\n- line 63: erf not defined.\n- line 65: quasi-polynomial refers to the dependence on epsilon and \\bar{d}, still assuming constant i. Point this out.\n- line 144: what are the a_i in the definition of \\hat(\\sigma)? These are only defined a few lines later, please fix this.\n- line 196: soften -> softened", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review. We will improve the writing according to the outlined suggestions.\n\nFirst, the reviewer says that our paper “seems to be a major milestone in learning theory for deep networks” and does not raise soundness concerns. We believe that this may qualify the paper for a rating better than 4. \n\nWe next address the reviewer’s concerns and questions:\n\n- Dependence on constants: The constant $D$ is of the form $L^{n^i}$ where $L$ is the Lipschitz constant of the activation function. We conjecture that the theorem is correct with respect to any constant. We will clarify it in the final version.\n\n- Non-Realizable setting: You understood correctly. If $1-\\epsilon_0$ fraction of the distribution is realizable by a random network, then our bounds are valid, up to an additive error of $\\epsilon_0$.\n\n- *“How much of a restriction is it to restrict the input data to the boundary of the sphere?”:*\nWe can relax this requirement and assume that the inputs are close to the sphere. This will result in an additional factor in the bounds.\n\n- ReLU-like vs. ReLU: As opposed to ReLU, ReLU-like activations have good polynomial approximations. Hence, our results give better bounds for these functions.\n\n"}, {"review_id": "hbxLFI7LXX", "reviewer": "Reviewer_cQDt", "summary": "The paper examines the extent to which neural networks learn deep models. Given the fact that there almost do not exist any 'rich' families of constant depth random neural networks that are efficiently learnable by some algorithm, the authors assert the existence of an algorithm that approximates these families of networks that are comprised by Lipschitz activation functions. To achieve this, they substitute each activation function with a low degree polynomial approximation (Hermite polynomial), and then show that the approximation is good enough, allowing for a standard SGD on the neural networks to be a PTAS.", "questions": "Please refer to the limitations below.", "limitations": "-The paper does not attempt to make an experiment as a proof of concept. For example it could try several neural networks of constant depth and Lipschitz activations and vary the rest of the hyperparameters randomly. Then there could be some kind of benchmarking across several  neural networks that measures how good the approximation is, while the learning runs in polynomial time. The running time is also interesting in terms of such reporting. \nAlthough the paper is theoretical, it discusses a potential application of such neural networks (their polynomial approximation). This is the reason why it would be interesting to offer a numerical result of the efficiency, accuracy and complexity of learning a polynomial. \n\n-It seems to be inherently difficult to find the polynomial of Th. 1.1 in order to prove the above point. Is this within the scope of this paper, besides the existence result?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-The paper examines the expressivity and learnabilty of random neural networks. This is a fundamental problem in the Theory of Deep Learning and the authors manage to address it by bounding the expected learning time, i.e. the # iterations for determining the weights of the networks approximately (if I undestand correctly Th.1.1.). This allows for a possible impact of the paper in this field. \n\n-From a first reading the results seem new.", "weaknesses": "-The presentation could be improved. The mathematical formulation could be more explained, e.g. with an example of a toy neural network, where the weights and random initialization can be displayed pictorially.\n\n-There could be a clear comparison to the previous approximation attempts (of the literature) to show the novelty in the current PTAS. E.g. in the 1.2. section there is a mention in Chen et al. [7] who provided an algorithm for learning deeper ReLU networks, with complexity polynomial in the input dimension but exponential in the other parameters. The current approach of this paper (from what I understand) considers fixed depth networks and asserts the existence of a polynomial which can be 'close' (approximately) to the learning outcome of the trained neural network: after i iterations, it can approximate it expectedly in 'well' (ideally constantly, as the iterations 'i' tend to infinity). This can be contrasted to previous approaches mentioned in 1.2 about learning depth-3 networks, hardness result of the setting where the target\nnetwork is random and an adversary chooses some input distribution which needs to be learned by the random target network etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review. We will improve the writing according to the outlined suggestions. \n\nWe next address the reviewer’s concerns:\n \n- Experiments: Thanks for the suggestion. We will run experiments and consider whether to add them to the final version.\n\n- Finding the polynomial: It is indeed not clear how to find the polynomial of the theorem. Yet, for the algorithms of the paper, existence is enough.\n"}]

Author rebuttal:

Meta-review: The reviewers have generally agreed that this paper presents a significant contribution to the field of deep learning theory. The paper's main strength lies in its novel approach to learning random Xavier networks of depth, providing a polynomial-time approximation scheme (PTAS) that is distribution-free in its input distribution. This is a significant advancement over previous work, which has been largely limited to one hidden-layer networks.

The reviewers have raised some concerns regarding the presentation and clarity of the paper, suggesting that the authors could provide more intuition behind their results and improve the explanation of their mathematical formulations. However, these concerns do not detract from the overall quality and impact of the paper.

Some reviewers have also suggested that the authors could provide a numerical proof of concept or discuss the practical implications of their results in more detail. While these suggestions could potentially enhance the paper, they are not essential for the acceptance of the paper.

In light of the above, the paper is accepted for publication. The authors are encouraged to take the reviewers' feedback into account when preparing the final version of their paper.
Decision: Accept (poster)