Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

main_review: Pros:
- The Rademacher complexity bounds of the CCP and the NCP are derived. 
- The Lipschitz constants for the CCP and the NCP are derived.

Cons:

1. 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?
If 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$.  

2. 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?

3. 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.

4. 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”.

Minor:
  
- Should Table 1 appear before Table 2?

- Figure 3 is not referenced. 
summary_of_the_review: - Optimizing the projection of $\prod_{i=1}^k || U_i||_{\infty}$ is not good enough. 
- I think the authors should also compare with some works that are for adversarial defense/attack tasks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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).
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.
The 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. 

L-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.

In 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

On 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. 
main_review: ## Strengths:
1. The main theoretical results are strong:
   - Novel - I am not aware of any prior works on the Rademacher Complexity and Lipschitz bounds of polynomial networks
   - 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. 
2. 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.

## Weaknesses: 
My 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).

## Other comments:
- "Cifar10" should be capitalized (e.g., in the Figure 3 caption)
- Appendix C - “This re-parametrization creates equivalent models in terms of models” - It is unclear what the second “models” means here.
- Appendix D -
    - $V = \\{v_1, \cdots v_n\\}$: should it be $d^k$ instead of $n$?
    - Equation 34: should it be $d^k$ on top of max (since $l \in [d^k]$)?
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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. 

Weakness: 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)
1. The C in Equation NCP is capitalized but not in the appendix.
2. The constraint on C in Equation 6 is not on infinity norm but should be on 1 norm.
3. The reference order is messy in the paper (e.g. Table 1 appears before Table 2), making it hard to read.
4. 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.
5. Appendix G, bullet point 5, did not mention CIFAR10.
6. Appendix G.5, "from all four datasets in Fig. 9"? There are altogether 6 datasets as listed by the author right above that line.
7. Appendix G.5, Table 11 is about MNIST and K-MNIST, not MNIST and E-MNIST.
8. 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.

Besides 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_review: Although the technical contribution of this paper is sound, the paper is not ready for publication due to the problems mentioned above.
review_title: null

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)