Title: UNDERSTANDING GANS VIA GENERALIZATION ANALYSIS FOR DISCONNECTED SUPPORT

Abstract: This paper provides theoretical analysis of generative adversarial networks (GANs) to explain its advantages over other standard methods of learning probability measures. GANs learn a probability through observations, using the objective function with a generator and a discriminator. While many empirical results indicate that GANs can generate realistic samples, the reason for such successful performance remains unelucidated. This paper focuses the situation where the target probability measure satisfies the disconnected support property, which means a separate support of a probability, and relates it with the advantage of GANs. It is theoretically shown that, unlike other popular models, GANs do not suffer from the decrease of generalization performance caused by the disconnected support property. We rigorously quantify the generalization performance of GANs of a given architecture, and compare it with the performance of the other models. Based on the theory, we also provide a guideline for selecting deep network architecture for GANs. We demonstrate some numerical examples which support our results.

1. INTRODUCTION:

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) attract much attention as technology for learning a distribution and generating data. The purpose of GANs is to learn a probability measure from a given dataset and generate samples from the learned measure. It is often seen that samples generated by GANs can extract effectively features in the real world; it is difficult, for instance, to distinguish real images and generated images. By practical successes, a countless number of variations of GANs have been developed (Dziugaite et al., 2015; Arjovsky et al., 2017; Li et al., 2015; Nowozin et al., 2016; Gulrajani et al., 2017; Zhao et al., 2016) , and applied to a wide range of tasks (Reed et al., 2016; Zhu et al., 2017; Gauthier, 2014) .

Understanding the remarkable performance of GANs is, however, still a challenging problem. There are active discussions on the role of generators in its learning scheme (Goodfellow, 2016; Arjovsky & Bottou, 2017; Arora et al., 2018; Creswell et al., 2018) , and adversarial structures with discriminators are also a target of interest (Lotter et al., 2015; Zhang et al., 2018) . A gaming structure between generators and discriminators is also regarded as a useful factor in the mechanism of GANs (Mescheder et al., 2017; Arora et al., 2017; Heusel et al., 2017) . Generalization performance of GANs has been investigated in several studies (Liang, 2017; Liu et al., 2017; Tolstikhin et al., 2017) . In spite of these studies, it is not yet clear why GANs can generate well-extracted data better than other standard methods.

This paper introduces the disconnected support property, and explains an advantage of GANs in connection with this notion. The disconnected support property refers to a probability measures of which the support is divided into several disjoint sets, allowing non-differentiable density on the boundary. The property makes a probability measure be complex, hence it can be an obstacle for standard methods to learn the measure effectively. This property, however, is popularly seen in many real data, especially data with cluster structure, as demonstrated in Section 3.

We investigate in detail the approximation and estimation ability of GANs and some other methods, and provide novel generalization analysis of probability measures with disconnected support. Firstly, we show that the other methods suffer worse generalization performance due to complex structures of disconnected supports (Proposition 1 and Lemma 2). Secondly, our generalization analysis reveals that GANs can learn the probability measure without loss of efficiency under the the disconnected supports (Theorem 1, Corollary 1 and ??). Additionally, we derive a guideline for choosing the number of layers or connections of the generator and discriminator from the generalization analysis. Numerical results support our theoretical findings.

We remark that the disconnected support property is different from the low-dimensional supports studied in Arjovsky & Bottou (2017) , where the support of a measure generated by neural networks is disjoint to the measure of observations. In contrast, this paper considers the case in which the support of the observation measure is divided into disjoint subsets. The problem of disconnected supports is complement to the low-dimensionality, hence these two problems can be investigated separately. In this paper, to simplify the discussion, we assume that the support of a probability measure is not low-dimensional.

The contributions of this paper are summarized as follows:

1. We show that GANs perform better than other standard methods of estimating probability measures when the measure satisfies the disconnected support property. 2. We provide a new generalization error bound under a general formulation of GANs by analyzing an approximation error. The result is thus applicable to a wide range of variations of GANs. 3. Based on the generalization bound, we provide a theoretical guideline for selecting architectures of generators and discriminators.

All the proofs are given in Supplementary materials.

2. PRELIMINARIES:



2.1. NOTATION:

We use notations I :" r0, 1s. A j-th element of a vector b is denoted by b j , and }b} q :" p ř j b q j q 1{q is the q-norm (q P r0, 8s). vecp¨q is a vectorization operator for matrices. For z P N, rzs :" t1, 2, . . . , zu is a set of positive integers no more than z. For α P R, tαu denotes the largest integer which is not larger than α. For a domain Ω in a Euclidean space and a function f : Ω Ñ R, }f } L p :" p ş Ω |f ptq| p dtq 1{p denotes the L p norm for p P r0, 8s. For f : Ω Ñ R D with a multidimensional output, f d denotes a d-th coordinate of f pxq " pf 1 pxq, ..., f D pxqq J . Let H β pΩq be the Hölder space for β ą 0 such as a set of β-smooth functions f : Ω Ñ R, namely, f is C tβu -class and its tβu-th derivative is β ´tβu-Hölder continuous. b denotes a tensor product, and ˝a composition of functions, namely, for functions f and f 1 , f ˝f 1 " f pf 1 p¨qq. A Borel σ-algebra of Ω is denoted as σpΩq. For a measurable mapping f : Ω Ñ Ω 1 and B 1 Ă Ω 1 , a pre-image of f is defined as

f ´1pB 1 q :" tt P Ω | B 1 Q f ptqu. Let 1 Ω : x Þ Ñ

t0, 1u be an indicator function such that 1 Ω pxq " 1 if x P Ω, and 1 Ω pxq " 0 otherwise.

2.2. GENERAL FRAMEWORK OF GANS:

We provide a general formulation of a learning problem with generative adversarial networks (GANs) following Liu et al. (2017) . In this paper, we consider a probability measure P ˚on a measurable space pI D , Σq with a dimensionality D P N and Σ :" σpI D q. Here, we set D ě 3. Suppose we have a set of n observations D :" tX 1 , ..., X n u which is independently and identically generated from P ˚. Let P n :" 1 n ř iPrns δ Xi be an empirical measure where δ x is the Dirac measure at x. The goal of generative networks is to estimate P ˚from D. To this end, we construct a probability measure by generators. Let P Z be the uniform distribution on pI D , Σq. For a measurable mapping g : I D Ñ I D , we define P g as the pushforward measure: i.e., P g pBq " P Z pg ´1pBqq for B P Σ. We call g as a generator and use G for a set of generators.

GANs employ a learning scheme with a metric with discriminators (Goodfellow et al., 2014) . Let F " tf : I D Ñ Ru be a a set of discriminators. This paper considers a general metric for GANs (Liu et al., 2017) ,

EQUATION

between probability measures P and P 1 .

For the learning process, we generate m noise samples r Z 1 , ..., r Z m from P Z and obtain generated samples as r X j :" gp r Z j q with g P G for j P rms. Let P g,m :" (2)

The metric (1) covers a wide variety of GANs by selecting F. Among others, the original GAN (Goodfellow et al., 2014) is realized if F contains a logarithm of density ratio; Wasserstein-GAN (Arjovsky et al., 2017) , MMD-GAN (Dziugaite et al., 2015; Li et al., 2017) and Energy-Based GAN (Zhao et al., 2016) are given if F is the set of 1-Lipschitz functions, a reproducing kernel Hilbert space, and the bounded continuous functions, respectively. The f -GAN (Nowozin et al., 2016 ) also belongs to this class.

We assume that F is large enough to contain functions which can work as a discriminator, namely, we assume that the following holds:

d F pP, P 1 q " 0 ô P " P 1 .

(3)

A sufficient condition for (3) is investigated in Zhang et al. (2018) .

2.3. DEEP NEURAL NETWORKS FOR GENERATORS AND DISCRIMINATORS:

In the schemes of GANs, F and G are realized by deep neural networks (DNNs). For further discussion, we formulate the function class given by DNNs.

Let L P N be a number of layers in DNNs, and D 1 P N be a dimensionality of variables in an -th layer for P rL `1s. Here, we set D 1 L`1 " D for generators and D 1 L`1 " 1 for discriminators. We introduce A P R D 1 `1ˆD 1 and b P R D 1 as matrix and vector parametersof the -th layer. An architecture Θ of DNNs is defined as a set of L pairs of pA , b q as Θ :" ppA 1 , b 1 q, ..., pA L , b L qq. We define notations for Θ as follow: |Θ| :" L as the number of layers, }Θ} 0 :" ř PrLs } vecpA q} 0 `}b } 0 as the number of non-zero elements in Θ, and }Θ} 8 :" maxtmax PrLs } vecpA q} 8 , max PrLs }b } 8 u be the scale of parameters in Θ. We employ the ReLU activation function η : R D 1 Ñ R D 1 for each D 1 P N such as ηpxq " pmaxtx d , 0uq dPrD 1 s .

We define functions of DNNs with an architecture Θ as ξrΘs : R D 1 Ñ R D 2 by ξrΘspxq " x pL`1q , x p1q :" x, x p `1q :" ηpA x p q `b q, for P rLs.

The function class of DNNs is thus given by ΞpS, B, Lq :"

! ξrΘs : I D Ñ R | }Θ} 0 ď S, }Θ} 8 ď B, |Θ| ď L ) ,

where S P N, B ą 0, and L P N are hyper-parameters. Here, S bounds the number of non-zero parameters of DNNs, namely, it controls the sparseness of DNNs. B is a bound for scales of parameters.

3. DISCONNECTED SUPPORT PROPERTY:



3.1. INTRODUCTION AND EXAMPLE:

It is often observed that data in real world data the support of its probability measure may not be connected but a union of disjoint subsets. This is typical if the data has cluster structures, as seen in many data sets for classification tasks. Moreover, the density function of the probability measure may not be smooth at a boundary of the support. Figures 1 (MNIST, (LeCun et al., 1998) ) and 2 (Shelter Animal, Center) illustrate such examples in the real world. They are projected onto a 2-dimensional Euclidean space by t-SNE (Maaten & Hinton, 2008 ) so that they preserve the original distance structure among points. We can see that both of the data are concentrated on several disjoint subsets and there are a clear gap or empty regions between some of the subsets. This observation suggests that the disconnected property of probability measures should be addressed in discussing estimation of probability measures, while standard analysis does not consider this phenomenon. In fact, this paper will show that the disconnected supports property has an important role in showing an advantage of GANs over standard estimation methods.

Figure 1 : Plot of the MNIST data.

Figure 2 : Plot of the animal data.

3.2. MATHEMATICAL FORMULATION OF DISCONNECTED SUPPORTS:

Here we make a rigorous definition of disconnected supports. The property of smoothness (i.e. differentiability) is involved, which is a key factor to analyze generalization performance in the fields of the statistics (Stone, 1982; Tsybakov, 2009) ; Stone (1982) shows, for instance, that smoothness and a dimension of data are sufficient to characterize an optimal convergence of generalization errors.

We first prepare a family of subsets as a component in the disconnected supports:

S α,J :" S Ă I D | A boundary of S is J combination of α-smooth hyper surfaces ( .

The supplementary material will provide a more rigorous definition. Now, we define the disconnected support property of probability measures as well as a probability measure with global support, i.e., with no the disconnected support property. Let SupppP q be the support of P ., i.e, SupppP q :" tx P I D | P pV x q ą 0 for all open neighborhood V x of xu.

Hereafter, M ě 2 is the number of disjoint components of a support. Definition 1. (Disconnected Supports / Global Support) Let M ě 2. A probability measure P on pI D , Σq has M disconnected supports, if there exist nonempty disjoint sets S 1 , ..., S M P S α,J such that SupppP q "

ď mPrM s S m .

A probability measure P on pI D , Σq has a global support, if SupppP q " I D .

Figure 3 illustrates the disconnected support property.

We next formulate a notion of smoothness for P with disconnected supports. Let β ě 1 be a parameter for a degree of smoothness of P . Definition 2. (Local Smoothness) A probability measure P with M disconnected support is locally β-smooth, if there exist M pairs p r S m , S m q P S 2β,J ˆS2β,J and β `1-smooth bijective measurable maps γ m : r S m Ñ S m as P pBq " P Z pγ ´1 m pBqq, @B P σpS m q, for m P rM s.

This definition of local smoothness says that a probability measure P with disconnected supports can be generated by sufficiently smooth mappings γ m . It is used for considering a smooth density function of P restricted on S m . Lemma 1. (Locally Smooth Density Functions) If a probability measure P with M disconnected support is locally β-smooth, then there exists a function p m : S m Ñ R `such that P pBq "

ż B p m pxqdλ, B P σpS m q,

where λ is the Lebesgue measure, and p m is β-smooth for all m P rM s.

We call p m as a local density function.

Note that, since P with disconnected supports is not absolutely continuous to the Lebesgue measure on I D z Ť mPrM s S m , an ordinary density function cannot be defined. Instead, a localized version of density functions for each S m is introduced, which is guaranteed by the local smoothness.

Figure 3 : Illustration of a probability measure P with a disconnected support. SupppP q is a union of two disjoint sets S 1 and S 2 .

Figure 4 : Illustration of a generator g. To represent discontinuous S 1 and S 2 , g should be discontinuous.

3.3. DIFFICULTY WITH DISCONNECTED SUPPORTS:

As shown in this subsection, the generalization performance of many standard estimation methods is worsened with disconnected supports. We consider popular nonparametric methods, for which the generalization performance is well-studied in the asymptotics of the observation size n. The considered methods are the kernel density estimator (KDE) (Nadaraya, 1964) , the nonparametric Bayes (NB) by the Dirichlet mixtures of normal distributions (Ferguson, 1973) , the series density estimator (SDE) (Efromovich et al., 2008; Efromovich, 2010) and the density estimator with Gaussian process (GP) (Leonard, 1978) . Bounds of the generalization errors for these methods are already known (Tsybakov, 2009; Ghosal et al., 2007; van der Vaart & van Zanten, 2008) , and they are optimal in the minimax sense. Here, their performance is evaluated with respect to a root of an expected squared loss with respect to the L 2 -norm, namely, d 2 pP, P 1 q :" Er}p ´p1 } 2 L 2 s 1{2 where p and p 1 are densities for P and P 1 .

We show the deterioration of their performance by the disconnected support property. Let p P be an estimator for P ˚by KDE, NB, SDE, or GP. If P ˚has a global support and a β-smooth density, the existing studies (Tsybakov, 2009; Ghosal et al., 2007; van der Vaart & van Zanten, 2008) show that

d 2 pP ˚, p P q " O ´n´β{p2β`Dq ¯.

These bounds are sufficiently tight, since these bounds corresponds to an optimal rate (Stone, 1982) , and the performance of the methods can be improved as the density for P ˚is smoother (larger β).

On the other hand, we consider a case in which P ˚has the disconnected support property.

Proposition 1. (Deterioration of other standard methods):

There exists P ˚of the disconnected support property and locally β-smooth such that d 2 pP ˚, p P q " O ´n´1{p2`Dq ¯.

When P ˚has disconnected supports, the errors are worse than those for the global support, independent of β. This worse generalization error can be understood by the non-smoothness or discontinuity of the density functions on the boundaries of the disconnected sets (see Figure 3 ).

We next discuss other generative models for estimating a probability measure. To the best of our knowledge, other probabilistic generative methods (Koller et al., 2009) and the variational autoencoder (Kingma & Welling, 2013), their statistical generalization property is not well investigated.

Here we provide a property of generators for probability measures with disconnected supports. Lemma 2. (Discontinuous Generators for Disconnected Supports) If P ˚has disconnected supports and P ˚" P g ˚with a generator g ˚, then g ˚is not uniformly continuous.

Lemma 2 states that a generator must be discontinuous to construct a probability measure with disconnected support sets. Intuitively, to make P g ˚pB q " 0 for B P I D with λpBq ą 0, the slope of g ˚at z P I D should be close to infinite for z P g ˚,´1 pBq, hence g ˚cannot be uniformly continuous (see Figure 4 ). Because of the discontinuity, generative models with smooth functions, such as an adversarial generative model with kernel generators (Sinn & Rawat, 2018) , cannot work well with disconnected supports.

4. GENERALIZATION BY GANS:

We provide generalization analysis for GANs for probability measures with and without disconnected supports. For the purpose, we employ a metric d F with properly selected discriminators F and evaluate the generalization error d F pP ˚, P p g q with respect to an observation size n and a sampling size m. We assume F is realized by DNNs as

F " ΞpS f , B f , L f q X r F with parameters S f , B f , L f , where r

F is a specified functional class; for an example, r F is 1-Lipschitz functions for Wasserstein-GAN. Here, we consider settings that all f P F are L 1 -Lipschitz continuous and }f } L 8 ď B F with constants L 1 , B F ą 0.Generators are also constructed by DNNs as G " ΞpS g , B g , L g q with parameters S g , B g , L g .

A standard line of discussing generalization, we should consider statistical errors and approximation errors. We define a measure of the complexity of F

Υ n pFq :" inf ηą0 4η `12n ´1{2 ż c η log N ppL 1 `1q ´1 , F, } ¨}n q 1{2 d ,

where c ą 0 is a constant depends on F and N p , r F, } ¨}q is a covering number of r F with respect to an empirical norm } ¨}. We note that Υ n pFq bounds an expectation of the Rademacher complexity as

Υ n pFq ě E » -sup f PF 1 n ˇˇˇˇˇÿ iPrns τ i f pX i q ˇˇˇˇˇfi fl ,

where τ i is the i.i.d. Rademacher random variables; Prpτ i " 1q " Prpτ i " 1q " 1{2, and the expectation is about X i and τ i . Using the statistics and learning theory van der Vaart & Wellner (1996) ; Bartlett et al. (2005) , we can apply a bound for Υ n pFq as

Υ n pFq ď C F n ´1{κ ,

with some constants C F ą 0 and κ ě 2.

Regarding approximation errors, we need to consider approximation of a discontinuous function; since Lemma 2 shows that a discontinuous generator is necessary to represent disconnected supports. To approximate such generators, DNNs in GANs has an advantage. Lemma 3. (Approximation for Discontinuous g by DNNs) Suppose P ˚has M disconnected supports and locally β-smooth, and also P ˚" P g ˚holds with some g ˚. Then, for any S g , there exist G, 9 g P G, and a constant c g " c g pB g , L g q ą 0 such that

EQUATION

Furthermore, if P ˚" P g ˚has a global support and it is β-smooth, (4) holds with M " 1.

Lemma 3 shows that G for GANs can approximate g ˚for disconnected supports with the rate (´β{D) by S g , and the rate is same in the case of global support. This implies an advantage of GANs in comparison with the other standard methods (Proposition 1).

Based on Lemma 3, we obtain the main theorem for generalization analysis. Theorem 1. (Generalization of GANs) Suppose that P ˚has M disconnected supports and locally β-smooth, and we have n observations and m samplings. Then, with F, an existing G, an estimator P p g by (2), and finite constants c 1 " c 1 pL f , B f , L g , B g q, c 2 , c 3 " c 3 pL f , B f q ą 0, the following inequality holds with high probability,

d F pP ˚, P p g q ď Υ m p r Fq `c1 a S g `aS f ? m looooooooooooooomooooooooooooooon ":I `c2 M DS ´β{D g loooooomoooooon ":II `Υn p r Fq `c3 c S f n looooooooomooooooooon ":III .

(5)

Furthermore, if P ˚has a global support and it is β-smooth, (5) holds with M " 1. `2d F pP n , P 0 q loooooomoooooon ":iii .

To obtain i ď I and iii ď III, we apply an empirical process technique (van der Vaart & Wellner, 1996) , especially convergence of integral probability measures (Sriperumbudur et al., 2012) and the entropy control technique (Lemma 4 and 5 in the supplementary material). To show ii ď II, we employ recent results on approximation ability of DNNs (Yarotsky, 2017; Petersen & Voigtlaender, 2017; Imaizumi & Fukumizu, 2018) and obtain an approximation bound for d F pP g , P ˚q (Lemma 3).

Combining these results, we obtain the statement of Theorem 1.

Theorem 1 provides two trade-off relations with respect to S g and S f . The generator class G controls uncertainty by sampling and the approximation error, while S f controls uncertainty of observations and discrimination. For balancing the trade-offs, we select the number of parameters (connections of DNNs) with some constants c g , c f ą 0 as S g " c g m D{p2β`Dq , and S f " c f n pκ´2q{κ ,

for optimizing the bound (5). We then obtain the following corollary. Corollary 1. (Convergence Rate of GANs) Make the same assumptions as Theorem 1, and set S f and S g as in (6). Then, with high probability converging to 1, we obtain

EQUATION

A selection of r F determines the first term in ( 7), since κ depends on r F. For an example, when F is a set of 1-Lipschitz functions, the first term is O `n´1{p2`2Dq ˘ (Sriperumbudur et al., 2012) . Remark 1. (Heterogeneous Smoothness) Corollary 1 can be extended when P ˚has different smoothness for each m P rM s, i.e., P ˚is locally β m -smooth on a set S m . In this case, we can easily extend our analysis in Theorem 1 and Corollary 1, and obtain the following convergence rate.

d F pP ˚, P p g q " O ´n´1{κ ¯`O ´m´1{κ `m´r β{p2 r β`Dq ¯,

where r β :" min mPrM s β m .

5. DISCUSSION:

We emphasize the theoretical results show that GANs do not suffer from the effect of disconnected supports. A larger β improves performance of GANs even with disconnected supports, as shown in Theorem 1 and Corollary 1. This phenomenon is different from the result of the other methods discussed in Proposition 1. Hence, we can state that GANs have advantages over the other methods which are deteriorated by the disconnected property (Section 3.3). In other words, when data are generated from a probability measure with disconnected supports and sufficiently smooth in each of the sets, only GANs can estimate the measure effectively and the other methdos cannot. This advantage of GANs comes from the approximation power for discontinuous generators shown in Lemma 3.

The results ( 5) and ( 7) provide interpretation about performance of GANs. About convergence with n, the complexity of r F and S f control a trade-off between convergence and a power of discrimination. While smaller S f reduce the errors in terms of d F , too small S f can lose the power of discrimination to satisfy (1). Hence, setting S f as in ( 6) can keep the discrimination power and does not worsen the overall rate of convergence Opn ´1{κ q. About convergence with m, S g controls the trade-off between the bias and variance of the estimator. An optimal way to select S g is provided in (6) which depends on β and D, and it is more important when κ is small (e.g. κ " 2 as MMD-GAN). Based on the interpretation and the selection rule (6), our study can provide a guideline for a design of the architecture of DNNs.

5.1. RELATED WORKS:

Compared with studies for understanding GANs (Dziugaite et al., 2015; Liang, 2017; Liu et al., 2017; Zhang et al., 2018; Biau et al., 2018; Arora et al., 2017) , we show that GANs can avoid influences of disconnected supports, unlike the other methods, hence it is a source of the advantage of GANs. This paper is the first work to focus on the disconnected support property, while several discussions (Goodfellow, 2016; Liang, 2017; Creswell et al., 2018) focus on models and metrics of the learning scheme of GANs.

It is important to compare our result with other studies for generalization analysis. Although some existing studies (Dziugaite et al., 2015; Liang, 2017; Liu et al., 2017; Zhang et al., 2018; Biau et al., 2018; Arora et al., 2017) provide generalization analysis, they do not analyze an approximation effect, namely, they evaluate d F pP ˚, P p g q ´inf gPG pP ˚, P g q. Since we analyze the term inf gPG pP ˚, P g q, we can provide a more general bound and discuss the effect of disconnected support.

As we mentioned in the introduction, this paper is not along with studies for low-dimensional supports (Arjovsky & Bottou, 2017) . We also note that an optimization aspect and gaming aspect of GANs are out of concerns of this paper. We focus on the statistical aspects of GANs such as sample complexity.

6. NUMERICAL EXPERIMENTS:

We compare the numerical performance of GANs and the other methods with toy data with. We generate synthetic data from the following two settings: (A) Gaussian distribution restricted on a compact set (global support), and (B) a probability measure with two disconnected supports (density function is the black solid line in Figure 6 ). We generate n " 500, 1000, ..., 5000 observations and estimate the true probability measures with Wasserstein GAN, MMD-GAN, KDE (the Gaussian kernel and the Epanechnikov kernel), SDE (Fourier basis), and NB (Dirichlet process prior). Hyperparameters for these methods are selected by cross-validation. For GANs, we set m " n. We use d F to evaluate errors by GANs, and a root of the expected squared errors with the L 2 -norm for the other methods. The plots are the mean of 30 replications.

Figure 5 shows generalization errors by the methods. With the disconnected support case (B), we plot the estimated density in Figure 6 . The black line shows the true density, the dashed line is by estimated densities of the other methods, and bars are histograms by GANs. The results by Wasserstein-GAN and MMD-GAN are almost same, so we omit the result by Wasserstein-GAN.

In Figure 5 , we see that in the case of global support (A), the error of GANs and the other methods are comparable. In contrast, in the case of disconnected supports (B), the other standard methods show worse generalization and only GANs keep the high performance. From Figure 6 , we can see that GANs can reveal the disconnected supports, while some of the other methods fail to fit. KDE with the Gaussian kernel represents the disconnected support by employing a small bandwidth. However, the small bandwidth yields a too sharp density, tending to worsen the generalization performance. 

7. CONCLUSION:

We investigate a generalization performance of GANs with a situation such that a support of real probability measures is divided into several sets. We find that GANs do not suffer from the division of supports, while some of the other nonparametric methods loss their efficiency by the division. Since real data are often distributed on such divided supports, the finding in this paper is related to the question of why GANs perform well with real datasets.

Supplementary Materials for "Understanding GANs via disconnected Support Detection":

We introduce a new notation P f :" E X"P rf pXqs with a probability measure P and a function f . For a set Ω with equipped distance d, let N p , Ω, dq be a covering number which is a minimum number of -balls to cover Ω.

A SOME ADDITIONAL INFORMATION:

A Rigorous Definition of S α,J

We consider a set represented by a combination of multiple horizon functions, which has been used in Petersen & Voigtlaender (2017) . Given α-smooth function h P H α pI D´1 q with α ě 1, a horizon function Ψ h : I D Ñ t0, 1u is defined for some d P rDs as

Ψ h " Ψpx 1 , . . . , x d´1 , x d ˘hpx 1 , . . . , x d´1 , x d`1 , . . . , x D q, x d`1 , ..., x D q,

where Ψ is the Heaviside function; Ψpxq " 1 txPI D |x d ě0u . We define a set by the intersection of J horizon functions Ψ h1 , ..., Ψ h J ; namely the family of sets is defined by

S α,J :" S Ă r0, 1s D | 1 S " Ψ h1 b ¨¨¨b Ψ h J ( .

Intuitively, h is regarded as an α-smooth curved surface in I D , and Ψ h describes a set which is one side of the surface. Also, S P S α,J is a set which is a intersection of J sets by Ψ h1 , ..., Ψ h J .

A Support of Probability Measures:

Let N

x denote an open neighborhood of x P I D , and For a probability measure P , a support of P is defined as SupppP q :" " x P I D | P pN x q ą 0, @N x P Σ * .

B PROOFS B.1 PROOF OF LEMMA 1:

Fix m P rM s and a corresponding r S m , S m and g m . For any B P σpS m q, the definition of γ m yields

P X pBq " P Z pγ ´1 m pBqq " ż γ ´1 m pBq p Z pzqdz,

where p Z is a density function of a uniform measure P Z . By changing variables x " γ m pzq, we have

ż γ ´1 m pBq p Z pzqdz " ż B p Z pγ ´1 m pxqqJ γm pxqdx,

where J γm pxq " | det ∇g ´1 m pxq|. Using p Z pzq " 1 for all z P I D , we obtain the following form of P X pBq using a function p m : r S m Ñ S m as

EQUATION

and p m is β-smooth since γ m is β `1-smooth and bijective.

B.2 PROOF OF LEMMA 2:

Firstly, we show the first points. Suppose that g is a continuous mapping. By the generalized intermediate value theorem (Theorem 24.3 in Munkres (2000) ), we know that gpI D q is connected since I D is a connected set. Thus, a support of P g is connected. However, P g has a disconnected support, thus there is a contradiction.

B.3 PROOF OF LEMMA 3:

In this proof, a À b denotes that b is larger than a up to a finite constant. ab denotes that a À b and a Á b hold.

By the definition of tg m u mPrM s for the measure with local smoothness, we consider an explicit form of g m . By Stein (2016), we can extend g m : r S m Ñ S m to r g m : I D Ñ S m since boundaries of r S m are Lipschitz continuous. Then, we provide the following formulation r g m pxq " pγ m,1 pxq, ..., γ m,D pxqq J , where γ m,d P H β pI D q. Then, we obtain the form of g ˚as

g ˚" ÿ mPrM s r g m b 1 r Sm .

Also, by the definition of S 2β,J which contains r S m , we obtain the form

1 r Sm " â jPrJs ψ hm,j ,

with existing ψ hm,j . Then, we have

g ˚" ÿ mPrM s r g m â jPrJs ψ hm,j .

Preliminarily, we apply sub-neural networks from Yarotsky (2017) and Petersen & Voigtlaender (2017) . Let ζrΘ `s be a network for summation such that ζrΘ `spx 1 , ..., x D 1 q " ř dPrD 1 s x d , and ζrΘ ˆs be a network for approximate multiplication such as |ζrΘ ˆspx 1 , ..., x D 1 q ´śdPrD 1 s x d | ă with some ą 0 for all x, x 1 P I (Proposition 3 in Yarotsky (2017) and Lemma 1 in Imaizumi & Fukumizu (2018) ).

We consider approximation ř mPrM s γ m,d Â jPrJs ψ hm,j for each d P rDs. Let ζrΘ γ,d,m s and ζrΘ h,m,j s for d P rDs, m P rM s and j P rJs, and we will specify the networks later. Also, let ζrΘ S,m s " ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq.

We consider a neural network ζrΘ d s " ζrΘ `spζ rΘ ˆspζ rΘ γ,d,1 sp¨q, ζrΘ S,1 sp¨qq, ..., ζrΘ ˆspζ rΘ γ,d,M sp¨q, ζrΘ S,M sp¨qqq. Then, an approximation error is evaluated as .

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 ď ÿ mPrM s › › › › › γ m,d â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ γ,d,m sp¨q, ζrΘ S,m sp¨qq › › › › › L 2 ď ÿ mPrM s › › › › › γ m,d â jPrJs ψ hm,j ´ζrΘ γ,d,m s b ζrΘ S,m s › › › › › L 2 `ÿ mPrM s › › › › ζrΘ γ,d,m s b ζrΘ S,m s ´ζrΘ ˆspζ rΘ γ,d,m sp¨q, ζrΘ S,m sp¨qq › › › › L 2 ď ÿ mPrM s › › ›γm,d b 1 r Sm ´ζrΘ γ,d,m s b ζrΘ S,m s › › › L 2 `M ď ÿ mPrM s › › ›γm,d b p1

For T 2,m , we specify ζrΘ h,m,j s as Theorem 3.1 in Petersen & Voigtlaender (2017) . Then, we evaluate the following as

}γ m,d ´ζrΘ γ,d,m s} L 2 ď › › › › › â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq › › › › › L 2 ď › › › › › â jPrJs ψ hm,j ´â jPrJs ζrΘ h,m,j s › › › › › L 2 `› › › › › â jPrJs ψ hm,j ´ζrΘ ˆspζ rΘ h,m,1 sp¨q, ..., ζrΘ h,m,1 sp¨qq › › › › › L 2 À ÿ jPrJs ź j 1 PrJsztju ´› › ›ψh m,j 1 › › › L 2 _ }ζrΘ h,m,j 1 } L 2 ¯› › ψ hm,j ´ζrΘ h,m,j s › › L 2 ` ď ÿ jPrJs › › ψ hm,j ´ζrΘ h,m,j s › › L 2 ` ˆ.

Here, the last inequality follows the boundedness of ψ h m,j 1 and ζrΘ h,m,j s by Theorem 3.1 in Petersen & Voigtlaender (2017) . Also, Theorem 3.1 in Petersen & Voigtlaender (2017) provides an existence of rΘ h,m,j such that }ψ hm,j ´ζrΘ h,m,j s} L 2 ď }Θ h,m,j } ´β{pD´1q 1

.

We apply the boundedness of ζrΘ h,m,j s, we have

T 2,m À ÿ jPrJs }Θ h,m,j } ´β{pD´1q 1 ` ˆ.

Combining the bounds for T 1,m and T 2,m , we bound

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 ď ÿ mPrM s }Θ γ,d,m } ´pβ`1q{D 1 `ÿ mPrM s ÿ jPrJs }Θ h,m,j } ´β{pD´1q 1 `pM `1q ˆ.

Here, we consider a parameter S " Yarotsky (2017) and Petersen & Voigtlaender (2017) , a proper selection of L " |Θ ˆ| and B " }Θ ˆ}8 provides ˆÀ }Θ ˆ}´β{D 0 . Then, we have

ř dPrDs }Θ d } 1 such that S -}Θ γ,d,m } 1 -}Θ h,m,j } 1 -}Θ ˆ}1 . Also, following

› › › › › › ÿ mPrM s γ m,d â jPrJs ψ hm,j ´ζrΘ d s › › › › › › L 2 À M JS ´β{D .

Since J is finite, we obtain the result.

B.4 PROOF OF THEOREM 1:

By the definition of p g in ( 2), the following inequality holds

EQUATION

for arbitrary g P G.

We consider a bound for d F pP ˚, P p g q as d F pP ˚, P

p g q " sup f PF pP ˚f ´Pp g f q " sup f PF pP ˚f ´Pn f `Pn f ´Pp g,m f `Pp g,m f ´Pp g f q ď sup f PF pP ˚f ´Pn f `Pp g,m f ´Pp g f q `sup f PF pP n f ´P 9 g,m f q,

where the inequality follows ( 9) with an existing 9 g P G. We will provide a detailed construction of g ˚. We continue the bound as

d F pP ˚, P p g q ď sup f PF pP ˚f ´Pn f `Pp g,m f ´Pp g f q `sup f PF pP n f ´P ˚f `P ˚f ´P 9 g f `P 9 g f ´P 9 g,m f q ď 2 sup gPG sup f PF |P g,m f ´Pg f | `sup f PF pP ˚f ´P 9 g f q `2 sup f PF |P n f ´P ˚f | ": i `ii `iii.

Here, i denotes an effect from m samplings, ii denotes an approximation error, and iii denotes an uncertainty with the n observations.

To evaluate i and iii, we provide the following lemma. This result follows a standard technique of the empirical process theory and we provide its outline for a sake of completeness. Lemma 4. Let H be a some set of measurable functions and X 1 , ..., X n " P be i.i.d. n observations. Suppose that E P rh 2 pXqs ď σ 2 and }h} L 8 ă C h hold with finite parameters σ 2 ą 0 and C h ą 0.

Then, there exists a constant C θ and we obtain

sup hPH ˇˇˇˇˇ1 n ÿ iPrns hpX i q ´EP rhpXqs ˇˇˇˇď inf ηą0 # 4η `12 ż C h η c log N p , H, } ¨}L 8 q n d `c 2τ σ 2 `4C θ n `τ C h n ˆ2 3 `Cθ

˙+ with probability at least 1 ´2 expp´τ q for all τ ą 0.

Proof. At the beginning, we bound an expectation of the empirical process (Steinwart & Christmann, 2008; Bartlett et al., 2005; Massart, 2000; Sriperumbudur et al., 2012) . Afterward, we evaluate a concentration of the empirical process around the expectation.

By applying the symmetrization and concentration techniques (Proposition 7.10 in Steinwart & Christmann ( 2008)), we obtain

E P bn » -sup hPH ˇˇˇˇˇ1 n ÿ iPrns hpX i q ´ErhpXqs ˇˇˇˇˇfi fl ď 2E P bn bν bn » -sup hPH ˇˇˇˇˇ1 n ÿ iPrns u i hpX i q ˇˇˇˇˇfi fl ,

where u i " ν is the Rademacher variable which takes 0 or 1 with probability 0.5. Combining this bound with the Taralgand's inequality (Theorem A.9.1 in Steinwart & Christmann (2008) ), we obtain the following inequality

EQUATION

with probability at least 1 ´expp´τ q for all τ ą 0 and θ ą 0.

About the term with the Rademacher variable, we also apply a similar strategy (Lemma A.4 in Bartlett et al. ( 2005)), then obtain

EQUATION

with probability at least 1 ´expp´τ 1 q for all τ 1 ą 0 and θ 1 ą 0.

Let } ¨}n be an empirical norm as }f } 2 n " n ´1 ř iPrns f pX i q 2 . About the term E ν bn " sup hPH ˇˇ1 n ř iPrns u i hpX i q ˇˇı, we apply the chaining technique and obtain

EQUATION

where the last inequality follows a bound for an empirical norm and the boundedness of H.

Combining ( 10), ( 11) and ( 12) and changing variables, we obtain the result.

To bound I with r X 1 , ..., r X m " P g , we consider the following value where we define H " th " f ˝g | f P F, g P Gu. To apply Lemma 4, we investigate a covering number N p , H, } ¨}L 8 q. Lemma 5. Assume that f P F is L 1 -Lipschitz continuous. We obtain log N p , H, } ¨}L 8 q ď log N pp1 `L1 q ´1 , G, } ¨}L 8 q `log N pp1 `L1 q ´1 , F, } ¨}L 8 q Proof. Fix ą 0. Let G Ă G and F Ă F be covering sets as a set of centers of -balls for the covering G and F. Obviously, |G| " N p , G, } ¨}L 8 q and |F | " N p , F, } ¨}L 8 q. We define a subset For any h P H, there exist g P G and f P F, then f " f ˝g holds. Also, by the definition of covering sets, there exist f 1 P F and g 1 P G such that }f ´f 1 } L 8 ď and }g ´g1 } L 8 ď . Let h 1 " f 1 ˝g1 , and we measure the distance }h ´h1 } L 8 ď }f ˝g ´f 1 ˝g1 } L 8

" }f ˝g ´f ˝g1 `f ˝g1 ´f 1 ˝g1 } L 8 ď }f ˝g ´f ˝g1 } L 8 `}f ˝g1 ´f 1 ˝g1 } L 8

ď L 1 }g ´g1 } L 8 `}f ´f 1 } L 8 ď pL 1 `1q .

Here, the third inequality follows the Lipschitz property of f P F. Here, we know that H is covered by pL 1 `1q -balls with the center H. Since |H| " |G| ˆ|F |, the result holds. Now, we have the following entropy bound log N p , H, } ¨}L 8 q ď log N pp1 `L1 q ´1 , G, } ¨}L 8 q `log N pp1 `L1 q ´1 , F, } ¨}L 8 q ď pS g `1q logp2pL 1 `1q ´1pL g `1qD g B g q `min " pS f `1q logp2pL 1 `1q ´1pL f `1qD f B f q, C κ p1 `L1 q ´κ* with D g :" ś PrLg`1s pD `1q and D f :" ś PrL f `1s pD `1q. Let Γ f :" 2pL f `1qD f B f , and N p r Fq :" log N p , r F, } ¨}n q for brevity. Here, we apply Lemma 8 in Schmidt-Hieber (2017) for the entropy bound for G and F. Using the entropy bound and Lemma 4, we obtain

EQUATION

with some η ą 0, A 1 " 12 log 1{2 Γ f , A 2 " C r F log 1{2 C r F `p2τ σ 2 `Cθ q 1{2 , and A 3 " τ C h p2{3 Cθ q. Also, we set Υ n p r

Fq " 4η `12

n 1{2 ş C Ă F

η N pL1`1q ´1 p r Fq 1{2 d . Then, we have

EQUATION

)

About I, we define Γ g :" 2pL f `1qD g B g and obtain a similar bound as

i ď Υ m p r Fq `1 m 1{2 ´pS g `1q 1{2 A 1 1 `A1 2 ¯`A 1 3 m ,

where A 1 1 " 12plog 1{2 Γ f `log 1{2 Γ g q, A 2 " C r F log 1{2 C r F `CG log 1{2 C G `2p2τ σ 2 `Cθ q 1{2 , and A 3 " 2τ C h p2{3 `Cθ q.

About ii, we evaluate the error from approximation by constructing a specific deep neural network for generators. We apply Lemma 3 and let 9 g " p 9 g 1 , ..., 9 g D q be a generator specified in Lemma 3.

ii 

:



Figures and Tables:

Figure 5: Generalization errors.

Figure 6: Estimated density functions with the case (B).

˝g | g P G, h P F * Ă H, and we known |H| " |G| ˆ|F |.

Each of the terms I, II and III has the following role: I bounds an error by the m samplings, II bounds an error from approximation by G, and III bounds an error by n observations.

Table content: <table><tr><td colspan="4">Proof Outline: By the definition of P g in (2) and standard calculation, we obtain the inequality p</td></tr><tr><td>d F pP ˚, P g q ď 2 sup p</td><td>sup</td><td>ˇľoooooooooooooooooooooooomoooooooooooooooooooooooon ˇˇE Pg,m rf pXqs ´EPg rf pXqs</td><td>`inf</td></tr><tr><td>gPG</td><td>f PF</td><td/><td/></tr><tr><td/><td/><td>":i</td><td/></tr></table>

Sm ´ζrΘ S,m sq `pγ m,d ´ζrΘ γ,d,m sq b ζrΘ S,m s `}γ m,d ´ζrΘ γ,d,m s} L 2 }ζrΘ S,m s} L 8 `M ":where the last inequality follows the Hölder's inequality.About T 1,m , there exists a corresponding ζrΘ γ,d,m s such that }γ m,d ´ζrΘ γ,d,m s} L 2 À }Θ γ,d,m }

Table content: <table><tr><td/><td/><td/><td>´pβ`1q{D 1</td><td>,</td></tr><tr><td colspan="4">by following Theorem A.8 in Petersen &amp; Voigtlaender (2017). Also, since γ m,d is bounded by its</td></tr><tr><td colspan="4">smoothness and compact support, we have }γ m,d } L 8 ă 8 hence</td></tr><tr><td/><td/><td colspan="2">´pβ`1q{D T 1,m À }Θ γ,d,m } 1</td></tr><tr><td/><td/><td/><td>›</td></tr><tr><td/><td/><td/><td>› › L 2 `M ď</td></tr><tr><td>ÿ</td><td/><td>›</td><td>›</td></tr><tr><td>mPrM s</td><td>}γ m,d } L 8</td><td colspan="2">› ›1 Sm ´ζrΘ S,m s r › › L 2</td></tr><tr><td>ÿ</td><td/><td/></tr><tr><td/><td colspan="2">T 1,m `T2,m `M ˆ,</td></tr><tr><td colspan="2">mPrM s</td><td/></tr></table>

" P g ˚f ´P 9 g f

Table content: <table><tr><td>ż</td><td/><td/><td/><td/></tr><tr><td>"</td><td colspan="4">pf ˝g˚´f ˝9 gqdP Z</td></tr><tr><td/><td/><td>ż</td><td/><td/></tr><tr><td colspan="2">ď L 1</td><td colspan="3">}g ˚´9 g} 2 dP Z</td></tr><tr><td colspan="2">ď L 1</td><td>¨ÿ dPrDs</td><td>ż</td><td>|g d pxq ´9 g d pxq| 2 dP Z pxq</td><td>‚1{2</td></tr><tr><td colspan="2">" L 1</td><td>¨ÿ dPrDs</td><td colspan="2">}g d ´9 g d } 2 L 2</td></tr></table>

Peer review (iclr2019):
 This paper provides a theoretical study of GANs in the following setting: - The target distribution has a locally smooth density on a compact set [0, 1]^D. It might be supported only on M disjoint components, each of which has a smooth boundary, within that compact set. - The latent noise dimension (inputs to the generator) is of the same dimension as the data. - An IPM loss (1) is used. - The discriminator functions of the IPM and the generator networks are both ReLU networks of at most L layers and at most S total nonzero weights, with all weights having magnitude at most B. - The discriminator functions are Lipschitz continuous; this is implied by the previous assumption, but the bound is tighter if we have a tighter constraint here. - We obtain the generator which exactly minimizes the IPM between the empirical distributions of m samples from the model and n samples from the target. - Maybe: there is some g such that P* is produced by g. It*s not clear in your statement of Theorem 1 whether this is necessary, or exactly what it means when you say that in Lemma 3, and I haven*t fully checked what*s used yet; it would help to explicitly say this is not assumed if it*s not. Pointing out that the kinds of distributions handled by GANs often have disjoint support, and analyzing this case, is certainly of interest. The full-dimensional support assumption is not ideal, but of course just because the analysis doesn*t apply to most practical GAN settings doesn*t mean it*s not an important step towards one that does. Also note that the assumption about the structure of the networks eliminates the MMD GANs that you use in experiments -- which have a kernel function at the top of the critic network -- though it does allow for most GAN variants. Maybe the most interesting algorithm for this setting is the Coulomb GAN (ICLR 2018, https://arxiv.org/abs/1708.08819 ), which uses a neural network critic of the kind you study but estimates a distance which (unlike the Wasserstein and most other GAN objective functions) has good statistical convergence properties (kappa=2 as you mention). My biggest concern by far, though, is Proposition 1. You present it as if it*s a lower bound: establishing that there is some class of distributions for which Theorem 1 shows that GANs can account for local smoothness and standard methods are shown not to be able to. This isn*t what you do; instead you exhibit a class of distributions for which Theorem 1 shows that GANs can account for local smoothness, and previous analyses of standard methods do not show that they are able to take advantage of it. This is not the same thing at all! Although the previous upper bounds have matching lower bounds, you don*t demonstrate (and it is likely not the case) that the distribution you show fits into the class of distributions used by the previous lower bounds, and so it remains very possible that other methods are able to take advantage of local smoothness as well as GANs do. Given that Proposition 1 is hence a very weak statement, your main contribution in terms of disconnected support becomes "we can show that GANs can adapt to disconnected supports (under these other assumptions) that has not previously been shown for other methods." Not only is this a weaker result, but the degree to which you show GANs can take advantage of local smoothness is somewhat limited: at least with the parameter choices in Corollary 1, the smoothness only improves m dependence, not n dependence. But in the GAN setting, m is essentially a question of how long you optimize for (and the relative rates between generator and discriminator updates, and various other questions like that out of scope for this paper), not any kind of externally fixed limitation like n. It*s perhaps not too surprising that you don*t show that optimizing a WGAN is statistically easier than estimating Wasserstein the distance, but given that estimating Wasserstein is so hard in high dimensions, it*s a little disappointing. (Maybe it*s easier, so that kappa is smaller, with locally smooth densities as here, though I don*t know of any results like that offhand.) (It*s interesting, then, that in Corollary 1 the generator complexity depends only on m, basically the amount of optimization you*re willing to do, while the discriminator complexity depends only on the available number of target samples n.) Another concern is that to me, it is not very clear exactly what the statements of the assumptions mean. For example, does Theorem 1 apply only if I search over all generators in the class .mathcal G = .Xi(S_g, B_g, L_g)? In particular, does this mean that I have to consider all possible architectures matching those constraints, including allowing for all possible depths up to L_g, and all possible ways of allocating widths of the various interior layers / which weight entries are fixed at zero? It seems so, but this could be more explicit in the statements, even just by replacing "an existing .mathcal G" with ".mathcal G = .Xi(S_g, B_g, L_g)" in the statement of (e.g.) Theorem 1. In your numerical experiments: you don*t make it at all clear enough that you*re plotting *different loss functions* for the GANs and the other methods! (You say this, but only in the text where it should definitely also be in the figure caption.) What happens if you plot the L2 difference for all methods, and the MMD/Wasserstein for all methods? Looking at Figure 6, it*s not obvious that the GAN would do so substantially better. (It does seem to perhaps have the overall scale of the two components better than the other methods, but it doesn*t look like as enormous a difference as it seems from Figure 5.) Overall: Theorem 1 is of interest, but the results and especially the comparison to classic methods are not as resounding as they*re presented here. (Note that I have not (yet) verified or even really read most of the proofs; I might come back and do that later.) Smaller points: - I don*t think that f-GAN actually fits in the framework (1) as you claim, since it needs to use the conjugate of f on the samples from Q. Also, the original GAN does fit into (1) but not your assumptions about the network form of f, since it needs a log in its activations. - Another class of generative models where disconnected supports are really important is normalizing flows, which often build "bridges" between separated modes because (like your Lemma 2) their generators are constrained to be smooth and invertible. See e.g. Figure 2 of https://arxiv.org/abs/1810.01367 (who propose a new normalizing flow less susceptible to these problems). - Remark 1 seems so obvious that it need not even be stated, since beta-smooth implies beta*-smooth for beta* < beta. It would only be interesting if you could actually take advantage of the smoother components somehow. - Many papers in your bibliography are cited only as arXiv preprints when they were actually published in various places. For example, the first four papers were published at ICLR 2017, ICML 2017, ICML 2017, and ICLR 2018, respectively. - There are many small typos and grammatical errors in the draft, including some that would be caught by a spell-checker ("methdos" on page 8), and an undefined LaTeX reference at the top of page 2. It would benefit from a thorough proofread.