Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels

By Kai Zhong, Zhao Song, Inderjit S. Dhillon. 2017

75 citations recorded by the source corpus.

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 $\mathit{~locally~strongly~convex}$ 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.

Subfields: Artificial Intelligence, Computational Mathematics, Computer Vision and Pattern Recognition, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “In a second concurrent work, Zou et al. (2018) also analyzed the convergence of gradient descent on fully-connected networks with ReLU activation. The emphasis is on different loss functions (e.g. hinge loss), so the results are not directly comparable. Both Zou et al. (2018) and Allen-Zhu et al.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Researchers have made various assumptions to get a better theoretical understanding of training neural networks, such as Gaussian input assumption (Brutzkus et al., 2017; Du et al., 2017a; Zhong et al., 2017) and independent activation assumption (Choromanska et al., 2015; Kawaguchi, 2016).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Many of them focus on two-layer (thus one-hidden-layer) neural networks and assume that the inputs are random Gaussian or sufﬁciently close to Gaussian [7, 15, 18, 32, 37, 50, 55, 60, 61].”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “Following [Zhong et al., 2017a,b, Li and Yuan, 2017, Tian, 2017, Brutzkus and Globerson, 2017, Shalev-Shwartz et al., 2017b], in this paper, we mainly focus on the population loss: Algorithm 1 GD for Learning One-Hidden-Layer CNN with Weight Normalization .”
Learning Compact Neural Networks with Regularization (2018, methodology): “…are closely related to the recent works on provably learning shallow neural nets (Zhong et al., 2017b; Tian, 2017; Soltanolkotabi, 2017; Panigrahy et al., 2018; Ge et al., 2017; Oymak & Soltanolkotabi, 2018; Zhong et al., 2017a; Safran & Shamir, 2017; Arora et al., 2014; Mei et al., 2016).”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, methodology): “Focusing on gradient-based algorithms, a line of research (Tian, 2017; Brutzkus and Globerson, 2017; Zhong et al., 2017a;b; Li and Yuan, 2017; Du et al., 2017b;c) analyzed the behavior of (stochastic) gradient descent with a structural assumption on the input distribution.”