# Controlling the Complexity and Lipschitz Constant improves polynomial nets

arXiv: https://arxiv.org/abs/2202.05068 · HTML: https://mlsanity.com/paper/2202.05068/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 56 references that are in the map.
- First posted on arXiv 10 Feb 2022.

## Builds on (most cited first, 27 of 27)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [A Style-Based Generator Architecture for Generative Adversarial Networks](https://mlsanity.com/paper/1812.04948/) (2018)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Non-local Neural Networks](https://mlsanity.com/paper/1711.07971/) (2017)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Defense against Adversarial Attacks Using High-Level Representation Guided Denoiser](https://mlsanity.com/paper/1712.02976/) (2017)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Feature Denoising for Improving Adversarial Robustness](https://mlsanity.com/paper/1812.03411/) (2018)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Parseval Networks: Improving Robustness to Adversarial Examples](https://mlsanity.com/paper/1704.08847/) (2017)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Neural Audio Synthesis of Musical Notes with WaveNet Autoencoders](https://mlsanity.com/paper/1704.01279/) (2017)
- [EMNIST: an extension of MNIST to handwritten letters](https://mlsanity.com/paper/1702.05373/) (2017)
- [The MegaFace Benchmark: 1 Million Faces for Recognition at Scale](https://mlsanity.com/paper/1512.00596/) (2015)
- [Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks](https://mlsanity.com/paper/1802.04034/) (2018)
- [Spectral Norm Regularization for Improving the Generalizability of Deep Learning](https://mlsanity.com/paper/1705.10941/) (2017)
- [Robust Learning with Jacobian Regularization](https://mlsanity.com/paper/1908.02729/) (2019)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [Convolutional Tensor-Train LSTM for Spatio-temporal Learning](https://mlsanity.com/paper/2002.09131/) (2020)

## Built on by (most cited first, 5 of 5)

- [Regularization of polynomial networks for image recognition](https://mlsanity.com/paper/2303.13896/) (2023)
- [Hadamard product in deep learning: Introduction, Advances and Challenges](https://mlsanity.com/paper/2504.13112/) (2025)
- [Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study](https://mlsanity.com/paper/2209.07736/) (2022)
- [Sound and Complete Verification of Polynomial Networks](https://mlsanity.com/paper/2209.07235/) (2022)
- [On the Study of Sample Complexity for Polynomial Neural Networks](https://mlsanity.com/paper/2207.08896/) (2022)

## Abstract (arXiv)

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 ℓ_∞-operator-norm and the ℓ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 in six datasets 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.