Fantastic Four: Differentiable and Efficient Bounds on Singular Values of Convolution Layers
Authors: Sahil Singla
Soheil Feizi
Venue: ICLR 2021 Poster (2021)
Keywords: spectral regularization
spectral normalization

Abstract: In deep neural networks, the spectral norm of the Jacobian of a layer bounds the factor by which the norm of a signal changes during forward/backward propagation. Spectral norm regularizations have been shown to improve generalization, robustness and optimization of deep learning methods. Existing methods to compute the spectral norm of convolution layers either rely on heuristics that are efficient in computation but lack guarantees or are theoretically-sound but computationally expensive. In this work, we obtain the best of both worlds by deriving {\it four} provable upper bounds on the spectral norm of a standard 2D multi-channel convolution layer. These bounds are differentiable and can be computed efficiently during training with negligible overhead. One of these bounds is in fact the popular heuristic method of Miyato et al. (multiplied by a constant factor depending on filter sizes). Each of these four bounds can achieve the tightest gap depending on convolution filters. Thus, we propose to use the minimum of these four bounds as a tight, differentiable and efficient upper bound on the spectral norm of convolution layers. Moreover, our spectral bound is an effective regularizer and can be used to bound either the lipschitz constant or curvature values (eigenvalues of the Hessian) of neural networks. Through experiments on MNIST and CIFAR-10, we demonstrate the effectiveness of our spectral bound in improving generalization and robustness of deep networks.

Published as a conference paper at ICLR 2021
FANTASTIC FOUR: DIFFERENTIABLE BOUNDS ON SINGULAR VALUES OF CONVOLUTION LAYERS
Sahil Singla & Soheil Feizi Department of Computer Science University of Maryland College Park, MD 20740, USA (ssingla, afeiii z ) umd. edu
ABSTRACT
In deep neural networks, the spectral norm of the Jacobian of layer bounds the factor by which the norm of signal changes during forward/backwart propagation. Spectral norm regularizations have been shown to improve generalization, robust- ness and optimization of deep learning methods. Existing methods to compute the spectral norm convolution layers either rely on heuristics that are efficient computation but lack guarantees expensive. In this work, we obtain the best of both worlds by deriving,for four provable upper bounds the spectral norm of standard 2D multi-channel convolution layer. These bounds are differentiable and can be computed efficiently during training with negligible overhead. One of these bounds is in fact the popular heuris- tic method of Miyato et al. (2018) (multiplied by constant factor depending on filter sizes). Each of these four bounds can achieve the tightest gap depending on convolution filters. Thus, we propose to use the minimum of these four bounds as a tight, differentiable and efficient upper bound on the spectral norm of convolution layers. We show that our spectral bound is an effective regularizer and can be used to bound either the lipschitz constant or curvature values (eigenvalues of the Hessian) of neural networks. Through experiments MNIST and CIFAR-10, we demonstrate the effectiveness of our spectral bound in improving generalization and provable robustness of deep networks.
mheoretically-sune but computationally
INTRODUCTION
Bounding singular values of different layers of a neural network is way control the complexity of the model and has been used in different problems including robustness, generalization, optimization, generative modeling, etc. In particular, the spectral norm (the maximum singular value) of layer bounds the factor by which the norm of the signal increases or decreases during both forward and backward propagation within that layer. If all singular values are all close one, then the gradients neither explode nor vanish (Hochreiter 1991 Hochreiter et al., |000] Klambauer et al.) 2017: Xiao al. 2018). Spectral norm regularizations/bounbe have been used in improving the generalization (Bartlett et al. 2017: Long & Sedghi 2020). in training deep generative models (Arjovsky et al.
2017 10017/allrajam et 2017: Tolstikhin al. 2018 Miyato et al. 2018 Hoogeboom et al.) 2020) and
in robustifyinggggg models against ad adersaaial attacks (Singla & Feizi |020 Szegedy et al. 20144] Peck
cet al. 2017 Zhang et al., 2018 Anil et al. 2018: Hein & Andriushchenko 2017 [Csse et al. 2017).
These applications have resulted in multiple works to regularize neural networks by penalizing the
spectral norm of the network layers (Drucker & Le Cun 1992; Yoshida & Miyato 2017
Miyato
al.
2018 2017 Sedghi al. 2019: Singla & Feizi 2020).
For a fully connected layer with weights W and bias b. the lipschitz constant is given by the spectral norm of the weight matrix i.e. [ which can be computed efficiently using the power iteration method (Golub & Van Loan 1996). In particular, if the matrix W of size p x the computational complexity of power iteration (assuming convergence in constant number of steps) is Opg)).
Convolution layers (Lecun et al. 1998 are one of the key components of modern neural networks, particularly in computer vision Krizhevsky al. 2012). Consider convolution filter L of size

---

Published as a conference paper at ICLR 2021
Cout Cin x h x where Cout, Cans h and denote the number of output channels, input channels, height and width of the filter respectively; and a square input sample of size Cin x 12 x n where n is its height and width. A naive representation of the Jacobian of this layer will result in a matrix of size n²Cout x n Cin- n For a typical convolution layer with the filter size 64 x 3 x 7 x 7 and an ImageNet sized input x 224 x 224 (Krizhevsky et al.. 2012), the corresponding jacobian matrix has very large size: 802816 x 150528. This makes an explicit computation of the jacobian infeasible. Ryu ct al.] (2019) provide a way to compute the spectral norm of convolution layers using convolution and transposed convolution operations in power iteration, thereby avoiding this explicit computation. This leads to an improved running time especially when the number of input/output channels small (Table I
n² Cout
However, addition to the running time, there is an additional difficulty in the approach proposed in Ryu et al. (2199) (and other existing approaches described later) regarding the computation of the spectral norm gradient (often used as a regularization during the training). The gradient of the largest singular value with respect to the jacobian can be naively computed by taking the outer product of corresponding singular vectors. However, due to the special structure of the convolution operation, the jacobian will be sparse matrix with repeated elements (see Appendix Section D for details). The naive computation of the gradient will result in non-zero gradient values at elements that should be in fact zeros throughout training and also will assign different gradient values at elements that should always be identical. These issues make the gradient computation of the spectral norm with respect to the convolution filter weights using the technique of Ryu et al. (2019) difficult.
Recently, Sedghi et al. (2019) provided a principled approach for exactly computing the singular values of convolution layers. They construct n²² matrices each of size Cout Cin by taking the Fourier transform of the convolution filter (details in Appendix Section
B The set of singular values of the jacobian equals the union of singular values of these n² matrices. However, this method can have high computational complexity since it requires SVD of n² matrices. Although this method can be adapted to compute the spectral norm of n² matrices using power iteration (in parallel with a GPU implementation) instead of full SVD, the intrinsic computational complexity (discussed in Table can make it difficult to use this approach for very deep networks and large input sizes especially when computational resources are limited. Moreover, computing the gradient of the spectral norm using this method is not straightforward since each of these n² matrices contain complex numbers. Thus, Sedghi et al. (2019) suggests to clip the singular values if they are above certain threshold to bound the spectral norm of the layer. In order to reduce the training overhead, they clip the singular values only after every 100 iterations. The resulting method reduces the training overhead but is still costly for large input sizes and very deep networks. We report the running time of this method in Table and its training time for one epoch (using GPU implementation) Table 4c
Because of the aforementioned issues, efficient methods to control the spectral norm of convolution layers have resorted to heuristics (Yoshida & Miyato, 2017 Miyato et al. 2018 Gouk et al. 2018). Typically, these methods reshape the convolution filter of dimensions Cout x Can x h x w to construct a matrix of dimensions Cout x hwC,,, and use the spectral norm of this matrix as an estimate of the spectral norm of the convolution layer. To regularize during training, they use the outer product of the corresponding singular vectors as the gradient of the largest singular value with respect to the reshaped matrix. Since the weights do not change significantly during each training step, they use only one iteration of power method during each step to update the singular values and vectors (using the singular vectors computed in the previous step). These methods result in negligible overhead during the training. However, due to lack of theoretical justifications (which we resolve in this work), they not guaranteed to work for all different shapes and weights of the convolution filter. Previous studies have observed under estimation of the spectral norm using these heuristics (Jiang et al.) 2019).
On one hand, there are computationally efficient but heuristic ways of computing and bounding the spectral norm of convolutional layers (Miyato et al., 2017 2018). On the other hand, the exact computation of the spectral norm of convolutional layers proposed by [edghh et al. (2019); Ryu et al. (2019) can be expensive for commonly used architectures especially with large inputs such as ImageNet samples. Moreover, the difficulty in computing the gradient of the spectral norm with respect to the jacobian under these methods make their use as regularization during the training process challenging.
In this paper, we resolve these issues by deriving a differentiable and efficient upper bound on the spectral norm of convolutional layers. Our bound provable and not based on heuristics. Our
2

---

Published as a conference paper at ICLR 2021
Spectral norm bounds
Running time (secs)
Exact (Sedghi Ryu)
Filter shape
Vhe x
Bound (Ours)
Sed- ghi
Ours
Ryu
R 2
||/2
T2 28.89
|
64 x 3 7
47.29
46.37
77.31
28.89
15.92
0.004
0.94
0.03
64 x 64 3
9.54
9.61
9.33
10.51
9.33
6.01
0.033
8.46
0.04
64 x 64
6.57
6.30
6.49
7.86
6.30
5.34
0.033
9.19
0.04
64 64 3
8.92
8.71
8,80
10.97
8.71
7.00
0.033
9.16
0.04
64 64 x
5.40
5.52
5.81
6.30
5.40
3.82
0.033
9.25
0.03
128 x 64 x 3
6.99
6.92
6.01
9.12
6.01
4.71
0.033
3.08
0.05
128 128 3 3
7.45
7.38
7.21
8.51
7.21
5.72
0.033
8.98
0.08
128 x 128 x 3
6.78
7.18
6.85
8.78
6.78
4.41
0.032
9.02
0.08
128 128 3 x
7.57
7.72
8.89
7.87
7.57
4.88
0.033
9.00
0.08
256 128 3 3
8.58
8.45
8.67
8.77
8.45
7.39
0.032
3.92
0.14
256 x 256 3 x
8.19
8.07
8.04
8.99
8.04
6.58
0.033
13.1
0.26
256 256 3 x 3
8.06
8.13
7.57
9.26
7.57
6.36
0.034
11.2
0.26
256 256 3 x 3
9.91
9.76
10.97
9.17
9.17
7.68
0.033
11.2
0.26
512 x 256 3 3
11.24
11.00
11,50
11.07
11.00
9.99
0.034
5.26
0.51
512 512
10.98
10.65
11.91
10.45
10.45
9.09
0.033
15.7
1.04
512 x 512 x 3
20.22
19.90
21.91
18.37
18.37
17.60
0.033
15.7
1.04
512 512 3
7.83
7.99
8.26
7.60
7.60
7.48
0.034
15,8
1.04
Table 1: Comparison between the exact spectral norm of the jacobian of convolution layers (computed using Sedghi et al.] (2019); et al. (2019)) and our proposed bound for the a Resnet-18 18 network pre-trained on ImageNet. Our bound within 1.5 times the exact spectral norm (except the first layer) while being significantly faster to compute compared to the exact methods. All running times were computed on GPU using tensorflow. For Sedghi al. 2219)'s 's method, to have a fair comparison, we only compute the largest singular value (and not all singular values) for all individual matrices in parallel using power iteration (on GPU) and take the maximum. We observe that for different filters, different components of our bound give the minimum value. Also, the values of the four bounds can be very different for different convolution filters (example: filter in the first layer).
computational complexity is similar to that of heuristics (Miyato et al. 2017 2018) allowing our bound to be used as a regularizer for efficiently training deep convolutional networks. In this way, our proposed approach combines the benefits of the speed of the heuristics and the theoretical rigor of Sedghi et al. (2019). Table 2 summarizes the differences between previous works and our approach. In Table
empirically observe that our bound can be computed in time significantly faster than Sedghi et al. (2019); Ryu et al./ (2019). while providing a guaranteed upper bound on the spectral norm. Moreover, we empirically observe that upper bound and the exact value are close each other (Section 3.1
Below, we briefly explain our main result. Consider convolution filter L of dimensions Cout X Gin x w and input of size Cin. x n x n. The corresponding jacobian matrix is of size n Cout X n Cin- We show that the largest singular value of the jacobian (i.e. [J]]2) is bounded as:
J|[ s hew min ([R |SI.SSL
T|2, 1U12)
where R. S, T and U are matrices of sizes hCout WCin. WCCut x JaCin Cout x hwC;; and hawCout X Cin respectively, and can be computed by appropriately reshaping the filter (details in Section 3) This upper bound is independent of the input width and height (n)). Formal results are stated in Theorem ] and proved in the appendix. Remarkably, [ 2 is the heuristic suggested by Miyato et al. 2018)) To the best of our knowledge, this is the first work that derives provable bound norm of convolution filter as a constant factor (dependant on filter sizes, but not filter weights) times the heuristic of Miyato et al. (2018). In Tables 1 and 3
the spectral
we show that the other 3 bounds (using
3

---

Published as a conference paper at ICLR 2021
| 21) can be significantly smaller than v hw 2 for different convolution filters. Thus, we take the minimum these 4 quantities to bound the spectral norm a convolution filter.
In Section show that bound can be used to improve the generalization and robustness properties of neural networks. Specifically, we show that using our bound as a regularizer during training.
achieve improvement in accuracy on par with exact method (Sedghi et al.) 2019) while being significantly faster to train (Table 4). We also achieve significantly higher robustness certificates against adversarial attacks than CNN-Cert (Boopathy et al. 2018) single layer CNN (Table These results demonstrate potentials for practical uses of our results. Code is available at the github repository: https//gtthb..com/iigaaaallll// 4/fantstiiot
Exact Sedghi al.
Exact Ryu et al. 2019)
Upper Bound (Ours)
2019
Norm of n²
Norm of four matrices, each of size: Cout
Norm of one matrix of size: n Con
Computation
matrices, each of size: CoutCin
Time complexity (O)
n² Cout Cin
n² h w Cout Cin
h W Cout Cin
Guaranteed bound
Easy gradient
X
computation
Table 2: Comparison of various methods used for computing the norm of convolution layers. n is the height and width for square input, Cjn is the number of input channels, Coua is the number of output channels, /t and w are the height and width of the convolution filter. For Sedghi et al. (2019), we only compute the largest singular value using power iteration (i.e all singular values).
2 NOTATION
For vector we use Vj to denote the element in the jth position of the vector. We use Aj, and A., to denote the jth row and k column of the matrix A respectively. We assume both Aj A to be column vectors (thus Aj is the transpose of jth row of A). Aj.k denotes the element in jth row and th column of A. The same rules can be directly extended to higher order tensors. For matrix A (रĄжर and tensor e RP*Ą*r, vee( (A denotes the vector constructed by stacking the rows of A and vec(B) denotes the vector constructed by stacking the vectors vec(B, B,:;,, j [p- 1]:
vec( A T [A
1
vec (B) =[B B B B[-
We use the following notation for a convolutional neural network. L. denotes the number of layers and is the activation function. For an input x, we use z(" R and (x)) R, to denote the raw (before applying σ) and activated (after applying Φ) neurons the 1 hidden layer respectively. (0) denotes the input image To simplify notation and when no confusion arises, make the dependency of (!) and a to x implicit. o' (z()) and Φ (z) denotes the elementwise first and second derivatives of Φ at z W() denotes the weights for the 7th layer i.e W()) will be a tensor for a convolution layer and matrix for fully connected layer. J(!) denotes the jacobian matrix of vee(z (1) with respect to the input x. 0 denotes the neural network parameters. fel (x) denotes the softmax probabilities output by the network for an input For an input x and label y, the cross entropy loss is denoted by (x).
MAIN RESULTS
Consider a convolution filter L of size Cout x Cin x h w applied to an input X of size Cin x n n. The filter L takes an input patch of size Cin h from the input and outputs vector of size Cout for every such patch. The same operation is applied across all such patches in the image. To apply convolution at the edges of the image, modern convolution layers either not compute the outputs
4

---

Published as a conference paper at ICLR 2021
thus reducing the size of the generated feature map, or pad the imput with zeros preserve its size. When we pad the image with zeroes, the corresponding jacobian becomes a toeplitz matrix. Another version of convolution treats the imput if it were torus; when the convolution operation calls for a pixel off the right end of the image, the layer "wraps around" to take it from the left edge, and similarly for the other edges. For this version of convolution, the jacobian is circulant matrix. The quality of approximations between toeplitz and circulant colvolutions has been analyzed in the case of ID Gray 2005) and 2D signals (Zhu & Wakin 2017). For the 2D case (similar the ID case), O(1/P) bound is obtained on the error, where p p is the size of both (topelitz and circulant) matrices. Consequently, theoretical analysis of convolutions that wrap around the input (i.e using circulant matrices) has been become standard. This is the case that we analyze in this work. Furthermore, we assume that the stride size to be in both horizontal and vertical directions.
The output Y produced from applying the filter L to an input X is of size Cout X 12 n. The corresponding jacobian (J) will be matrix of size n² n²Coutt x n Cin satisfying:
vec( Y) = Jvec(X).
Our goal is to bound the norm of jacobian of the convolution operation i.. |J Sedghi al. (2019) also derive an expression for the exact singular values of the jacobian of convolution layers. However, their method requires the computation of the spectral norm of n² matrices (each matrix of size Cout x Cin) ) for every convolution layer. We extend their result to derive a differentiable and easy-to-compute upper bound singular values stated in the following theorem:
Theorem 1. Consider a convolution filter L of size Cout x Cin. h w that applied to input X of size Gi x x gives output Y of size Cout n. The jacobian Y with respect X (i.e. J) will be matrix of size n Cout x n² Cin- The spectral norm of J is bounded by:
|] S Vhw min ( (1R12. ||
1112)
where the matrices R, S, S.T and U are defined as follows:
L,,0,0
L,,00,1
... L,:00.-1 L,,1,-11
L,,000
L,,100
L.
L,,10
L,111
L,,0,11
L
1,,1-111
R=
S
1,,0 1,0
L,gh-111
Ligh-1,1011
L,,00-11
L
T= = [Ao
A
An-i], where A
[1,,,00
L,d,1
Ladda-1]]
U
B
BT
B where B
[
L
LT 10
Proof of Theorem is in Appendix E. The matrices R,S,T T and U are of dimensions Couth h Wn Caur' W x Cinht Cout x cinhw and Couthww x Cin respectively. In the current literature (Miyato) lt al. 2018), the heuristic used for estimating the spectral norm involves combining the dimensions of sizes h, h,W, Cin in the filter L to create the matrix of dimensions Cout x hhoc The norm of resulting matrix is used as heuristic estimate of the spectral norm of the jacobian of convolution operator. However, in Theorem I
we show that the norm of this matrix multiplied with a factor of
Vhw gives provable upper bound on the singular values of the jacobian. In Tables and 3 we show that for different convolution filters, there can significant differences between the four bounds and any of these four bounds can be the minimum.
3.1 TIGHTNESS ANALYSIS
In Appendix we show that the bound is exact for a convolution filter with h w = 1:
Lemma 1. For h w 1, the bounds in Theorem 7 are exact i.e:
JJ]2 2
R = |S| [| = |U|
In Table 3] we analyze the tightness between our bound and the exact largest singular value computed by Sedghi et al. (2119) for different filter shapes. Each convolution filter was constructed by sampling from a standard normal distribution (0, 1). We observe that the bound is tight for small filter sizes but the ratio (Bound/Exact) becomes large for large h and w. We also observe that the values computed by the four bounds can be significantly different and that we can get a significantly improved bound by taking the minimum of the four quantities. In Appendix Section G Figure [ empirically observe that the gap between our upper bound and the exact value can become very small by adding our bound regularizer during training.
5

---

Published as a conference paper at ICLR 2021
V/w
Bound
Exact
Bound/
Filter shape
|R| 2
|
[T] 2
|U|
(Ours)
(Sedghi)
Exact
64 x 64 x x 2
44.19
46.11
46.76
47.88
44.19
31.96
1.38
64 x 64 x 3
84.03
82.71
95.27
97.36
82.71
48.77
1.70
64 64 x x
179.09
177.31
237.22
238.30
177.31
82.39
2.15
64 x 64 x x
297.02
296.18
444.69
451.52
296.18
116.05
2.55
64 16 x
32.27
32,45
31.18
38.20
31.18
23.25
1.34
64 x 16 x x
60.74
62.42
59.67
82.17
59.67
37.09
1.61
64 x 16 x 5
130.07
132.62
136.16
216.22
130.07
61.01
2.13
64 x6x7xx 220.25
220.20
248.50
415.14
220.20
86.54
2.54
Table 3: Tightness analysis between our proposed bound and exact method by Sedghi et al.
(2019
3.2 GRADIENT COMPUTATION
Since the matrix R can be directly computed by reshaping the filter weights L (equation 8) we can compute the derivative of our bound Vhw R (or ||||2, |2, [2) with respect filter weights
by first computing the derivative of //w R lz with respect to R. and then appropriately reshaping the obtained derivative.
Let u and v be the singular vectors corresponding to the largest singular value, i... |R/2. Then, the derivative of our upper bound Vhw R|2 with respect to R can be computed as follows:
V VRVhW R v hw uv" where |R||2 = u Rv.
Moreover, since the weights do not change significantly during the training, of power method to update u, v and |R| during each training step (similar to Miyato et al. (2018) )017). This allows us
iteration
bound efficiently regularizer during the training process.
EXPERIMENTS
All experiments were conducted using single NVIDIA GeForce RTX 2080 Ti GPU.
4.1 COMPARISON WITH EXISTING METHODS
In Table T we show a comparison between the exact spectral norms (computed using Sedghi et al. 2019), Ryu et al. 2019 and our upper bound, i.e. vhw min( R [S],, 2| 2 on a pre- trained R8 network (He et al. 2015). Except for the first layer, observe that our bound is within 1.5 times the value of the exact spectral norm while being significantly faster to compute.
Similar results can be observed in Table for a standard gaussian filter. Thus, by taking the minimum of the four bounds, we can get a significant gain.
4.2 EFFECTS ON GENERALIZATION
In Table we study the effect of using our proposed bound as a training regularizer on generalization error. We use a Resnet-32 neural network architecture and the CIFAR-10 dataset (Krizhevsky/ (2009) for training. For regularization, we use the sum of spectral norms of all layers of the network during training. Thus, our regularized objective function is given as follows
min E(x,v) [f([(x). 3 ())
where / is the regularization coefficient, (x; y) 's are the input-label pairs in the training data, (!) denotes the bound for the 7th convolution or fully connected layer. For the convolution layers, (1)
not use the sum log of spectral norm values since that would make the filter-size dependant factor of ho irreevant for gradient computation.

---

Published as a conference paper at ICLR 2021
is computed as v Vhw min( [R|[2, |S [T] U12) using Theorem
For fully connected layers,
we can compute (1) using power iteration
MMyato et al. 2018
Test Accuracy
Test Accuracy
No
weight decay= =
weight decay
Clipping threshold
No weight decay
weight decay 10
10-4
91.26%
92.53%
None
91.26%
92.53%
0.0008
91.62%
92.37%
0.1
90.67%
91.87%
0.0009
91.74%
92.95%
0.5
92.31%
93.30%
0.0010
91.79%
93.13%
1.0
91.92%
92.86%
0.0011
91.87%
92.75%
0.0012
91.81%
92.53%
(b) Singular value clipping (Sedghi al.
2019
0.0013
92.17%
92.73%
Method
Running time (s)
Increase
(%)
0.0014
92.23%
92.61% %
0.0015
91.87%
93.15%
Standard
49.58
0.0016
91.92%
93.26 %
Ours
54.39
9.7%
0.0017
91.70%
92.92%
Clipping 156.46
0.0018
91.52%
91.89%
(Sedghi
215.6%
ct al. 2019)
0.0019
92.00%
92.47%
0.0020
91.82%
92.56%
(c) Running time epoch on a dataset with 10,000 images size 224x224x3
(a) Our proposed regularizer
Table 4: Comparison between our proposed regularizer (a) and singular value clipping by Sedghi et al. (2019) (b) on test accuracy. Results are CIFAR-10 dataset using Resnet-32 network.
Since weight decay (Krogh & Hertz 1991 indirectly minimizes the Frobenius norm squared which is equal to the sum of squares of singular values, it implicitly forces the largest singular values for each layer (i.e the spectral norm) to be small. Therefore, to measure the effect of our regularizer on the test set accuracy, we compare the effect of adding our regularizer both with and without weight decay. The weight decay coefficient was selected using grid search using 20 values between [0, 2 10-3] using a held-out validation set of 5000 samples.
Our experimental results are reported Table 4a
For the case of no weight decay, we observe an improvement of 0.97% over the case when 0. When we include weight decay of 10-4 in training, there is an improvement of 0.73% over the baseline. Using the method of Sedghi et al. (2019) (i.e. clipping the singular values above 0.5 and results in gain of 0.77% (with weight decay) and 1.05% (without weight decay) which is similar to the results mentioned in their paper. In addition obtaining on par performance gains with the exact method of Sedghi al. (2099). key advantage of our approach is its very efficient rumning time allowing its use for very large input sizes and deep networks. We report the training time of these methods Table for dataset with large input sizes. The increase in the training time using our method compared to the standard training is just 9.7% while that for (edghi et al. (2019) around 215.6%.
4.3 EFFECTS ON PROVABLE ADVERSARIAL ROBUSTNESS
In this part, we show the usefulness of our spectral bound in enhancing provable robustness of convolutional classifiers against adversarial attacks (Szegedy et al. 2014). robustness certificate lower bound on the minimum distance of given input to the decision boundary of the classifier. For any perturbation of the input with a magnitude smaller than the robustness certificate value, the classification output will provably remain the same. However, computing exact robustness certificates requires solving non-convex optimization, making the computation difficult for deep classifiers. In the last couple of years. several certifiable defenses against adversarial attacks have been proposed
(e.g. Boopathy et al. (2018); Mirman et al. (2018); Zhang et al. (2018); 8); Weng et al. (2018): Singla
& Feizi (2020): Virmaux & Scaman 2008 Tsuzuuu al. 2018); Levine & Feizi (2020): Cohen
7

---

Published as a conference paper at ICLR 2021
et al. (2019; Levine & Feizi (2020).) In particular, to show the usefulness of our spectral bound in this application, we examine the method proposed in Singla & Feizi (2020) that uses a bound on the lipschitz constant of network gradients (i.e. the curvature values of the network). Their robustness certification method in fact depends on the spectral norm of the Jacobian of different network layers; making perfect case study for the of our spectral bound (details in Appendix Section (C)
Due to the difficulty of computing [J(1|2 when the I layer is convolution, Singla & Feizi (2020) restrict their analysis to fully connected networks where J( simply equals the 7 layer weight matrix. However, using our results in Theorem [1 we can further bound J(1) and similar experiments for the convolution layers. Thus, for 2 layer convolution network, our regularized objective function is given follows:
E(xw)) ( (fo(x.. + max (w v. - (vl))
min #
where y is the regularization coefficient, b is bound on the second-derivative of the activation function ((o (-)1 s 6), (x, y)'s are the imput-label pairs in the training data, and ( denotes the bound on the spectral norm for the 1th linear (convolution/fully connected) layer. For the convolutional layer, (2) is again computed as Vhwmmin( 2, [ |T] [[]) using Theorem
In Table 5 we study the effect of the regularization coefficient 7y on provable robustness when the network trained with curvature regularization (Singla & Feizi] (020). We use 2 layer convolutional neural network with the tanh (Dugas et al. (2000) activation function and filters in the convolution layer. We observe that the method in Singla & Feizi (2020) coupled with our bound gives significantly higher robustness certificate than CNN-Cert, the previous state of art (Boopathy et al. 2018).
In Appendix Table 7 we study the effect of the adversarial training method in Siinlaa & Feizi (2020) coupled with our bound on certified robust accuracy. We achieve certified accuracy of 91. 91.25% on MNIST dataset and 29. 19.26% on CIFAR-I0 10 dataset. These results further highlight the usefulness of our spectral bound on convolution layers improving the provable robustness the networks against adversarial attacks.
MNIST
Certified Robust Accuracy
Certificate Improvement (Percentage %)
Standard Accuracy
CRT Our bound
CNN-Cert
98.35%
0.0%
0.1503
0.1770
17.76%
0.01
94.85%
75.26%
0.2135
0.8427
294.70%
0.02
93.18%
74.42%
0.2378
0.9048
280.49%
0.03
91.97%
72.89%
0.2547
0.9162
259.71%
Table 5: Comparison between robustness certificates computed using CNN-Cert (Boopathy et al. 2018) and the method proposed (Singla & Feizi (2020) coupled with our spectral bound, for different values of for single hidden layer convolutional neural network with tanh activation function. Certified Robust Accuracy is computed as the fraction correctly classified samples with robustness-certtffcat (computed using (Singla & Feizi (0200) greater than 0.5.
CONCLUSION
In this paper, we derive four efficient and differentiable bounds on the spectral norm of convolution layer and take their minimum as our single tight spectral bound. This bound significantly improves over the popular heuristic method of MMyato et al. (2017) 2018), for which we provide the first provable guarantee. Compared to the exact methods of Sedghi et al. (2019) and Ryu et al.) (001)). our bound is significantly more efficient to compute, making it amendable to be used in large-scale problems. Over various filter sizes, we empirically observe that the gap between our bound and the true spectral norm is small. Using experiments MNIST and CIFAR-10. 10, demonstrate the usefulness our spectral bound in enhancing generalization as well as provable adversarial robustness of convolutional classifiers.
8

---

Published as a conference paper at ICLR 2021
6 ACKNOWLEDGEMENTS
This project was supported in part by NSF CAREER AWARD 1942230, HR001 19900226 HR001 12090132, NIST 60NANB20D134 and Simons Fellowship on "Foundations of Deep Learn- ing."
REFERENCES
Cem Anil, James Lucas, and Roger B. Grosse. Sorting out lipschitz function approximation. In ICML, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-223, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6241 62500, USA, 2017. Curran Associates Inc. ISBN 978-1- 5108-6096-4.
Akhilan Boopathy, Tsui Wei Weng, Pin-Ye Yu Chen, Sijia Liu, and Luea Daniel. Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks, 2018. 8.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp.
JMLR.org. 2017.
Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. ICML, 2019.
H. Drucker and Y. Le Cun. Improving generalization performance using double backpropagation. Trans. Neur. Netw., 3(6):991 997, November 1992. ISSN 1045-9227. doi: 10. 10.1109772.165600.
Charles Dugas, Yoshua Bengio, François Bélisle, Claude Nadeau, and René Garcia, Incorporating second-order functional knowledge for better option pricing. Proceedings of the 13th Interna- tional Conference Neural Information Processing Systems, NIPS'00, pp. 451-457, Cambridge, MA, USA, 2000. MIT Press.
Gene H. Golub and Charles F. Van Loan. Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA, 1996. ISBN 0-8018-5414-8.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity, 2018
Robert M. Gray. Toeplitz and circulant matrices: A review. Commun. Inf. Theory, 2(3):155-233) August 2005. ISSN 1567-2190. doi: 10. 10.156/00100000006
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. I. Guyon, U. V. Luxburg, S. Bengio, Wallach, R. Fergus. S. Vishwanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2015.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against adversarial manipulation. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan. and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 2266-2276. 2017.

---

Published as a conference paper at ICLR 2021
S. Hochreiter, Y. Bengio, P. Frasconi, and J. Schmidhuber. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies. S. C. Kremer and J. F. Kolen (eds.), Field Guide Dynamical Recurrent Neural Networks. IEEE Press, 2001.
Sepp Hochreiter. Untersuchungen zu dynamischen neuronalen netzen. 1991.
Emiel Hoogeboom, Victor Garcia Satorras, Jakub M. Tomc7ak, and Max Welling. The convolution exponential and generalized sylvester flows. In Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Haoming Jiang, Zhehui Chen, Minshuo Chen, Feng Liu, Dingding Wang, and Tuo Zhao. On computation and generalization of generative adversarial networks under spectrum control. In International Conference on Learning Representations, 2019.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Anders Krogh and John A. Hertz, A simple weight decay can improve generalization. In NIPS, 1991.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2324 1998. doi: 10.1/09/..76691.
Alexander Levine and Soheil Feizi. (de)randomized smoothing for certifiable defense against patch attacks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 6465 6465-6675.. 6475. Curran As- sociates, Inc., 2020. URL URL/ectpps:///roceeddin neurips wtt.ii...cccpppeee wc/ppape://222/ELLLLL 1rcee08855200222acccc33333333333 Paper..cappppp.......
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations, 2020.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In ICML, 2018
Takeru Miyato, Shin ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: A regularization method for supervised and cemi-supervised learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 41:1979-1999 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 201 8.
Jonathan Peck, Joris Roels, Bart Goossens, and Yvan Sacys. Lower bounds on the robustness to adversarial perturbations. In NIPS, 2017.
Ernest Ryu, Jialin Liu, Sicheng Wang, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Plug- and-play methods provably converge with properly trained denoisers. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Proceedings of Machine Learning Research, pp. 5546-5557, Long Beach,
Learning, volume California, USA, 09-15 Jun 2019. PMLR.
Hanie Sedghi, Vineet Gupta, and Philip M. Long. The singular values of convolutional layers. In International Conference Learning Representations, 2019.
10

---

Published as a conference paper at ICLR 2021
Sahil Singla and Soheil Feizi. Second-order provable defenses against adversarial attacks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8981-8991. PMLR, 13-18 Jul 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
llya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto-encoders. In International Conference on Learning Representations, 2018.
Yusuke Tsuzuku, I. Sato, and Masashi Sugiyama. Lipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks. NeurIPS, 2018.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, and Inderjit S. Dhillon ANDLuca Daniel. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning (ICML). july 2018.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of CNNs: How train 10,000-layer vanilla con- volutional neural networks. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 5393-5402, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning, ArXiv, abs/ 705./100.11000 10941, 2017.
Huan Zhang, Teu Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. S. Bengio, H. Wallach, H. Larochelle, and R. Garnett (eds.), Advances in Neural Information Processing
K. Grauman, N. Systems 31, pp. 1939-4948 Curran Associates, Inc., 2018
Z. Zhu and M. B. Wakin. On the asymptotic equivalence of circulant and toeplitz matrices. IEEE Trans- actions on Information Theory, 63(5):2975-2999 May 2017. doi: 10. 10.109//1.22117..66660.0.
Appendix
A NOTATION
For a vector v, we use Vi to denote the element in the tth position the vector. We use Aj, to denote the jth row of the matrix A, A., to denote the hth column of the matrix A. We assume both Aj and A to be column vectors (thus Aj is constructed by taking the transpose of jth row of A). A,, denotes the element in j row and 4tth column of A. Ajak and Agj, denote the vectors containing the first 1 elements of the jth row and first j elements of heth column, respectively. A.j.k denotes the matrix containing the first j rows and columns of A:
A A
A
Ao,k
Ag,0
Ao,1
A0,k-1
A1,k
A
A1,
A1
jock
A.i.A
Agj.k
A j
Aj-1,
Aj--10
Aj-1,1
AJ-LA-1
The same rules can be directly extended to higher order tensors.
For e N, we use [n] to denote the set {0...., n. and [p, q] (p < q) to denote the set {p. p+ 1.... 9). We will index the rows and columns of matrices using elements of [n]. i.c. numbering from 0.
Addition of row and column indices will be done mod unless otherwise indicated. For matrix
11

---

Published as a conference paper at ICLR 2021
A IR and tensor B RPxex,, (e) denotes the vector constructed by stacking the rows of A and vec(B) denotes the vector constructed by stacking the vectors vea B B,.)): j [p- -1]
A
vea (ec(Bu Bu
A1
vec B 11.p)
vec A)
vec(B)=
11
Dec 1,-)
For given vector v RR" circ(v) denotes the circulant matrix constructed from v i.e rows of circ(v) are circular shifts of v. For matrix A RR ciro(A) denotes the n² n² doubly block circulant matrix constructed from A, ie each n block of circ(A) is eirculant matrix constructed from the rows A jos j 1J:
R-1
circ(Ao;) cird(An-l
circ 1n))
circ(v)=
Vn VO
Vn-2
ciro(A)=
circ An-2;)
:
V2 Vu
(1r))11;)))))))))))))))))))))(
ciro(
We use F denote the Fourier matrix of dimensions
i. F F. witk 2-2mf/m , =1 For matrix A, a (A) denotes the set of singular values of A. Tmaz (m) and Tmin (A) denotes the largest and smallest singular values of A respectively. A B denotes the kronecker product of A and B. We use A @ B to denote the hadamard product between two matrices (or vectors) of the same size. We use L, denote the identity matrix of dimensions n2
We use the following notation for a convolutional neural network. L denotes the number of layers and s denotes the activation Φ. For an input x, we use 2 (x) R, and (x) E R to denote the raw (before applying the activation Φ) and activated (after applying the activation functionn neurons in the 1 hidden layer of the network, respectively. Thus (0) denotes the input image x. To simplify notation and when no confusion arises, we make the dependency of 2z)) and a o' (z) and o" (z)) denotes the elementwise derivative and double derivative of Φ at (1)), W(!) denotes the weights for the 1th layer i.e ( will tensor for convolution layer and matrix for fully connected layer. (()) denotes the jacobian matrix of vec(z(") with respect to the input x. 8 denotes the neural network parameters, fe (x) denotes the softmax probabilities output by the network for an input x. For an input x and label y, the cross entropy loss denoted by (fo(x))
x implicit.
B SEDGHI ET AL'S METHOD
Consider an input X RRoxxxxX and convolution filter Moc to X such that max(h, w). Using L, we construct a new filter K RC xnxn by padding with zeroes:
K Keddk.1 Led.k.l k [h - 1]. le [w-1]
otherwise }
The Jacobian matrix J of dimensions Comt x Cinti is given as follows:
(0,00)
B
B (0.
B(000)
B(.I)
-1)
B 1.0 1.0)
B (Cout-1.1)
B (oor (oon--1
where (e.d) is given as follows:
(add) circ(Ko.d:.))
By inspection we can see that:
vec Y) Jvec(X)
From Sedghi et al. 2019), we know that singular values of J are given by:
o(J)=
U
((G())
je[n-1]ke[n-11]
12

---

Published as a conference paper at ICLR 2021
where each ((.)) is matrix of dimensions Cout Cin. and each element of G is given by:
((.b))
(F"Kedd.. (K)dd.FF)jjs
CE [Cout 1], d [ein 1]
The largest singular value of J i.e [|J 2 can be computed as follows:
| 2 m (J)
max
max (G (1.b)
je[n-1].Ae[n-1]
C SECOND-ORDER ROBUSTNESS
C.1 ROBUSTNESS CERTIFICATION
Given an input x (0) e RP and a binary classifier f (here f: fRRD is differentiable everywhere),
goal is to find lower bound to the decision boundary f(x) 0. The primal is given follows:
Peert min max
" 2 x
x (0 nf nf(
The dual of the above optimization is given as follows:
deer max min
x x x0) +
2
The inner minimization can solved exactly when the function 1/2 x 10 nf(xx strictly convex, i.e has positive-definte hessian. The same condition can be written as:
x
( 1 nf(x)
It is easy to verify that if the eigenvalues of the hessian of f ie V are bounded between m and M for all x RD, i.c:
mI V
< MI,
VXERD
The hessian + 7/ > 0 (i.e is positive definite) for -1/M < < We refer an interested reader to (Singla & Feizi (2020) for more details and formal proof of the above theorem. Thus the inner minimization can be solved exactly for these set of values resulting in the following optimization:
Peer
max -1/Msns-1/mm 1/m
min
x
(0) (2f(xx)
Note that Ceert can be solved exactly using convex optimization. Thus, we get the following chain of inequalities:
Loor deert $ Poert
Thus solving Verr gives robustness certificate. The resulting certificate is called Curvature-based Robustness Certificate.
C.2 ADVERSARIAL TRAINING WITH CURVATURE REGULARIZATION
Let K(0, y, t) denote the upper bound on the magnitude of curvature values for label y and target (computed using Singla & Feizi (2020)). The objective function for training with curvature regularization given by:
min
E(x,)) [e (ff(()) v) <K(0.
The objective function for adversarial training with curvature regularization given by:
min [e (x (attack)) ),y) )
(attack) is computed by doing an adversarial attack on the input x either using l2 bounded PGD canvature-based Attack Optinization defined in (iinlla & Feizi (2020). When Curvature- Attack Optimization is used for adversarial attack, the resulting attack is called Curvature-bac
Robust Training (CRT).
13

---

Published as a conference paper at ICLR 2021
D DIFFICULTY OF COMPUTING THE GRADIENT OF CONVOLUTION
Consider a ID convolution filter size given by ([1,2,-1]] applied to an array of size 5. The corresponding jacobian matrix is given by:
-1
0
1
2
-1
0
1
2
-1
0
0
1
-1
0
0
The largest singular value ([J]22) the left singular vector (u) and the right singular vector (v) is given by:
0.55614
-0.63245
0.11457
0.19544
J 2 2.0008
0.62695
0.51167
0.27290
0.51167
00.4589
-0.19544
The gradient [V)[J]2) given as follows:
0.35174
0.10870
-0.28456
-0.28456
0.10870
-0.07246
0.02239
0.05862
0.05862
-0.02239
VJ|J
0.39652
-0.12253
0.32079
0.32079
-0.12253
0.17260
-0.05333
0.13964
0.13964
-0.05334
0.28984
0.08957
-0.23449
-0.23449
0.08957
Clearly the gradient contains non-zero elements in elements of J that are always zero and unequal gradient values at elements of that are always equal.
E PROOF OF THEOREM
Proof. Consider an input X e R and a convolution filter L Reost xhxx to X such that max(h, w). Using L, construct filter K e Ro by padding with zeroes:
Ked,k..1 - Len.k. k e [h 1]. [w-1]
otherwise
The output Y Xnxn of the convolution operation is given by:
Gin-1 n-
Y Yo,r,e ΣΣΣ d-0
X Xdrttk K.rkk.n Ked,il
R-O 2-0
construct matrix dimensions Courh Cinti as follows:
(0,0)
(
B -0
B(00)
B(.I)
-1,
B ( 1.0)
B (Cou
where (e.dd) is given as follows:
((edd) circ(K
By inspection we can see that:
vec Y) -vve
This directly implies that J is the jacobian of vec( Y) with respect vec(X) and our goal is find differentiable upper bound on the largest singular value of J.
From Sedghi et al. 2019), we know that singular values of J are given by:
o(J)=
U
((G())))
(3)
je(n-1l.
14

---

Published as a conference paper at ICLR 2021
where each ((.)) is matrix of dimensions Cout Cin. and each element of G is given by:
G (iih)) c,d
(F' (.d:: F) ce [Cout - 1], d d [cin 1]
(4)
Using equation value G that independent of j and & will give an desired upper bound. We will next derive the same.
3
we can directly observe that differentiable upper bound over the largest singular
Using equation
we can rewrite ((i.k) as: o,d
((i,) (F"K,d. (F..)) K.d......
(5)
Using equation] we know that Ke,d. is a sparse matrix of size n n with only the top-left block of size h x that is non-zero, We take the first h rows and columns of Ke,d. ie Ke,dsh,ws first elements of F.j i.c F. and first w elements of F.,. i. Fao,k- We have the following set of equalities:
G (1.))
(F..)) "(F.))"KKd.as Kedd..FF..
= (Fa Kodd Fow,k
(F Le Fankk
(6)
Thus, G(i.k) can be written as follows:
G GGA,)
h-1
Σ
Σ
Fi, Led.l.m m.
c,d
7-0 m=0
h-1
((i
Σ
Σ
FiJL
La m.kk
7-0 m=0
Now consider a block matrix R of dimensions Couch x Cin W given by:
L,,0,0
L,,0,11
L.s.U.-1
L L,.10
L
L w.l--
R
(8)
1,,0-110
Ligh-111
Legh-1 1,w-1
Thus the block in 1h row and mh column of R is the Cout cin matrix L.d..mm Consider two matrices: (F:h,))* T @ I (of dimensions Cout Couth) and F @ Ie,, (of dimensions
W Cin). Using equation] and equation we see that:
(j.k) ((Fe.s)* & Ieque) R (RFF @ Iem.)
Taking the spectral norm of both sides:
|G |(( )" + Iaon Fronk lew.) |G (FF JT @ Iemue) )l2 R (F ww Ic.. 1l
Using |A @ B
| BlIa and since both [ ll2 and Io ll2 are 1:
(G()) 1 E |R| Fa
Further note that since Fj wit, we have Fu ||2 TT and Fia, w..
|| s Vhw |R]|
Alternative inequality (1): Note that equation 6 can also be written by taking the transpose of the scalar (Fah.)) L.
((.k))
(f Frw,k (Fio. )T (Le,ds)) F o.d
15

---

Published as a conference paper at ICLR 2021
Thus, G can alternatively be written as follows:
Ni I h-
G (i.k)
= Σ
Σ
Fi, Lodd Fmn
c.d
1-0 m=0
Ni
h-
G(i
Σ
Σ
FIA L.L.a.m F Fm,
(10)
1-0 m=0
Now consider a block matrix of dimensions Cout cin given by:
L,,0,
1,,10
1, 1,0
1,,0111
L1111
1.1--111
S
(11)
1,,00011
For the block 1th row and m th column of R is the Cout cin matrix L.a.m.
Consider two matrices: (Fsw,))² @ L (of dimensions Cout x W) and F. @ lo,. (of dimensions Cinh x Cin).
Using equation and equation
11 we again have:
G(i.k) ((F...,)* Icaut (F @ Ic..)
(12)
Taking the spectral norm of both sides and using the procedure that used for R, get the following inequality:
(GO
Vie [S]2
Alternative inequality (2): Using equation 7
G(i can alternatively be written as follows:
GGiA)
h-1
m-11
Leddl. Fig Fi.
1=0 m=0
4-1
G(i
Σ
Σ
Lindm Fi.FFmm
(13)
1=0
m=
Now consider a block matrix T of dimensions Cout x hw given by:
T= [Ao A
A
(14)
where each block A; is matrix of dimensions Cout x Cin w given as follows:
A = [
L
Ltdda-1]
(15)
For T, the block in thh column the Cout x CinW matrix AG. For A,, the block in the mh column is the Cout x Gin matrix L.ddm- Consider the matrix: Fan.k
Fig & Le,, (of dimensions Garww Cin).
Using equation 13 equation and equation 15 again have:
((iA) ( 8 F F
@ Icm)
(16)
Taking the spectral norm of both sides and using the same procedure that we used for R and S, we get the following inequality:
[G || S how |T
Alternative inequality (3): Using equation 7 (G.A)) can alternatively be written as follows:
((iR))
h-1 w-1
Σ
Σ
Fi, F m. Led.l..
odd
1=0 mm0
h-1 w-1
((i)))
Σ
Σ
Fi. F
Lea
(17)
1=0 m00
16

---

Published as a conference paper at ICLR 2021
Now consider block matrix U of dimensions Couthw cin given by:
Bo
B
U
(18)
[
where each block B, is matrix of dimensions WoutW Con given as follows:
L,500
L
B
(19)
Lighw-1
For U, the block in 1 row is the Cout Cin matrix B For B,, the block in the m row is the
Cout X Cin matrix L.s.lm--
Consider the matrix: ((F & (w @ Loa (of dimensions Cout Couatiw).
Using equation 17 equation 18 and equation
19
again have:
G (1.)) ((Fth.)) @ (Fuw,k)² @ I
(20)
Taking the spectral norm of both sides and using the same procedure that we used for R. S and T, we get the following inequality:
|G
$ vhw 1|/
Taking the minimum of the four bounds i.e Vhw min [R] 2 |S]2 result.
12 (U12). we have the stated
F PROOF OF LEMMA
Proof. When h = and w 1, note that in equations
9
12
16 and 20
we have:
FAj= =
F Facck
This directly implies:
J |R||2
|S|2
[
|U|
G EFFECT OF INCREASING 3 ON SINGULAR VALUES
In Figure I plot the effect of increasing 3 the of true singular values of the network and sum of our upper bound. We observe that the gap between the two decreases as we increase 3.
In Table 6 show the effect of increasing on the bound on the largest singular value of each layer.
H EFFECT ON CERTIFIED ROBUST ACCURACY
17

---

Published as a conference paper at ICLR 2021
Filter shape
values
0
0.0006
0.0008
0.001
0.0012
0.0014
0.0016
0.0018
16 3 3
37.96
11.05
9.13
8.2
7.28
8.66
7.06
5.57
16 x 16 3
22.23
5.89
5.08
5.26
5.19
6.17
3,41
3.27
16 x x6 x
25.33
5.69
4.87
4.9
4.75
5.80
3.26
3.27
16 x
25.29
5.28
4.74
4.08
2.89
6.60
3.72
2.32
16 x 16x x
21.66
4.99
4.36
3.64
2.64
5.81
3.61
2.25
16 x
20.15
4.92
3.89
4.61
2.53
3.13
0.07
2.4
16 16x3x3
16.36
4.37
3.52
4.08
2.34
2.60
0.07
2.14
16 x x 3
15.39
5.39
5.65
3.15
4.1
4.72
2.31
1.69
16 16 x
14.67
4.38
4.61
2.32
3.52
3.66
2.37
1.57
16 x x6
19.26
7.41
6.28
4.96
3.57
0.13
5.38
3.19
16 x 16x3x3
14.60
5.77
4.84
4.01
2.68
0.09
4.31
2.64
32 x6
23.24
8.53
8.09
7.06
6.24
6.30
6.4
6.61
32 x
32
3
22.19
9.65
9.57
7.99
7.27
7.12
7.72
7.82
32 32
3
17.97
7.61
7.52
6.32
4.72
5.25
5.06
2.57
32
x 3
16.76
6.83
6.29
5.38
4.12
4.48
4.48
2.22
32 x 32
3
17.62
8.31
6.2
6.73
4.06
5.23
5.65
3.21
32
32
3
15.7
7.24
5.23
5.5
3.42
4.45
4.73
2.8
32 x 32
x
3
15.82
8.34
5.42
5.29
4.86
5.41
5.03
4.11
32 32 x
3
15.83
6.99
4.48
4.47
4.02
4.62
4.24
3.56
32 32
18.46
8.1
6.03
5.31
5.91
5.64
4.83
6.24
32 x 32 x
3
17.75
7.08
5.17
4.53
4.98
4.61
4.15
5.31
64 32 x 3
23.57
12.21
10.97
10.41
10.84
10.15
9.7
10.31
64 x x
22.97
13.2
12.23
11.72
12.55
11.36
11.14
12.39
64 64
x
22.35
12.18
11.71
11.13
10.53
10.57
10.2
10.43
64 64 x x
22.02
11.28
10.95
10.43
9.94
9.94
9.52
9.55
64 64
20.91
12.09
11.7
11.07
10.47
10.85
9.87
9.81
64 x x
21.77
10.85
10.51
9.81
9.6
9.62
8.56
8.43
64 64 x 3
19.63
11.97
11.56
10.28
10.98
10.02
9.32
8.69
64 x 64 x
3
17.61
10
10.03
8.81
9.63
8.26
7.57
7.35
64 x 64 3
16.67
10.34
11.61
10.26
10.93
8.64
8.05
8.56
64 3
17.81
8.16
8.73
7.68
8.18
6.61
6.07
6.49
10 x 64
12.43
10.79
10.55
10.53
10.11
10.14
9.64
9.39
Table Effect of increasing 3 on the bounds (Vhw) | R|2) 2) of each layer
18

---

Published as a conference paper at ICLR 2021
600
303
750
gin
Figure 1: We plot the effect of increasing 3 on the sum of the bounds (computed using our method ie Vhwl 2 and sum true spectral norms (IJ(1)2 computed using Sedghi et al. (2019) for Resnet-32 32 neural network trained CIFAR-10 10 dataset (without any weight decay). We observe that the gap between the two decreases as we increase 3. Table we show the effect of increasing on the bounds of individual layers of the same network.)
MNIST
CIFAR-10
Empirical Robust
Certified Robust
Empirical Robust
Certified
Standard Accuracy
Standard Accuracy
Robust
Accuracy
Accuracy
Accuracy
Accuracy
98.68%
87.81 %
0.00%
56.22%
14.88%
0.00%
0.01
97.08%
92.92%
91.25% %
53.52%
31.82%
17.39%
0.02
96.36%
90.98%
89.58%
49.55%
31.80%
25.93%
0.03
95.54%
89.99%
88.75%
46.56%
31.98%
29.26 %
Table 7: Comparison between certified robust accuracy for different values of the regularization parameter y for a single hidden layer convolutional neural network with softplus activation function.
Certified Robust Accuracy is computed as the fraction of correctly classified samples with CRC
(Curvature- crrvature-based Robustness Certificate as defined Singla & Feizi (2020) greater than 0.5.
Empirical robust accuracy is computed by running l2 bounded PGD (200 steps, step size 0.01). We use convolution layer with 64 filters and stride of size
19


Reviews:
[{"review_id": "nFnFlNdy6dL", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, an upper bound of the spectral norm of Jacobian of a convolutional layer is presented. The proposed bound enables us to compute the gradient much faster than the exact methods. In several experiments, the tightness of the bound and runtime/accuracy tradeoff are reported.\n\nPros:\nP1. A simple yet practical bound is provided\nP2. Code is provided, which is clean and easy to read\nP3. The problem is well motivated with a sufficient literature survey, which will stimulate the ICLR community\n\nCons:\nC1. The experiments do not include the seminal prior work (Miyato+ 2018) as a baseline\nC2. The terminology of \"difficult/easy\" for gradient computation is unclear\nC3. The technical contributions are relatively marginal\n\n\nDetailed comments:\n\nOverall, the paper is clearly written, and easy to follow the content. \n\nMy concerns:\n- [C1] One-step power method proposed by Miyato+ (2017; 2018) is not compared in the experiments. Since the proposed method is a generalization of Miyato's method, it looks like a natural way to make comparisons, e.g. in Section 4.2. Without comparison, the significance of this study would be not fully validated --- if Miyato's method achieves almost the same performance as the proposed method, the practical value would be degraded. \n- [C2] What does \"easy\" or \"difficult\" mean in terms of gradient computation? Does it refer to numerical stability, computational complexity, or something else? It seems there is no technical definition of them.\n- [C3] From (Miyato+ 2018), the main technical contributions are 1. proving that Miyato's method actually optimizes the upper bound of spectral norm up to constant scale, 2. tightening the bound by considering three more different reshaped matrices (R, S, U). In a theoretical sense, both 1 and 2 are meaningful. However, 1 does not contribute to the practical value, because when we use the spectral norm as a regularizer, the constant factor is absorbed in hyperparameter beta in (1). Also, there is no empirical evidence of how 2 improves the performance, as mentioned in [C1].", "extra_scores": {}, "extra_text": {}}, {"review_id": "n9kSQJOoUVb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nThis paper propose to study the Lipschitz constant of convolutional layers and to give an easy to compute and differentiable upper bound. The upper bound is composed of 4 different bounds, based on tensor unfolding of the Jacobian, and taking the min of these 4 values. This upper bound is then used to train networks with spectral norm regularization and compared with network trained with singular value clipping from `Sedghi et al. (2019)`. The proposed bound gives similar performances with much cheaper computational time.\n\n\n## Overall assessment\n\n- The title is misleading a bit. The bound is not on all the singular values but on the largest one. I would update it to `Fantastic four: differentiable upper bound on the Lipschitz constant of convolutional layers`.\n- The derivations for the 4 bounds are very straightforward from the results from `Sedghi et al. (2019)` as it is simply different unfolding of the hollow tensor that is obtained with the Jacobian of the convolution layer in the Fourier domain. The Jacobian is given in the preceding paper so the technical contribution is not very large.\n- My main concern with this paper is that the proposed evaluation is not sufficient to show the benefit of the proposed method IMO.\n    * First, I don't understand why the author choosed to compare singular value clipping with the spectral norm regularisation. Indeed, computing all the singular value will be much more expensive than computing a bound on the largest one. A proper evaluation with the same regularisation, using for instance the low number of power iterations proposed in `Ryu et al. (2019)` would be more convincing to show the computational benefit as well to compare the potential accuracy loss due to the approximation.\n    * Then, the results seems to be provided on single run of the method and not average on multiple random init. Averaging (and giving the standard deviation) would allow to asses the difference in stability of the proposed result.\n    * The weight decay is \"selected using grid search\" but there is no mention of validation set or the score used to select this parameter. This feels like the weight decay has been selected to maximize the test error, which is not a proper method to select such parameter.\n- I don't understand why the running time of the proposed method does not change between layer of size 64x64x3x3 and 512x512x3x3 in table.1. As the complexity of the bound is at least linear in the total shape of the filter, the running time should be mutliply by 64, which would give similar runtime as the one in Ryu et al (2019).\n\n\n## Minor comments, nitpicks and typos\n\n- p.3: `The corresponding Jacobian matrix` -> relative to the input. An introduction of the layer as a function $\\phi(x) = w * x$ and the definition of the Jacobian $J = \\frac{\\partial \\phi}{\\partial x}(x)$ would probably help in this regard.\n- Table.1: this table could probably be reduced to make more space for experiements\n- p.4: the notation section introduce many notations that are not used in the core of the paper. This should be trimmmed down to the minimum. For instance, I don't think that $\\phi'(z), \\phi''(z)$ or the per layer $z^{(I)}, a^{(I)}$ are used in the core of the text.\n- p.5: `O(1/p)bound is obtained on the error`: which error are the authors referring to? This should be properly introduced and discuss.\n- p.7: In the last paragraph of 4.2, the results are first given in order \"no weight decay/ with with decay\" and then in reverse order. This is confusing to read and changing the order would improve the readability.\n- Sedghi et al. (2018): The paper was pucblished in ICLR 2019, the proper citation is:\n```bibtex\n@inproceedings{Sedghi2019,\n    title={The Singular Values of Convolutional Layers},\n    author={Hanie Sedghi and Vineet Gupta and Philip M. Long},\n    booktitle={International Conference on Learning Representations},\n    year={2019},\n    url={https://openreview.net/forum?id=rJevYoA9Fm},\n}\n```\n- Ryu et al. (2019): The paper was published in ICML 2019:\n```bibtex\n @InProceedings{pmlr-v97-ryu19a,\n    title = {Plug-and-Play Methods Provably Converge with Properly Trained Denoisers},\n    author = {Ryu, Ernest and Liu, Jialin and Wang, Sicheng and Chen, Xiaohan and Wang, Zhangyang and Yin, Wotao},\n    pages = {5546--5557},\n    year = {2019},\n    editor = {Kamalika Chaudhuri and Ruslan Salakhutdinov},\n    volume = {97},\n    series = {Proceedings of Machine Learning Research},\n    address = {Long Beach, California, USA},\n    month = {09--15 Jun},\n    publisher = {PMLR},\n    pdf = {http://proceedings.mlr.press/v97/ryu19a/ryu19a.pdf},\n    url = {http://proceedings.mlr.press/v97/ryu19a.html}\n}\n ```\n- Other references should be checked.\n- Section D: The complex part here is not to compute the gradient of the convolution (which is simply computed with the correlation) but the shape of the gradient of the spectral norm of the Jacobian. This should be updated.\n- p.14: `will give a{n,} desired`.\n- p14/15/26: Eq.6/10/13/17 are the same (multiplication is associative and l/m are inverted in eq 10). The repetition is misleading as the reader search for the difference which is simply the ordering of terms. All these bounds would be much easier to derive/read if using tensor notation. Basically, what is done here seems to simply be computing the spectral norms of tensor slices unfolded along different dimensions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DInNW5GmUek", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary of the paper\n\nThis paper proposes an improved method to calculate an upper bound of the spectral norm of the 2d-convolutional layer. The advantage of the proposed method is fast computation and easy gradient computation. Experiments on MNIST and CIFAR10 show that regularizing spectral norms using the proposed method improves generalization. Additionally, they showed that their method could extend and improve an existing method for computing certified robustness accuracy.\n\n## Review\n\n### Summary\n\nThe paper is clearly written and easy to understand. However, the paper misses important literature and also seems to misunderstand existing methods. And I found the proposed method does not have the claimed advantages over existing methods.\n\n### More detailed comments\n\n1.  Misunderstandings of the existing method\nIf I understand it correctly, Ryu et al. do not directly calculate the singular vectors' outer-product. The spectral norm calculation written in Ryu et al. is differentiable. And thus, you can directly take the gradient of the spectral norm, and major deep learning frameworks efficiently compute its gradients.\n\n2. Missing literature\n\n> this is the first work that derives a provable bound on the spectral norm of convolution filter as a constant factor (dependant on filter sizes, but not filter weights) times the heuristic of Miyato et al. (2018)\n\nIt's at least mentioned in Cisse et al. (2017).\n\nAdditionally, efficient and differentiable computation of linear operators appeared in the literature repeatedly (Tsuzuku et al. 2018, Scaman & Virmaux 2018). They are not limited to the 2d convolutional layers, but any linear layers implemented using deep learning frameworks. Tsuzuku et al. 2018 also applied the method to improve certified robustness accuracy. I was not convinced that the proposed method has more advantages over these methods.\n\n\n3. Weak experiments\n\nThe experimental results seem noisy, and also the gain by the proposed regularizer looks marginal. Please write the number of each run and their standard deviations. Additionally, I am not convinced that the tighter bound results in better generalization. The proposed method is very similar to Yoshida & Miyato 2017, and it is not intuitive that the proposed method works better than it. Please add appropriate experimental comparisons with Yoshida & Miyato 2017. \n\n## References\n\nCisse et al. Parseval networks: Improving robustness to adversarial examples. ICML 2017.\nScaman and Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. NeurIPS 2018.\nTsuzuku et al. Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks. NeurIPS 2018\nYoshida and Miyato, Spectral norm regularization for improving the generalizability of deep learning. ArXiv, abs/1705.10941, 2017.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-VN0w0VReKX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides an method for computing an upper bound for the spectral norm of the linear transformation induced by a convolutional layer. An upper bound was first introduced as a heuristic by Miyato et al, but they did not prove any bounds. The authors use the exact computation of singular values of a convolutional layer in Sedghi, Gupta and Long to prove that the Miyato heuristic is indeed an upper bound. They further generalize Miyato's method to find 3 additional heuristics, all of which are proved to be upper bounds, and then show empirically that the minimum of these bounds gives a much tighter bound, often very close to the exact value. The bounds are significantly faster to compute than exact spectral norms, both in complexity and in practice.\n\nThe authors show that their bounds can be used for regularization, and produce results similar to the spectral projection method in Sedghi et al on CIFAR-10. They also show that spectral bounds enhance the robustness of CNNs against adversarial attacks - previous papers were unable to compute these spectral norms so remained restricted to fully connected networks. By extending the results of Singla & Feizi to convolutional nets, the authors are able to improve the state of the art significantly.\n\nStrengths:\nThe upper bounds are formally proved, and the proofs are easy to follow. The upper bounds are easy to compute - the methods overcomes the dependence on n^2 in the exact methods.\n\nWeaknesses:\nThe upper bounds only bound the spectral norm, and do not provide any information about the remaining singular values. The comparison with Sedghi's CIFAR-10 used a baseline that was weaker, Sedghi et al improved CIFAR-10 accuracy from 93.8 to 94.7. I would like Section 4.3 to be explained a bit better, so that I can understand the significance of the results more clearly.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide four rigorous upper bounds on the operator norm of the linear transformation associated with a 2D convolutional layer of a neural network.  One of these is a heuristic proposed in earlier work by Miyato et al, and widely used, so, among other things, their result provides theoretical context for that method which will be of broad interest.  All four of their bounds can be efficiently computed and have easily computed gradients, so they propose using the minimum of the four bounds for various purposes.  Since, for standard architectures, the Lipschitz constant of a network can be bounded above by the product of the operator norms of its layers, there are a variety of applications of differentiable bounds on these operator norms.  They show that their new bound is sometimes much tighter than the bound of Miyato et al, and can be computed much more efficiently than two known methods for exact computation.  The paper is written well, which will facilitate future work building on this work.  The analysis builds on earlier work, but insight was required to obtain the new results;  the fundamental novelty of the mathematical development was confirmed by an expert reviewer.

While they experimentally compared the accuracy of their approximations to those of the method of Miyato, et al, the case for the practical utility of their method would have been stronger if they had shown that their regularizer led to better results for some tasks.  However, I believe that the paper should be accepted purely on the basis of its theoretical contribution, which enhances our understanding of this important topic, and, even if it cannot be directly applied, seems like to inspire practically useful methods in the future.

Decision: Accept (Poster)