We consider the problem of learning a one-hidden-layer neural network: we assume the input x is from Gaussian distribution and the label $y = a \sigma(Bx) + \xi$, where a is a nonnegative vector and  $B$ is a full-rank weight matrix, and $\xi$ is a noise vector. We first give an analytic formula for the population risk of the standard squared loss and demonstrate that it implicitly attempts to decompose a sequence of low-rank tensors simultaneously. 
	
 Inspired by the formula, we design a non-convex objective function $G$ whose landscape is guaranteed to have the following properties:	

1. All local minima of $G$ are also global minima.
 2. All global minima of $G$ correspond to the ground truth parameters.
 3. The value and gradient of $G$ can be estimated using samples.
	
 With these properties, stochastic gradient descent on $G$ provably converges to the global minimum and learn the ground-truth parameters. We also prove finite sample complexity results and validate the results by simulations. Scalable optimization has played an important role in the success of deep learning, which has immense applications in artificial intelligence. Remarkably, optimization issues are often addressed through designing new models that make the resulting training objective functions easier to be optimized. For example, over-parameterization BID19 , batch-normalization BID14 , and residual networks BID12 b) are often considered as ways to improve the optimization landscape of the resulting objective functions.How do we design models and objective functions that allow efficient optimization with guarantees? Towards understanding this question in a principled way, this paper studies learning neural networks with one hidden layer. Roughly speaking, we will show that when the input is from Gaussian distribution and under certain simplifying assumptions on the weights, we can design an objective function G(·), such that[a] all local minima of G(·) are global minima [b] all the global minima are the desired solutions, namely, the ground-truth parameters (up to permutation and some fixed transformation).We note that designing such objective functions is challenging because 1) the natural 2 loss objective does have bad local minimum, and 2) due to the permutation invariance 1 , the objective function inherently has to contain an exponential number of isolated local minima. In this paper we first give an analytic formula for the population risk of the standard 2 loss, which empirically may converge to a spurious local minimum. We then design a novel population loss that is guaranteed to have no spurious local minimum.Designing objective functions with well-behaved landscape is an intriguing and potentially fruitful direction. We hope that our techniques can be useful for characterizing and designing the optimization landscape for other settings.We conjecture that the objective αf 2 + βf 4 12 has no spurious local minimum when α, β are reasonable constants and the ground-truth parameters are in general position. We provided empirical evidence to support the conjecture.Our results assume that the input distribution is Gaussian. Extending them to other input distributions is a very interesting open problem. 2 /2 ) in the following sense 13 . For two functions f, g that map R to R, define the inner product f, g with respect to the Gaussian measure as DISPLAYFORM0 The polynomials h 0 , . . . , h m , . . . are orthogonal to each other under this inner product: DISPLAYFORM1 2 /2 ) , let the k-th Hermite coefficient of σ be defined asσ DISPLAYFORM2 Since h 0 , . . . , h m , . . . , forms a complete orthonormal basis, we have the expansion that DISPLAYFORM3 We will leverage several other nice properties of the Hermite polynomials in our proofs. The following claim connects the Hermite polynomial to the coefficients of Taylor expansion of a certain exponential function. It can also serve as a definition of Hermite polynomials. 13 We denote by Donnell, 2014, Equation 11 .8)). We have that for t, z ∈ R, DISPLAYFORM4 DISPLAYFORM5 The following Claims shows that the expectation E [h n (x)h m (y)] can be computed easily when x, y are (correlated) Gaussian random variables. Claim A.2 ((O'Donnell, 2014, Section 11.2)). Let (x, y) be ρ-correlated standard normal variables (that is, both x,y have marginal distribution N (0, 1) and E[xy] = ρ). Then, DISPLAYFORM6 As a direct corollary, we can compute Ex∼N (0,Id d×d ) σ(u x)γ(v x) by expanding in the Hermite basis and applying the Claim above. Claim A.3. Let σ, γ be two functions from R to R such that DISPLAYFORM7 2 /2 ). Then, for any unit vectors u, v ∈ R d , we have that DISPLAYFORM8 Proof of Claim A.3. Let s = u x and t = v x. Then s, t are two spherical standard normal random variables that are u, v -correlated, and we have that DISPLAYFORM9 We expand σ(s ) and γ(t ) in the Fourier basis and obtain that DISPLAYFORM10 In this section we prove Theorem 2.1 and Theorem 2.2, which both follow from the following more general Theorem. DISPLAYFORM11 2 /2 ), andŷ = a γ(Bx) with parameter a ∈ R and B ∈ R ×d . Define the population risk f γ as DISPLAYFORM12 DISPLAYFORM13 whereσ k ,γ k are the k-th Hermite coefficients of the function σ and γ respectively.We can see that Theorem 2.1 follows from choosing γ = σ and Theorem 2.2 follows from choosing γ =σ 2 h 2 +σ 4 h 4 . The key intuition here is that we can decompose σ into a weighted combination of Hermite polynomials, and each Hermite polynomial influence the population risk more or less independently (because they are orthogonal polynomials with respect to the Gaussian measure).Proof of Theorem A.4. We have DISPLAYFORM14
The paper analyzes the optimization landscape of one-hidden-layer neural nets and designs a new objective that provably has no spurious local minimum.  This paper studies the problem of learning one-hidden layer neural networks, establishes a connection between least squares population loss and Hermite polynomials, and proposes a new loss function. A tensor factorization-type method for leaning one hidden-layer neural netowrk