Hannah Marienwald

Jean-Baptiste Fermanian

Gilles Blanchard

High-Dimensional Multi-Task Averaging and Application to Kernel Mean Embedding

We propose an improved estimator for the multi-task averaging problem, whose goal is the joint estimation of the means of multiple distributions using separate, independent data sets. The naive approach is to take the empirical mean of each data set individually, whereas the proposed method exploits similarities between tasks, without any related information being known in advance. First, for each data set, similar or neighboring means are determined from the data by multiple testing. Then each naive estimator is shrunk towards the local average of its neighbors. We prove theoretically that this approach provides a reduction in mean squared error. This improvement can be significant when the dimension of the input space is large, demonstrating a "blessing of dimensionality" phenomenon. An application of this approach is the estimation of multiple kernel mean embeddings, which plays an important role in many modern applications. The theoretical results are verified on artificial and real world data.

INTRODUCTION

The estimation of means from i.i.d. data is arguably one of the oldest and most classical problems in statistics. In this work we consider the problem of estimating multiple means µ 1 , . . . , µ B of probability distributions P 1 , . . . , P B , over a common space X = R d (or possibly a real Hilbert space H). We assume that for each individual distribution P i , we observe an i.i.d. data set X (i) • of size N i , and that these data sets have been collected independently from each other.

In the rest of the paper, we will call each such data set X (i)

• a bag. Mathematically, our model is thus X (i)

• := (X (i) k ) 1≤k≤Ni i.i.d. ∼ P i , 1 ≤ i ≤ B; (X (1)
• , . . . , X (B)

• ) independent, (1)
where P 1 , . . . , P B are square integrable distributions on R d which we call tasks, and our goal is the estimation of their means

µ i := E X∼P b [X] ∈ R d , 1 ≤ i ≤ B. (2)
Given an estimate µ i of µ i , we will be interested in its squared error µ iµ i 2 , and aim at controlling it either with high probability or in average (mean squared error, MSE):

MSE(i, µ i ) := E µ i -µ i 2 ;
this error can be considered either individually for each task P i or averaged over all tasks.

1 This problem is also known as multi-task averaging (MTA) [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF], an instance of the multi-task learning (MTL) problem. Prior work on MTL showed that learning multiple tasks jointly yields better performance compared to individual single task solutions [START_REF] Caruana | Multitask learning[END_REF][START_REF] Evgeniou | Learning multiple tasks with kernel methods[END_REF][START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF].

In this paper we adapt the idea of joint estimation to the multi-task averaging problem and will show that we can take advantage of some unknown structure in the set of tasks to improve the estimation. Here, by individual estimation we mean that our natural baseline is the naive estimator (NE) given by the simple empirical mean:

µ NE i := 1 N i Ni k=1 X (i) k ; MSE(i, µ NE i ) = 1 N i Tr Σ i , (3)
where Σ i is the covariance matrix of P i .

Our motivation for considering this setting is the growing number of large databases taking the above form, where independent bags corresponding to different but conceptually similar distributions are available; for example, one can think of i as an index for a large number of individuals, for each of which a number of observations (assumed to be sampled from an individual-specific distribution) are available, say medical records, or online activity information collected by some governmental or corporate mass spying device.

While estimating means in such databases is of interest of its own, a particularly important motivation to consider this setting is that of Kernel Mean Embedding (KME), a technique enjoying sustained attention in the statistical and machine learning community since its introduction in the seminal paper of [START_REF] Smola | A Hilbert space embedding for distributions[END_REF]; see [START_REF] Muandet | Kernel mean embedding of distributions: a review and beyond[END_REF] for an overview. The KME methodology is used in a large number of applications, e.g. two sample testing [START_REF] Gretton | A kernel two-sample test[END_REF], goodness-of-fit [START_REF] Chwialkowski | A kernel test of goodness of fit[END_REF], multiple instance or distributional learning for both supervised [START_REF] Muandet | Learning from distributions via support measure machines[END_REF][START_REF] Szabó | Learning theory for distribution regression[END_REF] as well as unsupervised learning [START_REF] Jegelka | Generalized clustering via kernel embeddings[END_REF], to name just a few.

The core principle of KME is to represent the distribution P Z of a random variable Z via the mean of X = φ(Z), where φ is a rich enough feature mapping from the input space Z to a (reproducing kernel) Hilbert space H. In practice, it is assumed that we have an i.i.d. bag (Z k ) 1≤k≤N from P, which is used to estimate its KME. Here we are interested again in the situation where a large number of independent data sets from different distributions are available, and we want to estimate their KMEs jointly. This is, therefore, an instance of the model (1), once we set X := H and X (i)

k := φ(Z (i) k ).

Relation to Previous Work

The fact that the naive estimator (3) can be improved upon when multiple, real-valued means are to be estimated simultaneously, has a long history in mathematical statistics. More precisely, let us introduce the following isotropic Gaussian setting:

P i = N (µ i , I i ); N i = N, 1 ≤ i ≤ B, (GI)
on which we will come back in the sequel.

As shown in [START_REF] Stein | Inadmissibility of the usual estimator for the mean of a multivariate normal distribution[END_REF], for B = 1 with d ≥ 3 the naive estimator is inadmissible, i.e. there exists a strictly better estimator, with a lower MSE for any true mean vector µ 1 . An explicit example of a better estimator is given by the celebrated James-Stein estimator (JSE) [START_REF] James | Estimation with quadratic loss[END_REF], which shrinks adaptively the naive estimator towards 0, or more generally, towards an a priori fixed vector ν 0 .

The MTA problem was introduced by [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF], who proposed an approach which regularizes the estimation such that similar tasks shall have similar means as well. However, they assumed the pairwise task similarity to be given, which is unfeasible in most practical applications. In addition to our own approach, we will also introduce a variation of theirs, suitable for the KME framework, that estimates the task similarity instead of assuming it to be known. [START_REF] Martínez-Rego | Multi-task averaging via task clustering[END_REF] proposed a method based on spectral clustering of the tasks and applying [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF]'s method separately on each cluster, but without theoretical analysis.

Variations of the JSE can be shown to yield possible improvements over the NE in more general situations as well (see [START_REF] Fathi | Relaxing the Gaussian assumption in shrinkage and SURE in high dimension[END_REF] for recent results in non-Gaussian settings). This has also been exploited for KME in [START_REF] Muandet | Kernel mean shrinkage estimators[END_REF], where a Stein-type estimator in kernel space was shown to generally improve over naive KME estimation. To the best of our knowledge, no shrinkage estimator for KME explicitly designed for or taking advantage of the MTA setting exists.

In the remainder of this work we will proceed as follows. Section 2 introduces the basic idea of the approach and starts with a general discussion. We will expose in Section 3 a theoretical analysis proving that the presented method improves upon the naive estimation in terms of squared error, possibly by a large factor. The general theoretical results will be discussed explicitly for the Gaussian setting (Sec. 3.3) and in the KME framework (Sec. 3.4). The approach is then tested for the KME setting on artificial and real world data in Section 4. All proofs are found in the appendix Sections A to F, Appendix G gives a detailed description of the estimators compared in the experiments, and Appendix H presents additional numerical results in the Gaussian setting.

METHOD

The basic idea of our approach is to improve the estimation of a mean of a task by basing its estimation not on its own bag alone, but concatenating the samples from all bags it is sufficiently similar to. Since in most practical applications task similarity is not known, we will propose a statistical test that assesses task relatedness based on the given data.

Overview of the Approach

In the remainder of the paper we will use the notation n := {1, . . . , n}. For convenience of exposition, assume the (GI) setting. In this case, the naive estimators all have the same MSE, σ 2 := d/N . Fix a particular task (reindexed i = 0) with mean µ 0 that we wish to estimate, and assume for now we are given the side information that for some constant τ > 0, it holds ∆ 2 0i := µ 0µ i 2 ≤ τ σ 2 for some "neighbor tasks" i ∈ V (a subset of the larger set of B tasks within range τ σ 2 to µ 0 , reindexed for convenience). Consider the estimator µ 0 obtained by a simple average of neighbor naive estimators,

µ 0 = 1 V +1 V i=0 µ NE i .
We can bound via usual bias-variance decomposition, independence of the bags and convexity of the squared norm:

MSE(0, µ 0 ) = 1 V + 1 V i=1 (µ 0 -µ i ) 2 + σ 2 V + 1 ≤ σ 2 (1 + V τ ) V + 1 . (4)
Thus, the above bound guarantees that µ 0 improves over µ NE 0 whenever τ < 1, and leads to a relative improvement of order max(τ, V -1 ).

In practice, we don't have any a priori side information on the configuration of the means. A simple idea is, therefore, to estimate the quantities ∆ 2 0i from the data by an estimator ∆ 2 0i and select only those bags for which ∆ 2 0i ≤ τ σ 2 . This is in a nutshell the principle of our proposed method.

The deceptive simplicity of the above idea might be met with some deserved skepticism. One might expect that the typical estimation error of ∆ 2 0i would be of the same order as the MSE of the naive estimators. Consequently, we could at best guarantee with high probability a bound of ∆ 2 0i σ 2 for the estimated neighbor tasks, i.e. τ ≈ 1, which does not lead to any substantial theoretical improvement when using (4). The reason why the above criticism is pessimistic, even in the worst case, is the role of the dimension d. From high-dimensional statistics, it is known that the rate of testing for ∆ 2 0i = 0, i.e. the minimum ρ 2 such that a statistical test can detect ∆ 2 0i ≥ ρ 2 with probability close to 1, is faster than the rate of estimation, [START_REF] Baraud | Non-asymptotic minimax rates of testing in signal detection[END_REF][START_REF] Blanchard | Minimax Euclidean separation rates for testing convex hypotheses in R d[END_REF]. Thus, we can reliably determine neighbor tasks with τ ≈ 1/ √ d. Based on (4), we can hope again for an improvement of order up to O(1/ √ d) over NE, which is significant even for a moderately large dimension. In the rest of the paper, we develop the idea sketched here more precisely and illustrate its consequences on KME by numerical experiments. The message we want to convey is that the curse of higher dimensional data with its effect on MSE can be to a limit mitigated by a relative blessing because we can take advantage of neighboring tasks more efficiently.

ρ 2 ≃ √ d/N = σ 2 / √ d (see e.g.

Proposed Approach

Denote

σ 2 i = MSE(i, µ NE i ), i ∈ B .
Introduce the following notation: ∆ ij := µ iµ j . In general, our approach assumes that we have at hand a family of tests (T ij ) 1≤i,j≤B for the null hypotheses

H 0 ij : ∆ 2 ij > τ σ 2 i against the alternatives H 1 ij : ∆ 2 ij ≤ τ ′ σ 2 i , for 0 ≤ τ ′ < τ .
The exact form of the tests will be discussed later for specific settings.

We denote the set of detected neighbors of task i ∈ B as V i := {j : T ij = 1, j ∈ B }; we can safely assume T ii = 1 so that that i ∈ V i always holds and |V i | ≥ 1. We will also denote

V * i = V i \ {i}. For γ ∈ [0, 1]
, define the modified estimator

µ i := γ µ NE i + (1 -γ) |V i | j∈Vi µ NE j , (5)
which can be interpreted as a local shrinkage estimator pulling the naive estimator towards the simple average of its neighbors.

THEORETICAL RESULTS

We will assume that the naive estimators defined by (3) satisfy

max i∈ B MSE(i, µ NE i ) ≤ σ 2 . ( 6
)
Define the notation

G(τ ) := (i, j) ∈ B 2 : ∆ 2 ij ≤ τ σ 2 ; G(τ ) := (i, j) ∈ B 2 : ∆ 2 ij ≥ τ σ 2 ,
and two following events:

A(τ ) := max (i,j)∈G(τ ) T ij = 1 ; B(τ ′ ) := min (i,j)∈G(τ ′ ) T ij = 0 ; so P[A(τ )]
is the collective false positive rate of the tests (or family-wise error rate) while P[B(τ ′ )] is the collective false negative rate to detect ∆ 2 ij ≤ τ ′ σ 2 (family-wise Type II error rate).

A General Result under Independence of Estimators and Tests

We start with a result assuming that the tests (T ij ) (i,j)∈ B 2 and the estimators ( µ NE i ) i∈ B are independent. This can be achieved for instance by splitting the original bags into two.

Theorem 3.1. Assume model (1) holds as well as (2), and that (6) holds. Furthermore, assume that there exists a family of tests (T ij ) (i,j)∈ B 2 that is independent of (X (i)

• ) i∈ B . For a fixed constant τ > 0, consider the family of estimators ( µ i ) i∈ B defined by (5) with respective parameters

γ i := τ |V * i | (1 + τ )|V * i | + 1 . ( 7
)
Then, conditionally to the event A c (τ ), it holds

∀i ∈ B : MSE(i, µ i ) ≤ τ |V * i | + 1 (1 + τ )|V * i | + 1 σ 2 . ( 8
)
Let N denote the covering number of the set of means {µ j , j ∈ B } by balls of radius √ τ ′ σ/2. Then, conditionally to the events A c (τ ) and B c (τ ′ ) (for τ ′ < τ ), it holds

1 B B i=1 MSE(i, µ b ) ≤ τ τ + 1 + N B 1 (τ + 1) σ 2 . ( 9
)
The proof can be found in the supplementary material. In a nutshell, conditional to the favorable event A c (τ ), and because the tests are independent of the estimators, we can use the argument leading to (4), extended to take into account the shrinkage factor γ, and optimize the value of γ to obtain (7), (8). If B c (τ ′ ) is satisfied as well, we can deduce (9) directly from (8).

Discussion.

• The factor in the individual MSE bound (8) is strictly less than 1 as soon as |V i | > 1. As the number of neighbors |V i | grows, the factor is larger than but approaches τ /(1 + τ ). Therefore, there is a general trade-off between τ and the number of neighbors in a neighborhood of radius √ τ σ. Nevertheless, in order to aim at possibly significant improvement over naive estimation, a small value of τ should be taken.

• The factor in the averaged MSE bound ( 9) is also always smaller than 1 (as expected from the individual MSE bound). It has a nice interpretation in terms of the ratio N /B: if N ≪ B, the improvement factor will be very close to τ /(1 + τ ). Thus, we collectively can improve over the naive estimation wrt MSE as soon as the set of means has a small covering number (at scale √ τ ′ σ/2) in comparison to its cardinality. This condition can be met in different structural low complexity situations, e.g. clustered means, means being sparse vectors, set of means on a low-dimensional manifold. Note that the method does not need information about said structure in advance and is in this sense adaptive to it.

Using the Same Data for Tests and Estimation

We now present a general result in the case where the estimators and tests are not assumed to be independent (e.g. computed from the same data.) To this end we introduce the following additional events:

C(τ ) : max i =j | µ NE i -µ i , µ NE j -µ j | > τ σ 2 ; C ′ (τ ) : max i µ NE i -µ i 2 > σ 2 + τ σ 2 .
Theorem 3.2. Assume that there exists a family of tests (T ij ) (i,j)∈ B 2 . For a given τ > 0 consider the family of estimators ( µ i ) i∈ B defined by (5) with respective parameters

γ i := τ 1 + τ . ( 10
)
Then, for τ ′ ≥ τ , with probability greater than

1 -P[A(τ ) ∪ B(τ ′ ) ∪ C(τ ) ∪ C ′ (τ )], it holds ∀i ∈ B : µ i -µ i 2 ≤ 2σ 2 τ + τ + |V i | -1 1 + τ . ( 11
)
Let N denote the covering number of the set of means {µ b , b ∈ B } by balls of radius √ τ ′ σ/2. Then, with the same probability as above, it holds

1 B B i=1 µ i -µ i 2 ≤ 2σ 2 τ + τ 1 + τ + N B 1 1 + τ . ( 12
)
The interpretation of the above result is similar to that of Theorem 3.1, with the caveat that the factor in the MSE bound is not always bounded by 1 as earlier; but the qualitative behaviour when τ is small, which is the relevant regime, is the same as previously described.

The Gaussian Setting

In view of the previous results, the crucial point is whether there exists a family of tests such that the events A(τ ), B(τ ′ ), C(τ ), C ′ (τ ) have small probability, for a value of τ significantly smaller than 1, and τ ′ of the same order as τ (up to an absolute numerical constant). This is what we establish now in the Gaussian setting.

Proposition 3.3. Assume (GI) is satisfied. For a fixed α ∈ (0, 1), define the tests

T ij = 1 µ NE i -µ NE j 2 ≤ ζd/N , ( 13
)
with ζ := √ 2 + τ -4 √ δ 2
, where we put δ := (2 log B + log α -1 )/d.

Then, provided τ ≥ max(Cδ, √ Cδ) (with C = 10 3 ), it holds P[A(τ )] ≤ α, P[B(τ ′ )] ≤ α with τ ′ = τ /3, P[C(τ )] ≤ 2α and P[C ′ (τ )] ≤ α .
The above result is significant in combination with Theorems 3.1 and 3.2 when δ is small, which is the case if log(B)/d is small. The message is the following: in a high-dimensional setting, provided B ≪ e d , we can reach a large improvement compared to the naive estimators, if the set of means exhibits structure, as witnessed by a small covering number at scale d 1 4

(log B)/N . The best-case scenario is when all the means are tightly clustered around a few values, so that N is small but B is large, then the improvement in the MSE is by a factor of order (log B)/d.

Methodology and Theory in the Kernel Mean Embedding Framework

We recall that the principle of KME posits a reproducing kernel k on an input space Z, corresponding to a feature mapping Φ : Z → H, where H is a Hilbert space, with k(z, z ′ ) = φ(z), φ(z ′ ) . The feature mapping φ can be extended to probability distributions P on Z, via φ(P) := E Z∼P [φ(Z)], provided this expectation exists, which can be guaranteed for instance if φ is bounded. This gives rise to an extended kernel on probability distributions via k(P,

Q) := φ(P), φ(Q) = E (Z,Z ′ )∼P⊗Q [k(Z, Z ′ )].
As explained in the introduction, if we have a large number of distributions (P i ) i∈ B for each of which an independent bag (Z

(i)
k ) 1≤k≤Ni is available, and we wish to collectively estimate their KMEs, this is an instance of the model ( 1)-( 2) under the transformation

X (i) k := φ(Z (i) k ).
The distributions P i are replaced by their image distribution through φ s.t. µ i = φ(P i ) and the naive estimators are µ NE i = φ( P i ), where P i is the empirical measure associated to bag Z (i)

• . We will make the assumption that the kernel is bounded, sup z∈Z k(z, z) = z∈Z φ(z) 2 ≤ L 2 , resulting in the following "bounded setting":

∀i ∈ B : N i = N and X (i) k ≤ L, P i -a.s., k ∈ N .
(BS)

(note in particular that we still assume that all bags have the same size for the theoretical results.) As always for kernel-based methods, elements of the Hilbert space H are an abstraction which are never explicitly represented in practice; instead, norms and scalar products between elements, that can be written as linear combinations of sample points, can be computed by straightforward formulas using the kernel. In this perspective, a central object is the inter-task Gram matrix K defined as K ij := k(P i , P j ) = µ i , µ j , (i, j) ∈ B 2 . In the framework of inference on distributions, the distributions P i act as (latent) training points and the matrix K as the usual kernel Gram matrix for kernel inference. In contrast to what is assumed in standard kernel inference, K is not directly observed but approximated by K s.t. K ij := µ i , µ j , for some estimators ( µ i ) i∈ B of the true KMEs. The following elementary proposition links the quality of approximation of the means with the corresponding inter-task Gram matrix:

Proposition 3.4. Assume the model (1)-(2) under the assumption X (i) k
≤ L for all k, i. Let µ i be estimators of µ i bounded by L, and the matrices K and K defined as the Gram matrices of (µ i ) i∈ B and ( µ i ) i∈ B , respectively. Then

1 B (K -K) 2 Fr. ≤ 4L 2 B i∈ B µ i -µ i 2 , ( 14
)
where K Fr. := Tr(KK T ) 1 2 is the Frobenius norm.

This result further illustrates the interest of improving the task-averaged squared error.

In order to apply our general results Theorems 3.1 and 3.2, we must again find suitable values of τ (as small as possible) and τ ′ (as close to τ as possible) so that the probability of the events A(τ ), B(τ ′ ), C(τ ), C ′ (τ ) is small, in the setting (BS). In that context, the role of the dimension d will be played by the effective dimension Tr Σ/ Σ op , where Σ is the covariance operator for the variable X. More precisely, since this quantity can change from one source distribution to the the other, we will make the following assumption: there exists d eff > 0 such that ∀i ∈ B :

d eff Σ i op ≤ Tr Σ i ≤ N σ 2 . ( 15
)
Observe that in view of (3), the upper bound above is merely a reformulation of (6) and, therefore, not a new assumption; the lower bound is. We consider tests based on the unbiased estimate of the maximum mean discrepancy (MMD; note that the MMD between tasks i and j is exactly ∆ 2 ij ):

U ij = 1 N (N -1) N k,ℓ=1 k =ℓ X (i) k , X (i) ℓ + X (j) k , X (j) ℓ - 2 N 2 N k,ℓ=1 X (i) k , X (j) ℓ
.

Proposition 3.5. Consider model (1), the bounded setting (BS) and assume (15) holds. Define

r(t) := 5 1 d eff + L N σ t + Lt N σ , (16)
and

τ min (t) := r(t) max √ 2, r(t) . ( 17
)
For a fixed t ≥ 1, define the tests T ij for i, j in B 2

T ij := 1 U ij < τ σ 2 /2 . ( 18
)
Then, provided τ ≥ 144τ min (t) , it holds

P[A(τ ) ∪ B(τ /4) ∪ C(τ /7) ∪ C ′ (τ /48)] ≤ 14B 2 e -t .
The quantity r(t) above (taking t = log(14B 2 α -1 ), where 1α is the target probability) plays a role analogous to δ in the Gaussian setting (Proposition 3.3). As the bag size N becomes sufficiently large, we expect σ = O(N -1 2 ) and, therefore, σN = O(N 1 2 ). Hence, provided N is large enough, the quantity r(t) is mainly of the order log(B)/d eff . Like in the Gaussian case, this factor determines the potential improvement with respect to the naive estimator, which can be very significant if the effective data dimensionality d eff is large.

From a technical point of view, capturing precisely the role of the effective dimension required us to establish concentration inequalities for deviations of sums of bounded vector-valued variables improving over the classical vectorial Bernstein's inequality of [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF]. We believe this result (see Corollary F.3 in the supplemental) to be of interest of its own and to have potential other applications.

EXPERIMENTS AND EVALUATION

We validate our theoretical results in the KME setting 1 on both synthetic as well as real world data. The neighboring kernel means are determined from the tests as described in Eq. ( 18). More specifically, in practice we use the modification that (i) we adapt the formula for possibly unequal bag sizes, and (ii) in each test T ij we replace σ 2 by the task-dependent unbiased estimate

MSE(i, µ NE i ) := 1 2N 2 i (N i -1) • Ni k =ℓ k(Z (i) k , Z (i) k ) -2k(Z (i) k , Z (i) ℓ ) + k(Z (i) ℓ , Z (i) ℓ ). ( 19
)
We analyze three different variations of our method which we call similarity test based (STB) approaches. STB-0 corresponds to Eq. ( 5) with γ = 0. STB weight uses model optimization to find a suitable value for γ, whereas STB theory sets γ as defined in Eq. ( 7). However, here we replaced τ with c • τ , where c > 0 is a multiplicative constant, to allow for more flexibility. We compare their performances to the naive estimation, NE, and the regularized shrinkage estimator, R-KMSE, [START_REF] Muandet | Kernel mean shrinkage estimators[END_REF] which also estimates the KME of each bag separately but shrinks it towards zero. Furthermore, we modified the multi-task averaging approach presented in [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF] such that it can be used for the estimation of kernel mean embeddings. Similar to our idea, this method shrinks the estimation towards related tasks. However, they require the task similarity to be known. Therefore, we test two options: MTA const assumes constant similarity for each bag; MTA stb uses the proposed test from Eq. ( 18) to assess the bags for their similarity. See Appendix G for a detailed description of the tested methods.

In the presented results, each considered method has up to two tuning parameters that, in our experiments, are picked in order to optimize averaged test error. Therefore, the reported results can be understood as close to "oracle" performance -the best potential of each method when parameters are close to optimal tuning. While this can be considered unrealistic for practice, a closely related situation can occur in the setting where the user wishes to use the method on test bags of size N , and has at hand a limited number of training bags of much larger size N ′ ≫ N . From each such training bag, one can subsample N points, use the method for estimation of the means of all bags of size N (incl. subsampled bags), and monitor the error with respect to the means of the full training bags (of size N ′ , used as a ground truth proxy). This allows a reasonable calibration of the tuning parameters.

Synthetic Data

The toy data consists of multiple, two-dimensional Gaussian distributed bags Z (i)

• with fixed means but randomly rotated covariance matrices, i.e.

Z (i) • ∼ N 0, R(θ i )ΣR(θ i ) T = P i , θ i ∼ U(-π /4, π /4),
where the covariance matrix Σ = diag(1, 10) is rotated using rotation matrix R(θ i ) according to angle θ i . The different estimators are evaluated using the unbiased, squared MMD between the estimation µ i and µ i as loss. Since µ i is unknown, it must be approximated by another (naive) estimation

µ NE i (Y (i) • ) based on independent test bags Y (i) •
from the same distribution as

Z (i) • , with |Y (i) • | = 1000. The test bag Y (i) • has much larger size than the training bag Z (i) • , as a consequence the estimator µ NE i (Y (i)
• ) has a lower MSE than all considered estimators based on Z (i)

• , and can be used as a proxy for the true µ i . 2 In order to guarantee comparability, all methods use a Gaussian RBF with the kernel width fixed to the average feature-wise standard deviation of the data. Optimal values for the model parameter, e.g. ζ and γ for STB weight, are selected such that they minimize the estimation error averaged over 100 trials. Once the values for the parameters are fixed, another 200 trials of data are generated to estimate the final generalization error. Different experimental setups were tested:

(a) Different Bag Sizes B = 50 and N i ∈ [10, 300] for all i ∈ B , (b) Different Number of Bags B ∈ [10, 300] and N i = 50 for all i ∈ B , (c) Imbalanced Bags B = 50 and N 1 = 10, . . . , N 50 = 300, (d) Clustered Bags N i , B = 50 for all i ∈ B but the Gaussian distributions are no longer centered around 0. Instead, each ten bags form a cluster with the cluster centers equally spaced on a circle. The radius of the circle is varied between 0 and 5, to model different degrees of overlap between clusters. The results for the experiments on the synthetic data can be found in Figure 1(a) to (d). The estimation of the KME becomes more accurate as the bag size per bag increases. Nevertheless, all of the tested methods provide an increase in estimation performance over the naive estimation, although, the improvement for larger bag sizes decreases for R-KMSE and MTA const. As expected, methods that use the local neighborhood of the KME yield lower estimation error when the number of available bags increases. Interestingly, this decrease seems to converge towards a capping value, which might reflect the intrinsic dimensionality of the data as indicated by Theorems 3.1 and 3.2 2 Additionally, the estimation of the squared loss is unbiased if the diagonal entries of the Gram matrix will be included for Z (i)

• but excluded for Y (i) • .
combined with Proposition 3.5. Although we assumed equal bag sizes in the theoretical results, the proposed approaches provide accurate estimations also for the imbalanced setting. Figure 1(c) shows that the improvement is most significant for bags with few samples, which is consistent with results on other multi-task learning problems (see e.g. [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF]. However, when the KME of a bag with many samples is shrunk towards a neighbor with few samples, the estimation can be deteriorated (compare results on (a) with those on (c) for large bag sizes). A similar effect can be seen in the results on the clustered setting. When the bags overlap, a bag from a different cluster might be considered as neighbor which leads to a stronger estimation bias. When the tasks have similar centers or are strictly separated, the methods show similar performance to what is shown in Figure 1(b).

To summarize, NE and R-KMSE give worst performances because they estimate the kernel means separately. Even though MTA const assumes all tasks to be related, it improves the estimation performance even when the bags are not similar. However, the methods that derive the task similarity from the local neighborhood achieve most accurate KME estimations in all of the tested scenarios, especially STB weight and STB theory.

Real World Data

We test our methods on a remote sensing data set. The AOD-MISR1 data set is a collection of 800 bags with each 100 samples. The samples correspond to randomly selected pixels from a MISR satellite, where each instance is formed by 12 reflectances from three MISR cameras. 3 It can be used to predict the aerosol optical depth (AOD) which poses an important problem in climate research [START_REF] Wang | Mixture model for multiple instance regression and applications in remote sensing[END_REF].

The data is standardized such that each of the features has unit standard deviation and is centered around zero. In each out of the 100 trials, we randomly subsample 20 samples from each bag, on which the KME estimation is based. This estimation is then compared to the naive estimation on the complete bag. Cross-validation, with 400 bags for training and testing, is used to optimize for the model parameters of each approach and then estimate its error. Again, all methods use a Gaussian RBF with the kernel width fixed to one. The results are shown in Table 1. Again, all of the methods provide a more accurate estimation of the KME than the naive approach. The estimations given by STB-0 are similar to those of NE, because STB-0 considers very few bags as neighbors. This lets us conclude that the bags are rather isolated than overlapping. MTA stb, STB weight and STB theory might give better estimations because they allow for more flexible shrinkage. Again, STB weight and STB theory are outperforming the remaining methods.

CONCLUSION

In this paper we proposed an improved estimator for the multi-task averaging problem. The estimation is improved by shrinking the naive estimation towards the average of its neighboring means. The neighbors of a task are found by multiple testing so that task similarities must not be known a priori. Provided that appropriate tests exist, we proved that the introduced shrinkage approach yields a lower mean squared error for each task individually and also on average. We show that there exists a family of statistical tests suitable for isotropic Gaussian distributed data or for means that lie in a reproducing kernel Hilbert space. Theoretical analysis shows that this improvement can be especially significant when the (effective) dimension of the data is large, using the property that the typical detection radius of the tests is much better than the standard estimation error in high dimension. This property is particularly important for the estimation of multiple kernel mean embeddings (KME) which is an interesting application relevant for the statistical and machine learning community. The proposed estimator and the theoretical results can naturally be translated to the KME framework.

We tested different variations of the presented approach on synthetic and real world data and compared its performance to other state-of-the-art methods. In all of the conducted experiments, the proposed shrinkage estimators yield the most accurate estimations.

Since the estimation of a KME is often only an intermediate step for solving a final task, as for example in distributional regression [START_REF] Szabó | Learning theory for distribution regression[END_REF], further effort must be made to assess whether the improved estimation of the KME also leads to a better final prediction performance. Furthermore, the results on the imbalanced toy data sets have shown that the shrinkage estimator particularly improves the estimation of small bags. However, when the KME of a bag with many samples is shrunk towards a neighbor with low bag size, its estimation might be distorted. There-fore, another direction for future work will be the development of a similarity test or a weighting scheme that take the bag size into account in a principled way. From a theoretical perspective, we also will investigate if the improvement factor with respect to the naive estimates is optimal in a suitable minimax sense, and if the logarithmic factor log(B) and the number of tasks appearing in this factor can be removed or alleviated in certain circumstances.

A Proof of Theorem 3.1

We argue conditional to the tests, below expectations are taken with respect to the samples (X (b)

• ) b∈ B only. Assume the event A c (τ ) holds, implying for all i:

j ∈ V i ⇒ ∆ 2 ij ≤ τ σ 2 . ( 20
)
Take i = 1 without loss of generality, and denote

V = V 1 , V * = V 1 \ {1}, and v = |V 1 |.
We also put η = 1γ. We use an argument similar to that leading to (4) using independence of the bags, triangle inequality and (20):

MSE(1, µ 1 ) = E (1 -η)( µ NE 1 -µ 1 ) + η v j∈V ( µ NE i -µ 1 ) 2 = η 2 v 2 i∈V * (µ i -µ 1 ) 2 + i∈V * E µ i -µ NE i 2 + (1 -η(1 -v -1 )) 2 E µ NE 1 -µ 1 2 ≤ σ 2 η 2 v 2 (v -1) 2 τ + (v -1) + (1 -η(1 -v -1 )) 2 = σ 2 η 2 (1 -v -1 ) (1 -v -1 )τ + 1 -2η(1 -v -1 ) + 1 .
The optimal value of γ = 1η is given by ( 7) and gives rise to (8).

Assume additionally that B c (τ ′ ) holds. Let ε := √ τ ′ σ/2 and let C := {x 1 , . . . , x N } be an ε-covering of the set of means. Let π(i) be the index of the element of C closest to µ i , and

N k := {b ∈ B : π(b) = k}, i ∈ N . By the triangle inequality, for any i ∈ N , b ∈ N i one has |V b | ≥ N π(i) . Hence averaging (8) over i we get 1 B B b=1 MSE(b, µ b ) ≤ σ 2 B i∈ B τ (|N π(i) | -1) + 1 1 + (1 + τ )(|N π(i) | -1) = σ 2 B k∈ N |N k |(τ (|N k | -1) + 1) 1 + (1 + τ )(|N k | -1) .
The above take the form k f (|N k |), and it is straightforward to check that f is convex. Since it holds 1 ≤ |N k | ≤ B -N + 1 for all k, and k∈ N |N k | = B, the maximum of the above expression is attained for an extremal point of this convex domain, i.e., by symmetry, N 1 = B -N + 1 and

N k = 1 for k ≥ 2. Therefore 1 B B b=1 MSE(b, µ b ) ≤ σ 2 B (N -1) + (B -N + 1)((B -N )τ + 1) (B -N )(1 + τ ) + 1 = σ 2 B N + (B -N ) 2 τ (B -N )(1 + τ ) + 1 ≤ σ 2 τ τ + 1 + N B 1 τ + 1 .

B Proof of Theorem 3.2

We follow the same general line as in theorem 3.1. Assume the event A c (τ )∩B c (τ ′ )∩C c (τ )∩C ′c (τ ) holds. Take i = 1 without loss of generality, and denote

V = V 1 , V * = V 1 \ {1}, and v = |V 1 |. We still put η = 1 -γ. Then µ 1 -µ 1 2 = (1 -η)( µ NE 1 -µ 1 ) + η v j∈V ( µ NE j -µ 1 ) 2 ≤ 2   (1 -η(1 -v -1 ))( µ NE 1 -µ 1 ) + η v j∈V * ( µ NE j -µ j ) 2 + η 2 v 2 j∈V * µ j -µ 1 2   .
Let us upper bound the different terms. Because j ∈ V , we know that ∆ j1 ≤ τ σ 2 , so by the triangle inequality

η v j∈V * µ j -µ 1 ≤ η v j∈V * ∆ ij ≤ η(1 -v -1 ) √ τ σ.
Let us develop the other term :

(

1 -η(1 -v -1 ))( µ NE 1 -µ 1 ) + η v j∈V * ( µ NE j -µ j ) 2 = (1 -η(1 -v -1 )) 2 µ NE 1 -µ 1 2 + 2η(1 -η(1 -v -1 )) v j∈V * µ NE 1 -µ 1 , µ NE j -µ j + η 2 v 2 j =k∈V * µ NE j -µ j , µ NE k -µ k + η 2 v 2 j∈V * µ NE j -µ j 2 ≤ σ 2 (1 -η(1 -v -1 )) 2 (1 + τ ) + 2η(1 -η(1 -v -1 ))(1 -v -1 )τ + η 2 (1 -v -1 ) 2 τ + η 2 v -1 (1 -v -1 )(1 + τ ) .
Let us associate the two expressions, we obtain that :

µ 1 -µ 1 2 ≤ 2σ 2 τ + 1 -2(1 -v -1 )η + (1 -v -1 )(1 + τ )η 2 .
The expression is minimal when η = (1 + τ ) -1 . By the same arguments about using covering numbers as in the proof of Theorem 3.1, we obtain that with probability greater than

1 -P[A(τ ) ∪ B(τ ′ ) ∪ C(τ ) ∪ C ′ (τ )] : 1 B i∈ B µ i -µ i 2 ≤ 2σ 2 B i∈ B τ + τ + |V i | -1 1 + τ ≤ 2σ 2 τ + τ 1 + τ + N B 1 1 + τ .

C Proof of Proposition 3.3

Recall that we assume the (GI) model. We first consider the behavior of a single test

T ij = 1 µ NE i -µ NE j 2 ≤ ζσ 2
, where σ 2 := d/N , we also put ∆ 2 = ∆ 2 ij for short. The random variable

Z := µ NE i -µ NE j is distributed as N (µ i -µ j , 2n -1 I d )
by independence of the bags. From classical concentration results for chi-squared variables recalled as Proposition E.1 in Section E, for any α ∈ (0, 1) either of the inequalities below hold with probability 1α:

∆ 2 + 2σ 2 -4σ log α -1 d ≤ Z ≤ ∆ 2 + 2σ 2 + 2σ log α -1 d . (21)
Put δ := (log α -1 )/d for short.

We start with analyzing Type I error: if ∆ 2 ≥ τ σ 2 , then the above lower bound implies

Z 2 ≥ σ 2 √ 2 + τ -4 √ δ 2 , so T ij = 0 if we choose ζ := √ 2 + τ -4 √ δ 2
. By union bound over (i, j) ∈ B 2 , with this choice we guarantee that P[A(τ )] ≤ α if we replace α by αB 2 (i.e. take δ = (2 log B + log α -1 )/d). This establishes the bound on family-wise type I error.

We now analyze type II error: assume now that we have picked

ζ := √ 2 + τ -4 √ δ 2 , with
τ ≥ max(Cδ, √ Cδ), C = 1000, and assume ∆ 2 ≤ τ ′ σ 2 . Then assuming the upper bound in ( 21) is satisfied, we ensure

T ij = 1 provided √ τ ′ + 2 ≤ √ τ + 2 -6 √ δ.
Note that the condition on τ ensures that the above right-hand-side is positive. Taking squares and further bounding, a sufficient condition for the above is τ ′ ≤ τ -12 (2 + τ )δ. Using the condition on τ , it holds

12 (2 + τ )δ ≤ 12 √ 3C -1 τ ≤ 2 3 τ,
hence τ ′ ≤ τ /3 is a sufficient condition. This ensures, by the union bound, that P[B(τ ′ )] ≤ α when replacing δ by δ ′ = (2 log B + log α -1 )/d as above.

We now turn to controlling the probability of the events C(τ ) and C ′ (τ ). For fixed i, j put

X 1 = µ NE i -µ i , X 2 = µ NE j -µ j . Under the (GI) model, X 1 , X 2 are independent N (0, N -1 I d ).
Applying the result of Proposition E.2, we obtain that for α ∈ (0, 1), we have probability at least 1 -2α:

| X i , X j | ≤ σ 2 √ 2δ + δ ,
where we have put δ := (log α -1 )/d as previously. As soon as τ ≥ max(Cδ, √ Cδ), (C ≥ 1) we obtain | X i , X j | ≤ 3τ σ 2 / √ C on the above event, implying that the event C(τ ) is a fortiori satisfied for C = 10 3 .

From estimate (24) in Proposition E.1, we have with probability at least 1α:

X 1 ≤ σ 2 1 + √ 2δ ≤ σ 2 1 + 2τ C -1 ,
under the same condition on τ as above. As previously, by the union bound the above estimates are true simultaneously for all i, j with the indicated probabilities if we replace δ by δ ′ = (2 log B + log α -1 )/d, and C ′ (τ ) is satisfied when taking C = 10 3 .

Suppose now ∆ ij 2 < (τ /4)σ 2 = (λ 2 /4)ξ(t). Then, according to the concentration ineqality (39), with probability greater than 1 -8e -t , it holds

U ij ≤ ∆ ij 2 + 2 ∆ q(t) + 2 2σ 2 q(t) + 11q 2 (t) ≤ λ 2 /4 + λ + 13 ξ(t) ≤ (λ 2 /2)ξ(t) = (τ /2)σ 2 .
We have used that λ 2 /4 + λ + 13 ≤ λ 2 /2 for λ ≥ 12. So

P ∆ ij 2 < τ σ 2 /4 and T i = 0 ≤ 2e -t .
An union bound over (i, j) ∈ B 2 gives that

P[A(τ ) ∪ B(τ /4)] ≤ 8B 2 e -t .
Remarking that σ 2 τ /7 ≥ 20q(t) max(q(t), 2σ 2 ) and σ 2 τ /48 ≥ 3q(t) max(q(t), 2σ 2 ) ≥ 2q(t) 2σ 2 + q 2 (t) and using the concentration inequalities ( 30) and ( 36) gives

P[C(τ /7)] ≤ 6(B 2 -B)e -
P Z ≥ µ 2 + σ 2 d + σ √ 2t ≤ e -t , (24)
and

P Z ≤ µ 2 + σ 2 d -2σ √ 2t ≤ e -t . (25)
Proof. The stated inequalities are direct consequences of classical deviation inequalities for (noncentral) χ 2 variables. Put λ := µ 2 , then for the upper deviation bound, Lemma 8.1 of [START_REF] Birgé | An alternative point of view on Lepski's method[END_REF]

states that P Z 2 ≥ λ + dσ 2 + 2 (2λ + dσ 2 )σ 2 t + 2σ 2 t ≤ e -t ,
and we have λ 24). For the lower deviation bound, Lemma 8.1 of [START_REF] Birgé | An alternative point of view on Lepski's method[END_REF] states that

+ dσ 2 + 2 (2λ + dσ 2 )σ 2 t + 2σ 2 t ≤ λ + dσ 2 + σ √ 2t 2 , implying (
P Z 2 ≤ λ + dσ 2 -2 (2λ + dσ 2 )σ 2 t ≤ e -t ,
and we have

λ + dσ 2 -2 (2λ + dσ 2 )σ 2 t + ≥ λ + dσ 2 λ + dσ 2 -2σ √ 2t + ≥ λ + dσ 2 -2σ √ 2t 2 +
, leading to (25).

Proposition E.2. Let X 1 , X 2 be independent N (0, σ 2 I d ) variables in dimension d. Then for any t ≥ 0:

P X 1 , X 2 ≥ σ 2 √ 2dt + t ≤ e -t . (26)
Proof. Without loss of generality assume σ 2 = 1. For two independent one-dimensional Gaussian variables G 1 , G 2 , one has for any λ ∈ [0, 1]:

E[exp λG 1 G 2 ] = E[E[exp λG 1 G 2 |G 2 ]] = E exp λ 2 2 G 2 2 = 1 √ 1 -λ 2 , so that log E[exp λ X 1 , X 2 ] = d 2 (-log(1 -λ 2 )) ≤ d 2 λ 2 (1 -λ) .
Applying Lemma 8.2 of [START_REF] Birgé | An alternative point of view on Lepski's method[END_REF] gives ( 26).

F Concentration Results in the Bounded Setting

Studying concentration in the kernel setting means having concentration results of bounded variables taking values in a separable Hilbert space. Recall that k(x, y) = φ(z), φ(z ′ ) H for all z,z ′ in H, so that if k is bounded by L 2 , then the map φ is bounded by L. To obtain concentration results, we will use Talagrand's inequality.

Theorem F.1 (Talagrand's inequality). Let X s 1 , ..., X s N be iid real random variables indexed by s ∈ S where S is a countable index set, and L be a positive constant such that:

E[X s k ] = 0 , and |X s k | ≤ L a.s. ∀k ∈ N , s ∈ S .
Let us note Z = sup s∈S N k=1 X s k , then for all t ≥ 0 :

P Z -E[Z] ≥ 2 (2v + 16LE[Z])t + 2Lt ≤ e -t ; P -Z + E[Z] ≥ 2 (4v + 32LE[Z])t + 4Lt ≤ e -t ,
where v = sup s∈S N k=1 E (X s k ) 2 . Talagrand's inequality appeared originally in [START_REF] Talagrand | New concentration inequalities in product spaces[END_REF], with the above form (using additional symmetrization and contraction arguments from [START_REF] Ledoux | Probability in Banach Spaces: Isoperimetry and Processes[END_REF] appearing in [START_REF] Massart | About the constants in Talagrand's concentration inequalities for empirical processes[END_REF]. The constants in the upper deviation bound have been improved by [START_REF] Rio | Une inégalité de Bennett pour les maxima de processus empiriques[END_REF] and [START_REF] Bousquet | A Bennett concentration inequality and its application to suprema of empirical processes[END_REF], however no such improvement is available for lower devations as far as we know. The above version is taken from Massart (2007) p. 169-170, (5.45) and (5.46) combined with (5.47) there.

Because a Hilbertian norm can be viewed as a supremum, we can use Talagrand's inequality to obtain a concentration inequality for the norm of the sum of bounded Hilbert-valued random variables.

Proposition F.2. Let (Z k ) 1≤k≤N be i.i.d. random variables taking values in a separable Hilbert space H, whose norm is bounded by L a.s. Let µ and Σ denote their common mean and covariance operator. Let

V = 1 N N k=1 Z k , and V c = 1 N N k=1 Z k -µ .
Corollary F.3. Using the setting and notation of Proposition F.2, we have

-2q Σ (1) + Tr Σ N ≤ E[V c ] ≤ Tr Σ N .
As a consequence, for any t > 0,

P V 2 ≥ µ 2 + Tr Σ N + q Σ (t) 2 + 2 µ q Σ (t) ≤ 2e -t , (34)
and for any t ≥ 1,

P V 2 ≤ µ 2 + Tr Σ N -4q Σ (t) 2 + -2 µ q Σ (t) ≤ 2e -t , (35)
Remark. To the expert reader, we want to point out that the above concentration estimates are sharper than the Bernstein's concentration inequality for vector random variables due to [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF] (Corollary 1 there) and which has found many uses in the recent literature on kernel methods. The reason is that in Pinelis and Sakhanenko's result, which concerns deviations of the centered process V c , the deviation term (in factor of t) for V c is proportional to Tr Σ/N . The inequality of Pinelis and Sakhanenko also only bounds upper deviations.

In contrast, in the above result, the term Tr Σ/N = E V c 2 1 2 appears with constant 1, and the main deviation term (in factor of t) only involves Σ op /N , which is better by a factor of 1/ √ d eff . We also obtain the informative lower deviation bound (35).

To summarize, [START_REF] Pinelis | Remarks on inequalities for large deviation probabilities[END_REF]'s inequality controls the upper deviations of V c from zero in terms of a factor of its expectation, while the above concentration inequalities control the two-sided deviations of V 2 c from its expectation, which is Tr Σ/N , in terms of a factor of its typical deviation, which is Σ op /N . This improvement makes the above bound first-order correct and mimic more closely the Gaussian chi-squared deviation phenomenon of Proposition E.1. This sharpness (and the fact that we get a control for two-sided deviations) is crucial in order to be able to capture the behavior of the effective dimension, see in particular Proposition F.5 below for the analysis of the MMD U-statistic, for which the exact cancellation of the first order terms is paramount.

Proof. The upper bound of the mean of V c is given directly by Jensen's inequality. For the lower bound, we can rewrite Talagrand's inequality (30) equivalently under the following form: there exists ξ, an exponential random variable of parameter 1, such that almost surely

V c ≤ E[V c ] + q Σ (ξ) = E[V c ] + α ξ + βξ,
where α and β are given by (29). Taking the square and then the mean gives :

E V 2 c ≤ E E[V c ] + α ξ + βξ 2 ≤ E E[V c ] + (α + β) ξ 2 + 2(α + β)E[V c ]ξ + (α + β) 2 ξ 2 .
We can use now the concavity of the function ξ

→ E[V c ] + (α + β) √ ξ 2 and Jensen's inequality, obtaining E V 2 c ≤ (E[V c ] + (α + β)) 2 + 2(α + β)E[V c ] + 2(α + β) 2 ≤ (E[V c ] + 2(α + β)) 2 .
which implies, using again (35), and N ≥ 2, that with probability greater than 1 -8e -t it holds:

U ≥ µ X -µ Y 2 -2 µ X -µ Y q(t) + Tr Σ X + Tr Σ Y N -4q(t) 2 + - Tr Σ X + Tr Σ Y N -16q 2 (t) ≥ µ X -µ Y 2 -2 µ X -µ Y q(t) -8 2σ 2 q(t) -32q 2 (t) ,
which is (40).

G Details on the Tested Methods in the Numerical Experiments

In the following, the methods that are tested in the experiments are described in more detail.

Recall, that V i := {j : T ij = 1, j ∈ B } and let T ij be defined as in Eq (18), i.e. V i holds the neighboring kernel means of bag i. All of the methods give KME estimations of the form μi :

= j∈ B ω ij • µ NE j ,
where the definition of the weighting w ij depends on the applied method.

1. NE considers each bag individually. Therefore, the weighting is simply

ω ij = 1, for i = j 0, otherwise.
2. R-KMSE was proposed by [START_REF] Muandet | Kernel mean shrinkage estimators[END_REF]. It estimates each KME individually but shrinks it towards 0. The amount of shrinkage depends on the data and is defined as 3. STB-0 is described in Eq. ( 5) with γ set to 0, i.e.

ω ij = 1 -λ 1+λ ,
ω ij = 1 |Vi| , for j ∈ V i 0, otherwise.
4. STB theory is defined by Eq. ( 5). It uses the optimal value for γ as described in Eq. ( 7) that was proven to be optimal. Here, τ is replaced by its empirical counterpart ζ and another multiplicative constant c > 0 was added to allow for more flexibility. Its specific value must be found using model optimization.

ω ij =      γ + 1-γi |Vi| , for i = j 1-γi
|Vi| , for i = j, j ∈ V i 0, otherwise with

γ i = c • ζ • (|V i | -1) (1 + c • ζ) • (|V i | -1) + 1 .
5. STB weight is also described by Eq. ( 5) but the optimal value of γ is found by model optimization

ω ij =      γ + 1-γ |Vi| , for i = j 1-γ
|Vi| , for i = j, j ∈ V i 0, otherwise.

6. MTA const is based on a multi-task averaging approach described in [START_REF] Feldman | Revisiting Stein's paradox: multi-task averaging[END_REF] which we translated to the KME framework as

ω ij = I + γ B D • L(A) -1 ij . (41)
Here, D = diag (E i ) i∈ B as defined in Eq. ( 19) and L(A) denotes the graph Laplacian of task-similarity matrix A. For MTA const the is assumed to be constant, i.e. A = a • (11 T ) with a = 1 B(B-1) i,j∈ B µ NE i µ NE j 2 H . Again, the optimal value for γ must be found using model optimization.

7. MTA stb is defined as in Eq. ( 41). In contrast to MTA const, the similarity matrix A is defined as

A ij = 1, for j ∈ V i 0, otherwise.
The methods STB-0, STB weight, STB theory and MTA stb use all the similarity test defined by T ij which depends on ζ. Nevertheless, the optimal value for ζ is found by model optimization for each method individually.

H Numerical Results in the Gaussian Setting

In this section we report numerical comparisons of the proposed approaches in the idealized Gaussian setting (GI). In that setting, since the tests and proposed estimates only depend on the naive estimators, we can reduce each bag to its naive estimator, in other words we can assume N = 1 (only one observation per bag). We consider the following models for the means (µ i ) i∈ B (in each case the number of bags is B = 2000):

• • Model SPHERE: ambient dimension d = 1000, the 6 first coordinates of the means are distributed uniformly on the sphere of radius 50 in R 6 , the rest are set to 0.

• Model SPARSE: ambient dimension d = 50, the means are 2-sparse vectors with two random coordinates distributed as Unif[0, 20].

In each case, we first select the parameter for the tests (parameter ζ in ( 13) ) from the oracle STB-0 performance. This value is held fixed and the shrinkage parameter in methods MTA stb, STB theory, STB weight is again determined as its "oracle" value by minimization over the squared error, as done in the KME experiments.

For comparison, we also display the results of the classical positive-part James-Stein estimator (PP James-Stein, Baranchik, 1970), which is a shrinkage estimator applied separately on each bag. It has no tuning parameter.

Figure 1 :

 1 Figure1: Decrease in KME estimation error compared to NE in percent on experimental setups (a) to (d). Higher is better. STB-0, STB weight and STB theory give similar results so that their results might be printed on top of each other.

  ( 1 /N b -1)̺ + (N b -

  Model UNIF: ambient dimension d = 1000, the means (µ i ) i∈ B are distributed uniformly over the lower-dimensional cube [-20, 20] d ′ , d ′ = 10 (the remaining coordinates are set to 0). • Model CLUSTER: ambient dimension d = 1000, the means are clustered in 20 clusters of centers (m i ) i∈ 10 , drawn as N (0, I d ), in each cluster the means are drawn as Gaussians N (m i , 0.1 * I d ),

Table 1 :

 1 Decrease in KME estimation error compared to NE in percent on the AOD-MISR1 data.

	METHOD	%	METHOD	%	METHOD	%
	R-KMSE	8.83	MTA const	13.92	STB theory 21.83
	STB-0	1.43	MTA stb	17.17	STB weight 22.73

  t , and P[C ′ (τ /48)] ≤ Be -t .E Concentration Results in the Gaussian SettingProposition E.1. Let Z be a normal N (µ, σ 2 I d ) random variable in R d . Then for any t ≥ 0:

Table 2 :

 2 Decrease in averaged squared estimation error compared to NE in percent on the Gaussian data (higher is better). Averaged results over 20 trials. Standard error of one given trial is of order 5.10 -3 .

		PP James-Stein MTA const MTA stb STB-0 STB theory STB weight
	UNIF	0.439	0.427	0.653	0.796	0.813	0.813
	CLUSTER	0.495	0.508	0.979	0.980	0.980	0.980
	SPHERE	0.285	0.285	0.745	0.894	0.898	0.898
	SPARSE	0.224	0.162	0.367	0.402	0.441	0.443

In the Gaussian setting, we report numerical results in the Appendix H.

We only use 12 out of 16 features because the remaining four are constant per bag.

Acknowledgements

The research of HM was funded by the German Ministry for Education and Research as BI-FOLD (01IS18025A and 01IS18037A). The research of GB has been partially funded by Deutsche Forschungsgemeinschaft (DFG) -SFB1294/1 -318763901, and by the Agence Nationale de la Recherche (ANR, Chaire IA "BiSCottE"). GB acknowledges various inspiring and motivating discussions with A. Carpentier, U. Dogan, C. Giraud, V. Koltchinskii, G. Lugosi, A. Maurer, G. Obozinski, C. Scott.

D Results in the Bounded Setting (for KME Estimation) D.1 Proof of Proposition 3.4

D.2 Proof of Proposition 3.5

Recall the notation

and τ min (t) := r(t) max √ 2, r(t) .

Introduce the notation q(t) := σr(t); ξ(t) := σ 2 τ min (t) = q(t) max( √ 2σ, q(t)). Let i, j ∈ B 2 be fixed and t ≥ 1. We put τ = λ 2 τ min (t) with λ ≥ 12.

Suppose that ∆ ij 2 > τ σ 2 = λ 2 τ min σ 2 = λ 2 ξ(t). We use the concentration inequality (40) for bounded variables, proved in Section F, and obtain that with probability greater than 1 -8e -t , and using the definition of ξ(t):

(To be more precise, (40) proves the above estimate for the value of q(t) defined by (37), the value of q(t) defined in the present proof is an upper bound for it, so the above also holds.) Observe ∆ ij ≥ λ ξ(t) ≥ 12 ξ(t) ≥ 2q(t). By monotonicity in ∆ ij under that condition,

where we have used that λ 2 -2λ -40 ≥ λ 2 /2 for λ ≥ 12. So

Then for any t ≥ 0:

and

where

Proof. Let us denote q(t) for q Σ (t) for this proof. We start with bounding the deviations of V c . Observe that

where the supremum can be restricted to u in a dense countable subset S of the unit sphere, since H is separable. We can therefore apply Talagrand's inequality with

Tr Σ by Jensen's inequality, which we use to further bound the deviation term by q(t).

By Theorem F.1, with probability greater than 1e -t for t ≥ 0, it holds

and with probability greater than 1e -t ,

We turn to bounding the deviations of

Using Bernstein's inequality for the variables

and |W i | ≤ L µ , we have that with probability greater than 1e -t , for t ≥ 0 :

Combining inequality ( 33) with ( 32) and ( 30) gives that with probability greater than 1 -2e -t :

and, combining (33), ( 32) and (31), we have with probability greater than 1 -2e -t :

Because E V 2 c = Tr Σ/N , and (α + β) = q Σ (1) by definition, we obtain that

If t ≥ 1, it holds q(t) ≥ q(1) and we can plug in the above estimates for E[V c ] into ( 27) and ( 28) to obtain (34) and ( 35), respectively (note that the condition t ≥ 1 is only needed for the lower devation bound).

∼ Y be independent families of centered random variables bounded by L in a separable Hilbert space H. Let Σ X and Σ Y be their respective covariance operators, σ 2 and d eff such that

Then for any t ≥ 0:

where

Proof. Let us remark that

So, by Corollary F.3, with probability greater than 1-6e -t , for t ≥ 1, and using (a-b) 2 + ≥ a 2 -2ab:

∼ Y be independent families of random variables bounded by L in H. Let µ x , Σ X and µ Y , Σ Y denote their respective means and covariance operators. Let U the statistic defined as

Then for any t ≥ 1, N ≥ 2:

and

where q(t) is given by (37).

Proof. Observe that

Using now the upper bound of Bernstein's inequality, since E X 2 = µ X 2 + Tr Σ X , with probability greater than 1e -t it holds:

So using (34) (twice), with probability greater than 1 -6e -t :

Using again (34), and N ≥ 2, with probability greater than 1 -8e -t :

which is (39). We proceed similarly for lower deviations of U : using again Bernstein's inequality and (35), with probability greater than 1 -6e -t , and using (ab) 2 + ≥ a 2 -2ab:


Christelle Baunez
email: christelle.baunez@univ-amu.fr

Mickael Degoulet
email: mickael.degoulet@univ-amu.fr

Stéphane Luchini
email: stephane.luchini@univ-amu.fr

Patrick A Pintus
email: patrick.pintus@univ-amu.fr

Miriam Teschl
email: miriam.teschl@ehess.fr

An Early Assessment of Curfew and Second COVID-19 Lock-down on Virus Propagation in France *

Keywords: JEL Classification Numbers: I18, H12 COVID-19, Effects of Curfew and Lock-down, Acceleration Index, Real-time Analysis, France

).

We find that while the pandemic is still in the acceleration regime, acceleration decreased notably with curfew measures and this more rapidly so for the more vulnerable population group, that is, for people older than 60. Acceleration continued to decline under lock-down, but more so for the active population under 60 than for those above 60. For the youngest population aged 0 to 19, curfew measures did not reduce acceleration but lock-down does. This suggests that if health policies aim at protecting the elderly population generally more at risk to suffer severe consequences from COVID-19, curfew measures may be effective enough. However, looking at the departmental map of France, we find that curfews have not necessarily been imposed in départements where acceleration was the largest.

Introduction

In this note, we provide an early assessment of reinforced measures to dampen the spread of COVID-19 in France. These measures where introduced in three waves, each with one week interval. First, from October 17 onwards, eight major cities and their adjacent surroundings called "métropoles", plus the whole of "Île de France" which includes Paris, all together corresponding to 16 "départements" (roughly counties) were put under curfew from 9pm to 6am. 1 The following week, 38 départements were further added, so that a total of 54 out of 96 départements of metropolitan France were declared under mandatory curfew from October 23 onwards. Finally, starting on October 30, a nation-wide lock-down was implemented and is still ongoing. These three waves of health policy measures to combat the COVID-19 pandemic provide an excellent data-set to compare. In the following, we refer to those three weeks respectively "curfew 1", "curfew 2" and "lock-down".

We first focus on virus propagation of two age groups, below and above 60 years, and across départements. These two age groups correspond roughly to the population which is more (above 60 years old) and less (59 years and younger) vulnerable in terms of hospitalisation and mortality (e.g. Promislow [START_REF] Promislow | A Geroscience Perspective on COVID-19 Mortality[END_REF]). We also single out in particular the age group of young people aged 19 and less as they continue to go to school even though curfew and lock-down measures were put in place.

To make this assessment, we update the acceleration index introduced in Baunez et al. [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF]. This index tracks in real-time the propagation of COVID-19 and can do so at very granular levels. It is a scale-free measure of the speed at which tests detect positive cases. This acceleration index aggregates information provided by the daily and average positivity rates, as computed from daily numbers of tests and confirmed cases. This means that the index tracks in real-time the acceleration and deceleration of the the virus and can thus serve to visualise rapidly whether any health policy measures have their desired effects or not.

The main results are that the curfew on a larger number of départements in week 2 seems almost as effective in dampening the acceleration among the age group 60+ who are particularly at risk of severe COVID-19 consequences as lock-down measures. Lock-down measures do have quicker effects on both age-groups and especially on the population 59 and younger. Curfew measures do not have any effects on reducing acceleration among the youngest population aged 0 to 19, but lockdown does. However, looking at the departemental map of France, we find that curfews have not necessarily been imposed on départements which did have the greatest acceleration. It is therefore difficult to judge unambiguously which of the policy measures was the most effective one, other than to say that lock-down measures have a quicker impact on the whole population, but very possibly with much higher economic and social costs than curfew measures. Given that the population aged 60 and more is notoriously more at risk of severe COVID-19 consequences, our data analysis may 1 A caveat is in order to indicate that the eight métropoles are not exactly corresponding to the départements in which they are. However, in the following, we consider métropoles to correspond to départements and therefore refer to 16 départements for the first curfew, one for each of the eight métropoles and the eight départements to which corresponds "Île de France".

suggest that curfew measures are enough to reduce the viral spread among this group.

In the following we present the effects of curfew and lock-down measures by looking in particular at the two age-groups 60 years and more, as well as 59 years and younger (section 2.1). In section 2.2, we single out the effect of reinforced COVID-19 measures on the youngest generation aged 0 to 19. Section 2.3 presents the analysis per départements over the three waves of COVID-19 measures for the two age groups.

The Effects of Curfew and Second Lock-down in France: an Early Assessment using the Acceleration Index

As stressed in Baunez et al. [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF], accurate information about the dynamics of a pandemic rests on both the number of cases and the number of tests, and that the former cannot be properly understood without the latter. In the aforementioned paper, we address this pressing issue and provide an acceleration index that relates to the daily and average positivity rates, in the following way. From data on the cumulated numbers of confirmed cases and tests, up to final date T , and if we denote the acceleration index at end date ε T , the following decomposition holds:

P T -P T -1 D T -D T -1 daily positivity rate = P T D T average positivity rate × ε T acceleration index (1)
where P T and D T denote respectively the cumulated numbers of positives/cases and diagnosis/tests at date T , and similarly for date T -1. Therefore, the decomposition in equation [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF] shows that the acceleration index is defined as the ratio of the daily positivity rate to the average positivity rate, that is, it is essentially an elasticity.

Effects on People Aged 60 and Older Relative to All Other People

In Figure 1 we report in panel (a) the daily and average positivity rates, while in panel (b) is depicted the acceleration index, for the age groups of people aged 59 and less (solid lines), on the one hand, and of people older than 60, on the other (dashed lines).

What is particularly striking in panel (b) of Figure 1 is that the acceleration index still increases during curfew 1 (Oct 17 -Oct 23) for both age groups when only 16 departments were under curfew, but started to decline during curfew 2 (Oct 24 -Oct 29), when the curfew was extended to 54 départements in France. Acceleration continues to decline markedly during the first week of lock-down (Oct 30 -Nov 6) for both age groups. The decline over the two last weeks is particularly true for the age group 60 and older. While their index was at 3.69 on Oct 17, it raised to 3.72 during curfew 1 on Oct 24 and then declined to 2.83 during curfew 2 and to 2.12 at the end of the first week of the lock-down. The percentage change of the acceleration index during curfew 2 was -23.9% and during the first week of the lock-down it was -25.2%. Looking at these numbers, it seems that curfew 2 had quite a considerable effect in terms of reducing acceleration for the more vulnerable group, with the lock-down having only a slightly better impact. The acceleration index for the age group 59 and younger however decreased during curfew 2 by only -14.5%, but decreased more rapidly by -27.3% during the first week of the lock-down. Hence it seems that while the curfew works for the age group 60+, it is especially the lock-down that affects the mostly active age group of 59 and younger. This appears intuitive as more active people are working from home or, in the worst case, cannot further engage in their professional activities and/or lose their jobs during lock-down and are thus supposedly less exposed to social contacts and transmission channels.

Looking at panel (a) in Figure 1, we see that the decline of the acceleration index for both age groups combines (i) a steadily increasing average positivity rate, which goes in the direction of decreasing the acceleration index, with (ii) a reversal of the daily positivity rate, which increases during curfew 1 and 2 but goes down during the first week of lock-down. This indicates that looking at daily or average positivity rate only does not deliver the same information as the acceleration index, or, if the trend persists, only at a much later stage.

All of the above suggests that the curfew has been rather effective, especially for the elderly population generally more at risk of severe consequences of COVID-19, including death. The momentum gained in terms of reducing virus circulation seems to be reinforced by the lock-down, affecting the population more generally, but at higher social and economic costs that are widely discussed elsewhere (e.g. Blanchard et al. 2020 [START_REF] Blanchard | A new policy toolkit is needed as countries exit COVID-19 lockdowns[END_REF]). It should also be noted that according to governmental the data as we have done above, the question may be raised whether a curfew would not be enough.

Effects on People Aged 19 and Younger

In Baunez et al. [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF], we show that the acceleration index increases rapidly for children aged 0 to 9 since early September. Before September, acceleration for that age group declined to reach the acceleration/deceleration threshold, that is an acceleration index of about 1, by the end of August (while the national average was still indicating acceleration). But since then, schools opened again and the acceleration increased to reach levels higher than national average. However, we did not observe such a sharp acceleration for the age group from 10 to 19 since schools opened again.

Acceleration increased as well but stayed below national average. We therefore look more specifically at the impact of the reinforced COVID-19 measures on the acceleration of the younger generation up to 19 years old, which is a widely discussed topic in academic and media circles. In Figure 2, we see that for both age groups, 0-9 and 10-19, curfews 1 and 2 do not stop the acceleration index from increasing, while lock-down does. This is to be expected since curfew measures do not affect most of the younger people's activities. However, even though schools remained open even during lock-down, an effect is visible, which could be linked to decreased physical and social activities outside school. The decrease is more marked for the 10 to 19 years old, than for the youngest children, who are possibly at an age where they engage in fewer social activities outside school than teenagers. However, the youngest children still face the greater acceleration. The acceleration index for children aged 0-9 was about 3.94 at the beginning of lock-down on October 30, but fell during the first week of lock-down by -19.5% to 3.17 on November 6. Their acceleration is thus well above the acceleration of people aged 60+, whose index was higher than of the whole group of people aged 59 and less. The acceleration index for teenagers aged 10-19 equaled about 2.72 on October 30 and fell by -28.5% to 1.95. It has to be stressed however that to the extent that children are in general at a very low risk of hospitalisation,3 acceleration among younger people are only worrying if they are in contact with the people most at risk of suffering from COVID-19 consequences. It seems therefore important to separate children from the population most at risk of having severe consequences from COVID-19. Whether a lock-down is the right measure to do so seems to be a valid question. Consequently, it may also be questioned whether a reinforced lock-down as some demand, which would include school closures, would be the right policy to take, in particular if the current trend of reduced acceleration among children persists.

Effects across Départements

In Figure 3, we report the weekly averages of the acceleration index across départements, for the age groups of people aged 59 and less (right maps), on the one hand, and of people older than 60, on the other (left maps).

What we can clearly see in Figure 3 is first, that even across départements, acceleration is generally higher for the age group 60+ than for those aged 59 and younger. Second, curfew 1 and 2 have not necessarily been imposed on those départements that experienced the strongest acceleration.

Rather, curfew 1 in particular, but also curfew 2 have been imposed on larger metropolitan areas with larger absolute numbers of positive cases. The official public health decision regarding which départements to put under curfew were based on the following governmental criteria: (i) more than 250 positive cases per 100 000 inhabitants, (ii) more than 100 cases per 100 000 elderly inhabitants; and (iii) the occupation rate of intensive care beds starts to exceed 30% with a tendency to increase further in the following weeks. As we show in Baunez et al. 2020 ([1]), the current testing strategy in place closely follows population numbers. It is then not surprising to find more cases when more tests are conducted in more populated areas. This explains why the selected dṕartements were put under curfew rather than those where the acceleration is greatest. However, as we also show only, curfew 2+ for second week of curfew followed by lock-down, curfew 1+ for two weeks of curfew followed by lock-down) for both age groups (weekly averages for the 3 consecutive weeks also shown in Figure 1). Dashed horizontal line in right panel represents when acceleration index equals 1.

Data source: Agence Santé Publique France Lock-down only in Baunez et al. [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF], more positive cases are not necessarily equivalent to greater acceleration. It may therefore be asked whether the governmental selection criteria were the right ones in the first place. Our guess is that curfew measures would have had an even stronger impact if they had been imposed on départements with the greatest acceleration from the very beginning.

From Figure 3, we also learn that none of the départments has switched from an acceleration regime to the deceleration regime. The whole map remains in different shades of red, but none of the départments turns green, which would indicate deceleration. The first two maps on the top have the 16 départments under curfew 1 encircled in light blue. The next two maps have the additional 38 départments under curfew 2 marked in dark blue. The last two maps represent the acceleration index during the first week of the lock-down for the two age-groups. We again observe that the reduction in the acceleration index for people older than 60 is more pronounced across the départments on which a curfew was imposed than for the people aged 59 or younger. The trend for a reduced acceleration continues during the first week of the lock-down for both age groups across France.

To sharpen the conclusions from the visual inspection of Figure 3, we focus on the development of the acceleration index over the three waves of COVID-19 policy measures of the two age groups across départments in three different scenarios or "treatments". These "treatments" are: départements under curfew 1 and more (curfew 1+), départements under curfew 2 and more (curfew 2+), and départements under lock-down only (lock-down only). In panel (a) of Figure 4, we report the acceleration index for the age group of people 59 and younger, while panel (b) takes care of the people 60 and older.

Figure 4 confirms that the dṕartements in "treatments" curfew 1+ and curfew 2+ have not been the ones where virus circulation was accelerating the most. This is especially the case for the 60+ who live in the départements of the lock-down only and the départements of the curfew 2 group. A similar conclusion holds for the people aged 59 and younger. As a result, it comes as no surprise that the ongoing lock-down has a stronger effect on reducing acceleration for the 60+ who live in the lock-down only départements. What we also see is that all three "treatments" achieve by and about the same acceleration index by Nov 6. Unfortunately, looking at this graph indicates that nothing more general can be said about which is the most efficient policy measure to the extent that, as we have said repeatedly above, the selection criteria for curfew has not been based on the acceleration of the COVID-19 spread. What is remarkable though is that curfew measures achieve by and large similar effects but over a longer period of time than a lock-down. Said differently, a general lock-down has, unexpectedly, quicker effects than curfew only measures. However, the collateral economic and social costs may well be higher with lock-down measures than with curfew measures.

Conclusion

This note provides an early assessment of the curfew and lock-down measures that have been adopted

to curb the COVID-19 pandemic in France. We analyse the change in virus propagation across age groups and across départements using an acceleration index introduced in Baunez et al. (2020) [START_REF] Baunez | Tracking the Dynamics and Allocating Tests for COVID-19 in Real-Time: an Acceleration Index with an Application to French Age Groups and Départements[END_REF].

We find that while the pandemic is still in the acceleration regime, acceleration decreased notably with curfew measures and this more rapidly so for the more vulnerable population group, that is, for people older than 60. Acceleration continued to decline under lock-down, in particular for the active population aged 59 and younger in comparison to curfew measures. For the youngest population aged 0 to 19, curfew measures did not reduce acceleration but lock-down does. This suggests that if health policies aim at protecting the elderly population generally more at risk to suffer severe consequences from COVID-19, curfew measures may be effective enough. Obviously, common sense would then also suggest that such measures should be accompanied with increased sanitary and social protection of the most vulnerable in this current pandemic situation as well as compensation for those who suffer from any economic losses among the general population due to the curfew. Unfortunately though, looking at the departmental map of France, we find that curfews have not necessarily been imposed in départements where acceleration was the largest, which makes conclusive comparisons of the effectiveness of COVID-19 measures harder to do. Our suggestion however is that curfew and lock-down measures would have gained from following the logic of our acceleration indicator.

In France and in other European countries, concerns about both the efficacy and the economic and social costs of a general lock-down, even in its "light form" have been raised extensively. Part of the theoretical literature has suggested that government might consider age-specific strategies that, in particular, allow to protect the most vulnerable citizens while allowing virus circulation to build up collective immunity. Gollier (2020) [START_REF] Gollier | Cost-Benefit Analysis of Age-Specific Deconfinement Strategies[END_REF], among others, make such an argument more formal within the setting of Susceptible-Infected-Recovered models at the country level.

The present contribution reinforces this conclusion, but by proposing an analysis of the existing data in real-time, based on our acceleration index. This index is particularly relevant to help assessing what the effects of the ongoing lock-down are, as it is applicable to data that are disaggregated geographically and also in the cross-section in terms of age-groups. This is a major advantage with respect to existing models that are hardly amenable to very granular levels and are subject to considerable parameter-uncertainty, especially at times when a novel pathogen emerges, as in the case of SARS-Cov2.

Our analysis clearly shows that the COVID-19 pandemic spreads differently within different agegroups and across space. It has become clear over the last few months since this novel pathogen emerged earlier this year that the age-group 60+ is the main group at risk of sever consequences due to COVID-19. Among the people currently in hospital, a vast majority of them are 60 years old and more. The same applies to dying from COVID-19. Other age-groups do not, in general, face the same severity even though they are currently exposed to by and large similar acceleration levels. Given this information and the adaptability of our indicator to local and age-specific but potentially also other characteristics, it can be used to guide health policy measures with the very specific aim to bring, in real time, the pandemic under control especially for the population most at risk and to keep them safe without imposing disproportional social and economic costs on the other population groups.

Figure 1 :

 1 Figure 1: Main acceleration indicators for different age groups -daily positivity rate (daily cases to daily tests ratio, black line) and average positivity rate (daily cumulated cases to daily cumulated tests ratio, purple line) over time in left panel; acceleration index (ratio of daily positivity rate to average positivity rate, blue line) over time in right panel, October 16 -November 6, 2020. Dashed horizontal line in right panel represents when acceleration index equals 1. Data source: Agence Santé Publique France (a) Average & Daily positivity rates Curfew 1 Curfew 2 Lockdown

Figure 2 :

 2 Figure 2: Main acceleration indicators for young age groups -daily positivity rate (daily cases to daily tests ratio, black line) and average positivity rate (daily cumulated cases to daily cumulated tests ratio, purple line) over time in left panel; acceleration index (ratio of daily positivity rate to average positivity rate, blue line) over time in right panel, October 16 -November 6, 2020. Dashed horizontal line in right panel represents when acceleration index equals 1. Data source: Agence Santé Publique France (a) Average & Daily positivity rates Curfew 1 Curfew 2 Lockdown

Figure 3 :

 3 Figure 3: Acceleration index for French départements for both age groups (weekly averages for the 3 consecutive weeks also shown in Figure 1 and 2). Contours in light (dark) blue depict départements subject to both Curfew 1 and Curfew 2 (Curfew 2 only). Data source: Agence Santé Publique France

Figure 4 :

 4 Figure 4: Acceleration index for French départements in different treatment groups (Lock-down

Hospital data is publicly available via https://geodes.santepubliquefrance.fr/, which gives the number of persons in hospital and intensive care by age group on a daily basis, as well as mortality rates for all age groups. On November 11,

31,477 are in hospital with COVID-19 and 84.6% of them are 60 years and older. Covid related deaths are also concentrated in the older age group: 93.8% of the deceased where 60 years old or older on November 10.

Hospital data at https://geodes.santepubliquefrance.fr/ show that by November 11, 106 children aged 0-9 were in hospital which represents 0.3% of all hospitalised people. That same day, 71 teenagers were in hospital, which represented 0.2% of all hospitalised people.

The authors thank Frédéric Aprahamian and Michaël Schwarzinger for useful comments on this paper. This work was supported by French National Research Agency Grants ANR-17-EURE-0020.