Giving provable guarantees for learning neural networks is a core challenge of machine learning theory. Most prior work gives parameter recovery guarantees for one hidden layer networks, however, the networks used in practice have multiple non-linear layers. In this work, we show how we can strengthen such results to deeper networks -- we address the problem of uncovering the lowest layer in a deep neural network under the assumption that the lowest layer uses a high threshold before applying the activation, the upper network can be modeled as a well-behaved polynomial and the input distribution is gaussian. Understanding the landscape of learning neural networks has been a major challege in machine learning. Various works gives parameter recovery guarantees for simple one-hidden-layer networks where the hidden layer applies a non-linear activation u after transforming the input x by a matrix W, and the upper layer is the weighted sum operator: thus f (x) = a i u(w T i x). However, the networks used in practice have multiple non-linear layers and it is not clear how to extend these known techniques to deeper networks.We consider a multilayer neural network with the first layer activation u and the layers above represented by an unknown polynomial P such that it has non-zero non-linear components. More precisely, the function f computed by the neural network is as follows: f W (x) = P (u(w We assume that the input x is generated from the standard Gaussian distribution and there is an underlying true network (parameterized by some unknown W * ) 1 from which the labels are generated.In this work we strengthen previous results for one hidden layer networks to a larger class of functions representing the transform made by the upper layer functions if the lowest layer uses a high threshold (high bias term) before applying the activation: u(a − t) instead of u(a). Intuitively, a high threshold is looking for a high correlation of the input a with a direction w * i . Thus even if the function f is applying a complex transform after the first layer, the identity of these high threshold directions may be preserved in the training data generated using f .Learning with linear terms in P . Suppose P has a linear component then we show that increasing the threshold t in the lowest layer is equivalent to amplifying the coefficients of the linear part. Instead of dealing with the polynomial P it turns out that we can roughly think of it as P (µX 1 , ..., µX d ) where µ decreases exponentially in t (µ ≈ e −t 2 ). As µ decreases it has the effect of diminishing the non-linear terms more strongly so that relatively the linear terms stand out. Taking advantage of this effect we manage to show that if t exceeds a certain threshold the non linear terms drop in value enough so that the directions w i can be learned by relatively simple methods. We show that we can get close to the w i applying a simple variant of PCA. While an application of PCA can be thought of as finding principal directions as the local maxima of max ||z||=1 E[f (x)(z T x) 2 ], DISPLAYFORM0 If W * has a constant condition number then the local maxima can be used to recover directions that are transforms of w i . Theorem 1 (informal version of Claim 2, Theorem 11). If t > c √ log d for large enough constant c > 0 and P has linear terms with absolute value of coefficients at least 1/poly(d) and all coefficients at most O(1), we can recover the weight vector w i within error 1/poly(d) in time poly(d).These approximations of w i obtained collectively can be further refined by looking at directions along which there is a high gradient in f ; for monotone functions we show how in this way we can recover w i exactly (or within any desired precision. Theorem 2. (informal version of Theorem 5) Under the conditions of the previous theorem, for monotone P , there exists a procedure to refine the angle to precision in time poly(1/ , d) starting from an estimate that is 1/poly(d) close.The above mentioned theorems hold for u being sign and ReLU. 3 When P is monotone and u is the sign function, learning W is equivalent to learning a union of half spaces. We learn W * by learning sign of P which is exactly the union of halfspaces w T i x = t. Thus our algorithm can also be viewed as a polynomial time algorithm for learning a union of large number of half spaces that are far from the origin -to our knowledge this is the first polynomial time algorithm for this problem but with this extra requirement (see earlier work BID12 for an exponential time algorithm). Refer to Appendix B.6 for more details.Such linear components in P may easily be present: consider for example the case where P (X) = u(v T X − b) where u is say the sigmoid or the logloss function. The taylor series of such functions has a linear component -note that since the linear term in the taylor expansion of u(x) has coefficient u (0), for expansion of u(x−b) it will be u (−b) which is Θ(e −b ) in the case of sigmoid. In fact one may even have a tower (deep network) or such sigmoid/logloss layers and the linear components will still be present -unless they are made to cancel out precisely; however, the coefficients will drop exponentially in the depth of the networks and the threshold b.Sample complexity with low thresholds and no explicit linear terms. Even if the threshold is not large or P is not monotone, we show that W * can be learned with a polynomial sample complexity (although possibly exponential time complexity) by finding directions that maximize the gradient of f . Theorem 3 (informal version of Corollary 1). If u is the sign function and w i 's are orthogonal then in poly(1/ , d) samples one can determine W * within precision if the coefficient of the linear terms in P (µ(X 1 + 1), µ(X 2 + 1), µ(X 3 + 1), . . .) is least 1/poly(d)Learning without explicit linear terms. We further provide evidence that P may not even need to have the linear terms -under some restricted cases (section 4), we show how such linear terms may implicitly arise even though they may be entirely apparently absent. For instance consider the case when P = X i X j that does not have any linear terms. Under certain additional assumptions we show that one can recover w i as long as the polynomial P (µ(X 1 + 1), µ(X 2 + 1), µ(X 3 + 1), ..) (where µ is e −t has linear terms components larger than the coefficients of the other terms). Note that this transform when applied to P automatically introduces linear terms. Note that as the threshold increases applying this transform on P has the effect of gathering linear components from all the different monomials in P and penalizing the higher degree monomials. We show that if W * is a sparse binary matrix then we can recover W * when activation u(a) = e ρa under certain assumptions about the structure of P . When we assume the coefficients are positive then these results extend for binary low l 1 -norm vectors without any threshold. Lastly, we show that for even activations (∀a, u(a) = u(−a)) under orthogonal weights, we can recover the weights with no threshold.Learning with high thresholds at deeper layers. We also point out how such high threshold layers could potentially facilitate learning at any depth, not just at the lowest layer. If there is any cut in the network that takes inputs X 1 , . . . , X d and if the upper layers operations can be modelled by a polynomial P , then assuming the inputs X i have some degree of independence we could use this to modularly learn the lower and upper parts of the network separately (Appendix E) Related Work. Various works have attempted to understand the learnability of simple neural networks. Despite known hardness results BID8 ; BID2 , there has been an array of positive results under various distributional assumptions on the input and the underlying noise in the label. Most of these works have focused on analyzing one hidden layer neural networks. A line of research has focused on understanding the dynamics of gradient descent on these networks for recovering the underlying parameters under gaussian input distribution Du et al. FIG1 ; BID10 ; BID16 ; BID14 ; BID17 . Another line of research borrows ideas from kernel methods and polynomial approximations to approximate the neural network by a linear function in a high dimensional space and subsequently learning the same BID15 ; BID8 ; BID7 a) . Tensor decomposition methods BID0 BID9 have also been applied to learning these simple architectures.The complexity of recovering arises from the highly non-convex nature of the loss function to be optimized. The main result we extend in this work is by BID5 . They learn the neural network by designing a loss function that allows a "well-behaved" landscape for optimization avoiding the complexity. However, much like most other results, it is unclear how to extend to deeper networks. The only known result for networks with more than one hidden layer is by BID7 . Combining kernel methods with isotonic regression, they show that they can provably learn networks with sigmoids in the first hidden layer and a single unit in the second hidden layer in polynomial time. We however model the above layer as a multivariate polynomial allowing for larger representation. Another work BID1 deals with learning a deep generative network when several random examples are generated in an unsupervised setting. By looking at correlations between input coordinates they are able to recover the network layer by layer. We use some of their ideas in section 4 when W is a sparse binary matrix.Notation. We denote vectors and matrices in bold face. || · || p denotes the l p -norm of a vector. || · || without subscript implies the l 2 -norm. For matrices || · || denotes the spectral norm and || · || F denotes the forbenius norm. N (0, Σ) denotes the multivariate gausssian distribution with mean 0 and covariance Σ. For a scalar x we will use φ(x) to denote the p.d.f. of the univariate standard normal distribution with mean zero and variance 1 .For a vector x we will use φ(x) to denote the p.d.f. of the multivariate standard normal distribution with mean zero and variance 1 in each direction. Φ denotes the c.d.f. of the standard gausssian distribution . Also define Φ c = 1 − Φ. Let h i denote the ith normalized Hermite polynomial Wikipedia contributors (2018). For a function f , letf i denote the ith coefficient in the hermite expansion of f , that is, DISPLAYFORM1 For a given function f computed by the neural network, we assume that the training samples (x, y) are such that x ∈ R n is distributed according to N (0, 1) and label has no noise, that is, y = f (x).Note: Most proofs are deferred to the Appendix due to lack of space . In this work we show how activations in a deep network that have a high threshold make it easier to learn the lowest layer of the network. We show that for a large class of functions that represent the upper layers, the lowest layer can be learned with high precision. Even if the threshold is low we show that the sample complexity is polynomially bounded. An interesting open direction is to apply these methods to learn all layers recursively. It would also be interesting to obtain stronger results if the high thresholds are only present at a higher layer based on the intuition we discussed.
We provably recover the lowest layer in a deep neural network assuming that the lowest layer uses a "high threshold" activation and the above network is a "well-behaved" polynomial.
{"src": "scitldr-AIC_train", "paper_id": "BkgFqiAqFX"}