PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Large Margin Deep Neural Networks

Jure Sokolic, Raja Giryes, Guillermo Sapiro, Miguel R. D. Rodrigues

arXiv:1605.08254v3stat.MLcs.LGcs.NE

TL;DR

The paper asks how deep neural networks can generalize despite existing bounds that depend adversely on depth or size. It derives classification-margin bounds using the network Jacobian, finding that bounded local Jacobian spectral norm can make generalization error independent of depth and size. The analysis also motivates Jacobian regularization alongside modern normalization strategies.

  • Problem

    Existing generalization bounds suggest that error depends on DNN depth or size, motivating bounds that better characterize observed generalization.

    Source: §I · p. 3, §VII · p. 29

  • Method

    The paper expresses generalization error through classification margin and bounds that margin using the network Jacobian.

    Source: §VII · p. 29

  • Results

    The bounds predict that DNN generalization error can be independent of network depth and size.

    Source: §VII · p. 29

  • Takeaways & Limitations

    The analysis suggests Jacobian-matrix regularization strategies that can be applied alongside weight or batch normalization.

    Source: §VII · p. 29

Abstract

from arXiv · show

The generalization error of deep neural networks via their classification margin is studied in this work. Our approach is based on the Jacobian matrix of a deep neural network and can be applied to networks with arbitrary non-linearities and pooling layers, and to networks with different architectures such as feed forward networks and residual networks. Our analysis leads to the conclusion that a bounded spectral norm of the network's Jacobian matrix in the neighbourhood of the training samples is crucial for a deep neural network of arbitrary depth and width to generalize well. This is a significant improvement over the current bounds in the literature, which imply that the generalization error grows with either the width or the depth of the network. Moreover, it shows that the recently proposed batch normalization and weight normalization re-parametrizations enjoy good generalization properties, and leads to a novel network regularizer based on the network's Jacobian matrix. The analysis is supported with experimental results on the MNIST, CIFAR-10, LaRED and ImageNet datasets.

I. INTRODUCTION

The introduction frames a tension between existing generalization bounds that worsen with network size and the low generalization error often observed in larger DNNs. The paper addresses this by relating generalization to classification margin while accounting for data structure.

  • Existing bounds suggest that generalization error requires training samples to grow with DNN depth or size.Source: §I · p. 3
  • In practice, increasing network depth or size often leads to lower generalization error.Source: §I · p. 3
  • Data structure influences generalization: the same network can fit structured and random data with respectively low and large generalization error.Source: §I · p. 3
  • Data-agnostic measures such as Rademacher complexity and VC-dimension are described as inadequate to explain modern DNN generalization.Source: §I · p. 3
  • The paper bounds generalization error through classification margin, independently of DNN depth and size while incorporating data structure through covering numbers.Source: §I · p. 3

A. Contributions

The paper develops Jacobian-based classification-margin bounds for broad classes of DNN classifiers. It concludes that local Jacobian control can yield size-independent generalization bounds and motivates a practical regularizer validated experimentally.

  • The analysis covers multi-class DNN classifiers with general nonlinearities, pooling layers, softmax outputs, and residual shortcut connections.Source: A. Contributions · pp. 4–5
  • The paper lower-bounds classification margin using the network Jacobian and derives generalization-error bounds from that margin.Source: A. Contributions · p. 4
  • The generalization error can be bounded independently of network depth or width when the Jacobian spectral norm is bounded near training samples.Source: A. Contributions · p. 4
  • The analysis explains why weight normalization and batch normalization can lead to small generalization error and supports Jacobian regularization for such networks.Source: A. Contributions · p. 4
  • Experiments on MNIST, CIFAR-10, LaRED, and ImageNet validate the analysis and demonstrate Jacobian-regularizer effectiveness.Source: A. Contributions · p. 4
  • The bounds directly address 0-1 classification loss, include pooling, and are tighter than bounds based on weight-matrix norms.Source: A. Contributions · p. 4

II. PROBLEM STATEMENT

The paper studies how well a DNN classifier’s empirical loss predicts expected loss. It uses classification robustness, covering numbers, and classification margin to derive generalization-error bounds.

1) Large Margin Classifier:

The paper defines classification margin as the largest input-space radius preserving a sample’s class label, then uses margin-based robustness to bound generalization error. For DNNs, the classifier is built from layered transformations ending in a linear or softmax output.

Large Margin Classifier

  • A classification margin is the largest metric-ball radius around a training sample that remains inside its correct decision region.The margin is defined using the supremum radius for which every nearby input receives the sample’s label.Source: 1) Large Margin Classifier · p. 8
  • Large-margin classifiers are robust because nearby samples within the margin share the same class prediction.The robustness result connects a margin γ to the covering number of the input space at scale γ/2.Source: 1) Large Margin Classifier · p. 8
  • The generalization bound depends on sample size, number of classes, input-space complexity, and classification margin.For large-margin classifiers, the error approaches zero at a 1/√m rate and grows sub-linearly with the number of classes.Source: 1) Large Margin Classifier · p. 8
  • For a CM regular k-dimensional manifold, the bound depends on k and the manifold constant CM when the margin is fixed at γ = 1.This removes explicit dependence on network depth from the corresponding bound.Source: 1) Large Margin Classifier · pp. 8–9
  • A DNN maps inputs through L parameterized layers to an output feature vector, followed by a linear or softmax classification layer.The softmax output is interpreted as class probabilities, while a linear output is typically paired with hinge loss.Source: C. Deep Neural Network Classifier · p. 9, POINT-WISE NON-LINEARITIES · p. 10

2) Non-linear layers:

The network’s nonlinear and pooling transformations determine how inputs are mapped into feature space and how decision boundaries change. The Jacobian formalism tracks this mapping through products of layer Jacobians and supports depth- and width-independent generalization bounds.

Non-linear layers

  • A nonlinear layer applies an element-wise nonlinearity to an affine transformation, including ReLU, sigmoid, and hyperbolic tangent choices.Convolutional layers fit this formulation when the weight matrix is block-cyclic.Source: 2) Non-linear layers · p. 10
  • Pooling layers reduce intermediate-representation dimension through down-sampling, max-pooling, or average pooling.The pooling operation is represented by a pooling matrix that depends on the preceding layer output.Source: 3) Pooling layers · p. 11
  • The network Jacobian is the product of the Jacobians of all layers evaluated at their corresponding intermediate inputs.This chain-rule structure applies the layerwise derivatives across the complete DNN transformation.Source: §III · pp. 11–12
  • Theorem 3 and Corollary 2 relate input-output differences to the average Jacobian and bound distance expansion through its spectral norm.The Jacobian acts as a linear operator mapping x′ − x to f(x′) − f(x).Source: §III · p. 12
  • The resulting margin and generalization-error bounds are independent of network depth or width when the relevant Jacobian or layer norms are controlled.The analysis therefore targets local geometric expansion rather than architecture size alone.Source: §III · pp. 11–12

3) Jacobian Matrix of Pooling Layers:

The paper bounds Jacobian spectral norms for network layers and uses these bounds to connect local sensitivity, classification margins, and generalization. It argues that Jacobian control avoids the depth and width dependence induced by Frobenius-norm bounds.

Jacobian Matrix of Pooling Layers

  • Layer Jacobian spectral norms can be bounded for linear, softmax, and nonlinear layers using their weight matrices and activation derivatives.The stated nonlinearities include ReLU, sigmoid, and hyperbolic tangent.Source: 3) Jacobian Matrix of Pooling Layers · p. 13
  • A small Jacobian norm yields small Fisher information for input perturbations and endows the network with robustness against those perturbations.The analysis interprets the perturbation magnitude as a parameter whose information is measured by the Fisher information.Source: 3) Jacobian Matrix of Pooling Layers · p. 14
  • Theorem 4 bounds classification margin using the training score and network properties, enabling generalization-error bounds for DNN classifiers.The resulting constraint sets jointly maximize training scores and constrain Jacobian or weight-matrix norms.Source: §IV · pp. 14–16
  • The spectral-norm bound is tighter than the Frobenius-norm bound for orthonormal-row weight matrices.The spectral constraint is independent of network width or depth, whereas the Frobenius constraint can be exponential in depth and polynomial in width.Source: §IV · pp. 16–17
  • The proposed bounds do not increase with the number of layers when the relevant spectral or Frobenius norms remain controlled.Under the manifold assumptions, the resulting error depends on data-manifold complexity rather than network depth.Source: §IV · p. 17

A. Jacobian Regularizer

The paper regularizes deep networks by penalizing the Jacobian norm at training samples, using a Frobenius-norm surrogate because spectral-norm optimization is inefficient.

  • The proposed regularizer bounds the network Jacobian norm evaluated at each training sample.Source: A. Jacobian Regularizer · p. 18
  • Computing spectral-norm subgradients requires singular-value decomposition, making the direct regularizer inefficient.Source: A. Jacobian Regularizer · p. 18
  • The derivation omits bias vectors, batch-normalization centering, and scaling under stated simplifications.The scaling can be incorporated into the following layer's weight matrix.Source: A. Jacobian Regularizer · p. 18
  • The Frobenius norm serves as a surrogate because it bounds the spectral norm up to the Jacobian rank.The paper states that this relationship justifies using the surrogate regularizer.Source: A. Jacobian Regularizer · p. 19

1) Computation of Gradients and Efficient Implementation:

The implementation computes Jacobian-related gradients and introduces a per-layer approximation that fixes intermediate inputs and samples one output index to reduce cost.

Computation of Gradients and Efficient Implementation

V. DISCUSSION

The Jacobian-based analysis extends beyond feed-forward networks and Euclidean margins, covering architectures with computable Jacobians and geodesic distances on manifolds.

VI. EXPERIMENTS

Experiments across several datasets and architectures compare Jacobian regularization with weight decay and examine how depth and width affect Jacobian-based behavior and generalization.

B. Convolutional DNN

The experiments compare Jacobian regularization with weight decay across convolutional DNNs on MNIST, CIFAR-10, and LaRED, including tests across subjects. Jacobian regularization generally performs better, especially with smaller training sets, while cross-subject generalization remains limited.

1) CIFAR-10:

On CIFAR-10 and ImageNet, Jacobian regularization generally improves generalization and testing accuracy, with particularly strong effects on smaller training sets and without data augmentation. The paper also develops a lower-cost per-layer regularizer for large-scale training.

CIFAR-10

  • The Wide ResNet experiments use a 22-layer network of width 5, with small and full training sets evaluated under different augmentation settings.The small training sets contain 2500 and 10000 samples; the full set uses data augmentation.Source: 1) CIFAR-10 · p. 26, CLASSIFICATION ACC. [%] OF RESNET… · p. 27
  • Jacobian-regularized ResNets outperform standard ResNets in all reported CIFAR-10 cases, with the strongest effect on smaller training sets.The experiments compare regularized and standard ResNets across training-set sizes and augmentation conditions.Source: CLASSIFICATION ACC. [%] OF RESNET… · p. 27

ImageNet

  • 23.83% GE is obtained with Jacobian regularization versus 61.53% for the baseline ResNet without data augmentation.The result is presented as evidence that Jacobian regularization can substantially reduce generalization error.Source: 2) ImageNet · p. 27

CIFAR-10

  • 47.51% testing accuracy is achieved by the Jacobian-regularized ResNet versus 46.75% for the baseline ResNet with data augmentation.Data augmentation narrows the generalization-error difference between the baseline and regularized models.Source: 2) ImageNet · p. 27

Computational cost

  • The per-layer Jacobian regularizer remains effective while increasing ImageNet computation time by only 58%.The paper presents this lower-cost form as more appropriate for large-scale experiments where computational time matters.Source: AVERAGE COMPUTATION TIME [s/BATCH] · p. 29

Conclusion

  • The theory expresses generalization error through classification margin, whose lower bound depends on output separation and the network Jacobian matrix.The resulting bounds can be independent of network depth and size, unlike bounds that grow exponentially with width or size.Source: §VII · p. 29
  • The proposed Jacobian regularization can complement weight and batch normalization and is especially effective with limited training data at moderate computational cost.These conclusions connect the theoretical bounds to the reported experimental behavior.Source: §VII · p. 29

APPENDIX

The appendix proves bounds connecting network behavior along input line segments to Jacobian norms, then applies spectral-norm inequalities to layers, pooling, classification margins, and normalized networks.

Jacobian bounds

Spectral-norm tools

Layer Jacobians

  • For nonlinear layers, the Jacobian is a diagonal derivative matrix multiplied by the weight matrix, so its spectral norm is bounded by ∥W_l∥2.The derivative diagonals of the considered nonlinearities are bounded by 1.Source: C. Proof of Lemma 1 · p. 30

Pooling

  • Non-overlapping pooling regions produce orthonormal pooling-operator rows, giving the pooling Jacobian spectral norm equal to 1.This establishes a norm bound for the pooling layers considered in the analysis.Source: C. Proof of Lemma 1 · p. 30

Classification margin

  • The classification-margin proof selects a boundary point at distance γ_d(s_i), then bounds the intervening Jacobian by its supremum near the training sample.This yields a margin bound based on local Jacobian behavior.Source: D. Proof of Theorem 4 · p. 31

Normalization

  • Batch normalization can make the layer weight matrices row normalized, except for the final weight matrix.The proof uses commutation of ReLU and diagonal non-negative matrices to establish the normalization relation.Source: E. Proof of Theorem 5 · p. 32

Related papers

Loading 1605.08254v3…