Title: ON COMPUTATION AND GENERALIZATION OF GENER-ATIVE ADVERSARIAL NETWORKS UNDER SPECTRUM CONTROL

Abstract: Generative Adversarial Networks (GANs), though powerful, is hard to train. Several recent works (Brock et al., 2016; Miyato et al., 2018) suggest that controlling the spectra of weight matrices in the discriminator can significantly improve the training of GANs. Motivated by their discovery, we propose a new framework for training GANs, which allows more flexible spectrum control (e.g., making the weight matrices of the discriminator have slow singular value decays). Specifically, we propose a new reparameterization approach for the weight matrices of the discriminator in GANs, which allows us to directly manipulate the spectra of the weight matrices through various regularizers and constraints, without intensively computing singular value decompositions. Theoretically, we further show that the spectrum control improves the generalization ability of GANs. Our experiments on CIFAR-10, STL-10, and ImgaeNet datasets confirm that compared to other methods, our proposed method is capable of generating images with competitive quality by utilizing spectral normalization and encouraging the slow singular value decay.

1. INTRODUCTION:

Many efforts have been recently devoted to studying Generative Adversarial Networks (GANs, Goodfellow et al. (2014) ). GANs provide a general unsupervised framework to learn a generative model from unlabeled real data. Successful applications of GANs include many unsupervised learning tasks, such as image generation, dialogue generation, and image inpainting (Abadi & Andersen, 2016; Goodfellow, 2016; Ho & Ermon, 2016; Li et al., 2017; Yu et al., 2018) . Different from other unsupervised learning methods, which directly maximize the likelihood of deep generative models (e.g., Variational Auto-encoder, Nonlinear ICA, and Restricted Boltzmann Machine), GANs introduce a competition between two neural networks. Specifically, one neural network serves as the generator that yields artificial samples, and the other serves as the discriminator that distinguishes the artificial samples from the real data.

Mathematically, GANs can be formulated as the following min-max optimization problem:

EQUATION

where {x i } n i=1 are n real data points, G θ denotes the generative deep neural network parameterized by θ, D W denotes the discriminative neural network parameterized by W, D G θ denotes the distribution generated by G θ , φ(•) : [0, 1] → R is a properly chosen monotone function, and A(•) denotes a monotone function related to the function φ(•). There have been many options for φ(•) and A(•) in existing literature. For example, the original GAN proposed in Goodfellow et al. (2014) chooses φ(x) = log(x), A = 1 1+exp(-x) ; Arjovsky et al. (2017) use φ(x) = x, A(x) = x, and (1) becomes the Wasserstein GAN. Min-max problem (1) has a natural interpretation: The minimization problem aims to find a discriminator D W , which can distinguish between the real data and the artificial samples generated by G θ , while the maximization problem aims to find a generator G θ , which can fool the discriminator D W . From the perspective of game theory, the generator and discriminator are essentially two players competing with each other and eventually achieving some equilibrium.

From an optimization perspective, problem (1) is a nonconvex-nonconcave min-max problem, that is, f (θ, W) is nonconvex in θ given a fixed W and nonconcave in W given a fixed θ. Unlike convexconcave min-max problems, which have been well studied in existing optimization literature, there is very limited understanding of general nonconvex-nonconcave min-max problems. Thus, most of existing algorithms for training GANs are heuristics. Although some theoretical guarantees have been established for a few algorithms, they all require very strong assumptions, which are not satisfied in practice (Heusel et al., 2017) .

Despite of the lack of theoretical justifications, significant progress has been made in empirical studies of training GANs. Numerous empirical evidence has suggested several approaches for stabilizing the training of the discriminator, which can eventually improve the training of the generator. For example, Goodfellow et al. (2014) adopt a simple algorithmic trick that updates W for multiple iterations after updating θ for one iteration, i.e., training the discriminator more frequently than the generator. Besides, Xiang & Li (2017) suggest that the weight normalization approach proposed in Salimans & Kingma (2016) can also stabilize the training of the discriminator. More recently, Miyato et al. (2018) propose a spectral normalization approach to control the spectral norm of the weight matrix in each layer. Specifically, in each forward step, they normalize the weight matrix by the approximation of its spectral norm, which is obtained by the one-step power method. They further show that spectral normalization essentially controls the Lipschitz constant of the discriminator with respect to the input. Compared to other methods for controlling the Lipschitz constant of the discriminator, e.g., gradient penalty (Gulrajani et al., 2017; Gao et al., 2017) , the experiments in Miyato et al. (2018) show that the spectral normalization approach achieves better performance with fairly low computational cost. Moreover, Miyato et al. (2018) show that spectral normalization suffers less from the mode collapse, that is, the generator outputs only over a fairly small support. Such a phenomenon, though not well understood, suggests that the spectral normalization will balance the discrimination and representation well.

Besides the aforementioned algorithmic tricks and normalization approaches, regularization can also stabilize the training of the discriminator (Brock et al., 2016; Roth et al., 2017; Nagarajan & Kolter, 2017; Liu et al., 2018) . For instance, orthogonal regularization, proposed by Brock et al. (2016) , forces the columns of weight matrices in the discriminator to be orthonormal by augmenting the objective function f (θ, W) with λ L i=1 W i W i -I F , where λ > 0 is the regularization parameter, W i denotes the weight matrix of the i-th layer in the discriminator, I denotes the identity matrix, and L is the depth of the discriminator. The experimental results in Brock et al. (2016) show that the orthogonal regularization improves the performance and generalization ability of GANs. However, the empirical evidence in Miyato et al. (2018) shows that the orthogonal regularization is still less competitive than the spectral normalization approach. One possible explanation is that the orthogonal normalization, forcing all non-zero singular values to be 1, is more restrictive than the spectral normalization, which only forces the largest singular value of each weight matrix to be 1.

Motivated by the spectral normalization, we propose a novel training framework, which provides more flexible and precise control over the spectra of weight matrices in the discriminator. Specifically, we reparameterize each weight matrix 

W i ∈ R di×di+1 as W i = U i E i V i ,

(x; U, E, V) = U L E L V L σ L-1 (• • • σ 1 (U 1 E 1 V 1 x) • • • ), where σ i (•)

is the entry-wise activation operator of the i-th layer, U := {U 1 , ..., U L }, E := {E 1 , ..., E L }, and V := {V 1 , ..., V L } denote the parameters of the discriminator D, and x denotes the input vector. This reparameterization allows us to control the spectra of the original weight matrix W i by manipulating E i . For example, we can rescale E i by its largest diagonal element, which essentially is the spectral normalization. Besides, we can also manipulate the diagonal entries of E i to control the decays in singular values (e.g., fast or slow decays). Recall that our reparameterization requires U i and V i to have orthonormal columns. This requirement can be achieved by several methods in the existing literature, such as the stiefel manifold gradient method. However, Huang et al. (2017) show that the stochastic stiefel manifold gradient method is unstable. Moreover, other methods, such as cayley transformation and householder transformation, suffer from several disadvantages: (I). High computational cost1 ; (II). Sophisticated implementation (Shepard et al., 2015) . Different from the methods mentioned above, our framework applies the orthogonal regularization to all U i 's and V i 's. Such a regularization suffices to guarantee the approximate orthogonality of U i 's and V i 's in practice, which is supported by our experiments. Moreover, our experimental results on CIFAR-10, STL-10 and ImageNet datasets show that our proposed method achieves competitive performance on CIFAR-10 and better performance than the spectral normalization and other competing approaches on STL-10 and ImageNet. Besides the empirical studies, we provide theoretical analysis, which characterizes how the spectrum control benefits the generalization ability of GANs. Specifically, denote µ as the underlying data distribution and ν n as the distribution given by the well trained generator. We establish a generalization bound under spectrum control as follows (informal): 

d F ,φ (µ, ν n ) ≤ inf ν∈D G d F ,φ (µ, ν) + O d 2 L n , where d = max{d 1 , . . . , d L }, d F ,φ (•, •) is the F-distance,

2. METHODOLOGY:

We present a new framework for flexibly controlling the spectra of weight matrices. We first consider an L-layer discriminator D as follows:

EQUATION

where σ i (•) denotes the entry-wise activation operator of the i-th layer, W i ∈ R di+1×di denotes the weight matrix of the i-th layer, x ∈ R d1 denotes the input feature, W := {W 1 , ..., W L } denotes the parameters of the discriminator D, and d L+1 = 1.

2.1. SVD REPARAMETERIZATION:

Our framework directly applies an SVD reparameterization to each weight matrix W i in the discriminator D, i.e.,

W i = U i E i V i , where r i = min(d i , d i+1 ), U i ∈ R di+1×ri and V i ∈ R di×ri denote two matrices with orthonormal columns, E i = diag(e i 1 , • • • , e i ri

) denotes a diagonal matrix, and e i 1 ≥ • • • ≥ e i ri ≥ 0 are the singular values of W i . The discriminator can be rewritten as follows:

EQUATION

where U := {U 1 , ..., U L }, E := {E 1 , ..., E L }, and V := {V 1 , ..., V L } 2 denote the parameters of the discriminator D. Throughout the rest of the paper, if not clear specified, we denote D(x; U, E, V) by D(x) for notational simplicity. The motivation behind this reparameterization is to control the singular values of each weight matrix W i by explicitly manipulating E i . We then consider a new min-max problem as follows:

EQUATION

) where I i denotes the identity matrix of size r i , R(E) is the regularizer with a regularization parameter γ > 0, and Ω denotes a feasible set. By choosing different Ω and R(E), (4) can control the spectrum of the weight matrix W i flexibly. For example, if we take the feasible set Ω = {E : e i j = 1 ∀e i j ∈ E i , E i ∈ E} and R(E) = 0, then our method essentially is the orthogonal regularization. We will discuss some options of Ω and R(E) later in detail.

As mentioned earlier, the orthogonal constraints in (4) suffer from the high computational cost and sophisticated implementation. To address these drawbacks, we directly apply the orthogonal regularization to all U i 's and V i 's. Therefore, problem (4) becomes

EQUATION

where λ > 0 is a regularization parameter. A relative large λ (e.g., λ = 1), ensures the orthogonality of U i and V i . See more details in Section 4.1. Moreover, (5) can be efficiently solved by stochastic gradient algorithms. Projection may be needed to handle the constraint Ω. See more details later.

2.2. SPECTRUM CONTROL:

We provide a few options of Ω and R(E) for controlling the spectra of weight matrices in the discriminator, which is motivated by Miyato et al. (2018) . Miyato et al. (2018) have shown that for an L-layer discriminator D, we have:

EQUATION

)

where ρ i is the Lipschitz constant of σ i (•). The last equation holds for our proposed reparameterization. For commonly used activation operators, such as the sigmoid, ReLU, and leak-ReLU functions, ρ i ≤ 1. Therefore, L i=1 e i 1 is essentially an upper bound for the Lipschitz constant, which can be controlled by our proposed Ω and R(E). Note that W L is a vector with only one singular value. For simplicity, we set e L 1 = 1 in the following analysis.

2.2.1. FLEXIBLE SPECTRAL CONTROL:

Comparing to the orthogonal regularization, Miyato et al. (2018) suggest that we should allow more flexibility by using spectral normalization, which only bounds the largest singular value. They implement spectral normalization by one-step power iteration.

• Spectrum Normalization: We can also easily implement spectral normalization under our SVD reparameterization framework. Specifically, the spectral normalization rescales the weight matrix E i by its spectral norm e i 1 , which is equivalent to solving the following problem:

min θ max Q(E),U ,V f (θ, Q(E), U, V) -λ L i=1 ( U i U i -I i 2 F + V i V i -I i 2 F ),

where

Q := { E1 e 1 1 , . . . , E L e L 1 }.

• Spectrum Constraint: Note that the spectral normalization essentially reparameterize the Lipschitz constraint Ω:

EQUATION

This essentially controls L i=1 e i 1 by forcing each e i 1 ≤ 1. Instead of spectral normalization, we consider directly solving the problem with the Lipschitz constraint. To maintain the feasibility of E, we only need a simple projection for each E i in the back propagation, which can be implemented by a simple entry-wise clipping operator defined as g(t)

EQUATION

where 1 t∈A = 1 if t ∈ A, and 0 otherwise. These two methods are essentially solving the same problem, but in different formulations. Therefore, different algorithms are adopted. Due to the nonconvex-nonconcave structure of (5), different solutions are obtained.

• Lipschitz Regularizer: We can also directly penalize Compared to the spectral constraint, which enforces all e i 1 ≤ 1, the Lipschitz regularizer is more flexible since it allows e i 1 > 1 for some i ∈ [L].

2.2.2 SLOW SINGULAR VALUE DECAY Miyato et al. (2018) owe their empirical success of training SN-GAN to controlling the spectral norm while allowing flexibility. This perspective, however, is not very concrete. As we know, orthogonal regularization and spectral normalization with SVD can both control the spectral norm. Their empirical performance is actually worse than SN-GAN. For example, on the STL-10 dataset, SN-GAN achieves an inception score of 8.83, while singular value truncation only achieves 8.69 and orthogonal regularization achieves 8.77.

The reason behind is that SN-GAN implements the spectral normalization via one-step power iteration. This procedure consistently underestimates spectral norms of weight matrices. Consequently, in addition to controlling the spectral norms, the spectral normalization in SN-GAN affects the whole spectrum of the weight matrix (encourages slow singular value decay as in Figure 1 ), which we refer to as "flexibility". Encouraging slow decay is essentially encouraging the network to capture as many features as possible while allowing correlation between neurons. Built upon these empirical observations, we conjecture that controlling the whole spectrum better improves the performance of GANs, which is further corroborated by our numerical experiments (Section 4). 1 : An illustration of smooth singular value decays with different methods. The vertical axis denotes the value and the horizontal axis denotes the normalized rank. The inception scores on STL-10 are also reported.

• D-Optimal Regularizer: We propose the D-Optimal Regularizer as follows:

EQUATION

which is motivated by D-optimal design. D-optimal design (Wu & Hamada, 2011) is a popular principle in experimental design, where people aim to estimate parameters of statistical models with a minimum number of experiments. Specifically, D-optimal design maximizes the determinant of Fisher information matrix while allowing correlation between features in experiments. Existing literature has shown the superiority of D-optimal design to the orthogonal (uncorrelated) design on nonlinear model estimation (Yang et al., 2013; Li & Majumdar, 2009; Mentre et al., 1997) .

Analogously, our proposed D-Optimal Regularizer essentially maximizes the log Gram determinant of the weight matrix,

1 2 L-1 i=1 log(|(W i W i ) -1 |) ≈ 1 2 L-1 i=1 log(|(E i E i ) -1 |).

The approximation holds due to the SVD reparameterization

W i = U i E i V i , with U i , V i approximately orthogonal.

Moreover, note that the derivative of log(t) is 1 t , a monotone decreasing function. Then log(t) has a significant impact when t is small. Thus, D-optimal regularizer R(E) encourages a slow singular value decay. To mimic such a decay, we consider a reference distribution, y = 1 -min(|z|, 1), where z ∼ N (0, a 2 ). Figure 2 shows the decays of 10K order statistics sampled from y. We then denote the density function of y as p and the probability mass function of a uniform discrete distribution over {e

i j } ri-1 j=1 as Q i (e i j ) = 1 ri-1 ∀j ∈ [r i -1].

Note that the K-L divergence between a discrete distribution and a continuous distribution is ∞. To address this issue, we discretize p. Specifically, given {e i j } ri j=1 , we construct a discrete distribution over {e i j } ri-1 j=1 with a probability mass function P * i , defined as follows:

P * i (e i j ) = p(e i j )(e i j+1 -e i j ) ri-1 k=1 p(e i k )(e i k+1 -e i k ) ∀j ∈ [r i -1].

Ignoring the normalization term in the denominator, we then define the regularizer as follows:

R(E) = L-1 i=1 1 r i -1 ri-1 k=1 log (r i -1) -1 (e i k+1 -e i k )p(e i k )

.

Note that the divergence regularizer requires the singular values in the interval [0, 1] and D-optimal regularizer cannot control the Lipschitz constant of the discriminator D. Therefore, we incorporate the divergence regularizer with the spectrum constraint and combine the D-optimal regularizer with the spectral normalization to bound the Lipschitz constant. Our experimental results show that both combinations improve the training of GANs on CIFAR10 and STL-10 datasets.

3. THEORY:

We show how the spectrum control benefits the generalization of GANs. Before proceed, we define F-distance as follows.

Definition 1

(F-distance). Let F be a class of functions from R d to [0, 1] such that if f ∈ F, 1 -f ∈ F. Let φ be a concave function. Then given two distributions µ and ν supported on R d , the F-distance d F ,φ (µ, ν) with respect to φ is defined as d F ,φ (µ, ν) = sup f ∈F E x∼µ [φ(f (x))] + E x∼ν [φ(1 -f (x))] -2φ(1/2).

Note that F-distance unifies Jensen-Shannon distance, Wasserstein distance and neural distance as proposed in Arora et al. (2017) . For example, when taking φ(x) = x and F = {all 1-Lipschitz functions from R d to [0, 1]}, the F-distance is the Wasserstein distance. Recall that by (1), the training of GANs is essentially minimizing the F-distance with F being the collection of composite functions A(D(•)), where D(•) is the L-layer discriminator network defined by (2). To establish the generalization bound, we impose the following assumption.

Assumption 1. The activation operator

σ i is 1-Lipschitz with σ i (0) = 0 for any i ∈ [L -1]. A is 1-Lipschitz such that if A(D(•)) ∈ F, 1 -A(D(•)) ∈ F. φ is ρ φ -Lipschitz.

The spectral norms of weight matrices are bounded respectively, i.e.,

W i 2 ≤ B Wi for any i ∈ [L].

Note that commonly used functions A, such as the sigmoid function, satisfy the assumption. We denote by µ the underlying data distribution, and by µ n the empirical data distribution. We further denote ν n as the distribution given by the generator that minimizes the loss (1) up to accuracy , i.e.,

d F ,φ ( µ n , ν n ) ≤ inf ν∈D G d F ,φ ( µ n , ν) + ,

where D G is the class of distributions generated by generators. Then we give the generalization bound based on the PAC-learning framework as follows.

Theorem 2. Under Assumption 1, assume that the input data

x i ∈ R d1 is bounded, i.e., x i 2 ≤ B x for i ∈ [n].

Then given activation operators σ 1 , . . . , σ L-1 , A, and φ, with probability at least 1 -δ over the joint distribution of x 1 , . . . , x n , we have

d F ,φ (µ, ν n ) ≤ inf ν∈D G d F ,φ (µ, ν) + O     ρ φ β d 2 L log √ dnLβ √ n + ρ φ β log 1 δ n     + , where β = B x L i=1 B Wi and d = max(d 1 , . . . , d L ).

The detailed proof is provided in Appendix A.1. By constraining each B Wi = 1, the generalization bound is reduced to of the order O d 2 L/n , which is polynomial in d and L. On the contrary, without such spectrum constraints, the bound can be exponentially dependent on L. For example, if B Wi ≥ 1 + r with some constant r > 0 for any i = 1, . . . , L, we have β ≥ B x (1 + r) L , which implies that GANs cannot generalize with polynomial number of samples. Remark 3. Empirical Rademacher complexity (ERC) is adopted to derive our generalization bound, which is of the order O β d 2 L/n . Directly applying the ERC based generalization bound in Bartlett et al. (2017) yields a bound of the order O β d 2 L3 /n . Our bound is tighter, and is derived by exploiting the Lipschitz continuity of the discriminator with respect to its model parameters (weight matrices). Similar idea is used in Zhang et al. (2017) , however, we derive sharper Lipschitz constants 3 by the key step of decoupling the spectral norms of weight matrices and the number of parameters, i.e., separating β and d 2 L. Remark 4. Theorem 2 shows the advantage of spectrum control in generalization by constraining the class of discriminators. However, as suggested in Arora et al. (2017) , the class of discriminators needs to be large enough to detect lack of diversity. Despite of a lack of theoretical justifications, empirical results in Miyato et al. (2018) show that discriminators with spectral normalization are powerful in distinguishing ν n from µ, and suffer less from the mode collapse. We conjecture that the observed singular value decay (as illustrated in Figure 1 ) contributes to preventing mode collapse. We leave this for future theoretical investigation.

4. EXPERIMENT:

To demonstrate our proposed new methods, we conduct experiments on CIFAR-10 ( Krizhevsky & Hinton, 2009) , STL-10 (Coates et al., 2011) , and ImageNet (Russakovsky et al., 2015) . We illustrate the importance of spectrum control in GANs training by revealing a close relation between the performance and the singular value decays.

All implementations are done in Chainer as the official implementation of the SN-GAN (Miyato et al., 2018) . Note that SN-GAN is using power iteration. If not specified, all orther Spectral Normalization (SN) methods are under SVD framework. For quantitative assessment of generated examples, we use inception score (Salimans et al., 2016) and Fréchet inception distance (FID, Heusel et al. (2017) ). All reported results correspond to 10 runs of the GAN training with different random initializations. The discussion of this paper is based on fully connected layer. When dealing with convolutional layer, we only need to reshape the 4D weight tensor to a 2D matrix. Denote the weight tensor of a convolutional layer as W C ∈ R co,ci,k h ,kw , where c o , c i , (k h , k w ) denotes the output channel, the input channel and the kernel size. We reshape W C as W ∈ R co,ci×k h ×kw (Huang et al., 2017) , i.e., merging the last three dimensions while preserving the first dimension. See more implementation details in Appendix C.1.

4.1. DC-GAN:

We test our methods on DC-GANs with two datasets, CIFAR-10 and STL-10. Specifically, we adopt a 5-layer CNN as the generator and a 7-layer CNN as the discriminator. Recall that our proposed training framework tries to solve the equilibrium for equation ( 5). We set φ(•) = log(•) and A being the sigmoid function. Denote

f D (E, U, V) = f (θ, E, U, V) -λL orth -γR(E) for a fixed θ and f G (θ) = -E x∼D G θ [A(D(x))] for fixed U, V, and E, where L orth (U, V) = L i=1 ( U i U i -I i 2 F + V i V i -I i 2 F ).

We maximize f D (E, U, V) for n dis iterations (n dis ≥ 1) followed by minimizing f G (θ) for one iteration. Note that we use a log D trick (Goodfellow et al., 2014) to ease the computation of minimizing f G (θ). Detailed implementations are provided in Appendices B and C.2. We choose tuning parameters λ = 10 and γ = 1 in all the experiments except for the Divergence regularizer, where we pick λ = 10 and γ = 0.054 . γ is chosen according to the output range of different regularizers. We set a smaller gamma for Divergence Regularizer, since its output is much larger than other regularizers. We take 100K iterations in all the experiments on CIFAR-10 and 200K iterations on STL-10 as suggested in Miyato et al. (2018) .

To solve (5), we adopt the setting in Radford et al. (2015) , which has been shown to be robust for different GANs by Miyato et al. (2018) . Specifically, we use the Adam optimizer (Kingma & Ba, 2014) with the following hyperparameters: (1) n dis = 1; (2) α = 0.0002, the initial learning rate; (3) β 1 = 0.5, β 2 = 0.999, the first and second order momentum parameters of Adam respectively.

Before we present our results, we show the effectiveness of our proposed reparameterization, which aims to approximate the singular values of weight matrices while avoiding direct SVDs. As can be seen, in Table 1 , U i and V i have nearly orthonormal columns respectively, i.e.,

U i U i -I i 2 F , V i V i -I i 2 F ≤ 10 -4 .

Although the reparameterization introduces more model parameters, it maintains comparable computational efficiency. See more details in Appendix D.2.

Table 1: The sub-orthogonality of U i 's and V i 's in the discriminator with the divergence regularizer on CIFAR-10 after 100K iterations. For other settings, we also observe that all U i 's and V i 's have nearly orthonormal columns. We can see that our method outperforms SN-GAN.

Figure 4 shows that the singular value decays of weight matrices with two different methods: SN-GAN and Doptimal regularizer with spectral normalization. As can be seen, our method achieves a slower decay in singular values than that of SN-GAN. See more results of other methods in Appendix D.3. Such a slower decay improves the performance of GANs. Specifically, Table 2 presents the inception scores and FIDs of our proposed methods as well as other methods on CIFAR-10 and STL-10. As can be seen, under CNN architecture, our methods achieve significant improvements on STL-10. Compared with STL-10, CIFAR-10 is easy to learn, and thus GAN training can only limitedly benefits from encouraging the slow singular value decay. As a result, on CIFAR-10, our methods slightly improve the result of SN-GAN. Moreover, as shown in Figure 4 , at the early stage (5k iteration), our method achieves slow decay while SN-GAN still decays fast. Thus, it converge faster than SN-GAN as shown in Figure 5 .

5K:

< l a t e x i t s h a 1 _ b a s e 6 4 = " f Q N j s X v v 7 7 Z F T K N s 4 6 p t P d o 5 j 4

A = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C b a C p 7 J b K H o s e h G 8 V L A f 0 C 4 l m 2 b b 0 C S 7 J F m h L P 0 L X j w o 4 t U / 5 M 1 / Y 7 b d g 7 Y + G H i 8 N 8 P M v C D m T B v X / X Y K G 5 t b 2 z v F 3 d L e / s H h U f n 4 p K O j R B H a J h G P V C / A m n I m a d s w w 2 k v V h S L g N N u M L 3 N / O 4 T V Z p F 8 t H M Y u o L P J Y s Z A S b T K o 2 q v f D c s W t u Q u g d e L l p A I 5 W s P y 1 2 A U k U R Q a Q j H W v c 9 N z Z + i p V h h N N 5 a Z B o G m M y x W P a t 1 R i Q b W f L m 6 d o w u r j F A Y K V v S o I X 6 e y L F Q u u Z C G y n w G a i V 7 1 M / M / r J y a 8 9 l M m 4 8 R Q S Z a L w o Q j E 6 H s c T R i i h L D Z 5 Z g o p i 9 F Z E J V p g Y G 0 / J h u C t v r x O O v W a 5 9 a 8 h 3 q l e Z P H U Y Q z O I d L 8 O A K m n A H L W g D g Q k 8 w y u 8 O c J 5 c d 6 d j 2 V r w c l n T u E P n M 8 f z p S N a A = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " f Q N j s X v v 7 7 Z F T K N s 4 6 p t P d o 5 j 4 A = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C b a C p 7 J b K H o s e h G 8 V L A f 0 C 4 l m 2 b b 0 C S 7 J F m h L P 0 L X j w o 4 t U / 5 M 1 / Y 7 b d g 7 Y + G H i 8 N 8 P M v C D m T B v X / X Y K G 5 t b 2 z v F 3 d L e / s H h U f n 4 p K O j R B H a J h G P V C / A m n I m a d s w w 2 k v V h S L g N N u M L 3 N / O 4 T V Z p F 8 t H M Y u o L P J Y s Z A S b T K o 2 q v f D c s W t u Q u g d e L l p A I 5 W s P y 1 2 A U k U R Q a Q j H W v c 9 N z Z + i p V h h N N 5 a Z B o G m M y x W P a t 1 R i Q b W f L m 6 d o w u r j F A Y K V v S o I X 6 e y L F Q u u Z C G y n w G a i V 7 1 M / M / r J y a 8 9 l M m 4 8 R Q S Z a L w o Q j E 6 H s c T R i i h L D Z 5 Z g o p i 9 F Z E J V p g Y G 0 / J h u C t v r x O O v W a 5 9 a 8 h 3 q l e Z P H U Y Q z O I d L 8 O A K m n A H L W g D g Q k 8 w y u 8 O c J 5 c d 6 d j 2 V r w c l n T u E P n M 8 f z p S N a A = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " f Q N j s X v v 7 7 Z F T K N s 4 6 p t P d o 5 j 4 A = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C b a C p 7 J b K H o s e h G 8 V L A f 0 C 4 l m 2 b b 0 C S 7 J F m h L P 0 L X j w o 4 t U / 5 M 1 / Y 7 b d g 7 Y + G H i 8 N 8 P M v C D m T B v X / X Y K G 5 t b 2 z v F 3 d L e / s H h U f n 4 p K O j R B H a J h G P V C / A m n I m a d s w w 2 k v V h S L g N N u M L 3 N / O 4 T V Z p F 8 t H M Y u o L P J Y s Z A S b T K o 2 q v f D c s W t u Q u g d e L l p A I 5 W s P y 1 2 A U k U R Q a Q j H W v c 9 N z Z + i p V h h N N 5 a Z B o G m M y x W P a t 1 R i Q b W f L m 6 d o w u r j F A Y K V v S o I X 6 e y L F Q u u Z C G y n w G a i V 7 1 M / M / r J y a 8 9 l M m 4 8 R Q S Z a L w o Q j E 6 H s c T R i i h L D Z 5 Z g o p i 9 F Z E J V p g Y G 0 / J h u C t v r x O O v W a 5 9 a 8 h 3 q l e Z P H U Y Q z O I d L 8 O A K m n A H L W g D g Q k 8 w y u 8 O c J 5 c d 6 d j 2 V r w c l n T u E P n M 8 f z p S N a A = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " f Q N j s X v v 7 7 Z F T K N s 4 6 p t P d o 5 j 4 A = " > A A A B 6 3 i c b V B N S w M x E J 2 t X 7 V + V T 1 6 C b a C p 7 J b K H o s e h G 8 V L A f 0 C 4 l m 2 b b 0 C S 7 J F m h L P 0 L X j w o 4 t U / 5 M 1 / Y 7 b d g 7 Y + G H i 8 N 8 P M v C D m T B v X / X Y K G 5 t b 2 z v F 3 d L e / s H h U f n 4 p K O j R B H a J h G P V C / A m n I m a d s w w 2 k v V h S L g N N u M L 3 N / O 4 T V Z p F 8 t H M Y u o L P J Y s Z A S b T K o 2 q v f D c s W t u Q u g d e L l p A I 5 W s P y 1 2 A U k U R Q a Q j H W v c 9 N z Z + i p V h h N N 5 a Z B o G m M y x W P a t 1 R i Q b W f L m 6 d o w u r j F A Y K V v S o I X 6 e y L F Q u u Z C G y n w G a i V 7 1 M / M / r J y a 8 9 l M m 4 8 R Q S Z a L w o Q j E 6 H s c T R i i h L D Z 5 Z g o p i 9 F Z E J V p g Y G 0 / J h u C t v r x O O v W a 5 9 a 8 h 3 q l e Z P H U Y Q z O I d L 8 O A K m n A H L W g D g Q k 8 w y u 8 O c J 5 c d 6 d j 2 V r w c l n T u E P n M 8 f z p S N a A = = < / l a t e x i t > 50K < l a t e x i t s h a 1 _ b a s e 6 4 = " S C d r P H w v e B n A m u a O h B k d F R T w V T Q = " > A A A B 7 H i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L L a C p 5 I U R I 9 F L 4 K X C r Y W 2 l A 2 2 0 m 7 d L M J u x u h h P 4 G L x 4 U 8 e o P 8 u a / c d v m o K 0 P B h 7 v z T A z L 0 g E 1 8 Z 1 v 5 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a u s 4 V Q x b L B a x 6 g R U o + A S W 4 Y b g Z 1 E I Y 0 C g Y / B + G b m P z 6 h 0 j y W D 2 a S o B / R o e Q h Z 9 R Y q V W 9 c K t 3 / X L F r b l z k F X i 5 a Q C O Z r 9 8 l d v E L M 0 Q m m Y o F p 3 P T c x f k a V 4 U z g t N R L N S a U j e k Q u 5 Z K G q H 2 s / m x U 3 J m l Q E J Y 2 V L G j J X f 0 9 k N N J 6 E g W 2 M 6 J m p J e 9 m f i f 1 0 1 N e O V n X C a p Q c k W i 8 J U E B O T 2 e d k w B U y I y a W U K a 4 v Z W w E V W U G Z t P y Y b g L b + 8 S t r 1 m u f W v P t 6 p X G d x 1 G E E z i F c / D g E h p w C 0 1 o A Q M O z / A K b 4 5 0 X p x 3 5 2 P R W n D y m W P 4 A + f z B z 0 G j a I = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " S C d r P H w v e B n A m u a O h B k d F R T w V T Q = " > A A A B 7 H i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L L a C p 5 I U R I 9 F L 4 K X C r Y W 2 l A 2 2 0 m 7 d L M J u x u h h P 4 G L x 4 U 8 e o P 8 u a / c d v m o K 0 P B h 7 v z T A z L 0 g E 1 8 Z 1 v 5 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a u s 4 V Q x b L B a x 6 g R U o + A S W 4 Y b g Z 1 E I Y 0 C g Y / B + G b m P z 6 h 0 j y W D 2 a S o B / R o e Q h Z 9 R Y q V W 9 c K t 3 / X L F r b l z k F X i 5 a Q C O Z r 9 8 l d v E L M 0 Q m m Y o F p 3 P T c x f k a V 4 U z g t N R L N S a U j e k Q u 5 Z K G q H 2 s / m x U 3 J m l Q E J Y 2 V L G j J X f 0 9 k N N J 6 E g W 2 M 6 J m p J e 9 m f i f 1 0 1 N e O V n X C a p Q c k W i 8 J U E B O T 2 e d k w B U y I y a W U K a 4 v Z W w E V W U G Z t P y Y b g L b + 8 S t r 1 m u f W v P t 6 p X G d x 1 G E E z i F c / D g E h p w C 0 1 o A Q M O z / A K b 4 5 0 X p x 3 5 2 P R W n D y m W P 4 A + f z B z 0 G j a I = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " S C d r P H w v e B n A m u a O h B k d F R T w V T Q = " > A A A B 7 H i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L L a C p 5 I U R I 9 F L 4 K X C r Y W 2 l A 2 2 0 m 7 d L M J u x u h h P 4 G L x 4 U 8 e o P 8 u a / c d v m o K 0 P B h 7 v z T A z L 0 g E 1 8 Z 1 v 5 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a u s 4 V Q x b L B a x 6 g R U o + A S W 4 Y b g Z 1 E I Y 0 C g Y / B + G b m P z 6 h 0 j y W D 2 a S o B / R o e Q h Z 9 R Y q V W 9 c K t 3 / X L F r b l z k F X i 5 a Q C O Z r 9 8 l d v E L M 0 Q m m Y o F p 3 P T c x f k a V 4 U z g t N R L N S a U j e k Q u 5 Z K G q H 2 s / m x U 3 J m l Q E J Y 2 V L G j J X f 0 9 k N N J 6 E g W 2 M 6 J m p J e 9 m f i f 1 0 1 N e O V n X C a p Q c k W i 8 J U E B O T 2 e d k w B U y I y a W U K a 4 v Z W w E V W U G Z t P y Y b g L b + 8 S t r 1 m u f W v P t 6 p X G d x 1 G E E z i F c / D g E h p w C 0 1 o A Q M O z / A K b 4 5 0 X p x 3 5 2 P R W n D y m W P 4 A + f z B z 0 G j a I = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " S C d r P H w v e B n A m u a O h B k d F R T w V T Q = " > A A A B 7 H i c b V B N S 8 N A E J 3 U r 1 q / q h 6 9 L L a C p 5 I U R I 9 F L 4 K X C r Y W 2 l A 2 2 0 m 7 d L M J u x u h h P 4 G L x 4 U 8 e o P 8 u a / c d v m o K 0 P B h 7 v z T A z L 0 g E 1 8 Z 1 v 5 3 C 2 v r G 5 l Z x u 7 S z u 7 d / U D 4 8 a u s 4 V Q x b L B a x 6 g R U o + A S W 4 Y b g Z 1 E I Y 0 C g Y / B + G b m P z 6 h 0 j y W D 2 a S o B / R o e Q h Z 9 R Y q V W 9 c K t 3 / X L F r b l z k F X i 5 a Q C O Z r 9 8 l d v E L M 0 Q m m Y o F p 3 P T c x f k a V 4 U z g t N R L N S a U j e k Q u 5 Z K G q H 2 s / m x U 3 J m l Q E J Y 2 V L G j J X f 0 9 k N N J 6 E g W 2 M 6 J m p J e 9 m f i f 1 0 1 N e O V n X C a p Q c k W i 8 J U E B O T 2 e d k w B U y I y a W U K a 4 v Z W w E V W U G Z t P y Y b g L b + 8 S t r 1 m u f W v P t 6 p X G d x 1 G E E z i F c / D g E h p w C 0 1 o A Q M O z / A K b 4 5 0 X p x 3 5 2 P R W n D y m W P 4 A + f z B z 0 G j a I = < / l a t e x i t >

100K:

< l a t e x i t s h a 1 _ b a s e 6 4 = " g P 

3 C 5 W M 2 J 0 A U j Q p g m 1 t k E T w M T 0 0 = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S

e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W h U f 4 8 p d v 1 T G V T w H W i V + T s q Q o 9 E v f f U G i q Y x k 5 Y K Y k z X x 4 k N M q I t p 4 J N i 7 3 U s I T Q M R m y r q O S x M w E 2 f z a K T p 3 y g B F S r u S F s 3 V 3 x M Z i Y 2 Z x K H r j I k d m W V v J v 7 n d V M b X Q U Z l 0 l q m a S L R V E q k F V o 9 j o a c M 2 o F R N H C N X c 3 Y r o i G h C r Q u o 6 E L w l 1 9 e J a 1 a 1 c d V / 7 5 W r l / n c R T g F M 7 g A n y 4 h D r c Q g O a Q O E R n u E V 3 j z l v X j v

3 s e i d c 3 L Z 0 7 g D 7 z P H 6 V 7 j d g = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " g P

3 C 5 W M 2 J 0 A U j Q p g m 1 t k E T w M T 0 0 = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W h U f 4 8 p d v 1 T G V T w H W i V + T s q Q o 9 E v f f U G i q Y x k 5 Y K Y k z X x 4 k N M q I t p 4 J N i 7 3 U s I T Q M R m y r q O S x M w E 2 f z a K T p 3 y g B F S r u S F s 3 V 3 x M Z i Y 2 Z x K H r j I k d m W V v J v 7 n d V M b X Q U Z l 0 l q m a S L R V E q k F V o 9 j o a c M 2 o F R N H C N X c 3 Y r o i G h C r Q u o 6 E L w l 1 9 e J a 1 a 1 c d V / 7 5 W r l / n c R T g F M 7 g A n y 4 h D r c Q g O a Q O E R n u E V 3 j z l v X j v

3 s e i d c 3 L Z 0 7 g D 7 z P H 6 V 7 j d g = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " g P

3 C 5 W M 2 J 0 A U j Q p g m 1 t k E T w M T 0 0 = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W h U f 4 8 p d v 1 T G V T w H W i V + T s q Q o 9 E v f f U G i q Y x k 5 Y K Y k z X x 4 k N M q I t p 4 J N i 7 3 U s I T Q M R m y r q O S x M w E 2 f z a K T p 3 y g B F S r u S F s 3 V 3 x M Z i Y 2 Z x K H r j I k d m W V v J v 7 n d V M b X Q U Z l 0 l q m a S L R V E q k F V o 9 j o a c M 2 o F R N H C N X c 3 Y r o i G h C r Q u o 6 E L w l 1 9 e J a 1 a 1 c d V / 7 5 W r l / n c R T g F M 7 g A n y 4 h D r c Q g O a Q O E R n u E V 3 j z l v X j v

3 s e i d c 3 L Z 0 7 g D 7 z P H 6 V 7 j d g = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " g P

3 C 5 W M 2 J 0 A U j Q p g m 1 t k E T w M T 0 0 = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W h U f 4 8 p d v 1 T G V T w H W i V + T s q Q o 9 E v f f U G i q Y x k 5 Y K Y k z X x 4 k N M q I t p 4 J N i 7 3 U s I T Q M R m y r q O S x M w E 2 f z a K T p 3 y g B F S r u S F s 3 V 3 x M Z i Y 2 Z x K H r j I k d m W V v J v 7 n d V M b X Q U Z l 0 l q m a S L R V E q k F V o 9 j o a c M 2 o F R N H C N X c 3 Y r o i G h C r Q u o 6 E L w l 1 9 e J a 1 a 1 c d V / 7 5 W r l / n c R T g F M 7 g A n y 4 h D r c Q g O a Q O E R n u E V 3 j z l v X j v

3 s e i d c 3 L Z 0 7 g D 7 z P H 6 V 7 j d g = < / l a t e x i t >

200K:

< l a t e x i t s h a 1 _ b a s e 6 4 = " F h 6 0

D O M z e Q O r d r a b V U b E n N 0 D f b w = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W p U a x p W 7 f q m M q 3 g O t E r 8 n J Q h R 6 N f + u o N F E 1 j J i 0 V x J i u j x M b Z E R b T g W b F n u p Y Q m h Y z J k X U c l i Z k J s v m 1 U 3 T u l A G K l H Y l L Z q r v y c y E h s z i U P X G R M 7 M s v e T P z P 6 6 Y 2 u g o y L p P U M k k X i 6 J U I K v Q 7 H U 0 4 J p R K y a O E K q 5 u x X R E d G E W h d Q 0 Y X g L 7 + 8 S l q 1 q o + r / n 2 t X L / O 4 y j A K Z z B B f h w C X W 4 h Q Y 0 g c I j P M M r v H n K e

/ H e v Y 9 F 6 5 q X z 5 z A H 3 i f P 6 c D j d k = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " F h 6 0

D O M z e Q O r d r a b V U b E n N 0 D f b w = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W p U a x p W 7 f q m M q 3 g O t E r 8 n J Q h R 6 N f + u o N F E 1 j J i 0 V x J i u j x M b Z E R b T g W b F n u p Y Q m h Y z J k X U c l i Z k J s v m 1 U 3 T u l A G K l H Y l L Z q r v y c y E h s z i U P X G R M 7 M s v e T P z P 6 6 Y 2 u g o y L p P U M k k X i 6 J U I K v Q 7 H U 0 4 J p R K y a O E K q 5 u x X R E d G E W h d Q 0 Y X g L 7 + 8 S l q 1 q o + r / n 2 t X L / O 4 y j A K Z z B B f h w C X W 4 h Q Y 0 g c I j P M M r v H n K e

/ H e v Y 9 F 6 5 q X z 5 z A H 3 i f P 6 c D j d k = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " F h 6 0

D O M z e Q O r d r a b V U b E n N 0 D f b w = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W p U a x p W 7 f q m M q 3 g O t E r 8 n J Q h R 6 N f + u o N F E 1 j J i 0 V x J i u j x M b Z E R b T g W b F n u p Y Q m h Y z J k X U c l i Z k J s v m 1 U 3 T u l A G K l H Y l L Z q r v y c y E h s z i U P X G R M 7 M s v e T P z P 6 6 Y 2 u g o y L p P U M k k X i 6 J U I K v Q 7 H U 0 4 J p R K y a O E K q 5 u x X R E d G E W h d Q 0 Y X g L 7 + 8 S l q 1 q o + r / n 2 t X L / O 4 y j A K Z z B B f h w C X W 4 h Q Y 0 g c I j P M M r v H n K e / H e v Y 9 F 6 5 q X z 5 z A H 3 i f P 6 c D j d k = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " F h 6 0 D O M z e Q O r d r a b V U b E n N 0 D f b w = " > A A A B 7 X i c b V B N S w M x E J 3 1 s 9 a v q k c v w V b w V L K 9 6 L H o R f B S w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6 e i 4 Z V S q K W t S J Z T u h M Q w w S V r W m 4 F 6 y S a k T g U r B 2 O b 2 Z + + 4 l p w 5 V 8 s J O E B T E Z S h 5 x S q y T W p U a x p W 7 f q m M q 3 g O t E r 8 n J Q h R 6 N f + u o N F E 1 j J i 0 V x J i u j x M b Z E R b T g W b F n u p Y Q m h Y z J k X U c l i Z k J s v m 1 U 3 T u l A G K l H Y l L Z q r v y c y E h s z i U P X G R M 7 M s v e T P z P 6 6 Y 2 u g o y L p P U M k k X i 6 J U I K v Q 7 H U 0 4 J p R K y a O E K q 5 u x X R E d G E W h d Q 0 Y X g L 7 + 8 S l q 1 q o + r / n 2 t X L / O 4 y j A K Z z B B f h w C X W 4 h Q Y 0 g c I j P M M r v H n K e

/ H e v Y 9 F 6 5 q X z 5 z A H 3 i f P 6 c D j d k = < / l a t e x i t > 

4.2. RESNET-GAN:

We also test our proposed method on ResNet, a more advanced structure, on both discriminator and generator (Appendix C.2). For these experiments, we adopt the hinge loss for adversarial training on discriminators:

f D (E, U, V) = E x∼D G θ [min (0, -1 -D(x))] + 1 n n i=1 min (0, -1 + D(x i )) .

We also adopt the commonly used hyperparameter settings for the Adam optimizer on ResNet: n dis = 5, α = 0.0002, β 1 = 0, and β 2 = 0.9 (Gulrajani et al., 2017) . Due to our computational resource limit, we only test the method of spectral normalization (our version) with D-optimal regularizer, which achieves the best performance on CNN experiments. We also test on the official subsampled 64 × 64 ImageNet data using the conditional GAN with a projected discriminator Miyato & Koyama (2018) .

The results of our experiments on CIFAR-10 and STL-10 are listed in Table 2 , and results on ImageNet are shown in Figure 3 . We see that our method is much better than the other methods on STL-10 and ImageNet. As for CIFAR-10, our method is better than orthogonal regularizer but slightly worse than SN-GAN. We believe the reason behind is that CIFAR-10 is relatively easy. As can be seen, for CIFAR-10, the inception scores of all methods are around 8, while the inception score of real data is around 11. In contrast, for STL-10, the inception score of real data is around 26, while inception scores of all methods are less than 10. As a result, when the dataset is complicated and network needs high capacity, our method performs better than SN-GAN. 8.06 ± .06 9.65 ± .06 20.5 ± .18 39.9 ± .33

5. CONCLUSION:

In this paper, we propose a new SVD-type reparameterization for weight matrices of the discriminator in GANs, allowing us to efficiently manipulate the spectra of weight matrices. We than establish a new generalization bound of GAN to justify the importance of spectrum control on weight matrices. Moreover, we propose new regularizers to encourage the slow singular value decay. Our experiments on CIFAR-10, STL-10, and ImageNet datasets support our proposed methods, theory, and discoveries.

A PROOF IN SECTION 3:

A.1 PROOF OF THEOREM 2

Proof. We bound the output of D(•) as follows,

EQUATION

)

Note that given x 1 , . . . , x i , . . . , x n and x 1 , . . . , x i , . . . , x n , we have

sup AD(•)∈F E x∼µ [φ(A(D(x)))] + E x∼µn [φ(A(D(x)))] -sup AD(•)∈F E x∼µ [φ(A(D(x)))] + E x∼µ n [φ(A(D(x)))] ≤ φ(A(D(x i ))) -φ(A(D(x i ))) n ≤ρ φ D(x i ) -D(x i ) n ≤ 2 n ρ φ B x L i=1 B Wi .

Then McDiarmid's inequality gives us, with probability at least 1 -δ/2, sup

EQUATION

By the argument of symmetrization, we have

EQUATION

where i 's are i.i.d. Rademacher random variables, i.e., P( i = 1) = P( i = -1) = 1/2. McDiarmid's inequality again gives us, with probability at least 1 -δ/2, we have

EQUATION

)

Note that E 1 n sup AD(•)∈F n i=1 i φ(A(D(x))) is essentially the empirical Rademacher complexity of φ(A(D(•))). Since φ and A are both Lipschitz, by Talagrand's lemma, we have

E 1 n sup AD(•)∈F n i=1 i φ(A(D(x i ))) ≤ ρ φ E 1 n sup D n i=1 i D(x i ) .

We then use the standard Dudley's entropy integral to bound E 1 n sup D n i=1 i D(x i ) . We exploit the parametric form of discriminators to find a tight covering number. We have to investigate the Lipschitz continuity of D(•) with respect to the weight matrices W 1 , . . . , W L . We based our argument on telescoping. Given two sets of weight matrices W 1 , . . . , W L and W 1 , . . . , W L and fix the activation operators and A, we have

D(x) -D (x) ∞ ≤ W L σ L-1 (• • • σ 1 (W 1 x) • • • ) -W L σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 = W L σ L-1 (• • • σ 1 (W 1 x) • • • ) -W L σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 + W L σ L-1 (• • • σ 1 (W 1 x) • • • )W L σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 ≤ W L -W L 2 σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 + W L 2 σ L-1 (• • • σ 1 (W 1 x) • • • ) -σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 ≤ W L -W L 2 B x L-1 i=1 B Wi + W L 2 σ L-1 (• • • σ 1 (W 1 x) • • • ) -σ L-1 (• • • σ 1 (W 1 x) • • • ) 2 ≤ • • • • • • ≤ L i=1 B x L j=1 B Wj B Wi W i -W i 2 .

For notational simplicity, we denote

L Wi = B L j=1 B W i B W i

. When the activation operators and A are given, function D has a one to one correspondence to weight matrices W 1 , . . . , W L . Thus, to construct a covering of F, it is enough to construct matrix coverings of W 1 , . . . , W L , and their Cartesian product gives us a covering of F. The standard argument of volume ratio gives us an upper bound of the covering number of matrices with bounded spectral norms. Suppose M = {M ∈ R d×h : M 2 ≤ λ}, the covering number N (M, , • 2 ) at scale with respect to spectral norm is bounded by

N (M, , • 2 ) ≤ 1 + min( √ d, √ h)λ dh .

Therefore, the covering number N (F, , • ∞ ) is bounded by

N (F, , • ∞ ) ≤ L i=1 N (W i , LL W -i , • 2 ) ≤ L i=1 1 + LL Wi min( √ d i , √ d i+1 )B Wi didi+1

.

Take d = max{d 1 , . . . , d L }. We get

N (F, , • ∞ ) ≤ 1 + √ dLB x L i=1 B Wi d 2 L

.

Then Dudley's entropy integral gives us

E 1 n sup D n i=1 i D(x i ) ≤ 4α √ n + 12 n Bx L i=1 B W i √ n α log N (F, , • ∞ )d ≤ 4α √ n + 12 n B x L i=1 B Wi √ n d 2 L log 1 + √ dLB x L i=1 B Wi α .

It is enough to pick α = 1 √ n , which yields

E 1 n sup D n i=1 i D(x i ) ≤ 4 n + 12B x L i=1 B Wi d 2 L log 2 √ dnLB x L i=1 B Wi √ n .

Thus, we immediately have,

EQUATION

Now, combining equations ( 10), ( 11), ( 12), (13), and ( 14) together, we get

d F ,φ (µ, ν n ) ≤ inf ν∈D G d F ,φ (µ, ν n ) + 16ρ φ n + 48ρ φ β d 2 L log 2 √ dnLβ √ n + 12ρ φ β log 1 δ n ,

where β = B x L i=1 B Wi . On the other hand, naively applying the argument from Bartlett et al. ( 2017) yields the generalization bound

d F ,φ (µ, ν n ) ≤ inf ν∈D G d F ,φ (µ, ν n ) + O     ρ φ β dL 3 log √ dnLβ √ n + ρ φ β log 1 δ n     .

Combining the two generalization bound together, we get

EQUATION

B ALGORITHM

Recall that we are maximizing the following objective function f D (E, U, V) for discriminator D in Section 4.1:

f D (E, U, V) = f (θ, E, U, V) -λL orth (U, V) -γR(E).

The detailed training algorithm is described in Algorithm 1:

Algorithm 1 Adversarial training with Spectrum Control of Discriminator, D Initialization 1: for l = 1, .., L do 2:

Determine the rank of l-layer: r i = min{d i , d i+1 }.

3::

Initialize U i ∈ R di×ri and V i ∈ R di+1×ri with orthonormal columns.

4::

Initialize E i = I ri . 5: end for Forward pass Input: mini-batch input H i ∈ R m×di from previous layer Output: mini-batch output S i+1 ∈ R m×di+1 Parameters: U i , V i , and E i 1: Perform Singluar value update on E i 2: Calculate weight matrix: Note that we omit the bias term for simplicity. 

W i = U i E i V i ∈ R di×di+1 . 3: Calculate output: S i+1 = H i W i . Backward pass Input: activation derivative ∇ S i+1 f Output: ∇ Hi f, ∇ Ui f D , ∇ Vi f D , ∇ Ei f D 1: Calculate: ∇ Hi f = ∇ Si+1 f W i as standard linear module. 2: Calculate: ∇ Wi f = H i ∇ Si+1 f as standard linear module. 3: Calculate: ∇ Ui f, ∇ Vi f, ∇ Ei f based on ∇ Wi f . 4: Calculate: ∇ Ui f D = ∇ Ui f -λ∇ Ui L orth , ∇ Vi f D = ∇ Vi f -λ∇ Vi L orth . 5: Calculate: ∇ Ei f D = ∇ Ei f -γ∇ Ei R(E). 6: Update U i , V i ,

i = { e i j } ri j=1 of recovered weight matrix W i = U i E i V i .

In Table 6 , we compare the maximum, the minimum, the mean and the variance of E i and E i .

Table 6 : The accuracy of singular value estimation on CIFAR-10 experiment with divergence regularizer after 100K iterations. For other layers and other setting, we can also observe highly accurate singular value approximation.

Max:

Min Mean Var U U -I 2 F V V -I 2 F E i E i E i E i E i E i E i E i 0-

th Layer 1.0000 1.0000 0.8344 0.8344 0.9448 0.9448 0.0037 0.0037 2.3e-5 7.9e-5 1-th Layer 1.0000 0.9999 0.8128 0.8128 0.9441 0.9441 0.0036 0.0036 1.2e-5 1.0e-5 2-th Layer 1.0000 0.9999 0.7972 0.7971 0.9438 0.9438 0.0036 0.0036 1.5e-5 1.7e-5 3-th Layer 1.0000 1.0000 0.7969 0.7969 0.9438 0.9438 0.0036 0.0036 1.6e-5 2.5e-5 4-th Layer 1.0000 1.0000 0.7816 0.7815 0.9432 0.9432 0.0036 0.0036 2.7e-5 4.1e-5 5-th Layer 1.0000 1.0002 0.7817 0.7816 0.9434 0.9434 0.0037 0.0037 2.5e-5 7.1e-5 6-th Layer 1.0000 1.0001 0.7765 0.7765 0.9591 0.9591 0.0033 0.0033 2.1e-5 3.9e-5

D.2 TIMING COMPARISON:

We compare the computational time on CIFAR-10 for different methods in Figure 6 . We can see Spectral Constraint with Divergence Regularizer is slightly slower than other methods. Note that the training time will be impacted by the hardware condition, i.e. how many tasks are simultaneously running on the same server. In order to leverage such fluctuation, we test timing for every 1000 iterations and then take their average. 7 . On CIFAR-10, we also observe a very similar pattern, and thus we only present the STL-10 results.

We summarize our observation as follows:

(1) Spectral normalization in SN-GAN yields a slow decay pattern because the power iteration consistently underestimate the spectral norm. So it rescales lower-ranking eigenvalues to br 1. 

:

Without a sparse matrix implementation, these methods are highly unscalable and inefficient (not supported by the existing deep learning libraries such as TensorFlow and PyTorch in GPU).

WL essentially is a vector. To be consistent, we still use ULELV L to reparametrize WL. Actually, it is not necessary. We can directly control the norm of WL in practice.

The Lipschitz constant inZhang et al. (2017) can be of the order d L .

In fact, the performance is not sensitive to these hyperparameters, since we only observe negligible difference by fine tuning these parameters. Specifically, when λ ∈ [1, 100] and γ ∈ [0.2,

5] (γ ∈ [0.01, 0.1] for Divergence regularizer), the algorithm yields similar results.

Figures and Tables:

and D G denotes the class of distributions generated by generators. Compared to the results inZhang et al. (2017), our result improves the generalization bound up to an exponential factor of the depth of the discriminator. More details will be discussed in Section 3.The rest of the paper is organized as follows: Section 2 introduces our proposed training framework in detail; Section 3 presents the generalization bound for GANs under spectrum control; Section 4 presents numerical experiments on CIFAR-10, STL-10, and ImageNet datasets. Notations: Given an integer d > 0, we denote [d] = {1, 2, ..., d}. Given a vector v ∈ R d , we denote v 2 2 = d i=1 |v i | 2 as its Euclidean norm. Given a matrix M ∈ R m×n , we denote the spectral norm by M 2 as the largest singular value of M . We adopt the standard O(•) notation, which is defined as f (x) = O (g(x)) as x → ∞, if and only if there exists M > 0 and x 0 , such that |f (x)| ≤ M g(x) for x ≥ x 0 . We use O(•) to denote O(•) with hidden logarithmic factors.

to control the Lipschitz constant of the discriminator D. Specifically, we define the Lipschitz regularizer as:

Figure 2: The plot of normalized ranks versus values of 10K order statistics sampled from reference distributions. The vertical axis denotes the value; the horizontal axis denotes the normalized rank.

Figure 3: Inception scores on ImageNet.We can see that our method outperforms SN-GAN.

w X 5 A u 5 R s m m 1 j s 8 m S Z I W y 9 D 9 4 8 a C I V / + P N / + N a b s H b X 0 w 8 H h v h p l 5 Y S K 4 s R h / e 2 v r G 5 t b 2 4 W d 4 u 7 e / s F h 6

Figure 4: Illustrations of singular value decay in 7 layers at 5K-th, 50K-th, 100K-th, and 200K-th iteration. The above figures are for the SN-GANs; the below are for D-optimal regularizer with SN.

Figure 6: Time cost per 1000 iterations.

(2) Under SVD reparametrization, the spectral norm is accurate. And thus the eigenvalues decay faster than the one with power iteration. (3) Because of D-Optimal regularization, the eigenvalues are pushed towards 1 and thus they decay slower. (4) The divergence regularizer pushes the eigenvalues towards a predefined slow decay curve and thus yields such a pattern. (5) The spectral constraint only clip the singluar values which are out of the range [0, 1]. It will not rescale the other singular values as the spectral normalization. The singular values tend to grow through the training process. Thus it yields a spectrum with almost no decay. (6) Similar to the spectral constraint, Lipschitz regularizer only penalize the largest singular value of each layer. Thus it yields a spectrum with almost no decay. But it does not enforces the largest singular value of each layer to be 1.

10, the growth of inception score and FID over iterations is shown in Figure7. While the image generation results are shown in Figure9.For STL-10, the growth of inception score and FID over iterations is shown in Figure8. While the image generation results are shown in Figure10. For ImageNet, the results are shown in Figure11

Figure 7: The growth of inception score and FID over iterations on CIFAR-10 dataset.

Figure 8: The inception scores and FID's of different methods on STL-10. The top part is for the inception score, and the bottom is for the FID. The inner graph zooms in the results after 55K iterations. The x-axis denotes the number of iterations.

Figure 9: Image generation on CIFAR-10 dataset.

Figure 10: Image generation on STL-10 dataset.

where U i and V i are required to have orthonormal columns, E i = diag(e i 1 , ..., e i ri ) denotes a diagonal matrix with r i = min(d

Table content: <table/>

The inception scores and FIDs on CIFAR-10 and STL-10. For consistency, we reimplement baselines under our Chainer environment. .05 22.3 ± .26 44.9 ± .35 SN-GAN (Power Iter.) 8.21 ± .05 9.15 ± .06 19.5 ± .22 43.0 ± .44 SN + D-Optimal Reg.

Table content: <table><tr><td>Method</td><td colspan="2">Inception Score CIFAR-10 STL-10</td><td>FID CIFAR-10</td><td>STL-10</td></tr><tr><td>Real Data</td><td colspan="2">11.24 ± .12 26.08 ± .26</td><td>7.8</td><td>7.9</td></tr><tr><td>CNN Baseline</td><td/><td/><td/></tr><tr><td>WGAN-GP</td><td>6.72 ± .11</td><td colspan="3">8.42 ± .09 39.0 ± .29 54.1 ± .35</td></tr><tr><td>Orthogonal Reg.</td><td>7.31 ± .09</td><td colspan="3">8.77 ± .07 25.7 ± .33 44.5 ± .30</td></tr><tr><td colspan="2">SN-GAN (Power Iter.) 7.39 ± .05</td><td colspan="3">8.83 ± .07 24.7 ± .25 45.5 ± .34</td></tr><tr><td colspan="2">Ours CNN (Under SVD)</td><td/><td/></tr><tr><td>Spectral Norm.</td><td>7.35 ± .05</td><td colspan="3">8.69 ± .08 25.2 ± .22 44.8 ± .39</td></tr><tr><td>Spectral Constraint</td><td>7.43 ± .08</td><td colspan="3">8.97 ± .05 24.8 ± .30 44.0 ± .42</td></tr><tr><td>Lipschitz Reg.</td><td>7.43 ± .08</td><td colspan="3">8.99 ± .06 24.1 ± .28 45.3 ± .38</td></tr><tr><td>SC + Divergence Reg.</td><td>7.44 ± .05</td><td colspan="3">9.21 ± .09 24.3 ± .21 41.9 ± .37</td></tr><tr><td>SN + D-Optimal Reg.</td><td>7.48 ± .06</td><td colspan="3">9.25 ± .08 23.0 ± .27 40.5 ± .41</td></tr><tr><td>ResNet Structure</td><td/><td/><td/></tr><tr><td>Orthogonal Reg.</td><td>7.90 ± .05</td><td>8.83 ±</td><td/></tr></table>

and E i with the Adam Optimizer. If use spectrum constraint: E i = g(E i ), where g(•) is the clipping operator defined in (8). 2: If use spectrum normalization: E i = E i /e i 1 . 3: If use Lipschitz regularizer: do nothing, since we do not need to layer-wisely control the Lipschitz constant in this case.

Table content: <table><tr><td>Singluar value update</td></tr><tr><td>Input: E i Output: E i with e i 1 ∈ [0, 1], i.e. the largest singular value is bounded by 1</td></tr><tr><td>1:</td></tr></table>

The ResNet architectures for ImageNet dataset. Recall that we adopts conditional GAN framework with projection discriminator. The ResBlock is implemented with the conditional batch normalization for the generator. Embed(y), h is the inner product of label embedding, Embed(y), and the hidden state, h, after the global sum pooling.(Miyato & Koyama, 2018). We use the same Residual Block asGulrajani et al. (2017) describes. .1 ACCURACY OF APPROXIMATING SINGULAR VALUE DECOMPOSITION In this section we evaluate how accurate can E i = {e i j } ri j=1 approximate the true singular value E

Table content: <table><tr><td/><td>(a) Generator</td><td/><td>(b) Discriminator</td></tr><tr><td>Input:</td><td>z ∈ R 128 ∼ N (0, I )</td><td>Input:</td><td>Image x ∈ R 64×64×3</td></tr><tr><td>Linear:</td><td>128 → 4 × 4× 1024</td><td/><td>Label y ∈ {1, 2, 3, ..., 1000}</td></tr><tr><td colspan="2">ResBlock: [1024, Up-sampling]</td><td colspan="2">ResBlock: [64, Down-Sampling]</td></tr><tr><td colspan="2">ResBlock: [512, Up-sampling]</td><td colspan="2">ResBlock: [128, Down-Sampling]</td></tr><tr><td colspan="2">ResBlock: [128, Up-sampling]</td><td colspan="2">ResBlock: [256, Down-Sampling]</td></tr><tr><td colspan="2">ResBlock: [64, Up-sampling]</td><td colspan="2">ResBlock: [512, Down-Sampling]</td></tr><tr><td/><td>BN,ReLU</td><td colspan="2">ResBlock: [1024, Down-Sampling]</td></tr><tr><td>Conv:</td><td>[3 × 3, 3, stride = 1], Tanh</td><td/><td>ReLU, Global sum pooling</td></tr><tr><td/><td/><td colspan="2">Projection+ : Embed(y), h + [1024 → 1] Linear</td></tr></table>

Singular value decays.

Table content: <table><tr><td/><td/><td>5K</td><td/><td/><td/><td/><td/><td>50K</td><td/><td/><td/><td/><td/><td colspan="2">100K</td><td/><td/><td/><td/><td colspan="2">200K</td><td/><td/></tr><tr><td>0.8 1.0</td><td>0-th layer 1-th layer 2-th layer 3-th layer 4-th layer 5-th layer 6-th layer</td><td/><td/><td/><td>0.8 1.0</td><td/><td>0-th layer 1-th layer 2-th layer 3-th layer 4-th layer 5-th layer 6-th layer</td><td/><td/><td/><td>0.8 1.0</td><td/><td>0-th layer 4-th layer 6-th layer 5-th layer 3-th layer 2-th layer 1-th layer</td><td/><td/><td/><td>0.8 1.0</td><td/><td/><td/><td/><td/><td/></tr><tr><td>0.6</td><td/><td/><td/><td/><td>0.6</td><td/><td/><td/><td/><td/><td>0.6</td><td/><td/><td/><td/><td/><td>0.6</td><td/><td/><td/><td/><td/><td/></tr><tr><td>0.2 0.4</td><td/><td/><td/><td/><td>0.2 0.4</td><td/><td/><td/><td/><td/><td>0.2 0.4</td><td/><td/><td/><td/><td/><td>0.2 0.4</td><td/><td/><td/><td/><td/><td>0-th layer 1-th layer 2-th layer 3-th layer 4-th layer 5-th layer 6-th layer</td></tr><tr><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>1.0</td><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>1.0</td><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>1.0</td><td>0.0</td><td>0.2</td><td>0.4</td><td>0.6</td><td>0.8</td><td>1.0</td></tr><tr><td/><td/><td/><td/><td/><td colspan="13">Spectral Normalization (Power Iteration, SN-GAN)</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 The paper is a natural extension of [1] which shows the importance of spectral normalization to encourage diversity of the discriminator weights in a GAN. A simple and effective parametrization of the weights similar to SVD is used: W = USV^T is used along with an orthonormal penalty on U and V and spectral penalty to control the decay of the spectrum. Unlike other parametrizations of orthogonal matrices which are exact but computationally expensive, the proposed one tends to be very accurate in practice and much faster. A generalization bound is provided that shows the benefit of controlling the spectral norm. Experimental results show that the method is accurate in constraining the orthonormality of U and V and in controlling the spectrum. The experiments also show a marginal improvement of the proposed method over SN-GAN [1]. However, the following it is unclear why one would want to control the whole spectrum when theorem 2 only involves the spectral norm. In [1], it is argued that this encourages diversity in the weights which seems intuitive. However, it seems enough to use Spectral Normalization to achieve such purpose empirically according to that same paper. It would be perhaps good to have an example where SN fails to control the spectrum in a way that significantly impacts the performance of the algorithm while the proposed method doesn*t. Overall the paper is clearly written and the proposed algorithm effectively controls the spectrum as shown experimentally, however, given that the idea is rather simple, it is important to show its significance with examples that clearly emphasize the importance of controlling the whole spectrum versus the spectral norm only. Revision: Figure 1 is convincing and hints to why SN-GAN acheives slow decay while in principle it only tries to control the spectral norm. I think this paper is a good contribution as it provides a simple and efficient algorithm to precisely control the spectrum. Moreover, a recent work ([2], theorem 1 ) provides theoretical evidence for the importance of controling the whole spectrum which makes this contribution even more relevant. [1] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral Normalization for Generative Adversarial Networks. Feb. 2018. [2] M. Arbel, D. J. Sutherland, M. Bin ́kowski, and A. Gretton. On gradient regularizers for MMD GANs. NIPS 2018