We study model recovery for data classification, where the training labels are generated from a one-hidden-layer fully -connected neural network with sigmoid activations, and the goal is to recover the weight vectors of the neural network. We prove that under Gaussian inputs, the empirical risk function using cross entropy exhibits strong convexity and smoothness uniformly in a local neighborhood of the ground truth, as soon as the sample complexity is sufficiently large. This implies that if initialized in this neighborhood, which can be achieved via the tensor method, gradient descent converges linearly to a critical point that is provably close to the ground truth without requiring a fresh set of samples at each iteration. To the best of our knowledge, this is the first global convergence guarantee established for the empirical risk minimization using cross entropy via gradient descent for learning one-hidden-layer neural networks, at the near-optimal sample and computational complexity with respect to the network input dimension. Neural networks have attracted a significant amount of research interest in recent years due to the success of deep neural networks BID18 in practical domains such as computer vision and artificial intelligence BID24 BID15 BID27 . However, the theoretical underpinnings behind such success remains mysterious to a large extent. Efforts have been taken to understand which classes of functions can be represented by deep neural networks BID7 BID16 BID0 Telgarsky, 2016) , when (stochastic) gradient descent is effective for optimizing a non-convex loss function BID8 , and why these networks generalize well BID1 .One important line of research that has attracted extensive attention is a model-recovery setup, i.e., given that the training samples (x i , y i ) ∼ (x, y) are generated i.i.d. from a distribution D based on a neural network model with the ground truth parameter W , the goal is to recover the underlying model parameter W , which is important for the network to generalize well BID22 . Previous studies along this topic can be mainly divided into two types of data generations. First, a regression problem, for example, assumes that each sample y is generated as y = 1 K K k=1 φ(w k x), where w k ∈ R d is the weight vector of the kth neuron, 1 ≤ k ≤ K, and the input x ∈ R d is Gaussian. This type of regression problem has been studied in various settings. In particular , BID28 studied the single-neuron model under ReLU activation, BID38 ) studied the onehidden-layer multi-neuron network model, and BID19 ) studied a two-layer feedforward networks with ReLU activations and identity mapping. Second, for a classification problem, suppose each label y ∈ {0, 1} is drawn under the conditional distribution P(y = 1|x) = 1 K K k=1 φ(w k x), where w k ∈ R d is the weight vector of the kth neuron, 1 ≤ k ≤ K, and the input x ∈ R d is Gaussian. Such a problem has been studied in BID21 in the case with a single neuron.For both the regression and the classification settings, in order to recover the neural network parameters, all previous studies considered (stochastic) gradient descent over the squared loss, i.e., qu (W ; x, y) = DISPLAYFORM0 Furthermore, previous studies provided two types of statistical guarantees for such model recovery problems using the squared loss. More specifically , BID38 showed that in the local neighborhood of the ground truth, the Hessian of the empirical loss function is positive definite for each given point under independent high probability event. Hence, their guarantee for gradient descent to converge to the ground truth requires a fresh set of samples at every iteration, thus the total sample complexity will depend on the number of iterations. On the other hand, studies such as BID21 BID28 establish certain types of uniform geometry such as strong convexity so that resampling per iteration is not needed for gradient descent to have guaranteed linear convergence as long as it enters such a local neighborhood. However, such a stronger statistical guarantee without per-iteration resampling have only been shown for the squared loss function. In this paper, we aim at developing such a strong statistical guarantee for the loss function in eq. (2), which is much more challenging but more practical than the squared loss for the classification problem. In this paper, we have studied the model recovery of a one-hidden-layer neural network using the cross entropy loss in a multi-neuron classification problem. In particular, we have characterized the sample complexity to guarantee local strong convexity in a neighborhood (whose size we have characterized as well) of the ground truth when the training data are generated from a classification model. This guarantees that with high probability, gradient descent converges linearly to the ground truth if initialized properly. In the future, it will be interesting to extend the analysis in this paper to more general class of activation functions, particularly ReLU-like activations; and more general network structures, such as convolutional neural networks BID10 BID37 .
We provide the first theoretical analysis of guaranteed recovery of one-hidden-layer neural networks under cross entropy loss for classification problems.
{"src": "scitldr-AIC_train", "paper_id": "HJlfAo09KX"}