Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation

By Colin Wei, Tengyu Ma. 2019

128 citations recorded by the source corpus.

Existing Rademacher complexity bounds for neural networks rely only on norm control of the weight matrices and depend exponentially on depth via a product of the matrix norms. Lower bounds show that this exponential dependence on depth is unavoidable when no additional properties of the training data are considered. We suspect that this conundrum comes from the fact that these bounds depend on the training data only through the margin. In practice, many data-dependent techniques such as Batchnorm improve the generalization performance. For feedforward neural nets as well as RNNs, we obtain tighter Rademacher complexity bounds by considering additional data-dependent properties of the network: the norms of the hidden layers of the network, and the norms of the Jacobians of each layer with respect to all previous layers. Our bounds scale polynomially in depth when these empirical quantities are small, as is usually the case in practice. To obtain these bounds, we develop general tools for augmenting a sequence of functions to make their composition Lipschitz and then covering the augmented functions. Inspired by our theory, we directly regularize the network's Jacobians during training and empirically demonstrate that this improves test performance.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Fantastic Generalization Measures and Where to Find Them (2019, background): “…have attempted to understand the generalization phenomenon in deep models from a theoretical perspective e.g. (Neyshabur et al., 2015b; Bartlett et al., 2017; Neyshabur et al., 2018a; Golowich et al., 2017; Arora et al., 2018; Nagarajan and Kolter, 2019a; Wei and Ma, 2019a; Long and Sedghi, 2019).”
On Measuring Excess Capacity in Neural Networks (2022, methodology): “Notably, replacing the function class F γ with a class of networks composed with a Lipschitz augmented loss function [43] facilitates deriving Rademacher complexity-and generalization bounds, which do not suffer from the exponential depth dependency via the product of Lipschitz constants.”
Decomposable-Net: Scalable Low-Rank Compression for Neural Networks (2019, methodology): “gued that the empirical value is much smaller than the theoretical one (Arora et al. 2018; Wei and Ma 2019).”
Generalization bounds for deep convolutional neural networks (2019, background): “…generalization of deep learning models (see Neyshabur et al., 2015; Zhang et al., 2016; Dziugaite and Roy, 2017; Bartlett et al., 2017; Neyshabur et al., 2017; 2018; Arora et al., 2018; Golowich et al., 2018; Neyshabur et al., 2019; Wei and Ma, 2019a; Cao and Gu, 2019; Daniely and Granot, 2019).”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, methodology): “Our bound considers the Jacobian norms, hidden layer norms, and output margin on the training data, and avoids the exponential depth dependency when these quantities are well-behaved, as is the case in practice [Arora et al., 2018, Nagarajan and Kolter, 2019, Wei and Ma, 2019].”
The Implicit and Explicit Regularization Effects of Dropout (2020, methodology): “Recent works (Arora et al., 2018; Nagarajan & Kolter, 2019; Wei & Ma, 2019a,b) support our stability-based regularization by bounding generalization of the model in terms of its Jacobian norms on the training data.”
The intriguing role of module criticality in the generalization of deep networks (2019, methodology): “These results are either based on covering number and Rademacher complexity (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2019; Long and Sedghi, 2019; Wei and Ma, 2019) or they use approaches similar to PAC-Bayes (McAllester, 1999; Dziugaite and Roy, 2017; Neyshabur et al.”
Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss (2019, background): “There is a large body of recent work on measuring the complexity of neural networks (see [4, 13, 57] and references therein), and our discussion below is orthogonal to the precise choices.”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “Wei and Ma [70] prove generalization bounds depending on additional data-dependent properties.”