Ugo Tanielian
email: <u.tanielian@criteo.com>.

Thibaut Issenhuth

Elvis Dohmatob

Jérémie Mary

Learning disconnected manifolds: no GAN's land

Typical architectures of Generative Adversarial

Networks make use of a unimodal latent/input distribution transformed by a continuous generator. Consequently, the modeled distribution always has connected support which is cumbersome when learning a disconnected set of manifolds. We formalize this problem by establishing a "no free lunch" theorem for the disconnected manifold learning stating an upper-bound on the precision of the targeted distribution. This is done by building on the necessary existence of a low-quality region where the generator continuously samples data between two disconnected modes. Finally, we derive a rejection sampling method based on the norm of generator's Jacobian and show its efficiency on several generators including BigGAN.

Introduction

GANs [START_REF] Goodfellow | Generative adversarial nets[END_REF] provide a very effective tool for the unsupervised learning of complex probability distributions. For example, [START_REF] Karras | A style-based generator architecture for generative adversarial networks[END_REF] generate very realistic human faces while [START_REF] Yu | Sequence generative adversarial nets with policy gradient[END_REF] match stateof-the-art text corpora generation. Despite some early theoretical results on the stability of GANs (Arjovsky & Bottou, 2017) and on their approximation and asymptotic properties [START_REF] Biau | Some theoretical properties of gans[END_REF], their training remains challenging. More specifically, GANs raise a mystery formalized by [START_REF] Khayatkhoei | Disconnected manifold learning for generative adversarial networks[END_REF]: how can they fit disconnected manifolds when they are trained to continuously transform a unimodal latent distribution? While this question remains widely open, we will show that studying it can lead to some improvements in the sampling quality of GANs.

Indeed, training a GAN with the objective of continuously transforming samples from an unimodal distribution into a disconnected requires balancing between two caveats. On Proceedings of the 37 th International Conference on Machine Learning, Vienna, Austria, PMLR 108, 2020. Copyright 2020 by the author(s). one hand, the generator could just ignore all modes but one, producing a very limited variety of high quality samples: this is an extreme case of the well known mode collapse (Arjovsky & Bottou, 2017). On the other hand, the generator could cover the different modes of the target distribution and necessarily generates samples out of the real data manifold as previously explained by [START_REF] Khayatkhoei | Disconnected manifold learning for generative adversarial networks[END_REF].

As brought to the fore by [START_REF] Roth | Stabilizing training of generative adversarial networks through regularization[END_REF], there is a density mis-specification between the true distribution and the model distribution. Indeed, one cannot find parameters such that the model density function is arbitrarily close to the true distribution. To solve this issue, many empirical works have proposed to over-parameterize the generative distributions, as for instance, using a mixture of generators to better fit the different target modes. [START_REF] Tolstikhin | Boosting generative models[END_REF] rely on boosting while [START_REF] Khayatkhoei | Disconnected manifold learning for generative adversarial networks[END_REF] force each generator to target different sub-manifolds thanks to a criterion based on mutual information. Another direction is to add complexity in the latent space using a mixture of Gaussian distributions [START_REF] Gurumurthy | Generative adversarial networks for diverse and limited data[END_REF].

To better visualize this phenomenon, we consider a simple 2D motivational example where the real data lies on two disconnected manifolds. Empirically, when learning the distribution, GANs split the Gaussian latent space into two modes, as highlighted by the separation line in red in Figure 1a. More importantly, each sample drawn inside this red area in Figure 1a is then mapped in the output space in between the two modes (see Figure 1b). For the quantitative evaluation of the presence of out-of-manifold samples, a natural metric is the Precision-Recall (PR) proposed by [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] and its improved version (Improved PR) [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF]. A first contribution of this paper is to formally link them. Then, taking advantage of these metrics, we lower bound the measure of this out-ofmanifold region and formalize the impossibility of learning disconnected manifolds with standard GANs. We also extend this observation to the multi-class generation case and show that the volume of off-manifold areas increases with the number of covered manifolds. In the limit, this increase drives the precision to zero.

To solve this issue and increase the precision of GANs, we argue that it is possible to remove out-of-manifold samples using a truncation method. Building on the work of [START_REF] Arvanitidis | Latent space oddity: on the curvature of deep generative models[END_REF] who define a Riemaniann metric that significantly improves clustering in the latent space, our truncation method is based on information conveyed by the Jacobian's norm of the generator. We empirically show that this rejection sampling scheme enables us to better fit disconnected manifolds without over-parametrizing neither the generative class of functions nor the latent distribution. Finally, in a very large high dimensional setting, we discuss the advantages of our rejection method and compare it to the truncation trick introduced by [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF].

In a nutshell, our contributions are the following:

• We discuss evaluation of GANs and formally link the PR measure [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] and its Improved PR version [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF].

• We upper bound the precision of GANs with Gaussian latent distribution and formalize an impossibility result for disconnected manifolds learning.

• Using toy datasets, we illustrate the behavior of GANs when learning disconnected manifolds and derive a new truncation method based on the Jacobian's Frobenius norm of the generator. We confirm its empirical performance on state-of-the-art models and datasets.

Related work

Fighting mode collapse. [START_REF] Goodfellow | Generative adversarial nets[END_REF] were the first to raise the problem of mode collapse in the learning of disconnected manifolds with GANs. They observed that when the generator is trained too long without updating the discriminator, the output distribution collapses to a few modes reducing the diversity of the samples. To tackle this issue, [START_REF] Salimans | Improved techniques for training gans[END_REF]; [START_REF] Lin | The power of two samples in generative adversarial networks[END_REF] suggested feeding several samples to the discriminator. [START_REF] Srivastava | Reducing mode collapse in gans using implicit variational learning[END_REF] proposed the use of a reconstructor network, mapping the data to the latent space to increase diversity.

In a different direction, Arjovsky & Bottou (2017) showed that training GANs using the original formulation [START_REF] Goodfellow | Generative adversarial nets[END_REF] leads to instability or vanishing gradients.

To solve this issue, they proposed a Wasserstein GAN architecture (Arjovsky et al., 2017) where they restrict the class of discriminative functions to 1-Lipschitz functions using weight clipping. Pointing to issues with this clipping, [START_REF] Gulrajani | Improved training of wasserstein gans[END_REF]; [START_REF] Miyato | Spectral normalization for generative adversarial networks[END_REF] proposed relaxed ways to enforce the Lipschitzness of the discriminator, either by using a gradient penalty or a spectral normalization. Albeit not exactly approximating the Wasserstein's distance [START_REF] Petzka | On the regularization of wasserstein GANs[END_REF], both implementations lead to good empirical results, significantly reducing mode collapse.

Building on all of these works, we will further assume that generators are now able to cover most of the modes of the target distribution, leaving us the problem of out-of-manifold samples (a.k.a. low-quality pictures).

Generation of disconnected manifolds. When learning complex manifolds in high dimensional spaces using deep generative models, [START_REF] Fefferman | Testing the manifold hypothesis[END_REF] highlighted the importance of understanding the underlying geometry. More precisely, the learning of disconnected manifold requires the introduction of disconnectedness in the model. [START_REF] Gurumurthy | Generative adversarial networks for diverse and limited data[END_REF] used a multi-modal entry distribution, making the latent space disconnected, and showed better coverage when data is limited and diverse. Alternatively, [START_REF] Khayatkhoei | Disconnected manifold learning for generative adversarial networks[END_REF] studied the learning of a mixture of generators. Using a mutual information term, they encourage each generator to focus on a different submanifold so that the mixture covers the whole support. This idea of using an ensemble of generators is also present in the work of [START_REF] Tolstikhin | Boosting generative models[END_REF] and [START_REF] Zhong | Rethinking generative mode coverage: A pointwise guaranteed approach[END_REF], though they were primarily interested in the reduction of mode collapse.

In this paper, we propose a truncation method to separate the latent space into several disjoint areas. It is a way to learn disconnected manifolds without relying on the previously introduced over-parameterization techniques. As our proposal can be applied without retraining the whole architecture, we can use it successfully on very larges nets.

Close to this idea, [START_REF] Azadi | Discriminator rejection sampling[END_REF] introduced a rejection strategy based on the output of the discriminator. However, this rejection sampling scheme requires the discriminator to be trained with a classification loss while our proposition can be applied to any generative models.

Evaluating GANs. The evaluation of generative models is an active area of research. Some of the proposed metrics only measure the quality of the generated samples such as the Inception score [START_REF] Salimans | Improved techniques for training gans[END_REF] while others define distances between probability distributions. This is the case of the Frechet Inception distance [START_REF] Heusel | Gans trained by a two time-scale update rule converge to a local nash equilibrium[END_REF], the Wasserstein distance (Arjovsky et al., 2017) or kernelbased metrics [START_REF] Gretton | A kernel two-sample test[END_REF]. The other main caveat for evaluating GANs lies in the fact that one does not have access to the true density nor the model density, prohibiting the use of any density based metrics. To solve this issue, the use of a third network that acts as an objective referee is common. For instance, the Inception score uses outputs from InceptionNet while the Fréchet Inception Distance compares statistics of InceptionNet activations. Since our work focuses on out-of-manifold samples, a natural measure is the PR measure [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] and its Improved PR version [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF], extensively discussed in the next section.

In the following, alongside precise definitions, we exhibit an upper bound on the precision of GANs with high recall (i.e. no mode collapse) and present a new truncation method.

Our approach

We start with a formal description of the framework of GANs and the relevant metrics. We later show a "no free lunch" theorem proving the necessary existence of an area in the latent space that generates out-of-manifold samples. We name this region the no GAN's land since any data point sampled from this area will be in the frontier in between two different modes. We claim that dealing with it requires special care. Finally, we propose a rejection sampling procedure to avoid points out of the true manifold.

Notations

In the original setting of Generative Adversarial Networks (GANs), one tries to generate data that are "similar" to samples collected from some unknown probability measure µ . To do so, we use a parametric family of generative distribution where each distribution is the push-forward measure of a latent distribution Z and a continuous function modeled by a neural network.

Assumption 1. The latent distribution Z is such that S Z is a connected space.

Note that for any distribution µ, S µ refers to its support. Assumption 1 is common for GANs as in most of all practical applications, the random variable Z defined on a low dimensional space R d is either a multivariate Gaussian distribution or uniform distribution defined on a compact.

The measure µ is defined on a subset E of R D (potentially a highly dimensional space), equipped with the norm • . The generator has the form of a parameterized class of functions from R d (a space with a much lower dimension) to E, say G = {G θ : θ ∈ Θ}, where Θ ⊆ R p is the set of parameters describing the model. Each function G θ thus takes input from a d-dimensional random variable Z (Z is associated with probability distribution γ) and outputs "fake" observations with distribution µ θ . Thus, the class of probability measures P = {µ θ : θ ∈ Θ} is the natural class of distributions associated with the generator, and the objective of GANs is to find inside this class of candidates the one that generates the most realistic samples, closest to the ones collected from the unknown distribution µ . Assumption 2. Let L > 0. The generator G θ takes the form of a neural network whose Lipchitz constant is smaller than L, i.e. for all (z, z ), we have

G θ (z ) -G θ (z) L z -z .
This is a reasonable assumption, since [START_REF] Virmaux | Lipschitz regularity of deep neural networks: analysis and efficient estimation[END_REF] present an algorithm that upper-bounds the Lipschitz constant of deep neural networks. Initially, 1-Lipschitzness was enforced only for the discriminator by clipping the weigths (Arjovsky et al., 2017;[START_REF] Zhang | On the discriminative-generalization tradeoff in GANs[END_REF], adding a gradient penalty [START_REF] Gulrajani | Improved training of wasserstein gans[END_REF][START_REF] Roth | Stabilizing training of generative adversarial networks through regularization[END_REF][START_REF] Petzka | On the regularization of wasserstein GANs[END_REF], or penalizing the spectral norms [START_REF] Miyato | Spectral normalization for generative adversarial networks[END_REF]. Nowadays, state-of-the-art architectures for large scale generators such as SAGAN [START_REF] Zhang | Self-attention generative adversarial networks[END_REF] and BigGAN [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF]) also make use of spectral normalization for the generator.

Evaluating GANs with Precision and Recall

When learning disconnected manifolds, [START_REF] Srivastava | Reducing mode collapse in gans using implicit variational learning[END_REF] proved the need of measuring simultaneously the quality of the samples generated and the mode collapse. [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] proposed the use of a PR metric to measure the quality of GANs. The key intuition is that precision should quantify how much of the fake distribution can be generated by the true distribution while recall measures how much of the true distribution can be re-constructed by the model distribution. More formally, it is defined as follows: Definition 1. [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] Let X, Y be two probability distributions. For α, β ∈ (0, 1], the probability distribution X is said to have an attainable precision α at recall β w.r.t. Y if there exists probability distributions µ, ν X , ν Y such that

Y = βµ + (1 -β)ν Y and X = αµ + (1 -α)ν X
The component ν Y denotes the part of Y that is "missed" by X, whereas, ν X denotes the "noise" part of X. We denote ᾱ (respectively β) the maximum attainable precision (respectively recall). Th. 1 of [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] states:

X S Y = ᾱ and Y S X = β Improved PR metric. [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF] highlighted an important drawback of the PR metric proposed by [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF]: it cannot correctly interpret situations when a large numbers of samples are packed together.

To better understand this situation, consider a case where the generator slightly collapses on a specific data point, i.e. there exists x ∈ E, µ θ (x) > 0. We show in Appendix A that if µ is a non-atomic probability measure and µ θ is highly precise (i.e. α = 1), then the recall β must be 0.

To solve these issues, [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF] proposed an Improved Precision-Recall (Improved PR) metric built on a nonparametric estimation of support of densities.

Definition 2. [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF] Let X, Y be two probability distributions. Let D X , D Y be two finite sample datasets:

D X := {x i ∼ X, i ∈ [1, n]} and D Y := {y i ∼ Y, i ∈ [1, n]}.
For any x ∈ D X (respectively for any y ∈ D Y ), we consider (x (1) , . . . , x (n-1) ), the re-ordening of elements in D X \ x given their euclidean distance with x.

For any k ∈ N and x ∈ D X , the precision α n k (x) of point x is defined as

α n k (x) = 1 ⇐⇒ ∃y ∈ D Y , x -y y (k) -y
Similarly, the recall

β n k (y) of any given y ∈ D Y is β n k (y) = 1 ⇐⇒ ∃x ∈ D X , y -x x (k) -x
Improved precision (respectively recall) are defined as the average over D X (respectively D Y ) as follows

α n k = 1 n xi∈D X α n k (x i ) β n k = 1 n yi∈D Y β n k (y i )
A first contribution is to formalize the link between PR and Improved PR with the following theorem:

Theorem 1. Let µ and µ θ be two probability distributions with uniformly continuous probability density functions f µ and f ν . Assume that there exists constants a 1 > 0, a 2 > 0 such that for all x ∈ E we have

a 1 < f µ (x) a 2 and a 1 < f µ θ (x) a 2 for some c > 0. Assume that k, n are such that k log(n) → +∞ and k n → 0. Then, α n k → ᾱ in probability and β n k → β in proba.
This theorem, whose proof is delayed to Appendix B, underlines the nature of the Improved PR metric: the metric compares the supports of the modeled probability distribution µ θ and of the true distribution µ . This means that Improved PR is a tuple made of both maximum attainable precision ᾱ and recall β (e.g. Theorem 1 of [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF]). As Improved PR is shown to have a better performance evaluating GANs sample quality, we use this metric for both the following theoretical results and experiments.

Learning disconnected manifolds

In this section, we aim to stress the difficulties of learning disconnected manifolds with standard GANs architectures.

To begin with, we recall the following lemma.

Lemma 1. Assume that Assumptions 1 and 2 are satisfied.

Then, for any θ ∈ Θ, the support S µ θ is connected.

There is consequently a discrepancy between the connectedness of S µ θ and the disconnectedness of S µ . In the case where the manifold lays on two disconnected components, our next theorem exhibit a no free lunch theorem:

Theorem 2. ("No free lunch" theorem) Assume that Assumptions 1 and 2 are satisfied. Assume also that true distribution µ lays on two equally measured disconnected manifolds distant from a distance D > 0.

Then, any estimator µ θ that samples equally in both modes must have a precision ᾱ such that ᾱ + 2ε

√ 2π e -Φ -1 ( ᾱ 2 ) 2 2 1. Besides, if ᾱ 3/4, ᾱ 1 -2 π W ( D 2 4L 2 ) where W is the Lambert W function.
The proof of this theorem is delayed to Appendix C. It is mainly based on the Gaussian isoperimetric inequality [START_REF] Borell | The brunn-minkowski inequality in gauss space[END_REF][START_REF] Sudakov | Extremal properties of half-spaces for spherically invariant measures[END_REF] that states that among all sets of given Gaussian measure in any finite dimensional Euclidean space, half-spaces have the minimal Gaussian boundary measure. If in Fig. 1, the generator has thus learned the optimal separation, it is yet not known, to the limit of our knowledge, how to enforce such geometrical properties in the latent space.

In real world applications, when the number of distinct sub-manifolds increases, we expect the volume of these boundaries to increase with respect to the number of different classes covered by the modeled distribution µ θ . Going in this direction, we better formalize this situation, and show an extended "no free lunch theorem" by expliciting an upper-bound of the precision ᾱ in this broader framework.

Assumption 3. The true distribution µ lays on M equallymeasured disconnected components at least distant from some constant D > 0.

This is likely to be true for datasets made of symbol designed to be highly distinguishable (e.g. digits in the MNIST dataset). In very high dimension, this assumption also holds for complex classes of objects appearing in many different contexts (e.g. the bubble class in ImageNet, see Appendix).

To better apprehend the next theorem, note A m the preimage in the latent space of mode m and A r m its renlargement:

A r m := {z ∈ R d | dist(z, A m ) ≤ r}, r > 0. Theorem 3.
(Generalized "no free lunch" theorem) Assume that Assumptions 1, 2, and 3 are satisfied, and that the pre- Then, any estimator µ θ with recall β > 1 M must have a precision ᾱ at most 1+x 2

x 2 e -1 2 ε 2 e -εx where x = Φ -1 (1 -1 βM ) and Φ is the c.d.f. of a standard normal distribution.

Theorem 3, whose proof is delayed to Appendix D, states a lower-bound the measure of samples mapped out of the true manifold. We expect our bound to be loose since no theoretical results are known, to the best of our knowledge, on the geometry of the separation that minimizes the boundary between different classes (when M 3). Finding this optimal cut would be an extension of the honeycomb theorem [START_REF] Hales | The honeycomb conjecture[END_REF]. In Appendix D.2 we give a more technical statement of Theorem 3 without assuming equality of measure of the sets A ε m . The idea of the proof is to consider the border of an individual cell with the rest of the partition. It is clear that at least half of the frontier will be inside this specific cell. Then, to get to the final result, we sum the measures of the frontiers contained inside all of the different cells. Remark that our analysis is fine enough to keep a dependency in M which translates into a maximum precision that goes to zero when M goes to the infinity and all the modes are covered. More precisely, in this scenario where all pre-images have equal measures in the latent space, one can derive the following bound for large values of K:

ᾱ K→∞ e -1 2 ε 2 e -ε √ 2 log(K) where ε = D 2L (1)
For a fixed generator, Equation (1) illustrates that the precision ᾱ decreases when either the distance D (equivalently ε) or the number of classes M increases. For a given ε, ᾱ converges to 0 with a speed O( 1

K √ 2ε
). To better illustrate this asymptotic result, we provide results from a 2D synthetic setting. In this toy dataset, we control both the number M of disconnected manifolds and the distance D.

Jacobian-based truncation (JBT) method

The analysis of the deformation of the latent space offers a grasp on the behavior of GANs. For instance, Arvanitidis et al. ( 2017) propose a distance accounting for the distortions made by the generator. For any pair of points (z 1 , z 2 ) ∼ Z 2 , the distance is defined as the length of the geodesic

d(z 1 , z 2 ) = [0,1] J G θ (γ t ) dγt
dt dt where γ is the geodesic parameterized by t ∈ [0, 1] and J G θ (z) denotes the Jacobian matrix of the generator at point z. Authors have shown that the use of this distance in the latent space improves clustering and interpretability. We make a similar observation that the generator's Jacobian Frobenius norm provides meaningful information.

Indeed, the frontiers highlighted in Figures 2a,2b, and 2c correspond to areas of low precision mapped out of the true manifold: this is the no GAN's land. We argue that when learning disconnected manifolds, the generator tries to minimize the number of samples that do not belong to the support of the true distribution and that this can only be done by making paths steeper in the no GAN's land. Consequently, data points G θ (z) with high Jacobian Frobenius norm (JFN) are more likely to be outside the true manifold. To improve the precision of generative models, we thus define a new truncation method by removing points with highest JFN.

However, note that computing the generators's JFN is expensive to compute for neural networks, since being defined as follows,

J G θ (z) 2 F = m i=1 n j=1 ∂G θ (z) i ∂z j 2 ,
it requires a number of backward passes equal to the output dimension. To make our truncation method tractable, we use a stochastic approximation of the Jacobian Frobenius norm based on the following result from [START_REF] Rifai | Higher order contractive auto-encoder[END_REF]:

J G θ (z) 2 = lim N →∞ σ→0 1 N N εi 1 σ 2 G θ (z + ε i ) -G θ (z) 2
where ε i ∼∼ N (0, σ 2 I and I is the identity matrix of dimension d. The variance σ of the noise and the number of samples are used as hyper-parameters. In practice, σ in [1e-4; 1e-2] and N = 10 give consistent results.

Based on the preceding analysis, we propose a new Jacobian-based truncation (JBT) method that rejects a certain ratio of the generated points with highest JFN. This truncation ratio is considered as an hyper-parameter for the model. We show in our experiments that our JBT can be used to to detect samples outside the real data manifold and that it consequently improves the precision of the generated distribution as measured by the Improved PR metric.

Experiments

In the following, we show that our truncation method, JBT, can significantly improve the performances of generative models on several models, metrics and datasets. Furthermore, we compare JBT with over-parametrization techniques specifically designed for disconnected manifold learning. We show that our truncation method reaches or surpasses their performance, while it has the benefit of not modifying the training process of GANs nor using a mixture of generators, which is computationally expensive. Finally, we confirm the efficiency of our method by applying it on top of BigGAN [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF].

Except for BigGAN, for all our experiments, we use Wasserstein GAN with gradient penalty [START_REF] Gulrajani | Improved training of wasserstein gans[END_REF], called WGAN for conciseness. We give in Appendix K the full details of our experimental setting. The use of WGAN is motivated by the fact that it was shown to stabilize the training and significantly reduce mode collapse (Arjovsky & Bottou, 2017). However, we want to emphasise that our method can be plugged on top of any generative model fitting disconnected components.

Evaluation metrics

To measure performances of GANs when dealing with low dimensional applications -as with synthetic datasets -we equip our space with the standard Euclidean distance. However, for high dimensional applications such as image generation, [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF]; [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF] have shown that embedding images into a feature space with a pre-trained convolutional classifier provides more semantic information. In this setting, we consequently use the euclidean distance between the images' embeddings from a classifier. φ is a pre-softmax layer of a supervised classifier, trained specifically on each dataset. Doing so, they will more easily separate images sampled from the true distribution µ from the ones sampled by the distribution µ θ .

We compare performances using Improved PR [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF]. We also report the Marginal Precision which is the precision of newly added samples when increasing the ratio of kept samples. Besides, for completeness, we report FID [START_REF] Heusel | Gans trained by a two time-scale update rule converge to a local nash equilibrium[END_REF] and recall precise definitions in Appendix G. Note that FID was not computed with InceptionNet, but a classifier pre-trained on each dataset.

Synthetic dataset

We first consider the true distribution to be a 2D Gaussian mixture of 9 components. Both the generator and the discriminator are modeled with a simple MLP with two hidden fully connected layers.

Interestingly, the generator tries to minimize the sampling of off-manifolds data during training until its JFN gets saturated. A visualization of this phenomenon is provided in Appendix H. One way to reduce the number of off-manifold samples is to use JBT. Indeed, off-manifold data points progressively disappear when being more and more selective, as illustrated in Figure 3c. We quantitatively confirm that our truncation method (JBT) improves the precision. On Fig. 3d, we observe that keeping the 70% of lowest JFN samples leads to an almost perfect precision of the support of the generated distribution. It proves that the off-manifold samples are in the 30% samples with highest JFN.

Image datasets

We further study JBT on three different datasets: MNIST (LeCun et al., 1998), FashionMNIST [START_REF] Xiao | Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms[END_REF] and CIFAR10 [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF]. Following (Khayatkhoei et al., 2018) implementation, we use a standard CNN architecture for MNIST and FashionMNIST while training a ResNet-based model for CIFAR10 [START_REF] Gulrajani | Improved training of wasserstein gans[END_REF].

Figure 4 highlights that JBT also works on high dimensional datasets as the marginal precision plummets for high truncation ratios. Furthermore, when looking at samples ranked by increasing order of their JFN, we notice that samples with highest JFN are standing in-between manifolds. For example, those are ambiguous digits resembling both a "0" and a "6" or shoes with unrealistic shapes.

To further assess the efficiency of our truncation method, we also compare its performances with two state-of-the-art over-parameterization techniques that were designed for disconnected manifold learning. First, [START_REF] Gurumurthy | Generative adversarial networks for diverse and limited data[END_REF] used on top of WGAN. Second, [START_REF] Khayatkhoei | Disconnected manifold learning for generative adversarial networks[END_REF] define DMLGAN, a mixture of generators to better learn disconnected manifolds. In this architecture, each generator is encouraged to target a different submanifold by enforcing high mutual information between generated samples and generator's ids. Keep in mind that for DeliGAN (respectively DMLGAN), the optimal number of components (respectively generators) is not known and is a hyper-parameter of the model that has to be cross-validated. Reported confidence intervals are 97% confidence intervals. On the second row, generated samples ordered by their JFN (left to right, top to bottom). We observe a concentration of off-manifold samples for images on the bottom row, confirming the soundness of JBT.

The results of the comparison are presented in Table 1. In both datasets, JBT 80 % outperforms DeliGAN and DML-GAN in terms of precision while keeping a reasonnable recall. This confirms our claim that over-parameterization techniques are unnecessary. As noticed by [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF], we also observe that FID does not correlate properly with the Improved PR metric. Based on the Frechet distance, only a distance between multivariate Gaussians, we argue that FID is not suited for disconnected manifold learning as it approximates distributions with unimodal ones and looses many information.

Spurious samples rejections on BigGAN

Thanks to the simplicity of JBT, we can also apply it on top of any trained generative model. In this subsection, we use JBT to improve the precision of a pre-trained Big-GAN model [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF], which generates classconditionned ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF] samples. The class-conditioning lowers the problem of off-manifold samples, since it reduces the disconnectedness in the output distribution. However, we argue that the issue can still exist on high-dimensional natural images, in particular complex classes can still be multi-modal (e.g. the bubble class). The bottom row in Figure 5 shows a random set of 128 images for three different classes ranked by their JFN in ascending order (left to right, top to bottom). We observe a clear concentration of spurious samples on the bottom row images.

To better assess the Jacobian based truncation method, we compare it with the truncation trick from [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF]. This truncation trick aims to reduce the variance of the latent space distribution using truncated Gaussians. While easy and effective, this truncation has some issues: it requires to complexify the loss to enforce orthogonality in weight matrices of the network. Moreover, as explained by Brock et al. ( 2019) "only 16% of models are amenable to truncation, compared to 60% when trained with Orthogonal Regularization". For fairness of comparison, the pre-trained network we use is optimized for their truncation method. On the opposite, JBT is simpler to apply since 100% of the tested models were amenable to the proposed truncation.

Results of this comparison are shown in the upper row of Figure 5. Our method can outperform their truncation trick on difficult classes with high intra-class variation, e.g. bubble and house finch. This confirms our claim that JBT can detect outliers within a class. However, one can note that their trick is particularly well suited for simpler unimodal classes, e.g. parachute and reaches high precision levels.

Conclusion

In this paper, we provide insights on the learning of disconnected manifolds with GANs. Our analysis shows the necessary existence of an off-manifold area with low precision. Besides, we empirically show on several datasets and models that we can detect these areas and remove samples located in between two modes thanks to a newly proposed truncation method. In future work, we will study how the use and understanding of latent space geometry can further help us to better fit the interior of disconnected manifolds. We suspect the no GAN's land to be involved in the training unstability of GANs since the presence of high gradients in a low probability region might induce a lot of variance.

A. Highlighting drawbacks of the PR metric by [START_REF] Sajjadi | Assessing generative models via precision and recall[END_REF] Lemma 2. Assume that the modeled distribution µ θ slightly collapses on a specific data point, i.e. there exists x ∈ E, µ θ (x) > 0. Assume also that µ is a continuous probability measure and that µ θ has a recall β = 1. Then the precision must be such that α = 0.

Proof. Using Definition 1, we have that there exists µ such that µ = αµ + (1 -α)ν µ and µ θ = µ Thus, 0 = µ (x) αµ(x) = αµ θ (x). Which implies that α = 0.

B. Proof of Theorem 1

The proof of Theorem 1 relies on theoretical results from non-parametric estimation of the supports of probability distribution studied by [START_REF] Devroye | Detection of abnormal behavior via nonparametric estimation of the support[END_REF].

For the following proofs, we will require the following notation: let ϕ be a strictly monotonous function be such that lim

n→∞ ϕ(n) n = 0 and lim n→∞ ϕ(n) log(n) = ∞.
We note B(x, r) ⊆ E, the open ball centered in x and of radius r. For a given probability distribution µ, S µ refers to its support. We recall that for any x in a dataset D, x (k) denotes its k nearest neighbor in D. Finally, for a given probability distribution µ and a dataset D µ sampled from µ n , we note R min and R max the following:

R min = min x∈E x -x (ϕ(n)) , R max = max x∈E x -x (ϕ(n))
(2)

In the following lemma, we show asymptotic behaviours for both R min and R max .

Lemma 3. Let µ be a probability distribution associated with a uniformly continuous probability density function f µ . Assume that there exists constants a 1 > 0, a 2 > 0 such that for all x ∈ E, we have a 1 < f µ (x) a 2 . Then,

R min -→ n→∞ 0 a.s. and R d min -→ n→∞ ∞ a.s. R max -→ n→∞ 0 a.s. and R d max -→ n→∞ ∞ a.s.
Proof. We will only prove that R max -→ n→∞ 0 a.s. and and R d min -→ n→∞ ∞ a.s. as the rest follows.

The result is based on a nearest neighbor result from [START_REF] Biau | Lectures on the nearest neighbor method[END_REF]. Considering the ϕ(n) nearest neighbor density estimate f

ϕ(n) n
based on a finite sample dataset D µ , Theorem 4.2 states that if f µ is uniformly continuous then:

sup x∈E f ϕ(n) n (x) -f µ (x) → 0. where f ϕ(n) n (x) = ϕ(n) nV d x-x ϕ(n) d with V d being the volume of the unit ball in R d .
Let ε > 0 such that ε < a 1 /2. There exists N ∈ N such that for all n N , we have, almost surely, for all x ∈ E:

a 1 -ε f ϕ(n) n (x) a 2 + ε a 1 -ε ϕ(n) nV d x -x ϕ(n) d a 2 + ε
Consequently, for all n N , for all x ∈ E almost surely:

x -x ϕ(n) ϕ(n) nV d (a 1 -ε) 1/d Thus ,sup x∈E x -x ϕ(n) → 0 a.s. Also, almost surely n x -x ϕ(n) d ϕ(n) V d (a 2 + ε) Thus, inf x∈E x -x ϕ(n) → ∞ a.s.
Lemma 4. Let µ, ν be two probability distributions associated with uniformly continuous probability density functions f µ and f ν . Assume that there exists constants a 1 > 0, a 2 > 0 such that for all x ∈ E, we have a 1 < f µ (x) a 2 and a 1 < f ν a 2 . Also, let D µ , D ν be datasets sampled from ν n , µ n . If µ is an estimator for ν, then

(i) for all x ∈ D µ , α n ϕ(n) (x) → n→∞ 1 supp(ν) (x) in proba. (ii) for all y ∈ D ν , β n ϕ(n) (y) → n→∞ 1 supp(µ) (x) in proba.
Proof. We will only show the result for (i), since a similar proof holds for (ii).

Thus, we want to show that

for all x ∈ D µ , α n ϕ(n) (x) → n→∞ 1 supp(ν) (x) a. s. First, let's assume that x / ∈ S ν . Biau & Devroye (2015, Lemma 2.2) have shown that lim n→∞ x (ϕ(n)) -x = inf{ x -y | y ∈ S ν } a.s.
As S ν is a closed set -e.g. [START_REF] Kallenberg | Foundations of modern probability[END_REF] -we have

lim n→∞ x -x (ϕ(n)) > 0 a.s. and for all y ∈ D ν , lim n→∞ y -y (ϕ(n)) = 0 a.s. Thus, lim n→∞ α n ϕ(n) (x) = 0 a.s..
Now, let's assume that x ∈ S ν . Using Definition 2, the precision of a given data point x can be rewritten as follows:

α n ϕ(n) (x) = 1 ⇐⇒ ∃y ∈ D ν , x ∈ B(y, y -y (ϕ(n)) )
Using notation from (2), we note

R min = min y∈ y -y (ϕ(n)) , R max = max y∈E y -y (ϕ(n)) .
It is clear that :

y∈Dν B(y, R min ) ⊆ S n ν ⊆ y∈Dν B(y, R max ), (3)
where S n ν = y∈Dν B(y, y -y (ϕ(n)) )). Besides, combining Lemma 3 with Devroye & Wise (1980, Theorem 1), we have that:

ν(S ν ∆ y∈Dν B(y, R min )) -→ n→0 0 in proba. ν(S ν ∆ y∈Dν B(y, R max )) -→ n→0 0 in proba.
where ∆ here refers to the symmetric difference. Thus, using (3), it is now clear that, µ(S ν ∆S n ν ) → 0 in probability. Finally, given x ∈ S µ , we have µ(x ∈ S n ν ) = ν(α n ϕ(n) (x) = 1) → 1 in probability.

We can now finish the proof for Theorem 1. Recall that ᾱ = µ S ν and similarly, β = ν S µ .

Proof. We have that

|α n ϕ(n) -ᾱ| = | 1 n xi∈Dµ α n ϕ(n) (x i ) - E 1 x∈Sν µ(dx)| Then, |α n ϕ(n) -ᾱ| = | 1 n xi∈Dµ (α n ϕ(n) (x i ) -1 xi∈Sν ) + 1 n xi∈Dµ 1 xi∈Sν - E 1 x∈Sν µ(dx) | = |E xi∼µn (α n ϕ(n) (x i ) -1 xi∈Sν ) (4) + E µn 1 Sν -E µ 1 Sν | (5)
where µ n is the empirical distribution of µ. As µ n converges weakly to µ almost surely (e.g. Dudley (2002, Theorem 11.4.1)) and since 1 x∈Sν is bounded, we can bound (5) as follows:

lim n→∞ E x∼µn 1 x∈supp(µ) -E x∼µ 1 x∈supp(µ) = 0 a. s.
Now, to bound (4), we use the fact that for any x ∈ D µ , the random variable α n ϕ(n) (x) converges to 1 x∈Sν in probability (Lemma 4) and that for all x ∈ D µ , both α n ϕ(n) (x) 1 and 1 x∈Sν 1. Consequently, using results from the weak law for triangular arrays, we have that

lim n→∞ 1 n xi∈Dµ (α n ϕ(n) (x i ) -1 xi∈Sν ) = 0 in proba.
Finally,

|α n ϕ(n) -ᾱ| → n→∞ 0 in proba.,
which proves the result. The same proof works for lim k→∞

β n k = β.

C. Proof of Theorem 2

This proof is based on the Gaussian isoperimetric inequality historically shown by [START_REF] Borell | The brunn-minkowski inequality in gauss space[END_REF][START_REF] Sudakov | Extremal properties of half-spaces for spherically invariant measures[END_REF].

Proof. Let µ be a distribution defined on E laying on two disconnected manifolds M 1 and M 2 such that µ

(M 1 ) = µ (M 2 ) = 1 2 and d(M 1 , M 2 ) = D. Note that for any subsets A ⊆ E and B ⊆ E, d(A, B) := inf (x,y)∈A×B x -y . Let G -1 θ (M 1 ) (respectively G -1 θ (M 2 ) be the subset in R d be the pre-images of M 1 (respectively M 2 ).

Consequently, we have for all

k ∈ [1, n] γ(G -1 θ (M 1 )) = µ θ (M 1 ) = γ(G -1 θ (M 2 )) ᾱ 2 We consider (G -1 θ (M 1 )) ε (respectively (G -1 θ (M 2 )) ε ) the ε enlargement of G -1 θ (M 1 ) (respectively G -1 θ (M 2 ) where ε = D 2L . We know that (G -1 θ (M 1 )) ε (G -1 θ (M 2 )) ε = ∅. Thus, we have that: γ (G -1 θ (M 1 )) ε + γ (G -1 θ (M 2 )) ε 1 Besides, by denoting Φ the function defined for any t ∈ R by Φ(t) = t -∞ exp(-t 2 /2) √ 2π
ds, we have [START_REF] Ledoux | Isoperimetry and gaussian analysis[END_REF])

γ (G -1 θ (M 1 )) ε + γ (G -1 θ (M 2 )) ε 2Φ Φ -1 ( α 2 ) + ε (using Theorem 1.3 from
α + 2ε √ 2π e -Φ -1 ( α 2 ) 2 /2 (since Φ -1 ( α 2 ) + ε < 0 and Φ convex on ] -∞, 0])
Thus, we have that

α + 2ε √ 2π e -Φ -1 ( α Thus, by noting α = sup{α ∈ [0, 1] | α + 2ε √ 2π e -Φ -1 ( α 2 ) 2 2 1},
we have our result.

For α 3/4. By noting α = 1 -x, we have

Φ -1 ( α 2 ) = √ 2πx 2 + O(x 3 )
And, e

-Φ -1 ( α 2 ) 2 2 = e -πx 2 4 + O(e -x 4 ) Thus, 1 -x + 2ε √ 2π e -πx 2 4 + O(e -x 4 ) 1 ⇐⇒ x 2ε √ 2π e -πx 2 4 + O(e -x 4 ) =⇒ x 2 π W ( 2 )
where W is the product log function. Thus, α 1 -

2 π W ( 2 ).
As an example, in the case where ε = 1, we have that W (1) ≈ 0.5671, x > 0.4525 and α < 0.5475.

D. Proof of Theorem 3 D.1. Equitable setting

This result is a consequence of Prop. 1 that we will assume true in this section.

We consider that the unknown true distribution µ lays on M disjoint manifolds of equal measure. As specified in Section 3, the latent distribution γ is a multivariate Gaussian defined on R d . For each k ∈ [1, M ], we consider in the latent space, the pre-images A k .

It is clear that A 1 , . . . , A M are pairwise disjoint Borel subsets of R d . We denote M , the number of classes covered by the estimator µ θ , such that for all i ∈ [1, M ], we have γ(A i ) > 0. We know that M M β > 1.

For each i ∈ [1, M ], we denote A ε i , the ε-enlargement of A i . For any pair (i, j) it is clear that A ε i A ε j = 0 where ε = D 2L (D being the minimum distance between two sub-manifolds and L being the Lipschitz constant of the generator).

As assumed, we know that A ε i , i ∈ [1, M ] partition the latent space in equal measure, consequently, we assume that

n i=1 γ(A ε i ) = 1 and γ(A 1 ) = . . . = γ(A M ) = 1/ M (6)
Thus, we have that

ᾱ = M i=1 γ(A ε i ) = 1 -γ(∆ -ε (A ε 1 , . . . , A ε M ))
Using Proposition 1, we have

γ(∆ -ε (A ε 1 , . . . , A ε n )) 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx Thus, ᾱ 1 + y 2 y 2 e -1 2 ε 2 e -εy
where

y = Φ -1 1 -max k∈[ M] γ(A ε k ) = Φ -1 ( M -1 M ) and Φ(t) = t -∞ exp(-t 2 /2) √ 2π
ds.

Knowing that M βM we have that

Φ -1 (1 - 1 M ) Φ -1 (1 - 1 βM )
We conclude by saying that the function x → 1+x 2

x 2 e -εx is decreasing for x > 0. Thus,

ᾱ 1 + y 2 y 2 e -1 2 ε 2 e -εy (7)
where

y = Φ -1 (1 -1 βM ) and Φ(t) = t -∞ exp(-t 2 /2) √ 2π
ds.

For the further analysis when K → ∞, please refer to subsection E, note using the result in ( 16), one obtains the desired upper-bound on ᾱ

ᾱ K→∞ 1 -e -1 2 ε 2 e -ε √ 2 log(K)

D.2. More general setting

As done previously, we denote M , the number of classes covered by the estimator µ θ , such that for all i ∈ [1, M ], we have γ(A i ) > 0. We still assume that M > 1. However, we now relax the previous assumption made in (6) and assume the milder assumption that there exists w 1 , . . . , w M ∈

[0, 1] M such that for all m ∈ [1, M ], γ(A ε m ) = w m , m w m 1 and max i∈[1,M ] w m = w max < 1. Consider, A = M i=1 A ε i and denote w c = γ(A ) 1 -ᾱ. Consequently, we have n i=1 γ(A ε i ) + γ(A ) = 1 γ(∆ -ε (A ε 1 , . . . , A ε M , A )) + M i=1 γ(A ε i ) = 1 -γ(A ) ᾱ = 1 -w -γ(∆ -ε (A ε 1 , . . . , A ε M , A ))
In this setting, it is clear that A 1 , . . . , A M , A is a a partition of R d under the measure γ. Using, result from Proposition 1, we have

γ(∆ -ε (A ε 1 , . . . , A ε M , A )) 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx
where x = Φ -1 1 -max(w , w max ) and

Φ(t) = t -∞ exp(-t 2 /2) √ 2π
ds.

Finally, we have that

ᾱ 1 + x 2 x 2 e -1 2 ε 2 e -εx -w (8)
In the case where γ(A ) = 0, we find a result similar to (7).

E. Lower-bounding boundaries of partitions in a Gaussian space

Notations and preliminaries Given ε ≥ 0 and a subset A of euclidean space

R d = (R d , •-• ), let A ε := {z ∈ R d | dist(z, A) ≤ ε} be its ε-enlargement, where dist(z, A) := inf z ∈A z -z 2 is the distance of the point z ∈ R d from A.
Let γ be the standard Gaussian distribution in R d and let A 1 , . . . , A K be K ≥ 2 pairwise disjoint Borel subsets of R d whose union has unit (i.e full) Gaussian measure K k=1 w k = 1, where w k := γ(A k ). Such a collection {A 1 , . . . , A K } will be called an (w 1 , . . . , w K )-partition of standard d-dimensional Gaussian space (R d , γ).

For each k ∈ [[K]], define the compliment A -k := ∪ k =k A k , and let ∂ -ε A k := {z ∈ A k | dist(z, A -k ) ≤
ε} be the inner ε-boundary of A k , i.e the points of A k which are within distance ε of some other A k . For every

(k, k ) ∈ [[K]] 2 with k = k, it is an easy exercise to show that ∂ -ε A k ∩ ∂ -ε A k = ∅ (9) ∂ -ε A k ∩ A -k = ∅ A ε -k = ∂ -ε A k ∪ A -k Now, let ∆ -ε (A 1 , . . . , A K ) := ∪ K k=1 ∂ -ε
A k be the union of all the inner ε-boundaries. This is ∆ -ε (A 1 , . . . , A K ) the set of points of ∪ K k=1 A k which are on the boundary between some two distinct A k and A k . We want to find a lower bound in the measure γ(∆ -ε (A 1 , . . . , A K )). Proposition 1. Given K ≥ 4 and w 1 , . . . , w K ∈ (0, 1/4] such that K k=1 w k = 1, we have the bound:

inf A1,...,A K γ(∆ -ε (A 1 , . . . , A K )) ≥ 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx
where the infinimum is taken over all (w 1 , . . . , w k )partitions of standard Gaussian space (R d , γ), and

x := Φ -1 1 -max k∈[[M ]] w k .
Proof. By (9), we have the formula

γ(∆ -ε (A 1 , . . . , A K )) = K k=1 γ(∂ -ε A k ) (10) = K k=1 γ(A ε -k ) -γ(A -k ). (11) Let w -k := γ(A -k ) = 1 -w k , and assume w -k ≥ 3/4, i.e w k ≤ 1/4, for all k ∈ [[K]].
For example, this condition holds in the equitable scenario where w k = 1/K for all k.

Now, by standard Gaussian Isoperimetric Inequality (see [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF] for example), one has

γ(A ε -k ) ≥ Φ(Φ -1 (γ(A -k ) + ε) = Φ(Φ -1 (1 -w k ) + ε). ( 12
)
Using the bound x 1+x 2 ϕ(x) < 1 -Φ(x) < 1 x ϕ(x) ∀x > 0 where ϕ is the density of the standard Gaussian law. We can further find that

Φ(Φ -1 (1 -w k ) + ε) ≥ 1 -w k 1 + Φ -1 (1 -w k ) 2 Φ -1 (1 -w k ) 2 × e -1 2 ε 2 e -εΦ -1 (1-w k ) ≥ 1 -w k 1 + x 2 x 2 e -1 2 ε 2 e -εx > 0 (13)
(since the function x → 1 + x 2

x 2 e -εx is decreasing for x > 0)

where 10), (12), and (13) yields the following

x := min k∈[[K]] Φ -1 (1 -w k ) = Φ -1 1 -max k∈[[K]] w k ≥ Φ -1 (3/4) > 0.67. Combin- ing (
γ(∆ -ε (A 1 , . . . , A K )) ≥ K k=1 1 -w k 1 + x 2 x 2 e -1 2 ε 2 e -εx -(1 -w k )) = K k=1 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx w k = 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx ,

Asymptotic analysis

In the limit, it is easy to check that in the case where max k∈[[K]] w k -→ 0, we have that x -→ ∞.

In this setting, we thus have 1+x 2 x 2 -→ 1 and can now derive the following bound:

inf A1,...,A K γ(∆ -ε (A 1 , . . . , A K )) max k∈[[K]] w k →0 -→ 1-e -1 2 ε 2 e -εx .
Equitable scenario In the equitable scenario where w k = 1/K for all k, we have inf

A1,...,A K γ(∆ -ε (A 1 , . . . , A K )) 1 - 1 + x 2 x 2 e -1 2 ε 2 e -εx
where

x = Φ -1 (1 -1/K) (14)
When K ≥ 8 we additionally have

Φ -1 (1 -1/K) 2 log K (q(K) 2 -1) √ 2πq(K) 3 (15)
where q(K) = 2 log( √ 2πK).

Consequently, we have when K → ∞, the following behavior:

γ(∆ -ε (A 1 , . . . , A K )) K→∞ -→ 1 -e -1 2 ε 2 e -ε √ 2 log(K) (16)
Proof of the inequality (15). Set p := 1/K. First, for any x > 0, we have the following upper:

∞ x e -y 2 /2 dy = ∞ x y y e -y 2 /2 dy ≤ 1 x ∞ x ye -y 2 /2 dy = e -x 2 /2 x .
For a lower bound: and combining these gives

∞ x e -y 2 /2 dy ≥ 1 x - 1 x 3 e -x 2 /2 . Thus 1 √ 2π 1 x - 1 x 3 e -x 2 /2 ≤ 1 -Φ(x) ≤ 1 √ 2π 1 x e -x 2 /2 , from where
1 √ 2π 1 Φ -1 (1 -p) - 1 Φ -1 (1 -p) 3 e -Φ -1 (1-p) 2 /2 (17) ≤ p ≤ 1 √ 2π 1 Φ -1 (1 -p) e -Φ -1 (1-p) 2 /2 (18)
Using ( 18), when Φ -1 (1 -p) ≥ 1 (that is p 0.15 or equivalently K ≥ 8), we have the following upper bound Φ -1 (1 -p) q(p) where q(p) := 2 log( √ 2π/p). Then, injecting q(p) in ( 17):

1 √ 2π 1 q(p) - 1 q(p) 3 e -Φ (1-p) 2 /2 ≤ p.
Now when q(p) ≥ 1 you have:

e -Φ -1 (1-p) 2 /2 ≤ √ 2πpq(p) 3 q(p) 2 -1 and Φ -1 (1 -p) ≥ 2 log q(p) 2 -1 √ 2πpq(p) 3 . ( 19
)
There is one additional requirement on p which is simply that the argument of the log should be ≥ 1 i.e. q(p) 2 -1 ≥ √ 2πpq(p) 3 , which is true as soon as K ≥ 8.

H. Saturation of a MLP neural network

In Section 4.2, we claim that the generator reduces the sampling of off-manifold data points up to a saturation point.

Figure 7 below provides a visualization of this phenomenon. In this synthetic case, we learn a 9-component mixture of Gaussians using simple GANs architecture (both the generator and the discriminator are MLP with two hidden layers). The minimal distance between two modes is set to 9. We clearly see in Figure 7d that the precision saturates around 80%.

I. More results and visualizations on MNIST/F-MNIST/CIFAR10

Additionally to those in Section 4.3, we provide in Figure 9 and Table 2 supplementary results for MNIST, F-MNIST and CIFAR-10 datasets. In Figure 11

  (a) Heatmap of the generator's Jacobian norm. White circles: quantiles of the latent distribution N (0, I). (b) Green: target distribution. Coloured dots: generated samples colored w.r.t. the Jacobian Norm using same heatmap than (a).

Figure 1 .

 1 Figure 1. Learning disconnected manifolds leads to the apparition of an area with high gradients and data sampled in between modes.

  (a) WGAN 4 classes: visualisation of JG(z) F . (b) WGAN 9 classes: visualisation of JG(z) F . (c) WGAN 25 classes: visualisation of JG(z) F . (d) Precision w.r.t. D (mode distance) and M (classes).

Figure 2 .

 2 Figure 2. Illustration of Theorem 3. If the number of classes M → ∞ or the distance D → ∞, then the precision ᾱ → 0. We provide in appendix heatmaps for more values of M .

  Figure 2 clearly corroborates (1) as we can easily get the maximum precision close to 0 (M = 25, D = 27).

  For a pair of images (a, b), we define the distance d(a, b) as d(a, b) = φ(a) -φ(b) 2 where (a) WGAN -2500 samples (b) WGAN 90% JBT. (c) WGAN 70% JBT. (d) 97% confidence intervals .

Figure 3 .

 3 Figure 3. Mixture of 9 Gaussians in green, generated points in blue. Our truncation method (JBT) removes least precise data points as marginal precision plummets.

Figure 4 .

 4 Figure4. For high levels of kept samples, the marginal precision plummets of newly added samples, underlining the efficiency of our truncation method (JBT). Reported confidence intervals are 97% confidence intervals. On the second row, generated samples ordered by their JFN (left to right, top to bottom). In the last row, the data points generated are blurrier and outside the true manifold.

Figure 5 .

 5 Figure 5. On the first row, per-class precision-recall curves comparing Brock et al. (2019)'s truncation trick and our truncation method (JBT), on three ImageNet classes generated by BigGAN. We show better results on complex and disconnected classes (e.g. bubble). Reported confidence intervals are 97% confidence intervals. On the second row, generated samples ordered by their JFN (left to right, top to bottom). We observe a concentration of off-manifold samples for images on the bottom row, confirming the soundness of JBT.

  -y 2 /2 dy ≤ e -x 2 /2x 3

  (a) Data points sampled after 5,000 steps of training. (b) Data points sampled after 50,000 steps of training. (c) Data points sampled after 100,000 steps of training. (d) Evolution of the precision ᾱ during training.

Figure 7 .

 7 Figure 7. Learning 9 disconnected manifolds with a standard GANs architecture.

  (a) MNIST: examples of data points selected by our JBT with a truncation ratio of 90% (we thus removed the 10% highest gradients). (b) MNIST: examples of data points removed by our JBT with a truncation ratio of 90% (these are the 10% highest gradients data points). (c) F-MNIST: examples of data points selected by our JBT with a truncation ratio of 90% (we thus removed the 10% highest gradients).. (d) F-MNIST: examples of data points removed by our JBT with a truncation ratio of 90% (these are the 10% highest gradients data points).

Figure 8 .

 8 Figure 8. Visualization of our truncation method on CIFAR10.

Figure 9 .

 9 Figure 9. Visualization of our truncation method (JBT) on three real-world datasets: MNIST, F-MNIST and CIFAR-10.

Figure 10 .

 10 Figure10. For high levels of kept samples, the marginal precision plummets of newly added samples, underlining the efficiency of our truncation method (JBT). Reported confidence intervals are 97% confidence intervals. On the second row, generated samples ordered by their JFN (left to right, top to bottom). In the last row, the data points generated are blurrier and outside the true manifold.

  , we show images from the Bubble class of Im-ageNet. It supports our claim of manifold disconectedness, even within a class, and outlines the importance of studying the learning of disconnected manifolds in generative models. Then, in Figure12, we give more exemples from BigGAN 128x128 class-conditionned generator. We plot in the same format than in 4.4. Specifically, for different classes, we plot 128 images ranked by JFN. Here again, we see a concentration of off-manifold samples on the last row, proving the efficiency of our method. Example of classes responding particularly well to our ranking are House Finch (c), Monnarch Butterfly (i) or Wood rabbit (m). For each class, we also show an histogram of JFN based on 1024 samples. It shows that the JFN is a good indicator of the complexity of the class. For example, classes such as Cornet (q) or Football are very diverse and disconnected, resulting in high JFNs.

Figure 11 .

 11 Figure 11. Images from the Bubble class of ImageNet showing that the class is complex and slightly multimodal.

  'Peacock' class histogram.

Figure 12 .

 12 Figure 12. For several classes with BigGAN model.

Table 1 .

 1 JBT x% means we keep the x% samples with lowest Jacobian norm. Our truncation method (JBT) matches overparameterization techniques. ± is 97% confidence interval.

	MNIST	Prec.	Rec.	FID
	WGAN	91.2±0.3 93.7±0.5	24.3±0.3
	WGAN JBT 90% 92.5±0.5	92.9±0.3	26.9±0.5
	WGAN JBT 80% 93.3±0.3 91.8±0.4	33.1±0.3
	W-Deligan	89.0±0.6 93.6±0.3	31.7±0.5
	DMLGAN	93.4±0.2 92.3±0.2	16.8±0.4
	F-MNIST
	WGAN	86.3±0.4 88.2±0.2 259.7±3.5
	WGAN JBT 90% 88.6±0.6	86.6±0.5 257.4±3.0
	WGAN JBT 80% 89.8±0.4 84.9±0.5	396.2±6.4
	W-Deligan	88.5±0.3	85.3±0.6	310.9±3.1
	DMLGAN	87.4±0.3 88.1±0.4 253.0±2.8

propose DeliGAN, a reparametrization trick to transform the unimodal Gaussian latent distribution into a mixture. The different mixture components are later learnt by gradient descent. For fairness, the re-parametrization trick is

Table 2 .

 2 WGAN 90% lowest JFN 88.6 ± 0.6 86.6 ± 0.5 87.6 ± 0.5 138.7 ± 0.9 257.4 ± 3.0 61.3 ± 0.6 WGAN 80% lowest JFN 89.8 ± 0.4 84.9 ± 0.5 87.3 ± 0.4 146.3 ± 1.1 ± 0.3 88.1 ± 0.4 87.7 ± 0.4 141.9 ± 1.2 253.0 ± 2.8 60.9 ± 0.4 CIFAR10 WGAN 74.3 ± 0.5 70.3 ± 0.4 72.3 ± 0.5 334.7 ± 3.5 634.8 ± 4.6 151.2 ± 0.2 WGAN 90% lowest JFN 76.0 ± 0.7 69.4 ± 0.5 72.5 ± 0.6 318.1 ± 3.7 631.3 ± 4.5 150.7 ± 0.2 WGAN 80% lowest JFN 76.9 ± 0.5 68.6 ± 0.5 72.5 ± 0.5 323.5 ± 4.0 725.0 ± 3.5 150.1 ± 0.3 Scores on MNIST and Fashion-MNIST. JFN stands for Jacobian Frobenius norm. ± is 97% confidence interval.

	MNIST	Prec.	Rec.	F1	Haus.	FID	EMD
	WGAN	91.2 ± 0.3 93.7 ± 0.5 92.4 ± 0.4	49.7 ± 0.2	24.3 ± 0.3	21.5 ± 0.1
	WGAN 90% lowest JFN 92.5 ± 0.5	92.9 ± 0.3 92.7 ± 0.4 48.1 ± 0.2	26.9 ± 0.5	21.3 ± 0.2
	WGAN 80% lowest JFN 93.3 ± 0.3 91.8 ± 0.4 92.6 ± 0.4	50.6 ± 0.4	33.1 ± 0.3	21.4 ± 0.4
	W-Deligan	89.0 ± 0.6 93.6 ± 0.3 91.2 ± 0.5	50.7 ± 0.3	31.7 ± 0.5	22.4 ± 0.1
	DMLGAN	93.4 ± 0.2 92.3 ± 0.2 92.8 ± 0.2 48.2 ± 0.3	16.8 ± 0.4	20.7 ± 0.1
	Fashion-MNIST
	WGAN	86.3 ± 0.4 88.2 ± 0.2 87.2 ± 0.3 140.6 ± 0.7	259.7 ± 3.5	61.9 ± 0.3
						396.2 ± 6.4	63.3 ± 0.7
	W-Deligan	88.5 ± 0.3	85.3 ± 0.6	86.9 ± 0.4	141.7 ± 1.1	310.9 ± 3.1	60.9 ± 0.4
	DMLGAN 87.4 W-Deligan 71.5 ± 0.7 69.8 ± 0.7 70.6 ± 0.7	328.7 ± 2.1	727.8 ± 3.9	154.0 ± 0.3
	DMLGAN	74.1 ± 0.5	65.7 ± 0.6	69.7 ± 0.6	328.6 ± 2.7	967.2 ± 4.1	152.0 ± 0.4

) 2 /2

G. Definition of the different metrics used

In the sequel, we present the different metrics used in Section 4 of the paper to assess performances of GANs. We have:

• Improved Precision/Recall (PR) metric [START_REF] Kynkäänniemi | Improved precision and recall metric for assessing generative models[END_REF]: it has been presented in Definition 2. Intuitively, Based on a k-NN estimation of the manifold of real (resp. generated) data, it assesses whether (resp. real) points belong in the real (resp. generated) data manifold or not. The proportion of generated (resp. real) points that are in the real (resp. generated) data manifold is the precision (resp. recall). • the Frechet Inception distance: first proposed by [START_REF] Dowson | The fréchet distance between multivariate normal distributions[END_REF], the Frechet distance was applied in the setting of GANs by [START_REF] Heusel | Gans trained by a two time-scale update rule converge to a local nash equilibrium[END_REF]. This distance between mutlivariate Gaussians compares statistic of generated samples to real samples as follows

where X = N (ν , Σ ) and X θ = N (ν θ , Σ θ ) are the activations of a pre-softmax layer. However, when dealing with disconnected manifolds, we argue that this distance is not well suited as it approximates the distributions with unimodal one, thus loosing many information.

The choice of such metrics is motivated by the fact that metrics measuring the performances of GANs should not rely on relative densities but should rather be point sets based metrics. For DeliGan, we use the same architecture and simply add 50 Gaussians for the reparametrization trick. For DMLGAN, we re-use the architecture of the authors.

K. Network Architecture and Hyperparameters


Jacques Luisetti

Jean-Luc Gaignard

Michel Ridé

come


Rubrique Carnet de terrain 'Regional' scale Local scale Sub-local scale Johannesburg City

The researcher as the ball in a political game Claire Benit-Gbaffou Maître de conférences à l"Ecole d"Architecture et d"Urbanisme de l"Université de Wits à Johannesburg ; chercheur associée au laboratoire Gecko (Paris Ouest Nanterre La Défense) ; coordonne, avec le Professeur Alan Mabin (université de Wits), un programme CORUS sur « La voix des pauvres dans la gouvernance urbaine : mobilisation, participation et politique dans les grandes villes sud-africaines » A former version of this text was presented to the CORUS seminar : "The voice of the poor in uban governance -participation, mobilization and politics in South African cities", Cape Town, 23-25 November 2009 Elements of context -This research, undertaken by PLANACT (an NGO) and for which I am playing a role as research adviser, is about the place of residents' participation in a hostel renovation project i . The hostel ii is located on former mining ground, close to the metropolitan fresh products market. It is not far from the city center in absolute terms (about 10 kilometers) and well connected to it through taxi routes: but in a no man's land made up of industrial zones, mine dumps, and toxic waste. It is also a political enclavean ANC stronghold in a DA iii ward, which mostly comprises (besides the hostel) former white working class suburbs. The hostel renovation is conducted by Joshco (Johannesburg Social Housing Company, an entity that is funded by the municipality and is accountable to it but has its own management structure), who also manages the rental units. The project is about converting a former male hostel (predominantly occupied by Xhosa residents, from the Eastern Cape) into family units, inviting the wife and children to join their long-gone husband. It is perceived by most residents as a radical change that has its own challenges (in particular when the migrant husband has established a relationship with another women; but even more generally because the coming of women challenges the former masculine environment and requires some reshuffling of traditional gender roles). In the process of conversion and renovation of the hostel, Joshco has been mainly interacting with the old Tenants Committee, composed of four men and often criticized by other stakeholders (including Joshco itself), for not being representative of all residents. Two other local organizations are powerful locally: the ANC and SANCO structures (partners in what is called the 'Alliance Forum') iv . They are said to have a wider audience, and are extremely critical of (and sometimes violently oppositional to) Joshco's project. It took a long time for us to identify who the leaders were and to organize a meeting, all the more that we were introduced in the hostel by Joshco's caretaker, who was reluctant to put us in touch with people he perceived as 'trouble makers', and was also very wary that the research process could open conflict and even violence in City Deep Hostel, especially in electoral times v . I had subsequently issued a poster and flyers in English and Xhosa to tell residents about the research and inform them that its purpose was to talk with all stakeholders and hear all voices, from an outsider's, independent perspective. After several months of fieldwork in the area, and eventually individual interviews with the local ANC representative, and the SANCO chair, I asked the former if I could attend an Alliance Forum executive committee meeting vi (since there was no public meeting in the pipeline) and he invited me. During the whole meeting I am the ball in a ping-pong game, whose players I can only partly identify: in turn, the political battle is between SANCO and the ANC (the two members of the Alliance); between the Alliance and Joshco (not represented at the meeting); and between the Alliance and the Mayor (not represented at the meeting). My overall first impression is of the extreme political skills displayed by the main players, who direct the discussion at leisure, and push me where they want to push me (not a very agreeable, but instructive, position for me). Secondly, they clearly are playing and enjoying the game (at my expense), although some degree of pity (especially since I am seven months pregnant) shows up at the end. But they are clearly interested in the research results as they see its potential political implications, and not willing to close the doorthis has been a game and a rite of passage. Thirdly, it is not an homogeneous group, with SANCO and ANC chairs being clearly pushed by power dynamics and enjoying the game; ANC voting district chair and Alliance chair (chairing the meeting) mostly remaining silent but trying to bring things forward and find pragmatic solutions, supporting me although in a very light and subtle way.

Fieldwork notes

KEY:

Metropolitan scale

In italicsadministrative positions or structures.

In bold, leaders or structures mentioned in the text. Arrow meaning: "reports to, is accountable towards" (so the direction of the arrow is indicating power)

NB: Not all ANC branches have voting district chairs. It is the case in our study because the hostel is an ANC stronghold in a broader DA wardthe ANC branch chair not being a hostel resident, it was important to have an ANC representative in the hostel (hence the voting district chair). NB2: This structure is made more complex by the fact that these various positions (in local government and in the ANC) are sometimes held by the same persons. For instance, Amos Masondo, the Mayor or Johannesburg, is also the ANC regional Chairperson. But he is weakened in the ANC regional structure by a strong opposition in the regional executive committee.

Figure 2. Structure of the Alliance executive meeting attended

I am attending the meeting with Lerato, one of my Planning students that I have asked to join to help me with translation issues, as my research partner from PLANACT, Malachia, could not be present. We are waiting for members to join the meeting: SANCO Chair John and Alliance Forum Chair Sinethemba viii (they are crucial to the point and without them coming, other speak of cancelling the meeting). In the meantime, informal discussion occurs mainly between the ANC branch Chair (Neil) and the ANC voting district chair (William whom I interviewed previously and who invited me to the meeting). They complain (in Zulu) about the Mayor, Amos Masondo, who does not care about their requests for meetings, and (halfjokingly) discuss of just organizing a toyi-toyi ix and hand him over a memorandum. They joke about Strike (Ralegkoma, the Member of the Mayoral Committee (MMC) for Housing in Council x ), the fact that he is double-faced, when is he going to walk to COPE xi , no, he probably won"t…

First battle -SANCO and ANC

Enters SANCO chair (John), his secretary Celia (that Malachia, my fellow researcher from PLANACT, and I have met and interviewed a few days ago), as well as Alliance Forum Chair, Sinethemba, who is about to start the meeting when he is interrupted by SANCO Chair. John, who is a "strong man" with a deep voice and large shoulders, objects to our presence here, saying he is very surprised to see us here, since he has not been consulted about it as a member of the Alliance Forum executive committee ("exco"). Moreover, he states that he has met with me in the past days, that I have requested to attend the exco meeting and he has told us he would get back to us, which he has not done yet. He therefore suggested the meeting to be cancelled. Doing otherwise would be like "pointing a gun at his head". ANC Chair, Neil, offers a counter proposition: that the Forum allows us to present why we are here and the research project, and then that we leave the meeting. He is seconded by John"s right hand, Celia, who I think sympathize with my (pregnant) condition. I also make a contribution, clarifying the fact that I approached William to be granted permission to attend this meeting; that I indeed met with John and requested permission from him, but to attend a SANCO exco meeting, which I thought was different. There is therefore no intention from my side to "point a gun at anyone"s head". At that stage, John reacts: "no, it is not you I was talking about", and I realize this is not about me. However, Sinethemba uses my statement to try and propose a way forward, as I "clearly could not know that SANCO and the Alliance work so closely together" and we should find a way forward to solve the issue now. It helps, to play the stupid little white girl… After a heated discussion, Sinethemba chairing the meeting makes a decision: since Neil"s proposal has been seconded, let us allow Dr Claire to present, ask her questions and then let her go. The agenda is adopted finally.

Second roundbattle between the Alliance and Joshco

The ANC chair (Neil) is however not an ally or support for me: he has a very specific agenda when allowing me to present the project. After I have traced the contours of PLANACT (a non profit, non political, non-governmental organization), of the project (voices of community into the renovation of the hostel), of the process (I state that I will be interviewing each stakeholder to try and understand each viewpoint; that I am happy to check with interviewees if they are satisfied with the way we have captured their viewpoint; that I am willing to present the draft report for comments), Neil starts to throw questions at me that at first are very unclear.

He asks about who "instructed" us, who "mandated" us to do this research; and what is our objective. I try to further explain that nobody instructed or mandated us; to explain the nature of PLANACT activities (using their motto, "making cities work for people"). He says I am sidelining the question and repeats it again and again, more and more aggressively, till SANCO"s Chair comes to my rescue by going more directly to the point -How did you get here? Who told you about City Deep? I then make a blunder, naively (well, also very much under pressure…) saying that we selected several case studies including City Deep because the City of Johannesburg indicated it as a "successful project" (and also, but they don"t hear me because obviously this is not relevant to them, that we wanted to do this research in a hostel environment because we assumed residents would be strongly organized). Immediately interest jumps, WHO in the city? Fortunately I am able to state that it is not the Department of Housing (with which they are at present in conflict -I am quite aware of that!), but the Department of Corporate Governancebut I become more aware that every word from this project is weighed and can be used as a political weapon in other battles. And it is not over: the next question is then: how did you get in the hostel, who was your contactthey obviously knew it was Joshco xii . When I formulated this, both ANC and SANCO chairs played outrage, "Joshco is not running this area", "WE are running this area", "how could they give you permission to enter this area without consulting us?", "this is a blatant disrespect for our structures". At that point I was more distant, both quite ironic and interested. This is a DA ward; ANC chair had asked me previously: "why do you want to study community participation? You should be aware of our legislation on local government that plans for participation xiii " -I had replied we needed to see it work in practice, from the ground, at a project level. Now, conveniently, the ward system"s legitimacy is forgotten and it is "us" (the ANC/ the Alliance) who run this area. ANC chair suggests that we "burn all the material we gathered" and "start afresh, following the correct protocol". I argue that I understand their position, that I am aware of a communication problem with Joshco, but that it seems rather unfair to ask me to solve such a problem, as I am an outsider and obviously do not have the capacity to do so. All of a sudden, they shift -"no no, it is not about Joshco, it is about consulting our political hierarchy". And it is unclear during the rest of the conversation what they are talking about -the right to attend their (executive committee) meeting? Or the right to enter the hostelplaying on the image of the "no-go" area they have gained especially in the 1990s during political violence crystallized around hostels xiv ? Is it my own perception, my own fears, or is violence really and effectively a usual way of solving conflict in the hostel xv ? Are they aware of these fears and playing on it? I tend to think they are.

Third round -Battle between the Alliance and the Mayor

The ANC chair suggests we approach the zonal and the regional chairpersons of the ANC (and the Regional Chair of SANCO) to ask for permission to conduct a research in City Deep Hostel (at a point he also mentions the Provincial Chair, and I bite my tongue not to ask, if he could also give me President Zuma"sthe National Chair-phone number?).

He gives me a lecture about the "practices of the apartheid time" (reference to apartheid is constant in the hostel environment, and extremely ambiguous, although not this time xvi ), where "white people" used to come uninvited, ask questions, do their report which would not reflect the people"s views but what people thought they were expecting. Coming to City Deep Hostel without following the right protocol, he argues, is doing like them. "We all need to learn democracy, and this forum is a good place to start". Sinethemba jokingly adds (to lighten the atmosphere, which is not tense but the accusation of apartheid practice is never light, no matter how instrumental it is), that one does not need to pay the R15.000 fee to go to Wits University (where I teach), we have free lessons here (and I follow his path, saying, "shh, shh, in front of my student! You want to deprive me of my job?" and everybody laughs). SANCO Chair reiterates ANC Chair comment and says we should ask permission from his Regional Chair. ANC Voting District Chair (who has been giving me looks of sympathy and light smiles throughout the meeting, but without saying much) says, in order to be pragmatic, that I should be given the contact numbers of the relevant people. I then realize that it is, for sure, about teaching me a lesson (maybe because of my title, Dr.in an interview I heard that some hostel dwellers were deeply resentful about "educated people who think they are better than us", although I don"t think I have been boasting too much about this -stressing rather my difficulties with Zulu…). But it was also about making us contact the Mayor (which is also the ANC Regional Chair) about City Deep Hostel, as a way to point out that there are issues there and that they are under academic, if not political, scrutiny.

At that stage, I remain very quiet. Partly out of the fear of making other blunders (knowing everything I would say would be toyed with; even humor might trigger wrath, sincere or affected). Sinethemba thanks us for our presence, our presentation and replies to questions, and apologizes for the way in which it has been received. The ANC Chair says that he hopes I understand there is nothing personal here; and that I should not go out in my state (i.e. pregnant) that late at night. SANCO Chair adds, "Claire, don"t stress too much about this, hey?". Which I understand as them saying, "OK, we have had a nice game, we"ve had fun, but this was a game"; or, maybe, "you past the test, don"t worry, it will go forward".

Indeed, intertwined in this series of battles, another member (unidentified: came late, entered with John and sat next to him: SANCO executive committee member?) raises the issue of the findings of the research. Was it finished, could they get a presentation of our findings, before the final report was written, etc.? I replied that obviously it was not finished and although we had gathered some information already, it remained superficial and that was precisely the reason why we wanted to attend their meetings. But of course, it was part of the process I had presented, we would be very happy to let them check our quotations from them (for them to complement or correct), and to present them a draft version of the report. There were questions about the time frame, and I replied cautiously that obviously PLANACT had its own time constraints for the research; that I had my own (natural) time constraints (maternity leave from early July), and that we were hoping, if possible, to have done the bulk of the interviews by the end of the month; that we would then write the report and probably be able to present it end September/ October. Sinethemba immediately supported me, saying that I had very gently made a request and that the research could continue since there was limited time left. This unidentified member stressed the fact he liked that I had committed to present the report to the Alliance-and people started referring to it as a "White Paper" xvii (saying that, like a White paper, you cannot write recommendations without consulting the people). The length of that discussion, as well as this nickname, made me understand better that everyone expected to be able to use the report politically, in their battles with Joshco and with the City, given the fact it was likely that it would be critical of the participatory process. It both reassured me (about the fact they wanted this research to go forward), and frightened me (about the difficulty we would have to keep the report balanced; about its future political manipulation in completely unknown directionsnot necessarily to empower residents and ease communication with local authorities; but also in more complex and possibly petty political conflicts). This however is a challenge for the next step of the research… Post meeting personal reaction I left the meeting deeply puzzled and annoyed, very frustrated, slightly humiliated (even more after their final words of sympathy which I took first mainly as an expression of pity and some degree of machismo). It is not pleasant to be "the ball" in a game, one feels powerless and even more: dispossessed of one"s individuality, ability to talk, as each word you utter can be, and will be, turned against you. Not knowing for instance when humor is welcome to defuse situation; not certain of what you should or should not compromise on. For instance it was evident that requiring me to ask for "permission" from the ANC to enter City Deep Hostel was illegitimate (and even if I had a permission to ask to "enter an area", it is a DA ward after all; ANC does not have a mandate in this area) and a way for the ANC to try and build its legitimacy. I was tempted to refer to the apartheid dompass xviii , especially when accused of reproducing apartheid practices (but I am glad I refrained from it!). In fact it was never clear if permission was requested in order to enter City Deep Hostel, or to attend the Alliance Exco meetings -have the Alliance"s endorsement of the processwhich was more understandable. What helped of course was my relative understanding of the process and the political stakes, after months of fieldwork. I understood for instance the role the ANC sees itself playing in local societies, as the main platform for people"s concerns and the legitimate local leader and authority (as opposed to local government structures xix ) . Crafting a letter to the ANC Chair and SANCO Chair, requesting their help in the task they had given me (in fact asking them to contact their own hierarchy), was a necessary step if one wants to avoid indefinite delays (I doubt the Mayor would respond a demand from PLANACT), and gave me back some sense of agency.

As I reflect later, more broadly, on these processes, I realize how political sense is a skilland how I lack such a skill: conducting a meeting, creating tension and playing anger and later on, defusing it and slowing the pace, in alternating tension and relaxation necessary to keep the 'victim' pressurized but also confident enough to continue talking (and making blunders); framing questions in indirect ways that hides their real purpose; identifying possible political weapons and looking deep for evidence; etc. It is like playing chess and constantly anticipating the other's movement, to bring him (her) where you want to bring him (her). What was puzzling to me was the fact that in spite of my relative understanding of the local political conflicts and stakes, even of individual positions of participants (and my intuitions about their rivalries and contrasted personalities and political styles), I was unable to counteract the political play I was engaged in, to foresee where each participant was aiming at and to be a player instead of being 'the ball'. Of course, I was coming into a game that the participants had spent years, if not decades, playing together... My academic understanding gave me the power to realize what was going on, but my only way of preventing it to go further was eventually to remain as silent as possible (a challenge when you are grilled and questioned, or when you are asking for a favorhere, attending the meeting). There, were displayed different types of knowledge, or rather different ways of using knowledge as an instrument of power (and of course academic knowledge is also power, as the last part of the discussion -about the findings and the 'White Paper'expresses clearly).

Would it even have been possible for me to 'know better'? One always tends to blame oneself for lack of foresight or for one's blunders. On the other hand, obviously any new player in a game that has taken years, if not decades, to build and establish, is at a disadvantageno research process (at least that has not been built over several years as well) can replace this time and depth of inter-connectednessso maybe the best response is just to observe and learn. But beyond this time / depth gap, I definitely had a strong sense that there was something generic, not locally-specific, in this game. In particular I had had exactly the same impression (being a ball in political game) when I interacted, this time as an activist, with local leaders in Alexandra township -also an 'enclave', a dense, free-hold black township in the middle of Sandton (formerly white privileged suburb) where innumerable politicians and activists (many of which are now in prominent political positions nationally) have undergone their political education. This was a similar kind of 'closed circle', where a high degree of political maneuvering and astuteness might be the only resource attainable to local residents, used both against outsiders (apartheid state agents) and insiders (rival leaders). Obviously I am not entirely naïve and have learnt to play with different belongings, registers, languages. Here, the ability to speak a little bit of Zulu (however limited) is important, if not to 'break' barriers, at least to unsettle too easy categories, and therefore bring conversation towards a less formal arena. Sometimes, it makes sense to play with these categories ('the stupid little white girl') at least implicitlyalthough the play around the vocabulary of apartheid is always heavy and one never is sure of what it will unleash; all players are generally aware it is a 'card' in the game, but in multi-racial settings it is almost impossible to counter it (impossible to say: 'no, I am not a racist!'). Is it therefore only a matter of insufficient communication skillsand here my insufficient ability to hide information or to disclose it as minimally as possible? Is there such a thing as 'communication skills'? Even if it is a field of expertise as such, I tend to understand it rather as quite specific to this form of interaction (quite different, for instance, from communication skills required to teach, or to market a product, etc.). Aren't actually these skills (communication and power games in a political setting) actually one of the objects of this research?

This experience also makes me reflect on the problematic relationships between 'low' (or petty) politics and 'high' politics. I was, in the initial formulation of the research question, and to some extent still am, looking for 'high' politicshow the Alliance is able (or not) to claim a voice in the renovation and hostel management process in the name of residents. And it is, to some extent: its action has led to a decrease in electricity tariffs charged to residents; to the suspension of the eviction of the wife of a legal tenant, after he passed away; etc. xx 'Low' politics, these never-ending power games even inside the Alliance, are often perceived as detrimental to 'high' politics. They are generally theorized as disconnected from it -I have at least not encountered yet theoretical frameworks that attempt to capture both in their complex articulations xxi . In City Deep Hostel (and elsewhere) it also has been the case: many initiatives taken by some Alliance members, that would have improved the residents' lives, were blocked by others out of political rivalry. But it is not enough to see low politics as opposed and detrimental to high politics. First the two are intrinsically connectedwhere there is a potential to change things, when there is agency and power (whatever it is), there is competition for it, competition for leadership and recognition. It is difficult to measure how important the potential for change or for access to resources needs to be to trigger power competition: it depends so much of local and personal contextsfor instance the existence or not of other platforms, for individuals or groups, of achievement and sense of self-importance.

Secondly, could it be that this very intense political educationleading to these quite specific skills-is necessary to accomplish political victories at other levels of political engagement? I am not sure yet. What I am sure of is the necessity for better understanding party politics and power dynamics at a quite micro-level if I want to understand anything about the way in which residents, in their maybe limited ways, can bring about some change in their living environments.

i The full research report and the chapter on City Deep Hostel (Bénit-Gbaffou and Mathoho 2010) are available on PLANACT"s website, http://www.planact.org.za.

ii Hostels have been providing accommodation for black residents who were conceived as temporary, migrant workers in pre 1994 South African cities [START_REF] Pirie | Hostels for African migrants in Greater Johannesburg[END_REF]. Some of them were managed by private companies (especially mining companies); some by municipalities. Traditional chiefs were often hired as hostel managers, in a form of indirect rule that efficiently kept internal social control (Minaar 1993). Single-sex hostels (male hostels mostly, sometimes female), they were meant to prevent full urbanization of black migrants who were in a way permanently temporary, and whose roots in their "homeland" was maintained through the division of their family and their relative physical isolation from urban black townships (Ramphele 1993). Hostels crystallized fears and violence in urban areas in the 1990s, around complex ethno-political divisions opposing hostel dwellers to township residents, and instrumentalised by the apartheid regime [START_REF] Chipkin I | Nationalism As Such: Violence during South Africa"s Political Transition[END_REF][START_REF] Elder G | Malevolent Traditions: Hostel Violence and the Procreational Geography of Apartheid[END_REF][START_REF] Segal L | Hostel dwellers speak: the Human Face of Violence[END_REF][START_REF] Sitas A | The New Tribalism: Hostels and Violence[END_REF].

iii The Democratic Alliance (DA) is the main opposition party in South Africa. iv The African National Congress (ANC) has got several hierarchised structures: local (through a branch that corresponds to the electoral ward; branch that is here divided into several voting districts); zonal (an aggregation of several branches often corresponding to a functional area, for instance a township: from 5 to 9 branches generally); regional (corresponding here to Johannesburg metropolitan boundary), provincial and national (see Figure 1). South African National Civic Organisations (SANCO) is a national federation of civics (residents associations that emerged mostly in black townships in the 1980s to fight apartheid), which has a similar structure but much less wide spread and functional with a much larger diversity of civics which do not necessarily follow national directives. SANCO has entered into a political alliance with the ANC at the national level, giving up what used to be its "watchdog role" towards government because it was (arguably wrongly) considered useless in democratic, post apartheid times (Zuern 2001).

v The research started early 2009, and national elections were held in April 2009. We had to wait till after the elections to meet some of the leaders, to respect Joshco"s request of not stirring an already unstable situation (in the meantime we carried on our interviews with other organizations and tenants). Even so, the SANCO contact given by Joshco was not the Chair but a SANCO disgruntled memberwho had left SANCO leadership and was more sympathetic to Joshco"s view. While we were greeting him (as the SANCO Chair we thought he was) in front of the hostel gate, the "real" chair of SANCO happened to pass by and he enquired about our presence.

He was outraged of being by-passed, disrupted the meeting, and requested us to "follow proper procedure" by phoning him the following week to make an appointment with the "right SANCO representative" (himself). vi An executive committee meeting is not a "public" meeting, as it is meant for leadership (executive committee members) and is supposed to deal with strategic issues. vii These notes were written in English shortly after the meeting. They were slightly edited for publication, and complemented by footnotes and figures for clarity to the reader. viii All the participants" names have been changed to protect anonymity. ix Protest march, generally involving songs and dances popularized during the apartheid struggles.

x In Johannesburg strong mayoral system, the Mayor appoints ten members of the Mayoral Committee (MMC) amongst the elected councilors (he does so in his political majority, the ANC, and not according to political parties" shares within the Council). Each MMC has a portfolio which corresponds to an administrative department in the City (Housing, Infrastructure, Health, Sports and Recreation, etc.).

xi COPE, Congress of the People, is a new political party that was constituted in 2008 as a splinter group from the ANC, after the Polokwane Conference (December 2007) which consecrated one ANC faction (Zuma"s faction, the current South African president) over the other (Thabo Mbeki"s faction -the former president). It is often seen by ANC politicians as a major threat to the party as it taps into similar anti-apartheid struggle credentials and could gather all those who are disappointed by the ANC.

xii See note iv.

xiii This legislation makes the ward councilor and around him/her, the ward committee, the key element of community participation. xiv See note ii.

xv See note iv. After being interrupted by SANCO chair, the former SANCO leader that Joshco had put us in touch with indicated that he was willing to grant us an interview, but not here, not then. He nevertheless immediately invited us to his place but did not utter a word as there was a visitor. We subsequently organized a meeting in PLANACT office rather than in the hostel, as we did with several interviewees. These fears, the fact that violence is also a "normal" way of settling conflicts, were later confirmed by episodes (see PLANACT report 2010 for more details).

xvi Apartheid is obviously loathed and condemned by all, but there is also an expression of nostalgia for the "old times" where men were respected, when order was prevailing, etc. Significant is the debate with Joshco about how the renovated hostel should workresidents request all public facilities be provided on site (postal services, clinic, school, etc.), whereas Joshco wants to break away from the apartheid legacy of the "enclave" and encourages residents to use services from surrounding suburbs.

xvii Official policy documents. xviii The dompass was the permit that each Black urban resident was supposed to permanently carry with him in order to justify his/her presence in urban areas (as Blacks were supposed to be temporary sojourners in cities, and authorization to live in the city often linked to their employment).

xix See Benit-Gbaffou, forthcoming.

xx For more detailed analyses see Benit-Gbaffou and Mathoho 2010.

xxi There are many texts analyzing how "high" politics or specific development policies create a whole range of brokers, mediators, whose actions could be linked to "low" or petty politics [START_REF] Blundo | La corruption quotidienne en Afrique de l"ouest[END_REF][START_REF] Auyero | Poor people's politics: peronist survival networks and the legacy of Evita[END_REF][START_REF]Urban land transformation for pro-poor economies[END_REF][START_REF]Reaching Larger Worlds: Negotiating the Complexities of Social Connectedness in Douala[END_REF][START_REF] Chatterjee | The Politics of the Governed: Popular Politics in Most of the World[END_REF]. But the focus is centered on how the opportunities opened by specific policies or resource distribution create gate keepers or gate openers; how it creates power stakes at the local level and rivalry for access to resources and constituencies; not the other way round: how the nature of party politics (its local pettiness, power tactics) links to (or impedes) the emergence of party policies, ideologies, or collective action.

Figure 1 -

 1 Figure 1 -Structures of leadership and power hierarchies in local government and in the ANC, Johannesburg 2010.

City Deep Hostel-12.06.09 vii Alliance Forum executive committee meeting, 10.06.09, City Deep Hostel, boardroom, 18h00.

Mayoral Committee 218 Councillors (ward and party list) City Manager Officials City utilities and agencies CEOs (= directorzone Chair ANC zone