Improper Deep Kernels

Uri Heinemann, Roi Livni, Elad Eban, Gal Elidan, Amir GlobersonAISTATS 2016 · OpenReview

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.

Error reduction over RBF and comparison with random features.

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.

Accuracy results on CIFAR-10 and STL-10 benchmarks.

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

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 proble...
BibTeX
@inproceedings{heinemann2016improper,
  author = {Uri Heinemann and Roi Livni and Elad Eban and Gal Elidan and Amir Globerson},
  title = {{Improper Deep Kernels}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=vP3mNQ3rXKt},
}
Figure