Rachid Guerraoui

Arsany Guirguis

Anne-Marie Kermarrec

Erwan Le Merrer
email: erwan.le-merrer@inria.fr

FeGAN: Scaling Distributed GANs

Existing approaches to distribute Generative Adversarial Networks (GANs) either (i) fail to scale for they typically put the two components of a GAN (the generator and the discriminator) on different machines, inducing significant communication overhead, or (ii) they face GAN training specific issues, exacerbated by distribution.

We propose FeGAN, the first middleware for distributing GANs over hundreds of devices addressing the issues of mode collapse and vanishing gradients. Essentially, we revisit the idea of Federated Learning, co-locating a generator with a discriminator on each device (addressing the scaling problem) and having a server aggregate the devices' models using balanced sampling and Kullback-Leibler (KL) weighting, mitigating training issues and boosting convergence.

Through extensive experiments, we show that FeGAN generates high-quality dataset samples in a scalable and devices' heterogeneity tolerant manner. In particular, FeGAN achieves up to 5× throughput gain with 1.5× less bandwidth compared to the state-of-the-art GAN distributed approach (named MD-GAN), while scaling to at least one order of magnitude more devices. We demonstrate that FeGAN boosts training by 2.6× w.r.t. a baseline application of Federated Learning to GANs, while preventing training issues.

Introduction

GANs enable learning the statistical distribution of a target dataset and generating new samples from that dataset on demand. This feature can be used in a wide range of applications such as generating pictures from text descriptions [START_REF] Reed | Generative Adversarial Text to Image Synthesis[END_REF], producing videos from still images [START_REF] Vondrick | Generating Videos with Scene Dynamics[END_REF], or increasing at will an image resolution [START_REF] Ledig | Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network[END_REF]. Other applications, such as Deep-Fakes generation [START_REF] Li | Exposing deepfake videos by detecting face warping artifacts[END_REF] are as impressive as they are critical for society.

At the core of a GAN lie two deep neural networks: the generator and the discriminator. They confront each other in a game: the generator aims at generating data that looks real (i.e., coming from the real data distribution) to feed the discriminator. When the latter can no longer distinguish real data from the generated one, the training stops. The generator has then captured the data distribution and has reached the point where it can generate new samples.

Training GANs is resource and time consuming. For instance, it takes up to 48 hours to train a GAN to learn the distribution of a 512x512 image dataset on Google TPUs v3 [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF] with one generator and distributed discriminators (on 21 machines) outperforms the centralized approach. Yet, (b) it does not scale, due to communication bottlenecks. devices [START_REF] Brock | Large scale GAN training for high fidelity natural image synthesis[END_REF]. Considering the number of potential applications, it is then of paramount importance to improve this training time. One obvious way to scale a system is to distribute the computing load on multiple devices. MD-GAN [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF] has been recently proposed as a way to distribute GANs. MD-GAN leverages a single generator, at a central location, and distributes the discriminator across multiple devices (this architecture is also adopted by [START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF]). Such an architecture follows the celebrated parameter server model [START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF], where the server is the generator and the workers are discriminators. Figure 1a illustrates the benefit of such an architecture with 21 machines on four datasets (MNIST [START_REF]Mnist dataset[END_REF] and Fashion-MNIST [START_REF]Fashion-mnist dataset[END_REF], often used as baselines, CelebA [START_REF] Liu | Deep learning face attributes in the wild[END_REF] and Ima-geNet [START_REF] Deng | Ima-geNet: A Large-Scale Hierarchical Image Database[END_REF], two state-of-the art datasets for image-based applications). Clearly, distributing the training improves the system throughput, defined as the number of epochs (the processing of all data samples in the dataset) the system handles per second. Yet, due to the presence of a single centralized generator, this architecture does not scale, i.e., adding devices does not improve the throughput, as illustrated in Figure 1b. This is due to the huge volumes of data to be transferred over the network to synchronize the generator and the multiple discriminators, making the central generator a bottleneck. Clearly there is a huge room for improvement.

Another architecture for distributed training is Federated Learning (FL) [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF], in which training happens on the edge devices that own private data, assisted by a central server.

Combining GAN training with this architecture can yield impressive applications on edge devices including text-toimage translation and generating new human poses. Yet, approaches that followed such an architecture for GAN training (for e.g., running diagnostics [START_REF] Augenstein | Generative models 12 for effective ml on private, decentralized datasets[END_REF] or for data privacy goals [START_REF] Triastcyn | Federated generative privacy[END_REF]) also reported difficulties due to learning divergence, vanishing gradients, and mode collapse problems: learning divergence happens when neither the generator nor the discriminator reaches its goal, i.e., Nash equilibrium is not reached [START_REF] Arjovsky | Towards principled methods for training generative adversarial networks[END_REF]. A second salient problem is vanishing gradients, that occur when the discriminator is much more powerful than the generator, which, in this case, always fails to generate convincing samples to the discriminator, where the feedback from the discriminator does not help the generator to learn [START_REF] Neyshabur | Stabilizing gan training with multiple random projections[END_REF]. Last but not least, the problem of mode collapse happens when the generator learns to generate only a few classes of data input rather than learning the true distribution of data [START_REF] Che | Mode regularized generative adversarial networks[END_REF]. Such problems manifest clearly in the FL context. For instance, the server cannot communicate with all devices at every round for scalability reasons; some form of device sampling is needed. Yet, such sampling should not be uniform because of the data distribution skewness on the devices hosting the GAN model. Unfortunately, such data skewness can easily lead to mode collapse. Thus, the mere application of the FL approach [START_REF] Xie | Slsgd: Secure and efficient distributed on-device machine learning[END_REF][START_REF] Xie | Practical distributed learning: Secure machine learning with communication-efficient local updates[END_REF][START_REF] Yang | Federated machine learning: Concept and applications[END_REF] to GANs training is bound to failure [START_REF] Hardy | Gossiping gans[END_REF] or to underperformance, as we shall confirm experimentally.

Contributions. We propose FeGAN, a distributed middleware that enables GANs to scale and cope with GAN specific issues such as mode collapse and vanishing gradients. Our main contributions are threefold.

1) We revisit the FL paradigm, normally dedicated to deep networks, to make it suitable to GANs. Essentially, we fully distribute both the generator and the discriminator so that a private GAN can be locally trained on each device. This helps scale the system and prevent the vanishing gradients problem, as we show in Sections 5 and 6.

2) We design mechanisms to make FeGAN resilient to GAN specific issues. In particular, we devise two techniques that are designed to resist the mode collapse and the learning divergence problems in a distributed setup. FeGAN prioritizes updates from certain nodes over some others, using Kullback-Leibler (KL) weighting scheme, and it carefully schedules the application of devices' updates on the global trained model, using the balanced sampling scheme. Both schemes not only boost the learning quality but also help save compute time and communication resources. FeGAN is tolerant to devices' heterogeneity in terms of memory and compute power and to server and network failures through periodic checkpointing of the learning state.

3) We conduct an extensive experimental evaluation of Fe-GAN and compare it to a state-of-the-art GAN distribution approach (MD-GAN), as well as with a centralized approach and a baseline application of Federated Learning to GANs.

Background

Generative Adversarial Networks

A GAN [START_REF] Goodfellow | Generative adversarial nets[END_REF], made of generator G and discriminator D, targets the learning of a dataset distribution in space X , where x ∈ X follows a distribution probability P data . The generator is modeled by the function G w : R ℓ -→ X , where w contains the parameters of its neural network G w , and ℓ is fixed. Similarly, for the discriminator D θ : X -→ [0, 1] where D θ (x) is the probability that x is a data from the training dataset, and θ contains the parameters of the discriminator D θ . The objective consists in finding the parameters w * for the generator:

w * = arg min w max θ (A θ + B θ,w ), with A θ = E x ∼P data [log D θ (x)] and B θ,w = E z ∼N ℓ [log (1 -D θ (G w (z))] ,
where z ∼ N ℓ means that each entry of the ℓ-dimensional random vector z follows a normal distribution with fixed parameters. In this equation, D adjusts its parameters θ to maximize A θ , i.e., the expected good classification on real data and B θ,w , the expected good classification on generated data. G adjusts its parameters w to minimize B θ,w (w does not have impact on A), which means that it tries to minimize the expected good classification of D on generated data. This competitive scheme ends, if convergence occurs, to the learning of the dataset distribution P data .

Distributed Machine Learning

The parameter server architecture [START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF] was a milestone for distributed ML, introduced to greatly accelerate the computation over a single centralized process. In this model, the parameter server allocates data (also called batches) to workers and orchestrates the learning process. Workers run computations locally and send back their gradient errors to the server that aggregates them in a global model. In turn, workers pull the up-to-date model from the server and iterate until the convergence of the global model is reached.

The Federated Learning (FL) [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF] approach however seeks to leverage a large crowd of edge devices that each owns private data, without imposing any movement of the data (unlike with the parameter server). The devices collaboratively train a global model, which is hosted on a centralized server. The server decides which subset of the devices should participate in a learning round through random selection. Selected devices, in turn, send their updates to the server after a number of learning iterations over their private data. Typically, the server aggregates the devices' updates using Federated Averaging [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF]. The accuracy of FL is shown in [START_REF] Zhao | Federated learning with non-iid data[END_REF] to be negatively impacted by the imbalanced data distribution on the devices.

FeGAN Design and Implementation

In this section, we first provide the system setup and an overview of FeGAN. Then, we focus on our design choices, which make FeGAN scalable and resilient to GAN training issues, and the system aspects of FeGAN. On top of this, training and system specifics are designed to reach our scalability and resilience goals. Each device owns a GAN locally, composed of a local generator and a local discriminator. Data stored on each device remains local: only the output of the local computation is sent to the server. Given its local nature, data might be unbalanced and possibly not identically nor independently distributed (non-iid) across devices. Yet, the server can gather metadata from devices regarding the number of local samples per class. Hence, we assume each device can label its data or at least can model its own data distribution, using generative or clustering schemes like Gaussian Mixture Models (GMM) [START_REF] Richardson | On bayesian analysis of mixtures with an unknown number of components (with discussion)[END_REF][START_REF] Williams | Gaussian processes for regression[END_REF] or K-means [START_REF] Faber | Clustering and the continuous k-means algorithm[END_REF].

Devices only communicate with the server. As they do not communicate with each other, they do not need to trust each other. Communication links between the devices and the server could be unreliable and asymmetric with limited bandwidth [START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF]. The server can keep the devices' updates secure using off-the-shelf secure aggregation protocols [START_REF] Bonawitz | Practical secure aggregation for federated learning on user-held data[END_REF]. Initialization. Before starting the training process, each device informs the server of its local data distribution (typically how many classes and how many samples per class it owns locally). Such a step could be repeated should the dataset change during the training process. The goal of collecting metadata from all devices is for the server to account for the data imbalance across devices.

The FeGAN Algorithm

To this end, the server computes the Kullback-Leibler (KL) divergence [START_REF] Kullback | Information theory and statistics[END_REF][START_REF] Kullback | On information and sufficiency[END_REF] scores, which reflect the degree of divergence of the devices' local data distribution from the global distribution. In particular, the KL divergence of device k is computed as follows:

D K L (P k ||Q) = x ∈X P k (x) log( P k (x ) Q (x ) )
, where P k is the normalized vector of samples per class x at device k, Q is the normalized vector of the total number of samples per class (in the global dataset), and X is the collection of all classes. For instance, P k (x) = n kx /n k , where n k x is the number of samples of class x at device k, and n k is the total number of samples at device k. The server then assigns a score s k to each device k as follows:

s k = n k n × D K L (P k ||Q)
, where n k is the total number of samples per device k and n is the total number of samples in the dataset.

All devices also send to the server their capabilities, in terms of memory size and compute power available for training. The server then uses this information to choose a training load for each device. As for the current version of FeGAN, the server follows a linear regression model to compute this load, which we assume fixed throughout the training process.

Server operation. The server starts each FL round by choosing a group of devices, using balanced sampling (Section 3.3), to update collectively the model state. The server then asks the sampled devices to contribute to the current round and assigns to each device the pre-computed training load. At the end of the FL round, the server collects the updates of the devices and aggregates them using the KL weighting scheme (Section 3.3). The server also weighs such updates by the devices' respective assigned batch sizes (Section 3.4). The server repeats this procedure till convergence.

Device operation. Devices remain idle until they are contacted by the server to participate in one FL round. A device selected for a given round receives the updated model state (of D and G) and the values for E, the number of local training iterations to be done by this device, and B, the training batch size. After running E local training iterations, each device sends back the updated model to the server.

FeGAN Design Choices

Co-locating networks. Training deep neural networks with backpropagation sometimes encounters the vanishing gradients problem, which happens when the computed gradients are extremely small, hindering the update of the network's parameters and hence, stopping the learning. In the context of GANs, such a problem happens usually due to having a very strong discriminator [START_REF] Neyshabur | Stabilizing gan training with multiple random projections[END_REF]. Given that training GANs is usually formulated as a game between two players/networks, typically a network gains strength with more experience (i.e., with more training iterations). This strength then reflects In the first round, the server chooses device 1 (with the highest number of samples) and device 3 (with samples from a class not represented by device 1). When the devices reply, the server updates the model, applying KL_weighting on their replies. In the second round, the server chooses the unsampled devices to maintain fairness and the training continues as usual.

how good the network is (either the generator or the discriminator) in doing its task. In the situation of a powerful discriminator, the generator fails to learn as it cannot get much information from the discriminator's feedback. Hence, the discriminator wins in this case, i.e., the generator always fails to generate fake samples that can trick the discriminator. In the centralized setup, this problem can be mitigated by choosing the correct set of hyper-parameters and loss functions [START_REF] Goodfellow | Generative adversarial nets[END_REF][START_REF] Lucic | Are gans created equal? a large-scale study[END_REF]. Yet, this is not sufficient in the distributed setup; it is also crucial to balance the strength of both networks. FeGAN solves this problem by co-locating the discriminator with the generator so that both networks can be trained simultaneously, increasing their strength at the same time.

Importantly, co-locating networks reduces the communication overhead, compared to other designs that centralize the generator in the server while distributing the discriminators on the devices, e.g., [START_REF] Augenstein | Generative models 12 for effective ml on private, decentralized datasets[END_REF][START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF]. In the latter case, the distributed discriminators should periodically send their feedback to the centralized generator, whose size is the same as that of the input space that is desired to be learned, e.g., pixels of an image. By co-locating networks, FeGAN drastically reduces such an overhead, as we show in Section 6.

Kullback-Leibler weighting. Data is more likely to follow different distributions on different devices and hence, using vanilla averaging of devices' local models might lead to learning divergence [START_REF] Lim | Federated learning in mobile edge networks: A comprehensive survey[END_REF]. Vanilla Federated Averaging (Fe-dAvg) [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF] is also not sufficient for convergence in some cases [START_REF] Zhao | Federated learning with non-iid data[END_REF] as it does not take data distribution discrepancies into consideration while weighting the devices' updates.

FeGAN mitigates learning divergence by relying on Kullback-Leibler (KL) weighting, which is applied as follows. Upon receipt of the updated models from the devices, the server weights them by applying the softmax function on the KL divergence score of each device. More specifically, the model received from device k is given a weight w k as follows:

w k = exp -s k i ∈I exp -s i
, where s k is the pre-computed KL score of device k, and I is the set of devices contributing to the current FL round. The softmax function acts as a normalization 1 to the weights given to the devices' updates so as to make these weights sum to 1. In other words, the output of the softmax function (i.e., the weights) can be seen as the probability of the contribution of each device to updating the global model state. The negative sign given to the score is to penalize the devices with more divergence from the global data distribution as their updates are less useful than the other devices' updates. Such a design of a weighting scheme is crucial to learn the global distribution of data.

Balanced sampling. Mode collapse [START_REF] Che | Mode regularized generative adversarial networks[END_REF] is arguably the hardest problem that one can encounter while training a GAN. Such a problem happens when the generator learns only partially the data distribution and hence, can only generate data from a limited number of classes. In our distributed, uncontrolled environment, the situation could be exacerbated due to the skewness of data distribution on the devices. Our balanced sampling scheme aims at solving this problem.

At each FL round, the server samples C × n d devices to do the training procedure, where C denotes the fraction of devices doing the training in each round with C ∈]0, 1], and n d is the total number of devices. Note that unlike vanilla Federated Learning [START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF], in FeGAN, the server starts the sampling procedure, by choosing devices with specific data distribution to avoid falling into mode collapse. The novelty of FeGAN's sampling is that it favors (1) devices with more samples, (2) devices with a balanced dataset (i.e., almost equal number of samples per class), and (3) unsampled devices in the previous rounds. Thus, our sampling technique always ensures a balanced number of samples per class in the updates applied to the model (G and D). Such a technique plays an important role in the robustness and the convergence speed, as we show in our evaluation.

Technically, FeGAN applies balanced sampling as follows: 1) The server maintains a priority queue with the number of accumulated samples per class from sampled devices (from previous rounds) stored in it. 2) At each round, the server picks the class with the least number of accumulated samples and chooses a device that declares to have this class to include it in the new round. 3) The server accounts for the samples from other classes that will be included in the new round (due to including the chosen device) and updates the queue accordingly. 4) The server repeats this procedure until it samples C × n d devices. It then sends the updated state of the model, i.e., D and G networks, to the sampled devices.

FeGAN System Aspects

Handling heterogeneity. Devices in the wild are not equal in many respects, including their hardware specifications (e.g., compute power and memory) and the available network bandwidth. Tolerating device heterogeneity in an optimal manner is an open problem with many heuristics [START_REF] Lim | Federated learning in mobile edge networks: A comprehensive survey[END_REF]. Because we are targeting GANs training, it is then crucial to design a solution that handles device heterogeneity without falling into GAN-specific problems. For instance, a solution that prefers sampling strong devices over weak devices e.g., [START_REF] Nishio | Client selection for federated learning with heterogeneous resources in mobile edge[END_REF] can lead to mode collapse if the weak devices owns data classes that are not represented by the strong devices.

FeGAN handles this issue by controlling the training load given to the contributing devices in one round. More specifically, the central server dictates the number of iterations and the batch size used for local training on devices. The server chooses less number of iterations and smaller data batches for weaker devices. This helps mitigate the straggler effect [START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF], which happens when some devices are significantly slow, degrading the whole system throughput. In the aggregation phase, devices' updates are also weighted based on the load given to each of them. Such weights are multiplied by the KL weights (w k ) explained in Section 3.3.

Fault tolerance. The central server represents a single point of failure: if it crashes, without any fault tolerance technique, the whole learning stops, as devices do not communicate nor trust each other. FeGAN uses periodic checkpointing for server's fault tolerance. Initially, FeGAN starts multiple servers, which number can be configured, yet, only one of them acts as a primary and the rest are backups. Only the primary communicates with the devices while other servers remain idle. After each FL round, the learning state is stored in a persistent database. This includes the state of both networks, G and D, the optimizer, the number of epochs passed, the data distribution on the devices, the devices capabilities, and the history of chosen devices in all previous rounds.

In the case of the crash of the primary server, a backup server takes over. First, it loads the latest learning state from the persistent database and announces to the devices that it is the new primary. The new primary then starts a new round by choosing a new set of devices to do the training.

Network failure is detected through a standard timeout mechanism. Such a failure could be either due to slow communication, network partition, or a crashing device. In the event of a failure, the server calls for completion or abortion of the current round. Such a decision relies purely on the server configuration and the current learning state. The server then records the actual devices participated in this round rather than the intended set of devices to participate.

Implementation. We implemented FeGAN on PyTorch [START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF]. We integrated our implementation with already-existing public implementations of different GAN architectures implemented for training on one machine. We now describe the communication abstractions we implemented to allow the distribution of GAN via FeGAN. Our source code will be publicly available soon.

We rely on the notion of distributed groups as instructed by the PyTorch distributed backend. Any invoked communication abstraction takes as an input a group defining the set of nodes that will be involved in this communication. As we rely on a centralized architecture (see Figure 2), we allow only the centralized server to create groups to avoid any conflicts with the devices and hence, achieve strong consistency on the group formation.

We introduce two abstractions that can be used off-theshelf directly by both the server and the devices: multicast model and the average models. Multicast model is used by the server at the beginning of any FL round to multicast the current state of the model to a group of devices (similar to map in MapReduce notation [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF]). To comply with PyTorch distributed runtime, the chosen devices should also invoke this abstraction (i.e., multicast model) to receive the models from the server. We use the NCCL backend of PyTorch [START_REF]NVIDIA[END_REF] so that the models stored on a GPU need not to be copied to the CPU memory before being sent back to the devices and hence, saving time and memory2 .

The second abstraction, average models, is used at the end of an FL round (similar to reduce in MapReduce notation). Typically, this function is invoked by the server to aggregate devices' updates. As our model is synchronous, the server waits for all contributing devices to send back their results before proceeding to the next round. If our weighting technique is not activated, we use the reduce operation from the distributed backend with ReduceOp.SUM as a reduce operator and then, divide by the number of contributing devices to this round to get the average of the updates. We use this operation as it is always faster than the other operations. Otherwise, we use the gather operation to first collect all the updates from the devices and then apply the weights calculated by the server. The main problem with the latter operation is that it does not work on GPUs 3 and hence, the updates need to be first copied to the main memory before sending them to the server. At the other end, the server collects all the updates, copy them to the GPU memory, and then calculates the weighted average to get the new model. We could not overcome this inherent problem of the PyTorch distributed backend as gather is the only appropriate abstraction we can use to implement our average model abstraction while applying weighted averaging.

Finally, we report on the number of lines of code (LoC) required to port two publicly available 4 GAN implementations to FeGAN. Factoring out the common code for dataset partitioning, group initialization, and performance measurements (e.g., FID calculation), it takes less than 70 LoC (which constitutes around 5% of the whole code) to port a GAN implementation to FeGAN.

Experimental Setup

In this section, we describe our experimental setup, baselines, and the configurations we used to evaluate FeGAN.

Testbed. We evaluate FeGAN on the Grid5000 platform [2], using machines from the same cluster. Each one has 1 CPU (Intel Xeon Gold 6126) with 2 cores, 16 GiB RAM and 2 Gbps Ethernet, and one GPU (Nvidia Tesla P100). Unless stated otherwise, experiments were run on 80 nodes. This number reaches up to 176 in some experiments.

Evaluation metrics. Although evaluating GANs has been an issue for ML practitioners, requiring human judgement to assess the quality of the generated data [START_REF] Borji | Pros and cons of gan evaluation measures[END_REF][START_REF] Lucic | Are gans created equal? a large-scale study[END_REF][START_REF] Mao | Least squares generative adversarial networks[END_REF], robust metrics are now commonly used to assess the performance of GANs [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF][START_REF] Kurach | A Large-Scale Study on Regularization and Normalization in GANs[END_REF][START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF] such as Frechet Inception Distance (FID). We evaluate FeGAN along two main metrics: FID to assess the GAN convergence (or quality of the learned distribution) and throughput to measure the system's efficiency. We chose FID as it is one of the most stable, robust, and widely-used metrics for GAN [START_REF] Borji | Pros and cons of gan evaluation measures[END_REF]; it was the one used by our predecessors [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF][START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF]. Besides, FID has an official implementation in the popular ML frameworks, including TensorFlow and PyTorch. 1. FID is a metric that computes the distance between feature vectors of real images and generated ones. The score reflects the statistical divergence between the generated images and the raw images using the Inception-v3 model [START_REF] Szegedy | Rethinking the inception architecture for computer vision[END_REF] used for image classification. The lower the score, the better (a 0.0 score indicates that the two groups of images are identical). 2. Throughput defines the number of updates the server can process per second. Such a metric reflects the scalability of the system as well as the efficiency of the communication.

Note that we observe training convergence with time, the number of training epochs, and FL rounds. However, in our experiments, we maintain a one-to-one mapping between the number of epochs and the number of FL rounds so, we always show only one of them for space constraints. Also, note that the shown results are the average of 6 runs per experiment; we omit error-bars for better readability.

Datasets. We evaluate FeGAN in the context of three datasets: MNIST [START_REF]Mnist dataset[END_REF], Fashion-MNIST [START_REF]Fashion-mnist dataset[END_REF], and ImageNet [START_REF] Deng | Ima-geNet: A Large-Scale Hierarchical Image Database[END_REF]. In our evaluation, we focus on image generation not only because it is very challenging and resource-demanding but also due to its multiple applications in the real world. MNIST and Fashion-MNIST both describe grey-scale images of 10 classes representing handwritten digits and clothes respectively. Each dataset has 28x28 60,000 training images and 10,000 testing images; we use the latter for computing FID. Ima-geNet [START_REF] Deng | Ima-geNet: A Large-Scale Hierarchical Image Database[END_REF] is a large dataset with around 14M images of a 256x256 resolution, dispatched into more than 21, 000 classes. ImageNet classification challenges usually use a subset of this dataset [START_REF] Russakovsky | ImageNet Large Scale Visual Recognition Challenge[END_REF][START_REF] Sutskever | Imagenet classification with deep convolutional neural networks[END_REF]. We use a subset of ImageNet with 100K images, distributed among 200 classes with 500 samples per class. Reducing the dataset only allows for faster convergence. Unless otherwise stated, we use Fashion-MNIST as a default dataset throughout our evaluation.

Non-iidness. In all the considered datasets, the data is balanced: the average number of samples per class is almost the same in all classes. To our knowledge, there is no publicly available dataset with inherent non-iidness or imbalanced data. We designed a distribution engine to emulate imbalanced and skewed distributions of data among devices.

Our engine accepts two input parameters: max_class and max_samples. The former defines the maximum number of classes any device can have, and the latter defines the maximum number of samples per class on any device. For each device, the engine generates a random number r _c ∈ [1, max_class×i n ], where i is the index of the device, i.e., i ∈ [1, n] and n is the total number of devices. r _c defines the number of classes this device will have. Then, the engine randomly samples r _c classes from the dataset. Similarly, the engine (at each device) generates a random number r _s for each selected class with r _s ∈ [1, min(i 2 , max_samples×i n

)]. Finally, the engine randomly samples r _s samples for each selected class from the dataset. Note that the engine generates a different value for r _s per class. Using this engine, we managed to emulate several cases of data imbalance and non-iid distribution of data among devices, including the typical non-iid workloads reported before in the literature [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF][START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF][START_REF] Sattler | Robust and communication-efficient federated learning from non-iid data[END_REF][START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF].

GAN architecture. Without loss of generality, we evaluate FeGAN with two popular GAN architectures. We believe our work can be ported to any GAN architecture, as FeGAN is GAN-internals agnostic. The two experimented architectures are: Least Squares Generative Adversarial Networks (LSGAN) [START_REF] Mao | Least squares generative adversarial networks[END_REF] for the MNIST and Fashion-MNIST datasets, and a Deep Convolutional Generative Adversarial Network (DCGAN) [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] for the ImageNet dataset. The generator network comprises of one fully-connected layer followed by three convolutional layers with a Leaky ReLU activation function each and a tanh activation function for the output. The discriminator network is composed of four convolutional layers with Leaky ReLU activation function followed by one fully-connected layer with a Sigmoid activation function at the output. The number of input, output, and hidden neurons per layer depends on the input image size. Our experiments show that both networks do not require more than 3 MB of memory for the storage of their architecture and weights.

Hyper-parameters. Unless otherwise stated, we use the following hyper-parameter values in our experiments. We set E, the local number of iterations per each device, to 30, C, the fraction of devices chosen each round (by the server) for the training, to 0.025, B, the batch size, to 50, and FID batch size, the number of samples used to calculate the FID, to 10,000. We discuss the effect of changing the values of E and C in Section 6. We monitor the progress of FID every 1000 training iterations (not to confuse with epochs nor with FL rounds). We use the Adam optimizer [START_REF] Kingma | A method for stochastic optimization[END_REF] for both the generator and the discriminator with an initial learning rate of 0.0002 and values for betas 0.5 and 0.999. As instructed in their original papers, we use Mean Square Error (MSE) loss function with LSGAN [START_REF] Mao | Least squares generative adversarial networks[END_REF] and Binary Cross-Entropy (BCE) with DCGAN [START_REF] Radford | Unsupervised representation learning with deep convolutional generative adversarial networks[END_REF] for both networks.

Baselines. We compare FeGAN against three competitors: 1. Centralized GAN. We use a centralized GAN as a baseline to be able to compare the resulting FID with FeGAN as well as to illustrate the throughput gain of distributing the computation. We train a GAN on a single machine with two GPUs. The hyper-parameters are set to the same value as FeGAN, including the batch size for fairness. 2. Parameter Server-based GAN. Existing approaches to distribute GANs rely on the parameter server architecture [START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF] to handle the distributed training [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF][START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF]. Note that the evaluation of such systems (in their original papers) has been conducted by emulation. Since none of these systems is opensourced yet and rely on the same architecture (with minor nuances), we picked MD-GAN [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF] as a representative of this class of systems. Like FeGAN, MD-GAN assumes that data on devices is never shared with any other machine. We implemented MD-GAN in our distributed framework using the same networking abstractions, models and datasets that we used in FeGAN. For the sake of fairness, we put Tensors on GPUs and handle communication using the same GPU-to-GPU abstractions. We also use the best values for the hyper-parameters as instructed by the authors in their original paper [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF].

Federated Averaging (FL-vanilla).

We compare to a strawman FL setup, where discriminators and generators remain on devices. Such devices send error gradient updates to a central server that hosts the up-to-date generator and discriminator. This constitutes the FL baseline, inspired by the FedAvg algorithm [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF], we coin FL-vanilla.

FeGAN configurations. We report on all the variants of our FeGAN system with all combinations of balanced sampling and KL weighting techniques being used or not. We abbreviate sampling with s and weighting with w in the figures with 0 means disabled and 1 means enabled. For example, s = 1, w = 0 denotes FeGAN deployment that uses our balanced sampling scheme but not the weighting one. This is completely independent of the distribution of data among devices. Note that setting s = 0, w = 0 is equivalent to employing FL-vanilla.

FeGAN Convergence

In this section, we show the quality of the data generated by FeGAN, measured by FID, as well as the convergence behavior compared to other baselines in both iid data and non-iid data contexts. . Convergence of FeGAN compared to the Centralized approach and MD-GAN. We distributed the Fashion-MNIST dataset identically and independently (iid) on 80 devices for the distributed deployments. FID metric: the lower, the better the generated samples.

Convergence of FeGAN in iid Settings

Comparison with competitors. We run a head-to-head comparison with a centralized GAN and MD-GAN w.r.t. convergence performance over time and the number of training epochs. In this experiment, we distribute data identically and independently (iid) over devices in the distributed deployments, namely MD-GAN and FeGAN. As we wanted to focus on the benefit obtained from FeGAN architecture, namely the fact that both the generator and the discriminator are distributed, we voluntarily disable the weighting and sampling schemes in this experiment (s = 0, w = 0). Indeed, distribution leads to communication overhead, which FeGAN minimizes (by the co-location of the generator with the discriminator on all devices in addition to sampling a limited number of devices for training in each round).

Results displayed on Figure 4 clearly show that FeGAN significantly outperforms both competitors. In both figures, we observe that FeGAN converges to an FID value of around 50 where the other approaches converge to an FID value of around 100. Compared to the centralized deployment, Fe-GAN achieves a better FID in less time (Figure 4a). At the first glance, this result looks counter-intuitive. Yet, this is due to the fact that in FeGAN, the server aggregates updates based on more data samples (i.e., collected from more devices), highlighting the advantage of distributing the training process. 5 This also gives FeGAN a more diverse view of the dataset and ensures a better convergence than in the centralized case [START_REF] Xie | Diversity-promoting and Large-scale Machine Learning for Healthcare[END_REF][START_REF] Zhou | Diverse ensemble evolution: Curriculum data-model marriage[END_REF]. This is consistent with the observations reported in [START_REF] Durugkar | Generative multiadversarial networks[END_REF][START_REF] Hoang | Multi-generator generative adversarial nets[END_REF] while comparing a centralized approach to a distributed one. Since MD-GAN relies on a single generator at the server, it fails to benefit from the data diversity on multiple devices and hence, achieves a performance similar to the centralized approach. FeGAN achieves a much faster convergence because the server communicates only with a fraction of devices in each round as opposed to MD-GAN where it communicates with all of them; this enables FeGAN to achieve faster iterations.

The results depicted on Figure 4b show that FeGAN consistently outperforms MD-GAN. However, the centralized approach converges faster than the distributed approaches in the first few hundreds of epochs. After that, FeGAN achieves a better FID value. This is due to the fact that in the first few epochs, FeGAN contacts different devices per round and hence, the server aggregates updates from different data, trying to adapt both networks (the generator and the discriminator) to this data, which leads to the observed slow start. In the subsequent iterations, as the weights of both networks become more stable, FeGAN leads to better-generated data (and hence, a better FID). FeGAN configurations. Results previously demonstrated the relevance of FeGAN (with s = 0, w = 0) in an iid setup over existing distributed and centralized approaches. We now assess the impact of the core mechanisms of FeGAN, namely the impact of s and w in an iid setting. Figure 5 displays the results of different FeGAN deployments with all combinations of enabling and disabling the balanced sampling and the KL weighting schemes. We observe that in terms of convergence speed (both in terms of time and training epochs) they perform approximately the same. FeGAN (with s = 1, w = 1) performs slightly better and provides quickly a smaller FID.

Those results demonstrate that, while we aimed at sustaining non-iid data distributions when designing our system, FeGAN is equally good in iid setups. This makes FeGAN an excellent system across data distributions.

Convergence in a Non-iid Context

In this section, we extensively evaluate the performance of FeGAN in a non-iid setup. To this end, we compare FeGAN in its full-fledged version (with s = 1, w = 1) to the FeGAN version where the sampling and the weighting schemes have been disabled (i.e., the FL-vanilla competitor). We run these experiments in three different datasets and different data distributions. We control the data distribution (and hence, the degree of non-iidness and data imbalance) using the data distribution engine described in Section 4. Figures 6,7, and 8 show the results on the MNIST, Fashion-MNIST, and Ima-geNet datasets respectively, each in two settings where we vary the maximum number of classes and samples per device. The first two datasets are used to show the effectiveness of FeGAN on well-known baseline datasets, while the Im-ageNet experiment shows the performance of FeGAN on a large-scale dataset. For space constraints and as they exhibit similar shapes, we discuss the three figures collectively, highlighting the main performance gains of FeGAN.

Faster model updates. Our first observation is that FeGAN runs epochs faster, i.e., leading to a faster convergence, than FL-vanilla 6 . The balanced sampling (as compared to random sampling in FL-vanilla) of FeGAN favors devices that were not visited in previous rounds and hence, it has a higher probability of sweeping over the whole dataset (distributed among devices) faster than FL-vanilla. We quantify this throughput gain to 1.27 -1.8× with MNIST, 1.57 -1.7× with Fashion-MNIST and 1.9 -2.13× with ImageNet. We discuss this observation in detail in Section 6.

Better FID. Not only FeGAN achieves faster epochs in all datasets but we also observe that it converges to a better FID value, compared to FL-vanilla, after training for the same number of epochs. This is due to both our balanced sampling and KL weighting schemes. The fact that the server adjusts the weight of each device depending on its data distribution helps achieve a better generation of data (and hence, a lower value for FID), as opposed to FL-vanilla that considers devices equal regardless of the number of classes and the number of samples per class they hold. This, in turn, enables the server of FeGAN to consider faster a diverse set of data with a higher probability, contributing to learning faster the global data distribution.

Convergence gain. To demonstrate the superiority of Fe-GAN over FL-vanilla, we compare the time required to achieve a given FID value (usually the best value achieved by FL-vanilla) and call it convergence gain. Results show that the convergence gain of FeGAN over FL-vanilla is 1.27 -1.57×, 1.71 -3× and 2.75 -3.67×, when training MNIST, Fashion-MNIST, and ImageNet respectively. Beyond the ultimate FID value, a system can achieve eventually, the convergence gain is an important end-metric for ML practitioners. Such a metric combines the system's performance aspect (e.g., throughput or latency) and the ML algorithm performance aspect (i.e., convergence over training epochs).

The less uniform, the more effective FeGAN is. When comparing the first and second rows of Figures 6 and7, we observe that the performance gap between FeGAN and FLvanilla is larger for lower values of max_class. In other words, the effectiveness of FeGAN is even clearer when each device owns only a few classes from the whole dataset. This demonstrates the ability of FeGAN to account for a higher degree of data imbalance over devices; we believe the latter is a realistic scenario as we do not expect that all classes would be represented on distributed devices. Figures 8c and8d show a real-world scenario, where each device has at most 50 samples from any of the 200 classes of ImageNet. Results from both figures show that FeGAN converges faster than FL-vanilla in terms of both the number of rounds and time.

Relative Importance of Sampling & Weighting

We evaluate the relative impact of activating each mechanism in all datasets. The results for Fashion-MNIST are depicted in Figure 9. We observe that while using only one mechanism is enough for FeGAN to achieve a lower FID than FL-vanilla (where using sampling alone is slightly better than using weighting alone), using both mechanisms achieves the lowest FID.

Preventing mode collapse. Figure 10 shows the KL-divergence of the data distribution seen by the server (over FL rounds) compared to the real data distribution. We compare balanced sampling (used by FeGAN) to random sampling (used by FL with FedAvg [START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF]) and the iid case (when data is distributed identically on all devices). On the one hand, the figure shows that using random sampling with non-iid data will let the server see a diverging distribution compared to the real distribution of data. On the other hand, balanced sampling of non-iid data allows the server to see almost-exact distribution of data (compared to the optimal case, i.e., with iid data). As demonstrated by previous work [START_REF] Lim | Federated learning in mobile edge networks: A comprehensive survey[END_REF], the smaller the KL-divergence, the less the probability of experiencing mode collapse; FeGAN then shows resilience in that respect. Preventing vanishing gradients. FeGAN co-locates the discriminator with the generator on all devices so that the training of both networks can happen simultaneously in all training iterations, allowing both networks to have the same power in confronting each other. To demonstrate the efficiency of this approach, we run an experiment in which the discriminator is trained in all iterations while the generator is trained only once each E iterations. Such a design reflects that of having one generator in the central server and multiple discriminators on the devices, which was proposed before, e.g., in [START_REF] Augenstein | Generative models 12 for effective ml on private, decentralized datasets[END_REF][START_REF] Triastcyn | Federated generative privacy[END_REF]. Figure 11 shows that the latter design creates a dominant discriminator that can always defeat the generator, hindering the latter from generating output data that looks real. Yet, the co-location of both networks on all devices (applied by FeGAN) allows the generator to be powerful enough to generate such data, as demonstrated by the lower FID values. FeGAN thus clearly avoids that problem.

FeGAN System Performance

This section reports the performance of FeGAN with regards to baselines. The results being similar across datasets, we only present the results obtained with the Fashion-MNIST dataset unless stated otherwise.

Throughput. We measure the system's throughput as the number of epochs achieved per second. Figure 12 plots the scaling of the throughput of both MD-GAN and FeGAN with the number of devices. We observe a stable throughput for MD-GAN, which is almost non-sensitive to an increasing number of devices. This is because the single generator on the server has a bounded processing capacity regardless of the number of devices interacting with it. Results show that FeGAN however exhibits a close to perfect scaling. The observed throughput increases linearly with the number of devices, fully leveraging the potential of distributing the training. With 176 devices, FeGAN exhibits a 5× throughput increase over MD-GAN. Note that such scalability also depends on the chosen values for E and C. For instance, we do not expect FeGAN to scale with C = 1, E = 1 as it will incur the same amount of communication as with MD-GAN in this case. Hence, the values of C and E largely control whether the bottleneck is the communication or the computation. Figure 13 presents the results obtained when varying the values of parameters E, the local number of iterations performed on each device in one FL round, and C, the fraction of devices chosen by the server in each round, for FeGAN and MD-GAN (as a baseline) in a 60-device configuration.

We observe that the performances of FeGAN are significantly better in several configurations and in any case at least as good as the ones of MD-GAN, but in the C = 2/15, E = 60 configuration. We believe this latter issue is a pure implementation issue, which we detail in the following. On the one hand, since the server in MD-GAN only averages the devices' updates, we use the reduce abstraction in PyTorch which has an efficient GPU-to-GPU NCCL [START_REF]NVIDIA[END_REF] implementation. On the other hand, we use the gather abstraction with Here, the maximum number of samples at each device is 50.

(ImageNet, 80 devices).

FeGAN to enable KL weighting, i.e., the server first gathers the updates and then applies a weighted sum on them. Such a communication abstraction is not supported on GPUs (todate in PyTorch) and hence, the models are copied to the CPU memory first, leading to slower end-to-end communication.

From the results, we observe that lower values of C give a significant advantage to FeGAN, with one configuration (C = 1/30, E = 60) even performing close to 4 times faster than the MD-GAN configuration. This is explained by the communication overhead between the server and the devices: the lower the value of C, the lower the number of devices chosen per round and hence, the lower the communication overhead. Since the communication overhead is the main bottleneck in distributed machine learning applications in general [START_REF] Hsieh | Geo-distributed machine learning approaching lan speeds[END_REF][START_REF] Xie | Slsgd: Secure and efficient distributed on-device machine learning[END_REF], reducing the communication drastically affects the system throughput, without impacting the convergence as demonstrated in the previous section.

Figure 13 also shows a positive correlation between the value of E and the throughput. The higher the value of E, the more local iterations per device per round, the lower the communication between the server and the devices per unit time and hence, the higher the system's throughput. Note that while studying the impact of the values of C and E gives us some indication, choosing the best values for C and E remains data and model-dependent.

Network bandwidth. Figure 14 shows the impact of Fe-GAN's balanced sampling on the data diversity (number of samples per class) observed by the server as a function of the number of FL rounds. We observe that balanced sampling significantly impacts the training time: it takes FeGAN 10 rounds to come across 500 samples against 10x this figure when random sampling is applied.

The effectiveness of balanced sampling directly translates into network bandwidth gain. Effectively, random sampling has a higher probability to visit the same data batch twice consuming unnecessary bandwidth. Table 1 summarizes the gains in terms of time and communication. This confirms the results displayed in Figure 14. Based on these numbers, random sampling requires around 1.5× more bandwidth, compared to our balanced sampling, per epoch. 1. Time to finish 200 epochs by FeGAN and FLvanilla. With the former, we use balanced sampling while with the latter, we use random sampling. The given two numbers in the first row represent max_class and max_samples respectively. The gain in time to finish one epoch can be also viewed as a gain in consumed bandwidth over random sampling for not looking at diverse data batches. Moreover, as Figure 15 shows, devices in FeGAN consume less bandwidth than with MD-GAN as each device is selected only once every few FL rounds as opposed to MD-GAN in which all devices train the model each round. In this figure, each device is sampled less than 10 times every 200 seconds. Heterogeneous devices. Figure 16 shows an experiment with a set of devices, some of them with limited memory or processing power (we denote those as weak devices). Based on FeGAN's design, such devices are assigned smaller batch sizes (to respect the memory constraints) or less number of local iterations (to respect the limited processing power). In this experiment, weak devices are assigned up to half of the batch size and half of the local number of iterations. The figure also shows the effect of having different ratios of weak devices compared to the total number of devices (in the range of 10-90%). All figures show that the presence of weak devices almost does not affect FeGAN's convergence. This shows the efficiency and the practicality of the adaptive methods included in the design of FeGAN.

Tolerating server crashes. As the central server failure is more critical than the devices' failures, we focus here on the former case. Figure 17 shows an experiment in which we crash the central server after 500 seconds from the beginning of the experiment. In such a case, a backup server loads the latest stored checkpoint, announces to the devices that it is the new primary, and continues the training normally from that checkpoint. The figure shows that the server failure/crash does not cause troubles (e.g., big stalls) to the training process, which continues normally after the crash.

Related Work

Few proposals suggested distributing GANs computation on multiple machines. MD-GAN [START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF] aims at reducing the computation on workers by relying on a single generator, hosted on the central server of the parameter server model. In this setup, every worker hosts a discriminator. Such an architecture then breaks the usual generator-discriminator couple, by setting up a 1-to-n game. The discriminators perform local learning steps on their datasets (that are never shared with other machines) and compute the error feedback on the generated samples they are given by the server. Discriminators are periodically swapped between the workers in a peer-to-peer fashion, in order to avoid overfitting the local datasets. MD-GAN is built with scalability to few tens of workers in mind for targeting the within-datacenter learning scheme; it also only targets the iid distribution of data.

A recent approach by Yonetani et al. [START_REF] Yonetani | Decentralized learning of generative adversarial networks from multi-client non-iid data[END_REF] builds on the architecture of MD-GAN, with also one single generator. They aim at tackling some distribution skew on worker nodes by proposing two independent unsupervised learning approaches: F2U and F2A. F2U is designed to fool the most forgiving discriminator for a given sample (as they judge the sample real and close to the data they own). F2A adaptively aggregates the feedback of discriminators by emphasizing those from the more forgiving ones. Augenstein et al. [START_REF] Augenstein | Generative models 12 for effective ml on private, decentralized datasets[END_REF] proposed a similar federated GAN algorithm but also with one generator at the server and multiple discriminators at the devices. Such an algorithm focuses on the privacy of users' data on devices with the goal of synthesizing data from similar distribution of real data for diagnosis. The scalability of a single generator is here also at stake; we propose instead to have multiple generator-discriminator couples.

Hardy et al. [START_REF] Hardy | Gossiping gans[END_REF] proposed a fully decentralized, peer-topeer architecture for distributing GANs. The authors experimented with GANs being gossiped and averaged between independent devices. While acceptable on small datasets, the performances are observed to be inferior to the baselines we use to evaluate FeGAN with bigger datasets.

Concluding Remarks

We evaluated FeGAN extensively, and here is our conclusion: (i) its careful design allows for scaling the training of GANs. While MD-GAN provides better throughput at a small scale (up to 32 devices), FeGAN then largely prevails, achieving a linear improvement in throughput with the number of devices (experimented with up to 176 devices) with even a lower bandwidth consumption. This scaling does not come at the cost of learning quality; at the opposite, we show lower FID values in both iid data and non-iid data contexts. (ii) We have shown that the proposed components of the FeGAN systems can circumvent GAN specific issues that a vanilla deployment of an FL-based scheme can encounter. In that respect, both the balanced sampling and the KL weighting schemes are instrumental in the effectiveness of FeGAN.

Such components essentially utilize the skew information released by the devices at the beginning of the learning, with regards to their local data. The requirement for extra information might constitute a privacy concern. Yet, recent work has shown how to employ differential privacy with training vanilla federated GANs [START_REF] Xin | Differential privacy synthetic data generation based on federated learning[END_REF]. Exploring approaches that tolerate data imbalance while ensuring full privacy of devices' data is an avenue for future research.

Figure 1 .

 1 Figure 1. (a) A Parameter Server-based deployment[START_REF] Hardy | Multidiscriminator generative adversarial networks for distributed datasets[END_REF] with one generator and distributed discriminators (on 21 machines) outperforms the centralized approach. Yet, (b) it does not scale, due to communication bottlenecks.

Figure 2 .

 2 Figure 2. FeGAN architecture: D and G are co-located on all devices. Dashed lines denote the communication of metadata about devices' dataset and specifications. Data across devices might be unbalanced and skewed.3.1 System SetupFeGAN revisits the general Federated Learning (FL) paradigm[START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF] which consists in (1) a central server (hereafter, server) hosting the up-to-date global model and (2) a set of computing devices that can be mobile phones or computing nodes (hereafter called devices). Figure2depicts the FeGAN architecture. The training model is composed of two neural networks: the generator G and the discriminator D. The server orchestrates the communication load by selecting which devices should contribute to updating the model at a given round. The server is also in charge of aggregating the computation from devices to update the global model. Each group of local iterations (on devices), ending with a global model update, is called an FL round (or simply round). On top of this, training and system specifics are designed to reach our scalability and resilience goals.Each device owns a GAN locally, composed of a local generator and a local discriminator. Data stored on each device remains local: only the output of the local computation is sent to the server. Given its local nature, data might be unbalanced and possibly not identically nor independently distributed (non-iid) across devices. Yet, the server can gather metadata from devices regarding the number of local samples per class. Hence, we assume each device can label its data or at least can model its own data distribution, using generative or clustering schemes like Gaussian Mixture Models (GMM)[START_REF] Richardson | On bayesian analysis of mixtures with an unknown number of components (with discussion)[END_REF][START_REF] Williams | Gaussian processes for regression[END_REF] or K-means[START_REF] Faber | Clustering and the continuous k-means algorithm[END_REF].Devices only communicate with the server. As they do not communicate with each other, they do not need to trust each other. Communication links between the devices and the server could be unreliable and asymmetric with limited bandwidth[START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF]. The server can keep the devices' updates secure using off-the-shelf secure aggregation protocols[START_REF] Bonawitz | Practical secure aggregation for federated learning on user-held data[END_REF].

Figure 3

 3 depicts a running example of FeGAN.

Figure 3 .

 3 Figure 3. Running example of how FeGAN works. Assume a dataset of 50 samples in 4 classes, distributed on 4 devices with C = 0.5. In the first round, the server chooses device 1 (with the highest number of samples) and device 3 (with samples from a class not represented by device 1). When the devices reply, the server updates the model, applying KL_weighting on their replies. In the second round, the server chooses the unsampled devices to maintain fairness and the training continues as usual.

Figure 4

 4 Figure 4. Convergence of FeGAN compared to the Centralized approach and MD-GAN. We distributed the Fashion-MNIST dataset identically and independently (iid) on 80 devices for the distributed deployments. FID metric: the lower, the better the generated samples.

Figure 5 .

 5 Figure 5. Convergence of a few FeGAN configurations in a distributed setup with the Fashion-MNIST dataset distributed identically and independently (iid) on 80 devices.

Figure 6 .Figure 7 .

 67 Figure 6. Convergence of FeGAN in a distributed setup with MNIST; data not distributed identically and independently (non-iid) on devices.

Figure 8 .

 8 Figure 8. Convergence of FeGAN in a distributed setup with ImageNet; data not distributed identically and independently (non-iid) on devices.

Figure 9 .

 9 Figure 9. Convergence of FeGAN with non-iid Fashion-MNIST data distributed on 80 devices, showing all cases of enabling and disabling weighting and sampling schemes.

Figure 10 .

 10 Figure 10. KL-divergence of the real distribution from the distribution seen by the centralized server. The smaller the KL-divergence, the lower the probability of mode collapse.

Figure 11 .

 11 Figure 11. The co-location of both networks on all nodes avoids yielding a powerful discriminator (as in MD-GAN), preventing the problem of vanishing gradients to happen.

Figure 12 .

 12 Figure 12. Scalability with the number of devices.

Figure 13 .

 13 Figure 13. The impact of the values of E and C (60 devices).

Figure 14 .

 14 Figure 14. Average number of samples per class seen by the server, through devices' updates, as a function of FL rounds. Here, the maximum number of samples at each device is 50. (ImageNet, 80 devices).

Figure 15 .Figure 16 .

 1516 Figure 15. Bandwidth consumption at one random device for both MD-GAN and FeGAN. We observe the same distribution (as plotted) at different sampled devices. Using FeGAN, each device is picked (by the server), on average, less than 10 times in a 200-second interval.

Figure 17 .

 17 Figure 17. FeGAN tolerates server crash.

We tried other normalization schemes (e.g., linear averaging and step-wise averaging), and we found that softmax normalization gives the best results.

This is only true if the used abstraction is implemented by NCCL; otherwise, we use the GLOO[START_REF] Gloo | [END_REF] backend.

https://pytorch.org/docs/stable/distributed.html.

https://github.com/eriklindernoren/PyTorch-GAN.

Note that we could not arbitrarily increase the training batch size on the centralized setup, that is prone to memory constraints.

Note that we run both systems for the same amount of time per experiment; that is why the lines in all sub-figures b are balanced, unlike sub-figures a.

Acknowledgement

We thank Georgios Damaskinos for his useful comments.


Georgios Damaskinos
email: georgios.damaskinos@epfl.ch

Rachid Guerraoui
email: rachid.guerraoui@epfl.ch

Erwan Le Merrer
email: erwan.le-merrer@inria.fr

Christoph Neumann
email: christoph.neumann@interdigital.com

The Imitation Game: Algorithm Selection by Exploiting Black-Box Recommenders

Keywords: Recommender algorithm selection, Black-box exploitation, Crossvalidation, Graph similarity, Spearman ranking

Cross-validation is commonly used to select the recommendation algorithms that will generalize best on yet unknown data. Yet, in many situations the available dataset used for cross-validation is scarce and the selected algorithm might not be the best suited for the unknown data. In contrast, established companies have a large amount of data available to select and tune their recommender algorithms, which therefore should generalize better. These companies often make their recommender systems available as black-boxes, i.e., users query the recommender through an API or a browser. This paper proposes RECRANK, a technique that exploits a black-box recommender system, in addition to classic cross-validation. RECRANK employs graph similarity measures to compute a distance between the output recommendations of the black-box and of the considered algorithms. We empirically show that RECRANK provides a substantial improvement (33%) for the selection of algorithms for the MovieLens dataset, in comparison with standalone cross-validation.

Introduction

The availability of open source recommendation algorithms and engines is appealing for startups or institutions that bootstrap their online services. A plethora of approaches, from collaborative filtering techniques to neural network based approaches are now at disposal 4 , along with the deluge of research results that are thoroughly described (but not open-sourced). The users of online services generate a huge volume of data thus triggering the advantage shift from solely leveraging a good item recommendation algorithm, to having access to both a good algorithm and a considerable amount of data for training or parameterizing it. In that context, it is clear that the big industrial players, have a steady and decisive advantage over potential newcomers on the market since they have both significant engineering work-forces and a large audience to get data from. Those established companies propose recommendation services, that interact with users through queries from browser-interactions or standard APIs. The recommendation algorithm acts as a black-box from the perspective of the user, and for potential observers such as those newcomers.

We present RECRANK, a method to sort a list of available recommendation algorithms based on their ability to generalize on unknown data. In stark contrast with cross-validation, this method exploits the recommendations of an established black-box recommender, and captures how well each of the available recommendation algorithms imitates the black-box recommender. We evaluate RECRANK and depict its superiority against classic cross-validation and an alternative ranking method. Our code is available [START_REF]RECRANK source-code[END_REF].

Problem setting. Let D be the corpus of data that the recommender interacts with. This data includes tuples of the form u, i, l where a user u gives feedback l (implicit or explicit) for a certain item i. We split D into three parts:

D = {D a ∪ D b ∪ D u }.
On the one hand, an entity (e.g., a startup) targets to bootstrap a recommender. This entity has access to an available dataset D a , typically limited in size. This entity has also access to a set of open-sourced or in-house candidate recommendation algorithms, and needs to select the ones that will generalize best (i.e., provide good recommendations) on an unknown dataset D u .

On the other hand, a well-established recommendation service (e.g., IMDB, Spotify) enables queries to its recommender, typically through an API. We assume that the well-established recommender was trained using a private (i.e., available only to itself) dataset D b (typically significantly larger than D a ) and a private algorithm. This algorithm is a black-box to a user, and we denote it as f (D b ). The inputs to the blackbox recommender are queries of the form u, i, l and the output is a ranked list of the top-N recommendations for user u, typically based on knowledge of the black-box recommender regarding u and i. For example, users make queries such as user, song, click (Spotify), user, video, like (YouTube) or user, movie, rating (IMDB) and get a ranked list of recommendations such as "Made for Alice" (Spotify), "Up next" (YouTube) or "Recommended For You" (IMDB), respectively.

Let A be the set of considered recommendation algorithms, along with their hyperparameters. We define P A (D) ∈ R as the performance measure of an algorithm A ∈ A given a dataset D (e.g., the precision of A after splitting D into a training and validation set). Let K be any side knowledge. We consider r(A, D, K) to be a ranking function producing a sorted array

[A 0 , A 1 , . . . , A n-1 ], such that P A0 (D) ≥ P A1 (D) ≥ • • • ≥ P An-1 (D).
Each algorithm in A is solely trained and cross-validated using D a . We define the optimal ranking as r * := r(A, D a ∪ D u , ∅), i.e., the perfect ranking for the available trained algorithms after taking into account the yet unknown data D u .

Black-box exploitation. We define the problem of exploiting a black-box recommender for algorithm selection as finding the ranking:

r := arg max r ρ(r * , r (A, D a , f (D b ))) (1)
with ρ being the Spearman ranking correlation score ( §3). The goal is to obtain side knowledge from the black-box in order to produce a ranking that gets closer to the optimal ranking. Our working hypothesis is that:

ρ(r * , r(A, D a , f (D b )) > ρ(r * , r(A, D a , ∅))) (2)
i.e., there exists a gain (in comparison with cross-validation) from the information f (D b ) leaked from the black-box. Noteworthy, the option of building a proxy recommender that always employs the black-box is not practical. Sending all the data to the black-box implies potential privacy violations as the user feedback (e.g., movie ratings) is forwarded to a third-party. From the system performance perspective, there are significant additional bandwidth costs and the service throughput is bounded by the query APIs limits (e.g., IMDB via RapidAPI has a limit of 1000 requests per day [START_REF]IMDB via RAPIDAPI query limit[END_REF]). Therefore, the goal is to bootstrap the service and then only utilize the selected algorithm locally.

RECRANK

We introduce, RECRANK, a ranking function that exploits the outputs of a black-box (series of top-N recommendations) to compute a distance between each algorithm in A and a black-box recommender, under the assumption that the black-box generalizes better due to its larger dataset (we validate this assumption in §3). The final ranking of RECRANK follows the ascending order of this distance: the better an algorithm imitates the black-box, the higher its ranking.

RECRANK consists of two components as shown in Figure 1. REC2GRAPH transforms the output of a recommender into a graph data structure. The graph obtained from the outputs of the black-box is compared to the graph obtained from the outputs of each algorithm in A, in order to compute a distance D with GRAPHDIST. The graph representation captures latent information about the recommender outputs (e.g., popularity of certain items among different subsets of users). This information is important for the performance of RECRANK, as we empirically show in §3 by using a baseline that directly compares the outputs of the two algorithms. RECRANK is shown in Algorithm 1, where get rec(X, D q ) returns the top-N recommendations of algorithm X given inputs in query dataset D q . Fig. 1: Core components of RECRANK. Algorithm A is each algorithm in set A using the available dataset D a , while B is the black-box recommender. RECRANK builds a graph for each algorithm using REC2GRAPH and computes a distance between graphs using GRAPHDIST.

Algorithm 1: RECRANK Input: Candidate algorithm set A, black-box B, query set D q 1 G b = REC2GRAPH (get rec(B, D q )) 2 for A in A do 3 G a = REC2GRAPH (get rec(A, D q )) 4 D(A, B) = GRAPHDIST (G a , G b ) 5 distances.

append(D(A, B))

6 end 7 return sort(distances) REC2GRAPH. This method transforms the output of the queried recommender into a graph. Building a graph from recommendations was recently shown to be interesting for several applications [START_REF] Merrer | The topological face of recommendation: models and application to bias detection[END_REF][START_REF] Hou | Navigated random walks on amazon book recommendation network[END_REF]. For each query u, i, l in the query dataset, we denote as D q , the recommender outputs a list of the top-N recommendations. REC2GRAPH constructs the graph according to the following rules.

-Vertex i: There exists a recommendation for item i and/or there exists a query for item i in D q (e.g., a movie rating).

-Edge e ij : Item j is at least in one of the top-N recommendation lists given as an output to a query for item i.

-Weight w ij = e ij ranking score e∈E e ranking score
where eij ranking score is the summation of the recommender output over all recommendations for item j triggered by a query for item i. 5The edge weight captures the fact that there are typically multiple recommendations between the same items. For example, a user might receive the same item in multiple top-N recommendations before she either clicks it or the recommender lowers its ranking and removes it from the top-N list. The denominator normalizes each weight in order for the graphs of different algorithms to be comparable, given that the scores of each recommender have different scales.

GRAPHDIST. In order to compare the two graphs, GRAPHDIST extracts a set of features for each graph (denoted as X A and X B ) and computes the distance between the two algorithms:

D(A, B) := X A -X B (3)
GRAPHDIST extracts features that capture the state of the algorithm recommendations. For the features that involve distributions, we employ statistical values depending on whether we assume a Gaussian prior or not. We list a subset of these features below, and note that X ∈ R 31 ; the full set of extracted features is available in our code [START_REF]RECRANK source-code[END_REF].

-Number vertices and number of edges. These illustrate the number of distinct recommendations. -Vertex in-degree. This shows how polarized the recommendations are, i.e., how many popular items are recommended and how much is their popularity. -PageRank. This indicates the PageRank centrality in the graph of the recommended items. -Eigenvector and betweeness centrality. These centrality measures show how many items are the most central, i.e., most popular among the recommendations. -Closeness centrality. This also captures the topological proximity of a given item to the others in the graph. -Assortativity. This shows the connectivity between nodes of similar degree, i.e., how much popular items are connected to other popular items. -Shortest distances. For each vertex, we compute the mean value of its shortest distances with each other vertex. We then average these mean values across all vertexes. This feature captures how close each item node is to the others.

The construction of GRAPHDIST makes RECRANK interpretable. Given the output of RECRANK, one can determine the contributing factor of each feature to this output. For example, if the Vertex in-degree feature has a very similar value for the candidate algorithm and the black box (i.e., contribution to the distance is minimal) comparing to the other features, then one can conclude that recommending popular items is an important factor for the final rank (output of RECRANK) of this candidate algorithm.

Evaluation

We study the performance of RECRANK on the MovieLens dataset6 that consists of 100,000 ratings from 943 users on 1682 movies. 1. We consider that a different implementation of the same algorithm constitutes a new candidate recommendation algorithm (e.g., KNNlib and KN-NWithMeans): the output recommendations depend on various factors that differ among the two libraries (e.g., the formula for calculating the rating prediction). Additionally, we include two versions of the PMF algorithm (denoted as PMFlib and PMF2lib) with a different hyper-parameter tuning setup. Therefore, we illustrate that a different tuning (that can be the result of a difference in the resources for the A/B testing phase) leads to a different recommendation behavior (Table 2), thus to a different candidate recommendation algorithm.

Evaluation metrics. We now describe the metrics used for reflecting the performance of the candidate recommender and for demonstrating the efficacy of RECRANK. Precision. We adopt this metric to test the accuracy of the recommendations. Given that H u is the set of recommended items that were clicked by a user u (hits), and R u is the set of items recommended to u, we denote the precision for u by P recision u and define it as follows.

P recision u = |H u | |R u | (4)
The overall precision over the whole test set is the average over the precision values for all users in the test set. Note that a recommended item is considered as a hit, if the user rates that item anytime later than the time of the recommendation with a rating score larger than 50% of the maximum score [START_REF] Damaskinos | Capturing the moment: Lightweight similarity computations[END_REF].

Recall. We use this metric to capture the sensitivity of a recommender to the frequency of updates. Given that C u is the set of items clicked by a user u, we denote the recall for u by Recall u and define it as follows.

Recall u = |H u | |C u | (5)
The overall recall is the average over the recall values for all the users in the test set. F1-score. We employ this standard metric to measure the recommendation accuracy in order to combine the precision and recall into a single score.

F 1 u = 2 * P recision u * Recall u P recision u + Recall u
Spearman correlation. We use this metric to evaluate the ranking quality of RECRANK. Moreover, we compute the Spearman rank-order correlation coefficient between the output ranking and the optimal ranking r * , i.e., the ranking after evaluating the candidates on the dataset D u . A value of 0 indicates no correlation and a value of 1 an exact monotonic relationship; thus the higher the value of this metric, the better the performance. We compute this metric as follows:

ρ = 1 - 6 d 2 i n(n 2 -1) , 1 ≤ i ≤ C (6)
where d i = rank(A i ) -optimal rank(A i ), is the difference between the two ranks for each candidate algorithm and n is the number of candidates. The impact of an ordering mismatch does not depend on the rank of the mismatch. For example, the Spearman correlation between {1,2,3,4} and {1,2,4,3} is the same as {1,2,3,4} and {2,1,4,3}. This ensures an equal weight for all the ranked candidates based on the fact that the entity that employs RECRANK can have access to any subset of these candidates.

Evaluation scheme. We replay the dataset, ordered by the timestamp, to capture the original temporal behavior. We split the dataset into D a , D b , D u , D q , according to D a , i.e., most recent 1000 ratings, based on the benchmark for evaluating stream-based recommenders [START_REF] Kille | Overview of clef newsreel 2015: News recommendation evaluation lab[END_REF]). Further information regarding our training setup (e.g., choice of hyperparameters) is available in our open-source repository [START_REF]RECRANK source-code[END_REF].

Baselines. We compare RECRANK with the traditional ranking approach (i.e., crossvalidation) along with a baseline algorithm, namely SETDISTRANK. SETDISTRANK computes the distance between algorithms directly from their outputs (i.e., without the REC2GRAPH and GRAPHDIST methods). The comparison with SETDISTRANK illustrates the importance of these two methods for the performance of RECRANK. SETDIS-TRANK computes the distance as follows:

D(A, B) = | u∈U Recommended u | + | i∈I Recommended i | 2 ( 7
)
where U is the set of users and I is the set of items. Recommended u is the per-user recommendation set, i.e., the set of all the items recommended after a query from user u. u∈U Recommended u denotes the intersection among all the per-user recommendation sets of the algorithms A, B. Recommended i is defined respectively.

Experimental results. We train the candidate recommendation algorithms (Table 1) by using the data scheme in Figure 2 and present the results in Table 2. First, we observe that the ranking derived from cross-validation on D u (2nd column) is different than the optimal ranking (3rd column). Therefore, there is room for RECRANK to get a better ranking. We train all the algorithms with the black-box dataset D b in order to select the black-box recommender. According to the results shown in the 4th column, this algorithm is LLORMAlib. The 5th column contains the results when training each algorithm on the training set and evaluating on the query set D q , which constitutes the comparison case for all presented competitors. We compare the performance of the ranking algorithms by comparing the Spearman correlation with respect to the third column of Table 2. Table 3 depicts the results. The poor performance of the cross-validation on the query set D q can be attributed to the chronological sorting of the ratings; the cross-validation becomes accurate if the validation and training set are closer in time and thus have significant overlap in the user sets. We then observe the substantial improvement (33%) that RECRANK provides in comparison with the standard cross-validation. The fact that SETDISTRANK also outperforms the cross-validation approach confirms that the information provided by the black-box recommender is valuable even without REC2GRAPH and GRAPHDIST. Figure 3 depicts the effect that the size of the query set has to the performance of RECRANK. As the portion of D q used to query recommenders increases, RECRANK exploits more information to compute better distance values, resulting in a better final ranking. The results of Table 3 have been obtained with a query set D q by sampling 50% of D u (1000 out of 2000 ratings shown in Figure 2).

Related Work

RECRANK proceeds by comparing the outputs of recommenders similar to benchmarking frameworks [START_REF] Kowald | The tagrec framework as a toolkit for the development of tag-based recommender systems[END_REF][START_REF] Said | Rival: a toolkit to foster reproducibility in recommender system evaluation[END_REF]. These frameworks enable the ranking of a set of recommendation algorithms according to some metric (e.g., F1-score) -similar to what RECRANK does based on D a and the output of a black-box service. These frameworks do not allow to compare against the output recommendations of a black-box service that has been trained and tuned on an unknown set of data.

Evaluation of recommenders is very challenging when using offline datasets such as MovieLens. We plan to evaluate RECRANK with additional metrics such as propensityweighting techniques [START_REF] Agarwal | Offline comparison of ranking functions using randomized data[END_REF], as well as employ alternative online methodologies and user studies [START_REF] Beel | A comparison of offline evaluations, online evaluations, and user studies in the context of research-paper recommender systems[END_REF]. We also plan to include additional baselines to the standard (i.e., leave-oneout) cross-validation, e.g., based on k-fold validation [START_REF] Košir | How to improve the statistical power of the 10-fold cross validation scheme in recommender systems[END_REF]. Nevertheless, the functionality of RECRANK is independent of the evaluation methodology.

Black-box analysis of recommendation algorithms has been also studied for the goal of algorithmic transparency. Xray [START_REF] Lécuyer | Xray: Enhancing the web's transparency with differential correlation[END_REF] infers which user data (e.g. e-mails, searches) a recommender is using. Le Merrer et al. [START_REF] Merrer | The topological face of recommendation: models and application to bias detection[END_REF] propose a framework for detecting bias in recommended items. Hou et al. [START_REF] Hou | Navigated random walks on amazon book recommendation network[END_REF] proposed to operate random walks on the graph extracted from the recommendations to a user by the Amazon book platform. While these related works try to understand how the remote recommender system works, they do not try build their own recommendation system (i.e. they do not try to benefit from the gained insights to tune a recommender) .

Imitation learning [START_REF] Hussein | Imitation learning: A survey of learning methods[END_REF] and knowledge distillation [START_REF] Polino | Model compression via distillation and quantization[END_REF][START_REF] Hinton | Distilling the knowledge in a neural network[END_REF] apply the broad idea of learning a policy, a reward function or prediction function by observing an expert system. In that sense, RECRANK is the first attempt to improve the selection of a recommender algorithm by imitating an expert recommender system, typically in production.

RECRANK targets to boost the recommendation quality given a limited amount of data, a problem also known as cold-start. Techniques that boost the quality of a specific recommender, e.g., transfer learning [START_REF] Pan | Transfer learning in collaborative filtering for sparsity reduction[END_REF], or meta-learing [START_REF] Vartak | A meta-learning perspective on cold-start recommendations for items[END_REF] can be used for creating better candidate recommendation algorithms as input to RECRANK.

Discussion and Limitations

It is important to notice that, while RECRANK is the first tool to exploit black-box recommender systems for algorithm selection, we do not claim it to be a silver bullet. We discuss the limitations of our work in the following.

Black-box recommender bias. The recommendations of the black-box during the operation of RECRANK may be biased, i.e., not solely targeting the relevance to the users. For example, a commercial music recommender may promote songs from certain premium producers with the goal of direct financial gain. As a second example, the black-box may be a relatively new service that undergoes an A/B testing phase or some "exploration" phase (e.g., with random recommendations). In such cases, we expect RECRANK to output a biased ranking. Given that it is impossible for the user of RECRANK to determine whether the black-box is biased at a given time, we propose multiple deployments of RECRANK across different times. The similarities between the outputs of these deployments could help indicate the deployments that are biased; if the bias is not transient, multiple deployments will not be effective.

Advancing the state-of-the-art. The goal of RECRANK is not to directly create new recommendation algorithms but to select the most promising ones among a list of candidates. Nevertheless, this selection could be instrumental in developing a new state-ofthe-art recommender that is an ensemble of multiple recommendation algorithms. For example, the cold-start component could be intentionally designed to mimic the coldstart behaviour of a well-established service; in that case RECRANK would be of great interest.

Local VS black-box data. A question that may arise in our problem setup is whether there are any constraints for the relation between the training data of the candidate algorithms (local) and the training data of the black-box. In our evaluation ( §3), this relation is that the data has no overlap but comes from the same dataset, i.e., the user rating behaviour follows the preference and behavioural drifts of the MovieLens dataset [START_REF] Damaskinos | Capturing the moment: Lightweight similarity computations[END_REF]. We plan to evaluate the performance of RECRANK under alternative relation scenarios (e.g., the data comes from different datasets) as part of our future work.

We expect the performance of RECRANK to degrade as the difference between the characteristics (e.g., how frequent are popular items rated and with what scores) of the local and black-box training data grows. Nevertheless, we highlight that the operation of RECRANK does not have any constraints regarding the training data as the query data is the same both for the candidate algorithms and the black-box. The smaller the relevance between the query data and the training data, the less the performance degradation of RECRANK due to differences in the training data. For example, if the query data only contains new users and new items, then RECRANK is essentially imitating the cold-start behaviour of the black-box and we thus do not expect differences in the training data to significantly degrade RECRANK performance.

The only requirement is for the input and output format of the query dataset to be compliant with the black-box. This requirement is easily satisfied given our generic form of input (tuples of the form u, i, l ) and output (ranking list of top-N recommendations) as mentioned in §1.

Concluding remarks

We present RECRANK, an algorithm that facilitates recommender algorithm selection, traditionally made solely via cross-validation. Our initial results show a promising potential for this tool. Nevertheless, these results do not constitute an in-depth experimental validation and there is work towards measuring the true potential of RECRANK. We also plan to compare REC2GRAPH with alternative methods for transforming the recommender outputs into graphs [START_REF] Merrer | The topological face of recommendation: models and application to bias detection[END_REF][START_REF] Hou | Navigated random walks on amazon book recommendation network[END_REF]. Finally, We propose RECRANK as one instance of an algorithm that exploits a black-box recommender; we believe this proposal will motivate related works for finding other good performing alternatives with a similar goal.

Fig. 2 :

 2 Fig. 2: Chronological data split for MovieLens. The first part is used for D a , the largest part for the black-box D b , and the last part is the yet unknown data D u .

Fig. 3 :

 3 Fig. 3: Effect of the amount of queries on the performance of RECRANK.

Table 1 :

 1 Candidate recommendation algorithms. Information regarding the hyperparameters is available in our open-source repository[START_REF]RECRANK source-code[END_REF]. We collect recommendation algorithms from opensource libraries: 14 algorithms from Librec 7 and 5 algorithms from SurpriseLib 8 , as summarized in Table

	Library	Model-based	Memory-based Baselines
	Librec	AOBPR, BIASEDMFlib,	KNNlib	MPOPlib,
		BPMFlib, EALSlib, LDAlib,		RANDlib
		LLORMAlib, NMFlib,
		SVDPPlib, PMF2lib
		PMFlib, RBMlib
	Surpriselib NMF, PMF, SVD, SVDpp KNNWithMeans
	Recommendation algorithms.

Table 2 :

 2 F1 @ top-20 recommendations (and rank) of candidate algorithms (black-box algorithm is in bold).

		Standard	Optimal	Black-box	Cross-validation
		cross-validation ranking	ranking	on query set
	Training set Evaluation set	D training a D validation a	D training a D u	D b D u	D training a D q
	AOBPRlib	0.213 (4)	0.087 (5) 0.156 (5) 0.046 (4)
	BIASEDMFlib 0.136 (9)	0.054 (11) 0.057 (11) 0.028 (13)
	BPMFlib	0.618 (1)	0.419 (2) 0.408 (2) 0.374 (2)
	EALSlib	0.197 (7)	0.084 (7) 0.138 (6) 0.046 (4)
	KNNlib	0.206 (6)	0.085 (6) 0.126 (7) 0.046 (4)
	KNNWithMeans 0.039 (19)	0.024 (18) 0.027 (15) 0.016 (18)
	LDAlib	0.210 (5)	0.095 (4) 0.164 (4) 0.046 (4)
	LLORMAlib	0.611 (2)	0.420 (1) 0.412 (1) 0.377 (1)
	MPOPlib	0.188 (8)	0.074 (9) 0.115 (8) 0.042 (8)
	NMF	0.115 (13)	0.048 (15) 0.023 (16) 0.032 (11)
	NMFlib	0.045 (18)	0.016 (19) 0.002 (19) 0.012 (19)
	PMF	0.083 (16)	0.043 (16) 0.016 (18) 0.022 (17)
	PMF2lib	0.133 (10)	0.076 (8) 0.058 (10) 0.037 (9)
	PMFlib	0.106 (15)	0.050 (13) 0.030 (14) 0.027 (14)
	RANDlib	0.083 (16)	0.039 (17) 0.023 (16) 0.024 (16)
	RBMlib	0.565 (3)	0.398 (3) 0.403 (3) 0.358 (3)
	SVD	0.123 (11)	0.049 (14) 0.059 (9) 0.033 (10)
	SVDpp	0.120 (12)	0.052 (12) 0.051 (12) 0.031 (12)
	SVDpplib	0.109 (14)	0.055 (10) 0.031 (13) 0.027 (14)

Table 3 :

 3 Candidate algorithms ranking evaluation.

	Ranking method	Spearman correlation
	Standard cross-validation	0.53
	Cross-validation on query set -0.44
	SETDISTRANK	0.68
	RECRANK	0.79

https://github.com/grahamjenson/list_of_recommender_systems

If the recommender only outputs a top-N list, the output for each item is the rank (e.g., value ∈[START_REF]RECRANK source-code[END_REF][START_REF] Damaskinos | Capturing the moment: Lightweight similarity computations[END_REF] for top-5 outputs).

http://grouplens.org/datasets/movielens/

https://www.librec.net/

https://www.surpriselib.com/