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.

  • Method

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

  • Results

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

  • Takeaways & Limitations

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

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.
  • In practice, increasing network depth or size often leads to lower generalization error.
  • Data structure influences generalization: the same network can fit structured and random data with respectively low and large generalization error.
  • Data-agnostic measures such as Rademacher complexity and VC-dimension are described as inadequate to explain modern DNN generalization.
  • The paper bounds generalization error through classification margin, independently of DNN depth and size while incorporating data structure through covering numbers.

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.
  • The paper lower-bounds classification margin using the network Jacobian and derives generalization-error bounds from that margin.
  • The generalization error can be bounded independently of network depth or width when the Jacobian spectral norm is bounded near training samples.
  • The analysis explains why weight normalization and batch normalization can lead to small generalization error and supports Jacobian regularization for such networks.
  • Experiments on MNIST, CIFAR-10, LaRED, and ImageNet validate the analysis and demonstrate Jacobian-regularizer effectiveness.
  • The bounds directly address 0-1 classification loss, include pooling, and are tighter than bounds based on weight-matrix norms.

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.

  • The central problem is predicting expected loss from the empirical loss of a DNN classifier learned from a training set.
  • Generalization error is defined as the difference between expected loss and empirical loss.
  • The analysis leverages an algorithmic-robustness framework in which nearby samples have close losses under a partition of sample space.
  • The robustness bound contains a training-set-dependent term and a second term that behaves as O(1/√m) and vanishes as training-set size increases.
  • The number of partitions is bounded using covering numbers, which quantify how many metric balls cover the sample space.
  • Covering numbers can reflect intrinsic structure for models including Gaussian mixtures, sparse signals, and low-dimensional manifolds.

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.
  • Large Margin Classifier: 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.
  • Large Margin Classifier: 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.
  • Large Margin Classifier: 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.
  • Large Margin Classifier: 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.

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.
  • Non-linear layers: 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.
  • Non-linear layers: 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.
  • Non-linear layers: 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).
  • Non-linear layers: 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.

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.
  • Jacobian Matrix of Pooling Layers: 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.
  • Jacobian Matrix of Pooling Layers: 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.
  • Jacobian Matrix of Pooling Layers: 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.
  • Jacobian Matrix of Pooling Layers: 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.

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.
  • Computing spectral-norm subgradients requires singular-value decomposition, making the direct regularizer inefficient.
  • 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.
  • 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.

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: The regularizer gradient requires gradients of output components and Jacobian matrices between successive layers.
  • Computation of Gradients and Efficient Implementation: The per-layer Jacobian regularizer is introduced as a simplified version to avoid excessive computational complexity.
  • Computation of Gradients and Efficient Implementation: Choosing one random output index per training sample reduces the computation to one additional gradient per sample.
  • Computation of Gradients and Efficient Implementation: Fixing the input of layer l removes computation of the preceding-layer Jacobian from the per-layer approximation.
  • Computation of Gradients and Efficient Implementation: The paper states that the proposed regularizer's effectiveness is evaluated experimentally.

V. DISCUSSION

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

  • The framework encompasses DNN architectures for which the network Jacobian can be computed, including ResNets, RNNs, LSTMs, and auto-encoders.
  • A ResNet Jacobian sums Jacobians from all possible subnetworks, including L-layer and one-layer paths.
  • The discussion extends the analysis to geodesic distance as a margin metric on a Riemannian manifold.
  • Geodesic covering numbers may yield tighter generalization-error bounds when manifold geodesic balls cover the input space more efficiently.
  • The output Euclidean-distance-to-input-geodesic-distance ratio is bounded by the maximum Jacobian spectral norm along the connecting curve.
  • For unbalanced data, the generalization bounds remain valid, but classification error can be dominated by the class with highest prior probability.

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.

  • Experiments use MNIST, CIFAR-10, LaRED, and ImageNet across fully connected, convolutional, and residual DNNs.
  • Jacobian regularization always outperforms weight decay in the reported fully connected-network comparisons.
  • With MNIST, 20000 samples and Jacobian regularization perform on par with 50000 samples and weight decay for a 4-layer DNN.
  • Weight-normalized networks achieve increasing testing accuracy with depth and weight-matrix size despite nearly perfect training accuracy.
  • The experiments indicate that Frobenius-norm-based margin bounds are too pessimistic because their predicted error growth conflicts with observed behavior.
  • The maximum training-set Jacobian spectral norm decreases with depth and width, whereas the testing-set maximum increases with depth and slightly with width.
  • The authors associate lower training-set Jacobian spectral norms with the good generalization of deeper and wider weight-normalized networks.

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.

  • For LaRED, the experiments evaluate gesture classification from depth images across 81 gestures and include testing on subjects excluded from training.
  • Jacobian regularization outperforms weight decay across the evaluated convolutional-DNN configurations.
  • The advantage of Jacobian regularization is most apparent at smaller training-set sizes, including on LaRED.
  • On MNIST with 1000 training samples, accuracy increases from 94% with weight decay to 96.3% with Jacobian regularization.
  • 97%+ accuracy on same-subject testing contrasts with 46% accuracy on different-subject testing using 50000 training samples.
  • Jacobian regularization also yields smaller generalization error and remains effective for batch-normalized DNNs and ResNets.

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.
  • CIFAR-10: 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Conclusion: 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.

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: The proof analyzes the line segment x + t(x′ − x) and uses the fundamental theorem of calculus to relate output differences to an integrated Jacobian.The segment parameter satisfies t ∈ [0, 1].
  • Spectral-norm tools: Submultiplicativity and the Frobenius-norm upper bound control the spectral norm of matrix products used throughout the proofs.The appendix uses ∥AB∥2 ≤ ∥A∥2∥B∥2 and ∥A∥2 ≤ ∥A∥F.
  • 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.
  • 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.
  • 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.
  • 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.
Loading 1605.08254v3…