Neural networks have been used prominently in several machine learning and statistics applications. In general, the underlying optimization of neural networks is non-convex which makes their performance analysis challenging. In this paper, we take a novel approach to this problem by asking whether one can constrain neural network weights to make its optimization landscape have good theoretical properties while at the same time, be a good approximation for the unconstrained one. For two-layer neural networks, we provide affirmative answers to these questions by introducing Porcupine Neural Networks (PNNs) whose weight vectors are constrained to lie over a finite set of lines. We show that most local optima of PNN optimizations are global while we have a characterization of regions where bad local optimizers may exist. Moreover, our theoretical and empirical results suggest that an unconstrained neural network can be approximated using a polynomially-large PNN.
References @cite_19 @cite_4 @cite_9 consider a two-layer neural network with Gaussian inputs under a matched (realizable) model where the output is generated from a network with planted weights. Moreover, they assume the number of neurons in the hidden layer is smaller than the dimension of inputs. This critical assumption makes the loss function positive-definite in a small neighborhood near the global optimum. Then, reference @cite_9 provides a tensor-based method to initialize the local search algorithm in that neighborhood which guarantees its convergence to the global optimum. In our problem formulation, the number of hidden neurons can be larger than the dimension of inputs as it is often the case in practice. Moreover, we characterize risk landscapes for a certain family of neural networks in all parameter regions, not just around the global optimizer. This can guide us towards understanding the reason behind the success of local search methods in practice.
@cite_19 @cite_9 @cite_4
2750924312 2625063094 2593709294
In this paper, we use dynamical system to analyze the nonlinear weight dynamics of two-layered bias-free networks in the form of @math , where @math is ReLU nonlinearity. We assume that the input @math follow Gaussian distribution. The network is trained using gradient descent to mimic the output of a teacher network of the same size with fixed parameters @math using @math loss. We first show that when @math , the nonlinear dynamics can be written in close form, and converges to @math with at least @math probability, if random weight initializations of proper standard derivation ( @math ) is used, verifying empirical practice. For networks with many ReLU nodes ( @math ), we apply our close form dynamics and prove that when the teacher parameters @math forms orthonormal bases, (1) a symmetric weight initialization yields a convergence to a saddle point and (2) a certain symmetry-breaking weight initialization yields global convergence to @math without local minima. To our knowledge, this is the first proof that shows global convergence in nonlinear neural network without unrealistic assumptions on the independence of ReLU activations. In addition, we also give a concise gradient update formulation for a multilayer ReLU network when it follows a teacher of the same size with @math loss. Simulations verify our theoretical analysis. In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to @math in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show @math guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity @math and computational complexity @math for smooth homogeneous activations with high probability, where @math is the dimension of the input, @math ( @math ) is the number of hidden nodes, @math is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, @math is the targeted precision and @math is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity @math in the input dimension and @math in the precision. In this paper, we explore theoretical properties of training a two-layered ReLU network @math with centered @math -dimensional spherical Gaussian input @math ( @math =ReLU). We train our network with gradient descent on @math to mimic the output of a teacher network with the same architecture and fixed parameters @math . We show that its population gradient has an analytical formula, leading to interesting theoretical analysis of critical points and convergence behaviors. First, we prove that critical points outside the hyperplane spanned by the teacher parameters ("out-of-plane") are not isolated and form manifolds, and characterize in-plane critical-point-free regions for two ReLU case. On the other hand, convergence to @math for one ReLU node is guaranteed with at least @math probability, if weights are initialized randomly with standard deviation upper-bounded by @math , consistent with empirical practice. For network with many ReLU nodes, we prove that an infinitesimal perturbation of weight initialization results in convergence towards @math (or its permutation), a phenomenon known as spontaneous symmetric-breaking (SSB) in physics. We assume no independence of ReLU activations. Simulation verifies our findings.