Denis Dezest

Fabrice Mathieu

Laurent Mazenq

Caroline Soyer

Jean Costecalde

Denis Remiens

Olivier Thomas

Jean-François Deü

Liviu Nicu

Wafer-scale integration of piezoelectric actuation capabilities in nanoelectromechanical systems resonators

come   L'archive ouverte pluridisciplinaire

For nanoelectromechanical systems (NEMS) to start being a viable alternative to their microscale counterparts (i.e. microelectromechanical systems or MEMS), the fully integrated transduction at the wafer scale represents the ultimate goal to be achieved. By integrated transduction one means both actuation and sensing of movement capabilities of freestanding nanostructures. So far, relevant results in that sense have been obtained at the chip level either by transposing traditional transduction schemes at the nanoscale [START_REF] Villanueva | A Nanoscale Parametric Feedback Amplifier[END_REF][START_REF] Li | Ultra-Sensitive NEMSbased Cantilevers for Sensing, Scanned Probe and Very High-Frequency Applications[END_REF] or delivering brand new schemes exclusively adapted to the NEMS realm [START_REF] Unterreithmeier | Universal Transduction Scheme for Nanomechanical Systems Based on Dielectric Forces[END_REF]. Recent efforts to demonstrate full-wafer NEMS with integrated transduction means have been done [START_REF] Arcamone | Full-Wafer Fabrication by Nanotencil Lithography of Micro/Nanomechanical Mass Sensors Monolithically Integrated with CMOS[END_REF][START_REF] Bargatin | Large-Scale integration of NEMS for Gas Sensing Applications[END_REF] but remain rather seldom which demonstrates how critical the gap between chip and wafer scale is.

In this work, we demonstrate the integration of piezoelectric actuation means on arrays of nanocantilevers at the wafer scale. We use lead titanate zirconate (PZT) as piezoelectric material mainly because of its excellent actuation properties even when geometrically constrained at extreme scale [START_REF] Guillon | Lead Zirconate Titanate Nanoscale Patterning by UV-based Lithography Lift-Off Technique for Nano-Electromechanical Systems Applications[END_REF].

The fabrication is performed on SOI 4" P-type (100) wafer (525µm/1µm/340nm). Arrays of four nanocantilevers of different lengths (from 2µm to 10.5µm) have been placed on the wafer so that each array contains same wide devices. The width was varied from 1µm to 2.8µm. A piezoelectric stack including top Ti-Pt (12-120nm thick) and bottom LNO (100nm thick) electrodes as well as the PZT material (150nm thick) has been patterned on each nanocantilever in two covering configurations: full-length or half-length of the nanocantilever. The elastic support beneath the piezoelectric stack is made of the SOI device silicon layer covered by a 30nm thick thermal silicon dioxide (see Figure 1). The main fabrication steps are, in order, silicon RIE definition of the nanocantilevers' shape, lift-off patterning of the piezoelectric stack and sacrificial release of the nanocantilevers, the latter being by far the most critical step which imposes the final yield (33%) of the implemented fabrication process.. The whole fabrication process is performed at the wafer scale, the lithography steps being realized using a UV stepper photo repeater (I line CANON FPA 3000i4/i5 N.A. 0.63). A photoresist protection layer is provided to cover the wafer and to protect the suspended nanocantilevers prior to dicing into individual chips.

The dynamic characterization of the nanocantilevers is performed in two ways (external and internal actuationsensing configurations). First, the mechanical integrity of the nanocantilevers is assessed by external piezoelectric actuation and optical sensing of the fundamental mode resonant frequency. Measurements are performed in a home-made fully-automated Fabry-Perot interferometer configuration, under vacuum and ambient temperature conditions. The fully automated option allows convenient characterization at the nanocantilevers level by using the 3D displacement of the chip bearing the nanodevices under the laser spot. The resonant frequency values are compared to theoretical datas issued from finite elements modeling of the nanocantilevers exact configuration, taking into account the specific geometry of the piezoelectric stack (see Figure 2).

The piezoelectric actuation at the nanodevice level is then tested by biasing the top and bottom electrodes as shown in the scheme (see Figure 1). In a first attempt to check the piezoelectric actuation efficiency, no electrical poling of the PZT layer is performed. The results are shown in Figure 3 demonstrating that the piezoelectric layer acts as expected and does not necessarily require electrical poling prior to its use. Nevertheless, in a second attempt, PZT layer is poled at five times the coercitive field value (6.7kV/m) during 15 minutes and the resonant frequency peak shape successively measured shows the enhancement of the actuation efficiency by an increase of the amplitude value of around 30%. In conclusion, we achieved integration of piezoelectric actuation capabilities on NEMS at the full wafer scale. Further work on the piezoelectric sensing demonstration by collecting the electrical charges generated by the PZT layer using a charge amplifier set-up is currently under progress. This work paves promising ways for NEMS to be used in configurations where transduction capabilities are integrated at the nanodevice level providing fabrication at the wafer-scale.

REFERENCES:

Figure 1 :

 1 Figure 1: SEM image (false colors) of an array of four nanocantilevers showing the biasing scheme for the internal piezoelectric actuation. The cantilevers dimensions are 2µm wide and respectively 10.2, 8.2, 6.2 and 4.2µm long (scale bar corresponds to 20µm). The stack is composed of a 150nm thick PZT layer (green) sandwiched between a 100nm thick LNO lower electrode (brown) and a 12-120nm thick Ti-Pt upper electrode (blue). A 30nm thick thermal oxide (purple) grown on top of the silicon ensures the electrical insulation between the stack and the substrate. The structures are actuated by applying an AC voltage between the electrodes through a 100-700 nm thick Ti-Au metallization (yellow). The inset is a close view of the 10.2 µm long cantilever showing the different layers (scale bar corresponds to 3µm).

Figure 2 :

 2 Figure 2: Plot of the fundamental mode resonant frequencies of 2.4µm wide cantilevers with three different lengths l showing the linear dependence on 1 / l². Theoretical datas (red) are obtained from finite element modeling. Experimental datas are obtained under external actuation and sensing configuration at

Figure 3 :

 3 Figure 3: Fundamental mode resonant frequency of a 2µm wide and 10.2µm long cantilever before (black curve) and after (red curve) poling of the PZT thin film. Measurements are achieved according to the integrated actuation (12.6mV AC voltage is applied) and external sensing configuration, at room temperature and under secondary vacuum (9.8.10 -7 mbars). Each datas curve has been averaged 10 times. The structure exhibits a quality factor of 1150 at 9.63MHz.


Introduction

1 Secondly, we aim to discuss the questionnaires used to evaluate RTW-SE in 2 quantitative studies focusing on the RTW of cancer survivors. Finally, this 3 commentary proposes possible interventions that could enhance RTW-SE, and 4 explores future research perspectives.

6 General-SE, cancer management-SE and RTW-SE

7 According to [START_REF] Bandura | Self-efficacy : The exercise of control[END_REF], it does not make sense theoretically to talk about 8 general-SE. No significant relationship has been found between RTW of cancer 9 survivors and general-SE or cancer management-SE, respectively (Bains et al., 10 2012;[START_REF] Koch | Employment pathways and work-related issues in head and neck cancer 23 survivors[END_REF]. Conversely, cancer patients showing low levels of RTW-SE 11 are more likely to be on sick leave upon diagnosis [START_REF] Bains | The impact of colorectal cancer and self-efficacy beliefs on work ability and 8 employment status : A longitudinal study: Colorectal cancer, work ability and 9 employment[END_REF] and are more 12 likely to have longer delays before full-RTW [START_REF] Wolvers | Predictors for earlier return to work of cancer patients[END_REF]. 13 The predictive power of RTW-SE on cancer survivors' RTW should be discussed.

14 [START_REF] Rosbjerg | The Predictive Value of Return to Work Self-efficacy for Return to Work 23 Among Employees with Cancer Undergoing Chemotherapy[END_REF] suggested that RTW-SE does not appear as the strongest 15 predictor of RTW among cancer patients undergoing chemotherapy. However, the 16 small sample size of this study does not permit any generalisation of this result 17 [START_REF] Rosbjerg | The Predictive Value of Return to Work Self-efficacy for Return to Work 23 Among Employees with Cancer Undergoing Chemotherapy[END_REF]). Among workers with psychological or upper-body 18 musculoskeletal injuries, RTW-SE showed the strongest relationship with RTW 19 [START_REF] Black | The Effect of Self-16 Efficacy on Return-to-Work Outcomes for Workers with Psychological or Upper-17 Body Musculoskeletal Injuries : A Review of the Literature[END_REF]. Job-SE also showed a strong predictive association with 20 remaining at work following a RTW attempt [START_REF] Black | The Effect of Self-16 Efficacy on Return-to-Work Outcomes for Workers with Psychological or Upper-17 Body Musculoskeletal Injuries : A Review of the Literature[END_REF]. 21 To study the RTW process, there is a significant need to focus on RTW-SE. 16 behaviours (e.g., pain, physical activity, coping with cancer, and stress 17 management). This study also revealed a small/medium effect size of physical 18 activity on cancer patients' SE [START_REF] Merluzzi | Interventions to enhance self-efficacy in cancer patients : A 11 meta-analysis of randomized controlled trials[END_REF]. [START_REF] Brouwer | The 20 Predictive Validity of the Return-to-Work Self-Efficacy Scale for Return-to-Work 21 Outcomes in Claimants with Musculoskeletal Disorders[END_REF] In order to improve RTW-SE, several possibilities could be taken into account. 20 According to [START_REF] Bandura | Self-efficacy : The exercise of control[END_REF], SE is enhanced through:

21

 mastery experience, which could be implemented by a progressive succession 22 of small professional tasks that are easy to carry out [START_REF] Gollwitzer | Implementation Intentions : Strong Effects of Simple Plans[END_REF].

22 25 1

 25 Complementary investigations, within a large sample, are therefore necessary to 23 understand the strength of the association between RTW-SE and RTW in cancer 24 patients. Junior et al. (2018) yielded a bidimensional questionnaire. To increase knowledge on 2 RTW-SE, the RTWSE-11 (Lagerveld et al., 2010) should be adapted for cancer 3 survivors by using rigorous reliability and validity testing.

4 5 6

 56 Interventions An interventional study has been proposed by Leensen et al. (2017), that includes 7 physical exercise and occupational counselling programmes aimed at enhancing 8 RTW-SE, work ability, and finally, the RTW of cancer patients. Despite the fact that 9 Leensen et al. (2017) showed significant increases in RTW-SE and subsequent 10 RTW-SE over time, the study lacked a control group. To evaluate the effectiveness of 11 interventions aimed at increasing RTW-SE, and promote RTW in cancer patients, 12 randomised controlled trials should be conducted. For example, a meta-analysis 13 conducted by Merluzzi et al. (2019) revealed medium effect sizes of 14 complementary/integrative medicine, social support, cognitive behaviour therapy and 15 self-management interventions in enhancing cancer patients' SE related to specific

  SE is an emerging topic of interest in psycho-oncology for cancer patients who 20 have not yet RTW. Research in patients with other chronic diseases has highlighted 21 the importance of studying the association between RTW-SE and RTW (Black et al., 22 2018). To make this research possible in cancer patients, it is important to use 23 reliable and valid measurements of RTW-SE. It also seems wise to investigate the 24 temporal aspects of RTW-SE developmental pathways because of the psychological 25 or physical changes cancer patients experience during their treatment. Interventional

	1	 verbal persuasion, which could be articulated around positive discourse from
	2	supervisors and colleagues (Greidanus, de Boer, et al., 2018; Greidanus,
	3	Tamminga, et al., 2018).
	4	 physiological feedback, which refers to a virtuous circle between enhancing
	5	RTW-SE, RTW and promoting cancer management (Kennedy et al., 2007).
	6
	7 Future research perspectives
	8 Leensen et al. (2017) observed temporal changes in RTW-SE followed by actual
	9 RTW. However, not all cancer patients are able to develop RTW-SE. We therefore
	10 hypothesise that there are several developmental pathways for RTW-SE.
	11 Investigating developmental trajectories of RTW-SE, and identifying their association
	12 with RTW over time, will allow for better identification of cancer patients at risk of
	13 non-RTW, in order to improve supportive care. Furthermore, knowledge on the
	14 developmental pathways of RTW-SE and its association with subsequent RTW will
	15 allow the development of innovative interventions which could be aimed at improving
	16 the RTW-SE of cancer patients, potentially leading to actual RTW.
	17
	18 Conclusion
	19 RTW-
	23	 vicarious experience, which could be induced with support groups focusing on
	24	vocational rehabilitation after cancer (De Blasi et al., 2014).

European Journal of Cancer Care


Frédéric Chazal

Clément Levrard

Martin Royer

Optimal quantization of the mean measure and applications to statistical learning

This paper addresses the case where data come as point sets, or more generally as discrete measures. Our motivation is twofold: first we intend to approximate with a compactly supported measure the mean of the measure generating process, that coincides with the intensity measure in the point process framework, or with the expected persistence diagram in the framework of persistence-based topological data analysis. To this aim we provide two algorithms that we prove almost minimax optimal.

. At last, we assess the effectiveness of our approach on simulated and real datasets, encompassing text classification and large-scale graph classification.

Introduction

This paper handles the case where we observe n i.i.d measures X 1 , . . . , X n on R d , rather than n i.i.d sample points, the latter case being the standard input of many machine learning algorithms. Such kind of observations naturally arise in many situations, for instance when data are spatial point patterns: in species distribution modeling [START_REF] Renner | Point process models for presence-only analysis[END_REF], repartition of clusters of diseases [START_REF] Diggle | A Point Process Modelling Approach to Raised Incidence of a Rare Phenomenon in the Vicinity of a Prespecified Point[END_REF], modelisation of crime repartition [START_REF] Shirota | Analyzing Car Thefts and Recoveries with Connections to Modeling Origin-Destination Point Patterns[END_REF] to name a few. The framework of i.i.d sample measures also encompasses analysis of multi-channel time series, for instance in embankment dam anomaly detection from piezometers [START_REF] Jung | Exploration and evaluation of AR, MPCA and KL anomaly detection techniques to embankment dam piezometer data[END_REF], as well as topological data analysis, where persistence diagrams naturally appear as discrete measures in R 2 [START_REF] Chazal | Gromov-Hausdorff Stable Signatures for Shapes using Persistence[END_REF][START_REF] Chazal | The structure and stability of persistence modules[END_REF].

The objective of the paper is the following: we want to build from data an embedding of the sample measures into a finite-dimensional Euclidean space that preserves clusters structure, if any. Such an embedding, combined with standard clustering techniques should result in efficient measure clustering procedures. It is worth noting that clustering of measures has a wide range of possible applications: in the case where data come as a collection of finite point sets for instance, including ecology [START_REF] Renner | Point process models for presence-only analysis[END_REF], genetics [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF][START_REF] Adams | Persistence images: a stable vector representation of persistent homology[END_REF], graphs clustering [START_REF] Carrière | PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures[END_REF][START_REF] Hoan Tran | Scale-variant topological information for characterizing the structure of complex networks[END_REF] and shapes clustering [START_REF] Chazal | Gromov-Hausdorff Stable Signatures for Shapes using Persistence[END_REF].

Our vectorization scheme is quite simple: for a k-points vector c = (c 1 , . . . , c k ) in (R d ) k , we map each measure X i on R d into a vector v i ∈ R k that roughly encodes how much weight X i spreads around every c j . Then, in a mixture distribution framework, we provide general conditions on the k-points vectors that allow an efficient clustering based on the corresponding vectorization. Thus, efficiency of our measure clustering procedure essentially depends on our ability to find discriminative k-points vectors from sample.

Choosing a fixed grid of R d as vectorization points is possible, however the dimension of such a vectorization is constrained and can grow quite large. Another choice could be to draw vectorization points at random from the sample measures. Note however that such a method could miss discriminative areas. We choose an intermediate approach, by building a k-points approximation of a central measure of X 1 , . . . , X n . Note that finding compact representations of central tendencies of measures is an interesting problem in itself, especially when the sample measures are naturally organized around a central measure of interest, for instance in image analysis [START_REF] Cuturi | Fast Computation of Wasserstein Barycenters[END_REF] or point processes modeling [START_REF] Renner | Point process models for presence-only analysis[END_REF][START_REF] Diggle | A Point Process Modelling Approach to Raised Incidence of a Rare Phenomenon in the Vicinity of a Prespecified Point[END_REF][START_REF] Shirota | Analyzing Car Thefts and Recoveries with Connections to Modeling Origin-Destination Point Patterns[END_REF].

In [START_REF] Cuturi | Fast Computation of Wasserstein Barycenters[END_REF], the central measure is defined as the Wasserstein barycenter of the distribution of measures. Namely, if we assume that X 1 , . . . , X n are i.i.d measures on R d drawn from X, where X is a probability distribution on the space of measures, then the central measure is defined as µ W = arg min ν E (W 2 (X, ν)) 2 , where ν ranges in the space of measures and W 2 denotes the Wasserstein distance. Note that this definition only makes sense in the case where X(R d ) is constant a.s., that is when we draw measures with the same total mass. Moreover, computing the Wasserstein barycenter of X 1 , . . . , X n in practice is too costly for large n's, even with approximating algorithms [START_REF] Cuturi | Fast Computation of Wasserstein Barycenters[END_REF][START_REF] Rabin | Wasserstein Barycenter and Its Application to Texture Mixing[END_REF]. To overcome these difficulties, we choose to define the central measure as the arithmetic mean of X, denoted by E(X), that assigns the weight E [X(A)] to a borelian set A. In the point process theory, the mean measure is often referred to as the intensity function of the process.

An easily computable estimator of this mean measure is the sample mean measure Xn = ( n i=1 X i ) /n. We intend to build a k-points approximation of E(X), that is a distribution P c supported by c = (c 1 , . . . , c k ) that approximates well E(X), based on X 1 , . . . , X n . To this aim, we introduce two algorithms (batch and mini-batch) that extend classical quantization techniques intended to solve the k-means problem [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. In fact, these algorithms are built to solve the k-means problem for Xn . We prove in Section 3.1 that these algorithms provide minimax optimal estimators of a best possible k-points approximation of E(X), provided that E(X) satisfies some structural assumption. Interestingly, our results also prove optimality of the classical quantization techniques [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF][START_REF] Lloyd | Least squares quantization in PCM[END_REF] in the point sample case.

We assess the overall validity of our appproach by giving theoretical guarantees on our vectorization and clustering process in a topological data analysis framework, where measures are persistence diagrams from different shapes. In this case, vectorization via evaluation onto a fixed grid is the technique exposed in [START_REF] Adams | Persistence images: a stable vector representation of persistent homology[END_REF], whereas our method has clear connections with the procedures described in [START_REF] Zieliński | Persistence Bag-of-Words for Topological Data Analysis[END_REF][START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF]. Our theoretical results are given for vectorizations via evaluations of kernel functions around each point c j , for a general class of kernel functions that encompasses the one used in [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF]. Up to our knowledge, this provides the only theoretical guarantee on a measure-based clustering algorithm.

At last, we perform numerical experiments in Section 4 to assess the effectiveness of our method on real and synthetic data, in a clustering and classification framework. In a nutshell, our vectorization scheme combined with standard algorithms provides state-of-the art performances on various classification and clustering problems, with a lighter computational cost. The classification problems encompass sentiment analysis of IMDB reviews [START_REF] Maas | Learning Word Vectors for Sentiment Analysis[END_REF] as well as large-scale graph classification [START_REF] Rozemberczki | An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs[END_REF][START_REF] Yanardag | Deep Graph Kernels[END_REF]. Surprisingly, our somehow coarse approach turns out to outperform more involved methods in several large-scale graph classification problems.

The paper is organized as follows: Section 2 introduces our general vectorization technique, and conditions that guarantee a correct clustering based on it. Section 3 gives some detail on how our vectorization points are build, by introducing the mean measure k-points quantization problem. Then, two theoretically grounded algorithms are described to solve this problem from the sample X 1 , . . . , X n . Section 3.3 investigates the special case where the measures are persistence diagrams built from samplings of different shapes, showing that all the previously exposed theoretical results apply in this framework. The numerical experiments are exposed in Section 4. Sections 5 and 6 gather the main proofs of the results. Proofs of intermediate and technical results are deferred to Appendix A.

Vectorization and clustering of measures

Throughout the paper we will consider finite measures on the d-dimensional ball B(0, R) of the Euclidean space R d , equipped with its Borel algebra. Let M(R, M ) denote the set of such measures of total mass smaller than M . For µ ∈ M(R, M ) and f a borelian function from R d to R, we denote by f (y)µ(dy) integration of f with respect to µ, whenever |f (y)|µ(dy) is finite. We let X be a random variable with values in M(R, M ) (equipped with the smallest algebra such that f dX is measurable, for any continuous and bounded f ), and X 1 , . . . , X n be an i.i.d sample drawn from X.

Vectorization of measures

We aim to provide a map v from M(R, M ) into a finite-dimensional space that preserves separation between sources. That is, if we assume that there exists

(Z 1 , . . . , Z n ) ∈ [[1, L]] n a vector of (hidden) label variables such that X i | {Z i = } ∼ X ( ) , for different mixture components X (1) , . . . , X (L) taking values in M(R, M ), we want v(X i1 ) -v(X i2 ) to be large whenever Z i1 = Z i2 .
The intuition is the following. Let µ 1 = µ 2 be two different measures on B(0, R). Then there exists x ∈ B(0, R) and r > 0 such that µ 1 (B(x, r)) = µ 2 (B(x, r)). Thus, the vectorization that sends X i into X i (B(x, r)) will allow to separate the sources X (1) = δ µ1 and X (2) = δ µ2 . We extend this intuition to the multiclasses case. To adopt the quantization terminology, for k ∈ N * we let c 1 , . . . , c k be codepoints, and c = (c 1 , . . . , c k ) ∈ (R d ) k is called a codebook. For a given codebook c and a scale r > 0, we may represent a measure µ via the vector of weights (µ(B(c 1 , r)), . . . , µ(B(c k , r))) that encodes the mass that µ spreads around every pole c j . Provided that the codepoints are discriminative (this will be discussed in the following section), separation between clusters of measure will be preserved. In practice, convolution with kernels is often preferred to local masses (see, e.g., [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF]). To ease computation, we will restrict ourselves to the following class of kernel functions.

Definition 1. For (p, δ) ∈ N * × [0, 1/2], a function ψ : R + → R + is called a (p, δ)-kernel function if i) ψ ∞ ≤ 1, ii) sup |u|≤1/p ψ(u) ≥ 1 -δ, iii) sup |u|>2p ψ(u) ≤ δ, iv) ψ is 1-Lipschitz.
Note that a (p, δ)-kernel is also a (q, δ)-kernel, for q > p. This definition of a kernel function encompasses widely used kernels, such as Gaussian or Laplace kernels. In particular, the function ψ(u) = exp(-u) that is used in [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF] is a (p, 1/p)-kernel for p ∈ N * . The 1-Lispchitz requirement is not necessary to prove that the representations of two separated measures will be well-separated. However, it is a key assumption to prove that the representations of two measures from the same cluster will remain close in R k . From a theoretical viewpoint, a convenient kernel is

ψ 0 : x → (1 -((x -1) ∨ 0)) ∨ 0, which is a (1, 0)-kernel, thus a (p, 0)-kernel for all p ∈ N * .
From now on we assume that the kernel ψ is fixed, and, for a k-points codebook c and scale factor σ, consider the vectorization

v c,σ : M(R, M ) → [0, M ] k µ → ψ( u -c 1 /σ)µ(du), . . . , ψ( u -c k /σ)µ(du) . (1)
Note that the dimension of the vectorization depends on the cardinality of the codebook c. To guarantee that such a vectorization is appropriate for a clustering purpose is the aim of the following section.

Discriminative codebooks and clustering of measures

In this section we assume that there exists a vector (Z

1 , . . . , Z n ) ∈ [[1, L]
] n of (hidden) label variables, and let M 1 , . . . , M L be such that, if

Z i = , X i ∈ M(R, M ).
We also denote M = max ≤L M , and investigate under which conditions the vectorization exposed in the above section provides a representation that is suitable for clustering. For a given codebook c, we introduce the following definition of (p, r, ∆)-scattering to quantify how well c will allow to separate clusters.

Definition 2. Let (p, r, ∆) ∈ (N * × R + × R + ). A codebook c ∈ B(0, R) k is said to (p, r, ∆) -shatter X 1 , . . . , X n if, for any i 1 , i 2 ∈ [[1, n]] such that Z i1 = Z i2 , there exists j i1,i2 ∈ [[1, k]] such that X i1 (B(c ji 1 ,i 2 , r/p)) ≥ X i2 (B(c ji 1 ,i 2 , 4pr)) + ∆, or X i2 (B(c ji 1 ,i 2 , r/p)) ≥ X i1 (B(c ji 1 ,i 2 , 4pr)) + ∆.
In a nutshell, the codebook c shatters the sample if two different measures from two different clusters have different masses around one of the codepoint of c, at scale r. Note that, for any i, j, X i (B(c j , r/p)) ≥ X i ({c j }), so that a stronger definition of shattering in terms of X i ({c j })'s might be stated, in the particular case where X i ({c j }) > 0. The following Proposition ensures that a codebook which shatters the sample yields a vectorization into separated clusters, provided the kernel decreases fast enough.

Proposition 3. Assume that c ∈ B(0, R) k shatters X 1 , . . . , X n , with parameters (p, r, ∆). Then, if Ψ is a (p, δ)-kernel, with δ ≤ ∆ 4M , we have, for all i 1 , i 2 ∈ [[1, n]] and σ ∈ [r, 2r], Z i1 = Z i2 ⇒ v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≥ ∆ 2 .
A proof of Proposition 3 can be found in Section 5.1. This proposition sheds some light on how X 1 , . . . , X n has to be shattered with respect to the parameters of Ψ. Indeed, assume that ∆ = 1 (that is the case if the X i 's are integer-valued measures, such as count processes for instance). Then, to separate clusters, one has to choose δ small enough compared to 1/M , and thus p large enough if Ψ is non-increasing. Hence, the vectorization will work roughly if the support points of two different counting processes are rp-separated, for some scale r. This scale r then drives the choice of the bandwidth σ. Section 3.3 below provides an instance of shattered measures in the case where measures are persistence diagrams originating from well separated shapes. If the requirements of Proposition 3 are fulfilled, then a standard hierarchical clustering procedure such as Single Linkage with L ∞ distance will separate the clusters for the scales smaller than ∆/2. Note that, without more assumptions, this global clustering scheme can result in more than L clusters, nested into the ground truth label classes. Now, to achieve a perfect clustering of the sample based on our vectorization scheme, we have to ensure that measures from the same cluster are not too far in terms of Wasserstein distance, implying in particular that they have the same total mass. This motivates the following definition. For p ∈ [ [1, +∞]] and

µ 1 , µ 2 ∈ M(R, M ) such that µ 1 (R d ) = µ 2 (R d ), we denote by W p (µ 1 , µ 2 ) the p-Wasserstein distance between µ 1 and µ 2 . Definition 4. The sample of measures X 1 , . . . X n is called w-concentrated if, for all i 1 , i 2 in [[1, n]] such that Z i1 = Z i2 , i) X i1 (R d ) = X i2 (R d ), ii) W 1 (X i1 , X i2 ) ≤ w.
It now falls under the intuition that well-concentrated and shattered sample measures are likely to be represented in R k by well-clusterable points. A precise statement is given by the following Proposition 5.

Proposition 5. Assume that X 1 , . . . , X n is w-concentrated. If Ψ is 1-Lipschitz, then, for all c ∈ B(0, R) k and σ > 0, for all i 1 , i 2 in [[1, n]] such that Z i1 = Z i2 , v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≤ w σ .
Therefore, if X 1 , . . . , X n is (p, r, ∆)-shattered by c, and (r∆/4)-concentrated, then, for any (p, δ)-kernel satisfying δ ≤ ∆ 4M , we have, for σ ∈ [r, 2r],

Z i1 = Z i2 ⇒ v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≤ ∆ 4 , Z i1 = Z i2 ⇒ v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≥ ∆ 2 .
A proof of Proposition 5 is given in Section 5.2. An immediate consequence of Proposition 5 is that (p, r, ∆)-shattered and r∆/4-concentrated sample measures can be vectorized in R k into a point cloud that is structured in L clusters. These clusters can be exactly recovered via Single Linkage clustering, with stopping parameter in ]∆/4, ∆/2]. In practice, tuning the parameter σ is crucial. Some heuristic is proposed in [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF] in the special case of i.i.d persistence diagrams. An alternative calibration strategy is proposed in Section 3.3. Constructing shattering codebooks from sample is the purpose of the following section.

Quantization of the mean measure

To find discriminative codepoints from a measure sample X 1 , . . . , X n , a naive approach could be to choose a ε-grid of B(0, R), for ε small enough. Such an approach ignores the sample, and results in quite large codebooks, with k ∼ (R/ε) d codepoints. An opposite approach is to sample k i points from every X i , with k = n i=1 k i , resulting in a k-points codebook that might miss some discriminative areas, especially in the case where discriminative areas have small X i -masses. We propose an intermediate procedure, based on quantization of the mean measure. Definition 6 below introduces the mean measure. Definition 6. Let B(R d ) denote the borelian sets of R d . The mean measure E(X) is defined as the measure such that

∀A ∈ B(R d ) E(X)(A) = E (X(A)) .
The empirical mean measure Xn may be defined via

Xn (A) = 1 n n i=1 X i (A).
In the case where the measures of interest are persistence diagrams, the mean measure defined above is the expected persistence diagram, defined in [START_REF] Chazal | The density of expected persistence diagrams and its kernel based estimation[END_REF]. If the sample measures are point processes, E(X) is the intensity function of the process. It is straightforward that, if P (X ∈ M(R, M )) = 1, then both E(X) and Xn are (almost surely) elements of M(R, M ).

For a codebook c = (c 1 , . . . , c k ) ∈ B(0, R) k , we let

W j (c) = {x ∈ R d | ∀i < j x -c j < x -c i and ∀i > j x -c j ≤ x -c i }, N (c) = {x | ∃i < j x ∈ W i (c) and x -c i = x -c j },
so that (W 1 (c), . . . , W k (c)) forms a partition of R d and N (c) represents the skeleton of the Voronoi diagram associated with c. To grid the support of E(X), we want to minimize the distortion F , that is

F (c) = min j=1,...,k u -c j 2 E(X)(du) = W 2 2 (E(X), P c ),
where

P c = k j=1 E(X)(W j (c))δ cj is a measure supported by c. It is worth noting that if P k = k j=1 µ j δ cj , with k j=1 µ j = E(X)(R d ), then W 2 2 (E(X), P k ) ≥ W 2
2 (E(X), P c ), so that P c is the best approximation of E(X) with support c in terms of W 2 distance.

According to [START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF]Corollary 3.1], since E(X) ∈ M(R, M ), there exist minimizers c * of F (c), and we let C opt denote the set of such minimizers. As well, if M k (R, M ) denotes the subset of M(R, M ) that consists of distributions supported by k points and c * ∈ C opt , then P c * is a best approximation of E(X) in M k (R, M ) in terms of W 2 distance. Note that distortions and thus optimal codebooks may be defined for W p , p = 2. However, simple algorithms are available to approximate such a c * in the special case p = 2, as discussed below.

Batch and mini-batch algorithms

This section exposes two algorithms that are intended to approximate a best kpoints codebook for E(X) from a measure sample X 1 , . . . , X n . These algorithms are extensions of two well-known clustering algorithms, namely the Lloyd algorithm ( [START_REF] Lloyd | Least squares quantization in PCM[END_REF]) and Mac Queen algorithm ( [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]). We first introduce the counterpart of Lloyd algorithm.

Algorithm 1: Batch algorithm (Lloyd) Input : X 1 , . . . , X n and k ; # Initialization Sample c

(0) 1 , c (0) 2 ,. . . c (0) k from Xn . ; while c (t+1) = c (t) do : # Centroid update . f o r j in 1 . . k : c (t+1) j = 1 Xn(Wj (c (t) ))
u1 Wj (c (t) ) (u) Xn (du) ; Output : c (T ) (codebook of the last iteration) .

Note that Algorithm 1 is a batch algorithm, in the sense that every iteration needs to process the whole data set X 1 , . . . , X n . Fortunately, Theorem 9 below ensures that a limited number of iterations are required for Algorithm 1 to provide an almost optimal solution. In the sample point case, that is when we observe n i.i.d points X

(1) i , Algorithm 1 is the usual Lloyd's algorithm. In this case, the mean measure E(X) is the distribution of X 1 , that is the usual sampling distribution of the n i.i.d points. As well, the counterpart of Mac-Queen algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] for standard k-means clustering is the following mini-batch algorithm. We let π B(0,R) k denote the projection onto B(0, R) k .

Algorithm 2: Mini-batch algorithm (Mac-Queen) Input : X 1 , . . . , X n , divided into mini-batches (B 1 , . . . , B T ) of sizes (n 1 , . . . , n T ), and k. For j = 1, . . . , T , B j is divided in two halves, B

(1) j and B

(2)

j . Maximal radius R ; # Initialization Sample c (0) 1 , c (0) 2 ,. . . c (0) k from Xn . ; f o r j = 0, . . . , T -1 do : # Centroid update . f o r j in 1 . . k : c (t+1) j = π B(0,R) k c (t) j - (c (t) j -u)1 W j (c (t) ) (u) XB (2) t+1 (du)
(t+1) XB (1) t+1 (Wj(c (t) )) ;

Output : c (T ) (codebook of the last iteration) .

Note that the mini-batches split in two halves is motivated by technical considerations only that are exposed in Section 6.2. Whenever n i = 1 for i = 1, . . . , n (and

B (1) i = B (2) i = {X i }), Algorithm 2 is
a slight modification of the original Mac-Queen algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. Indeed, the Mac-Queen algorithm takes mini-batches of size 1, and estimates the population of the cell j at the t-th iteration via

t =1 p( ) j instead of tp (t) j , where p(t) j = XB (1) t W j (c (t)
) . These modifications are motivated by Theorem 10, that guarantees near-optimality of the output of Algorithm 2, provided that the mini-batches are large enough.

Theoretical guarantees

We now investigate the distortions of the outputs of Algorithm 1 and 2. In what follows, F * will denote the optimal distortion achievable with k points, that is F * = F (c), where c ∈ C opt . Note that F * = 0 if and only if E(X) is supported by less than k points, in which case the quantization problem is trivial. In what follows we assume that E(X) is supported by more than k points. Basic properties of C opt are recalled below.

Proposition 7. [24, Proposition 1] Recall that E(X) ∈ M(R, M ). Then, 1. B = inf c * ∈Copt,j =i c * i -c * j > 0, 2. p min = inf c * ∈Copt,j=1,...,k E(X) (W j (c * )) > 0.
We will further assume that E(X) satisfies a so-called margin condition, defined in [22, Definition 2.1] and recalled below. For any subset A of an Euclidean space, and r > 0, we denote by B(A, r) the set ∪ u∈A B(u, r). Definition 8. E(X) ∈ M(R, M ) satisfies a margin condition with radius r 0 > 0 if and only if, for all 0 ≤ t ≤ r 0 ,

sup c * ∈Copt E(X) (B(N (c * ), t)) ≤ Bp min 128R 2 t.
In a nutshell, a margin condition ensures that the mean distribution E(X) is well-concentrated around k poles. For instance, finitely-supported distributions satisfy a margin condition. Following [START_REF] Levrard | Quantization/Clustering: when and why does k-means work[END_REF], a margin condition will ensure that usual k-means type algorithms are almost optimal in terms of distortion. Up to our knowledge, margin-like conditions are always required to guarantee convergence of Lloyd-type algorithms [START_REF] Tang | On Lloyd's Algorithm: New Theoretical Insights for Clustering in Practice[END_REF][START_REF] Levrard | Quantization/Clustering: when and why does k-means work[END_REF].

A special interest will be paid to the sample-size dependency of the excess distortion. From this standpoint, a first negative result may be derived from [START_REF] Levrard | Quantization/Clustering: when and why does k-means work[END_REF]Proposition 7]. Namely, for any empirically designed codebook ĉ, we have sup {X|E(X) has a r 0 -margin}

E(F (ĉ) -F * ) E(X)(R d ) ≥ c 0 R 2 k 1-2 d n . (2)
In fact, this bounds holds in the special case where X satisfies the additional assumption X = δ X (1) a.s., pertaining to the vector quantization case. Thus it holds in the general case. This small result ensures that the sample-size dependency of the minimax excess distortion over the class of distribution of measures whose mean measure satisfies a margin condition with radius r 0 is of order 1/n or greater.

A first upper bound on this minimax excess distortion may be derived from the following Theorem 9, that investigates the performance of the output of Algorithm 1. We recall that, for N ∈ N * , M N (R, M ) denotes the subset of measures in M(R, M ) that are supported by N points.

Theorem 9. Let X ∈ M Nmax (R, M ), for some N max ∈ N * . Assume that E(X) satisfies a margin condition with radius r 0 , and denote by

R 0 = Br0 16 √ 2R , κ 0 = R0 R . Choose T = log(n) log(4/3) , and let c (T ) denote the output of Algorithm 1. If c (0) ∈ B(C opt , R 0 ), then, for n large enough, with probability 1 -9e -c1np 2 min κ 2 0 /M 2 -e -x ,
where c 1 is a constant, we have

F (c (T ) ) -F * ≤ E(X)(R d ) B 2 r 2 0 512R 2 n + C M 2 R 2 k 2 d log(k) np 2 min (1 + x) ,
for all x > 0, where C is a constant.

A proof of Theorem 9 is given in Section 6.1. Combined with (2), Theorem 9 ensures that Algorithm 1 reaches the minimax precision rate in terms of excess distortion after O(log(n)) iterations, provided that the initialization is good enough. Note that Theorem 9 is valid for discrete measures that are supported by a uniformly bounded number of points N max . This assumption is relaxed for Algorithm 2 in Theorem 10.

In the vector quantization case, Theorem 9 might be compared with [START_REF] Levrard | Nonasymptotic bounds for vector quantization in Hilbert spaces[END_REF]Theorem 3.1] for instance. In this case, the dependency on the dimension d provided by Theorem 9 is sub-optimal. Slightly anticipating, dimension-free bounds in the mean-measure quantization case exist, for instance by considering the output of Algorithm 2.

Theorem 9 guarantees that choosing T = 2 log(n) and repeating several Lloyd algorithms starting from different initializations provides an optimal quantization scheme. From a theoretical viewpoint, for a fixed R 0 , the number of trials to get a good initialization grows exponentially with the dimension d. In fact, Algorithm 1 seems quite sensitive to the initialization step, as for every EM-like algorithm. From a practical viewpoint, we use 10 initializations using a k-means++ sampling [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF] for the experiments of Section 4, leading to results that are close to the reported ones for Algorithm 2.

Note that combining [24, Theorem 3] or [START_REF] Tang | On Lloyd's Algorithm: New Theoretical Insights for Clustering in Practice[END_REF] and a deviation inequality for distortions such as in [START_REF] Levrard | Nonasymptotic bounds for vector quantization in Hilbert spaces[END_REF] gives an alternative proof of the optimality of Lloyd type schemes, in the sample points case where X i = δ X (1) i . In addition, Theorem 9 provides an upper bound on the number of iterations needed, as well as an extension of these results to the quantization of mean measure case. Its proof, that may be found in Section 6.1, relies on stochastic gradient techniques in the convex and non-smooth case. Bounds for the single-pass Algorithm 2 might be stated the same way.

Theorem 10. Let X ∈ M(R, M ). Assume that E(X) satisfies a margin condition with radius r 0 , and denote by 2 , where c is a positive constant, and c (T ) denotes the output of Algorithm 2, then, provided that c (0) ∈ B(C opt , R 0 ), we have

R 0 = Br0 16 √ 2R , κ 0 = R 0 /R. If (B 1 , . . . , B T ) are equally sized mini-batches of length ckM 2 log(n)/(κ 0 p min )
E F (c (T ) ) -F * ≤ E(X)(R d ) Ck 2 M 3 R 2 log(n) nκ 2 0 p 3 min .
In the sample point case, the same result holds with the centroid update

c (t+1) j = c (t) j - (c (t) j -u)1 Wj (c (t) ) (u) XBt+1 (du) (t + 1) XBt+1 W j (c (t) ) ,
that is without splitting the batches.

A proof of Theorem 10 is given in Section 6.2. Note that Theorem 10 does not require the values of X to be finitely supported measures, contrary to Theorem 9. Theorem 10 entails that the resulting codebook of Algorithm 2 has an optimal distortion, up to a log(n) factor and provided that a good enough initialization is chosen. As for Algorithm 1, several initializations may be tried and the codebook with the best empirical distortion is chosen. In practice, the results of Section 4 are given for a single initialization at random using k-means++ sampling [START_REF] Arthur | k-means++: the advantages of careful seeding[END_REF].

Note that Theorem 10 provides a bound on the expectation of the distortion. Crude deviation bounds can be obtained using for instance a bounded difference inequality (see, e.g., [START_REF] Boucheron | Oxford A nonasymptotic theory of independence[END_REF]Theorem 6.2]). In the point sample case, more refined bounds can be obtained, using for instance [22, Theorem 4.1, Proposition 4.1]. To investigate whether these kind of bounds still hold in the measure sample case is beyond the scope of the paper. Note also that the bound on the excess distortion provided by Theorem 10 does not depend on the dimension d. This is also the case in [START_REF] Levrard | Nonasymptotic bounds for vector quantization in Hilbert spaces[END_REF]Theorem 3.1], where a dimension-free theoretical bound on the excess distortion of an empirical risk minimizer is stated in the sample points case. Interestingly, this bound also has the correct dependency in n, namely 1/n. According to Theorem 9 and 10, providing a quantization scheme that provably achieves a dimension-free excess distortion of order 1/n in the sample measure case remains an open question.

We may now connect Theorem 9 and 10 to the results of Section 2.2.

Corollary 11. Assume that E(X) satisfies the requirements of Theorem 9, and that c * provides a (p, r, ∆) shattering of X 1 , . . . , X n , with p ≥ 2. Let ĉn denote the output of Algorithm 1. Then ĉn is a ( p 2 , r, ∆) shattering of X 1 , . . . , X n , with probability larger than 1 -exp -C

nr 2 p 2 min p 2 M 2 R 2 k 2 d log(k) - p 2 min B 2 r 2 0 M 2 R 4 k 2 d log(k)
, where C is a constant.

A proof of Corollary 11 is given in Section 6.3. Corollary 11 ensures that if c * shatters well X 1 , . . . , X n , so will ĉn , where ĉn is built with Algorithm 1. To fully assess the relevance of our vectorization technique, it remains to prove that k-points optimal codebooks for the mean measure provide a shattering of the sample measure, with high probability. This kind of result implies more structural assumptions on the components of the mixture X. The following section describes such a situation.

Application: clustering persistence diagrams

In this section we investigate the properties of our measure-clustering scheme in a particular instance of i.i.d. measure observations. Recall that in our mixture model, (Z 1 , . . . , Z n ) is the vector of i.i.d. labels such that X i | {Z i = } ∼ X ( ) . We further denote by π = P(Z i = ), so that X ∼ L =1 π X ( ) . Our mixture of persistence diagrams model is the following. For ∈ [[1, L]] let S ( ) denote a compact d -manifold and D ( ) denote the persistence diagram generated by d S ( ) , the distance to S ( ) . This persistence diagram can either be thought of as a multiset of points (set of points with integer-valued multiplicity) in the half-plane

H + = {(b, d) ∈ R 2 | 0 ≤ b ≤ d} (
for a general introduction to persistence diagrams the reader is referred to [5, Section 11.5]), or as a discrete measure on H + (see, e.g., [START_REF] Chazal | The density of expected persistence diagrams and its kernel based estimation[END_REF] for more details on the measure point of view on persistence diagrams). For a fixed scale s > 0, we define D

= (m 1 , m 2 ) ∈ D such that m 2 -m 1 ≥ s is finite. A proof of Lemma 12 is given in Appendix A.2. Now, for ∈ [[1, L]] we let Y N be an N -sample drawn on S ( ) with density f ( ) satisfying f ( ) (u) ≥ f min, , for u ∈ S ( ) . If D( ) denotes the persistence diagram generated by d Y N , we define X ( ) as a thresholded version of D( ) , that is X ( ) ∼ D( ) ≥s-h ,
for some bandwidth h . To sum up, conditionally on Z i = , X i is a thresholded persistence diagram corresponding to a N -sampling of the shape S ( ) . To retrieve the labels Z i 's from a vectorization of the X i 's, we have to assume that the persistence diagrams of the underlying shapes differ by at least one point.

Definition 13. The shapes S (1) , . . . , S ( ) are discriminable at scale s if for any

1 ≤ 1 < 2 ≤ L there exists m 1, 2 ∈ H + such that D ( 1) ≥s ({m 1 , 2 }) = D ( 2) ≥s ({m 1, 2 }),
where the thresholded persistence diagrams are considered as measures.

Note that if m 1, 2 satisfies the discrimination condition stated above, then

m 1 , 2 ∈ D ( 1 ) ≥s or m 1, 2 ∈ D ( 2)
≥s . Next, we must ensure that optimal codebooks of the mean measure have codepoints close enough to discrimination points. Assume that S (1) , . . . , S (L) are discriminable at scale s, and let m 1 , . . . , m k0 denote the discrimination points. Let K 0 (h) denote and(c * 1 , . . . , c * k ) denote an optimal k-points quantizer of E(X). Then, provided that N is large enough for all , we have

inf{k ≥ 0 | ∃t 1 , . . . , t k L =1 D ( ) ≥s \ {m 1 , . . . , m k0 } ⊂ k s=1 B ∞ (t s , h)}. Let k ≥ k 0 + K 0 (h),
∀j ∈ [[1, k 0 ]] ∃p ∈ [[1, k]] c * p -m j ∞ ≤ 5 √ M h √ π min .
The proof of Proposition 14 is given in Section 6.4. If D≥s denotes the mean persistence diagram

L =1 π D ( )
≥s , and D≥s has K 0 points, then it is immediate that k 0 + K 0 (h) ≤ K 0 . Moreover, we also have k 0 ≤ L(L+1)

2

. Proposition 14 ensures that the discrimination points are well enough approximated by optimal k-centers of the expected persistence diagram E(X), provided the shapes S ( ) are well-enough sampled and k is large enough so that D≥s is well-covered by k balls with radius h. Note that this is always the case if we choose k = K 0 , but also allows for smaller k's.

In turn, provided that the shapes S (1) , . . . , S (L) are discriminable at scale s and that k is large enough, we can prove that an optimal k-points codebook c * is a (p, r, ∆)-shattering of the sample, with high probability.

Proposition 15. Assume that the requirements of Proposition 14 are satisfied. Let B = min i=1,...,k0,j=1,...,K0,j =i m i -m j ∞ ∧ s. Let κ > 0 be a small enough constant. Then, if N is large enough for all ∈ [[1, ]], X 1 , . . . , X n is (p, r, 1)shattered by c * , with probability larger than

1 -n max ≤L N - (κ B) d f min, N C d log(N )
, provided that

• r p ≥ 2κ B, • 4rp ≤ 1 2 -κ B. Moreover, on this probability event, X 1 , . . . , X n is 2M κ B-concentrated.
A proof of Proposition 15 is given in Section 6.5. In turn, Proposition 15 can be combined with Proposition 5 and Corollary 11 to provide guarantees on the output of Algorithm 1 combined with a suitable kernel. We choose to give results for the theoretical kernel ψ 0 : x → (1 -((x -1) ∨ 0)) ∨ 0, and for the kernel used in [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF], ψ AT = x → exp(-x).

Corollary 16. Assume that E(X) satisfies a margin condition, and that the requirements of Proposition 15 are satisfied. For short, denote by v i the vectorization of X i based on the output of Algorithm 1. Then, with probability larger than

1-exp -C nr 2 p 2 min p 2 M 2 R 2 k 2 d log(k) - p 2 min B 2 r 2 0 M 2 R 4 k 2 d log(k) -n max ≤L N - (κ B) d f min, N C d log(N )
, where κ and C are small enough constants, we have

Z i1 = Z i2 ⇒ v i1 -v i2 ∞ ≤ 1 4 , Z i1 = Z i2 ⇒ v i1 -v i2 ∞ ≥ 1 2 ,
for σ ∈ [r, 2r] and the following choices of p and r:

• If Ψ = Ψ AT , p AT = 4M , and r AT = B 32p AT . • If Ψ = Ψ 0 , p 0 = 1 and r 0 = B 32 .
A proof of Corollary 16 is given in Section 6.6. Corollary 16 can be turned into probability bounds on the exactness of the output of hierarchical clustering schemes applied to the sample points. For instance, on the probability event described by Corollary 16, Single Linkage with norm . ∞ will provide an exact clustering. The probability bound in Corollary 16 shed some light on the quality of sampling of each shape that is required to achieve a perfect classification: roughly, for N in Ω(log(n)), the probability of misclassification can be controlled. Note that though the key parameter B is not known, in practice it can be scaled as several times the minimum distance between two points of a diagram.

Investigating whether the margin condition required by Corollary 16 is satisfied in the mixture of shapes framework is beyond the scope of the paper. This condition is needed to prove that the algorithms exposed in Section 3.1 provide provably good approximations of optimal c * 's (those in turn can be proved to be discriminative codebooks). Experimental results below asses the validity of our algorithms in practice.

Experimental results

This section investigates numerical performances of our vectorization and clustering procedure. The vectorization step is carried out using the Atol procedure (Automatic Topologically-Oriented Learning, [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF]): codebooks are defined using Algorithm 2, and an exponential kernel Ψ AT is used to construct the embedding as in [START_REF] Aamari | Nonasymptotic rates for manifold, tangent space and curvature estimation[END_REF]. As a remark, Algorithm 1 combined with other kernels such as ψ 0 lead to similar results in our three experiments.

It is worth noting that our method requires few to no tuning: for all experiments we use minibatches of size 1000 and the same calibration scheme (use a random 10% of the sample measures for learning the space quantization). We use the same kernel Ψ AT , only the Atol budget k (length of the vectorization) will sometimes vary in the three experiments.

Our numerical experiments encompass synthetic measure clustering, but also investigate the performance of our vectorization technique on two (supervised) classification problems: large-scale graph classification and text classification. On these problems, we achieve state-of-the-art performances.

Measure clustering

In this first experiment, we settle in the framework of Section 2.2. Namely, we consider an i.i.d sample drawn from a mixture of measures, and evaluate our method on a clustering task. We generate a synthetic mixture of L measures. We first choose p -1 centers shared by all mixture components on the d -1dimensional sphere of radius 10 and denote them by {S i d | i = 1, . . . , p -1}; then for each mixture component another center is placed at a separate vertex of the d-dimensional unit cube (implying L 2 d ), labeled Cube |d for ∈ [[1, . . . , L]], so that the inner center is the only center that varies amongst mixture components, see instances Figure 1. The support centers C for the mixture component are given by

C = {S i d | i = 1, . . . , p -1} ∪ Cube |d . (3)
For every mixture component and signal level r > 0, we then make N normal simultaneous draws with variance 1 centered around every element of r × C , resulting in a point cloud of cardinality p × N that is interpreted as a measure.

To sum up, the -th mixture component X k has distribution

X = c∈C i=1,...,N {rc + ε c,i },
where the ε's are i.i.d standard d-dimensional Gaussian random variables.

We compare with several measure clustering procedures, some of them being based on alternative vectorizations. Namely, the rand procedure randomly chooses codepoints among the sample measures points, whereas the grid procedure takes as codepoints a regular grid of [0, 10r] d . For fair comparison we use the same kernel Ψ AT as in Atol to vectorize from these two codebooks.

We also compare with two other standard clustering procedures: the histogram procedure, that learns a regular tiling of the space and vectorizes measures by counting inside the tiles, and the W2-spectral method that is just spectral clustering based on the W 2 distance (to build the Gram matrix). Note that the histogram procedure is conceptually close to the grid procedure.

At last, for all methods the final clustering step consists in a standard k-means clustering with 100 initializations. We designed these mixtures to exemplify problems where the data are significantly separated (by L discriminative points corresponding to hypercube vertices), but also very similar by including draws from the same set of centers on the outer sphere. In this experiment r may be thought of as the strength of the signal separation, and p can be interpreted as a measure of noise. Empirically we use two different setups for the number of supporting centers p: p = 4 or p = 20, that we interpret respectively as low and high noise situations in Figure 1. We fix L = 3, and generate measures in dimension 2 and 5. We also set N = 25 and sample every mixture component 20 times, so that the final sample of measures consist of 60 i.i.d. finite measures, each with 25 × p points.

Regardless of the dimension, for the p = 4 setup, W2-spectral takes about 4.3 seconds on average, 0.2 seconds for Atol, and the other methods are naturally faster. Note that for the p = 20 case, the W2-spectral clustering procedure runs takes too long to compute and is not reported, whereas Atol runs in 0.5 seconds on average. Each experiment is performed identically a hundred times and the resulting average normalized mutual information (NMI) with true labels and 95% confidence intervals are presented for each method. Two sets of experiments are performed, corresponding to the following two questions.

Q1: at a given signal level r = 1, for increasing budget (that is, the size of the codebooks used in the vectorization process), how accurate are methods at clustering 3-mixtures? Q1 aims at comparing the various methods potentials at capturing the underlying signal with respect to budget.

Results are displayed in Figure 2. The Atol procedure is shown to produce the best results in almost all situations. Namely, it is the procedure that will most likely cluster the mixture exactly while requiring the least amount of budget for doing so. The grid procedures grid and histogram naturally suffer from the dimension growth (bottom panels). The oscillations of the histogram procedure performances, exposed in the upper right panel, may be due to the existence of a center tile (that cannot discriminate between several vertices of the cube) that our oversimple implementation allows. To draw a fair comparison, the local minima of the histogram curve are not considered as representative, leading to an overall flat behavior of this method in the case d = 2, p = 20. In dimension 2 the grid procedure shows to be very efficient, but for measures in dimension 5 it seems always better to select codepoints at random, rather than using some instance of regular grid. Whenever possible, W2-spectral outperforms all vectorization-based methods, at the price of a significantly larger computational cost. Note however that the performance gap with Atol is discernable for small budgets only (k ≤ 15).

Q2: for a given budget k = 32 and increasing signal level, how accurate are methods at clustering 3-mixtures? Q2 investigates how the various methods fare with respect to signal strength at a given, low codebook length k = 32, the most favorably low budget for regular grid procedures in dimension 5.

Results are shown in Figure 3. Atol and grid procedures give similar results, and compare well to W2-spectral in the case p = 4. Figure 3 also confirms the intuition that the rand procedure is more sensitive to p than competitors, resulting in significantly weaker performances when p = 20.

Large-scale graph classification

We now look at the large-scale graph classification problem. Provided that graphs may be considered as measures, our vectorization method provides an embedding into R k that may be combined with standard learning algorithms. In this framework, our vectorization procedure can be thought of as a dimensionality reduction technique for supervised learning, that is performed in an unsupervised way. Note that the notion of shattering codebook introduced in Section 2.2 is still relevant in this context, since a (p, r, ∆)-shattering codebook would lead to exact sample classification if combined with a classification tree for instance. Theoretically investigating the generalization error of such an approach is beyond the scope of the paper.

As exposed above, since Atol is an unsupervised procedure that is not specifically conceived for graphs, it is likely that other dedicated techniques would provide better performances in this graph classification problem. However, its simplicity can be a competitive advantage for large-scale applications.

There are multiple ways to interpret graphs as measures. In this section we borrow from [START_REF] Carrière | PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures[END_REF]: for a diffusion time t > 0 we compute the Heat Kernel Signatures (HKS t ) for all vertices in a graph, so that each graph G(V, E) is embedded in R |V | (see, e.g., [7, Section 2.2]). Then four graph descriptors per diffusion time may be computed using the extended persistence framework (see, e.g., [7, Section 2.1]), that is four types of persistence diagrams (PDs). Schematically for a graph G(V, E) the descriptors are derived as:

G(V, E) heat kernel -------→ signatures HKS t (G) ∈ R |V | , G(V, E) extended -------→ persistence PD(HKS t (G), G) ∈ (M(R 2 )) 4 . (4)
In these experiments we will show that the graph embedding strategy of (4) paired with Atol can perform up to the state of the art on large-scale graph classification problems. We will also demonstrate that Atol is well assisted but not dependent on the aforementioned TDA tools. Large-scale binary classification from [START_REF] Rozemberczki | An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs[END_REF] Recently [START_REF] Rozemberczki | An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs[END_REF] introduced large-scale graph datasets of social or web origin. For each dataset the associated task is binary classification. The authors perform a 80% train/test split of the data and report mean area under the curve (AUC) along with standard errors over a hundred experiments for all the following graph embedding methods. SF from [START_REF] De Lara | A Simple Baseline Algorithm for Graph Classification[END_REF] extracts the k lowest spectral values from the graph Laplacian, and a standard Random Forest Classifier (RFC) for classification. NetLSD from [START_REF] Tsitsulin | NetLSD[END_REF] uses a more refined representation of the graph Laplacian, the heat trace signature (a global variant of the HKS) of a graph using 250 diffusion times, and a 1layer neural network (NN) for classification. FGSD from [START_REF] Verma | Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs[END_REF] computes the biharmonic spectral distance of a graph and uses histogram vectorization with small binwidths that results in vectorization of size [100, 1000000], with a Support Vector Machine (SVM) classifier. GeoScattering from [START_REF] Gao | Geometric Scattering for Graph Data Analysis[END_REF] uses graph wavelet transform to produce 125 graph embedding features, also with a SVM classifier.

We add our own results for Atol paired with (4): we use the extended persistence diagrams as input for Atol computed from the HKS values with diffusion times t 1 = .1, t 2 = 10, and vectorize the diagrams with budget k = 10 for each diagram type and diffusion time so that the resulting vectorization for graph G is v Atol (G) ∈ R 2×4×10 . We then train a standard RFC (as in [START_REF] De Lara | A Simple Baseline Algorithm for Graph Classification[END_REF], we use the implementation from sklearn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] with all default parameters) on the resulting vectorized measures.

The results are shown Table 1. Atol is close to or over the state-of-the-art for all four datasets. Most of these methods operate directly from graph Laplacians so they are fairly comparable, in essence or as for the dimension of the embedding that is used. The most positive results on github stargazers improves on the best method by more than 6 points. A variant of the large-scale graph classification from [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF] The graph classification tasks above were binary classifications. [START_REF] Yanardag | Deep Graph Kernels[END_REF] introduced now popular datasets of large-scale graphs associated with multiple classes. These datasets have been tackled with top performant graph methods including the graph kernel methods RetGK from [START_REF] Zhang | RetGK: Graph Kernels based on Return Probabilities of Random Walks[END_REF], WKPI from [START_REF] Zhao | Learning metrics for persistence-based summaries and applications for graph classification[END_REF] and GNTK from [START_REF] Du | Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels[END_REF] (combined with a graph neural network), and the aforementioned graph embedding method FGSD from [START_REF] Verma | Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs[END_REF]. PersLay from [START_REF] Carrière | PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures[END_REF] is not designed for graphs but used (4) as input for a 1-NN classifier. Lastly, in [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF], the authors also used (4) and the same diagrams as input data for the Atol procedure and obtained competitive results within reasonable computation times (the largest is 110 seconds, for the COLLAB dataset, see [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF]Section 3.1] for all computation times).

Here we propose to bypass the topological feature extraction step in (4). Instead of topological descriptors, we use simpler graph descriptors: we compute four HKS descriptors corresponding to diffusion times t 1 = .1, t 2 = 1, t 3 = 10, t 4 = 100 for all vertices in a graph, but this time directly interpret the output as a measure embedding in dimension 4. From there we use Atol with k = 80 budget. Therefore each graph G(V, E) is embedded in R 4|V | seen as M(R 4 ) and our measure vectorization framework is readily applicable from there. To sum-up we now use the point of view:

G(V, E) heat kernel -------→ signatures HKS t1,t2,t3,t4 (G) ∈ R 4|V | ≈ M(R 4 ). ( 5
)
It is important to note that the proposed transformation from graphs to measures can be computed using any type of node or edge embedding. Our vectorization method could be applied the same way as for HKS's.

Table 2

Mean accuracies and standard deviations for the large multi-classes problems of [START_REF] Yanardag | Deep Graph Kernels[END_REF].

On Table 2 we quote results and competitors from [START_REF] Royer | ATOL: Measure Vectorisation for Automatic Topologically-Oriented Learning[END_REF] and on the right column we add our own experiment with Atol. The Atol methodology works very efficiently with the direct HKS embedding as well, although the results tend to be slightly inferior. This may hint at the fact that although PDs are not essential to capturing signal from this dataset, they can be a significant addition for doing so. Overall Atol with (5), though much lighter than Atol with (4), remains competitive for large-scale graph multiclass classification.

Text classification with word embedding

At last we intend to apply our methodology in a high-dimensional framework, namely text classification. Basically, texts are sequences of words and if one forgets about word order, a text can be thought of as a measure in the (fairly unstructured) space of words. We use the word2vec word embedding technique ( [START_REF] Mikolov | Distributed Representations of Words and Phrases and their Compositionality[END_REF]), that uses a two-layer neural network to learn a real-valued vector representation for each word in a dictionary in such a way that distances between words are learnt to reflect the semantic closeness between them, with respect to the corpus. Therefore, for a given dimension E ∈ N, every word w is mapped to the embedding space v word2vec (w) ∈ R E , and we can use word embedding to interpret texts as measures in a given word embedding space:

T ∈ M({words}) word -------→ embedding T word2vec = v word2vec (w) w∈T ∈ M(R E ). ( 6
)
In practice we will use the Large Movie Review Dataset from [START_REF] Maas | Learning Word Vectors for Sentiment Analysis[END_REF] for our text corpus, and learn word embedding on this corpus. To ease the intuition, Figure 4 below depicts the codepoints provided by Algorithm 2, based on a 2-dimensional word embedding. Note that this word embedding step does not depend on the classification task that will follow.

We now turn to the task of classification and use the binary sentiment annotation (positive or negative reviews) from the dataset. For classifying texts with modern machine-learning techniques there are several problems to overcome: important words in a text can be found at almost any place, texts usually have different sizes so that they have to be padded in some way, etc. The measure viewpoint is a direct and simple solution.

The successful way to proceed after a word embedding step is to use some form of deep neural network learning. We learn a 100-dimensional word embedding using the word2vec implementation from the gensim module, then compare the following classification methods: directly run a recurrent neural network (LSTM with 64 units), against the Atol vectorization followed by a simple dense layer with 32 units. We measure accuracies through a single 10-fold.

The Atol vectorization with word embedding in dimension 100, 20 centers, and 1-NN classifier reaches 85.6 accuracy with .95 standard deviation. The average quantization and vectorization times are respectively 5.5 and 208.3 seconds. The recurrent neural network alternative with word embedding in dimension 100 reaches 89.3 mean accuracy with .44 standard deviation, for an average run time of about 1 hour.

Naturally the results are overall greatly hindered by the fact that we have treated texts as a separate collection of words, forgetting sentence structure when most competitive methods use complex neural networks to analyse n-uplets of words as additional inputs. Additional precision can be also gained using a task-dependend embedding of words, at the price of a larger computation time (see for instance the kaggle winner algorithm [START_REF] Cherniuk | IMDB review challenge using Word2Vec and BiLSTM[END_REF], with precision 99% and run time 10379 seconds).

Proofs for Section 2

Proof of Proposition 3

Assume that X 1 , . . . , X n is (p, r, ∆)-shattered by c, let i 1 , i 2 in [ [1, n]] be such that Z i1 = Z i2 , and without loss of generality assume that

X i1 (B(c 1 , r/p)) ≥ X i2 (B(c 1 , 4rp)) + ∆.
Let Ψ be a (p, δ)-kernel and σ ∈ [r, 2r]. We have

Ψ( u -c 1 /σ)X i1 (du) ≥ Ψ( u -c 1 /σ)1 B(c1,r/p) (u)X i1 (du) ≥ (1 -δ)X i1 (B(c 1 , r/p)) ≥ X i1 (B(c 1 , r/p)) -δM.
On the other hand, we have that

Ψ( u -c 1 /σ)X i2 (du) ≤ Ψ( u -c 1 /σ)1 B(c1,4pr) X i2 (du) + Ψ( u -c 1 /σ)1 (B(c1,4pr)) c X i2 (du) ≤ X i2 (B(c 1 , 4pr)) + δX i2 ((B(c 1 , 4pr)) c ) ≤ X i1 (B(c 1 , r/p)) -∆ + δM. We deduce that v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≥ ∆ -2δM ≥ ∆ 2 whenever δ ≤ ∆ 4M .

Proof of Proposition 5

Let

i 1 , i 2 in [[1, n]] such that Z i1 = Z i2 . Let (Y 1 , Y 2 ) be a random vector such that Y 1 ∼ X i1 , Y 2 ∼ X i2 , and E( Y 1 -Y 2 ) ≤ w. Let c ∈ B(0, R), we have Ψ( u -c /σ)X i1 (du) -Ψ( u -c /σ)X i2 (du) ≤ |E [Ψ( Y 1 -c /σ) -Ψ( Y 2 -c /σ)]| ≤ E Y 1 -Y 2 σ ≤ w σ , hence v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≤ w/σ. Now if X 1 . . . , X n is r∆/4-concentrated, and σ ∈ [r, 2r], we have v c,σ (X i1 ) -v c,σ (X i2 ) ∞ ≤ ∆ 4 .
6. Proofs for Section 3

Proof of Theorem 9

Throughout this section we assume that E(X) satisfies a margin condition with radius r 0 , and that P(X ∈ M Nmax (R, M )) = 1. The proof of Theorem 9 is based on the following lemma, which ensures that every step of Algorithm 1 is, up to concentration terms, a contraction towards an optimal codebook. We recall here that

R 0 = Br0 16 √ 2R , κ 0 = R0 R .
Lemma 17. Assume that c (0) ∈ B(c * , R 0 ). Then, with probability larger than 1 -9e -c1npmin/M -e -x , for n large enough, we have, for every t,

c (t+1) -c * 2 ≤ 3 4 c (t) -c * 2 + K p 2 min D 2 n , (7)
where

D n = CRM √ n k d log(k) + √ x and C, K are positive constants.
The proof of Lemma 17 is deferred to Appendix A.1.1.

Proof of Theorem 9. Equipped with Lemma 17, the proof of Theorem 9 is straightforward. On the probability event of Lemma 17, using [START_REF] Carrière | PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures[END_REF] we have that

c (t) -c * 2 ≤ 3 4 t c (0) -c * 2 + t-1 p=0 3 4 p K p 2 min D 2 n ≤ 3 4 t c (0) -c * 2 + 4K p 2 min D 2 n .

Proof of Theorem 10

The proof of Theorem 10 follows the proof of [32, Lemma 1]. Throughout this section we assume that E(X) satisfies a margin condition with radius r 0 . The proof of Theorem 10 is based on the following lemma. Recall that

R 0 = Br0 16 √ 2R , κ 0 = R0 R .
We let c (t) denote the output of Algorithm 2 (or its variant in the sample point case).

Lemma 18. Assume that c (0) ∈ B(c * , R 0 ), and

n t ≥ c 0 k 2 M 2 p 2 min κ 2 0 log(n), for some constant c 0 , with n ≥ k. Then we have, for any t = 0, . . . , T -1, E c (t+1) -c * 2 ≤ 1 - 2 -K 1 t + 1 E c (t) -c * 2 + 16kM R 2 p min (t + 1) 2 , (8) with K 1 ≤ 0.5.
The proof of Lemma 18 is deferred to Appendix A.1.2.

Proof of Theorem 10. Equipped with Lemma 18, we can prove Theorem 10 using the same method as in the proof of [START_REF] Rakhlin | Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization[END_REF]Lemma 1]. Namely, denoting by a t = c (t) -c * 2 , we prove recursively that

Ea t ≤ 32kM R 2 p min t .
Denote by G = 16kM R 2 pmin . The case t = 1 is obvious. Next, assuming that Ea t ≤ 2G t and using (8) we may write

Ea t+1 ≤ 1 - 2 t + 1 Ea t + K 1 t + 1 Ea t + G (t + 1) 2 ≤ G t(t + 1) [2t + 2K 1 -1] .
Since K 1 ≤ 1 2 , we get that Ea t+1 ≤ 2G/(t + 1).

Proof of Corollary 11

For n large enough, with probability larger than 1-exp -C

nr 2 p 2 min p 2 M 2 R 2 k 2 d log(k) - p 2 min B 2 r 2 0 M 2 R 4 k 2 d log(k) , we have ĉn -c * ≤ r p , according to Theorem 9. Let i 1 , i 2 ∈ [[1, n]] be such that Z i1 = Z i2 . Without loss of generality assume that X i1 (B(c * 1 , r/p)) ≥ X i2 (B(c * 1 , 4pr)) + ∆. Then X i1 (B(ĉ 1 , 2r/p)) ≥ X i1 (B(ĉ 1 , r/p))), combined with X i2 (B(ĉ 1 , 4(p/2)r)) ≤ X i2 (B(c * 1 , 4pr)) entails that X i1 (B(ĉ 1 , 2r/p)) ≥ X i2 (B(ĉ 1 , 4(p/2)r)) + ∆.

Proof of Proposition 14

The proof of Proposition 14 relies on the two following lemmas. First, Lemma 19 below ensures that the persistence diagram transformation is stable with respect to the sup-norm.

Lemma 19. [START_REF] Cohen-Steiner | Stability of persistence diagrams[END_REF] If X and Y are compact sets of R D , then

d B (D(d X ), D(d Y )) ≤ d X -d Y ∞ .
1 -1 N k d , we have d S -d Y N ∞ ≤ h.
We let Z denote the latent label variable, so that

X | {Z = } ∼ X ( ) , or equivalently X = X (Z) . Now, for ∈ [[1, L]], we let α = 1 N d + 2 d , h = C d log(N ) f min, N 1/d
, for some constants C d , and ≥s have the same number of (multiple) points, when A c occurs. Further, we have

A = { d Y N Z -d S Z ∞ > h Z },
F (m) = E =1 1 Z= min j=1,...,k0+K0(h) u -m j 2 X ( ) (du) = E =1 1 Z= ∩A min j=1,...,k0+K0(h) u -m j 2 X ( ) (du) + E =1 1 Z= ∩A c min j=1,...,k0+K0 (h)
u -m j 2 X ( ) (du) , so that

F (m) ≤ E =1 1 Z= ∩A 4R 2 N d + E =1 1 Z= ∩A c M ( ) 2h 2 ≤ 2h 2 M + 4R 2 L =1 π α N d .
For N large enough so that α N d ≤ M h 2 R 2 , we have F (m) ≤ 6h 2 M . On the other hand, let c be a k-points codebook such that, for every

p ∈ [[1, k]], m 1 -c p ∞ > 5 M πmin h. Then we have F (c) ≥ E    L =1 1 A c ∩Z= X ( ) (B ∞ (m 1 , h))   5 M π min -1   2    h 2 ≥ E    L =1 1 A c ∩Z= n ( ) (m 1 )   5 M π min -1   2    h 2 .
Now let 0 be such that n ( 0) (m 1 ) ≥ 1, and assume that the N 's are large enough so that α ≤ 1 2 . It holds

F (c) ≥   5 M π min -1   2 h 2 π 0 (1 -α 0 ) ≥ 8 M h 2 > F (m),
hence the result.

Proof of Proposition 15

We let M = max ≤L M , h 0 be such that D≥s-h0 = D≥s . Let κ ≤ 1 16 ∧ h0 . Then we have

P ∃i ∈ [[1, n]] | d B (X i , D Zi ≥s ) > κ B ≤ n i=1 P d B (X i , D Zi ) > κ B ≤ n i=1 L =1 π α ≤ n max ≤L α .
For the remaining of the proof we assume that, for i = 1, . . . , n, d B (X i , D Zi ≥s ) ≤ κ B, that occurs with probability larger than 1 -n max ≤L α . Recall that on this probability event, under the assumptions of Proposition 14, X i and D Zi ≥s have the same number of (multiple) points. Let i 1 = i 2 , and assume that

Z i1 = Z i2 = z. Then W ∞ (X i1 , X i2 ) = d B (X i1 , X i2 ) ≤ 2κ B. Hence W 1 (X i1 , X i2 ) ≤ 2M κ B.
Now assume that Z i1 = Z i2 , and without loss of generality m Zi 1 ,Zi 2 = m 1 with

D Zi 1 ≥s ({m 1 }) ≥ D Zi 2 ≥s ({m 1 }) + 1. Let (p, r) in N * × R + be such that r/p ≥ 2κ B and 4rp ≤ 1 2 -κ B. Since c * 1 -m 1 ∞ ≤ κ B and d B (X i1 , D Zi 1 ≥s ) ≤ κ B < h 0 , we get X i1 B(c * 1 , r p ) = D Zi 1 ≥s ({m 1 }).
On the other hand, since 4rp ≤ ( 1 2 -κ) B, we also have Lemma [START_REF] Du | Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels[END_REF]. Assume that c (0) ∈ B(c * , R 0 ). Then, with probability larger than 1 -9e -c1npmin/M -e -x , for n large enough, we have, for every t,

X i2 (B(c * 1 , 4rp)) = D Zi 2 ≥s ({m 1 }). Thus X 1 , . . . , X n is (p, r, 1)-shattered by c * . • k j=1 |p j (c) -p j (c * )| ≤ pmin 64 , • k j=1 (u -c j )1 Wj (c) (u)E(X)(du) -p j (c * )(c * j -c j ) ≤ pmin
c (t+1) -c * 2 ≤ 3 4 c (t) -c * 2 + K p 2 min D 2 n , (7)
where

D n = CRM √ n k d log(k) + √
x and C, K are positive constants.

We adopt the following notation: for any c ∈ B(0, R) k , we denote by pj (c) = Xn (W j (c)), as well as p j (c) = E(X)(W j (c)). Moreover, we denote by m(c) (resp. m(c)) the codebooks satisfying, for j

∈ [[1, k]], m(c) j = u1 Wj (c) (u) Xn (du) pj (c) , m(c) j = u1 Wj (c) (u)E(X)(du) p j (c) ,
if pj (c) > 0 (resp. p j (c) > 0), and m(c) j = 0 (resp. m(c) j = 0) if pj (c) = 0 (resp. p j (c) = 0). The proof of Lemma 17 will make use of the following concentration lemma.

Lemma 22. With probability larger than 1 -8e -x , for all c ∈ B(0, R) k ,

pj (c) ≤ p j (c) + 4M c 0 kd log(k) log(2nN max ) n + 4M x n p j (c) pj (c) ≥ p j (c) - 4M c 0 kd log(k) log(2nN max ) n - 4M x n - 4M c 0 kd log(k) log(2nN max ) n + 4M x n p j (c),
where c 0 is an absolute constant. Moreover, with probability larger than 1 -e -x , we have

sup c∈B(0,R) k (c j -u)1 Wj (c) (u)( Xn -E(X))(du) j=1,...,k ≤ CRM √ n k d log(k) + √ x ,
where C is a constant.

The proof of Lemma 22 is given in Appendix A.1.3, and is based on empirical processes theory.

Proof of Lemma 17. Let c ∈ B(c * , R 0 ), and

D n = sup c∈B(0,R) k (c j -u)1 Wj (c) (u)( Xn -E(X))(du) j=1,...,k .
We decompose m(c) -c * 2 as follows.

m(c) -c * 2 = c -c * 2 + 2 m(c) -c, c -c * + m(c) -c 2 . ( 9
)
Next, we bound the first term of [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF].

2 m(c) -c, c -c * = 2 k j=1 1 pj (c) (u -c j )1 Wj (c) (u) Xn (du), c j -c * j ≤ 2 k j=1 1 pj (c) (u -c j )1 Wj (c) (u)E(X)(du), c j -c * j + 2D n k j=1 c j -c * j 2 pj (c) 2 ≤ 2 k j=1 1 pj (c) p j (c * )(c * j -c j ), c j -c * j + 2p min 8 √ 2 c -c * k j=1 c j -c * j 2 pj (c) 2 + 2D n k j=1 c j -c * j 2 pj (c) 2 ,
where the last line follows from Lemma 21. Now, using Lemma 22 with x = c 1 np min /M , for c 1 a small enough absolute constant, entails that, with probability larger than 1 -8e

2 m(c) -c, c -c * ≤ -2 k j=1 p j (c * ) pj (c) c j -c * j 2 + 32 124 √ 2 c -c * 2 + K 1 c -c * 2 + K -1 1 32 2 31 2 p 2 min D 2 n , (10)
where K 1 > 0 is to be fixed later. Then, the second term of (9) may be bounded as follows.

m(c) -c 2 = k j=1 (u -c j )1 Wj (c) (u) Xn (du) 2 pj (c) 2 = k j=1 p j (c * )(c j -c * j ) + ∆ j (c) + ∆ n,j (c) 2 pj (c) 2 , where ∆ j (c) = (u -c j )1 Wj (c) (u) -(u -c * j )1 Wj (c * ) (u) E(X)(du), so that k j=1 ∆ j (c) ≤ pmin 8 √
2 cc * , according to Lemma 21, and

∆ n,j (c) = (u -c j )1 Wj (c) (u)( Xn -E(X))(du), so that k j=1 ∆ n,j 2 ≤ D 2 n . Thus, m(c) -c 2 ≤ (1 + K 2 + K 3 ) k j=1 p j (c * ) 2 pj (c) 2 c j -c * j 2 + 1 + K -1 2 + K 4 k j=1 ∆ j (c) 2 pj (c) 2 + 1 + K -1 3 + K -1 4 k j=1 ∆ n,j (c) 2 pj (c) 2 ≤ (1 + K 2 + K 3 ) k j=1 p j (c * ) 2 pj (c) 2 c j -c * j 2 + 1 + K -1 2 + K 4 32 2 31 2 × 128 c -c * 2 + 1 + K -1 3 + K -1 4 32 2 31 2 p 2 min D 2 n , (11)
where K 2 , K 3 and K 4 are positive constants to be fixed later. Combining [START_REF] Chazal | The structure and stability of persistence modules[END_REF] and [START_REF] Chazal | The density of expected persistence diagrams and its kernel based estimation[END_REF]

yields that m(c) -c * 2 ≤ c -c * 2 1 + K 1 + 32 124 √ 2 + 32 2 31 2 × 128 1 + K -1 2 + K 4 -2 k j=1 p j (c * ) pj (c) c j -c * j 2 + (1 + K 2 + K 3 ) k j=1 p j (c * ) 2 pj (c) 2 c j -c * j 2 + D 2 n 32 2 31 2 p 2 min 1 + K -1 1 + K -1 3 + K -1 4 . Taking K 2 = 1 32 gives, through numerical computation, m(c) -c * 2 ≤ c -c * 2 0.62 + K 1 + K 3 32 2 31 2 + K 4 32 2 31 2 × 128 + D 2 n 32 2 31 2 p 2 min 1 + K -1 1 + K -1 3 + K -1 4 ≤ 3 4 c -c * 2 + K p 2 min D 2 n ,
for K 1 , K 3 and K 4 small enough. Now, according to Lemma 22, it holds

K p 2 min D 2 n ≤ R 2 0 4 ,
with probability larger than 1 -e -c1np 2 min κ 2 0 /M 2 , for some constant c 1 small enough.

Recalling that, for any t, c (t+1) = m(c (t) ), a straightforward recursion entails that, on a global probability event that has probability larger than 1 -9e -cnκ 2 0 p 2 min /M 2 -e -x , for c small enough, provided that c (0) ∈ B(c * , R 0 ), we have for any t ≥ 0 c (t) ∈ B(c * , R 0 ) and

c (t+1) -c * 2 ≤ 3 4 c (t) -c * 2 + K p 2 min D 2 n ≤ 3 4 c (t) -c * 2 + K p 2 min C 2 R 2 M 2 n k d log(k) + √ x 2 .
A.1.2. Proof of Lemma 18

Lemma [START_REF] Fischer | Quantization and clustering with Bregman divergences[END_REF]. Assume that c (0) ∈ B(c * , R 0 ), and n t ≥ c 0 k 2 M 2 p 2 min κ 2 0 log(n), for some constant c 0 , with n ≥ k. Then we have, for any t = 0, . . . , T -1,

E c (t+1) -c * 2 ≤ 1 - 2 -K 1 t + 1 E c (t) -c * 2 + 16kM R 2 p min (t + 1) 2 , (8)
with K 1 ≤ 0.5.

The proof of Lemma 18 will make use of the following deviation bounds.

Lemma 23. Let c ∈ B(0, R) k . Then, with probability larger than 1 -2ke -x , we have, for all j = 1, . . . , k,

|p j (c) -p j (c)| ≤ 2M p j (c)x n + M x n .
Moreover, with probability larger than 1 -e -x , we have,

(c j -u)1 Wj (c) (u)( Xn -E(X))(du) j=1,...,k ≤ 4RM √ k √ n 1 + √ x .
A proof of Lemma 23 is given in Appendix A.1.4.

Proof of Lemma 18. Assume that n ≥ k, and let n t = |B t |/2 ≥ CM pmin log(n), for C large enough to be fixed later. For a given t ≤ T , denote by p(t) j = XB (1) t (W j (c (t) ), and by A t,1 and A t,2 the events

A t,1 = ∀j = 1 . . . , k |p (t) j -p (t) j | ≤ pmin+ p (t) j pmin 256 , A t,2 = ∀j = 1 . . . , k (c (t) j -u)1 Wj (c (t) ) (u)( XB (2) t -E(X))(du) ≤ 8R M kpmin C .
According to Lemma 23 with x = 4 log(2n), we have P(A c t,j ) ≤ k/(2n 4 ), for j = 1, 2. We let also A ≤t denote the event ∩ r≤t A r1 ∩ A r2 , that has probability larger than 1-kt/n 4 . First we prove that if c (0) ∈ B(c * , R 0 ), then, on A ≤t , for all r ≤ t, c (r) ∈ B(c * , R 0 ). We proceed recursively, assuming that c (t) ∈ B(c * , R 0 ). Then, on A ≤t+1 , applying Lemma 21 yields that 33 32 p * j ≥ pt j ≥ 31 32 p * j . Denoting by a t = c (t) -c * 2 and g t+1 = (c

(t) j -u)1 W j (c (t) ) (u) XB (2) t+1 (du) pt+1 j j
, the recursion equation entails that

a t+1 = π B(0,R) k c (t) - g t+1 t + 1 -c * 2 ≤ c (t) - g t+1 t + 1 -c * 2 = a t - 2 t + 1 g t+1 , c -c * + 1 (t + 1) 2 g t+1 2 .
(

) 12
As in the proof of Lemma 17, denote by

∆ t j = (u -c (t) j )1 Wj (c (t) ) (u)E(X)(du) -p * j (c * j -c (t) j ) ∆ t+1 n,j = (u -c (t) j )1 Wj (c (t) ) (u)( XB (2) t+1 -E(X))(du) D t+1 n = k j=1 ∆ t+1 n,j (D t+1 n ) 2 ≤ 32 2 31 2 c (t) -c * 2 1 + K 1 + K 2 + 1 + K -1 2 + K 3 128 + (D t+1 n ) 2 32 2 (1 + K -1 1 + K -1 3 ) 31 2 p 2 min ,
where K 1 , K 2 and K 3 are constants to be fixed later. Combining pieces and using t + 1 ≥ 1 leads to

a t+1 ≤ a t + a t t + 1 -64 33 + 64 8 √ 2 × 31 + K 4 + 32 2 31 2 1 + K 1 + K 2 + 1 + K -1 2 + K 3 128 + D t+1 n 2 32 2 31 2 p 2 min K -1 4 + 32 2 (1 + K -1 1 + K -1 3 ) 31 2 p 2 min . Choosing K 2 = 1 32 entails that -64 33 + 64 8 √ 2 × 31 + K 4 + 32 2 31 2 1 + K 1 + K 2 + 1 + K -1 2 + K 3 128
≤ -0.38 + K 4 + 32 2 31 2 K 1 + K 3 128 ,
so that, for K 1 , K 3 and K 4 small enough, we have

a t+1 ≤ 0.8a t + K p 2 min (D t+1 n ) 2 . Now, if n t ≥ c 0 k 2 M 2 p 2 min κ 2 0 log(n), n ≥ k, where c 0 is an absolute constant, on A ≤t+1 we have a t+1 ≤ 0.8a t + 0.2R 2 0 ≤ R 2 0 .
Thus, provided that c (0) ∈ B(c * , R 0 ), on A ≤t we have c (p) ∈ B(c * , R 0 ), for p ≤ t.

Next, if F t denotes the sigma-algebra corresponding to the observations of the t first mini-batches B 1 , . . . , B t , and E t denotes the conditional expectation with respect to F t . We will show that

Ea t+1 ≤ 1 - 2 -K 1 t + 1 Ea t + 16kM R 2 p min (t + 1) 2 ,
where K 1 < 0.5. First, we may write

Ea t+1 = E a t+1 1 A ≤t 1 At+1,1 + R 1 , with R 1 ≤ (4k 2 R 2 )/n 3 ≤ 4kM R 2 /(p min (t + 1) 2 ), since p min ≤ M/k and t + 1 ≤ T ≤ n. Then, using (12) entails E a t+1 1 A ≤t ∩At+1,1 ≤ Ea t - 2 t + 1 E g t+1 , c (t) -c * 1 A ≤t ∩At+1,1 + 1 (t + 1) 2 E g t+1 2 1 A ≤t ∩At+1,1 .
Next, we bound the scalar product as follows. The first term may be bounded by We proceed as before, writing E(a t+1 ) = E(a t+1 1 A ≤t )+R 1 , with R 1 ≤ 4kR 2 /(p min (t+ 1) 2 ), and

E -g t+1 , c (t) -c * 1 A ≤t ∩At+1,1 = E   1A ≤t k j=1 E t    (u -c (t) j )1 Wj (c (t) ) (u) XB (2) t+1 (du), c (t)
E t (u -c (
E(a t+1 1 A ≤t ) ≤ Ea t + 1 (t + 1) 2 E( g t+1 2 ) - 2 t + 1 E g t+1 , c (t) -c * 1 A ≤t .
Note that g t+1 2 ≤ 4kR 2 , so that the second term might be bounded by 4kR 2 /(t + 1) 2 . To bound the scalar product, we proceed as follows. Let j ∈ [[1, k]],

and, for i ∈ B t+1 , denote by U i,j the random variable 1 Wj (c (t) ) (X i ). We have The remaining of the proof is the same as for the sample measure case.

A.1.3. Proof of Lemma 22

Let Z 1 denote the process For the sake of completeness a proof of Lemma 24 is given in Appendix A.1.5. Next, introducing σ 1 , . . . , σ n independent Rademacher variables, we get

Z 1 = sup c∈B(0,R) k ,
P sup f ∈F (P n -P n )f (P n f + P n f )/2 ≥ t ≤ P sup f ∈F 1 n n i=1 σ i (f (X i ) -f (X i )) (P n f + P n f )/2 ≥ t
≤ E X1,...,Xn,X 1 ,...,X n P σ sup

f ∈F 1 n n i=1 σ i (f (X i ) -f (X i )) (P n f + P n f )/2 ≥ t .
For a set of functions F and elements x 1 , . . . , x q ∈ M(R) we denote by S F (x 1 , . . . , x q ) the cardinality of the set {(f (x 1 ), . . . , f (x q )) | f ∈ F}. Let

i=1 (f (X i ) -f (X i )) 2 n i=1 (f (X i ) + f (X i )) ≤ 1.
Thus, combining Hoeffding's inequality and a plain union bound yields

P σ sup f ∈F 1 n n i=1 σ i (f (X i ) -f (X i )) (P n f + P n f )/2 ≥ t ≤ 2 n i=1 (n i + n i ) c0kd log(k)
e -nt 2 , hence, since for i = 1, . . . , n, X i ∈ M Nmax (R, M ), 2 ) concludes the proof of the lemma.

,

  thresholded persistence diagram of d S ( ) , that is D ( ) ≥s = {(b,d)∈D ( ) |d-b≥s} n(b, d)δ (b,d) := k where the multiplicities n(b, d) ∈ N * , and the m ( ) j 's satisfy (m ( ) j ) 2 -(m ( ) j ) 1 ≥ s. The following lemma ensures that k ( ) 0 is finite. Lemma 12. Let S be a compact subset of R d , and D denote the persistence diagram of the distance function d S . For any s > 0, the truncated diagram consisting of the points m

Proposition 14 .

 14 Let h = C d log(N ) f min, N 1/d , for some constants C d , and h = max ≤L h . Moreover, let M = D ( ) ≥s (H + ), M = L =1 π M , and π min = min ≤L π .

Fig 1 :

 1 Fig 1: Synthetic 3-mixture of measures instance (blue, dark brown and pink) and their support centers for indication (dark green for the outer centers, yellow, green and brown for the middle centers) with either 4 (left) or 20 (right) support centers in dimension 2, r = 1. The sets of points similarly coloured constitute measures.

Fig 2 :

 2 Fig 2: NMI as budget increases, r = 1, increasing dimensions along rows, low noise and high noise contexts (left and right columns)

Fig 3 :

 3 Fig 3: NMI as r increases, budget k = 32, increasing dimensions along rows, low noise and high noise contexts (left and right columns)

Fig 4 :

 4 Fig 4: Blue: point cloud embedding in dimension 2 for the words of all reviews; green: point cloud embedding for the words of the first review ("Story of a man who has unnatural feelings for a pig. [...]"); red: codepoints computed by Algorithm 2, with the text print of their closest corresponding word.

To apply Lemma 19 1 d

 191 to d Y N and d ( ) S , for ∈ [[1, L]], a bound on d Y N -d ( ) S ∞ may be derived from the following result. Lemma 20. [1, Lemma B.7] Let S ⊂ R D be a d-dimensional submanifold with positive reach τ S , and let Y N = Y 1 , . . . , Y N be an i.i.d. sample drawn from a distribution that has a density f (x) with respect to the Hausdorff measure of S. Assume that for all x ∈ S, 0 < f min ≤ f (x), and let h = C d k log(N ) fminN , where C d is a constant depending on d. If h ≤ τ S /4, then, with probability larger than

  so that P(A | Z = ) ≤ α . Also, let m k0+1 , . . . , m k0+K0(h) be such thatL =1 D ( ) ≥s \ {m 1 , . . . , m k0 } ⊂ K0(h) s=1 B ∞ (m k0+s ,h), and m = (m 1 , . . . , m k0+K0(h) ). At last, we let R = max ≤L diam(S ). Choosing the N 's large enough so that D ( ) ≥s-h = D ( ) ≥s and s/2 > h , X (Z) and D (Z)

2 B

 2 . Under the assumptions of Proposition 14, we choose N , ≤ L large enough so that 5√ M h/( √ π min ) ≤ κ B. Next, denote by α = N -(κ B) d f min, N C d log(N )

8 √ 2 c

 82 c * . The proof of Lemma 21 follows from [23, Section A.3]. A.1.1. Proof of Lemma 17

j ) 1 j ) 1

 11 any j ∈ [[1, k]],we have Wj (c (t) ) (u) XB(2) Wj (c (t) ) (u) XB(2)

j ) 1 j ) 1 -c j 2 1 A

 111 Wj (c (t) (u) XBt+1 (du), c Wj (c (t) ) (u) XBt+1 (du) | F t , (U i,j ) i∈Bt+1 , c ≤t ) + 32 31p min E( ∆ j,t c t j -c * j 1 A ≤t ).

F 1

 1 denote the set offunctions {X ∈ M(R, M ) → X(W )/M | W = k j=1 H j , H j half-space}. Since, for every i ∈ [[1, n]], X i = ni j=1 µ i,j δ x (i) j , we have S F1 (X 1 , . . . , X n , X 1 , . . . , X n ) ≤ |{(1 W (x (i) j )) i=1,...,2n,j=1,...,ni | W = k j=1 H j , H j half-space}| ≤ 2 n i=1 n i + n i c0kd log(k), using [28, Theorem 1], and[START_REF] Van Der Vaart | A note on bounds for VC dimensions[END_REF] Theorem 1] to bound the VC-dimension of the sets W 's. On the other hand, for any f ∈ F 1 , it holds

  n

  -P n )f (P n f + P n f )/2 ≥ t ≤ (4nN max ) c0kd log(k) e -nt 2 ,that proves the second inequality of Lemma 22. The first inequality of Lemma 22 derives the same way from the second inequality of Lemma 24.We turn to the third inequality of Lemma 22. Let Z denote the processZ = sup c∈B(0,R) k , t ≤1 (c j -u)1 Wj (c)and, for j = 1, . . . , k,Z j = sup c∈B(0,R) k , tj ≤1 1 M (c j -u)1 Wj (c) (u)( Xn -E(X))(du), t j , so that Z ≤ k j=1 Z 2 j .According to the bounded differences inequality ([6, Theorem 6.2]), we haveP Z j ≥ E(Z j ) -u)1 Wj (c) (u)X i (du), t j , d -1S ([0, t]), t > 2diam(S) have the same homology. As a consequence, no point in D has a larger coordinate than 2diam(S) and D is contained in [0, 2diam(S)] 2 . Since S is compact, the persistence module of the filtration defined by the sublevel sets of d S is q-tame ([10,Corollary 3.35]). Equivalently, this means that for any b 0 < d 0 , the intersection of D with the quadrant Q (b0,d0) = {(b, d) : b < b 0 and d 0 < d} is finite. Noting that the intersection of [0, 2diam(S)] 2 with the half-plane {(b, d) : d ≥ b + s} can be covered by a finite union of quadrants Q (b,b+ s

Table 1

 1 is a simple graph embedding method that Large graph binary classification problems. Mean ROC-AUC and standard deviations.

	method		SF	NetLSD	FGSD GeoScat	Atol
	problem	size	[15]	[38]	[40]	[19]
	reddit threads	(203K) 81.4±.2	82.7±.1	82.5±.2	80.0±.1	80.7±.1
	twitch egos	(127K) 67.8±.3	63.1±.2	70.5±.3	69.7±.1	69.7±.1
	github stargazers (12.7K) 55.8±.1	63.2±.1	65.6±.1	54.6±.3 72.3±.4
	deezer ego nets	(9.6K)	50.1±.1	52.2±.1	52.6±.1	52.2±.3	51.0±.6

  c1npmin/M , for n large enough and every c ∈ B(c * , R 0 ),

	pj (c) ≥	63 64	p j (c) -	p min 64	≥	31 32	p min
	pj (c) ≤	33 32	p j (c * ),
	according to Lemma 21. Therefore

  t+1 , c (t) -c * 1 A ≤t ∩At+1,1 ≤according to Lemma 21. At last, the bound on g t+1 2 writes as follows.E g t+1 2 1 A ≤t ∩At+1,1 = E 1 A ≤t E t g t+1 2 1 At+1,1 Ea t + 16kM R 2 p min (t + 1) 2 , with K 1 ≤ 0.5.At last, in the point sample case where we observe n points in R d X 1 , . . . , X n i.i.d with distribution X, recall that we take With a slight abuse of notation we denote by A ≤t the event onto which the concentration inequalities of Lemma 23 are satisfied (with B = B t ). The first step of the proof is the same: if n t ≥ c 0 and n ≥ k, then, on A ≤t , for all j ≤ t, a j ≤ R 0 . It remains to prove the recursion inequality

	and the second term by
	32 33p * j	1 A ≤t ≤ E t	1 pt+1 j	1 At+1,1 1 A ≤t ≤	32 31p * j	.
	This gives
	E -g 32 33	E a t 1 A ≤t +	32 31p min	E	 	k j=1	∆ j,t c (t) j -c * j 1 A ≤t	 
					≤ -	32 33	E(a t ) +	32 31 × 8	√	2	E(a t ) +	32 33	4k 2 R 2 n 3 ,
					≤	32 31	4kM R 2 p min	.
	Gathering all pieces leads to
	Ea t+1 ≤ 1 -	2 -K 1 t + 1
	c (t+1) = c (t) -	g t+1 t + 1	, with g t+1 =	(c (t)
										k	(1) t	= B	(2) t
										p 2 min κ 2 0
	Ea t+1 ≤ 1 -	2 -K 1 t + 1			Ea t +	16kR 2 p min (t + 1) 2 .
	t) j )1 Wj (c (t) ) (u) XB (2) t+1	(du), c (t) j -c * j	1 A ≤t ≤ -p * j c (t) j -c * j	2 1 A ≤t
										+ ∆ j,t c	(t) j -c * j ,

j -u)1 Wj (c (t) (u) XBt+1 (du) pt+1 j .

  j=1,...,k Note that the VC dimension of Voronoi cells in a k-points Voronoi diagram is at most c 0 kd log(k) ([39, Theorem 1.1]). We first use a symmetrization bound.Lemma 24. Let F denote a class of functions taking values in [0, 1], and X 1 , . . . , X n , X 1 , . . . , X n i.i.d random variables drawn from P . Denote by P n and P n the empirical distributions associated to the X i 's and X i 's. If nt 2 ≥ 1, then

			1 Wj (c) (u)	Xn M	-	E(X) M	(du) .
	P sup f ∈F	(P -P n )f √ P f	≥ 2t ≤ 2P sup f ∈F	(P n -P n )f (P n f + P n f )/2	≥ t
	P sup f ∈F	(P n -P )f √ P n f	≥ 2t ≤ 2P sup

f ∈F (P n -P n )f (P n f + P n f )/2 ≥ t .

Proof of Corollary 16

In the case where Ψ = Ψ AT , we have that Ψ AT is a (p, 1/p) kernel. The requirement 1/p ≤ 1 4M of Proposition 3 is thus satisfied for p AT = 4M . On the other hand, choosing r AT = B 32p AT ensures that 8r AT p AT ≤ (1/2 -κ) B and r AT 2p AT ≥ 2κ B, for κ small enough. Thus, the requirements of Proposition 15 are satisfied: c * is a (2p AT , r, 1) shattering of X 1 , . . . , X n . At last, using Corollary 11, we have that ĉn is a (p AT , r AT , 1) shattering of X 1 , . . . , X n , on the probability event described by Corollary 11. It remains to note that 2κ B ≤ r AT 4 for κ small enough to conclude that X 1 , . . . , X n is r AT 4 -concentrated on the probability event described in Proposition 15. Thus Proposition 5 applies.

The case Ψ = Ψ 0 is simpler. Since Ψ 0 is a (1, 0)-kernel, we obviously have that 0 ≤ 1 2M , so that the requirement of Proposition 15 is satisfied. With p 0 = 1 and r 0 = B 16 we immediately get that r 0 /(2p 0 ) ≥ 2κ B and 8r 0 p 0 ≤ (1/2 -κ B), for κ small enough, so that ĉ is a (p 0 , r 0 , 1) shattering of X 1 , . . . , X n . As well, 2M κ B ≤ r0 4 , for κ small enough. Thus Proposition 5 applies.

Appendix A: Technical proofs

To ease understanding the statements of the results are recalled before their proofs.

A.1. Proofs for Section 6

A key ingredient of the proofs of Lemma 17 and 18 is the following Lemma 21, ensuring that around optimal codebooks the expected gradients of Algorithms 1 and 2 are almost Lipschitz.

Lemma 21. Assume that E(X) ∈ M(R, M ) satisfies a margin condition with radius r 0 , and denote by R 0 = Br0 We have that

according to Lemma 21, where K 4 denotes a constant. Next, the second term in ( 12) may be bounded by

where σ 1 , . . . , σ n are i.i.d Rademacher variables. Now assume that X 1 , . . . , X n is fixed and j = 1. For a set F of real-valued functions we denote by N (F, ε, . ) its ε-covering number with respect to the norm . . Denoting by Γ 0 , Γ 1 and Γ 2 the following sets

(c 1 ,t 1 ) (u)γ

(2)

(c 1 ,t 1 ) ∞ ≤ ε, we may write (γ

Thus,

( Xn/M ( Xn)) . We deduce

for every ε > 0. According to [28, Theorem 1], we may write

, where K is a constant and ε < 2. Thus, for every ε < 2,

.

Using Dudley's entropy integral (see, e.g., [6, Corollary 13.2]) yields, for k ≥ 2,

hence the result.

A.1.4. Proof of Lemma 23

The first bound of Lemma 23 follows from Bernstein's inequality. To prove the second inequality, we first bound the expectation as follows.

A bounded difference inequality (see, e.g., [6, Theorem 6.2] entails that, with probability larger than 1 -e -x ,

hence the result.

A.1.5. Proof of Lemma 24

We follow the proof of [4, Theorem 1]. Let t > 0, and assume that P f -P n f > 2t √ P f , as well as P n f ≥ P f -t √ P f ≥ 0. Let g a : R + → R be defined as

), so that

Thus,

The previous inequality may be written as

with, for a fixed f ∈ F, using Cantelli's inequality,

Since, for any f ∈ F, f ∞ ≤ 1, we have Var(f ) ≤ P f 2 ≤ P f , thus

The other inequality proceeds from the same reasoning, considering f such that P n f -P f > 2t √ P n f and P n f ≤ P f + t √ P n f , and g a : R + → R defined by g a (x) = a-x √ a+x , that is nonincreasing for a ≥ 0. Choosing a = P n f , 0 ≤ x 1 = P n f ≤ P f + t √ P n f = x 2 leads to

. Using Cantelli's inequality again leads to the result.

A.2. Proof of Lemma 12

Lemma (12). Let S be a compact subset of R d , and D denote the persistence diagram of the distance function d S . For any s > 0, the truncated diagram consisting of the points m = (m 1 , m 2 ) ∈ D such that m 2 -m 1 ≥ s is finite.

The lemma follows from standard arguments in geometric inference and persistent homology theory.

First, the definition of generalized gradient of d S -see [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF] or [5, Section 9.2]implies that the critical points of d S are all contained in the convex hull of S. As a consequence, they are all contained in the sublevel set d -1

S ([0, 2diam(S)]). It follows from the Isotopy Lemma -[5, Theorem 9.5] -that all the sublevel sets