Gwendoline De Bie
email: debie@dma.ens.fr

Herilalaina Rakotoarison

Gabriel Peyré
email: gabriel.peyre@ens.fr

Michele Sebag
email: sebag@lri.fr

Distribution-Based Invariant Deep Networks for Learning Meta-Features

Recent advances in deep learning from probability distributions successfully achieve classification or regression from distribution samples, thus invariant under permutation of the samples. The first contribution of the paper is to extend these neural architectures to achieve invariance under permutation of the features, too. The proposed architecture, called Dida, inherits the NN properties of universal approximation, and its robustness w.r.t. Lipschitz-bounded transformations of the input distribution is established. The second contribution is to empirically and comparatively demonstrate the merits of the approach on two tasks defined at the dataset level. On both tasks, Dida learns meta-features supporting the characterization of a (labelled) dataset. The first task consists of predicting whether two dataset patches are extracted from the same initial dataset. The second task consists of predicting whether the learning performance achieved by a hyper-parameter configuration under a fixed algorithm (ranging in k-NN, SVM, logistic regression and linear SGD) dominates that of another configuration, for a dataset extracted from the OpenML benchmarking suite. On both tasks, Dida outperforms the state of the art: DSS [23] and Dataset2Vec [16] architectures, as well as the models based on the hand-crafted meta-features of the literature.

Introduction

Deep networks architectures, initially devised for structured data such as images [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and speech [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF], have been extended to enforce some invariance or 1 arXiv:2006.13708v2 [stat.ML] 18 Oct 2020 equivariance properties [START_REF] Shawe-Taylor | Symmetries and discriminability in feedforward network architectures[END_REF] for more complex data representations. Typically, the network output is required to be invariant with respect to permutations of the input points when dealing with point clouds [START_REF] Qi | Deep learning on point sets for 3d classification and segmentation[END_REF], graphs [START_REF] Henaff | Deep convolutional networks on graph-structured data[END_REF] or probability distributions [START_REF] De Bie | Stochastic deep networks[END_REF]. The merit of invariant or equivariant neural architectures is twofold. On the one hand, they inherit the universal approximation properties of neural nets [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF]. On the other hand, the fact that these architectures comply with the requirements attached to the data representation yields more robust and more general models, through constraining the neural weights and/or reducing their number.

Related works. Invariance or equivariance properties are relevant to a wide range of applications. In the sequence-to-sequence framework, one might want to relax the sequence order [START_REF] Vinyals | Order matters: Sequence to sequence for sets[END_REF]. When modelling dynamic cell processes, one might want to follow the cell evolution at a macroscopic level, in terms of distributions as opposed to, a set of individual cell trajectories [START_REF] Hashimoto | Learning populationlevel diffusions with generative rnns[END_REF]. In computer vision, one might want to handle a set of pixels, as opposed to a voxellized representation, for the sake of a better scalability in terms of data dimensionality and computational resources [START_REF] De Bie | Stochastic deep networks[END_REF].

Neural architectures enforcing invariance or equivariance properties have been pioneered by [START_REF] Qi | Deep learning on point sets for 3d classification and segmentation[END_REF][START_REF] Zaheer | Deep sets[END_REF] for learning from point clouds subject to permutation invariance or equivariance. These have been extended to permutation equivariance across sets [START_REF] Hartford | Deep models of interactions across sets[END_REF]. Characterizations of invariance or equivariance under group actions have been proposed in the finite [START_REF] Gens | Deep symmetry networks[END_REF][START_REF] Cohen | Group equivariant convolutional networks[END_REF][START_REF] Ravanbakhsh | Equivariance through parameter-sharing[END_REF] or infinite case [START_REF] Wood | Representation theory and invariant neural networks[END_REF][START_REF] Kondor | On the generalization of equivariance and convolution in neural networks to the action of compact groups[END_REF].

On the theoretical side, [START_REF] Maron | Invariant and equivariant graph networks[END_REF][START_REF] Keriven | Universal invariant and equivariant graph neural networks[END_REF] have proposed a general characterization of linear layers enforcing invariance or equivariance properties with respect to the whole permutation group on the feature set. The universal approximation properties of such architectures have been established in the case of sets [START_REF] Zaheer | Deep sets[END_REF], point clouds [START_REF] Qi | Deep learning on point sets for 3d classification and segmentation[END_REF], equivariant point clouds [START_REF] Segol | On universal equivariant set networks[END_REF], discrete measures [START_REF] De Bie | Stochastic deep networks[END_REF], invariant [START_REF] Maron | On the universality of invariant networks[END_REF] and equivariant [START_REF] Keriven | Universal invariant and equivariant graph neural networks[END_REF] graph neural networks. The approach most related to our work is that of [START_REF] Maron | On learning sets of symmetric elements[END_REF], handling point clouds and presenting a neural architecture invariant w.r.t. the ordering of points and their features. In this paper, the proposed distribution-based invariant deep architecture (Dida) extends [START_REF] Maron | On learning sets of symmetric elements[END_REF] as it handles (discrete or continuous) probability distributions instead of point clouds. This enables to leverage the topology of the Wasserstein distance to provide more general approximation results, covering [START_REF] Maron | On learning sets of symmetric elements[END_REF] as a special case.

Motivations. A main motivation for Dida is the ability to characterize datasets through learned meta-features. Meta-features, aimed to represent a dataset as a vector of characteristcs, have been mentioned in the ML literature for over 40 years, in relation with several key ML challenges: (i) learning a performance model, predicting a priori the performance of an algorithm (and the hyper-parameters thereof) on a dataset [START_REF] Rice | The algorithm selection problem[END_REF][START_REF] Wolpert | The lack of A priori distinctions between learning algorithms[END_REF][START_REF] Hutter | Automated Machine Learning: Methods, Systems, Challenges[END_REF]; (ii) learning a generic model able of quick adaptation to new tasks, e.g. one-shot or few-shot, through the so-called meta-learning approach [START_REF] Finn | Probabilistic model-agnostic metalearning[END_REF][START_REF] Yoon | Bayesian model-agnostic meta-learning[END_REF]; (iii) hyper-parameter transfer learning [START_REF] Perrone | Scalable hyperparameter transfer learning[END_REF], aimed to transfer the performance model learned for a task, to another task.

A large number of meta-features have been manually designed along the years [START_REF] Muñoz | Instance spaces for machine learning classification[END_REF], ranging from sufficient statistics to the so-called landmarks [START_REF] Pfahringer | Metalearning by landmarking various learning algorithms[END_REF], computing the performance of fast ML algorithms on the considered dataset. Meta-features, expected to describe the joint distribution underlying the dataset, should also be inexpensive to compute. The learning of meta-features has been first tackled by [START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF] to our best knowledge, defining the Dataset2Vec representation. Specifically, Dataset2Vec is provided two patches of datasets, (two subsets of examples, described by two (different) sets of features), and is trained to predict whether those patches are extracted from the same initial dataset.

Contributions. The proposed Dida approach extends the state of the art [START_REF] Maron | On learning sets of symmetric elements[END_REF][START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF] in two ways. Firstly, it is designed to handle discrete or continuous probability distributions, as opposed to point sets (Section 2). As said, this extension enables to leverage the more general topology of the Wasserstein distance as opposed to that of the Haussdorf distance (Section 3). This framework is used to derive theoretical guarantees of stability under bounded distribution transformations, as well as universal approximation results, extending [START_REF] Maron | On learning sets of symmetric elements[END_REF] to the continuous setting. Secondly, the empirical validation of the approach on two tasks defined at the dataset level demonstrates the merit of the approach compared to the state of the art [START_REF] Maron | On learning sets of symmetric elements[END_REF][START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF][START_REF] Muñoz | Instance spaces for machine learning classification[END_REF] (Section 4).

Notations.

[m] denotes the set of integers {1, . . . m}. Distributions, including discrete distributions (datasets) are noted in bold font. Vectors are noted in italic, with x[k] denoting the k-th coordinate of vector x.

Distribution-Based Invariant Networks for Meta-Feature Learning

This section describes the core of the proposed distribution-based invariant neural architectures, specifically the mechanism of mapping a point distribution onto another one subject to sample and feature invariance, referred to as invariant layer. For the sake of readability, this section focuses on the case of discrete distributions, referring the reader to Appendix A for the general case of continuous distributions. = S d X × S d Y denote the group of permutations independently operating on the feature and label spaces. For σ = (σ X , σ Y ) ∈ G, the image σ(z) of a labelled sample is defined as

Invariant Functions of Discrete Distributions

Let z= {(x i , y i ) ∈ R d , i ∈ [n]} denote a dataset including n labelled samples, with x i ∈ R d X an
(σ X (x), σ Y (y)), with x = (x[k], k ∈ [d X ]) and σ X (x) def. = (x[σ -1 X (k)], k ∈ [d X ]
). For simplicity and by abuse of notations, the operator mapping a distribution z = (z i , i

∈ [n]) to {σ(z i )} def. = σ z is still denoted σ.
Let Z(Ω) denote the space of distributions supported on some domain Ω ⊂ R d , with Ω invariant under permutations in G. The goal of the paper is to define and train deep architectures, implementing functions ϕ on Z(Ω ⊂ R d ) that are invariant under G, i.e. such that ∀σ ∈ G, ϕ(σ z) = ϕ(z) 1 . By construction, a multi-label dataset is invariant under permutations of the samples, of the features, and of the multi-labels. Therefore, any meta-feature, that is, a feature describing a multi-label dataset, is required to satisfy the above property.

Distribution-Based Invariant Layers

The building block of the proposed architecture, the invariant layer meant to satisfy the feature and label invariance requirements, is defined as follows, taking inspiration from [START_REF] De Bie | Stochastic deep networks[END_REF].

Definition 1. (Distribution-based invariant layers) Let an interaction functional

ϕ : R d × R d → R r be G-invariant: ∀σ ∈ G, ∀(z 1 , z 2 ) ∈ R d × R d , ϕ(z 1 , z 2 ) = ϕ(σ(z 1 ), σ(z 2 )).
The distribution-based invariant layer f ϕ is defined as

f ϕ : z = (z i ) i∈[n] ∈ Z(R d ) → f ϕ (z) def. =   1 n n j=1 ϕ(z 1 , z j ), . . . , 1 n n j=1 ϕ(z n , z j )   ∈ Z(R r ). (1)
It is easy to see that f ϕ is G-invariant. The construction of f ϕ is extended to the general case of possibly continuous probability distributions by essentially replacing sums by integrals (Appendix A).

Remark 1. (Varying sample size n). By construction, f ϕ is defined on Z(R d ) = ∪ n Z n (R d ) (independent of n),
such that it supports inputs of arbitrary cardinality n. Remark 2. (Discussion w.r.t. [START_REF] Maron | On learning sets of symmetric elements[END_REF]) The above definition of f ϕ is based on the aggregation of pairwise terms ϕ(z i , z j ). The motivation for using a pairwise ϕ is twofold. On the one hand, capturing local sample interactions allows to create more expressive architectures, which is important to improve the performance on some complex data sets, as illustrated in the experiments (Section 4). On the other hand, interaction functionals are crucial to design universal architectures (Appendix C, theorem 2). The proposed theoretical framework relies on the Wasserstein distance (corresponding to the convergence in law of probability distributions), which enables to compare distributions with varying number of points or even with continuous densities. In contrast, [START_REF] Maron | On learning sets of symmetric elements[END_REF] do not use interaction functionals, and establish the universality of their DSS architecture for fixed dimension d and number of points n. Moreover, DSS happens to resort to max pooling operators, discontinuous w.r.t. the Wasserstein topology (see Remark 5).

Two particular cases are when ϕ only depends on its first or second input:

(i) if ϕ(z, z ) = ψ(z ), then f ϕ computes a global "moment" descriptor of the input, as f ϕ (z) = 1 n n j=1 ψ(z j ) ∈ R r . (ii) if ϕ(z, z ) = ξ(z), then f ϕ transports the input distribution via ξ, as f ϕ (z) = {ξ(z i ), i ∈ [n]} ∈ Z(R r
). This operation is referred to as a push-forward.

Remark 3. (Varying dimensions d X and d Y ). Both in practice and in theory, it is important that f ϕ layers (in particular the first layer of the neural architecture) handle datasets of arbitrary number of features d X and number of multi-labels d Y . The proposed approach, used in the experiments (Section 4), is to define ϕ on the top of a four-dimensional aggregator, as follows. Letting z = (x, y) and z = (x , y ) be two samples in

R d X × R d Y , let u be defined from R 4 onto R t , consider the sum of u(x[k], x [k], y[ ], y [ ]) for k ranging in [d X ] and in [d Y ],
and apply mapping v from R t to R r on the sum:

ϕ(z, z ) = v d X k=1 d Y =1 u(x[k], x [k], y[ ], y [ ])
Remark 4. (Localized computation) In practice, the quadratic complexity of f ϕ w.r.t. the number n of samples can be reduced by only computing ϕ(z i , z j ) for pairs z i , z j sufficiently close to each other. Layer f ϕ thus extracts and aggregates information related to the neighborhood of the samples.

Learning Meta-features

The proposed distributional neural architectures defined on point distributions (Dida) are sought as

z ∈ Z(R d ) → F ζ (z) def. = f ϕm • f ϕm-1 • . . . • f ϕ1 (z) ∈ R dm+1 (2)
where ζ are the trainable parameters of the architecture (below). Only the case d Y = 1 is considered in the remainder. The k-th layer is built on the top of ϕ k , mapping pairs of vectors in R d k onto R d k+1 , with d 1 = d (the dimension of the input samples). Last layer is built on ϕ m , only depending on its second argument;

it maps the distribution in layer m -1 onto a vector, whose coordinates are referred to as meta-features. The G-invariance and dimension-agnosticity of the whole architecture only depend on the first layer f ϕ1 satisfying these properties. In the first layer, ϕ 1 is sought as ϕ 1 ((x, y), (x , y

)) = v( k u(x[k], x [k], y, y )) (Remark 3), with u(x[k], x [k], y, y ) = (ρ(A u • (x[k]; x [k]) + b u , 1 y =y ) in R t × {0, 1},
def. = (A u , b u , A v , b v , {A k , b k } k )
, that is classically learned by stochastic gradient descent from the loss function defined after the task at hand (Section 4).

Theoretical Analysis

This section analyzes the properties of invariant-layer based neural architectures, specifically their robustness w.r.t. bounded transformations of the involved distributions, and their approximation abilities w.r.t. the convergence in law, which is the natural topology for distributions. As already said, the discrete distribution case is considered in this section for the sake of readability, referring the reader to Appendix A for the general case of continuous distributions.

Optimal Transport Comparison of Datasets

Point clouds vs. distributions. Our claim is that datasets should be seen as probability distributions, rather than point clouds. Typically, including many copies of a point in a dataset amounts to increasing its importance, which usually makes a difference in a standard machine learning setting. Accordingly, the topological framework used to define and learn meta-features in the following is that of the convergence in law, with the distance among two datasets being quantified using the Wasserstein distance (below). In contrast, the point clouds setting (see for instance [START_REF] Qi | Deep learning on point sets for 3d classification and segmentation[END_REF]) relies on the Haussdorff distance among sets to theoretically assess the robustness of these architectures. While it is standard for 2D and 3D data involved in graphics and vision domains, it faces some limitations in higher dimensional domains, e.g. due to max-pooling being a non-continuous operator w.r.t. the convergence in law topology.

Wasserstein distance. Referring the reader to [START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF][START_REF] Peyré | Computational optimal transport[END_REF] for a more comprehensive presentation, the standard 1-Wasserstein distance between two discrete

probability distributions z, z ∈ Z n (R d ) × Z m (R d ) is defined as: W 1 (z, z ) def. = max f ∈Lip 1 (R d ) 1 n n i=1 f (z i ) - 1 m m j=1 f (z j )
with Lip 1 (R d ) the space of 1-Lipschitz functions f : R d → R. To account for the invariance requirement (making indistinguishable z = (z 1 , . . . , z n ) and its permuted image (σ(z 1 ), . . . , σ(z n ))

def. = σ z under σ ∈ G), we introduce the G-invariant 1-Wasserstein distance: for z ∈ Z n (R d ), z ∈ Z m (R d ): W 1 (z, z ) = min σ∈G W 1 (σ z, z )
such that W 1 (z, z ) = 0 if and only if z and z belong to the same equivalence class (Appendix A), i.e. are equal in the sense of probability distributions up to sample and feature permutations.

Lipschitz property. In this context, a map f from Z(R d ) onto Z(R r ) is continuous for the convergence in law (a.k.a. weak convergence on distributions, denoted ) iff for any sequence z (k) z, then f (z (k) ) f (z). The Wasserstein distance metrizes the convergence in law, in the sense that z (k) z is equivalent to

W 1 (z (k) , z) → 0. Furthermore, map f is said to be C-Lipschitz for the permutation invariant 1-Wasserstein distance iff ∀z, z ∈ Z(R d ), W 1 (f (z), f (z )) CW 1 (z, z ). (3)
The C-Lipschitz property entails the continuity of f w.r.t. its input: if two input distributions are close in the permutation invariant 1-Wasserstein sense, the corresponding outputs are close too.

Regularity of Distribution-Based Invariant Layers

Assuming the interaction functional to satisfy the Lipschitz property:

∀z ∈ R d , ϕ(z, •) and ϕ(•, z) are C ϕ -Lipschitz. ( 4
)
the robustness of invariant layers with respect to different variations of their input is established (proofs in Appendix B). We first show that invariant layers also satisfy Lipschitz property, ensuring that deep architectures of the form (2) map close inputs onto close outputs.

Proposition 1. Invariant layer f ϕ of type ( 1) is (2rC ϕ )-Lipschitz in the sense of (3).

A second result regards the case where two datasets z and z are such that z is the image of z through some diffeomorphism τ (z = (z 1 , . . . , z n ) and z = τ z = (τ (z 1 ), . . . , τ (z n )). If τ is close to identity, then the following proposition shows that f ϕ (τ z) and f ϕ (z) are close too. More generally, if continuous transformations τ and ξ respectively apply on the input and output space of f ϕ , and are close to identity, then ξ f ϕ (τ z) and f ϕ (z) are also close.

∀z ∈ Z(Ω), W 1 (ξ f ϕ (τ z), f ϕ (z)) sup x∈fϕ(τ (Ω)) ||ξ(x) -x|| 2 + 2r Lip(ϕ) sup x∈Ω ||τ (x) -x|| 2 ∀z, z ∈ Z(Ω), if τ is equivariant, W 1 (ξ f ϕ (τ z), ξ f ϕ (τ z )) 2r C ϕ C τ C ξ W 1 (z, z )

Universality of Invariant Layers

Lastly, the universality of the proposed architecture is established, showing that the composition of an invariant layer (1) and a fully-connected layer is enough to enjoy the universal approximation property, over all functions defined on Z(R d ) with dimension d less than some D (Remark 3).

Theorem 1. Let F : Z(Ω) → R be a G-invariant map on a compact Ω, continuous for the convergence in law. Then ∀ε > 0, there exists two continuous maps ψ, ϕ such that

∀z ∈ Z(Ω), |F(z) -ψ • f ϕ (z)| < ε
where ϕ is G-invariant and independent of F.

Proof. The sketch of the proof is as follows (complete proof in Appendix C). Let us define ϕ = g • h where: (i) h is the collection of d X elementary symmetric polynomials in the features and d Y elementary symmetric polynomials in the labels, which is invariant under G; (ii) a discretization of h(Ω) on a grid is then considered, achieved thanks to g that aims at collecting integrals over each cell of the discretization; (iii) ψ applies function F on this discretized measure; this requires h to be bijective, and is achieved by h, through a projection on the quotient space S d /G and a restriction to its image compact Ω . To sum up, f ϕ defined as such computes an expectation which collects integrals over each cell of the grid to approximate measure h z by a discrete counterpart h z. Hence ψ applies F to h-1 ( h z). Continuity is obtained as follows: (i) proximity of h z and h z follows from Lemma 1 in [START_REF] De Bie | Stochastic deep networks[END_REF]) and gets tighter as the grid discretization step tends to 0; (ii) Map h-1 is 1/d-Hölder, after Theorem 1.3.1 from [START_REF] Rahman | Analytic theory of polynomials[END_REF]); therefore Lemma 2 entails that W 1 (z, h-1 h z) can be upper-bounded; (iii) since Ω is compact, by Banach-Alaoglu theorem, Z(Ω) also is. Since F is continuous, it is thus uniformly weakly continuous: choosing a discretization step small enough ensures the result.

Remark 5. (Comparison with [START_REF] Maron | On learning sets of symmetric elements[END_REF]) The above proof holds for functionals of arbitrary input sample size n, as well as continuous distributions, generalizing results in [START_REF] Maron | On learning sets of symmetric elements[END_REF]. Note that the two types of architectures radically differ (more in Section 4).

Remark 6. (Approximation by an invariant NN) After theorem 1, any invariant continuous function defined on distributions with compact support can be approximated with arbitrary precision by an invariant neural network (Appendix C). The proof involves mainly three steps: (i) an invariant layer f ϕ can be approximated by an invariant network; (ii) the universal approximation theorem [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF]; (iii) uniform continuity is used to obtain uniform bounds. The experimental validation presented in this section considers two goals of experiments: (i) assessing the ability of Dida to learn accurate meta-features; (ii) assessing the merit of the Dida invariant layer design, building invariant f ϕ on the top of an interactional function ϕ (Eq. 1). As said, this architecture is expected to grasp contrasts among samples, e.g. belonging to different classes; the proposed experimental setting aims to empirically investigate this conjecture. These goals of experiments are tackled by comparing Dida to three baselines: DSS layers [START_REF] Maron | On learning sets of symmetric elements[END_REF]; hand-crafted meta-features (HC) [START_REF] Muñoz | Instance spaces for machine learning classification[END_REF] (Table 4 in Appendix D); Dataset2Vec [START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF]. We implemented DSS (the code being not available) using linear and non-linear invariant layers. 2 . All compared systems are allocated ca the same number of parameters.

Experimental validation

Experimental setting. Two tasks defined at the dataset level are considered: patch identification (section 4.1) and performance modelling (section 4.2). On both tasks, the same Dida architecture is considered (Fig 1 ), involving 2 invariant layers followed by 3 fully connected (FC) layers. Meta-features F ζ (z) consist of the output of the third FC layer, with ζ denoting the trained Dida parameters. All experiments run on 1 NVIDIA-Tesla-V100-SXM2 GPU with 32GB memory, using Adam optimizer with base learning rate 10 -3 .

Task 1: Patch Identification

The patch identification task consists of detecting whether two blocks of data are extracted from the same original dataset [START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF]. Letting u denote a n-sample, d-dimensional dataset, a patch z is constructed from u by retaining samples with index in I ⊂ [n] and features with index in J ⊂ [d]. To each pair of patches z, z with same number of instances, is associated a binary metalabel (z, z ) set to 1 iff z and z' are extracted from the same initial dataset u. Dida parameters ζ are trained to minimize the cross-entropy loss of model

ˆ ζ (z, z ) = exp (-||F ζ (z) -F ζ (z )|| 2 ), with F ζ (z) and F ζ (z ) the meta-features computed for z and z : Minimize L(ζ) = - z,z (z, z ) log( ˆ ζ (z, z ))+(1-(z, z )) log(1-ˆ ζ (z, z )) (5)
The classification results on toy datasets and UCI datasets (

Task 2: Performance model learning

The performance modelling task aims to assess a priori the accuracy of the classifier learned from a given machine learning algorithm with a given configuration θ (vector of hyper-parameters ranging in a hyper-parameter space Θ, Appendix D), on a dataset z (for brevity, the performance of θ on z) [START_REF] Rice | The algorithm selection problem[END_REF]. In each epoch, a batch made of triplets (z, θ 1 , θ 2 ) is built, with θ 1 , θ 2 uniformly drawn in the algorithm configuration space (Table 5) and z a n-sample ddimensional patch of a dataset in the OpenML CC-2018 [START_REF] Bischl | Openml benchmarking suites[END_REF] with n uniformly drawn in [700; 900] and d in [3; 10].

The quality of the Dida meta-features is assessed from the ranking accuracy (Table 2), showing their relevance. The performance gap compared to the baselines is higher for the k-NN modelling task; this is explained as the sought performance model only depends on the local geometry of the examples. Still, good performances are observed over all considered algorithms. A regression setting, where a real-valued (F ζ (z), θ) learns the predicted performance, can be successfully considered on top of the learned meta-features F ζ (z) (illustrated on the k-NN algorithm on Figure 2; other results are presented in Appendix D).

Conclusion

The theoretical contribution of the paper is the Dida architecture, able to learn from discrete and continuous distributions on R d , invariant w.r.t. feature ordering, agnostic w.r.t. the size and dimension d of the considered distribution sample (with d less than some upper bound D). This architecture enjoys universal approximation and robustness properties, generalizing former results obtained for point clouds [START_REF] Maron | On learning sets of symmetric elements[END_REF]. The merits of Dida are demonstrated on two tasks defined at the dataset level: patch identification and performance model learning, comparatively to the state of the art [START_REF] Maron | On learning sets of symmetric elements[END_REF][START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF][START_REF] Muñoz | Instance spaces for machine learning classification[END_REF]. The ability to accurately describe a dataset in the landscape defined by ML algorithms opens new perspectives to compare datasets and algorithms, e.g. for domain adaptation [START_REF] Ben-David | Analysis of representations for domain adaptation[END_REF][START_REF] Ben-David | A theory of learning from different domains[END_REF] and meta-learning [START_REF] Finn | Probabilistic model-agnostic metalearning[END_REF][START_REF] Yoon | Bayesian model-agnostic meta-learning[END_REF].

A Extension to arbitrary distributions

Overall notations. Let X ∈ R(R d ) denote a random vector on R d with α X ∈ P(R d ) its law (a positive Radon measure with unit mass). By definition, its expectation denoted E(X) reads E(X) = R d xdα X (x) ∈ R d , and for any continuous function f :

R d → R r , E(f (X)) = R d f (x)dα X (x).
In the following, two random vectors X and X with same law α X are considered indistinguishable, noted X ∼ X. Letting f : R d → R r denote a function on R d , the push-forward operator by f , noted f : P(R d ) → P(R r ) is defined as follows, for any g continuous function from

R d to R r (g in C(R d ; R r )): ∀g ∈ C(R d ; R r ) R r gd(f α) def. = R d g(f (x))dα(x)
Letting {x i } be a set of points in R d with w i 0 such that i w i = 1, the discrete measure α X = i w i δ xi is the sum of the Dirac measures δ xi weighted by w i .

Invariances. In this paper, we consider functions on probability measures that are invariant with respect to permutations of coordinates. Therefore, denoting S d the d-sized permutation group, we consider measures over a symmetrized compact Ω ⊂ R d equipped with the following equivalence relation: for α, β ∈ P(Ω), α ∼ β ⇐⇒ ∃σ ∈ S d , β = σ α, such that a measure and its permuted counterpart are indistinguishable in the corresponding quotient space, denoted alternatively P(Ω) /∼ or R(Ω) /∼ . A function ϕ : Ω n → R is said to be invariant (by permutations of coordinates) iff ∀σ ∈ S d , ϕ(x 1 , . . . , x n ) = ϕ(σ(x 1 ), . . . , σ(x n )) (Definition 1).

Tensorization. Letting X and Y respectively denote two random vectors on R(R d ) and R(R p ), the tensor product vector X ⊗ Y is defined as:

X ⊗ Y def. = (X , Y ) ∈ R(R d × R p )
, where X and Y are independent and have the same law as X and Y , i.e. d(α X⊗Y )(x, y) = dα X (x)dα Y (y). In the finite case, for α X = 1 n i δ xi and α Y = 1 m j δ yj , then α X⊗Y = 1 nm i,j δ xi,yj , weighted sum of Dirac measures on all pairs (x i , y j ). The k-fold tensorization of a random vector X ∼ α X , with law α ⊗k X , generalizes the above construction to the case of k independent random variables with law α X . Tensorization will be used to define the law of datasets, and design universal architectures (Appendix C).

Invariant layers. In the general case, a G-invariant layer f ϕ with invariant map ϕ :

R d × R d → R r such that ϕ satisfies ∀(x 1 , x 2 ) ∈ (R d ) 2 , ∀σ ∈ G, ϕ(σ(x 1 ), σ(x 2 )) = ϕ(x 1 , x 2 )
is defined as

f ϕ : X ∈ R(R d ) /∼ → E X ∼X [ϕ(X, X )] ∈ R(R r ) /∼
where the expectation is taken over X ∼ X. Note that considering the couple (X, X ) of independent random vectors X ∼ X amounts to consider the tensorized law α X ⊗ α X . Remark 8. Taking as input a discrete distribution α X = n i=1 w i δ xi , the invariant layer outputs another discrete distribution α Y = n i=1 w i δ yi with y i = n j=1 w j ϕ(x i , x j ); each input point x i is mapped onto y i summarizing the pairwise interactions with x i after ϕ.

Remark 9. (Generalization to arbitrary invariance groups) The definition of invariant ϕ can be generalized to arbitrary invariance groups operating on R d , in particular sub-groups of the permutation group S d . After [START_REF] Maron | On learning sets of symmetric elements[END_REF] (Thm 5), a simple and only way to design an invariant linear function is to consider ϕ(z, z ) = ψ(z + z ) with ψ being G-invariant. How to design invariant functions in the general non-linear case is left for further work.

Remark 10. Invariant layers can also be generalized to handle higher order interactions functionals, namely f ϕ (X) def.

= E X2,...,X N ∼X [ϕ(X, X 2 , . . . , X N )], which amounts to consider, in the discrete case, N -uple of inputs points (x j1 , . . . , x j N ).

B Proofs on Regularity

= min

X∼α,Y ∼β

E(||X -Y ||)
where the minimum is taken over measures on R d × R d with marginals α, β ∈ P(R d ). W 1 is known to be a norm [START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF], that can be conveniently computed using

W 1 (α, β) = W 1 (α -β) = max Lip(g) 1 R d gd(α -β),
where Lip(g) is the Lipschitz constant of g : R d → R with respect to the Euclidean norm (unless otherwise stated). For simplicity and by abuse of notations,

W 1 (X, Y ) is used instead of W 1 (α, β) when X ∼ α and Y ∼ β. The convergence in law denoted is equivalent to the convergence in Wasserstein distance in the sense that X k X is equivalent to W 1 (X k , X) → 0.
Permutation-invariant Wasserstein distance. The Wasserstein distance is quotiented according to the permutation-invariance equivalence classes: for

α, β ∈ P(R d ) W 1 (α, β) def.
= min

σ∈S d W 1 (σ α, β) = min σ∈S d max Lip(g) 1 R d g • σdα - R d gdβ such that W 1 (α, β) = 0 ⇐⇒ α ∼ β. W 1 defines a norm on P(R d ) /∼ . Lipschitz property. A map f : R(R d ) → R(R r
) is continuous for the convergence in law (aka the weak * of measures) if for any sequence X k X, then f (X k ) f (X). Such a map is furthermore said to be C-Lipschitz for the permutation invariant 1-Wasserstein distance if

∀ (X, Y ) ∈ (R(R d ) /∼ ) 2 , W 1 (f (X), f (Y )) CW 1 (X, Y ). ( 6
)
Lipschitz properties enable us to analyze robustness to input perturbations, since it ensures that if the input distributions of random vectors are close in the permutation invariant Wasserstein sense, the corresponding output laws are close, too.

Proofs of section 3.2.

Proof. (Proposition 1). For α, β ∈ P(R d ), Proposition 1 from [START_REF] De Bie | Stochastic deep networks[END_REF] yields

W 1 (f ϕ (α), f ϕ (β)) 2r Lip(ϕ) W 1 (α, β), hence, for σ ∈ G, W 1 (σ f ϕ (α), f ϕ (β)) W 1 (σ f ϕ (α), f ϕ (α)) + W 1 (f ϕ (α), f ϕ (β)) W 1 (σ f ϕ (α), f ϕ (α)) + 2r Lip(ϕ) W 1 (α, β)
hence, taking the infimum over σ yields

W 1 (f ϕ (α), f ϕ (β)) W 1 (f ϕ (α), f ϕ (α)) + 2r Lip(ϕ) W 1 (α, β) 2r Lip(ϕ) W 1 (α, β) Since f ϕ is invariant, for σ ∈ G, f ϕ (z) = f ϕ (σ z), W 1 (f ϕ (α), f ϕ (β)) 2r Lip(ϕ) W 1 (σ α, β)
Taking the infimum over σ yields the result.

Proof. (Proposition 2). To upper bound W 1 (ξ f ϕ (τ α), f ϕ (α)) for α ∈ P(R d ), we proceed as follows, using proposition 3 from [START_REF] De Bie | Stochastic deep networks[END_REF] and proposition 1:

W 1 (ξ f ϕ (τ α ϕ (α)), f ϕ (α)) W 1 (ξ f ϕ (τ α), f ϕ (τ α)) + W 1 (f ϕ (τ α), f ϕ (α)) ||ξ -id|| L 1 (fϕ(τ α)) + Lip(f ϕ ) W 1 (τ α, α) sup y∈fϕ(τ (Ω)) ||ξ(y) -y|| 2 + 2r Lip(ϕ) sup x∈Ω ||τ (x) -x|| 2
For σ ∈ G, we get

W 1 (σ ξ f ϕ (τ α), f ϕ (α)) W 1 (σ ξ f ϕ (τ α), ξ f ϕ (τ α)) + W 1 (ξ f ϕ (τ α), f ϕ (α))
Taking the infimum over σ yields

W 1 (ξ f ϕ (τ α), f ϕ (α)) W 1 (ξ f ϕ (τ α), f ϕ (α)) sup y∈fϕ(τ (Ω)) ||ξ(y) -y|| 2 + 2rC(ϕ) sup x∈Ω ||τ (x) -x|| 2 Similarly, for α, β ∈ (P(R d )) 2 , W 1 (ξ f ϕ (τ α), ξ f ϕ (τ β)) Lip(ξ) W 1 (f ϕ (τ α), f ϕ (τ β)) Lip(ξ) Lip(f ϕ ) W 1 (τ α, τ β) 2r Lip(ϕ) Lip(ξ) Lip(τ ) W 1 (α, β) hence, for σ ∈ G, W 1 (σ ξ f ϕ (τ α), ξ f ϕ (τ β)) W 1 (σ ξ f ϕ (τ α), ξ f ϕ (τ α)) + W 1 (ξ f ϕ (τ α), ξ f ϕ (τ β))
and taking the infimum over σ yields

W 1 (ξ f ϕ (τ α), ξ f ϕ (τ β)) W 1 (ξ f ϕ (τ α), ξ f ϕ (τ β)) 2r Lip(ϕ) Lip(ξ) Lip(τ ) W 1 (α, β) Since τ is equivariant: namely, for α ∈ P(R d ), σ ∈ G, τ (σ α) = σ (τ α), hence, since f ϕ is invariant, f ϕ (τ (σ α)) = f ϕ (σ (τ α)) = f ϕ (τ α), hence for σ ∈ G, W 1 (ξ f ϕ (τ α), ξ f ϕ (τ β)) 2r Lip(ϕ) Lip(ξ) Lip(τ ) W 1 (σ α, β)
Taking the infimum over σ yields the result.

C Proofs on Universality

Detailed proof of Theorem 1. This paragraph details the result in the case of S d -invariance, while the next one focuses on invariances w.r.t. products of permutations. Before providing a proof of Theorem 1 we first state two useful lemmas. Lemma 1 is mentioned for completeness, referring the reader to [START_REF] De Bie | Stochastic deep networks[END_REF], Lemma 1 for a proof.

Lemma 1. Let (S j ) N j=1 be a partition of a domain including Ω (S j ⊂ R d ) and let x j ∈ S j . Let (ϕ j ) N j=1 a set of bounded functions ϕ j : Ω → R supported on S j , such that j ϕ j = 1 on Ω. For α ∈ P(Ω), we denote αN

def. = N j=1 α j δ xj with α j def. = Sj ϕ j dα. One has, denoting ∆ j def. = max x∈Sj ||x j -x||, W 1 ( αN , α) max 1 j N ∆ j .
Lemma 2. Let f : R d → R q a 1/p-Hölder continuous function (p 1), then there exists a constant C > 0 such that for all α,

β ∈ P(R d ), W 1 (f α, f β) C W 1 (α, β) 1/p .
Proof. For any transport map π with marginals α and β, 1/p-Hölderness of

f with constant C yields ||f (x) -f (y)|| 2 dπ(x, y) C ||x -y|| 1/p 2 dπ(x, y) C ||x -y|| 2 dπ(x, y)
1/p using Jensen's inequality (p 1). Taking the infimum

over π yields W 1 (f α, f β) C W 1 (α, β) 1/p .
Proof. We provide a proof in the case G = S d × S p , which naturally extends to any product group G = S d1 × . . . × S dn . We trade h for the collection of elementary symmetric polynomials in the first d variables; and in the last p variables: h : (x 1 , . . . , x d , y 1 , . . . , y p ) ∈ R d+p → ([ 1 j1<...<ji d x j1 . . . x ji ] d i=1 ; [ 1 j1<...<ji p y j1 . . . y ji ] p i=1 ) ∈ R d+p up to normalizing constants (see Lemma 4). Step 1 (in Lemma 3) consists in showing that h does not lead to a loss of information, in the sense that it generates the ring of S d × S p -invariant polynomials. In step 2 (in Lemma 4), we show that h-1 is 1/ max(d, p)-Hölder. Combined with the proof of Theorem 1, this amounts to showing that the concatenation of Hölder functions (up to normalizing constants) is Hölder. With these ingredients, the sketch of the previous proof yields the result. Lemma 3. Let the collection of symmetric invariant polynomials

[P i (X 1 , . . . , X d )] d i=1 def. = [ 1 j1<...<ji d X j1 . . . X ji ] d i=1 and [Q i (Y 1 , . . . , Y p )] p i=1 = [ 1 j1<...<ji p Y j1 . . . Y ji ] p i=1 . The d + p-sized family (P 1 , . . . , P d , Q 1 , . . . , Q p ) generates the ring of S d × S p -invariant polynomials.
Proof. The result comes from the fact the fundamental theorem of symmetric polynomials (see [START_REF] Cox | Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF] chapter 7, theorem 3) does not depend on the base field. Every Proof. Without loss of generality, we consider d > p so that max(d, p) = d, and f, g normalized (f.i. ∀x,

S d × S p -invariant polynomial P (X 1 , . . . , X d , Y 1 , . . . , Y p ) is also S d × I p -invariant with coefficients in R[Y 1 , . . . , Y p ], hence it can be written P = R(Y 1 , . . . , Y p )(P 1 , . . . , P d ). It is then also S p -invariant
x 0 ∈ (R d ) 2 , ||f (x) -f (x 0 )|| 1 ||x -x 0 || 1/d 1 ). For (x, y), (x 0 , y 0 ) ∈ Ω 2 , ||h(x, y) -h(x 0 , y 0 )|| 1 ||f (x) -f (x 0 )|| 1 + ||g(y) -g(y 0 )|| 1 ||x -x 0 || 1/d 1 + ||y -y 0 || 1/p 1
since both f, g are Hölder. We denote D the diameter of Ω, such that both ||x-x 0 || 1 /D 1 and ||y-y 0 || 1 /D 1 hold. Therefore ||h(x, y)-

h(x 0 , y 0 )|| 1 D 1/d ||x-x0||1 D 1/d + D 1/p ||y-y0||1 D 1/p 2 1-1/d D 1/p-1/d ||(x, y) - (x 0 , y 0 )|| 1/d 1
using Jensen's inequality, hence the result.

In the next two paragraphs, we focus the case of S d -invariant functions for the sake of clarity, without loss of generality. Indeed, the same technique applies to G-invariant functions as h in that case has the same structure: its first d X components are S d X -invariant functions of the first d X variables and its last d Y components are S d Y -invariant functions of the last variables. ). Then functions f and g from Theorem 1 are uniform: there exists f, g continuous, h 1 , . . . , h dm continuous invariant such that

∀k = 1 . . . d m , ∀α k ∈ P(I k ), |F k (α k ) -f • E • g(h k α k )| < ε.
Proof. Theorem 1 yields continuous f, g and a continuous invariant h dm such that ∀α ∈ P(I dm ),

|F dm -f • E • g(h dm α)| < ε. For k = 1 . . . d m -1, we denote h k : (x 1 , . . . , x k ) ∈ R k → (( 1 j1<...<ji k x (j1) • . . . • x (ji) ) i=1...k , 0 . . . , 0) ∈ R dm . With the hypothesis, for k = 1 . . . d m -1, α k ∈ P(I k ), the fact that h k (α k ) = h dm (α k ⊗ δ ⊗dm-k 0 ) yields the result.
Approximation by invariant neural networks. Based on theorem 1, F is uniformly close to f • E • g • h:

• We approximate f by a neural network f θ : x ∈ R N → C 1 λ(A 1 x + b 1 ) ∈ R,
where p 1 is an integer,

A 1 ∈ R p1×N , C 1 ∈ R 1×p1 are weights, b 1 ∈ R p1 is a
bias and λ is a non-linearity.

• Since each component [START_REF] Zaheer | Deep sets[END_REF] (which is a special case of our layers with a base function only depending on its first argument, see section 2.2), ρ j : R d+1 → R, and u : R → R d+1 independent of j (see [START_REF] Zaheer | Deep sets[END_REF], theorem 7).

ϕ j of ϕ = g • h is permutation-invariant, it has the representation ϕ j : x = (x 1 , . . . , x d ) ∈ R d → ρ j d i=1 u(x i )
• We can approximate ρ j and u by neural networks ρ j,θ :

x ∈ R d+1 → C 2,j λ(A 2,j x + b 2,j ) ∈ R and u θ : x ∈ R d → C 3 λ(A 3 x + b 3 ) ∈ R d+1
, where p 2,j , p 3 are integers, A 2,j ∈ R p2,j ×(d+1) , C 2,j ∈ R 1×p2,j , A 3 ∈ R p3×1 , C 3 ∈ R (d+1)×p3 are weights and b 2,j ∈ R p2,j , b 3 ∈ R p3 are biases, and denote ϕ θ (x) = (ϕ j,θ (x)) j def.

= (ρ j,θ ( d i=1 u θ (x i ))) j . Indeed, we upper-bound the difference of interest |F(α) -f θ (E X∼α (ϕ θ (X)))| by triangular inequality by the sum of three terms:

• |F(α) -f (E X∼α (ϕ(X)))| • |f (E X∼α (ϕ(X))) -f θ (E X∼α (ϕ(X)))| • |f θ (E X∼α (ϕ(X))) -f θ (E X∼α (ϕ θ (X)))|
and bound each term by ε 3 , which yields the result. The bound on the first term directly comes from theorem 1 and yields a constant N which depends on ε. The bound on the second term is a direct application of the universal approximation theorem (UAT) [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Leshno | Multilayer feedforward networks with a nonpolynomial activation function can approximate any function[END_REF]. Indeed, since α is a probability measure, input values of f lie in a compact subset of R N : || Ω g •h(x)dα|| ∞ max x∈Ω max i |g i •h(x)|, hence the theorem is applicable as long as λ is a nonconstant, bounded and continuous activation function. Let us focus on the third term. Uniform continuity of f θ yields the existence of δ > 0 s.

t. ||u -v|| 1 < δ implies |f θ (u) -f θ (v)| < ε 3 .
Let us apply the UAT: each component ϕ j of h can be approximated by a neural network ϕ j,θ . Therefore:

||E X∼α (ϕ(X) -ϕ θ (X)) || 1 E X∼α ||ϕ(X) -ϕ θ (X)|| 1 N j=1 Ω |ϕ j (x) -ϕ j,θ (x)|dα(x) N j=1 Ω |ϕ j (x) -ρ j,θ ( d i=1 u(x i ))|dα(x) + N j=1 Ω |ρ j,θ ( d i=1 u(x i )) -ρ j,θ ( d i=1 u θ (x i ))|dα(x) N δ 2N + N δ 2N = δ
using the triangular inequality and the fact that α is a probability measure. The first term is small by UAT on ρ j while the second also is, by UAT on u and uniform continuity of ρ j,θ . Therefore, by uniform continuity of f θ , we can conclude.

Universality of tensorization. This complementary theorem provides insight into the benefits of tensorization for approximating invariant regression functionals, as long as the test function is invariant.

Theorem 2. The algebra

A Ω def. = F : P(Ω) /∼ → R, ∃n ∈ N, ∃ϕ : Ω n → R invariant, ∀α, F(α) = Ω n ϕdα ⊗n
where ⊗n denotes the n-fold tensor product, is dense in C(M 1 + (Ω) /∼ ). Proof. This result follows from the Stone-Weierstrass theorem. Since Ω is compact, by Banach-Alaoglu theorem, we obtain that P(Ω) is weakly-* compact, hence P(Ω) /∼ also is. In order to apply Stone-Weierstrass, we show that A Ω contains a non-zero constant function and is an algebra that separates points. A (non-zero, constant) 1-valued function is obtained with n = 1 and ϕ = 1. Stability by scalar is straightforward. For stability by sum: given

(F 1 , F 2 ) ∈ A 2 Ω (with associated functions (ϕ 1 , ϕ 2 ) of tensorization degrees (n 2 , n 2 )), we denote n def. = max(n 1 , n 2 ) and ϕ(x 1 , . . . , x n ) def. = ϕ 1 (x 1 , . . . , x n1 ) + ϕ 2 (x 1 , . . . , x n2 ) which is indeed invariant, hence F 1 + F 2 = Ω n ϕdα ⊗n ∈ A Ω .
Similarly, for stability by product: denoting this time n = n 1 + n 2 , we introduce the invariant ϕ(x 1 , . . . , x n ) = ϕ 1 (x 1 , . . . , x n1 ) × ϕ 2 (x n1+1 , . . . , x n ), which shows that F = F 1 × F 2 ∈ A Ω using Fubini's theorem. Finally, A Ω separates points: if α = ν, then there exists a symmetrized domain S such that α(S) = ν(S): indeed, if for all symmetrized domains S, α(S) = ν(S), then α(Ω) = ν(Ω) which is absurd. Taking n = 1 and ϕ = 1 S (invariant since S is symmetrized) yields an F such that F(α) = F(ν).

D Experimental validation, supplementary material

Dida and DSS source code are provided in the last file of the supplementary material.

D.1 Benchmark Details

Three benchmarks are used (Table 3): TOY and UCI, taken from [START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF], and OpenML CC-18. TOY includes 10,000 datasets, where instances are distributed along mixtures of Gaussian, intertwinning moons and rings in R 2 , with 2 to 7 classes. UCI includes 121 datasets from the UCI Irvine repository [START_REF] Dua | UCI machine learning repository[END_REF]

D.2 Baseline Details

Dataset2Vec details. We used the available implementation of Dataset2Vec3 .

In the experiments, Dataset2Vec hyperparameters are set to their default values except size and number of patches, set to same values as in Dida.

DSS layer details. We built our own implementation of invariant DSS layers, as follows. Linear invariant DSS layers (see [START_REF] Maron | On learning sets of symmetric elements[END_REF], Theorem 5, 3.) are of the form

L inv : X ∈ R n×d → L H ( n j=1 x j ) ∈ R K (7)
where L H : R d → R K is a linear H-invariant function. Our applicative setting requires that the implementation accommodates to varying input dimensions d as well as permutation invariance, hence we consider the Deep Sets representation (see [START_REF] Zaheer | Deep sets[END_REF], Theorem 7)

L H : x = (x 1 , . . . , x d ) ∈ R d → ρ d i=1 ϕ(x i ) ∈ R K (8)
where ϕ : R → R d+1 and ρ : R d+1 → R K are modelled as (i) purely linear functions; (ii) FC networks, which extends the initial linear setting [START_REF] De Bie | Stochastic deep networks[END_REF]. In our case, H = S d X × S d Y , hence, two invariant layers of the form (7-8) are combined to suit both feature-and label-invariance requirements. Both outputs are concatenated and followed by an FC network to form the DSS meta-features.

The last experiments use DSS equivariant layers (see [START_REF] Maron | On learning sets of symmetric elements[END_REF], Theorem 1), which take the form

L eq : X ∈ R n×d →   L 1 eq (x i ) + L 2 eq ( j =i x j )   i∈[n] ∈ R n×d (9)
where L 1 eq and L 2 eq are linear H-equivariant layers. Similarly, both feature-and label-equivariance requirements are handled via the Deep Sets representation of equivariant functions (see [START_REF] Zaheer | Deep sets[END_REF], Lemma 3) and concatenated to be followed by an invariant layer, forming the DSS meta-features. All methods are allocated the same number of parameters to ensure fair comparison. We provide our implementation of the DSS layers in the supplementary material.

Hand-crafted meta-features. For the sake of reproducibility, the list of meta-features used in section 4 is given in Table 4. Note that meta-features related to missing values and categorical features are omitted, as being irrelevant for the considered benchmarks. Hand-crafted meta-features are extracted using the BYU metalearn library4 .

D.3 Performance Prediction

Experimental setting. Table 5 details all hyper-parameter configurations Θ considered in Section 4.2. As said, the learnt meta-features F ζ (z) can be used in a regression setting, predicting the performance of various ML algorithms on a dataset z. Several performance models have been considered on top of the meta-features learnt in Section 4.2, for instance (i) a BOHAMIANN network [START_REF] Springenberg | Bayesian optimization with robust bayesian neural networks[END_REF]; (ii) Random Forest models, trained under a Mean Squared Error loss between predicted and true performances.

Results. Table 6 reports the Mean Squared Error on the test set with performance model BOHAMIANN [START_REF] Springenberg | Bayesian optimization with robust bayesian neural networks[END_REF], comparatively to DSS and hand-crafted ones. Replacing the surrogate model with Random Forest concludes to the same ranking as in Table 6. Figure 3 complements Table 6 in assessing the learnt Dida meta-features for performance model learning. It shows Dida's ability to capture more expressive meta-features than both DSS and hand-crafted ones, for all ML algorithms considered.

  instance and y i ∈ R d Y the associated multi-label. With d X and d Y respectively the dimensions of the instance and label spaces, let d def. = d X + d Y . By construction, z is invariant under permutation on the sample ordering; it is viewed as an n-size discrete distribution 1 n n i=1 δ zi in R d with δ zi the Dirac function at z i . In the following, Z n (R d ) denotes the space of such n-size point distributions, with Z(R d ) def.= ∪ n Z n (R d ) the space of distributions of arbitrary size.Let G def.

Proposition 2 .

 2 Let τ : R d → R d and ξ : R r → R r be two Lipschitz maps with respectively Lipschitz constants C τ and C ξ . Then,

Remark 7 .

 7 (Extension to different spaces) Theorem 1 also extends to distributions supported on different spaces, via embedding them into a high-dimensional space. Therefore, any invariant function on distributions with compact support in R d with d ≤ D can be uniformly approximated by an invariant network (Appendix C).

Figure 1 :

 1 Figure 1: Learning meta-features with Dida. Top: the Dida architecture (BN stands for batch norm; FC for fully connected layer). Bottom left: Learning meta-features for patch identification using a Siamese architecture (section 4.1). Bottom right: learning meta-features for performance modelling, specifically to rank two hyper-parameter configurations θ 1 and θ 2 (section 4.2).

Figure 2 :

 2 Figure 2: k-NN: True performance vs performance predicted by regression on top of the meta-features (i) learned by Dida, (ii) DSS or (iii) Hand-crafted statistics.

  Wasserstein distance. The regularity of the involved functionals is measured w.r.t. the 1-Wasserstein distance between two probability distributions (α,β) ∈ P(R d ) W 1 (α, β) def. = min π1=α,π2=β R d ×R d||x -y||dπ(x, y)def.

Lemma 4 .

 4 with coefficients in R[P 1 , . . . , P d ], hence it can be writtenP = S(Q 1 , . . . , Q p )(P 1 , . . . , P d ) ∈ R[P 1 , . . . , P d , Q 1 , . . . , Q p ]. Let h : (x, y) ∈ Ω ⊂ R d+p → (f (x)/C 1 , g(y)/C 2 ) ∈ R d+p where Ω is compact, f : R d → R d is 1/d-Hölder with constant C 1 and g : R p → R p is 1/p-Hölder with constant C 2 . Then h is 1/ max(d, p)-Hölder.

Corollary 2 .

 2 Extension of Theorem 1 to distributions on spaces of varying dimension. Let I = [0; 1] and, for k ∈ [1; d m ], F k : P(I k ) → R continuous and S k -invariant. Suppose (F k ) k=1...dm-1 are restrictions of F dm , namely, ∀α k ∈ P(I k ), F k (α k ) = F dm (α k ⊗ δ ⊗dm-k 0

Figure 3 :

 3 Figure 3: Comparison between the true performance and the performance predicted by the trained surrogate model on Dida, DSS or Hand-crafted metafeatures, for various ML algorithms: (a) k-NN; (b) Logistic Regression; (c) SVM; (d) Linear classifier learnt with stochastic gradient descent.

  where ρ is a non-linear activation function, A u a (2, t) matrix, (x[k]; x [k]) the 2-dimensional vector concatenating x[k] and x [k], and b u a t-dimensional vector. With e = k u(x[k], x [k], y, y )), function v likewise applies a non-linear activation function ρ on an affine transformation of e: v(e) = ρ(A v • e + b v ), with A v a (t, r) matrix and b v a r-dimensional vector. Note that the subsequent layers need neither be invariant w.r.t. the number of samples, nor handle a varying number of dimensions. Every ϕ k , k ≥ 2 is defined as ϕ k = ρ(A k •+b k ), with ρ an activation function, A k a (d k , d k+1 ) matrix and b k a d k+1 -dimensional vector. The Dida neural net thus is parameterized by ζ

Table 1 ,

 1 detailed in Appendix D) show the pertinence of the Dida meta-features, particularly on the UCI datasets where the number of features widely varies from one dataset to another. The relevance of the interactional invariant layer design is established on this problem as Dida outperforms both Dataset2Vec and DSS.

	Method	TOY	UCI
	Dataset2Vec( * )	96.19 %± 0.28	77.58 %± 3.13
	DSS layers (Linear aggregation)	89.32 %± 1.85	76.23 %± 1.84
	DSS layers (Non-linear aggregation) 96.24 %± 2.04	83.97 %± 2.89
	DSS layers (Equivariant+invariant) 96.26 %± 1.40	82.94 %± 3.36
	Dida	97.2 % ± 0.1 89.70 % ± 1.89

Table 1 :

 1 Patch identification: performance on 10 runs of Dida, DSS layers and Dataset2Vec. (

* ): values reported from

[START_REF] Jomaa | Dataset2vec: Learning dataset meta-features[END_REF]

.

Table 2 :

 2 DIDA 78.41 ± 0.41 84.14 ± 0.02 89.77 ± 0.50 81.82 ± 0.91 Pairwise ranking of configurations, for ML algorithms SGD, SVM, LR and k-NN: performance on test set of Dida, hand-crafted and DSS (average and std deviation on 3 runs).

	Method	SGD	SVM	LR	k-NN
	Hand-crafted	71.18 ± 0.41	75.39 ± 0.29	86.41 ± 0.419	65.44 ± 0.73
	DSS (Linear aggregation)	73.46 ± 1.44	82.91 ± 0.22	87.93 ± 0.58	70.07 ± 2.82
	DSS (Equivariant+Invariant)	73.54 ± 0.26	81.29 ± 1.65	87.65 ± 0.03	68.55 ± 2.84
	DSS (Non-linear aggregation)	74.13 ± 1.01	83.38 ± 0.37	87.92 ± 0.27	73.07 ± 0.77

  . Each benchmark is divided into 70%-30% training-test sets.

		# datasets # samples	# features # labels test ratio
	Toy Dataset	10000	[2048, 8192]	2	[2, 7]	0.3
	UCI	121	[10, 130064]	[3, 262]	[2, 100]	0.3
	OpenML CC-18	71	[500, 100000]	[5, 3073]	[2, 46]	0.5

Table 3 :

 3 Benchmarks characteristics

Table 5 :

 5 Hyper-parameter configurations considered in Section 4.2.

		Parameter		Parameter values	Scale
		warm start		True, Fase
		fit intercept		True, Fase
	LR	tol C		[0.00001, 0.0001] [1e-4, 1e4]	log
		solver	newton-cg, lbfgs, liblinear, sag, saga
		max_iter		[5, 1000]
		kernel		linear, rbf, poly, sigmoid
		C		[0.0001, 10000]	log
		shrinking		True, False
	SVM	degree			[1, 5]
		coef0			[0, 10]
		gamma		[0.0001, 8]
		max_iter		[5, 1000]
		n_neighbors			[1, 100]	log
	KNN	p			[1, 2]
		weights		uniform, distance
		alpha		[0.1, 0.0001]	log
		average		True, False
		fit_intercept		True, False
		learning rate		optimal, invscaling, constant
		loss	hinge, log, modified_huber, squared_hinge, perceptron
	SGD	penalty		l1, l2, elasticnet
		tol		[1e-05, 0.1]	log
		eta0		[1e-7, 0.1]	log
		power_t		[1e-05, 0.1]	log
		epsilon		[1e-05, 0.1]	log
		l1_ratio		[1e-05, 0.1]	log
		Method	SGD	SVM	LR	KNN
	Hand-crafted	0.016 ± 0.001	0.021 ± 0.001	0.018 ± 0.002	0.034 ± 0.001
	DSS (Linear aggregation)	0.015 ± 0.007	0.020 ± 0.002	0.019 ± 0.001	0.025 ± 0.010
	DSS (Equivariant+Invariant)	0.014 ± 0.002	0.017 ± 0.003	0.015 ± 0.003	0.028 ± 0.003
	DSS (Non-linear aggregation)	0.015 ± 0.009	0.016 ± 0.003	0.014 ± 0.001	0.020 ± 0.005
		DIDA	0.012 ± 0.001 0.015 ± 0.001 0.010 ± 0.001 0.009 ± 0.000

Table 6 :

 6 Performance modelling, comparative results of Dida, DSS and Handcrafted (HC) meta-features: Mean Squared Error (average over 5 runs) on test set, between the true performance and the performance predicted by the trained BOHAMIANN surrogate model, for ML algorithms SVM, LR, kNN, SGD (see text).

As opposed to G-equivariant functions that are characterized by ∀σ ∈ G, ϕ(σ z) = σ ϕ(z)

The code source of Dida and (our implementation of) DSS is available in Appendix D.

Dataset2Vec code is available at https://github.com/hadijomaa/dataset2vec

See https://github.com/byu-dml/metalearn

Acknowledgements

The work of G. De Bie is supported by the Région Ile-de-France. H. Rakotoarison acknowledges funding from the ADEME #1782C0034 project NEXT. The work of G. Peyré was supported by the European Research Council (ERC project NORIA) and by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).

Now we are ready to dive into the proof. Let α ∈ P(R d ). We consider:

∈ R d the collection of d elementary symmetric polynomials; h does not lead to a loss in information, in the sense that it generates the ring of S d -invariant polynomials (see for instance [START_REF] Cox | Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF], chapter 7, theorem 3) while preserving the classes (see the proof of Lemma 2, appendix D from [START_REF] Maron | On learning sets of symmetric elements[END_REF]);

• h is obviously not injective, so we consider π :

• Let (ϕ i ) i=1...N the piecewise affine P1 finite element basis, which are hat functions on a discretization (S i ) i=1...N of Ω ⊂ R d , with centers of cells (y i ) i=1...N . We then define g :

We approximate F using the following steps:

• Lemma 1 (see Lemma 1 from [START_REF] De Bie | Stochastic deep networks[END_REF]) yields that h α and h α =

• The map h-1 is regular enough (1/d-Hölder) such that according to Lemma 2, there exists a constant C > 0 such that

Note that h maps the roots of polynomial d i=1 (X -x (i) ) to its coefficients (up to signs). Theorem 1.3.1 from [START_REF] Rahman | Analytic theory of polynomials[END_REF] yields continuity and 1/d-Hölderness of the reverse map. Hence h-1 is 1/d-Hölder.

• Since Ω is compact, by Banach-Alaoglu theorem, we obtain that P(Ω) is weakly-* compact, hence P(Ω) /∼ also is. Since F is continuous, it is thus uniformly weak-* continuous: for any ε > 0, there exists δ > 0 such that

Extension of Theorem 1 to products of permutation groups.

where Ω is a symmetrized compact over R d . Then ∀ε > 0, there exists three continuous maps f, g, h such that