Optimization and Adaptive Generalization of Three layer Neural Networks

Khashayar Gatmiry, Stefanie Jegelka, Jonathan KelnerICLR 2022 · OpenReview

Introduction

For the past few years, the theoretical understanding of neural networks has been heavily dominated by the Neural Tangent Kernel (NTK) framework. NTK theory suggests that sufficiently wide neural networks behave like linear models using a fixed kernel. While mathematically convenient, this "lazy regime" implies that networks do not actually learn new features, but merely combine existing ones at initialization.

However, the empirical success of deep learning relies fundamentally on feature extraction—the ability of a network to adapt its internal representations to the underlying data distribution. Furthermore, NTK-based models can be sensitive to noise and often fail to explain why deep networks outperform traditional kernel methods in practice.

This paper addresses a major theoretical gap: proving mathematically that a neural network can learn features (i.e., adaptively choose a kernel) while remaining efficiently optimizable. By focusing on three-layer ReLU networks, the authors identify a mathematically tractable regime that is strictly nonlinear, moving beyond the limitations of the NTK.

Methodology: Escaping the "Lazy" Regime

The authors analyze a three-layer ReLU network where the first and second layers are trained, while certain components (such as a random sign matrix between layers) remain fixed to facilitate theoretical analysis.

To solve the dual challenges of non-convex optimization and generalization, they introduce two key technical innovations:

  1. Projected Stochastic Gradient Descent (PSGD): Standard SGD is notoriously difficult to analyze in non-convex landscapes. The authors employ a specific variant that incorporates:
  2. Randomized Smoothing: Adding Gaussian noise to the weights during training to "round off" the sharp, non-differentiable edges of the ReLU activation functions.
  3. Orthogonality Constraint: Weight updates in the second layer are forced to be orthogonal to the features produced by the first layer at initialization. This explicitly prevents the linear behavior of the NTK regime from dominating the learning process, forcing the network to explore new representations.
  4. Adaptive Complexity Measure: They define a novel function norm ($\left\|\cdot\right\|_\zeta$) that measures complexity not against a single fixed kernel, but as the minimum complexity across an entire family of kernels. This mathematical formulation allows the model to "pick" the most efficient feature representation for the specific task.

Key Theoretical Results

This is a purely theoretical paper; rather than evaluating performance on standard empirical benchmarks like ImageNet, the authors provide rigorous mathematical proofs demonstrating the superiority of their framework.

  • Adaptive Generalization Bounds: The authors prove a generalization bound that scales with the "best" kernel in a predefined family. If a simpler, more efficient feature representation exists for a given dataset, the network is guaranteed to find a solution that generalizes according to that simpler representation.
  • Surpassing NTK: The proposed adaptive complexity measure acts as an upper bound on the NTK norm. In the worst-case scenario, the network performs as well as an NTK model. However, in many cases—such as synthetic setups involving functions represented as polynomial series—the adaptive bounds are strictly tighter and perform significantly better.
  • Polynomial Efficiency: Despite the empirical loss function being non-convex, the authors prove that PSGD converges to a good solution (low population risk) in polynomial time, relative to the inverse of the precision and the number of data points.
  • Noise Robustness: Unlike standard Kernel Ridgeless Regression (KRLR), which can struggle significantly with noisy labels, the generalization bounds developed in this nonlinear regime remain robust and meaningful even when the data distribution is noisy.

Limitations and Future Work

While this work represents a significant step forward in deep learning theory, it comes with specific constraints:

  • Layer Depth: The analysis is strictly limited to three-layer networks. While this is a notable advancement over common two-layer analyses, real-world deep networks have dozens or hundreds of layers. Extending this "adaptive kernel" view to deeper architectures remains an open challenge.
  • Architecture Constraints: The proofs rely on specific architectural choices, such as fixed random sign matrices and specific initialization scales, which do not perfectly mirror production architectures like Transformers or ResNets.
  • Algorithmic Gap: PSGD is primarily a theoretical tool designed to make the mathematical analysis tractable. Whether standard, unconstrained SGD achieves this same "adaptive kernel" selection in practice remains a subject for future investigation.

Ultimately, the authors suggest that the techniques developed here could pave the way for a formal proof of "depth separation"—the mathematical confirmation that deeper networks are fundamentally superior at learning complex feature hierarchies than shallower ones.

Summary updated

Abstract

While there has been substantial recent work studying generalization of neural networks, the ability of deep nets in automating the process of feature extraction still evades a thorough mathematical understanding. As a step toward this goal, we analyze learning and generalization of a three-layer neural network with ReLU activations in a regime that goes beyond the linear approximation of the network, and is hence not captured by the common Neural Tangent Kernel. We show that despite nonconvexity of the empirical loss, a variant of SGD converges in polynomially many iterations to a good solution that generalizes. In particular, our generalization bounds are adaptive: they automatically optimize over a family of kernels that includes the Neural Tangent Kernel, to provide the tightest bound.
BibTeX
@inproceedings{gatmiry2022optimization,
  author = {Khashayar Gatmiry and Stefanie Jegelka and Jonathan Kelner},
  title = {{Optimization and Adaptive Generalization of Three layer Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=dPyRNUlttBv},
}
Figure