Title: POLYGAN: HIGH-ORDER POLYNOMIAL GENERATORS

Abstract: Generative Adversarial Networks (GANs) have become the gold standard when it comes to learning generative models for high-dimensional distributions. Since their advent, numerous variations of GANs have been introduced in the literature, primarily focusing on utilization of novel loss functions, optimization/regularization strategies and network architectures. In this paper, we turn our attention to the generator and investigate the use of high-order polynomials as an alternative class of universal function approximators. Concretely, we propose PolyGAN, where we model the data generator by means of a high-order polynomial whose unknown parameters are naturally represented by high-order tensors. We introduce two tensor decompositions that significantly reduce the number of parameters and show how they can be efficiently implemented by hierarchical neural networks that only employ linear/convolutional blocks. We exhibit for the first time that by using our approach a GAN generator can approximate the data distribution without using any activation functions. Thorough experimental evaluation on both synthetic and real data (images and 3D point clouds) demonstrates the merits of PolyGAN against the state of the art.

1. INTRODUCTION:

Generative Adversarial Networks (GANs) are currently one of the most popular lines of research in machine learning. Research on GANs mainly revolves around: (a) how to achieve faster and/or more accurate convergence (e.g., by studying different loss functions (Nowozin et al., 2016; Arjovsky & Bottou, 2017; Mao et al., 2017) or regularization schemes (Odena et al., 2018; Miyato et al., 2018; Gulrajani et al., 2017) ), and (b) how to design different hierarchical neural networks architectures composed of linear and non-linear operators that can effectively model high-dimensional distributions (e.g., by progressively training large networks (Karras et al., 2018) or by utilizing deep ResNet type of networks as generators (Brock et al., 2019) ).

Even though hierarchical deep networks are efficient universal approximators for the class of continuous compositional functions (Mhaskar et al., 2016) , the non-linear activation functions pose difficulties in their theoretical analysis, understanding, and interpretation. For instance, as illustrated in Arora et al. (2019) , element-wise non-linearities pose a challenge on proving convergence, especially in an adversarial learning setting (Ji & Liang, 2018) . Consequently, several methods, e.g., Saxe et al. (2014) ; Hardt & Ma (2017) ; Laurent & Brecht (2018) ; Lampinen & Ganguli (2019) , focus only on linear models (with respect to the weights) in order to be able to rigorously analyze the neural network dynamics, the residual design principle, local extrema and generalization error, respectively. Moreover, as stated in the recent in-depth comparison of many different GAN training schemes (Lucic et al., 2018) , the improvements may mainly arise from a higher computational budget and tuning and not from fundamental architectural choices.

In this paper, we depart from the choice of hierarchical neural networks that involve activation functions and investigate for the first time in the literature of GANs the use of high-order polynomials as an alternative class of universal function approximators for data generator functions. This choice is motivated by the strong evidence provided by the Stone-Weierstrass theorem (Stone, 1948) , which states that every continuous function defined on a closed interval can be uniformly approximated as closely as desired by a polynomial function. Hence, we propose to model the vector-valued generator function Gpzq : R d Ñ R o by a high-order multivariate polynomial of the latent vector z, whose unknown parameters are naturally represented by high-order tensors.

However, the number of parameters required to accommodate all higher-order correlations of the latent vector explodes with the desired order of the polynomial and the dimension of the latent vector. To alleviate this issue and at the same time capture interactions of parameters across different orders of approximation in a hierarchical manner, we cast polynomial parameters estimation as a coupled tensor factorization (Papalexakis et al., 2016; Sidiropoulos et al., 2017) that jointly factorizes all the polynomial parameters tensors. To this end, we introduce two specifically tailored coupled canonical polyadic (CP)-type of decompositions with shared factors. The proposed coupled decompositions of the parameters tensors result into two different hierarchical structures (i.e., architectures of neural network decoders) that do not involve any activation function, providing an intuitive way of generating samples with an increasing level of detail. This is pictorially shown in Figure 1 . The result of the proposed PolyGAN using a fourth-order polynomial approximator is shown in Figure 1 (a), while Figure 1 (b) shows the corresponding generation when removing the fourth-order power from the generator.

Our contributions are summarized as follows:

• We model the data generator with a high-order polynomial. Core to our approach is to cast polynomial parameters estimation as a coupled tensor factorization with shared factors.

To this end, we develop two coupled tensor decompositions and demonstrate how those two derivations result in different neural network architectures involving only linear (e.g., convolution) units. This approach reveals links between high-order polynomials, coupled tensor decompositions and network architectures.

• We experimentally verify that the resulting networks can learn to approximate functions with analytic expressions.

• We show how the proposed networks can be used with linear blocks, i.e., without utilizing activation functions, to synthesize high-order intricate signals, such as images.

• We demonstrate that by incorporating activation functions to the derived polynomial-based architectures, PolyGAN improves upon three different GAN architectures, namely DC-GAN (Radford et al., 2015) , SNGAN (Miyato et al., 2018) and SAGAN (Zhang et al., 2019) .

(a) (b)

Figure 1 : Generated samples by an instance of the proposed PolyGAN. (a) Generated samples using a fourth-order polynomial and (b) the corresponding generated samples when removing the terms that correspond to the fourth-order. As evidenced, by extending the polynomial terms, PolyGAN generates samples with an increasing level of detail.

2. METHOD:

In this Section, we investigate the use of a polynomial expansion as a function approximator for the data generator in the context of GANs. To begin with, we introduce the notation in Section 2.1. In Section 2.2, we introduce two different polynomials models along with specifically tailored coupled tensor factorizations for the efficient estimation of their parameters.

2.1. PRELIMINARIES AND NOTATION:

Matrices (vectors) are denoted by uppercase (lowercase) boldface letters e.g., X, (x). Tensors are denoted by calligraphic letters, e.g., X . The order of a tensor is the number of indices needed to address its elements. Consequently, each element of an M th-order tensor X is addressed by M indices, i.e., pX q i1,i2,...,i M . " x i1,i2,...,i M .

The mode-m unfolding of a tensor X P R I1ˆI2ˆ¨¨¨ˆI M maps X to a matrix X pmq P R ImˆĪm with Īm " ś M k"1 k‰m I k such that the tensor element x i1,i2,...,i M is mapped to the matrix element x im,j

where j " 1 `řM

k"1 k‰m pi k ´1qJ k with J k " ś k´1

n"1 n‰m I n . The mode-m vector product of X with a vector u P R Im , denoted by X ˆn u P R I1ˆI2ˆ¨¨¨ˆIn´1ˆIn`1ˆ¨¨¨ˆI N , results in a tensor of order M ´1: pX ˆm uq i1,...,im´1,im`1,...,i M "

EQUATION

Furthermore, we denote X ˆ1 u p1q ˆ2 u p2q ˆ3 ¨¨¨ˆM u pM q . " X ś m m"1 ˆmu pmq . The Khatri-Rao product (i.e., column-wise Kronecker product) of matrices A P R IˆN and B P R JˆN is denoted by A d B and yields a matrix of dimensions pIJq ˆN . The Hadamard product of A P R IˆN and B P R IˆN is defined as A ˚B and is equal to A pi,jq B pi,jq for the pi, jq element.

The CP decomposition (Kolda & Bader, 2009; Sidiropoulos et al., 2017) factorizes a tensor into a sum of component rank-one tensors. An M th-order tensor X P R I1ˆI2ˆ¨¨¨ˆI M has rank-1, when it is decomposed as the outer product of M vectors tu pmq P R Im u M m"1 . That is, X " u p1q ˝up2q ˝¨¨¨˝u pM q .

" M m"1 x pmq , where ˝denotes for the vector outer product. Consequently, the rank-R CP decomposition of an M th-order tensor X is written as:

X:

.

" rrU r1s , U r2s , . . . , U rM s ss "

EQUATION

where the factor matrices U rms " ru

pmq 1 , u pmq 2 , ¨¨¨, u pmq R s P R ImˆR ( M m"

1 collect the vectors from the rank-one components. By considering the mode-1 unfolding of X , the CP decomposition can be written in matrix form as (Kolda & Bader, 2009) :

EQUATION

More details on tensors and multilinear operators can be found in Kolda & Bader (2009) ; Sidiropoulos et al. (2017) .

2.2. HIGH-ORDER POLYNOMIAL GENERATORS:

GANs typically consist of two deep networks, namely a generator G and a discriminator D. G is a decoder (i.e., a function approximator of the sampler of the target distribution) which receives as input a random noise vector z P R d and outputs a sample x " Gpzq P R o . D receives as input both Gpzq and real samples and tries to differentiate the fake and the real samples. During training, both G and D compete against each other till they reach an "equilibrium" (Goodfellow et al., 2014) . In practice, both the generator and the discriminator are modeled as deep neural networks, involving composition of linear and non-linear operators (Radford et al., 2015) . In this paper, we focus on the generator. Instead of modeling the generator as a composition of linear and non-linear functions, we assume that each generated pixel x i " pGpzqq i may be expanded as a N th order polynomial1 in z. That is,

EQUATION

where the scalar β i , and the set of tensors W

rns i P R ś n

m"1 ˆmd ( N n"1 are the parameters of the polynomial expansion associated to each output of the generator, e.g., pixel. Clearly, when n " 1, the weights are d-dimensional vectors; when n " 2, the weights, i.e., W r2s i , form a d ˆd matrix. For higher orders of approximation, i.e., when n ě 3, the weights are n th order tensors.

By stacking the parameters for all pixels, we define the parameters β .

" rβ 1 , β 2 , . . . , β o s T P R o and W rns P R oˆś n m"1 ˆmd ( N n"1 . Consequently, the vector-valued generator function is expressed as:

EQUATION

Intuitively, ( 5) is an expansion which allows the N th order interactions between the elements of the noise latent vector z. Furthermore, (5) resembles the functional form of a truncated Maclaurin expansion of vector-valued functions. In the case of a Maclaurin expansion, W rns represent the n th order partial derivatives of a known function. However, in our case the generator function is unknown and hence all the parameters need to be estimated from training samples.

The number of the unknown parameters in ( 5) is pd N `1 ´1q o d´1 , which grows exponentially with the order of the approximation. Consequently, the model of ( 5) is prone to overfitting and its training is computationally demanding.

A natural approach to reduce the number of parameters is to assume that the weights exhibit redundancy and hence the parameter tensors are of low-rank. To this end, several low-rank tensor decompositions can be employed (Kolda & Bader, 2009; Sidiropoulos et al., 2017) . For instance, let the parameter tensors W rns admit a CP decompostion (Kolda & Bader, 2009) of mutilinear rank-k, namely, tW rns " rrU rns,1 , U rns,2 , . . . , U rns,pn`1q ssu N n"1 , with U rns,1 P R oˆk , and U rns,m P R dˆk , for m " 2, . . . , n `1. Then, (5) is expressed as

EQUATION

which has significantly less parameters than (5), especially when k ! d. However, a set of different factor matrices for each level of approximation are required in equation 6, and hence the hierarchical nature of images is not taken into account. To promote compositional structures and capture interactions among parameters in different orders of approximation we introduce next two coupled CP decompositions with shared factors.

Model 1: Coupled CP decomposition:

Instead of factorizing each parameters tensor individually we propose to jointly factorize all the parameter tensors using a coupled CP decomposition with a specific pattern of factor sharing. To illustrate the factorization, we assume a third order approximation (N " 3), however in the appendix a generalization to N -th order approximation is provided. Let us assume that the parameters tensors admit the following coupled CP decomposition with the factors corresponding to lower-order levels of approximation being shared across all parameters tensors. That is:

• Let W r1s " CU T r1s , be the parameters for first level of approximation.

• Let assume W r2s being a superposition of of two weights tensors, namely W r2s " W r2s 1:2

Ẁr2s:

1:3 , with W r2s i:j denoting parameters associated with the second order interactions across the i-th and j-th order of approximation. By enforcing the CP decomposition of the above tensors to share the factor with tensors corresponding to lower-order of approximation we obtain in matrix form: Symbol ˚refers to the Hadamard product.

W r2s p1q " CpU r3s d U r1s q T `CpU r2s d U r1s q T . z U [1] * + U [2] G(z) * + U [3] * + C β

• Similarly, we enforce the third-order parameters tensor to admit the following CP decomposition (in matrix form) W r3s p1q " CpU r3s d U r2s d U r1s q T . Note that all but the U r3s factor matrices are shared in the factorization of tensors capturing polynomial parameters for the first and second order of approximation.

The parameters are C P R oˆk , U rms P R dˆk for m " 1, 2, 3. Then, (6) for N " 3 is written as:

EQUATION

The third order approximation of ( 7) can be implemented as a neural network with the structure of Figure 2 (proved in section B, Claim 1 of the appendix). It is worth noting that the structure of the proposed network allows for incremental network growth.

Model 2: Coupled nested CP decomposition: Instead of explicitly separating the interactions between layers, we can utilize a joint hierarchical decomposition on the polynomial parameters. Let us first introduce learnable hyper-parameters b rns P R ω ( N n"1 , which act as scaling factors for each parameter tensor. Therefore, we modify (5) to:

EQUATION

with W rns P R oˆωˆś n m"1 ˆmd ( N n"1 . For illustration purposes, we consider a third order function approximation (N " 3). That is,

Gpzq " β `Wr1s ˆ2 b r1s ˆ3 z `Wr2s ˆ2 b r2s ˆ3 z ˆ4 z `Wr3s ˆ2 b r3s ˆ3 z ˆ4 z ˆ5 z (9)

To estimate its parameters we jointly factorize all parameters tensors by employing nested CP detecomposion with parameter sharing as follows (in matrix form)

• First order parameters :

W r1s p1q " CpA r3s d B r3s q T .

• Second order parametes:

W r2s p1q " C " A r3s d " ´Ar2s d B r2s ¯Sr3s * T .

• Third order parameters:

W r3s p1q " C " A r3s d "ˆA r2s d !´A r1s d B r1s ¯Sr2s ) ˙Sr3s * T

with C P R oˆk , A rns P R dˆk , S rns P R kˆk , B rns P R ωˆk for n " 1, . . . , N . Altogether, ( 9) is written as:

EQUATION

As we prove in the appendix (section B, Claim 3), ( 10) can be implemented in a hierarchical manner with a three-layer neural network as shown in Figure 3 .

Comparison between the two models: Both models are based on the polynomial expansion, however there are few differences between those. The Coupled CP decomposition has a simpler expression, however the Coupled nested CP decomposition relates to standard architectures using hierarchical composition that has recently yielded promising results in GANs (see Section 3). In the remainder of the paper, we use the Coupled nested CP decomposition by default; in Section G, we include an experimental comparison of the two models. The experimental comparison demonstrates that neither model outperforms the other in all datasets; they perform similarly.

b 

[1] B [1] * S [2] + * S [3] + * C + A [1] A [2] A [3] z B [2] B [3] b [2] b [3] β G(z)

3. RELATED WORK:

The literature on GANs is vast; we focus only on the works most closely related to ours. The interested reader can find further information in a recent survey (Creswell et al., 2018) . Berthelot et al. (2017) use skip connections to concatenate the noise z in deeper layers in the generator. The recent BigGAN (Brock et al., 2019 ) performs a hierarchical composition through skip connections from the noise z to multiple resolutions of the generator. In their implementation, they split z into one chunk per resolution and concatenate each chunk (of z) to the respective resolution.

Despite the propagation of the noise z to successive layers, the aforementioned works have substantial differences from ours. We introduce a well-motivated and mathematically elaborate method to achieve a more precise approximation with a polynomial expansion. In contrast to the previously mentioned works, we also do not concatenate the noise with the feature representations, but rather perform multiplication of the noise with the feature representations, which we mathematically justify.

The work that is most closely related to ours is the recently proposed StyleGAN (Karras et al., 2019) , which is an improvement over the Progressive Growing of GANs (ProGAN) (Karras et al., 2018) . As ProGAN, StyleGAN is a highly-engineered network that achieves compelling results on synthesized 2D images. In order to provide an explanation on the improvements of StyleGAN over ProGAN, the authors adopt arguments from the style transfer literature (Huang & Belongie, 2017) . Nevertheless, the idea of style transfer proposes to use features from images for conditional image translation, which is very different to unsupervised samples (image) generation. We believe that these improvements can be better explained under the light of our proposed polynomial function approximation. That is, as we show in Figure 1 , the Hadamard products build a hierachical decomposition with increasing level of detail (rather than different styles). In addition, the improvements in StyleGAN (Karras et al., 2019) are demonstrated by using a well-tuned model. In this paper we showcase that without any complicated engineering process the polynomial generation can be applied into several architectures (or any other type of decoders) and consistently improves the performance.

4. EXPERIMENTS:

A sequence of experiments in both synthetic data (2D and 3D data manifolds) and higher-dimensional signals are conducted to assess the empirical performance of the proposed polynomial expansion.

The first experiments are conducted on a 2D manifolds that are analytically known (Section 4.1).

Further experiments on three 3D manifolds are deferred to the appendix (Section D). In Section 4.2, the polynomial expansion is used for synthesizing digits. Experiments on images beyond digits are conducted in Section E; more specifically, we experiment with images of faces and natural scenes. The experiments with such images demonstrate how polynomial expansion can be used for learning highly complex distributions by using a single activation function in the generator. Lastly, we augment our polynomial-based generator with non-linearities and show that this generator is at least as powerful as contemporary architectures.

Apart from the polynomial-based generators, we implemented two variations that are considered baselines: (a) 'Concat': we replace the Hadamard operator with concatenation (used frequently in recent methods, such as in Brock et al. ( 2019)), (b) 'Orig': the Hadamard products are ditched, while use b r1s Ð z, i.e., there is a composition of linear layers that transform the noise z.

4.1. SYNTHETIC EXPERIMENT ON 2D MANIFOLD:

Sinusoidal: We assess the polynomial-based generator on a sinusoidal function in the bounded domain r0, 2πs. Only linear blocks, i.e., no activation functions, are used in the generator. That is, all the element-wise non-linearities (such as ReLU's, tanh) are ditched. The distribution we want to match is a sin x signal. The input to the generator is z P R and the output is rx, sin xs with x P r0, 2πs. We assume a 12 th order approximation where each S ris , A ris is a fully-connected layer and B ris is an identity matrix. Each fully-connected layer has width 15. In Figure 4 , 2, 000 random samples are synthesized. We indeed verify that in low-dimensional distributions, such as the univariate sinusoidal, PolyGAN indeed approximates the data distribution quite accurately without using any non-linear activation functions. 

4.2. DIGIT GENERATION WITH LINEAR BLOCKS:

The linear generator of the previous section is extended to greyscale images, in which an analytic expression of the ground-truth distribution remains elusive. To our knowledge, there has not been a generation of greyscale images based on polynomial expansion in the past.

We capitalize on the expressivity of the recent resnet-based generator (Miyato et al., 2018; Brock et al., 2019) , to devise a new polynomial generator Gpzq : R 128 Ñ R 32x32 . We consider a fourth-order approximation (as derived in ( 5)) where B ris is the identity matrix, S ris is a residual block with two convolutions for i " 1, . . . , 4. We emphasize that the residual block as well as all layers are linear, i.e., there are no activation functions. We only add a tanh in the output of the generator for normalization purposes. The discriminator and the optimization procedure are the same as in SNGAN; the only difference is that we run one discriminator step per generator step (n dis " 1). Note that the 'Orig' resnet-based generator resembles the generator of Miyato et al. (2018) in this case.

We perform digit generation (trained on MNIST (LeCun et al., 1998) ). In Figure 5 , random samples are visualized for the three compared methods. Note that the two baselines have practically collapsed into a single number each, whereas PolyGAN does synthesize plausible digits.

To further assist the generation process, we utilize the labels and train a conditional GAN. That is, the class labels are used for conditional batch normalization. As illustrated in Figure 6 , the samples synthesized are improved over the unsupervised setting. 'Orig' and 'Concat' still suffer from severe mode collapse, while PolyGAN synthesizes digits that have different thickness (e.g. 9), style (e.g. 2) and rotation (e.g. 1). 

5. CONCLUSION:

We express data generation as a polynomial expansion task. We model the high-order polynomials with tensorial factors. We introduce two tailored coupled decompositions and show how the polynomial parameters can be implemented by hierarchical neural networks, e.g. as generators in a GAN setting. We exhibit how such polynomial-based generators can be used to synthesize images by utilizing only linear blocks. In addition, we empirically demonstrate that our polynomial expansion can be used with non-linear activation functions to improve the performance of standard state-of-the-art architectures. Finally, it is worth mentioning that our approach reveals links between high-order polynomials, coupled tensor decompositions and network architectures. Algorithm 1: PolyGAN (model 1).

Input :Noise z P R d , N P N Output :x P R o % global transformation(s) of z. v = Linear(z) % first layer. κ " pU r1s q T v for n=2:N do % Perform the Hadamard product for the n th layer.

κ " κ `´pU rns q T v ¯˚κ end

x " β `Cκ.

Algorithm 2: PolyGAN (model 2).

Input :Noise z P R d , N P N Output :x P R o 1 % global transformation(s) of z. 2 v = Linear(z) 3 % first layer. 4 κ " ´pB r1s q T b r1s ¯˚´p A r1s q T v 5 for n=2:N do 6

% Multiply with the current layer weight S rns and perform the Hadamard product.

κ " ´Srns κ `pB rns q T b rns

¯˚´p A rns q T v 7 end 8 x " β `Cκ.

Table 2 : The pseudocode for the two models for N th order polynomial approximation.

A INTRODUCTION:

The appendix is organized as:

• Section B provides the Lemmas and their proofs required for our derivations.

• Section C generalizes the Coupled CP decomposition for N th order expansion.

• Section D extends the experiments to 3D manifolds.

• In Section E, additional experiments on image generation with linear blocks are conducted.

• Comparisons with popular GAN architectures are conducted in Section F. Specifically, we utilize three popular generator architectures and devise their polynomial equivalent and perform comparisons on image generation. We also conduct an ablation study indicating how standard engineering techniques affect the image generation of the polynomial generator. • In Section G, a comparison between the two proposed decompositions is conducted on data distributions from the previous Sections.

B PROOFS:

For a set of matrices tX m P R ImˆN u N m"1 the Khatri-Rao product is denoted by:

EQUATION

In this section, we prove the following identity connecting the sets of matrices

tA ν R Iν ˆK u N ν"1 and tB ν R Iν ˆLu N ν"1 : p N ä ν"1 A ν q T ¨p N ä ν"1 B ν q " pA T 1 ¨B1 q ˚pA T 2 ¨B2 q ˚. . . ˚pA T N ¨BN q (12)

To demonstrate the simple case with two matrices, we prove first the special case with N " 2. Lemma 1. It holds that

pA 1 d A 2 q T ¨pB 1 d B 2 q " pA T 1 ¨B1 q ˚pA T 2 ¨B2 q (13)

Proof. Initially, both sides of the equation have dimensions of K ˆL, i.e., they match. The pi, jq element of the matrix product of pA T 1 ¨B1 q is B.1 PROOFS FOR MODEL 1

Below, we prove that (7) (main paper) is equivalent to the three-layer neural network as shown in Figure 2 .

Claim 1. Let ω " ´U T r2s z ¯˚´U T r1s z ¯`U T r1s z.

Then, the form of ( 7) is equal to:

EQUATION

Proof. Applying Lemma 2 on (7), we obtain:

Gpzq " β `C" U T r1s z `´U T r3s z ¯˚´U T r1s z ¯`´U T r2s z ¯˚´U T r1s z ¯Ù T r3s z ¯˚´U T r2s z ¯˚´U T r1s z ¯* " β `C" ´U T r3s z ¯˚"´U T r2s z ¯˚´U T r1s z ¯`U T r1s z ı `´U T r2s z ¯˚´U T r1s z ¯`U T r1s z * (22)

The last equation is the same as (21).

B.2 PROOFS FOR MODEL 2:

In Claim 2 and Claim 3, we prove that (10) (main paper) is equivalent to the three-layer neural network as shown in Figure 3 . Claim 2. Let ω " ˆpA r2s q T z ˙˚" pB r2s q T b r2s `pS r2s q T "ˆp

A r1s q T z ˙˚ˆp B r1s q T b r1s ˙* (23) It holds that ω " " A r2s d "´A r1s d B r1s ¯Sr2s ı * T ´z d z d b r1s ¯`´A r2s d B r2s ¯T ´z d b r2s ¯(24)

Proof. We will prove the equivalence starting from ( 23) and transform it into (24). From (23):

EQUATION

where in the last equation, we have applied Lemma 1. Applying the Lemma once more in the last term of (25), we obtain (24).

EQUATION

with ω as in Claim 2. Then, it holds for Gpzq of (10) that Gpzq " λ.

Proof. Transforming ( 26) into (10):

EQUATION

To simplify the notation, we define M 1 "

" A r2s d "´A r1s dB r1s ¯Sr2s ı * and M 2 " ´Ar2s dB r2s ¯. Then, ω " M T 1 ´z d z d b r1s ¯`M T 2 ´z d b r2s ¯.

The last term of ( 27) becomes:

ˆpA r3s q T z ˙˚ˆp S r3s q T ω ˙" ˆpA r3s q T z ˙˚"ˆM 1 S r3s ˙T ´z d z d b r1s ¯M 2 S r3s ˙T ´z d b r2s ¯ " " A r3s d ˆM1 S r3s ˙T ´z d z d z d b r1s ¯`" A r3s d ˆM2 S r3s ˙T ´z d z d b r2s ¯(28)

Replacing ( 28) into ( 27), we obtain (10).

Note that the λ in Claim 3 is the equation behind Figure 3 . By proving the claim, we have illustrated how the polynomial generator can be transformed into a network architecture for third-order approximation.

C DERIVATIONS:

In this Section, we will show how the Coupled CP decomposition generalizes to the N th order approximation. It suffices to find the decomposition that converts the N th order polynomial into a network structure (see Alg. 1). Sin3D: The data manifold is an extension over the 2D manifold of the sinusoidal experiment (Section 4.1). The function we want to learn is Gpzq : R2 Ñ R 3 with the data manifold described by the vector rx, y, sinp10 ˚ax 2 `y2 qs for x, y P r´0.5, 0.5s.

In Figure 8 , 20, 000 samples are sampled from the generators and visualized. PolyGAN captures the data distribution, while 'Orig' and 'Concat' fail. Swiss roll: The three dimensional vector rt¨sin t, y, t¨cos ts`0.05¨s for t, y P r0, 1s and s " N p0, 1q forms the data manifold 2 . In Figure 9 , 20, 000 samples are visualized. Gabriel's Horn: The three dimensional vector rx, α ¨cos t x , α ¨sin t x s for t P r0, 160πs and x P r1, 4s forms the data manifold. The dependence on both sinusoidal and the function 1

x makes this curve challenging for a polynomial expansion. In Figure 10 , the synthesized samples are plotted. PolyGAN learns how to generate samples on the manifold despite the fraction in the parametric form.

E IMAGE GENERATION WITH LINEAR BLOCKS:

Apart from digit generation (Section 4.2), we conduct two experiments on image generation of face and natural scenes. Since both distributions are harder than the digits one, we extend the approximation followed on Section 4.2 by one order, i.e., we assume a fifth-order approximation. We emphasize that each block is a residual block with no activation functions. In Table 3 , we evaluate the standard metrics of Inception Score (IS) and Frechet Inception Distance (FID) (see more details for the metrics in section F). Our model outperforms both 'Orig' and 'Concat' by a considerable margin. In Figure 12 , some random synthesized samples are presented. Figure 12 : Conditional image generation on CIFAR10 for a generator with linear blocks and a single activation function. Our approach generates more realistic samples in comparison to the compared methods, where severe mode collapse also takes place.

F IMAGE GENERATION WITH ACTIVATION FUNCTIONS:

To demonstrate the flexibility of the PolyGAN, we utilize three different popular generators. The three acrhitectures chosen are DCGAN (Radford et al., 2015) , SNGAN (Miyato et al., 2018), and SAGAN (Zhang et al., 2019) . Each original generator is converted into a polynomial expansion, while we use the non-linearities to boost the performance of the polynomial generator. The hyperparameters are kept the same as the corresponding baseline. Algorithms 3 and 4 succinctly present the key differences of our approach compared to the traditional one (in the case of SNGAN, similarly for other architectures).

In addition to the baseline, we implement the most closely related alternative to our framework, namely instead of using the Hadamard operator as in Figure 3 , we concatenate the noise with the feature representations at that block. The latter approach is frequently used in the literature (Berthelot et al., 2017; Brock et al., 2019 ) (referred as "Concat" in the paper). The number of the trainable parameters of the generators are reported in Table 13 . Our method has only a minimal increase of the parameters, while the concatenation increases the number of parameters substantially.

To reduce the variance often observed during GAN training (Lucic et al., 2018; Odena et al., 2018) , each reported score is averaged over 10 runs utilizing different seeds. The metrics we utilize are Inception Score (IS) (Salimans et al., 2016) and Frechet Inception Distance (FID) (Heusel et al., 2017) .

Below, we perform an ablation study on Section F.2, and then present the experiments on unsupervised (Section F.3) and conditional image generation (Section F.4) respectively.

Datasets: We use CIFAR10 (Krizhevsky et al., 2014) and Imagenet (Russakovsky et al., 2015) as the two most widely used baselines for GANs:

• CIFAR10 (Krizhevsky et al., 2014) includes 60, 000 images of 32 ˆ32 resolution. We use 50, 000 images for training and the rest for testing.

• Imagenet (Russakovsky et al., 2015) is a large scale dataset that includes over one million training images and 50, 000 validation images. We reshape the images to 128 ˆ128 resolution.

Baseline architectures: The architectures employed are:

• DCGAN (Radford et al., 2015) , as implemented in https://github.com/pytorch/ examples/tree/master/dcgan. This is a widely used baseline. • SNGAN (Miyato et al., 2018) , as implemented in https://github.com/ pfnet-research/sngan_projection. SNGAN is a strong performing GAN that introduced a spectral normalization in the discriminator.

• SAGAN (Zhang et al., 2019) , as implemented in https://github.com/voletiv/ self-attention-GAN-pytorch. This is a recent network architecture that utilizes 

:

With an N th order polynomial we can approximate any smooth function(Stone, 1948).

This is a standard synthetic distribution in popular machine learning frameworks such as scikit-learn.

A similar transformation is performed in other GAN architectures, such as inKarras et al. (2019).

Given the batch size difference, our training corresponds to roughly the 100, 000 steps of the authors' reported results.

Figures and Tables:

Figure 2: Schematic illustration of the Coupled CP decomposition (for third order approximation). Symbol ˚refers to the Hadamard product.

Figure 3: Schematic illustration of the Coupled nested CP decomposition (for third order approximation). Symbol ˚refers to the Hadamard product.

Figure 4: Synthesized data for learning the rx, sin xs signal. No activation functions are used in the generators. From left to right: (a) the data distribution, (b) 'Orig', (c) 'Concat', (d) PolyGAN. Notably, neither 'Orig' nor 'Concat' can learn to approximate different Taylor terms.

Figure 5: Synthesized data for MNIST with a single activation in the generator. From left to right: (a) The ground-truth signals, (b) 'Orig', (c) 'Concat', (d) PolyGAN.

Figure6: Conditional digit generation. Note that both 'Orig' and 'Concat' suffer from severe mode collapse (details in section 4.2). On the contrary, PolyGAN synthesizes digits that have different thickness (e.g. 9), style (e.g. 2) and rotation (e.g. 1).

Figure 7: Synthesized data for learning the 'astroid' signal. No activation functions are used in the generators.

Figure 8: Experiment on 3D synthetic data. From left to right: (a) the data distribution, (b) 'Orig', (c) 'Concat', (d) PolyGAN. As expected, the 'Orig' and the 'Concat' cannot capture the data distribution.

Figure 9: Experiment on 3D synthetic data ('swiss roll'). From left to right: (a) the data distribution, (b) 'Orig', (c) 'Concat', (d) PolyGAN.

Figure 10: Synthesized data on 'Gabriel's Horn'. From left to right: (a) the data distribution, (b) 'Orig', (c) 'Concat', (d) PolyGAN.

In the experiment with faces, we utilize as the training samples the YaleB(Georghiades et al., 2001) dataset. The dataset includes greyscale images of faces under extreme illuminations. We rescale all of the images into 64 ˆ64 for our analysis.Random samples are illustrated in Figure11. Our method generates diverse images and captures the case of illuminating either half part of the face, while 'Orig' and 'Concat' generate images that have a dark side only on the left and right side, respectively. The difference becomes profound in the finer details of the face (please zoom in), where both baselines fail to synthesize realistic semantic parts of the face.

Figure11: Image generation on faces(YaleB (Georghiades et al., 2001)) for a generator with linear blocks and a single activation function only on the output (i.e., tan h). Notice that our method can illuminate either the left or right part of the face, in contrast to 'Orig' (and 'Concat') which generate images that have a dark side only on the left (respectively right) side. In addition, both 'Orig' and 'Concat' fail to capture the fine details of the facial structure (please zoom in for the details).

Figure 13: Synthesized data for learning the rx, sinpxqs signal. No activation functions are used in the generators. From left to right: (a) the data distribution, (b) Coupled CP decomposition, (c) Coupled nested CP decomposition.

Figure 14: Synthesized data for learning the Astroid. Both models generate only plausible examples.

Figure 15: Experiment on 3D synthetic data. From left to right: (a) the data distribution, (b) Coupled CP decomposition, (c) Coupled nested CP decomposition.

Figure 16: Experiment on 3D synthetic data ('swiss roll'). From left to right: (a) the data distribution, (b) Coupled CP decomposition, (c) Coupled nested CP decomposition. Note that Coupled CP decompositiongenerates some noisy samples in contrast to Coupled nested CP decomposition.

Figure 17: Comparison of the two decompositions on digit generation.

S rns , B rns R dˆk , R kˆk , R ωˆk Matrix parameters in the hierarchical decomposition.

Table content: <table><tr><td/><td/><td>: Nomenclature</td></tr><tr><td>Symbol</td><td>Dimension(s)</td><td>Definition</td></tr><tr><td>n, N</td><td>N</td><td>Polynomial term order, total approximation order.</td></tr><tr><td>k</td><td>N</td><td>Rank of the decompositions.</td></tr><tr><td>z</td><td>R d</td><td>Input to the polynomial approximator, i.e., generator.</td></tr><tr><td>C, β</td><td>R oˆk , R o</td><td>Parameters in both decompositions.</td></tr><tr><td colspan="2">A rns , d, ˚-</td><td>Khatri-Rao product, Hadamard product.</td></tr></table>

Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note on the evaluation of generative models. In International Conference on Learning Representations (ICLR), 2016. Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In IEEE Proceedings of International Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7794-7803, 2018. Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. In International Conference on Machine Learning (ICML), 2019.

Table content: <table/>

IS/FID scores on CIFAR10(Krizhevsky et al., 2014) with linear blocks.

Table content: <table><tr><td colspan="3">conditional SNGAN with linear blocks on CIFAR10</td></tr><tr><td>Model</td><td>IS (Ò)</td><td>FID (Ó)</td></tr><tr><td>Orig</td><td>4.47 ˘0.21</td><td>156.67 ˘12.29</td></tr><tr><td>Concat</td><td>4.23 ˘0.37</td><td>188.08 ˘17.00</td></tr><tr><td colspan="2">PolyGAN 6.43 ˘0.11</td><td>53.50 ˘2.71</td></tr></table>

Number of parameters for the generators of each approach and on various databases. As can be seen, our method only marginally increases the parameters while substantially improving the performance. On the other hand, "Concat" significantly increases the parameters without analogous increase in the performance.

Table content: <table><tr><td>DCGAN (CIFAR10) Model Params Orig 3, 573, 440 Concat 6, 416, 448 PolyGAN 3, 663, 936</td><td>SNGAN (CIFAR10) Model Params Orig 4, 276, 739 Concat 6, 383, 875 PolyGAN 4, 408, 835</td><td>SAGAN (Imagenet) Model Params Orig 42, 079, 300 PolyGAN 42, 351, 748</td></tr></table>

Peer review (iclr2020):
This paper proposes to replace the generator in GANs by a single-layer polynomial generator. In other words, the usual deep network of the generator is replaced by linear tensor product. Although the tensor product are linear in each parameter of the noise vector, they involve multiplications between tuples of input parameters and are therefore more expressive than a single linear layer (single matrix multiplication). The results are presented on synthetic low dimensional data, MNIST, YaleB and CIFAR10. Although it is always difficult to judge the quality of GAN generated samples, the samples presented are of poor quality compared to the state of the art. My main objection to this paper is that it does not present a clear justification for their approach. It does not seem to work better empirically, and there is no strong theoretical justification. The authors explain well that polynomial can approximate any function, but that is also the case of many approximators, including deep neural networks. The main thing that this paper shows, in my opinion, is that the GAN framework is robust to different kinds of generators, but that is not the stated point of this paper. Besides, polynomial approximators tend to produce unstable approximations when their degree increases, which is not addressed in the paper. Why not use approximators that were proven to be stable, such as splines of wavelets, is not well explained. I am actually surprised that the polynomial generator is stable enough to generate samples. One possible reason is that GAN training (with a discriminator) makes the generated polynomials more stable, which could be an interesting result if investigated. The overall structure of the paper is acceptable, although many of the notations that are introduced early in the paper are actually only useful in the appendix and should probably be moved there. I would suggest publishing this paper in a workshop.