Convexified Convolutional Neural Networks

By Yuchen Zhang, Percy Liang, Martin J. Wainwright. 2016

66 citations recorded by the source corpus.

We describe the class of convexified convolutional neural networks (CCNNs), which capture the parameter sharing of convolutional neural networks in a convex manner. By representing the nonlinear convolutional filters as vectors in a reproducing kernel Hilbert space, the CNN parameters can be represented as a low-rank matrix, which can be relaxed to obtain a convex optimization problem. For learning two-layer convolutional neural networks, we prove that the generalization error obtained by a convexified CNN converges to that of the best possible CNN. For learning deeper networks, we train CCNNs in a layer-wise manner. Empirically, CCNNs achieve performance competitive with CNNs trained by backpropagation, SVMs, fully-connected neural networks, stacked denoising auto-encoders, and other baseline methods.

Subfields: Artificial Intelligence, Computational Mechanics

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 Mechanics

Citations in the corpus

BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain (2017, methodology): “Our baseline network for this task is a CNN with two convolutional layers and two fully connected layers [38].”
Federated Multi-Task Learning (2017, background): “While MOCHA does not apply to non-convex deep learning models in its current form, we note that there may be natural connections between this approach and “convexified” deep learning models [6, 34, 51, 56] in the context of kernelized federated multi-task learning.”
Deriving Neural Architectures from Sequence and Graph Kernels (2017, methodology): “It turns out that many activations are also functions in the reproducing kernel Hilbert space (RKHS) of certain kernel functions (see Shalev-Shwartz et al. (2011); Zhang et al. (2016)).”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “(Zhang et al., 2016a;b) propose kernel methods to learn the prediction function which is guaranteed to have generalization performance close to that of the NN.”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Various recent papers show that poly-time learning is possible in the case that the the learnt function can be realized by a neural network with certain (usually fairly strong) restrictions on the weights [23, 34, 33, 35], or under the assumption that the data is generated by a generative model that”
A comparison of deep networks with ReLU activation function and linear spline-type methods (2018, background): “For a result of the same flavor, see Theorem 1 in [23].”
Group Invariance, Stability to Deformations, and Complexity of Deep Convolutional Representations (2017, unknown): “As noticed by Zhang et al. (2016, 2017b), this is for instance the case for the inverse polynomial kernel.”
Neural Taylor Approximations: Convergence and Exploration in Rectifier Networks (2016, background): “A convex multi-layer architectures are developed in Aslan et al. (2014); Zhang et al. (2016).”
A Kernel Perspective for Regularizing Deep Neural Networks (2018, unknown): “The construction of hierarchical kernels and the study of neural networks in the corresponding RKHS was studied by Mairal (2016); Zhang et al. (2016; 2017); Bi-etti & Mairal (2019).”
Invariance and Stability of Deep Convolutional Representations (2017, unknown): “(Left) non-homogeneous setting of [35, 36].”
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud (2017, methodology): “Neural Networks For the two MNIST tasks, we used a convolutional neural network same as [21] with 2 convolutional layers with 5 × 5 filters, a stride of 1 and a mapcount of 16 and 32 for the first and second layer respectively.”
A Provably Correct Algorithm for Deep Learning that Actually Works (2018, methodology): “The work of [19] analyses a method of learning a model similar to CNN which can be applied to learn multi-layer networks, but the analysis is limited to shallow two-layer settings, when the formulated problem is convex.”
On Regularization and Robustness of Deep Neural Networks (2018, methodology): “The construction of hierarchical kernels and the study of neural networks in the corresponding RKHS was studied by Mairal (2016); Zhang et al. (2016; 2017); Bietti & Mairal (2018).”
Invisible Backdoor Attacks on Deep Neural Networks Via Steganography and Regularization (2019, methodology): “4 Network 6CNN+2FC 6CNN+2FC 6CNN+2FC 6CNN+2FC Dataset GTSRB GTSRB GTSRB GTSRB Target classes [1-43] [1-43] [1-43] [1-43] Trigger Number 43 43 43 43 Inject Rate (Each Class) 0.”
BadNets: Evaluating Backdooring Attacks on Deep Neural Networks (2019, methodology): “Our baseline network for this task is a CNN with two convolutional layers and two fully connected layers [49].”