PaperlayerView exact revision on arXiv

Source-linked AI summary

Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks

Qiyang Li, Saminul Haque, Cem Anil, James Lucas, Roger Grosse, Jörn-Henrik Jacobsen

arXiv:1911.00937v2cs.LGstat.ML

TL;DR

Provable Lipschitz constraints matter for robustness and Wasserstein estimation, but matching heuristic methods’ practical success while guaranteeing the constraint remains challenging, and gradient attenuation complicates layerwise designs. The paper introduces convolutional GNP networks using BCOP, an orthogonal-convolution parameterization, and reports strong results on robustness and Wasserstein estimation. It also shows a scope boundary: the discussed 2-D representation covers only a subset of orthogonal convolutions.

  • Problem

    Heuristic Lipschitz-constraint methods can succeed in practice but provide no Lipschitz guarantees, while layerwise constraints can attenuate gradients and prior GNP architectures addressed fully connected networks.

    Source: §1 · p. 1

  • Method

    The paper builds convolutional GNP networks with BCOP, an efficient parameterization of orthogonal convolutions, and analyzes the disconnectedness of the orthogonal-convolution space.

    Source: §1 · p. 2, §3 · p. 3, §3.3 · p. 5

  • Results

    The authors report state-of-the-art deterministic provable L2 robustness on MNIST and CIFAR10 and tighter Wasserstein estimates than competing approaches.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    For Wasserstein estimation, restricting the search to GNP functions is not necessarily a hindrance because the optimal 1-Lipschitz function is GNP almost everywhere.

    Source: §1 · p. 2

    The discussed 2-D orthogonal-convolution representation covers only a subset of such convolutions, and whether simple modifications make it complete is open.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Lipschitz constraints under L2 norm on deep neural networks are useful for provable adversarial robustness bounds, stable training, and Wasserstein distance estimation. While heuristic approaches such as the gradient penalty have seen much practical success, it is challenging to achieve similar practical performance while provably enforcing a Lipschitz constraint. In principle, one can design Lipschitz constrained architectures using the composition property of Lipschitz functions, but Anil et al. recently identified a key obstacle to this approach: gradient norm attenuation. They showed how to circumvent this problem in the case of fully connected networks by designing each layer to be gradient norm preserving. We extend their approach to train scalable, expressive, provably Lipschitz convolutional networks. In particular, we present the Block Convolution Orthogonal Parameterization (BCOP), an expressive parameterization of orthogonal convolution operations. We show that even though the space of orthogonal convolutions is disconnected, the largest connected component of BCOP with 2n channels can represent arbitrary BCOP convolutions over n channels. Our BCOP parameterization allows us to train large convolutional networks with provable Lipschitz bounds. Empirically, we find that it is competitive with existing approaches to provable adversarial robustness and Wasserstein distance estimation.

1 Introduction

Provable Lipschitz constraints offer benefits for robustness, generalization bounds, and Wasserstein estimation, but matching heuristic methods’ practical success with guarantees remains challenging. The paper extends gradient norm preservation to convolutional networks and reports strong results on robustness and Wasserstein estimation.

1 Introduction

  • Heuristic methods such as gradient penalty and spectral norm regularization have practical success but do not guarantee the Lipschitz constant; existing convolutional approaches also face trade-offs in bounds, expressivity, optimization, or computation.The cited approaches include loose bounds, vanishing singular values, and computational intractability for larger networks.Source: §1 · pp. 1–2
  • Layerwise Lipschitz constraints can attenuate backpropagated gradients, while prior GNP architectures addressed this problem only for fully connected networks.The paper identifies convolutional networks as an open case for Lipschitz constraints.Source: §1 · pp. 1–2
  • The authors introduce convolutional GNP networks using an efficient orthogonal-convolution parameterization adapted from Xiao et al..Their theoretical analysis addresses the disconnected orthogonal-convolution space and optimization challenges associated with it.Source: §1 · p. 2
  • The convolutional GNP networks outperform state-of-the-art methods for deterministic provable L2 robustness on MNIST and CIFAR10 and obtain tighter Wasserstein estimates than competing approaches.The paper evaluates these networks on adversarial robustness and Wasserstein distance estimation.Source: §1 · p. 2

2 Background

This background explains how layerwise Lipschitz bounds compose and why preserving gradient norms matters for deep networks. It also introduces the certification criterion for norm-bounded robustness and the Lipschitz-function formulation of Wasserstein estimation.

2.1 Lipschitz Functions under L2 Norm

  • A network’s Lipschitz constant is upper-bounded by the product of its layer constants, but this bound can become loose in deep networks and constraints may diminish usable capacity.The paper focuses on Lipschitz functions under the L2 norm.Source: §2.1 · p. 2

2.2 Gradient Norm Preservation (GNP)

  • Gradient norm preservation (GNP) constrains layers to preserve gradient norms; strict GNP functions are 1-Lipschitz, compose as GNP functions, and have Jacobian orthogonality when input and output dimensions match.The paper takes the stricter definition with G = R^m so strict GNP functions can be composed directly.Source: §2.2 · pp. 2–3

2.3 Provable Norm-bounded Adversarial Robustness

  • For a classifier with margin M_f(x), the paper gives the robustness certificate 2lϵ < M_f(x) for an l-Lipschitz function.The margin is the true-class logit minus the largest competing logit, clipped below at zero.Source: §2.3 · p. 3, §2.4 · p. 3

2.4 Wasserstein Distance Estimation

  • The Kantorovich-Rubinstein formulation expresses Wasserstein distance as a maximization over 1-Lipschitz functions, and the optimal scalar function is GNP almost everywhere [18].Prior work found GNP networks can achieve tighter lower bounds than non-GNP networks.Source: §2.4 · p. 3

3 Orthogonal Convolution Kernels

Orthogonal convolution kernels provide the linear building blocks for gradient-norm-preserving convolutional networks, but their parameter space is disconnected; BCOP addresses this by adding channels.

3 Orthogonal Convolution Kernels

  • The paper identifies gradient-norm-preserving convolution construction as the key step, since a convolution is gradient-norm-preserving exactly when its linear operator is orthogonal.The authors analyze disconnectedness and use an auxiliary channel dimension to address its optimization challenge.Source: §3 · p. 3

3.1 Constructing Orthogonal Convolutions

  • In 1-D, orthogonal kernels can be composed from size-2 orthogonal convolutions and a channel-wise orthogonal transformation; the described 2-D representation covers only a subset of orthogonal kernels.Block convolution corresponds to composition of kernel operators.Source: §3.1 · p. 4

3.2 Topology of the Orthogonal Convolution Space

  • 2-D orthogonal convolutions with 2 × 2 kernels have at least 2(n + 1)^2 connected components, confining gradient-based optimizers to their initial component.In 1-D, the space is compact and has 2(K − 1)n + 2 components.Source: §3.2 · p. 5

3.3 Block Convolution Orthogonal Parameterization (BCOP)

  • With 2n channels, one connected component can represent every n-channel orthogonal convolution, at the cost of four times as many parameters.The construction uses projectors of rank n.Source: §3.3 · p. 5
  • BCOP parameterizes a connected subspace of orthogonal convolutions, using the 2n-channel construction to address optimization challenges caused by disconnected components.The method is named Block Convolution Orthogonal Parameterization.Source: §3.3 · p. 5

4 Related Work

Prior convolutional Lipschitz methods trade tightness, expressiveness, or computational cost, while approaches to deterministic robustness certification use varied training strategies. The paper positions BCOP as avoiding several of these convolutional-method limitations and extends gradient-norm preservation to convolutional networks.

4 Related Work

  • RKO strictly orthogonalizes the reshaped kernel matrix, but its conservative convolution bound can limit expressive power [12, 47, 39].Cisse et al. use soft regularization rather than strict orthogonality.Source: §4 · pp. 5–6
  • OSSN scales kernels to bound the convolution operator’s spectral norm by 1, but Euclidean steepest descent with its matrix 2-norm projection is not guaranteed to converge correctly [20].The authors report better performance when projecting during the forward pass, as in Miyato et al..Source: §4 · p. 6
  • SVCM approximates projection to the orthogonal-kernel space, but its many expensive iterations make tight constraints computationally intractable for large-network training.Unlike spectral normalization, singular-value clipping is a valid Frobenius-norm projection.Source: §4 · p. 6
  • BCOP avoids the runtime scaling of OSSN and SVCM, RKO’s lack of an exact Lipschitz guarantee, and the absence of gradient-norm preservation in those methods.The comparison identifies the shortcomings that BCOP is designed to avoid.Source: §4 · p. 6

4.1 Provable Adversarial Robustness

  • Deterministic robustness work includes training for easier verification [16], maximizing output margins using estimated Lipschitz bounds, and enforcing gradient-norm preservation.This paper extends the gradient-norm-preserving approach from fully connected to convolutional networks.Source: §4.1 · p. 6

5 Experiments

The experiments compare Lipschitz-constrained convolution methods on deterministic robustness and Wasserstein estimation, with BCOP outperforming competing methods in robust classification and BCOP with MaxMin giving the best Wasserstein estimate.

5.1 Network Architectures and Training Details

  • The architectures omit residual connections and batch normalization, use cyclic padding, and use invertible downsampling to preserve gradient norm.The networks are based on Wong et al.’s Small and Large convolutional architectures for robustness, and Radford et al.’s fully convolutional critic for Wasserstein estimation.Source: §5.1 · p. 7

5.2.1 Robustness Evaluation

  • Robustness evaluation uses an L2-bounded threat model, with decision-based attacks run only on the first 100 test examples because they are expensive.Robust accuracy is a lower bound determined from the model’s prediction margin.Source: §5.2.1 · p. 7

5.2.2 Comparison of Different Methods for Enforcing Spectral Norm of Convolution

  • BCOP outperforms competing methods across architectures on MNIST and CIFAR10.The comparison uses methods with a tight Lipschitz constraint of 1.Source: §5 · p. 6, §5.2.2 · p. 7, Table 1 · p. 8
  • BCOP keeps all singular values at 1 during training, while OSSN and RKO push many singular values toward 0.The authors attribute BCOP’s behavior to gradient norm preservation and orthogonality.Source: §5.2.2 · pp. 7–8, Figure 2 · p. 8

5.2.3 State-of-the-art Comparison

  • BCOP matches Wong et al. on the Small architecture and performs better on the Large architecture.The comparison is on CIFAR10; Table 3 reports results on the full test set and, for some results, the first 100 samples.Source: §5.2.3 · p. 8, Table 3 · p. 9

5.3 Wasserstein Distance Estimation

  • BCOP with MaxMin gives the best Wasserstein estimate, and gradient norm preservation yields significantly tighter lower bounds.The estimates are strict lower bounds for the data and generator distributions of an STL-10 GAN.Source: §5 · p. 7, §5.3 · p. 9, Table 4 · p. 9

6 Conclusion and Future Work

The paper concludes that BCOP enables convolutional gradient-norm-preserving networks with strong robustness and Wasserstein results, while noting that its parameterization covers only a subspace of orthogonal convolutions. The accompanying appendices analyze spectral normalization, complexity, and architectural choices for these networks.

6 Conclusion and Future Work

  • BCOP convolutional GNP networks outperform state-of-the-art deterministic provable robustness methods on MNIST and CIFAR10 and provide tighter Wasserstein distance estimates than competing approaches.The parameterization remains limited to a subspace of orthogonal convolutions; a complete parameterization is left for future work.Source: §6 · p. 9

A Optimizing under spectral normalization

  • Spectral normalization is a valid projection under the operator 2-norm but not the Frobenius norm, and a diagonal example converges to [1, 0.5] rather than the identity under the described update.The appendix gives the steepest descent direction under the matrix operator 2-norm by rescaling all nonzero singular values equally.Source: A Optimizing under spectral… · p. 13

B Examples of Lipschitz Functions

  • Orthogonal linear transformations preserve vector norms when input dimension is no greater than output dimension, and are gradient-norm-preserving when input dimension is at least output dimension.GroupSort is a 1-Lipschitz activation that can recover ReLU and absolute value and addresses ReLU’s capacity limitation in Lipschitz-constrained networks.Source: B Examples of Lipschitz Functions · p. 14

C Algorithm Complexity of Different Approaches to Enforce Lipschitz Convolution

D Architectural Detail Considerations for GNP Convolutional Networks

  • The architecture removes residual connections and batch normalization, and uses MaxMin activation with group size 2 to maintain the GNP and Lipschitz design.Residual connections are difficult to reconcile with a 1-Lipschitz GNP network, while batch normalization is neither 1-Lipschitz nor gradient-norm-preserving.Source: D Architectural Detail Considerations… · p. 15, §D.1 · p. 15, §D.4 · p. 16

D.2 Zero-Padded Orthogonal Convolutions

  • Zero-padded orthogonal 1-D convolutions can only have size-1 kernels, so the construction uses cyclic padding instead..Source: §D.2 · p. 16

D.3 Invertible Downsampling

  • Invertible downsampling rearranges pixels from one channel into multiple channels, making a stride-1 convolution equivalent to a strided convolution on the original image.The illustrated case uses one input channel and stride 2.Source: §D.3 · p. 16, Figure 3 · p. 16

E Network Architectures

The appendix specifies the network architectures, training settings, orthogonalization procedure, and BCOP implementation used in the experiments.

E Network Architectures

  • The Small convolutional network has two stride-2 convolutional layers and two linear layers, while the Large network has four convolutional layers and three linear layers.The appendix also describes the FC-3 and DCGAN Critic architectures; most layers decrease in size, so orthogonality suffices for gradient-norm preservation through most of these networks.Source: E Network Architectures · pp. 16–17

F Training Details

  • Robustness experiments trained for 200 epochs with Adam, while Wasserstein estimation networks trained for 25,600 iterations using RMSprop.The selected learning rates were 0.001 for robustness experiments and 0.001 for ReLU or 0.0001 for MaxMin in Wasserstein estimation.Source: F Training Details · p. 17

G Orthogonalization Procedure

  • The orthogonalization procedure uses 20 iterations of first-order Björck with p = 1.Björck is used to find a nearby orthogonal matrix under the Frobenius norm of the difference.Source: G Orthogonalization Procedure · pp. 17–18

H BCOP Implementation

  • BCOP builds convolutions from block convolutions and symmetric projectors, using Björck orthogonalization and power-iteration rescaling for convergence guarantees.The rescaling does not change the converged orthogonal matrix because Björck is scale-invariant.Source: H BCOP Implementation · p. 18

I Additional Ablation Experiments

The appendix describes alternative methods and comparison tables for provable robustness, but the supplied passages do not report the table outcomes.

I Additional Ablation Experiments

  • BCOP-Fixed freezes convolution weights and trains only the fully connected layer as a check that BCOP convolution layers contribute to learning.The check addresses whether training might be offloaded to the fully connected layer, as reported for other work.Source: I Additional Ablation Experiments · p. 18
  • RK-L2NE bounds the reshaped kernel’s spectral norm, then scales it down by the kernel size to bound the convolution’s spectral norm.The computations are performed during the forward pass.Source: I Additional Ablation Experiments · p. 18
  • Tables 8 and 9 compare convolutional networks with Croce and Hein and Qian and Wegman provable-robustness models, respectively.The supplied passages identify the comparison scope but do not provide table values or outcomes.Source: Table 8 · p. 19, Table 9 · p. 19

J Comparison to Other Baselines for Provable Adversarial Robustness on MNIST and CIFAR10

The appendix reports comparisons with provable-robustness baselines and analyzes the connected components of 1-D orthogonal convolution spaces. It characterizes these components through symmetric projectors and canonical SOCK submanifolds.

J Comparison to Other Baselines for Provable Adversarial Robustness on MNIST and CIFAR10

  • Both convolutional models outperform Croce and Hein’s Small model on clean and robust accuracy; the fully connected baseline is slightly better on MNIST but performs worse on CIFAR10.The Qian and Wegman models target empirical attacks, while the comparison reports both certified robustness and gradient-based attack accuracy.Source: J Comparison to Other Baselines for… · p. 19

K Topology of of 1-D Orthogonal Convolution Kernel

K.1 Background: Symmetric Projector

  • Symmetric projectors correspond to orthogonal projections onto subspaces; projectors of each fixed rank form a compact, path-connected space, while spaces of different ranks are disjoint.The range map identifies rank-k projectors with the Grassmannian of k-dimensional subspaces.Source: §K.1 · p. 20

K.2 Connected Components of 1-D Special Orthogonal Convolution Kernels (SOCK)

  • A 1-D special orthogonal convolution kernel is represented using an orthogonal matrix and a sequence of symmetric projectors combined by block convolution.The general representation space C is defined by allowing each projector to range over P(n).Source: §K.2 · p. 20, We can also define · p. 21

We can also define

  • The 1-D special orthogonal convolution space is compact and has (K − 1)n + 1 connected components, each a canonical SOCK submanifold.The canonical submanifolds fully contain the other SOCK submanifolds.Source: We can also define · p. 21

K.2.1 Equivalent SOCK Construction

  • Equivalent SOCK constructions show that balancing neighboring projector ranks can yield a contained submanifold, and rank balancing extends this containment across separated equal ranks..Source: §K.2.1 · p. 22

K.2.2 Dominance of Canonical SOCK Submanifold

The appendix shows how rank balancing places every SOCK submanifold within a canonical subspace, then identifies the connected components of the 1-D orthogonal convolution space. For 1-D kernels, that space is compact and has 2(K − 1)n + 2 connected components.

K.2.2 Dominance of Canonical SOCK Submanifold

  • Balanced rank tuples with the same rank sum define equivalent SOCK submanifolds, as adjacent ranks can be swapped without changing the subspace.Repeated adjacent swaps connect a balanced tuple to its canonical rank tuple.Source: §K.2.2 · p. 23
  • If two ranks differ by at least two, shifting one rank up and the other down gives a containing subspace with a strictly smaller imbalance score.The adjacent-rank case follows from Lemma 6.3, and the nonadjacent case from Lemma 6.4.Source: §K.2.2 · p. 23
  • Every SOCK submanifold belongs to a canonical subspace C_k, so the union of the canonical subspaces is complete.For a fixed rank sum k, balanced rank tuples yield C_k; balancing preserves the rank sum while enlarging the subspace.Source: §K.2.2 · pp. 23–24

K.2.3 Connected Components of C are Canonical SOCK Submanifolds

  • 2(K − 1)n + 2 connected components characterize the compact 1-D orthogonal convolution space, with K the kernel size and n the channel count.The SOCK components number (K − 1)n + 1; negating a row supplies the other determinant class and doubles the count.Source: §K.2.3 · p. 24

L Additional Proofs

These proofs establish when two SOCK parameterizations represent the same convolution and give an expansion of kernel elements in terms of the construction’s component matrices.

L Additional Proofs

  • Two SOCK constructions are equivalent when the adjacent projector sums match and the orthogonal matrix H is unchanged.The proof reduces equality of the full constructions to equality of the adjacent-factor sums and H.Source: L Additional Proofs · pp. 24, 26
  • The auxiliary Q function uses binary variables to select P_j or I − P_j factors, giving an alternate representation of A.This representation is introduced to simplify the subsequent proof.Source: L Additional Proofs · p. 25
  • In the kernel-element expansion, the free binary positions must contain exactly j − k ones after k forced positions are set.The passage counts these choices among (K − 1) − k free positions when deriving the coefficients.Source: L Additional Proofs · p. 27

M Disconnectedness of 2-D Orthogonal Convolutions

For 2-D orthogonal convolutions with 2 × 2 kernels, the analysis establishes a lower bound on the number of connected components by indexing components through projector ranks and the orthogonal matrix.

M Disconnectedness of 2-D Orthogonal Convolutions

  • At least 2(n + 1)^2 connected components occur for 2-D orthogonal convolutions with 2 × 2 kernels.The component count combines the (n + 1)^2 disjoint rank-pair components with the two components of the orthogonal matrix H.Source: M Disconnectedness of 2-D Orthogonal… · pp. 27–28
  • The construction can realize arbitrary symmetric projectors P and Q by choosing the kernel blocks appropriately.The passage identifies P = ˜A1 + ˜A2 and Q = ˜A1 + ˜A3.Source: M Disconnectedness of 2-D Orthogonal… · p. 28
  • The component pairs are indexed by the ranks of P and Q; every rank pair is attainable, and distinct pairs lie in disconnected sets.P and Q are formed from sums of the kernel blocks, and their symmetric-projector ranks each range across n + 1 components.Source: M Disconnectedness of 2-D Orthogonal… · p. 28

N Doubling the Channel Size Addresses BCOP Disconnectedness Issues

Doubling channels lets BCOP represent n-channel convolutions within a single connected component. The parameterization remains incomplete for 2-D orthogonal kernels, and the robustness section gives a margin-based certificate.

N Doubling the Channel Size Addresses BCOP Disconnectedness Issues

  • With 2n channels, rank-n-projector BCOP can match any n-channel BCOP convolution on the first n output channels, representing all such convolutions within one connected component.This construction requires four times as many parameters.Source: N Doubling the Channel Size Addresses… · pp. 28–29

O Incompleteness of 2-D Convolution Parameterization

  • BCOP's 2-D parameterization does not cover the full orthogonal-kernel space; the exhibited counterexample is a reordering of 1-D convolutions that can be represented by composing two BCOP convolutions.Whether reordering the 1-D components suffices to represent all 2-D orthogonal convolutions remains open.Source: O Incompleteness of 2-D Convolution… · pp. 29–30

P Certifying Provable Robustness for Lipschitz Network

  • For an L_p-Lipschitz model, the stated certificate guarantees robustness to perturbations of norm at most ε when the Lipschitz-scaled radius is below the prediction margin.The condition compares the prediction margin M_f(x) with the product of the Lipschitz bound and ε.Source: P Certifying Provable Robustness for… · p. 31
Loading 1911.00937v2…