Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin

By Colin Wei, Tengyu Ma. 2019

95 citations recorded by the source corpus.

For linear classifiers, the relationship between (normalized) output margin and generalization is captured in a clear and simple bound -- a large output margin implies good generalization. Unfortunately, for deep models, this relationship is less clear: existing analyses of the output margin give complicated bounds which sometimes depend exponentially on depth. In this work, we propose to instead analyze a new notion of margin, which we call the "all-layer margin." Our analysis reveals that the all-layer margin has a clear and direct relationship with generalization for deep models. This enables the following concrete applications of the all-layer margin: 1) by analyzing the all-layer margin, we obtain tighter generalization bounds for neural nets which depend on Jacobian and hidden layer norms and remove the exponential dependency on depth 2) our neural net results easily translate to the adversarially robust setting, giving the first direct analysis of robust test error for deep networks, and 3) we present a theoretically inspired training algorithm for increasing the all-layer margin and demonstrate that our algorithm improves test performance over strong baselines in practice.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Scaling & 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 Computer Vision and Pattern Recognition

In Scaling & Learning Theory

Citations in the corpus

Sharpness-Aware Minimization for Efficiently Improving Generalization (2020, background): “The notion of all-layer margin introduced by Wei & Ma (2020) is closely related to this work; one is adversarial perturbation over the activations of a network and the other over its weights, and there is some coupling between these two quantities.”
MOPO: Model-based Offline Policy Optimization (2020, methodology): “First, as shown in the standard settings [44, 68, 69], Lipschitz regularization may improve the in-distribution and out-of-distribution generalization performance of the learned dynamics.”
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).”
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.”
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).”
The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization (2020, background): “There is a large body of work dedicated to adversarially robust models [Zhang and Zhu, 2019, Santurkar et al., 2019, Zhang et al., 2019, Bhagoji et al., 2019, Diochnos et al., 2019, Wei and Ma, 2019].”