PaperlayerView exact revision on arXiv

Source-linked AI summary

Orthogonalizing Convolutional Layers with the Cayley Transform

Asher Trockman, J. Zico Kolter

arXiv:2104.07167v1cs.LGstat.ML

TL;DR

Orthogonal convolutions are harder to enforce directly than orthogonality in fully connected layers, while existing convolutional approaches can be limited in scope or costly. This paper uses a Fourier-domain Cayley transform to parameterize orthogonal convolutions, and reports state-of-the-art deterministic certified robustness against ℓ2-bounded adversaries. The approach maintains high orthogonality and scales to some architectures better than prior methods.

  • Problem

    Existing convolutional orthogonalization methods are heuristic, costly, or limited in which orthogonal convolutions they can represent.

    Source: §1 · p. 1

  • Method

    The method applies the Cayley transform to skew-symmetric convolutions and computes the required inverse convolution efficiently in the Fourier domain.

    Source: §1 · pp. 1–2, §4 · p. 4

  • Results

    The Cayley layer achieves state-of-the-art deterministic certified robustness against ℓ2-bounded adversaries and generally outperforms alternatives, particularly for larger architectures.

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

  • Takeaways & Limitations

    The method maintains high orthogonality before and after learning and scales better to some architectures than previous approaches.

    Source: §6 · p. 9

    The parameterization excludes orthogonal convolutions with -1 eigenvalues, and ordinary strided convolutions are generally incompatible because downsampling is not invertible.

    Source: §4.1 · p. 5

Abstract

from arXiv · show

Recent work has highlighted several advantages of enforcing orthogonality in the weight layers of deep networks, such as maintaining the stability of activations, preserving gradient norms, and enhancing adversarial robustness by enforcing low Lipschitz constants. Although numerous methods exist for enforcing the orthogonality of fully-connected layers, those for convolutional layers are more heuristic in nature, often focusing on penalty methods or limited classes of convolutions. In this work, we propose and evaluate an alternative approach to directly parameterize convolutional layers that are constrained to be orthogonal. Specifically, we propose to apply the Cayley transform to a skew-symmetric convolution in the Fourier domain, so that the inverse convolution needed by the Cayley transform can be computed efficiently. We compare our method to previous Lipschitz-constrained and orthogonal convolutional layers and show that it indeed preserves orthogonality to a high degree even for large convolutions. Applied to the problem of certified adversarial robustness, we show that networks incorporating the layer outperform existing deterministic methods for certified defense against $\ell_2$-norm-bounded adversaries, while scaling to larger architectures than previously investigated. Code is available at https://github.com/locuslab/orthogonal-convolutions.

1 Introduction

The section motivates orthogonality for deep networks and identifies a gap in expressive, scalable orthogonal convolutions. It introduces a Cayley-transform approach and reports strong orthogonality and certified-robustness results.

1 Introduction

  • Orthogonal initialization can support fast, stable training of very deep vanilla CNNs (Xiao et al., 2018; Saxe et al., 2013), while orthogonality is associated with gradient preservation and adversarial robustness.The section also relates orthogonality to stable activations and long-term dependencies in RNNs.Source: §1 · p. 1
  • Convolutional orthogonalization remains challenging: prior Lipschitz methods give loose bounds and can attenuate gradients, singular-value clipping needs costly projections, and BCOP cannot express all orthogonal convolutions.The prior-work claims cite Tsuzuku et al. (2018), Sedghi et al. (2018), and Li et al. (2019), respectively.Source: §1 · p. 1
  • The proposed method directly parameterizes orthogonal convolutions with the Cayley transform applied to skew-symmetric convolutions, including non-square weight matrices.It computes the inverse convolution required by the transform efficiently in the Fourier domain.Source: §1 · pp. 1–2
  • The Cayley layer achieves state-of-the-art deterministic certified robustness against ℓ2-bounded adversaries and generally outperforms alternatives, particularly in larger architectures.It also preserves orthogonality in 32-bit precision irrespective of channel count and provides considerable empirical robustness without adversarial training.Source: §1 · p. 2

2 Related Work

Related work connects orthogonality to signal preservation and reviews matrix-based and Lipschitz-constrained approaches. The paper distinguishes its direct parameterization of orthogonal convolutions from methods that reshape kernels or constrain Lipschitzness.

2 Related Work

  • Orthogonality has been studied for deep-network initialization, training regularization, and RNN memory, with prior work demonstrating applications to very deep CNNs and long-term dependencies.The section cites Saxe et al. (2013), Pennington et al. (2017), Xiao et al. (2018), Qi et al. (2020), Helfrich et al. (2018), and Arjovsky et al. (2016).Source: §2 · p. 2
  • Earlier Cayley-transform methods orthogonalize matrices or reshaped kernels, whereas this paper directly parameterizes orthogonal convolutions (Sedghi et al., 2018).Li et al. (2020) use an iterative Cayley approximation for orthogonally constrained optimizers; the paper distinguishes that from orthogonal convolution.Source: §2 · p. 2
  • Lipschitz bounds can support deterministic certificates for ℓ2-bounded perturbations, but mere Lipschitz constraints can attenuate gradients unlike orthogonal layers.The section cites Tsuzuku et al. (2018) for certification and Anil et al. (2019) for gradient attenuation.Source: §2 · p. 2
  • The review contrasts scalable Lipschitz-layer bounds with other verification approaches and notes that probabilistic methods still outperform deterministic methods (Cohen et al., 2019).It also describes SMT, integer-programming, and semidefinite-programming verification approaches, and an LP-based robust-loss bound.Source: §2 · p. 2

3 Background

The background defines orthogonality and its convolutional analogue, then relates orthogonality to ℓ2 Lipschitzness. It explains how Lipschitz bounds and classification margins yield certificates against bounded perturbations.

3 Background

  • For a semi-orthogonal matrix, U^T U = I or UU^T = I; when m ≥ n it preserves input norms, and when m < n it is non-expansive.A matrix is orthogonal exactly when all its singular values equal 1.Source: §3 · p. 3
  • A convolution with equal input and output channels is orthogonal when it preserves the Frobenius norm of every input tensor; unequal channel counts extend this to semi-orthogonality.Orthogonalizing individual kernels does not necessarily make the convolution norm-preserving.Source: §3 · p. 3
  • Orthogonality implies 1-Lipschitzness, and composition bounds a network's Lipschitz constant by the product of layer constants; residual sums use the sum of their constants.These bounds can be loose; the section motivates convex combinations in residual connections.Source: §3 · p. 3
  • A classification can be certified robust to ℓ2 perturbations of size ϵ when its margin exceeds 2Lϵ, where L is the logit function's Lipschitz constant.The margin is the distance between the correct logit and the next-largest logit.Source: §3 · p. 3

4 The Cayley transform of a Convolution

The method applies the Cayley transform to a skew-symmetric convolution, using Fourier-domain matrix operations to compute the inverses it requires. Its scope and cost are shaped by circular-convolution assumptions, incomplete parameterization, and runtime trade-offs.

4 The Cayley transform of a Convolution

  • The Cayley transform is applied to circular convolutions represented as doubly block-circulant matrices, avoiding direct construction and inversion of the full convolution matrix.The method focuses on circular convolutions, where out-of-bounds kernel values wrap around and Fourier-domain computation is efficient.Source: §4 · pp. 3–4
  • Fourier-domain multi-channel convolution becomes a batch of matrix-vector products, so inverting those smaller matrices computes the inverse convolution needed by the Cayley transform.The Fourier representation also makes finding the skew-Hermitian part equivalent to skew-symmetrizing the convolution.Source: §4 · pp. 3–4
  • The algorithm forms skew-Hermitian Fourier-domain weights, inverts I + A, computes the Cayley transform, and returns to the spatial domain with an inverse FFT.The inverse FFT result is stated to be exactly real despite the intermediate complex matrices.Source: §4 · p. 4, §4.1 · p. 5

4.1 Properties of our approach

  • For rectangular channel dimensions, padding and projection yield norm-preserving semi-orthogonal maps when cout ≥ cin and non-expansive maps when cin ≥ cout.The efficient implementation inverts a square matrix of order min(cin, cout).Source: §4.1 · p. 5
  • Unlike BCOP’s fixed-size kernels, the Cayley layer can represent learnable kernels up to the input size, but its parameterization omits orthogonal convolutions with −1 eigenvalues.Fixed diagonal ±1 scaling can represent such cases, but the method cannot optimize over those discrete scalings or all orthogonal and special orthogonal convolutions.Source: §4.1 · p. 5
  • Stride-2 convolution cannot be inverted after downsampling; compensating with 4× as many output channels is possible but computationally inefficient.The authors instead use an invertible downsampling layer to emulate striding.Source: §4.1 · p. 5
  • The resulting convolution uses circular rather than zero padding, which the authors expect to have little performance impact when image subjects are centered.BCOP and Sedghi et al. also restricted their attention to circular convolutions.Source: §4.1 · p. 5
  • The Cayley layer is substantially slower than plain convolution, but takes 1/2× to 4× as long as BCOP depending on architecture.The paper gives Fourier-transform and matrix-inversion complexity estimates and reports runtime comparisons in Figure 6 and Tables 4 and 5.Source: §4.1 · pp. 5–6

5 Experiments

Experiments evaluate practical orthogonality and adversarial robustness against alternatives across CIFAR-10 architectures. The Cayley layer is nearly norm-preserving in practice and outperforms BCOP on KWLarge certifiable robustness, with results also reported for empirical attacks and larger models.

5.1 Training and Architectural Details

  • CIFAR-10 experiments used Adam and piecewise triangular learning rates; multi-class hinge loss outperformed cross-entropy, with ε0=0.5 controlling the accuracy–robustness tradeoff.The learning rate was selected from five values for each architecture/convolution pair; 0.001 was most often appropriate.Source: §5.1 · pp. 6–7
  • Comparisons used KWLarge, 1-Lipschitz ResNet9, and WideResNet10-10; residual paths were convex combinations to remain non-expansive, and BatchNorm was excluded.Architectures were limited by compute and memory; GroupSort with group size 2 was more effective than ReLU.Source: §5.1 · p. 7

5.2 Adversarial Robustness

  • Certifiable accuracy counts test points with margin above 2Lε at ε=36/255; empirical attacks used 10-step PGD and AutoAttack’s APGD-CE and APGD-DLR.Decision-based AutoAttack attacks provided no improvements.Source: §5.2 · p. 7

5.3 Results

  • 75.33% clean test accuracy and 59.16% certifiable robust accuracy at ε=36/255 were reported for Cayley, versus BCOP’s 75.11% and 58.29%, respectively.The comparison reports means and standard deviations over five experiments.Source: Table 1 · p. 8, §5.3 · p. 8
  • Norm ratios stayed between 0.99999 and 1.00001; layers that preserve or increase channel count are guaranteed orthogonal, while channel-reducing layers are non-expansive.The channel-reducing layer became slightly more norm-preserving after training.Source: §5.3 · p. 8
  • At a Lipschitz upper bound of 0.85, Cayley reached 59.99% certifiable robustness with 74.35% test accuracy; the four top-performing methods were similar after scaling.The bound was selected to give Cayley test accuracy similar to RKO.Source: §5.3 · pp. 8–9
  • With width multiplied by 3 and kernel size increased to 5, certified robust accuracy reached 61.13% for Cayley and 60.55% for BCOP.The paper reports no certifiable-accuracy improvement with ResNets; kernel size 5 helped, while 7 and 9 were slightly worse.Source: §5.3 · p. 9
  • For WideResNet10-10, Cayley achieved 82.99% clean accuracy and 73.16% robust accuracy at ε=36/255; it outperformed alternatives in ResNet9 and WideResNet10-10, with less decisive results for KWLarge.RKO performed similarly at larger Lipschitz bounds, while Cayley was consistently slightly better than BCOP.Source: §5.3 · p. 9

6 Conclusion

The paper presents a Cayley-transform parameterization that maintains high orthogonality and improves deterministic certified robustness against ℓ2-bounded adversaries. Its Fourier-domain construction extends to semi-orthogonal circular convolutions when input and output channel counts differ.

6 Conclusion

  • The method improved state-of-the-art deterministic certified robustness against ℓ2-bounded adversaries and maintained high orthogonality before and after learning.The authors also report that it scales better to some architectures than previous approaches and gives networks considerable inherent robustness.Source: §6 · p. 9
  • The authors caution that kernel-orthogonalization heuristics also performed well for empirical robustness, while orthogonality's gradient-norm advantage may require deeper networks than tested.They hypothesize that Lipschitz-constant control, rather than orthogonality itself, may be better for the robustness/accuracy tradeoff.Source: §6 · p. 9

A Orthogonalizing Convolutions in the Fourier Domain

  • A suitable discrete Fourier transform block-diagonalizes multi-channel circular convolution, allowing the Cayley transform to produce a real orthogonal convolution when input and output channel counts match.The Fourier-domain representation remains real after the transform when the original convolution is real.Source: A Orthogonalizing Convolutions in the… · pp. 13–14
  • Because the Fourier-domain matrix is block diagonal, the Cayley transform requires inverting only n^2 blocks of size c × c rather than the full convolution matrix.The transform is applied to the blocks of D.Source: A Orthogonalizing Convolutions in the… · pp. 13, 15

A.1 Semi-Orthogonal Convolutions

  • When channel counts differ, the method uses semi-orthogonalization; for cin ≤ cout it computes the needed inverse efficiently via a Schur complement.The construction is equivalent to padding to equal channel counts and projecting, without literally performing those operations.Source: §A.1 · pp. 15–16
  • The Fourier-domain procedure efficiently semi-orthogonalizes real multi-channel 2D circular convolutions, and the authors note it may also support determinant or singular-value calculations.They suggest approximations or the exponential map as possible ways to avoid expensive inverses in future work.Source: §6 · p. 9, §A.1 · p. 16

B Additional Results

The additional results examine how robustness and accuracy vary with Lipschitz upper bounds for ResNet9 and KWLarge, and with ε0 for KWLarge. On KWLarge, Cayley exceeds BCOP in robust accuracy, while RKO methods are overall more robust by around 2% with a marginal clean-accuracy decrease.

Additional Results

  • Figure 3 examines the robustness/accuracy tradeoff as the Lipschitz upper bound changes for ResNet9.Source: Figure 3 · p. 17
  • Table 3 reports means and standard deviations from five experiments with normalized inputs, whose normalization layer raises the network Lipschitz bound to approximately 4.1.The caption identifies the reference as CIFAR-10 standard deviation.Source: Table 3 · p. 17
  • Figure 4 examines the robustness-versus-accuracy tradeoff as the Lipschitz upper bound changes for KWLarge.The best upper bound for Cayley and BCOP may be less than 1 for this architecture.Source: Figure 4 · p. 17, B Additional Results · p. 17
  • On KWLarge, RKO methods are overall more robust than Cayley by around 2%, with only a marginal decrease in clean accuracy.Cayley nevertheless outperforms BCOP in robust accuracy.Source: B Additional Results · p. 17
  • Figure 5 examines the effect of varying ε0 for Lipschitz margin training on KWLarge.Source: Figure 5 · p. 17

C Empirical runtimes

The runtime comparison varies KWLarge width and examines how convolutional layer shape affects efficiency. Cayley can be more efficient for small spatial dimensions, large kernels, or unequal input and output channel counts, but orthogonal convolutional layers remain slower than plain convolutions.

C Empirical runtimes

  • The KWLarge width comparison reports accuracy changes and average runtime per epoch over 100 epochs; BCOP could not be scaled to width 8 because of time and memory constraints.The caption notes that wider networks may need more epochs to converge.Source: Table 4 · p. 18
  • Cayley was not as fast for residual networks, particularly WideResNet, where larger spatial dimensions and more channels can increase its runtime.The table caption attributes this to spatial dimension and channel count as multiplicative runtime factors.Source: Table 5 · p. 18
  • Cayley is especially efficient with small spatial dimensions, large kernels, or unequal input and output channels, while BCOP tends to be faster at very large spatial sizes or with large spatial sizes and many channels.All orthogonal convolutional layers are significantly slower than plain convolutional layers.Source: Figure 6 · p. 19
  • Runtime was measured with PyTorch's autograd profiler by summing CUDA execution times, using batch size 128 and averaging each data point over 32 iterations.Measurements used an Nvidia Quadro RTX 8000.Source: C Empirical runtimes · p. 19

D.1 Robustness Experiments

These additional robustness experiments compare Cayley-based variants and a plain-convolution baseline. The plain convolution gains accuracy but loses some robustness, while replacing Björck with Cayley in BCOP slightly decreases performance across metrics.

D.1 Robustness Experiments

  • Table 6 covers KWLarge trained for provable robustness and reports mean and standard deviation over five trials.Source: Table 6 · p. 20
  • Table 7 covers ResNet9 trained for empirical adversarial robustness and reports mean and standard deviation over three trials.Source: Table 7 · p. 20
  • Replacing Björck orthogonalization with Cayley in BCOP slightly decreases performance across metrics, paralleling the relationship between RKO and CRKO.The CayleyBCOP experiments are reported in Tables 6 and 7.Source: §D.1 · p. 20
  • Replacing the Cayley convolution with a plain convolution gains accuracy but loses some robustness.The plain-convolution baseline retains Cayley fully-connected layers for the cited comparison.Source: §D.1 · p. 20
  • A plain-convolution baseline was not reported for KWLarge provable-robustness experiments because bounding each layer's Lipschitz constant would require a more sophisticated technique outside the investigation's scope.Source: §D.1 · p. 20

D.2 Wasserstein Distance Estimation

The Wasserstein distance experiment replaces BCOP and Björck layers with Cayley layers and reports a significantly tighter bound. The comparison uses the GroupSort (MaxMin) activation on STL-10.

D.2 Wasserstein Distance Estimation

  • The Cayley-layer Wasserstein GAN experiment achieved a significantly tighter bound than the reported BCOP, RKO, and OSSN results.Table 8 reports the best bounds for those methods across repository trials and the result of one Cayley trial.Source: Table 8 · p. 20
  • The reported Wasserstein GAN comparison uses the GroupSort (MaxMin) activation and the STL-10 dataset.Source: Table 8 · p. 20
  • The experiment replaced BCOP with a Cayley convolutional layer and the Björck linear layer with a Cayley fully-connected layer.It selected the best Wasserstein distance bound from one trial at each of four learning rates used in BCOP: 0.1, 0.01, 0.001, and 0.0001.Source: §D.2 · p. 20

E Example Implementations

The example implements CayleyConv with Fourier-domain operations and includes a variant for stride-2 convolutions. Its helpers construct a frequency shift matrix and compute the Cayley transform.

Cayley transform helper

  • The Cayley helper handles cin > cout by transposing channels, then builds the transform from matrix blocks and an inverse of I + A.The code forms A from skew-symmetric and V-conjugate-product terms before concatenating the output blocks.Source: E Example Implementations · p. 21

Frequency shift

  • A frequency shift matrix is formed from pairwise index sums and complex exponentials, then registered for use in the Fourier-domain convolution.The shift amount is derived from the kernel size, and the stored matrix is restricted to the real FFT frequencies.Source: E Example Implementations · p. 21

CayleyConv

  • The forward pass transforms inputs and weights with 2D real FFTs, applies the Cayley-transformed weights frequency by frequency, then reconstructs the output with an inverse FFT.The implementation also applies a shift matrix to the transformed weights.Source: E Example Implementations · p. 21

Stride-2 implementation

  • For stride-2 support, the example substitutes a StridedConv base class that expands input channels fourfold and halves the kernel size.The class uses einops for its downsampling-related input rearrangement.Source: E Example Implementations · p. 21

Implementation resources

  • The paper points readers to the project repository for further implementation and experiment details.The example states that it uses PyTorch 1.8.Source: E Example Implementations · p. 21

Related papers

Loading 2104.07167v1…