Controlling the Complexity and Lipschitz Constant improves Polynomial Nets
Authors: Zhenyu Zhu
Fabian Latorre
Grigorios Chrysos
Volkan Cevher
Venue: ICLR 2022 Poster (2022)
Keywords: Polynomial Nets
Rademacher Complexity
Lipschitz constant
Coupled CP decomposition

Abstract: While the class of Polynomial Nets demonstrates comparable performance to neural networks (NN), it currently has neither theoretical generalization characterization nor robustness guarantees. To this end, we derive new complexity bounds for the set of Coupled CP-Decomposition (CCP) and Nested Coupled CP-decomposition (NCP) models of Polynomial Nets in terms of the $\ell_\infty$-operator-norm and the $\ell_2$-operator norm. In addition, we derive bounds on the Lipschitz constant for both models to establish a theoretical certificate for their robustness. The theoretical results enable us to propose a principled regularization scheme that we also evaluate experimentally and show that it improves the accuracy as well as the robustness of the models to adversarial perturbations. We showcase how this regularization can be combined with adversarial training, resulting in further improvements.

Published as a conference paper at ICLR 2022
CONTROLLING THE COMPLEXITY AND LIPSCHITZ CONSTANT IMPROVES POLYNOMIAL NETS
Zhenyu Zhu, Fabian Latorre, Grigorios G Chrysos
Volkan Cevher
EPFL, Switzerland
([first name] [surname] [@epfl.co .ch
ABSTRACT
While the class of Polynomial Nets demonstrates comparable performance to neural networks (NN), it currently has neither theoretical generalization characterization nor robustness guarantees. To this end, we derive new complexity bounds for the set of Coupled CP-Decomposition (CCP) and Nested Coupled -e-decomposition (NCP) models of Polynomial Nets in terms of the -e--rpratoo-norn and the l-- operator norm. In addition, we derive bounds on the Lipschitz constant for both models to establish a theoretical certificate for their robustness. The theoretical results enable us to propose a principled regularization scheme that we also evaluate experimentally in six datasets and show that it improves the accuracy well the robustness of the models to adversarial perturbations. We showcase how this regularization be combined with adversarial training, resulting in further improvements.
INTRODUCTION
Recently, high-degree Polynomial Nets (PNs) have been demonstrating statc-of-the-an performance in range of challenging tasks like image generation (Karras et al., 2019; Chrysos and Panagakis, 2020), image classification (Wang et al., 2018), reinforcement learning (Jayakumar et al., 2020), non-euclidean representation learning (Chrysos et al., 2020) and sequence models (Su et al., 2020). In particular, in public benchmarks like the Face verification on MegaFace task' (Kemelmacher- Shlizerman et al., 2016), Polynomial Nets are currently the top performing model.
A major advantage of Polynomial Nets over traditional Neural 2etworks is that they are compatible with efficient Leveled Fully Homomorphic Eneryption (LFHE) protocols (Brakerski al., 2014). Such protocols allow efficient computation on encrypted data, but they only support addition or multiplication operations i.e., polynomials. This has prompted an effort to adapt neural networks by replacing typical activation functions with polynomial approximations (Gilad-Bacc Bachrach et al., 2016; Hesamifard al., 2018). Polynomial Nets do not need any adaptation work with LFHE.
Without doubt, these arguments motivate further investigation about the inner-workings of Polynomial Nets. Surprisingly, little is known about the theoretical properties of such high-degree polynomial expansions, despite their success. Previous work PNs (Chrysos et al., 2020; Chrysos and Panagakis, 2020) have focused on developing the foundational structure of the models as well as their training, but do not provide analysis of their generalization ability robustness to adversarial perturbations.
In contrast, such type of results are readily available for traditional feed-forward Deep Neural Networks, in the form of high-probability generalization eтrоr bounds (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2017; Golowich et al., 2018) or upper bounds on their Lipschitz constant (Scaman and Virmaux, 2018; Fazlyab al., 2019; Latorre al., 2020). Despite their similarity in the compositional structure, theoretical results for Deep Neural Networks" do not apply Polynomial Nets, as they are essentialy non-overlapping classes of functions.
Why are such results important? First, they provide key theoretical quantities like the sample complexity of hypothesis class: how many samples are required succeed learning in the PAC-framework. Second, they provide certified performance guarantees to adversarial perturbations
'https: / wwpp//aapwwwiiia thooe com/sctal how/:/taa/aaceeeeeeeeeeeeee fare-veri with non-polynomial activation functions.

---

Published as a conference paper at ICLR 2022
(Szegedy al., 2014; Goodfellow et al., 2015) via worst-case analysis c.f. Scaman and Virmaux (2018). Most importantly, the bounds themselves provide principled way to regularize the hypothesis class and improve their accuracy robustness.
For example, Generalization and Lipschitz constant bounds of Deep Neural Networks that depend on the operator-norm of their weight matrices (Bartlett et al., 2017; Neyshabur et al., 2017) have layed out the path for regularization schemes like spectral regularization (Yoshida and Miyato, 2017; Miyato et al., 2018), Lipschitz-margin training (Tsuzuku al., 2018) and Parseval Networks (Cisse et al., 2017] 7), to name a few.
Indeed, such schemes have been observed in practice to improve the performance of Deep Neural Networks. Unfortunately, similar regularization schemes for Polynomial Nets do not exist due to the lack of analogous bounds. Hence, it is possible that PNs are not yet being used to their fullest potential. We believe that theoretical advances in their understanding might lead to more resilient and accurate models. In this work, we aim to fill the gap in the theoretical understanding of PNs. We summarize our main contributions as follows:
Rademacher Complexity Bounds. We derive bounds on the Rademacher Complexity of the Cou- pled CP-decomposition model (CCP) and Nested Coupled CP-decomposition model (NCP) of PNs, under the assumption of a unit -norm bound on the input (Theorems and 3), a natural assumption in image-based applications. Analogous bounds for the fn-norm are also provided (Appendices E.3 and F.3). Such bounds lead to the first known generalization error bounds for this class of models.
Lipschitz constant Bounds. To complement our understanding of the CCP and NCP models, we derive upper bounds on their LLp-iscciitz constants (Theorems 2 and 4), which are directly related to their robustness against -oundded adversarial perturbations, and provide formal guarantees. Analogous results hold for any fy-norm (Appendices E.4 and F.4).
Regularization schemes. We identify key quantities that simultaneously control both Rademacher Complexity and Lipschitz constant bounds that we previously derived, i.e., the operator norms of the weight matrices in the Polynomial Nets. Hence, we propose to regularize the CCP and NCP models by constraining such operator norms. In doing so, our theoretical results indicate that both the generalization and the robustness to adversarial perturbations should improve. We propose a Projected Stochastic Gradient Descent scheme (A (Algorithm 1), enjoying the same per-iteration complexity as vanilla paok-propagation the Lx -norm case, and a variant that augments the base algorithm with adversarial traning ( (Algorithm 2).
Experiments. We conduct experimentation in five widely-used datasets on image recognition and on dataset in audio recognition. The experimentation illustrates how the aforementioned regularization schemes impact the accuracy (and the robust accuracy) of both CCP and NCP models, outperforming alternative schemes such as Jacobian regularization and the Le weight decay. Indeed, for a grid of regularization parameters we observe that there exists a sweet-spot for the regularization parameter which not only increases the test-accuracy of the model, but also its resilience to adversarial pertur- bations. Larger values of the regularization parameter also allow a trade-off between accuracy and robustness. The observation is consistent across all datasets and all adversarial attacks demonstrating the efficacy of the proposed regularization scheme.
2 RADEMACHER COMPLEXITY AND LIPSCHITZ CONSTANT BOUNDS FOR POLYNOMIAL NETS
The symbol denotes the Hadamard (element-wise product, the symbol is the face- splitting product, while the symbol * denotes a convolutional operator. Matrices are denoted by uppercase letters e.g.. V. Due to the space constraints, detailed notation is deferred Appendix C.
Notation.
assume an lo -orm unit bound on the input data i.c., || < 1 for any input z. This is the most common assumption in magee-omain applications in contemporary deep learning, i.e., each pixel takes values in [-1, 1] interval. Nevertheless, analogous results for fn-norm unit bound assumptions are presented in Appendices E.3, E.4, F.3 and E.4.
Assumption the input distribution. Unless explicitly mentioned otherwise,
We now introduce the basic concepts that will be developed throughout the paper i.c., the Rademacher Complexity of class of functions (Bartlett and Mendelson, 2002) and the Lipschitz constant.
2

---

Published as a conference paper at ICLR 2022
U2
U
U
A3
A2
As
0/
f(a)
(()
Figure 1: Schematic of CCP model (left) and NCP model (right), where e denotes the Hadamard product. Blue boxes correspond learnable parameters. Green and red boxes denote input and output, respectively. Yellow boxes denote operations.
Definition (Empirical Rademacher Complexity). Let = {z1...., 2n3 S I& and let wy:jjl,.... be independent Rademacher random variables i.e., taking values uniformly in +1}. Let F be class of real-valued functions over RR.. The Empirical Rademacher complexity of with respect to Z is defined as follows:
Rz(F) E
Σ ())))) fEF n
sup -
Definition (Lipschitz constant). Given two normed spaces (X, || x1x)) and (3), Ilyy a function f: y is called Lipschitz continuous with Lipschitz constant K 2 for all ø 22 in X:
llf(x=) (x2))lly K| x22lx
2.1 COUPLED CP-DECOMPOSITION OF POLYNOMIAL NETS (CCP MODEL)
The Coupled Pe--ecommosition (CCP) model of PNs (Chrysos et al., 2020) leverages a coupled CP Tensor decomposition (Kolda and Bader, 2009) to vastly reduce the parameters required to describe high-degree polynomial, and allows its computation in compositional fashion, much similar to fced-forward pass through traditional neural network. The CCP model was used in Chrysos and Panagakis (2020) to construct generative model. CCP can be succintly defined as follows:
f(z) C of U,2,
(CCP)
where z E RRd is the input data, ((z E Ro the output of the model and Un E RR C E Roxm are the learnable parameters, where m E N is the hidden rank. In Fig. we provide a schematic of the architecture, while in Appendix D. include further details on the original CCP formulation (and how to obtain our equivalent re-parametrization) for the interested reader.
In Theorem we derive upper bound on the complexity of CCP models with bounded loc -operator norms of the face-splitiig product of the weight matrices. Its proof can be found in Appendix E. For given CCP model, we derive an upper bound on its Ex -Lipschitz constant in Theorem 2 and its proof is given in Appendix E.4.1.
Theorem 1. Let Z = {-1,-.. zn} C Rdd and suppose that ||= S 1 for all = 1,...,n Let n.
Fier (f(z) (c, of U,2) ||c|| S p. U. $}
The Empirical Rademacher Complexity of CCPk (k-degree CCP polynomials) with respect to Z is bounded as:
2k log(d)
Rz(F S 2
n
Proof sketch of Theorem 1 the complete and detailed proof steps presented in Appendix E.l. First, Hölder's inequality is used to bound the Rademacher complexity as:
We now describe the core steps of the proof. For the interested reader,
n
R2(F(er) sup feF n
c, Σ o j=1
S
sup FEF
|elli
Σ
o 2 (U,z)))
j=1
3

---

Published as a conference paper at ICLR 2022
This shows why the factor ||c]] S r appears in the final bound. Then, using the mixed product property (Slyusar, 1999) and its extension to repeated Hadamard products (Lemma 7 in Appendix C.3), can rewrite the summation in the right-hand-sien of (1) as follows:
Σo x (U,) 1 (z,) - (U,) 00
x (z))
This step can be seen as a linearization of the polynomial by lifting the problem a higher dimensional space. We use this fact and the definition of the operator norm to further bound the term inside the -norm in the right-hand-side of (I). Such term is bounded as the product the - norm of i (U.). and the lx -orm of an expression involving the Rademacher variables o and the vectors ( Finally, an application of Massart's ' Lemma (Shalev-Shwarl and Ben-David (2014), Lemma 26.8) leads to the final result.
Theorem 2. The Lipschitz constant (with respect to the to norm) of the function defined in Eq. (CCP), restricted to the set {z E Rd: 2| I 1} is bounded as:
Lf) S &|||| 00 U.
2.2 NESTED COUPLED CP-DECOMPOSITION (NCP MODEL)
The Nested Coupled De-Decomposition (NCP) model leverages joint hierarchical decomposition, which provided strong results in both generative and discriminative tasks Chrysos et (2020). A slight re-parametrization of the model (Appendix D.2) can be expressed with the following recursive relation:
s = (A))) (81), xr, = (An=) (Sn
[(=) = Car:
(NCP)
where = E Rd the input vector and E Roxm An E RR S. E Rmxxm and 81 E R are the learnable parameters. In Fig. 1 we provide schematic of the architecture.
In Theorem we derive an upper bound on the complexity of NCP models with bounded foe operator norm of a matrix function of its parameters. Its proof can be found in Appendix F.I. For given NCP model, we derive an upper bound on its -Lpsschtt constant in Theorem and its proof given in Appendix F.4.1.
Theorem 3. Let 7 = (zi,..., 2n) C Rd and suppose that || S 1 all j = 1,...., the matrix &6 (AA,, Si.... An, S.) = (A, St) IT:=1 @ A, o S, Consider the class of functions: Flic == (f(z) as in (NCP): ||C||so S S4, (1,,, S1. Si.... Ak, (...s)lloo A)
n. Define
where C E 1x (single output), thus, will write it as and the corresponding bound also becomes ||c]la < p. The Empirical Rademacher Complexity of NCPs (k-degree NCP polynomials)
with respect to Z is bounded as:
2k log
Rz S 2
n
Theorem The Lipschitz constant (with respect to the norm) of the function defined in Eq. (NCP), restricted to the set {z E Rd =| I 1} is bounded as:
Lip (f) < k||C|| 30 II (1 (
ALGORITHMS
By constraining the quantities in the upper bounds on the Rademacher complexity (Thcorems 1 and 3), we regularize the empirical loss minimization objective (Mohri al., 2018. Theorem 3.3). Such method would prevent overfitting and can lead to an improved accuracy. However, one issue with the quantities involved in Theorems and 3, namely
R-
L Uilloc
(Ax A Sw)
I 18 S
4

---

Published as a conference paper at ICLR 2022
is that projecting onto their level sets correspond to difficult non-convex problem. Nevertheless, can control an upper bound that depends on the &g -operator norm of each weight matrix:
Lemma 1. It holds that ||
I
Lemma 2. It holds that (AA Sk))
II @ A S. $ | (o
The proof's of Lemmas 1 and 2 can be found in Appendix E.2 and Appendix F.2. These results mean that by constraining the operator norms of each weight matrix, we can control the overall complexity of the CCP and NCP models.
Projecting a matrix onto an operatto norm ball is a simple task that can achieved by projecting each row of the matrix onto an f1-nrrm ball, for example, using the well-known algorithm from Duchi et al. (2008). The final optimization objective for training a regularized CCP is the following:
min C,U1 UN
E
U.:
subject to ||C|| S μ. | X,
(2)
where (e) is the training dataset, is the loss function (e.g., cross-entropy) and μt, À the regularization parameters. We notice that the constraints on the learnable parameters U; and C have the effect of simultaneously controlling the Rademacher Complexity and the Lipschitz constant of the CCP model. For the NCP model, an analogous objective function is used.
To solve the optimization problem Eq. (2) we will use Projected Stochastic Gradient Descent method Al Algorithm 1. We also propose variant that combines Adversarial Training with the projection step (Algorithm 2) with the goal of increasing robustness to adversarial examples.
Algorithm 1: Projected SGD
Algorithm 2: Projected SGD Adversarial Training
Input: dataset Z, learning rate (7x > T-1 iterations T, hyper-parameters R. f Loss L.
Input: dataset Z, learning rate {7: > -) iterations T
and n, hyper-parameters R. f e and a, Loss L
Output: model with parameters
Output: model with parameters O.
Initialize 0.
Initialize 0.
for t = 0 to 1 do Sample (ar,) from Z for i to 1 do
for t = 0 to T - do
Sample (x. 3) from Z
0 = 0 - 7t v (0; x v).
[c] ad [I -
(ar +oV2
i mod| f then
Vo adv .9)
0 [[ sm) (0)
if f mod f f then
1l |1 |1 sR) (0)
In Algorithms and 2 the parameter f set in practice to a positive value, so that the projection (denoted by II) is made only every few iterations. The variable 0 represents the weight matrices of the model, and the projection the last line should be understood as applied independently for every weight matrix. The regularization parameter R corresponds to the variables μr, in Eq. (2).
Convolutional layers Frequently, convolutions are employed in the literature, especially in the image-domain. important to understand how our previous results extend to this case, and how the proposed algorithms work in that case. Below, convolutional layer (as a linear operator) related to the -operator norm the kernel after a reshaping operation. For simplicity, we consider only convolutions with padding.
show that the Lo -operatoo norm of the
We study the cases of ID, 2D and 3D convolutions. For clarity, we mention below the result for the 3D convolution, since this is relevant to experimental validation, and defer the other two cases to Appendix G.
Theorem 5. Les A E XXXmXr be an input image and let K E Bhxxxexo be a convolutional kernel with output channels. For simplicity assume that k < min(n, m) is odd. Denote by B = K * A the output of the convolutional layer. Let E numox be the matrix such that veo B) = Uve Lee. U is the matrix representation of the convolution. Let M (K) Roxhhr be the matricization of
5

---

Published as a conference paper at ICLR 2022
K, where each contains the parameters of single oupput channel of the convolution. It holds that: | = [JM
Thus,
control the &o -o--orrrtoor-nome of convolutional layer during training by controlling that of the reshaping of the kernel, which done with the same code as for fully connected layers. can be seen that when the padding non-zero, the result still holds.
NUMERICAL EVIDENCE
The generalization properties and the robustness of PNs are numerically verified in this section. We evaluate the robustness to three widely-used adversarial attacks in sec. 4.2. We assess whether the compared regularization schemes can also help in the case of adversarial training in see. 4.3. Experiments with additional datasets, models (NCP models), adversarial attacks (APGDT, PGDT) and layer-wise bound (instead of a single bound for all matrices) are conducted in Appendix H due to the restricted space. The results exhibit a consistent behavior across different adversarial attacks, different datasets and different models. Whenever the results differ, we explicitly mention the differences in the main body below.
4.1 EXPERIMENTAL SETUP
The accuracy is reported as the evaluation metric for every experiment, where higher accuracy translates to better performance.
We conduct experiments on the popular datasets of Fashion- MNIST (Xiao et al., 2017), E-MNIST (Cohen al., 2017) and CIFAR-10 (Krizhevsky et al., 2014). The first two datasets include grayscale images of resolution 28 28, while CIFAR-10 includes 60, 000 RGB images of resolution 32 x 32. Each image is annotated with one out of the ten categories. We use two popular regularization methods from the literature for comparison, i.e., Jacobian regularization (Hoffman et al., 2019) and L2 regularization (weight decay).
Datasets and Benchmark Models:
Models: We report results using the following three models: 1) -eggre CCP model named "PN-4", 2) a 10th -egreee CCP model referenced as "PN-10" and 3) a 4th -degree Convolutional CCP model called "PN-Conv". In the PN-Conv, we have replaced all the U; matrices with convolutional kernels. None of the variants contains any activation functions.
papper-parmmtter: Unless mentioned otherwise, all models are trained for 100 epochs with a batch size of 64. The initial value of the learning rate is 0.001. After the first 25 epochs, the learning rate is multiplied by a factor of 0.2 every 50 epochs. The SGD used to optimize all the models, while the cross- cross-entropy loss is used. In the experiments that include projection or adversarial training, the first 50 epochs are pre-training. i.c., training only with the cross-entropy loss. The projection is performed every ten iterations.
Adversarial Attack Settings: We utilize two widely used attacks: a) Fast Gradient Sign Method (FGSM) and b) Projected Gradient Descent (PGD). In FGSM the step size of the adversarial attack. PGD there is a triple of parameters (Crotal, Niter fiter), which represent the maximum step size of the total adversarial attack, the number of steps to perform for single attack, and the step size of each adversarial attack step respectively. We consider the following arperpparamtters for the attacks: a) FGSM with 0.1. b) PGD with parameters (0.1, 20, 0.01), c) PGD with parameters (0.3, 20, 0.03).
represents the
4.2 EVALUATION OF THE ROBUSTNESS OF PNS
In the next experiment, we assess the robustness of PNs under adversarial noise. That is, the method is trained on the train set of the respective dataset and the evaluation is performed on the test set perturbed by additive adversarial noise. That is, each image individually perturbed based on the respective adversarial attack. The proposed method implements Algorithm 1.
The quantitative results in both Mishion-MNIST and E-MNIST using PN-4, PN-10 and PN-Conv under the three attacks are reported in Table 1. The column 'No-proj' exhibits the plain SGD training (i.e.. without regularization), while the remaining columns include the proposed regularization, Jacobian and the L2 regularization respectively. The results without regularization exhibit substantial decrease in accuracy for stronger adversarial attacks. The proposed regularization outperforms all methods consistently across different adversarial attacks. Interestingly, the stronger the adversarial

---

Published as a conference paper at ICLR 2022
No proj.
Our method
Jacobian
L2
Method
Fashion-MNIST
Clean
87.28 + 0.18%
87.32 + 0.14%
86.24 = 0.14%
87.31 0.13%
FGSM-0.1
12.92 +: 2.74%
46.43 + 0.95%
17.90 + 6.51%
13.80 3.65%
PN-4
PGD-(0.1,, 20, 0.01)
1.64:1.70 1.76%
0.59% 49.58
12.23 5.63%
5.01
PGD-(0.3, 20, 0.03)
0.18 0.16%
#8.9622.30
1.27 = 1.29%
0.18%
Clean
88.48
88.12 =
88.46 0.19%
FGSM-0.1
15.96
1.24%%
19.52 1.14%
16.51 2.33%
PN-10
PGD-(0.1, 20, 0.01)
1.94
47.94
1:94:2200 2.29%
5.44 114:00 0.81%
2.16 1 0.95%
PGD-(0.3, 20, 0.03)
0.03%
30.51 1.22%
0.05 1 0.02%
0.01 0.02%
Clean
86.36 0.21%
86.38 0.26%
84.69 + 0.44%
86.45 0.21
FGSM-0.1
10.80
48.15 1.23%
10.62 = 0.77%
10.73 1.58%
PN-Conv
PGD-(0.1, 1, 20, 0.01)
9.37 + 1.00%
46.63 + 3.68%
10.20 0.32%
8.96 - 0.83%
PGD-(0.3, 20, 0.03)
1.75 + 0.83%
28.94 + 1.20%
8.26 + 1.05%
2.03 + 0.99%
E-MNIST
Clean
84.27 + 0.26%
0.31
81.99 + 0.33%
84.22 + 0.33%
FGSM-0.1
8.92 + 1.99%
3.3322
PN-4
PGD-(0.1, 20, 0.01)
6.24 1.43%
29.46
6.75 1 2.92%
1.97%
PGD-(0.3,, 20, 0.03)
1.22 + 0.85%
19.07#0.990
3.06 + 0.53%
+
Clean
80.31 0.00%
00.5610.10%)
89.19 + 0.07%
89.23 = 0.13%
FGSM-0.1
15.56 + 1.16%
37.11 2.81%
24.21 + 1.89%
16.30 1.30=1 1.82%
PN-10
PGD-(0.11, 20, 0.01)
2.63 0.65%
37.89 + 2.91%
9.18 1.09%
2.33 0.43%
(0., 0.03)
0.00 + 0.00%
20.47 + 0.96%
0.11 + 0.08%
0.02 + 0.03%
Clean
91.49 1 0.29% 0.20%
91.57 1 0.19%
90.38 0.13%
91.41 0.18%
FGSM-0.1
4.28 + 0.55%
35.39 7.51%
3.88 + 0.04%
4.13 - 0.41%
PN-Conv
PGD-(0.1, 20, 0,01)
3.98 + 0.82%
33.75 = 7.17%
3.86 0.01%
4.83 - 0.87%
PGD-(0.3, 20, 0.03) 3.24 + 0.76%
28.10 - 3.27%
3.84 0.01%
2.76 = 0.65%
Table I: Comparison of regularization techniques on Fashion-MNIST (top) and E-MNIST (bottom)..
In each dataset, the base networks are PN-4, i.e., 4th degree polynomial, on the top four rows, PN-10, ie.. 10th degree polynomial, on the middle four rows and PN-Conv, i.e., a 4th degree polynomial with convolutions, on the bottom four rows. Our projection method exhibits the best performance in
all three attacks, with the difference accuracy to stronger attacks being substantial.
attack, the bigger the difference of the proposed regularization scheme with the alternatives of Jacobian and 122 regularizations.
Next, we learn the networks with varying projection bounds. The results on Fashion-MNIST and E-MNIST are visualized in Fig. 2, where the x-axis plotted log-scale. As a reference point, we include the clean accuracy curves, i.e., when there is no adversarial noise. Projection bounds larger than (in the log-axis) leave the accuracy unchanged. As the bounds decrease, the results gradually improve. This can be attributed to the constraints the projection bounds impose into the U, matrices.
Similar observations can be made when evaluating the clean accuracy (i.e., no adversarial noise in the test set). However, in the case of adversarial attacks tighter bound performs better, i.c., the best accuracy exhibited in the region of 0 in the log-axis. The projection bounds can have a substantial improvement the performance, especially in the case of stronger adversarial attacks, i.e., PGD. Notice that all the aforementioned cases, the intermediate values of the projection bounds yield an increased performance in terms of the test-accuracy and the adversarial perturbations.
Beyond the aforementioned datasets, we also validate the proposed method on CIFAR-10 10 dataset. The results in Fig. 3 and Table 2 exhibit similar patterns the aforementioned experiments. Although the improvement is smaller than the case of Fashion-MNIST and E-MNIST, we can still obtain about 10% accuracy improvement under three different adversarial attacks.
4.3 ADVERSARIAL TRAINING (AT) ON PNs
Adversarial training has been used as a strong defence against adversarial attacks. In this experiment evaluate whether different regularization methods work in conjunction with adversarial training that is widely used as a defence method. Since multi-step adversarial attacks are computationally intensive, utilize the FGSM attack during training, while evaluate the trained model in all three
7

---

Published as a conference paper at ICLR 2022
Clean
FGSM 0.1
1GD_0.1_0.01121
PGD PGD_0.3_ 0...0.033_.230000013 20
PN-4
PN-10
PN-Conv
100
80
Accuracy(%)
60
40
20
Log of Bound
Log of Bound
Log of Bound
Fashion-MNIST
PN-4
PN-10
PN-Conv
100
80
Accuracy
60
40
0
Log Bound
of Bound
Log Bound
(b) E-MNIST
Figure 2: Adversarial attacks during testing on (a) MNNIST (top), (b) E-MNIST (bottom) with the x-axis is plotted in log-scale. Note that intermediate values of projection bounds yield the highest accuracy. The patterns are consistent in both datasets and across adversarial attacks.
Clean ...
FGBML6.1 PSD.0.10.0120
PSD_0.3..03.00
PN-Conv
100
Accuracy(5)
60
20
Log of Bound
Figure 3; Adversarial attacks during testing on CIFAR-10.
8

---

Published as a conference paper at ICLR 2022
Model
PN-Conv
Projection
No-proj
Our method
Jacobian
L2
Clean accuracy FGSM-0.1
65.09 = 0.14%
65.22 - 0.13%
64.43 = 0.19%
63.11 - 0.08%
6.00 + 0.53%
15.13 + 0.81%
3.34 + 0.40%
1.27 + 0.10%
PGD-(0.1, I, 20, 0.01)
7.08 + 0.68%
15.17 + 0.88%
1.74 + 0.14%
1.05 + 0.05%
PGD-(0.3, 20, 0.03)
0.41 + 0.09%
11.71 = 1.11%
0.04 = 0.02%
0.51 0.04%
Table 2: Evaluation of the robustness of PN models CIFAR-10. Each line refers different adversarial attack. The projection offers an improvement in the accuracy in each case; in PGD attacks the projection improves the accuracy by significant margin.
adversarial attacks. For this experiment we select PN-10 as the base model. The proposed model implements Algorithm 2.
The accuracy is reported Table 3 with Fashion-MNIST on the top and E-MNIST on the bottom. In the FGSM attack, the difference of the compared methods is smaller, which is expected since similar attack is used for the training. However, for stronger attacks the difference becomes pronounced with the proposed regularization method outperforming both the Jacobian and the L2 regularization methods.
AT'
Our method AT
Jacobian + AT
L +
Method
Adversarial training (AT) with PN-10 on Fashion-MNIST
FGSM-0.1
65.33 + 0.46%
65.64 + 0.35%
62.04 + 0.22%
65.62 + 0.15%
PGD- 20, 0.01)
57.45 + 0.35%
59.89 + 0.22%
57.42 = 0.24%
57.40 + 0.36%
PGD-(0.3, 20, 0.03)
24.46 + 0.45%
39.79 + 1.40%
25.59 + 0.20%
24.99 + 0.57%
Adversarial training (AT) with PN- 10 on E-MNIST
FGSM-0.1 PGD-(0.1, 20, 0.01) 68.40 + 0.32%
78.30 = 0.18%
78.61 + 0.58%
70.11 = 0.18%
78.31 = 0.32%
68.51 + 0.19%
64.61 = 0.16%
68.41 + 0.37%
PGD-(0.3, 20, 0.03) 35.58 + 0.33%
42.22 + 0.60%
39.83 + 0.24%
35.17 + 0.46%
Table 3: Comparison of regularization techniques on (a) Fashion- (top) and (b) E-MNIST (bot- tom) along with adversarial training (AT). The base network is PN-10, i.e., 10th degree polynomial. Our projection method exhibits the best performance in all three attacks.
The limitations of the proposed work are threefold. Firstly, Theorem relies on the foe -operator norm of the face-splitting product of the weight matrices, which in practice relax in Lemma 1 for performing the projection. In the future, we aim to study if it is feasible to compute the non-convex projection onto the set of PNs with bounded &oo -nom of the face-splitting product of the weight matrices. This would allow us to let go off the relaxation argument and directly optimize the original tighter Rademacher Complexity bound (Theorem 1).
Secondly, the regularization effect of the projection differs across datasets and adversarial attacks, a topic that is worth investigating in the future.
Thirdly, our bounds do not take into account the algorithm used, which corresponds to a variant of the Stochastic Projected Gradient Descent, and hence any improved generalization properties due to possible uniform stability (Bousquet and Elisseeff, 2002) of the algorithm or implicit regularization properties (Neyshabur, 2017), do not play a role in our analysis.
CONCLUSION
In this work, we explore the generalization properties of the Coupled CP-decomposition (CCP) and nested coupled CP CPddecompooition (NCP) models that belong in the class of Polynomial Nets (PNs). We derive bounds for the Rademacher complexity and the Lipschitz constant the CCP and the NCP models. We utilize the computed bounds regularization during training. The regularization terms have also substantial effect on the robustness of the model, i.e., when adversarial noise is added to the test set. A future direction of research is obtain generalization bounds for this class of functions using stability notions. Along with the recent empirical results on PNs, our derived bounds can further explain the benefits and drawbacks of using PNs.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We are thankful to Igor Krawezuk and Andreas Loukas for their comments on the paper. We are also thankful to the reviewers for providing constructive feedback. Research was sponsored by the Army Research Office and was accomplished under Grant Number 199119999-000044 This work is funded (in part) through a PhD fellowship of the Swiss Data Science Center, a joint venture between EPFL and ETH Zurich. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement number 725594 time-data).
REFERENCES
P. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normaaizee margin bounds for neural networks, 2017.
P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
O. Bousquet and Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions Computation Theory (TOCT), 6(3):1-36, 2014.
G. Chrysos. S. Moschoglou, G, Bouritsas, Y. Panagakis. J. Deng, and S. Zafeiriou. x-nets: Deep polynomial neural networks. Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
G. G. Chrysos and Y. Panagakis. NAPS: Non-adversarial polynomial synthesis. Pattern Recognit. Lett., 140:318 324, 2020.
M. Cisse, P. Bojanowski, E. Grave, Y. Dauphin, and N. Usunier. Parseval networks: Improving robustness to adversarial examples. In International Conference on Machine Learning, pages 854-863. PMLR, 2017.
T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha. Deep learning for classical japanese literature. arXiv preprint
2018
G. Cohen, S. Afshar, J. Tapson, and A. van Schaik. Emnist: an extension of mnist to handwritten letters. arXiv preprint 1000::190..000 06571, 2017.
Croce and M. Hein. Reliable evaluation of adversarial robustness with ensemble of diverse parameter-free free attacks, In Proceedings of the 37th International Conference on Machine Learning, 2020.
Z. Cvetkovski. Hölder's Inequality, Minkowski's Inequality and Their Variants, pages 95-105. Springer Berlin Heidelberg, 2012. doi: 111100/9778-3362-23799999
Duchi, S. Shalev-Shwarzz Singer, and Chandra. Efficient projections onto the 1-ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pages 272-279. 2008
J. Engel, C. Resnick, A. Roberts, S. Dieleman, D. Eck, K. Simonyan, and M. Norouzi. Neural audio synthesis of musical notes with wavenet autoencoders, 2017.
M. Fazlyab, A. Robey, H. Hassani, M. Morari, and G. Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in neural information processing systems (NeurIPS), 2019.
H. Federer. Geometric measure theory. Springer, 2014.
10

---

Published as a conference paper at ICLR 2022
R.
N. Dowlin, K. Laine, K. Lauter, M. Nachrig, and J. Wernsing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In M. F. Balcan and K. Q. Weinberger, editors, Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 201-210, New York, New York, USA, 20-22 Jun 2016. PMLR.
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In COLT, 2018.
J. Goodfellow, Shlens, and C. Szegedy. Explaining and hamesssing adversarial examples. In International Conference Learning Representations (ICLR), 2015.
Hesamifard, H. Takabi, M. Ghasemi, and Wright. Privacy- preeeccpreseriing machine learning as a service. Proc. Priv. Enhuncing Technol., 201 133)1123- 2018.
Hoffmman, D. A. Roberts, and Yaida. Robust learning with jacobian regularization, 2019.
S. M. Jayakumar, W. M. Czamecki, J. Menick, J. Schwarz, J. Rae, S. Osindero, Y. W. Teh, T. Harley, and R. Pascanu. Multiplicative interactions and where to find them. In International Conference on Learning Representations (ICLR), 2020.
T. Karras, S. Laine, and T. Aila. A style-based generator architecture for generative adversarial networks. In Conference on Computer Vision and Puttern Recognition (CVPR), 2019.
I. Saamellmacher-Shizeemaaa S. M. Seitz, D. Miller, and E. Brossard. The megaface benchmark: 1 million faces for recognition at scale. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4873-4882, 2016.
G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM review, 51(3):455-500, 2009.
A. Krizhevsky, V. Nair, and G. Hinton. The cifar-10 dataset. online: http://www. cs. toronto. edu/kriz/cifar himl, 55, 2014.
Latorre, P. Rolland, and V. Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In International Conference on Learning Representations (ICLR), 2020.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-231) 1998. doi: 10. 10.1109/5.72679.
Liao, M. Liang, Dong, T. Pang, X. Hu, and Zhu. Defense against adversarial attacks using high-level representation guided denoiser. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018
T. Lyche. Numerical Linear Algebra and Matrix Factorizations. Springer, Cham, 2020.
T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, edition, 2018. ISBN 978-0- 262-03940-6.
B. Neyshabur: Implicit regularization deep learning. arXiv preprint arXiv: veXiiv:/09..00 /70::0/999.9933 2017.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR. 2015.
B. Neyshabur, S. Bhojanapalli, and N. Srebro. pac-bayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint 1rX1v:1707.09564. 2017.
C. R. Rao. Estimation of heteroscedastic variances in linear models. Journal of the American Statistical Association, 611329): 1970. doi: 10. 1970
11

---

Published as a conference paper at ICLR 2022
K. Scaman and A. Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in neural information processing systems (NeurIPS), 2018.
S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. ISBN 1107057132.
V. Slyusar. A family of face products of matrices and its properties. Cybernetics and Systems Analysis, 35(3):379-384, 1999.
J. Su, W. Byeon, J. Kossaifi, F. Huang, J. Kautz, and A. Anandkumar. Convolutional tensor-train Istm for spatio-tempora learning. Advances in neural information processing systems (NeurIPS), 2020.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
Y. Tsuzuku, I. Sato, and M. Sugiyama. Lipschitz-margin training: Scalable certification of perturba- tion invariance for deep neural networks. S. Bengio, Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc., 2018
X. Wang, R. Girshick, A. Gupta, and K. He. Non-local neural networks. In Conference on Computer Vision and Pattern Recognition (CVPR), pages 7794-7803, 2018.
H. Xiao, K. Rasul, and Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747. 2017.
C. Xie, Y. Wu, L. v. d. Maaten, A. L. Yuille, and K. He. Feature denoising for improving adver- sarial robustness. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
Y. Yoshida and T. Miyato. Spectral Norm Regularization for Improving the Generalizability of Deep Learning. arXiv e-prints, art. arXiv:1705.1099 May 2017.
H. Zhang, Y. Yu, J. Jiao, E. Xing, L. E. Ghaoui, and M. Jordan. Theoretically principled trade-off between robustness and accuracy, In Proceedings of the 36th International Conference on Machine Learning, 2019.
12

---

Published as a conference paper at ICLR 2022
A
APPENDIX INTRODUCTION
The Appendix is organized as follows:
The related work is summarized Appendix B.
In Appendix C the notation and the core Lemmas from the literature are described.
Further details on the Polynomial Nets are provided in Appendix D.
The proofs on the CCP and the NCP models are added in Appendix E and Appendix respectively.
The extensions of the theorems for convolutional layers and their proofs are detailed in Appendix G.
Additional experiments are included in Appendix H.
B RELATED WORK
Known bounds for the class of polynomials are consequence of more general result for kernel methods (Mohri et al., 2018, Theorem 6.12). Support Vector Machines (SVMs) with polynomial kernel of degree & effectively correspond to general polynomial with the same degree. contrast, our bound tailored to the parametric definition of the CCP and the NCP models, which are subset of the class of all polynomials. Hence, they are tighter than the general kernel complexity bounds.
Rademacher Complexity:
Bounds for the class of neural networks were stablished in (Bartlett et al., 2017: Neyshabur et al., 2017), but they require a long and technical proof, and in particular it assumes an 2z-bound on the input, which is incompatible with image-based applications. This bound also depend the product of spectral norms of each layer. In contrast, our bounds are more similar in spirit to the path-norm- complexity bounds (Neyshabur et al., 2015), they depend interactions between neurons different layers. This interaction precisely corresponds to the face-splitting product between weight matrices that appears Theorem
Lipschitz constant: A variety of methods have been proposed for estimating the Lipschitz constant of neural networks. For example, Scaman and Virmaux (2018) (SVD), Fazlyab al. (2019) (Semidef- inite programming) and Latorre et al. (2020) (Polynomial Optimization) are expensive optimization methods to compute tighter bounds on such constant. These methods are unusable in our case as they would require a non-trivial adaptation to work with Polynomial Nets. In contrast we find an upper bound that applies such family of models, and can be controlled with efficient -xe-rrrat norm projections. However, our bounds might not be the tightest. Developing tighter methods to bound and control the Lipschitz constant for Polynomial Nets is promising direction future research.
C BACKGROUND
Below, we develop detailed notation in Appendix C. we include related definitions in Appendix C.2 and Lemmas required for our proofs in Appendix C.3. The goal of this section cover many of the required information for following the proofs and the notation we follow in this work. Readers familiar with the different matrix/vector products, e.g., Khatri-Rao face-splitting product, and with basic inequalities, e.g., Hölder's 's inequality, can skip to the next section.
C.1 NOTATION
Different matrix products and their associated symbols are referenced in Table 4, while matrix operations on a matrix are defined on Table 5. Every matrix product, e.g., Hadamard product, can be used in two ways: a) A B, which translates to Hadamard product of matrices A and B, b) N A, abbreviates the Hadamard products A o A o.....4 AN-
N products
The symbol of refers to 7th element of vector a;;-
13

---

Published as a conference paper at ICLR 2022
Table 4: Symbols for various matrix products. The precise definitions of the products included in Appendix C.2 for completion.
Symbol
Definition
Hadamard (element-wise wisee) product.
Column-wise Khatri-Rao product.
Face-splitting product.
Kronecker product.
Convolution.
Table 5: Operations and symbols on matrix A.
Symbol
Definition
[
operator-norm; corresponds to the maximum -n-ormm of its rows.
A'
1th row of A.
0i
(i element of A.
Aij The i-th matrix set of matrices (A1,' A
(i, block of block-matrix A
A,
C.2 DEFINITIONS
For thoroughness, include the definitions of the core products that use in this work. Specifically, the definitions of the Hadamard product (Definition 3), Kronecker product (Definition 4), the Khatri- Rao product (Definition 5), column-wise Khatri-Rac product (Definition 6) and the face-splitting product (Definition 7) are included.
Definition (Hadamard product). For two matrices A and of the same dimension m x n, the Hadamard product A B is matrix of the same dimension the operands, with elements given by
(a b)t,j = 01.3bi5-
Definition 4 (Kronecker product). If A is an m x n matrix and B is a x q matrix, then the Kronecker product & B is the pm qn block matrix, given as follows:
a
01 B
A B
0m,1
Om B
Example: the Kronecker product of the matrices A R2x2 and B R222 is computed below:
Te.1bb,1
a1,2b1.2 01,1b2,2
01.1b1,2
41,2b1,1
01,1
01.2 02,2
b
b1.2
01,1b2,1
01,222,1
a1,2b2.2
02,1
b2.1
b2.2
02,11111
02,201.2 021b2,
221
02221,
022122,1
022222
02,2b2,2
A&B
Definition 5 (Khatri-Rao product). The Khatri-Rao product is defined as:
A = (Ats X Big)s.j
in which the (i, block is the m.p; X nzjj sized Kronecker product of the corresponding blocks of A and B, assuming the number of row and column partitions of both matrices is equal. The size of the product is then (E, m.p:) ) x
Example: if A and B both are partitioned matrices e.g.:
A
A
01.1
01,2
01,3
A
A
A
Q2.1
02.2
02,3
03,1
0322
03.3
14

---

Published as a conference paper at ICLR 2022
b1.1
bi.2
b1,3
B
B
B
2g11
22,2
22,3
B2.1
B,,2
13.1
b3.2
b3.3
then we obtain the following:
01,1 b1,1
01,2b1,1
01,ab1.2
01,3b1,3
A1,1 @ B1.1
A1,2 89 B1.2
02 11,1
02,2
02,301,2
02,3b1.3
A B
A2,1 0 B2,1
22, 30 B2.2
03, 19,1
03,2
03,3/2,2
03,302,3
03,1
03,2b3,1
03,303,2
03,3b3,3
Definition 6 (Column-wii) wise Khatri-Rao product). column-wise Kronecker product of two matrices may also be called the Khatri-Rao product. This product assumes the partitions of the matrices are their columns. In this case my = m, Pı = p. n and for each nj = Pj The resulting product is mp matrix of which each column is the Kronecker product of the corresponding columns of A and B.
Example: the Column-wise Khatri- Rao product of the matrices A E R22x3 and 33x3 is computed below:
21,2b122
01,301.3
01,2b2.2
01,322,3
Tb1.1
b122
b
01,1
112
01,3
b2,1
b2,2
b
01,103,
21,2b3,2
01,3b3,3
02.1
222
(2,,3
by.1
b3.2
by.3.
02.2b12
02,3b1,3
22.12.11
22,222.2
02,322.3
B
02,1b3,1
02,2b3.2
02,333,3
A=B
From here on, all refer to Column- wise Khatri-Rao product.
Definition 7 (Face-splitting product). The alternative concept of the matrix product, which uses row-wise splitting of matrices with a given quantity of rows. This matrix operation was named the face-splitting product of matrices or the transposed Khatri-Rao product. This type of operation is based on row-hy-row Kronecker products of two matrices.
Example: the Face-splitting product of the matrices A E 3x3x2 and B E 3x3x2 is computed below:
11,1
01,2
Tb1,1
b1,2
Ta 11,1
01,201,1 22,222,1
01 i1,1 b1,2
01,2 02, b2.2
2221
03.2
b2.1
22.2
=
02,1
02,222,2 03,203,2_
03,1
03.2.
(ba
b
L3,,bb,1
23,2
03 ba.2
A
C.3 WELL-KNOWN LEMMAS
In this section, we provide the details on the Lemmas required for our proofs along with their proofs the corresponding citations where the Lemmas can be found well.
Lemma 3. (Federer, 2014) Let h be two composable Lipschitz functions. Then h is also Here and only here o represents function composition. Lemma 4. (Federer, 2014) Let f X C R2 + m be differentiable and Lipschitz continuous. Let (x( denote its total derivative (Jacobian) at Then Lip, suppex [|Jr(x)]], where
Lipschitz with Lip(g o h) S Lip(g)
1 is the induced operator norm on (x)
Lemma 5 (Hölder's inequality). (Cvetkovski, 2012) Let (5, E.E. be measure space and let Then, for all measurable real-valued functions f and g on S.
p. g [1. with +
holds that:
|| & [I 1gll,
15

---

Published as a conference paper at ICLR 2022
Lemma 6 (Mixed Product Property 1). (Styusar. 1999) The following holds:
(1, (A.Ba) (A1 (2) B2).
Lemma (Mixed Product Property 2). The following holds:
(A - (A,) + (B:).
Proof. We prove this lemma by induction on N. Base case (NV 1): A, B1.
Inductive step: Assume that the induction hypothesis holds for a particular k i.e. the case N holds. That can be expressed as:
(A,B,) = * (B.).
(3)
Then we will prove that it holds for N = +
k+1 (A,B:)
==
oo
(A, (A++1 Bx+1)
(A,,)
k 1=1 [B:) (As+1 BB-1) use inductive hypothesis (Eq. (3))
(A,) A A (B:) B&t1] Lemma 6 [Mixed product property 1]
(A.) (B:).
That is, the case l: + also holds true, establishing the inductive step.
Lemma 8 (Massatt Lemma. Lemma 26.8 in Shalev-Shwartz and Ben-David (2014)). Let A
="a ,aN} be a finite vectors in R Define = Ei= ag Then:
R(A) max a all /2 N aEA
m
Definition 8 (Consistency of matrix norm). A matrix norm is called consistent C if
AB ||||] BI|
holds for A, E CD.R.
Lemma (Consistency of the operator norm). (Lyche, 2020) The operator norm is consistent if the vector norm II-II is defined for all m E N and [1-1|g = Il-Ila
Proof.
|ABx
|A lla
Ba
lla
AB
max
Bry0
||0||a
Bay0
|Bx ll.
| lx
||
Bx:
Ba:la
max
max
|||||
[
|
#/0
x
Lemma 10. (Rao, 1970)
(AC) (BD) @ D).
D DETAILS ON POLYNOMIAL NETWORKS
In this section, we provide further details on the two most prominent parametrizations proposed in Chrysos et al. (2020). This re- parametrization creates equivalent models, but enables us absorb the bias terms into the input terms. Firstly, we provide the re- paraametitiizioonn of the CCP model in Appendix D.1 and then we create the re-parametrization of the NCP model in Appendix D.2.
16

---

Published as a conference paper at ICLR 2022
D.1 REPPARAMETRIZATION OF CCP MODEL
The Coupled oP-Decomposition (CCP) model of PNs (Chrysos et al., 2020) leverages a coupled CP Tensor decomposition. k-degree CCP model f(C) can be succinctly described by the following recursive relations:
yi ViS, Y, - (VaC) o yn-l Yn-1,
f(() Qyx + +
where Ç E IR is the input data with 6 E N. f(() E Ro is the output of the model and V, E R Q Rox and [3 IR are the learnable parameters, where μ N is the hidden rank. In order to simplify the bias terms in the model, we will introduce a minor re-parametrization in Lemma 11 that we will use to present our results in the subsequent sections.
Lemma 11. Let z 1s 1]T Rd. Dn = [ 1]T R", C = [Q, E Roxm d _ex 1,m= Define:
VI U = 0
V
1 1
E mRdd
U.
E
RRmx
(i> 1).
where the boldface numbers O and 1 denote all-zeros and all-ones column vectors of appropriate size, respectively. The CCP model in Eq. (4) can be rewritten as f(z = C o U.z, which the one used in Eq. (CCP).
As reminder before providing the proof, the core symbols for this proof are summarized in Table
Table 6: Core symbols in the proof of Lemma 11.
Symbol Dimensions
Definition
Hadamard (element-wisse product.
C
R
Input of the polynomial expansion.
f(()
RR
Output of the polynomial expansion.
k
N
Degree of polynomial expansion.
m
N
Hidden rank of the expansion.
V
R
Learnable matrices the expansion.
Q
Rox
Learnable matrix of the expansion.
B
IR
Bias of the expansion.
Rd
Re- Re-parametrization of the input. C (Q.3).
C
Roxm
Proof. By definition, we have:
2e = 1yv [
y/1
V1C
Vi
0 1
C
Vi
[CT,
1] U
1
0
O
In = [y
1
Vn
(VnC)
In- + Yn
V. + 1
o リn
1
1
1
V 1
c
Yn-1
Va
0
1
1
15
1]
I 1]
- 2x
Hence, it holds that:
f(z) Qui + B = (Q,3)
yk
= CC
1
CU22 08-1 06-1
C 12) 0 2x
C (Ut-1z) o (U2))
C (Up-12) (U2)) (U12)
C (Uiz).
17

---

Published as a conference paper at ICLR 2022
D.2 REPARAMETRIZATION THE NCP MODEL
The nested coupled CP decomposition (NCP) model of PNs (Chrysos al., 2020) leverages a joint hierarchical decomposition. A k-degree NCP model f(C) is expressed with the following recursive relations:
o (b.),
yn = (V.C) (U, b,),
f(C) = Qyı + B.
(5)
where Ç E R is the input data with 6 E N. f(C) E R the output of the model and V E Rax b, R Un RO* Q E Rxx and B E Rº are the learnable parameters, where μ N the hidden rank. order to simplify the bias terms in the model, we will introduce a minor re-parametrization in Lemma 12 that will use present results in the subsequent sections.
Lemma 12. Let = (sT,1] RR an = yn 1] IR" m C [Q,
Rexm + 1,m
#+1 1. Let:
U
bi 1
V 0'
81 = =1bb]11] ER",
S =
E R MRX (i> (R
A; =
E
Rad
where the boldface numbers and 1 denote all-zeros and all-ones column vectors of appropriate size, respectively. The NCP model in Eq. (5) can be rewritten as
41 (A1z) (81);
Tr = (Anz) (Sn
[(z) = Crrk
(6)
In the aforementioned Eq. (6), have written Sn even for 1, when s1 is technically vector, but this is done for convenience only and does not change the end result.
E
RESULT OF THE CCP MODEL
E. PROOF OF THEOREM 1: RADEMACHER COMPLEXITY BOUND OF CCP UNDER &oo NORM
To facilitate the proof below, we include the related symbols in Table Below, to avoid cluttering the notation, consider that the expectation is over and omit the brackets well.
Table 7: Core symbols for proof of Theorem 1.
Symbol
Dimensions
Definition
Hadamard (element-wise) product. Face-splitting product.
Column- wise Khatri-Rao product.
Rd
Input of the polynomial expansion.
f(z)
R
Output of the polynomial expansion.
Degree of polynomial expansion.
N
Hidden rank of the expansion.
U
IR
Learnable matrices.
R 1m
Learnable matrix.
1
R
| p..
A
R
(U:)) S X.
18

---

Published as a conference paper at ICLR 2022
Proof.
R2 R2( = E sup
Σ 0zf(zz)
fEF
j=1
E sup FEP
Σ
(az (c, (
j=1
oy /0 (U12))
sup
c,
/EP
/=1
< E sup
|cl
Σ 1, (Uiz})
Lemma 5 [Hölder's inequality]
fEF
E sup FE
|c|
Σ oj (U,) #=1 (z,)
Lemma 7 [Mixed product property]
/=1
E sup fEPl
|c||
L (U)) Σ
Jo == (zz))
E sup fEPt
|c|1
Σ og + (z,)l
E
o # (zy)]
n
Next, we compute the bound of IE Ey * (2/))
Let Zj (zz) Rdt For each e [d*1, let ii (Z).... ,,,) RR. Note that ||0/||2 5
vn max, |2 Let V (vi,..., Daz Then, it is true that:
E
b o
==1
[z,)
=E
0 3
E max
d
Σ og (w1)
=nR(V).
(8)
Using Lemma [Massart Lemma] we have that:
R(V) 2 max 1Z V /loog (d.
(9)
19

---

Published as a conference paper at ICLR 2022
Then, it holds that:
R2 (F((P = E sup
-
1
Σ
0zf(2z)
f
n
==1
1Ad
E
Σ ooy * (zj))
Eq. (7)
71
nd
nR(V)
Eq. (8)
(10)
S 2pd max 1y )2log(d))/n
Eq. (9)
| (25) ol / log (dt))
2udmax
s 2pM(max | )a V 2 log (dt)/n n s 2 2k log (d)/n.
3
E.2 PROOF OF LEMMA
Table 8: Core symbols in the proof of Lemma
Symbol
Dimensions
Definition
Kronecker product.
Face-splitting product.
Rd
Input of the polynomial expansion.
/
2
IR
Output of the polynomial expansion.
k
N
Degree of polynomial expansion.
m
N
Hidden rank of the expansion.
U
R
mmmxd
Learnable matrices.
U
Rd
jth row of U.
A
lk
U.
S X for 1,2, 1.2....KR R.
Proof.
(U:)
max J
m
(U))))
max
[
Definition of Face-splitting product
1=1
max ==1
Multiplicativity of absolute value
max
k:
UU lloe
E.3 RADEMACHER COMPLEXITY BOUND UNDER E NORM
Theorem 6. Let 7 = (zi...., 2n} C Rdd and suppose that ||2 f all j = 1,..., n. Let
Flop= = (ʃ(=) (c, of U1z) ||c||2 & n. _ $1].
20

---

Published as a conference paper at ICLR 2022
The Empirical Rademacher Complexity of CCPs (k-degree CCP polynomials) with respect Z is bounded as:
ai Vn
Rz( 2
To facilitate the proof below, we include the related symbols in Table 9, Below, to avoid cluttering the notation, we consider that the expectation over and omit the brackets well.
Table 9: Core symbols for proof of Theorem 6.
Symbol Dimensions
Definition
Hadamard (element-wise product. Face-splitting product.
Column-wise Khatri-Rao product.
2
Rd
Input of the polynomial expansion.
f(2)
IR
Output of the polynomial expansion.
k
N
Degree polynomial expansion.
N
Hidden rank of the expansion.
U.
Rmxd
Learnable matrices.
C
R Ilxm
Learnable matrix.
R
||c||2 S p.
A
IR
(U:) S X.
Proof.
n
Rz(F(cp) = E sup
(z,)
JEF
j=l
E sup
Σ
(c. - (U,z,)))
fEFt
j=1
E sup
c,
Jo (
feft
< sup /EFt
|cl/
Σ f
(12;))
Lemma [Hölder's inequality]
sup fe
|clp
Σ 0
(U,)
# (2,)
Lemma [Mixed product property]
1=1
sup fEFt
|cl2
(U)) >
Jo
* 1=1
(zy)
1=1
2
sup f
|cl2
Σ Jo + (zy)
+ UU.
21

---

Published as a conference paper at ICLR 2022
E
# ==1
[z))]
=E
Σ
(z₁)]
E
oj
#==1 (zz)]
Jensen's 's inequality
n
E
1 * (2₂))]
(11)
s,j
(z)
1
j=1
A
S vn.
So:
R2 (F(ce)
S E sup
1
|c||
Σ
oo + (z))
(())) 1
feT
sup
||e||2 + (U))
و
Vn
pd
Vn
E.4 LIPSCHITZ CONSTANT BOUND OF THE CCP MODEL
We will first prove more general result about the fp- Lipschitt constant of the CCP model. Theorem 7. The Lipschitz constant (with respect the fn-norm) of the function defined in Eq. (CCP). restricted to the set (z E Rdd ||=||pp S 1} is bounded as:
Lip, S. C| II U.llp
Proof. Let g(x) = Ca and [((2) = (U, Then it holds that f(x) g(h(2)). By Lemma we have: Lip,( < (g) (h). We will compute an upper bound of each function individually.
Let us first consider the function g(x) Ca. By Lemma 4, because g is linear map represented by a matrix C, its Jacobian is Tz(x) C. So:
Lip (g) ||C||p := sup ||=||,=1
||Cx|pp
where ||C|lp is the operator norm on matrices induced by the vector p-norm.
Now, let consider the function h(z) ot U... Its Jacobian is given by:
dh k
dz (0)
22

---

Published as a conference paper at ICLR 2022
Using Lemma 4 we have:
(h) sup * <1
diag diag(o)/s((
sup o (Ug=)) (
Triangle inequality
=
sup
ddiag( g (U,z))lIp |U:
Lemma 9 [consistency]
sup
1o (U,=)lp |0::
x: =1 i=1
((1 |
sup
i=1 jز =1 S
sup
( II || 1U:
=1||+|| SI
i=1 j
s sup
EI
x: *|| S1 1=1
1,,1,
j=1
So:
Lip,(FL) s (t)p
&
s |||| II U1
E.4.1 PROOF OF THEOREM
Proof. This is particular case of Theorem 7 when p oc.
23

---

Published as a conference paper at ICLR 2022
F RESULT OF THE NCP MODEL
F.1 PROOF OF THEEORM 3: RADEMACHER COMPLEXITY OF NCP UNDER &oo NORM
Proof.
1 n fz(zz))
R2((FeP)
E sup fer
TI j=1
E sup FEF
(az (c, a (2;)))
T1
j=1
E sup NCP
a (z))]
1
12
S E sup fEF NCP n
||c||
[0))
Lemma 5 [Hölder's inequality]
1
E sup fEF NCP
||c||
Σ (a)(())))) o (S
71
1
E sup FEF MC
||c|
Σ [ay((As Sx)(2z * xk 1 (z,)))
Lemma [Mixed product property)
n
/=1
1
n
E sup fE NEP
||ch
(As
Sk)
Σ [a, 0b-
T1
j=1
(12)
Now, because the recursive definition of the Eq. (NCP), we obtain:
وz * xg- (2,)) =
Σ
oz * (A--1z;) (S xz 2(2,)))
j=l
Σ
dz(2] * ((A Sz-1) 22,)))))))
Lemma 7
j=l
Σ j=1
oj [I 2 (Aa-1 Sx-1)) (z) xx-2(2z)))
Lemma 10
(A Sk-1) Σ Jo, * (z) 2z)2(2z))) )))
(13)
recursively applying this argument we have:
h-1 I| I A, . S.
Eo th (zz)
Σ 0, * 2 12)))
(14)
Combining the two previous equations (Eqs. (13) and (14) inside Eq. (12) we finally obtain
24

---

Published as a conference paper at ICLR 2022
Rz((NeP) (CP) S E sup
1
|c||
(A Sx))
II A. S
Eo ;=1 (2))
SEFNI 71
8
S E sup
1
|c||
(A Sk)
I A, S
Σ oj 1= (zz)
fEF
71
Ad
E
jj 1=1 (2/)
71
pd nR(V) μXR(V).
Eq. (8).
following the same arguments as in Eq. (10) it follows that:
log (d)
R2 (F S V
n
F.2
PROOF OF LEMMA 2
Proof.
(A& Sa) II A S.
1 Sk
Ø A; - S:ll oo
Lemma 9 [consistent]
1=1
A, Silla
AAl1oo |
Lemma 1.
1=1
F.3 RADEMACHER COMPLEXITY UNDER & NORM
Theorem 8. Let Z = (z1,..., 2n} C Rd and suppose that || < for all j = l,..., Define the matrix (AAi, Si..... An, Sa) (Ax St) IT-=] & S Consider the class functions:
Fhipp= = (f(z) as in (NCP): : ||C||2 S n. (b Si...., A.. Sw)l S {}
where C E R1xm (single output case). The Empirical Rademacher Complexity of NCP (k-degree NCP polynomials) with respect Z is bounded
41
Rz (J
NCP) <
vii
25

---

Published as a conference paper at ICLR 2022
Proof.
1
Rz R2( = E. sup
o (22)
feJ NCP
j=l
E sup feF
(o (z,)))
E sup
C2
o ,
feJ NC
n2
j=1
1
< E sup fe
||c|2
2 o (z)))
Lemma 5 [Hölder's inequality]
1
E sup Sr
||c|2
2 or ((A (S,xx-1(2))))
11
E sup fET NCP
||||
2 Joy ((A Sk)(2) xz- (2,)))
Lemma [Mixed product property]
1
E sup SEF n
||c|2
(Ac Sk) Diss(z (
j=l
2
1 ||||2
E sup fEF
(A₁ Sk)
I A . S
Σ
(2,)
Eq. (14)
1 ||||
12 Σ
E sup fEF
(A Sk)
II + A S
jj
*
-=1 (2,))
m
/=1
n1
Σ jr 1
(24)
7
n
Eq. (11).
Vn n
F.4 LIPSCUITZ CONSTANT BOUND OF THE NCP MODEL
Theorem 9. Let Fr, be the class of functions defined as
FL = x1 (A1z) o (Si), 2n = (Anz) (1)
Co
|C'| S n. 1.dll I A., 11 SP. $1 $1
The Lipschitz Constant of Fe (k-degree NCP potynomial) under Ep norm restrictions is bounded as:
(F)) < kp (A.p))
Proof. Let g(x) Ca. h(2)) (Anz)
Then it holds that f(z) = g(h(z)).
26

---

Published as a conference paper at ICLR 2022
By Lemma 3, have: Lip(f) Σ Lip(g)Lip(h). This enables to compute upper bound of each function (i.e., 9, h) individually.
Let us first consider the function g(x) Ca. By Lemma 4, because g is linear map represented by a matrix C, its Jacobian (g(x)) C. So:
max (C) max; Ej Co.
if p = 2
Lipp(0) = |C = sup
|Callp
||
if p
where ||Cllp is the operator norm on matrices induced by the vector p-norm, and F (C) is the largest singular value of C.
Now, let us consider the function I.,, (2) = h1(2) = (Anz) o - Its Jacobian is given by:
Ja,, = (izig(AA=)S,,ou
1)
Jay diag(Si)
Lipp(h)
sup
|| llp
>:||= 1,51
sup
|| diag(A, Snn + (
*:||> 1.51
sup
|| diagg( An S Jn Jl diag(S A
Triangle inequality
= 11$1
sup
diagg( An 2) 11 St, 11pppll.mmm--1 diag( diagg (5.
Lemma [consistent]
=:|= 1,
sup
A S 1
1
* 11
sup
[A.]Ial S.
11
| || [n- |
* 11
sup
11
11
S. 1p
[(An 1 21)llllll
=:||= 11
sup
|
|
|A,
1 n A l|p
2:||= 1,
sup
| 2l Am1lp
(111.111=111115.111.0.0.. .llp + ||A 1 11.
sup
z:| 1,51
n-1
sup
|| 11
II
=:| 1,51
Then we proof the result by induction. Inductive hypothesis:
sup =:1|=||pS1
|a llp
Case
Lipp(h)=
sup
|| llp
2:11 1-1
= || (diag(S$)440 lIp
|| (diag(Si))lb>) A llz
| Atll.
27

---

Published as a conference paper at ICLR 2022
Case k n2
(hp
sup
|| l1p
x:l 51
sup
| |/mlpl
1-1
R-1
II (1S Alp) + (15511144
sup
S ||
2=1
So:
Lipp(Ft) S Lip,
&
< || II (
F.4.1 PROOF OF THEOREM 4
Proof. This is particular of Theorem 9 with p
G RELATIONSHIP BETWEEN A CONVOLUTIONAL LAYER AND A FULLY CONNECTED LAYER
In this section we discuss various cases of input/output types depending on the dimensionality of the input tensor and the output tensor. We also provide the proof of Theorem 5.
Theorem 10. Let E Rd, Let K Rh 1-D convolutional kernel. For simplicity, we assume h is odd and h convolutional operator i.e., the linear operator (matrix) U E Raxn such that B K A It holds that |U ||||
Let B E R" B K + A be the output of the convolution. Let U be the
Theorem 11. Let A == and let K Raxh be a 2-D convolutional kernel. For simplicity assume h is odd number and < min(n, m). Let B Ruxm, B = K A be the output of the convolution. Let U be the convolutional operator i.e., the linear operator (matrix) U E R such that vec( B) Uvec( A). It holds that |Ul| = =]]vec(K]]], (K)l,-
G.1 PROOF OF THROREM 10
Proof. From, B + A = U A we can obtain the following:
U1.1
U122
U1n
1221
12,2
U2n
(A1 1A..... (A"...,A")) AT) (K) KhOT (A .A " T
14,11
Un,2
un.
We observe that:
K A+1 +j
if li <
Wij
0
if j-i-
28

---

Published as a conference paper at ICLR 2022
Then, it holds that:
n
|U
= max 1=1
72 S
max
KJ = K
11
1=1
==1
G.2 PROOF OF THEBREM 11
Proof. We partition U into partition matrices of shape m x m. Then the (i. partition matrix (i.s) describes the relationship between the B and the A So, U(..)) also similar the Toeplitz matrix in the previous result.
M M
if j j <
2
((S)))
l j| >
h-1
2
Meanwhile, the matrix M satisfies:
kic A- +1-
if 5
h-1
m)(a,))
0
if 1|
Then, have the following:
h
| max
max
1
S
max
K
=
Σ
||
K
||vve
K
||
==1
1=1
In addition, by h < h < m we have:
h = Σ
| |
K
(15)
Then, it holds that || Eín || K |
L
G.3 PROOF OF THEOREM 5
Proof. We partition into X r partition matrices of shape nm x nm. Then the (i, partition of the matrix ((.) describes the relationship between the 7th channel of B and the j channel of
A. Then, the following holds: (V,,))l = -h K Il. where K,j means the two wwo-dimensional tensor obtained by the third dimension of K takes and the fourth dimension of takes i.
axmxr
U max
Σ
Σ
max
max
Misamdlj+nma
1=0
{=1
==0 Ø=1
m
max 1=0
mx max iml
Juo (0-nm j+mms))
j=l
U Uat1otulll
max
U la
max 1=1
Ki ll
max
K
1=1
K
29

---

Published as a conference paper at ICLR 2022
Similar to Eq. (15): for every nm rows, we choose k+1 row. Then its 1-norm is equal to this nm Tows of the K s co-norm. So the equation holds.
H AUXILIARY NUMERICAL EVIDENCE
A number of additional experiments are conducted in this section. Unless explicitly mentioned otherwise, the experimental setup remains similar to the one in the main paper. The following experiments are conducted below:
1. The difference between the theoretical and the algorithmic bound and their evolution during training is studied in Appendix H.1.
2. An ablation study on the hidden size is conducted in Appendix H.2.
3. An ablation study is conducted the effect of adversarial steps in Appendix H.3.
4. We evaluate the effect of the proposed projection into the testset performance in Ap- pendix H.4.
5. We conduct experiments on four new datasets, i.e., MNIST, K-MNIST, E-MNIST-BY, NSYNTH in Appendix H.5. These experiments conducted in addition to the datasets already presented in the main paper.
6. In Appendix H.6 experiments three additional adversarial attacks, i.e., FGSM-0.01, APGDT and TPGD, are performed.
7. We conduct experiment using the NCP model in Appendix H.7.
8. The layer-wise bound (instead of single bound for all matrices) is explored in Ap- pendix H.8.
9. The comparison with adversarial defense methods is conducted in Appendix H.9.
H. THEORETICAL AND ALGORITHIIC BOUND
As mentioned in Section 3, projecting the quantity = f Up U/|l onto their level set corresponds to difficult non-convex problem. Given that we have an upper bound
0 = Up|la < IU 7.
we want to understand in practice how tight is this bound. In Fig. we compute the ratio 3 for PN-4. In Fig. the ratio is illustrated for randomly initialized matrices (i.e., untrained networks).
H.2 ABLATION STUDY ON THE HIDDEN SIZE
Initially, explore the effect of the hidden rank of PN-4 and PN-10 on Fashion-MNISTT. Fig. exhibits the accuracy on both the training and the test-set for both models. We observe that PN-10 has better accuracy the training set, however the accuracy the test set is the same in the two models. We also note that increasing the hidden rank improves the accuracy on the training set, but not on the test set.
H.3 ABLATION STUDY ON THE EFFECT OF ADVERSARIAL STEPS
Our next experiment scrutinizes the effect of the number of adversarial steps on the robust accuracy. We consider in all cases a projection bound of 1, which provides the best empirical results. We vary the number of adversaria steps and report the accuracy in Fig. 7. The results exhibit similar performance both in terms of the dataset (i.e., Fashion-MNIS. the network (PN-4 and PN-Conv). Notice that when the adversarial attack has more than 10 steps the performance does not vary significantly from the performance at 10 steps, indicating that the projection bound is effective for stronger adversarial attacks.
and K-MNIST) and in terms of
30

---

Published as a conference paper at ICLR 2022
PN-4 Fashion-MNIST
PN-4 Fashion-MNIST
51000
54000
$2000
Nach
48000
48000
1.02
1.00
42000
10
10
40
50
Log of bound for each makris in regularization
Epochs
(a)
(b)
PN-4 K.NNIST
PN K-NIIST
52000
1.150
50000
1.125
48000
1.100
40000
1.075
1.080
44000
1.025
42000
1,000
-2
10
10
50
Log of bound for each makii regularization
Epochs
(c)
(d)
Figure Visualization of the difference between the bound results on Fashion- MNIST (top row) and K-MNIST (bottom row). Specifically, in (a) and (c) visualize the ratio 3 11,- || for
| U.
different log bound values for PN-4. In (b), (d) the exact values of the two bounds are computed over the course of the unregularized training. Notice that there is gap between the two bounds, however importantly the two bounds are increasing at the same rate, while their ratio close to
PN-10
Nidden rank
1.9
1.4
4.6
1.3
1.5
12-
1.1
1.2
1.0
12
of
Depth
(a)
(b)
Figure 5: Visualization of the ratio I I0. in a randomly initialized network (i.e., using normal
distribution random matrices). Specifically, in (a) we visualize the ratio for different log hidden rank values for PN-10. In (b) we visualize the ratio for different depth values for hidden rank 16. Neither of two plots contain any regularization.
31

---

Published as a conference paper at ICLR 2022
100
Actuncycsss
PHN-4-TOO PRIN-4-Train
70
59
Figure 6: Accuracy of PN-4 and PN-10 when the hidden rank varies (plotted in log-scale).
PN-4
PN-Conv
Ablation study on the effect of adversarial steps
Ab lalation study on the effect of adversarial steps
70
85
60
55
55
50
45
45
35
stops
(a)
(b) K-MNIST
Figure 7: Ablation study the effect of adversarial steps in Fashion-MNIST and K-MNIST. All
methods are run by considering projection bound of
32

---

Published as a conference paper at ICLR 2022
H.4 EVALUATION THE ACCURACY OF PNS
In this experiment, we evaluate the accuracy of PNs. We consider three networks, i.e., PN-4, PN-10 and PN-Conv, and train them under varying projection bounds using Algorithm Each model is evaluated on the test set of (a) Bushion-MNISS and (b) E-MNIST.
The accuracy of each method is reported in Fig. 8, where the x-axis is plotted log-scale (natural logarithm). The accuracy is better for bounds larger than (in the log-axis) when compared to tighter bounds (i.e., values less than 0). Very tight bounds stifle the ability of the network to learn, which explains the decreased accuracy. Interestingly, PN-4 reaches similar accuracy to PN-10 and PN-Conv in Fashion-MNIST as the bound increases, while in E-MNIST cannot reach the same performance the bound increases. The best bounds for all three models are observed in the intermediate values, Le., in the region of in the log-axis for PN-4 and PN-10.
PN-4
PN-10
PN-Conv
Fashion-MNIST
E-MNIST
100
80
Accuracy(2))
60
40
20
Log of Bound
Log of Bound
Figure 8: Accuracy of PN-4, PN-10 and PN-Conv under varying projection bounds (x-axis in log-scale) learned on (a) Fashion-MNIST, (b) E-MNIST. Notice that the performance increases for intermediate values, while it deteriorates when the bound is very tight.
We scrutinize further the projection bounds by training the same models only with cross-entropy loss (i.e., no bound regularization), In Table 10, we include the accuracy of the three networks with and without projection. Note that projection consistently improves the accuracy, particularly in the case of larger networks, i.e., PN-10.
PN-4
PN-10
PN-Conv
Method
Fashion-MNIST
No projection
87.28 + 0.18%
88.48 + 0.17%
86.36 0.21% 86.38 = 0.26%
Projection
87.32 = 0.14%
88.72 + 0.12%
E-MNIST
No projection
84.27 + 0.26%
89.31 + 0.09%
91.49 + 0.29%
Projection
84.34 + 0.31%
90.56 + 0.10%
91.57 - 0.19%
Table 10: The accuracy of different PN models on Fashion-MNIST (top) and E-MNIST (bottom) when trained only with SGD (first row) and when trained with projection (last row).
33

---

Published as a conference paper at ICLR 2022
H.S EXPERIMENTAL RESULTS ON ADDITIONAL DATASETS
To validate even further we experiment with additional datasets. We describe the datasets below and then present the robust accuracy in each case. The experimental setup remains the same in Section 4,2 in the main paper. As a reminder, we are evaluating the robustness of the different models under adversarial noise.
Dataset details: There are six datasets used in this work:
1. Fashion-MNIST (Xiao et al., 2017) includes grayseale images of clothing. The training set consists of 60, 000 examples, and the test set of 10, 000 examples. The resolution of each image is 28 x 28, with each image belonging one of the 10 classes.
2. E-MNIST (Cohen et al., 2017) includes handwritten character and digit images with a training set of 124, 800 examples, and test set of 20, 800 examples. The resolution of each image is 28 x 28. E-MNIST includes 26 classes. We also use the variant EMNIST-BY that includes 62 classes with 697, 932 examples for training and 116, 323 examples for testing.
3. K-MNIST (Clanuwat et al., 2018) depicts grayscale images of Hiragana characters with training set of 60, 000examples, and test set of 10, 000 examples. The resolution of each image is 28 x 28. K-MNIST has 10 classes.
4. MNIST (Lecun et al., 1998) includes handwritten digits images. MNIST has a training set of 60, 000 examples, and test set of 10, 000 examples. The resolution of each image is 28 x 28.
5. CIFAR-10 (Krizhevsky et al., 2014) depicts images of natural scenes. CIFAR-10 has training set of 50, 000 examples, and a test set of 10, 000 examples. The resolution of each RGB image is 32 x 32.
6. NSYNTH (Engel et al., 2017) is an audio dataset containing 305, 979 musical notes, each with a unique pitch, timbre, and envelope.
We provide a visualization' of indicative samples from MNIST, Fashion-MNIST. K-MNIST and E-MNIST in Fig. 9.
We originally train PN-4, PN-10 and PN-Conv without projection bounds. The results are reported in Table 11 (columns titled 'No proj') for MNIST and K-MNIST, Table 13 (columns titled "No proj') for E-MNIST-BY and Table 14 (columns titled 'No proj') for NSYNTH. Next, we consider the performance under varying projection bounds; the accuracy each case is depicted in Fig. 10 for K-MNIST, MNIST and E-MNIST-BY and Fig. 11 for NSYNTH. The figures (and the tables) depict the same patterns that emerged the two main experiments, i.e., the performance can be vastly improved for intermediate values of the projection bound. Similarly, we validate the performance when using adversarial training. The results Table 12 demonstrate the benefits of using projection bounds even in the case of adversarial training.
H.6 EXPERIMENTAL RESULTS OF MORE TYPES OF ATTACKS
To further verify the results of the main paper, we conduct experiments with three additional adver- sarial attacks: a) FGSM with 0.01, b) Projected Gradient Descent in Trades (TPGD) (Zhang et al., 2019), <) Targeted Auto-Projected Gradient Descent (APGDT) (Croce and Hein, 2020). In TPGD and APGDT, we use the default parameters for one-step attack.
The quantitative results are reported in Table 15 for four datasets and the curves of Fashion-MNIST and E-MNIST are visualized in Fig. 12 and the curves of K-MNIST and MNIST are visualized in Fig. 13. The results in both cases remain similar to the attacks in the main paper, i.e., the proposed projection improves the performance consistently across attacks, types of networks and adversarial attacks.
H.7 EXPERIMENTAL RESULTS IN NCP MODEL
To complement, the results of the CCP model, conduct experiment using the NCP model. That is, we use a th degree polynomial expansion, called NCP-4, for our experiment. We conduct an
"The samples were found in https: www.wwteenso..... www.oooor///tttteee/aaaaoao
34

---

Published as a conference paper at ICLR 2022
4
7
8
Adh
2
7
MNIST
Fashion MNIST
7
L22
a
(c) K-MNIST
(d) E-MNIST
Figure 9: Samples from the datasets used for the numerical evidence. Below each image, the class name and the class number are denoted.
35

---

Published as a conference paper at ICLR 2022
Clean
FGSM 0.1 1.1
PGD_ 01__0.11__00
_CD_0.1_0 2.1_0.01_20
PGD_0. 00__0..3003_____0010000033003030
PN-4
PN-10
PN-Conv
100
Accuracy(35)
60
40
0
Log of Bound
Log of Bound
Log of Bound
(a) K-MNIST
PN-4
PN-10
PN-Conv
100
80
Accuracy(3)
40
20
0
4
Log Bound
Log of Bound
Log of Bound
(b) MNIST
PN-4
PN-10
PN-Conv
100
80
Accuracy(%)
60
20
Log of Bound
Log of Bound
Log of Bound
(c) E-MNIST-BY
Figure 10: Adversarial attacks during testing on (a) K-MNIST (top), (b) MNIST (middle), (c) E-MNIST-BY (bottom) with the x-axis is plotted in log-scale. Note that intermediate values of projection bounds yield the highest accuracy. The patterns are consistent in all datasets and across adversarial attacks.
36

---

Published as a conference paper at ICLR 2022
Clean
FGSM 0.1
PGD_0.1_0.01_21
PGD PGD_0.3_00
2ee_0.3__000 _.3_0.03__0
PN-4
100
80
Accuracy(%))
60
40
20
0
1
0
2
3
4
Log of Bound
Figure 11: Adversarial attacks during testing on NSYNTH.
37

---

Published as a conference paper at ICLR 2022
Clean
FGSMO.01
APGDT
TPGD
PN-4
PN-10
PN-Conv
100
80
Accuracy(%5
60
20
2
4
Log of Bound
Log of Bound
Log of Bound
(a) Fashion-MNIST
PN-4
PN-10
PN-Conv
100
Accuracy(%)
60
40
4
0
Log Bound
Log Bound
Log Bound
(b) E-MNIST
Three new adversarial attacks during testing on (a) Fashion-MNIST (top), (b) E-MNIST (bottom) ) with the x-axis is plotted in log-scale. Note that intermediate values of projection bounds yield the highest accuracy. The patterns are consistent in both datasets and across adversarial attacks.
Figure 12:
38

---

Published as a conference paper at ICLR 2022
Clean
FGSMO.01
APGDT
TPGD
PN-4
PN-10
PN-Conv
80
Accuracy(%5
60
20
4
Log of Bound
Log of Bound
Log of Bound
(a) K-MNIST
PN-4
PN-10
PN-Conv
100
Accuracy(
60
40
0
2 Log of Bound
4
0
Log Bound
Log Bound
(b) MNIST
Figure 13: Three new adversarial attacks during testing on (a) K-MNIST (top). (b) MNIST (bottom) with the x-axis plotted in log-scale. Note that intermediate values of projection bounds yield the highest accuracy. The patterns are consistent in both datasets and across adversarial attacks.
39

---

Published as a conference paper at ICLR 2022
No proj.
Our method
Jacobian
L2
Method
K-MNIST
Clean
84.04 + 0.30%
84.23 + 0.30%
83.16 0.31%
84.18 0.44%
FGSM-0.1
18.86 +: 2.61%
35.84 1.67%
2 1:1::.10 1.30%
22.05 = 2.76%
PN-4
PGD-(0.1, 20, 0,01)
11.20 4.27%
40.26 1.36%
16.00
10.93 2.42%
PGD-(0.3, 20, 0.03)
24.75 1.32%
2.59%
2.70 1.26%
Clean
$7.904
88.80
88.73 0..63%
87.93 = 0.18%
FGSM-0.1
2.00%
26.90 1.02%
26.62 1.59%
PN-10
PGD-(0.1, 20, 0.01)
7.54
39.55 0.64%
11.50 + 1.35%
5.09 + 0.68%
PGD-(0.3, 20, 0.03)
0.05 0.04%
25.24
1.24 0.64%
0.19 0.12%
Clean
0.37%%
88.48 - 0.42%
86.57 + 0.46%
88.56 + 0.62%
FGSM-0.1
13.04
47.75 2..03%
14.16 3.05%
12.43 = 2.58%
PN-Conv
PGD-(0.1, 1, 20, 0.01)
10.81 1.25%
3.11% 45.68
12.05 + 0.82%
11.05 0.85%
PGD-(0.3, 20, 0.03)
6.91 + 2.04%
31.68 + 1.43%
7.54 + 1.39%
6.28 2.37%
MNIST
Clean
96.52 + 0.13%
06.62
95.88 + 0.16%
96.44 0.18%
FGSM-0.1
20.96 + 5.16%
2.41%
33.59 + 8.46%
26.07 5.64%
PN-4
PGD-(0.1, 20, 0,01)
14.23 + 5.39%
66.05 5..77%
20.83 = 5.64%
16.06 = 5.84%
PGD-(0.3, 20, 0.03)
2.59 + 2.01%
4.92 + 1.18%
4.26 + 2.44%
Clean
07.4610.111
97.63
97.36 1 0.05%
97.53 = 0.10%
FGSM-0.1
30.12 4.58%
1.28%
40.22 2.31%
28.77 = 2.41%
PN-10
PGD-(0.1, 20, 0.01)
9.70
1.17%
18.74 + 5.39%
10.91 2.32%
(GD- 0.03)
0.47 +: 0.53%
55.36 2.32%%
2.49 + 1.46%
0.44 + 0.29%
Clean
98.32 0.12%
9.140
97.88 0.12%
98.32 0.11%
FGSM-0.1
18.98 + 2.99%
67.50 6.22%
27.02 + 9.88%
23.77 = 5.58%
PN-Conv
PGD-(0.1, 20, 0,01)
12.57 + 2.81%
72.85 + 12.23%
13.96 + 2.57%
13.84 = 3.18%
PGD-(0.3, 20, 0.03) 10.57 + 4.08%
55.56 + 8.48%
10.22 + 0.52%
9.10 3.62%
Table 11:
Comparison of regularization techniques on K-MNIST (top) and MNIST (bottom). In each dataset, the base networks are PN-4, i.e., 4th degree polynomial, on the top four rows, PN-10, i.e.,
10th degree polynomial, on the middle four rows and PN-Conv, i.e., a 4th degree polynomial with convolutions, on the bottom four rows. Our projection method exhibits the best performance in all three attacks, with the difference accuracy to stronger attacks being substantial.
AT
Our method + AT Jacobian + AT
Le + AT
Method
Adversarial training (AT) with PN-10 K-MNIST
FGSM-0.1
70.93
0.46%
71.14 + 0.30%
64.48 + 0.51%
70.90 + 0.57%
PGD-(0.1, 20, 0.01)
60.94
0.71%
61.20 + 0.39%
57.89 + 0.31%
61.47 + 0.44%
PGD-(0.3, 20, 0.03)
30.77
0.26%
33.07 + 0.58%
29.96 + 0.21%
30.35 + 0.42%
Adversarial training (AT)
with PN-10 on MNIST
FGSM-0.1
91.89 0.30%
91.94 = 0.17%
87.85 + 0.27%
92.22 + 0.30%
PGD-(0.1, 1. 20, 0.01)
87.36 0.29%
87.38 + 0.37%
84.96 + 0.25%
87.26 + 0.49%
PGD-(0.3, 20, 0.03) 61.96 0.92%
63.96 + 1.02%
62.24 + 0.24%
62.44 0.76%
Table 12: Comparison of regularization techniques on (a) K-MNIST (top) and (b) MNIST (bottom) along with ad adversarial training (AT). The base network is a PN- 10, i.e., 10th degree polynomial. Our projection method exhibits the best performance in all three attacks.
experiment in the K-MNIST dataset and present the result with varying bound in Fig. 14. Notice that the patterns remain similar to the CCP model, i.e., intermediate values of the projection bound can increase the performance significantly.
H.8 8 LAYER- - BOUND
To assess the flexibility of the proposed method, assess the performance of the layer-wise bound. In the previous sections, we have considered using a single bound for all the matrices, i.e., || lo < X, because the projection for single matrix has efficient projection algorithms. However, Lemma 1 enables each matrix U, to have a different bound A₃ We assess the performance of having different bounds for each matrix U,.
40

---

Published as a conference paper at ICLR 2022
PN-4, PN-10 and PN-Conv on E-MNIST-BY
Method
No proj.
Our method
Clean
80.18 = 0.19%
80.26 0.17%
FGSM-0.1
3.65 + 0.76%
16.58 + 3.87%
PN-4
PGD-(0.1, 20, 0.01)
4.57 + 1.98%
19.77 4.42%
PGD-(0.3, 20, 0.03)
0.59 + 0.40%
10.13 + 2.08%
Clean
84.17 = 0.06%
85.32 0.04%
FGSM-0.1
11.67 = 1.21%
32.37 2.58%
PN-10
PGD-(0.1, 20, 0.01)
2.48 + 0.66%
31.22 2.32%
PGD-(0.3, 20, 0.03)
0.03 + 0.05%
18.74+0.779
Clean
85.92 + 0.08%
86.03 + 0.08%
FGSM-0.1
0.65 0.17%
29.07 + 2.72%
PN-Conv
PGD-(0.1, I, 20, 0.01) PGD-(0.3, 20, 0.03)
1.57 + 1.40%
31.06 + 4.70%
0.33 = 0.06%
23.93 + 6.32%
Table 13: Comparison of regularization techniques on E-MNIST-BY. The base network are PN-4, Le., 4th degree polynomial, the top four rows, PN-10, i.e., 10th degree polynomial, the middle four rows and PN-Conv, i.e., a 4th degree polynomial with convolution, on the bottom four rows. Our projection method exhibits the best performance in all three attacks, with the difference accuracy to stronger attacks being substantial.
Model Projection
PN-4
No-proj
Proj
Clean accuracy
80.25 + 0.27%
80.33 + 0.26%
FGSM-0.1
0.91 + 0.14%
22.25 + 0.04%
PGD-(0.1, 20, 0.01)
0.31 + 0.11%
22.27 + 0.00%
PGD-(0.3, 20, 0.03)
0.46 - 0.29%
20.38 + 2.30%
Table 14: Evaluation of the robustness of PN models on NSYNTH. Each line refers to different adversarial attack. The projection offers an improvement in the accuracy in each case; PGD attacks projection improves the accuracy by remarkable margin.
41

---

Published as a conference paper at ICLR 2022
Clean
FGSM 0.1
PGD_0. 001_0.01__20
PGD @GD_0.3_000 ___0000_000
K-MNIST
100
80
Accuracy(
60
40
20
0
-1
0
2
3
4
Log of Bound
Figure 14: Experimental result of K-MNIST in NCP model.
42

---

Published as a conference paper at ICLR 2022
No proj.
Our method
Method
Fashion-MNIST
FGSM-0.01
26.49
3.13%
58.09 1.63%
PN-4
APGDT
16.59 + 4.35%
50.83 + 1.55%
TPGD
26.88 + 6.78%
59.03 = 1.45%
FGSM-0.01
18.59
1.82%
60.56
1.06%
PN-10
APGDT
8.76 1 1.14%
51.93 = 1.91%
TPGD
14.53
1.49%
63.33 0.51%
FGSM-0.01
15.30 = 3.10%
55.90 = 2.60%
PN-Conv
APGDT
11.88
1.33%
53.49 0.72%
TPGD
14.50 + 1.59%
58.72 1 1.87%
E-MNIST
FGSM-0.01
13.40
5.16%
32.83 + 2.08%
PN-4
APGDT
9.33 + 4.00%
26.38 + 2.70%
TPGD
17.40 3.11%
34.68 - 1.92%
FGSM-0.01
14.47 = 1.80%
48.28 = 3.06%
PN-10
APGDT
10.13 0.93%
41.72 4.05%
TPGD
13.97 + 0.88%
47.44 3.62%
FGSM-0.01
4.71 1.10%
39.37 5.43% 5.43%
PN-Conv
APGDT
3.58 - 0.66%
30.43 + 4.87%
TPGD
4.08 + 0.33%
35.85 + 10.20%
K-MNIST
FGSM-0.01
23.31 5.34%
43.74 5.97%
PN-4
APGDT
6.97%
39.43 1.89%
TPGD
23.45
48.46 3.84%
FGSM-0.01
2.14%
50.99
3.52%
PN-10
APGDT
16.23 + 1.32%
41.46 + 3.85%
TPGD
22.63 0.99%
49.91 1.37%
FGSM-0.01
12.31 = 2.03%
52.58 - 6.80%
PN-Conv
APGDT
13.47 2.19%
42.94 = 1.68%
TPGD
2.51% 14.25
48.19 + 3.02%
MNIST
FGSM-0.01
34.14 7.63%
73.95 + 5.18%
PN-4
APGDT
29.88 + 9.47%
71.26
4.88%
TPGD
27.01 = 9.77%%
76.88 1 1.9881198%
FGSM-0.01
32.34 4.67%
7
PN-10
APGDT
19.55
1.72%
75.22 2.05% 2.05%
TPGD
28.11 + 3.87%
79.74 + 2.07%
FGSM-0.01
22.73 3.10%
69.83 = 8.91%
PN-Conv APGDT
17.95 - 3.39%
64.94 8.96%
TPGD
21.82 - 3.07%
66.47 + 11.83% 11.83%
Table 15: Evaluation of the robustness of PN models four datasets with three new types of attacks. Each line refers to different adversarial attack. The projection offers an improvement in the accuracy in each case.
We experiment PN-4 that we use five different candidate values for each A; and then perform the grid search on the Fashion- MNIST FGSM-0.01 attack. The results Fashion-MNIST in Table 16 exhibit how the layer-wise bounds outperform the previously used single bound The best performing values for PN-4 are A1 1.5, A2 A3 1.5, A μ 0.8. The values of A, the first few layers larger, while the value in the output matrix C' is tighter.
different projection bound for each matrix U, Specifically,
To scrutinize the results even further, we evaluate whether the best performing X can improve the performance in different datasets and the FGSM-0.1 attack. In both cases, the best performing ), can improve the performance of the single bound.
"The single bound is mentioned as "Our method' in the previous tables. In this experiment both 'single bound' and wliyer-wise bound' proposed.
43

---

Published as a conference paper at ICLR 2022
No proj.
Jacobian
L2 MNITT
Single bound
Layer-wise bound
Method
26.49 3.13% FGSM-0.01
39.88
4.59%
24.36 1.95%
58.09 1.63%
63.95 + 1.26% 55.14 + 3.65%
FGSM-0.1 12.92 + 2.74%
17.90 + 6.51%
13.80 + 3.65%
46.43 + 0.95%
K-MNIST
FGSM-0.01 23.31 + 5.34%
25.46 + 3.51%
27.85 + 7.62%
5.97%
49.61 + 1.44%
FGSM-0.1 18.86 + 2.61% 22.61 + 1.30%
22.05 + 2.76% 35.84 1.67%
47.54 + 3.74%
MNIST
FGSM-0.01 4 32.78 + 6.94%
29.31
3.95%
73.95 + 5.18%
79.23 + 3.65% 74.97 + 5.60%
FGSM-0.1 20.96 - 5.16% 33.59 + 8.46% 26.07 + 5.64% 64.09 - 2.41%
Table 16: Evaluation of our layer-wise bound versus our single bound. To avoid confusion with previous results, note that 'single bound' corresponds "Our method' in the rest of the tables in this work. The different X, values are optimized on Fashion-MNIST FGSM-0.01 attack. Then, the same A values are used for training the rest the methods. The proposed layer-wise wise bound outperforms the single bound by large margin, improving even further by baseline regularization schemes.
pro).
Single bound
Layer-wise bound Gaussiun denoising Median denoising Guided denoising
Fashion MNIST
FGSM-600 26.49 3.13% 58.09 1.3%
63.95 + 1.26%
18.80 + 3.08%
19.68 + 3.20%
29.69 + 5.37%
FGSM-0.1 12.92 + 2.74%
0.95%
55.14 3.65%
14.14 2.77%
14.02 + 1.5%%
22.94 + 5.65%
Table 17: Comparison of the proposed method against adversarial defense methods denoising (Xie et al., 2019) and guided denoising (Liao al., 2018). Notice that the single bound (cf. Appendix H.8 for details) already outperforms the proposed defense methods, while the layer-wise bounds further improves upon our single bound case.
feature
H.9 ADVERSARIAL DEFENSE METHOD
One frequent method used against adversarial perturbations are the so called adversarial defense methods. We assess the performance of adversarial defense methods on the PNs when compared with the proposed method.
We experiment on PN-4 Fashion-MNIST. We chose three different methods: gaussian denoising. median denoising and guided denoising (Liao et al., 2018). Gaussian denoising and median denoising are the methods of using gaussian filter and median filter for feature denoising (Xie al., 2019). The results in Table 17 show that in both attacks method performs favourably the adversarial defense methods.
44


Reviews:
[{"review_id": "xeS8pm2LC0", "reviewer": "Reviewer_GLBZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strength: The paper contributes both theoretically and empirically. It provides the first known generalization error bounds and Lipschitz constant bounds. Given its theoretical contribution, regularization schemes are proposed to boost the performance of PNs. \n\nWeakness: The theoretical contribution of the paper is useful but not significant. It finds ways to translate the complexity problem of CCP and NCP to functions of R(V) and uses Massart Lemma to complete the proofs, which is relatively less challenging. Most of my concern comes from the presentation of the paper: (list in order of the sections)\n1. The C in Equation NCP is capitalized but not in the appendix.\n2. The constraint on C in Equation 6 is not on infinity norm but should be on 1 norm.\n3. The reference order is messy in the paper (e.g. Table 1 appears before Table 2), making it hard to read.\n4. Figure 3 and Table 2 are never referred to (pls correct me if I am wrong), neither in the main text nor in the appendix.\n5. Appendix G, bullet point 5, did not mention CIFAR10.\n6. Appendix G.5, \"from all four datasets in Fig. 9\"? There are altogether 6 datasets as listed by the author right above that line.\n7. Appendix G.5, Table 11 is about MNIST and K-MNIST, not MNIST and E-MNIST.\n8. Although in the summary of main contributions, the author mentioned the sweet-spot for regularization parameter and accuracy robustness trade-off, there are little to no descriptions/explanations/justifications for them in the experiment section. The \"Log of Bound\" might be the regularization parameter that the authors were referring to, but still, the lack of sufficient descriptions of the data shown makes things hard to comprehend.\n\nBesides the problem of paper presentation, I have concerns about the overall performance of the method on more challenging datasets. From Figure 3 and Table 2, the accuracy of CIFAR10 seems low and there is no comparison with other baselines. Since the method seems to be sensitive to the regularization parameter, can the authors give intuitions or guidance on its choice? ", "summary_of_the_paper": "The paper derives empirical Rademacher complexity bounds for two variants of PN, along with their Lipschitz constants. The derived bounds motivate practical regularization schemes that are implemented based on projected gradient descent. Empirical results demonstrate the usefulness of the proposed method.", "summary_of_the_review": "Although the technical contribution of this paper is sound, the paper is not ready for publication due to the problems mentioned above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UTrhNBAIeEy", "reviewer": "Reviewer_opuA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Pros:\n- The Rademacher complexity bounds of the CCP and the NCP are derived. \n- The Lipschitz constants for the CCP and the NCP are derived.\n\nCons:\n\n1. Lemma 1 requires projecting $\\prod_{i=1}^k || U_i||_{\\infty}$, all $U_i$ jointly, in a ball. But in Eq. (9), the authors project each $U_i$ independently to the same ball, which makes me less excited. Do you set the same $\\lambda$ for all $U_i$? Different $U_i$ may need different $\\lambda$, right?\nIf we take a squre of the constraints of $U_i$ in Eq. (9) on both sides, i.e. $|| U_i ||^2 \\leq \\lambda^2$, and add it to the objective using Lagrange multiplier, it is equivalent to the L2 regularization (the weight decay) for each $U_i$.  \n\n2. In Fig. 2, decreasing the bounds could hurt the classification performance on clean data. Is there a bound that can keep the performance of clean data the highest and the accuracy for the adversarial data also the highest?\n\n3. Results in Table 1 show that the proposed method on clean data does not have obvious superiority over the Jacobian regularization and the L2 regularization methods. But from the title of this paper, I would expect that the proposed method can also significantly outperform other regularization methods on clean data.\n\n4. Since the main advantage of this method is adversarial defense and attack. Why not compare with some work that is proposed for adversarial defense/attack? For example, “Feature Denoising for Improving Adversarial Robustness, CVPR 2019”.\n\nMinor:\n  \n- Should Table 1 appear before Table 2?\n\n- Figure 3 is not referenced. ", "summary_of_the_paper": "This paper analyzed the empirical Rademacher complexity of polynomial nets, the Coupled CP-Decomposition (CCP), and Nested Coupled CP-decomposition(NCP) nets. The corresponding Lipschitz constants for both models are derived. The Projected SGD and the Projected SGD + Adversarial Training algorithms are used to optimize the CCP and the NCP with the Lipschitz constants. Experiments on classification and adversarial attack tasks are performed to evaluate the proposed method. Results show that the proposed projection regularization is better than the Jacobian regularization and the L2 regularization methods in adversarial attack tasks.\n", "summary_of_the_review": "- Optimizing the projection of $\\prod_{i=1}^k || U_i||_{\\infty}$ is not good enough. \n- I think the authors should also compare with some works that are for adversarial defense/attack tasks. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6HzovPDtrq9", "reviewer": "Reviewer_7Q5M", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "## Strengths:\n1. The main theoretical results are strong:\n   - Novel - I am not aware of any prior works on the Rademacher Complexity and Lipschitz bounds of polynomial networks\n   - Sound - I checked the proofs for Theorem 1 and 2 and they all look correct to me. The three other theorems (Theorem 3, 4 and 5) all look reasonable to me, but I admittedly did not check their proofs. \n2. The empirical results are comprehensive and convincing. The authors showed that the proposed infinity projection approach is effective at making polynomial networks more robust than baselines on five image recognition datasets and one audio recognition dataset. Although the idea of constraining $L_\\infty$ norm of weight matrices to defend against $L_\\infty$ perturbation is not new in the adversarial robustness literature for standard feedforward networks, seeing its effectiveness in polynomial networks is still quite interesting.\n\n## Weaknesses: \nMy biggest concern is the gap between the Rademacher Complexity upper-bound presented (in Theorem 1) and the practical bound that is used for regularizing the polynomial networks in the empirical section. Rather than controlling the norm of the face-splitting product $\\\\|U_1 \\bullet \\cdots \\bullet U_k \\\\|_\\infty$ suggested by the theory, the proposed technique individually controls the norm $\\\\|U_i\\\\|_\\infty$. This seems to be quite a significant relaxation and it is unclear how loose the practical bound is. To help get a sense of how much is lost in this relaxation, I wonder if there is a way to numerically approximate the gap between these two bounds (for some fixed polynomial nets).\n\n## Other comments:\n- \"Cifar10\" should be capitalized (e.g., in the Figure 3 caption)\n- Appendix C - “This re-parametrization creates equivalent models in terms of models” - It is unclear what the second “models” means here.\n- Appendix D -\n    - $V = \\\\{v_1, \\cdots v_n\\\\}$: should it be $d^k$ instead of $n$?\n    - Equation 34: should it be $d^k$ on top of max (since $l \\in [d^k]$)?", "summary_of_the_paper": "The paper introduces Rademacher Complexity bounds and Lipschitz constant bounds (both $\\ell_2$ and $\\ell_\\infty$) for two families of polynomial networks. While prior theoretical results on complexity and Lipschitz constant bounds exist for standard neural networks that consist of linear layers and activation functions, these results do not directly apply to Polynomial networks due to their vastly different structures from standard neural networks. \n\nOn the practical side, the authors found that imposing $L_\\infty$ norm constraint on the weight matrices of the polynomial networks is effective against adversarial perturbation. In particular, the paper focuses on robust image and audio recognition tasks and found out that imposing $L_\\infty$ norm constraint via projected gradient descent is more effective than other commonly deployed regularization techniques (in standard networks) such as Jacobian regularization and weight decay. ", "summary_of_the_review": "The theoretical results in this paper are strong, and they serve as a significant first step in understanding the generalization and robustness properties of polynomial networks. The practical regularization technique motivated by the theoretical results is effective in making polynomial networks more robust evaluated by common gradient-based adversarial attacks on image and audio recognition tasks. The only weakness of the paper is that the proposed regularization technique can feel a bit disconnected from the main theoretical results (due to relaxation for tractability consideration), making it a bit less clear whether the practical regularization is actually controlling the Rademacher complexity effectively. Despite this weakness, I believe the paper still deserves acceptance for its great theoretical and practical contributions in polynomial networks. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "27zOGSgBVr3", "reviewer": "Reviewer_SK73", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Rademacher complexity bounds imply theoretical generalization guarantees. Polynomial networks have been recently proposed and have shown good empirical performance, so analysis of their theoretical properties is relevant. It is not clear to me how these bounds compare to known generalization bounds for regular neural networks.\nThe bounds are the first generalization bounds for polynomial networks, but do not use algorithmic properties like stability or regularization and are therefore potentially loose. Bounding network weight norms for regularization itself is not novel, but for polynomial networks small empirical improvements are observed in accuracy of using proposed regularization in non-adversarial settings. \n\nL-infinity Lipschitz constant of the networks is related to robustness against L-infinity-bounded adversarial perturbations. Again the algorithmic insights of coupling regularization with adversarial training are not novel, but the idea is verified to be useful also in the context of polynomial networks.\n\nIn my opinion the theoretical contributions of the paper are the most interesting, and it would be useful if the authors include brief technical insights or proof sketches for the main theorems.", "summary_of_the_paper": "The paper provides theoretical guarantees for polynomial neural networks, specifically bounds on Empirical Rademacher Complexity (which implies generalization guarantees) and on the Lipschitz constant of the networks (implies robustness). Polynomial nets have shown state-of-the-art results for several machine learning tasks. Specifically CCP and NCP models of Chrysos et al. (2020) are considered, and the bounds assume bounded l-infinity-norm which is meaningful for image inputs. Further an algorithm is proposed which adds regularization to polynomial networks using the terms in the theoretical upper bounds (corresponding to weight norms) which leads to gain in accuracy, especially in adversarial settings (where the regularization is combined with adversarial training).", "summary_of_the_review": "The paper provides first generalization bounds for polynomial networks, which have been found to be empirically effective in prior work. Also an upper bound is provided for the Lipschitz constant of polynomial networks. Formal guarantees of low error and high robustness for empirically used techniques are an important contribution of the paper. The algorithmic insights from the bounds can potentially guide regularization and robustness techniques used with these networks. My main complaint is that very little space is allocated to providing proof insights, and practical insights of regularizing network weights and combining with adversarial training have limited novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers generalization of polynomial networks. It gives a characterization of the Rademacher complexity as well as Lipschitz constants for polynomial nets. Inspired by the theoretical results, the paper also proposed regularization schemes that empirically improves accuracy and robustness. Most reviewers found the theoretical results to be interesting (but there are some concerns about the mismatch between the upperbound in theory and used in practice, which was partially addressed in the response). There are some more concerns about the experiments but many of them are addressed in the new version. Overall although polynomial networks are not popular in practice, this paper provides some interesting theoretical results.
Decision: Accept (Poster)