Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
Authors: Pranjal Awasthi
Alex Tang
Aravindan Vijayaraghavan
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning theory
polynomial time algorithms
learning ReLU networks
tensor decompositions

Abstract: We present polynomial time and sample efficient algorithms for learning an unknown depth-2 feedforward neural network with general ReLU activations, under mild non-degeneracy assumptions. In particular, we consider learning an unknown network of the form $f(x) = {a}^{\mathsf{T}}\sigma({W}^\mathsf{T}x+b)$, where $x$ is drawn from the Gaussian distribution, and $\sigma(t) = \max(t,0)$ is the ReLU activation. Prior works for learning networks with ReLU activations assume that the bias ($b$) is zero. 

In order to deal with the presence of the bias terms, our proposed algorithm consists of robustly decomposing multiple higher order tensors arising from the Hermite expansion of the function $f(x)$. Using these ideas we also establish identifiability of the network parameters under very mild assumptions.

Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
Pranjal Awasthi
Alex Tang
Aravindan Vijayaraghavan Northwestern University aravindy @ wwwteeowttttoeeeeee
Google Research
Northwestern University alextang @ eunoortweesttmmmedd
srajjlawwstiiggoogle.com google.com
Abstract
We present polynomial time and sample efficient algorithms for learning an un- known depth-2 feedforward neural network with general ReLU activations, under mild non-degeneracy assumptions. In particular, we consider learning an unknown network of the form f(x) = a oW x: + b). where x is drawn from the Gaussian distribution, and (t) = max(t, 0) is the ReLU activation. Prior works for learn- ing networks with ReLU activations assume that the bias b is zero. In order to deal with the presence of the bias terms, our proposed algorithm consists of robustly decomposing multiple higher order tensors arising from the Hermite expansion of the function (z). Using these ideas we also establish identifiability of the network parameters under minimal assumptions.
Introduction
The empirical success of deep learning in recent years has led to flurry of recent works exploring various theoretical aspects deep learning such as learning, optimization and generalization. A fundamental question in the theory of deep learning is identify conditions under which can design provably time-efficient and sample-efficiee learning algorithms for neural networks. Perhaps surprisingly, even for the simplest case of depth-2 feedforward neural network, the learning question remains unresolved. In this work we make progress on this front by studying the problem of learning an unknown neural network of the form
(1) We are given access to a finite amount of samples of the form (xt, y:) drawn i.i.d. from the data distribution, where each x; is comes from the standard Gaussian distribution NN,,, 7), and y f(x)). The goal is to design an algorithm that outputs an approximation the function ff up to an arbitrary error measured in the expected mean squared metric (squared &g loss). An efficient learning algorithm has running time and sample complexity that are polynomial in the diffcrent problem parameters such the input dimensionality, number of hidden units, and the desired error.
y= f(x) = ao x b).
Without any further assumptions on the 2epth-2 network, efficient learning algorithms are unlikely. The recent work of [DKKZ20] provides evidence by proving exponential statistical query lower bounds (even when & is Gaussian) that rule out broad class algorithms.
Several recent works have designed efficient algorithms for depth-2 neural networks in the special setting when the bias term b O. One prominent line of work [GLM18, BJW 19] give polynomial time algorithms under the non-degeneracy assumption that the matrix W has full-rank, Another body of work relaxes the full-rank assumption by designing algorithms that incur an exponential dependence on the number of hidden units [DKKZ20, CKM20, GK19), J. or quasipolynomial dependence when the coefficients {a; E [m]) are all non-negative [DK20]. There is little existing literature on learning neural networks in the presence of the bias term. A notable exception is an approach based on computing "score functions" [JSA15] that applies certain activations with bias and requires
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

various assumptions that are not satisfied by the ReLU function. The diminished expressivity of neural networks without the bias terms leads to the following compelling question:
Can we design polynomial time algorithms even in the presence of bias terms in the ReLU units?
We answer the question affirmatively by designing efficient algorithms for learning 2epth-2 neural networks with general ReLU activations, under the assumption that W Wdxm has linearly independent columns (hence m I d). In fact, our algorithms can be extended to work under much weaker assumptions on W, that allow for m >> d (m I (dd)) for any constant E 2 1) in a natural smoothed analysis setting considered in prior works [GKLW19] (see Theorem 3.2 and Corollary 3.3). An important consequence of our techniques is the fact that the network parameters are identifiable up to signs, as long as no two columns of W are parallel, and all the {a; : E [m]] are non- zero. Furthermore we show that this ambiguity in recovering the signs is inherent unless stronger assumptions are made.
Conceptual and technical challenges with bias terms. Similar to prior works [GKLW19, JSA15], our techniques rely on the use of tensor decomposition algorithms to recover the parameters of the network. In the absence of any bias, it can be shown that the 4th Hermite coefficient of the function f(z) takes the form fA = Ei=1 a, where wi are the columns of W and a = (a1, a2,... .o....... :)- When the columns of W are linearly independent, existing algorithms for tensor decompositions in the full-rank setting can be used to recover the parameters [Har70]. However, when bias terms are present, there are several challenges that we highlight below.
In the presence of biases the kth Hermite expansion of f(xx) takes the form fx = EE= 0ggg% (be Jusk where gu is a function that may vanish on some of the unknown b, parameters. This creates a hurdle in recovering the corresponding wy A simple example where the above approach fails is when some of the b, +1, since the corresponding rank-1 1 terms vanish from the decomposition of fa- To overcome this obstacle, we first give a precise expression for the function gi (b:) involving the (k 2)th Hermite polynomial (see Lemma 3.5). We then design an algorithm that decomposes multiple tensors obtained from Hermite coefficients to recover the parameters. We use various properties of Hermite polynomials to analyze the algorithm e.g., the separation of roots of consecutive Hermite polynomials is used to argue that each wy is recovered from decomposing at least one of the tensors.
Secondly, in the presence of the bias terms, recovery of all the parameters (even up to sign ambiguities) may not even be possible from polynomially many samples. For instance, consider particular hidden node with output ar (w: x + ). If 6, is a large positive number then it behaves like a linear function (always active). Hence if multiple bis are large positive numbers then one can only hope to recover a linear combination of their corresponding weights and biases. On the other hand if by is a large negative constant then the activation is O except with probability exponentially small in [bg]. We cannot afford a sample complexity that is exponential in the magnitude of the parameters. Furthermore, when the columns of W are not linearly independent, the tensor decomposition based method will only recover good approximations up to sign ambiguity for the terms whose bias does not have very large magnitude i.e., we recover [w: x + b.) if [6:] is not very large.
To handle the above issue we proceed in two stages. In the first stage we recover the network parameters (up signs) of all the "good" terms, i.e., hidden units with biases of small magnitude. To handle the "bad" terms (large magnitude bias) we show that linear functions is good approximation to the residual function comprising of the bad terms. Based on the above, we show that one can solve a truncated linear regression problem to learn a function (()) that achieves low mean squared error with respect the target (x) The output function (xx) is also depth-2 ReL.U network with at most two additional hidden units than the target network.
There are several other technical challenges that arise in the analysis sketched above, when there are sampling errors due to using only a polynomial amount of data (for example, the tensors obtained from fü may have some rank-1 terms that are small but not negligible, that may affect the robust recovery guarantees for tensor decompositions). We obtain our robust guarantees by leveraging many useful properties of Hermite polynomials, and a careful analysis of how the errors propagate.
'Tensor decompositions will in fact recover each ReLU activation up to ambiguity in the sign. However, in the full-rank setting, the correct sign also be recovered (as demonstrate later in Theorem 3.1).
2

---

The rest of the paper is organized as follows. We present preliminaries in Section 1.1 followed by related work in Section 2. We then formally present and discuss our main results in Section 3. In Section 4 we present our main algorithm and analysis in the population setting, i.c., under the assumption that one has access to infinite data from the distribution. We then present the finite sample extension of our algorithm in Section 5 that achieves polynomial runtime and sample complexity.
1.1 Model Setup and Preliminaries
We consider the supervised learning problem with input E Rd drawn from standard d- dimensional Gaussian distribution .N (0, Idxa) and labels y generated by a neural network y = f()) = a o x + b), where a. b E R W E < and is the element-wise ReLU activation function, i.e., (1) max(t, 0). We denote the column vectors of W wa E TRd with E [m]] and o, as the i'th element of vector similarly for b and z. We pose a constraint on magnitudes of a, b, W such that they are all B-bounded for some S B S poly(m, d), i.e. ||a]|so ||b|] oo. |[ llso S B, and min |a:| 2 1/B. Furthermore, we assume ||uc;|2 = 1 without loss of generality. If wy are not unit vectors, can always scale a, and b, to ||ws:|/e and b
||ar.] respectively so that wy are normalized.
We will denote by ((-) the cumulative density function (CDF) of the standard Gaussian distribution. Finally, for matrix M. we will use 8% (M) to denote the kthh largest singular value of M.
For introduction and further preliminaries regarding poly(-) notation, basics of Hermite polynomials and tensor decomposition, please refer to Appendix A.
2
Related Work
By now there is vast literature exploring various aspects of deep learning from theoretical perspective. Here we discuss the works most relevant in the context of our results. As discussed earlier, the recent works of [GLM18, BJW19, GKLW19] provide polynomial time algorithms for learning depth-2 feedforward ReLU networks under the assumption that the input distribution is Gaussian and that the matrix W is full rank. Some of these works consider a setting where the output is also a high dimensional vector [BJW19, GKLW19], and also consider learning beyond the Gaussian distribution. However, these works do not extend the case of non-zero bias.
The work of [JSA15] proposed a general approach based on tensor decompositions for learning an unknown 2 neural network that could also handle the presence of the bias terms. The tensor used in the work of [JSA15] is formed by taking the weighted average of a "score" function evaluated on each data point. In this way their approach generalizes a large class of distributions provided one has access to the score function. However, for most data distributions computing the score function hard task itself. When the input distribution is Gaussian, then the score functions correspond to the Hermite coefficients of the target function fxx and can be evaluated efficiently. However, the analysis in [JSA15] does not extend the case of ReLU activations for several reasons. Their technique needs certain smoothness and symmetry assumptions on the activations that do not hold for ReLU. These assumptions also ensure that all the terms in the appropriate tensor are non-zero. We do not make such assumptions, and tackle one of the main challenges by showing that one can indeed recover a good approximation
the network by analyzing multiple higher order tensors. Furthermore, the authors in [JSA15] assume that the biases, and the spectral norm of W are both bounded by a constant. As a result they do not handle the case of biases of large magnitude where some of the ReI.U units mostly function as linear functions (with high probability).
There have also been works on designing learning algorithms for neural networks without assumptions on the linear independence of columns of W. These results incur an exponential dependence on either the input dimensionality or the number of parameters in the unknown network [DKKZ20, CKM20J, or quasipolynomial dependence when the coefficients (a, : i E [m]] are all non-negative [DK20]. In particular, the result of [CKM20] provides a learning algorithm for arbitrary depth neural networks under the Gaussian distribution with an "FPT"" guarantee: its running time is polynomial in the dimension, but exponential in the number of ReLU units. Given the recent correlational statistical query lower bounds on learning deep neural networks [DKKZ20, 2G)+ DV21], getting a fully polynomial time algorithm without any assumptions challenging open problem, even under Gaussian marginals.
3

---

Polynomial time algorithms with fewer assumptions and beyond depth-2 can be designed if the activation functions in the first hidden layer are sigmoid functions [GK19]. Finally, there is also extensive literature on analyzing the convergence properties of gradient descent and stochastic gradient descent for neural networks. The results in this setting implicitly or explicitly assume that the target function is well approximated in the Neural Tangent Kernel (NTK) space of an unknown network. Under this assumption these results show that gradient descent on massively overparameterized neural networks can learn the target [APVZ14, Dan17, DFS16, AZLS19, DZPS19, ADH 19, LXS* 19, CB18, JGH21J.
3
Main Results
There are two related but different goals that we consider in learning the ReLU network:
Achieves low error: Output a ReLU network g(x) a' (W"T x + b¹) such that the L2 error is at most ε for a given é >> 0 i.e. Ex-N((, (() - =(x)) s
Parameter recovery: Output W, ā, b, such that each parameter is s-close (up to permuting the m co-ordinates of a, E !h and reordering the corresponding columns of W).
We remark that the second goal is harder and implies the first; in particular, when E = 0, the second goal corresponds to identifiability of the model. However in some cases, parameter recovery may be impossible to achieve (see later for some examples) even though we can achieve the goal of achieving low error. As we have seen earlier, given N samples if b, >> vlog N, then (w, b4) will be indistinguishable from the linear function wt x: + w.h.p.; hence if there with large magnitude, the best we can hope to do is recover the sum of all those linear terms. Our first result shows that this is the only obstacle when we are in the full-rank or undercomplete setting i.e. {wi : i E [m]] are linearly independent (in a robust sense).
multiple such b; E [m]]
Theorem 3.1 (Full-rank setting). Suppose & E (0.1) and N Z poly(m, d. 1/e, 1/ (W), B) samples be generated by ReLU network f(x) = a o( x b) that is B-bounded, and [bx] <
<//og(1/emdl) for all i E [m]. Then there exists an algorithm that runs in poly(N, m, d) time
and with high probability recovers ā. by, w. such that I|w, w + la; - ā,l + 1b. - bil < E for all i [m].
The above theorem recovers all the parameters when the biases (4. : : E [m]] of each ReLU unit does not have very large magnitude. Moreover even when there are b, of large magnitude, we can learn a depth-2 ReLU network g that achieves low error, and simultancously recover parameters for the terms that have a small magnitude of b; (up potential ambiguity in signs). In fact, our algorithm and guarantees are more general, and can operate under the much milder condition that {wfe i E [m]] are linearly independent for any constant 2 1; the setting when E > corresponds to what is often called the overcomplete setting. In what follows, for any constant & E NN we use poly,(n,, .))...) to denote a polynomial dependency on 11, ......, and potentially exponential dependence on e.
Theorem 3.2. Suppose E E N be a constant, and > O. If we given N i.i.d. samples as described above from a ReLU network f(z) = a o( x + b) that is B-bounded then there is an algorithm that given N 2 poly:(m, d, d/,, 1/ 8m (WO)), B) runs in poly(N) m, d) time and with high probability finds a ReLU network g(x) a' ( x + +b)) with at most m + 2 hidden units, such that the L2 error Ez-Ni0,Jexa)ll (I g(x))) < Sea Farthermore there are constants =<(E)= > 0, > O and signs & E (+1) Vi E [m], such that in poly(N, d) time, for all E [m] with [ba] < Leyloog cooooo///( m)] we can recover (ū,, Ws bi), such that la, āsl + -|ws - E
|b: - Ebb,, < dee/(mB).
In the special case of 1 in Theorem 3.2, we need the least singular value 8m (W) > 0 (this neces- sitates that m I d). This corresponds to the full-rank setting considered in Theorem 3.1. In contrast to the full-rank setting, for f >>1 1 we only require that the set of vectors w 00 ..... m are linearly independent (in robust sense), which one can expect for much larger values of m typically. The following corollary formalizes this in the smoothed analysis framework of Spielman and Teng [ST04], which popular paradigm for reasoning about non-worst-case instances [Rou20]. Combining the above theorem with existing results on smoothed analysis [BCPV19] implies polynomial time

---

learning guarantees for non-degenerate instances with m Odd+) for any constant &> 0. Below, W denotes the columns of W are r-smoothed i.e., randomly perturbed with standard Gaussian of average length 7 that is at least inverse polynomial (See Section E for the formal smoothed analysis model and result).
Corollary 3.3 (Smoothed Analysis). Suppose é E N and > are constants in the smoothed analysis model with smoothing parameter T > 0, and also assume the ReLU network f(x) = T No(W x b) is B-bounded with m S (.9-((+)-1). Then there is an algorithm that given N 2 polye(m, d, 1/s, B, 1,1/T) samples runs in poly Ooly(N, m, d) time and with high probability finds ReLU network g(x) a' ( I x+ f/) with at most m + 2 hidden units, such that the L2 error <²² Furthermore there are constants c' >> O and signs & E E (xxN((o.)xxa((((()) - g(x) = I
[+13 Vi E [m], such that in poly(N, m, d) time, for all i E [m]] with [0,| < <<vlog(1/(e (aa()/((emBB)) we can recover (āz, W; b,). such that aa, a,l + ||0c - E,0i l2 + bb - E,b, < c'e/(mB).
While our algorithm and the analysis give guarantees that are robust to sampling errors and inverse polynomial error, even the non-robus, analysis has implications and, implies identifiability of the model (up to ambiguity in the signs) as long as no two rows of W are parallel. Note that in general identifiability may not imply any finite sample complexity bounds.
Theorem 3.4 (Partial Identifiability). Suppose we are given samples from a ReLU network f(x) = + b) where min |a:] > and no two columns of W are parallel to each other. Then given samples, the model parameters (a,, by, w; i E [ml] are identified up to ambiguity in the signs and reordering indices i.e., we can recover {(a;, E.bs,,sb,,p Eows)) i E [m]] for some
T (W TTT
x
& E [++,-111 -1} Vi [m].
Moreover given any (5: E [+1,-11 : E [mm] such that
m
Σ a. (.,((b))u,, and Σ (.,b = m
m
m
Σ
a. (a,D(E
(bb))((b)..
we have that the set of parameters ((az, Eabs; Erw; E [m]) also gives rise to the same distribution.
The above theorem shows that under a very mild assumption on W, the parameters can be identified up to signs. However, this ambiguity in the signs may be unavoidable the second part of the Theorem 3.4 shows that any combination of signs that match the zeroth and first Hermite coefficient gives rise a valid solution (this corresponds to the d + equations in (2)). Even in the case when all the 6. = 0, we have non-identifiability due to ambiguities in signs whenever the {w; : i E [m]] are not linearly independent for an appropriate setting of the {a:]: see Claim 4.8 for a formal statement. On the other hand, Theorem 4.1 gives unique identifiability result in the full-rank setting (as there is only one setting of the signs that match the first Hermite coefficient in the full-rank setting).
Our results rely on the precise expressions for higher order Hermite coefficients of f(x) given below.
Lemma 3.5. Let fr = EE-NN Hex (with k E N) be the k t'th Hermite coefficient (this is an order-k tensor) of f(x) = a (W xx b). Then
m
6 exp(
m
fo = Σ a. (b,((b,) +
f1
Σ
a
(b.))
(3)
2-T
63 exp(
Vk 2 2, fn = > 1- a. Hee- Hex)2(b))
(4)
v 2
We prove this by considering higher order derivatives and using properties of Hermite polynomials. A key property we use here is that the k &'th derivative of a standard Gaussian function is itself multiplied by the k'th Hermite polynomial (with sign flipped for odd k:). This significantly simplifies the expression for the coefficient (bb)) of go
We remark that the above lemma may also be used to give an expression for the training objective for 2 ReLU networks, analogous to the result of [GLM18] for ReLU activations with no bias, that provides an expression as a combination of tensor decomposition problems of increasing order. Please refer to Appendix B for more details.
5

---

4 Non-robust Algorithm and Analysis
Our algorithms for learning the parameters of f(z)= = o( = + b) decompose tensors obtained from the Hermite coefficients {Le E (RR))() of the function f. In this section, we design an algorithm assuming that we have access to all the necessary Hermite coefficients exactly (no noise or sampling errors). This will illustrate the basic algorithmic ideas and the identifiability result. However with polynomial samples, we can only hope to estimate these quantities up to inverse polynomial accuracy. In Section 5 we describe how we deal with the challenges that arise from emrors. For proofs for the following lemmas and claims, please refer to Appendix C.
Our first result is polynomial time algorithm in the full-rank setting that recovers all the parameters exactly.
Theorem 4.1 (Full-rank non-robust setting). Suppose the parameters (ar wx) i [m]] satisfies: (i) 0, + for all i E [m]. (ii) (w; : E [m]} are linearly independent. Then given {fe 0 S t I 4) exactly, Algorithm I recovers (with probability 1) the unknown parameters b and W in poly (m, d) time.
See Theorem 3.1 for the analogous theorem in the presence of errors in estimating the Hermite coefficients {f.). Our algorithm for recovering the parameters estimates different Hermite coefficient tensors (fz : 0 S & S 4} and uses tensor decomposition algorithms these tensors first find the {w, : E [m]] up to some ambiguity in signs. We can also recover all the coefficients (b, : E [m]] up to signs (corresponding the signs of w; ) and all the {a; : E [m]] (no sign ambiguities). This portion of the algorithm extends to higher order f, under a weaker assumption on the matrix W.
Theorem 4.2. Suppose the parameters {(ai, bs; wx) ; E [m]] satisfies: (i) no two {w; : E [m]]
are linearly dependent and, (ii) for a constant & E N, fw i E [m]] are linearly independent, (iii) * 0 for all E [m]. Then given (fe 0 S t S 2 + 2} exactly, Algorithm 1 in poly, (m. d) time outputs (with probability 1) {ā;, w; b, : E [m]] such that we can recover the parameters up to a reordering of the indices [m]] and up to signs i.e., for some {&: E {-1,11} : : [m]} we have à = as, Wy E,w; and b, = E,b,, Furthermore, given exact statistical query access to the distribution (0, laxd).² there exists an algorithm that runs in time poly(m, d, B) and outputs
function g(x) such that En-N(0, (f(z) g(z))² O.
We now describe the algorithm for general / (this specializes the full-rank setting for l = 1).
Algorithm I: Algorithm for order E: recover a, b, W given (ʃ+ : 5
Input: fe, fe41, Se43, f2441, F2e12:
1. Let T" = flatten( e, 1) R xdx and T" = flatten((a22,, Rdd xaxx x be
order-3 tensors obtained by flattening fae-1 and f2442.
Set k' = rank (ollfffatten
f, f 1, 0)). Run Jennrich's algorithm [Har70] on T" to recover 8 u, E [k]]]. where Vi E [k'], u, E Sd-1 and af E R. e, 2- 1, 0)). Run Jenmrich's 's algorithm [Har70] on T" to recover
@ u 3. Set k" = rank (allttttten(feee
rank-l terms {a @6
rank-1 terms {a." @ o & 002 | E [R""], where Vi E [K'], E gd-1 and a E R. Remove duplicates and negations (i.e., antipodal pairs of the form e and -i) from
{ur u2. ... ug! } U fer, uz..... uw } to get W1. W2.... Wm.
5. Run subroutine RECOVERSCALARS(/
(w, : E [m]], fe, fer ferz, se+a) to get
{ā,, by : E [m]].
6. l = 1 (full-rank setting), run Algorithm 3 (FIXSIGNS) on parameters m, fi and (ā,, by, W. : E [m]) to get (af- = ā,, b/, w/ : E [m]). Result: Output (wi, az by : E [m]}
"This means that for any function h(r, y) that can be computed in polynomial time, one can obtain Ez.y [1(2, y)] exactly.

---

Subroutine Algorithm 2 finds the unknown parameters d1;-.., Om R and b 01,..., nm E IR given W1, wf,...., WWm- While Algorithm changes a little when we have errors the estimates, the subroutine Algorithm 2 remains the same even for the robust version of the algorithm.
Algorithm 2: Subroutine RECOVERSCALARS to recover by (up to signs) and a; given wy (up to signs) for all i [m].
Input: m, e, (w; ; E [ml), and tensors T,, T2,1, Te42, Te+3 which are tensors of orders E 2.8+1.4 1, + 2, respectively;
if l =0=11 then
1. For (2,3), solve the system of linear equation Σ Ei=1 (y(1) =ve(TT)) to recover unknowns {()(t) i E [m]]:
(a( and a; (2(i) v 22Te For each E [m]] set Sa(o))
else
1. For (1,8+1, 2 3), solve the system of linear equation
Σ (i))vec( vec(T,) to recover unknowns {cr i [m]]:
For each E [m]. 9i == ((0+1 (s)(),, set U, = - (1) and (1())
ã. = 2 ( He (b:), as described in (34) (Lemma 4.5).
end
Result:
Output (a,, b; E [ml)
The above two algorithms together recover for all E [m]], the a; and up a sign the w; and 6;, In the special case of f = which we refer to as the full-rank setting, we can also recover the correct signs, and hence recover all the parameters.
Algorithm 3: Algorithm FIX SIGNS FULL-RANK SETTING.
Input: m, fi e Rd and estimates ā, b,, W for each E [m]]
1. Solve the system of linear equation >i zāūū;; fi to recover unknowns (z: | E [m]]; Set E, sign(1) 2,) for each E [m]]
Result: Output (ā., &b., E,w;; : i [m])
Algorithm decomposes two different tensors obtained from consecutive Hermite coefficients f2c+1, fe0+2 to obtain the {wi} up to signs. We use two different tensors because the bias 6, could make the coefficient of the ith term in the decomposition 0 (e.g.. He2-- (b.) = for f2e+1): hence w; cannot be recovered by decomposing f2411 Hence f2441 can degenerate to rank m' < m tensor, and Jennrich's 's algorithm will return only m' < m eigenvectors that correspond to non-zero eigenvalues.
The following lemma addresses this issue by showing that two consecutive Hermite polynomials can not both take small values at any point E R. This implies separation between roots of consecutive Hermite polynomials or and establishes a "robust" version that will be useful in Section Moreover, this lemma also shows that when [x] is not close to 0, at least one out of every two consecutive odd Hermite polynomials takes value of large magnitude at x.
Lemma 4.3 (Separation of Roots). For all k E N, x R, max (ex())) [H<{)()))] 2 /kl/22
The following claim shows that Jennrich's algorithm for decomposing tensor successfully recovers all the rank-1 terms whose appropriate (b)(b,) # O. This claim along with Lemma 4.3 shows that Steps 2-3 of Algorithm I successfully recovers all the {w; i E [m]] up signs.
Claim 4.4. Let E1, la > l and E IR xd xd'2 x u Dts with Fu : [m]] being linearly independent. Consider matrix M = flatten(T l l2 0) E ER x and let r= runk(M). Then Jennrich's 's algorithm applied with rank r runs in poly polyerter+s, (m, d) time recovers (w.p. 1) the rank-1 terms corresponding to {i [m] : | > 0). Moreover for each with lai) > O, we have w. Eyw, for some E (+1.-1}.
have a decomposition T E a.w, 00 Z w 2tttt2 222
7

---

The above claim was useful in recovering wi up to sign ambiguity. The following lemma is useful for recovering a, parameters (no sign ambiguities) and the b; parameters up to sign ambiguity, once we have recovered the w; up to sign ambiguity. uses various properties of Hermite polynomials along with Lemma 3.5 and Lemma 4.3.
Lemma 4.5. Suppose k E N, A: 2 2. Suppose for some unknowns G, E IR with 3 o O, we are given values of 73 (-1) Blee) Vj [k, k + 1, + 2, + 33 for some E {+1,-1} Then z, B are uniquely determined by
For Q = argmax Insl. ç 7 + + Ta JE(K+1
8 = (-1)
7/ Heg(Ez)
(5)
7/
robust version of this lemma (see Section D.2.2) will be important in the robust analysis of Section 5.
The following claim applies the above lemma for each E [m]] with & = b, and = a,e 42/2 /v2, to show that Step 5 of the algorithm recovers the correct
(.bz)) given the Claim 4.6. Given {w; = E,w, : i E [m]] where & E {+1,1} Vi E [m], Step of Alg. recovers
{(a E,b,, (rw))) [m]].
We now complete the proof of the non-robust analysis for any constant f 8 0.
Proof of Theorem 4.2. The proof follows by combining Claim 4.4 and Claim 4.6, along with
Lemma 4.3. Let Q1 {i |Heze- (b:)l >> 0} and Q2 = {i |ezz41 > 0}. From Claim 4.4, Step recovers all the rank-1 terms in Q1 with probability 1; hence we obtain in particular {+1, -1.. Similarly, in Step 3 we recover w.p. 1, the (5ww; E sd-1 E Q2) for some & E 11.
[Erw; E Sd-1 E Q1) for some signs
From Lemma 4.3, know that no IR is simultaneous root of He24+1 (z:). Hez)+2(z). Hence Q1 U Q2 = {1, 2, m... Thus we obtain {Eaw; E gd-1: E [m]] in Step 4 for some signs & (1, for all i E [m]. Finally using Claim 4.6, we recover for each E [m]] the a, E,b, E R corresponding to E,w.
Next, in order to recover a function g(x) of zero I.2 error we set up linear regression problem. Given I E Rd consider 2m dimensional feature space d(x) where o(x);; (E,, x fxbe) E.b:). Then is is easy see that the target network f()) can be cquivalently written as f(x) = 3 ((x) for some vector 8r. Hence we can recover another vector 3 of zero L2 error by solving ordinary least squares, i.e, 8 E[Ø(=) [[=)) ((ó(r)))) Notice that both the expectations can be calculated exactly given exact statistical query access to the data distribution. In Section D.3 provide more general analysis of the above argument with finite sample analysis that will let us approximate f((x) up to arbitrary accuracy in the presence of sampling errors.
and ((x)2++1 a-
We now complete the proof of recovery in the full-rank setting.
Proof of Theorem 4.1. We first apply Theorem 4.2 (and its above proof) with E 1. We note that the conditions satisfied since smin(W) > 0 and all the a, # 0. Theorem 4.2 guarantees that the first steps of Algorithm recovers (with probability 1) for each E [m]. 0; by = Eiby and wi = Eww; for some & E (+1,1]. From Lemma 3.5, we have that
A Σ
Σ aaa for 2 = (b.( Vi E [m].
and (b;) is the Gaussian CDF and restricted to (0, 1). Moreover the (w, E [m]] are linearly
independent. Hence there is unique solution (zī : E (m]) to the system of linear equations in the
unknowns (z+ : i e [m]) in step 6 of Algorithm 1, and & & as required. Hence (a,, E,b,, EnW, i [m]) are the true parameters of the network (up to reordering indices).
We remark that using Claim D.14, we can further consolidate the terms to get ReLU network with at most + hidden units.
8

---

Proof of Identifiahility (Theorem 3.4): Theorem 3.4 follows by verifying that the conditions of Theorem 4.2 hold for 8 f= m. Conditions (i) and (iii) follow from the conditions of Theorem 3.4.
We now verify condition (ii.. For matrix U with columns {u; [m]]] the krank(U)) (denoting the Kruskal-rank) is at least iff every & of the m columns of are linearly independent. Note that krank(U') S rank(U)= S m. The krank increases under the Khatri-Rao product.
Fact 4.7 (Lemma A.4 of [BCV14]). For two matrices U, V with m columns, krank(U C V) = min((rank(UU) + krank(V) 1,
Non-identifiability of signs when {wa: : [m]] are not linearly independent. Theorem 4. shows that when the {w, following claim shows that even in the special setting when the biases b; = 0 Vi E [m²], whenever the (w, i (ml) are linearly dependent, the model is non-identifiable (for appropriate (a, i [ml)) because of ambiguities in the signs (Theorem 4.2 also shows is identifiable up to this sign ambiguity).
[m]] are linearly independent, the model is identifiable. The
Claim 4.8. Suppose wi,.... Wm are linearly dependent. Then there exists a1 a1..... with not all +1 such that the ReLU networks f and g defined
:. am (not all 0)
and signs E1, ,m. {+1}
m
m
f(x) = Σ aoo x), g(0) Σ
(5 x)) satisfy f(x) = Vx Rd.
Rd.
5 Robustness Analysis
In this section, we prove Theorem 3.1 and Theorem 3.2 which give polynomial time and sample complexity bounds for our algorithms. In the previous section we showed that given oracle access to (fie), can recover the exact network parameters a, b, W (or at least up signs). In reality, only access polynomially many samples in polynomial time, and we will have sampling errors when estimating {fa]. Therefore, given data generated from the target network (T1, W1), (NN MN). we will approximate fi through the empirical estimator
N Th
N y: He (z;)
Σ 1=1
Observe that Ti is an unbiased estimator for fu. We first show using standard concentration bounds that for any 77 > O, with N 2 poly(d', m, B, 1/n) samples, the empirical estimates with high probability satisfies VŁ [k], |kElle = [Te - fells constant k, with polynomial samples, we can obtain with high probability, estimates for the tensors TT..T...... .......... ] that are accurate up any desired inverse polysmmpo error.
17 (see Appendix D. Hence for any
Overview of Analysis. The error in the tensors Tk introduces additional challenges that we described in Section 1. The analysis is technical and long, but we now briefly describe the main components.
(i) Recall from Section 1, that when there are errors, it may not even be possible to recover the parameters of some ReLU units! In particular when the bias b, large magnitude, the ReLU unit will be indistinguishable from simple linear function. It will contribute negligibly to any of the higher order Hermite coefficients, and hence will be impossible to recover them individually (especially if there are multiple such units). For a desired recovery error >> units are split into groups (for analysis)
O, the m hidden ReLU
G {i E [m]
|b,] < O( O(Vlog(L/(= mdB)))), and P = (1.2..... m. \G
We aim to recover all of the parameters of the units corresponding to G up to signs. For the terms in P. we will show the existence of a linear function that approximates the total contribution from all the terms in P.
(ii) The tensor decomposition steps (steps 2-3) are simpler in the no-noise setting: the parameter w; of the ith ReLU unit can be recovered (up to sign ambiguity) as long its bias b; is not a root of Heze-1. When there noise, there could terms E [m] for which by are not roots of He)-2(x), and yet their signal can get swamped by the sampling error in the tensor. We can only hope to

---

recover those m components whose corresponding coefficient is above some chosen threshold "n (the other terms are considered as part of the error tensor). However a technical issue that arises is that the robust recovery guarantees for tensor decomposition algorithms lose polynomial factors in different parameters including the least singular value (s)(+) of the factor matrices. Hence, for each of step and 3, we argue that recovery possible only if the coefficient of the corresponding term is significantly large, and this may give reasonable estimates for only a subset of these m terms with coefficients >
(iii) When decomposing two consecutive tensors T2e+1 and T2c+2, we use Lemma 4.3 to argue that each i G will have a large coefficient in least one of these two tensors. Hence we can stitch together estimates (i; i E G) which are accurate up to a sign and small error. This will in turn be used to recover (4;; by for i G, with properties of Hermite polynomials used to ensure that the errors do not propagate badly.
(iv) We argue that the other ReLU units in P [m] G can be approximated altogether using linear function. This is obtained by subtracting from estimates To, Ti with the corresponding terms from G.
(v) The above arguments let us compute good approximations to the parameters for the units in G, but only up signs. In order use this to learn good predictor for f fz) we consider solving a truncated linear regression problem in an expanded feature space. At a high level, for each i E G, given estimates (ā,, W7 by) we consider an expanded feature representation for this unit into an 8-dimensional vector where each coordinate of the form (E, ü; x + & b.) for Si Si, (1-1,+1 +1). Repeating this for every i E G it is easy to see that there is linear function in the expanded space that approximates the part of the function / (ar) that depends on units in G. Combining with the previous argument that the units in P [m] \ G can be approximated by a linear function in the original feature space, we deduce that there an O + m) dimensional feature space where fa)) admits a good linear approximation. We then solve truncated least squares problem in this space to obtain our final function g(x) that approximates f(x) in La error.
We will state the main claims and intermediate steps that prove the robustness of the algorithm and establish Theorems D. 3.1, 3.2 in Appendix D.
6 Conclusion
In this paper, we designed polynomial time algorithms for learning depth-2 neural networks with general ReLU activations (with non-zero bias terms), and gave provable guarantees under mild non-degeneracy conditions. The results of this work are theoretical in nature, in trying to understand whether efficient algorithms exist for learning ReLU networks; hence we believe they do not have any adverse societal impact. We addressed multiple challenges for learning such ReLU network with non-zero bias terms throughout our analyses, that may be more broadly useful handling bias terms in the ReLU activations. We also proved identifiability under minimal assumptions and adopted the framework of smoothed analysis to establish beyond-worss worst-caee guarantees. The major open direction is to provide similar guarantees for networks of higher depth.
7
Acknowledgement
The last two authors are supported by the National Science Foundation (NSF) under Grant No. CCF- 1652491, CCF-1637585 and
References
[ADH*19] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019. 4
*While this portion of the algorithm works more generally with ambiguities in the sign of a. b., and w., in our case, the sign ambiguity of w, and b, are coordinated, and the sign of the a, are also recovered correctly; hence 2- 2-dimensional vector suffices in this case. Moreover the terms can be consolidated to get equivalent ReLU network with most |G| + 2 hidden units (see Claim D.14 and Lemma D.1.).
10

---

[APVZ14]
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning polynomials with neural networks. In International conference on machine learning, pages 1908- 1916. PMLR, 2014. 4
[AZLS19] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via parreeeraettiii.tiioon.. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[BBV04] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. 32
[BCMV14] A. Bhaskara, M. Charikar, A. Moitra, and A. Vijayaraghavan. Smoothed analysis of Proceedings the the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '10 14, page 594-603, New York, NY, USA, 2014. Association for Computing Machinery. 14, 18, 35
tensor decompositions.
[BCPV19] Aditya Bhaskara, Aidao Chen, Aidan Perreault, and Aravindan Vijayaraghavan. Smoothed analysis in unsupervised learning via decoupling. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2019. 4, 35
[BCV14] Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan. Uniqueness of tensor decompositions with applications to polynomial identifiability. In Maria Florina Balcan, Vitaly Feldman, and Csaba Szepesvári, editors, Proceedings of The 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 742-778, Barcelona, Spain, 2014. PMLR. 9, 14
[Bha97]
Rajendra Bhatia. Matrix Analysis, volume 169. Springer, 1997. 30
[BJW19]
Ainesh Bakshi, Rajesh Jayaram, and David Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268.
PMLR, 2019. 1,
[CB18]
Lénaïc Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 3040-3050, Red Hook, NY, USA, 2018. Curran Associates Inc. 4
[CKM20]
Sitan Chen, Adam R Klivans, and Raghu Meka. Learning deep relu networks is fixed- parameter tractable. arXiv preprint arXiv:2009. 00222009913322. /35/2, 2020. 1,3
[7n
Amit Daniely, Sgd learns the conjugate kernel class of the network. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 2419-2427, Red Hook, NY, USA, 2017. Curran Associates Inc. 4
[DFS16]
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view expressivity. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016. 4
[DK20]
Haass Diakonikolas and Daniel M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 184-195. IEEE, 2020. 1,3
[DKKZ20] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. In Conference on Learning Theory, pages 1514-1539. PMLR, 2020. 1,
[DV21] Amit Daniely and Gal Vardi. From local pscudorandom generators to hardness of learning. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pages 1358 1394. PMLR, 2021. 3
[DZPS19] Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent prov- ably optimizes waertearaettrrized neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019, 4

---

[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. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020. 3
[GK19]
Surbhi Goel and Adam Klivans. Learning neural networks with two nonlinear layers in polynomial time. In Conference Learning Theory, pages 1470-1499. PMLR, 2019.
1,
[GKLW19] Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural net- works with symmetric inputs. In International Conference on Learning Representations, 2019. 2.3
[GLMI8] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In International Conference on Learning Representations, 2018.
1, 3,5
[GVX14]
Navin Goyal, Santosh Vempala, and Ying Xiao. Fourier pea and robust tensor de- composition. STOC 14, page 584-593, New York, NY, USA, 2014. Association for Computing Machinery. 14
[Har70]
R. Harshman. Foundations of the parafac procedure: Models and conditions for an "explanatory" multi-model factor analysis. 1970. 2, 6, 13,
[JG21]] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks (invited paper). In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021, page New York, NY, USA, 2021. Association for Computing Machinery. 4
[JGKA19]
Majid Janzamin, Rong Ge, Jean Kossaifi, and Animashree Anandkumar. Spectral learning matrices and tensors. Foundations and Trends in Machine Learning, 12, 11 2019. 13
[JS115]
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non- convexity: Guaranteed training of neural networks using tensor methods. arXiv preprint arXiv:1506.08473. 2015. 2,
[LXS+119 19] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Bus E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[Moi18]
Ankur Moitra. Algorithmic Aspects of Machine Learning. Cambridge University Press, 2018. 14
[MRT18]
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018. 32
[O'D14]
Ryan O' O'Donnell, Analysis of Boolean Functions. Cambridge University Press, USA. 2014. 14
[Rou20]
Tim Roughgarden. Beyond the Worst-Case Analysis of Algorithms. Cambridge Univer- sity Press, 2020. 4, 12
[ST04]
Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. ACM, 51(3):385-463, 2004. 4, 35
[Tur50]
Paul Turán. On the zeros of the polynomials of legendre. Casopis pro pēstování matematiky fyssiky, 15(3):113-122 1950. 16
[Vij20]
Aravindan Vijayaraghavan. Beyond the Worst-Case Analysis of Algorithmss chapter
Efficient Tensor Decomposition. In [Rou20], 2020. 13, 17,
12


Reviews:
[{"review_id": "nlQWRsgtDw1", "reviewer": "Reviewer_MHqc", "summary": "Essentially all existing provable guarantees for learning neural networks over Gaussian inputs focus on activations without a bias term. This submission gives a polynomial-time algorithm for (parameter and PAC) learning one hidden layer neural networks with ReLU activations and nonzero biases over Gaussians when the hidden weight matrix is well-conditioned. In fact their guarantee is more general: even if the hidden weight matrix is ill-conditioned/not full rank, if for some degree k, the k-th tensor powers of the hidden weight vectors are well-conditioned, then their algorithm runs in time exponential in \\ell.\n\nLike many previous algorithms in this literature, theirs is based on tensor decomposition of suitable Hermite coefficients of the network. Just as in the zero-bias case, the k-th Hermite coefficient of the network turns out to be the low-rank tensor given by a linear combination of k-th tensor powers of the hidden weight vectors. But unlike in the zero-bias case where the coefficients are given by the output layer weights, in the nonzero-bias case, each of these coefficients is additionally multiplied by a factor given by a certain function g_k(b_i) of the corresponding bias b_i (see Lemma 3.4). These coefficients can be quite small, and this poses several technical challenges that this paper overcomes.\n\nAs a corollary of their result and known results on the condition number of collections of tensor powers of *smoothed* vectors, they also get a guarantee for learning one hidden layer networks with biases in a smoothed setting.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The general approach of tensor decomposing Hermite coefficients is by now very standard in this line of  work. The main technical innovation in this paper is showing how to deal with components in the tensor which have small coefficient because g_k(b_i) is small. \n\nThe idea is fairly simple. g_k(b_i) turns out to be, up to a sign, He_{k-2}(b_i) * gamma(b_i), where gamma is the pdf of N(0,1), so g_k(b_i) can be small either because He_{k-2}(b_i) is small, or because |b_i| is very large so that the corresponding neuron barely ever or almost always activates. The latter case is not too hard to deal with, because the sum of all neurons for which |b_i| is large essentially behaves like a linear function. Handling the former case is arguably the most interesting part of the paper.\n\nTheir strategy is to aggregate estimates for the hidden weight vectors by decomposing *two tensors*, namely the Hermite coefficients at degree k and k+2; the punchline is that at least one of He_{k-2}(b_i) and He_k(b_i) must be non-negligible, so provided |b_i| is not too large, the coefficient of the corresponding rank-1 component in at least one of the two tensors will be sufficiently large.\n\nThere is a decent amount of technical work that goes into implementing these ideas, and overall it's a solid, well-written result. The particular problem they address was a well-known drawback of existing papers on learning shallow nets over Gaussians, so it's nice that a slight modification of existing tensor-based approaches suffices to handle nonzero biases in the well-conditioned case. Another nice feature is that they make explicit the observation that these tensor-based approaches don't need to assume the weight vectors are well-conditioned, but merely that their tensor powers are. This is a folklore fact to people familiar with tensor decomposition, but to my knowledge I don't think it was ever pointed out in any of the papers on learning neural nets using tensor decomposition.\n\nThe only criticism is that the practical significance is limited, given the Gaussianity assumption and the way in which it's used by looking at Hermite coefficients, but I think it's a solid theoretical contribution nevertheless.\n\nMinor comments:\n- Line 31: \"designing algorithm\" -> \"designing algorithms\"\n- Line 32: the citation of [GK19] is a bit odd as that paper focuses on x's from the unit ball\n- Line 56: \"we first show give\" -> \"we first give\"\n- Line 98: \"we wll\" -> \"we will\"\n- Line 147: \"Given the recent statistical query\" -> \"Given the recent correlational statistical query\"\n- Line 151: again, not sure if [GK19] is relevant here\n- Line 180: there should be a pointer to A.1 for the definition of this poly_ell notation\n- Supplement eqs. (18), (24), (25): check formatting of brackets\n- Supplement eq. (21) ||...|| should be |...|, and similarly for subsequent lines", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the limitations of their work. The result is primarily of theoretical interest, and I don't see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LjnSAralB2h", "reviewer": "Reviewer_4QxN", "summary": "This paper improves upon existing work on learning two-layer relu networks by considering a bias term. The paper presents polynomial time efficient algorithms for this learning task, states the required assumptions, and provides theoretical guarantees.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "1. Regarding the motivation of studying the learning problem in the presence of the bias term, it is stated in the introduction that “The diminished expressivity of neural networks without the bias terms leads to the following compelling question:..”. By concatenating a 1 to the feature vector x, we can achieve the same expressivity without a bias term (though this new vector won’t be Gaussian now). I think the motivation for the bias term needs further justification.\n\n2. Is learning planted weights useful in practice? What would be some applications? In my opinion, a discussion on this would improve the paper for a wider audience.\n\n3. I think this paper is well-written and the assumptions and results are clearly stated. My biggest concern is around the motivation of this work.\n\n4. I think some numerical simulation results to verify the theoretical results could also be useful.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "EIBDC85vrij", "reviewer": "Reviewer_yvHw", "summary": "This paper gave a polynomial time and sample efficient algorithm for learning a two layer ReLU neural network with bias terms under standard Gaussian distribution. The result does not requires the weights $w_i$'s to be linearly independent. Instead, for any constant $\\ell,$ as long as $w_i^{\\otimes \\ell}$'s are linearly independent, the algorithm can learn the network with time complexity and sample complexity exponential in $\\ell$ and polynomial in other parameters. The algorithm relies on decomposing multiple higher order tensors ($O(l)$-order) arising from the Hermite expansion of the ground truth label function. It's also proved that the network is identifiable as long as no two weight vectors are parallel. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I think this is a good theory paper that designed a tensor decomposition algorithm for learning two layer ReLU nets with bias terms. Most of the previous works along this line do not consider bias terms. The bias terms do bring some new challenges into the analysis. I believe the ideas and techniques in this paper is useful in the theoretical study of ReLU nets with bias terms. \n\nThe algorithm proceeds by first estimating several high order tensors of the weight vectors (with order $O(\\ell)$), and then decompose these tensors to recover the weight vectors. With the recovered weight vectors, the second layer coefficients and bias terms can also be recovered. The bias terms in the ReLU indeed brings some challenges. First, the algorithms needs to recover the weights from multiple higher order tensors instead of a single one as in the bias-free setting. Second, when a bias term is high, it's impossible to estimate the corresponding weight vectors using polynomial number of samples. So the authors divided the weights into two groups, one group with relatively small bias and the other group with large bias; then recovered the weights in the first group, and fitted the second group using a linear function. \n\nMy main concern for this paper is that the analysis is restricted into the Gaussian inputs. It does not seem to be able to generalize to other distributions because it strongly relies on the Hermite polynomials. Also, these tensor decomposition algorithms are usually not very effective in real network training. \n\nThat being said, I still think this is a solid theory paper that studied an important problem. The techniques developed in this paper can be useful in the general study of ReLU nets with bias terms.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4WxRAukXu70", "reviewer": "Reviewer_pfsw", "summary": "The paper gives a polynomial-time algorithm for learning depth-2 neural networks with the ReLU activation and bias terms in the realizable setting w.r.t. the square loss. The result assumes Gaussian marginals and certain assumptions on the weights matrix W. Assumptions of this nature are required due to known harness results. Prior works on efficient learning of depth-2 networks either assume that there is no bias or require some assumptions on the activation function that are not satisfied by the ReLU function. Thus, the algorithm shown in this paper is the first efficient algorithms for learning depth-2 ReLU networks with bias.\n\nThe main results are:\n- Assume that the input distribution is Gaussian, the parameters of the target network are bounded, and the smallest singular value of W^{\\odot \\ell} for some constant \\ell is at least inverse polynomial, then the algorithm runs in polynomial time in all relevant parameters (and in exponential time in \\ell) and finds w.h.p. a depth-2 network that approximates the target network. If the bias terms of the target network are not too large, then the algorithm also recovers the parameters of the target network. If the bias terms are large then recovering (some of) the parameters is not possible. Where \\ell=1 the assumption on W^{\\odot \\ell} implies that W has full rank. Where \\ell>1 the requirement may allow the number of hidden neurons m to be significantly larger than the input dimension d. \n- The authors show that the above assumption on W^{\\odot \\ell} holds w.h.p. in the smoothed-analysis setting, namely, where the target weights matrix is slightly perturbed with a random i.i.d. gaussian noise. Hence, in the smoothed-analysis setting the assumption on W^{\\odot \\ell} is not required. In this case, the number of hidden neurons can be m=O(d^\\ell) and the running time of the algorithm is exponential in \\ell (and polynomial in the other parameters).\n- Another consequence of the analysis, is that if the weights in the second layer are non-zero, and there are no two parallel weight vectors in the fist layer, then the parameters of the target network are uniquely identifiable (not necessarily in polynomial time).\n\nThe algorithm is obtained in two steps. First, assuming that the Hermite coefficients are already known, the authors give an algorithm for recovering the parameters. This algorithm is non-robust since in reality the coefficients are not known, and we have to estimate them (with some errors) from the training set. In the second step the authors give the robust algorithm, that uses an unbiased estimator for the Hermite coefficients obtained from the training set. The algorithm relies on Jennrich’s algorithm for tensor decomposition.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The problem studied in the paper is natural and interesting. Indeed, a similar problem has been already studied in several prior works, but the prior results do not handle the standard setting of ReLU activations with bias terms. The assumptions in the paper are reasonable. Some assumptions on the input distribution and on the weight matrix are required in order to obtain an efficient algorithm, and all prior results also include similar assumptions. Moreover, the fact that the assumption on W^{\\odot \\ell} holds w.h.p. in the smoothed-analysis setting suggests that it is likely to hold in real-world settings.\n\nThe paper considers the realizable setting, where we have y_i=f(x_i) for a target network f. However, the paper does not discuss whether the results can be extended to a non-realizable setting, where we have y_i=f(x_i)+\\xi_i for some noise \\xi_i. The robust algorithm tolerates errors in the estimation of the Hermite coefficients, which occur since we estimate the coefficients using a polynomial number of samples. What happens in the non-realizable setting where the errors in the estimates of the coefficients are also affected by \\xi_i ? \n\nOverall, I think that the results in the paper are significant and recommend acceptance. \n\nSome minor comments:\n- Line 56: “show give”\n- Line 104: v_u -> v_i\n- In lines 147-148 the authors mention recent SQ lower bounds for learning deep networks with Gaussian marginals. There is also a recent hardness result for improper learning of neural networks with Gaussian marginals (Amit Daniely and Gal Vardi, From Local Pseudorandom Generators to Hardness of Learning), which holds for all algorithms.\n- Line 468: “if and if”\n- Lines 490 and 495: “A.5” appears as a subscript\n- Line 829: \\tilde{W} instead of \\hat{W}\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A solid progress in a well studied line of research
Decision: Accept (Poster)