Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

Abstract

In this paper, we consider parameter recovery for non-overlapping convolutional neural networks (CNNs) with multiple kernels. We show that when the inputs follow Gaussian distribution and the sample size is sufficiently large, the squared loss of such CNNs is $locallystronglyconvex$ in a basin of attraction near the global optima for most popular activation functions, like ReLU, Leaky ReLU, Squared ReLU, Sigmoid and Tanh. The required sample complexity is proportional to the dimension of the input and polynomial in the number of kernels and a condition number of the parameters. We also show that tensor methods are able to initialize the parameters to the local strong convex region. Hence, for most smooth activations, gradient descent following tensor initialization is guaranteed to converge to the global optimal with time that is linear in input dimension, logarithmic in precision and polynomial in other factors. To the best of our knowledge, this is the first work that provides recovery guarantees for CNNs with multiple kernels under polynomial sample and computational complexities.

arXiv admin note: text overlap with arXiv:1706.03175

References in corpus (2)

• On the Expressive Power of Deep Neural Networks
• Most tensor problems are NP-hard

Cited by in corpus (25)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• On the Convergence Rate of Training Recurrent Neural Networks
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• Stationary Points of Shallow Neural Networks with Quadratic Activation Function
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• Generalized Leverage Score Sampling for Neural Networks
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• On the Learnability of Deep Random Networks
• Theory III: Dynamics and Generalization in Deep Networks
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• MixCon: Adjusting the Separability of Data Representations for Harder Data Recovery
• Recursive Sketches for Modular Deep Learning
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
• Towards Searching Efficient and Accurate Neural Network Architectures in Binary Classification Problems
• On the Learning Dynamics of Two-layer Nonlinear Convolutional Neural Networks
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
• Nearly Minimal Over-Parametrization of Shallow Neural Networks
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• Learning Graph Neural Networks with Approximate Gradient Descent
• Training Linear Neural Networks: Non-Local Convergence and Complexity Results