# Deriving the big $O_p$ of a sum involving estimation errors of bounded functions

Suppose $$\frac{1}{n}\sum_{i=1}^n\{f(X_i) - \hat{f}_n(X_i)\}^2$$ and $$\frac{1}{n}\sum_{i=1}^n\{g(X_i) - \hat{g}_n(X_i)\}^2$$ are $$O_p(a^2_n)$$ for some sequence $$a_n$$ such that $$a_n = O(n^{-r}$$) where $$r > 1/4$$.

Suppose $$Y_i$$ is a binary 0/1 random variable, $$f(\cdot)$$ is bounded between -1 and 1, (i.e., $$-1 \leq f(X_i) \leq 1$$ for any $$X_i$$) and $$g(\cdot)$$ is bounded between 0 and 1 (i.e., $$0 \leq g(X_i) \leq 1$$ for any $$X_i$$). Observations $$i = 1, \ldots, n$$ are i.i.d, and $$\hat{f}_n(\cdot)$$ and $$\hat{g}_n(\cdot)$$ are estimators obtained from these observations.

What is the big $$O_p$$ for

$$\frac{1}{n}\sum_{i=1}^n [(f(X_i) - \hat{f}_n(X_i))g(X_i) + (\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))]^2?$$

Expanding the square, we get a sum of 3 terms:

\begin{align*} &\frac{1}{n}\sum_{i=1}^n [(f(X_i) - \hat{f}_n(X_i))g(X_i) + (\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))]^2\\ &=\frac{1}{n}\sum_{i=1}^n \{f(X_i) - \hat{f}_n(X_i)\}^2g^2(X_i)+2(f(X_i) - \hat{f}_n(X_i))g(X_i)(\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i)) + (\hat{f}_n(X_i) - Y_i)^2(g(X_i) - \hat{g}_n(X_i))^2 \end{align*}

Term 1: $$\frac{1}{n}\sum_{i=1}^n \{f(X_i) - \hat{f}_n(X_i)\}^2g^2(X_i)$$

Since $$g(X_i)$$ is bounded, and $$\frac{1}{n}\sum_{i=1}^n\{f(X_i)-\hat{f}_n(X_i)\}^2$$ is $$O_p(a^2_n)$$, then Term 1 is $$O_p(a^2_n)$$.

Term 2: $$\frac{2}{n}\sum_{i=1}^n (f(X_i) - \hat{f}_n(X_i))g(X_i)(\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))$$

Since $$g(X_i) \leq 1$$ and $$|\hat{f}_n(X_i) - Y_i| \leq 2$$, then we have

\begin{align*} &\frac{2}{n}\sum_{i=1}^n (f(X_i) - \hat{f}_n(X_i))g(X_i)(\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))\\ &\leq C \sqrt{\left(\frac{1}{n}\sum_{i=1}^n \{f(X_i)-\hat{f}_n(X_i)\}^2\right)\left(\frac{1}{n}\sum_{i=1}^n \{g(X_i) - \hat{g}_n(X_i)\}^2\right)}\\ &= O_p(a^2_n) \end{align*} where $$C$$ is some positive constant, and the inequality holds by Cauchy-Schwarz.

Term 3: $$\frac{1}{n}\sum_{i=1}^n (\hat{f}_n(X_i) - Y_i)^2(g(X_i) - \hat{g}_n(X_i))^2$$

Since $$|\hat{f}_n(X_i) - Y_i| \leq 2$$

$$\frac{1}{n}\sum_{i=1}^n (\hat{f}_n(X_i) - Y_i)^2(g(X_i) - \hat{g}_n(X_i))^2 \leq \frac{4}{n}\sum_{i=1}^n (g(X_i) - \hat{g}_n(X_i))^2 = O_p(a^2_n)$$

Altogether, we have

\begin{align*} &\frac{1}{n}\sum_{i=1}^n [(f(X_i) - \hat{f}_n(X_i))g(X_i) + (\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))]^2\\ &= O_p(a^2_n) + O_p(a^2_n) + O_p(a^2_n)\\ &= O_p(a^2_n) \end{align*}

Is the above correct? I'm not very sure about Term 2 and Term 3 particularly with respect to factoring out $$\hat{f}_n(X_i)-Y_i$$.

• Did you try to simulate it? Commented Aug 1 at 17:11
• @Adrian the example was actually incorrect. That expectation $e^{-n}/n$ only decreases faster than $e^{-n} \cdot e^{-n(1-p)}$ when $p=1$. If the variable is non-negative, then for any quantile $p<1$ the decrease is bounded by the decrease of the expectation. Commented Aug 2 at 7:05
• The expressions are not all clear. Subscripts are missing occasionally. Also, the bounds of $\hat{f}(X_n)$ are not clear. Commented Aug 2 at 9:11
• "Assume observations i=1,…,n are i.i.d" Does this mean that the terms $\{f(X_i) - \hat{f}(X_i)\}$ are i.i.d. distributed? Then, if the average of their square approaches zero, this must mean that the expectation of the square is zero and that these variables have a zero second raw moment $E[\{f(X_i) - \hat{f}(X_i)\}^2] = 0$. Commented Aug 2 at 10:11
• No. $\{f(X_i) - \hat{f}(X_i)\}$ is not necessarily i.i.d. because I'll clarify that $\hat{f}$ is an estimator derived from $\{X_i\}_{i=1}^n$. Commented Aug 2 at 12:09

In theory no, in practice yes.

Since $$f(\cdot)$$ is bounded between 1 and -1, any sensible estimator $$\hat{f}_n(\cdot)$$ would alo be bounded between 1 and -1. In that case, we can bound $$|g(X_i)| \leq 1$$ and $$|\hat{f}_n(X_i) - Y_i| \leq 2$$ and everything works.

\begin{align}\frac{1}{n}\sum_{i=1}^n \left[(f(X_i) - \hat{f}_n(X_i))g(X_i) + (\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))\right]^2 \\ \leq \frac{4}{n}\sum_{i=1}^n \left[|f(X_i) - \hat{f}_n(X_i)| + |g(X_i) - \hat{g}_n(X_i)|\right]^2\\ \leq \frac{8}{n}\sum_{i=1}^n \left[|f(X_i) - \hat{f}_n(X_i)|^2 + |g(X_i) - \hat{g}_n(X_i)|^2\right]\\ = 8\cdot O_p(a_n^2) + 8\cdot O_p(a_n^2) = O_p(a_n^2)\\ \end{align}

However, if we have some crazy estimator, things may go wrong. Consider for example the following scenario:

• $$f(X_i) = g(X_i) = 0$$ for all $$i$$
• $$\hat{f}_n(X_i) = \hat{g}_n(X_i) = \sqrt[5]{n}$$ if $$n = 32^k$$ for some $$k \in \mathbb{N}$$
• $$\hat{f}_n(X_i) = \hat{g}_n(X_i) = 0$$ if $$n$$ is not a power of 32

In this case $$\frac{1}{n}\sum_{i=1}^n (f(X_i) - \hat{f}_n(X_i))^2 = \frac{1}{n}\sum_{i=1}^n (g(X_i) - \hat{g}_n(X_i))^2 = O(n^{-3/5})$$.

However, setting $$n = 32^k$$, we also get \begin{align}\frac{1}{n}\sum_{i=1}^n \left[(f(X_i) - \hat{f}_n(X_i))g(X_i) + (\hat{f}_n(X_i) - Y_i)(g(X_i) - \hat{g}_n(X_i))\right]^2\\ = \frac{1}{n}\sum_{i=1}^{k} \left[2^i\cdot g(X_{32^i}) + (2^i - Y_{32^i})(g(X_{32^i}) - 2^i)\right]^2\\ \geq \frac{1}{n}\left[n^{1/5}\cdot g(X_n) + (n^{1/5} - Y_n)(g(X_n) - n^{1/5})\right]^2\\ = \Omega(n^{-1/5})\\ \end{align} which contradicts that the expression would be $$O_p(a_n^2)$$ for some $$a_n = O(n^{-r})$$ with $$r > 1/4$$.