# Correcting Convexity Bias in Function and Functional Estimate

Chao Ma  Department of Mathematics, Stanford University  Lexing Ying
Department of Mathematics, Stanford University

###### Abstract

A general framework with a series of different methods is proposed to improve
the estimate of convex function (or functional) values when only noisy
observations of the true input are available. Technically, our methods catch
the bias introduced by the convexity and remove this bias from a baseline
estimate. Theoretical analysis are conducted to show that the proposed methods
can strictly reduce the expected estimate error under mild conditions. When
applied, the methods require no specific knowledge about the problem except
the convexity and the evaluation of the function. Therefore, they can serve as
off-the-shelf tools to obtain good estimate for a wide range of problems,
including optimization problems with random objective functions or
constraints, and functionals of probability distributions such as the entropy
and the Wasserstein distance. Numerical experiments on a wide variety of
problems show that our methods can significantly improve the quality of the
estimate compared with the baseline method.

##  1 Introduction

In this paper, we study the problem of estimating function/functional values
when uncertainty exists on the input value. Specifically, let $F$ be a
function or functional, and $\Omega$ be its input domain. We want to estimate
$F(\mathbf{x}^{*})$ for some $\mathbf{x}^{*}\in\Omega$, while only having
access to a set of observations sampled from a probability distribution $\mu$
on $\Omega$ with $\mathbb{E}_{\mu}\mathbf{x}=\mathbf{x}^{*}$. Let
$\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}$ be the observations. By the
law of large numbers, the average of the observations,
$\bar{\mathbf{x}}:=(\mathbf{x}_{1}+\cdots+\mathbf{x}_{n})/n$, is close to
$\mathbf{x}$ when $n$ is large. Therefore, a straightforward estimate of
$F(\mathbf{x}^{*})$ is to use $F(\bar{\mathbf{x}})$. However, since $F$ is not
necessarily linear, biases may exist when $F(\bar{\mathbf{x}})$ is used as an
estimate. For example, when $F$ is convex, the Jensen’s inequality

$F(\mathbf{x}^{*})=F(\mathbb{E}\bar{\mathbf{x}})\leq\mathbb{E}F(\bar{\mathbf{x}})$

reveals positive bias when $F(\bar{\mathbf{x}})$ is used to estimate
$F(\mathbf{x}^{*})$. Taking into consideration the special properties of $F$
(such as convexity/concavity), it is possible to find estimate methods that
have less bias and outperform the straightforward estimate using the sample
average.

The function/functional value estimate problem appears in many applications,
such as the estimate of functionals of probability distributions (e.g.
expectation, entropy, distance etc) or the estimate of optimal value of
optimization problems with noisy constraints. Some of these problems have been
under investigation for a long time, with many methods proposed. For instance,
the James-Stein estimator of the expectation of Gaussian distributions [18,
12], the estimate of entropy [16, 25, 17, 9, 21, 19, 11], mutual information
[17, 14, 8, 15], other functionals of probability distributions [23, 13, 1,
10], etc. Besides, the estimate of the minimizers of quadratic functions has
also been studied in recent works [7, 6]. These works usually study a specific
class of problems and propose methods that perform well on these problems.
Besides methods, related theoretical analysis are also rich in the literature
[2, 13, 24, 4]. The works mentioned here are not meant to be comprehensive.
For more detailed discussion of the literature, readers can refer to the
reviews in [20, 17, 13]

In this work, instead, we propose a general framework that can improve the
estimate for all convex or concave functions/functionals. Our methods produce
improved estimate for $F(\mathbf{x}^{*})$ by estimating the bias introduced by
convexity/concavity using noisy observations and removing that bias from the
naive estimate $F(\bar{\mathbf{x}})$. Concretely, we either shift
$F(\bar{\mathbf{x}})$ by an appropriate amount $c$ and use
$F(\bar{\mathbf{x}})+c$ as a new estimate, or scale $F(\bar{\mathbf{x}})$ by a
factor $s$ and use $sF(\bar{\mathbf{x}})$ as a new estimate. These “debiasing
quantities” $c$ and $s$ are derived to minimize the square error of the
estimate, i.e.

$\mathbb{E}\big{(}F(\bar{\mathbf{x}})+c-F(\mathbf{x}^{*})\big{)}^{2}\ \
\textrm{or}\ \
\mathbb{E}\big{(}sF(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}^{2}.$

The so derived debiasing quantities $c$ and $s$ are in population sense, i.e.
they inevitably depend on unknown quantities such as $\mathbf{x}^{*}$ and
$\mathbb{E}F(\bar{\mathbf{x}})$. With only the observations
$\mathbf{x}_{1},\cdots\mathbf{x}_{n}$ in hand, we use bootstrap to approximate
these population debiasing quantities and obtain “empirical” debiasing
quantities $\hat{c}$ and $\hat{s}$ (See Section 2 for details). Theoretical
analysis are conducted to show that the $\hat{c}$ and $\hat{s}$ obtained using
bootstrap appropriately can indeed reduce the square error of the estimate. In
the following is an informal statement of our main theorems 2 and 3.

######  Theorem 1.

(Informal main theorem) Let $F$ be a convex function on $\Omega$ and $\mu$ be
a probability distribution on $\Omega$ with
$\mathbf{x}^{*}=\mathbb{E}_{\mu}\mathbf{x}$. Let $\hat{c}$ and $\hat{s}$ be
the shifting and scaling debiasing quantities computed using samples
$\mathbf{x}_{1},\cdots\mathbf{x}_{n}$ drawn from $\mu$. Under some assumptions
on $F$, $\mu$, and the bootstrap method, when $n$ is sufficiently large, we
have

$\mathbb{E}\big{(}F(\bar{\mathbf{x}})+\hat{c}-F(\mathbf{x}^{*})\big{)}^{2}<\mathbb{E}\big{(}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}^{2},$

and

$\mathbb{E}\big{(}\hat{s}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}^{2}<\mathbb{E}\big{(}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}^{2}.$

Besides the bootstrap method, other method can be employed to estimate the
debiasing quantities when more information of $F$ is available. One
“covariance estimate” method that makes use of $F$’s second-order curvature is
also introduced in Section 2.

Finally, extensive numerical experiments are conducted on a series of
problems, from simple convex functions, to optimization problems with
stochastic objective function and constrains, and then to the estimate of
entropy and Wasserstein distance of probability distributions. The same
framework is applied to all the problems, with the only difference being the
methods used to solve the problems themselves. In the experiments, our methods
can reduce both the expected bias and the expected square error by a
significant amount compared with the naive estimate. This shows that the
proposed framework can serve as a handy and convenient method to improve the
estimate of functions/functionals without requiring specific domain knowledge
except convexity/concavity.

##  2 Problem settings and methods

###  2.1 Problem settings

Without loss of generality, we introduce our method using convex functions on
Euclidean spaces. Let $F:\Omega\rightarrow\mathbb{R}$ be a convex function
with $\Omega\in\mathbb{R}^{d}$. Let $\mu$ be a probability distribution on
$\mathbb{R}^{d}$ that satisfies $\mathbb{E}_{\mu}\mathbf{x}=\mathbf{x}^{*}$.
Given noisy observations $\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}$
sampled i.i.d from $\mu$, our goal is to estimate $F(\mathbf{x}^{*})$ using
only the observations. As mentioned in the introduction, a naive estimate of
$F(\mathbf{x}^{*})$ is to use the function value at the sample average of the
observations, $F(\bar{\mathbf{x}})$, where
$\bar{\mathbf{x}}:=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$. When the function
$F$ is continuous at $\mathbf{x}^{*}$, this estimate is consistent. However,
bias exists due to convexity. By the Jensen’s inequality we have
$F(\mathbf{x}^{*})\leq\mathbb{E}F(\bar{\mathbf{x}})$, where the expectation is
taken over the sampling of $\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$. This bias
may be large if the curvature of $F$ is big or the number of available
observations $n$ is small. To reduce the convexity bias, we design methods to
correct the naive estimate $F(\bar{\mathbf{x}})$. We explore two possible ways
of changing $F(\bar{\mathbf{x}})$: the shifting method and the scaling method.
The shifting method takes an additive approach. We estimate a debiasing
quantity $c$, add it to $F(\bar{\mathbf{x}})$, and use $F(\bar{\mathbf{x}})+c$
as an improved estimate for $F(\mathbf{x}^{*})$. On the other hand, the
scaling method takes a multiplicative approach. We estimate another debiasing
quantity $s$, multiply it to $F(\bar{\mathbf{x}})$, and use
$sF(\bar{\mathbf{x}})$ as an improved estimate for $F(\mathbf{x}^{*})$. In the
following subsections we introduce the two methods in detail.

###  2.2 The shifting method

In the shifting method, we find an additive debiasing quantity $c$ such that
$F(\bar{\mathbf{x}})+c$ is a better estimate for $F(\mathbf{x}^{*})$ than
$F(\bar{\mathbf{x}})$. We measure the quality of the estimate using the
squared error

$\mathbb{E}\left(F(\bar{\mathbf{x}})+c-F(\mathbf{x}^{*})\right)^{2},$ (1)

and find $c$ to minimize (1). Treating $c$ as a constant and expanding (1), we
obtain a quadratic function of $c$,

$c^{2}+2c\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))+\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2},$

whose minimum is achieved at

$c=F(\mathbf{x}^{*})-\mathbb{E}F(\bar{\mathbf{x}}).$ (2)

Hence, ideally we can use the $c$ defined in (2) as the debiasing quantity.

In practise, however, $\mathbf{x}^{*}$ and $\mathbb{E}F(\bar{\mathbf{x}})$ are
unknown, and can only be approximated using noisy observation
$\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$. For general $F$ and $\mu$, we can use
bootstrap [5] to estimate the $c$ in (2). bootstrap uses a uniform
distribution on $\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$ to approximate $\mu$.
Denote $\mathcal{X}=\\{\mathbf{x}_{1},...,\mathbf{x}_{n}\\}$ and let
$\mu_{\mathcal{X}}$ be the uniform distribution on $\mathcal{X}$. For
$k=1,2,...,K$, define

$\tilde{\mathbf{x}}_{k}=\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{x}_{k,i},$ (3)

where $\\{\mathbf{x}_{k,i}\\}_{i=1}^{n}$ are i.i.d. sampled from
$\mu_{\mathcal{X}}$. Then, the empirical distribution of
$\\{\tilde{\mathbf{x}}_{k}\\}$ is an estimate of the distribution of
$\bar{\mathbf{x}}$. Hence, the shifting debiasing quantity $c$ can be
approximated by

$c=F(\mathbf{x}^{*})-\mathbb{E}F(\bar{\mathbf{x}})\approx
F\left(\frac{1}{K}\sum\limits_{k=1}^{K}\tilde{\mathbf{x}}_{k}\right)-\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k}).$

Since $\mathbb{E}_{\mu_{\mathcal{X}}}\tilde{\mathbf{x}}_{k}=\bar{\mathbf{x}}$,
we have $F(\bar{\mathbf{x}})\approx
F\big{(}\frac{1}{K}\sum\limits_{k=1}^{K}\tilde{\mathbf{x}}_{k}\big{)}$ when
$K$ is large. Therefore, we can use

$\hat{c}:=F(\bar{\mathbf{x}})-\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k}),$
(4)

as an approximation of $c$. With this definition of $\hat{c}$, the steps of
the shifting method with bootstrap is listed in Algorithm 1.

1

Input : A convex function $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$,
observations $\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\in\mathbb{R}^{d}$, $K$

Output : Debiased estimate $F(\bar{\mathbf{x}})+\hat{c}$

2

3$\bar{\mathbf{x}}\leftarrow\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{x}_{i}$;

4

5for  _$k\leftarrow 1$ to $K$_ do

6 Sample $\tilde{\mathbf{x}}_{k,1},\cdots,\tilde{\mathbf{x}}_{k,n}$ i.i.d.
from the uniform distribution on $\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$;

7

8
$\tilde{\mathbf{x}}_{k}\leftarrow\frac{1}{n}\sum\limits_{i=1}^{n}\tilde{\mathbf{x}}_{k,i}$

9 end for

10$\hat{c}\leftarrow
F(\bar{\mathbf{x}})-\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})$;

Algorithm 1 The Shifting Debiasing Method with bootstrap

##### The covariance estimate method

bootstrap is not the only approach to estimate the debiasing quantity $c$,
especially when more knowledge about the problem is available. For example,
when the distribution $\mu$ is concentrated in a region where $F$ is close to
a quadratic function, we can estimate $c$ by estimating the covariance of
$\mathbf{x}$. To see this, assume $F$ is close to its second Taylor polynomial
at $\mathbf{x}^{*}$, then for $F(\bar{\mathbf{x}})$ we have

$F(\bar{\mathbf{x}})\approx F(\mathbf{x}^{*})+\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})+\frac{1}{2}(\bar{\mathbf{x}}-\mathbf{x}^{*})^{T}\nabla^{2}F(\mathbf{x}^{*})(\bar{\mathbf{x}}-\mathbf{x}^{*}).$
(5)

Taking expectation, note that $\mathbb{E}(\bar{\mathbf{x}}-\mathbf{x}^{*})=0$,
we have

$\mathbb{E}\big{(}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}\approx\frac{1}{2}\mathbb{E}(\bar{\mathbf{x}}-\mathbf{x}^{*})^{T}\nabla^{2}F(\mathbf{x}^{*})(\bar{\mathbf{x}}-\mathbf{x}^{*})=\frac{1}{2}\operatorname{Tr}(\bar{C}\nabla^{2}F(\mathbf{x}^{*})),$

where $\bar{C}$ is the covariance matrix of $\bar{\mathbf{x}}$. Let $C$ be the
covariance of $\mathbf{x}$, then we have $\bar{C}=C/n$ and

$\mathbb{E}\big{(}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\big{)}\approx\frac{1}{2n}\operatorname{Tr}(C\nabla^{2}F(\mathbf{x}^{*})).$

Therefore, once we have some knowledge on $\nabla^{2}F(\mathbf{x}^{*})$, e.g.
having access to a matrix $H\approx\nabla^{2}F(\mathbf{x}^{*})$, we can obtain
an estimate of $c$ without using bootstrap:

$\displaystyle\hat{c}$
$\displaystyle=-\frac{1}{2n}\operatorname{Tr}\left(\frac{1}{n-1}\sum\limits_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}H\right)$
$\displaystyle=-\frac{1}{2n(n-1)}\sum\limits_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}H(\mathbf{x}_{i}-\bar{\mathbf{x}}).$
(6)

An algorithm using the covariance estimate method takes similar inputs and
outputs as Algorithm 1, replacing the bootstrap steps in line 2-6 by computing
the $\hat{c}$ in (6). We skip the step-by-step algorithm here.

###  2.3 The scaling method

The scaling method can be applied when $F$ is always positive (or negative)
for any $\mathbf{x}$. In this case, we find a multiplicative debiasing
quantity $s$ such that $sF(\bar{\mathbf{x}})$ becomes a good estimate for
$F(\mathbf{x}^{*})$. Still consider the squared error, which becomes

$\mathbb{E}\left(sF(\bar{\mathbf{x}})-F(\mathbb{E}\mathbf{x})\right)^{2}.$

Treating $s$ as a constant and minimizing the squared error as a quadratic
function of $s$ gives the following ideal choice of $s$:

$s=\frac{F(\mathbf{x}^{*})\mathbb{E}F(\bar{\mathbf{x}})}{\mathbb{E}F^{2}(\bar{\mathbf{x}})}.$
(7)

In practice, we can still use bootstrap to obtain an estimate of the $s$ in
(7). Recall the choice of $\\{\tilde{\mathbf{x}}_{k}\\}_{k=1}^{K}$ in (3).
Using the uniform distribution on $\\{\tilde{\mathbf{x}}_{k}\\}_{k=1}^{K}$ as
an approximation of $\mu$, and $\bar{\mathbf{x}}$ as an approximation of
$\mathbf{x}^{*}$, we can take

$\hat{s}:=\frac{F(\bar{\mathbf{x}})\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})}{\frac{1}{K}\sum\limits_{k=1}^{K}F^{2}(\tilde{\mathbf{x}}_{k})}=\frac{F(\bar{\mathbf{x}})\sum_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})}{\sum_{k=1}^{K}F^{2}(\tilde{\mathbf{x}}_{k})}.$
(8)

as an approximation of $s$. An algorithm using the scaling method is given in
Algorithm 2.

1

Input : A convex and positive function
$F:\mathbb{R}^{d}\rightarrow\mathbb{R}$, observations
$\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\in\mathbb{R}^{d}$, $K$

Output : Debiased estimate $\hat{s}F(\bar{\mathbf{x}})$

2 $\bar{\mathbf{x}}\leftarrow\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{x}_{i}$;

3

4for  _$k\leftarrow 1$ to $K$_ do

5 Sample $\tilde{\mathbf{x}}_{k,1},\cdots,\tilde{\mathbf{x}}_{k,n}$ i.i.d.
from the uniform distribution on $\mathbf{x}_{1},\cdots,\mathbf{x}_{n}$;

6

7
$\tilde{\mathbf{x}}_{k}\leftarrow\frac{1}{n}\sum\limits_{i=1}^{n}\tilde{\mathbf{x}}_{k,i}$

8 end for

9$\hat{s}\leftarrow\frac{F(\bar{\mathbf{x}})\sum_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})}{\sum_{k=1}^{K}F^{2}(\tilde{\mathbf{x}}_{k})}$;

Algorithm 2 The Scaling Debiasing Method with bootstrap

###  2.4 Dealing with functionals

The methods above can be easily applied to the cases where $F$ is a
convex/concave functional. Taking a functional of probability distribution,
$F[p]$, as an example. Suppose $p\in\mathcal{P}(\Omega)$ is a distribution on
$\Omega\in\mathbb{R}^{d}$ and $F$ is convex with respect to $p$. Such
functional can be the entropy of $p$, or the distance from $p$ to some other
probability distributions (e.g. the KL divergence, the Wasserstein distance).
Let $\mathbf{x}_{1},...,\mathbf{x}_{n}$ be points in $\Omega$ i.i.d. sampled
from $p$. Then, the Dirac delta distributions
$\delta_{\mathbf{x}_{1}},...,\delta_{\mathbf{x}_{n}}$ can be understood as
noisy observations of $p$. In this case, the naive estimate of $F[p]$ is
$F[\bar{p}]$, where $\bar{p}$ is the empirical distribution
$\bar{p}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\mathbf{x}_{i}}$. To estimate the
debiasing quantities with bootstrap, for $k=1,2,...,K$ and $i=,2,...,n$, let
$\mathbf{x}_{k,i}$ be i.i.d. samples taken uniformly from
$\\{\mathbf{x}_{1},...,\mathbf{x}_{n}\\}$, and let
$\tilde{p}_{k}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\mathbf{x}_{k,i}}.$ Then, for
the shifting method we can take

$\hat{c}=F[\bar{p}]-\frac{1}{K}\sum\limits_{k=1}^{K}F[\tilde{p}_{k}],$ (9)

and for the scaling method we can take

$\hat{s}=\frac{F[\bar{p}]\sum_{k=1}^{K}F[\tilde{p}_{k}]}{\sum_{k=1}^{K}F^{2}[\tilde{p}_{k}]}.$
(10)

##  3 Theoretical results

In this section, we provide theoretical results which show that our debiasing
methods can reduce the expected squared error of the estimate. In the
statement of the theorems, without loss of generality, we consider
$\mathbf{x}\in\mathbb{R}^{n}$ and $F$ as a convex function of $\mathbf{x}$. In
the theorems and the proofs, we use Einstein notations to represent tensor
contractions involving tensors with rank $\geq 3$. For some examples, if
$A,B\in\mathbb{R}^{d\times d}$ are matrices, $A_{ab}B^{bc}$ represents the
matrix product $AB$; if $A\in\mathbb{R}^{d\times d\times d\times d}$ and
$B\in\mathbb{R}^{d\times d}$, $A_{abcd}B^{cd}$ gives a $d\times d$ matrix by
contracting the last two dimensions of $A$ with the two dimensions of $B$; if
$F:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is a function and
$\mathbf{x}=(x^{1},\cdots,x^{d}),\bm{y}=(y^{1},\cdots,y^{d})\in\mathbb{R}^{d}$
are vectors, $\partial_{abc}^{3}F(\mathbf{x})y^{a}y^{b}y^{c}$ means the sum

$\sum\limits_{i,j,k=1}^{d}\frac{\partial^{3}F(\mathbf{x})}{\partial
x^{i}\partial x^{j}\partial x^{k}}y^{i}y^{j}y^{k}.$

We first make some assumptions on the input distribution $\mu$ and the
function $F$. In the following, the norm $\|\cdot\|$ is by default the
$\ell_{2}$ norm for vectors and matrices.

######  Assumption 1.

The probability distribution $\mu$ has up to 8-th finite moments.

######  Assumption 2.

$F$ is convex, and it has finite fourth-order derivatives.

Under the assumptions above, the following main result shows that the shifting
method can strictly reduce the expected squared error, as long as $K$ is at
least at the same order of $n$.

######  Theorem 2.

Suppose Assumption 1 and 2 hold. Consider the shifting debiasing method using
the debiasing quantity $\hat{c}$ defined in (4). Denote
$M_{2}=\mathbb{E}(\mathbf{x}-\mathbf{x}^{*})(\mathbf{x}-\mathbf{x}^{*})^{T}\in\mathbb{R}^{d\times
d}$, $M_{4}=\mathbb{E}(\mathbf{x}-\mathbf{x}^{*})^{\otimes
4}\in\mathbb{R}^{d\times d\times d\times d}$ be the second and fourth centered
moment tensors of $\mu$. Define

$\displaystyle\sigma_{1}$
$\displaystyle=\partial_{a}F(\mathbf{x}^{*})\partial_{b}F(\mathbf{x}^{*})(M_{2})^{ab}=\nabla
F(\mathbf{x}^{*})^{T}M_{2}\nabla F(\mathbf{x}^{*}),$ $\displaystyle\sigma_{2}$
$\displaystyle=\partial^{2}_{ab}F(\mathbf{x}^{*})(M_{2})^{ab}=\operatorname{Tr}(M_{2}\nabla^{2}F(\mathbf{x}^{*})),$
$\displaystyle\sigma_{3}$
$\displaystyle=\partial_{a}F(\mathbf{x}^{*})(M_{2})^{ab}\partial^{3}_{bcd}F(\mathbf{x}^{*})(M_{2})^{cd},$
$\displaystyle\sigma_{4}$
$\displaystyle=\partial^{2}_{ab}F(\mathbf{x}^{*})\partial^{2}_{cd}F(\mathbf{x}^{*})(M_{4})^{abcd}.$

Then, if $n$ is sufficiently large, $K\geq C_{K}n$ for some constant $C_{K}$,
and

$\frac{\sigma_{1}}{C_{K}}+\sqrt{\sigma_{1}\sigma_{4}}-\sigma_{3}\leq\frac{\sigma_{2}^{2}}{4},$
(11)

we have

$\mathbb{E}(F(\bar{\mathbf{x}})+\hat{c}-F(\mathbf{x}^{*}))^{2}<\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2},$
(12)

where the expectation is taken on both the sampling of
$\\{\mathbf{x}_{i}\\}_{i=1}^{n}$ and the bootstrap.

By the condition (11), our shifting method works when $\sigma_{2}$ is large
compared with $\sigma_{1}$ and $\sigma_{3}$, this happens when the second
derivative of $F$ is large compared with the its gradient at $\mathbf{x}^{*}$.
A sketch of the proof of the theorem is shown in the next subsection. The full
proof is provided in Section 6.

Next, we study the scaling method, and show a similar results as that for the
shifting method. For the ease of analysis, we make the following stronger
assumptions on $\mu$ and $F$:

######  Assumption 3.

The probability distribution $\mu$ has finite moment of all orders.

######  Assumption 4.

There exists a constant $B>0$, such that $F(\mathbf{x})\geq B$ for any
$\mathbf{x}$.

######  Remark 1.

Assumption 3 is made for the convenience of analysis. The “finite moment of
all orders” can be relaxed to finite moments up to a certain finite order. The
orders we need can be obtained by tracing the higher-order-terms in the proof
of Theorem 3 (given in Section 7).

Under the new assumptions, we have the following theorem whose proof is given
in Section 7.

######  Theorem 3.

Suppose Assumption 2, 3 and 4 hold. Consider the scaling debiasing method
using the debiasing quantity $\hat{s}$ defined in (8). Let $M_{2}$, $M_{4}$,
$\sigma_{1}$, $\sigma_{2}$, $\sigma_{3}$ be defined in the same as those in
Theorem 2. Define

$\sigma^{\prime}_{4}=\left(\nabla^{2}F(\mathbf{x}^{*})+\frac{2\nabla
F(\mathbf{x}^{*})\nabla
F(\mathbf{x}^{*})}{F(\mathbf{x}^{*})}\right)_{ab}\left(\nabla^{2}F(\mathbf{x}^{*})+\frac{2\nabla
F(\mathbf{x}^{*})\nabla
F(\mathbf{x}^{*})}{F(\mathbf{x}^{*})}\right)_{cd}(M_{4})^{abcd}.$

Then, if $n$ is sufficiently large, $K\geq C_{K}n$ for some constant $C_{K}$,
and

$\frac{\sigma_{1}}{C_{K}}+\sqrt{\sigma_{1}\sigma^{\prime}_{4}}-\sigma_{3}-\frac{4\sigma_{1}\sigma_{2}}{F(\mathbf{x}^{*})}+\frac{3\sigma_{1}^{2}}{F(\mathbf{x}^{*})^{2}}\leq\frac{\sigma_{2}^{2}}{4},$
(13)

we have

$\mathbb{E}(\hat{s}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}<\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2},$
(14)

where the expectation is taken on both the sampling of $\\{\mathbf{x}_{i}\\}$
and the bootstrap.

###  3.1 Proof sketch of Theorem 2

In this section, we show the idea of the proof for Theorem 2. The proof for
Theorem 3 takes a similar approach, with more involved analysis. As an
illustration, some arguments in this section might not be rigorous. Strict
proofs for both Theorem 2 and 3 are given in later sections.

##### Notations

In this proof sketch, we write $h=O(g)$ if there exists a constant $C$
independent with $n$ such that $|h|<C|g|$ always holds. We use
$\textrm{hot}(k)$ to denote higher-order-terms containing
$\bar{\mathbf{x}}-\mathbf{x}^{*}$ or (and)
$\tilde{\mathbf{x}}-\bar{\mathbf{x}}$ with total orders $\geq k$. Given
observations $\mathbf{x}_{1},...,\mathbf{x}_{n}$, we use $\tilde{\mathbf{x}}$
to denote the random variable given by the average of $n$ uniformly drawn
samples from $\mathbf{x}_{1},...,\mathbf{x}_{n}$. When taking expectation, we
use $\mathbb{E}$ to denote the expectation over both the sampling of
$\\{\mathbf{x}_{i}\\}$ and the choice of $\tilde{\mathbf{x}}$ during
bootstrap, and use $\mathbb{E}_{\tilde{\mathbf{x}}}$ to denote the expectation
over $\\{\tilde{\mathbf{x}}\\}$ based on a fixed set of
$\mathbf{x}_{1},...,\mathbf{x}_{n}$. Let
$H(\mathbf{x}):=\nabla^{2}F(\mathbf{x})$. For any positive semidefinite matrix
$A\in\mathbb{R}^{d\times d}$ and vector $\mathbf{x}\in\mathbb{R}^{d}$, denote
$\|\mathbf{x}\|^{2}_{A}=\mathbf{x}^{T}A\mathbf{x}$.

To prove Theorem 2, first notice that

$E(F(\bar{\mathbf{x}})+\hat{c}-F(\mathbf{x}^{*}))^{2}=\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}+\mathbb{E}\hat{c}^{2}+2\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}.$

Hence, we only need to show
$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}<0$.
Let

$\bar{c}=\mathbb{E}_{\tilde{\mathbf{x}}}\hat{c}=F(\bar{\mathbf{x}})-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}),\
\ \textrm{and}\
\delta=\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})-\frac{1}{K}\sum_{k=1}^{K}F(\tilde{\mathbf{x}}_{k}).$

Then, we have $\hat{c}=\bar{c}+\delta$ and
$\mathbb{E}_{\tilde{\mathbf{x}}}\delta=0$, and

$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}=\mathbb{E}\big{(}\bar{c}^{2}+2\bar{c}\delta+\delta^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\delta\big{)}.$

Since $\bar{c}$ and $F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})$ do not depend on
the sampling of $\tilde{\mathbf{x}}_{k}$, by the law of total expectation, we
have

$\mathbb{E}\bar{c}\delta=\mathbb{E}\left(\mathbb{E}_{\tilde{\mathbf{x}}}\bar{c}\delta\right)=\mathbb{E}\left(\bar{c}\mathbb{E}_{\tilde{\mathbf{x}}}\delta\right)=0,$

and similarly $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\delta=0$.
Therefore,

$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}=\mathbb{E}\big{(}\bar{c}^{2}+\delta^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}\big{)}.$
(15)

Among the three terms on the right hand side, $\mathbb{E}\bar{c}^{2}$ and
$\mathbb{E}\delta^{2}$ are positive. As an expected debiasing quantity,
$\bar{c}$ has a negative correlation with
$F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})$, hence
$2\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$ is negative. Next,
we will estimate the three terms, and show that under the condition 11 the
negative term $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$ has
larger absolute value than the first two terms. Hence, (15) is negative in
total.

#### Estimate of $\mathbb{E}\bar{c}^{2}$

Taking a Taylor expansion for $F(\tilde{\mathbf{x}})$ at $\bar{\mathbf{x}}$,
by Assumption 2, we have

$F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}})=\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6}\partial^{3}_{abc}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$

Taking expectation over $\tilde{\mathbf{x}}$, noting that
$\mathbb{E}_{\tilde{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})=0$, we
have

$-\bar{c}=\frac{1}{2}\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\textrm{hot}(3)=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\textrm{hot}(3).$
(16)

The second equality above follows the Lemma 2. Then, a Taylor expansion of
$H(\bar{\mathbf{x}})$ at $\mathbf{x}^{*}$ further gives

$\displaystyle-\bar{c}$
$\displaystyle=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})-H(\mathbf{x}^{*})}+\textrm{hot}(3)$
(17)
$\displaystyle=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+\frac{\textrm{hot}(1)}{n}+\textrm{hot}(3).$
(18)

In Lemma 6, we show that generally we have
$\mathbb{E}\textrm{hot}(k)=O(n^{-k/2})$. Also,
$\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\sim
O(n)$ (strictly speaking, we need to take the expectation of its square).
Therefore, from 18 we can obtain

$\mathbb{E}\bar{c}^{2}=\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+O(\frac{1}{n^{2.5}}).$

Finally, by showing

$\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}=\frac{\operatorname{Tr}(M_{2}H(\mathbf{x}^{*}))^{2}}{4n^{2}}+O(\frac{1}{n^{3}})=\frac{\sigma_{2}^{2}}{4n^{2}}+O(\frac{1}{n^{3}}),$

we have the following estimate for $\mathbb{E}\bar{c}^{2}$:

$\mathbb{E}\bar{c}^{2}=\frac{\sigma_{2}^{2}}{4n^{2}}+O(\frac{1}{n^{2.5}}).$
(19)

Note that the leading term in the estimate has order $O(\frac{1}{n^{2}})$.
This is also the leading term in all the following estimates. Finally we
compare the coefficients of the leading terms and complete the proof by
showing that the total coefficient is negative. The higher-order-terms
$O(\frac{1}{n^{2.5}})$ can be made sufficiently small when $n$ is sufficiently
large.

#### Estimate of $\mathbb{E}\delta^{2}$

First, we have

$\displaystyle\mathbb{E}\delta^{2}$
$\displaystyle=\mathbb{E}\left(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})-\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})\right)^{2}=\mathbb{E}\textrm{Var}_{\tilde{\mathbf{x}}}\left(\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})\right)=\frac{1}{K}\mathbb{E}\textrm{Var}_{\tilde{\mathbf{x}}}(F(\tilde{\mathbf{x}}))$
$\displaystyle=\frac{1}{K}\mathbb{E}\mathbb{E}_{\tilde{\mathbf{x}}}\big{(}F(\tilde{\mathbf{x}})-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2}\leq\frac{1}{K}\mathbb{E}\mathbb{E}_{\tilde{\mathbf{x}}}\big{(}F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}})\big{)}^{2}=\frac{1}{K}\mathbb{E}(F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}}))^{2}.$

Still using a Taylor expansion of $F(\tilde{\mathbf{x}})$ at
$\bar{\mathbf{x}}$, substituting $K=C_{K}n$, we have

$\mathbb{E}\delta^{2}\leq\frac{1}{C_{K}n}\mathbb{E}\left(\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}(2)\right)^{2}.$

Then, expanding $\nabla F(\bar{\mathbf{x}})$ at $\mathbf{x}^{*}$ gives

$\displaystyle\mathbb{E}\delta^{2}$
$\displaystyle\leq\frac{1}{C_{K}n}\mathbb{E}\left(\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}(2)\right)^{2}$
$\displaystyle=\frac{1}{C_{K}n}\left(\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}+\textrm{hot}(3)\right)$
$\displaystyle=\frac{1}{C_{K}n}\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}+O(\frac{1}{n^{2.5}}).$

By Lemma 2, we have

$\displaystyle\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}$
$\displaystyle=\frac{1}{n^{2}}\mathbb{E}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|_{\nabla
F(\mathbf{x}^{*})\nabla
F(\mathbf{x}^{*})^{T}}^{2}=\frac{1}{n}\mathbb{E}\|\mathbf{x}_{1}-\bar{\mathbf{x}}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}$
$\displaystyle=\frac{1}{n}\mathbb{E}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}+O(\frac{1}{n^{1.5}}).$

Therefore,

$\mathbb{E}\delta^{2}\leq\frac{\mathbb{E}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|_{\nabla
F(\mathbf{x}^{*})\nabla
F(\mathbf{x}^{*})^{T}}^{2}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}})=\frac{\sigma_{1}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}}).$
(20)

#### Estimate of $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$

A Taylor expansion of $F(\bar{\mathbf{x}})$ at $\mathbf{x}^{*}$ gives

$\displaystyle\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}=\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\bar{c}+\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}+\mathbb{E}\textrm{hot}(3)\bar{c}.$
(21)

For the third term on the right hand side of 21, recall that the estimate for
$\bar{c}$ gives $\mathbb{E}\bar{c}^{2}=O(\frac{1}{n^{2}})$, which implies
$\mathbb{E}\ \textrm{hot}(3)\bar{c}\leq O(\frac{1}{n^{2.5}})$ via the Cauchy-
Schwarz inequality.

For the second term, note that the leading term of $\bar{c}$ is negative, this
second term is negative. This term represents the goodness of the debiasing
quantity, and is used to offset all other positive terms, including
$\mathbb{E}\bar{c}^{2}$ and $\mathbb{E}\delta^{2}$. Specifically, by (18), we
have

$\displaystyle\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}$
$\displaystyle=-\frac{1}{4n^{2}}\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+O(\frac{1}{n^{2.5}}).$

Then, we show that

$\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}=\frac{1}{n^{2}}\left(\sum\limits_{i,j=1}^{n}\mathbb{E}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|_{H(\mathbf{x}^{*})}\right)^{2}+O(\frac{1}{\sqrt{n}})=\sigma_{2}^{2}+O(\frac{1}{\sqrt{n}}),$

(details in Section 6). Therefore, we have

$\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}=-\frac{\sigma_{2}^{2}}{4n^{2}}+O(\frac{1}{n^{2.5}}).$
(22)

The leading term of the estimate above has the same magnitude as the estimate
for $\mathbb{E}\bar{c}^{2}$. However, this negative part will take over
$\mathbb{E}\bar{c}^{2}$ given the factor $2$ before
$\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$.

Next, we consider the first term on the right hand side of 21. We need a finer
representation for $\bar{c}$. By Lemma 3, we can improve (16) into

$\displaystyle-\bar{c}$
$\displaystyle=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6n^{3}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\bar{\mathbf{x}})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c})+\textrm{hot}(3)$
$\displaystyle=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{\textrm{hot}(0)}{n^{2}}+\textrm{hot}(3).$
(23)

Taylor expansions of $H(\bar{\mathbf{x}})$ and $\nabla^{3}F(\bar{\mathbf{x}})$
at $\mathbf{x}^{*}$ further give

$\bar{c}=-\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}-\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c})+\frac{\textrm{hot}(0)}{n^{2}}+\textrm{hot}(3)$

Therefore,

$\displaystyle\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$
$\displaystyle=-\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}$
$\displaystyle\ \ \ -\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c})$
$\displaystyle\ \ \ +\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\left(\frac{\textrm{hot}(0)}{n^{2}}+\textrm{hot}(3)\right).$
(24)

The last term in (24) is obviously $O(\frac{1}{n^{2.5}})$. For the other two
terms, we have the following estimate (see the details in Section 6):

$-\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\leq\frac{\sqrt{\sigma_{2}\sigma_{4}}}{2n^{2}}+O(\frac{1}{n^{2.5}}),$
$-\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c})=-\frac{\sigma_{3}}{2n^{2}}+O(\frac{1}{n^{3}}).$

Altogether, we have

$\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\bar{c}\leq\frac{\sqrt{\sigma_{2}\sigma_{4}}-c_{3}}{2n^{2}}+O(\frac{1}{n^{2.5}}).$

And for $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\bar{c})$ we have

$\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\bar{c})\leq-\frac{\sigma_{2}^{2}}{4n^{2}}+\frac{\sqrt{\sigma_{2}\sigma_{4}}-c_{3}}{2n^{2}}+O(\frac{1}{n^{2.5}}).$
(25)

####  3.1.1 Putting together

Finally, combining the estimates (19), (20), and (25), we have

$\mathbb{E}\left(\bar{c}^{2}+\delta^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\bar{c})\right)\leq-\frac{\sigma_{2}^{2}}{4n^{2}}+\frac{\sigma_{1}}{C_{K}n^{2}}+\frac{\sqrt{\sigma_{2}\sigma_{4}}-c_{3}}{n^{2}}+O(\frac{1}{n^{2.5}}).$
(26)

The coefficient of $\frac{1}{n^{2}}$ is negative when condition 11 is
satisfied. This completes the proof.

##  4 Numerical experiments

In this section we show numerical results of the debiasing methods proposed in
Section 2. As a general framework of debiasing convex/concave functions, we
test our methods on a wide variety of problems ranging from simple convex
functions, optimization problems, to functionals of probability distributions.
Specifically, we test the following seven problems: (P1) Quadratic functions,
(P2) Fourth-order polynomials, (P3) Rational functions, (P4) Unconstrained
optimization problems with random objective functions, (P5) Constrained
optimization problems with random constraints, (P6) Entropy of discrete
probability distribution, (P7) Wasserstein distance between two probability
distributions. For all the problems, we apply both the shifting and scaling
methods using bootstrap. The covariance estimate method is tested on a subset
of problems for which it is easy to obtain an estimate of the Hessian at
$\mathbf{x}^{*}$.

###  4.1 P1: Quadratic functions

We consider simple multivariate quadratic functions

$F(\mathbf{x})=\mathbf{x}^{T}A\mathbf{x},$ (P1)

with $\mathbf{x}\in\mathbb{R}^{d}$ and $A\in\mathbb{R}^{d\times d}$ being a
positive definite matrix. Obviously, $F$ is a convex function with respect to
$\mathbf{x}$. As described in previous sections, given $A$ and a probability
distribution $\mu$ on $\mathbb{R}^{d}$ which satisfies
$\mathbb{E}_{\mu}\mathbf{x}=\mathbf{x}^{*}$, we estimate $F(\mathbf{x}^{*})$
using samples from $\mu$. The debiasing methods are tested for many different
$A$’s and $\mu$’s. For each $A$ and $\mu$, the experiment is repeated by
$R=1000$ times, and in each experiment we first sample a new set of noisy
observations and then run the debiasing methods.

To measure and compare the performance of our debiasing methods, we compute
the root mean squared error (RMSE) and the average bias of the estimates
across $1000$ experiments, and compare the values with that of the naive
estimate. Concretely, let $F_{\textrm{debias}}^{i}$ and
$F_{\textrm{naive}}^{i}$ be the estimate given by the debiasing method and the
naive method in the $i$-th experiment, respectively, we compute and compare
the following two relative quantities:

$\textrm{RMSE}_{r}=\frac{\sqrt{\sum_{i=1}^{1000}(F_{\textrm{debias}}^{i}-F(\mathbf{x}^{*}))^{2}}}{\sqrt{\sum_{i=1}^{1000}(F_{\textrm{naive}}^{i}-F(\mathbf{x}^{*}))^{2}}},\qquad\textrm{Bias}_{r}=\frac{\sum_{i=1}^{1000}(F_{\textrm{debias}}^{i}-F(\mathbf{x}^{*}))}{\sum_{i=1}^{1000}(F_{\textrm{naive}}^{i}-F(\mathbf{x}^{*}))}.$
(27)

By the definitions, when the debiasing method is effective, we expect
$\textrm{RMSE}_{r}\in[0,1)$ and $\textrm{Bias}_{r}\in(-1,1)$. The closer these
quantities are to zero, the more effective the debiasing method. These two
errors will also be studied in the experiments for other problems.

Before the debiasing methods are applied, a generic positive definite matrix
$A$ is generated by its eigenvalue decomposition. Concretely, we generate a
diagonal matrix $\Lambda$ with positive entries, and an orthogonal matrix $Q$,
and then let $A=Q\Lambda Q^{T}$. We take $\mu$ as an isotropic Gaussian
distribution centered at $\mathbf{x}^{*}$, i.e.
$\mu=N(\mathbf{x}^{*},\sigma^{2}I)$. The experiment results for (P1) are shown
in Figure 1 and 2. In the experiments, we study the performance of all the
three debiasing methods (shifting, scaling, covariance estimate) for problems
with different dimensions (Figure 1 left), different condition numbers of $A$
(Figure 1 middle), different noisy strength $\sigma$ (Figure 1 right), and
different norm of $\mathbf{x}^{*}$ (Figure 2 left). Throughout these
experiments, we take $n=10$ noisy observations of $\mathbf{x}^{*}$, and do
$K=10$ rounds of resampling when bootstrap is applied. The figures show that
the shifting debiasing method and the covariance estimate method can usually
significantly reduce the estimate error and bias, while the scaling method
does not perform as well when the dimension is large or the noise is strong.
The debiasing methods become less effective when the noise level is low or
$\|\mathbf{x}^{*}\|$ is large, in which case the noise observations are
(effectively) close to $\mathbf{x}^{*}$ and the naive estimate is already
good. The experiments on the condition number of $A$ show that our methods are
not sensitive to the spectrum of $A$. Here we remark that the covariance
estimate method performs especially well because the function $F$ is
quadratic, hence the Hessian matrix has all information about the function.

Figure 1: Experiment results for the quadratic function (P1). For all the
experiments shown in this figure, we take $n=K=10$ and
$\|\mathbf{x}^{*}\|^{2}=2$. (left) the relative RMSEs and biases for problems
with different dimension $d$, while we fix $\sigma=1$ and $\kappa=2$ ($\kappa$
is the condition number of $A$). (middle) results for problems with different
$\kappa$, while we fix $d=100$ and $\sigma=1$. (right) results for problems
with different $\sigma$, while we fix $d=100$ and $\kappa=2$.

For the bootstrap methods, we also study the number of resampling rounds $K$
required for different $n$. Results in Figure 2 show that a constant $K$ is
usually sufficient to approach best-achievable performance for any $n$. The
RMSE almost stops decreasing after $K\approx 50$ even when $n$ is much bigger.
This shows that our theories in Section 3 can potentially be improved.

Figure 2: (left) results for P1 with different norms of $\mathbf{x}^{*}$,
while we fix $d=100$, $\kappa=2$, and $\sigma=1$. (middle and right) Bootstrap
methods (shifting and scaling) for different $n$ and $K$. The middle panel
shows the results for the shifting method, and the right panel shows the
results for the scaling method. Results for different $n$ are shown in lines
with different colors. During the experiments we fix $d=100$, $\kappa=2$, and
$\sigma=1$.

###  4.2 P2: Fourth-order polynomials

We then consider a higher-order polynomial function given by

$F(\mathbf{x})=(\mathbf{x}^{T}A\mathbf{x})^{2},$ (P2)

where $\mathbf{x}\in\mathbb{R}^{d}$ and $A\in\mathbb{R}^{d\times d}$ is a
positive definite matrix. Compared with P1, this function has non-uniform
curvature. It is flat when $\mathbf{x}$ is small and grows fast when
$\mathbf{x}$ is large. In P2, we consider similar experiment settings as those
for $P1$. We test the methods against problems with different dimensions,
noise levels, and norms of $\mathbf{x}^{*}$. The results are shown in Figures
3. We see that for this problem only the scaling method performs well in most
cases. The covariance estimate method works when $\sigma$ and
$\|\mathbf{x}^{*}\|$ lie in specific ranges. The shifting method sometimes
even performs worse than the naive estimate. Experiments on the condition
number of $A$ still show that the methods are insensitive with $\kappa$. We
ignore the figure here.

Figure 3: Experiment results for the quadratic function (P2). For all the
experiments, we take $n=K=10$ and $\kappa=2$. (left) the relative RMSEs and
biases for problems with different dimension $d$, while we fix $\sigma=1$ and
$\|\mathbf{x}^{*}\|^{2}=2$. (middle) results for problems with different
$\sigma$, while we fix $d=100$ and $\|\mathbf{x}^{*}\|^{2}=2$. (right) results
for problems with different $\|\mathbf{x}^{*}\|$, while we fix $d=100$ and
$\sigma=1$.

###  4.3 P3: Rational functions

Next, we consider a rational function

$F(\mathbf{x})=\sum\limits_{i=1}^{d}\big{(}b_{i}x_{i}+\frac{c_{i}}{x_{i}}\big{)},$
(P3)

where $\mathbf{x}=(x_{1},...,x_{d})^{T}\in\mathbb{R}^{d}$ is the input and
$b_{i},c_{i}$, $i=1,2,...,d$ are positive numbers. This function is convex for
$x_{i}>0$, $i=1,...,d$. Hence, in the experiments, we take a coordinate-wise
exponential distribution as $\mu$. Fixing $n=K=10$, we test our methods on
problems with different dimensions, magnitudes of $c_{i}$, and
$\|\mathbf{x}^{*}\|$. Note that changing the magnitude of $b_{i}$ is
equivalent with changing $c_{i}$ in the opposite direction. Results in Figure
4 show that the three debiasing methods perform similarly. They become more
effective when the dimension of the problem increases. When $c$ is small or
$\mathbf{x}^{*}$ is large, the debiasing methods do not provide much
improvement compared with the naive estimate. This is because in these cases
the function is almost linear around $\mathbf{x}^{*}$ and the convexity bias
is small.

Figure 4: Experiment results for the rational function (P3). For all the
experiments, we keep $n=K=10$ and $\|\bm{b}\|=1$. (left) the relative RMSEs
and biases for problems with different dimension $d$, while we fix
$\|\bm{c}\|=1$ and $\|\mathbf{x}^{*}\|=2$. (middle) results for problems with
different $\|\bm{c}\|$, while we fix $d=100$ and $\|\mathbf{x}^{*}\|^{2}=2$.
(right) results for problems with different $\|\mathbf{x}^{*}\|$, while we fix
$d=100$ and $\|\bm{c}\|=1$.

###  4.4 P4: Unconstrained optimization problems

When the objective function is parameterized by a parameter vector, the
optimal value of some optimization problems is a convex or concave function of
the parameters. For instance, let $F(\alpha)$ be the optimal value of the
following minimization problem given some $\alpha\in\mathbb{R}^{d}$,

$\min_{\mathbf{x}}\alpha^{T}f(\mathbf{x})+g(\mathbf{x}),$ (28)

where $f:\mathbb{R}^{p}\rightarrow\mathbb{R}^{d}$,
$g:\mathbb{R}^{p}\rightarrow\mathbb{R}$ are functions of $\mathbf{x}$. Then,
$F$ is a concave function of $\alpha$ because it is the minimum of a family of
affine functions [3]. Therefore, our debiasing methods can be applied when we
are interested in the minimum value of (28) at $\alpha^{*}$ but can only get
access to its noisy observations.

In the experiments, we consider specifically the minimization of a quadratic
function when the Hessian of the objective function has some randomness, i.e.
the concave function we debias is

$F(A)=\min_{\mathbf{x}\in\mathbb{R}^{d}}\frac{1}{2}\mathbf{x}^{T}A\mathbf{x}+\bm{b}^{T}\mathbf{x},$
(P4)

where $A\in\mathbb{R}^{d\times d}$ is a positive definite matrix with
randomness, and $\bm{b}$ is a fixed vector. We easily have
$F(A)=-\frac{1}{2}\bm{b}^{T}A^{-1}\bm{b}$. Given a generic groundtruth Hessian
matrix $A^{*}=U\Lambda U^{T}$, where $U\Lambda U^{T}$ is the eigenvalue
decomposition of $A^{*}$ and
$\Lambda=\textrm{diag}(\lambda_{1},...,\lambda_{d})$, we generate noisy
observations of $A^{*}$ by sampling

$A\sim U\cdot\textrm{diag}(\xi_{1}\lambda_{1},...,\xi_{d}\lambda_{d})\cdot
U^{T},$

where $\xi_{1},...,\xi_{d}$ are independent random variables that follows the
gamma distribution with shape $k$ and scale $1/k$, whose density function is
$f(x)=\frac{k^{k}}{\Gamma(k)}x^{k-1}e^{-kx}$ and expectation is $1$. This
makes sure that all noisy observations are positive definite.

Fixing $n=10$ and $K=100$, Figure 5 shows the RMSEs and biases of the shifting
and scaling methods for different dimensions, condition numbers of $A^{*}$,
and the shape parameter $k$. Note that the actual dimension of the problem is
$d^{2}$. The results show that our methods are generally effective. The
methods perform better when the dimension is higher, or the condition number
of $A$ is not too large. When $k$ is small, i.e. the variance of the data
distribution is large, the shifting method does not work well, while the
scaling method keeps working well.

Figure 5: Experiment results for the rational function (P4). For all the
experiments, we keep $n=10$ and $K=100$. (left) the relative RMSEs and biases
for problems with different dimension $d^{2}$, while we fix $\kappa=2$ and
$k=1$. (middle) results for problems with different $\kappa$, while we fix
$d=100$ and $k=1$. (right) results for problems with different $k$, while we
fix $d=100$ and $\kappa=2$.

###  4.5 P5: Constrained optimization problem

Convex debiasing methods can also be applied to constrained optimization
problems with randomness. The randomness can appear on the constraints.
Consider

$\displaystyle\min_{\mathbf{x}}\ f(\mathbf{x})\ \ \ \ s.t.\
A\mathbf{x}=\bm{b}.$ (29)

Fixing $f$ and $A$, let $F(\bm{b})$ be the optimal value of (29) given
$\bm{b}$. Suppose strong duality holds, then

$F(\bm{b})=\min_{\mathbf{x}}\max_{\mu}f(\mathbf{x})+\mu^{T}(A\mathbf{x}-\bm{b})=\max_{\mu}\big{(}\mu^{T}\bm{b}+\max_{\mathbf{x}}(f(\mathbf{x})-\mu^{T}A\mathbf{x})\big{)},$

which shows that $F(\bm{b})$ is the maximum of affine functions of $\bm{b}$.
Therefore, $F$ is convex. The debiasing methods applies when we are interested
in the optimal value at some $\bm{b}^{*}$ while only its noisy observations
can be obtained.

In the experiments, we estimate

$F(\bm{b}^{*})=\arg\min_{\mathbf{x}}\ \mathbf{x}^{T}B\mathbf{x},\quad s.t.\
A\mathbf{x}=\bm{b},$ (P5)

where $\mathbf{x}\in\mathbb{R}^{p}$, $B\in\mathbb{R}^{p\times p}$ is a
positive definite matrix, $A\in\mathbb{R}^{d\times p}$, and
$\bm{b}\in\mathbb{R}^{d}$. Given $\bm{b}^{*}$, we take $\mu$ as an isotropic
Gaussian distribution centered at $\bm{b}^{*}$, i.e.
$\mu=N(\bm{b}^{*},\sigma^{2}I)$. Throughout the experiments, we fix $n=10$ and
$K=100$, and test the methods for different dimensions, ratio of $d/p$, and
noise level $\sigma$. Figure 6 shows the results. We see that both methods can
significantly reduce the bias and RMSE, while the shifting method usually
outperforms the scaling method. Better performance is achieved when $d$ is
large, $d$ is not too close to $p$, or $\sigma$ is large.

Figure 6: Experiment results for the constrained optimization problem (P5).
For all the experiments, we keep $n=10$, $K=100$, and $\|\bm{b}\|=1$. (left)
the relative RMSEs and biases for problems with different dimension $d$, while
we take $p=2d$. (middle) results for problems with different $d$ fixing
$p=100$. The horizontal axis is the ratio of $d$ and $p$. (right) results for
problems with different $\sigma$, while we fix $d=100$ and $p=200$.

###  4.6 P6: Entropy

Next, we test the estimate of entropy for discrete probability distributions,
i.e.

$H(p)=-\sum\limits_{i=1}^{n}p_{i}\ln p_{i},$ (P6)

where $p=(p_{1},...,p_{d})$ satisfies $p_{i}\geq 0$ and
$\sum_{i=1}^{d}p_{i}=1$. We generate the groundtruth distribution $p^{*}$ from
symmetric Dirichlet distribution with parameter $\alpha$. Noisy observations
of $p^{*}$ are the empirical distributions of single samples from $p^{*}$. In
the experiments, we fix $K=100$, and study the performance of the debiasing
methods for problems with different dimension $d$, $\alpha$, and the ratio of
$n$ and $d$.

For this problem, the covariance estimate method takes simple form. Let
$\bar{p}=(p_{1},p_{2},...,p_{d})$ be the average of noisy observations of
$p^{*}$. Then, the covariance matrix is
$\textrm{diag}(\bar{p})-\bar{p}\bar{p}^{T}$, and the Hessian of the entropy
functional (viewed as a function of vector $p$) is
$\textrm{diag}(-1/\bar{p})$. Hence, we have $\operatorname{Tr}(CH)=-(d-1)$,
and the debiased estimate is $H(\bar{p})+\frac{d-1}{2n}$. It is the same as
the classical debiasing scheme in [16].

The results are shown in Figure 7. For well-behaved problems, all three
methods perform similarly. They can all significantly reduce the bias and
error. When $\alpha$ is small, i.e. the distribution is sparse, or when $n$ is
small compared with $d$, the bootstrap methods perform better than the
covariance estimate method. We remark here that the experiments are part of
the effort to show the wide applicability of our methods. Many delicate
methods have been developed specifically for the entropy estimate problem, and
we do not expect our methods to outperform all of them on this specific
problem. Hence, we do not compare our methods with state-of-the-art methods
here.

Figure 7: Experiment results for the entropy estimate problem (P6). For all
the experiments, we keep $K=100$. (left) the relative RMSEs and biases for
problems with different dimension $d$, while we take $n=5d$ and $\alpha=1$.
(middle) results for problems with different $\alpha$ fixing $d=100$ and
$n=500$. (right) results for problems with different $n/d$, while we fix
$d=100$ and $\alpha=1$.

###  4.7 P7: Wasserstein distance

Finally, we estimate the 2-Wasserstein distance between a pair of
distributions ($p$, $q$) on $\mathbb{R}^{d}$, defined by

$W_{2}(p,q)^{2}=\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}\|\mathbf{x}-\bm{y}\|_{2}^{2}d\gamma(\mathbf{x},\bm{y}),$
(P7)

where $\gamma$ is a coupling of $p$ and $q$ whose two marginals are $p$ and
$q$, respectively. In the experiments, $p^{*}$ and $q^{*}$ are taken as
Gaussian distributions $N(\mu_{1},\sigma_{1}^{2}I)$ and
$N(\mu_{2},\sigma_{2}^{2}I)$, where $\mu_{1},\mu_{2}\in\mathbb{R}^{d}$ are two
vectors fixed for all trials. Noisy observations of $p^{*}$ and $q^{*}$ are
empirical distributions of i.i.d. samples of the distributions. The
Wasserstein distance between empirical distributions are computed by a linear
programming problem. Specifically, let $\hat{p}$ be an empirical distribution
on $\mathbf{x}_{1},...,\mathbf{x}_{n}$, $\hat{q}$ be an empirical distribution
on $\bm{y}_{1},...,\bm{y}_{m}$, $W(\hat{p},\hat{q})$ is given by the following
problem

$\min_{\gamma\in\mathbb{R}^{m\times
n}}\sum\limits_{i,j}\gamma_{ij}\|\mathbf{x}_{i}-\bm{y}_{j}\|^{2},\quad
s.t.\gamma\mathbf{1}=\frac{1}{m}\mathbf{1},\ \
\gamma^{T}\mathbf{1}=\frac{1}{n}\mathbf{1},$ (30)

where $\mathbf{1}$ denotes the all-one vector with proper size.

In the experiments, without loss of generality, we take $\mu_{1}=0$. We
consider $\sigma_{1}=\sigma_{2}=\sigma$, and fix $\sigma=1$, $K=50$. Figure 8
shows the results for problems with different dimension $d$, $\|\mu_{2}\|$,
and $n$. Results show that our methods can improve the naive estimate. The
improvement gets smaller when the dimension is higher. This might be caused by
the essential difficulty of estimating the Wasserstein distance in high
dimensional spaces [22].

Figure 8: Experiment results for the Wasserstein distance problem (P7). For
all the experiments, we keep $K=50$. (left) the relative RMSEs and biases for
problems with different dimension $d$, while we take $n=10$ and
$\|\mu_{2}\|=1$. (middle) results for problems with different $\|\mu_{2}\|$
fixing $d=5$ and $n=10$. (right) results for problems with different $n$,
while we fix $d=5$ and $\|\mu_{2}\|=1$.

##  5 Summary

In this work, we propose a general framework to correct the bias introduced by
convexity/concavity when estimating the value of functions or functionals. Our
methods do not require domain knowledge of the objective functions, and can be
applied as long as noisy observations of the groundtruth input are available.
Numerical experiments on a wide range of problems show the effectiveness of
our methods.

While our methods have general applicability, their performance may not be
optimal on specific problems. For example, extensive researches are conducted
on the estimate of entropy, and some proposed methods might have better
empirical or theoretical properties than our methods. We emphasize that the
value of our approach lies mostly on its generality—it can serve as an off-
the-shelf tool to debias the estimate of convex functions and obtain
improvement upon the naive estimate using the sample mean.

Nevertheless, the gain is not free—it comes with a price of additional
computational cost. Compared with the naive estimate, our methods with
bootstrap requires evaluating the function for multiple times. For some
applications, such as optimization problems, evaluating the function can be
expensive. Though, what to blame is not the methods, but the limited
observations and knowledge on the problem. This is the cost of generality. If
we have more domain knowledge, the covariance estimate method can be applied
without high computational cost.

##  6 Proof of Theorem 2

###  6.1 Notations.

In the proof, we write $h=O(g)$ if there exists a constant $C$ independent
with $n$ such that $|h|<C|g|$ always holds. When using these $O$ notations,
the dimension $d$ is treated as a constant. We use $\textrm{hot}(\cdot;\cdot)$
to denote higher-order-terms appearing in the Taylor expansion. Specifically,
for quantities $f_{1},\cdots,f_{k}$ and integer $r$,
$\textrm{hot}(f_{1},\cdots,f_{k};r)$ denotes (sum of) terms with form
$f_{1}^{r_{1}}\cdots f_{k}^{r_{k}}$ with $r_{1}+\cdots+r_{k}\geq r$. When
taking expectation, we use $\mathbb{E}$ to denote the expectation over both
the sampling of $\\{\mathbf{x}_{i}\\}$ and the sampling of
$\\{\tilde{\mathbf{x}}\\}$ during bootstrap, and use
$\mathbb{E}_{\tilde{\mathbf{x}}}$ to denote the expectation over the sampling
of $\\{\tilde{\mathbf{x}}\\}$ based on a fixed set of
$\mathbf{x}_{1},...,\mathbf{x}_{n}$. The norm $\|\cdot\|$ always means 2-norm.
We use $H(\mathbf{x})$ to denote the Hessian matrix of $F$ at $\mathbf{x}$,
i.e. $H(\mathbf{x})=\nabla^{2}F(\mathbf{x})$. For any positive semidefinite
matrix $A\in\mathbb{R}^{d\times d}$ and vector $\mathbf{x}\in\mathbb{R}^{d}$,
denote $\|\mathbf{x}\|^{2}_{A}=\mathbf{x}^{T}A\mathbf{x}$.

We use Einstein notations mostly when tensors with dimension $\geq 3$ are
involved. When only vectors and matrices are involved, we still use the
conventional matrix product notations. For vectors, we use superscript as the
index of entries, and subscript as the index of the vector in a set of
vectors. Entries are denoted by lower case letters. For example, the $i$-th
noisy observation vector is given by
$\mathbf{x}_{i}=(x^{1}_{i},x^{2}_{i},\cdots,x^{d}_{i})\in\mathbb{R}^{d}$.

###  6.2 Main proof

To prove the theorem, first notice that

$E(F(\bar{\mathbf{x}})+\hat{c}-F(\mathbf{x}^{*}))^{2}=\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}+\mathbb{E}\hat{c}^{2}+2\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}.$

Hence, we only need to show
$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}<0$.
Let

$\bar{c}=\mathbb{E}_{\tilde{\mathbf{x}}}\hat{c}=F(\bar{\mathbf{x}})-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}),\
\ \textrm{and}\
\delta=\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})-\frac{1}{K}\sum_{k=1}^{K}F(\tilde{\mathbf{x}}_{k}).$

Then, we have $\hat{c}=\bar{c}+\delta$ and
$\mathbb{E}_{\tilde{\mathbf{x}}}\delta=0$, and

$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}=\mathbb{E}\big{(}\bar{c}^{2}+2\bar{c}\delta+\delta^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\delta\big{)}.$

Note that $\bar{c}$ and $F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})$ do not depend
on the sampling of $\tilde{\mathbf{x}}_{k}$, by the law of total expectation,
we have

$\mathbb{E}\bar{c}\delta=\mathbb{E}\left(\mathbb{E}_{\tilde{\mathbf{x}}}\bar{c}\delta\right)=\mathbb{E}\left(\bar{c}\mathbb{E}_{\tilde{\mathbf{x}}}\delta\right)=0,$

and similarly $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\delta=0$.
Therefore,

$\mathbb{E}\big{(}\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c}\big{)}=\mathbb{E}\big{(}\bar{c}^{2}+\delta^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}\big{)}.$
(31)

Next, we estimate the three terms on the right hand side of (31) separately.
In the estimates below, we take $O(\frac{1}{n^{2}})$ terms as leading terms,
and show that there is no term with lower order.

####  6.2.1 Estimate of $\mathbb{E}\bar{c}^{2}$.

In the proof, we will extensively use the Taylor expansion of $F$ and its
derivatives. The results are given in Lemma 1. By the the Taylor expansion
(59) in Lemma 1, we have

$\small F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}})=\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6}\partial^{3}_{abc}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$

Taking expectation over $\tilde{\mathbf{x}}$, note that
$\mathbb{E}_{\tilde{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})=0$, we
have

$-\bar{c}=\frac{1}{2}\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6}\mathbb{E}_{\tilde{\mathbf{x}}}\partial^{3}_{abc}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$

According to Lemma 2 and 3, we have

$-\bar{c}=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6n^{3}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\bar{\mathbf{x}})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c})+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$

By the Taylor expansion (61) for $H$, for any vector
$\bm{y}\in\mathbb{R}^{d}$, we have

$\|\bm{y}\|_{H(\bar{\mathbf{x}})}^{2}=\|\bm{y}\|_{H(\mathbf{x}^{*})}^{2}+\partial^{3}_{abc}F(\mathbf{x}^{*})y^{a}y^{b}(\bar{x}^{c}-(x^{*})^{c})+O(\|\bm{y}\|^{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}).$

Therefore, for $\bar{c}$ we have

$\displaystyle-\bar{c}$
$\displaystyle=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c})$
$\displaystyle\ \ \
+O\left(\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}\right)+\frac{1}{6n^{3}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\bar{\mathbf{x}})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c})$
$\displaystyle\ \ \
+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$

Let

$\displaystyle c_{1}$
$\displaystyle=-\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c}),\quad
c_{2}=\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|_{2}^{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2},$
$\displaystyle c_{3}$
$\displaystyle=-\frac{1}{6n^{3}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\bar{\mathbf{x}})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c}),\quad\quad\
\
c_{4}=\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}.$

Then, we have

$\bar{c}=-\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+c_{1}+O(c_{2})+c_{3}+O(c_{4}),$
(32)

Hence, there exists a constant $C$ such that we have

$\bar{c}\geq-\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}-C(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|).$
(33)

By the Jensen’s inequality, $\bar{c}\leq 0$. Therefore, taking square and
expectation for (32), we obtain

$\displaystyle\mathbb{E}\bar{c}^{2}$
$\displaystyle\leq\mathbb{E}\frac{1}{4n^{4}}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+C^{2}\mathbb{E}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)^{2}$
$\displaystyle\ \ \ \
+\mathbb{E}\frac{C}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)$
$\displaystyle\leq\mathbb{E}\frac{1}{4n^{4}}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+C^{2}\mathbb{E}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)^{2}$
$\displaystyle\ \ \ \
+\frac{1}{2\sqrt{n}}\mathbb{E}\left(\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+\frac{\sqrt{n}}{2}C^{2}\mathbb{E}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)^{2}.$
(34)

Next, we give estimates to the terms in (34). We will use results in Lemma 6.
First, Letting $\lambda_{\max}$ be the largest eigenvalue of
$H(\mathbf{x}^{*})$, we have

$\displaystyle\mathbb{E}\left(\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}$
$\displaystyle\leq\frac{\lambda_{\max}^{2}}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\right)^{2}=O(\frac{1}{n^{2}}).$

Therefore,

$\frac{1}{2\sqrt{n}}\mathbb{E}\left(\frac{1}{2n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}=O(\frac{1}{n^{2.5}}).$
(35)

Next, for $\mathbb{E}c_{1}^{2}$, we have

$\displaystyle\mathbb{E}c_{1}^{2}$
$\displaystyle\leq\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(\bar{x}^{c}-(x^{*})^{c})\right)^{2}$
$\displaystyle\leq\frac{d^{3}\max\limits_{a,b,c}\partial_{abc}^{3}F(\mathbf{x}^{*})^{2}}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\right)^{2}$
$\displaystyle\leq\frac{d^{3}\max\limits_{a,b,c}\partial_{abc}^{3}F(\mathbf{x}^{*})^{2}}{4n^{4}}\sum\limits_{i,j=1}^{n}\mathbb{E}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\|\mathbf{x}_{j}-\bar{\mathbf{x}}\|^{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}$
$\displaystyle\leq\frac{d^{3}\max\limits_{a,b,c}\partial^{3}_{abc}F(\mathbf{x}^{*})^{2}}{4n^{4}}\sum\limits_{i,j=1}^{n}\left(\mathbb{E}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{6}\right)^{\frac{1}{3}}\left(\mathbb{E}\|\mathbf{x}_{j}-\bar{\mathbf{x}}\|^{6}\right)^{\frac{1}{3}}\left(\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{6}\right)^{\frac{1}{3}}$
$\displaystyle=\frac{d^{3}\max\limits_{i,j,k}\partial_{ijk}F(\mathbf{x}^{*})^{2}}{4n^{4}}\cdot
n^{2}O(\frac{1}{n})$ $\displaystyle=O(\frac{1}{n^{3}}),$ (36)

where the fourth to the fifth line is given by Lemma 6. Similarly, we can
obtain $\mathbb{E}c_{2}^{2}=O(\frac{1}{n^{4}})$. And by Lemma 7 and similar
derivations, we can obtain $\mathbb{E}c_{4}^{2}=O(\frac{1}{n^{4}})$. For
$c_{3}$, the Taylor expansion 62 gives

$\displaystyle|c_{3}|$
$\displaystyle=\left|\frac{1}{6n^{3}}\sum\limits_{i=1}^{n}\partial^{3}_{abc}F(\mathbf{x}^{*})(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c})+\frac{1}{6n^{3}}O(\sum\limits_{i=1}^{n}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{3})\right|$
$\displaystyle\leq\frac{d^{3}\max\limits_{a,b,c}\partial^{3}_{abc}|F(\mathbf{x}^{*})|}{6n^{3}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{3}+\frac{1}{6n^{3}}O(\sum\limits_{i=1}^{n}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{3}).$

Taking square and by Lemma 6 we have $\mathbb{E}c_{3}^{2}=O(\frac{1}{n^{4}})$.
Therefore, considering $(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)^{2}\leq
4(c_{1}^{2}+c_{2}^{2}+c_{3}^{2}+c_{4}^{2})$, back to (34) we have

$\mathbb{E}\bar{c}^{2}\leq\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+O(\frac{1}{n^{2.5}}).$
(37)

Next, by
$\mathbf{x}_{i}-\bar{\mathbf{x}}=(\mathbf{x}_{i}-\mathbf{x}^{*})+(\mathbf{x}^{*}-\bar{\mathbf{x}})$
we obtain

$\displaystyle\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\leq\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}+2\|\mathbf{x}_{i}-\mathbf{x}^{*}\|_{H(\mathbf{x}^{*})}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|_{H(\mathbf{x}^{*})}+\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}.$

Note that the terms with powers of $\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|$
become small quantities (no bigger than $O(\frac{1}{\sqrt{n}})$) after taking
expectation, we have

$\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}=\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+O(\frac{1}{n^{2.5}}).$

Thus,

$\mathbb{E}\bar{c}^{2}\leq\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}+O(\frac{1}{n^{2.5}}).$

Further notice that

$\displaystyle\frac{1}{4n^{4}}\mathbb{E}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\right)^{2}$
$\displaystyle=\frac{1}{4n^{4}}\sum\limits_{i,j=1}^{n}\mathbb{E}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\|\mathbf{x}_{j}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}$
$\displaystyle=\frac{1}{4n^{4}}\sum\limits_{i,j=1}^{n}\mathbb{E}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\mathbb{E}\|\mathbf{x}_{j}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}$
$\displaystyle\ \ \
+\frac{1}{4n^{4}}\sum\limits_{i=1}^{n}\mathbb{E}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{4}_{H(\mathbf{x}^{*})}-\big{(}\mathbb{E}\|\mathbf{x}_{i}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\big{)}^{2}$
$\displaystyle=\frac{1}{4n^{2}}\big{(}\mathbb{E}\|\mathbf{x}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\big{)}^{2}+O(\frac{1}{n^{3}}).$

Finally, since
$\mathbb{E}\|\mathbf{x}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}=\operatorname{Tr}(M_{2}H(\mathbf{x}^{*}))$,
we have the following estimate for $\mathbb{E}\bar{c}^{2}$:

$\mathbb{E}\bar{c}^{2}\leq\frac{\operatorname{Tr}(M_{2}H(\mathbf{x}^{*}))^{2}}{4n^{2}}+O(\frac{1}{n^{2.5}})=\frac{\sigma_{2}^{2}}{4n^{2}}+O(\frac{1}{n^{2.5}}).$
(38)

####  6.2.2 Estimate of $\mathbb{E}\delta^{2}$.

For $\mathbb{E}\delta^{2}$, first notice that

$\displaystyle\mathbb{E}\delta^{2}$
$\displaystyle=\mathbb{E}\left(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})-\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})\right)^{2}=\mathbb{E}\textrm{Var}_{\tilde{\mathbf{x}}}\left(\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})\right)=\frac{1}{K}\mathbb{E}\textrm{Var}_{\tilde{\mathbf{x}}}(F(\tilde{\mathbf{x}}))$
$\displaystyle=\frac{1}{K}\mathbb{E}\mathbb{E}_{\tilde{\mathbf{x}}}\big{(}F(\tilde{\mathbf{x}})-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2}\leq\frac{1}{K}\mathbb{E}\mathbb{E}_{\tilde{\mathbf{x}}}\big{(}F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}})\big{)}^{2}=\frac{1}{K}\mathbb{E}(F(\tilde{\mathbf{x}})-F(\bar{\mathbf{x}}))^{2}.$

Hence, taking the Taylor expansion for $F(\tilde{\mathbf{x}})$ at
$\bar{\mathbf{x}}$, the last term above gives

$\displaystyle\mathbb{E}\delta^{2}$
$\displaystyle\leq\frac{1}{C_{K}n}\mathbb{E}\left(\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}\right.$
$\displaystyle\ \ \
+\left.\frac{1}{6}\partial^{3}_{abc}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4})\right)^{2}$
$\displaystyle=\frac{1}{C_{K}n}\mathbb{E}\left(\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|)+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|)\right.$
$\displaystyle\ \ \
+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{3}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|)+\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2})$
$\displaystyle\ \ \
\left.+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2})+\frac{1}{6}\nabla^{3}F(\mathbf{x}^{*})[\tilde{\mathbf{x}}-\bar{\mathbf{x}}]+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{3})+O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4})\right)^{2}$
$\displaystyle=\frac{1}{C_{K}n}\left(\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}+\textrm{hot}(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|,\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|;3)\right).$
(39)

where the second equality follows from the Taylor expansions of $\nabla
F(\bar{\mathbf{x}})$, $H(\bar{\mathbf{x}})$, and
$\nabla^{3}F(\bar{\mathbf{x}})$ at $\mathbf{x}^{*}$. The highest-order terms
in
$\textrm{hot}(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|,\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|;3)$
have order $8$. Therefore, by Lemma 6 and 7, we have
$\mathbb{E}\textrm{hot}(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|,\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|;3)=O(\frac{1}{n^{1.5}})$,
and thus

$\displaystyle\mathbb{E}\delta^{2}\leq\frac{1}{C_{K}n}\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}+O(\frac{1}{n^{2.5}})=\frac{1}{C_{K}n}\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}+O(\frac{1}{n^{2.5}}).$

Next, by Lemma 2, we have

$\displaystyle\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}$
$\displaystyle=\frac{1}{n^{2}}\mathbb{E}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}$
$\displaystyle=\frac{1}{n}\mathbb{E}\|\mathbf{x}_{1}-\bar{\mathbf{x}}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}$
$\displaystyle=\frac{1}{n}\mathbb{E}\|\mathbf{x}_{1}-\mathbf{x}^{*}\|_{\nabla
F(\mathbf{x}^{*})\nabla F(\mathbf{x}^{*})^{T}}^{2}+O(\frac{1}{n^{1.5}}).$ (40)

Hence, $\mathbb{E}\delta^{2}$ can be bounded by:

$\mathbb{E}\delta^{2}\leq\frac{1}{C_{K}n^{2}}\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\mathbf{x}-\mathbf{x}^{*})\big{)}^{2}+O(\frac{1}{n^{2.5}})=\frac{\sigma_{1}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}}).$
(41)

####  6.2.3 Estimate of
$\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$

Taking Taylor expansion for $F$, we have

$\displaystyle\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$
$\displaystyle=\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})+\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}$
$\displaystyle\ \ \
+\frac{1}{6}\partial^{3}_{abc}F(\mathbf{x}^{*})(\bar{x}^{a}-(x^{*})^{a})(\bar{x}^{b}-(x^{*})^{b})(\bar{x}^{c}-(x^{*})^{c})+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{4})\big{)}\bar{c}$
$\displaystyle=\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\bar{c}+\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}+\mathbb{E}O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{3})\bar{c}$
(42)

We will estimate the three terms above using the estimate (32) for $\bar{c}$.

For the first term on the right hand side of (42), there exists a constant
$C$, such that

$\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\bar{c}$
$\displaystyle=\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\left(-\frac{1}{2n^{2}}\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+c_{1}+O(c_{2})+c_{3}+O(c_{4})\right)$
$\displaystyle\leq-\frac{1}{2n^{2}}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})c_{1}$ $\displaystyle\ \
+C\|\nabla
F(\mathbf{x}^{*})\|\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|(|c_{2}|+|c_{3}|+|c_{4}|).$
(43)

We first consider the first term on the right hand side of (43). For
convenience, let $\bm{z}_{i}=\mathbf{x}_{i}-\mathbf{x}^{*}$, and
$\bar{\bm{z}}=\bar{\mathbf{x}}-\mathbf{x}^{*}$. Then, we have
$\mathbb{E}\bm{z}_{i}=0$, and

$\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\sum\limits_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\bar{\mathbf{x}})=\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\sum\limits_{i=1}^{n}(\bm{z}_{i}-\bar{\bm{z}})^{T}H(\mathbf{x}^{*})(\bm{z}_{i}-\bar{\bm{z}}).$

For the right hand side, we have

$\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\sum\limits_{i=1}^{n}(\bm{z}_{i}-\bar{\bm{z}})^{T}H(\mathbf{x}^{*})(\bm{z}_{i}-\bar{\bm{z}})$
$\displaystyle=$ $\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\left(\sum\limits_{i=1}^{n}\bm{z}_{i}^{T}H(\mathbf{x}^{*})\bm{z}_{i}-n\bar{\bm{z}}^{T}H(\mathbf{x}^{*})\bar{\bm{z}}\right)$
$\displaystyle=$ $\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\frac{1}{n}\sum\limits_{i=1}^{n}\bm{z}_{i}\sum\limits_{i=1}^{n}\bm{z}_{i}^{T}H(\mathbf{x}^{*})\bm{z}_{i}-n\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\cdot\bar{\bm{z}}^{T}H(\mathbf{x}^{*})\bar{\bm{z}}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum\limits_{i,j=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\bm{z}_{j}^{T}H(\mathbf{x}^{*})\bm{z}_{j}-n\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\cdot\bar{\bm{z}}^{T}H(\mathbf{x}^{*})\bar{\bm{z}}.$
(44)

For the first term above, because of the independence of
$\bm{z}_{1},...,\bm{z}_{n}$ and $\mathbb{E}\bm{z}_{i}=0$, we have

$\displaystyle\left|\frac{1}{n}\sum\limits_{i,j=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\bm{z}_{j}^{T}H(\mathbf{x}^{*})\bm{z}_{j}\right|$
$\displaystyle=\left|\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\bm{z}_{i}^{T}H(\mathbf{x}^{*})\bm{z}_{i}\right|$
$\displaystyle=\big{|}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{1}\bm{z}_{1}^{T}H(\mathbf{x}^{*})\bm{z}_{1}\big{|}$
$\displaystyle\leq\sqrt{\mathbb{E}\big{(}\nabla
F(\mathbf{x}^{*})^{T}(\mathbf{x}_{1}-\mathbf{x}^{*})\big{)}^{2}\mathbb{E}\left((\mathbf{x}_{1}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{1}-\mathbf{x}^{*})\right)^{2}}$
$\displaystyle=\sqrt{\big{(}\nabla F(\mathbf{x}^{*})^{T}M_{2}\nabla
F(\mathbf{x}^{*})\big{)}\big{(}H(\mathbf{x}^{*})_{ab}H(\mathbf{x}^{*})_{cd}(M_{4})^{abcd}\big{)}}$
$\displaystyle=\sqrt{\sigma_{2}\sigma_{4}}.$ (45)

For the second term in (44), by Lemma 6 we have

$\displaystyle\big{|}n\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\cdot\bar{\bm{z}}^{T}H(\mathbf{x}^{*})\bar{\bm{z}}\big{|}$
$\displaystyle\leq
n\|F(\mathbf{x}^{*})\|\lambda_{\max}\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{3}=O(\frac{1}{\sqrt{n}}).$
(46)

Combining (45) and (46) gives

$\displaystyle-\frac{1}{2n^{2}}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}$
$\displaystyle\leq\frac{\sqrt{\sigma_{2}\sigma_{4}}}{2n^{2}}+O(\frac{1}{n^{2.5}}).$
(47)

Next, we consider the second term on the right hand side of (43). Using the
same $\bm{z}$ notations as above, we have

$\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})c_{1}$
$\displaystyle=-\frac{1}{2n^{2}}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\sum\limits_{i=1}^{n}\partial_{abc}^{3}F(\mathbf{x}^{*})(z_{i}^{a}-\bar{z}^{a})(z_{i}^{b}-\bar{z}^{b})\bar{z}^{c}.$

For the right hand side, we have

$\displaystyle-\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\sum\limits_{i=1}^{n}\partial_{abc}^{3}F(\mathbf{x}^{*})(z_{i}^{a}-\bar{z}^{a})(z_{i}^{b}-\bar{z}^{b})\bar{z}^{c}$
$\displaystyle=$ $\displaystyle-\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\sum\limits_{i=1}^{n}\partial_{abc}^{3}F(\mathbf{x}^{*})z_{i}^{a}z_{i}^{b}\bar{z}^{c}+n\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bar{\bm{z}}\partial_{abc}^{3}F(\mathbf{x}^{*})\bar{z}^{a}\bar{z}^{b}\bar{z}^{c}$
$\displaystyle=$
$\displaystyle-\frac{1}{n^{2}}\sum\limits_{i,j,k=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\big{(}\partial^{3}_{abc}F(\mathbf{x}^{*})z_{j}^{a}z_{j}^{b}z_{k}^{c}\big{)}+n\mathbb{E}\textrm{hot}(\bar{\bm{z}};4)$
$\displaystyle=$
$\displaystyle-\frac{1}{n^{2}}\sum\limits_{i,j,k=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\big{(}\partial^{3}_{abc}F(\mathbf{x}^{*})z_{j}^{a}z_{j}^{b}z_{k}^{c}\big{)}+O(\frac{1}{n}).$
(48)

By the independence of $\bm{z}_{i}$ and $\mathbb{E}\bm{z}_{i}=0$, we obtain

$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,j,k=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\big{(}\partial^{3}_{abc}F(\mathbf{x}^{*})z_{j}^{a}z_{j}^{b}z_{k}^{c}\big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,j=1}^{n}\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\big{(}\partial^{3}_{abc}F(\mathbf{x}^{*})z_{j}^{a}z_{j}^{b}z_{i}^{c}\big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,j=1}^{n}(\mathbb{E}\bm{z}_{i}^{T}\nabla
F(\mathbf{x}^{*})\bm{z}_{i})^{T}(\mathbb{E}\partial^{3}_{abc}F(\mathbf{x}^{*})z_{j}^{b}z_{j}^{c})$
$\displaystyle+\frac{1}{n^{2}}\sum\limits_{i=1}^{n}\left(\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}\bm{z}_{i}\partial_{abc}^{3}F(\mathbf{x}^{*})z_{i}^{a}z_{i}^{b}z_{i}^{c}-(\mathbb{E}\bm{z}_{i}^{T}\nabla
F(\mathbf{x}^{*})\bm{z}_{i})^{T}(\mathbb{E}\partial_{abc}^{3}F(\mathbf{x}^{*})z_{i}^{b}z_{i}^{c}\right)$
$\displaystyle=$ $\displaystyle(\mathbb{E}\bm{z}^{T}\nabla
F(\mathbf{x}^{*})\bm{z})^{T}(\mathbb{E}\partial_{abc}^{3}F(\mathbf{x}^{*})z^{b}z^{c})+O(\frac{1}{n})$
$\displaystyle=$ $\displaystyle(\nabla
F(\mathbf{x}^{*})^{T}M_{2})(\partial_{abc}^{3}F(\mathbf{x}^{*})(M_{2})^{bc})+O(\frac{1}{n})$
$\displaystyle=$ $\displaystyle\sigma_{3}+O(\frac{1}{n}).$ (49)

Therefore, we have

$\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})c_{1}=-\frac{\sigma_{3}}{2n^{2}}+O(\frac{1}{n^{3}}).$
(50)

For the third term in (43), recall that
$\mathbb{E}c_{2}^{2}=O(\frac{1}{n^{4}})$,
$\mathbb{E}c_{3}^{2}=O(\frac{1}{n^{4}})$, and
$\mathbb{E}c_{4}^{2}=O(\frac{1}{n^{4}})$, by Hölder’s inequality we have

$\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|(|c_{2}|+|c_{3}|+|c_{4}|)=O(\frac{1}{n^{2.5}}).$
(51)

Combining (47), (50), and (51), we have

$\displaystyle\mathbb{E}\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\bar{c}$
$\displaystyle\leq\frac{\sqrt{\sigma_{2}\sigma_{4}}-\sigma_{3}}{2n^{2}}+O(\frac{1}{n^{2.5}}).$
(52)

For the second term on the right hand side of (42), there exists a constant
$C$, such that

$\displaystyle\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}$
$\displaystyle\leq-\frac{1}{4n^{2}}\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}C\sum\limits_{i=1}^{4}|c_{i}|$
$\displaystyle=-\frac{1}{4n^{2}}\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\sum_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}+O(\frac{1}{n^{2.5}}),$
(53)

where the estimate of
$\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|_{H(\mathbf{x}^{*})}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)$
follows similarly the estimate of
$\frac{1}{2n^{2}}\mathbb{E}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}(|c_{1}|+|c_{2}|+|c_{3}|+|c_{4}|)$
when we deal with $\mathbb{E}\bar{c}^{2}$. For the first term on the right
hand side of (53), we have

$\displaystyle\mathbb{E}(\bar{\mathbf{x}}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\bar{\mathbf{x}}-\mathbf{x}^{*})\sum_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\bar{\mathbf{x}})$
$\displaystyle=$
$\displaystyle\mathbb{E}(\bar{\mathbf{x}}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\bar{\mathbf{x}}-\mathbf{x}^{*})\sum_{i=1}^{n}(\mathbf{x}_{i}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\mathbf{x}^{*})+O(\frac{1}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,j,k=1}^{n}\mathbb{E}(\mathbf{x}_{i}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{j}-\mathbf{x}^{*})(\mathbf{x}_{k}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{k}-\mathbf{x}^{*})+O(\frac{1}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,k=1}^{n}\mathbb{E}(\mathbf{x}_{i}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\mathbf{x}^{*})(\mathbf{x}_{k}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{k}-\mathbf{x}^{*})+O(\frac{1}{\sqrt{n}})$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\sum\limits_{i,k=1}^{n}\mathbb{E}(\mathbf{x}_{i}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\mathbf{x}^{*})\mathbb{E}(\mathbf{x}_{k}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{k}-\mathbf{x}^{*})+O(\frac{1}{\sqrt{n}})$
$\displaystyle=$ $\displaystyle\sigma_{2}^{2}+O(\frac{1}{\sqrt{n}}).$

Note that from the fourth to the fifth line we are moving terms with $i=k$
into the $O(\frac{1}{\sqrt{n}})$ term, and adding
$\frac{1}{n^{2}}\big{(}\mathbb{E}(\mathbf{x}_{i}-\mathbf{x}^{*})^{T}H(\mathbf{x}^{*})(\mathbf{x}_{i}-\mathbf{x}^{*})\big{)}^{2}$
terms, which are also no bigger than $O(\frac{1}{\sqrt{n}})$. Hence, back to
(53) we have

$\mathbb{E}\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{2}_{H(\mathbf{x}^{*})}\bar{c}\leq-\frac{\sigma_{2}^{2}}{4n^{2}}+O(\frac{1}{n^{2.5}}).$
(54)

For the third term on the right hand side of (42), recall that
$\mathbb{E}\bar{c}^{2}=O(\frac{1}{n^{2}})$, we have

$\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{3}\bar{c}\leq\sqrt{\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{6}\mathbb{E}\bar{c}^{2}}=O(\frac{1}{n^{2.5}}).$
(55)

Finally, combining (52), (54) and (55), we have

$\displaystyle\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\bar{c}$
$\displaystyle\leq-\frac{\sigma_{2}^{2}}{4n^{2}}+\frac{\sqrt{\sigma_{2}\sigma_{4}}-\sigma_{3}}{2n^{2}}+O(\frac{1}{n^{2.5}}).$
(56)

####  6.2.4 Putting together.

Finally, putting the estimates (38), (41), (56) together, we have

$\displaystyle\mathbb{E}(\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c})$
$\displaystyle\leq\frac{\sigma_{2}^{2}}{4n^{2}}+\frac{\sigma_{1}}{C_{K}n^{2}}-\frac{\sigma_{2}^{2}}{2n^{2}}+\frac{\sqrt{\sigma_{1}\sigma_{4}}}{n^{2}}-\frac{\sigma_{3}}{n^{2}}+O(\frac{1}{n^{2.5}})$
$\displaystyle=\frac{1}{n^{2}}\left(-\frac{\sigma_{2}^{2}}{4}+\frac{\sigma_{1}}{C_{K}}+\sqrt{\sigma_{1}\sigma_{4}}-\sigma_{3}\right)+O(\frac{1}{n^{2.5}}).$
(57)

By the condition (11), the coefficient for $\frac{1}{n^{2}}$ is negative.
Hence, when $n$ is sufficiently large, we have

$\mathbb{E}(\hat{c}^{2}+2(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))\hat{c})<0.$
(58)

This completes the proof.

###  6.3 Lemmas

In this section we provide and prove several lemmas used in the proof above.
These lemmas may also be used in the proof of Theorem 3.

The first lemma gives Taylor expansions for $F$ and its derivatives based on
Assumption 2. The results are standard in calculus, hence we ignore the proof.

######  Lemma 1.

Let $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be a function satisfying
Assumption 2. Then, for any $\mathbf{x},\bm{y}\in\mathbb{R}^{d}$, we have the
following Taylor expansions for $F$ and its derivatives:

$\displaystyle F(\bm{y})$ $\displaystyle=F(\mathbf{x})+\nabla
F(\mathbf{x})^{T}(\bm{y}-\mathbf{x})+\frac{1}{2}(\bm{y}-\mathbf{x})^{T}\nabla^{2}F(\mathbf{x})(\bm{y}-\mathbf{x})$
$\displaystyle\ \ \
+\frac{1}{6}\partial^{3}_{abc}F(\mathbf{x})(y^{a}-x^{a})(y^{b}-x^{b})(y^{c}-x^{c})+O(\|\bm{y}-\mathbf{x}\|^{4}),$
(59) $\displaystyle\nabla F(\bm{y})$ $\displaystyle=\nabla
F(\mathbf{x})+\nabla^{2}F(\mathbf{x})(\bm{y}-\mathbf{x})+\frac{1}{2}\partial^{3}_{abc}F(\mathbf{x})(y^{b}-x^{b})(y^{c}-x^{c})+O(\|\bm{y}-\mathbf{x}\|^{3}),$
(60) $\displaystyle\nabla^{2}F(\bm{y})$
$\displaystyle=\nabla^{2}F(\mathbf{x})+\partial^{3}_{abc}F(\mathbf{x})(y^{c}-x^{c})+O(\|\bm{y}-\mathbf{x}\|^{2}),$
(61) $\displaystyle\nabla^{3}F(\bm{y})$
$\displaystyle=\nabla^{3}F(\mathbf{x})+O(\|\bm{y}-\mathbf{x}\|).$ (62)

The next two lemmas deal with the expectation of quadratic forms and third
order monomials over the choice of $\tilde{\mathbf{x}}$.

######  Lemma 2.

Let $\nu$ be the uniform distribution on $n$ points
$\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}\in\mathbb{R}^{d}$, and
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}=\mathbb{E}_{\nu}\mathbf{x}$.
Let $\tilde{\mathbf{x}}$ be the empirical mean of $m$ samples i.i.d. sampled
from $\nu$, i.e.
$\tilde{\mathbf{x}}=\frac{1}{m}\sum_{i=1}^{m}\tilde{\mathbf{x}}_{i}$,
$\tilde{\mathbf{x}}_{i}\stackrel{{\scriptstyle iid}}{{\sim}}\nu$. Let
$A\in\mathbb{R}^{d\times d}$ be an arbitrary matrix. Then,

$\mathbb{E}_{\nu}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}-\bar{\mathbf{x}})=\frac{1}{nm}\sum\limits_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}A(\mathbf{x}_{i}-\bar{\mathbf{x}}).$

###### Proof.

We ignore the subscript $\nu$ in the expectation. Obviously, we have
$\mathbb{E}\tilde{\mathbf{x}}=\bar{\mathbf{x}}$ and
$\mathbb{E}\tilde{\mathbf{x}}_{i}=\bar{\mathbf{x}}$. Hence,

$\displaystyle\mathbb{E}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}-\bar{\mathbf{x}})$
$\displaystyle=\frac{1}{m^{2}}\sum\limits_{i,j=1}^{m}\mathbb{E}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}_{j}-\bar{\mathbf{x}})$
$\displaystyle=\frac{1}{m^{2}}\left(\sum\limits_{i=1}^{m}\mathbb{E}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})+\sum\limits_{i\neq
j}\mathbb{E}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}_{j}-\bar{\mathbf{x}})\right)$
$\displaystyle=\frac{1}{m^{2}}\sum\limits_{i=1}^{m}\mathbb{E}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}A(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})$
$\displaystyle=\frac{1}{m}\frac{1}{n}\sum\limits_{i=1}^{n}(\mathbf{x}_{i}-\bar{\mathbf{x}})^{T}A(\mathbf{x}_{i}-\bar{\mathbf{x}}).$

∎

######  Lemma 3.

Let $\nu$ be the uniform distribution on $n$ points
$\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}\in\mathbb{R}^{d}$, and
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}=\mathbb{E}_{\nu}\mathbf{x}$.
Let $\tilde{\mathbf{x}}$ be the empirical mean of $m$ samples i.i.d. sampled
by $\nu$, i.e.
$\tilde{\mathbf{x}}=\frac{1}{m}\sum_{i=1}^{m}\tilde{\mathbf{x}}_{i}$,
$\tilde{\mathbf{x}}_{i}\stackrel{{\scriptstyle iid}}{{\sim}}\nu$. Let
$T\in\mathbb{R}^{d\times d\times d}$ be an arbitrary $d\times d\times d$
tensor. Then,

$\mathbb{E}_{\nu}T_{abc}(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})=\frac{1}{m^{2}n}\sum\limits_{i=1}^{n}T_{abc}(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c}).$

###### Proof.

The proof is similar to that of Lemma 2. Still ignore the subscript $\nu$ in
the expectation. We have

$\displaystyle\mathbb{E}T_{abc}(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})$
$\displaystyle=\mathbb{E}T_{abc}\left(\frac{1}{m}\sum\limits_{i=1}^{m}\tilde{x}^{a}_{i}-\bar{x}^{a}\right)\left(\frac{1}{m}\sum\limits_{i=1}^{m}\tilde{x}^{b}_{i}-\bar{x}^{b}\right)\left(\frac{1}{m}\sum\limits_{i=1}^{m}\tilde{x}^{c}_{i}-\bar{x}^{c}\right)$
$\displaystyle=\frac{1}{m^{3}}\sum\limits_{i,j,k=1}^{m}\mathbb{E}T_{abc}(\tilde{x}^{a}_{i}-\bar{x}^{a})(\tilde{x}^{b}_{j}-\bar{x}^{b})(\tilde{x}^{c}_{k}-\bar{x}^{c})$
$\displaystyle=\frac{1}{m^{3}}\sum\limits_{i=1}^{m}\mathbb{E}T_{abc}(\tilde{x}^{a}_{i}-\bar{x}^{a})(\tilde{x}^{b}_{i}-\bar{x}^{b})(\tilde{x}^{c}_{i}-\bar{x}^{c})$
$\displaystyle=\frac{1}{m^{2}}\frac{1}{n}\sum\limits_{i=1}^{n}T_{abc}(x_{i}^{a}-\bar{x}^{a})(x_{i}^{b}-\bar{x}^{b})(x_{i}^{c}-\bar{x}^{c}).$

∎

The next lemma deals with the residual term
$\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{3}$
of $\bar{c}$.

######  Lemma 4.

Let $\nu$ be the uniform distribution on $n$ points
$\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}\in\mathbb{R}^{d}$, and
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}=\mathbb{E}_{\nu}\mathbf{x}$.
Let $\tilde{\mathbf{x}}$ be the empirical mean of $n$ samples i.i.d. sampled
by $\nu$, i.e.
$\tilde{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\tilde{\mathbf{x}}_{i}$,
$\tilde{\mathbf{x}}_{i}\stackrel{{\scriptstyle iid}}{{\sim}}\nu$. Then,

$\mathbb{E}_{\nu}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{3}\leq\frac{1}{n^{3}}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{4}\right)^{\frac{1}{2}}+\frac{\sqrt{3}}{n^{3}}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\right)^{\frac{3}{2}}.$

###### Proof.

We ignore the subscript $\nu$ in the expectation. By Cauchy-Schwartz
inequality, we have

$\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{3}\leq\sqrt{\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}}.$
(63)

For $\mathbb{E}_{\nu}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}$, by Lemma 2,
we have

$\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}=\frac{1}{n^{2}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}.$
(64)

For $\mathbb{E}_{\nu}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}$, noting the
independency of $\\{\tilde{\mathbf{x}}_{i}\\}$, we expand the expression and
drop the zero terms, and obtain

$\displaystyle\mathbb{E}_{\nu}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}$
$\displaystyle=\frac{1}{n^{4}}\sum\limits_{i,j,k,l=1}^{n}\mathbb{E}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}_{j}-\bar{\mathbf{x}})(\tilde{\mathbf{x}}_{k}-\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}_{l}-\bar{\mathbf{x}})$
$\displaystyle=\frac{1}{n^{4}}\left(\sum\limits_{i=1}^{n}\mathbb{E}\|\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}}\|^{4}+\sum\limits_{i\neq
j}\mathbb{E}\|\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}}\|^{2}\|\tilde{\mathbf{x}}_{j}-\bar{\mathbf{x}}\|^{2}+2\sum\limits_{i\neq
j}\mathbb{E}\big{(}(\tilde{\mathbf{x}}_{i}-\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}_{j}-\bar{\mathbf{x}})\big{)}^{2}\right)$
$\displaystyle\leq\frac{1}{n^{3}}\mathbb{E}\|\tilde{\mathbf{x}}_{1}-\bar{\mathbf{x}}\|^{4}+\frac{3}{n^{2}}\big{(}\mathbb{E}\|\tilde{\mathbf{x}}_{1}-\bar{\mathbf{x}}\|^{2}\big{)}^{2}$
$\displaystyle=\frac{1}{n^{4}}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{4}+\frac{3}{n^{4}}\left(\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{2}\right)^{2}.$
(65)

Substituting (64) and (65) into (63), and use the result
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ completes the proof. ∎

The next two lemmas estimates the moments of $\mathbf{x}-\mathbf{x}^{*}$,
$\mathbf{x}-\bar{\mathbf{x}}$ and $\bar{\mathbf{x}}-\mathbf{x}^{*}$. The first
one is a general result for moments of the average of i.i.d random variables.

######  Lemma 5.

Let $X$ be a random variable taking values on $\mathbb{R}$, and
$X_{1},X_{2},...,X_{n}$ are i.i.d copies of $X$. Let
$\bar{X}=\frac{1}{n}(X_{1}+X_{2}+\cdots+X_{n})$. Let $k$ be a positive
integer. Assume $\mathbb{E}X=0$, and $X$ has up to $2k$-th order finite
moments. Then, for any $l\leq 2k$, we have
$\mathbb{E}|\bar{X}|^{l}=O(\frac{1}{n^{l/2}})$.

###### Proof.

We first show the results for even $l$. Consider the set

$\mathcal{S}_{l}=\left\\{(r_{1},r_{2},...,r_{p}):\ r_{1}\geq r_{2}\geq...\geq
r_{p}>0,\ \sum\limits_{i=1}^{p}r_{i}=l\right\\}.$

Let $|\mathcal{S}_{l}|$ be the number of elements in $\mathcal{S}_{l}$. Then,
$|\mathcal{S}_{l}|$ is a number that depends only on $l$. When $l$ is an even
number, we have

$\mathbb{E}|\bar{X}|^{l}=\frac{1}{n^{l}}\mathbb{E}\big{(}X_{1}+...+X_{n}\big{)}^{l}=\frac{1}{n^{l}}\mathbb{E}\left(\sum\limits_{(r_{1},...,r_{p})\in\mathcal{S}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}X_{i_{1}}^{r_{1}}X_{i_{2}}^{r_{2}}\cdots
X_{i_{p}}^{r_{p}}\right).$ (66)

The right hand side of (66) is the multinomial expansion of
$(X_{1}+...+X_{n})^{l}$, organized according to the powers of different
$X_{i}$’s in each term, and $C_{(r_{1},...,r_{p})}$ are positive integers
related with multinomial coefficients. $C_{(r_{1},...,r_{p})}$ depends on $l$
and $r_{1},...,r_{p}$, but is independent with $n$. Since $\mathbb{E}X=0$, the
expectation of $X_{i_{1}}^{r_{1}}X_{i_{2}}^{r_{2}}\cdots X_{i_{p}}^{r_{p}}$ is
nonzero only when there is no $r_{i}$ that equals to $1$. Hence, (66) equals
to

$\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}\mathbb{E}\big{(}X_{i_{1}}^{r_{1}}X_{i_{2}}^{r_{2}}\cdots
X_{i_{p}}^{r_{p}}\big{)}\right).$ (67)

Because $X_{i_{1}},...,X_{i_{p}}$ are independent, we have
$\mathbb{E}\big{(}X_{i_{1}}^{r_{1}}X_{i_{2}}^{r_{2}}\cdots
X_{i_{p}}^{r_{p}}\big{)}=\prod_{j=1}^{p}\mathbb{E}X_{i_{j}}^{r_{j}}$. By the
finite moment assumption of $X$, we can find a constant $C$ such that
$|\mathbb{E}X^{j}|\leq C$ holds for any $1\leq j\leq 2k$. Then, we have

$\displaystyle\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}\mathbb{E}\big{(}X_{i_{1}}^{r_{1}}X_{i_{2}}^{r_{2}}\cdots
X_{i_{p}}^{r_{p}}\big{)}\right)$
$\displaystyle\leq\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq i_{p}\end{subarray}}^{n}C^{p}\right).$

Moreover, since $r_{1}\geq r_{2}\geq...\geq r_{p}\geq 2$, we have $p\leq l/2$,
and hence

$\frac{1}{n^{l}}\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}C^{l}\leq\frac{1}{n^{l}}\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}n^{\frac{l}{2}}C^{l}\leq\frac{|S_{l}|\max
C_{(r_{1},...,r_{p})}C^{l}}{n^{l/2}}.$

This completes the proof for even $l$.

For odd $l$, note that $2k\geq l+1$. The result follows by a Cauchy-Schwartz
inequality:

$\mathbb{E}|\bar{X}|^{l}\leq\sqrt{\mathbb{E}|\bar{X}|^{l+1}\mathbb{E}|\bar{X}|^{l-1}}.$

∎

######  Lemma 6.

Let $\mu$ be a probability distribution on $\mathbb{R}^{d}$ that satisfies
Assumption 1, and
$\mathbf{x},\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}$ be i.i.d samples
from $\mu$. Let $\mathbf{x}^{*}=\mathbb{E}_{\mu}\mathbf{x}$, and
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$. Then, for any
positive integer $k\leq 8$, we have

$\mathbb{E}\|\mathbf{x}-\mathbf{x}^{*}\|^{k}=O(1),\quad\mathbb{E}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{k}=O(1),\quad\mathbb{E}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{k}=O(\frac{1}{n^{k/2}}).$

###### Proof.

The first result is given by Assumption 1. The third result is a direct
corollary of Lemma 5. The second results follows the triangle inequality:

$\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{k}\leq\big{(}\|\mathbf{x}-\mathbf{x}^{*}\|+\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|\big{)}^{k}\leq
2^{k}\big{(}\|\mathbf{x}-\mathbf{x}^{*}\|^{k}+\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{K}\big{)}.$

∎

Finally, we study $\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|$ using
similar approaches.

######  Lemma 7.

Let $\mu$ be a probability distribution on $\mathbb{R}^{d}$ that satisfies
Assumption 1, and $\nu$ is the uniform ditribution on $[n]$. Consider
$\mathbf{x},\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{n}$ i.i.d sampled
from $\mu$, and $k_{1},...,k_{n}$ i.i.d sampled from $\nu$. Let
$\bar{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}$, and
$\tilde{\mathbf{x}}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{k_{i}}$. Then, for
any positive integer $k\leq 8$, we have

$\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{k}=O(\frac{1}{n^{k/2}}),$

where the expectation is taken on both $\mu$ and $\nu$.

###### Proof.

Following the proof of Lemma 5, fixing $\mathbf{x}_{1},...,\mathbf{x}_{n}$,
for even number $l\leq 8$ we have

$\displaystyle\mathbb{E}_{\nu}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{l}$
$\displaystyle\leq\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}\mathbb{E}_{\nu}\|\mathbf{x}_{k_{i_{1}}}-\bar{\mathbf{x}}\|^{r_{1}}\mathbb{E}_{\nu}\|\mathbf{x}_{k_{i_{2}}}-\bar{\mathbf{x}}\|^{r_{2}}\cdots\mathbb{E}_{\nu}\|\mathbf{x}_{k_{i_{p}}}-\bar{\mathbf{x}}\|^{r_{p}}\right)$
$\displaystyle=\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}\prod\limits_{j=1}^{p}\big{(}\frac{1}{n}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{r_{j}}\big{)}\right).$
(68)

When we consider the sampling of $\mathbf{x}_{1},...,\mathbf{x}_{n}$, we need
to take an expectation of (68) over $\\{\mathbf{x}_{i}\\}$. For each term in
the sums in (68), we have

$\displaystyle\mathbb{E}_{\mu}\prod\limits_{j=1}^{p}\big{(}\frac{1}{n}\sum\limits_{i=1}^{n}\|\mathbf{x}_{i}-\bar{\mathbf{x}}\|^{r_{j}}\big{)}$
$\displaystyle=\frac{1}{n^{p}}\sum_{k_{1},...,k_{p}=1}^{n}\mathbb{E}_{\mu}\prod\limits_{j=1}^{p}\|\mathbf{x}_{k_{j}}-\bar{\mathbf{x}}\|^{r_{j}}$
$\displaystyle\leq\frac{1}{n^{p}}\sum_{k_{1},...,k_{p}=1}^{n}\prod\limits_{j=1}^{p}\big{(}\mathbb{E}_{\mu}\|\mathbf{x}_{k_{j}}-\bar{\mathbf{x}}\|^{l}\big{)}^{\frac{r_{j}}{l}}$
$\displaystyle=\frac{1}{n^{p}}\sum_{k_{1},...,k_{p}=1}^{n}\prod\limits_{j=1}^{p}O(1)$
$\displaystyle=O(1),$

where the first to the second line is given by the Hölder’s inequality, and
the second to the third line is given by Lemma 6. Substituting the estimate
above to (63), we have that there exists a constant $C$ independent with $n$,
such that

$\mathbb{E}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{l}\leq\frac{1}{n^{l}}\left(\sum\limits_{\begin{subarray}{c}(r_{1},...,r_{p})\in\mathcal{S}\\\
r_{p}\geq
2\end{subarray}}C_{(r_{1},...,r_{p})}\sum\limits_{\begin{subarray}{c}i_{1},...,i_{p}=1\\\
i_{1}\neq...\neq
i_{p}\end{subarray}}^{n}C\right)=O(\frac{1}{n^{\frac{l}{2}}}).$

For odd $l$ we can show the result similar to the proof of Lemma 5 using the
Cauchy-Schwartz inequality. ∎

##  7 Proof of Theorem 3

###  7.1 Additional notations

In this section, we will expand our use of the hot notations. We use
$\textrm{hot}_{\bar{\mathbf{x}}}$ to denote higher-order-terms with
coefficients depending on $F(\bar{\mathbf{x}})$ or derivatives of $F$
evaluated at $\bar{\mathbf{x}}$. For example,

$\big{(}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\big{)}^{2}+F(\bar{\mathbf{x}})\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}$

can be represented by
$\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}};2)$. By
Lemma 1, $F(\bar{\mathbf{x}})$, $\nabla F(\bar{\mathbf{x}})$,
$\nabla^{2}F(\bar{\mathbf{x}})$ and $\nabla^{3}F(\bar{\mathbf{x}})$ can be
represented by $\textrm{hot}(\bar{\mathbf{x}}-\mathbf{x}^{*};0)$. (Note that
in the Taylor expansion the coefficients depends on $\mathbf{x}^{*}$, which is
treated as a constant.) Hence, any
$\textrm{hot}_{\bar{\mathbf{x}}}(f_{1},\cdots,f_{k};r)$ can be represented by
$\textrm{hot}(f_{1},\cdots,f_{k},\bar{\mathbf{x}}-\mathbf{x}^{*};r)$.
Moreover, we use $\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}$ to denote
higher-order-terms that expectations with respect to $\tilde{\mathbf{x}}$ are
taken for some parts. For example,

$\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\mathbf{x}^{*})}$

can be represented by
$\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\bar{\mathbf{x}}-\mathbf{x}^{*},\tilde{\mathbf{x}}-\bar{\mathbf{x}};3)$.
Using the Hölder’s inequality and Jensen’s inequality, it is easy to show that
the $\mathbb{E}_{\tilde{\mathbf{x}}}$ does not change the order of the
expectation of the higher-order-terms. For any $r>0$, we have

$\mathbb{E}\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\bar{\mathbf{x}}-\mathbf{x}^{*},\tilde{\mathbf{x}}-\bar{\mathbf{x}};r)=O(\frac{1}{n^{r/2}}).$

###  7.2 Main proof

We take a similar path as the proof of Theorem 2. Specifically, in this
section we consider another $\hat{c}$ defined as
$\hat{c}=(\hat{s}-1)F(\bar{\mathbf{x}})$, then we have

$\mathbb{E}(\hat{s}F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}=\mathbb{E}(F(\bar{\mathbf{x}})+\hat{c}-F(\mathbf{x}^{*}))^{2},$

which gives the same form as the shifting debiasing, but with a different
debiasing quantity. To prove the theorem, we still show
$\mathbb{E}\hat{c}^{2}+2\hat{c}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))<0$.

We first decompose $\hat{c}$ to separate the effect of the sampling of
$\\{\mathbf{x}_{i}\\}$ and the sampling of $\\{\tilde{\mathbf{x}}_{k}\\}$.
Recall that

$\hat{s}=\frac{F(\bar{\mathbf{x}})\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})}{\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})^{2}}=\frac{F(\bar{\mathbf{x}})\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})}{\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})^{2}}.$

Define
$\bar{s}=\frac{F(\bar{\mathbf{x}})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})}{\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}}$,
$\bar{c}=(\bar{s}-1)F(\bar{\mathbf{x}})$, and

$s_{1}=\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}),\quad
s_{2}=\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})^{2}-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}.$
(69)

Then, we have

$\displaystyle\hat{c}$
$\displaystyle=\bar{c}+(\hat{s}-\bar{s})F(\bar{\mathbf{x}})=\bar{c}+\frac{F(\bar{\mathbf{x}})^{2}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}+s_{2})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}}$
$\displaystyle=\bar{c}+\frac{F(\bar{\mathbf{x}})^{2}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}}-\frac{F(\bar{\mathbf{x}})^{2}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}s_{2}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}+s_{2})(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}}.$

Denote

$\delta_{1}=\frac{F(\bar{\mathbf{x}})^{2}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}},\quad\delta_{2}=-\frac{F(\bar{\mathbf{x}})^{2}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}s_{2}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}+s_{2})(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}}.$

Then, we can write $\hat{c}=\bar{c}+\delta_{1}+\delta_{2}$. Since
$\mathbb{E}_{\tilde{\mathbf{x}}}s_{1}=\mathbb{E}_{\tilde{\mathbf{x}}}s_{2}=0$,
we know $\mathbb{E}_{\tilde{\mathbf{x}}}\delta_{1}=0$, and hence

$\displaystyle\mathbb{E}\hat{c}^{2}+2\hat{c}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))$
$\displaystyle=\mathbb{E}\left(\bar{c}^{2}+\delta_{1}^{2}+\delta_{2}^{2}+2\bar{c}\delta_{1}+2\bar{c}\delta_{2}+2\delta_{1}\delta_{2}\right.$
$\displaystyle+\left.2\bar{c}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})+2\delta_{1}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})+2\delta_{2}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\right)$
$\displaystyle=\mathbb{E}\left(\bar{c}^{2}+\delta_{1}^{2}+\delta_{2}^{2}+2\bar{c}\delta_{2}+2\delta_{1}\delta_{2}+2\bar{c}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})+2\delta_{2}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*})\right).$
(70)

Next, we estimate the terms in (70).

####  7.2.1 Estimate of $\mathbb{E}\delta_{2}^{2}$

By Assumption 4, $F$ has a positive lower bound $B$. Hence, we have
$\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}\geq B^{2}$ and

$\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}+s_{2}=\frac{1}{K}\sum\limits_{k=1}^{K}F(\tilde{\mathbf{x}}_{k})^{2}\geq
B^{2}.$

Substituting the lower bounds into $\delta_{2}$, we have

$|\delta_{2}|\leq\frac{F(\bar{\mathbf{x}})^{2}}{B^{6}}\left|\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}s_{2}\right|\leq\frac{F(\bar{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}}{B^{6}}|s_{1}s_{2}|+\frac{F(\bar{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})}{B^{6}}|s_{2}^{2}|.$

Therefore, by the Hölder’s inequality and the Jensen’s inequality,

$\displaystyle\mathbb{E}\delta_{2}^{2}$
$\displaystyle\leq\frac{2}{B^{12}}\left(\mathbb{E}[F(\bar{\mathbf{x}})^{4}(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}s_{1}^{2}s_{2}^{2}]+\mathbb{E}[F(\bar{\mathbf{x}})^{4}(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}))^{2}s_{2}^{4}]\right)$
$\displaystyle\leq\frac{2}{B^{12}}\left(\big{(}\mathbb{E}F(\bar{\mathbf{x}})^{12}\big{)}^{\frac{1}{3}}\big{(}\mathbb{E}F(\tilde{\mathbf{x}})^{12}\big{)}^{\frac{1}{3}}\big{(}\mathbb{E}s_{1}^{12}\mathbb{E}s_{2}^{12}\big{)}^{\frac{1}{6}}+\big{(}\mathbb{E}F(\bar{\mathbf{x}})^{10}\big{)}^{\frac{2}{5}}\big{(}\mathbb{E}F(\tilde{\mathbf{x}})^{10}\big{)}^{\frac{1}{5}}\big{(}\mathbb{E}s_{2}^{10}\big{)}^{\frac{2}{5}}\right).$

For the $s_{1}$, $s_{2}$ terms, by Lemma 10, we have

$\big{(}\mathbb{E}s_{1}^{12}\mathbb{E}s_{2}^{12}\big{)}^{\frac{1}{6}}=O(\frac{1}{K^{2}n^{2}})=O(\frac{1}{n^{4}}),\
\textrm{and}\
\big{(}\mathbb{E}s_{2}^{10}\big{)}^{\frac{2}{5}}=O(\frac{1}{K^{2}n^{2}})=O(\frac{1}{n^{4}}).$

For the $\mathbb{E}F(\bar{\mathbf{x}})^{12}$,
$\mathbb{E}F(\bar{\mathbf{x}})^{10}$, $\mathbb{E}F(\tilde{\mathbf{x}})^{12}$,
and $\mathbb{E}F(\tilde{\mathbf{x}})^{10}$ terms, by Lemma 11, they are all
$O(1)$. Therefore, we have the following estimate for
$\mathbb{E}\delta_{2}^{2}$:

$\mathbb{E}\delta_{2}^{2}=O(\frac{1}{n^{4}}).$ (71)

####  7.2.2 Estimate of $\mathbb{E}\delta_{1}\delta_{2}$

Similar to the estimate of $\delta_{2}$, we have

$|\delta_{1}|\leq\frac{F(\bar{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}}{B^{4}}|s_{1}|+\frac{F(\bar{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})}{B^{4}}|s_{2}|.$

Therefore, together with the estimate of $\delta_{2}$, we have

$\displaystyle|\mathbb{E}\delta_{1}\delta_{2}|$
$\displaystyle\leq\frac{1}{B^{10}}\left(\mathbb{E}[F(\bar{\mathbf{x}})^{4}(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{2}s_{1}^{2}|s_{2}|]+2\mathbb{E}[F(\bar{\mathbf{x}})^{4}(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}))|s_{1}|s_{2}^{2}]\right.$
$\displaystyle\ \ \ \ \ \ \ \ \
\left.+\mathbb{E}[F(\bar{\mathbf{x}})^{4}(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}}))^{2}|s_{2}|^{3}]\right)$
$\displaystyle\leq\frac{1}{B^{10}}\left((\mathbb{E}F(\bar{\mathbf{x}})^{11})^{\frac{4}{11}}\mathbb{E}F(\tilde{\mathbf{x}})^{11})^{\frac{4}{11}}(\mathbb{E}|s_{1}|^{11})^{\frac{2}{11}}(\mathbb{E}|s_{2}|^{11})^{\frac{1}{11}}\right.$
$\displaystyle\ \ \ \ \ \ \ \ \
+2(\mathbb{E}F(\bar{\mathbf{x}})^{10})^{\frac{4}{10}}\mathbb{E}F(\tilde{\mathbf{x}})^{10})^{\frac{3}{10}}(\mathbb{E}|s_{1}|^{10})^{\frac{1}{10}}(\mathbb{E}|s_{2}|^{10})^{\frac{2}{10}}$
$\displaystyle\ \ \ \ \ \ \ \ \
+\left.(\mathbb{E}F(\bar{\mathbf{x}})^{9})^{\frac{4}{9}}\mathbb{E}F(\tilde{\mathbf{x}})^{9})^{\frac{2}{9}}(\mathbb{E}|s_{2}|^{9})^{\frac{3}{9}}\right)$
$\displaystyle=O(\frac{1}{n^{3}})+O(\frac{1}{n^{3}})+O(\frac{1}{n^{3}})$
$\displaystyle=O(\frac{1}{n^{3}}).$ (72)

In the derivations above, we use Lemma 10 and the fact that
$\mathbb{E}F(\bar{\mathbf{x}})^{l}=O(1)$,
$\mathbb{E}F(\tilde{\mathbf{x}})=O(1)$ for $l>0$ (Lemma 11).

####  7.2.3 Estimate of
$\mathbb{E}\delta_{2}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))$

By the Hölder’s inequality and the result in Section 7.2.1, we have

$\displaystyle|\mathbb{E}\delta_{2}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))|$
$\displaystyle\leq\sqrt{\mathbb{E}\delta_{2}^{2}\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}}$
$\displaystyle\leq
O(\frac{1}{n^{2}})\sqrt{\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}}.$

For $\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}$, by the Taylor
expansion and Lemma 8 we have

$\displaystyle\mathbb{E}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))^{2}$
$\displaystyle=\mathbb{E}\left(\nabla
F(\mathbf{x}^{*})^{T}(\bar{\mathbf{x}}-\mathbf{x}^{*})+\frac{1}{2}\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|_{H(\mathbf{x}^{*})}+\frac{1}{6}\nabla^{3}F(\mathbf{x}^{*})[\bar{\mathbf{x}}-\mathbf{x}^{*}]+O(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|^{4})\right)^{2}$
$\displaystyle\leq\mathbb{E}\big{(}\textrm{hot}(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|;2)\big{)}$
$\displaystyle=O(\frac{1}{n}).$

Therefore,

$\mathbb{E}\delta_{2}(F(\bar{\mathbf{x}})-F(\mathbf{x}^{*}))=O(\frac{1}{n^{2.5}}).$
(73)

####  7.2.4 Estimate of $\mathbb{E}\delta_{1}^{2}$

Note that

$\delta_{1}^{2}=\frac{F(\bar{\mathbf{x}})^{4}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2}.$

We first simplify the problem by noticing that $F(\bar{\mathbf{x}})$ and
$F(\tilde{\mathbf{x}})$ are both close to $F(\mathbf{x}^{*})$. Specifically,
let

$\alpha:=\frac{1}{F(\mathbf{x}^{*})^{4}}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2},\qquad\beta=\delta_{1}^{2}-\alpha.$

Then,

$\beta=\frac{F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}}{(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}F(\mathbf{x}^{*})^{4}}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2}.$
(74)

By the lower bound of $F$ and the Hölder’s inequality, we have

$\mathbb{E}|\beta|\leq\frac{1}{B^{12}}\sqrt{\mathbb{E}\left(F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}\right)^{2}\mathbb{E}\left(s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\right)^{4}}.$
(75)

For the term in (75) with $s_{1}$ and $s_{2}$, note that this term contains
fourth-order monomials of $s_{1}$ and $s_{2}$. Similar to the analysis in
Section 7.2.1, we know this term has order $O(\frac{1}{n^{4}})$. For the other
term, by Jensen’s inequality we have

$\displaystyle\mathbb{E}\left(F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}\right)^{2}$
$\displaystyle\leq\mathbb{E}\left(F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{8}\right)^{2}$
$\displaystyle=\mathbb{E}\left(\mathbb{E}_{\tilde{\mathbf{x}}}\big{(}F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-F(\tilde{\mathbf{x}})^{8}\big{)}\right)^{2}$
$\displaystyle\leq\mathbb{E}\left(F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-F(\tilde{\mathbf{x}})^{8}\right)^{2}$

For the term on the last line, a Taylor expansion at $\mathbf{x}^{*}$ gives

$\displaystyle\mathbb{E}\left(F(\mathbf{x}^{*})^{4}\big{(}F(\mathbf{x}^{*})+\textrm{hot}(\bar{\mathbf{x}}-\mathbf{x}^{*};1)\big{)}^{4}-\big{(}F(\mathbf{x}^{*})+\textrm{hot}(\tilde{\mathbf{x}}-\mathbf{x}^{*};1)\big{)}^{8}\right)^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\big{(}\textrm{hot}(\bar{\mathbf{x}}-\mathbf{x}^{*};1)+\textrm{hot}(\tilde{\mathbf{x}}-\mathbf{x}^{*};1)\big{)}^{2}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\big{(}\textrm{hot}(\|\bar{\mathbf{x}}-\mathbf{x}^{*}\|,\|\tilde{\mathbf{x}}-\mathbf{x}^{*}\|;2)\big{)}$
$\displaystyle=$ $\displaystyle O(\frac{1}{n}).$

Therefore, we have

$\mathbb{E}\left(F(\bar{\mathbf{x}})^{4}F(\mathbf{x}^{*})^{4}-(\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2})^{4}\right)^{2}=O(\frac{1}{n}),$

and back to (75) we have $\mathbb{E}|\beta|=O(\frac{1}{n^{2.5}})$, and hence

$\mathbb{E}\delta_{1}^{2}=\mathbb{E}\alpha+O(\frac{1}{n^{2.5}}).$

Next, we study $\mathbb{E}\alpha$. By the definition of $s_{1}$ and $s_{2}$,
using the theorem of total expectation, we have

$\displaystyle\mathbb{E}\big{(}s_{1}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-s_{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}^{2}$
$\displaystyle=\mathbb{E}\textrm{Var}_{\tilde{\mathbf{x}}}\left(\frac{1}{K}\sum\limits_{k=1}^{K}\big{(}F(\tilde{\mathbf{x}}_{k})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-F(\tilde{\mathbf{x}}_{k})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\big{)}\right)$
$\displaystyle=\frac{1}{K}\mathbb{E}\mathbb{E}_{\tilde{\mathbf{x}}}\left(F(\tilde{\mathbf{x}})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-F(\tilde{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\right)^{2}$
$\displaystyle=\frac{1}{C_{K}n}\mathbb{E}\left(F(\tilde{\mathbf{x}})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-F(\tilde{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\right)^{2}.$
(76)

Taylor expansion of $F(\tilde{\mathbf{x}})$ at $\bar{\mathbf{x}}$ gives

$\displaystyle F(\tilde{\mathbf{x}})$
$\displaystyle=F(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}};2),$
$\displaystyle F(\tilde{\mathbf{x}})^{2}$
$\displaystyle=F(\bar{\mathbf{x}})^{2}+2F(\bar{\mathbf{x}})\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}};2).$

Here, the higher-order-terms notation $\textrm{hot}_{\bar{\mathbf{x}}}$ means
these terms depends on the derivatives of $F$ at $\bar{\mathbf{x}}$. We note
that a Taylor expansion of these derivatives at $\mathbf{x}^{*}$ will replace
the dependency on $\nabla F(\bar{\mathbf{x}})$, $H(\bar{\mathbf{x}})$ and
$\nabla F(\bar{\mathbf{x}})$ by powers of $\bar{\mathbf{x}}-\mathbf{x}^{*}$.
It will not lower the order of the terms, Hence, the higher-order-terms can be
written as
$\textrm{hot}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2)$.
Plugging the Taylor expansions into (76), since
$\mathbb{E}_{\tilde{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})=0$, we
obtain

$\displaystyle
F(\tilde{\mathbf{x}})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}$
$\displaystyle=F(\bar{\mathbf{x}})^{3}+F(\bar{\mathbf{x}})^{2}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+F(\bar{\mathbf{x}})^{2}\textrm{hot}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2)$
$\displaystyle\ \ +\left(F(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2)\right)\mathbb{E}_{\tilde{\mathbf{x}}}\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2)$
$\displaystyle=F(\bar{\mathbf{x}})^{3}+F(\bar{\mathbf{x}})^{2}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2),$
(77)

where $\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}$ denotes higher-order-
terms in which expectations over $\bar{\mathbf{x}}$ are taken for some terms.
Similarly, we have

$F(\tilde{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})=F(\bar{\mathbf{x}})^{3}+2F(\bar{\mathbf{x}})^{2}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2).$
(78)

Combining (77) and (78), (76) becomes

$\displaystyle\frac{1}{C_{K}n}\mathbb{E}\left(F(\bar{\mathbf{x}})^{2}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};2)\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{C_{K}n}\mathbb{E}\left(F(\bar{\mathbf{x}})^{2}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\right)^{2}+\frac{1}{C_{K}n}\mathbb{E}\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};3)$
$\displaystyle=$
$\displaystyle\frac{1}{C_{K}n}\mathbb{E}F(\bar{\mathbf{x}})^{4}(\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}}))^{2}+O(\frac{1}{n^{2.5}}).$
(79)

Expanding $F(\bar{\mathbf{x}})$ and $\nabla F(\bar{\mathbf{x}})$ at
$\mathbf{x}^{*}$, similar to arguments above Equation (77), we have

$\displaystyle\mathbb{E}F(\bar{\mathbf{x}})^{4}\left(\nabla
F(\bar{\mathbf{x}})(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\right)^{2}$
$\displaystyle=\mathbb{E}F(\mathbf{x}^{*})^{4}\left(\nabla
F(\mathbf{x}^{*})(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\right)^{2}+\mathbb{E}\big{(}\textrm{hot}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};3)\big{)}$
$\displaystyle=\mathbb{E}F(\mathbf{x}^{*})^{4}\left(\nabla
F(\mathbf{x}^{*})(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\right)^{2}+O(\frac{1}{n^{1.5}}).$

Moreover, by the analysis (40) in Section 6.2.2, we have

$\mathbb{E}\left(\nabla
F(\mathbf{x}^{*})(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\right)^{2}=\frac{1}{n}\nabla
F(\mathbf{x}^{*})^{T}M_{2}\nabla
F(\mathbf{x}^{*})+O(\frac{1}{n^{1.5}})=\frac{\sigma_{1}}{n}+O(\frac{1}{n^{1.5}}).$

Back to (76), we have

$\frac{1}{C_{K}n}\mathbb{E}\left(F(\tilde{\mathbf{x}})\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}-F(\tilde{\mathbf{x}})^{2}\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})\right)^{2}=\frac{F(\mathbf{x}^{*})^{4}\sigma_{1}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}}).$

Hence, for $\alpha$, we have

$\mathbb{E}\alpha=\frac{\sigma_{1}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}}),$

and for $\delta_{1}^{2}$ we have the same estimate

$\mathbb{E}\delta_{1}^{2}=\frac{\sigma_{1}}{C_{K}n^{2}}+O(\frac{1}{n^{2.5}}).$
(80)

####  7.2.5 Estimate of $\mathbb{E}\bar{c}^{2}$

To estimate $\mathbb{E}\bar{c}^{2}$, we first study $\bar{c}$. Recall that

$\bar{c}=(\bar{s}-1)F(\bar{\mathbf{x}})=\frac{F(\bar{\mathbf{x}})^{2}\mathbb{E}F(\tilde{\mathbf{x}})}{\mathbb{E}F(\tilde{\mathbf{x}})^{2}}-F(\bar{\mathbf{x}}).$

To simplify notations, we use $F$, $E_{1}$, $E_{2}$ to represent
$F(\bar{\mathbf{x}})$, $\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})$,
and $\mathbb{E}_{\tilde{\mathbf{x}}}F(\tilde{\mathbf{x}})^{2}$ when no
confusion is caused. Our intuition is that $E_{1}$ is close to $F$ and $E_{2}$
is close to $F^{2}$. Hence, we will try to expand $F(\tilde{\mathbf{x}})$ and
$F(\tilde{\mathbf{x}})^{2}$ at $\bar{\mathbf{x}}$. First, applying the
identity $\frac{1}{1+a}=1-a+\frac{a^{2}}{1+a}$ for $a=\frac{E_{2}}{F^{2}}-1$,
we have

$\displaystyle\bar{c}$ $\displaystyle=\frac{E_{1}}{\frac{E_{2}}{F^{2}}}-F$
$\displaystyle=E_{1}\left(1-\big{(}\frac{E_{2}}{F^{2}}-1\big{)}+\frac{\big{(}\frac{E_{2}}{F^{2}}-1\big{)}^{2}}{\frac{E_{2}}{F^{2}}}\right)-F$
$\displaystyle=(E_{1}-F)+\frac{E_{1}}{F^{2}}(F^{2}-E_{2})+\frac{E_{1}(E_{2}-F^{2})^{2}}{F^{2}E_{2}}.$
(81)

We will estimate the three terms in (81). We start from the first and the
second terms.

For the first term $E_{1}-F$, expanding $F(\tilde{\mathbf{x}})$ at
$\bar{\mathbf{x}}$ gives

$E_{1}-F=\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{6}\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$
(82)

For the second term in (81), we first expand $E_{1}$ and $F^{2}-E_{2}$. For
$E_{1}$, similar to (82) we have

$E_{1}=F(\bar{\mathbf{x}})+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{6}\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4}).$
(83)

For $E_{2}$, we have

$\displaystyle E_{2}$
$\displaystyle=\mathbb{E}_{\tilde{\mathbf{x}}}\left(F(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})+\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\frac{1}{6}\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})\right.$
$\displaystyle\ \
\quad\quad+O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4})\biggr{)}^{2}$
$\displaystyle=F(\bar{\mathbf{x}})^{2}+\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{(F(\bar{\mathbf{x}})H(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})\nabla
F(\bar{\mathbf{x}})^{T})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{3}F(\bar{\mathbf{x}})\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})$
$\displaystyle\ \ \ +\mathbb{E}_{\tilde{\mathbf{x}}}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\mathbb{E}_{\tilde{\mathbf{x}}}\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}};4).$
(84)

We still replace
$\textrm{hot}_{\bar{\mathbf{x}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}};4)$ by
$\textrm{hot}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};4)$.
Combining (83) and (84), we have

$\displaystyle E_{1}(E_{2}-F^{2})$ $\displaystyle=$
$\displaystyle\left(F(\bar{\mathbf{x}})+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{2}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{6}\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})+\mathbb{E}_{\tilde{\mathbf{x}}}O(\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{4})\right)$
$\displaystyle\times\left(\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{(F(\bar{\mathbf{x}})H(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})\nabla
F(\bar{\mathbf{x}})^{T})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{3}F(\bar{\mathbf{x}})\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})\right.$
$\displaystyle\qquad+\mathbb{E}_{\tilde{\mathbf{x}}}\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\mathbb{E}_{\tilde{\mathbf{x}}}\textrm{hot}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};4)\biggr{)}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\tilde{\mathbf{x}}}F(\bar{\mathbf{x}})\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{(F(\bar{\mathbf{x}})H(\bar{\mathbf{x}})+\nabla
F(\bar{\mathbf{x}})\nabla
F(\bar{\mathbf{x}})^{T})}+\mathbb{E}_{\tilde{\mathbf{x}}}\frac{1}{3}F(\bar{\mathbf{x}})^{2}\partial_{abc}^{3}F(\bar{\mathbf{x}})(\tilde{x}^{a}-\bar{x}^{a})(\tilde{x}^{b}-\bar{x}^{b})(\tilde{x}^{c}-\bar{x}^{c})$
$\displaystyle+\mathbb{E}_{\tilde{\mathbf{x}}}F(\bar{\mathbf{x}})\nabla
F(\bar{\mathbf{x}})^{T}(\tilde{\mathbf{x}}-\bar{\mathbf{x}})\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{H(\bar{\mathbf{x}})}+\textrm{hot}_{\mathbb{E}_{\tilde{\mathbf{x}}}}(\tilde{\mathbf{x}}-\bar{\mathbf{x}},\bar{\mathbf{x}}-\mathbf{x}^{*};4).$

Therefore,

$\displaystyle\frac{E_{1}}{F^{2}}(F^{2}-E_{2})$
$\displaystyle=-\mathbb{E}_{\tilde{\mathbf{x}}}\|\tilde{\mathbf{x}}-\bar{\mathbf{x}}\|^{2}_{\left(H(\bar{\mathbf{x}})+\frac{\nabla
F(\bar{\mathbf{x}})\nabla