PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectrum Extraction and Clipping for Implicitly Linear Layers

Ali Ebrahimpour Boroojeny, Matus Telgarsky, Hari Sundaram

arXiv:2402.16017v2cs.LGcs.CV

TL;DR

Efficiently and correctly computing and controlling spectra for implicitly linear layers, especially convolutions, remains challenging. The paper uses automatic differentiation for spectrum extraction and introduces iterative clipping that handles general convolution layers and compositions. The authors report improved generalization and adversarial robustness, while showing that circular-padding convolutions cannot represent arbitrary spectra.

  • Problem

    Efficient and correct computation and control of spectra remain challenging for implicitly linear layers such as convolutions, while explicit matrix construction is slow.

    Source: §1 · p. 1

  • Method

    The authors use automatic differentiation for implicit shifted-subspace spectrum extraction and develop iterative FastClip for implicitly linear layers and their compositions.

    Source: §1 · p. 2, §2.1 · p. 3

  • Results

    Experiments report that FastClip improves generalization and adversarial robustness, and the authors describe their algorithms as more accurate and effective than existing methods.

    Source: §1 · p. 2, §4 · p. 12

  • Takeaways & Limitations

    The methods can control spectral norms for convolutional and dense layers, including compositions with batch normalization, and the authors identify this as a route to controlling model Lipschitz constants.

    Source: §3.3 · p. 10, §4 · p. 12

    Circular-padding convolutions cannot represent arbitrary spectra, limiting clipping approaches that assign arbitrary values to all singular values at once.

    Source: §2.3 · p. 6

Abstract

from arXiv · show

We show the effectiveness of automatic differentiation in efficiently and correctly computing and controlling the spectrum of implicitly linear operators, a rich family of layer types including all standard convolutional and dense layers. We provide the first clipping method which is correct for general convolution layers, and illuminate the representational limitation that caused correctness issues in prior work. We study the effect of the batch normalization layers when concatenated with convolutional layers and show how our clipping method can be applied to their composition. By comparing the accuracy and performance of our algorithms to the state-of-the-art methods, using various experiments, we show they are more precise and efficient and lead to better generalization and adversarial robustness. We provide the code for using our methods at https://github.com/Ali-E/FastClip.

1 INTRODUCTION

The paper addresses the difficulty of efficiently and correctly computing and controlling spectra for implicitly linear layers, especially convolutional layers. It introduces automatic-differentiation-based extraction and clipping methods, and identifies limits on which spectra convolutions can represent.

1 INTRODUCTION

  • Controlling implicitly linear layers’ largest singular values matters for generalization, adversarial robustness, and stable backpropagation, but efficient and correct methods for general convolutional layers remain challenging.Explicitly unrolling convolutions to compute singular values is slow and cumbersome across padding and stride settings.Source: §1 · p. 1
  • PowerQR uses automatic differentiation to extract top-k singular values and vectors, while FastClip iteratively clips spectral norms for implicitly linear layers, including standard convolutions.The authors report that their extraction method is more efficient than prior work for top-k singular values and that clipping supports compositions of layers.Source: §1 · p. 2
  • The paper identifies a representational limitation: convolutional layers with circular padding cannot realize arbitrary spectra.Source: §1 · p. 2

1.1 Related Work

  • Prior methods either approximate convolution spectra, restrict padding or stride, scale the whole spectrum, or incur extra computation; the cited approaches include Miyato et al. (2018), Sedghi et al. (2018), and Senderovich et al. (2022).The paper also notes that successive power-method runs with deflation are less efficient for extracting multiple singular values than its method.Source: §1.1 · p. 2

2 METHODS

The methods combine implicit spectrum extraction with iterative spectral-norm clipping, then examine convolutional representational limits and batch-normalization compositions. The approach uses automatic differentiation to avoid forming explicit transformation matrices and can be applied to layer compositions.

2.1 Spectrum Extraction

  • PowerQR implicitly performs shifted subspace iteration using automatic differentiation, extracting top-k singular values and vectors without constructing the transformation matrix.For an affine function, subtracting its value at zero removes the bias; the method also applies to compositions of affine functions.Source: §2.1 · p. 3
  • Warm-starting PowerQR with the previous step’s right singular vectors can reduce training-time extraction to one iteration per SGD step after initial steps.The authors report that a warm start with more iterations on the initial weights helps track the top-k singular values during training.Source: §2.1 · p. 3

2.2 Clipping the Spectral Norm

  • FastClip iteratively shrinks the largest singular-value subspace rather than scaling all parameters, which would scale the whole spectrum instead of projecting onto a norm ball.The clipping loop updates the leading singular direction and repeats until the target bound is reached.Source: §2.2 · p. 4
  • For convolutional layers, the clipping update uses a value of λ below 1 for stable convergence, whereas dense layers can reach the target with λ = 1.During training, the reported setup clips every 100 steps and uses one iteration of the clipping loops.Source: §2.2 · p. 4

2.3 Limitations of Convolutional Layers

  • Circular-padding convolutions have linked singular values and, except for at most two, duplicate singular values, restricting the spectra they can represent.The theorem’s stated scope includes one input channel and multiple output channels, or one output channel and multiple input channels.Source: §2.3 · pp. 5–6
  • Because convolutions cannot represent arbitrary spectra, clipping methods that assign arbitrary values to all singular values at once cannot generally produce a valid convolutional layer; Figure 1 shows correct clipping across four tested settings for this method.The figure’s settings vary kernel size, padding, and stride.Source: §2.3 · p. 6, Figure 1 · p. 6

2.4 Batch Normalization Layers

  • Clipping a convolution more tightly can coincide with a larger batch-normalization spectral norm, while the concatenated norm slightly decreases in the reported MNIST example.The CIFAR-10 ResNet-18 example shows the convolution-batch-normalization concatenation can have a much larger norm than the convolution clipped to 1.Source: §2.4 · p. 6, Figure 2 · p. 7
  • FastClip can clip the convolution–batch-normalization composition while leaving batch-normalization layers unclipped, controlling the concatenated norm without separately adjusting those layers.Separate clipping yields a correct but potentially loose product upper bound, which may over-constrain the composition.Source: §2.4 · pp. 6–7

3 EXPERIMENTS

The experiments report that FastClip is precise and efficient across the tested models, while clipping outcomes for generalization and robustness depend on batch normalization and model structure. Applying clipping to convolution–batch-normalization concatenations offers a way to control their combined spectral norm without directly clipping batch-normalization layers.

3 EXPERIMENTS

  • The experiments compare methods on ResNet-18 and DLA using MNIST and CIFAR-10, following recommended settings for the compared methods.They include test-set accuracy and adversarial examples generated with PGD and CW.Source: §3 · p. 7, §3.2 · p. 7

3.1 PowerQR

3.2 Clipping Method

  • The study compares clipping-model correctness across convolutional-layer types and evaluates each method’s generalization and robustness on ResNet-18, training models on MNIST and CIFAR-10.It also evaluates Deep Layer Aggregation (DLA), described as more complex with more layers and parameters.Source: §3.2 · p. 7

3.2.1 Precision and Efficiency

  • FastClip is the most precise clipping method on ResNet-18 and DLA while remaining much faster than relatively accurate alternatives, with a smaller runtime increase on the larger DLA model.The ResNet-18 comparisons cover CIFAR-10 and MNIST; Figure 3 reports layer-wise spectral norms and epoch times.Source: Figure 3 · p. 8, §3.2.1 · p. 9

3.2.2 Generalization and Robustness

  • FastClip gives the largest reported generalization improvement on both DLA datasets and improves ResNet-18 test accuracy and adversarial robustness, while DLA robustness is competitive or better than alternatives.DLA models could not be trained without batch normalization under the default settings; for ResNet-18, removing batch normalization improved robustness but reduced test accuracy.Source: §3.2.2 · pp. 9–10

3.3 Clipping Batch Norm

  • FastClip-concat controls the spectral norm of convolution–batch-normalization concatenations and improves robustness without the test-accuracy loss seen when batch normalization is removed.The reported comparison also finds that direct batch-normalization clipping hinders optimization, whereas FastClip-concat follows FastClip's training-accuracy trajectory.Source: §3.3 · p. 11, Table 3 · p. 11

4 CONCLUSIONS

The paper presents efficient, accurate spectrum extraction and clipping for implicitly linear layers, including compositions with batch normalization. Experiments support their use as regularization associated with better generalization and adversarial robustness.

4 CONCLUSIONS

  • The algorithms extract and clip spectra efficiently and accurately for implicitly linear layers, including convolutional and dense layers.The method also applies to concatenations with other implicitly linear layers, such as batch normalization.Source: §4 · p. 12
  • The experiments show that the clipping method can serve as regularization for neural networks with convolutional and dense layers, with better generalization and adversarial robustness.Source: §4 · p. 12
  • Applying the algorithms to layer concatenations offers a route to controlling model Lipschitz constants that the paper identifies as needing further exploration.Source: §4 · p. 12

A.1 Proofs of Section 2.1

The proof links gradients of an implicitly linear layer to its linear operator, then interprets the algorithm's shifted iteration as subspace iteration. Subtracting the shift recovers eigenvalues of the operator product, whose eigenvalues yield squared singular values.

A.1 Proofs of Section 2.1

  • Subtracting μ from the eigenvalues of A′ = AW + μI recovers the eigenvalues of AW, which are the squared singular values of MW.Source: §A.1 · p. 14
  • The algorithm's QR steps form subspace iteration on A′, so the diagonal entries of R converge to its eigenvalues and Q's columns converge to corresponding eigenvectors.Source: §A.1 · p. 14
  • For g(X) = f(X) − f(0), the affine offset cancels, leaving the linear part MWX used in the gradient-based argument.Source: §A.1 · p. 14

A.2 Proofs of Section 2.3

The proofs derive singular-value results for circularly padded convolutions by representing them with circulant matrices. They also establish lower and upper spectral-norm bounds for single-input- or single-output-channel cases.

A.2 Proofs of Section 2.3

  • For a single input and output channel, the lemma sets up the singular-value derivation for a circular convolution from its vectorized kernel.The corollary’s bounds are then proved using this lemma and the circulant eigenvalue argument.Source: §A.2 · pp. 14–16
  • Circulant-matrix eigenvalues yield the singular values of the single-channel circular convolution by taking square roots of the eigenvalues of its Gram matrix.The proof constructs the Gram matrix as a symmetric circulant matrix and derives its eigenvalues from the first row.Source: §A.2 · p. 14
  • The proof handles multiple output channels by expressing the operator as stacked circulant channel matrices and forming their Gram matrix.The resulting matrix is a sum of channel-wise terms, allowing the single-channel circulant result to be applied.Source: §A.2 · p. 15
  • For layers with one input or output channel, the corollary gives lower and upper bounds on the spectral norm, which coincide when all kernel values are non-negative.The lower bound follows by evaluating at the root of unity 1; the proof identifies this value as one of the layer’s singular values.Source: §A.2 · pp. 15–16

B.1 Modifying the Whole Spectrum

This section describes changing an operator’s spectrum and then fitting the result back into the original layer form. It notes that this procedure can be slow and may not attain an exact fit for some operator classes.

B.1 Modifying the Whole Spectrum

  • PowerQR’s singular values and right singular vectors can specify a modified operator with a chosen spectrum without computing the exact left singular vectors or operator matrix.The construction replaces the singular values while retaining the extracted right singular vectors.Source: §B.1 · p. 16
  • For convolutional layers, the modified operator may not itself have convolutional form, so the method fits new kernel parameters by regression.The regression objective uses randomly sampled inputs; the text states that as few as n samples suffice when the operator rank is n.Source: §B.1 · pp. 16–17
  • The whole-spectrum procedure is not practical for controlling large models during training because the matrix of right singular vectors can be very large.The passage notes that using only top singular values and vectors may reduce cost, but does not make the presented whole-spectrum method practical for large-model training.Source: §B.1 · p. 17
  • The fitting objective may not reach zero when the requested spectrum cannot be represented by the operator class.For a 1 × 1 convolution, the transformation has equal singular values, so a requested spectrum that is not full-rank or does not have equal singular values cannot be attained exactly.Source: §B.1 · p. 17

B.2 Clipping Batch Norm

The section considers batch normalization’s effect on robustness and describes clipping its spectral norm by changing scale parameters. It presents clipping the convolution–batch-normalization composition as an alternative for retaining batch normalization’s training benefits.

B.2 Clipping Batch Norm

  • Leaving batch-normalization spectral norms uncontrolled can forfeit benefits of clipping convolutional layers, while removing batch normalization boosts adversarial robustness but harms test performance and optimization.The text notes that optimization may be completely hindered when batch normalization is removed from more complex models such as DLA.Source: §B.2 · p. 17
  • Batch normalization’s spectral norm can be clipped by changing the magnitudes of its γ_i scale parameters.The passage represents the transformation as diagonal, with entries γ_i divided by the square root of the corresponding variance plus ϵ.Source: §B.2 · p. 17
  • The authors propose applying their clipping method to concatenated convolution and batch-normalization layers as an alternative to clipping batch normalization alone.They leave a fuller exploration of this approach’s potential to future work.Source: §B.2 · p. 17

C Experiments

The experiments use ResNet-18 and DLA, with CIFAR-10 and MNIST evaluations. Figure 5 also describes comparisons of convolutional approximations and singular-value extraction runtimes.

C Experiments

  • The experiments use ResNet-18 and DLA, with the same training procedure for both models.ResNet-18 residual-branch outputs are divided by 2; training uses SGD for 200 epochs and decays the learning rate by 0.1 every 40 steps.Source: C Experiments · pp. 17–18
  • Figure 5a compares absolute spectral-norm differences between convolutional layers and circulant approximations across padding types, kernel sizes, and channel counts.Values are averaged over 100 normally drawn convolutional filters per setting.Source: Figure 5 · p. 18
  • Figure 5b compares PowerQR (algorithm 1) runtime with the pipeline used by Virmaux & Scaman (2018) for computing top-k singular values on a 32 × 32 image.The convolutional layer uses 3×3 filters and 32 input/output channels.Source: Figure 5 · p. 18

C.1 Error in Circulant Approximation

Prior circulant-based methods have restricted scope or incur high cost, while circulant approximation can produce large spectral-norm errors on standard convolutions.

C.1 Error in Circulant Approximation

  • Sedghi et al. (2018) compute convolution spectra only with circular padding and no strides; Senderovich et al. (2022) extend this to strides but retain circular padding.The paper reports that these methods are slow and memory-consuming for large models.Source: §C.1 · p. 18
  • Delattre et al. (2023) use Gram iteration for a fast-converging upper bound on stride-1 convolutions with circular padding, but are slower for clipping and less accurate.The comparison is reported in Figure 3.Source: §C.1 · p. 18
  • Circulant approximation errors can be large for random convolutions, especially as channel count or kernel size increases.The absolute difference from the true spectral norm is averaged over 100 trials per setting across standard padding types and filter sizes.Source: §C.1 · p. 18
  • The paper’s method computes the exact spectrum of any implicitly linear layer, including different convolution types.Source: §C.1 · p. 18

C.2 Extracting Multiple Singular Values

The paper compares PowerQR-based implicit subspace iteration with successive power-method runs for extracting a top-k eigenspace.

C.2 Extracting Multiple Singular Values

  • Implicit subspace iteration is dramatically more efficient than k successive power-method runs in the reported runtime comparison.PowerQR uses 100 steps; the comparison omits the deflation step required by the power-method proposal, which would make that method slower still.Source: §C.2 · p. 18
  • The runtime comparison uses PowerQR with 100 steps against k successive power-method runs, as suggested by Virmaux & Scaman (2018).Source: §C.2 · p. 18
  • The comparison excludes deflation, which is required for the proposed successive power-method approach to work.Source: §C.2 · p. 18
Loading 2402.16017v2…