Orthogonal Deep Neural Networks

Kui Jia; Shuai Li; Yuxin Wen; Tongliang Liu; Dacheng Tao

Source-linked AI summary

Orthogonal Deep Neural Networks

Kui Jia, Shuai Li, Yuxin Wen, Tongliang Liu, Dacheng Tao

arXiv:1905.05929v2May 15, 2019cs.LGcs.CVstat.ML

TL;DR

Over-parameterized DNNs can generalize well despite traditional bounds not readily explaining practical performance, motivating solution properties tied to network weights. The paper derives a local-isometry-based, singular-value-sensitive generalization bound, then proposes strict and approximate OrthDNNs, including SVB and BBN. Experiments on benchmark image classification report efficacy and robustness, while the authors identify computational and optimization drawbacks of strict Stiefel-manifold constraints.

Problem
Over-parameterized DNNs can fit randomly labeled data yet perform well on practical tasks, so data-independent generalization analysis does not readily explain their behavior.
Method
The paper proves local isometry for DNNs, derives a generalization bound sensitive to each weight matrix’s singular-value spectrum, and uses it to design OrthDNNs, SVB, and BBN.
Results
Experiments on benchmark image classification show OrthDNN efficacy and robustness, with approximate OrthDNNs performing as well as strict ones at lower computational cost.
Takeaways & Limitations
Equal singular values provide the theoretically preferred isometry condition, while SVB offers a simpler route to approximate orthogonality for practical training.
Takeaways & Limitations
Strict Stiefel-manifold optimization has computational, empirical-performance, and compatibility shortcomings, and may miss better nearby Euclidean optima with lower training error.

Abstract

from arXiv · show

In this paper, we introduce the algorithms of Orthogonal Deep Neural Networks (OrthDNNs) to connect with recent interest of spectrally regularized deep learning methods. OrthDNNs are theoretically motivated by generalization analysis of modern DNNs, with the aim to find solution properties of network weights that guarantee better generalization. To this end, we first prove that DNNs are of local isometry on data distributions of practical interest; by using a new covering of the sample space and introducing the local isometry property of DNNs into generalization analysis, we establish a new generalization error bound that is both scale- and range-sensitive to singular value spectrum of each of networks' weight matrices. We prove that the optimal bound w.r.t. the degree of isometry is attained when each weight matrix has a spectrum of equal singular values, among which orthogonal weight matrix or a non-square one with orthonormal rows or columns is the most straightforward choice, suggesting the algorithms of OrthDNNs. We present both algorithms of strict and approximate OrthDNNs, and for the later ones we propose a simple yet effective algorithm called Singular Value Bounding (SVB), which performs as well as strict OrthDNNs, but at a much lower computational cost. We also propose Bounded Batch Normalization (BBN) to make compatible use of batch normalization with OrthDNNs. We conduct extensive comparative studies by using modern architectures on benchmark image classification. Experiments show the efficacy of OrthDNNs.

1 INTRODUCTION

The paper connects spectral regularization with generalization analysis by deriving a singular-value-sensitive bound and using it to motivate OrthDNNs. Experiments on benchmark image classification report improved generalization and robustness, while SVB achieves approximate orthogonality more efficiently than strict OrthDNNs.

Theory: The paper introduces local isometry into algorithmic-robustness analysis and derives a generalization bound sensitive to the scale and range of each layer’s singular values.A new sample-space covering captures effects from both distance expansion and contraction.
OrthDNNs: Equal singular values minimize the bound with respect to isometry, motivating orthogonal or row- and column-orthonormal weight matrices in OrthDNNs.These structures provide the most direct realization of the theoretically preferred spectrum.
Algorithms: SVB periodically constrains every weight matrix’s singular values to a narrow band around 1, providing approximate OrthDNNs without the heavy computation of strict Stiefel-manifold optimization.The paper also proposes BBN to address batch normalization’s potential ill-conditioned layer transforms.
Experiments: Experiments on modern architectures and benchmark image classification show consistent generalization gains, comparable performance for approximate and strict OrthDNNs, and improved robustness to image corruptions.The reported robustness persists as corruption severity increases, with stronger effects especially for smaller training sets.
Motivation: Over-parameterized DNNs can generalize well despite fitting randomly labeled data, motivating analyses beyond traditional data-independent bounds.The paper relates practical generalization to properties of learned solutions and natural-signal data.

2 PROBLEM STATEMENT

The paper formulates classification-representation learning as minimizing empirical risk while controlling generalization error. It then uses algorithmic robustness, covering numbers, and local isometry to relate network mappings and weight spectra to generalization bounds.

Classification learning: The learning objective is to identify a classifier minimizing expected risk, using empirical risk as its observable proxy because the data distribution is unknown.The discrepancy between expected and empirical risk is the generalization error.
Classification-representation learning: In classification-representation learning, a neural network map T extracts task-relevant features while the classifier minimizes loss on the transformed examples.The analysis isolates T because its mapping properties are central to the paper’s theory.
Algorithmic robustness: Algorithmic robustness partitions the sample space so that losses for training and test examples within the same set remain close.Covering numbers provide a way to control loss variation and represent the number of such partitions.
Local isometry: A δ-isometry controls how much a mapping can expand or contract distances, enabling robustness-based generalization bounds using covering numbers.The cited theorem gives robustness parameters involving the covering number and A(γ + δ).
Network model: The theoretical model uses multilayer perceptrons with linear weight maps followed by ReLU, while noting that the analysis extends almost equally to convolutional networks.Feature spaces use the ℓ2 metric, and the singular-value spectrum characterizes each weight matrix.

NETWORKS

The paper develops generalization bounds for DNNs by modeling local isometry on practical data distributions and relating expansion, contraction, and covering geometry to weight-matrix singular values. The resulting analysis motivates OrthDNNs, whose equal-singular-value weights attain the optimal bound with respect to the isometry degree.

Generalization analysis: Constraining the singular-value spectra of layer weight matrices controls both the network’s local δ-isometry and the covering-ball diameter γ.The bound depends on δ-isometry and γ, with γ controlled through maximum singular values of selected layers.
Generalization bound: Including differently labeled instances in the same covering balls captures errors from both inter-class contraction and intra-class expansion.This covering scheme can reduce the covering-set size and may produce a tighter bound in cases where nearby differently labeled examples are rarely misclassified.
Local isometry: DNNs are locally linear within regions induced by nonlinear layers, yielding local δ-isometry on bounded variation subspaces outside the relevant null spaces.For nonlinear networks, the input space is recursively partitioned into regions where the network acts linearly on local variations.
Generalization bound: The pairwise error function measures the largest loss difference among nearby examples whose transformed distances fall within the δ-isometry range, and it increases monotonically with δ.Its candidate examples satisfy γ − δ ≤ ||T x′ − T x|| ≤ γ + δ and ||x − x′|| ≤ γ.
OrthDNNs: The optimal generalization bound with respect to δ occurs only when every layer’s weight matrix has equal singular values.Setting all singular values to 1 gives orthogonal matrices or non-square matrices with orthonormal rows or columns, motivating OrthDNNs.

4 ALGORITHMS OF ORTHOGONAL DEEP NEURAL NETWORKS

OrthDNNs enforce or approximate near-isometry in layer weight matrices through strict manifold optimization, Singular Value Bounding, and batch-normalization variants. The section also explains computational trade-offs, BN compatibility, and the matrix treatment of convolutional kernels.

Strict OrthDNNs: Strict OrthDNNs enforce orthogonality by optimizing weight matrices on their Stiefel manifolds.For sufficiently tall matrices, the manifold is defined by W_l^T W_l = I; tangent-space projection and retraction maintain the constraint.
Approximate OrthDNNs: Strict Stiefel-manifold optimization is computationally expensive because gradient projection and manifold retraction dominate each training iteration.Allowing weights to move slightly away from the manifolds permits these operations to occur less frequently, amortizing their cost.
Approximate OrthDNNs: Singular Value Bounding creates approximate OrthDNNs by placing every weight matrix’s singular values in [1/(1 + ϵ), (1 + ϵ)] after every T_svb SGD iterations.SVB is described as a projected-SGD method using hard regularization.
Empirical evaluation: Image-classification experiments show that SVB sometimes outperforms strict OrthDNNs, while both outperform commonly used SGD-based methods, often by a large margin.The experiments also report that approximate OrthDNNs perform as well as strict ones at much lower computational cost.
Batch-normalization compatibility: Batch normalization can alter layer-transform singular values, making direct BN ineffective for enforcing strict orthogonality.DBN preserves the conditioning of strict orthogonal weights, while BBN bounds batch-normalization scale variations for approximate OrthDNNs; experiments report improved performance with BBN instead of BN.
Orthogonal convolutional networks: For convolutional layers, OrthDNN algorithms are applied after converting each weight tensor into a matrix of size n_l × (n_{l−1} n_h n_w).The paper notes that this matrix does not exactly specify the convolutional layer’s full linear transformation, whose exact weight matrix contains doubly block-circulant submatrices.

5 EXPERIMENTS

Experiments across CIFAR10, CIFAR100, and ImageNet evaluate strict and approximate OrthDNNs, especially SVB and BBN, as regularizers for modern architectures. The methods generally improve generalization, robustness, and practical efficiency.

Comparative studies: Strict and approximate OrthDNNs outperform standard SGD on 20-layer ConvNet and ResNet models trained on CIFAR10.Approximate methods perform as well as strict OrthDNNs at much lower computational cost.
Hard and soft regularization: SVB and SRIP outperform soft regularization on a 68-layer CIFAR10 ResNet, while BBN slightly improves performance over BN.BBN may be incompatible with soft regularization and RRIP, causing degraded performance when combined.
Modern architectures: SVB and BBN improve generalization across ResNet, Wide ResNet, DenseNet, and ResNeXt models on CIFAR10 and CIFAR100.Improvements are generally greater on CIFAR100 than CIFAR10, possibly because CIFAR100 provides fewer samples per category.
Modern architectures: SVB and BBN improve generalization for large-scale ResNet-152, DenseNet-264, and ResNeXt-101 models on ImageNet.The ImageNet results use single-crop testing at 320 × 320.
Varying sample sizes: SVB and BBN consistently improve classification across ImageNet training subsets containing 1/10, 1/5, 1/2, or all training images per category.The improvements are more obvious for smaller training subsets.
Robustness against common corruptions: SVB and BBN improve robustness to common ImageNet corruptions, with gains maintained as corruption severity increases.Results average performance across 15 corruption types and five severity levels.

6 CONCLUSION

The paper connects spectral regularization with generalization theory by deriving a singular-value-sensitive bound and designing OrthDNN algorithms from its optimum. Experiments report efficacy and robustness for OrthDNNs, SVB, and BBN.

Conclusion: The paper derives a generalization error bound sensitive to the scale and range of each weight matrix’s singular-value spectrum.The analysis first proves local isometry on practical data distributions and incorporates it into PAC-based generalization analysis.
Conclusion: Equal singular values optimize the bound’s degree of isometry, motivating strict and approximate OrthDNNs with orthonormal rows or columns.The paper proposes SVB for approximate OrthDNNs and BBN for compatibility with batch normalization.
Conclusion: Benchmark image-classification experiments show efficacy and robustness for OrthDNNs and the proposed SVB and BBN methods.

APPENDIX A PROOF OF LEMMA 3.1.

The proof establishes how singular-value structure controls local variation through matrix pseudoinverses and singular-vector subspaces. It then propagates these relationships across network layers.

Pseudoinverse lemma: The appendix introduces a pseudoinverse lemma for vectors outside a matrix’s null space.For such vectors, the pseudoinverse reconstructs the original vector through W†W.
Layerwise singular-value analysis: SVD decomposes each weight matrix into orthogonal factors and singular values, identifying the subspaces relevant to layerwise input variation.The proof uses orthogonality of the singular-vector factors and constrains variation to directions associated with nonzero singular values.
Layerwise singular-value analysis: The proof shows that nonzero layer variation must correspond to nonzero singular values and lies in the appropriate right-singular-vector subspace.This relationship enables tighter control of sample variation through the singular values of the weight matrices.
Cascading across layers: Applying the layerwise result successively across all layers yields the network-level variation bound.The argument uses norm preservation by orthogonal matrices together with the singular-value constraints.

APPENDIX B PROOF OF LEMMA 3.2.

The proof constructs a partition of input space on which each layer, and therefore the full network, is linear. ReLU and max-pooling neurons refine regions through hyperplane arrangements and activation labels.

Inductive construction: The induction maintains regions in which each neuron is a linear functional on its active support and zero elsewhere.The base case represents first-layer rows as hyperplanes partitioning the input space.
ReLU case: ReLU neurons split a region according to the sign of their pre-activation, producing subregions with fixed activation patterns.The resulting labels record whether each neuron is active on a region.
Max-pooling case: Max pooling further partitions regions using hyperplanes that compare pooled pre-activations and determine the maximizing neuron.Within each resulting subregion, the selected max-pooling output is linear.
Inductive construction: Combining the refined regions and their labels preserves the linear-map property through successive layers.The proof handles networks with or without max pooling and completes the induction over layers.
Conclusion of proof: Consequently, the full network is a linear map on every region in the final partition.

APPENDIX C PROOF OF LEMMA 3.3.

The proof constructs a covering of the sample space whose regions make the network linear, then bounds each region’s geometry through distances to activation boundaries and singular values.

For each sample, the proof identifies the nearest region boundary and the neuron whose activation hyperplane produces that shortest distance.The relevant neuron may occur in any intermediate layer, depending on the training set and learned network.
The nearest-boundary distance is related to the neuron’s activation value and bounded using the maximum singular values of the preceding weight matrices.The proof uses the fact that the activation vanishes on the selected boundary and invokes singular-value bounds.
Submatrix singular values are controlled through the Cauchy interlacing law applied after deleting rows from the relevant weight matrices.
A covering set is constructed so that the network T is linear within each covering ball.The covering radius is r, giving ball diameter γ = 2r.

APPENDIX D PROOF OF LEMMA 3.4.

The proof shows that each covering ball inherits local isometry from the network’s linear restriction, with its isometry range controlled by the singular values of the full weight matrices.

A covering of X is chosen so that T is linear on every ball containing a training sample.
Within each ball, the restricted mapping T|B is δ|B-isometric with respect to the variation space X − N(T|B).
The minimum and maximum singular values of each full weight matrix are compared with the corresponding singular values of T|B.The comparison uses the Cauchy interlacing law by row deletion.
Max-pooling does not prevent the row-deletion argument because the pooling projection preserves the relevant norm calculation.
A mapping that is jointly bounded by δ1 and δ2 relative to one is also isometric with the larger deviation max(|δ1 − 1|, |δ2 − 1|).

APPENDIX E PROOF OF THEOREM 3.1

The theorem combines local isometry with a manifold covering and concentration argument to obtain a robustness and generalization bound for the network.

Because X is a k-dimensional manifold, its covering number is upper bounded using a k-dependent geometric expression.
The covering partitions samples into balls, whose training-sample counts form a multinomial random variable.
The argument assumes that T is γ-cover δ-isometric with respect to the input distribution over samples.
Applying the Lipschitz condition to the loss and bounding within-ball deviations yields an upper bound of A(γ + δ).
The resulting algorithm is (|Y|N, A(γ + δ))-robust when the covering number is N = (CX/γ)^k.

APPENDIX F

The appendix describes an SGD procedure that keeps network weight matrices on Stiefel manifolds by projecting gradients onto tangent spaces and retracting updates back to the constraint set.

The constrained optimization trains an L-layer DNN while enforcing manifold constraints on its weight matrices.
For rectangular layers with nl ≥ nl−1, the Stiefel constraint is Wl^T Wl = I.The algorithm applies directly to fully connected layers; convolutional kernels require conversion to matrix form.
Each SGD iteration updates a layer weight matrix within its Stiefel manifold while leaving bias updates standard.
The procedure follows optimization methods on matrix manifolds whose convergence properties have been analyzed previously.
The Euclidean gradient, or a momentum variant, is projected onto the tangent space before the weight update.
A retraction maps the updated tangent-space point back to the Stiefel manifold using the Q factor of a QR decomposition.QR decomposition may be computed by Gram-Schmidt orthonormalization.

APPENDIX G PROOF OF LEMMA 4.1

The proof analyzes singular values of a transformed matrix in general and full-row-rank rectangular cases. In the special case, it shows that the transformed matrix’s singular values are the absolute values of the diagonal entries of G.

General case: The general case sets P = min(M, N), assumes W has P singular values equal to 1, and orders the transformed matrix’s singular values decreasingly.The proof then invokes bounds based on extreme singular values and the operator-norm inequality ∥Ab∥2 ≤ ∥A∥2∥b∥2.
General case: Because G has nonzero entries and W = G−1 eG, the proof selects a minimizing nonzero vector to relate the extreme singular values of the transformed matrix and W.The argument uses the minimizing vector x∗ together with definitions of the extreme singular values.
Special case: For M ≤ N and rank(W) = M, the proof assumes the diagonal entries of G are positive and ordered without loss of generality.It represents the transformed matrix as fW = IGW, where I is an M × M identity matrix.
Special case: The proof constructs an SVD of the transformed matrix using an orthogonal complement of W, yielding fW = I[G, 0]V⊤.Sign changes in corresponding columns of I or V handle diagonal entries of G that are not positive.
Special case: The transformed matrix’s singular values are exactly {|gi|}M, because matrix singular values are uniquely determined even though singular vectors are not.This identifies the spectrum directly from the diagonal entries of G.