## A MULTIVARIATE CLT FOR BOUNDED DECOMPOSABLE RANDOM VECTORS WITH THE BEST KNOWN RATE

Xiao Fang ∗

National University of Singapore

## Abstract

We prove a multivariate central limit theorem with explicit error bound in a non-smooth function distance for sums of bounded decomposable d -dimensional random vectors. The decomposition structure is similar to that of Barbour, Karo´ski and Ruci´ski (1989) and n n is more general than the local dependence structure considered in Chen and Shao (2004). The error bound is of the order d 1 4 n -1 2 , where d is the dimension and n is the number of summands. The dependence on d , namely d 1 4 , is the best known dependence even for sums of independent and identically distributed random vectors, and the dependence on n , namely n -1 2 , is optimal. We apply our main result to a random graph example.

Key words and phrases: Stein's method; multivariate normal approximation; non-smooth function distance; rate of convergence; random graph counting

AMS 2010 Subject Classification: 60F05

## 1 INTRODUCTION

Let W = 1 √ n ∑ n i =1 X i be a standardized sum of independent and identically distributed d -dimensional random vectors such that /BX ( X 1 ) = 0, Cov( X 1 ) = /C1 d and /BX ( | X 1 | 3 ) &lt; ∞ where /C1 d denotes the d -dimensional identity matrix and | · | denotes the Euclidean norm of a vector. Bentkus [5] proved the following bound on a non-smooth function distance between the distribution of W and the standard d -dimensional Gaussian distribution:

$$\sup _ { A \in \mathcal { A } } | \mathbb { P } ( W \in A ) - \mathbb { P } ( Z \in A ) | \leqslant C \mathbb { E } ( | X _ { 1 } | ^ { 3 } ) d ^ { \frac { 1 } { 4 } } n ^ { - \frac { 1 } { 2 } } & & ( 1. 1 ) \\ \text{lenotes the collection of all the convex sets in } \mathbb { R } ^ { d }, \, Z \text{ is a $d$-dimensional standard}$$

In this paper, we aim to prove a multivariate central limit theorem with an error bound having the same order of magnitude in terms of d and n for the same non-smooth function distance as in (1.1), but for general bounded dependent random vectors. The dependence structure we consider is similar to that of Barbour, Karo´ nski and Ruci´ski [4] n and is more general than the local where A denotes the collection of all the convex sets in /CA d , Z is a d -dimensional standard Gaussian vector, and C is an absolute constant.

∗ Department of Statistics and Applied Probability, Block S16, Level 7, 6 Science Drive 2, Faculty of Science, National University of Singapore, Singapore 117546

dependence structure considered in Chen and Shao [10]. The approach we use is the recursive approach in Stein's method for multivariate normal approximation.

Stein's method was introduced by Stein [18] for normal approximation and has become a powerful tool in proving distributional approximations. We refer to Barbour and Chen [3] for an introduction to Stein's method. Stein's method for multivariate normal approximation was first studied in G¨tze [13]. o Along with an inductive argument for sums of independent random vectors, he proved an error bound whose dependence on the dimension is d 3 2 for the distance in (1.1). The dependence on the dimension was improved to d 1 4 in Bentkus [5] (cf. (1.1)) and Bentkus [6] by using the same inductive approach and a Lindeberg-type argument. Using the recursive approach in Stein's method, Rinott and Rotar [17] proved a multivariate normal approximaton result for sums of bounded random vectors that allow for a certain decomposition. The error bound they obtained for the distance in (1.1) is typically of the order O d ( n -1 2 log n ) with unspecified dependence on d and an additional logarithmic factor. Recently, Fang and R¨llin [11] o proved a multivariate normal approximation result under the general framework of Stein coupling (cf. Chen and R¨ ollin [9]). For sums of locally dependent bounded random vectors, their bound for the distance in (1.1) is typically of the order d 7 4 n -1 2 . Compared with the existing literature on bounding the non-smooth function distance in (1.1) for multivariate normal approximation for sums of bounded random vectors, our new result not only applies to a decomposition structure more general than local dependence, but also obtains an error bound typically of the same order as for sums of independent and identically distributed random vectors in (1.1). Stein's method has also been used to prove smooth function distances for multivariate normal approximation under various dependence structures, see, for example, Goldstein and Rinott [12], Raiˇ [15], Chatterjee c and Meckes [7] and Reinert and R¨llin [16]. o

Many problems in random graph counting satisfy the decomposition structure considered in this paper. See, for example, Barbour, Karo´ski and Ruci´ski [4], n n Janson and Nowicki [14], Avram and Bertsimas [1], and Rinott and Rotar [17]. We will study an example from Rinott and Rotar [17] and show that the error bound obtained by our main theorem is better than that by Rinott and Rotar [17].

The paper is organized as follows. In the next section, we state our main result. In Section 3, we study a random graph counting problem. In Section 4, we prove our main result. Throughout this article, | · | denotes the Euclidean norm of a vector or the cardinality of a set, and /C1 d denotes the d -dimensional identity matrix. Define [ n ] := { 1 , . . . , n } and X N := ∑ i ∈ N X i for an index set N .

## 2 MAIN RESULTS

For a sum of standardized d -dimensional random vectors W = ∑ n i =1 X i with a certain decomposition structure, we aim to bound the quantity

$$d _ { c } \left ( \mathcal { L } ( W ), \mathcal { L } ( Z ) \right ) & = \sup _ { A \in \mathcal { A } } | \mathbb { P } ( W \in A ) - \mathbb { P } ( Z \in A ) |, & ( 2. 1 ) \\ \text{has standard } \underset { s \ \. } { d - \text{dimensional Gaussian distribution and } \mathcal { A } } \text{ denotes the collection of all }$$

/CA

where Z has standard d -dimensional Gaussian distribution and A denotes the collection of all the convex sets in d . The following is our main theorem.

Theorem 2.1. Let W = ∑ n i =1 X i be a sum of d -dimensional random vectors such that /BX ( X i ) = 0 and Cov( W ) = d . Suppose W can be decomposed as follows:

$$\ u n d \, \text{Ov} ( W ) = \mathbb { I } _ { d }. \, \text{Suppose W} \, \text{ can be decomposed as follows:} \\ \quad & \forall \, i \in [ n ], \, \exists \, i \in N _ { i } \subset [ n ] \text{ such that } W - X _ { N _ { i } } \text{ is independent of } X _ { i } ; \quad \quad ( 2. 2 ) \\ \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot$$

$$\forall \, i \in [ n ], j \in N _ { i }, \, \exists \, N _ { i } \subset N _ { i j } \subset [ n ] \ s u c h \, t h \, W - X _ { N _ { i j } } \ i s \, i n d e p e n d e n t \ o f \ \{ X _ { i }, X _ { j } \} ; \quad ( 2. 3 ) \\ \dots \ \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdots \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdoplus \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cd.$$

∀ i ∈ [ n , j ] ∈ N , k i ∈ N , ij ∃ N ij ⊂ N ijk ⊂ [ n ] such that W -X N ijk is independent of { X , X , X i j k } . (2.4)

Suppose further that for each i ∈ [ n , j ] ∈ N i and k ∈ N ij ,

$$| X _ { i } | \leqslant \beta, \ | N _ { i } | \leqslant n _ { 1 }, \ | N _ { i j } | \leqslant n _ { 2 }, \ | N _ { i j k } | \leqslant n _ { 3 }.$$

Then there is a universal constant C such that

$$d _ { c } ( \mathcal { L } ( W ), \mathcal { L } ( Z ) ) \leqslant C d ^ { 1 / 4 } n \beta ^ { 3 } n _ { 1 } ( n _ { 2 } + \frac { n _ { 3 } } { d } ),$$

where d c is defined as in (2.1) and Z is a d -dimensional standard Gaussian random vector.

Remark 2.2. Under the conditions of Theorem 2.1 but with Cov( W ) = Σ, by considering Σ -1 2 / W , we have

$$d _ { c } ( \mathcal { L } ( W ), \mathcal { L } ( \Sigma ^ { 1 / 2 } Z ) ) \leqslant C d ^ { 1 / 4 } n | | \Sigma ^ { - 1 / 2 } | | ^ { 3 } \beta ^ { 3 } n _ { 1 } ( n _ { 2 } + \frac { n _ { 3 } } { d } ),$$

where || Σ -1 2 / || is the operator norm of Σ -1 2 / .

Remark 2.3. The decomposition (2.2) and (2.3) is the same as that of Barbour, Karo´ski and n Ruci´ski [4], and, as observed there, is more general than the local dependence structure studied n in Chen [8] and later in Chen and Shao [10]. Condition (2.4) is a natural extension of the decomposition of Barbour, Karo´ski and Ruci´ski [4]. n n We need this extra condition to obtain the bound in (2.6).

Remark 2.4. As mentioned at the beginning of the Introduction, the dependence on the dimension d in (2.6) is the best known dependence even for sums of independent and identically distributed random vectors. In typical applications, β is of the order O n ( -1 2 ). From the decomposition (2.2)-(2.4), the neighborhood sizes n 2 and n 3 are typically of the same order as n 1 . On the other hand, in the local dependence structure studied in Chen [8] and Chen and Shao [10], quantities corresponding to n 2 and n 3 are typically of the order O n ( 2 1 ) and O n ( 3 1 ) respectively. Rinott and Rotar [17] proved a bound similar to (2.6) for a different decomposition structure. Their bound does not have explicit dependence on d and has an additional log n term. Recently, Fang and R¨ ollin [11] proved a general multivariate central limit theorem for the non-smooth function distance under the framework of Stein coupling (cf. Chen and R¨ ollin [9]) with boundedness conditions. Although their bound is more widely applicable, it does not yield optimal dependence on d and does not directly apply to the decomposition structure considered in this paper.

## 3 AN APPLICATION

Let n /greaterorequalslant 2 , m /greaterorequalslant 1 , d /greaterorequalslant 2 be positive integers. Consider a regular graph with n vertices and vertex degree m . Let N = nm/ 2 be the total number of edges. We color each vertex independently with one of the colors c i , 1 /lessorequalslant i /lessorequalslant d , with the probability of c i being π i , where ∑ d i =1 π i = 1. For i ∈ { 1 , . . . , d } , let W i be the number of edges connecting vertices both of color c i . Formally, with edges indexed by j ∈ { 1 , . . . , N } , we set

$$W _ { i } = \sum _ { j = 1 } ^ { N } X _ { j i },$$

where X ji is the indicator of the event that the edge j connects two vertices both of color c i . Let

$$W = ( W _ { 1 }, \dots, W _ { d } ) ^ { t }.$$

Let λ = ( W ), Σ = Cov( W ). It is known that

$$\lambda = ( N \pi _ { 1 } ^ { 2 }, \dots, N \pi _ { d } ^ { 2 } ) ^ { t },$$

/BX

and (cf. (3.1) of Rinott and Rotar [17])

$$\text{Var} ( W _ { i } ) = N \pi _ { i } ^ { 2 } ( 1 - \pi _ { i } ^ { 2 } ) + 2 N ( m - 1 ) ( \pi _ { i } ^ { 3 } - \pi _ { i } ^ { 4 } ), \\ \text{$\psi$ } \psi \psi$$

$$\begin{array} { c } \text{Cov} ( W _ { i }, W _ { j } ) = - N ( 2 m - 1 ) \pi _ { i } ^ { 2 } \pi _ { j } ^ { 2 }, & \text{for } i \neq j. \\ \cdot \quad, & \cdot \quad. \quad. \quad. \quad. \end{array}$$

/negationslash

We prove the following bound on the non-smooth function distance between the standardized distribution of W and the standard d -dimensional Gaussian distribution.

Proposition 3.1. Let W be defined as in (3.1) . Let λ and Σ be the mean and covariance matrix of W respectively. We have

$$d _ { c } ( \mathcal { L } ( \Sigma ^ { - 1 / 2 } ( W - \lambda ) ), \mathcal { L } ( Z ) ) \leqslant C d ^ { 7 / 4 } m ^ { 3 / 2 } L ^ { 3 } n ^ { - 1 / 2 }$$

where d c is defined as in (2.1) , Z is a d -dimensional standard Gaussian vector, C is an absolute constant, and

L

= [min

2

1 2

1

/lessorequalslant

i

/lessorequalslant

d

{

π

i

(1

-

π

i

)

}

]

-

/

.

Remark 3.2. Rinott and Rotar [17] proved an upper bound for the left-hand side of (3.2) as follows (cf. (3.2) of Rinott and Rotar [17]):

$$d _ { c } ( \mathcal { L } ( \Sigma ^ { - 1 / 2 } ( W - \lambda ) ), \mathcal { L } ( Z ) ) \leqslant c _ { d } m ^ { 3 / 2 } L ^ { 3 } ( | \log L | + \log n ) n ^ { - 1 / 2 },$$

where c d is an unspecified constant depending on d . Compared to (3.3), our bound in (3.2) has explicit dependence on d and does not have the logarithmic terms.

Proof of Proposition 3.1. Recall that

$$\Sigma ^ { - 1 / 2 } ( W - \lambda ) = \sum _ { j = 1 } ^ { N } \Sigma ^ { - 1 / 2 } \left ( ( X _ { j 1 }, \dots, X _ { j d } ) ^ { t } - ( \pi _ { 1 } ^ { 2 }, \dots, \pi _ { d } ^ { 2 } ) ^ { t } \right ) = \colon \sum _ { j = 1 } ^ { N } \xi _ { j }.$$

Observe that at most one of { X ,... , X j 1 jd } can be non-zero. Together with ∑ d i =1 π i = 1 and the fact that the elements of Σ -1 2 / are bounded in modulus by N -1 2 / L (cf. page 339 of Rinott and Rotar [17]), we have

$$| \xi _ { j } | \underset { \begin{array} { c } \cdot \cdot \cdot \cdot \end{array} } { \leqslant } 2 d ^ { 1 / 2 } N ^ { - 1 / 2 } L. \\ \cdot \cdot \cdot \cdot \cdot$$

Moreover, the summation ∑ N j =1 ξ j can be easily seen to satisfy the decomposition structure (2.2)-(2.4) with

$$| N _ { i } | \leqslant 2 m, \quad | N _ { i j } | \leqslant 3 m, \quad | N _ { i j k } | \leqslant 4 m. \\ \int _ { \alpha \, \iota \, \dots \, \iota \, \dots \, \iota \, \dots \, \iota \, \dots \, \iota \, \dots \, \iota \, \rangle \, \alpha \, \infty$$

By applying Theorem 2.1, we obtain the bound (3.2).

## 4 PROOF OF MAIN THEOREM

For given test function h , we consider the Stein equation

$$\Delta f ( w ) - w ^ { t } \nabla f ( w ) = h ( w ) - \mathbb { E } [ h ( Z ) ], \quad w \in \mathbb { R } ^ { d }, \quad \quad \quad ( 4. 1 ) \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

/BX /CA where ∆ denotes the Laplacian operator and ∇ the gradient operator. If h is not continuous (as for the indicator function of a convex set), then f is not smooth enough to apply Taylor's expansion to the necessary degree, so more refined techniques are necessary.

We follow the smoothing technique of Bentkus [5]. Recall that A is the collection of all the convex sets in d . For A ∈ A , let h A ( x ) = I A ( x ), and define the smoothed function

$$h _ { A, \varepsilon } ( w ) = \psi \left ( \frac { \text{dist} ( w, A ) } { \varepsilon } \right ),$$

/CA

where dist( w,A ) = inf v ∈ A | w - | v and

Define also

$$\Pi _ { v \in A } \left | w - v \right | \, \text{and} \\ \psi ( x ) = \begin{cases} 1, & x < 0, \\ 1 - 2 x ^ { 2 }, & 0 \leqslant x < \frac { 1 } { 2 }, \\ 2 ( 1 - x ) ^ { 2 }, & \frac { 1 } { 2 } \leqslant x < 1, \\ 0, & 1 \leqslant x. \end{cases} & & ( 4. 3 ) \\ \begin{matrix} - \lambda &. &. &. &. &. &. &. &. &. &. \end{matrix} ) \\ - \lambda &. &. &. &. &. &. &. &. \end{matrix}$$

$$A ^ { \varepsilon } = \{ x \in \mathbb { R } ^ { d } \, \colon \, \text{dist} ( x, A ) \leqslant \varepsilon \}, \quad A ^ { - \varepsilon } = \{ x \in A \, \colon \, \text{dist} ( x, \mathbb { R } ^ { d } \, \sum A ) > \varepsilon \} \\. \quad. \quad. \quad. \quad. \quad. \quad.. \quad..$$

/negationslash

/CA (note that in general ( A -ε ) ε = A ).

/CA

We will use the following lemmas in the proof of Theorem 2.1.

Lemma 4.1 (Lemma 2.3 of Bentkus [5]) . The function h A,ε as defined above has the following properties:

$$( i ) \ h _ { A, \varepsilon } ( w ) & = 1 \text{ for all } w \in A, \\ \Gamma _ { \colon \cdots } \ u _ { 1 } \ u _ { \cdots } \ u _ { 2 } \ u _ { 3 } \ u _ { 4 } \ u _ { 5 } \ u _ { 6 } \ u _ { 7 } \ u _ { 8 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 } \ u _ { 9 }$$

$$& \{ \imath \} \ h _ { A, \varepsilon } ( w ) = 0 \ J o r \ a l l \ w \in \mathbb { R } ^ { - } \ \, \sum \, A ^ { - }, \\ & ( i i i ) \ 0 \leqslant h _ { A, \varepsilon } ( w ) \leqslant 1 \ f o r \ a l l \ w \in A ^ { \varepsilon } \ \, \sum \, A, \\ & ( i v ) \ \, | \nabla h _ { A \, \varepsilon } ( w ) | \leqslant 2 \varepsilon ^ { - 1 } \ f o r \ a l l \ w \in \mathbb { R } ^ { d }.$$

$$& ( i i ) \ h _ { A, \varepsilon } ( w ) = 0 \text{ for all } w \in \mathbb { R } ^ { d } \, \sum A ^ { \varepsilon }, \\ & ( i i i \, \mathbb { N } < h \,. \, \mathbb { N } < 1 \text{ for all } w \, \subset \, \mathbb { A } ^ { \varepsilon } \, \sum \, \mathbb { A } & ( A \, \mathfrak { K } \, \mathfrak { K } )$$

$$( i v ) & \ | \nabla h _ { A, \varepsilon } ( w ) | \leqslant 2 \varepsilon ^ { - 1 } \text{ for all } w \in \mathbb { R } ^ { d }, \\ \int _ { \wedge \, \colon \, } \left | \tilde { \nu } \int _ { \wedge \, \colon \, } \left | \tilde { \wedge \, } \right | \tilde { \nu } \int _ { \wedge \, \colon \, } \left | \tilde { \wedge \, } \right | \cdots \int _ { \wedge \, } \left | \tilde { \nu } \right | \cdots \int _ { \wedge \, \colon \, } \left | \tilde { \nu } \right | \cdots \int _ { \wedge \, \colon \, } \right | \cdots \int _ { \wedge \, \colon \, } \right | \cdots \int _ { \wedge \, \colon \, } \right | \cdots \int _ { \wedge \, \colon \, } \right | \cdots \int _ { \wedge \, \colon \, } \right | \cdots \int _ { \wedge \, \colon \, }$$

/CA

$$\{ v ) & \ | \vee n _ { A, \varepsilon } [ w ) | \leqslant 2 \varepsilon \ ^ { \ } f o r \ a l l \ w \in \mathbb { R } ^ { \kappa }, \\ ( v ) & \ | \nabla h _ { A, \varepsilon } ( v ) - \nabla h _ { A, \varepsilon } ( w ) | \leqslant 8 | v - w | \varepsilon ^ { - 2 } \ f o r \ a l l \ v, w \in \mathbb { R } ^ { d }.$$

Lemma 4.2 (Ball [2], Bentkus [5]) . We have

$$\sup _ { A \in \mathcal { A } } \max \{ \mathbb { P } ( Z \in A ^ { \varepsilon } \, \sum A ), \mathbb { P } ( Z \in A \, \sum A ^ { - \varepsilon } ) \} \leqslant 4 d ^ { 1 / 4 } \varepsilon, \quad \ \ ( 4. 9 ) \\ \text{dependence on $d$ in $(4.9)$ is optimal.}$$

and the dependence on d in (4.9) is optimal.

Lemma 4.3 (Lemma 4.2 of Fang and R¨llin [11]) o . For any d -dimensional random vector W ,

$$d _ { c } ( \mathcal { L } ( W ), \mathcal { L } ( Z ) ) \leqslant 4 d ^ { 1 / 4 } \varepsilon + \sup _ { A \in \mathcal { A } } \left | \mathbb { E } [ h _ { A, \varepsilon } ( W ) ] - \mathbb { E } [ h _ { A, \varepsilon } ( Z ) ] \right |. \quad ( 4. 1 0 ) \\ \ n m a { 4. 4 } \ ( \text{Lemma 4.3 of Fang and } \text{R} \| \text{lin} \ [ 1 1 ] ). \text{ For each map } a \colon \{ 1, \dots, d \} ^ { k } \to \mathbb { R }, \, w e \, ha v e$$

$$\text{Lemma } 4. 4 \text{ (Lemma } 4. 3 \text{ of Fang and } R \delta \text{lin} \left [ 1 1 \right ] \text{.} & \text{ For each map } a \colon \{ 1, \dots, d \} ^ { k } \to \mathbb { R }, \, w e \, \text{have} \\ \int _ { \mathbb { R } ^ { d } } \left ( \sum _ { i _ { 1 }, \dots, i _ { k } = 1 } ^ { d } a ( i _ { 1 }, \dots, i _ { k } ) \frac { \varphi _ { i _ { 1 } \dots i _ { k } } ( z ) } { \varphi ( z ) } \right ) ^ { 2 } \varphi ( z ) d z \leqslant k! \sum _ { i _ { 1 }, \dots, i _ { k } = 1 } ^ { d } \left ( a ( i _ { 1 }, \dots, i _ { k } ) \right ) ^ { 2 }, \quad \text{ (4.11)} \\ \text{withor the } \lambda ( \nu ) \, \text{is the denoitu of } d \text{dimensional } \text{and} \text{normal distribution and normal distribution and notmal distribution and}$$

Lemma 4.4 (Lemma 4.3 of Fang and R¨llin [11]) o . For each map a : { 1 , . . . , d } k → , we have

/CA where ϕ z ( ) is the density of d -dimensional standard normal distribution and

$$\varphi _ { i _ { 1 } \dots i _ { k } } ( z ) = \partial ^ { k } \varphi ( z ) / ( \partial z _ { i _ { 1 } } \dots \partial z _ { i _ { k } } ).$$

Now fix ε and a convex set A ⊂ d . It can be verified directly that, defining the function

/CA

$$& \text{Now fix $\varepsilon$ and a convex set $A\subset\mathbb{R}^{d}$. It can be verified directly that, defining} \\ & g _ { A, \varepsilon } ( w, \tau ) = - \frac { 1 } { 2 ( 1 - \tau ) } \int _ { \mathbb { R } ^ { d } } \{ h _ { A, \varepsilon } ( \sqrt { 1 - \tau } w + \sqrt { \tau } z ) - \mathbb { E } [ h _ { A, \varepsilon } ( Z ) ] \} \varphi ( z ) d z, \\ & \text{the function} \\ & \quad. \. \. \ \, \quad \, \quad \, \quad \, \quad \, \quad \,.$$

$$f _ { A, \varepsilon } ( w ) = \int _ { 0 } ^ { 1 } g _ { A, \varepsilon } ( w, \tau ) d \tau$$

is a solution to (4.1) is (cf. G¨ otze [13]). In what follows, we keep the dependence on A and ε implicit and write g = g A,ε , f = f A,ε and h = h A,ε . For real-valued functions on /CA d we write f r ( x ) for ∂f x /∂x ( ) r , f rs ( x ) for ∂ f x / ∂x ∂x 2 ( ) ( r s ) and so forth. We also write g r ( w,τ ) = ∂g w,τ /∂w ( ) r and so on. Moreover, let ∇ g w, τ ( ) = ( g 1 ( w,τ , . . . , g ) d ( w,τ )) t and let ∆ g w, τ ( ) = ∑ d r =1 g rr ( w,τ ). Using this notation and the integration by parts formula, we have for 1 /lessorequalslant r, s, t /lessorequalslant d that

$$g _ { r s } ( w, \tau ) & = - \frac { 1 } { 2 \tau } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } w + \sqrt { \tau } z ) \varphi _ { r s } ( z ) d z \\ & = \frac { 1 } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } h _ { s } ( \sqrt { 1 - \tau } w + \sqrt { \tau } z ) \varphi _ { r } ( z ) d z$$

and

/CA

/CA

$$g _ { r s t } ( w, \tau ) & = \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } w + \sqrt { \tau } z ) \varphi _ { r s t } ( z ) d z \\ & = \frac { \sqrt { 1 - \tau } } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } h _ { j k } ( \sqrt { 1 - \tau } w + \sqrt { \tau } z ) \varphi _ { r } ( z ) d z.$$

Proof of Theorem 2.1. Fix A ∈ A and ε &gt; 0 (to be chosen later) and let f = f A,ε be the solution to the Stein equation (4.1) corresponding to h = h A,ε as defined by (4.2). Let

$$\kappa \coloneqq d _ { c } ( \mathcal { L } ( W ), \mathcal { L } ( Z ) ).$$

To avoid confusion, we will always use r, s, t to index the components of d -dimensional vectors. Define

$$W _ { i } \coloneqq W - X _ { N _ { i } }, \quad W _ { i j } \coloneqq W - X _ { N _ { i j } }, \quad W _ { i j k } \coloneqq W - X _ { N _ { i j k } }.$$

By assumption (2.2) and because ( X i ) = 0, we have

$$& - \mathbb { E } [ W ^ { t } \nabla g ( W, \tau ) ] = - \sum _ { r = 1 } ^ { d } \mathbb { E } [ ( W ) _ { r } g _ { r } ( W, \tau ) ] \\ & = - \sum _ { r = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \mathbb { E } [ ( X _ { i } ) _ { r } g _ { r } ( W, \tau ) ] = \sum _ { r = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \mathbb { E } \{ ( X _ { i } ) _ { r } [ g _ { r } ( W _ { i }, \tau ) - g _ { r } ( W, \tau ) ] \}. \\ \text{Here and subsequently, we use } ( X ) _ { r } \text{ to denote the rth component of a vector } X. \text{ By assumption} \\ ^ { 2 } \sum \text{and} \text{Cow} ( W ) = \mathbb { I }, \text{ we have } \nabla ^ { n } \. \. \. \ \mathbb { E } \{ ( X \cdot \cdot \cdot ) \cdot ( X \cdot \cdot \cdot \cdot ) \colon = \dots \text{ where } \delta \text{ denotes the Kronocker}$$

$$\text{tion } ( 2. 2 ) & \text{ and because } \mathbb { E } ( X _ { i } ) = 0, \, \text{we have} \\ - & \mathbb { E } [ W ^ { t } \nabla g ( W, \tau ) ] = - \sum _ { r = 1 } ^ { d } \mathbb { E } [ ( W ) _ { r } g _ { r } ( W, \tau ) ] \\ & \quad, \quad.$$

Here and subsequently, we use ( X ) r to denote the r th component of a vector X . By assumption (2.2) and Cov( W ) = /C1 d , we have ∑ n i =1 ∑ j ∈ N i /BX { ( X i ) r ( X j ) s } = δ rs where δ denotes the Kronecker delta. This implies that

Adding and subtracting the corresponding terms, and using (2.3), we have

$$\mathbb { E } [ \Delta g ( W, \tau ) ] = \mathbb { E } \{ \sum _ { r, s = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } ( \mathbb { E } [ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ] ) g _ { r s } ( W, \tau ) \}. \\ \text{and subtracting the corresponding terms, and using (2.3), we have}$$

$$\text{Adding and subtracting the corresponding terms, and using (2.3), we have } \\ = \mathbb { E } \{ \sum _ { r = 1 } ^ { d } \sum _ { i = 1 } ^ { n } ( X _ { i } ) _ { r } \left [ g _ { r } ( W _ { i }, \tau ) - g _ { r } ( W, \tau ) + \sum _ { s = 1 } ^ { d } \sum _ { j \in N _ { i } } ( X _ { j } ) _ { s } g _ { r s } ( W, \tau ) \right ] \} \\ + \mathbb { E } \{ \sum _ { r, s = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } ( \mathbb { E } [ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ] - ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ) [ g _ { r s } ( W, \tau ) - g _ { r s } ( W _ { i j }, \tau ) ] \} \\ = \colon R _ { 1 } ( \tau ) + R _ { 2 } ( \tau ). \\ \text{Taking } \alpha ( w. \tau ) = \alpha _ { A } \varepsilon ( w. \tau ) \text{ in (4.12). it follows from (4.1) and (4.13) that}$$

Taking g w, τ ( ) = g A,ε ( w,τ ) in (4.12), it follows from (4.1) and (4.13) that

$$\mathbb { E } [ h ( W ) ] - \mathbb { E } [ h ( Z ) ] = \int _ { 0 } ^ { 1 } ( R _ { 1 } ( \tau ) + R _ { 2 } ( \tau ) ) d \tau. & & ( 4. 1 7 ) \\ \mathfrak { n g } \, \text{we will first give an upper bound for } | \int _ { 0 } ^ { 1 } R _ { 1 } ( \tau ) d \tau |, \, \text{and then argue that an upper}$$

To estimate ∫ 1 0 R 1 ( τ ) dτ , we consider the cases ε 2 &lt; τ /lessorequalslant 1 and 0 &lt; τ /lessorequalslant ε 2 separately. For the first case, we use the first expression of g rs ( w,τ ) in (4.14), Taylor's expansion

In the following we will first give an upper bound for | ∫ 1 0 R 1 ( τ ) dτ | , and then argue that an upper bound for | ∫ 1 0 R 2 ( τ ) dτ | can be derived similarly.

$$f ( x + a ) - f ( x ) = \int _ { 0 } ^ { 1 } a ^ { t } \nabla f ( x + u a ) d u = \mathbb { E } \{ a ^ { t } \nabla f ( x + U a ) \}, \\ 7$$

and the integration by parts formula, and get

$$\int _ { \varepsilon ^ { 2 } } ^ { 1 } R _ { i _ { 1 } } ( \tau ) d \tau = \mathbb { E } \{ \sum _ { r, s = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { 1 } { 2 \tau } \int _ { \mathbb { R } ^ { d } } [ h ( \sqrt { 1 - \tau } ( W - U X _ { N _ { i _ { 1 } } } ) + \sqrt { \tau } z ) - h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] \\ & \times ( X _ { i _ { 1 } } ) _ { r } ( X _ { j } ) _ { s } \varphi _ { r s } ( z ) d z d \tau \} \\.$$

$$& \times \{ \mathcal { A } _ { i } \} _ { r } \{ \mathcal { A } _ { j } \} _ { s } \varphi _ { r s } \{ z \} a z a \tau \} \\ & = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U V X _ { N _ { i } } ) \\ & \quad \times U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \},$$

$$& \vdots _ { 1 } \overline { i = 1 } \, \overline { j \in N _ { i } } \, J _ { \varepsilon ^ { 2 } } \, \stackrel { 4 \pi } { \times } ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } \varphi _ { r s } ( z ) d z d \tau \} \\ & \vdots \, \overset { n } { \Xi } \, \underset { 1 } { \sum } \, \int ^ { 1 } \, \sqrt { 1 - \tau } \, \int \,, \, \longrightarrow$$

/CA × U X ( i ) r ( X j ) s ( X k ) t ϕ rst ( z dzdτ ) } , where U and V are independent random variables distributed uniformly on [0 1]. , By writing h ( √ 1 -τW + √ τz -√ 1 -τUV X N i ) as a sum of differences, and using the independence assumption (2.4), we have

$$\int _ { \varepsilon ^ { 2 } } ^ { 1 } R _ { 1 } ( \tau ) d \tau = R _ { 1, 1 } + R _ { 1, 2 } + R _ { 1, 3 } + R _ { 1, 4 }$$

$$R _ { 1, 1 } = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } \left [ h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U V X _ { N _ { i } } ) \\ - h ( \sqrt { 1 - \tau } W _ { i j k } + \sqrt { \tau } z ) \right ] U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \},$$

$$& \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \\ R _ { 1, 2 } = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } \{ \mathbb { E } [ h ( \sqrt { 1 - \tau } W _ { i j k } + \sqrt { \tau } z ) ] } \\ & \quad - \mathbb { E } [ h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \},$$

$$\| _ { r, \overline { s, t = 1 } } \| _ { i = 1 } \| _ { j, k \in N _ { i } } \| _ { J \varepsilon ^ { 2 } \left ( \overline { T } ^ { \vee ^ { \prime } } \right ) \right ) J \mathbb { R } ^ { d } } \| _ { \ } \\ - \| h ( \sqrt { 1 - \tau } W _ { i j k } + \sqrt { \tau } z ) \right ] U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \}, \\ d \quad \ n \quad \ e 1 \quad \overline { \tau } \right ) \left ( \frac { 1 } { 2 } \right ) \right ) \ e$$

$$\dot { \ r, \overline { s, t = 1 } } & \frac { 1 } { i = 1 } \frac { 1 } { j, k \in N _ { i } } \, J _ { \varepsilon ^ { 2 } } \, \frac { 2 \tau \nu / \nu } { \Lambda } \, \dot { \ J } \, \mathbb { R } ^ { d } \, \dot { \ } \\ & \quad - \, \mathbb { E } [ h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] \, \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \, \}, \\ \cdot \, \stackrel { d } { \longrightarrow } \, \stackrel { n } { \longrightarrow } \, \frac { 1 } { \Lambda } \, \left ( \cdots \, \right ) \, \right ) \, \right ) =.$$

$$- \, \mathbb { E } [ h ( \sqrt { 1 } - \tau W + \sqrt { \tau } z ) ] \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \}, \\ R _ { 1, 3 } = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } \left \{ \mathbb { E } [ h ( ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] } \\ \frac { - \, \cdot } { } - \,.$$

$$& \mathbb { E } [ h ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z ) ] \Big \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \Big \}, \\ & \underline { d } \ \underline { n } \ \, = \ \, r ^ { 1 } \,. \sqrt { 1 - \tau } \ \, r$$

$$R _ { 1, 3 } = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } \left \{ \mathbb { E } [ h ( ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] \\ - \mathbb { E } [ h ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z ) ] \right \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \right \}, \\ d \quad n \quad r ^ { 1 } \, \cdots / \frac { r } { 1 - \tau } \quad r$$

/CA × U X ( i ) r ( X j ) s ( X k ) t ϕ rst ( z dzdτ ) } ,

$$& - \mathbb { E } [ h ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z ) ] \} U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \}, \\ R _ { 1, 4 } = \mathbb { E } \{ & \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z ) \\ & \quad \times U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) d z d \tau \}, \\ - \,. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

where Z is an independent d -dimensional standard Gaussian random vector.

By the properties of h in (4.4) and (4.5), the boundedness condition (2.5) and the independence assumption (2.4),

$$\dots \dots \dots \dots \dots _ { r } \dots \dots \dots _ { \nu } \dots \dots _ { \nu } \dots \\ | R _ { 1, 1 } | & \leqslant \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 4 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } I ( d i s t ( \sqrt { 1 - \tau } W _ { i j k } + \sqrt { \tau } z, A ^ { \varepsilon } \sum A ) \leqslant \sqrt { 1 - \tau } n _ { 3 } \beta ) \\ & \quad \times | ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) | d z d \tau \}.$$

$$\overline { s, t = 1 } & \overline { i = 1 } \overline { j, k \in N _ { i } } \ J _ { \varepsilon ^ { 2 } } \ 4 \tau \nu / \varepsilon \ J _ { \mathbb { R } ^ { d } } \\ & \times \left | ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) \right | d z d \tau \right \}.$$

where

By the boundedness condition (2.5), the definition of κ in (4.16) and (4.9),

$$\text{oundedness condition (2.5), the definition of $\kappa$ in (4.16) and (4.9),} \\ \mathbb { E } & \mathbb { E } [ I ( d i s t ( \sqrt { 1 - \tau } W _ { i j k } + \sqrt { \tau } z, A ^ { \varepsilon } \Lambda ) \leqslant \sqrt { 1 - \tau } n _ { 3 } \beta ) ] \\ \leqslant \mathbb { E } [ I ( d i s t ( \sqrt { 1 - \tau } W + \sqrt { \tau } z, A ^ { \varepsilon } \Lambda ) \leqslant 2 \sqrt { 1 - \tau } n _ { 3 } \beta ) ] \\ \leqslant 4 d ^ { 1 / 4 } ( \frac { \varepsilon } { \sqrt { 1 - \tau } } + 4 n _ { 3 } \beta ) + 2 \kappa. \\ \text{Cauchy-Schwartz inequality, (4.11) and the boundedness condition (2.5),}$$

By the Cauchy-Schwartz inequality, (4.11) and the boundedness condition (2.5),

$$\int _ { \mathbb { R } ^ { d } } \sum _ { r, s, t = 1 } ^ { d } | ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r s t } ( z ) | d z \leqslant \sqrt { 6 } \beta ^ { 3 }.$$

$$| R _ { 1, 1 } | \leqslant C n \beta ^ { 3 } n _ { 1 } ^ { 2 } \frac { 1 } { \varepsilon } [ d ^ { 1 / 4 } ( \varepsilon + n _ { 3 } \beta ) + \kappa ].$$

/CA Therefore, using ∫ 1 ε 2 1 τ 3 / 2 dτ /lessorequalslant C 1 ε ,

Here and in the remainder of the proof, C denotes an absolute constant, which may differ from line to line.

By the same argument, | R 1 2 , | has the same upper bound as | R 1 1 , | . By the properties of h in (4.4) and (4.5), the definition of κ in (4.16), and (4.9),

$$& \text{By the properties of $h$ in $(4.4)$ and $(4.5)$, the definition of $\kappa$ in $(4.16)$, and $(4.9)$,} \\ & \mathbb { E } [ h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) - h ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z ) ] \\ & \leq \mathbb { E } [ I ( \sqrt { 1 - \tau } W + \sqrt { \tau } z \in A ^ { \varepsilon } ) - I ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z \in A ) ] \\ & = \mathbb { E } [ I ( \sqrt { 1 - \tau } W + \sqrt { \tau } z \in A ^ { \varepsilon } ) - I ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z \in A ^ { \varepsilon } ) + I ( \sqrt { 1 - \tau } Z + \sqrt { \tau } z \in A ^ { \varepsilon } \lambda ) ] \\ & \leq \kappa + 4 d ^ { 1 / 4 } \frac { \varepsilon } { \sqrt { 1 - \tau } }. \\ & \text{By the same lower bound and a similar argument as for $R_{1,1}$, we can bound $R_{1,3}$ by}$$

By the same lower bound and a similar argument as for R 1 1 , , we can bound R 1 3 , by

$$| R _ { 1, 3 } | \leqslant C n \beta ^ { 3 } n _ { 1 } ^ { 2 } \frac { 1 } { \varepsilon } ( d ^ { 1 / 4 } \varepsilon + \kappa ).$$

Using the first expression of g rst ( w,s ) in (4.15), we have

$$R _ { 1, 4 } = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } U \mathbb { E } [ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } ] g _ { r s t } ( Z, \tau ) d \tau \}. \\ \text{ver that, from (4.12)},$$

Observe that, from (4.12),

$$\text{Observe that, from } ( 4. 1 2 ), \\ \mathbb { E } [ g ( Z + w, \tau ) ] & = - \frac { 1 } { 2 ( 1 - \tau ) } \int _ { \mathbb { R } ^ { d } } \left \{ \mathbb { E } [ h ( \sqrt { 1 - \tau } ( Z + w ) + \sqrt { \tau } z ) ] - \mathbb { E } [ h ( Z ) ] \right \} \varphi ( z ) d z \\ & = - \frac { 1 } { 2 ( 1 - \tau ) } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } w + z ) \varphi ( z ) d z + \frac { 1 } { 2 ( 1 - \tau ) } \mathbb { E } [ h ( Z ) ] \\ & = - \frac { 1 } { 2 ( 1 - \tau ) } \int _ { \mathbb { R } ^ { d } } h ( x ) \varphi ( x - \sqrt { 1 - \tau } w ) d x + \frac { 1 } { 2 ( 1 - \tau ) } \mathbb { E } [ h ( Z ) ].$$

/CA

Differentiating with respect to w , w r s and w t , and evaluating at w = 0, we obtain

Now with (4.11) and (2.5),

$$\iota \sigma _ { P } \cos \chi \, \omega _ { r }, \omega _ { s } \, \Gamma _ { t }, \Gamma _ { \alpha } \cos \chi \, \omega _ { t }, \, \omega _ { \alpha } \cos \chi \, \omega _ { t } \, \\ \mathbb { E } [ g _ { r s t } ( Z, \tau ) ] & = \frac { \sqrt { 1 - \tau } } { 2 } \int _ { \mathbb { R } ^ { d } } h ( x ) \varphi _ { r s t } ( x ) d x. \\ \intertext { d ( 2. 5 ) } \, + \, \mathfrak { D } + \overline { > C _ { \alpha } \, \partial 3 \, \dots } 2$$

$$| R _ { 1, 4 } | \leqslant C n \beta ^ { 3 } n _ { 1 } ^ { 2 }. \quad \ \ \ \ \ ( 4. 2 1 ) \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

$$\mathbb { R } ^ { \cdot } \\ \beta ^ { 3 }$$

For the case 0 &lt; τ /lessorequalslant ε 2 , we use the second expression of g rs ( w,τ ) in (4.14) and the Taylor expansion

$$\text{expansion} \\ \int _ { 0 } ^ { \epsilon ^ { 2 } } R _ { 1 } ( \tau ) d \tau & = - \mathbb { E } \{ \sum _ { r, s = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } \int _ { 0 } ^ { \epsilon ^ { 2 } } \frac { 1 } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } [ h _ { s } ( \sqrt { 1 - \tau } ( W - U X _ { N _ { i } } ) + \sqrt { \tau } z ) \\ & \quad - h _ { s } ( \sqrt { 1 - \tau } W + \sqrt { \tau } z ) ] ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } \varphi _ { r } ( z ) d z d \tau \} \\ & = \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j, k \in N _ { i } } \int _ { 0 } ^ { \epsilon ^ { 2 } } \frac { \sqrt { 1 - \tau } } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } h _ { s t } ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U V X _ { N _ { i } } ) \\ & \quad \times U ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ( X _ { k } ) _ { t } \varphi _ { r } ( z ) d z d \tau \}, \\ \text{where we recall that } U \text{ and } V \text{ are independent random variables distributed uniformly on } [ 0, 1 ]. \\ \text{By } ( 4. 4 ), ( 4. 5 ), ( 4. 8 ), \text{and } ( 2. 5 ),$$

where we recall that U and V are independent random variables distributed uniformly on [0 1]. , By (4.4), (4.5), (4.8), and (2.5),

$$& \div _ { \mu } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ & \left | \int _ { 0 } ^ { \varepsilon ^ { 2 } } R _ { 1 } ( \tau ) d \tau \right | \leqslant \frac { 8 } { \varepsilon } \beta ^ { 2 } n _ { 1 } 2 \mathbb { E } \{ & \sum _ { r = 1 } ^ { d } \int _ { 0 } ^ { \varepsilon ^ { 2 } } \frac { \sqrt { 1 - \tau } } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } I ( d i s t ( \sqrt { 1 - \tau } W _ { i } + \sqrt { \tau } z, A ^ { \varepsilon } \lambda ) \leqslant \sqrt { 1 - \tau } n _ { 1 } \beta ) \\ & \quad \times U | ( X _ { i } ) _ { r } \varphi _ { r } ( z ) | d z d \tau \}. \\ & \text{Much as in } ( 4. 1 8 ),$$

Much as in (4.18),

$$\mathbb { E } [ I ( d i s t ( \sqrt { 1 - \tau } W _ { i } + \sqrt { \tau } z, A ^ { \varepsilon } \sum A ) \leqslant \sqrt { 1 - \tau } n _ { 1 } \beta ) ] \\ \leqslant \mathbb { E } [ I ( d i s t ( \sqrt { 1 - \tau } W + \sqrt { \tau } z, A ^ { \varepsilon } \sum A ) \leqslant 2 \sqrt { 1 - \tau } n _ { 1 } \beta ) ] \\ \leqslant 4 d ^ { 1 / 4 } ( \frac { \varepsilon } { \sqrt { 1 - \tau } } + 4 n _ { 1 } \beta ) + 2 \kappa. \\ \text{th (2.2)}, ( 2.5) \text{ and (4.11)}, we obtain$$

Together with (2.2), (2.5) and (4.11), we obtain

$$\left | \int _ { 0 } ^ { \varepsilon ^ { 2 } } R _ { 1 } ( \tau ) d \tau \right | & \leqslant C n \beta ^ { 3 } n _ { 1 } ^ { 2 } \frac { 1 } { \varepsilon } [ d ^ { 1 / 4 } ( \varepsilon + n _ { 1 } \beta ) + \kappa ], \\ ( 4. 1 9 ), \, ( 4. 2 0 ) \text{ and } ( 4. 2 1 ),$$

and hence, from (4.19), (4.20) and (4.21),

$$\left | \int _ { 0 } ^ { 1 } R _ { 1 } ( \tau ) d \tau \right | \leqslant C n \beta ^ { 3 } n _ { 1 } ^ { 2 } \frac { 1 } { \varepsilon } [ d ^ { 1 / 4 } ( \varepsilon + n _ { 3 } \beta ) + \kappa ].$$

Now we turn to bounding | ∫ 1 0 R 2 ( s ds ) | . Much as for R 1 ( s ),

$$\int _ { 0 } ^ { 1 } R _ { 2 } ( \tau ) d \tau = - \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } \sum _ { k \in N _ { i j } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U X _ { i j } ) \\ & \times ( X _ { k } ) _ { t } \{ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } - \mathbb { E } [ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ] \} \varphi _ { r s t } ( z ) d z d \tau \} \\ - \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } \sum _ { k \in N _ { i j } } \int _ { \frac { \varepsilon ^ { 2 } } { 2 } } \frac { \sqrt { 1 - \tau } } { 2 \sqrt { \tau } } \int _ { \mathbb { R } ^ { d } } h _ { s t } ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U X _ { N _ { i j } } ) \\ & \times ( X _ { k } ) _ { t } \{ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } - \mathbb { E } [ ( X _ { i } ) _ { r } ( X _ { j } ) _ { s } ] \} \varphi _ { r } ( z ) d z d \tau \} \\ \therefore U \, U \, \text{is a independent random variable distributed uniformly on } [ 0, 1 ]. \, By the same arguments
 \text{sed in bounding } | \, I _ { 1 } ^ { 1 } R _ { 1 } ( \tau ) d \tau |. \, \text{we have}$$

$$\int _ { 0 } ^ { 1 } R _ { 2 } ( \tau ) d \tau = - \mathbb { E } \{ \sum _ { r, s, t = 1 } ^ { d } \sum _ { i = 1 } ^ { n } \sum _ { j \in N _ { i } } \sum _ { k \in N _ { i j } } \int _ { \varepsilon ^ { 2 } } ^ { 1 } \frac { \sqrt { 1 - \tau } } { 2 \tau ^ { 3 / 2 } } \int _ { \mathbb { R } ^ { d } } h ( \sqrt { 1 - \tau } W + \sqrt { \tau } z - \sqrt { 1 - \tau } U X _ { N _ { i j } } )$$

/BX where U is a independent random variable distributed uniformly on [0 1]. , By the same arguments used in bounding | ∫ 1 0 R 1 ( τ ) dτ | , we have

By (4.10), (4.17), (4.22) and (4.23),

$$\left | \int _ { 0 } ^ { 1 } R _ { 2 } ( \tau ) d \tau \right | & \leqslant C n \beta ^ { 3 } n _ { 1 } n _ { 2 } \frac { 1 } { \varepsilon } [ d ^ { 1 / 4 } ( \varepsilon + n _ { 3 } \beta ) + \kappa ]. \\ ( 4. 1 7 ), ( 4. 2 2 ) \text{ and } ( 4. 2 3 ),$$

$$\kappa \leqslant 4 d ^ { 1 / 4 } \varepsilon + C n \beta ^ { 3 } n _ { 1 } n _ { 2 } \frac { 1 } { \varepsilon } [ d ^ { 1 / 4 } ( \varepsilon + n _ { 3 } \beta ) + \kappa ].$$

The final bound (2.6) is obtained by choosing ε = 2 Cnβ n n 3 1 2 for the same C as in (4.24), solving the recursive inequality (4.24) and observing that d /lessorequalslant nβ n 2 1 from Cov( W ) = d and (2.5).

/C1

## ACKNOWLEDGMENTS

This work is based on part of the author's Ph.D. thesis. He is grateful to his advisor, Louis H. Y. Chen, for his guidance. He would like to thank Adrian R¨llin for helpful discussions. o He would also like to thank the referees for their helpful comments and suggestions which have significantly improved the presentation of this paper. This paper was written under the financial support of NUS-Overseas Postdoctoral Fellowship from the National University of Singapore.

## REFERENCES

- [1] F. Avram and D. Bertsimas. On central limit theorems in geometrical probability. Ann. Appl. Probab. 3 , 1033-1046 (1993)
- [2] K. Ball. The reverse isoperimetric problem for Gaussian measure. Discrete Comput. Geom. 10 , 411-420 (1993)
- [3] A. D. Barbour and L. H. Y. Chen. An Introduction to Stein's method . Lecture Notes Series 4 , Institute for Mathematical Sciences, National University of Singapore, Singapore University Press and World Scientific (2005)
- [4] A. D. Barbour, M. Karo´ski and A. Ruci´ski. n n A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47 , 125-145 (1989)
- [5] V. Bentkus. On the dependence of the Berry-Esseen bound on dimension. J. Statist. Plann. Inference 113 , 385-402 (2003)

- [6] Bentkus, V. A Lyapunov type bound in R d . Theory Probab. Appl. 49 311-323 (2005)
- [7] S. Chatterjee and E. Meckes. Multivariate normal approximation using exchangeable pairs. ALEA Lat. Am. J. Probab. Math. Stat. 4 , 257-283 (2008)
- [8] L. H. Y. Chen. Two central limit problems for dependent random variables. 2. Wahrsch. Verw. Gebiete 43 , 223-243 (1978)
- [9] L. H. Y. Chen and A. R¨ ollin. Stein couplings for normal approximation. Preprint . Available at http://arxiv.org/abs/1003.6039 (2010)
- [10] L. H. Y. Chen and Q.-M. Shao. Normal approximation under local dependence. Ann. Probab. 32 , 1985-2028 (2004)
- [11] X. Fang and A. R¨llin. Rates of convergence for multivariate normal approximation with applications o to dense graphs and doubly indexed permutation statistics. To appear in Bernoulli . Available at http://arxiv.org/abs/1206.6586 (2014).
- [12] L. Goldstein and Y. Rinott. Multivariate normal approximations by Stein's method and size bias couplings. J. Appl. Probab. 33 , 1-17 (1996)
- [13] F. G¨ otze. On the rate of convergence in the multivariate CLT. Ann. Probab. 19 , 724-739 (1991)
- [14] S. Janson and K. Nowicki. The asymptotic distributions of generalized U -statistics with applications to random graphs. Probab. Theory Related Fields 90 , 341-375 (1991)
- [15] M. Raiˇ c. A multivariate CLT for decomposable random vectors with finite second moments. J. Theoret. Probab. 17 , 573-603 (2004)
- [16] G. Reinert and A. R¨llin. o Multivariate normal approximation with Stein's method of exchangeable pairs under a general linearity condition. Ann. Probab. 37 , 2150-2173 (2009)
- [17] Y. Rinott and V. Rotar. A multivariate CLT for local dependence with n -1 / 2 log n rate and applications to multivariate graph related statistics. J. Multivariate Anal. 56 , 333-350 (1996)
- [18] C. Stein. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Sixth Berkeley Symp. Math. Stat. Prob. 2 Univ. California Press. Berkeley, Calif., 583-602 (1972)
Xiao Fang
A multivariate CLT for bounded decomposable random vectors with the best known rate
We prove a multivariate central limit theorem with explicit error bound on a
non-smooth function distance for sums of bounded decomposable $d$-dimensional
random vectors. The decomposition structure is similar to that of Barbour,
Karo\'nski and Ruci\'nski (1989) and is more general than the local dependence
structure considered in Chen and Shao (2004). The error bound is of the order
$d^{\frac{1}{4}} n^{-\frac{1}{2}}$, where $d$ is the dimension and $n$ is the
number of summands. The dependence on $d$, namely $d^{\frac{1}{4}}$, is the
best known dependence even for sums of independent and identically distributed
random vectors, and the dependence on $n$, namely $n^{-\frac{1}{2}}$, is
optimal. We apply our main result to a random graph example.