Abstract
Neural networks have recently re-emerged as a powerful hypothesis class, yielding impressive classification accuracy in multiple domains. However, their training is a non-convex optimization problem. This paper introduces Improper Deep Kernels (IDK), which treat a neural network as a feature mapping and learn a "mixture" of all possible weight configurations. This approach transforms the notoriously difficult non-convex optimization of deep networks into a globally optimal, convex SVM problem with a closed-form recursive kernel.
Introduction
Training deep neural networks is traditionally a "proper" learning task: the goal is to find the single best set of weights for a specific architecture. Due to non-linearities, this results in a non-convex loss surface filled with local minima, requiring researchers to rely on heuristics like dropout, specific initializations, and complex learning rate schedules.
In contrast, kernel methods, such as Support Vector Machines (SVMs), are convex and offer global optimality. However, they traditionally struggle to capture the hierarchical, compositional features that make deep learning so powerful. This research explores whether the power of deep architectures can be leveraged within the mathematically well-behaved framework of kernel methods.
Methodology: Improper Learning and Recursive Kernels
The authors employ a strategy called improper learning. Instead of searching for one specific neural network, they define a new feature space where the features are the outputs of a neural network for every possible weight configuration. They then learn a linear classifier in this infinite-dimensional space.
The Kernel Construction
The key technical breakthrough is proving that for deep networks using threshold activation functions (step functions), the inner product in this infinite-dimensional space—the kernel—can be calculated exactly. The kernel is defined as the integral over all possible weight instantiations of the network.
Closed-Form Recursion
The authors derive a recursive formula that allows for the computation of this kernel for a network of any depth by building up from the input layer. Once the kernel is computed, the learning problem becomes a standard dual quadratic program (an SVM), which is guaranteed to find a global optimum.
Experimental Evaluation
The Improper Deep Kernel (IDK) was evaluated on synthetic data and standard image recognition benchmarks.
Synthetic and Numerical Analysis
On synthetic data generated by a known two-layer threshold network, IDK significantly outperformed standard RBF kernels and previous deep kernels (CS0/CS1), particularly as the margin between classes decreased.
Furthermore, the authors compared their exact recursive kernel against a numerical approximation using random weight sampling. As shown in the figure below, the closed-form IDK consistently achieved lower error than the sampling-based approach, even as the number of random features increased.
Benchmark Performance
The IDK was tested on the CIFAR-10 and STL-10 datasets. On STL-10, the IDK achieved 62.6% accuracy, outperforming RBF (61.7%), CS0 (62.3%), and Convolutional Kernel Networks (62.32%). On CIFAR-10, it reached 81.8%, remaining competitive with other kernel-based methods.
Key Insights
- Convexity and Complexity: The research demonstrates a trade-off between the "hardness" of non-convex optimization and sample complexity. Moving to a kernel space ensures convexity, but the number of samples required for generalization grows with the network's complexity.
- Stability: A theoretical insight suggests that the learnability of these kernels depends on the stability of the optimal neural network. If performance is robust to slight weight perturbations, the corresponding kernel is easier to learn.
- Finite Architectures: Unlike previous kernels modeling infinite-width networks, this approach targets finite architectures, providing a more direct kernelized version of standard deep networks.
Limitations and Future Work
While promising, the current IDK framework has several limitations. The closed-form solution is currently specific to threshold activations; extending this to ReLUs remains an open question. Additionally, adapting the framework to convolutional and max-pooling layers is necessary for broader application in computer vision. Finally, computing the recursive kernel for very deep or wide networks can be computationally intensive compared to standard backpropagation.
Summary updated