Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations
Year: 2021

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) = aT (WTx+ b), where x is drawn from the Gaussian distribution, and (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 minimal assumptions.

heading: 1 Introduction
text: The empirical success of deep learning in recent years has led to a flurry of recent works exploring various theoretical aspects of deep learning such as learning, optimization and generalization. A fundamental question in the theory of deep learning is to identify conditions under which one can design provably time-efficient and sample-efficient learning algorithms for neural networks. Perhaps surprisingly, even for the simplest case of a 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
y = f(x) = aT (WTx+ b). (1)
We are given access to a finite amount of samples of the form (xi, yi) drawn i.i.d. from the data distribution, where each xi is comes from the standard Gaussian distribution N (0, I), and yi = f(xi). The goal is to design an algorithm that outputs an approximation of the function f up to an arbitrary error measured in the expected mean squared metric (squared `2 loss). An efficient learning algorithm has running time and sample complexity that are polynomial in the different problem parameters such as the input dimensionality, number of hidden units, and the desired error.
Without any further assumptions on the depth-2 network, efficient learning algorithms are unlikely. The recent work of [DKKZ20] provides evidence by proving exponential statistical query lower bounds (even when x is Gaussian) that rule out a broad class of algorithms.
Several recent works have designed efficient algorithms for depth-2 neural networks in the special setting when the bias term b = 0. One prominent line of work [GLM18, BJW19] 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], or a quasipolynomial dependence when the coefficients {ai : i 2 [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 to certain activations with bias and requires
35th Conference on Neural Information Processing Systems (NeurIPS 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 depth-2 neural networks with general ReLU activations, under the assumption that Wd⇥m has linearly independent columns (hence m  d). In fact, our algorithms can be extended to work under much weaker assumptions on W , that allow for m d (m  O(d`) for any constant ` 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 {ai : i 2 [m]} are nonzero. 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(x) takes the form f̂4 = P i=1 aiw ⌦4 i
where wi are the columns of W and a = (a1, a2, . . . , ). 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].1 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(x) takes the form f̂k = P m i=1 aigk(bi)w ⌦k i
, where gk is a function that may vanish on some of the unknown bi parameters. This creates a hurdle in recovering the corresponding wi. A simple example where the above approach fails is when some of the bi = ±1, since the corresponding rank-1 terms vanish from the decomposition of f̂4. To overcome this obstacle, we first give a precise expression for the function gk(bi) 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 wi 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 a particular hidden node with output (w>
i x+ bi). If bi 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 bi is a large negative constant then the activation is 0 except with probability exponentially small in |bi|. 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 a sign ambiguity for the terms whose bias does not have very large magnitude i.e., we recover ±(w>
i x+ bi) if |bi| is not very large.
To handle the above issue we proceed in two stages. In the first stage we recover the network parameters (up to 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 a linear functions is a 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 g(x) that achieves low mean squared error with respect to the target f(x). The output function g(x) is also a depth-2 ReLU 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̂k 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.
1Tensor decompositions will in fact recover each ReLU activation up to an ambiguity in the sign. However, in the full-rank setting, the correct sign can also be recovered (as we demonstrate later in Theorem 3.1).
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.e., 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.

heading: 1.1 Model Setup and Preliminaries
text: We consider the supervised learning problem with input x 2 Rd drawn from a standard ddimensional Gaussian distribution N (0, Id⇥d) and labels y generated by a neural network y = f(x) = aT (WTx+ b), where a, b 2 Rm, W 2 Rd⇥m and is the element-wise ReLU activation function, i.e., (t) = max(t, 0). We denote the column vectors of W as wi 2 Rd with i 2 [m] and ai as the i’th element of vector a, similarly for b and x. We pose a constraint on magnitudes of a, b,W such that they are all B-bounded for some 1  B  poly(m, d), i.e. kak1, kbk1, kWk1  B, and mini2[m] |ai| 1/B. Furthermore, we assume kwik2 = 1 without loss of generality. If wi are not unit vectors, we can always scale ai and bi to kwikai and bikwik respectively so that wi are normalized. We will denote by (·) the cumulative density function (CDF) of the standard Gaussian distribution. Finally, for a matrix M , we will use sk(M) to denote the kth 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.

heading: 2 Related Work
text: By now there is a vast literature exploring various aspects of deep learning from a 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 to the case of non-zero bias.
The work of [JSA15] proposed a general approach based on tensor decompositions for learning an unknown depth-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 to a large class of distributions provided one has access to the score function. However, for most data distributions computing the score function is a hard task itself. When the input distribution is Gaussian, then the score functions correspond to the Hermite coefficients of the target function f(x) and can be evaluated efficiently. However, the analysis in [JSA15] does not extend to 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 to 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 ReLU 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, CKM20], or quasipolynomial dependence when the coefficients {ai : i 2 [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, GGJ+20, DV21], getting a fully polynomial time algorithm without any assumptions is a challenging open problem, even under Gaussian marginals.
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, JGH21].

heading: 3 Main Results
text: There are two related but different goals that we consider in learning the ReLU network: • Achieves low error: Output a ReLU network g(x) = a0> (W 0>x + b0) such that the L2
error is at most " for a given " > 0 i.e., Ex⇠N (0,Id⇥d)[(f(x) g(x))2]  "2. • Parameter recovery: Output fW,ea,eb, such that each parameter is "-close (up to permuting
the m co-ordinates of a, b 2 Rm and reordering the corresponding columns of W ).
We remark that the second goal is harder and implies the first; in particular, when " = 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 bi p logN , then (w> i x + bi) will be indistinguishable from the linear function w> i x+ b w.h.p.; hence if there are multiple such bi 2 [m] 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 2 [m]} are linearly independent (in a robust sense). Theorem 3.1 (Full-rank setting). Suppose " 2 (0, 1) and N poly(m, d, 1/", 1/sm(W ), B) samples be generated by a ReLU network f(x) = a> (W>x + b) that is B-bounded, and |bi| < c p
log(1/"mdB) for all i 2 [m]. Then there exists an algorithm that runs in poly(N,m, d) time and with high probability recovers eai, ebi, ewi such that kwi ewik2 + |ai eai|+ |bi ebi| < " for all i 2 [m].
The above theorem recovers all the parameters when the biases {bi : i 2 [m]} of each ReLU unit does not have very large magnitude. Moreover even when there are bi of large magnitude, we can learn a depth-2 ReLU network g that achieves low error, and simultaneously recover parameters for the terms that have a small magnitude of bi (up to a potential ambiguity in signs). In fact, our algorithm and guarantees are more general, and can operate under the much milder condition that {w⌦`
i : i 2 [m]} are linearly independent for any constant ` 1; the setting when ` > 1 corresponds to what is often called the overcomplete setting. In what follows, for any constant ` 2 N we use poly
` (n1, n2, . . . ) to denote a polynomial dependency on n1, n2, . . . , and potentially exponential dependence on `. Theorem 3.2. Suppose ` 2 N be a constant, and " > 0. If we are given N i.i.d. samples as described above from a ReLU network f(x) = a> (W>x + b) that is B-bounded then there is an algorithm that given N poly
` (m, d, 1/", 1/sm(W `), B) runs in poly(N,m, d) time and
with high probability finds a ReLU network g(x) = a0> (W 0>x+ b0) with at most m+ 2 hidden units, such that the L2 error Ex⇠N (0,Id⇥d)[(f(x) g(x))2]  "2. Furthermore there are constants c = c(`) > 0, c0 > 0 and signs ⇠i 2 {±1} 8i 2 [m], such that in poly(N,m, d) time, for all i 2 [m] with |bi| < c p log(1/(" ·mdB)), we can recover (eai, ewi,ebi), such that |ai eai|+ kwi ⇠i ewik2 + |bi ⇠iebi| < c0"/(mB).
In the special case of ` = 1 in Theorem 3.2, we need the least singular value sm(W ) > 0 (this necessitates that m  d). This corresponds to the full-rank setting considered in Theorem 3.1. In contrast to the full-rank setting, for ` > 1 we only require that the set of vectors w⌦`1 , w ⌦` 2 , . . . , w ⌦` m
are linearly independent (in a 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 is a 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 = O(d`) for any constant ` > 0. Below, cW denotes the columns of W are ⌧ -smoothed i.e., randomly perturbed with standard Gaussian of average length ⌧ that is at least inverse polynomial (See Section E for the formal smoothed analysis model and result). Corollary 3.3 (Smoothed Analysis). Suppose ` 2 N and " > 0 are constants in the smoothed analysis model with smoothing parameter ⌧ > 0, and also assume the ReLU network f(x) = a> (cW>x + b) is B-bounded with m  0.99 d+` 1
`
. Then there is an algorithm that given
N poly ` (m, d, 1/", B, 1/⌧) samples runs in poly(N,m, d) time and with high probability finds a ReLU network g(x) = a0> (W 0>x+ b0) with at most m+ 2 hidden units, such that the L2 error Ex⇠N (0,Id⇥d)[(f(x) g(x))2]  "2. Furthermore there are constants c, c0 > 0 and signs ⇠i 2 {±1} 8i 2 [m], such that in poly(N,m, d) time, for all i 2 [m] with |bi| < c p log(1/(" ·mdB)), we can recover (eai, ewi,ebi), such that |ai eai|+ kwi ⇠i ewik2 + |bi ⇠iebi| < c0"/(mB).
While our algorithm and the analysis give guarantees that are robust to sampling errors and inverse polynomial error, even the non-robust 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) = a> (W>x + b) where mini2[m] |ai| > 0 and no two columns of W are parallel to each other. Then given samples, the model parameters (ai, bi, wi : i 2 [m]) are identified up to ambiguity in the signs and reordering indices i.e., we can recover {(ai, ⇠ibi, ⇠iwi) : i 2 [m]} for some ⇠i 2 {+1, 1} 8i 2 [m]. Moreover given any (⇠i 2 {+1, 1} : i 2 [m]) such that
mX
i=1
ai (⇠ibi)⇠iwi = mX
i=1
ai (bi)wi, and mX
i=1
aibi (⇠ibi) = mX
i=1
aibi (bi), (2)
we have that the set of parameters ((ai, ⇠ibi, ⇠iwi : i 2 [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 to a valid solution (this corresponds to the d+1 equations in (2)). Even in the case when all the bi = 0, we have non-identifiability due to ambiguities in signs whenever the {wi : i 2 [m]} are not linearly independent for an appropriate setting of the {ai}; 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 f̂k = Ex⇠N (0,I)[f(x)Hek(x)] (with k 2 N) be the k’th Hermite coefficient (this is an order-k tensor) of f(x) = a> (W>x+ b). Then
f̂0 = mX
i=1
ai ⇣ bi (bi) + exp( b 2 i 2 )p
2⇡
⌘ , f̂1 = mX
i=1
ai (bi)wi (3)
8k 2, f̂k = mX
i=1
( 1)k · ai ·Hek 2(bi) · exp( b
2 i
2 )p 2⇡ · w⌦k i
(4)
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 g(bi) of w⌦ki .
We remark that the above lemma may also be used to give an expression for the training objective for depth-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.

heading: 4 Non-robust Algorithm and Analysis
text: Our algorithms for learning the parameters of f(x) = a> (W>x+ b) decompose tensors obtained from the Hermite coefficients {f̂t 2 (Rd)⌦t} 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 errors. For proofs for the following lemmas and claims, please refer to Appendix C.
Our first result is a 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 {(ai, bi, wi) : i 2 [m]} satisfies: (i) ai 6= 0 for all i 2 [m], (ii) {wi : i 2 [m]} are linearly independent. Then given {f̂t : 0  t  4} exactly, Algorithm 1 recovers (with probability 1) the unknown parameters a, 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̂t}. Our algorithm for recovering the parameters estimates different Hermite coefficient tensors {f̂t : 0  t  4} and uses tensor decomposition algorithms on these tensors to first find the {wi : i 2 [m]} up to some ambiguity in signs. We can also recover all the coefficients {bi : i 2 [m]} up to signs (corresponding to the signs of wi ), and all the {ai : i 2 [m]} (no sign ambiguities). This portion of the algorithm extends to higher order `, under a weaker assumption on the matrix W .
Theorem 4.2. Suppose the parameters {(ai, bi, wi) : i 2 [m]} satisfies: (i) no two {wi : i 2 [m]} are linearly dependent and, (ii) for a constant ` 2 N, {w⌦`
i : i 2 [m]} are linearly independent,
(iii) ai 6= 0 for all i 2 [m]. Then given {f̂t : 0  t  2` + 2} exactly, Algorithm 1 in poly`(m, d) time outputs (with probability 1) {âi, ŵi, b̂i : i 2 [m]} such that we can recover the parameters up to a reordering of the indices [m] and up to signs i.e., for some {⇠i 2 { 1, 1} : i 2 [m]} we have âi = ai, ŵi = ⇠iwi and b̂i = ⇠ibi. Furthermore, given exact statistical query access to the distribution N (0, Id⇥d),2 there exists an algorithm that runs in time poly(m, d,B) and outputs a function g(x) such that Ex⇠N (0,Id⇥d) f(x) g(x) 2 = 0.
We now describe the algorithm for general ` 1 (this specializes to the full-rank setting for ` = 1).
Algorithm 1: Algorithm for order `: recover a, b, W given {f̂t : 0  t  2`+ 2} Input: f̂`, f̂`+1, f̂`+2, f̂`+3, f̂2`+1, f̂2`+2; 1. Let T 0 = flatten(f̂2`+1, `, `, 1) 2 Rd `⇥d`⇥d and T 00 = flatten(f̂2`+2, `, `, 2) 2 Rd `⇥d`⇥d2 be
order-3 tensors obtained by flattening f̂2`+1 and f̂2`+2. 2. Set k0 = rank(flatten(f̂2`+1, `, `+ 1, 0)). Run Jennrich’s algorithm [Har70] on T 0 to recover
rank-1 terms {↵0 i u⌦` i ⌦ u⌦` i ⌦ ui | i 2 [k0]}, where 8i 2 [k0], ui 2 Sd 1 and ↵0i 2 R. 3. Set k00 = rank(flatten(f̂2`+2, `, `+ 1, 0)). Run Jennrich’s algorithm [Har70] on T 00 to recover
rank-1 terms {↵00 i v⌦` i ⌦ v⌦` i ⌦ v⌦2 i | i 2 [k00]}, where 8i 2 [k00], vi 2 Sd 1 and ↵00i 2 R. 4. Remove duplicates and negations (i.e., antipodal pairs of the form v and v) from {u1, u2, . . . , uk0} [ {v1, v2, . . . , vk00} to get ew1, ew2, . . . , ewm. 5. Run subroutine RECOVERSCALARS(m, `, { ewi : i 2 [m]}, f̂`, f̂`+1, f̂`+2, f̂`+3) to get {eai,ebi : i 2 [m]}.
6. If ` = 1 (full-rank setting), run Algorithm 3 (FIXSIGNS) on parameters m, f̂1 and (eai,ebi, ewi : i 2 [m]) to get (a0i = eai, b0i, w0i : i 2 [m]). Result: Output { ewi,eai,ebi : i 2 [m]}
2This means that for any function h(x, y) that can be computed in polynomial time, one can obtain Ex,y[h(x, y)] exactly.
Subroutine Algorithm 2 finds the unknown parameters a1, . . . , am 2 R and b1, . . . , bm 2 R given w1, w2, . . . , wm. While Algorithm 1 changes a little when we have errors in the estimates, the subroutine Algorithm 2 remains the same even for the robust version of the algorithm.
Algorithm 2: Subroutine RECOVERSCALARS to recover bi (up to signs) and ai given wi (up to signs) for all i 2 [m]. Input: m, `, ( ewi : i 2 [m]), and tensors T`, T`+1, T`+2, T`+3 which are tensors of orders `, `+ 1, `+ 2, `+ 3 respectively; if ` = 1 then 1. For j 2 {2, 3}, solve the system of linear equation P m
i=1 ⇣j(i)vec( ew ⌦j i
) = vec(Tj) to recover unknowns {⇣j(i) | i 2 [m]};
2. For each i 2 [m], set bi = ⇣3(i)⇣2(i) , and ai = ⇣2(i) · p 2⇡eb 2 i /2.
else 1. For j 2 {`, `+ 1, `+ 2, `+ 3}, solve the system of linear equationP
m i=1 ⇣j(i)vec( ew ⌦j i ) = vec(Tj) to recover unknowns {⇣j(i) | i 2 [m]};
2. For each i 2 [m], qi := argmaxj2{`+1,`+2} |⇣j(i)|, set ebi = ⇣q+1(i)+q·⇣q 1(i) q(i) , and
eai = p 2⇡( 1)q⇣q(i)eb 2 i /2/Heq(bi), as described in (34) (Lemma 4.5).
end Result: Output (eai,ebi : i 2 [m])
The above two algorithms together recover for all i 2 [m], the ai and up to a sign the wi and bi. In the special case of ` = 1 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 IN FULL-RANK SETTING. Input: m, f̂1 2 Rd and estimates ãi, b̃i, w̃i for each i 2 [m]; 1. Solve the system of linear equation P m
i=1 ziãiw̃i = f̂1 to recover unknowns {zi | i 2 [m]}; 2. Set ⇠̃i = sign(zi) for each i 2 [m]. Result: Output (ãi, ⇠̃ib̃i, ⇠̃iw̃i : i 2 [m])
Algorithm 1 decomposes two different tensors obtained from consecutive Hermite coefficients f̂2`+1, f̂2`+2 to obtain the {wi} up to signs. We use two different tensors because the bias bi could make the coefficient of the ith term in the decomposition 0 (e.g., He2` 1(bi) = 0 for f̂2`+1); hence wi cannot be recovered by decomposing f̂2`+1. Hence f̂2`+1 can degenerate to a rank m0 < m tensor, and Jennrich’s algorithm will return only m0 < 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 x 2 R. This implies a separation between roots of consecutive Hermite polynomials or , and establishes a “robust” version that will be useful in Section 5. 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 a value of large magnitude at x. Lemma 4.3 (Separation of Roots). For all k 2 N, x 2 R, max{|Hek(x)|, |Hek+1(x)|} p k!/2.
The following claim shows that Jennrich’s algorithm for decomposing a tensor successfully recovers all the rank-1 terms whose appropriate Hek(bi) 6= 0. This claim along with Lemma 4.3 shows that Steps 2-3 of Algorithm 1 successfully recovers all the {wi : i 2 [m]} up to signs.
Claim 4.4. Let `1, `2 ` and T 2 Rd `1⇥d`2⇥d`3 have a decomposition T =
P m
i=1 ↵iw ⌦`1 i ⌦w⌦`2 i ⌦ w⌦`3
i , with {w⌦` i : i 2 [m]} being linearly independent. Consider matrix M = flatten(T, `1, `2 + `3, 0) 2 Rd `1⇥d`2+`3 , and let r := rank(M). Then Jennrich’s algorithm applied with rank r runs in poly `1+`2+`3(m, d) time recovers (w.p. 1) the rank-1 terms corresponding to {i 2 [m] : |↵i| > 0}. Moreover for each i with |↵i| > 0, we have w̃i = ⇠iwi for some ⇠i 2 {+1, 1}.
The above claim was useful in recovering wi up to a sign ambiguity. The following lemma is useful for recovering ai parameters (no sign ambiguities) and the bi parameters up to sign ambiguity, once we have recovered the wi up to sign ambiguity. It uses various properties of Hermite polynomials along with Lemma 3.5 and Lemma 4.3. Lemma 4.5. Suppose k 2 N, k 2. Suppose for some unknowns , z 2 R with 6= 0, we are given values of j = ( 1)j⇠j Hej(z) 8j 2 {k, k + 1, k + 2, k + 3} for some ⇠ 2 {+1, 1}. Then z, are uniquely determined by
For q := argmax j2{k+1,k+2}
| j |, ⇠z = q+1 + q · q 1
q , = ( 1)q q Heq(⇠z) (5)
A 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 i 2 [m] with ⇠iz = bi and = aie b 2 i /2/ p 2⇡, to show that Step 5 of the algorithm recovers the correct {(ai, ⇠ibi)}i2[m] given the {⇠iwi}i2[m]. Claim 4.6. Given { ewi = ⇠iwi : i 2 [m]} where ⇠i 2 {+1, 1} 8i 2 [m], Step 5 of Alg. 1 recovers {(ai, ⇠ibi, ⇠iwi) : i 2 [m]}.
We now complete the proof of the non-robust analysis for any constant ` 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 : |He2` 1(bi)| > 0} and Q2 = {i : |He2`+1(bi)| > 0}. From Claim 4.4, Step 2 recovers all the rank-1 terms in Q1 with probability 1; hence we obtain in particular {⇠iwi 2 Sd 1 | i 2 Q1} for some signs ⇠i 2 {+1, 1}. Similarly, in Step 3 we recover w.p. 1, the {⇠iwi 2 Sd 1 | i 2 Q2} for some ⇠i 2 {1, 1}. From Lemma 4.3, we know that no x 2 R is a simultaneous root of He2`+1(x), He2`+2(x). Hence Q1 [ Q2 = {1, 2, . . . ,m}. Thus we obtain {⇠iwi 2 Sd 1 : i 2 [m]} in Step 4 for some signs ⇠i 2 {1, 1} for all i 2 [m]. Finally using Claim 4.6, we recover for each i 2 [m], the ai, ⇠ibi 2 R corresponding to ⇠iwi.
Next, in order to recover a function g(x) of zero L2 error we set up a linear regression problem. Given x 2 Rd consider a 2m dimensional feature space (x) where (x)2i = ai (⇠iw>i x + ⇠ibi) and (x)2i+1 = ai ( ⇠iw>i x ⇠ibi). Then is is easy to see that the target network f(x) can be equivalently written as f(x) = ⇤> (x) for some vector ⇤. Hence we can recover another vector of zero L2 error by solving ordinary least squares, i.e, = E[ (x)> (x)]†E[ (x)y].3 Notice that both the expectations can be calculated exactly given exact statistical query access to the data distribution. In Section D.3 we provide a 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.
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 ` = 1. We note that the conditions are satisfied since smin(W ) > 0 and all the ai 6= 0. Theorem 4.2 guarantees that the first 5 steps of Algorithm 1 recovers (with probability 1) for each i 2 [m], ai,ebi = ⇠ibi and ewi = ⇠iwi for some ⇠i 2 {+1, 1}. From Lemma 3.5, we have that
f̂1 = mX
i=1
ai (bi)wi = mX
i=1
z⇤ i ai ewi, for z⇤i = ⇠i (bi) 8i 2 [m],
and (bi) is the Gaussian CDF and restricted to (0, 1). Moreover the {wi : i 2 [m]} are linearly independent. Hence there is a unique solution (z⇤
i : i 2 [m]) to the system of linear equations in the
unknowns (zi : i 2 [m]) in step 6 of Algorithm 1, and e⇠i = ⇠i as required. Hence (ai, ⇠̃iebi, ⇠̃i ewi : i 2 [m]) are the true parameters of the network (up to reordering indices).
3We remark that using Claim D.14, we can further consolidate the terms to get a ReLU network with at most m+ 2 hidden units.
Proof of Identifiability (Theorem 3.4): Theorem 3.4 follows by verifying that the conditions of Theorem 4.2 hold for ` = m. Conditions (i) and (iii) follow from the conditions of Theorem 3.4.
We now verify condition (ii). For a matrix U with columns {ui : i 2 [m]}, the krank(U) (denoting the Kruskal-rank) is at least k iff every k of the m columns of U are linearly independent. Note that krank(U)  rank(U)  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 V ) = min(krank(U) + krank(V ) 1,m).
Non-identifiability of signs when {wi : i 2 [m]} are not linearly independent. Theorem 4.1 shows that when the {wi : i 2 [m]} are linearly independent, the model is identifiable. The following claim shows that even in the special setting when the biases bi = 0 8i 2 [m], whenever the (wi : i 2 [m]) are linearly dependent, the model is non-identifiable (for appropriate (ai : i 2 [m])) because of ambiguities in the signs (Theorem 4.2 also shows it is identifiable up to this sign ambiguity). Claim 4.8. Suppose w1, . . . , wm are linearly dependent. Then there exists a1, . . . , am (not all 0) and signs ⇠1, ⇠2, . . . , ⇠m 2 {±1} with not all +1 such that the ReLU networks f and g defined as
f(x) := mX
i=1
ai (w > i x), g(x) :=
mX
i=1
ai (⇠iw > i x) satisfy f(x) = g(x) 8x 2 Rd.

heading: 5 Robustness Analysis
text: 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 {f̂k}, we can recover the exact network parameters a, b,W (or at least up to signs). In reality, we can only access polynomially many samples in polynomial time, and we will have sampling errors when estimating {f̂k}. Therefore, given data generated from the target network (x1, y1), ..., (xN , yN ), we will approximate f̂k through the empirical estimator
Tk = 1
N
NX
i=1
yiHek(xi) (6)
Observe that Tk is an unbiased estimator for f̂k. We first show using standard concentration bounds that for any ⌘ > 0, with N poly(dk,m,B, 1/⌘) samples, the empirical estimates with high probability satisfies 8` 2 [k], k⇠`kF := kT` f̂`kF  ⌘ (see Appendix D.1). Hence for any constant k, with polynomial samples, we can obtain with high probability, estimates for the tensors {T0, T1, . . . , Tk} that are accurate up to any desired inverse-polynomial error.
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 bi is large in magnitude, the ReLU unit will be indistinguishable from a 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 " > 0, the m hidden ReLU units are split into groups (for analysis)
G = {i 2 [m] | |bi| < O p log(1/(" ·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 wi of the ith ReLU unit can be recovered (up to sign ambiguity) as long its bias bi is not a root of He2` 1. When there is noise, there could be terms i 2 [m] for which bi are not roots of Hek 2(x), and yet their signal can get swamped by the sampling error in the tensor. We can only hope to
recover those k  m components whose corresponding coefficient is above some chosen threshold ⌘1 (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 (sk(·)) of the factor matrices. Hence, for each of step 2 and 3, we argue that recovery is 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 T2`+1 and T2`+2, we use Lemma 4.3 to argue that each i 2 G will have a large coefficient in at least one of these two tensors. Hence we can stitch together estimates { ewi : i 2 G} which are accurate up to a sign and small error. This will in turn be used to recover ai, bi for i 2 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 a linear function. This is obtained by subtracting from estimates T0, T1 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 to signs. In order to use this to learn a good predictor for f(x) we consider solving a truncated linear regression problem in an expanded feature space. At a high level, for each i 2 G, given estimates (eai, ewi,ebi) we consider an expanded feature representation for this unit into an 8-dimensional vector where each coordinate is of the form ⇠i3eai (⇠i1 ewi · x + ⇠i2ebi) for ⇠i1 , ⇠i2 , ⇠i3 2 { 1,+1}.4 Repeating this for every i 2 G it is easy to see that there is a linear function in the expanded space that approximates the part of the function f(x) 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 is an O(d+m) dimensional feature space where f(x) admits a good linear approximation. We then solve a truncated least squares problem in this space to obtain our final function g(x) that approximates f(x) in L2 error.
We will state the main claims and intermediate steps that prove the robustness of the algorithm and establish Theorems D.1, 3.1, 3.2 in Appendix D.

heading: 6 Conclusion
text: 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 in handling bias terms in the ReLU activations. We also proved identifiability under minimal assumptions and adopted the framework of smoothed analysis to establish beyond-worst-case guarantees. The major open direction is to provide similar guarantees for networks of higher depth.

heading: 7 Acknowledgement
text: The last two authors are supported by the National Science Foundation (NSF) under Grant No. CCF1652491, CCF-1637585 and CCF-1934931.

Review summaries:
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.  Like 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.  As 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. 

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.  The main results are: - 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.  - 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). - 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).  The 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. 

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.