On the Expressive Power of Deep Polynomial Neural Networks

Introduction

A fundamental problem in the theory of deep learning is to study the functional space of deep neural networks. A network can be modeled as a composition of elementary maps, however the family of all functions that can be obtained in this way is extremely complex. Many recent papers paint an accurate picture for the case of shallow networks (e.g., using mean field theory chizat_global_2018 ; mei_mean_2018 ) and of deep linear networks arora_convergence_2018 ; arora_optimization_2018 ; kawaguchi_deep_2016 , however a similar investigation of deep nonlinear networks appears to be significantly more challenging, and require very different tools.

In this paper, we consider a general model for deep polynomial neural networks, where the activation function is a polynomial ($r$-th power) exponentiation. The advantage of this framework is that the functional space associated with a network architecture is algebraic, so we can use tools from algebraic geometry harris_algebraic_1995 for a precise investigation of deep neural networks. Indeed, for a fixed activation degree $r$ and architecture $\bm{d}=(d_{0},\ldots,d_{h})$ (expressed as a sequence of widths), the family of all networks with varying weights can be identified with an algebraic variety $\mathcal{V}_{\bm{d},r}$, embedded in a finite-dimensional Euclidean space. In this setting, an algebraic variety can be thought of as a manifold that may have singularities.

In this paper, our main object of study is the dimension of $\mathcal{V}_{\bm{d},r}$ as a variety (in practice, as a manifold), which may be regarded as a precise measure of the architecture’s expressiveness. Specifically, we prove that this dimension stabilizes when activations are high degree, and we provide an exact dimension formula for this case (Theorem 14). We also investigate conditions under which $\mathcal{V}_{\bm{d},r}$ fills its ambient space. This question is important from the vantage point of optimization, since an architecture is “filling” if and only if it corresponds to a convex functional space (Proposition 6). In this direction, we prove a bottleneck property, that if a width is not sufficiently large, the network can never fill the ambient space regardless of the size of other layers (Theorem 19).

In a broader sense, our work introduces a powerful language and suite of mathematical tools for studying the geometry of network architectures. Although this setting requires polynomial activations, it may be used as a testing ground for more general situations and, e.g., to verify rules of thumb rigorously. Finally, our results show that polynomial neural networks are intimately related to the theory of tensor decompositions Landsberg-book . In fact, representing a polynomial as a deep network corresponds to a type of decomposition of tensors which may be viewed as a composition of decompositions of a recently introduced sort LORS-2019 . Using this connection, we establish general non-trivial upper bounds on filling widths (Theorem 10). We believe that our work can serve as a step towards many interesting research challenges in developing the theoretical underpinnings of deep learning.

The study of the expressive power of neural networks dates back to seminal work on the universality of networks as function approximators cybenko_approximation_1989 ; hornik_multilayer_1989 . More recently, there has been research supporting the hypothesis of “depth efficiency”, i.e., the fact that deep networks can approximate functions more efficiently than shallow networks delalleau2011shallow ; martens_expressive_2014 ; cohen_expressive_2016 ; cohen_convolutional_2016 . Our paper differs from this line of work, in that we do not emphasize approximation properties, but rather the study of the functions that can be expressed exactly using a network.

Most of the aforementioned studies make strong hypotheses on the network architecture. In particular, delalleau2011shallow ; martens_expressive_2014 focus on arithmetic circuits, or sum-product networks poon_sum-product_2012 . These are networks composed of units that compute either the product or a weighted sum of their inputs. In cohen_expressive_2016 , the authors introduce a model of convolutional arithmetic circuits. This is a particular class of arithmetic circuits that includes networks with layers of 1D convolutions and product pooling. This model does not allow for non-linear activations (beside the product pooling), although the follow-up paper cohen_convolutional_2016 extends some results to ReLU activations with sum pooling. Interestingly, these networks are related to Hierarchical Tucker (HT) decomposition of tensors.

The polynomial networks studied in this paper are not arithmetic circuits, but feedforward deep networks with polynomial $r$-th power activations. This is a vast generalization of a setting considered in several recent papers venturi2018a ; du_power_2018 ; soltanolkotabi_theoretical_2018 , that study shallow (two layer) networks with quadratic activations ($r=2$). These papers show that if the width of the intermediate layer is at least twice the input dimension, then the quadratic loss has no “bad” local minima. This result in line with our Proposition 5, which explains in this case the functional space is convex and fills the ambient space. We also point out that polynomial activations are required for the functional space of the network to span a finite dimensional vector space leshno_multilayer_1993 ; venturi2018a .

The polynomial networks considered in this paper do not correspond to HT tensor decompositions as in cohen_expressive_2016 ; cohen_convolutional_2016 , rather they are related to a different polynomial/tensor decomposition attracting very recent interest FOS-PNAS ; LORS-2019 . These generalize usual decompositions, however their algorithmic and theoretical understanding are, mostly, wide open. Neural networks motivate several questions in this vein.

Our main contributions can be summarized as follows.

We give a precise formulation of the expressiveness of polynomial networks in terms of the algebraic dimension of the functional space as an algebraic variety.

We spell out the close, two-way relationship between polynomial networks and a particular family of decompositions of tensors.

We prove several theoretical results on the functional space of polynomial networks. Notably, we give a formula for the dimension that holds for sufficiently high activation degrees (Theorem 14) and we prove a tight lower bound on the width of the layers for the network to be “filling” in the functional space (Theorem 19).

Notation.

Basic setup

For fixed degree $r$ and architecture $\bm{d}=(d_{0},\ldots,d_{h})$, there exists an algebraic map

The functional variety $\mathcal{V}_{\bm{d},r}$ may be significantly larger than the actual functional space ${\mathcal{F}_{\bm{d},r}}$, since the Zariski closure is typically larger than the closure with respect to the standard the Euclidean topology. On the other hand, the dimensions of the spaces $\mathcal{V}_{\bm{d},r}$ and $\mathcal{F}_{\bm{d},r}$ agree, and the set $\mathcal{V}_{\bm{d},r}$ is usually “nicer” (it can be described by polynomial equations, whereas an exact implicit description of $\mathcal{F}_{\bm{d},r}$ may require inequalities).

We present some examples that describe the functional variety $\mathcal{V}_{\bm{d},r}$ in simple cases.

Consider $\bm{d}=(2,2,3)$ and $r=2$. The input variables are $x=[x_{1},x_{2}]^{T}$, and the parameters $\theta$ are the weights

The network map $p_{\theta}$ is a triple of quadratic polynomials in $x_{1},x_{2}$, that can be written as

2 Objectives

The main goal of this paper is to study the dimension of $\mathcal{V}_{\bm{d},r}$ as the network’s architecture $\bm{d}$ and the activation degree $r$ vary. This dimension may be considered a precise and intrinsic measure of the polynomial network’s expressivity, quantifying degrees of freedom of the functional space. For example, the dimension reflects the number of input/output pairs the network can interpolate, as each sample imposes one linear constraint on the variety $\mathcal{V}_{\bm{d},r}$.

In summary, while an architecture with a filling functional variety may not necessarily have a filling functional space, it is sufficient to double all the intermediate widths for this stronger condition to hold. As argued below, we expect architectures with thick/filling functional spaces to have more favorable properties in terms of optimization and training. On the other hand, non-filling architectures may lead to interesting functional spaces for capturing patterns in data. In fact, we show in Section 3.2 that non-filling architectures generalize families of low-rank tensors.

3 Connection to optimization

The following two results illustrate that thick/filling functional spaces are helpful for optimization.

If a functional space $\mathcal{F}_{\bm{d},r}$ is not thick, then it is not convex.

Architecture dimensions

In this section, we begin our study of the dimension of $\mathcal{V}_{\bm{d},r}$. We describe the connection between polynomial networks and tensor decompositions for both shallow (Section 3.1) and deep (Section 3.2) networks, and we present some computational examples (Section 3.3).

Furthermore, the celebrated Alexander-Hirschowitz Theorem alexander1995 from algebraic geometry provides the dimension of $\mathcal{V}_{\bm{d},r}$ for all shallow, single-output architectures.

If $\bm{d}=(d_{0},d_{1},1)$, the dimension of $\mathcal{V}_{\bm{d},r}$ is given by $\min\left(d_{0}d_{1},\binom{d_{0}+r-1}{r}\right)$, except for the following cases:

2 Deep networks and tensors

Deep polynomial networks also relate to a certain iterated tensor decomposition. We first note the map $\Phi_{\bm{d},r}$ may be expressed via the so-called Khatri-Rao product from multilinear algebra. Indeed $\theta$ maps to:

Another viewpoint comes from using polynomials and inspecting the layers in reverse order. Writing $[p_{\theta 1},\ldots,p_{\theta d_{h-1}}]^{T}$ for the output polynomials at depth $h-1$, the top output at depth $h$ is:

This expresses a polynomial as a weighted sum of $r$-th powers of other (nonlinear) polynomials. Recently, a study of such decompositions has been initiated in the algebra community LORS-2019 . Such expressions extend usual tensor decompositions, since weighted sums of powers of homogeneous linear forms correspond to CP symmetric decompositions. Accounting for earlier layers, our neural network expresses each $p_{\theta i}$ in (9) as $r$-th powers of lower-degree polynomials at depth $h-2$, so forth. Iterating the main result in FOS-PNAS on decompositions of type (9), we obtain the following bound on filling intermediate widths.

Suppose $\bm{d}=(d_{0},d_{1},\ldots,d_{h})$ and $r\geq 2$ satisfy

for each $i=1,\ldots,h-1$. Then the functional variety $\mathcal{V}_{\bm{d},r}$ is filling.

3 Computational investigation of dimensions

We have written codeAvailable at https://github.com/mtrager/polynomial_networks. in the mathematical software SageMath sagemath that computes the dimension of $\mathcal{V}_{\bm{d},r}$ for a general architecture $\bm{d}$ and activation degree $r$. Our approach is based on randomly selecting parameters $\theta=(W_{h},\ldots,W_{1})$ and computing the rank of the Jacobian of $\Phi_{\bm{d},r}(\theta)$ in (2). This method is based on the following lemma, coming from the fact that the map $\Phi_{\bm{d},r}$ is algebraic.

Thus if $\textup{Jac }\Phi_{\bm{d},r}(\theta)$ is full rank at any $\theta$, this witnesses a mathematical proof $\mathcal{V}_{\bm{d},r}$ is filling. On the other hand if the Jacobian is rank-deficient at random $\theta$, this indicates with “probability 1" that $\mathcal{V}_{\bm{d},r}$ is not filling. We have implemented two variations of this strategy, by leveraging backpropagation:

The first algorithm is simpler and does not require interpolation, but is generally slower. We present examples of some of our computations in Tables 1 and 2. Table 1 shows minimal architectures $\bm{d}=(d_{0},\ldots,d_{h})$ that are filling, as the depth $h$ varies. Here, “minimal” is with respect to the partial ordering comparing all widths. It is interesting to note that for deeper networks, there is not a unique minimally filling network. Also conspicuous is that minimal filling widths are “unimodal", (weakly) increasing and then (weakly) decreasing. Arguably, this pattern conforms with common wisdom.

Fix $r$, $h$, $d_{0}$ and $d_{h}$. If $\bm{d}=(d_{0},d_{1},\ldots,d_{h})$ is a minimal filling architecture, there is $i$ such that $d_{0}\leq d_{1}\leq\ldots\leq d_{i}$ and $d_{i}\geq d_{i+1}\geq\ldots\geq d_{h}$.

Table 2 shows examples of computed dimensions, for varying architectures and degrees. Notice that the dimension of an architecture stabilizes as the degree $r$ increases.

General results

This section presents general results on the dimension of $\mathcal{V}_{\bm{d},r}$. We begin by pointing out symmetries in the network map $\Phi_{\bm{d},r}$, under suitable scaling and permutation.

Thus the dimension of a generic fiber (pre-image) of $\Phi_{\bm{d},r}$ is at least $\sum_{i=1}^{h-1}d_{i}$.

Our next result deduces a general upper bound on the dimension of $\mathcal{V}_{\bm{d},r}$. Conditional on a standalone conjecture in algebra, we prove that equality in the bound is achieved for all sufficiently high activation degrees $r$. An unconditional result is achieved by varying the activation degrees per layer.

Proposition 15 and Conjecture 16 are used in induction on $h$ for the equality statements in Theorem 14. Our next result uses the iterative nature of neural networks to provide a recursive bound.

For all $(d_{0},\ldots,d_{k},\ldots,d_{h})$ and $r$, we have:

Using the recursive bound, we can prove an interesting bottleneck property for polynomial networks.

This expresses our finding that too narrow a layer can “choke" a polynomial network, such that there is no hope of filling the ambient space, regardless of how wide elsewhere or deep the network is.

If $r\geq 2,d_{0}\geq 2,i\geq 1$, then $d_{i}=2d_{0}-2$ is an asymptotic bottleneck. Moreover conditional on Conjecture 2 in nicklasson-2017 , then $d_{i}=2d_{0}$ is not an asymptotic bottleneck.

Proposition 17 affords a simple proof $d_{i}=d_{0}-1$ is an asymptotic bottleneck. However to obtain the full statement of Theorem 19, we seem to need more powerful tools from algebraic geometry.

Conclusion

We have studied the functional space of neural networks from a novel perspective. Deep polynomial networks furnish a framework for nonlinear networks, to which the powerful mathematical machinery of algebraic geometry may be applied. In this respect, we believe polynomial networks can help us access a better understanding of deep nonlinear architectures, for which a precise theoretical analysis has been extremely difficult to obtain. Furthermore, polynomials can be used to approximate any continuous activation function over any compact support (Stone?Weierstrass theorem). For these reasons, developing a theory of deep polynomial networks is likely to pay dividends in building understanding of general neural networks.

In this paper, we have focused our attention on the dimension of the functional space of polynomial networks. The dimension is the first and most basic descriptor of an algebraic variety, and in this context it provides an exact measure of the expressive power of an architecture. Our novel theoretical results include a general formula for the dimension of the architecture attained in high degree, as well as a tight lower bound and nontrivial upper bounds on the width of layers in order for the functional variety to be filling. We have also demonstrated intriguing connections with tensor and polynomial decompositions, including some which appear in very recent literature in algebraic geometry.

The tools and concepts introduced in this work for fully connected feedforward polynomial networks can be applied in principle to more general algebraic network architectures. Variations of our algebraic model could include multiple polynomial activations (rather than just single exponentiations) or more complex connectivity patterns of the network (convolutions, skip connections, etc.). The functional varieties of these architectures could be studied in detail and compared. Another possible research direction is a geometric study of the functional varieties, beyond the simple dimension. For example, the degree or the Euclidean distance degree draisma_euclidean_2013 of these varieties could be used to bound the number of critical points of a loss function. Additionally, motivated by Section 3.2, we would like to develop computational methods for constructing a network architecture that represents an assigned polynomial mapping. Such algorithms might lead to “closed form” approaches for learning using polynomial networks (similar to SVD or tensor decomposition), as a provable counterpoint to gradient descent methods. Our research program might also shed light on the practical problem of choosing an appropriate architecture for a given application.

Acknowledgements

We thank Justin Chen, Amit Moscovich, Claudiu Raicu and Steven Sam for their help. JK was partially supported by the Simons Collaboration on Algorithms and Geometry. MT and JB were partially supported by the Alfred P. Sloan Foundation, NSF RI-1816753 and Samsung Electronics.

References

Appendix A Technical proofs

We note entries of $\textup{Jac }\Phi_{\bm{d},r}(\theta)$ are polynomials in $\theta$, thus minors of $\textup{Jac }\Phi_{\bm{d},r}(\theta)$ are polynomials in $\theta$, so $\textup{Jac }\Phi_{\bm{d},r}(\theta)$ has a Zariski-generic rank (the largest size of minor that is a nonzero polynomial), which is also the maximum rank of $\textup{Jac }\Phi_{\bm{d},r}(\theta)$. By basic algebraic geometry, this is the dimension of $\mathcal{V}_{\bm{d},r}$ (see “generic submersiveness" of algebraic maps in characteristic 0 ). ∎

This is from the multi-homogeneity of the $r$-th power activation $\rho_{r}$ by substituting. ∎

For the unconditional result with differing degrees per layer, the argument runs closely along similar lines, but it relies on Proposition 15 in place of Conjecture 16. For brevity, details are omitted. ∎

More formally, the network map $\Phi_{(d_{0},\ldots,d_{h}),r}$ factors as:

We first point out that Proposition 17 gives an elementary proof $d_{i}=d_{0}-1$ is an asymptotic bottleneck. This is because as $h$ grows the ambient dimension grows like $O(d_{h}\cdot d_{0}^{r^{h-1}})$, while the RHS bound grows like $O(d_{h}\cdot d_{i}^{r^{h-i-1}})$, so if $d_{i}<d_{0}$ then $\mathcal{V}_{\bm{d},r}$ cannot fill for $h\gg 0$.

By the preceding discussion, the claim establishes $d_{i}=2d_{0}-2$ is an asymptotic bottleneck.