Theoretical properties of the global optimizer of two layer neural network

Abstract

In this paper, we study the problem of optimizing a two-layer artificial neural network that best fits a training dataset. We look at this problem in the setting where the number of parameters is greater than the number of sampled points. We show that for a wide class of differentiable activation functions (this class involves "almost" all functions which are not piecewise linear), we have that first-order optimal solutions satisfy global optimality provided the hidden layer is non-singular. Our results are easily extended to hidden layers given by a flat matrix from that of a square matrix. Results are applicable even if network has more than one hidden layer provided all hidden layers satisfy non-singularity, all activations are from the given "good" class of differentiable functions and optimization is only with respect to the last hidden layer. We also study the smoothness properties of the objective function and show that it is actually Lipschitz smooth, i.e., its gradients do not change sharply. We use smoothness properties to guarantee asymptotic convergence of O(1/number of iterations) to a first-order optimal solution. We also show that our algorithm will maintain non-singularity of hidden layer for any finite number of iterations.

References in corpus (8)

• Understanding deep learning requires rethinking generalization
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• The loss surface of deep and wide neural networks
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• Generalized Uniformly Optimal Methods for Nonlinear Programming

Cited by in corpus (15)

• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• Optimization for deep learning: theory and algorithms
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• Understanding the Loss Surface of Neural Networks for Binary Classification
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Can SGD Learn Recurrent Neural Networks with Provable Generalization?
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
• Making Method of Moments Great Again? -- How can GANs learn distributions
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Neural Optimization Kernel: Towards Robust Deep Learning
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Towards Scalable Koopman Operator Learning: Convergence Rates and A Distributed Learning Algorithm