Hervé Cardot
email: herve.cardot@u-bourgogne.fr

Peggy Cénac
email: peggy.cenac@u-bourgogne.fr

Pierre-André Zitt
email: pierre-andre.zitt@u-bourgogne.fr

Recursive estimation of the conditional geometric median in Hilbert spaces

Keywords: asymptotic normality, averaging, CLT, kernel regression, Mallows-Wasserstein distance, online data, Robbins-Monro, robust estimator, sequential estimation, Stochastic gradient

A recursive estimator of the conditional geometric median in Hilbert spaces is studied. It is based on a stochastic gradient algorithm whose aim is to minimize a weighted L 1 criterion and is consequently well adapted for robust online estimation. The weights are controlled by a kernel function and an associated bandwidth. Almost sure convergence and L 2 rates of convergence are proved under general conditions on the conditional distribution as well as the sequence of descent steps of the algorithm and the sequence of bandwidths. Asymptotic normality is also proved for the averaged version of the algorithm with an optimal rate of convergence. A simulation study confirms the interest of this new and fast algorithm when the sample sizes are large. Finally, the ability of these recursive algorithms to deal with very high-dimensional data is illustrated on the robust estimation of television audience profiles conditional on the total time spent watching television over a period of 24 hours.

Introduction

It is not unusual nowadays to get large samples of high-dimensional or functional data together with real covariates that are correlated with the functional variable under study. The estimation of how the shape of the functional response may depend on real or functional covariates has been deeply studied in the statistical literature : linear models for functional response have been proposed by [START_REF] Faraway | Regression analysis for a functional response[END_REF], [START_REF] Cuevas | Linear functional regression : the case of fixed design and functional response[END_REF] or [START_REF] Bosq | Linear processes in function spaces[END_REF] (see also [START_REF] Ramsay | Functional Data Analysis[END_REF]) and [START_REF] Greven | Longitudinal functional principal component analysis[END_REF] whereas nonlinear relationships are studied in [START_REF] Lecoutre | Uniform consistency of a class of regression function estimators for Banach-space valued variables[END_REF], [START_REF] Chiou | Functional response models[END_REF], [START_REF] Lian | Nonlinear functional models for functional response in reproducing kernel Hilbert spaces[END_REF], [START_REF] Cardot | Conditional functional principal components analysis[END_REF], [START_REF] Lian | Convergence of functional k-nearest neighbor regression estimate with functional responses[END_REF] and [START_REF] Ferraty | Kernel regression with functional response[END_REF].

The main drawback of all the above mentioned estimators, whose target is the conditional expectation, is that they all rely, explicitly or not, on least squares and are consequently sensitive to outliers. In such a context of large samples of high dimensional data, outlying observations, which may not be uncommon, might be hard to detect with automatic procedures. Directly considering robust indicators of centrality such as medians is a way to deal with this issue. If Y be a random variable taking values in a Hilbert space H, its geometric median m (also called spatial median or L 1 -median, see [START_REF] Small | A survey of multidimensional medians[END_REF] for a survey) is defined as follows

m := argmin α∈H E [ Y -α -Y ] .
(1)

The median m is uniquely defined under simple conditions when the dimension of H is larger than or equal to 2, it has a 0.5 breakdown point [START_REF] Kemperman | The median of a finite measure on a Banach space[END_REF]) as well as a bounded gross sensitivity error [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]. When one has a sample at hand, algorithms based on the minimization of the empirical version of risk (1) have been proposed by [START_REF] Vardi | The multivariate L 1 -median and associated data depth[END_REF] and properties of such robust estimators can be found in the recent review by [START_REF] Möttönen | Asymptotic theory of the spatial median. In Nonparametrics and Robustness in Modern Statistical Inference and Time Series Analysis: A Festschrift in honor of Professor Jana Jurecková[END_REF]. Nevertheless, these computational techniques may not be able to handle very large samples of high-dimensional data since they require to store all the data. An alternative approach, developed by [START_REF] Chaouch | Using complex surveys to estimate the L 1 -median of a functional variable: application to electricity load curves[END_REF] and which can cope with this issue, consists in considering unequal probability sampling techniques in order to select, in a effective way, subsamples with sizes much smaller than the initial sample size.

We suggest in this work another direction based on recursive techniques which do not require to store all the data. Another interest of these recursive approaches is that they allow automatic update of the estimators if, for example, the data arrive sequentially. Recently, a simple recursive algorithm which gives efficient estimates of the geometric median in separable Hilbert spaces has been proposed by [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]. It is shown that averaged versions of classic stochastic gradient algorithms have a limiting normal distribution that is the same as the distribution of the static estimator based on a direct minimization of the empirical version of risk (1).

In a finite dimension context, [START_REF] Cadre | Asymptotic normality of consistent estimate of the condition L 1 -median[END_REF] and [START_REF] Cheng | On the uth geometric conditional quantile[END_REF] proposed to introduce a kernel function K in the empirical version of (1) in order to take covariate effects into account. The kernel weights are controlled by a sequence of bandwidth values that tends to zero when the sample size increases in order to build consistent estimates of the conditional geometric median. With the same ideas of local approximation of the conditional distribution, we study, in this work, a modification of the recursive algorithm suggested in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]. It consists in introducing weights, controlled by a kernel function, in order to build consistent recursive estimators of the conditional geometric median. The response variable is also allowed to take values in a separable Hilbert space. For real response, recursive estimators of the regression function based on kernel weights have been introduced by [START_REF] Révész | How to apply the method of stochastic approximation in the nonparametric estimation of a regression function[END_REF] whereas a deep study of their asymptotic properties, which also includes averaged estimation procedures, is proposed in [START_REF] Mokkadem | Revisiting Révész stochastic approximation method for the estimation of a regression function[END_REF].

The paper is organized as follows. In Section 2, we first define the stochastic gradient recursive estimator as well as its averaged version for the case of a real covariate. Note that our results could be extended to multidimensional covariates. We state the asymptotic normality, under general conditions, of the averaged algorithm in separable Hilbert spaces, with an optimal rate of convergence. The regularity hypotheses, which are much weaker than those of [START_REF] Cadre | Asymptotic normality of consistent estimate of the condition L 1 -median[END_REF], are also expressed in terms of the Wasserstein distance between the conditional distributions.

In Section 3, a comparison of the static approach, which consists in minimizing the empirical version of risk (1), with the stochastic gradient estimator and its averaged version is performed on a simulation study. It confirms the good behavior as well as the stability, with respect to the descent steps, of the averaged algorithm. The ability of this estimator to deal with large samples of very high-dimensional data is then illustrated on the estimation of television audience profiles given the total time spent watching television. Proofs are gathered in Section 4.

Notations, hypotheses and main results

Let (Y, X) be a pair of random variables taking values in H × R, where H is a Hilbert space whose norm is denoted by • . Suppose that X is continuous, and denote by p(x) its density at x ∈ R. For any x in the support of X, denote by µ x the conditional law of Y given X = x. Consider, for (α, x) ∈ H × R, the following functional

G(α, x) := p(x) E [ Y -α -Y |X = x] .
(2)

The geometric median of Y given X = x, denoted by m(x), is defined as the solution of the following optimization problem:

m(x) := argmin α∈H G(α, x).
(3)

The solution of ( 3) is unique provided that the conditional distribution µ x is not supported by a straight line [START_REF] Kemperman | The median of a finite measure on a Banach space[END_REF]). We suppose from now on the following assumption.

A1.

For every x in the support of the probability density function p of the random variable X, µ x is not concentrated on a straight line: for all v ∈ H, there is w ∈ H such that v, w = 0 and

Var( w, Y |X = x) > 0. ( 4
)
Suppose we have a sequence (X n , Y n ) n≥1 of independent copies of (X, Y). In the unconditional case where the X variable is not taken into account, one can look for the unconditional median, i.e. the minimum m defined by (1). Under weak hypotheses, the median is uniquely defined as the zero of the derivative:

-E Y -α Y -α .
We introduced in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF] the following recursive estimator of m:

Z n+1 = Z n + γ n Y n+1 -Z n Y n+1 -Z n , (5)
where γ n was a well-chosen deterministic sequence. In the present case, the law of Y n is not the conditional law µ x , so this idea does not work directly. However, it is natural to see Y n as an approximate sample of µ x if X n happens to be very close to x. Therefore, a simple estimator can be built by introducing weights, through a kernel function K, whose properties will be specified later. We modify (5) as follows to take the weights into account, and define our recursive estimator of m(x):

Z n+1 (x) = Z n (x) + γ n Y n+1 -Z n (x) Y n+1 -Z n (x) 1 h n K X n+1 -x h n (6)
with two deterministic sequences of tuning parameters h n and γ n whose properties are given below.

For a constant sequence (h n ), this algorithm converges towards the minimum of the modified objective function:

G h (α, x) := E ( Y -α -Y ) 1 h K X -x h . ( 7
)
The partial derivative of G h with respect to α is an element of H defined by

Φ h (α) := ∇ α G h (α, x) = -E Y -α Y -α 1 h K X -x h . ( 8
)
We will see in Proposition 4.1 that, under suitable hypotheses, when h goes to zero, Φ h goes to the gradient Φ of G, defined by:

Φ(x, α) = -p(x)E Y -α Y -α X = x . ( 9
)
The idea of using a kernel, and of assigning a large weight to Y n when X n is close to x can only work if the conditional law µ x varies, in some sense, regularly. A natural way of expressing this regularity is through the Mallows-Wasserstein distance. Let us recall its definition.

Definition 1. Let µ and ν be two probability measures on H with finite second order moments. Let C be the set of couplings of µ and ν, i.e. the set of measures π on H × H whose first marginal is µ and whose second marginal is ν.

The Wasserstein distance between µ and ν is given by:

W 2 (µ, ν) = inf π∈C x -y 2 dπ(x, y) 1/2 .
We may now state our assumptions.

A2. The probability density function p of the random variable X is bounded and satisfies a uniform Hölder condition : there are two constants β > 0 and C 2 > 0 such that

∀(x, x ) ∈ R 2 , |p(x) -p(x )| ≤ C 2 |x -x | β .
We denote by p max = sup x∈R p(x).

A3. The gradient Φ(x, α) defined by (9) satisfies a uniform Hölder condition with coefficient β. There is

C 3 > 0 such that ∀(x, x ) ∈ R 2 , ∀α ∈ H, Φ(α, x) -Φ(α, x ) ≤ C 3 |x -x | β . ( 10
)
A4. The conditional law µ x = L(Y|X = x) varies regularly with x: there are two constants C 4 and

β such that W 2 (µ x , µ x ) ≤ C 4 x -x β . ( 11
)
A5. The kernel function K is positive, bounded with compact support and satisfies R K(u)du = 1.

A6.

There is a constant C 6 such that:

∀α ∈ H, ∀x, E Y -α -2 |X = x ≤ C 6 . ( 12
)
Remark 1. Without loss of generality, we suppose that the constant β in A2, A3 and A4 has always the same value. Assumption A3 is a regularity assumption that is required to control the approximation error and to prove the convergence of the algorithm. Assumption A4 seems to be more natural, and we prove in section 4.1 that, together with A6, it implies A3.

Hypotheses A2 and A5 are classical in nonparametric estimation and could be weakened at the expense of more complicated proofs. For classical properties of kernel estimators under general hypotheses, see for example [START_REF] Wand | Kernel Smoothing[END_REF].

Similarly, Hypothesis A6 is stated quite strongly here, in order to avoid additional technicalities in the proof of the asymptotic normality if the averaged algorithm. See [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF] for a relaxed version, under which the same results should hold. Informally it forces the law to be "spread out" and this avoids pathological behaviors of the algorithm.

We have three main results. The first one states the almost sure convergence of the algorithm.

Theorem 2.1. Under assumptions A1-A3 and A5, and if

∑ n γ n = ∞, ∑ n γ 2 n h -1 n < ∞ as well as ∑ n γ n h β n < ∞, then, for all x such that p(x) > 0, lim n→∞ Z n (x) -m(x) = 0 a.s.
Remark 2. In the following, for simplicity, we choose the step size and window size as inverse powers of n:

γ n = c γ n γ , h n = c h n h . ( 13
)
With these choices the assumptions on the step sizes are:

γ ≤ 1, 2γ -h > 1, γ + βh > 1. ( 14
)
The assumptions on h and γ are always satisfied if we choose γ = 1 and h < 1. However, as shown in the simulation study, the performances of algorithm (6) strongly depend on the choice of the steps γ n and particularly on the constant c γ . Therefore, we also introduce the following averaged algorithm which is less sensitive to the choice of the step sizes γ n and has nice convergence properties,

Z n+1 (x) = 1 n n ∑ k=1 Z k (x). ( 15
)
Our main result is a central limit theorem on this averaged algorithm. To adapt the proof of the corresponding CLT from [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], we need a good a priori bound on the error Z n (x)m.

Proposition 2.2. Suppose that x is such that p(x) > 0 and that γ ≤ 1, 2γh > 1, γ + βh > 1, and h(1 + 2β) ≥ γ. Under Assumptions A1-A3 and A5, there exist an increasing sequence of events (Ω N ) N∈N , and constants C N , such that Ω = N∈N Ω N , and

∀N, E 1 Ω N Z n -m(x) 2 ≤ C N ln(n) n γ-h .
This proposition tells us that, up to a logarithmic factor, the optimal rates of convergence in nonparametric estimation can be attained for well chosen values of the parameter γ and h

. If γ = 1 and h = (1 + 2β) -1 , then, Z n -m(x) 2 = O p ln(n) n -2β/(2β+1) . ( 16
)
Finally our main result is the following central limit theorem for the averaged algorithm.

Theorem 2.3. Assume A1, A2 and A4-A6. Let x satisfy p(x) > 0.

If γ < 1, 2γ -h > 1, γ + βh > 1 and h > (2β + 1) -1 , then: n ∑ n k=1 1 h k Z n -m(x) L ---→ n→∞ N 0, Γ -1 ΣΓ -1 ,
where

Σ = p(x) K 2 (u)du E (Y -m(x)) ⊗ (Y -m(x)) Y -m(x) 2 X = x , (17)
Γ = E 1 Y -m(x) I H - (Y -m(x)) ⊗ (Y -m(x)) Y -m(x) 2 X = x . ( 18
)
As shown in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF] in the unconditional framework, the operator Γ has a bounded inverse under assumption A1, so that the asymptotic variance operator is well defined. Let us also remark that with our assumptions on the sequence of bandwidths, we have

n ∑ k=1 1 h k = n h n . 1 1 + h + o nh -1 n . (19)
Consequently, the rate of convergence in the CLT is of order √ nh n , which is the usual rate of convergence in distribution for nonparametric regression, provided that the bias term is negligible compared to the variance. This latter condition is ensured by the additional condition h < (2β + 1) -1 and we have, with Theorem 2.3,

nh n Z n -m(x) L ---→ n→∞ N 0, 1 1 + h Γ -1 ΣΓ -1 .
As in the real regression case (see [START_REF] Mokkadem | Revisiting Révész stochastic approximation method for the estimation of a regression function[END_REF]) it turns out that the averaged estimator has a smaller asymptotic variance, with in our case a factor (1 + h) -1 , than the classical kernel estimator which minimizes the empirical version of risk (7).

Remark 3. Proceeding exactly as in the proof of Theorem 2.3, it is possible to establish a CLT for another weighted version of the algorithm

Z n = 1 n ∑ n k=1 √ h k (Z k -m), which is the empirical mean of √ h n (Z n -m).
Under the same assumptions of Theorem 2.3, one has:

√ n Z n L ---→ n→∞ N 0, Γ -1 ΣΓ -1 .

Examples

We first consider a simple simulated example in order to compare the performances of the averaged algorithm with the more classic static one as well as the recursive Robbins-Monro estimator without averaging. Then, the ability of our recursive averaged estimator to deal with large samples of very high-dimensional data is illustrated on the robust estimation of television audience profiles, measured at a minute scale over a period of 24 hours, given the total time spent watching television. All functions are coded in (R Development Core Team ( 2010)) and are available on request to the authors.

γ h h ( 1 + 2 β ) ≥ γ 1/3 h(1 + 2β) ≥ 1 1 γ + β h > 1 1 2 γ -h > 1 2/3 β = 1 γ h h ( 1 + 2 β ) ≥ γ 1/2 h(1 + 2β) ≥ 1 γ + β h > 1 1 2 γ -h > 1 1 3/4 β = 1/2
In this picture we represent the possible choices for the parameters h and γ, when β varies. On the left is the most regular case where β = 1, on the right we set β = 1/2. In both cases, if (γ, h) lies in the lighter region, Theorem 2.1 holds and the algorithm converges. In the middle region, the algorithm converges and the additional convergence estimate of Proposition 2.2 holds. Finally, if (γ, h) is in the darker region, the CLT of Theorem 2.3 holds. All these two regions get smaller when β is small. Note that even in the most regular case β = 1, in order to fulfill the hypotheses of Theorem 2.3, it is necessary to choose γ larger than 2/3 and h larger than 1/3.

A simulated example

Consider a Brownian motion Y measured at d equispaced time points in the interval [0, 1], so that we have Y = (Y(t 1 ), . . . , Y(t d )). Besides, suppose that we know the mean value X = 1 0 Y(t)dt of each trajectory Y. We can look for the conditional (geometric) median of vector Y given X. The joint distribution of (Y, X) is clearly Gaussian with EY = 0, EX = 0,

Cov(Y(t j ), Y(t )) = min(t j , t ), Var(X) = 1 3 and Cov(X, Y(t j )) = t j 1 - t j 2 .
Consequently, the distribution of Y given X = x is Gaussian with conditional expectation, for j = 1, . . . , p,

E Y(t j ) X = x = 3 2 t j (2 -t j )x,
and a covariance matrix that does not depend on x. By symmetry of the Gaussian distribution, it is also clear that the conditional expectation is equal to the conditional geometric median, when H = R d equipped with the usual Euclidean norm, so that

m(t j , x) = 3 2 t j (2 -t j )x. ( 20
)
The hypotheses on the density p are clearly satisfied since X is a Gaussian random variable. Furthermore, the Wasserstein distance between two Gaussian laws with expectations m 1 and m 2 and the same covariance matrix is simply m 1m 2 , (see e.g. [START_REF] Givens | A class of Wassertstein metrics for probability distributions[END_REF]) so that we can deduce, with (20), that β = 1 in Assumption A4.

We draw n i.i.d. copies of (Y, X) and we focus in this simulation study on the geometric median of Y given x = 0.39, which corresponds to the value of the third quartile of X. Note that our conclusions remain unchanged for other non extreme values of X.

We first compute the static estimator, named "static kernel" in the following. It is based on a direct minimization, with the Weiszfeld's algorithm (see [START_REF] Vardi | The multivariate L 1 -median and associated data depth[END_REF] and [START_REF] Möttönen | Asymptotic theory of the spatial median. In Nonparametrics and Robustness in Modern Statistical Inference and Time Series Analysis: A Festschrift in honor of Professor Jana Jurecková[END_REF]), of

α → n ∑ i=1 w i Y i -α , ( 21
)
where

w i = ∑ n =1 K(h -1 n (X -x)) -1 K(h -1 n (X i -x))
and K is the Gaussian kernel. The Robbins Monro estimator Z n , defined in (6), and the averaged estimator Z n , defined in (15), are run for 10 starting points chosen randomly in the sample. Among the 10 estimations, we retain the one with the smallest empirical risk (21).

The accuracy of the different estimators m are compared, for different values of the bandwidth h and sample sizes n, with the quadratic criterion,

R( m) = 1 d d ∑ j=1 m(t j ) -m(t j ) 2 . ( 22
)
Since β = 1, we can choose γ = 9/10 and h = 3/10, c h = 1, so that the quadratic estimation error for the Robbins-Monro algorithm, will be, up to the ln(n) factor, of order n -6/10 (see Proposition 2.2). Note that, for simplicity of comparison with the static kernel estimator, we also consider fixed values for h n ∈ {0.05, 0.10, 0.15, 0.20, 0.25} and take in this case γ = 2/3. We are aware that the assumptions needed for the asymptotic convergence are not satisfied but the sample size is fixed in advance here.

We first present in Table 1 the mean value, over 500 replications, of the MSE defined in (22), when estimating the conditional median with a sample size of n = 500 in dimension d = 100. For comparison and interpretability of the results, note that 100R(0) = 18.4.

We note that, when the sample size is moderate (i.e. n = 500), the interest of considering the averaged recursive estimation procedure is less evident than in the unconditional case (see [START_REF] Cardot | Stochastic approximation to the multivariate and the functional median[END_REF]) since the Robbins-Monro estimator Z n defined in (6) can perform, for well chosen values of the tuning parameters c γ and h n , nearly as well as the static estimator. Nevertheless, we can remark that Z n is highly sensitive to the values of the tuning parameters and its performances deteriorate much with small variations of these parameters as seen in Table 1. This is not the case of the averaged estimator Z n , defined in (15), which is much less sensitive and thus allows less sharp choices of the values of the tuning parameters provided the descent steps do not force the algorithm to converge too rapidly. We note again (see [START_REF] Cardot | Stochastic approximation to the multivariate and the functional median[END_REF]) that for too small values of c γ (i.e. c γ = 0.1), the algorithm converges too quickly and averaging leads to estimations that are outperformed by the direct Robbins-Monro approach. A way to deal with this drawback is to perform averaging only after a certain number of iterations. All these remarks are clearly illustrated in Figure 2 which presents the estimation error, defined in ( 22), for both algorithms and for different values of c γ .

When the sample size gets larger the interest of the averaging step becomes clearer since the estimation error of the Robbins-Monro estimator are always larger as soon as c γ ≥ 1 (see Table 2). Furthermore, the estimation errors of the static kernel estimator and the averaged recursive one are also now very close to each other.

MSE

Robbins Monro Averaging

Television audience data

We have a sample of n = 5422 individual audiences measured every minute over a period of 24 hours and by the Médiamétrie company in France. For j = 1, . . . , 1440, an observation Y i (t j ) represents the proportion of time spent by the individual i watching television during the j th minute of this day. Thus, each vector Y i belongs to [0, 1] 1440 . Note that in fact the first measurement t 1 is made at 3 AM of day d and the last one just before 3 AM of day d + 1 (see Figure 3). A more detailed description of these data can be found in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF].

We are interested in estimating television consumption behaviors, over a 24 hours period, according to the total time spent watching television. The covariate X, is the proportion of time spent watching television over the considered period, X i = (∑ j Y i (t j ))/1440, for i = 1, . . . , n = 5422. We consider the quantile values of X which are, in the sample, q 25 = 0.0599, q 50 = 0.128, q 75 = 0.225 and q 90 = 0.348. This means for example, that the ten percent of consumers with the highest consumption levels spend more than 34.8 % of their time watching television whereas the 25 % of consumers with the lowest consumption levels spend less than 6% of their time watching television.

We have drawn in Figure 3 the estimated conditional median profiles with a bandwidth value set to h n = 0.05 and a descent parameter c γ = 0.5, for x ∈ {q 25 , q 50 , q 75 , q 90 }. For comparison and better interpretation, we have also plotted the overall geometric median as well as the mean profile. One can note that the shape of the conditional profiles strongly depend on the value of the covariate and that multiplicative models that could be thought to be natural (see the simulation study), are in fact not adapted for modeling the conditional audience median profiles. This is clear if we compare, for example, the levels of the conditional median curves for x = q 75 and x = q 90 at time 15 and at time 21. Around 21, their values are approximately the same and are close to the global maximum whereas at time 15 the value of the conditional median for x = q 90 is about twice the value of the conditional median for x = q 75 .

From a computational speed point of view, for one starting point, our algorithm, which takes less than two seconds, is about 70 times faster than the static estimator which requires 140 seconds to converge.

Proofs

Notation. In all the proofs, x will be a fixed point in R satisfying p(x) > 0. Since x will not vary, we will abuse notation and drop it from various quantities. In particular, in the following m will denote the median m(x) of the conditional law µ x , and we will write Z n = Z n (x) and Φ(α) = Φ(x, α).

About the assumptions

We begin by a simple geometric result on unit vectors. For a, b two points in H, let D(a, b) be the unit vector "starting" from a in the direction of b. Now if a, b, c are three points in H, such that ab ≤ ac , Thales' theorem shows that: In any case,

D(a, b) -D(a, c) b -c = a + D(a, b) -a a -b = 1 a -b , so D(a, b) -D(a, c) ≤ b -c a -b ≤ b -c a -b .
D(a, b) -D(a, c) ≤ b -c min( a -b , a -c ) . ( 23
)
We will need a "decoupled" version of this inequality:

D(a, b) -D(a, c) ≤ b -c a -b + b -c a -c . ( 24
)
We can now prove that A4 and A6 imply A3. Let x, x be two real numbers in the support of p. Recall that µ x denotes the law L(Y|X = x). Let Y and Y be two random variables with respective laws µ x and µ x , such that their joint law π achieves the Wasserstein distance. Let us first show that:

∀α ∈ H, E [D(α, Y)] -E D(α, Y ) ≤ C x -x β . ( 25
)
Fix an α ∈ H. We have:

E [D(α, Y)] -E D(α, Y ) ≤ E π D(α, Y) -D(α, Y ) ≤ E π D(α, Y) -D(α, Y ) .
Now we use the geometric bound (24), and Hölder's inequality:

E [D(α, Y)] -E D(α, Y ) ≤ E π Y -Y Y -α + E π Y -Y Y -α ≤   E 1 Y -α 2 + E 1 Y -α 2   E π Y -Y 2 .
The first term is bounded by 2 √ C 6 thanks to A6. The second one is, by definition, the Wasserstein distance, and is bounded by

C 4 |x -x | β thanks to A4, therefore (25) holds. Since p is C 2 with compact support, the product Φ(x, α) = p(x)E [D(α, Y)|X = x] is itself uniformly β-Hölder continuous; in other words A3 holds.

First properties

Recall that, for z ∈ H, Φ h (z) is defined by (8) as the conditional expectation of the step, with window size h. When h goes to zero, this "expected step" converges.

Proposition 4.1. The expected step is bounded:

∃C, ∀h > 0, ∀α ∈ H, Φ h (α) ≤ p max . ( 26
)
Moreover, under hypotheses A2, A3 and A5, there exists a constant C such that:

Φ h (α) -Φ(α) ≤ Ch β , ( 27
)
where Φ(x, α) is defined by (9).

Proof. With our strong hypotheses this result is easy to prove. Indeed

Φ h (α) = 1 h K x -x h Φ(x , α)dx ,
so that by Jensen's inequality

Φ h (α) ≤ p max x 1 h K x -x h dx = p max .
Moreover,

Φ h (α) -Φ(α) ≤ 1 h K x -x h Φ(x , α) -Φ(x, α) dx .
Now we use Assumption A3 to bound the norm by C 3 |x -x| β , the compact support of the bounded function K (Assumption A5) and we integrate:

Φ h (α) -Φ(α) ≤ C 3 1 h K x -x h x -x β dx ≤ C 3 K(t)h β t β dt ≤ Ch β .
Thanks to this result, we have a natural decomposition of algorithm ( 6). Let us introduce the two following quantities:

D h (z) = Φ h (z) -Φ(z), (28)
ξ n+1 = - Y n+1 -Z n Y n+1 -Z n 1 h n K X n+1 -x h n -Φ h n (Z n ) . ( 29
)
In terms of these quantities, we can rewrite (6) as:

Z n+1 = Z n -γ n Φ(Z n ) -γ n D h n (Z n ) -γ n ξ n+1 . ( 30
)
The first term D h n (Z n ) will be controlled by Proposition 4.1. The second term ξ n+1 defines a sequence of martingale differences, since the conditional expectation given the sequence of σ-algebra

F n = σ(Z 1 , . . . , Z n ) = σ(Y 1 , X 1 , . . . , Y n , X n ) satisfies E [ξ n+1 |F n ] = 0, a.s.
For future reference, let us note the following bound on ξ n :

E ξ n+1 2 F n = E Y n+1 -Z n Y n+1 -Z n 1 h n K X n+1 -x h n 2 F n -Φ h n (Z n ) 2 , a.s ≤ 1 h 2 n E K 2 X n+1 -x h n -Φ h n (Z n ) 2 , a.s ≤ C h n , a.s. ( 31
)

Almost sure convergence

In this section we prove Theorem 2.1. Define V n = Z nm 2 . By (30), we have:

V n+1 = V n + γ 2 n Φ(Z n ) 2 + γ 2 n D h n (Z n ) + ξ n+1 2 + 2 Z n -m, γ n Φ(Z n ) + 2γ n Z n -m, D h n (Z n ) + ξ n+1 + 2γ 2 n Φ(Z n ), D h n (Z n ) + ξ n+1 .
The first scalar product is non positive, we denote it by (-η n ). We condition by F n : the ξ n+1 in the scalar products disappear by the martingale property. Then we use Hölder's inequality:

E [V n+1 |F n ] ≤ V n + γ 2 n Φ(Z n ) 2 + 2γ 2 n D h n (Z n ) 2 + 2γ 2 n E ξ n+1 2 F n -η n + 2γ n Z n -m D h n (Z n ) + 2γ 2 n Φ(Z n ) D h n (Z n ) .
On the last term we use 2xy ≤ x 2 + y 2 to get:

E [V n+1 |F n ] ≤ V n + 2γ 2 n Φ(Z n ) 2 + 3γ 2 n D h n (Z n ) 2 + 2γ 2 n E ξ n+1 2 F n -η n + 2γ n Z n -m D h n (Z n ) .
On the last term we bound Z nm by (1 + V n ) to get:

E [V n+1 |F n ] ≤ (1 + 2γ n D h n (Z n ) ) V n + 2γ 2 n Φ(Z n ) 2 + 3γ 2 n D h n (Z n ) 2 + 2γ 2 n E ξ n+1 2 F n + 2γ n D h n (Z n ) -η n .
Finally we bound D h n (Z n ) by Ch and Φ(Z n ) by p(x). This yields:

E [V n+1 |F n ] ≤ 1 + 2Cγ n h β n V n + 2p(x)γ 2 n + 3C 2 γ 2 n h 2β n + 2C γ 2 n h n + 2Cγ n h β n -η n ≤ (1 + b n )V n + χ n -η n , where b n = 2Cγ n h β n and χ n = 3C 2 γ 2 n h 2β n + 2Cγ 2 n h -1 n + 2Cγ n h β n satisfy: ∑ b n < ∞, ∑ χ n < ∞.
Therefore by the Robbins-Siegmund Lemma (Theorem 1.3.12 of [START_REF] Duflo | of Applications of Mathematics[END_REF]), V n converges almost surely and ∑ n η n < ∞. This implies that the limit of V n is zero, by the same argument than in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], assuming that ∑ n γ n = ∞.

Proof of proposition 2.2

For the sake of clarity, we follow the same steps as the proof of Proposition 3.2 in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], and emphasize the necessary changes.

Step 1 -a spectral decomposition. This step is exactly the same as in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]: thanks to a spectral decomposition of Γ, we can define the operators:

α k = I H -γ k Γ, β n = α n α n-1 • • • α 1 .
Introducing the sequence of real functions, for n ∈ N,

f n (x) = n ∏ k=1 (1 -γ k x),
we see that each operator β n can be also expressed as follows:

β n x = ∑ λ∈Λ f n (λ) e λ , x e λ , x ∈ H,
their inverses are bounded operators, and satisfy:

β -1 n x = ∑ λ∈Λ f -1 n (λ) e λ ,
x e λ . Moreover there exist constants κ 1 , κ 2 , κ 3 such that:

∀x ∈ σ(Γ), κ 1 exp (-s n x) ≤ f n (x) ≤ κ 2 exp (-s n x) , s n - c γ 1 -γ n 1-γ ≤ κ 3 , (32)
where we recall that s n = ∑ n k=1 γ k , and

γ k = c γ k -γ .
Step 2 -Decomposition of the algorithm. Recall the decomposition (30) , and rewrite the algorithm as follows:

Z n+1 = Z n -γ n ξ n+1 -γ n Φ(Z n ) -γ n D h n (Z n ) = Z n -γ n ξ n+1 -γ n (Γ(Z n -m) + δ n ) -γ n D h n (Z n ) ( 33
)
where

δ n = Φ(Z n ) -Γ(Z n -m)
is the difference between the gradient of G and the gradient of its quadratic approximation. Compared to [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], there are two differences: the martingale difference ξ n has changed, and there is an additional term

γ n D h n (Z n ). There- fore: ∀k, Z k+1 -m = α k (Z k -m) -γ k ξ k+1 -γ k δ k -γ k D h k (Z k ). ( 34
) Rewriting α n-1 α n-2 • • • α k+1 as β n-1 β -1 k , we get by induction, Z n -m = β n-1 (Z 1 -m) + β n-1 M n -β n-1 R n-1 -β n-1 R n-1 , (35)
where

R n = n-1 ∑ k=1 γ k β -1 k δ k M n = - n-1 ∑ k=1 γ k β -1 k ξ k+1 R n = n-1 ∑ k=1 γ k β -1 k D h k (Z k ).
At this point, the first and third term are the same as in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], the martingale has changed and there is an additional remainder term R n .

Step 3 -The deterministic term. Just as in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], we get:

E β n-1 (Z 1 -m) 2 ≤ C exp -2n 1-γ E Z 1 -m 2 . ( 36
)
Step 4 -The martingale. Still following [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], we use the spectral decomposition to deal with the martingale part. The changes appear just before eq. ( 41) in that paper, where the bound on E[ ξ k 2 ] has to be changed (from 1 to C/h n , using the new bound ( 31)). Then we use the bounds (32) to get:

E β n-1 M n 2 ≤ C ∑ k≤n-1 γ 2 k h k f n-1 (λ min ) f k (λ min ) 2 ≤ C ∑ k≤n-1 γ 2 k h k exp - 1 1 -γ n 1-γ -k 1-γ . ( 37
)
Once more, the first terms in the sum are negligible (thanks to the exponential), and we isolate the last terms, for k ≥ l(n), where l(n) is given by

l(n) 1-γ = n 1-γ -c α ln(n) , (38)
for some constant c α . Choosing c α large enough, the arguments from [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF] ensure that the main contribution comes from the last terms. The number of terms, that is nl(n), is of the order ln(n)n γ , and

γ 2 l(n) /h l(n) is equivalent to cn h-2γ . Therefore E β n-1 M n 2 ≤ C ln(n) n γ-h . ( 39
)
Step 5 -the error terms.

The first error term is

R n = β n-1 ∑ n k=1 γ k β -1 k δ k , where δ k = Φ(Z k ) -Γ(Z k -m)
. This one can be treated exactly as in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]. We recall the definition of the event Ω N :

Ω N =    ω, ∀n ≥ N, ∀k ≥ n -l(n), Z k (ω) -m ≤ 1/K and δ k (ω) ≤ C r Z k (ω) -m 2 ∀k, δ k (ω) ≤ N.    ,
for a value of K to be chosen later, and l(n) defined by (38). Then, for any power of n (say n -42 ) there is a C such that, on Ω N and for n ≥ N,

β n-1 R n 2 ≤ CN 2 n 42 + C K 2 n ∑ k=l(n)+1 γ k Z k -m 2 . ( 40
)
We now turn to the bound of the new error term

R n = β n-1 ∑ n-1 k=1 γ k β -1 k D h k (Z k ). To bound D h , we use (27): D h (z) ≤ Ch β .
Therefore for N large enough, and for k ≥ l(n),

1 Ω N D h k (Z k ) ≤ Ch β k .
For k smaller than l(n), we use the crude bound D h k (Z k ) ≤ p max + 1. Finally we get:

1 Ω N R n ≤ C n 42 + (n -l(n))γ l(n) h β l(n) .
The last term is bounded by Cn -βh and dominates the first term. Finally, since by assumption, h(1 + 2β) ≥ γ, one gets

1 Ω N R n 2 ≤ C n γ-h . ( 41
)
Now we use ( 36), ( 39), ( 40) and ( 41) to bound the four terms that appear in (35). We get, for n ≥ N and some new constant C:

E 1 Ω N Z n -m 2 ≤ C ln(n) n γ-h + C K 2 sup l(n)<k≤n E 1 Ω N Z k -m 2 .
By the same induction than in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF], we obtain the bound announced in Proposition 2.2.

Proof of Theorem 2.3

The following proof follows the same guidelines as the proof of Theorem 3.4 in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF]. Again we emphasize the necessary changes due to the introduction of the kernel and of the conditional distribution. We first linearize the target function around the conditional median m as in (33):

∀n, Z n+1 -m = (I H -γ n Γ)(Z n -m) -γ n ξ n+1 -γ n δ n -γ n D h n (Z n ),
where (ξ n ) is a martingale difference sequence. Therefore, for all k,

Γ(Z k -m) = γ -1 k ((Z k -m) -(Z k+1 -m)) -ξ k+1 -δ k -D h k (Z k ). (42)
Define now,

T n := Z n -m, T n := Z n -m and M n+1 := n ∑ k=1 ξ k+1 ,
and sum (42) over k

nΓT n = n ∑ k=1 1 γ k (T k -T k+1 ) - n ∑ k=1 δ k + D h k (Z k ) -M n+1 , so that n ∑ n k=1 1 h k ΓT n = n ∑ n k=1 1 h k T 1 √ h 1 γ 1 -A n + A n -A n + n ∑ n k=1 1 h k M n+1 , (43)
where

A n := T n+1 γ n , A n := n ∑ k=2 T k 1 γ k - 1 γ k+1 , A n := n ∑ k=1 δ k + D h k (Z k ) .
Step Zero -convergence of covariance operators Our first task is to establish a central limit theorem for the last term of (43): n

∑ n k=1 1 h k M n L ---→ n→∞ N (0, Σ) , ( 44
)
where Σ is the limiting covariance defined by ( 17). On the space of linear operators on H we consider two classical norms, the (strong) operator norm and the Hilbert-Schmidt norm:

A op = sup { Ay H ; y ≤ 1} , A H.S. = ∞ ∑ i=0 Ae j , e j 2 1/2
, where e j is an orthonormal base of H. The following lemma will be useful.

Lemma 4.2. Define a random covariance operator Σ n by:

Σ n = h n E [ξ n+1 ⊗ ξ n+1 |F n ] . (45)
Then:

√ Σ n H.-S. ---→ n→∞ √ Σ, a.s. ( 46
)
In particular, Σ n converges to Σ a.s. in the operator norm. Moreover, if Σ n denotes the following averaged version of Σ n :

Σ n = 1 ∑ n k=1 1 h k n ∑ k=1 1 h k Σ k = 1 ∑ n k=1 1 h k n ∑ k=1 E [ξ k+1 ⊗ ξ k+1 |F k ] , then Σ n H.-S. ---→ n→∞ √ Σ, a.s. (47)
Finally, for any orthogonal projection operator P,

E Tr ΣP ---→ n→∞ E [Tr (ΣP)] . ( 48
)
Remark 4. Let us note that the convergence of square roots of covariance operators is equivalent to the convergence of the centered Gaussian laws with these covariances; see e.g. [START_REF] Bogachev | Gaussian measures[END_REF], Example 3.8.13.

Proof. We first show that the convergence (46) holds in operator norm. Recall that D(x, y) denotes the unit vector (yx)/ yx . Let us rewrite Σ n .

Σ n = 1 h n E K 2 X n+1 -x h n D(Z n , Y n+1 ) ⊗ D(Z n , Y n+1 ) F n -h n Φ h n (Z n ) ⊗ Φ h n (Z n ).
Denote by (X, Y) a couple of random variables with the original joint law, and Y x be a random variable with law µ x , independent from (X, Y).

We decompose the difference

Σ n -Σ = D 1 + D 2 + D 3 + D 4
where

D 1 = 1 h n E K 2 X n+1 -x h n D(Z n , Y n+1 ) ⊗ D(Z n , Y n+1 ) F n - 1 h n E K 2 X -x h n D(m, Y) ⊗ D(m, Y) D 2 = 1 h n E K 2 X -x h n D(m, Y) ⊗ D(m, Y) - 1 h n E K 2 X -x h n D(m, Y x ) ⊗ D(m, Y x ) D 3 = 1 h n E K 2 X -x h n D(m, Y x ) ⊗ D(m, Y x ) -Σ D 4 = -h n Φ h n (Z n ) ⊗ Φ h n (Z n ).
Note that only the first and the last terms are random; the others depend on n only through the quantity h n . For (a, b, c) ∈ H 3 , it is easy to see that:

D(a, b) ⊗ D(a, b) -D(a, c) ⊗ D(a, c) op ≤ ( D(a, b) + D(a, c) ) D(a, b) -D(a, c) ≤ 2 1 a -b + 1 a -c b -c ,
where we used (24) in the last line. Therefore:

D 1 op ≤ 2 h n E K 2 X -x h n 1 Y -m + 1 Y -Z n Z n -m .
Conditioning on X and using Assumption A6, we get:

D 1 op ≤ 4 C 6 1 h n E K 2 ((X -x)/h n ) Z n -m .
The boundedness of p and the finiteness of

v 2 = K 2 (u)du ensure 1 h n E K 2 ((X -x)/h n ) ---→ n→∞ p(x)v 2 , ( 49
)
by dominated convergence; therefore the sequence (h

n ) -1 E K 2 ((X -x)/h n ) is bounded.
Since Z n converges a.s. to m, D 1 op converges a.s. to zero.

The second term D 2 is treated similarly; we get:

D 2 op ≤ 2 h n E K 2 X -x h n 1 Y -m + 1 Y x -m Y -Y x .
Recall that µ x = L(Y|X = x) and let µ x,x be a coupling of µ x and µ x that achieves the Wasserstein distance. We condition on the value of X and we apply Hölder's inequality in order to bound the first integral with Assumption A6 and the second one with Assumption A4:

D 2 op ≤ 2 h n E   K 2 X -x h n 1 y -m 2 dµ X (y) 1/2 y -y 2 dµ x,X (y, y ) 1/2   + 2 h n E   K 2 X -x h n 1 y -m 2 µ x (dy) 1/2 y -y 2 dµ x,X (y, y ) 1/2   ≤ 4 √ C 6 h n E K 2 X -x h n W 2 (µ X , µ x ) ≤ 4C 4 √ C 6 h n E K 2 X -x h n |X -x| β = 4C 4 C 6 h β n K 2 (y) |y| β dy = O(h β n ) ---→ n→∞ 0.
In the third term D 3 , since Y x is independent of X we may write

D 3 = 1 h n E K 2 ((X -x)/h n ) -p(x)v 2 Σ.
Thanks to (49), this converges to zero. Finally, by Proposition 4.1, Φ h n (Z n ) is almost surely bounded, and since a ⊗ b op ≤ a b ,

h n Φ h n (Z n ) ⊗ Φ h n (Z n ) op ≤ h n Φ h n (Z n ) 2 ---→ n→∞ 0, a.s.
Therefore, Σ n converges to Σ in the operator norm.

To prove the convergence of Σ n in operator norm, observe that

Σ n -Σ op ≤ 1 ∑ 1 h k ∑ 1 h k Σ k -Σ op .
Since Σ k -Σ op converges to zero, the conclusion follows by the Toeplitz lemma.

Let us show that these convergences hold in the Hilbert-Schmidt norm. For any a, Tr(a ⊗ a) = a . Therefore:

√ Σ n 2 H.S. = Tr(Σ n ) = 1 h n E K 2 ((X -x)/h n ) -h n Φ h n (Z n ) 2 ---→ n→∞ p(x)v 2 = Tr(Σ) = √ Σ 2 H.S.
. Another application of the Toeplitz lemma shows that

Σ n 2 H.S. = Tr(Σ n ) = 1 ∑ n k=1 1 h k n ∑ k=1 Tr 1 h k Σ k ---→ n→∞ Tr(Σ) = √ Σ 2 H.S.
. By the same reasoning as in Example 3.8.15 of [START_REF] Bogachev | Gaussian measures[END_REF], this implies the H.-S. convergences ( 46) and (47). Finally, let P be an orthogonal projection operator. Choose a basis (e i ) i∈N of orthonormal eigenvectors of P: Pe i = 0 or Pe i = e i . Since Σ n is trace-class, so is Σ n P and:

Tr Σ n P = ∑ i e i , Σ n Pe i = ∑ i Pe i , Σ n Pe i = ∑ i Σ n Pe i , Σ n Pe i = ∑ i Σ n Pe i 2 = Σ n P 2 H.S. ---→ n→∞ ΣP 2 H.S. = Tr(ΣP).
This convergence is almost sure. Since Tr(Σ k ) ≤ 1 h k E K 2 ((Xx)/h k ) ≤ C, the convergence also holds in L 1 by dominated convergence, and (48) holds.

Step 1 -The CLT for the martingale. To prove the CLT (44), let us check that the assumptions of Theorem 5.1 in [START_REF] Jakubowski | Tightness criteria for random measures with application to the principle of conditioning in Hilbert spaces[END_REF] are fulfilled. Reminding (19), translated in our context, these assumptions are:

∀η > 0 lim n→∞ P sup 1≤k≤n h n n ξ k+1 > η = 0, (50) a
.s. lim n→∞ 1 ∑ n k=1 1 h k n ∑ k=1 ξ k+1 , e i ξ k+1 , e j = ψ i,j , (51)
∀ε > 0 lim

N→∞ lim sup n→∞ P h n n n ∑ i=1 ∞ ∑ j=N ξ i+1 , e j 2 > ε = 0, (52)
where (e n ) n∈N is an orthonormal basis of H and ψ i,j := Σe i , e j . We deal with condition (50) by applying Markov's inequality. Let η > 0.

P

p) n p/2-h(p/2-1)-1 . Since p > 2, one has p/2h(p/2 -1) -1 > 0 and thus (50) holds.

Condition (51) is a consequence of the law of large numbers for martingales. Let us consider (e n ) n∈N an orthonormal basis of H. From the decomposition ξ n+1 , e i ξ n+1 , e j = E ξ n+1 , e i ξ n+1 , e j F n + ε n+1 , with ε n+1 := ξ n+1 , e i ξ n+1 , e j -E ξ n+1 , e i ξ n+1 , e j F n , we have

1 ∑ n k=1 1 h k n ∑ k=1 ξ k+1 , e i ξ k+1 , e j = 1 ∑ n k=1 1 h k n ∑ k=1 E ξ k+1 , e i ξ k+1 , e j |F k + 1 ∑ n k=1 1 h k n ∑ k=1 ε k+1 = e i , Σ n e j + 1 ∑ n k=1 1 h k n ∑ k=1 ε k+1 .
By Lemma 4.2, the matrix element e i , Σ n e j converges to ψ i,j . The law of large numbers for the martingale (∑ n k=1 ε k+1 ) n∈N whose increasing process is of order Step 2 -The remaining terms are negligible. Now, it remains to prove that all the other terms in (43) converge in probability to zero. Due to the equivalence (19), we have to prove the convergence in probability to zero of

h n n T 1 √ h 1 γ 1 -A n + A n -A n .
Recall that E 1 Ω N T n 2 ≤ C N

ln(n)

n γ h n , thanks to Proposition 2.2. For the first term A n = T n+1 γ n , we have: The end of the proof follows the same guidelines as in [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF].

E 1 Ω N h n n A n 2 ≤ C N ln(n) n 1-γ ,

Figure 1 :

 1 Figure 1: Possible choices for h and γ.

Figure 2 :

 2 Figure 2: Comparison of the two recursive algorithms according to the mean square error of estimation for different values of c γ (with a logarithmic scale). The sample size is n = 500 and d = 100.

Figure 3 :

 3 Figure 3: Estimation of the conditional median profile for different levels of total time spent watching television, on the 6th September 2010.

βn

  thanks to (27), E ξ n+1 2 F n by C/h n thanks to (31)

Table 1 :

 1 Mean estimation errors (× 100) of the different estimators, for n = 500, d = 100, and descent parameter γ = 2/3 when h n has a constant value and γ = 0.9 when h n = n -h with h = γ/3 = 0.3.

				Bandwidth h n
		0.05	0.10	0.15	0.20	0.25 n -0.3
	Static kernel	0.349 0.179 0.148 0.172 0.245
	Robbins Monro
	c γ = 0.1	0.689 0.625 0.659 0.769 0.912 2.458
	c γ = 0.3	0.370 0.194 0.159 0.178 0.253 0.332
	c γ = 1	0.590 0.297 0.229 0.240 0.297 0.183
	c γ = 3	1.177 0.647 0.486 0.425 0.453 0.248
	Averaged
	c γ = 0.1	1.047 1.000 1.051 1.160 1.336 2.995
	c γ = 0.3	0.406 0.213 0.178 0.202 0.287 0.534
	c γ = 1	0.402 0.195 0.160 0.182 0.252 0.192
	c γ = 3	0.443 0.209 0.163 0.252 0.256 0.170

Table 2 :

 2 Mean estimation errors (× 100) of the different estimators, for n = 2000, d = 100, and descent parameter γ = 2/3 when h n has a constant value and γ = 0.9 when h n = n -h with h = γ/3 = 0.3.

				Bandwidth h n
		0.05	0.10	0.15	0.20	0.25 n -0.3
	Static kernel	0.082 0.053 0.060 0.099 0.176
	Robbins Monro
	c γ = 0.1	0.139 0.128 0.149 0.205 0.324 1.321
	c γ = 0.3	0.095 0.061 0.065 0.103 0.181 0.083
	c γ = 1	0.173 0.104 0.098 0.126 0.194 0.061
	c γ = 3	0.403 0.230 0.175 0.192 0.253 0.096
	Averaged
	c γ = 0.1	0.240 0.237 0.270 0.332 0.484 1.712
	c γ = 0.3	0.091 0.058 0.065 0.102 0.183 0.138
	c γ = 1	0.090 0.057 0.063 0.101 0.178 0.060
	c γ = 3	0.097 0.058 0.064 0.101 0.180 0.057

  ≥ 1. We chose an integer p such that p > 2. By convexity of the function x → x p , we have, for any n,+ 2 p-1 E Φ h n (Z n ) p .In the last term, Φ h n (Z n ) is bounded, thanks to (26). Consequently, there exists a constant C(p) (independent of n) such that

	sup 1≤k≤n	h n n	ξ k+1 > η ≤	n ∑ k=1	P	h n n	ξ k+1 > η
							≤	1 η p	n ∑ k=1	E	h n n	p/2	ξ k+1	p ,
	for any p ξ n+1	p ≤ 2 p-1 1 h p n	K p X n+1 -x h n	+ Φ h n (Z n ) p .
	Thus an easy computation yields
	E ξ n+1	p ≤	2 p-1 p max R K p (z)dz p-1 h n
				E ξ n+1	p ≤	C(p) p-1 h n
	P sup 1≤k≤n	h n n	ξ k+1 > η ≤	C(p)h n p/2 η p p/2 n	k=1 n ∑	h	-p+1 k	≤	C

.

Hence we have, for a constant C (p) independent of n,

  It remains to check condition (52). Let ε > 0. Applying Markov's inequality, we have , Σ n e j .Call P N the orthogonal projection on the e i , i ≥ N.

	P	h n n	n ∑ k=1	∞ ∑ j=N	ξ k+1 , e j	2 > ε ≤	h n nε	k=1 n ∑	j=N ∞ ∑	E ξ k+1 , e j	2
											≤	h n nε	∑ 1 h k h k ∑ 1	k=1 n ∑	j=N ∞ ∑	E E ξ k+1 , e j	2 F k
											≤	h n nε	n ∑ k=1	1 h k	E
		P	h n n	n ∑ k=1	∞ ∑ j=N	ξ k+1 , e j	2 > ε ≤	h n nε	n ∑ k=1	1 h k	E Tr(Σ n P N ) .
	Therefore
		lim sup n	P	h n n	n ∑ k=1	∞ ∑ j=N	ξ k+1 , e j	2 > ε ≤	1 (1 + h)ε	E [Tr(ΣP N )] ,
	and (52) follows.
												n 1+3h yields
							lim n→∞	1 k=1 ∑ n	1 h k

n ∑ k=1 ε k+1 = 0 a.s., since h < 1, and condition (51) is satisfied. ∞ ∑ j=N e j

  Finally, for the last termA n = ∑ n k=1 δ k + D h k (Z k ) , since on Ω N , δ k ≤ C r Z km 2 , we have for the part in δ k : C ln(n)n h/2-γ+1/2 ,For the additional term, due to (27), we have E 1 Ω N D h k (Z k ) ≤ Ch

		E 1 Ω N		h n n	n ∑ k=1	δ k	≤ β k so that for some
	positive constant C,
			E 1 Ω N	h n n	A n	≤ Cn 1/2-h/2-hβ .
	therefore h n n .A n	P ---→ n→∞	0. Let us turn to the second term A n = ∑ n k=2 T k	1 γ k -1 γ k+1 . Since
	there exists a constant C such that
					1 γ k	-	1 γ k+1	≤ Ck γ-1 ,
	by applying Jensen's inequality together with Proposition 2.2, there is a positive constant C
	such that
			E	h n n	A n 1 Ω N ≤ C ln(n)n γ/2-1/2 .
	Therefore h n n .A n

P

---→ n→∞ 0 since γ < 1.

Acknowledgements. We thank the company Médiamétrie for allowing us to illustrate our methodologies with their data.