Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian

By Samet Oymak, Zalan Fabian, Mingchen Li, M. Soltanolkotabi. 2019

108 citations recorded by the source corpus.

Modern neural network architectures often generalize well despite containing many more parameters than the size of the training dataset. This paper explores the generalization capabilities of neural networks trained via gradient descent. We develop a data-dependent optimization and generalization theory which leverages the low-rank structure of the Jacobian matrix associated with the network. Our results help demystify why training and generalization is easier on clean and structured datasets and harder on noisy and unstructured datasets as well as how the network size affects the evolution of the train and test errors during training. Specifically, we use a control knob to split the Jacobian spectum into "information" and "nuisance" spaces associated with the large and small singular values. We show that over the information space learning is fast and one can quickly train a model with zero training loss that can also generalize well. Over the nuisance space training is slower and early stopping can help with generalization at the expense of some bias. We also show that the overall generalization capability of the network is controlled by how well the label vector is aligned with the information space. A key feature of our results is that even constant width neural nets can provably generalize for sufficiently nice datasets. We conduct various numerical experiments on deep networks that corroborate our theoretical findings and demonstrate that: (i) the Jacobian of typical neural networks exhibit low-rank structure with a few large singular values and many small ones leading to a low-dimensional information space, (ii) over the information space learning is fast and most of the label vector falls on this space, and (iii) label noise falls on the nuisance space and impedes optimization/generalization.

Subfields: Artificial Intelligence, Computational Mechanics, Statistical and Nonlinear Physics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistical and Nonlinear Physics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “Moreover, it is known that for many deep learning tasks, especially those with a heavily over-parametrized neural network, the learned neural network will enjoy low-rank properties after training [29].”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “, 2018; Nagarajan and Kolter, 2019), which may decrease as the model capacity increases (Arora et al., 2019b; Li and Liang, 2018; Allen-Zhu et al., 2018a; Oymak et al., 2019).”
Diametrical Risk Minimization: theory and computations (2019, background): “Thus, it has been a goal of many researchers to either locate the flat minimizers of such problems or to construct objective functions and/or NN architectures which do not have a large number of sharp minimizers [13, 31, 8, 10] Figure 1b illustrates a different kind of sharpness, which can be induce”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, methodology): “The following theorem is borrowed from Oymak and Soltanolkotabi (2019) and characterizes three key properties of the neural network Jacobian.”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “[15, 78] suggests that a form of implicit regularization is induced by an alignment between NTK’s principal components and only a few task-relevant (2)Recall that it took 3 years for the psychologist, Oskar Pfungst, to realize that Clever Hans was not capable of doing any arithmetic.”
Geometric compression of invariant manifolds in neural nets (2020, background): “On the empirical side, the alignment occurring during learning between the function being learnt and the top eigenvectors of the Gram matrix was noticed in [33] and observed more systematically in [34].”