Robust Generalization of Quadratic Neural Networks via Function Identification

Kan Xu, Hamsa Bastani, Osbert Bastani

Abstract

Standard machine learning theory relies heavily on the assumption that training and test data are independent and identically distributed (i.i.d.). When this assumption is violated—a phenomenon known as distribution shift—neural networks often fail to generalize. While parameter identifiability is traditionally seen as the key to robustness, the inherent symmetries of neural networks (e.g., weight permutations and rotations) make parameter recovery impossible in over-parameterized regimes. This paper proposes a shift in perspective: focusing on function identification rather than parameter identification. By analyzing Quadratic Neural Networks (QNNs) and specific ReLU architectures, the authors prove that the underlying function can be recovered exactly, enabling robust generalization across arbitrary distribution shifts.

Introduction

The "i.i.d. assumption" is the bedrock of most statistical learning guarantees. However, real-world applications frequently encounter distribution shifts where the test environment differs significantly from the training environment. In such cases, a model that has merely "memorized" patterns specific to the training distribution will fail.

The gold standard for addressing this is identifiability: if a model can recover the unique "true" parameters that generated the data, it should, in theory, generalize to any distribution. Unfortunately, neural networks are notoriously non-identifiable. Because multiple sets of weights can represent the exact same mathematical function, the search for "true" parameters is often a fool's errand. This research asks whether we can achieve the same robust generalization by identifying the function itself, bypassing the need to pin down specific parameters.

Methodology: From Parameters to Functions

The researchers focus their analysis on Quadratic Neural Networks (QNNs), which take the form: $$f_\theta(x) = \sum_{j=1}^m \langle \theta_j, x \rangle^2$$

1. The Matrix Factorization Perspective

A key insight of the paper is that a QNN can be reformulated as a matrix operation. Specifically, $f_\theta(x) = x^\top (\theta \theta^\top) x$. While the individual weight matrix $\theta$ is not identifiable due to orthogonal transformations (you can rotate the weights without changing the output), the product $\phi = \theta \theta^\top$ is a stable, identifiable object.

2. Function Identification and Convexity

The authors prove that under mild conditions—such as the training data having a non-singular covariance—the loss function is strongly convex with respect to the matrix $\phi$. This allows them to demonstrate that as the number of training samples $n$ increases, the learned function converges to the true function for all possible inputs in the domain, regardless of whether those inputs were represented in the training distribution.

3. Extensions to ReLU and Algorithmic Analysis

The study extends these principles to a subclass of ReLU networks where hidden layer components are unit vectors with sufficient "separation." Furthermore, the authors use algorithmic analysis to show that standard gradient descent effectively finds these global minima in practice. They apply this theory to two complex scenarios: Contextual Bandits, where the distribution changes dynamically as an agent learns, and Transfer Learning.

Key Insights

  • Symmetry as a Bypass: Rather than viewing over-parameterization and symmetry as obstacles, this paper shows they can be bypassed by focusing on the functional manifold. Even if the parameters $\theta$ are "sliding" along a symmetry group, the output $f(x)$ remains stable and identifiable.
  • Handling Large Distribution Shifts: Most existing generalization bounds (like PAC-Bayes) require the test distribution to have significant overlap with the training distribution. Function identification allows for "large" shifts where the test data might occupy a completely different part of the input space, provided the model architecture is correctly specified.
  • The Necessity of Correct Specification: A critical takeaway is that these robustness guarantees depend on the model family being capable of representing the true data-generating process. If the model is misspecified, the guarantees for function identification vanish.

Results and Performance

As a theoretical work, the paper establishes several key mathematical benchmarks:

  • Convergence Rates: The authors provide a high-probability bound showing the difference between the learned QNN and the true function vanishes at a rate of approximately $n^{-1/4}$.
  • Bandit Regret: In QNN-based contextual bandits, the authors prove an expected regret of $\tilde{O}(T^{2/3})$. While this is slower than the $\tilde{O}(\sqrt{T})$ rate typical of linear models, it represents a significant guarantee for a non-identifiable, over-parameterized setting.
  • Transfer Learning Utility: The theory demonstrates that knowledge can be successfully transferred from a large "proxy" dataset to a small "gold" dataset even when labels shift slightly and covariates shift significantly, provided the underlying functional form is identified.

Limitations and Future Directions

While the paper provides a rigorous foundation for function identification, several challenges remain. First, the theory assumes correct specification—that the "true" world behaves quadratically or follows the specific ReLU constraints. In practice, the true functional form of data is rarely known. Second, the proofs are currently limited to shallow networks (one hidden layer). Extending these results to deep, multi-layer architectures is difficult because the symmetries involved become exponentially more complex. Finally, the $n^{-1/4}$ convergence rate is relatively slow, suggesting that more refined analysis might be needed to improve the efficiency of these guarantees in practical applications.

Summary updated

BibTeX
@inproceedings{xu2022robust,
  author = {Kan Xu and Hamsa Bastani and Osbert Bastani},
  title = {{Robust Generalization of Quadratic Neural Networks via Function Identification}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=Xx4MNjSmQQ9},
}
Figure