Ladder Polynomial Neural Networks
Authors: Li-Ping Liu
Ruiyuan Gu
Xiaozhe Hu
Venue:  (2020)
Keywords: polynomial neural networks

Abstract: The underlying functions of polynomial neural networks are polynomial functions. These networks are shown to have nice theoretical properties by previous analysis, but they are actually hard to train when their polynomial orders are high. In this work, we devise a new type of activations and then create the Ladder Polynomial Neural Network (LPNN). This new network
can be trained with generic optimization algorithms. With a feedforward structure, it can also be combined with deep learning techniques such as batch normalization and dropout. Furthermore, an LPNN provides good control of its polynomial order because its polynomial order increases by 1 with each of its hidden layers. In our empirical study, deep LPNN models achieve good performances in a series of regression and classification tasks.

Under review as a conference paper at ICLR 2020
LADDER POLYNOMIAL NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Polynomial neural networks are essentially polynomial functions. These networks are shown have nice theoretical properties by previous analysis, but they are hard to train when their polynomial orders are high. In this work, we devise a new type of activations and then create the Ladder Polynomial Neural Network (LPNN). The LPNN has a feedforward structure. It provides good control of its polynomial order because its order increases by with each of its hidden layers. The new network can be treated with deep learning techniques such as batch normalization and dropout. As result, it can be well trained with generic optimization algorithms regardless of its depth. In our empirical study, deep LPNN models achieve good performances series of regression and classification tasks.
1 INTRODUCTION
A polynomial neural network has a unique underlying function, which is polynomial. Well studied by mathematicians, polynomial functions have been shown to have many favorable theoretical properties. Polynomial neural networks also bridge the analysis of general neural architectures to the properties of polynomial functions. However, in practice, there is still gap in performance between polynomial neural networks and popular feedforward neural networks. One purpose of this work is to narrow the gap and provide new model for both theoretical study and practice.
One method of constructing polynomial neural networks is use the quadratic function as activations in feedforward network. [ivni et al. (2014) call this specific type of networks as PNNs and show several of their theoretical properties, e.g. they are polynomial-time learnable, and they can approximate other feedforward neural networks. KKlleel et al. (2019) study their functional space from the algebraic perspective. The theoretical analysis favors low-order polynomials in terms of learning time. However, PNNs cannot have arbitrary order, as their orders grow exponentially with their layers. For learning PNN models, researchers often devise specialized learning algorithms (Livni et al., (2044] Soltani & Hegde (018 Du & Leel 2018 Soltani & Hegde 2019). Most of these algorithms only work for PNNs with one or two hidden layers. deep PNN will have a very large order, then the model becomes hard to train.
Polynomial learning models can also be constructed by defining polynomial kernel over input features and network parameters (Blondel al. 2016b a 2017). Blondel et al. (2016b) show that PNNs with one hidden layer can be constructed by second-order polynomial kernel. One can use an arbitrary order in the polynomial kernel, then the constructed learning model has the same order. Factorization machines (Rendle) 2010 Blondel et al.) (2016a) is another polynomial model constructed from the ANOVA kernel. Training these models often needs special optimization methods. They don't 't have layered structure, it is not easy apply deep learning techniques, such as batch normalization, to these models.
In this work, we propose new type of polynomial neural networks, Ladder Polynomial Neural Networks (LPNNs). Particularly, we introduce a new activation function, product activation, and use it in feedforward structure. In this new activation function, the hidden layer is multiplied to a linear transformation of the input feature. This activation always increases the polynomial order of the network by one, so we can specify an arbitrary order for the network. As a type of feedforward networks, an LPNN can be trained with standard training techniques. Further analysis shows that the function surface of L.NN has much better smooth guarantee than PNNs. As a function of learnable parameters, the network is block multiconvex with respect it weight

---

Under review as a conference paper at ICLR 2020
matrices, providing opportunities of faster learning methods. The model space of LPNNs includes models constructed from polynomial kernels as special cases, indicating LPNNS are more flexible than these models.
The LPNN model evaluated in a list of benchmark regression and classification tasks. The re- sults indicate that the LPNN outperforms other polynomial networks in general. Its classification performances match those of a standard feedforward neural network. Our results also indicate the necessity of batch normalization and dropout when training deep LPNN models.
2 THE LADDER POLYNOMIAL NEURAL NETWORK
We first define the general form of feedforward neural network. Suppose the input to the neural network feature vector X E 12o, and denote h x. Suppose the network has L hidden layers, with each layer E {1...., .......] L} takes the input h and has the output h., Each layer is defined by
= (W"h²-))
(1)
Here W is the weight matrix for layer f. and ((.) is the activation function. Note that superscripts of hidden vectors and weight matrices always denote layer indices, not exponents. For notational simplicity, we omit intercept vectors for now and will add them back later.
We first define the product activation (.(.) before we define the new network,
Op Op(u; V, x) = u (Vx).
Here O is the element-wise product. V is the parameter for the activation function. V has shape of (d, do) if u has d entries. The activation is data-dependent. If is polynomial function of x, then pp [u; V, x) is also polynomial function of x with the polynomial order increased by 1. Note that the product activation is not a function of u because different x values may give the same u value but different responses from op (u; x).
We product activations in feedforward structure and get LPNN. We use a different matrix V for the product activation in each layer f. Suppose h, is the output of the neural network, the function of the LPNN is formally defined as h, L. LPPNN(x O).
(3) Here we use to denote all network parameters, 0 = (w WL V V4). The first hidden layer h a second order polynomial of the input, and each activation increase the order by 1, the hidden layer h is an order (E ++ 1) polynomial. The entire network is order L + polynomial function of the input.
LPNN 0) = op (W op (W
(W'ss x; V x) V 1-1
x) V x).
We further we-te the function with simple additions and multiplications.
de
h = (w @ (V'x)
e, (W/h") (Vfx).
(4)
Here e; is a one-hot vector with its i-th entry to be one. Note that W and V are both row vectors, so both (W(h)) and (Vfx) are scalars.
After expanding all product activations and taking out all summations, we write the entire network as
d(--1)
di W
in ) (W())) x)
A x
] (5)
LPNN(x;0) Σ eiL
Σ
II 1=
1(2-1==1
4,=1
This equation further show that the polynomial order increases with the number of layers.
In this form, every monomial term has order L ++1 1. To include terms with different orders, we need to include intercept vectors. Suppose each layer has an intercept vector b9, then the layer is defined by
h h²=o, 1-1 bb; V x).
(6)
2

---

Under review as a conference paper at ICLR 2020
We can re-write the input, hidden vectors, and weight matrices in the following form,
&
h h
W
W
b'
V
V 0
0 1
(7)
O
then still have the previous form, h opl (W V 2), and then all previous deriva- tions apply. For notational simplicity, the following analysis continues to use notations without the intercept term.
3 ANALYSIS
3.1 SMOOTHNESS OF THE FUNCTION SURFACE
The smoothness of the function surface of a neural network characterizes the network's important properties, such being robust to input perturbations. This subsection gives upper bound of the Lipschitz constant of the LPNN function.
We first compute the first order derivative of h (ax) with respective the input x. According we have,
Vh = diag( V x) W + diag( X)
(8)
Vh diag( V W (Vh + diag (W' IIV,, 6= 2,3,
(9)
where diag(u) denotes diagonal matrix with its diagonal.
Then we can give bound the first order derivative, which in turn gives an estimate of the Lipschitz constant of h as function of The results are summarized in the following theorem.
Here, for the sake of simplicity, we use 1 norm (ll []) for both vectors and matrices.
Theorem 3.1. If h defined recursively as (I) and (2). then, for =..2.....
[ -
II |
||x||
[I p(V* )o(r)) ||x||*+
(10)
and
[IVh (e+
(í k=1
I [
||x|| |x]|== (e+1)
(TAV
||x| (11)
k==
where p(-) takes the maximal singular value of input matrix.
Proof. Our proof is based on two inequalities. The first one is from the definition of matrix
norm, e.g. l/Whh--1| S p (We) [[ The second one is the Cauchy- -echh-S inequality, e.g. (W'h @ (V'x)] s |[ (W"h 1)]
hehh)1)] [IVV'))]l-
We will use mathematical induction to derive the results. For 1
||b'|| ddiag((²x)) - < V ||| |||x
|/h' |diag( V x) W diag( W x)v'1 2 W |||x/||
This means 10 and hold for f 1. Now assume 10p and hold for 1, then
V ( ||x]|et1,
hh diag (
V ||||||||||
and
Vh = diag V x
+ diag h
(xx))
(+++)
II
| ||x||__
3

---

Under review as a conference paper at ICLR 2020
This bound indicates the relation between the smoothness and the norm of weight matrices. The result is similar to the feedforward neural networks with other activation functions whose gradients are always between -1 and 1 (Virmaux & Scaman 2018). The proof above is inde- pendent of the data and network parameters. We can further improve the bound by considering network weights with an approach similar to (Virmaux & Scaman 2018), but we defer the further investigation to future work.
As a comparison, the same type of bound is much higher for deep PNN model, as its order is exponential in its number of layers.
3.2 MULTICONVEXITY IN PARAMETERS
We also study the network as function of its parameters to understand its function surface for parameter optimization.
The network output h2 is linear in weight matrix W V if we hold other weights stants. We can see so if we examine the function form in (5): there is no multiplications between any entries in W V With this property, the learning model is block multiconvex with respect to the model parameters.
Theorem 3.2. Let h2 LPN (x; 0) and y be the fitting target. Suppose loss( y) is a convex loss function, then the training objective of an LPNN,
(f) = loss(h,, y)
x
Σ 1=1
(I
IV))
(12)
is block multiconvex in blocks {W! W4, V V4J.
Multiconvexity enables some specialized optimization algorithms (Shen et al. 2017). These algorithms have the potential be combined with generic optimization algorithms and speed up the training of LPNN.
As a comparison, network weights in PNNs are exponentiated through hidden layers. We believe PNNs has much rough surface than LPNNs.
3.3 TRAINING WITH BATCH NORMALIZATION AND DROPOUT
Batch normalization (BN) (offf & Szegedy 2015) and dropout (Srivastava et al. 2014) are effective techniques for training deep neural networks. We can apply batch normalization and dropout to LPNN without any modification given its layered structure. We put the BN layer after the activation per some practitioners' advice, though the original paper suggests putting it before the activation.
When LPNN has BN layers, the model in training is not polynomial function, but the trained model with constant BN parameters are still polynomial functions. Here we want integrate BN parameters into network weights so that previous derivations still apply. We consider hidden layer and omit layer indices for notational simplicity.
Let [h...... h be hidden layer values of instances in a batch, then the batch-normalized hidden layer h, of instance computed by
1 n 71
h; >(, (hhhh///((0000 +c) with
h
h 1
(13)
n
Here the division / and the square are element-wise operations, and is a small positive number.
In the training procedure, the variance is function of input instances in the batch, therefore, the hidden vector h; is not a linear function of the input anymore. After training, the mean vector μ and the variance vector become constants, then the model still a polynomial function.
4

---

Under review as a conference paper at ICLR 2020
Let's write the model with BN into the original function form. Let f4, o, and 3 are convergent values the training procedure, then the equivalent LPNN without batch normalization has parameters defined as follows.
W W diag(n/(o e)), = W diag(ru/( +
(14)
Here need to build equivalence with the LPNN with intercept terms. These terms can be absorbed into weight matrices by
In this result, we can see that BN changes the norm of weight matrices and then the Lipschitz constant of the network function. Based on the study by Santurkar et al. (2018), BN can simply shrink the norms of weight matrices avoid having steep slopes in the function surface.
Dropout can be directly applied LPNN, In the training phase, using dropout equivalent removing some entries in summations of (5) and rescaling the summation. In the testing phase, dropout have no effect, and the trained model just as the definition above.
3.4 RELATION WITH MODELS BASED ON POLYNOMIAL KERNELS
In this subsection, we show that the polynomial networks constructed from polynomial kernel functions (Blondel et al. 2016b) are special cases of LPNN networks.
Lemma 3.3. The polynomial kernel function pd (p.x) (A+ + x)" with p, R2 can be written in the form of LPNN(x; f) such that network weights can be expressed by p.
Proof. Append the feature vector, hg [x_, Set W =[pT, V Ip AJT for all =1, I....,m m - 1, and Wn [1] for é = 2, 2,... L. then ((NN(( 0) is equivalent to the kernel by
Theorem 3.4. The learning models in the form of Ek TA(A + x)m Blondel et al. 2016b) are special cases of LPNN. Theorem 3.5. The second order factorization machines are special cases of LPNN.
Proof. By Appendix D.3 in (Blondel et al. 2016b) the function of a factorization machine can be computed by
1 FM(x; U,S)
x US x (U diag(x)diag(x{SS)))
2
1 UST x (x xx) TaeeTdiie diag (SUT)
xx
(15)
2
We can set the network as follows.
U
S
W
V =
(16)
Here the identity matrix in W and V1 passes x to the hidden layer and get (x @ x) there. The hidden layer h' = [Ux) @ (Sx); @ x]. Then we set W [1 T with diag (SUT).
then w = (x: U.S).
From this analysis, we that the LPNN is more flexible than polynomial models constructed from polynomial kernel functions. We believe the LPNN is also more flexible than the factor- ization machine. Compared with LPNNs, the factorization machine does not have monomials that contains the second or higher order exponential of feature entry. We don't expect this difference brings much expressiveness the factorization machine, though creates difficulties for writing factorization machine in the form of an LPNN.
5

---

Under review as a conference paper at ICLR 2020
Table 1: RMSE of different models regression tasks
methods
winc-quality
power-plant
kin8nm
boston- -housig
conerete-strength
FF
0.60 + 0.04*
4.05 =0.17*
0.100 + 0.002
2.82 + 0.76*
5.10 =0.49*
0.73 1
4.43 0.15
0.155 0.004
4.80
1.14
8.52 10.59
PK
4.39 1 5.50
4.05 1 0.15*
0.100 1 0.005
41.9 1 77.2
7.95 12.42
PNN
5.49 1 16.5
5,83 1 1.39
0.102 1 0.007
4.59 1 2.74
5.58 10.48
LPNN
0.82+ 0.18
4.13 0.16
0.099 0.006
4.05 2.13
5.20 =0.62
Table 2: Error rates of different models on classification tasks
methods
mnist
fashion-mni
skin
sensIT
letter
covtype-b
covtype
FF
0.0185
0.108
0.0313
0.176
0.096
0.113
0.146
FM
0.0573
0.167
0.0439
0.260
0.546
0.208
0.575
PK
0.0506
0.168
0,0039
0.225
0.248
0.191
0.494
PNN
0.0503
0.127
0.0018
0.199
0.104
0.097
0.103
LPNN
0.0171
0.117
0.0017
0.175
0.0729
0.117
0.140
4 EXPERIMENT
4.1 EXPERIMENT SETUP
In this section, we evaluate the LPNN on several learning tasks. The LPNN is compared against feedforwrad network and three polynomial learning models. All models are summarized below.
Feedforward network (FF); FF uses ReLU functions as activations. We add (-2 norm regulraiza- tion to the model. The regularization weight is chosen from (le-6, 1e-5, le-4, 5e-4). When dropout is applied, the dropout rate is chosen from (0, 0.05, 0.1, 0.2, 0.4).
Polynomial Neural Network (PNN): the model is the same the FF except its activations are the quadratic function. It has the same hyperparameters as FF, and it is trained in the same way FF.
Factorization Machine (FM): we use the implementation from the sklearn package (Niculae Accessed 2019). The order of FM in this implementation can be 2 or 3. It add several ANOVA kernel functions (called factors) to increase model complexity. The model is also regularized by 1-2 norm. The hyperparameters of FM include the order, the number of factors, and the weight of regularization. The number of factors is chosen from from {2, 4, 8, 16), and the regularization weight is chose from the same range as This implementation of FF does not have multiple outputs, so we have used one-vs-rest for multiclass classification problems.
Polynomial Kernel (PK): PK uses polynomial kernels. Other than that, PK is similar to FM. We can specify the order of the underlying polynomial function of PK. The hyperparameters of PK are the same FM. The implementation is also from the sklearn package.
LPNN: the model is the same as the FF except its activations are product activations. Its hyperparameters are the same FF, and it is trained in the same way as FF.
We test these models on five regression datasets (wine-quality, power-plant, kin8nm, boston- housing, and concrete-stre -hereetestrenggh) and six classification datasets (mnist, mushion-mnist. skin, sensIT, letter, covtype-b, and covtype). The mnist and fasion-mnist datasets come with the Keras package, the skin, sensIT, and co datasets are from the libSVM website, and all other datasets are from the UCI repository.
4.2 PRODUCT ACTIVATIONS
We first examine the product activation function h (u: V in trained model. We set up LPNN with three hidden layers and then train it on the mnist dataset. The training finishes after 20 epoches when the network has validation accuracy of 0.984. Then check inputs
6

---

Under review as a conference paper at ICLR 2020
10
10
0-
-10
(a)
(b)
(a)
(b)
10
-5
-10
-10
0
0
10
-5
0
5
-10
5
(c)
(d)
(c)
(d)
hidden layer
hidden layer 2
hidden layer 3
Figure 1: Product activations LPNN on the mnist dataset. The model has three hidden layers.
From each layer, activations of four hidden units are plot here in the same color.
Table 3: Effect of batch normalization and dropout
L BN and dropout
only dropout
only BN
neither
7,77 = 0.53
7.78 : 0.54
7,82 1 0.55
7.76 + 0.53
2
6.05 + 0.50
5.98 0.57
6.26
6.30 0.96
5.20 0.62
5.12 0.58
5.82 1.13
6.89 2.06
5
4.72 0.66
4.92 = 0.78
5,46 1.83
7.86 3.10
10
5.11 + 2.18
4.71 = 0.90
4.97 = 0.97
7.49 2.77
and responses of the activation functions three different layers. We plot the response he against the corresponding u; for each hidden unit i to generate a subplot. We randomly select 400 instances and plot each (hs, uz) pair. We plot four hidden units each of all three hidden layers and generate plots in Figure
In these results, we see that the product activation is not really a function because inputs with the same value may have different responses. It is also clear that the product activation is not linear. The behavior of the activation is versatile: the activations shown in (c) layer and (b) at layer 3 exhibit some linear behavior while the activations shown in (d) at layer I and (c) at layer 2 roughly approximate the quadratic function.
4.3 REGRESSION AND CLASSIFICATION
We first apply the model to five regression tasks. We use the same data splits by Gal (Accessed in 2019). Each dataset has random splits. On each split, we run model selection through five-fold cross validation, re-train the model, and then test the model on the test set. The results are averaged over the 20 splits. For FF, PNN, and LPNN, we set three hidden layers and 50 hidden units in each hidden layer. We apply dropout and batch normalization to all the three models. We set the polynomial order to be 4 for the PK model to match the order as LPNN. We set the order of FM be For each model, we select all hyperparameters described in the subsection above.
Table I tabulates RMSE of all algorithms on all datasets. On most datasets, no single algorithm outperforms others with statistical significance, but we put * at the smallest error mean. If comparing the mean values only, LPNN performs a little worse than FF but better than other polynomial models. The PNN has very bad performances on two splits of the wine-quality dataset. We speculate that PNN is not stable when its polynomial order is high. PK has bad
7

---

Under review as a conference paper at ICLR 2020
Table 4: Effect of batch normalization and dropout the mnist dataset
L
BN and dropout
only dropout
only BN
neither
1
0.0191
0.0208
0.0242
0.0171
2
0.0191
0.0188
0.0202
0.0192
3
0.0170
0.0187
0.0229
0.0207
5 0.0207
0.7657
0.0271
0.8947
10
0.0230
0.0298
0.0207
0,0241
performances wine-quality and boston- houtonn because the model does not fit the two tasks- its performances are bad on most splits.
We then test these models on seven classification tasks. For each dataset, we set 30% as the test set, except for mnist and fasion-mnist datasets, which come with test sets. We do model selection for both architecture and hyperparameters on 20% of the training set. For neural networks, the number of hidden layers chosen from (1, 4]. We shrink the number of hidden units from the bottom to the top. The number of hidden units is computed by a a' dan) dout so that the number of hidden units middle layer between the input dimension and the output dimension. The shrinking factor a is chose from {0.3, 0.5, 0.7, 0.8). We also select the order for PK from {2, 3, 5} to match the order LPNN. All other hyperparameters model are also selcted together with architectures.
The error rates of different models are reported in Table In general, the performance of LPNN is comparable to FF and better other polynomial models. Comparing to feedforward networks, LPNN has relatively better performance classification tasks. We speculate the reason is that an LPNN only needs to decide discrete labels from its outputs classification tasks while it needs fit the exact value in regression tasks. LPNN may be not flexible enough for fitting continuous values compared to feedforward networks.
4.4 THE EFFECT OF BATCH NORMALIZATION AND DROPOUT
In this subsection, we investigate the effect of batch normalization and dropout on LPNN. We use L E 2,, 3, 10). For each depth, try four configurations: using/not using batch normalization and using/not using dropout. We select other hyperparameters through model selection. We run the experiment on regression task (concrete- senerete-sttength) and classification task (mnist).
The results are shown in Table 3 From this result, we see that both batch normalization and dropout are needed to train good LPNN model. On the mnist dataset, the LPNN without batch normalization has very bad performance when L = 5. Its performance drops sharply after few epochs. This observation indicates that the LPNN without batch normalization is very unstable due to some bad optimization directions.
5 CONCLUSION
In this paper, we have proposed LPNN, a new type of polynomial neural networks that can have arbitrary polynomial order. The network is based on product activations. A product activation multiplies& a linear transformation of the input to the hidden layer to achieve non-linear transformation of the input. The product activation always increases the polynomial order by 1. LPNN uses product activations in feedforward structure. With modern training techniques, such as dropout and batch normalization, we can well train deep LPNN models. These models achieve competitive performances in our empirical evaluations. The LPNN has the potential to provide new insights to the theoretical study of polynomial learning models and. also a valuable learning method in practice.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mathieu Blondel, Akinori Fujino, Naonori Ueda, and Masakazu Ishihata. Higher-order factor- ization machines. In Advances in Neural Information Processing Systems, pp. 3351-3355 2016a.
Mathieu Blondel, Masakazu Ishihata, Akinori Fujino, and Naonori Ueda. Polynomial networks and factorization machines: New insights and efficient training algorithms. In International Conference on Machine Learning, pp. 850-858, 2016b.
Mathieu Blondel, Vlad Niculae, Takuma Otsuka, and Naonori Ueda. Multi-output polynomial networks and factorization machines. Advances in Neural Information Processing Systems, pp. 3349-3359, 2017.
Simon S Du and Jason D Lee. On the power of over-parameerrizaton in neural networks with quadratic activation. In International Conference on Machine Learning, pp. 1328-1337, 2018.
Yarin Gal. http://shftttooooogoo//o//o//oln Accessdd in 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.033167 2015.
Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. arXiv preprint /905:/995./22000 2019.
Ming Lin, Shuang Qiu, Bin Hong, and Jieping Ye. The second order linear model. arXiv preprint Sttl::1703.00500 2017.
Roi Livni, Shai Shwarr, and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Vlad Niculae.
http:////sttttoemooooooo/////l// Accessed in 2019.
Steffen Rendle. Factorization machines. In 2010 IEEE International Conference Data Mining, pp. 995-1000, IEEE, 2010.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normalization help optimization? Advances in Neural Information Processing Systems, pp. 2483-2493 2018.
Xinyue Shen, Steven Diamond, Madeleine Udell, Yuantao Gu, and Stephen Boyd. Disciplined multi-covexx programming. 2017 29th Chinese Control And Decision Conference (CCDC), pp. 895-900. IEEE, 2017.
Mohammadreza Soltani and Chinmay Hegde. Towards provable learning of polynomial ral networks using low-rank matrix estimation. In International Conference on Artificial Intelligence and Statistics, pp. 1417-1426, 2018.
Mohammadreza Soltani and Chinmay Hegde. Fast and provable algorithms for learning two-layer polynomial neural networks. IEEE Transactions Signal Processing, 67(13): 3361-3371, 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1988 2014.
Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. In Advances Neural Information Processing Systems, pp. 3835 3844, 2018.
9


Reviews:
[{"review_id": "HyxHu42TFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Ladder Polynomial Neural Networks (LPNNs) that use a new type of activation primitive -- a product activation -- in a feed-forward architecture. Unlike other polynomial architectures that grow in the order exponentially with network depth, the proposed approach gives explicit control over the order and smoothness of the network output and enables training with standard techniques.\t\n\t\t\t\t\nThe proposed architecture is closely related to a decomposition of a k’th order multivariate polynomial function\n[T, x^{\\otimes k}] = \\lambda^\\top (A x \\odot A x \\odot …  \\odot A x)\t=  \\lambda^\\top (A x)^{\\odot k}\nwhere T is a symmetric tensor of polynomial coefficients and [\\cdot,\\cdot] denotes contraction. This is a shallow (one layer architecture) and sometimes referred as a Waring decomposition.\n\nIn this paper, the authors propose a specific chain factorization of the polynomial (Eq 5 in the paper), where they write the factors recursively, that they name as a ladder polynomial neural network. \n\nh^\\ell = (W_\\ell h^{\\ell-1} \\odot V^{\\ell} x)\n\nThe ladder architecture is very closely related to tensor trains (https://epubs.siam.org/doi/10.1137/090752286). I found it surprising and somewhat alarming that this literature is not being cited as these methods are also quite well known in deep learning.\n\nI like the smoothness analysis of section 3.1 -- the proof is quite easy to follow and direct. I would be quite surprised if this result would not be known in the literature in some other form but I don’t recall seeing it. On the other hand it seems to be inevitably very loose for a deep ladder network unless the network models the zero function. It would have been a valuable addition to the experimental section, if this bound would have been illustrated numerically on synthetic examples.\n\nIn 3.2, The authors say that the objective is multiconvex -- I would argue that it is multilinear (apart from the regularization term, that is later introduces). The observation in 3.3, that batch-normalization or dropout can be used for this model is perhaps tangential to the main argument. These is investigated in the experimental section but I don’t see a clear conclusion. The section in 3.4 must include links to tensor decompositions beyond factorization machines.\n\t\t\nOverall, I think the paper has some merit and could be interesting for some readers, despite the fact that the contribution is not very original and the treatment could be improved in many ways. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkl5UHQ3YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work introduces a new polynomial feed-forward neural network called Ladder Polynomial Neural Network (LPNN). Theoretical results show that LPNNs generalize vanilla PNNs and FMs. In the experimental analyses, LPNNs perform similar to the vanilla FMs and PNNs, as well.\n\n- In the statement “V has a shape of (d, d0) if u has d entries”, what do you mean by shape, more precisely?\n\n- x is a feature vector fed to a neural network as an input. I assume that it is given in the input layer l=0, according to the notation. Then, should x^l be used instead of x in equations (4), (5), (6), (9), and the other corresponding statements? Otherwise, is V^l applied to the input vector x at each layer l?\n\n- What do \\| \\|^2, \\| \\|^l, \\| \\|^{l+1} denote?\n\n- How do you define the norm \\| \\| for matrices, more precisely?\n\n- Please provide standard deviation/variance of classification error of different models in Table 2.\n\n- Please clarify novelty and superiority of the proposed LPNNs compared to the vanilla and state-of-the-art methods in theory and practice. For this purpose, I suggest to further analyze and compare convergence and generalization properties of LPNNs with the sota in theory and practice.\n\nAfter the rebuttal:\n\nAuthors responded some of my questions. However, I still consider that the contribution of the paper is limited, and should be improved for a clear acceptance. Therefore, I keep my rating.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lRcpQ79H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors a new type of polynomial neural networks LPNN that can have an arbitrary polynomial order. The network has a feedforward structure which provides a good control of its polynomial order. Empirical study shows that deep LPNN models achieve good performances in regression and classification tasks. In general, the paper is clearly written by addressing an interesting problem but I still have several concerns. \n1.\tThe authors are expected to analyze the time complexity in terms of both theoretical and experimental analysis since the time cost the one of the major limitation of PNN. \n2.\tThe experimental section is rather weak since the authors only report results in some simple data. The authors are expected to report more complex tasks to show its effectivenss. \n3.\tIt would be interesting if the authors could show whether the algorithm can integrate with other structure such as convolutional operator to cope with the image classification, and other relevant tasks.   \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new type of Polynomial NN called Ladder Polynomial NN (LPNN) which is easy to train with general optimization algorithms and can be combined with techniques like batch normalization and dropout.  Experiments show it works better than FMs with simple classification and regression tasks, but no experiments are done in more complex tasks. All reviewers agree the paper addresses an interesting question and makes some progress but the contribution is limited and there are still many ways to improve.
Decision: Reject