Spectral Analysis of Kernel and Neural Embeddings: Optimization and Generalization

Emilio Jorge, Morteza Haghir Chehreghani, Devdatt P. DubhashiarXiv 2019 · arXiv

Overview

This research extends theoretical breakthroughs in shallow neural networks to deeper architectures, demonstrating that kernel and neural embeddings significantly boost both training speed and generalization. By ensuring that data representations align with the top eigenvectors of the model's Gram matrix, the authors provide a practical bridge between kernel theory and deep learning performance.

The Problem: Bridging Theory and Practice

Despite the massive success of deep learning, our theoretical understanding of why these models generalize so well remains incomplete. A landmark 2019 study by Arora et al. provided a "fine-grained" analysis for simple two-layer networks, showing that optimization and generalization are governed by the Gram matrix (a matrix representing the inner products of all data points in a specific feature space). Specifically, if the target labels align well with the top eigenvectors of this matrix, the network learns faster and generalizes better.

However, this theory was largely confined to shallow, two-layer models. This paper addresses a critical gap: How can we extend these spectral insights to deeper networks? The authors hypothesize that the earlier layers of a deep network act as an embedding function that "prepares" the data for the final layers by improving this crucial spectral alignment.

Methodology and Datasets

The authors treat the layers preceding the final hidden layer as a fixed embedding function, $\phi(x)$. They investigate four main types of representations across standard computer vision benchmarks (MNIST, CIFAR-10, LSUN, and Fashion-MNIST):

  1. Gaussian Kernels: A standard "label-unaware" kernel, approximated using Random Fourier Features (RFF).
  2. Neural Embeddings: Representations produced by hidden layers, testing both task-specific pre-training and transfer learning.
  3. Arc-cosine Kernels: Specialized kernels designed to mimic infinite-width neural network layers.
  4. Multiple Kernel Learning (alignf): An optimization-based approach that maximizes alignment between data and target labels.

The Role of Spectral Alignment

The core insight of the paper is that a "good" representation isn't just one that is complex or expressive; it is one that aligns the signal (labels) with the most dominant components (top eigenvectors) of the data's internal geometry. The results suggest that the power of deep learning lies in its ability to perform "feature engineering" that transforms raw data into a space where the Gram matrix is perfectly tuned for the task.

Cumulative alignment of labels with Gram matrix eigenvectors across different kernel dimensions.

As shown in the spectral analysis, increasing the dimensionality of the kernel space (or moving toward an infinite-dimensional kernel) significantly improves the cumulative alignment of the labels with the top eigenvectors. This alignment is the "secret sauce" that facilitates easier optimization for the final layers of the network.

Empirical Results: Optimization and Generalization

The study found that using kernel or neural embeddings led to a much sharper drop in training loss compared to the "no-kernel" baseline. For example, on CIFAR-10, kernelized models reached low loss levels thousands of epochs earlier than standard models.

Test accuracy over training iterations, demonstrating improved generalization with kernel embeddings.

Beyond speed, generalization improved markedly. The authors calculated a data-dependent complexity measure used to upper-bound generalization error. On CIFAR-10, the alignf kernel reduced this theoretical bound from 3.86 (no kernel) to 1.45. Across all experiments, the performance hierarchy remained stable: alignf (Best) > Arc-cosine > Gaussian > No Kernel (Worst).

Conclusion and Future Directions

The research proves that label-aware representations are fundamentally easier for neural networks to optimize. While the current spectral theory is most mature for binary classification, it provides a rigorous foundation for understanding deep learning. Future work will focus on extending this analysis to multi-class problems and exploring the "co-evolution" of embeddings and final layers during the dynamic training process.

Summary updated

Abstract

Recent results on optimization and generalization properties of neural networks showed that in a simple two-layer network, the alignment of the labels to the eigenvectors of the corresponding Gram matrix determines the convergence of the optimization during training. Such analyses also provide upper bounds on the generalization error. We experimentally investigate the implications of these results to deeper networks via embeddings. We regard the layers preceding the final hidden layer as producing different representations of the input data which are then fed to the two-layer model. We show that these representations improve both optimization and generalization. In particular, we investigate three kernel representations when fed to the final hidden layer: the Gaussian kernel and its approximation by random Fourier features, kernels designed to imitate representations produced by neural networks and finally an optimal kernel designed to align the data with target labels. The approximated representations induced by these kernels are fed to the neural network and the optimization and generalization properties of the final model are evaluated and compared.
BibTeX
@misc{jorge2019spectral,
  author = {Emilio Jorge and Morteza Haghir Chehreghani and Devdatt P. Dubhashi},
  title = {{Spectral Analysis of Kernel and Neural Embeddings: Optimization and Generalization}},
  year = {2019},
  eprint = {1905.05095},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.05095},
}
Figure