Keywords: Bootstrap, Rééchantillonnage, Plus proches voisins, Vitesse de convergence

Sur la vitesse de convergence de l'estimateur du plus proche voisin baggé Résumé : On s'intéresse à l'estimation de la fonction de régression r(

) que l'estimateur ainsi obtenu est universellement convergent à condition que k n tende vers l'infini et k n /n tende vers 0 lorsque n → ∞. Nous montrons dans ce travail que, mieux encore, la vitesse de convergence de cet estimateur baggé est optimale.

1 Introduction

Bagging

Ensemble methods are popular machine learning algorithms which train multiple learners and combine their predictions. The success of ensemble algorithms on many benchmark data sets has raised considerable interest in understanding why such methods succeed and identifying circumstances in which they can be expected to produce good results. It is now well-known that the generalization ability of an ensemble can be significantly better than that of a single predictor, and ensemble learning has therefore been a hot topic during the past years. For a comprehensive review of the domain, we refer the reader to Dietterich [6] and the references therein.

One of the first and simplest ways to combine predictors in order to improve their performance is bagging (bootstrap aggregating), suggested by Breiman [START_REF] Breiman | Bagging predictors[END_REF]. This ensemble method proceeds by generating bootstrap samples from the original data set, constructing a predictor from each bootstrap sample, and decide by combining. It is one of the most effective computationally intensive procedures to improve on unstable estimators or classifiers, especially for large, high dimensional data set problems where finding a good model or classifier in one step is impossible because of the complexity and scale of the problem. Bagging has attracted much attention and is frequently applied, although its statistical mechanisms are not yet fully understood and are still under active investigation. Recent theoretical contributions to bagging and related methodologies include those of Friedman and Hall [START_REF] Friedman | On bagging and nonlinear estimation[END_REF], Bühlmann and Yu [START_REF] Bühlmann | Analyzing bagging[END_REF], Hall and Samworth [START_REF] Hall | Properties of bagged nearest neighbour classifiers[END_REF], Buja and Stuetzle [START_REF] Buja | Observations on bagging[END_REF], and Biau and Devroye [START_REF] Biau | On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification[END_REF].

It turns out that Breiman's bagging principle has a simple application in the context of nearest neighbor methods. Nearest neighbor predictors are one of the oldest approach to regression and classification, dating back to Fix and Hodges [START_REF] Fix | Discriminatory analysis. Nonparametric discrimination: Consistency properties[END_REF][START_REF] Fix | Discriminatory analysis: small sample performance[END_REF]. A major attraction of nearest neighbor procedures is their simplicity. For implementation, they require only a measure of distance in the sample space, along with samples of training data, hence their popularity as a starting point for refinement, improvement and adaptation to new settings (see for example Devroye, Györfi and Lugosi [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], Chapter 19). Before we formalize the link between bagging and nearest neighbors, some definitions are in order. Throughout the paper, we suppose that we are given a sample D n = {(X 1 , Y 1 ), . . . , (X n , Y n )} of i.i.d. R d × R-valued random variables with the same distribution as a generic pair (X, Y ) satisfying E|Y | < ∞. The space R d is equipped with the standard Euclidean metric. For fixed x ∈ R d , our mission is to estimate the regression function r(x) = E[Y |X = x] using the data D n . With this respect, we say that a regression function estimate r n (x) is consistent if E[r n (X)r(X)] 2 → 0 as n → ∞. It is universally consistent if this property is true for all distributions of (X, Y ) with E[Y 2 ] < ∞.

Bagging and nearest neighbors

Recall that the 1-nearest neighbor (1-NN) regression estimate sets r n (x) = Y (1) (x) where Y (1) (x) is the observation of the feature vector X (1) (x) whose Euclidean distance to x is minimal among all X 1 , . . . , X n . Ties are broken in favor of smallest indices. Contrary to some beliefs, it is clearly not, in general, a consistent estimate (Devroye, Gÿorfi and Lugosi [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF], Chapter 5). However, by bagging, one may turn the 1-NN estimate into a consistent one, provided that the size of the bootstrap sample is sufficiently small. We proceed as follows, via a randomized basic regression estimate r kn in which 1 ≤ k n ≤ n is a parameter. The elementary predictor r kn is the 1-NN rule for a random subsample S n drawn with (or without) replacement from {X 1 , . . . , X n }, with Card(S n ) = k n . We apply bagging, that is, we repeat the random sampling an infinite number of times, and take the average of the individual outcomes. Thus, theoretically, the bagged regression estimate r ⋆ n is defined by

r ⋆ n (x) = E ⋆ [r kn (x)]
, where E ⋆ denotes expectation with respect to the resampling distribution, conditionally on the data set D n . In practice, the resampling distribution is implemented by Monte-Carlo: we repeat the random sampling m times, and take the average of the individual outcomes. Formally, if Z t = r kn (x) is the prediction in the t-th round of bagging, we let the bagged regression estimate be approximately

r ⋆ n (x) ≈ 1 T T t=1 Z t ,
where Z 1 , . . . , Z T are the outcomes in the individual rounds. However, for definiteness, we shall always treat in this paper the version of the bagged nearest neighbor predictor which uses an infinite number of simulations in the aggregation step.

The next result, proved in [START_REF] Biau | On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification[END_REF], shows that for an appropriate choice of k n , the bagged version of the 1-NN regression estimate is universally consistent:

Theorem 1.1. If k n → ∞ and k n /n → 0, then r ⋆ n is universally consistent.
In this theorem, the fact that resampling is done with or without replacement is irrelevant. Thus, by bagging, one may turn the crude 1-NN procedure into a consistent one, provided the size of the resamples is sufficiently small. To understand the statistical forces driving Theorem 1.1, recall that if we let V 1 ≥ V 2 ≥ . . . ≥ V n ≥ 0 denote weights (depending on n) that sum to one, and

V 1 → 0, i>εn V i → 0 for all ε > 0 as n → ∞, then the regression estimate n i=1 V i Y (i) (x), with (X (1) (x), Y (1) (x)), . . . , (X (n) (x), Y (n) (x)) the reordering of the data such that x -X (1) (x) ≤ . . . ≤ x -X (n) (x)
is called the weighted nearest neighbor regression estimate. It is known to be universally consistent (Stone [15], and Problems 11.7, 11.8 of Devroye, Györfi

INRIA

and Lugosi [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]). The crux to prove Theorem 1.1 is to observe that r ⋆ n is in fact a weighted nearest neighbor estimate with

V i = P(i-th nearest neighbor of x is the 1-NN in a random selection).
Then, a moment's thought shows that for the "without replacement" sampling, V i is hypergeometric:

V i =            n -i k n -1 n k n , i ≤ n -k n + 1 0, i > n -k n + 1,
whereas for sampling "with replacement",

V i = 1 - i -1 n kn -1 - i n kn .
The core of the proof of Theorem 1.1 is then to show that, in both cases, the weights V i satisfy the conditions V 1 → 0 and i>εn V i → 0 for all ε > 0 as n → ∞. These bagging weights have been independently exhibited by Steele [START_REF] Steele | Exact bootstrap k-nearest neighbor learners[END_REF], who shows on practical examples that substantial reductions in prediction error are possible under bootstrap sub-sampling.

In the present paper, we go one step further in the analysis and study the rates of convergence of E [r ⋆ n (x)r(x)] 2 as n → ∞. Building upon [START_REF] Biau | On the layered nearest neighbour estimate, the bagged nearest neighbour estimate and the random forest method in regression and classification[END_REF], we will distinguish between the "with replacement" (Section 2) and "without replacement" cases (Section 3). In both cases, we show that, for d ≥ 3, the estimate r ⋆ is of optimum rate for the class of distributions of (X, Y ) such that X has compact support and the regression function r is Lipschitz. We wish to emphasize that all the results are obtained by letting the resampling size k n grows with n in such a manner that k n → ∞ and k n /n → 0. These results are of interest because the majority of bagging experiments employ relatively large resample sizes. In fact, much of the evidence against the performance of bagged nearest nearest neighbor methods is for full sample size resamples (see the discussion in Breiman [START_REF] Breiman | Bagging predictors[END_REF], Paragraph 6.4), except the notable results of Hall and Samworth [START_REF] Hall | Properties of bagged nearest neighbour classifiers[END_REF] and Steele [START_REF] Steele | Exact bootstrap k-nearest neighbor learners[END_REF], who also report encouraging numerical calculations in the context of regression and classification.

Bagging "with replacement"

This bagging-type is sometimes called moon-bagging, standing for m out of n boostrap aggregating. In this case, the bagged 1-NN regression estimate takes the form

r ⋆ n (x) = n i=1 V i Y (i) (x),
where

V i = 1 - i -1 n kn -1 - i n kn .

RR n°6860

Here and throughout the document, the symbol V denotes variance and Γ(t) is the Gamma function

Γ(t) = ∞ 0 x t-1 e -x dx, t > 0.
Remind that if p is a positive integer, then Γ(p) = (p -1)!, with the convention 0! = 1.

Let us now recall various topological definitions that will be used in the paper. We first define the well-known notion of covering numbers which characterize the massiveness of a set (Kolmogorov and Tihomirov [START_REF] Kolmogorov | ε-entropy and ε-capacity of sets in functional spaces[END_REF]). As put forward in Kulkarni and Posner [START_REF] Kulkarni | Rates of convergence of nearest neighbor estimation under arbitrary sampling[END_REF], these quantities play a key role is the context of nearest neighbor analysis. Let B(x, ε) denote the open Euclidean ball in R d centered at x of radius ε.

N (ε) = inf k ≥ 1 : ∃ x 1 , . . . , x k ∈ R d such that A ⊂ k i=1 B(x i , ε) . A set A ⊂ R d is bounded if and only if N (ε) < ∞ for all ε > 0.
Note that as a function of ε, N (ε) is a non increasing, piecewise-constant and rightcontinuous function. The following discrete function, called the metric covering radius, can be interpreted as a pseudo-inverse of the function N (ε).

Definition 2.2. The metric covering radius N -1 (r) [= N -1 (r, A)] is defined as the smallest radius such that there exist r balls of this radius which cover the set A. That is

N -1 (r) = inf ε > 0 : ∃ x 1 , . . . , x r ∈ R d such that A ⊂ r i=1 B(x i , ε) .
We note that N -1 (r) is a non increasing discrete function of r. Finally, we let the support S(µ) of a probability measure µ be defined as the collection of all x with µ(B(x, ε)) > 0 for all ε > 0.

From now on, we denote by µ the distribution of X. Throughout the paper, it will be asumed that X is bounded. Letting ρ = N -1 (1, S(µ)), we observe that 2ρ is an upper bound of the diameter of the support of µ. We are now in a position to state the main result of this section.

Theorem 2.1. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Suppose in addition that, for all x and x ′ ∈ R d ,

σ 2 (x) = V[Y | X = x] ≤ σ 2 and |r(x) -r(x ′ )| ≤ C x -x ′ ,
for some nonnegative constants σ 2 and C. Then

INRIA (i) If d = 1, E [r ⋆ n (X) -r(X)] 2 ≤ 2σ 2 k n n 1 + 1 n 2kn + 32C 2 ρ 2 k n 1 + 1 n kn . (ii) If d = 2, E [r ⋆ n (X) -r(X)] 2 ≤ 2σ 2 k n n 1 + 1 n 2kn + 16C 2 ρ 2 k n 1 + 1 n kn [1 + ln(k n + 1)] . (iii) If d ≥ 3, E [r ⋆ n (X) -r(X)] 2 ≤ 2σ 2 k n n 1 + 1 n 2kn + 8C 2 ρ 2 1 -2/d 1 n kn + α d 1 + 1 n kn k n -2/d ,
where

α d = 2Γ d -2 d Γ d + 2 d .
By balancing the variance and bias terms in the theorem above, we are led to the following corollary.

Corollary 2.1. Under the assumptions of Theorem 2.1, we have:

(i) If d = 1, for k n = (4Cρ/ √ σ 2 e)n 1/2 , E [r ⋆ n (X) -r(X)] 2 ≤ Λ √ n ,
where Λ = 16e 3/2 σCρ.

(ii) If d = 2, for k n = (2 √ 2Cρ/ √ σ 2 e) n(1 + ln n), E [r ⋆ n (X) -r(X)] 2 ≤ Λ 1 + ln n n ,
where

Λ = 8 √ 2e 3/2 σCρ. (iii) If d ≥ 3, for k n = [4(1 + eα d C 2 ρ 2 )/(σ 2 e 2 (1 -2/d))] d/(d+2) n d d+2 , E [r ⋆ n (X) -r(X)] 2 ≤ ΛC 2d d+2 n -2 d+2 ,
where

Λ = 4σ 2 e 2 4(1 + eα d )ρ 2 σ 2 e 2 (1 -2/d) d/(d+2)
.

Two important remarks are in order.

1. First, we note that, for d ≥ 3 and a suitable choice of k n , the bagged nearest neighbor estimate achieves both the minimax n -2/(d+2) rate and the optimal constant C 2d/(d+2) on the class of distributions of (X, Y ) such that X has compact support and the regression function r is Lipschitz with Lipschitz constant C (Györfi, Kohler, Krzyżak and Walk [START_REF] Györfi | A Distributionfree Theory of Nonparametric Regression[END_REF], Chapter 3). Seconds, the bounds are valid for finite sample sizes, so that we are in fact able to approach the minimax lower bound not only asymptotically but even for finite sample sizes. On the other hand, the estimate with the optimal rate of convergence depends on the unknown distribution of (X, Y ), and especially on the covering radius ρ and the smoothness of the regression function measured by the constant C.

It is an open question whether there exists an optimal adaptive (i.e., data-dependent) choice of k n which still achieves the optimal rate of convergence over traditional classes of regression functions. Preliminary empirical results for crossvalidation are reported in Hall and Samworth [START_REF] Hall | Properties of bagged nearest neighbour classifiers[END_REF].

2. For d = 1, the obtained rate is not optimal, whereas it is optimal up to a log term for d = 2. This low-dimensional phenomenon is also true for the standard k n -nearest neighbor regression estimate, which does not achieve the optimal rates in dimensions 1 and 2 (see Problem 6.1 and Problem 6.7 in [START_REF] Györfi | A Distributionfree Theory of Nonparametric Regression[END_REF], Chapter 3).

Setting

r⋆ n (x) = n i=1 V i r(X (i) (x)),
the proof of Theorem 2.1 will rely on the variance/bias decomposition

E [r ⋆ n (X) -r(X)] 2 = E [r ⋆ n (X) -r⋆ n (X)] 2 + E [r ⋆ n (X) -r(X)] 2 . ( 1
)
The first term is treated in Proposition 2.1 and the second one in Proposition 2.3.

Proposition 2.1. Suppose that, for all x ∈ R d ,

σ 2 (x) = V[Y | X = x] ≤ σ 2 .
Then, for all x ∈ R d and all n ≥ 1,

E [r ⋆ n (x) -r⋆ n (x)] 2 ≤ 2σ 2 k n n 1 + 1 n 2kn .
The message of Proposition 1 is that, when resampling is done with replacement, the variance term of the bagged NN estimate is O(k n /n).

To analyse the bias term in (1), we will need the following result, which bounds the convergence rate of the expected i-th nearest neighbor distance in terms of the metric covering radii of the support of the distribution µ of X. Proposition 2.2 is a generalization of Theorem 1, page 1032 in Kulkarni and Posner [START_REF] Kulkarni | Rates of convergence of nearest neighbor estimation under arbitrary sampling[END_REF], which only report results for the rate of convergence of the nearest neighbor convergence rate. Therefore, this result is interesting by itself. As for now, we let the symbol ⌊.⌋ denote the integer part function.

INRIA Proposition 2.2. Suppose that X is bounded. Then E X (i) (X) -X 2 ≤ 8i n ⌊n/i⌋ j=1 N -1 (j, S(µ)) 2 .
For any bounded set A in the Euclidean d-space, the covering radius satisfies [START_REF] Kolmogorov | ε-entropy and ε-capacity of sets in functional spaces[END_REF]). Hence the following corollary: Corollary 2.2. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Then

N -1 (r, A) ≤ N -1 (1, A)r -1/d (see
(i) If d = 1, E X (i) (X) -X 2 ≤ 16ρ 2 i n . (ii) If d = 2, E X (i) (X) -X 2 ≤ 8ρ 2 i n 1 + ln n i . (iii) If d ≥ 3, E X (i) (X) -X 2 ≤ 8ρ 2 ⌊n/i⌋ -2/d 1 -2/d .
We are now in a position to upper bound the bias term in (1).

Proposition 2.3. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Suppose in addition that, for all x and x ′ ∈ R d ,

|r(x) -r(x ′ )| ≤ C x -x ′ ,
for some nonnegative constant C. Then

(i) If d = 1, E [r ⋆ n (X) -r(X)] 2 ≤ 32C 2 ρ 2 k n 1 + 1 n kn . (ii) If d = 2, E [r ⋆ n (X) -r(X)] 2 ≤ 16C 2 ρ 2 k n 1 + 1 n kn [1 + ln(k n + 1)] (iii) If d ≥ 3, E [r ⋆ n (X) -r(X)] 2 ≤ 8C 2 ρ 2 1 -2/d 1 n kn + α d 1 + 1 n kn k n -2/d ,
where

α d = Γ d -2 d Γ d + 2 d .
The take-home message here is that,

for d ≥ 3, E [r ⋆ n (X) -r(X)] 2 = O(k -2/d n
).

RR n°6860

3 Bagging "without replacement"

We analyse in this section the rate of convergence of the bagged nearest neighbor estimate, assuming this time that, at each step, the k n observations are distinctly chosen at random within the sample set D n . This alternative aggregation scheme is called subagging (for subsample aggregating) in Bühlmann and Yu [START_REF] Bühlmann | Analyzing bagging[END_REF]. In this case, the bagged 1-NN regression estimate takes the form

r ⋆ n (x) = n i=1 V i Y (i) (x),
where

V i =            n -i k n -1 n k n , i ≤ n -k n + 1 0, i > n -k n + 1.
Due to the fact that there is no repetition in the sampling process, the analysis turns out to be simpler. Our result is as follows.

Theorem 3.1. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Suppose in addition that, for all x and x ′ ∈ R d ,

σ 2 (x) = V[Y | X = x] ≤ σ 2 and |r(x) -r(x ′ )| ≤ C x -x ′ ,
for some nonnegative constants σ 2 and C. Then

(i) If d = 1, E [r ⋆ n (X) -r(X)] 2 ≤ k n n σ 2 (1 -k n /n + 1/n) 2 + 8C 2 ρ 2 k n . (ii) If d = 2, E [r ⋆ n (X) -r(X)] 2 ≤ k n n σ 2 (1 -k n /n + 1/n) 2 + 4C 2 ρ 2 k n (1 + ln k n ). (iii) If d ≥ 3, E [r ⋆ n (X) -r(X)] 2 ≤ k n n σ 2 (1 -k n /n + 1/n) 2 + 4C 2 ρ 2 1 -2/d k -2/d n .
By balancing the variance and bias terms in the theorem above, we are led to the following corollary.

Corollary 3.1. Under the assumptions of Theorem 3.1, we have:

(i) If d = 1, for k n = n 1/2 , E [r ⋆ n (X) -r(X)] 2 ≤ Λ √ n ,
where

Λ = σ 2 + 8C 2 ρ 2 . INRIA (ii) If d = 2, for k n = n(1 + ln n), E [r ⋆ n (X) -r(X)] 2 ≤ Λ 1 + ln n n ,
where

Λ = 5σ 2 + 4C 2 ρ 2 . (iii) If d ≥ 3, for k n = n d d+2 , E [r ⋆ n (X) -r(X)] 2 ≤ σ 2 C 2 d + Λ n -2 d+2 ,
where

C d = max n≥1 1 1 -n -2/(d+2) + 1 n and Λ = 4C 2 ρ 2 1 -2/d .
As in bagging with replacement,Theorem 3.1 expresses the fact that the without replacement bagged NN estimate achieves the standard minimax rate of convergence for d ≥ 3, with bounds which are valid for finite sample sizes. However, and contrary to bagging with replacement, the obtained constant in front of n -2/(d+2) is not optimal, and attentions shows that C d → ∞ as d → ∞. We do not know whether this constant can be sharpened or not.

To prove Theorem 3.1, we start again by the variance/bias decomposition

E [r ⋆ n (X) -r(X)] 2 = E [r ⋆ n (X) -r⋆ n (X)] 2 + E [r ⋆ n (X) -r(X)] 2 , with r⋆ n (x) = n i=1 V i r(X (i) (x)),
and we analyse each term separately.

Proposition 3.1. Suppose that, for all x ∈ R d ,

σ 2 (x) = V[Y | X = x] ≤ σ 2 .
Then, for all x ∈ R d and all n ≥ 1,

E [r ⋆ n (x) -r⋆ n (x)] 2 ≤ k n n σ 2 (1 -k n /n + 1/n) 2 .
As in the with replacement case, Proposition 3.1 above shows that the variance term of the without repetition-bagged NN estimate is O(k n /n). In order to analyse the bias term, we need the following proposition, which bounds the convergence rate of the expected nearest neighbor distance in terms of the metric covering radii of the support of the distribution µ of X. This result sharpens the constant of Theorem 1, page 1032 in Kulkarni and Posner [START_REF] Kulkarni | Rates of convergence of nearest neighbor estimation under arbitrary sampling[END_REF] and of Proposition 2.2 in the case of the nearest neighbor. Proposition 3.2. Suppose that X is bounded. Then

E X (1) (X) -X 2 ≤ 4 n n i=1 N -1 (i, S(µ)) 2 .
Biau & al.

Corollary 3.2. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Then

(i) If d = 1, E X (1) (X) -X 2 ≤ 8ρ 2 n . (ii) If d = 2, E X (1) (X) -X 2 ≤ 4ρ 2 n (1 + ln n). (iii) If d ≥ 3, E X (1) (X) -X 2 ≤ 4ρ 2 n -2/d 1 -2/d .
Recall that for any bounded set A in the Euclidean d-space, the covering radius satisfies N -1 (r, A) ≤ N -1 (1, A)r -1/d . Hence the following corollary: Proposition 3.3. Suppose that X is bounded, and set ρ = N -1 (1, S(µ)). Suppose in addition that, for all x and x ′ ∈ R d , and

|r(x) -r(x ′ )| ≤ C x -x ′ , for some nonnegative constant C. Then (i) If d = 1, E [r ⋆ n (X) -r(X)] 2 ≤ 8C 2 ρ 2 k n . (ii) If d = 2, E [r ⋆ n (X) -r(X)] 2 ≤ 4C 2 ρ 2 k n (1 + ln k n ). (iii) If d ≥ 3, E [r ⋆ n (X) -r(X)] 2 ≤ 4C 2 ρ 2 k n -2/d 1 -2/d .
We are now in a position to upper bound the bias term.

Thus, for d ≥ 3, we have as in the with replacement case : First, we observe that, for all x ∈ R d ,

E [r ⋆ n (X) -r(X)] 2 = O(k -2/d n ).
E [r ⋆ n (x) -r⋆ n (x)] 2 = E n i=1 V i Y (i) (x) -r(X (i) (x)) 2 = E n i=1 V 2 i Y (i) (x) -r(X (i) (x)) 2
(by conditioning on the X i 's and since r(

X (i) (x)) = E Y (i) (x) ) = E n i=1 V 2 i σ 2 X (i) (x) ≤ σ 2 n i=1 V 2 i . (2)
Next, an easy calculation shows that n i=1

V 2 i = n i=1 1 - i -1 n kn -1 - i n kn 2 = 2 n-1 i=0 1 - i n kn 1 - i n kn -1 - i + 1 n kn -1.
Let the map f : R → R be defined by f (x) = (1x) kn . Then, by the mean value theorem,

0 ≤ 1 - i n kn -1 - i + 1 n kn ≤ - 1 n f ′ i n = k n n 1 - i n kn-1 . Thus, n i=1 V 2 i ≤ 2k n n n-1 i=0 1 - i n 2kn-1 -1.
In addition, let the map g : R → R be defined by g(x) = (1-x) 2kn-1 . Observing that

1 0 g(x)dx = 1 2k n , we obtain n i=1 V 2 i ≤ 2k n 1 n n-1 i=0 g i n - 1 0 g(x)dx = 2k n n-1 i=0 (i+1)/n i/n g i n -g(x) dx.

Biau & al.

Invoking again the mean value theorem, we may write, for all x ∈ [i/n, (i+1)/n],

0 ≤ g i n -g(x) ≤ - 1 n g ′ i n .
Therefore,

n i=1 V 2 i ≤ 2k n n 2 n-1 i=0 -g ′ i n .
A moment's thought shows that

1 n n-1 i=0 -g ′ i n ≤ - 1-1/n -1/n g ′ (x)dx = g - 1 n -g 1 - 1 n .
Putting all pieces together, we finally obtain

n i=1 V 2 i ≤ 2k n n 1 + 1 n 2kn-1 - 1 n 2kn-1 ≤ 2k n n 1 + 1 n 2kn .
This, together with inequality (2), concludes the proof of the proposition.

Proof of Proposition 2.2

All the covering and metric numbers we use in this proof are pertaining to the bounded set S(µ). Therefore, to lighten notation a bit, we set N (ε) = N (ε, S(µ)) and N -1 (r) = N -1 (r, S(µ)).

Let X ′ be a random variable distributed as and independent of X and let, for ε > 0,

F X (ε) = P ( X -X ′ ≤ ε|X)
be the cumulative distribution function of the Euclidean distance between X and X ′ conditionally on X. Set finally

D (i) (X) = d X, X (i,N ) (X) .
Clearly,

P D 2 (i) (X) > ε = E P D (i) (X) > √ ε|X = E   i-1 j=0 n j F X √ ε j 1 -F X √ ε n-j   . ( 3
) Take B 1 , . . . , B N ( √ ε/2) a √ ε/2-covering of S(µ)
, and define an N ( √ ε/2)-partition of S(µ) as follows. For each ℓ = 1, . . . , N ( √ ε/2), let

P ℓ = B ℓ - ℓ-1 j=1 B j .

INRIA

Then P ℓ ⊂ B ℓ and

N ( √ ε/2) ℓ=1 B ℓ = N ( √ ε/2) ℓ=1 P ℓ ,
with P i ∩ P m = ∅. Also,

N (ε/2) ℓ=1 µ(P ℓ ) = 1.
Thus, letting p ℓ = µ(P ℓ ), we may write

F X √ ε ≥ P(∃ ℓ = 1, . . . , N ( √ ε/2) : X ∈ P ℓ and X ′ ∈ P ℓ |X) = E   N ( √ ε/2) ℓ=1 ½ X ′ ∈P ℓ ½ X∈P ℓ X   = N ( √ ε/2) ℓ=1 p ℓ ½ X∈P ℓ
As a by-product, we remark that ∀ε > 0 we have

F X ( √ ε) > 0 almost surely. Moreover E 1 F X ( √ ε) ≤ E 1 N ( √ ε/2) ℓ=1 p ℓ ½ X∈P ℓ = E   N ( √ ε/2) ℓ=1 1 p ℓ ½ X∈P ℓ   , which leads to E 1 F X ( √ ε) ≤ N ( √ ε/2). (4)
Consequently, combining inequalities (3), ( 4) and technical Lemma 4.1, we obtain

P D 2 (i) (X) > ε = E   1 F X ( √ ε) i-1 j=0 n j F X √ ε j+1 1 -F X √ ε n-j   ≤ i n + 1 E 1 F X ( √ ε) ≤ i n N √ ε/2 . Thus, since P(D 2 (i) (X) > ε) = 0 for ε > 4[N -1 (1)] 2 , we obtain E D 2 (i) (X) = ∞ 0 P(D 2 (i) (X) > ε)dε = 4[N -1 (1)] 2 0 P(D 2 (i) (X) > ε)dε ≤ 4 N -1 n i 2 + i n 4[N -1 (1)] 2 4[N -1 (⌊n/i⌋)] 2 N ( √ ε/2)dε. Biau & al. Since N ( √ ε) = j for N -1 (j) ≤ √ ε < N -1 (j -1), we get E D 2 (i) (X) ≤ 4 N -1 n i 2 + 4i n [N -1 (1)] 2 [N -1 (⌊n/i⌋)] 2 N ( √ ε)dε ≤ 4 N -1 n i 2 + 4i n ⌊n/i⌋ j=2 [N -1 (j-1)] 2 [N -1 (j)] 2 j dε = 4 N -1 n i 2 + 4i n   2 N -1 (1) 2 - n i N -1 n i 2 + ⌊n/i⌋-1 j=2 N -1 (j) 2   ≤ 8i n N -1 (1) 2 + 4i n N -1 n i 2 + 4i n ⌊n/i⌋-1 j=2 N -1 (j) 2 ,
where the last statement follows from the inequality

- 4i n n i + 4 ≤ 4i n .
In conclusion, we are led to

E D 2 (i) (X) ≤ 8i n ⌊n/i⌋ j=1 N -1 (j) 2 ,
as desired.

Proof of Corollary 2.2

For any bounded set A in the Euclidean d-space, the covering radius satisfies N -1 (r, A) ≤ N -1 (1, A)r -1/d (see [START_REF] Kolmogorov | ε-entropy and ε-capacity of sets in functional spaces[END_REF]). Consequently, using Proposition 2.2, we obtain

(i) For d = 1, E X (i) (X) -X 2 ≤ 8ρ 2 i n ⌊n/i⌋ j=1 j -2 ≤ 8ρ 2 i n 1 + ⌊n/i⌋ 1 x -2 dx ≤ 16ρ 2 i n . INRIA (ii) For d = 2, E X (i) (X) -X 2 ≤ 8ρ 2 i n ⌊n/i⌋ j=1 j -1 ≤ 8ρ 2 i n 1 + ⌊n/i⌋ 1 x -1 dx ≤ 8ρ 2 i n 1 + ln n i . (iii) For d ≥ 3, E X (i) (X) -X 2 ≤ 8ρ 2 i n ⌊n/kn⌋ j=1 j -2/d ≤ 8ρ 2 i n ⌊n/i⌋ 0 x -2/d dx = 8ρ 2 ⌊n/i⌋ -2/d 1 -2/d .
In the last statement, we used the inequality i/n ≤ 1/⌊n/i⌋.

Proof of Proposition 2.3

We write first

E [r ⋆ n (x) -r(x)] 2 = E n i=1 V i r(X (i) (x)) -r(x) 2 ≤ E n i=1 V i r(X (i) (x)) -r(x) 2 ≤ C 2 E n i=1 V i X (i) (x) -x 2 ≤ C 2 n i=1 V i E X (i) (x) -x 2
(by Cauchy-Schwarz inequality and since

n i=1 V i = 1).
Thus, integrating with respect to the distribution of X,

E [r ⋆ n (X) -r(X)] 2 ≤ C 2 n i=1 V i E X (i) (X) -X 2 .
To bound the term E X (i) (X) -X 2 , we apply Corollary 2.2 and distinguish the cases d = 1, d = 2 and d ≥ 3.

Biau & al. (i) If d = 1, for i = 1, . . . , n, E X (i) (X) -X 2 ≤ 16ρ 2 i n .
Consequently,

E [r ⋆ n (X) -r(X)] 2 ≤ 16C 2 ρ 2 n i=1 V i i n ,
and by definition of the V i 's

E [r ⋆ n (X) -r(X)] 2 ≤ 16C 2 ρ 2 n i=1 1 - i -1 n kn -1 - i n kn i n .
Thus x(1x) kn-j dx.

E [r ⋆ n (X) -r(X)] 2 ≤ 16C 2 ρ 2 n i=1 1 - i n + 1 n kn -1 - i n kn i n = 16C 2 ρ 2 n i=1   kn j=1 k n j 1 n j 1 - i n kn-j   i n = 16C 2 ρ 2 kn j=1 k n j 1 n j-1 1 n n i=1 1 - i n kn-j i n . i0+1 n i0 n n-1 n 1 1 2n f ( i0 n ) + f ( i0+1 n ) ≤ i 0 +1 n i 0 n f (x) dx

INRIA

For all j = 1, . . . , k n , we now use the inequality

1 n n i=1 i n 1 - i n kn-j ≤ 2 1 0 x(1 -x) kn-j dx
This inequality is clearly true for j = k n , even without the factor 2 in front of the integral. For j < k n , it is illustrated on Figure 1 where

f (x) = x(1 -x) kn-j . The factor 2 is this time necessary because f is not monotonous on [0, 1].
Consequently,

E [r ⋆ n (X) -r(X)] 2 ≤ 32C 2 ρ 2 kn j=1 k n j 1 n j-1 1 0 x(1 -x) kn-j dx.
Recalling the general formula

1 0 x p-1 (1 -x) q-1 dx = Γ(p)Γ(q) Γ(p + q) , p, q > 0, (5)
we obtain

E [r ⋆ n (X) -r(X)] 2 ≤ 32C 2 ρ 2 kn j=1 k n j 1 n j-1 Γ(2)Γ(k n -j + 1) Γ(k n -j + 3) ≤ 32C 2 ρ 2 kn j=1 k n j 1 n j-1 1 (k n -j + 1)(k n -j + 2) = 32C 2 ρ 2 kn j=1 k n j -1 1 n j-1 1 j(k n -j + 2) = 32C 2 ρ 2 kn-1 j=0 k n j 1 n j 1 (j + 1)(k n -j + 1)
.

Observing finally that (j + 1)(k nj + 1) ≥ k n for all j = 0, . . . , k n -1, we conclude

E [r ⋆ n (X) -r(X)] 2 ≤ 32C 2 ρ 2 k n kn-1 j=0 k n j 1 n j ≤ 32C 2 ρ 2 k n 1 + 1 n kn .
(ii) For d = 2, a reasoning similar to the one reported in statement (i) above can be followed, to show that

E [r ⋆ n (X) -r(X)] 2 ≤ 16C 2 ρ 2 1 k n 1 + 1 n kn - kn j=1 k n j 1 n j-1 1 0 x(1 -x) kn-j ln xdx . (6)
Denoting by H n the n-th harmonic number, i.e.,

H n = 1 + 1 2 + . . . + 1 n ,
we may write, using technical Lemma 4.2,

- kn j=1 k n j 1 n j-1 1 0 x(1 -x) kn-j ln xdx = kn j=1 k n j 1 n j-1 H kn-j+2 -1 (k n -j + 1)(k n -j + 2) = kn-1 j=0 k n j 1 n j H kn-j+1 -1 (j + 1)(k n -j + 1)
.

For all j = 0, . . . , k n -1, we have (j + 1)(k nj + 1) ≥ k n as well as

H kn-j+1 -1 = 1 2 + . . . + 1 k n -j + 1 ≤ kn-j+1 1 dx x = ln(k n -j + 1) ≤ ln(k n + 1). Therefore, - kn j=1 k n j 1 n j-1 1 0 x(1 -x) kn-j ln xdx ≤ ln(k n + 1) k n kn-1 j=0 k n j 1 n j ≤ ln(k n + 1) k n 1 + 1 n kn . (7)
Combining inequalities (6) and ( 7) leads to the desired result.

(iii) For d ≥ 3, starting again as in (i), we obtain

E [r ⋆ n (X) -r(X)] 2 ≤ 8C 2 ρ 2 1 -2/d n i=1 V i n i -2/d . ( 8
)
To upper bound the right-hand side, we note that for all i = 1, . . . , n -1,

n i -2/d ≤ i/n 1 -i/n 2/d
, and set consequently

S n = 1 n kn + n-1 i=1 1 - i -1 n kn -1 - i n kn i/n 1 -i/n 2/d . INRIA We obtain S n = 1 n kn + n-1 i=1   kn j=1 k n j 1 n j 1 - i n kn-j   i/n 1 -i/n 2/d = 1 n kn + kn j=1 k n j 1 n j-1 1 n n-1 i=1 1 - i n kn-j-2/d i n 2/d ≤ 1 n kn + 2 kn j=1 k n j 1 n j-1 1 0 x 2/d (1 -x) kn-j-2/d dx.
Applying formula (5) again, together with the identity

Γ p + d -2 d = Γ d -2 d p ℓ=1 ℓ - 2 d ,
we obtain

S n ≤ 1 n kn + α d kn j=1 k n j 1 n j-1 1 (k n -j + 1) kn-j ℓ=1 1 - 2 dℓ (with α d = 2Γ((d -2)/d) Γ((d + 2)/d) = 1 n kn + α d kn j=1 k n ! j!(k n -j + 1)! 1 n j-1 kn-j ℓ=1 1 - 2 dℓ = 1 n kn + α d kn j=1 1 n j-1 k n j -1 1 j kn-j ℓ=1 1 - 2 dℓ = 1 n kn + α d kn-1 j=0 1 n j k n j 1 j + 1 kn-j-1 ℓ=1 1 - 2 dℓ
and by technical Lemma 4.3:

S n ≤ 1 n kn + α d kn-1 j=0 k n j 1 n j k -2/d n ≤ 1 n kn + α d 1 + 1 n kn k -2/d n . (9)
Finally, combining inequalities ( 8) and ( 9) concludes the proof of Proposition 2.3.

Proof of Proposition 3.1

Starting as in the proof of Proposition 2.1, we write

E [r ⋆ n (x) -r⋆ n (x)] 2 ≤ σ 2 n i=1 V 2 i , RR n°6860
Biau & al.

where, for i = 1, . . . , nk n + 1,

V i = n -i k n -1 n k n = k n n -k n + 1 kn-2 j=0 1 - i n -j ≤ k n n -k n + 1 kn-2 j=0 1 - i n = k n n -k n + 1 1 - i n kn-1 . This yields n i=1 V 2 i ≤ k 2 n (n -k n + 1) 2 n-kn+1 i=1 1 - i n 2(kn-1) ≤ k 2 n n (n -k n + 1) 2 1 n n i=1 1 - i n 2(kn-1)
.

Observing finally that

1 n n i=1 1 - i n 2(kn-1) ≤ 1 0 (1 -x) 2(kn-1) dx = 1 2k n -1 , we conclude that n i=1 V 2 i ≤ k 2 n n (2k n -1)(n -k n + 1) 2 ≤ k n n 1 (1 -k n /n + 1/n) 2 .

Proof of Proposition 3.2

All the covering and metric numbers we use in this proof are pertaining to the bounded set S(µ). Therefore, to lighten notation a bit, we set N (ε) = N (ε, S(µ)) and N -1 (r) = N -1 (r, S(µ)).

Let X ′ be a random variable distributed as and independent of X and let, for ε > 0, F X (ε) = P ( X -X ′ ≤ ε|X)

be the cumulative distribution function of the Euclidean distance between X and X ′ conditionally on X. Set finally

D (1) (X) = d X, X (1,N ) (X) . INRIA Clearly, P D 2 (1) (X) > ε = E P D (1) (X) > √ ε|X = E (1 -F X ( √ ε)) N . Take B 1 , . . . , B N ( √ ε/2) a √ ε/2-covering of S(µ)
, and define an N ( √ ε/2)-partition of S(µ) as follows. For each ℓ = 1, . . . , N ( √ ε/2), let

P ℓ = B ℓ - ℓ-1 j=1 B j .
Then P ℓ ⊂ B ℓ and

N ( √ ε/2) ℓ=1 B ℓ = N ( √ ε/2) ℓ=1 P ℓ , with P ℓ ∩ P ℓ ′ = ∅. Also, N (ε/2) ℓ=1 µ(P ℓ ) = 1.
Thus, letting p ℓ = µ(P ℓ ), we may write

F X √ ε ≥ P(∃ ℓ = 1, . . . , N ( √ ε/2) : X ∈ P ℓ and X ′ ∈ P ℓ |X) = E   N ( √ ε/2) ℓ=1 ½ X ′ ∈P ℓ ½ X∈P ℓ X   = N ( √ ε/2) ℓ=1 p ℓ ½ X∈P ℓ
As a by-product, we remark that ∀ε > 0 we have F X ( √ ε) > 0 almost surely. Moreover

E 1 F X ( √ ε) ≤ E 1 N ( √ ε/2) ℓ=1 p ℓ ½ X∈P ℓ = E   N ( √ ε/2) ℓ=1 1 p ℓ ½ X∈P ℓ   , which leads to E 1 F X ( √ ε) ≤ N ( √ ε/2) Since p(1 -p) N ≤ e -1 N +1 ≤ 1 2N for all p ∈ [0, 1], we can deduce P D 2 (1) (X) > ε = E (1 -F X ( √ ε)) N = E 1 F X ( √ ε) F X √ ε (1 -F X ( √ ε)) N ≤ 1 2N E 1 F X ( √ ε) ≤ N ( √ ε/2) 2N RR n°6860
Biau & al.

Using the fact that P(D (1) (X) > ε) = 0 for ε > 2N -1 (1), we may write

E D 2 (1) (X) = ∞ 0 P D 2 (1) (X) > ε dε = 4[N -1 (1)] 2 0 P D 2 (1) (X) > ε dε = 4[N -N (1)] 2 0 P D 2 (1) (X) > ε dε + 4[N -1 (1)] 2 4[N -1 (N )] 2 P D 2 (1) (X) > ε dε ≤ 4 N -1 (N ) 2 + 1 2N 4[N -1 (1)] 2 4[N -1 (N )] 2 N ( √ ε/2)dε = 4 N -1 (N ) 2 + 2 N [N -1 (1)] 2 [N -1 (N )] 2 N ( √ ε)dε = 4 N -1 (N ) 2 + 2 N N i=2 [N -1 (i-1)] 2 [N -1 (i)] 2 N ( √ ε)dε Since N ( √ ε) = i for N -1 (i) ≤ √ ε < N -1 (i -1)
, we can upper bound this last quantity as follows

E D 2 (1) (X) ≤ 4 N -1 (N ) 2 + 2 N N i=2 i N -1 (i -1) 2 -N -1 (i) 2 . = 4 N N -1 (1) 2 + 2 N N -1 i=2 N -1 (i) 2 + 2 N -1 (N ) 2 ≤ 4 N N i=1 N -1 (i) 2 .
For the last inequality, recall that the sequence (N -1 (i)) is non increasing, so that

N -1 (N ) 2 ≤ N i=2 N -1 (i) 2 N -1 .
Then the decomposition

N -1 (N ) 2 = N -1 N N -1 (N ) 2 + 1 N N -1 (N ) 2
leads to the desired result.

Proof of Corollary 3.2

Recall that the covering radius satisfies the property

N -1 (r, S(µ)) ≤ N -1 (1, S(µ))r -1/d
(see [START_REF] Kolmogorov | ε-entropy and ε-capacity of sets in functional spaces[END_REF]). Thus, using Proposition 3.2, we obtain

(i) For d = 1, E X (1) (X) -X 2 ≤ 4ρ 2 n n i=1 i -2 ≤ 8ρ 2 n . INRIA (ii) For d = 2, E X (1) (X) -X 2 ≤ 4ρ 2 n n i=1 i -1 ≤ 4ρ 2 n (1 + ln n). (iii) For d ≥ 3, E X (1) (X) -X 2 ≤ 4ρ 2 n n i=1 i -2/d ≤ 4ρ 2 n n 0 x -2/d dx ≤ 4ρ 2 n -2/d 1 -2/d . 4.8 Proof of Proposition 3.3 Recall that r⋆ n (x) = n i=1 V i r(X (i) (x)),
and observe that r⋆

n (x) = E ⋆ r(X ⋆ (1) (x)) ,
where X ⋆ (1) (x) is the nearest neighbor of x in a random subsample S n drawn without replacement from {X 1 , . . . , X n } with Card(S n ) = k n , and E ⋆ denotes expectation with respect to the resampling distribution, conditionally on the data set D n . Consequently, by Jensen's inequality,

E [r ⋆ n (x) -r(x)] 2 = E E ⋆ r X ⋆ (1) (x) | D n -r(x) 2 = E E ⋆ r X ⋆ (1) (x) -r(x) | D n 2 ≤ E E ⋆ r X ⋆ (1) (x) -r(x) 2 | D n = E r X ⋆ (1) (x) -r(x) 2 ≤ C 2 E X ⋆ (1) (x) -r(x) 2
Since Card(S n ) = k n , we can now apply Corollary 3.2, replacing n with k n . Thus, using 1 + 1/2 + . . . + 1/p ≥ ln(p + 1), we deduce

Some technical lemmas

kn-j-1 ℓ=1 1 - 2 dℓ ≤ (k n -j) -2/d
To conclude, we use the fact that, for j = 0, . . . , k n -1,

1 j + 1 (k n -j) -2/d ≤ k -2/d n .
To see this, note that the inequality above may be written under the equivalent form (1j/k n ) -2/d ≤ 1 + j = 1 + k n • j k n .

The result can be deduced from the comparison between the map ϕ :

Definition 2 . 1 .

 21 Let A be a subset of R d . The ε-covering number N (ε) [= N (ε, A)] is defined as the smallest number of open balls of radius ε that cover the set A. That is

Figure 1 :

 1 Figure 1: Illustration of 1 n

Lemma 4 . 1 . 1 . 1 . 1 . 4 . 2 .I m = - 1 0x( 1 - 4 . 2 1 0 1 0= - 1 +Lemma 4 . 3 ..

 4111142114211143 For j = 0, . . . , n -1, let the map ϕ n,j (p) be defined byϕ n,j (p) = n j p j+1 (1p) n-j , 0 ≤ p ≤ Then for all i ≤ n sup 0≤p≤1 i-1 j=0 ϕ n,j (p) ≤ i n +Proof of Lemma 4.1 Each map ϕ n,j is nonnegative, continuously increasing on the interval [0, (j + 1)/(n + 1)] and decreasing on [(j + 1)/(n + 1), 1]. Consequently, the supremum of the continuous function i-1 j=0 ϕ n,j (p) is achieved at some point p ⋆ of the interval [1/(n + 1), i/(n+ 1)]. That is, p ⋆ ) n-j = p ⋆ ≤ i n + Lemma Let, for each integer m ≥ 0, x) m ln xdx. Then I m = H m+2 -1 (m + 1)(m + 2),where H n is the n-th harmonic number, i.e., Two successive integrations by parts of I m show that(m + 2)(m + 1)I m = -(m + 2) (m + 1)(1x) m x ln xdx = -(m + 2)(1x) m+1 (1 + ln x)dx. = (1x) m+2 -1 (1 + ln x) H m+2 .INRIA For each d ≥ 3, each k n ≥ 1, and j = 0, . . . , k n -1,Proof of Lemma 4.3 First, since 0 ≤ 1x ≤ e -x for all x ∈ [0, 1],

x → ( 1 -

 1 x) -2/d and ψ :x → 1 + k n x on the interval [0, 1 -1/k n ]. Just note that ϕ(0) = ψ(0), ϕ(1 -1/k n ) = k -2/d n < 1/k n = ψ(1 -1/k n ) since d ≥ 3,and ϕ is convex while ψ is affine (see Figure2).

Figure 2 :

 2 Figure 2: Illustration of ϕ(x) ≤ ψ(x) ∀x ∈ [0, 1 -1/k n ], see text.

[ 6 ]

 6 Dietterich, T.G.(2000). Ensemble methods in machine learning, in J. Kittler and F. Roli (Eds.), First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science, 1-15, Springer-Verlag, New York.

RR n°6860

Biau & al.


Yanliang Yi

Xinyuan Ma

Ruiwen Liu

Xindang Chu

Haiwei Li

Jiayi Zhang

Qianqian Gao

Yongmin Zhang

Lihe Zhang

Demin Zhou

Sulong Xiao
email: slxiao@bjmu.edu.cn

An attempt to synthesize the two monomers of CDTOH: Unexpected NMR and X-ray diffraction crystal analysis

Keywords: CDTOH, β-cyclodextrin, Crystal structure, Click chemistry, Interinclusion

Two monomer compounds of CDTOH, 6 A -deoxy-6 A -(4-(2-hydroxyethyl)-1H-1,2,3-triazol-1-yl)-per-O-methylated β-cyclodextrin 4 and 6 A -deoxy-6 A -(4-(2-hydroxyethyl)-1H-1,2,3-triazol-1-yl) β-cyclodextrin 7, have been synthesized via click chemistry. The structures were confirmed by 1 H NMR, 13 C NMR and ESI-HRMS. In comparison to the 1 H NMR spectra of compound 4 and intermediate 6, two sets of peaks in the high field of 7 are somewhat unusual. The X-ray single-crystal analysis of 7 showed the existence of an intramolecular hydrogen bond between the CH 2 OH donor of glucose B and the terminal hydroxy acceptor of the side chain, leading to the 4-(2-hydroxyethyl)-1H-1,2,3-triazole group protruding outside the cavity and embedding in the hydrophobic cavity of the adjacent molecule (interinclusion) to form an interlocked helical columnar superstructure.

Introduction

Cyclodextrins (CDs) are naturally occurring cyclic oligomers of (α-1,4)-linked D-glucopyranoside and are commonly known as hexamers to octamers. 1 Due to their toroid cone structures, CDs have many interesting biological properties resulting in hydrophobic cores and hydrophilic exteriors. They can form inclusion complexes with a broad variety of guest molecules with sizes compatible with the cavity size, 2 which have a vast range of applications from drug delivery systems and enzyme mimics to chemical and biological sensors. [2][3][4] Over the past several decades, randomly methylated β-CD (RAME-β-CD) has attracted increasing attention given its unique properties such as high solubility both in water and in nonaqueous solvents. 5,6 The solubility of RAME-β-CD in water at 25 °C (50 g/100 mL) is 27-fold greater than that of β-CD (1.85 g/100 mL). Therefore, RAME-β-CD has a superior effect on the aqueous solubility of various active molecules. In addition, the addition of RAME-β-CD and RAME-β-CD-NEt 2 has an effect on the efficiency and selectivity of palladium-catalyzed Heck arylation. 7 Interestingly, RAME-β-CDs with hydrophilic moieties in the 4-position of the 1,2,3-triazole group on the primary face, such as CDTSO 3 Na, CDTpolyOH and CDTOH (Figure 1), can constitute a new class of multiwall carbon nanotube (MWNT) dispersion agents. 8 The 1,4-disubstituted-1,2,3-triazole-linked RAME-β-CD dimers are also well known to be very effective mass transfer promoters to convert long alkyl-chain substrates in the palladium-catalyzed Tsuji-Trost reaction. 9 Despite extensive research on RAME-β-CDs, many of them are a mixture of partially methylated β-CDs with an average degree of substitution of 1.8 methyl groups per glucopyranose unit. In addition, their biological effect has been shown to be concentration-dependent and variable based on the type of modified CD and degree of substitution. 10 NMR spectrum of 7. To better understand this, a single crystal of compound 7 was obtained for X-ray diffraction and the intermolecular threading was observed in solid state. As compared with the crystal analysis, the concentration-dependent NMR spectroscopy indicated that the 1,2,3-triazole group included in the β-CD cavity. Herein, we report the synthesis and unambiguous structural characterization of triazole-functionalized β-CDs by NMR, together with an investigation of the structural characterization of 7 by X-ray diffraction analysis.

Results and discussion

The synthesis route of the two mono-4-(2-hydroxyethyl)-1,2,3-triazole functionalized β-CD derivatives 4 and 7 is summarized in Scheme 1. Briefly, β-CD was converted into 6 A -deoxy-6 A -azide per-O-methylated β-CD (3) or 6 A -deoxy-6 A -azide per-O-acetylated β-CD (5) through a previously described easy and efficient three-step reaction procedure. 11 referring to 2H, could be assigned to the methylene next to the triazole group.

To our surprise, two sets of relatively broad double peaks at 2.83 ppm (J = 11.9 Hz) and 3.19 ppm (J = 12.3 Hz), each referring to 1H, were clearly observed, which was unlike its analogs of 4 and 6 (Figure 2). Analysis of the COSY and HSQC spectra of 7 (Figures S3 andS4) reveals that they should be CH 2 of one glucose unit of β-CD. To gain more information about the structure of 7, we performed a ROESY experiment. After careful analysis, the ROESY spectrum indicated that the CH 2 group should be close to glucose A, possibly glucose B or F, due to it shows strong cross peaks between H 6a B(F) and H 6b B(F) and H 4 B(F) (peaks A and B) and weak cross peaks between H 6a B(F) and H 5 A and H 6b A (peaks C and D) (Figure 3). However, we are curious why it is unlike the CH 2 group of the other five glucoses. To provide a definitive answer to the structure of 7, a single crystal was obtained for X-ray diffraction analysis. Crystallographic data are given in Table 1 and have been deposited at the Cambridge Crystallographic Data Centre (deposition no.). A tetragonal crystal with the space Group P4 1 2 1 2 was obtained from a water solution. An ORTEP drawing of 7 is shown in Figure 4, while the fractional atomic coordinates and equivalent isotropic displacement parameters, anisotropic displacement parameters, bond lengths, bond angles, hydrogen bonds and torsion angles are given in the Supporting Information (Tables S1-S6). In the crystalline form, the β-CD ring presents a bottomless bowl-shaped molecule stiffened by hydrogen bonding between the 3-OH and 2-OH groups around the outer rim (Figure 4A), 13 with the 4-(2-hydroxyethyl)-1H-1,2,3-triazol side chain protruding outside from the primary face of the cavity. In addition, it was determined that a short intramolecular hydrogen bond (O6B-H6BB Each molecule behaves as both a host and a guest. According to the X-ray crystal analysis (Figure 5), it is clearly that the triazole side chain can be embedded in the cavity of the adjacent molecule to form interinclusions (species C, Figure 6). from the second rim to form an interlocked helical columnar superstructure.

Experimental

General

Reagents and solvents were obtained from several commercial sources and used as received.

Electrospray ionization high-resolution mass spectra (ESI-HRMS) were acquired using an APEX IV FT_MS (7.0 T) spectrometer (Bruker) operating in positive mode. NMR spectra were recorded on a Bruker DRX 400 or 600 spectrometer at ambient temperature. Reaction progress was monitored by thin-layer chromatography (TLC) on commercial silica gel plates (E. Merck 60 F 254 on aluminum sheets, Germany) and visualized by spraying with a solution of 6% H 2 SO 4 in ethanol, followed by heating.

β-CD derivatives 1-3 and 5 were synthesized by literature methods, 11 and the data were consistent with those previously published.

6 A -Deoxy-6 A -[4-(2-hydroxyethyl)-1H-1,2,3-triazol-1-yl] per-O-methylated β-CD (4)

A solution of compound 3 (154 mg, 0.11 mmol) and 3-butyn-1-ol (11.2 mg, 0.16 mmol) in A solution of compound 5 (150.0 mg, 0.075 mmol) and 3-butyn-1-ol (6.7 mg, 0.097 mmol) in To a solution of compound 6 (62 mg, 0.030 mmol) in dry MeOH (3 mL) was added 30%

NaOMe (100 μL), and the solution was stirred for 2 h at room temperature. After neutralization with an Amberlite ® IR 120-H ion exchange resin, the solvent was evaporated by an oil pump to afford compound 7 (37 mg, 100%).

X-ray diffraction of 7

A concentrated solution of 7 in water at room temperature was allowed to cool to 4 °C, and rod-shaped crystals were obtained after 3 days. Single-crystal data were collected on a XtaLAB Synergy R HyPix diffractometer. The crystal was kept at 100.00 (10) K during data collection.

Using Olex2, 14 the structure was solved with the ShelXS structure solution program using Direct Methods and refined with the ShelXL refinement package using least squares minimization. 15 Crystallographic data for the structure reported in this paper have been deposited with the Cambridge Crystallographic Data Centre as supplementary publication no 2123295.

Fig. 1 .

 1 Fig. 1. Structures of CDTOH and its two monomer compounds 4 and 7. DS: average number of methyl groups per glucopyranose unit In order to further study the effect of the substituents of CDTOH on their chemistry and biology activity, we attempt to synthesize the two monomer compounds of CDTOH, 6 A -deoxy-6 A -[4-(2-hydroxyethyl)-1,2,3-triazol-1-yl] per-O-methylated β-CD (HETPM-β-CD, 4) and 6 A -deoxy-6 A -[4-(2-hydroxyethyl)-1,2,3-triazol-1-yl] β-CD (HET-β-CD, 7). To our surprise, two sets of unusual signals were observed clearly at δ 2.83 ppm and 3.19 ppm in the high-field 1 H

Scheme 1 .

 1 Scheme 1. Reagents and conditions: (a) NaOH, H 2 O, TsCl, 13%; (b) NaN 3 , DMF, 80 °C, 86%; (c) NaH, CH 3 I, DMF, 65%; (d) 3-butyr-1-ol, CuSO 4 , Na-L-ascorbate, THF-H 2 O (1:1, V/V), 74%; (e) Ac 2 O, pyridine, DMAP; (f) 3-butyr-1-ol, CuSO 4 , Na-L-ascorbate, THF-H 2 O (1:1, V/V), 45%; (g) CH 3 ONa/CH 3 OH, rt, 100%The acetyl groups of 6 were further removed by a Zemblén reaction in the presence of CH 3 ONa to quantitatively afford 7. Although the synthesis of compound 7 has been previously

Figure 2 .

 2 Figure 2. Partial 1D 1 H NMR spectra of (a) compound 4 (CDCl 3 , 298K, 400 MHz), (b) compound

Figure 3 .

 3 Figure 3. 1 H ROESY spectrum (600 MHz) of 7 in D 2 O at 298 K. Key NOE correlations (red arrows) observed for the CH 2 OH group of glucoses A and B

Figure 4 .

 4 Figure 4. ORTEP view of 7. (A) Side view showing the 4-(2-hydroxyethyl)-1H-1,2,3-triazol side group at position C-6 on glucose A protruding outside the cavity. (B) Top-down view from the 4-(2-hydroxyethyl)-1H-1,2,3-triazol side chain. Intermolecular hydrogen bond assigned by red dashed line (Carbon: gray; hydrogen: white; oxygen: red and nitrogen: blue) The unique layering that results in the extended crystal structure is shown in Figure 5. The crystal structure clearly reveals that the 4-(2-hydroxyethyl)-1H-1,2,3-triazole side group is consecutively inserted into the adjacent β-CD cavity from the secondary face, as expected, thus giving rise to an interlocked helical supramolecular formed by self-assembly in which the 4-(2-hydroxyethyl)-1H-1,2,3-triazole side group acts as bridge between the cyclodextrin units.

Figure 5 .

 5 Figure 5. Interlocked helical superstructure of compound 7. The column is located on a 4-fold screw axis. (Carbon: gray; oxygen: red and nitrogen: blue) It was reported that a cross shift of two broad signals of the triazole proton was observed in the 1 H NMR spectrum of CDTOH in D 2 O, 9 highlighting a capping process of the β-CD cavity by the triazole substituent. However, the 1 H NMR spectra of compounds 4 and 6 in CDCl 3 and 7 in D 2 O all show one signal of the triazole proton, indicating that the threading and de-threading process may faster than the NMR time scale. Therefore, the concentration-dependent NMR spectroscopy was carried out (Figures S5).Both triazole-H and β-CD-H 5 A are slightly shifted

  Both triazole-H and β-CD-H 5 A are slightly shifted upfield giving chemical shifts of the range from 0.0002 to 0.0025 ppm and from 0.0013 to 0.0069 ppm, respectively, with the increasing concentration of the compound 7 in the range from 0.625 mM to 5.0 mM, suggesting that the 4-(2-hydroxyethyl)-1H-1,2,3-triazole side chain is included in the β-CD cavity in solution to form noncovalent inclusion complexes (species B or C, Figure6).

Figure 6 .

 6 Figure 6. Schematic representations of 7 (A) and its inclusion complexes (B and C).

3 Conclusion

 3 In summary, we successfully synthesized and characterized two monomer compounds of CDTOH, 4 and 7. Due to the formation of an intramolecular hydrogen bond between the terminal hydroxy group of the side chain and glucose B of 7, as indicated by the 2D ROESY spectrum and single crystal X-ray diffraction analysis; the chemical shifts of CH 2 of glucose B shift upfield. The 1,2,3-triazole group of 7 inserted into the hydrophobic cavity of the adjacent β-CD (interinclusion)

  1 H NMR (600 MHz, D 2 O): δ 7.88 (s, 1H), 5.19 (d, J = 3.7 Hz, 1H), 5.13-5.06 (m, 4H), 5.04-4.98 (m, 3H), 4.60 (dd, J = 14.6, 9.5 Hz, 1H), 4.20 (t, J = 9.6 Hz, 1H), 4.08-3.81 (m, 24H), 3.78 (dd, J = 12.0, 4.1 Hz, 1H), 3.71 (dd, J = 10.1, 3.8 Hz, 1H), 3.70-3.50 (m, 13H), 3.19 (br d, J = 12.3 Hz, 1H), 2.97 (t, J = 6.5 Hz, 2H), 2.83 (br d, J = 11.9 Hz, 1H); 13 C NMR (151 MHz, D 2 O): δ 125.

Table 1 .

 1 •••O10A, with O•••O 2.745(8) Å and angle O-H•••O 169.6°) between the CH 2 CH 2 OH proton acceptor side chain and the 6-OH proton donor group of glucose B causes the protons of CH 2 A and CH 2 B to be close enough in distance, resulting in the observation of anomalous NOEs in the ROESY spectrum. Additionally, due to the formation of the hydrogen bond, the CH 2 group of glucose B is located in the shielding region (ring currents affect) less than 3.3 Å from the centroid of the triazole, which explains why the chemical shifts of CH 2 A are unlike those of the CH 2 group of glucoses C-G. Crystallographic data for 7

	Empirical Formula	C 46 H 75 N 3 O 35
	Formula weight	1230.09
	Temperature/K	100.00 (10)
	Crystal system	tetragonal
	Space group	P4 1 2 1 2
	a/Å	21.65007 (13)
	b/Å	21.65007 (13)
	c/Å	28.6778 (3)
	α/°	90
	β/°	90
	γ/°	90
	Volume/Å 3	13442.0 (2)
	Z	8
	ρ calc g/cm 3	1.216
	μ/mm -1	0.913
	F (000)	5216.0
	Crystal size/mm 3	0.21 × 0.18 × 0.12
	Radiation	CuKα (λ = 1.54184)
	2Θ range for data collection/°	6.544 to 140.132
	Index ranges	-26 ≤ h ≤ 26, -25 ≤ k ≤ 26, -34 ≤ l ≤ 33
	Reflections collected	112688
	Independent reflections	12711 [R int = 0.0628, R sigma = 0.0264]
	Data/restraints/parameters	12711/30/842
	Goodness-of-fit on F 2	1.054

  1:1 CH 3 OH-H 2 O (4 mL), CuSO 4 (10 mg, 0.06 mmol) and sodium ascorbate (20 mg, 0.10 mmol) was added. After stirring at room temperature for 10 h, the crude product was extracted with CH 2 Cl 2 . The organic layer was dried with Na 2 SO 4 and then filtered. The filtrate was evaporated and then purified by silica gel column chromatography (CH 2 Cl 2 /CH 3 OH= 9:1) to obtain compound 4 (120 mg, 74%). R f = 0.36 (eluent:CH 2 Cl 2 /CH 3 OH = 20:1).1 H NMR (400 MHz,

	CDCl 3 ): δ 7.53 (s, 1H), 5.24 (d, J = 3.7 Hz, 1H), 5.17-5.11 (m, 5H), 5.09 (d, J = 3.6 Hz, 1H), 4.99
	(dd, J = 14.3, 2.1 Hz, 1H), 4.62 (dd, J = 14.4, 7.3 Hz, 1H), 4.13-4.04 (m, 1H), 3.98-3.90 (m, 3H),
	3.90-3.74 (m, 9H), 3.70-3.46 (m, 62H), 3.40 (s, 3H), 3.39 (s, 3H), 3.39 (s, 3H), 3.37 (s, 3H), 3.31
	(s, 3H), 3.29 (s, 3H), 3.27-3.12 (m, 9H), 3.09 (dd, J = 9.8, 3.4 Hz, 1H), 2.94 (t, J = 5.8 Hz, 2H);
	13 C NMR (101 MHz, CDCl 3 ): δ 145.15, 123.46, 99.40, 99.20, 98.95, 98.90, 98.87, 98.81, 98.26,
	83.02, 82.10, 82.03, 81.97, 81.89, 81.86, 81.76, 81.74, 81.67, 81.13, 80.34, 80.25, 80.23, 80.13,
	80.01, 79.20, 71.42, 71.41, 71.36, 71.30, 71.24, 71.01, 70.96, 70.85, 70.73, 70.67, 70.56, 61.65,
	61.54, 61.39, 61.37, 61.31, 59.10, 59.09, 59.04, 59.02, 58.92, 58.78, 58.65, 58.54, 58.52, 58.49,
	58.46, 51.36, 28.75; ESI-HRMS (m/z) [M + H] + calcd for C 66 H 116 N 3 O 35 , 1510.7384, found,
	1510.7385.

  Hz, 1H), 3.57 (t, J = 9.0 Hz, 1H), 2.96-2.89 (m, 2H), 2.14-1.97 (m, 60H);13 C NMR (151 MHz, CDCl 3 ): δ 170.88, 170.76, 170.74, 170.71, 170.69, 170.61, 170.54, 170.50, 170.40, 170.30, 169.58, 169.42, 169.41, 169.38, 169.34, 169.31, 169.19, 145.32, 124.45, 97.07, 96.88, 96.76,

	96.72, 96.50, 96.44, 77.49, 77.11, 76.85, 76.51, 76.36, 75.86, 71.60, 71.35, 71.30, 71.01, 70.85,
	70.61, 70.35, 70.28, 70.22, 70.07, 70.01, 69.86, 69.67, 69.62, 69.57, 69.41, 69.27, 62.75, 62.66,
	62.62, 62.59, 62.50, 62.21, 61.53, 49.32, 28.66, 20.88, 20.85, 20.83, 20.82, 20.81, 20.79, 20.75,
	20.72, 20.70, 20.67, 20.65; ESI-HRMS (m/z) [M + H] + calcd for C 86 H 116 N 3 O 55 , 2070.6367, found,
	2070.6348.
	1:1 CH 3 OH-H 2 O (4 mL), CuSO 4 (20 mg, 0.12 mmol) and sodium ascorbate (40 mg, 0.20 mmol)
	was added. After stirring at room temperature for 10 h, the crude product was extracted with
	CH 2 Cl 2 . The organic layer was dried with Na 2 SO 4 and then filtered. The filtrate was evaporated
	and then purified by silica gel column chromatography (CH 2 Cl 2 /CH 3 OH= 20:1) to obtain
	compound 6 (70 mg, 45%). R f = 0.30 (eluent: ethyl acetate/CH 3 OH = 20:1). 1 H NMR (600 MHz,
	CDCl 3 ): δ 7.48 (s, 1H), 5.53 (d, J = 3.9 Hz, 1H), 5.37-5.21 (m, 6H), 5.17 (t, J = 7.8 Hz, 1H), 5.15
	(d, J = 3.9 Hz, 1H), 5.12-5.07 (m, 3H), 5.04 (d, J = 3.7 Hz, 1H), 5.03 (d, J = 3.8 Hz, 1H), 4.96 (d,
	J = 3.6 Hz, 1H), 4.91 (dd, J = 8.6, 4.0 Hz, 1H), 4.84-4.78 (m, 3H), 4.74 (dd, J = 7.4, 3.8 Hz, 1H),

4.72 (dd, J = 7.6, 3.6 Hz, 1H), 4.67 (br d, J = 12.5 Hz, 1H), 4.63 (dd, J = 14.8, 3.0 Hz, 1H), 4.59-4.51 (m, 4H), 4.49 (dd, J = 10.2, 3.6 Hz, 1H), 4.39 (br d, J = 11.6 Hz, 1H), 4.34-4.13 (m, 10H), 4.11 (br d, J = 9.5 Hz, 1H), 4.06 (m, 2H), 3.95-3.90 (m, 2H), 3.76-3.66 (m, 5H), 3.62 (t, J = 9.5

  29, 102.07, 101.93, 101.86, 101.83, 101.44, 83.16, 81.27, 81.09, 81.04, 80.65, 73.06, 73.02, 73.00, 72.79, 72.04, 72.02, 71.95, 71.89, 71.82, 71.80, 71.77, 71.69, 71.41, 70.70, 60.50, 60.31, 60.19, 60.12, 58.98, 51.12, 27.78; ESI-HRMS (m/z) [M + H] + calcd for C 46 H 76 N 3 O 35 , 1230.4254, found, 1230.4271.

Acknowledgments

We would like to thank Dr. Fuling Yin from the State Key Laboratory of Natural and Biomimetic Drugs, Peking University, for her assistance with the X-ray diffraction crystal analysis.

We gratefully acknowledge the financial support by the International Cooperation and Exchange

Program (NSFC-RFBR, grant number 82161148006) and the National Natural Science Foundation of China (grant nos. 21877007 and 91753202) and Shenzhen Bay Laboratory Start-up Fund (21230071).

Appendix A. Supplementary data

Full crystallographic details have been deposited with the Cambridge Crystallographic Data

Center. These data may be obtained on request from The Director, CCDC, 12 Road, Cambridge CB2 1EZ, UK (Tel.: +44-1223-336408; fax: +44-1223-336033; e-mail: deposit@ccdc.cam.ac.uk.1 or www: http://www.ccdc.cam.ac.uk). The other supplementary data related to this article can be found online at