Learning One-hidden-layer Neural Networks on Gaussian Mixture Models with Guaranteed Generalizability
Authors: Hongkang Li
Shuai Zhang
Meng Wang
Venue:  (2021)
Keywords: neural networks
generalization
Gaussian mixture model
sample complexity
learning algorithm

Abstract: We analyze the learning problem of fully connected neural networks with the sigmoid activation function for binary classification in the teacher-student setup, where the outputs are assumed to be generated by a ground-truth teacher neural network with unknown parameters, and the learning objective is to estimate the teacher network model by minimizing a non-convex cross-entropy risk function of the training data over a student neural network. This paper analyzes a  general and practical scenario that the input features follow a Gaussian mixture model of a finite number of Gaussian distributions of various mean and variance. We propose a gradient descent algorithm with a tensor initialization approach and show that our algorithm converges linearly to a critical point that has a  diminishing distance to the ground-truth model with guaranteed generalizability. We characterize the required number of samples for successful convergence, referred to as the sample complexity,  as a function of the parameters of the Gaussian mixture model. We prove analytically that when any mean or variance in the mixture model is large, or when all variances are close to zero, the sample complexity increases, and the convergence slows down, indicating a more challenging learning problem. Although focusing on one-hidden-layer neural networks, to the best of our knowledge, this paper provides the first explicit characterization of the impact of the parameters of the input distributions on the sample complexity and learning rate.

Under review as a conference paper at ICLR 2021
LEARNING ONE-HIDDEN-LAYER NEURAL NETWORKS ON GAUSSIAN MIXTURE MODELS WITH GUARAN- TEED GENERALIZABILITY
Anonymous authors Paper under double-bling blind review
ABSTRACT
We analyze the learning problem of fully connected neural networks with the sigmoid activation function for binary classification in the teacher-student setup, where the outputs are assumed to generated by ground-truth teacher neural network with unknown parameters, and the learning objective is to estimate the teacher network model by minimizing a non-convex cross-entropy risk function of the training data over a student neural network. This paper analyzes general and practical scenario that the input features follow a Gaussian mixture model of a finite number of Gaussian distributions of various mean and variance. We propose a gradient descent algorithm with a tensor initialization approach and show that our algorithm converges linearly to critical point that has diminishing distance to the ground-truie truth model with guaranteed generalizability. We characterize the required number of samples for successful convergence, referred as the sample complexity, function of the parameters of the Gaussian mixture model. We prove analytically that when any mean or variance the mixture model large, or when all variances are close to zero, the sample complexity increases, and the con- vergence slows down, indicating a more challenging learning problem. Although focusing mne-hidden-lane layer neural networks, to the best of our knowledge, this paper provides the first explicit characterization of the impact of the parameters the input distributions the sample complexity and learning rate.
INTRODUCTION
Deep neural networks (LeCun et al., 2015) have demonstrated superior empirical performance in various applications such as speech recognition (Krizhevsky et al., 2012) and computer vision (Graves et al., 2013; He et al., 2016). Despite the numerical success, the theoretical underpin of learning neural networks is much less investigated. One bottleneck for the wide acceptance of deep learning in critical applications is the lack of the theoretical generalization guarantees, i.e., why a model learned from the training data would achieve high accuracy on the testing data.
This paper studies the generalization performance of neural networks in the "teacher-student setup, where the training data are generated by a teacher neural network, and the learning is performed on student network by minimizing the empirical risk of the training data. This teacher-student setup has been studied in the statistical learning community for long time (Engel & Broeck, 2001; Seung et al., 1992) and applied to neural networks recently (Goldt et al., 2019a; Zhong et al., 2017 7b;a; Zhang et al., 2019; 2020b: Fu et al., 2020; Zhang et al., 2020a). Assuming that the student network has the same architecture the teacher network, the existing generalization analyses mostly focus on one-hidden-layer networks, because the optimization problem already nonconvex, and the analytical complexity increases tremendously when the number of hidden layers increases.
One critical assumption of most works this line that the input features follow the standard Gaus- sian distribution. Although other distributions are considered in (Du et al., 2017: Ghorbani et al.. 2020: Goldt et al., 2019b; Li & Liang, 2018; Mei et al., 2018b; Mignacco et al., 2020; Yoshida & Okada, 2019), the generalization performance beyond the standard Gaussian input is less investi- gated. On the other hand, the learning performance clearly depends on the input data distribution. (LeCun al., 1998) states that the learning method converges faster if the inputs are whitened to

---

Under review as a conference paper at ICLR 2021
be the standard Gaussian. Batch normalization (loffe & Szegedy, 2015) modifies the mean and variance in each layer and is a popular practical method to achieve a fast and stable convergence. Various explanations such as (Bjorck et al., 2018; Chai et al., 2020; Santurkar et al., 2018) have been proposed to explain the enormous success of Batch normalization, but little consensus exists on the exact mechanism.
This paper provides a theoretical analysis of learning me--hddee-llaye neural net- works when the input distribution follows a Gaussian mixture model containing an arbitrary number of Gaussian distributions with arbitrary mean and variance. The Gaussian mixture model has been employed in many applications such as data clustering and unsupervised learning (Dasgupta, 1999; Figueiredo & Jain, 2002; Jain, 2010), and image classification and segmentation (Permuter et al., 2006). The parameters of the mixture model can be estimated from data by the EM algorithm (Redner & Walker, 1984) or the moment-based method (Hsu & Kakade, 2013), with theoretical performance guarantees, see, e.g., (Ho & Nguyen, 2016; Ho et al., 2020; Dwivedi et al., 2020a:b).
Contributions:
For the binary classification problem with the cross entropy loss function, this paper proposes gradient descent algorithm with tensor initialization to estimate the weights of the one-hidden-layer fully-connected neural network. Our algorithm converges to critical point linearly, and the returned critical point converges to the ground tround-truth model at rate of v log n/n, where d is the dimension of the feature, and n is the number of samples. We also characterize the required number of samples for accurate estimation, referred to as the sample complexity, as function of d. the number of neurons K, and the input distribution. Our explicit bounds imply (1) when the absolute value of any mean in the Gaussian mixture model increases from zero, the sample complexity increases, and the algorithm converges slower, indicating that it will be more challenging to learn model with a small test error; (2) The same phenomenon happens when any variance in the mixture model increases to infinity from a certain positive value, or if all the variances in the mixture model approach zero. Our results indicate that the training converges faster and requires a less number of samples if the input data are zero mean with certain non-zero variance. This can be viewed as one theoretical explanation in one-hiddens our knowledge, this paper provides the first theoretical and explicit characterization about how the mean and variance of the input distribution affect the sample complexity and learning rate.
for the success of Batch normalization. Moreover, to the best of
1.1 RELATED WORK
Learning over- parameterized neural networks. One line of theoretical research on the learning performance considers the over parameterized setting where the number of network parameters is greater than the number of training samples. (Bousquet& & Elisseeff, 2002; Hardt et al., 2016; Keskar et al., 2016; Livni et al., 2014; Neyshabur et al., 2017: Rumelhart et al., 1988; Soltanolkotabi et al., 2018; Allen-Zhu et al., 2019a). (Allen-Zhu -Zhu et al., 2019b; Du al., 2019 Zou & Gu, 2019) show the deep neural networks can fit all training samples in polynomial time. The optimization problem has no spurious local minima (Livni et al., 2014: Zhang et al., 2016; Soltanolkotabi et al., 2018), 8), and the global minimum of the empirical risk function can be obtained by gradient descent (Li & Yuan, 2017: Du et al., 2018b; Zou et al., 2020). Although the returned model can achieve a zero training error, these works do not discuss whether it achieves small test error not. (Allen-Zhu et al., 2019a; Li & Liang, 2018) analyze the generalization error by characterizing the training error and test error separately. Still, there is no guarantee that a learned model with a small training error would have a small test error. (Cao & Gu, 2019) provides the bounds of the generalization error of the learned model by stochastic gradient descent (SGD) in deep neural networks, based on the assumption that there exists a good model with small test error around the initialization of the SGD algorithm, and no discussion is provided about how find such an initialization. In contrast, our tensor initialization method in this paper provides an initialization that is close to the ground-truth teacher model such that our algorithm can find this model with a zero test error.
Generalization performance with the standard Gaussian input. In the teacher-student setup of one-hidden-layer neural networks, (Brutzkus & Globerson, 2017; Du et al., 2018a; Ge et al., 2018; Liang et al., 2018; Li & Yuan, 2017; Shamir, 2018; Safran & Shamir, 2018; Tian, 2017) consider the ideal case of an infinite number of training samples so that the training and test accuracy coincide and can be analyzed simultaneously. When the number of training samples is finite, (Zhong et al., 2017b;a) characterize the sample complexity, i.c., the required number of samples, of learning one-hidden-layer fully connected neural networks with smooth activation functions and propose
2

---

Under review as a conference paper at ICLR 2021
gradient descent algorithm that converges to the ground-truth model linearly. (Zhang et al., 2019; 2020b) extend the analyses to the non-smooth ReLU for fully-connected and convolutional neural networks, respectively. (Zhang et al., 2020a) analyzes the generalizability of graph neural networks for both regression and binary classification problems. (Fu et al., 2020) analyzes the cross entropy loss function for binary classification problems. Compared with other common loss functions such as the squared loss, the cross entropy loss function is harder to analyze due to the complicated forms and the saturation phenomenon of its Gradient and Hessian (Fu et al., 2020).
Theoretical characterization of learning performance from other input distributions. (Du et al., 2017) considers rotationally invariant distributions, but the results only apply to a perceptron (i.e., single-node network). (Mei et al., 2018b) analyzes the generalization error of one-hidden-layee neural networks in the mean-field limit trained on a large class of distributions, including mix- ture of Gaussian distributions with the same mean. The results only hold in the high-dimensional region where both the number of neurons K and the input dimension are sufficiently large, and no sample complexity analysis is provided. (Li & Liang, 2018) studies the generalization error of wver-parameterized one-hidden-laye
networks when the data come from mixtures of well-separated distribution, but the separation requirement excludes Gaussian distributions and Gaussian mixture models. (Yoshida& & Okada, 2019) analyzes the Plateau Phenomenon that the decrease of the risk slows down significantly partway and speeds up again in one-hidden-layer neural networks with in- puts drawn from a single Gaussian with an arbitrary covariance. (Goldt et al., 201 1019b; 2020) analyze the dynamics of learning one-hidden-layee -layer networks with SGD when the inputs are drawn from wide class of generative models. (Mignacco et al., 2020) provides analytical equations for SGD evolution in perceptron trained on the Gaussian mixture model. (Ghorbani et al., 2020) considers inputs with low-dimensional structures and compares neural networks with kernel methods.
Vectors are in bold lowercase, matrices and tensors in are bold uppercase. Scalars are in normal fonts. For instance, Z is a matrix, and z is a vector. z; denotes the i-th entry of z, and Zz.j denotes the (i. entry of Z. [K] (K > 0) denotes the set including integers from 1 to K. Ia E Rdxd and e; represent the identity matrix in Iddd and the i-th standard basis vector, respectively. We use (Z) to denote the i-th largest singular value of Z. A t O means A is positive semi-definite (PSD) matrix. The gradient and the Hessian of a function f(W) are denoted
Notations:
by V (WW and V J(W) respectively. The outer product of vectors z; E IR"',, E [1], is defined
as T = 21 @ ... X 21 E RT X." with T.. = (z1);, (Z1) Given a tensor T E Xnggx and matrices A E xdd, B E R22 C e ReaXda, the (i,, 22, iy) entry of the tensor B, C) is given by
n1 12
n3
ΣΣΣ
T
A Beg Cig.ss
(1)
1 &/2
1/2
We follow the convention that f(x) = (z)))) (or M(g(1), (((()))) means that f(r) increases at most, least, or in the order of g(x)), respectively.
PROBLEM FORMULATION
We consider a one-hidden- fully connected neural network where all the weights in the second layer have the same fixed value. This structure is also known as the committee machine, see, e.g., (Aubin et al., 2018; Monasson & Zecchina, 1995; Schwarze & Hertz, 1992; 1993). Let E Rd denote the input features. Let K 2 1 be the number of neurons in the hidden layer. Following the teacher-student setup, see e.g., (Fu et al., 2020), the output labels are generated by teacher neural network with unknown ground- weights wi E Rd (j E [K]. Let W = [w] ..... will E _a contain all the weights. Let 6, (W*) denote the i-th largest singular value of W Let (W") K (. and define 7) = 1=
- (- The nonlinear activation function here is the sigmoid function d(x)= I+) We consider binary classification, and the binary output y is generated
(.(W')
by the teacher committee machine through
1 K K
Ply 1/x) H(W x)
Σ
oww x). j=1
(2)
3

---

Under review as a conference paper at ICLR 2021
Learning is performed over student neural network that has the same architecture the teacher network, and its weights are denoted by W E Rd*k Given n pairs of training samples (a the empirical risk function is
(w Σ (W;
where ((W; ys) is the cross-entropy loss function, i.e.,
((W; æt, (4,3)) - log(H(W, (.))) - (1 y1) log H(W x1)).
(4)
To estimate W from training samples, we solve the following nonconvex minimization problem (w)
min WER1X
Here we assume the input features 2; are generated ii.d. from the Gaussian mixture model (Pearson, 1894; Titterington et al., 1985; Hsu & Kakade, 2013), which we denote
XN La),)
(6)
where N denotes the multi-variate Gaussian distribution with mean lat E Rdd, and covariance Iı for or E R for all 7 [T.]. The Gaussian mixture model can be viewed as
= μ4 + 2/: E RRd
where h is discrete random variable with Pr(h = = A for I E [7]], and follows the multivari- ate Gaussian N (0, of Ia) with zero mean and covariance of Ia
If the Gaussian mixture model is symmetric, the symmetric distribution can be written
Σ (N((m,) of))
L even
(8)
A Σ X(N(m. + N L odd
We assume without loss of generality that μ belongs to the column space of W for all E [L]. To this, that arbitrary lat can be written as j4 + AA21 where Mill belongs to the column space of W and Til is perpendicular to the column space. Then, from (2) and (7) we have
K
K
H(W x)
Mwy (Pill + 14 + 2x))
Σ
6lw) T (MN) + =))) = H(W x')
K
K
Ø=1
(9)
where x' Ele NuN If.. Thus, these two cases are equivalent.
3 PROPOSED LEARNING ALGORITHM
We propose Algorithm 1 to solve (5) and defer its theoeretical analysis to Section 4. The method starts from a initialization Wo E T computed based on the tensor initialization method (Sub- routine 1) and then updates the iterates W, using gradient descent with the step size 7oo- To analyze the general cases, we assume an i..dd. zero-mean noise { E R with bounded magnitude ((4))al & EÚC [d] k E [K] for some & 2 when computing the gradient of the loss in (4).
Our tensor initialization method is extended from (Janzamin et al., 2014) and (Zhong et al., 2017b). The idea is to compute quantities (M, in (10)) that are tensors of w and then apply the tensor decomposition method to estimate w." Because M, can only be estimated from training samples, tensor decomposition does not return w exactly but provides a close approximation. Because the existing method only applies to the standard Gaussian, we exploit the relationship between proba- bility density functions and tensor expressions developed in (Janzamin et al., 2014) to design tensors suitable for the Gaussian mixture model. Formally,
'One easily extend our analysis to the case when the covariance is diag(añ. afa). One needs to revise Property and Lemma 7 correspondingly. We the same a; simplify the presentation.
4

---

Under review as a conference paper at ICLR 2021
Algorithm
Our proposed learning algorithm
Input:
Training data {< 34) J== the step size = 0
Ei= A on t
iteration T
Initialization: Wo + Tensor initialization method via Subroutine Gradient Descent: for / = 0, 1, 1
W4+1 Wi 770
VI(W 2. +2) W.
(
(W)
72
Output: WT
Definition Let p(z) Eiz (2(2TO)) - exp(- 1|=--11-11
be the probability density function of exp(-1la_pa 20f
the Gaussian mixture model (6). We define
Mj := of ly (-1)'='(x)\V> p(x)), j j= 1,2,3
(10)
Let a E Rd denote an arbitrary vector. If the Gaussian Mixture Model is symmetric as in (8), then P2= = M3(Ia, Ox). Otherwise, P2 M2.
Mj is jth-order tensor of w e.g., M3 K EE E EE (1, r) (ww" x) w2,
These quantifies cannot be directly computed from (10) but can be estimated by sample means, de- noted by M. (i 1,) and Pz, from samples {æ,, M/ ) The following assumption guarantees that these tensors nonzero and can thus be leveraged estimate W
Assumption The Gaussian Mixture Model in (6) satisfies the following conditions:
1. E EE of ( (ooTTa) x)] + for E [K]. which implies that M3 is nonzero.
2. If the distribution is not symmetric, then BRSEE AeN In x]] * 0 f i e [K], which implies M2 and Pg in this case are nonzero.
Note that Assumption I is a very mild assumption Moreover, as indicted in (Janzamin et al., 2014), the rare case that some quantities M, (i 1, 3) and P3 are zero, one can construct higher-order tensors in similar way as in Definition 1 and then estimate W from higher-order tensors.
Subroutine estimates the direction and magnitude of .n [K]. separately. The key steps are follows. We first use the power method decompose Pa approximate the subspace spanned by (w], ung.... ) denoted by Ú. Then, we project M3 E Rdddxd R3 E Rkxxx using U to reduce the computational and sample complexity for decomposing a third-order tensor in the next step. We then apply the KCL algorithm to decompose Rg into vectors G, Note that ÜT S, where 8; (1,-- (1} is random sign. Then the direction of w is determined. Finally, the magnitude of "x's and the signs of s;'s are determined by solving a linear system of equations using the RecMagSign method. Please refer to (Zhong al., 2b) and (Kuleshov al., 2015) for more details on the power method, KCL and RecMagSign methods.
4 MAIN THEORETICAL RESULTS
The main idea of our analysis is to show that the empirical risk function in (3) is strongly convex in region near W Then Wo returned by Subroutine 3 is in this convex region, and the iterates returned by Algorithm converge to a critical point in this region. Before formally stating our result in Theorem
summarize the key implications of Theorem
follow.
1. Convergence rate and estimation accuracy: When gradients are accurate (i.e., & = 0), the iterates W. converge to critical point W, linearly, and the distance between W,, and W is
BBy mild we mean given L, if Assumption is not met for some (Ao, Mo) there exists infinite number of (X, M', a²) in any neighhorhood of (No, Mo, aT) such that Assumption I holds for (X, M',a'),
5

---

Under review as a conference paper at ICLR 2021
Subroutine 1 Tensor Initialization Method
Input: Partition pairs of data {( |2 into three subsets D1, D2. D3
Compute P2 using D1 and arbitrary vector
Ü +- PowerMethod( Po. K)
Compute R3 - M2 Ü, (, from data set D2
(i))E(K] < (C
(Wo) f- RecMagSign( Ü, { [ε]]] Dz)
Return: Wo
Oly d n/ggn/n). With the noise in the gradient, there is an additional error term of O /d log n/n).. For example, when n is (d log" d), the estimation error decays as O
1+5
log
2. Sample complexity: The sample complexity for accurate estimation is Od d) where d is the feature dimension. This result is in the same order as the sample complexity for the standard Gaussian input in (Fu et al., 2020) and (Zhong et al., 2017b), indicating that our method can handle input from the Gaussian mixture model without increasing the order the sample complexity. Our bound is almost order-wise optimal with respect d because the degree of freedom is dK. The additional multiplier of log? d results from the concentration bound in the proof technique.
3. Impact of the mean: of (i) of the Gaussian mixture model increases from 0 (in terms of the absolute value), the sample complexity increases to infinity and the convergence slows down. The intuition is that as the absolute value of some mean increases, some training samples have significantly large magnitude such that the sigmoid function saturates. These training samples are not informative for the estimation of W and the gradient of these samples is close zero. Therefore, the required number of samples to estimate W needs to increase, and the gradient descent algorithm slows down.
If everything else fixed, and at least one entry of mean (M(()) (the ith entry
Impact of the variance: everything else is fixed, and least one variance or of the Gaussian mixture model increases from a certain positive value, the sample complexity increases to infinity and the convergence slows down. The intuition is the same as increasing [Mt(a) in point 3. On the other hand, when all variances in the Gaussian mixture model approach zero, the sample complexity increases to infinity, and the convergence slows down. The intuition that when the input data are concentrated on few vectors, the optimization problem does not have a benign landscape.
Combining points and 4, one can see that to learn the teacher network characterized by (2), the training samples shall have zero mean and medium level of variance to reduce the sample complex- ity and speed up the convergence. If the variance is too large, some samples become non-informative and affect the learning negatively. If the variance is too small, the learning problem becomes math- ematically challenging to solve. This theoretical characterization can be viewed as one motivation of the empirical techniques to improve learning rate such as whiting (LeCun et al., 1998) and Batch normalization (loffe & Szegedy, 2015). We state our main theoretical result as follows.
Theorem Consider the binary classification problem with one hidden-layer fully connected neu- ral network as in (2), Suppose Assumption 1 holds, then there exist en E (0, 2t and positive value functions B( X, M, o, W*) and q(,, M, a. W*) such that as long as the sample size n satisfies
2 == poly(( K)B(A, M. W W")dlog" d.
(11)
we have that with probability at least 1 d-10, the iterates (W.YT= returned by Algorithm I with step size no0 O El_, Ailllerl +o.) converge linearly with statistical error to critical point
Wa with the rate of convergence = 1-
K - (1,,,,,. M, oF W*), i.e.
7o
||, W. Wa-lallF v Wo - WallF + -
V dK log n/n,
(12)
Moreover, the distance between W and W,, is bounded by
W... Wr s (1 (1 +....vllloo///l vdlogn/n)
(13)

---

Under review as a conference paper at ICLR 2021
We next quantify the impact of the parameters of the Gaussian mixture model the sample com- plexity nse and the convergence rate discussed in Theorem as follows.
Corollary (Impact of the Gaussian mixture model on nuec and v)
(1) When everything else is fixed, Rue increases to infinity, and increases to 1, as |P(G)) with any 1 E [L] and E [d] increases, where Pr(j) is the i-th entry of pt-
(2). When everything else is fixed except for some foror any E [T.], Dae increases to infinity, and o increases 1, as di increases from for some constant Ça > 0.
(3) Niee increases to infinity, and v increases to if all ot 's go to zero for all I E [4].
To the best of our knowledge, Theorem I provides the first explicit characterization of the sample complexity and learning rate when the input follows the Gaussian mixture model. Although we consider the sigmoid activation in this paper, our results apply to any activation function & provided that ø' an even function, and é. ø' and 6" are bounded. Examples include tanh and erf. Algorithm I employs a constant step size. One can potentially speed up the convergence, i.e., reduce v, by using a variable step size. We leave the corresponding theoretical analysis for future work.
If we scale the weights W = W /c and the input feature x' = cæ simultaneously, the output remains the same for any nonzero constant Therefore, the learning problems in these two cases are equivalent in terms of the sample complexity and convergence rate. Theorem reflects such equivalence. One can check that B(A, M, a,, W*) = B(X, M a', W*') from the proof in Section B. Similarly, the convergence rate in (12) remains the same in both cases.
One main component in the proof of Theorem I to show that if (11) holds, the landscape of the empirical risk is close to that of the population risk in a local neighborhood of W (Mei et al., 2018a) quantified the similarity of these two functions when K approach can be extended to the case K > 1. Here, focusing on the Gaussian mixture model, we explicitly quantify the impact of the parameters of the input distribution on the landscapes of these functions. Please see Appendix-C C for details.
but it is not clear if their
Compared with the analyses for the standard Gaussian in (Fu al., 2020; Zhong et al., 2017b), develop new techniques in the following aspects. First, a direct extension of the matrix concentration inequalities in these works leads concentration bounds to tighten it (dd Odlog d). Second, the existing analysis to bound the Hessian of the population risk function does not extend to the Gaussian mixture model. We develop new tools that also apply to other activation functions like tanh or erf. Third, we design new tensors for the initialization, and the proof about the tensor initialization is revised accordingly.
sample complexity bound of (dd), while we develop new
The above results assume the parameters of the Gaussian mixture are known. In practice, they can be estimated by the EM algorithm (Redner & Walker, 1984) and the moment-based method (Hsu & Kakade, 2013). The EM algorithm returns model parameters within Euclidean distance O ((()))) when the number of mixture components L is known. When L is unknown, one usually over- specifies an estimate L > L, then the estimation error by the EM algorithm scales as ((())
Please refer to (Ho & Nguyen, 2016; Ho et al., 2020; Dwivedi et al., 2020a;b) for details.
5 NUMERICAL EXPERIMENTS
We verify Theorem I through numerical experiments. We generate a ground-truth W E Bdxk from the Gaussian distribution. The training samples (æ,, Mi 1a are generated using (6) and (2). The maximum number of iterations of Algorithm is set as 12000.
5.1 TENSOR INITIALIZATION
Fig. 1 shows the accuracy of the returned model by Algorithm 1. Here d = 5. K 2, = 0.5, 141 = -1 and μt2 = O. We compare the tensor initialization with a random initialization in a local region { (W& E RddK ||W-W"ll
W < E). Tensor initialization in Subroutine I returns initial point close W with relative error of 0.61. If the random initialization is also close to W e.g.,
7

---

Under review as a conference paper at ICLR 2021
c= 0.1, then the gradient descent algorithm converges to critical point from both initializations, and the linear convergence rate is the same. If the random initialization is far away, c.g.. c = 1.5, the algorithm does not converge. On MacBook Pro with Intel(R) Core(TM) i5-7360U CPU at 2.30GHz and MATLAB 2017a, it takes 0.55 second to compute the tensor initialization. We consider random initialization with 0.1 in the following experiments simplify the computation.
5.2 SAMPLE COMPLEXITY
Let μl be all one vector in Rd and let μ22 -11 Let 01 = d2 1. We vary d and evaluate the sample complexity bound in (11) with respect to d. We randomly initialize M times and let (.(")) denote the output of Algorithm in the mth trail. Let W,, denote the mean values of all (m))) and let dw =V V 1== i W.
Consider the case that K = 3, I. = 2, A1
denote the variance. An experiment is successful if dw S 10-4 and fails otherwise. M is set as 20.
We vary d and the number of samples For each pair of d and n, 20 independent the corresponding training samples are generated. Fig. shows the success rate of these independent experiments. black block means that all the experiments fail. white block means that they all succeed. The sample complexity is indeed almost linear in d, as predicted by (11). Moreover, the coefficient n/ n/d can be large depending on the problem setup.
of W and
10
130000
Wolle:/B.
1015
100000
10
Temoor infislization
Random intinaizaaionn e-0.1
10
Bandon inFielizaiin,, e*1.
200
400
600
800
1800
Number Iterations
of
Figure 1: Comparison between gradi- ent descent with tensor initialization and random initialization
Figure 2: The sample complexity against the feature dimension d
We then fix d = 5 and study the impact on the sample complexity when the mean and variance in the Gaussian mixture model change. Fig. 3.(a), we fix σ = 02 and let l μ 1, 442 = 1. μ varies from 0 to 7.5. Fig. 3.(a) shows that when the mean increases, the sample complexity increases. This coincides with our theoretical analyses in Section 4. In Fig. 3.(b), we fix μ1 1, 24 -1, and let 01 complexity increases both when increases and when o approaches zero. The results match our theoretical prediction in Section 4.
and 02 1. varies from 10 to 10 The sample
10000
20000
Number of S'Smpppsss
Number of Samples
2000
2
7
Value
log (o)
(a)
(b)
Figure The sample complexity (a) when one mean changes, (b) when one variance changes.
8

---

Under review as a conference paper at ICLR 2021
5.3 CONVERGENCE ANALYSIS
We next study the convergence rate of Algorithm 1. d fixed as 5. Fig. 4.(a) shows the impact of the mean of the Gaussian mixture model the convergence rate. We set Å X2 0.5, μ4i p 1, d2 = 1. The sample complexity is set to 10000. One can see that Algorithm always converges linearly when μ changes. Moreover, as l increases, Algorithm converges slower, as predicted by our theoretical analyses in Section 4. In Fig. 4.(b) shows the impact of the variance the Gaussian mixture model. We set λ = X2 0.5, μ1 1, μ2 = -1, 01 = d2 a. The sample complexity n is set to 50000. Among different we test, Algorithm I converges fastest when a 1. The convergence rate slows down when a increases to 2 or when a decreases to 0.5. The result is consistent with our theoretical results in Section 4.
422 = 11 and
We then verify the convergence rate (12), which shows that v = - ( We set X2 0.5, 141 1, A4 -1, 02 1. K ranges from 8. One from Fig. 5 that, as predicted, the convergence rate is almost linear in 1/K².
109
10
Relative etvor
10
Relaiive
10
1.5
0000.7
p=1
111.5
1.5
10'5
1000
2000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Number of iterations (a)
iterations
(b)
Figure 4: (a) The convergence rate with different 14, (b) The convergence rate with different a.
0.15
0.99
0.1
0.986
Locn
Figure 5:
Convergence rate when the number of neurons K changes
Figure 6: The relative error of the learned model with the ground-truth when changes
We then evaluate the distance between W, returned by Algorithm 1 and W measured by I|W, W'l.e. d is n ranges from 10 6 x 10a. σ1 = de 3. f4 = 1, μ 1. Each point in Fig. 6 is averaged over 100 independent experiments of different W* and the corresponding training set. || is normalized to 1. The error is indeed linear in Vlog(n)/n. predicted by (12).
CONCLUSIONS
This paper analyzes the theoretical performance guarantee of learning one-hidden-layer neural net- works for binary classification when the input follows the Gaussian mixture model. We develop an algorithm that converges linearly to model that has a diminishing difference from the ground-truth model that has guaranteed generalizability. We also provide the first explicit characterization of the impact of the input distribution the sample complexity and convergence rate. Future works in- clude the analysis of multiple-hidded hidden-layerr neural networks and multi-class classification. Because of the concatenation of nonlinear activation functions, the analysis of the landscape of the empirical risk and the design of a proper initialization is more challenging and requires the development of new tools.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang, Learning and generalization in overparameter- ized neural networks, going beyond two layers. Advances neural information processing systems, pp. 6155-6166, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019b.
Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová. The committee machine: Computational to statistical gaps in learning a two-layers neural network. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 3223- 3234. Curran Associates, Inc., 2018.
Nils Bjorek, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In Advances in Neural Information Processing Systems, pp. 7694-7705, 2018
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 605-614. JMLR. org, 2017.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10836-10846, 2019.
Elaina Chai, Mert Pilanci, and Boris Murmann. Separating the effects of batch normalization on cnn training speed and stability using classical adaptive filter theory. arXiv preprint 2rX6v:2002.10674, 2020.
Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 634-644. IEFF, 1999.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685, 2019.
Simon S. Du, Jason D. Lee, and Yuandong Tian. When is a convolutional filter easy to lear? arXiv 2017.
preprint, http://arxi.orrgass///00..000
Simon S Du, Jason D Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don't t be afraid of spurious local minima. In International Confer- ence on Machine Learning, pp. 1338-1347, 2018a.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations, 2018b.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Michael I. Jordan, Martin J. Wainwright, and Bin Yu. Singularity, misspecification, and the convergence rate of em. To appear, Annals of Statistics, 2020a.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, Michael Jordan, and Bin Yu. Sharp analysis of expectation-maxiiizaiion for weakly identifiable models. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artifi- cial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1866-1876, Online, 26-28 Aug 2020b. PMLR.
Andreas Engel and Christian P. L. Van den Broeck. Statistical Mechanics of Learning. Cambridge University Press, USA, 2001. ISBN 0521773075.
10

---

Under review as a conference paper at ICLR 2021
Mario A. T. Figueiredo and Anil K. Jain. Unsupervised learning of finite mixture models. 1EEE Transactions on pattern analysis and machine intelligence, 24(3):381-396, 2002.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of one-hidden-laae neural networks via cross entropy. IEEE Transactions on Signal Processing, 68:3225-3235, 2020.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with land- scape design. In International Conference on Learning Representations, 2018. URL https: //openzeview
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? ArXiv preprint arXiv: 2006. 2006. 13409, 2020.
Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dy- namics of stochastic gradient descent for two-layer neural networks in teacher-student setup. In Advances in Neural Information Processing Systems, volume 32, pp. 6981-6991, 2019a.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modelling the influence of data structure on learning in neural networks: the hidden manifold model. arXiv preprint arXiv: 1909.11500, 2019b.
Sebastian Goldt, Galen Reeves, Mare Mézard, Florent Krzakala, and Lenka Zdehorová. The gaus- sian equivalence of generative models for learning with two-layer neural networks, 2020.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645-6649. IEEE, 2013.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Nhat Ho and XuanLong Nguyen. Convergence rates of parameter estimation for weakly identifiable finite mixtures. Ann. Statist., 2466)2726-2255,, 12 2016. doi: 10.1214/16-AOS144 URL
1211/12111111 A0511444
Nhat Ho, Raaz Dwivedi, Koulik Khamaru, Martin J. Wainwright, Michael Jordan, and Bin Yu. Instability, computational efficiency and statistical accuracy. Arxiv preprint Arxiv: 2005.11411, 2020.
Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Proceedings of the 4th conference on Innovations Theoretical Computer Science, pp. 11-20, 2013.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448-456, 2015.
Anil K Jain. Data clustering: 50 years beyond k-means. Pattern recognition letters, 31(8):6511666 2010.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Score function features discriminative learning: Matrix and tensor framework. arXiv preprint 14 2014.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On batch-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609, 04836, 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Proc. Ady. Neural Inf. Process. Syst., pp. 1097-1105, 100,, 2012.

---

Under review as a conference paper at ICLR 2021
Volodymyr Kuleshov, Arun Chaganty, and Percy Liang. Tensor factorization via matrix factoriza- tion. In Artificial Intelligence and Statistics, pp. 507-516, 2015.
Yann LeCun, Leon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Neural Networks: Tricks of the Trade, pp. 9-50. Springer, 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436444 May 2015.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31, pp. 8157-8166 Curran Associates, Inc., 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with ReLU activa- tion. In Advances Neural Information Processing Systems, pp. 597-6077 2017.
Shiyu Liang, Ruoyu Sun, Jason Lee, and R Srikant. Adding one neuron can eliminate all bad local minima. In Advances in Neural Information Processing Systems, pp. 4355-4365. 2018.
Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for non-convex losses.
Ann. Statist., 46(6A):2747-2774, 2018 la.
Song Mci, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(3)):77665-E767) 2018b.
Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Dynamical mean-field theory for stochastic gradient descent gaussian mixture classification, Arxiv preprint Arxīv: 0609,, 2020.
Rémi Monasson and Riccardo Zecehina. Weight space structure and internal representations: A direct approach to learning and generalization multilayer neural networks. Phys. Rev. Lett., 75: 2432-2433 Sep 1995.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956,
2017.
Karl Pearson. Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London. A, 185:71-110, 1894.
Haim Permuter, Joseph Francos, and Ian Jermyn. A study of gaussian mixture models of color and texture features for image classification and segmentation. Pattern Recognition, 39(4):695-706,
2006.
Richard Redner and Homer F Walker. Mixture densities, maximum likelihood and the em algo- rithm. SIAM review, 26(2): 2299, 1984.
David E Rumelhart, Geoffrey E Hinton, Ronald J Williams, al. Learning representations by mack-propagating errors. Cognitive modeling. 5(3), 1988.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4430-4438, 2018.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch nor- malization help optimization? In Advances in Neural Information Processing Systems, pp. 2483- 2493, 2018
Henry Schwarze and John Hertz. Generalization in a large committee machine. Europhysics Letters (EPL., (0(4):375-380 oct 1992.
12

---

Under review as a conference paper at ICLR 2021
Henry Schwarze and John Hertz. Statistical mechanics of learning in a large committee machine. In Advances in Neural Information Processing Systems, volume 31, pp. 523-530, 1993.
Hyunjune Sebastian Seung, Haim Sompolinsky, and Naftali Tishby, Statistical mechanics of learn-
ing from examples. Phys. Rev. A, 45:6056-6091, Apr 1992. doi: 10.1 10.110%/hyyseev445..0mm URL https:://// /ttp///ikkk//// aps wttpooogg/oooooooooooo
1101111011111 http////o/...11//////e/ereee/ 45. 6056.
Ohad Shamir. Distribution-specific hardness of learning neural networks. The Journal of Machine Learning Research, (91):1135-11633 2018.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of pwrrmeeareeterizee shallow neural networks. IEEE Transactions Information Theory, 65(2):742-769, 2018.
Yuandong Tian, An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3404-3413. JMLR. org, 2017.
D Michael Titterington, Adrian FM Smith, and Udi E Makov. Stufistical analysis of finite mixture distributions. Wiley, 1985.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Yuki Yoshida and Masato Okada. Data-dependence of plateau phenomenon in learning with neu- ral network - statistical mechanical analysis. In H. Wallach, H. Larochelle, A. Beygelzimer, dAlché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Sys- tems, volume 32, pp. 1722-1732 Curran Associates, Inc., 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1rXiv:1611.0353: 2016.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability: One-hidden-layer case. arXiv preprint arXiv:2006.14117 2020a.
Shuai Zhang, Meng Wang, Jinjun Xiong, Sijia Liu, and Pin-Yo Chen. Improved linear convergence of training cnns with generalizability guarantees: one-hidden-layer case. IEEE Transactions on Neural Networks and Learning Systems, 2020b.
Xiao Zhang, Yaodong Yu, Lingxiao Wang. and Quanquan Gu. Learning one-hidden-las layer relu networks via gradient descent. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1524 1534. PMLR, 2019.
Kai Zhong, Zhao Song, and Inderjit S Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. arXiv preprint arXiv:1711.034400, 2017a.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for -lyee neural networks. Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 4140-4149, 2017b. URL https:///axiiw orgg / 1706. 03175. .df..
Difan Zou and Quanquan Gu. An improved analysis training over wer-parameterized deep neural networks. In Advances in Neural Information Processing Systems, pp. 2055-2064, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 109(3):467 2020.
13

---

Under review as a conference paper at ICLR 2021
A PRELIMINARIES
In this section, we introduce some definitions and properties that will be used in proving the main results.
First we define the sub-Gaussian random variable and sub-Gause Sab-Ganssian norm.
Definition We say X is a sub- sub-Gaussian random variable with sub- Gaussian norm K > O, if (E|XI)) & KVP for all 2 1. In addition, the sub-Gaussian norm of X, denoted || is defined as ||X sup p21 P.
Then we define the following three quantities. o( is motivated by the parameter for the standard Gaussian distribution in (Zhong al., 2017b), and we generalize Gaussian with an arbitrary mean and variance. We define the new quantities п(λ, M, o, W*) and D (A, M, or) for the Gaussian mixture model.
Definition (p-sunction). Let z N(u, Ia) E Rd. Define ong (i, u, Ee,,N(u 2,) and Bg (i, u, = E2,~N(u,,,) (0 (2.))))) =,)=; V q {0, (0, where 24 and u, the i-th entry of and u, respectively. Define puu, 0) as
azli, u, o)
p(u,o)= min jJEldliii [(u] + () o) - aoli, u,
(14)
ui +1
Definition 4 (I' (I-ffucction). With (6), (14) and K, defined in Section 2, we define
T(A. W
Σ
A of of
pl (W*)
W orox (W*))
(15)
R2n 2 max
1=1
Definition (D-function). Given the Gaussian Mixture Model in (6) and any positive integer m, define Dm (x, M. as
Dm (A, M,) A1 Mull 1)m,
(16)
where À -A1, ,,..,,,,) AL) M (M1, (L) E Rdx and o (o ,OL) R
g-function defined to compute the lower bound of the Hessian of the population risk with Gaussian input. I function is the weighted function is positive and upper bounded by a small value. It is increasing when |AtØl increases. When oi increases, I' increases first and then decreases. r goes to zero if all || lloe or all o goes to infinity. D-function is normalized parameter for the means and variances. It is lower bounded by 1. D-function is an increasing function of || and a decreasing function of az
of p-function under mixture Gaussian distribution. This
Property We have that [|pile is sub-Gaussian random variable with its sub-Gaussian norm bounded bu EVR.
Proof:
E E < (E d <
(17)
Property 2 p(u, o') in Definition 3 satisfies the following properties,
1. p(u, σ) > 0 for any u dd and a + 0.
2. p(u, σ) converges to a positive value function of a as u; goes to O, í.e. lim p(u, a): C. (g).
14

---

Under review as a conference paper at ICLR 2021
3. When all u, + 0 (i [d]). p( o) converges a positive value function of u goes to
O, i.e. limo-o pl :. σ) == C. (u). When u, = 0 for some i E [d], limo-40 P σ) =
4. When everything else except |uy] is fixed, pl W. positive value function, Lm Cm(oax(W-)) (W*), which monotonically decreasing to
W (W " 0ōx (W*)) (ox(W") is lower bounded by
0 as [us] increases.
5. When everything else except is fixed, pl W OokkWW>) oox (W")) lower bounded by positive value function, Lol W.TT σok (W*)), which satisfies the following conditions:
(a) there exists &e >> O, such that 0 Lo( ( oox(W"y σdx (W*)) is an increasing function of when a (0, (s)): (b) there exists Ço 0 such that Cs (bx (ox is an decreasing of a when a E (Sa,
W
W.
Proof:
(1) From the Cauchy Schwarz's inequality, we have
Bx,-Morr 2:) s / VeanWon.n)oP 21)
(18)
Be 2)2s 22l S Be,,N(u,,))) 10 21)2 (BL
(19)
V 60 (a. 2,)2,1
/n++1 +1
The equalities of the (18) and (19) hold if and only if o' is constant function. Since that is the sigmoid function, the equalities of (18) and (19) cannot hold.
By the definition of o(u, in Definition 3, have Bo u, ag u, o) and (2 u, (1.000 uf+1
> 0. Therefore,
p(u,o) >0
(20)
(2)
lim
()o(i, u. 2g(i,u,)) u.
+0
u2
|| uzll? )dz
lim
1)(
(0 (2 - expl
σ²
2
6'(a 2; (2T) - expp || - 1112
)dz;)²)
2
= π2
+ +1(
1
100
(0 =2)(2 - exp(
||:11|
)dz,
(
000
22)x))))22))- exp(
|| )dz,)
2
2
00
(21)
1
lim #0
(32(i,
ue + ag u, o))
||2| u1
lim
2 22)2((2)))
exp(
)dz
8,
|| 11
8'(a . 2 2) (2T))
exp(
)dz,
u
-00
2
|201|
x0
||
( 2 (mT) 1 exp(
)dz;
-1
exp(
)dzz) )2
2
2
(22)
Combining (21) and (22), we can derive that p(u, a) converges to positive value function of a as M4 goes to 0, i.e. limy->0 p(u, a) (m)
15

---

Under review as a conference paper at ICLR 2021
(3) When all us + 0 (i [d],
lim d=+
u (32
0)
1
a (i, u
_0))
o))
- +1
4x
||:
11
lim
(a 21)2
exp(
)dz
o 0-0
-00
2
| 41 |1?
d'(o- (2
- *exp(
)dzi)
"
2
Fz)) ui
0²
100 11
lim
12xh
exp(
)d.;
o 8
0²
2 2
0²
Ira - 111
"
d'(u 2z)
02
1
2
2m
exp(
2 2
)dz,)
24
(23)
u
-lim o-1
8 (u:)
(Ø'
0²
42
u
lim --0
U1
1 14:
lim (u:)
a a-0
1 a²
(w:)
The third step of (23) by the fact that the Gaussian distribution goes to a Dirac delta function when goes to 0. Then the integral will take the value when x;; 1. Similarly, we can obtain the following
u _0) - agli, u .0)
lim o-0
(Boli.
o
||| 2:1l" 112 )dz
lim
( (2 1 expl
a
(24)
x
|| - M: 2 2
0'(o (2 3 exp(
2 )dz;
(ws) 8 (u:) =0
9 u 0) - agli, u .o))
lim
(Bo(i,
do
0
||:; ui
lim
(²(xx) 2) - exp(
)do
do
202
|10 - -usl?
-
o' (I:)) & eexp(
)dr;
= 0 2i
20
||:; - uil12
lim
(22(2))2TT0 - eexp(
1--011
-1 + ||,2, uell20 2)xx;
202
(25)
||,;;
uil1 )dr;)
2(
d'(x)((2TO0)) 2- exp(
20²
d'(x,) - | - mill"
exp(
(-o -1 + ||l1 - u.1130 -2)2z))
202
(u) -2Ø'(u;) o(uu) ) -o
lim
duu)
lim
+00
0
16

---

Under review as a conference paper at ICLR 2021
Therefore, by L' L'Hopital's rule and (24), (25), we have
u
2
lim
+
(Bo(ii, _. -alli; (00l..0))
0 +0
σ²
lim
"
(3p
u u 0) - aoli, _: o)) _
(26)
d-0
20
do
00
Combining (26) and (23), we can derive that p( σ) converges to positive value function of u as goes to i.e. lim,-o : 0) == Cu)
When u, = 0 for some i [d]. lim, _ +1) -)) σ)) = 0 by (24). Then from the Definition 3, we have oo p 2 = O.
(4) We show the statement by contradiction. Suppose that for any positive value func- tion, h(ue), which is monotonically decreasing to 0 |ul increases, there exists W'J pl ooo od o0x
un E R such that h(u;) 2 lim +ag pl W
Then we can derive that 14
(W-) σōœ (W:))
W M O. Since that p ( W odR (W*)) is continuous,
O, which contradicts to the conclusion in obtain that p( oōx (W+)) σdx (W*)) M4=u.
W.
Property 2.1.
(5) The condition (b) can be easily proved as (4). Therefore, we only need to show the condition (a). When (W T u): # 0 for all [K], lim pl lox (W+j.
w σōx (W*)) C, (v.) Cz,)) 0. Therefore,
there exists Ss > 0, such that when 0 < < So. pl W
(W oō (wx)) > C. u) Then we == C.W" [u) 0² such that - -L. W
2
(ox odx (W*)) is an can define L.( oox W. σdx (W*)). When (W- u); = 0 for some i E [K], increasing function of a below pl Moox(W")
26,
then lim pl W. ( (W*)) 0. We can derive
W... WW
od ()))
a W T do oōx (W.) σōk ()*))= 2
lim 0-0
lim a
pl
(wx())))
(27)
The last step of (27) is because the limit negative, then pl [W= odx W')) will be negative
in small neighborhood around = 0, which contradicts to the fact that pl W 0.
>
a Gagiww wag.iwy..oo .ōx (W"))
If the limit in (27) O, then lim. 8a
otherwise there will be small
pl w
0. In this case we only need to If the limit in (27) is positive, we can find positive lower bound of pl (lokk( "o.""".66x6 (wx)(W)) in small neighborhood around 0 and an (W*)) can be defined to be less than this positive increasing function of o -- ( 00x lower bound.
neighborhood around O in which
"L. W' W oōx (W*)) p( M
let aoooo'Coo
w
In conclusion, the condition (a) is proved.
Property With the notation in (6), if function (xx is an even function, then
B [[()]] Po
(28)
Proof: Denote
- = f==)
exp(
(29)
20
17

---

Under review as a conference paper at ICLR 2021
- ... / g(a1, .. za)dar ... drd
00
E on)
g(x)dx
( 22, .. , )dzz ... da
0 T2
.r dx ... dxd
(30)
g( (dr
ZERd
| + 1ll2 )d
(xx) exp(
MER
20²
B Ia)
Therefore, we have
Bo-N = (o
(31)
Property Under Gaussian Mixture Model a ~ Eie ANN of we have the following upper bound.
E Ele of 2 S (21
1)!!|[u 2t
Acll + 01)
(32)
Proof:
The main idea is to find an upper bound with symmetric distribution assumption first, and then apply Property 3 to extend the conclusion to the general case.
(a) If the
distribution is symmetric and L = 2, i.e.
2/2 (N(H, o +
((-M,oola) then we first need analyse the distribution of u x by computing the moment generating function
E } (o (Wiu.o (exp(lu' x)] = Elexp(1 uga:a) II E E(exp((uxr;))
d
2
(x; - (-1) )dx;}
exp(tuzz;)
exp(
2
202
i=1
j=1
-00
d
2
cxp(tu;(-1)))
2
i=1
(33)
(2, - (-1) ps) )do;
exp (Lu,1r, (-1))u))
exp(
V2TO
20²
d
(ap(-tuf44)) 2 2 + eex((tufti + +2 2
1
1
2d
2d exp(tu4+ 1 PP))) 2
which is the Moment Generating Function of Σ J.W4 of) The last step of (33) is by expanding the multiplication of d terms. Specifically, let {s denote all 2 vectors in I taking values from 0 and 1. Let of (k E [d] denote the k-th entry of sf. We define 14 (-1'
IR for E [2*], and o' = a||u||| R. where uy and μ4 are the k-th entry of the vector and μa. respectively. Then we can derive the first few steps of E((u 22)
18

---

Under review as a conference paper at ICLR 2021
E
2 (N [(u 22)
2
0
(W-uf)²
2012
dy
2d
V
1=1
2d
(x-ek)2
(y μ4 + +1))2z
20r2
dy
V2TO'
1=1
24
21
21
14
21-
(y - =p')
(x- ol 2
20 dy
V
P=0
(34)
2
21
2f
21 21-PP
p is odd
2d
p
(p 1)1lo
is even
1m
P=D
24
21
22
22
(2k 1)!!
2d
2k
2
1
2t
(2k
1)!!
14
2d
2k
k=0
1=1
The first step is by the distribution of u." T x we obtain from (33). The third step follows from the binomial expansion. The forth step results from the calculation of high-order moment of Gaussian distribution. The second to last step is derived from the inverse of binomial expansion. The last step due to the substitution of summation. To compute the inner summation in the last step of (34),
19

---

Under review as a conference paper at ICLR 2021
have
2d
20
4
1=1
(ur(-1) + =2(-1)) + ... + uul (
(21)!
(u1 (u1(- (-11)) 11) ((ual-1)(uaa)
P1
1p
(9)
!..pd
!
=21
(2))
(2i
all the p; are even
(1)
(1)
pd
(2
(u) ...(u)p3)
(1)
Pj
( (4)
(i)
93
P1 12 ... Pd
(2))!
(t)
Σ
(t)!
(u (u ...1123))
max
(1) (1)
(1)
(1)
(
1
19
(1) (1)
Pi P2 .d
Σk= (6) =t
(21)
(t)!
max
-uf + .... 2b(2)
(4)
Pi 1p
Pa
192
2d
(2t)
(t)
m
(u] ... + wz)² max((u;]]
(1) ( !....g
Pi 12 ..... Pa
91 1gg
9d
<2n |||l max 11,,1)
21 (21 1)!!
Firstly we explain the third step. For any odd pe, there is term ao = (ux(-1)0) (35) Iagee(ux (11((11)))pa))) among the expansion of 1²?a whose corresponding vector s is (s), sy. ... sy)) We can find a n such that its corresponding vector is which is only different from the tuple of μĄ in the b-th entry. Therefore, in the expansion of n there exists a term de = (wu(-1)1-s) pt))*t IIIzee (=){(()))
... sg),
that can be cancelled out by ag- Therefore, there will be no odd power terms left. The third to last step of (35) is by the inverse binomial expansion. The second to last step is by the inequality ΣM a&bs I max(b;} E as
where a and b; are positive. The last step is because
(21)
(t)!
(5)
(8)
P1
P d
1/2
4d
(8)
(9)
(2t)
P62
Pdm.
2
2
!
Pd,
(1)
Pd
(3)
Pdm..
(0)
(36)
(2
1
2
(2t)
1
(2t-1)!! 1)!!
In the first equality of (36), Pá, .... Pd.. denote all the positive p,. Thus, have m Pa. 2t where pd, 2 2. Therefore, < 1 which is used in the second inequality. Therefore, Toobiiige,combiingg
20

---

Under review as a conference paper at ICLR 2021
(35), continue the derivation of (34) follows.
E
(NiH,
[u 2)
æ~
1
21
2k
(2k-
1)1!
Pi
2
2d
2k
k=0
(37)
8
2t
2h
(2k - 1)!! |2|121
max(|1yl]
2t 22t 1 1!
2k
8
k=
< (2t 1)!!||/|1 ( (1 + 0
The last step because that
2t
22k 1)!! < (2t-1- 1 -2k)!! (2t 1)(2t 3) (2t
2k 1) (2t 1)!!
terms
(b) From Property 3, since that (u TT) 20)2 is an even function, we have result for a general Gaussian distribution
E o( (u x) )
x;2²
(38)
(21 1)!! 2 ((laa]) oc + o)
Therefore, if there are L components in the Gaussian Mixture Model, then
E BE of Ta)l 2) S (2t - 1)!!|/2/ 20 Aclllmillo + 00))
(39)
Property With Gaussian Mixture Model (7), we have
F Ee o s d' (21 1)
A (e 1oo + 01)
(40)
Proof:
E B El An (,y1
F Ea Nn (11
1=1
x2
= E nn E Eb Ao (
dd'
d
1=1
25
< Eis o1)
dl
(x; -Mje)²
(xt - M45 + 11ji) 2,
exp(
)dx
V
203
(41)
21
lo is odd k is even
Aylmss1 20
(k-1))!off
(1
A 2 (2t 1)!!
1:
Ay(1اss + t0,) 21 1)!!
<d 1)!!
(1 + +0
21

---

Under review as a conference paper at ICLR 2021
In the 3rd step, apply Jensen inequality because f(x) = x' is convex when and t 2 1. In the 4th step we apply the Binomial theorem and the result of k-order central moment of Gaussian variable.
Property The population risk risk function f(W) defined as
S(W)
EE, - (n (n))/
2m El of 1a) (W; vi)
(42)
=E =E SI (L of of La) [e(W; 3i, ys)l
Based on (2), (3) and (4), can derive its gradient and Hessian follows.
de w.)
1
H(W)
K H(W (1 H(W) 1 (1(w, x)) <(W)
(43)
ow,0um Ei wa
(44)
K² ('(n a)) x) Hw
j
(W)
HWW H H(W)
x= c'u] (w) x) H=())L-H(W)) K k [w) x) H(W]L-H(W))
j=1
(45)
Property 7 With Dm (A, A,MMor σ) defined in definition 5, we have
(i) Dm (A, M D2m M,, s Dam (A, M,)
(46)
(ti) (m, ()))) s D2m (2m
(47)
Proof:
To prove (46), we can first compare the terms Ete Xda E/e dza and E/e Aoay where a, 2 1, i E [Z.] and Σ/= >
1.
L Σ
Apaz
Aaaz
(0)
}za3)
1=1
1=1
J=1
A2az ((1 -xx)a²
Σ
Azaz)
I5iEL
Σ
Apa;
Σ
Xjs
Σ 2وa3)
I8iSLiji
I8i$4jji
(48)
Σ Apa;
Σ
Xy(a az))
ISiSLjti
Σ
(Nidyar - a3) + > af))
-
Σ
Ady(a,--0 -2)) + taj) 20
The second to last step is because we can find the pairwise terms Xaa; ,y - at) and Λjaz >a(0 - of) in the summation that can be putted together. From (48), we can obtain
I.
I.
Xja;
Aja
S
Σ
X
(49)
i=l
i=1
22

---

Under review as a conference paper at ICLR 2021
Combining (49) and the definition of Dm M)) in (5), we can derive (46). Similarly, to prove (47), we can first compare the terms (Ei=) Ara;)² and Ei=1 Araf, where a; 2
1.
1, i E [L] and E X = 1.
2 A5a
)xa;)
A (a: )zaz)
>}aas)
i=1
]=1
Aaa; - (1:j=
E )ja;)
==1
ISishafi
Σ Ara E Aya: -
E )zas)
ISiShjfi
IsisLiji
(50)
Σ Aaa
(
E 2y(a; aa²)
ISiSh.fi
E
(N,yaa(a; - -ay) + >ıdjaa(ay -a))
=
ISUSLiii
Σ A0gg(u -a,)² 20
The derivation of (50) close (48). By (50) we have
)1az)² S Σ x
(51)
Combining (51) and the definition of Dm (A, M, o) in (5), we can derive (47).
B PROOF OF THEOREM
Theorem 1 is built upon three lemmas. Lemma I shows that with O(dK' log2 d) samples, the empirical risk function is strongly convex in the neighborhood of W Lemma 2 shows that initialized in the convex region, that the gradient descent algorithm converges linearly to critical point WT n. that is close to W Lemma 3 shows that the Tensor Initialization Method in Subroutine initializes Wo E RRdx in the local convex region. Theorem follows naturally by combining these three lemmas.
This proving approach is built upon those in (Fu et al., 2020). One of our major technical contri- bution extending Lemmas 1 and 2 to the Gaussian mixture model, while the results in (Fu al., 2020) only apply to Standard Gaussian models. The second major contribution is a new tensor initialization method for Gaussian mixture model such that the initial point is in the convex region (see Lemma 3). Both contributions require the development of new tools, and our analyses are much more involved than those for the standard Gaussian due to the complexity introduced by the Gaussian mixture model.
To present these lemmas, the Euclidean ball B(W* .r) is used denote the neighborhood of W where r is the radius of the ball.
B(W .r) = ( e gdxk ||W - -W 5r}
(52)
The radius of the convex region is
Csso ELe d -
W pl Tp
b σ10k (oxx((W>) (W+))
(53)
Kł EL Melllee1loo + 01) Et= Aell + t1)88
with some constant C3 > 0.
23

---

Under review as a conference paper at ICLR 2021
Lemma (Strongly local convexity) Consider the classification model with FCN (2) and the sig- moid activation function. There exists a constant C such that as long as the sample size
W Mi (W*) orok
2 CLED 2
Aell + (1))))
A
dk log'
σ10k
(54)
for some constant C₁ > 0 and E (0, t)) we have for all W E B(W,, .FON))
2e0
b
of
W My στōx (ox(W=))> σ10x (W:)) Iak
Ω
A
K
1=1
(55)
fn(W)) C2
dellm + to)²² Iak
with probability at least 1 10 for some constant C2 >
Lemma (Linear convergence of gradient descent) Assume the conditions in Lemma 1 hold. If the local convexity holds, there exists critical point in B(W*, r) for some constant C3 0 and E (0, })) such that
K El= X A + o1)2
dlog n
Ww, 1 S S0
(56)
Et= À Pl
W- W Fr (W-))
If the initial poins Wo E B ((W, .)), the gradient descent linearly converges to Wn, i.e.,
Elm A of W mi (..) (.0
[[, - Walle & 01- (1- K2 K Milloo + t1)
WWi-Walee
mic Pl
(1 ) Walle
(57)
with probability at least 10
Lemma (Tensor initialization) For classification model, with D& M, σ) defined in Definition have that if the sample size
n
dlog d,
(58)
then the output Wo Baxk satisfies
dlog n
Wo " De(A,
W
(59)
with probability at least (2(6
Proof of Theorem and Corollary
From Lemma 2 and Lemma 3, we know that if n is sufficiently large such that the initialization Wo by the tensor method the region B(W*, r). then the gradient descent method converges to
critical point W, that is sufficiently close to W To achieve that, one sufficient condition is
d d n
W. W IF S W. - W W VDDoA,
C3E0I(A, M, W
(60)
K3 EL Acll + ot) Ele Alll + +1))8)
where the first inequality follows from ||]F S K |||l|| for W Rx the second inequality comes from Lemma 3, and the third inequality comes from the requirement to be in the region
Omin and max denote the minimum and maximum among (01,-..
, respectively.
Emaa..
Pmin
24

---

Under review as a conference paper at ICLR 2021
B(W", .r). That is equivalent to the following condition
2005 112 K
11 + t0)
Σ Aellluul folllssooo))) +oi))) (6((W)))P(((.MM.o))
1=1
.TA, W*) - d dooge
(61)
where Co = max Cz²).
By the definition 5, we can obtain
4 lelleeeloo + 01)* Σ
Eulleel + +,))8)² S M,)DA M, max
(62)
1=
1=1
From Property 7, we have that
(63)
S D122 V M, M,,)
Plugging (62), (63) into (61), we have
n 2 Coep" . K K 51 (W"))),, M,
dloggd d
(64)
Considering the requirements on the sample complexity in (54), (58) and (64), (64) shows sufficient number of samples. Taking the union bound of all the failure probabilities in Lemma 1, and 3, (64) holds with probability d-10
By Property 2.3, pl W W*TH,
can be lower bounded by positive and monotonically oj05 (W*)) when everything else except |MG() is fixed, or decreasing functions Lm W "
(W=3 ,
Co( W' (Wo olōk (W*)) when everything else except or is fixed. Then, by substituting the lower W Mr
bound of pl orogg (W-j+ ojox(("))) for itself in I'(A, M, W*), we can have an upper bound of ( (o:0((WW))))))) (W*))* 12722, M. 222-= M. .r), denoted as B(A, M, a, W*).
To be more specific, when everything else except |(())) is fixed, Lm W 1y (1(x((")
plugged in M(A,M, W*).
Then since that D12(A, M, or W*) and
W mu f. (olxx (W'). oxoxxxx (W*))-2 are both increasing function of PM())) B(A, M, a. W*) is an increasing function of [pta]-
When everything else except or is fixed, oj Fmax > Co. then p D12 X M, o, W*) w 1 o10x (W+) is decreasing function, C
is incrcasing function of dr. Since that Le
W ((((0((()))) -2 is an increasing function of o₁. Hence, increasing function of Moreover, when all < Se' and go to 0, two decreasing functions of dre max W.T. (W.). (W*))-2 and D12(A, M. will be the dominant term of B(A, M, or, W*). Therefore, B(A, M, W*) increases to infinity as all az's go to 0.
Co( mi (W-3, σ
is an
Hence, we have
n 2 poly K6 K)B(A, M, o, W dlogga d
(65)
Similarly, by replacing pl W u. [ σd (W")) with L.m (W .r5x (W*)) when every- thing else except [puس) is fixed, La( [- σlox (W*)) (or -2 W ( σj0 (W*)) for a > 1) when everything else except σ is fixed, (57) can also be transferred to an- other feasible upper bound. We denote the modified version of the convergence rate v = 1 (²2 M.Or, o, W*). Since that (A,, M, a, W*) a ratio between the smallest and the largest singular value of V2 we have q( (A, M, W E (0, Hence, we can obtain " o, W*) (0,1) by K Z 1. When everything clse except |P(9) is fixed, since that L. 6 /4 (W") is monotonically decreasing and El= A(1 + o))² is increasing as |m(() increases, v is an increasing function of [((())] to 1. Similarly, when ev- erything else except 0i is fixed where Ti max(1,Gs), Σl. Ar +o.) decreases to as P oróx(())) by -2 W i4
W mi
W C.(_W"TTm 4
oi increases. We replace p( W
[ o x (W")) and then
25

---

Under review as a conference paper at ICLR 2021
σ². 0 Lo W
Lo o1 016x( Lol W orox(W"))> σrog (W*) is an decreasing function less " odox (W)).. Therefore, is an increasing function of or to 1 when or 2 max (.). When everything else except all 0i S Ca's go to 0, all La( w or6x (W (
than W ue
Maj
(W*)'s
of
and Σis Ae( boo 's decrease to 0. Therefore, v increases 1. The bound of Wn W'IF is directly from (56).
C PROOF OF LEMMA
We first state some important lemmas used in proof in Section C.I and describe the proof in Section C.2. The proofs of these lemmas are provided in Section C.3 to C.7 in sequence. The proof idea mainly follows from (Fu et al. (2020)). Lemma shows the Hessian f2)(W) of the population risk function is smooth. Lemma 7 illustrates that f²f(W) is strongly convex in the neighborhood around y Lemma 8 shows the Hessian of the empirical risk function V f.(")) is close to its population risk ((W() in the local convex region. Summing up these three lemmas, we can derive the proof of Lemma 1. Lemma 4 is used in the proof of Lemma 7. Lemma 5 is used in the proof of Lemma The analysis of the Hessian matrix of the population loss in (Fu et al., 2020) and (Zhong et al., 2017b) can not be extended to the Gaussian mixture model. To solve this problem, we develop new tools using some good properties of symmetric distribution and even function. Our approach can also be applied to other activations like tanh or erf. Moreover, if we directly apply the existing matrix concentration inequalities in these works in bounding the error between the empirical loss and the population loss, the resulting sample complexity would (dd) and cannot reflect the influence of each component of the Gaussian mixture distribution. We develop new version of Bernstein's inequality (see (137)) so that the final bound is Od d).
(Mei et al. (2018a)) showed that the landscape of the empirical risk is close to that of the population risk when the number of samples is sufficiently large for the special case that K = 1. Focusing on Gaussian mixture models, our result explicitly shows how the parameters of the input distribution, including the proportion, mean and variance of cach component will affect the error bound between the empirical loss and the population loss in Lemma 8.
C.I
USEFUL LEMMAS IN THE PROOF OF LEMMA
Lemma 4
E ANi Io) (-(-) (Ep x 000-00o0000 2:1)]] 0000=2))))]
p(u,
(66)
where p(u,, o) is defined in Desinition 3.
Lemma
With the FCN model (2) and the Gaussian Mixture Model (7). for some constant C12 0.
we have
|| xx) <28(W" "VV" m.)1
Ba-Et, A
sup WWW'ER
I| W'
(67)
1 Σ Allllll + t
<C12 d
Σ Aelllalloc + o1)4
Lemma (Hessian smoothness of population loss)In the FCN model (2), assume || l| S 1 for all k. Then for some constant C3 > 0, we have
L
J - -- C5 K²
Σ
Aelllall + OT)*
Xell + )zr)))*
W W'
(68)
26

---

Under review as a conference paper at ICLR 2021
Lemma 7 (Local strong convexity of population loss) In the FCN model (2), if W for an Eo E (0, ( then for some constant C4 >> 0,
W= Sr
4(1
co)
W. arox(W"))
A1
01 ( -aa Z (WS 3 C4
Ae(lluu -ak
K
TJk
1m1
(69)
Lemma 8 In the FCN model (2), as long n C' huve
dK log dK for some constant C' > 0,
dK log
sup W (FON)
J f(W) S C. Aelleellac + +
Σ
(70)
n2
1=1
with probability at least d for some constant Cs
C.2 PROOF OF LEMMA
From Lemma and 8, with probability at least 1 d d=
V fz (W)
f(W) (W) 1/
V
((W) -
V (W)
1.
W pi
0
E0
A
pl
K2
σiōx(
(71)
0(G Σ
Mllmml + o,)²
dK log m
I
1=1
As long as the sample complexity is to satisfy
dK lKl
d1 of nns pl
W 14 (W.)..ox
C
Allluul + t,)²
Σ
(72)
K2
1=1
ie.,
W Hi (wo)(
n 2 Ciep
Σ Aelllpll )3)
σr o(x",)"))))))) dk's log² d (73)
1=1
for some constant C1 > 0, then we have the lower bound of the Hessian with probability at least d 100
2E0
W. HN orox(W-)..10k (1xx))))(
fn W) 2 Ω
(74)
K2
orōx(W-))
By (69) and (70), we can also derive the upper bound as follows,
(2 < ||V2S(W)II || (n. -
dK log
$ C1 M11lo + 01)2 + Cs Σ Acll + +01)²/
n
(75)
S C2 Σ
Ai + 0
for some constant C2 > 0. Combining (74) and (75), have
② 1
200
L
pl nK2
of
o(ox(W-)) o..)(W-).016r 0,0
W
H4
σ15x (W") 1 13 = C2 Σ
X /o0 + 2
K2
1=1
(76)
with probability at least 10
27

---

Under review as a conference paper at ICLR 2021
C.3 PROOF OF LEMMA 4
Following the proof idea in Lemma D.4 of (Zhong et al., 2017b), we have
p. x d' (aaxxx1)) x;))]] Ao + Bo
E New.
(77)
Σ p x. 80 Iz) xx (p:p R
Ag = E "o==NNi.TT++NNi-m.
(78)
Bu = Ex No
d' 12)0'(o xi) xx pi)
(79)
In Ag, we know that E - 0. Therefore,
Ao =
Ban -Bensrteeno p. (oP(o-z))(222 + (Ex,)e
==1
j$1
+ +,je,)) + ΣΣ nymeeee))) Pi
jti I
Σ Bon. (0)(o +
(80)
Ben- (o0 e.e,
j
Σ P. + ΣΣ (1 1=1
==1 jt
In Bo. (i 0) de) (2:0 = 0. By the equation in Page 30 of (Zhong et al.. 2017b), we have
Bo
Σ E En
pi
1:)0((o x)) (0((o-1)600
tffeee n +
x
eie,)) +
Σ Ta + Σ Eajteefe +
ΣΣ , pi
1F1
+ +1]
iff
(81)
Therefore,
Ao + Bo Σ
a2 (,,)) o)
[pioo(l:u.)//1412 2
Pii
11
1+ m
lif
(1,
)r² +
Pio (i, oz) + ΣΣ Σ
2
p So f4, (1 m3))
i=1 tyi
i=1
i=1 j#
a3(1,14, +
Σ pi
(2, ())
B2(i,
pig -abl + 13))
azli,
1+
1=1
im
2 O),
(82)
28

---

Under review as a conference paper at ICLR 2021
C.4 PROOF OF LEMMA 5
Following the equation (92) in Lemma 8 of (Fu et al., 2020) and by (45)
K
K
[[ (PE(W")l <
(w)
(,,(WW)) |
(83)
By Lagrange's inequality, we have
(,,(W) (n'(W)) - (max [Taaa)) ||,||| vK| W W'
(84)
From Lemma 6, we know
max T3 S Cj
(85)
By Property 5, we have
E Et of ||=||
[| d 1)!! Σ
Alllmll + 01)
(86)
Therefore, for some constant C12
( V-((W'))
E (f
sup WFW"
< K
W W'
<K3
d
Acllooo + 01)2
3d
Aelluullo t0))
(87)
L =C12 d²
Σ Nallullll + 01)2 Σ Alllu + o1)*
C.5
PROOF LEMMA
Let (aI.... (T)) E RddK Let Aj V²f(W*) RdKxdk By definition,
Rdxd be the (j.l)-th block of V2S(W)
K Σ a A
(WW (
max Σ
(88)
|a|=1
By the mean value theorem and (45),
f((")) fF((W)
A ow,dw; Ow
E En St., A.N of - ()"(W")) xx 1
(Er,(W"))
Ow ww wx xxx 1
BL A
(89)
=Ea-Ste Aclimn
(Ty..k x, urk uri) x.
where W' >W + (1 W for some 7 (0, 1) and Tyu is defined such that (cx(WW)
T3A x E Rdd Then we provide an upper bound for Egp Since that y = or 0, we first compute the case in which 1. From (45) we can obtain
( = {{
d x) (w, x)
i
H'(Wj.
(90)
[wo (w) x) " * σ (w) x) H(W
j ==1
29

---

Under review as a conference paper at ICLR 2021
We can bound (W) by bounding each components of (90). Note that have
1 K²2 ol (1) ()) (e)o((w) (w) x)) H2WW
1 [[w] x)o(wi x) (1 - p(w) x))(1 6(20, x))
K²
R bw x k))( x)
(91)
(w x) (w x)) 20 w x))
K (w]x x)- H(W)
1
I
(92)
K
K ( x))
where (91) holds for any j, [K]. The case y = 0 can be computed with the same upper bound by
substituting (1 (W)) オ レー (1
K
[[w] x)) for H(W in (90), (91) and (92). Therefore,
there exists constant Cg 0, such that
(w) S Co
(93)
We then need to calculate TaI Following the analysis of Egp1 W), we only consider the case of y here for simplicity.
-2
T3 K3H3(W1) o (wo) (w) a)) Φ)) where j, k k are not equal to each other
(94)
2 ReH कe (w') 2n)dd (w)) x))d (w k x)) + k- o" (w'", 2) (w' x)
j k
Tyssk
K.म (6' (w0) x))² + R-H (ww' 2e (w) x)) 6" 2))
KH(W)> j = k (95)
a. 11100 Ea- Nimoof
Σ
Tyaak (a,, we - ww])
x)]
K
K
E of
J.
E
(x, wt - w w (a]x)(a])))) x))
km
km
K
K
E E E Nlumaf r)
Te
B((wE wz)
Bi(a x) x)4]
R=
Am
K 1|wx - 12112-1a,11 1/a1
< Cs
E Ba
Th
1=1
k=1
1. Acllmul + t01)* Σ
Acll (((1)lllo
for some constant Cs > 0. All the three inequalities of (96) are derived from (96) inequality. Note that we have
-2 K3H (0(w) x))² d' x)) 5
20 (1 (ww Mw)) xx) (w x))
K3 k3 (w) x) x)) x)
(97)
2((1 {(w) x1)] (( $2
2
9' ['mm) z) (w) x) x)o'(w 2
(98)
K3H3(W)
3
K2 d0 (w) x (ww)) x:)
36(w) [w] xx) 21 (11) T x) )1 - 20( ()) ):((1 dlwe [x))
(99)
K² kzz f x)o( x) x)
3(1 6(1) x1) - 26 x)) - (1w) x)) 53
30

---

Under review as a conference paper at ICLR 2021
8T (w x) (
[[w] x) [(w) x)) - 60(w) + x))
<
(100)
K ( w x)
Therefore, by combining (94), (95) and (97) to (100), we have
[T C7 + T S C7 Vj,kk (K), for some constants Cr 0. By (88), (89), (96), (101) and the Cauchy- Inequality, we have
(101)
1V ((W(W))
A + o1) E Aell (omell)++)))))) to))))² 3
SC& W l
K K
Σ |||=1
max
|a31221aa112
jml
1=1
K
CGsVOKK IW 1'
Aelluell + t0)
delll + +1))))²
(
|a51l)
1=1
Aellelloo + t1)))) 7
CC W W
(1 + 0,)
(102)
Hence, we have
Allllpel + w|W W
((W) - v C.K
X Mill bo + +01)*
Σ
1=1
(103)
for some constant C2 > 0.
C.6 PROOF LEMMA
From (Fu et al. (2020)), we know
K
v2f(W*)> > min
K2 Et (
Σ /=1
o' (wwj x)(a} x)) x))² 21
Iak
(104)
|
with a = (a ... , k RdK And
K (ajzr x)²
V²f(W*) max a T f(W")a))
I Iak 3 Cr max E ||a||=
En A
Lak
j=1
(105)
for some constant C4 > O. By applying Property 4, derive the upper bound in (105) as
C4 B..BEEE AM
[(a
Tak 3 C4
Σ 1=1
Aelliii + or)² Lax
(106)
To find a lower bound for (104), can first transfer the expectation of the Gaussian Mixture Model to the weight sum the expectations over general Gaussian distributions.
(
o' (w) 2))(aa x)) I
min E ||||=1
(107)
min
Σ
8' (w a) x))²
||
31

---

Under review as a conference paper at ICLR 2021
Denote U R the orthogonal basis of W For any vector d; E R there exists two vectors b, E R and C E Rd-K such that
a. = Ub; + U-
(108)
where U, E Rdx(d-K) denotes the complement U. We also have U pt = 0 by (9). Plugging (108) into RHS of (107), and then we have
k
N La)
(
Σ
a
x ø' o'w;;" (w;;T))) 1
i=1
(109)
K
Σ
Ub,
Ulci) -e:: 2))² -A+++C
k
A = Em-N(mu (
E DTTTTT x "''Ww =;)"|
(110)
Σ c, U p'(w," ((wx]x))) (Σ U. d'(w," (((w;T))) x))
C Ea
K
K
2c, UI x Eaw U x "lw, T x) (w) 2:] (111)
E of
1=1
Σ
2c U
(enei b. x p'w, x))((u; xx) =0
ui
j=1
where the last step is by UIu 0 (9).
K
c UU x d'wff" x))2
=E BanNimm s)
by defining t = Σ p'ww; (x)c E Ra-K and s = U
Elt +
Σ
El E[tatys;sy)
i
K
1
+
E UUT 44) +
>
Blt,t,((UPP]) p.); -UT mi))
iml
d-K
d-K
(ff?) + [t T U [1) = E 1=1
Σ (77
1=1
(112)
The last step is by U = O. The 4th step is because that is independent of 4, thus B[(t),88,]]= B[L,,,
E[st8g] -{ M.. (UT (II) if +oz ifi=j
(UIM):-UU
(113)
Since (E D. x. 8' a:)) is even function, so from Property 3 we have
k Em-N(ni Σ x' = -ee.dd/Nu...
x;))?
(114)
Combining Lemma and Property 3. we next follow the derivation for the standard Gaussian distribution in Page 36 of (Zhong et al., 2017b) and generalize the result Gaussian distribution
32

---

Under review as a conference paper at ICLR 2021
with arbitrary mean and variance as follows.
K
A = E (1, Tu)
(
E
b
U x
o'w,, )((w;Txx) "
==1
/ (2mot)) $ 1((
-
Σ
b, x 0'(u, x2) 3 exp (
200 (-20pll= 1|=
1
UT pe UTwill 1zll2)dz
/emTot) - [(2 (E
b
vv
8 ((si))
exp
(-
1
|V 8 UT
(mil)) -UUTill
det( voteviiaaa
207
2 / (2mott- - 5/ [(
Σ
k
b,
Vi 8. ((i))
exp
|18
||8- V UT 1Ill
/dei(Vi) do
20% (W*) '07
i=1
2 / (2T) $0 -K K [[E
vt (6x(W d'(6x(("))o (oon)::))) } (b. VTT 5x(W"))g (((ok((W')) s
bi
1=1
11g
W m
1
0jok(
ddel(v)) of ox (W")dg
exp
2
of
Eg
1
of
T
x2 σ1gk (W*)* σ15k (W"))|111)
pl
(115)
The second step is by letting = U x. The third step is by letting = VT z. The last to second
step follows from g = [W-j. where g NV w 14
orbg Ix) and the last inequality is by
Lemma 4. Similarly, we extend the derivation in Page 37 of (Zhong et al., 2017b) for the standard Gaussian distribution to general Gaussian distribution as follows.
of qne (115) and (116), we have
W Mr σiŌx
B = De Ta |||0)1 Combining
pl
orxx ([
(116)
(
of mnu (wo) o(x((")) (117)
W-T
min Be-Nioo |||||=]
a x. p(ww 2))3²/
pl
Am
For the Gaussian Mixture Model
Et N(m, Ia)), we have
h a x o' d'ww; [=]]]))]]]
W.
min E EL A |1
>
1=1 Tys2 (
N
pl
|a
(118)
Therefore,
W* 14 pl
d nna m
σígx (W+) "rr))""'((""))) Lak = ('((W') = Ca Σ Milmill + +01)2
Lak
K2
1=1
(119)
From (68) in Lemma 6, since that we have the condition w -W I r and (53), we can obtain
||V [(W) v2
<CsK 1
Aclluulloo + +1)
Aclllm + W
(120)
4r0
N of
W 11
<
mn? pl
K2
1=1
33

---

Under review as a conference paper at ICLR 2021
where 6o E (0, 2). Then have
[VZ 2 || |
v2r(W)]l
4(1 - 60)
1
d1 of
W 14
(121)
Σ
Pl
( (.....10x(W.))
K²
m
1=1
( & || + | f(W) f(W(I)
4
\ of
W W M
S C4 A1llllloo - +1)
P(
oiok(W-). (idx..xxx.WW (W*))
K2
1=1 nk²
(122)
2 C4 Σ Aelllaloo + o0)2
The last inequality of (122) holds since C4 Ei dellleelloo + 01)² M)
K² Ei=1 de of
W me ni² pl ( σí0k (W*)) ((ox(W))) 0 maxx) and ( 2 92( (22))) Combining (121)
and (122), we have
4(1 60) K2
W. Mr arōk(W.) ( (1kk("))) ( 3 Σ Aclllall + t1)32.
tpp 2 pl
(123)
C.7 PROOF OF LEMMA 8
Let Ne be the e-covering number of the Euclidean ball (WW*, r). It is known that log N, < dK log( 3r) from (Vershynin, 2010). Let W. [ W WN. } be the e-cover set with N, elements. For any W E B(W', r), let jWW) = arg min W W Wowwll S c for all W E ((W",
JE[N.)
Then for any W E 1B (W', Wr),,, have
V f. (W) flI
2 ((W: Vee(W x(W);
(124)
((W (W) E E! AuN(H (V2 x;);
(2E( (W)(w)) -Eg B
V
Ele A (m)
Hence, we have
P sup Web(W-.r)
fa v-) 2))
P(G))
(125)
where A,, B, and C2 are defined
n ((W:,)) : 1
A
sup WeB(W .)) n
3)
(126)
t
B, { sup WEB(W", .))
N V
n
3
E Se ( V" (W (127)
C [ sup
(128)
E EL XnN(Ho (W:
( |
34

---

Under review as a conference paper at ICLR 2021
Then we bound P(A),, P(Bi) and P(C() separately. 1) Upper bound on P(,).. By Lemma 6 in (Fu al., 2020), we obtain
Σ
2 ((W; (L
i=1
(129)
1 Σ
Ba Wt )
<2 sup vEVi
v.
; w:)
n i=l
where V is a --cover of the unit-Enclidean-nom ball (B,0, with log VV the union bound over W. and V3. we have
s dK log 12. Taking
P(B,) <P
sup WEW..
1 G. 2
Σ
7 i=1
(130)
Cexp(dK(log'
3r + log 12))
sup WEW
D G
P(
2=1
where Gi (V'((W,
..i) - ER AM (VW a:)]o)) and E[G.] = 0. Here
=(uu ...,,,,,,, [T E Rd
K
K
E ax uu - -B (f xx mil]
G. =
1=1 1=1
(131)
S Cg
Σ
[ 2x)
E
Baw NNlIp) 2x)2
1=1
1=1
for some C. > 0. The first step (131) is by (44). The last step is by (93) and the Cauchy- Schwarz's Inequality.
35

---

Under review as a conference paper at ICLR 2021
P
(
EI|G,|" -
Σ
Cg. LL
K
2 x) )2)
k
E BN Ia) x)) (u]))))
n-1
1=1
1!
K
Cg E It Ac
E
u x )
I1-=1 1
xx
j=1
Σ
E Ete (L (2)
K
Co
Σ
E Et (f) (3)
1== 15!
4+
E Dt deN(H (a) (u) 2))) 2)))r=
(132)
Co
E Et. (N
K
E El A. Af x) x))) p-1
/=1
K
= Co
B Nn E/, X Xd ( xx))
1=1
K
Aelll + )1)))p
S Cg
!!! 111
Acllmml + )
$ Co
where the second to last inequality results from Property 4. The last inequality is because v E Σj 11, |||||| < 1.
Elexp((GG:) = OE[
p!
< Σ
30
c0p
Cg
Ac + +
(133)
p
p=2
< 1 Cp |e0
Aelle + +o))2)
where the first inequality holds from p! 2 (B)P and (132), and the third line holds provided that
le (1)))
EL >e + +1)))
(p+ 1)(++)
max p22
15
(134)
L
>eCllpeeloo + t01)2)
36

---

Under review as a conference paper at ICLR 2021
Note that the quantity inside the maximization in (134) achieves its maximum when p 2, because it is monotonously decreasing. Therefore, (134) holds if 0 S
27 Σ Allllll o,)². Then
t -P exp(( Gi) 2 exp(
not
G
E elep (6G:)
6
(135)
Mello ) not
S exp exppCin0f
6
for some constant Co0 O. The first inequality follows from the Markov's Inequality. When
0
min
27
E Mello + o1)3), we have modified Bern-
12C10
Els Aelll lo tm.
stein's Inequality for the Gaussian Mixture Model as follows
Ciont
G
E cxp mmaxf-
6
144
E Arlllvelloo
x1)))
(136)
Cun Aell/miloooo to1)² .t)
1=1
for constant Ci 0. We can obtain the same bound for 2 Gi 2 ()) by replacing G as GG,. Therefore, we have
P( Σ G.l 1=1
t - ))
exxp
max
Ciont²
Σl Aelluulloo + t1)) 21
144
(137)
Cun Σ Aclllm +
Thus, as long
dK log
log
dK log 30r log
t t C. max
Aell + {
(138)
El de(lle4elloo + 2
for some large constant C > have P(B.) S
Upper bound on (AA) and (PC)). From Lemma 5, we can obtain
|| AN 2 x[w): (WW((W(():
Ex ANiin (P((W
sup WER(W*.) vn)
EL AW 2 [()) (WW((((w)) EL V2
sup WCB(W*.r)
| Wyw)lle
sup WEB(W-W)) ())
W Wl
L Σ Al + t.)
C12 dikE
Aelluulloo + .
(139)
Therefore, C, holds if
2 C12 dàk3
Σ Mlllii o1)2
A 11 + .c
(140)
37

---

Under review as a conference paper at ICLR 2021
We can bound the A, as below.
<eE(W; x; )ll 9)
(w))a; (WW)(())
sup WEB(W (n)
1=1
t D A
sup WEB(W :r)
222((V (ee((WWwW))) ((W) <<(( x;)]]]
3
Et- Bt
sup WEB(W
V VV ((W)) -V =+)1l
(141)
1
3
V [ x; Vee(W: xz)
sup
sup
I Www)lle
WeB(W-.r)
Wo(woll
WEB(W
C1 . K Els Alll + 01) E'' Anllmmllo + +0))
Thus, taking
C1 dd K3 v
VerVEie Et Aclluuillo + t1)) Ei= Aclll + to)
t Σ
(142)
8
ensures that IP(A,) S 5
2-
3) Final step
Let C12-d K2 /EL. de [m +o Et do (1leille nnk and dd-10 then from (138)
and (142) we need
8 max
Co
Σ 1=1
Allluullo 01)2
ndk
dK log(36rnd 22 K3 Et Aell + +01 Ei= Aello + t1)a) + log 1
dK log 106r33r KÝ V Et., Aelllmlllo 01)² Ete Aellmulloo + t1)) log 3
Et Aellmelloo + 02)2n
(143)
So by setting
1 A:(ll4e1loo + +oi)2/
dk logn as long as n 2 C² dK log dK, we have
dK log
PP sup WEB(W",")
||V2f.(W) &2f(W)1 Co Σ Ao
< dd (144)
1=1
D PROOF OF LEMMA
We first present a lemma used in proving Lemma in Section D.1 and then prove Lemma 2 in Section D.2.
D.I A USEFUL LEMMA USED IN THE PROOF
Lemma r is defined in (53)for co E (0, 1), then with probability at least 10 we have
(W) is defined 1 Ee (VI(W, W.a,, ., vi) 24) in algorithm
38

---

Under review as a conference paper at ICLR 2021
Aelllelllo +0)0gy dlogn (1+ (145)
/ n
sup (W) v/(W)] S C13 WeB(W*.)) .r)
K
for some constant C13 O.
Proof:
Note that (W) (W)
+ E2 vi(w- V/(W) Vf(W). Therefore,
have
(l) vi(W)Il
VV - v)(W)Il + 1 Σ vill (146) F=1
sup W
sup WER(W
Then, similar the idea of the proof of Lemma 8, we adopt an e-covering net of the ball (BW .r) to build a relationship between any arbitrary point in the ball and the points in the covering set. We can then divide the distance between (W) and V((W) into three parts, similar (124). (147) to (149) can be derived in a similar way (126) to (128), with "V2" replaced by "V". Then we need bound P(A)). PBB)) and P(C)) respectively, where A/, B; and C2 are defined below.
A = { sup
WEB(W" s) (e(:; - (WW) (w)
(147)
B.= { sup WEB(W*.r)
(()) E Et A. Ve( ((W)
(148)
== sup WEB(W
| A.V
B Ve(W (W); w;)l
(149)
L E B Au Ve(W: x;)]] 2 "
(a) Upper bound of (B)). Applying Lemma in (Mei al., 201 20) we have
x3:) EL A V :z))
n
(150)
(((W,(w);)) E EaD Af V((W VE(W (w)): ))
$2 sup vEVi
n i=1
Here Rd. To compute V((W, ax)), we require the derivation in Property 6. Then we can have an upper bound of C(W) in (43).
Define G² (u v, (V((W, a.) E of Ve(W, x;
S s(w ((w]a)((1 x)(1- æ))
<(W)
K H(W
8' (w) x))
K d(
1,
y
(151)
o(wn m)(1 j m))
K
1 1
d' (w) x))
<
(1 [(w] m)) < 1,
0
Then we have upper bound of G²₁-
G = 1,,10 T x EawEL AuN o a:|
(152)
< v æ + E Et of) [xT]] æ|]
Following the idea of (132) and (133), and by a E Vg., we have
Aelllullo + +)))))$
E| S
(153)
Elcxp(#G')) < 1 + |GB2|
Σ Alll + t0)
(154)
39

---

Under review as a conference paper at ICLR 2021
27 E
where (154) holds if s
4e V
Aollu oz)?. Following the derivation of (130) and (135)
(138), have
1 Σ G P(
2
72
(155)
C
L
exp max {
Cisn
Aelllulll + 01)2 .2.
144 Ei= Arll + o1)²
for some constant C14 > and C1s O. Moreover, we can obtain P( S as long as
L
(elllplll + V dK log log
dK log log 2
2 C13 max
El= Aclllmill> + t1)) n
(156)
(b) For the upper bound of ((4)) and P(C)). we can first derive
Ve(W x) Ve(W', x
EE A
sup WWW' (r)
I W
((WW) <(W")I ||||||
SB SB AN(H)
sup WWW'EB(W im)
W W
maxIgMSK (S..
[V W
W
< <BEEE AN((I1OP1
sup WWW'EBWW' :m)
IW W
C x / W
W IF
<B ANlinoofTa
sup
WBW'E
W
W
3Co33VKl Σ Aellloo +0)
(157)
The first inequality is by (43). The second inequality is by the Mean Value Theorem. The third step by (93). The last inequality by Property Therefore, following the steps part (2) Lemma 8, conclude that C² holds if
t 2 3Ca VKd Edllalllo + +,)3..c
(158)
I=1
Moreover, from (142) Lemma 8 we have that
18Cg KKd. Σl_ Aelluuloo + 02)2..
(159)
8
ensures P(AA) < 2- Therefore, let 6 = VKd. A (ot 8 d-10 and f =
C13y K K Acllmulloo + t,) dlogn if 2 C" dK log dK for some constant C" we
have
d n
P( sup We
[V) VS(W)II) 2 Cis K
Aclleelloo + o,)2
dd
(160)
By Hoeffding's inequality in (Vershynin, 2010) and Property 1, we have
dk log n
| 2 C1s
X(llAulloo + t
n
(161)
Aell + 01)2 01) Edd 22d logn dk
Sexp( 02
1=1
Sd 10
40

---

Under review as a conference paper at ICLR 2021
Therefore,
dlog
(V)
v/(W]ll S C13
K Aellllll + +o
|4ll
sup W)
dlog
$ C13
K
Aellleeeloo + +opp
|4
dlog (1 ++ E
S C13
K Aelllueloo + to)3g
(162)
D.2 PROOF OF LEMMA 2
Following the proof Theorem in [Fu et al. (2020)), first we have the Taylor's expansion of (w)
Ww, (f (f vee Wn - Wh))
(163)
vec W. W W (W W*)
Here W is on the straight line connecting W and W.. By the fact that fu (n(,,,) S fn(W"), we have
vec W
("") w Vfn(W')) vec(W, W')
(164)
From Lemma and Lemma we have
4
W k
O(ōk(W-)) .. (rr((" W. W
K2
mh
(165)
5 vec Wn
WW*
and
V ( veo vec(W, Wn W-)
V (WW W W
< V(a V I) [W, - W (1 (1+5) W,
(166)
<0( K Aelll )r
doog n
W
The second to last step of (166) comes from the triangle inequality and the last step follows from the fact (W("*) 0. Combining (164), (165) and (166), we have
K VL Σ
Aell + (1) E) +
dlog n
|| W 00
W.TH W o1 (W-)) V
(167)
Therefore, we have concluded that there indeed exists a critical point W in (B(W*,). Then we show the linear convergence of Algorithm as below. By the update rule, we have
W W. W.
To
V fn W.)
Σ vc) - (... V..
(168)
= -(I- / (' (We W.)
770 Σ m
1
41

---

Under review as a conference paper at ICLR 2021
where (1)) ,W,, (1 W, for y E (0,1). Since W(r) E B(W", .r), by Lemma have
miin I (W((())) Hmx
(169)
where Mmin = O R3
Ei 1iml A c my pl
Flok σiδk (W:))) Hmax
W m
C4 Et Ac(lleeello +
o1)². Therefore,
[ W -1 70 / (')(((()))l I, W + 70 villf
(170)
(1- 1o H W. W
Mell ||
By setting 7o Hmax 0 Eisn trll) we obtain
W 41 Walle S1
Hmin Hmax
I[
Walle +
7/0 71
Uellle
(171)
Therefore, Algorithm 1 converges linearly to the local minimizer with an extra statistical error. By Hoeffding's inequality in (Vershynin, 2010) and Property have
dK log
5) exp(< {2dK log n dKE²
P
|elle 2
) 2 d-10
(172)
72
n
Therefore, with probability 1- -t-0 10
we can derive
Hmin ( W.llF Mma
dK log
IW. WallF
(173)
H Hmax
Hmin
n
E PROOF OF LEMMA 3
We need Lemma 10 Lemma 14, which are stated in Section E. for the proof of Lemma 3. Sec- tion E.2 summarizes the proof of Lemma 3. The proofs of Lemma 10 to Lemma 12 are provided in Section E.3 to Section E.5. Lemma and Lemma 14 are cited from (Zhong et al., 2017b). Al- though (Zhong et al., 2017b) considers the standard Gaussian distribution, the proofs of Lemma 13 and 14 hold for any data distribution. Therefore, these two lemmas can be applied here directly. The tensor initialization in (Zhong et al., 2017b) only holds for the standard Gaussian distribution. We exploit a more general definition of tensors from (Janzamin et al. (2014)) for the tensor initial- ization in algorithm. We also develop new error bounds for the initialization.
E. USEFUL LEMMAS IN THE PROOF
Lemma 10 Let P2 follow Definition 1. Let S be set of i...d. samples generated from the mixed Gaussian distribution El= NNN(H, of Let Pa be the empirical version of P3 using data set S. Then with probability at least 1 2n 2n- -0(6()) we have
P2 - Palls dlogn n
(174)
Lemma Lei BBdk be the orthogonal column span of W Let a be a fixed unit vec- for and Ô E gaxk denote an orthogonal matrix satisfying | T - -Ú S Define Ra M2 Ü,Ū), where M3 is defined in Definition 1. Let Ra be the empirical version of R3 using data set S, where each sample of S is i...d. sampled from the mixed Gaussian distribution Σle \NN I Then with probability at least n - we have
log
R Rall 55 (PVDo(A.M,O))
(175)
n
42

---

Under review as a conference paper at ICLR 2021
Lemma 12 Let M1 be the empirical version of M1 using dataset S. Then with probability at least 1 - 2n Q(d), we have
dlog
| - M ( M.)
(176)
n
Lemma 13 ((Zhong et al., 2017b). Lemma E.6) Let P2 be defined in Definition and Pa be its
empirical version. Let E _dd be the column span of W Assume [P - 1-lP - 10
(xx) Then
after T == ) iterations, the output of the Tensor Initialization Method 3, U will satisfy
|| Pall
-UT
t
(177)
5x (P))
which implies
P Pall
II(I 1(0-00T) )um, S
+ e)]lw;f1
(178)
5g (22)
Lemma 14 ([Zhong et al., 2017b), Lemma E.13) Let U E Bd be the orthogonal column span of W". Let U RaxK be orthogonal matrix such that |IUU - 10 S ' S Φ/R. For
each i [K), let 6, denote the vector satisfying || ÜTw, w,,'
1 Let M1 be defined
72 /V:
in Lemma 12 and M1 be its empirical version. M -Mill & 73 M || 2 HllMi] then we have
|||0,||| - au| (K²* (71 + 72) + N² k k w
(179)
E.2 PROOF OF LEMMA 3
[|w3 ā,ا6ر
0, |w 00 + w 06 -
< 3 |w 1
W |3]106 a 2,00,
||,||||
i 06,
||زس||| -5 |6,10
||w|||| w 00 30 +00 2,," - 06, + ||زس|| ay |||0,|111
x (W (1|00) [00"" 00 w) +1+ Ū w, " -611) + |لتس| - 25
(180)
By Lemma 10, Lemma 13 and
S 0% we have
P2 Pa1
d dloog n
57 K
00 - --0 w,," 1
S
7 VDDIAAMM.)DD.A.MM.O
ōK Po)
(181)
d logg n
k² / D2 M,
Moreover, have
K 0% (W.)
K33 log n
8,
R3 R k2 (78 (F
(182)
in which the first step is by Theorem 3 in [Kuleshov et al. (2015)) and the second step is by Lemma 11. By Lemma 14, we have
|||3||| /3 s <*** + +22) + +
(183)
Therefore, taking the union bound of failure probabilities in Lemmas 10, 11 and 12 and by D² M, (A, M. σ) I Do(A, M, o) from Property 7, we have that the sample size n R M. o) -dlog"
2 d. then the output Wo E Raxk satisfies
dlog W'll
W. - W'Il R 6 DoDo
(184)
n
43

---

(187) Under review as a conference paper at ICLR 2021
with probability at least - n -2((6))
E.3 PROOF OF LEMMA 10
From Assumption 1, if the Gaussian Mixture Model is symmetric probability distribution defined in (8), then P2- = M2 ox). Therefore, by Definition we have
-
1
Σ
n
Yi p())
Σ
(2TTT) -expppxxpp---
exp((
|| 11l
209
n2
1=1
(
Mt jou
x 14
100 21) (I,
of
of
| pe 112
E
y
p(a:)
(2(TTOO)) - expl
20
603
x
80 21) (1,
(1)
of
(185)
Following (Zhong et al., 2017b), @ is defined such that for any v E Rd and Z E Rdt Xds,
d2 0 1
2 Z
2, 1 82,
(186)
where 2; is the i-th column of Z. By Definition 1, we have
v. p(x))
A (2TOr) - exp(
|
mill3
x pi
pi
100 21) (1, I,)
207
-
o
Eln (2 1 exp( 1| 1|0-111 u 12)
1 )82 (a T 2 (-
207
Σ/n (2 - 1 exp(
11--1,11 1. 11
20
$ 110 min (2.) T aa,,,,
The first step of (187) is because (² (
(T is the dominant term of the entire ex- pression, and y S 1. The second step is because the expression can be considered as a normal- ized weighted summation of (z y&d (a (* and (x. a)æ;æ? is its dominant term. Define
Sm = (-1)m² V="(()), where p(z) is the probability density function of the random variable x.
p(æ)
From Definition 1, we can verify that
M, = Ely- S. (x)] j E (1,2,3}
(188)
Then define Gp: = (v, (lw Sz (z)))) (La, La, a) [lm (s(xx))(La Id, a)) v)). where ||w||| = 1,
then E[Gp, = 0. Similar to the proof of (131), (132) and (133) in Lemma 8, we have
|Gp.l" S l (z) (xx 0)² + E EL N(m Io (x. ax [xTT))]]
(189)
B[lGp/|'] (E Nw of 18) 10 I (2, [e)TT
1 min
app 2 Dith N Wilm
a 2 &
a BN Mo. 0)413 o
(190)
S D2(A, M, D. M.)
0P E(exp((Gpp)) 1+
(cD), M, o)) p
11+
p!
(191)
44

---

Under review as a conference paper at ICLR 2021
Hence, similar to the derivation of (135), we have
P Gp 21) S exp (-nôt nôt + Cien (7 (,
(192)
1=1
for some constant C16 > 0. Let 0
2010 (f and t = of
(r (oDDAA M, σ))
dogg then we have
d dlog n (193)
Ma(Ia, La) Ma Ia. a) S o0 (.)
with probability at least 2n - If the Gaussian Mixture Model is not symmetric distribution which is defined in (8), then
Ps = M2. We would have a similar result as follows.
|M, M2l1 = | Σ We S2(x)) - Ely S S2(x))]
(194)
K Σ
119: S2(2:))11 2 11omin K
plun xi mx)a,, 1|
(195)
Then define Gp/y (v, (Iy: (2(2) y S2(e:: w)), where ||0|| 1, then E|Gp!!
0.
Similar to the proof of (131). (132) and (133) in Lemma 8, we have
GGyll" 2 m (a: 0)²² + EI N(m., (o minn (a. 1)
(196)
Gp/
2 EB Nf I (c, u)?1) (aTTv))))
S M. 07
(197)
PE G' PP
|e01 D2 M.)
E (exp((Gpp)
- 1 +
11+
p!
(198)
p=2
< 1 6 (2
Hence, similar to the derivation of (135), we have
P
Gp: 2 < exp ( - not + CIrno (ADg(A,,
(-not
(199)
for constant C17 > 0. Let
20 20 (F)))... and t = 57 (7A
d dlog
then have
dlog n
IM, M&ll S -
(200)
with probability at least 2n ((
To sum up. from (193) and (200) have
d log n
||P - Pall
of D))
(201)
d logn o7 DD
n
with probability at least 2n ((674)
45

---

Under review as a conference paper at ICLR 2021
E.4 PROOF OF LEMMA 11
We consider each component of y K Ei=1 oww; x).
Define (x) IR + RKxKRK such that
(x) (6( x)) x)- ((,
(202)
We flatten (x) Rd
k along the first dimension to obtain function
(x) Rdd - RK*K* Similar to the derivation of the last step of Lemma E.8 in (Zhong et al., 2017b), we can obtain [T](x)] = [z)() By (185), we have
K
(x)]l S o miu K
1 Mww a;)((UT x;)
Σ
(203)
f=1
Define Gryy (v, (xx)) (x, where ||a|| 1, so B,Gr,] 0. Similar the proof of (131), (132) and (133) in Lemma 8, we have
Grr, 1 $ o min(( (v Ü UT)
E BE N(mio) lo (v ( x)
(204)
B[]Gr,PP] S (Ba~ Ei M(m.,f Imin (v
(U (TT(T))'))) T Do M, ))
(205)
E(exp(0Gr::) ) 11+ P Gr,P1) 11
|00 Do A, M, o
p!
pp
(206)
p=2
p=2
1 0 (7
M,(A,M,o))
Hence, similar to the derivation of (135), we have
n
Gr. 2t) 1) S exp ( (-not not Cist ( Mo))
(207)
for some constant Cis Let 0
Cia Cir(AV/Da(AMM..))) and 57 (F(,
log then have
logn
RRg Rall S o7. (HVDD((,,M.))
(208)
with probability at least - -2n 2((6))
E.5 PROOF OF LEMMA 12
From the Definition I, we have
[|M Mill = - jy: (i)) Ely S S
(209)
Based on Definition 1,
E1=1 >e(2 exp(
|| 11--1111
(--
20
1
(ww) x; ja
Ele (2TT7) exp(
|| mi
12
min
20
(210)
Define Gq; = (v. (1/ S (a:; )] [ly S (2x; )] l)) where ||0||| = 1, so E.Gq.] 0. Similar to the proof of (131), (132) and (133) in Lemma 8, we have
l < - (2, u) Ea-It Na 1 (2 u)]
(211)
46

---

Under review as a conference paper at ICLR 2021
B|]Gg:|P| x (BowEL, of Imin (1)) v))) S 72p D2(2 M. "
(212)
P | Gq.l" 1"1
|e01">20 2 M,)
E]exp(OGq.) 2 11+
+1+1
2=2 p!
pp
(213)
p=2
11 + 0² (T M2,A,M,,))
Hence, similar to the derivation of (135), we have
Gq 21) S exp ( (- + (P)
P
(214)
for some constant C1 > 0. Let (12 (2)
and (P,
d
then we have
dllo n
| Mil ( (2
(215)
with probability at least
2n R(())
47


Reviews:
[{"review_id": "emvOtsH9fh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the convergence behaviour of the general one-hidden-layer fully connected neural network  in the practical scenario that the input features follow a Gaussian Mixture Model (GMM) distribution. Under certain assumptions, the authors prove that the GMM nduced learning algorithm converges linearly to a critical point  of the empirical risk function, which really  makes a progress on the training convergence study of this network.  However, I  have the following concerns: (1).   What is the ground-truth weights?  For a large traning set, it is possible that there may be no such ground-truth weights. Moroever, the ground-truth weights cannot  form a critical point of the empiirical risk function. So, this assumption is not reasonable. (2).  The assumptin of the Gaussian mixture model is special, not general, and its parameters are  assumed to be known a priori. This  may be too strict and limits the significance of the result. (3). There are some errors  in the mathematical denotations like Eq.(4).\n\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "cO4DVNNjdDU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Update after response of the authors**\n\nThe authors partly corrected the points I mentioned, and I thank them for extensively addressing my comments. However I still believe that the paper oversells its results and analysis, although in a much less strong manner (e.g. in the last sentence of the abstract) and that many concerns remain. For instance, my concern on the tensor initialization has been partially addressed by the authors which showed that it performed as well as a random initialization close to the solution. The very small dimension (d = 5) for which these simulations were performed is however still a concern for verifying this analysis, which would need to be more rigorous and much more extensive to justify replacing the tensor initialization with the random one.\nAs a consequence of all the changes made by the authors, I have raised my grade from 3 to 4 (and I would grade the current state of the paper between 4 and 5).\n\n**Summary:**\n\nThe paper focuses on the behavior of gradient descent in one-hidden-layer neural networks (with fixed second layer weights), in a “teacher-student” setup. In this setup, the labels are generated by an unknown teacher network with the same architecture, and the student aims at recovering the teacher weights. The main ambition of the paper is to provide guarantees for the convergence of gradient descent on the cross-entropy loss, for an input data which comes from a non-trivial model, here a mixture of Gaussians. The algorithm is moreover initialized with a tensor initialization method, which will be crucial to assess its performance. The paper provides a precise theorem to guarantee convergence of this algorithm, and studies how the learning process can depend on the parameters of the mixture of Gaussians. Importantly, the theoretical analysis also relies on the knowledge of these parameters. In particular, they derive limit regimes in which learning should be very hard, e.g. when the variances of the mixture are either very small or very large. They finally provide numerical evidence to support their claims. \n\nGiven the length and available time, I did not check the calculations given in the supplementary material.\n\n**Overall decision:**\n\nConsidering all my criticisms and comments, I cannot recommend publication of this paper at ICLR 2021 as it is. For me to reconsider this decision, the authors would have to slightly improve the quality of the writing (see the remarks and typos), to improve the numerical analysis, and to provide a more convincing presentation of the impact and novelty of their theoretical results with respect to the previous literature. \n\n**Strengths of the paper:**\n\n- The authors provide an involved tensor initialization method to start the gradient descent algorithm, which provably reaches a basin of attraction of a local minimum very close to the true weights.\n\n- The bounds derived in Theorem 1, both on the convergence of the algorithm and on the distance between the local minimum and the true weights are quite explicit, in particular as a function of the number n of samples, the dimension d of the data, and the number K of hidden neurons. Having these two bounds together is important and interesting, as it allows not only to probe the optimization but also the generalization properties. Moreover, the assumptions needed on the activation function (Assumption 1) are quite generic, and allow for a large class of activation functions. \n\n- They show that the sample complexity needed for precise estimation with this algorithm is in the scale $d \\ (\\log d)^2$. I wonder if such a bound is sharp? Also perhaps the authors could comment on the work of [Mei, Bai & Montanari, ‘18], which showed that in this scaling, the landscape of some estimation problems is already trivialized (i.e. close to the population loss landscape). They showed it in particular for a single-hidden-node model: it could be interesting to compare their result with the present paper in the limit $K = 1$.\n\n- Corollary 1 allows to study the impact of the parameters of the mixture of Gaussians (i.e. the structure of the data) on the learning procedure, with the mentioned algorithm. In particular, they show that either too large or too small variances can be detrimental to optimization. While it is intuitive that large variances would harm optimization, the finding on small variances is particularly interesting, as one would expect that small variances in the Gaussian mixture would imply an easier optimization problem. On this point, Fig. 2 is very qualitative, but shows the dependency of the sample complexity on the parameters of the mixture of Gaussians. In particular, Fig.(2b) manages to show the interesting divergence of the sample complexity when the variance goes either to $0$ or $\\infty$. \n\n- Figures 3 and 4 do a decent job at showing the dependency of the final convergence time on the parameters of the mixture, of the convergence rate on the size of the hidden layer, and of the distance of the true weights to the critical point achieved by gradient descent on the number of samples. The results are quite consistent with the theoretical analysis. \n\n**Concerns and remarks:** \n\n- In the introduction, the authors explain that they consider a setup in which the labels are generated by a ground truth network, and provide some recent literature on this hypothesis. They however do not mention that this assumption is known as the “teacher-student” setup, and it has been studied for a long time in the statistical learning community (in particular from a statistical physics point of view in which such a setup is very natural). The paper should correct this point by providing a much more exhaustive view of the literature on this topic. For instance, they can refer to [Seung, Sompolinsky & Tishby ‘92], [Engel & Van den Broeck ‘01]. See also [Goldt & al, NeurIPS’19] for recent applications to neural networks. \n\n- Fig 1 (in the numerical experiments) is somehow unclear. While the authors pretend that the sample complexity needed to recover is indeed almost linear in d, this is not obvious from the picture. Moreover, the difference in orders of magnitudes between n (from 6000-60 000) and d (from 1 to 30) indicate that, even with a quasi-linear dependency, the prefactor would be huge, and the authors should discuss this point.\n\n My two main concerns are the following:\n\n- First, as emphasized in the beginning of Section 4, the tensor initialization is crucial, as it actually returns an estimate already in the basin of attraction of a critical point very close to the ground truth.  However, in Section 5 (on the numerics), the authors precise “We use random initialization rather than tensor initialization to reduce the computational time”, without any justification of how this could impact the results. This reduces greatly the relevance of these numerical results, and their relation with the theoretical findings. This also raises the question: is the tensor initialization numerically tractable? If the tensor initialization provably returns an estimate in the correct basin of attraction, this algorithm is actually doing the most important part of the estimation, and replacing it with a random initialization close to the ground truth removes a lot of the relevance of the theoretical findings (as obviously, when starting in a convex region, gradient descent will work). \n\n- Secondly, the following bold claims can be found in the abstract and the main text, and are very emphasized:\n\n1) “Instead of following the conventional and restrictive assumption in the literature that the input features follow the standard Gaussian distribution, this paper, for the first time, analyzes a more general and practical scenario that the input features follow a Gaussian mixture model of a finite number of Gaussian distributions of various mean and variance.”\n2) “This paper provides the first theoretical analysis of learning one-hidden-layer neural networks when the input distribution follows a Gaussian mixture model containing an arbitrary number of Gaussian distributions with arbitrary mean and variance.”\n\n3) “This is the first theoretical characterization about how the input distribution affects the learning performance.”\n\n4) “Theorem 1 provides the first theoretical guarantee of learning one-hidden-layer neural networks with the input following the Gaussian mixture model.”\n\n    In my point of view, these are exaggerated statements. While it is true that there is ample room for new studies of non-trivial input distributions, several previous and impacting papers have followed very similar approaches, beyond [Du&al ‘17] which is the only paper cited by the authors in this context. For instance, the following (very incomplete) list of papers all either consider training a one-hidden-layer neural net on a dataset with a non-trivial covariance, or a mixture of Gaussians data model:\n    1. Mei, Montanari & Nguyen [PNAS 2018] study one-hidden-layer networks in the mean-field limit trained on a large class of distributions, including a mixture of Gaussians with the same mean (see Fig 1 of the paper). \n    2. Li & Liang [NeurIPS 2018] studied over-parameterized one-hidden-layer nets \"when the data comes from mixtures of well-separated distributions\".\n    3. Yoshida & Okada [NeurIPS 2019] study one-hidden-layer neural networks with inputs drawn from a single Gaussian with arbitrary covariance.\n    4. Goldt et al. (arXiv:1909.11500 and arXiv:2006.14709) study one-hidden-layer networks with inputs drawn from a wide class of generative models. \n    5. Mignacco et al. (arXiv:2006.06098) give exact equations for the size-one minibatch SGD evolution in a perceptron (i.e. a single-node network) trained on a mixture of Gaussians. \n    6. Ghorbani et al. (arXiv:2006.13409) consider labels which depend on low-dimensional projections of the inputs, which, I believe, is very related to a mixture of Gaussians.\nSome of the papers in this list (e.g. [1,2,4,6]) also provide a rigorous analysis of some of their results.\n\nWhile, to the best of my knowledge, the theoretical results of the present paper (i.e. global convergence guarantees for gradient descent with tensor initialization, for data coming from a mixture of Gaussians) are indeed new, their impact and novelty is, I believe, exaggerated. In particular, similar results already exist in the literature cited above, and the new results of this paper should be discussed in comparison to them. \n\n**Minor points and questions:**\n\n- The notations section is very long. While some precisions are useful, many are very standard (N, Z, R, or the transpose, or the L2 norm) and, I believe, do not have to be reminded. Similarly, the footnote at the end of page 5 is not necessary. \n\n- The paper studies one-hidden-layer neural networks with fixed second layer weights. The authors should mention that this setup is known as the committee machine, and they should refer to some literature on this (besides some references given in the concerns section, one can for instance refer to [Aubin&al NeurIPS 2018, Schwarze&al ‘92,’93, Monasson&Zecchina ‘95] and many others).\n\n- Is it possible to add a noise in the gradient descent algorithm without affecting the theoretical findings? Even an uncorrelated noise (i.e. Langevin dynamics), as I expect that the noise in plain SGD will not be easily tractable.\n\n- Algorithm 1 requires a constant learning rate: I wonder if the authors tried (even just numerically) to see if the bounds could be improved by considering an adaptive learning rate (for instance with a linear decrease)?\n\n**Typos:**\n\n- At the beginning of the introduction: “Neural” → “neural”.\n- Just after, I believe: “theoretical underpin of leaning neural networks” → “theoretical underpin of learning in neural networks”.\n- Again, just after: “lack of the theoretical generalization guarantee” → “lack of theoretical generalization guarantees”.\n- In the “Contributions” paragraph,  the “etc” when listing the applications of the Gaussian mixture model does not read well. \n- In the “Contributions”: “One interesting finding is the”→ “One interesting finding is that”.\n- Just after: “all the variance approaches” → “all the variances approach”.\n- In Section 2: “Let kappa denote the number that kappa =...” → “Let kappa = …”\n- Below eq.(6): sigma_l \\in R → sigma_l \\in R_+.\n- End of page 4: “more details of” → “more details on”\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OcLZ-ge8IZ0", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the paper, the authors provide theoretical analysis of learning one-hidden-layer neural networks when the input distribution follows a mixture of location-scale Gaussian distributions instead of single location-scale Gaussian distribution as in the previous work. I think the results in the paper are interesting \n\nHere are my comments with the paper:\n\n(1) The literature with Gaussian mixtures is quite poor. Except for the references with the application of Gaussian mixtures in the paper, I think the authors may consider adding a few more relevant references about theoretical aspect of Gaussian mixtures. For instance, the work of [1] provides convergence rate/ sample complexity for estimating unknown location and scale parameters when the data are generated from Gaussian mixtures. Furthermore, the work of [2] provide theoretical analysis of optimization algorithms, such as gradient descent/ EM/ Newton algorithms,  for learning location and scale parameters in Gaussian mixtures (Section 4.2 in this work).\n\n(2) The assumption that the weight, location, scale of Gaussian mixtures as well as the number of components $L$ are known is quite strong in my opinion. In particular, the number of components $L$ in Gaussian mixtures is rarely known in practice; therefore, we usually choose some $\\bar{L}$ as the number of components and $\\bar{L}$ can be much larger than $L$. By doing that, we overspecify the number of components in Gaussian mixtures. This over-specification leads to the slow convergence rates of estimating weight, location, scale of Gaussian mixtures; see the references [1], [2], and [3]. For the settings that being considered by the authors, when $\\bar{L} = L + 1$, if we use EM algorithm, the convergence rates of estimating these parameters from the EM algorithm for location parameter is $(d/n)^{1/4}$ and for scale parameter is $(d/n)^{1/2}$ when $d \\geq 2$ (n stands for the sample size) (see references [2], [3], and [4] for details). Therefore, in light of the results in the paper, the total sample complexity is $\\sqrt{d \\log n/n} + (d/n)^{1/4}$ when the parameters of Gaussian mixtures are unknown. When the covariance matrices are not spherical and $\\bar{L} > L$, the work of [1] show that the sample complexity of estimating location and covariance matrices depends on the solvability of a system of polynomial equations and eventually grows with $\\bar{L} - L$. I think the authors should provide a clarification of these points in the paper.\n\n(3) The paper specifically assumes that the covariance matrices of each component are $\\sigma_{l}^2 I_{d}$, i.e., homogeneous among all dimension in each subpopulation. When the covariance matrices have a bit more realistic structures like $\\text{diag}(\\sigma_{l1}^2, \\ldots, \\sigma_{ld}^2) I_{d}$ for all $1 \\leq l \\leq L$, will the results in Theorem 1 still hold?\n\n(4) In Theorem 1, what is the intuition behind $K^{5/2}$ and $\\Gamma(\\lambda, M, \\sigma, W^{*})$$ on the difference between $\\widehat{W}_{n}$ and $W^{*}$ as well as $D_{12}$ in the condition of sample size $n$?\n\n(5) Can the authors provide some initial theoretical analysis/ discussion for the setting of multi-layer neural networks? I agree that one layer neural network is quite interesting; however, it will be useful for the readers to understand the challenges of extending the \ncurrent results to the multi-layers settings.\n\n(6) A few minor comments:\n\n- In Definition 1, what is $M_{3}(I_{d}, I_{d}, \\alpha)$?\n\n\n\nReferences:\n\n[1] N. Ho and L. Nguyen. Convergence rates of parameter estimation for some weakly identifiable finite mixtures. Annals of Statistics, 44(6), 2726-2755, 2016\n\n[2] N. Ho, R. Dwivedi, K. Khamaru, M. J. Wainwright, M. I . Jordan, B. Yu. Instability, computational efficiency and statistical accuracy. Arxiv preprint Arxiv: 2005.11411.\n\n[3] R. Dwivedi, N. Ho, K. Khamaru, M. J. Wainwright, M. I. Jordan, B. Yu. Singularity, misspecification, and the convergence rate of EM. To appear, Annals of Statistics.\n\n[4] R. Dwivedi, N. Ho, K. Khamaru, M. J. Wainwright, M. I. Jordan, B. Yu. Sharp analysis of Expectation-Maximization for weakly identifiable models. AISTATS, 2020.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FWh1zp9Nhtt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of learning one-hidden-layer neural networks with Gaussian mixture input in the teacher-student setting. The authors consider the neural network with sigmoid activation functions and the learning algorithm is gradient descent plus tensor initialization.  There is a line of research studying such a problem, and the main contribution of the current paper is to extend the standard Gaussian input distribution to the mixture of Gaussian input distribution. My main concern is the contribution of the current paper. The main techniques used in this paper seem to be based on existing approaches in Fu et al, 2020 and Zhong et al, 2017, and the Gaussian mixture input setting considered in this paper seems not to be very interesting and realistic. Here are some problems I have for the current paper:\n1. Please clarify the main differences of the current analysis compared with Fu et al, 2020 and Zhong et al, 2017.\n2. Please elaborate more about Assumption 1. Intuitively, what can we imply from this assumption and why you think it is a mild assumption?\n3. The description of the tensor initialization at the end of page 4 is not very clear.\n4. Please add some comments on functions in Definition 2,3,4. It is unclear what are the meanings of these functions.\n5. Thereom 1 looks not correct since there is no requirement on the step size in Algorithm1. In addition, why the parameter v can belong to (0,1)?\n6. Since the paper claims to use tensor initialization, the experiments should also include such results.\n7. The presentation of the current paper is good. However, there are some concurrent works [1,2] also study the training and generalization of neural networks, the authors may want to discuss them in the introduction section.\n\nReference:\n[1] Zou, Difan, et al. \"Gradient descent optimizes over-parameterized deep ReLU networks.\" Machine Learning 109.3 (2020): 467-492.\n[2] Cao, Yuan, and Quanquan Gu. \"Generalization bounds of stochastic gradient descent for wide and deep neural networks.\" Advances in Neural Information Processing Systems. 2019.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gives a way to learn one-hidden-layer neural networks on when the input comes from Gaussian mixture model. The main algorithm uses [Janzamin et al. 2014] as an initialization and then performs gradient descent. The main contribution of this paper is 1. to give a characterization of sample complexity for estimating the moment tensors when the input distribution comes from a mixture of Gaussian; 2. to give a local convergence result when the samples come from a mixture of Gaussian. The paper claims certain behavior in the input data would make the problem harder and slow down the convergence, although the claim is based on an upperbound and would be stronger if there is some corresponding lowerbound.
Decision: Reject