$\lambda_{1}\|f_{\mathrm{P},\mathrm{E}}\|_{E}\leq\lambda_{1}/T$. Moreover, by
Jensen’s inequality, we have

$\displaystyle\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}$
$\displaystyle=\int_{\mathcal{X}}\biggl{(}\frac{1}{T}\sum_{t=1}^{T}f_{\mathrm{P}}^{p,t}-f_{L,\mathrm{P}}^{*}\biggr{)}^{2}\,d\mathrm{P}_{X}$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\int_{\mathcal{X}}(f_{\mathrm{P}}^{p,t}-f_{L,\mathrm{P}}^{*})^{2}\,d\mathrm{P}_{X}$
$\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\biggl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p,t})-\mathcal{R}_{L,\mathrm{P}}^{*}\biggr{)}.$

Combining this with Proposition 33, we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}$
$\displaystyle\leq(2r)^{2\alpha}d(2^{-p})^{\frac{1-4^{-\alpha}}{d\log 2}}.$

Consequently we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}A(\lambda)$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\inf_{f\in
E}\lambda_{1}\|f\|_{E}+\lambda_{2}\Omega(h)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\biggr{)}$
$\displaystyle\leq\lambda_{1}\|f_{\mathrm{P},\mathrm{E}}\|_{E}+\lambda_{2}\Omega(h)+\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}$
$\displaystyle\leq\lambda_{1}/T+c\cdot\lambda_{2}^{\frac{1-4^{-\alpha}}{2d\log
2+(1-4^{-\alpha})}}.$

Then Theorem 34 implies that with probability $\mathrm{P}^{n}$ not less than
$1-3/n^{2}$, there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\lambda_{1}\|f\|_{E}+\lambda_{2}\Omega(p)+\mathcal{R}_{L,\mathrm{D}}(f_{\mathrm{D},B})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}$
$\displaystyle\leq 6\lambda_{1}/T+6c\lambda_{2}^{\frac{1-4^{-\alpha}}{2d\log
2+(1-4^{-\alpha})}}+3c_{0}^{\prime}T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2}+3456M^{2}(2\log
n)/n,$ (57)

where $\delta=1/(d\cdot 2^{p})$, $c$ and $c_{0}^{\prime}$ are constants
defined as in Proposition 33 and Theorem 34. Minimizing the right hand side of
(57), we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D},B})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}\leq
c^{\prime\prime}n^{-\frac{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{-\alpha})+2d\log
2}},$ (58)

if we choose

$\displaystyle\lambda_{1,n}=n^{-\frac{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{\alpha})+2d\log
2}},\,\lambda_{2,n}=n^{-\frac{2(1-4^{-\alpha}+2d\log
2)}{(4-2\delta)(1-4^{-\alpha})+2d\log 2}},\,p_{n}\asymp\frac{2d\log 2\log
n}{(4-2\delta)(1-4^{-\alpha})+2d\log 2},$

where $c^{\prime\prime}$ is a constant depending on $c$, $c_{0}^{\prime}$,
$d$, $M$, $R$ and $T$. Consequently, by the Borel-Cantelli Lemma, (58) holds
with probability $\mathrm{P}^{n}$ equal to one for sufficiently large $n$,
which leads to the desired assertion.

####  7.2.4 Proofs Related to Section 3.4

Proof [of Theorem 14] It is easy to see that $\bar{f}_{\mathrm{P},\mathrm{E}}$
defined by (41) satisfies $\bar{f}_{\mathrm{P},\mathrm{E}}\in E$ and
$\lambda_{1}\|\bar{f}_{\mathrm{P},\mathrm{E}}\|_{E}\leq\lambda_{1}/T$.
Moreover, by Jensen’s inequality, we have

$\displaystyle\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}$
$\displaystyle=\int_{\mathcal{X}}\biggl{(}\frac{1}{T}\sum_{t=1}^{T}\bar{f}_{\mathrm{P}}^{p,t}-f_{L,\mathrm{P}}^{*}\biggr{)}^{2}\,d\mathrm{P}_{X}$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\int_{\mathcal{X}}(\bar{f}_{\mathrm{P}}^{p,t}-f_{L,\mathrm{P}}^{*})^{2}\,d\mathrm{P}_{X}$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T}\int_{\mathcal{X}}\frac{1}{K}\sum_{k=1}^{K}(f_{\mathrm{P}}^{p,t,k}-f_{L,\mathrm{P}}^{*})^{2}\,d\mathrm{P}_{X}$
$\displaystyle=\frac{1}{TK}\sum_{t=1}^{T}\sum_{k=1}^{K}\biggl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p,t,k})-\mathcal{R}_{L,\mathrm{P}}^{*}\biggr{)}.$

Combining this with Proposition 33, we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{t,k})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}$
$\displaystyle\leq(2r)^{2\alpha}d(2^{-p})^{\frac{1-4^{-\alpha}}{d\log 2}}.$

Consequently we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bar{A}(\lambda)$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\inf_{f\in\bar{E}}\lambda_{1}\|f\|_{\bar{E}}+\lambda_{2}\Omega(h)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\biggr{)}$
$\displaystyle\leq\lambda_{1}\|\bar{f}_{\mathrm{P},\mathrm{E}}\|_{\bar{E}}+\lambda_{2}\Omega(p)+\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}$
$\displaystyle\leq\lambda_{1}/T+c\cdot\lambda_{2}^{\frac{1-4^{-\alpha}}{2d\log
2+(1-4^{-\alpha})}}.$

Then, Theorem 35 implies that with probability $\mathrm{P}^{n}$ not less than
$1-3/n^{2}$, there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\lambda_{1}\|f\|_{\bar{E}}+\lambda_{2}\Omega(p)+\mathcal{R}_{L,\mathrm{D}}(\bar{f}_{\mathrm{D},B})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}$
$\displaystyle\leq 6\lambda_{1}/T+6c\lambda_{2}^{\frac{1-4^{-\alpha}}{2d\log
2+(1-4^{-\alpha})}}+3c_{0}^{\prime}T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2}+3456M^{2}(2\log
n)/n,$ (59)

where $\delta=1/(d\cdot 2^{p})$, $c$ and $c_{0}^{\prime}$ are constants
defined as in Proposition 33 and Theorem 34. Minimizing the right hand side of
(57), we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{D},B})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}\leq
c^{\prime\prime}n^{-\frac{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{-\alpha})+2d\log
2}},$ (60)

if we choose

$\displaystyle\lambda_{1,n}=n^{-\frac{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{\alpha})+2d\log
2}},\,\lambda_{2,n}=n^{-\frac{2(1-4^{-\alpha}+2d\log
2)}{(4-2\delta)(1-4^{-\alpha})+2d\log 2}},\,p_{n}\asymp\frac{2d\log 2\log
n}{(4-2\delta)(1-4^{-\alpha})+2d\log 2},$

where $c^{\prime\prime}$ is a constant depending on $c$, $c_{0}^{\prime}$,
$d$, $M$, $R$ and $T$. Consequently, by the Borel-Cantelli Lemma, (58) holds
with probability $\mathrm{P}^{n}$ equal to one for sufficiently large $n$,
which leads to the desired assertion.

###  7.3 Proofs for $f^{*}_{L,\mathrm{P}}\in C^{1,0}$

####  7.3.1 Proofs Related to Section 6.3.1

Proof [of Proposition 36] According to the rotated binary histogram splitting
rule, the rotation transformation $\\{H_{t}\\}_{t=1}^{T}$ and split
coordinates $\\{Z_{t}\\}_{t=1}^{T}$ are i.i.d. Therefore, for any $x\in
B_{r,d}$, the expected approximation error term can be decomposed as follows:

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}(f_{\mathrm{P},\mathrm{E}}(x)-\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P},\mathrm{E}}(x)))+\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P},\mathrm{E}}(x))-f_{L,\mathrm{P}}^{*}(x))\bigr{)}^{2}$
$\displaystyle=\mathrm{Var}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P},\mathrm{E}}(x))+(\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P},\mathrm{E}}(x))-f_{L,\mathrm{P}}^{*}(x))^{2}$
$\displaystyle=\frac{1}{T}\cdot\mathrm{Var}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p,1}(x))+\bigl{(}\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p,1}(x))-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}.$
(61)

For the first term in (61), the assumption $f_{L,\mathrm{P}}^{*}\in C^{1,0}$
implies

$\displaystyle\mathrm{Var}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P}}^{p}(x)\bigr{)}$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P}}^{p}(x)-\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p}(x))\bigr{)}^{2}$
$\displaystyle\leq\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P}}^{p}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}f_{L,\mathrm{P}}^{*}(x^{\prime})\,d\mathrm{P}_{X}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)\biggr{)}^{2}$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}\bigl{(}f_{L,\mathrm{P}}^{*}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)\bigr{)}\,d\mathrm{P}_{X}(x^{\prime})\biggr{)}^{2}$
$\displaystyle\leq\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}c_{L}\mathrm{diam}\bigl{(}A_{p}(x)\bigr{)}\bigr{)}^{2}$
(62)

According to Lemma 23, the first term is further bounded by

$\displaystyle\mathrm{Var}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P}}^{p}(x)\bigr{)}\leq
c_{L}^{2}(2r)^{4}d\exp\biggl{(}-\frac{0.75p}{d}\biggr{)}.$ (63)

We now consider the second term in (61). Taking the first-order Taylor
expansion of $f_{L,\mathrm{P}}^{*}(x^{\prime})$ at $x$, we get

$\displaystyle f_{L,\mathrm{P}}^{*}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)$
$\displaystyle=\int_{0}^{1}\bigl{(}\nabla
f_{L,\mathrm{P}}^{*}(x+t(x^{\prime}-x))\bigr{)}^{\top}(x^{\prime}-x)\,dt.$
(64)

Therefore, there holds

$\displaystyle\bigl{|}f_{L,\mathrm{P}}^{*}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)-\nabla
f_{L,\mathrm{P}}^{*}(x)^{\top}(x^{\prime}-x)\bigr{|}$
$\displaystyle=\biggl{|}\int_{0}^{1}\bigl{(}\nabla
f_{L,\mathrm{P}}^{*}(x+t(x^{\prime}-x))-\nabla
f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{\top}(x^{\prime}-x)\,dt\biggr{|}$
$\displaystyle\leq\int^{1}_{0}c_{L}(t\|x^{\prime}-x\|_{2})^{\alpha}\|x^{\prime}-x\|_{2}\,dt$
$\displaystyle\leq c_{L}\|x^{\prime}-x\|^{1+\alpha}.$

Now, by the triangle inequality, we have

$\displaystyle\biggl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}(f^{*}_{L,\mathrm{P}}(x^{\prime})-f^{*}_{L,\mathrm{P}}(x))d\mathrm{P}_{X}(x^{\prime})\biggr{)}\biggr{|}$
$\displaystyle\quad-\biggl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)d\mathrm{P}_{X}(x^{\prime})\biggr{)}\biggr{|}$
$\displaystyle\leq\biggl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}(f^{*}_{L,\mathrm{P}}(x^{\prime})-f^{*}_{L,\mathrm{P}}(x)-\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x))d\mathrm{P}(x^{\prime})\biggr{)}\biggr{|}$
$\displaystyle\leq\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{c_{L}}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}\|x^{\prime}-x\|^{1+\alpha}d\mathrm{P}(x^{\prime})\biggr{)}$
$\displaystyle\leq
c_{L}\mathbb{E}_{\mathrm{P}_{R,Z}}(\mathrm{diam}(A_{p}(x))^{1+\alpha}).$

Then we get

$\displaystyle\big{|}\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p,1}(x))-f_{L,\mathrm{P}}^{*}(x)\big{|}$
$\displaystyle\leq\biggl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{\mathrm{P}_{X}(A_{p}(x))}\int_{A_{p}(x)}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)d\mathrm{P}_{X}(x^{\prime})\biggr{|}+c_{L}\mathbb{E}_{\mathrm{P}_{R,Z}}(\mathrm{diam}(A_{p}(x))^{1+\alpha})$
$\displaystyle\leq\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\frac{1}{c_{r,d}\mathrm{P}_{X}(A_{p}(x))}\biggl{|}\int_{A_{p}(x)\cap
B_{r,d}}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)dx^{\prime}\biggr{|}\biggr{)}+c_{L}\mathbb{E}_{\mathrm{P}_{R,Z}}(\mathrm{diam}(A_{p}(x))^{1+\alpha}),$
(65)

where $c_{r,d}:=d^{d/2}/((2r)^{d})$ is a constant. By making the substitution
$x^{\prime}=R^{-1}\cdot\tilde{x}^{\prime}$ and writing $\tilde{x}:=R\cdot x$,
we obtain

$\displaystyle\biggl{|}\int_{A_{p}(x)\cap B_{r,d}}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)dx^{\prime}\biggr{|}$
$\displaystyle=\biggl{|}\int_{H(A_{p}(x)\cap B_{r,d})}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}R^{-1}(\tilde{x}^{\prime}-\tilde{x})d\tilde{x}^{\prime}\biggr{|}$
$\displaystyle=\biggl{|}\int_{H(A_{p}(x)\cap B_{r,d})}(R\cdot\nabla
f^{*}_{L,\mathrm{P}}(x))^{\top}(\tilde{x}^{\prime}-\tilde{x})d\tilde{x}^{\prime}\biggr{|}.$
(66)

Since $f^{*}_{L,\mathrm{P}}\in C^{1,0}$ we have $\|\nabla
f^{*}_{L,\mathrm{P}}\|\leq c_{L}$, recall that $R$ is a orthogonal matrix,
thus we find

$\displaystyle\|R\cdot\nabla
f^{*}_{L,\mathrm{P}}(x)\|_{\infty}\leq\|R\cdot\nabla
f^{*}_{L,\mathrm{P}}(x)\|=\sqrt{(R\cdot\nabla
f^{*}_{L,\mathrm{P}}(x))^{\top}H\nabla f^{*}_{L,\mathrm{P}}(x)}=\|\nabla
f^{*}_{L,\mathrm{P}}(x)\|\leq c_{L}.$

Together with (7.3.1), we find

$\displaystyle\biggl{|}\int_{A_{p}(x)\cap B_{r,d}}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)dx^{\prime}\biggr{|}\leq
c_{L}\sum^{d}_{j=1}\biggl{|}\int_{H(A_{p}(x)\cap
B_{r,d})}(\tilde{x}_{j}^{\prime}-\tilde{x}_{j})d\tilde{x}^{\prime}\biggr{|},$
(67)

where $\tilde{x}_{j}$ and $\tilde{x}_{j}^{\prime}$ denote the $j$-th entries
of the vectors $\tilde{x}$ and $\tilde{x}^{\prime}$ respectively.

Recall that $\underline{a}_{p}^{j}(x)$ and $\overline{a}_{p}^{j}(x)$ denotes
the minimum and maximum values of the $j$-th entries of points in
$H(A_{p}(x))$. Moreover, by the construction of rotated binary histogram,
there holds

$\displaystyle
H(A_{p}(x))=[\underline{a}_{p}^{1}(x),\overline{a}_{p}^{1}(x)]\times\cdots\times[\underline{a}_{p}^{d}(x),\overline{a}_{p}^{d}(x)].$

Since $A_{p}(x)\cap B_{r,d}\subset A_{p}(x)$, we have
$|\tilde{x}^{\prime}_{j}-\tilde{x}_{j}|\leq\overline{a}_{p}^{j}(x)-\underline{a}_{p}^{j}(x)$
for any $\tilde{x}^{\prime},\tilde{x}\in A_{p}(x)\cap B_{r,d}$ and $1\leq
j\leq d$. Consequently, we get

$\displaystyle\biggl{|}\int_{H(A_{p}(x)\cap
B_{r,d})}(\tilde{x}_{j}^{\prime}-\tilde{x}_{j})\,d\tilde{x}^{\prime}\biggr{|}$
$\displaystyle\leq\int_{H(A_{p}(x)\cap
B_{r,d})}|\tilde{x}_{j}^{\prime}-\tilde{x}_{j}|\,d\tilde{x}^{\prime}$
$\displaystyle\leq(\overline{a}_{p}^{j}(x)-\underline{a}_{p}^{j}(x))\int_{H(A_{p}(x)\cap
B_{r,d})}\,d\tilde{x}^{\prime}$ $\displaystyle=\mu(H(A_{p}(x)\cap
B_{r,d}))(\overline{a}_{p}^{j}(x)-\underline{a}_{p}^{j}(x))$
$\displaystyle=\mu(A_{p}(x)\cap B_{r,d})A_{p}^{j}(x),$ (68)

where we use the fact that an orthogonal transformation is volume-preserving.
Combining (67) with (7.3.1), we obtain

$\displaystyle\biggl{|}\int_{A_{p}(x)\cap B_{r,d}}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)\,dx^{\prime}\biggr{|}\leq
c_{L}\mu(A_{p}(x)\cap B_{r,d})\sum^{d}_{j=1}A_{p}^{j}(x).$ (69)

Then (7.3.1) together with (7.3.1) yields

$\displaystyle\frac{1}{c_{r,d}\mathrm{P}_{X}(A_{p}(x))}\biggl{|}\int_{A_{p}(x)\cap
B_{r,d}}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)\,dx^{\prime}\biggr{|}$
$\displaystyle=\frac{1}{c_{r,d}\mathrm{P}_{X}(A_{p}(x))}\biggl{|}\int_{H(A_{p}(x)\cap
B_{r,d})}\nabla
f^{*}_{L,\mathrm{P}}(x)^{\top}(x^{\prime}-x)\,dx^{\prime}\biggr{|}$
$\displaystyle\leq\frac{c_{L}\mu(A_{p}(x)\cap
B_{r,d})}{c_{r,d}\mathrm{P}_{X}(A_{p}(x))}\sum^{d}_{j=1}A_{p}^{j}(x)=c_{L}\sum^{d}_{j=1}A_{p}^{j}(x).$

Combining this with (7.3.1), we obtain

$\displaystyle\bigl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p,1}(x))-f_{L,\mathrm{P}}^{*}(x)\bigr{|}\leq
c_{L}\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\sum^{d}_{j=1}A_{p}^{j}(x)\biggr{)}+\mathbb{E}_{\mathrm{P}_{R,Z}}({\mathrm{diam}(A_{p}(x))}^{1+\alpha}).$
(70)

By (25), we have

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\sum^{d}_{j=1}A_{p}^{j}(x)\biggr{)}=\sum^{d}_{j=1}\mathbb{E}_{\mathrm{P}_{R}}\mathbb{E}_{\mathrm{P}_{Z}}(A_{p}^{j}(x)|R)=2rd\biggl{(}1-\frac{1}{2d}\biggr{)}^{p}\leq
2rd\exp\biggl{(}-\frac{p}{2d}\biggr{)}.$ (71)

Moreover, Lemma 23 implies

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}({\mathrm{diam}(A_{p}(x))}^{1+\alpha})\leq(2r)^{1+\alpha}d\exp\biggl{(}\frac{(2^{-\alpha-1}-1)p}{d}\biggr{)}.$
(72)

Combining (71), (72) with (70), we get

$\displaystyle\bigl{|}\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{p,1}(x))-f_{L,\mathrm{P}}^{*}(x)\bigr{|}$
$\displaystyle\leq
2c_{L}rd\exp\biggl{(}-\frac{p}{2d}\biggr{)}+c_{L}(2r)^{1+\alpha}d\exp\biggl{(}\frac{(2^{-\alpha-1}-1)p}{d}\biggr{)}$
$\displaystyle\leq 2c_{L}(2r)^{\alpha+1}d\exp\biggl{(}-\frac{p}{2d}\biggr{)}.$
(73)

Combining (63), (7.3.1) with (61), we find

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}\leq\frac{c_{L}^{2}(2r)^{4}d}{T}\exp\biggl{(}-\frac{0.75p}{d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)}.$

Taking expectation with respect to $\mathrm{P}_{X}$, we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{X}}\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}\leq\frac{c_{L}^{2}(2r)^{4}d}{T}\exp\biggl{(}-\frac{0.75p}{d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)},$

which leads to the desired assertion by exchanging the order of integration.

####  7.3.2 Proofs Related to the Upper Bound in Section 3.3

Proof [of Theorem 9] It is easy to see that $\bar{f}_{\mathrm{P},\mathrm{E}}$
defined by (37) satisfies $\bar{f}_{\mathrm{P},\mathrm{E}}\in\bar{E}$ and
$\lambda_{1}\|f_{\mathrm{P},\mathrm{E}}\|_{\bar{E}}\leq\lambda_{1}/T$. Then we
have

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bar{A}(\lambda)$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\inf_{f\in\bar{E}}\lambda_{1}\|f\|_{\bar{E}}+\lambda_{2}\Omega(h)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\biggr{)}$
$\displaystyle\leq\lambda_{1}\|f_{\mathrm{P},\mathrm{E}}\|_{\bar{E}}+\lambda_{2}\Omega(h)+\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}.$

Applying Proposition 36, we find

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bar{A}(\lambda)\leq\lambda_{1}/T+\frac{c_{L}^{2}(2r)^{4}d}{T}\exp\biggl{(}-\frac{3p}{4d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)}.$

This together with Theorem 34 implies that with probability at least
$1-3/n^{2}$, there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle\lesssim\frac{\lambda_{1}}{T}+\lambda_{2}\cdot
4^{p}+\exp\biggl{(}-\frac{p}{d}\biggr{)}+\frac{1}{T}\exp\biggl{(}-\frac{3p}{4d}\biggr{)}+T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2}+3456M^{2}\biggl{(}\frac{2\log
n}{n}\biggr{)},$

where $\delta^{\prime}:=1-\delta$ and $\delta:=1/(d\cdot 2^{p})$. Choosing

$\displaystyle\lambda_{1,n}:=n^{-\frac{3}{4(2-\delta+d\log
2)}},\,\lambda_{2,n}:=n^{-\frac{2d\log 2+1}{2-\delta+d\log
2}},\,T_{n}:=n^{\frac{1}{4(2-\delta+d\log 2)}},\,p_{n}:=\frac{d\log
n}{2-\delta+d\log 2},$

we obtain that with probability $\mathrm{P}^{n}$ not less than $1-3/n^{2}$,
there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}\lesssim
n^{-\frac{1}{2-\delta+d\log 2}}.$

Consequently, by the Borel-Cantelli Lemma, (22) holds with probability
$\mathrm{P}^{n}$ equal to one for sufficiently large $n$. This completes the
proof.

####  7.3.3 Proofs Related to Section 3.5

Proof [of Theorem 16] It is easy to see that $\bar{f}_{\mathrm{P},\mathrm{E}}$
defined by (41) satisfies $\bar{f}_{\mathrm{P},\mathrm{E}}\in\bar{E}$ and
$\lambda_{1}\|f\bar{f}_{\mathrm{P},\mathrm{E}}\|_{\bar{E}}\leq\lambda_{1}/T$.
Then we have

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bar{A}(\lambda)$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\biggl{(}\inf_{f\in\bar{E}}\lambda_{1}\|f\|_{\bar{E}}+\lambda_{2}\Omega(h)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\biggr{)}$
$\displaystyle\leq\lambda_{1}\|f_{\mathrm{P},\mathrm{E}}\|_{\bar{E}}+\lambda_{2}\Omega(h)+\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}.$

Applying Proposition 36, we find

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bar{A}(\lambda)\leq\frac{\lambda_{1}}{T}+\frac{c_{L}^{2}(2r)^{4}d}{TK}\exp\biggl{(}-\frac{3p}{4d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)}.$

This together with Theorem 35 implies that with probability at least
$1-3/n^{2}$, there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle\lesssim\frac{\lambda_{1}}{T}+\lambda_{2}\cdot
4^{p}+\exp\biggl{(}-\frac{p}{d}\biggr{)}+\frac{1}{TK}\exp\biggl{(}-\frac{3p}{4d}\biggr{)}+T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2}+3456M^{2}\biggl{(}\frac{2\log
n}{n}\biggr{)},$

where $\delta^{\prime}:=1-\delta$ and $\delta:=1/(d\cdot 2^{p})$. Choosing

$\displaystyle\lambda_{1,n}:=n^{-\frac{3}{4(2-\delta+d\log
2)}},\,\lambda_{2,n}:=n^{-\frac{2d\log 2+1}{2-\delta+d\log
2}},\,T_{n}K_{n}:=n^{\frac{1}{4(2-\delta+d\log 2)}},\,p_{n}:=\frac{d\log
n}{2-\delta+d\log 2},$

we obtain that with probability $\mathrm{P}^{n}$ not less than $1-3/n^{2}$,
there holds

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}\lesssim
n^{-\frac{1}{2-\delta+d\log 2}}.$

Consequently, by the Borel-Cantelli Lemma, (24) holds with probability
$\mathrm{P}^{n}$ equal to one for sufficiently large $n$. This completes the
proof.

####  7.3.4 Proofs Related to Section 6.3.2

Proof [of Proposition 37] According to the rotated binary histogram splitting
rule, the rotation transformation $\\{H_{t}^{k}\\}$ and split coordinates
$\\{Z_{t}^{k}\\}$, $1\leq t\leq T$, $1\leq k\leq K$ are i.i.d. Therefore, for
any $x\in B_{r,d}$, the expected approximation error term can be decomposed as
follows:

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\bar{f}_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}$
$\displaystyle=\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}(\bar{f}_{\mathrm{P},\mathrm{E}}(x)-\mathbb{E}_{\mathrm{P}_{R,Z}}(\bar{f}_{\mathrm{P},\mathrm{E}}(x)))+\mathbb{E}_{\mathrm{P}_{R,Z}}(\bar{f}_{\mathrm{P},\mathrm{E}}(x))-f_{L,\mathrm{P}}^{*}(x))\bigr{)}^{2}$
$\displaystyle=\mathrm{Var}_{\mathrm{P}_{R,Z}}(\bar{f}_{\mathrm{P},\mathrm{E}}(x))+(\mathbb{E}_{\mathrm{P}_{R,Z}}(\bar{f}_{\mathrm{P},\mathrm{E}}(x))-f_{L,\mathrm{P}}^{*}(x))^{2}$
$\displaystyle=\frac{1}{KT}\cdot\mathrm{Var}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{1,1}(x))+\bigl{(}\mathbb{E}_{\mathrm{P}_{R,Z}}(f_{\mathrm{P}}^{1,1}(x))-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}.$
(74)

Combining (74) with (63) and (7.3.1), we find

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}\leq\frac{c_{L}^{2}(2r)^{4}d}{KT}\exp\biggl{(}-\frac{0.75p}{d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)}.$

Taking expectation with respect to $\mathrm{P}_{X}$, we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{X}}\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}f_{\mathrm{P},\mathrm{E}}(x)-f_{L,\mathrm{P}}^{*}(x)\bigr{)}^{2}\leq\frac{c_{L}^{2}(2r)^{4}d}{KT}\exp\biggl{(}-\frac{0.75p}{d}\biggr{)}+4c_{L}^{2}(2r)^{2\alpha+2}d^{2}\exp\biggl{(}-\frac{p}{d}\biggr{)},$

which leads to the desired assertion by exchanging the order of integration.

####  7.3.5 Proofs Related to Section 6.3.3

We first show proofs for lower bound of approximation error for binary
histogram regression.

Proof [of Proposition 38] Recall that the regression model is defined as
$Y=f(X)+\varepsilon$. Considering the case when $X$ has the uniform
distribution, for any $j\in\mathcal{I}_{p}$ and $x\in A_{j}$, we have

$\displaystyle
f_{\mathrm{P}}^{p}(x)=\frac{1}{\mathrm{P}_{X}(A_{j})}\int_{A_{j}}f(x^{\prime})\,d\mathrm{P}_{X}(x^{\prime})=\frac{1}{\mu(A_{j})}\int_{A_{j}}f(x^{\prime})\,dx^{\prime}.$

Since $f(x)\in C^{1,0}$, according to the mean-value theorem, there exists
$x^{j}\in A_{j}$ such that

$\displaystyle
f(x^{j})=\frac{1}{\mu(A_{j})}\int_{A_{j}}f(x^{\prime})\,dx^{\prime}=f_{\mathrm{P}}^{p}(x).$

Consequently, we have

$\displaystyle\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}$
$\displaystyle=\frac{1}{(2r)^{d}}\int_{B_{r}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}\,dx$
$\displaystyle=\frac{1}{(2r)^{d}}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}\,dx$
$\displaystyle=\frac{1}{(2r)^{d}}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}(f(x^{j})-f(x))^{2}\,dx.$
(75)

Let $g(t):=f(x^{j}+t(x-x^{j}))-f(x^{j})$, $0\leq t\leq 1$. Since $f(x)\in
C^{1,0}$, $g(t)$ is differentiable at every $t\in(0,1)$. According to
Lagrange’s mean value theorem, there exists $t^{*}\in(0,1)$ such that

$\displaystyle g(1)-g(0)=g^{\prime}(t^{*})=\nabla
f(x^{j}+t^{*}(x-x^{j}))^{\top}(x-x^{j}).$

Let $\xi_{j,x}^{*}:=x^{j}+t^{*}(x-x^{j})$. Then we have

$\displaystyle(f(x^{j})-f(x))^{2}=(\nabla
f(\xi_{j,x}^{*})(x-x^{j}))^{\top}\nabla f(\xi_{j,x}^{*})(x-x^{j})=\|\nabla
f(\xi_{j,x}^{*})\|^{2}\|x-x^{j}\|^{2}.$

Since $\|\nabla f\|\geq\underline{c}_{f}$, we have

$\displaystyle(f(x^{j})-f(x))^{2}\geq\underline{c}_{f}^{2}\|x-x^{j}\|^{2}.$

Combining this with (7.3.5), we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}$
$\displaystyle\geq\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}\|x-x^{j}\|^{2}\,dx$
$\displaystyle=\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum_{j\in\mathcal{I}_{p}}\sum^{d}_{i=1}\int_{A_{j}}|x_{i}-x^{j}_{i}|^{2}\,dx$
$\displaystyle=\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum^{d}_{i=1}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}(x_{i}-x^{j}_{i})^{2}\,dx,$
(76)

where $x_{i}^{j}$ denotes the $i$-th entry of the vector $x^{j}$. Let
$\underline{a}_{j}^{i}$ and $\overline{a}_{j}^{i}$ be the minimum and maximum
values of the $i$-th coordinates of points in $A_{j}$. Since $H(x)=x$ is an
identity map, by the construction of the binary histogram partition, we have

$\displaystyle
A_{j}=[\underline{a}_{j}^{1},\overline{a}_{j}^{1}]\times\cdots\times[\underline{a}_{j}^{d},\overline{a}_{j}^{d}].$

Moreover, let $h(t):=\int_{A_{j}}(x_{i}-t)^{2}\,dx$. Then by the iterated
integral rule, we have

$\displaystyle h(t)$ $\displaystyle=\prod_{s\neq
i}(\overline{a}_{j}^{s}-\underline{a}_{j}^{s})\int_{\underline{a}_{j}^{i}}^{\overline{a}_{j}^{i}}(x_{i}-t)^{2}\,dx_{i}$
$\displaystyle=\prod_{s\neq
i}(\overline{a}_{j}^{s}-\underline{a}_{j}^{s})\biggl{(}(\overline{a}_{j}^{i}-\underline{a}_{j}^{i})t^{2}-2t\int_{\underline{a}_{j}^{i}}^{\overline{a}_{j}^{i}}x_{i}\,dx_{i}+\int_{\underline{a}_{j}^{i}}^{\overline{a}_{j}^{i}}x_{i}^{2}\,dx_{i}\biggr{)}$
$\displaystyle\geq
h\biggl{(}\frac{\underline{a}_{j}^{i}+\overline{a}_{j}^{i}}{2}\biggr{)}.$

Consequently, we get

$\displaystyle\int_{A_{j}}(x_{i}-x^{j}_{i})^{2}\,dx=h(x_{i}^{j})\geq
h\biggl{(}\frac{\underline{a}_{j}^{i}+\overline{a}_{j}^{i}}{2}\biggr{)}=\int_{A_{j}}\biggl{(}x_{i}-\frac{\underline{a}_{j}^{i}+\overline{a}_{j}^{i}}{2}\biggr{)}^{2}\,dx.$

This together with (7.3.5) implies

$\displaystyle\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}$
$\displaystyle\geq\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum^{d}_{i=1}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}\biggl{(}x_{i}-\frac{\underline{a}_{j}^{i}+\overline{a}_{j}^{i}}{2}\biggr{)}^{2}\,dx$
$\displaystyle=\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum^{d}_{i=1}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}\biggl{(}x_{i}-\frac{\underline{a}_{p}^{i}(x)+\overline{a}_{p}^{i}(x)}{2}\biggr{)}^{2}\,dx$
$\displaystyle=\underline{c}_{f}^{2}\mathbb{E}_{\mathrm{P}_{X}}\sum^{d}_{i=1}\biggl{(}x_{i}-\frac{\underline{a}_{p}^{i}(x)+\overline{a}_{p}^{i}(x)}{2}\biggr{)}^{2},$

where $\underline{a}_{p}^{i}(x)$ and $\overline{a}_{p}^{i}(x)$ are the minimum
and maximum values of the $i$-th coordinates of points in $A_{p}(x)$.
Therefore, we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}\geq\underline{c}_{f}^{2}\mathbb{E}_{\mathrm{P}_{X}}\sum^{d}_{i=1}\mathbb{E}_{\mathrm{P}_{Z}}\biggl{(}x_{i}-\frac{\underline{a}_{p}^{i}(x)+\overline{a}_{p}^{i}(x)}{2}\biggr{)}^{2}.$
(77)

Let $S_{p}^{i}(x)$ be the number of times that $A_{p}(x)$ is split on the
$i$-th coordinate. According to Lemma 24, if $S_{p}^{i}(x)=k$, $0\leq k\leq
q$, then we have

$\displaystyle\biggl{|}x_{i}-\frac{\underline{a}_{p}^{i}(x)+\overline{a}_{p}^{i}(x)}{2}\biggr{|}=\min_{q\in
Q_{k}}|x_{i}-q|,$

where

$\displaystyle
Q_{k}=\biggl{\\{}\frac{r(2j-1)}{2^{k}}\,\bigg{|}\,-2^{k-1}+1\leq j\leq
2^{k-1}\biggr{\\}}.$

Therefore, we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{Z}}\biggl{(}x_{i}-\frac{\underline{a}_{p}^{i}(x)+\overline{a}_{p}^{i}(x)}{2}\biggr{)}^{2}=\sum^{p}_{k=0}\mathrm{P}_{Z}(S_{p}^{i}(x)=k)\min_{q\in
Q_{k}}(x_{i}-q)^{2}.$

This together with (77) implies

$\displaystyle\mathbb{E}_{\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}$
$\displaystyle\geq\underline{c}_{f}^{2}\mathbb{E}_{\mathrm{P}_{X}}\sum^{d}_{i=1}\sum^{p}_{k=0}\mathrm{P}_{Z}(S_{p}^{i}(x)=k)\min_{q\in
Q_{k}}(x_{i}-q)^{2}$
$\displaystyle=\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\int_{B_{r}}\sum^{d}_{i=1}\sum^{p}_{k=0}\mathrm{P}_{Z}(S_{p}^{i}(x)=k)\min_{q\in
Q_{k}}(x_{i}-q)^{2}\,dx$
$\displaystyle=\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum^{d}_{i=1}\biggl{(}\sum^{p}_{k=0}f(k,p,1/d)\int_{B_{r}}\min_{q\in
Q_{k}}(x_{i}-q)^{2}\,dx\biggr{)},$ (78)

where $f(k,p,1/d)=\binom{p}{k}(\frac{1}{d})^{k}(1-\frac{1}{d})^{n-k}$. By the
definition of $Q_{k}$, we have

$\displaystyle\int_{B_{r}}\min_{q\in Q_{k}}(x_{i}-q)^{2}\,dx$
$\displaystyle=(2r)^{d-1}\int_{-r}^{r}\min_{q\in Q_{k}}(x_{i}-q)^{2}\,dx_{i}$
$\displaystyle=(2r)^{d-1}\cdot
2^{k+1}\int_{r-r/2^{k}}^{r}(x_{i}-(r-r/2^{k}))^{2}\,dx_{i}$
$\displaystyle=\frac{3(2r)^{d-1}}{2}\cdot\frac{r^{3}}{2^{2k}}.$

This together with (7.3.5) implies

$\displaystyle\mathbb{E}_{\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(x)-f(x))^{2}\geq\frac{\underline{c}_{f}^{2}}{(2r)^{d}}\sum^{d}_{i=1}\biggl{(}\sum^{p}_{k=0}2^{-2k}\cdot
f(k,p,1/d)\biggr{)}=\frac{3\underline{c}_{f}^{2}r^{2}d}{4}\biggl{(}1-\frac{3}{4d}\biggr{)}^{p},$

which completes the proof.

Then we present proofs for lower bound of sample error for binary histogram
regression.

Proof [of Proposition 39] Since $H(x)=x$ is a identity map, for any fixed
split coordinates $Z=\\{Z_{i,j},1\leq i\leq p,1\leq j\leq 2^{i-1}\\}$,
$\\{A_{j}\\}_{j\in\mathcal{I}_{p}}$ forms a partition of $B_{r}$, then for
$j\in\mathcal{I}_{p}$ we define the random variable $N_{j}$ by

$\displaystyle N_{j}:=\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i}).$

Since the random variables $\\{\boldsymbol{1}_{A_{j}}(X_{i})\\}_{i=1}^{n}$ are
i.i.d. Bernoulli distributed with parameter $\mathrm{P}_{X}(x\in A_{j})$, it
is clear to see that the random variable $N_{j}$ is Binomial distributed with
parameters $n$ and $\mathrm{P}_{X}(x\in A_{j})$. Therefore, for any
$j\in\mathcal{I}_{p}$, we have

$\displaystyle\mathbb{E}(N_{j})=n\cdot\mathrm{P}_{X}(x\in A_{j}).$

Moreover, the GBBH regressor $f_{\mathrm{D}}^{p}$ can be defined by

$\displaystyle
f_{\mathrm{D}}^{p}(x)=\begin{cases}\displaystyle\frac{\sum_{i=1}^{n}Y_{i}\boldsymbol{1}_{A_{j}}(X_{i})}{\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})}\cdot\boldsymbol{1}_{A_{j}}(x)&\text{
if }N_{j}>0,\\\ 0&\text{ if }N_{j}=0.\end{cases}$

By the law of total probability, we get

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\mathbb{E}_{\mathrm{P}_{X}}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}$
$\displaystyle=\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j}\bigr{)}\cdot\mathrm{P}_{X}(x\in A_{j})\biggr{)}$
$\displaystyle=\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j},N_{j}>0\bigr{)}\cdot\mathrm{P}(N_{j}>0)\cdot\mathrm{P}_{X}(x\in
A_{j})\biggr{)}$ (79)
$\displaystyle\phantom{=}+\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j},N_{j}=0\bigr{)}\cdot\mathrm{P}(N_{j}=0)\cdot\mathrm{P}_{X}(x\in
A_{j})\biggr{)}.$ (80)

For the term (79), we have

$\displaystyle\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}(f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x))^{2}\big{|}X\in
A_{j},N_{j}>0\bigr{)}\cdot\mathrm{P}(N_{j}>0)\mathrm{P}_{X}(x\in A_{j})$
$\displaystyle=\sum_{j\in\mathcal{I}_{p}}\biggl{(}\frac{\sum_{i=1}^{n}Y_{i}\boldsymbol{1}_{A_{j}}(X_{i})}{\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})}-\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)|X\in
A_{j})\biggr{)}^{2}\cdot\mathrm{P}(N_{j}>0)\mathrm{P}_{X}(x\in A_{j})$
$\displaystyle=\sum_{j\in\mathcal{I}_{p}}\biggl{(}\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})\bigl{(}Y_{i}-\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)|X\in
A_{j})\bigr{)}\biggr{)}^{2}\cdot\frac{\mathrm{P}_{X}(x\in
A_{j})}{(\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i}))^{2}}\cdot\mathrm{P}(N_{j}>0).$

Since for a fixed $j\in\mathcal{I}_{p}$, there holds

$\displaystyle\sum_{j\in\mathcal{I}_{p}}\biggl{(}\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})\bigl{(}Y_{i}-\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)|X\in
A_{j})\bigr{)}\biggr{)}^{2}\cdot\frac{\mathrm{P}_{X}(x\in
A_{j})}{(\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i}))^{2}}$
$\displaystyle=\sum_{j\in\mathcal{I}_{p}}\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}^{2}(X_{i})\mathbb{E}\bigl{(}\bigl{(}Y-f_{\mathrm{P}}^{p}(X)\bigr{)}^{2}\big{|}X\in
A_{j}\bigr{)}\cdot\frac{\mathrm{P}_{X}(x\in
A_{j})}{(\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i}))^{2}}$
$\displaystyle=\sum_{j\in\mathcal{I}_{p}}\frac{\mathrm{P}_{X}(x\in
A_{j})}{\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})}\cdot\mathbb{E}\bigl{(}\bigl{(}Y-f_{\mathrm{P}}^{p}(X))^{2}\big{|}X\in
A_{j}\bigr{)}.$ (81)

Moreover, for any fixed $j\in\mathcal{I}_{p}$, there holds

$\displaystyle\mathbb{E}(f_{\mathrm{P}}^{p}(X)|X\in
A_{j})=\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)|X\in A_{j}).$

Consequently, we obtain

$\displaystyle\mathbb{E}\bigl{(}(Y-f_{\mathrm{P}}^{p}(X))^{2}\big{|}X\in
A_{j}\bigr{)}$
$\displaystyle=\mathbb{E}\bigl{(}(Y-f_{L,\mathrm{P}}^{*}(X))^{2}\big{|}X\in
A_{j}\bigr{)}+\mathbb{E}\bigl{(}(f_{L,\mathrm{P}}^{*}(X)-f_{\mathrm{P}}^{p}(X))^{2}\big{|}X\in
A_{j}\bigr{)}$
$\displaystyle=\sigma^{2}+\mathbb{E}\bigl{(}(f_{L,\mathrm{P}}^{*}(X)-f_{\mathrm{P}}^{p}(X))^{2}\big{|}X\in
A_{j}\bigr{)}.$

Therefore, we get

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j},N_{j}>0\bigr{)}\cdot\mathrm{P}(N_{j}>0)\cdot\mathrm{P}_{X}(x\in
A_{j})\biggr{)}$
$\displaystyle=\bigl{(}\sigma^{2}+\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)-f_{\mathrm{P}}^{p}(X))^{2}\bigr{)}$
$\displaystyle\phantom{=}\cdot\sum_{j\in\mathcal{I}_{p}}\biggl{(}\mathrm{P}_{X}(x\in
A_{j})\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\biggl{(}\sum_{i=1}^{n}\boldsymbol{1}_{A_{j}}(X_{i})\biggr{)}^{-1}\bigg{|}N_{j}>0\biggr{)}\biggr{)}\cdot\mathrm{P}(N_{j}>0)$
$\displaystyle=\bigl{(}\sigma^{2}+\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)-f_{\mathrm{P}}^{p}(X))^{2}\bigr{)}\cdot\sum_{j\in\mathcal{I}_{p}}\bigl{(}\mathrm{P}_{X}(x\in
A_{j})\mathbb{E}_{D\sim\mathrm{P}^{n}}(N_{j}^{-1}|N_{j}>0)\bigr{)}\mathrm{P}(N_{j}>0)$
$\displaystyle=n^{-1}\bigl{(}\sigma^{2}+\mathbb{E}(f_{L,\mathrm{P}}^{*}(X)-f_{\mathrm{P}}^{p}(X))^{2}\bigr{)}\cdot\sum_{j\in\mathcal{I}_{p}}\bigl{(}\mathbb{E}(N_{j})\cdot\mathbb{E}(N_{j}^{-1}|N_{j}>0)\bigr{)}\mathrm{P}(N_{j}>0).$

Clearly, $x^{-1}$ is convex for $x>0$. Therefore, by Jensen’s inequality, we
get

$\displaystyle\mathbb{E}(N_{j})\cdot\mathbb{E}(N_{j}^{-1}|N_{j}>0)\mathrm{P}(N_{j}>0)$
$\displaystyle\geq\mathbb{E}(N_{j})\cdot\mathbb{E}(N_{j}|N_{j}>0)^{-1}\mathrm{P}(N_{j}>0)$
$\displaystyle=\mathbb{E}(N_{j})\cdot\mathbb{E}(N_{j}\boldsymbol{1}_{\\{N_{j}>0\\}})^{-1}\mathrm{P}(N_{j}>0)\mathrm{P}(N_{j}>0)$
$\displaystyle=\mathrm{P}(N_{j}>0)^{2}=(1-\mathrm{P}(N_{j}=0))^{2}$
$\displaystyle=\bigl{(}1-(1-\mathrm{P}_{X}(x\in A_{j}))^{n}\bigr{)}^{2}$
$\displaystyle\geq 1-2e^{-n\mathrm{P}_{X}(x\in A_{j})},$

where the last inequality follows from $(1-x)^{n}\leq e^{-nx}$, $x\in(0,1)$.
Therefore, we have

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j},N_{j}>0\bigr{)}\cdot\mathrm{P}(N_{j}>0)\cdot\mathrm{P}_{X}(x\in
A_{j})\biggr{)}$
$\displaystyle\geq\frac{\sigma^{2}}{n}\sum_{j\in\mathcal{I}_{p}}(1-2e^{-n\mathrm{P}_{X}(x\in
A_{j})})=\frac{\sigma^{2}}{n}\sum_{j\in\mathcal{I}_{p}}(1-2e^{-n/2^{p}})=\frac{\sigma^{2}\cdot
2^{p}}{n}(1-2e^{-n/2^{p}}),$ (82)

where we use the fact that $\mu(A_{j})=(2r)^{d}/2^{p}$ for
$j\in\mathcal{I}_{p}$ by (26) and $\mathrm{P}_{X}$ is the uniform distribution
on $B_{r}$.

We now turn to estimate the term (80). By the definition of
$f_{\mathrm{D}}^{p}$, we have

$\displaystyle\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(X)-f_{\mathrm{P}}^{p}(X))^{2}\big{|}X\in
A_{j},N_{j}=0\bigr{)}\cdot\mathrm{P}(N_{j}=0)\cdot\mathrm{P}_{X}(x\in A_{j})$
$\displaystyle=(2r)^{-d}\sum_{j\in\mathcal{I}_{p}}\biggl{(}\boldsymbol{1}_{\\{N_{j}=0\\}}\int_{A_{j}}f_{\mathrm{P}}^{p}(x)^{2}\,dx\biggr{)}.$

Since for $x\in A_{j}$, we have

$\displaystyle
f_{\mathrm{P}}^{p}(x)=\mu(A_{j})^{-1}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)dx,$

consequently, we obtain

$\displaystyle\sum_{j\in\mathcal{I}_{p}}\biggl{(}\boldsymbol{1}_{\\{N_{j}=0\\}}\int_{A_{j}}f_{\mathrm{P}}^{p}(x)^{2}\,dx\biggr{)}=\sum_{j\in\mathcal{I}_{p}}\frac{\boldsymbol{1}_{\\{N_{j}=0\\}}}{\mu(A_{j})}\biggl{(}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)dx\biggr{)}^{2}.$

Together with (26) in Fact 21, we find

$\displaystyle(2r)^{-d}\sum_{j\in\mathcal{I}_{p}}\biggl{(}\boldsymbol{1}_{\\{N_{j}=0\\}}\int_{A_{j}}f_{\mathrm{P}}^{p}(x)^{2}\,dx\biggr{)}=2^{p}\sum_{j\in\mathcal{I}_{p}}\biggl{(}\biggl{(}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)\,dx\biggr{)}^{2}\cdot\boldsymbol{1}_{\\{N_{j}=0\\}}\biggr{)}.$

Therefore, we get

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\mathbb{E}\bigl{(}\bigl{(}f_{\mathrm{D}}^{p}(x)-f_{\mathrm{P}}^{p}(x)\bigr{)}^{2}\big{|}x\in
A_{j},N_{j}=0\bigr{)}\cdot\mathrm{P}(N_{j}=0)\cdot\mathrm{P}_{X}(x\in
A_{j})\biggr{)}$
$\displaystyle=2^{p}\cdot\mathbb{E}_{D\sim\mathrm{P}^{n}}\sum_{j\in\mathcal{I}_{p}}\biggl{(}\biggl{(}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)\,dx\biggr{)}^{2}\cdot\boldsymbol{1}_{\\{N_{j}=0\\}}\biggr{)}$
$\displaystyle=2^{p}\cdot\sum_{j\in\mathcal{I}_{p}}\biggl{(}\mathrm{P}(N_{j}=0)\biggl{(}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)\,dx\biggr{)}^{2}\biggr{)}$
$\displaystyle=\biggl{(}1-\frac{1}{2^{p}}\biggr{)}^{n}\biggl{(}2^{p}\sum_{j\in\mathcal{I}_{p}}\biggl{(}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)\,dx\biggr{)}^{2}\biggr{)}$
$\displaystyle\geq\biggl{(}1-\frac{1}{2^{p}}\biggr{)}^{n}\biggl{(}\sum_{j\in\mathcal{I}_{p}}\int_{A_{j}}f^{*}_{L,\mathrm{P}}(x)\,dx\biggr{)}^{2}\geq(2r)^{2d}\underline{c}_{f}^{2}\biggl{(}1-\frac{1}{2^{p}}\biggr{)}^{n}.$
(83)

Combining (7.3.5) and (7.3.5), we obtain

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\mathbb{E}_{\mathrm{P}_{X}}\bigl{(}f_{\mathrm{D}}^{p}(X)-f_{\mathrm{P}}^{p}(X)\bigr{)}^{2}\geq\frac{\sigma^{2}\cdot
2^{p}}{n}\biggl{(}1-2\exp\biggl{(}-\frac{n}{2^{p}}\biggr{)}\biggr{)}+(2r)^{2d}\underline{c}_{f}^{2}\biggl{(}1-\frac{1}{2^{p}}\biggr{)}^{n}.$

Taking expectation with respect to $\mathrm{P}_{Z}$, we prove the desired
assertion.

####  7.3.6 Proofs Related to the Lower Bound in Section 3.3

Proof [of Theorem 12] Recall the error decomposition (42). Applying
Propositions 38 and 39, we get

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle=\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}\bigl{(}f_{\mathrm{D}}(X)-f_{L,\mathrm{P}}^{*}(X)\bigr{)}^{2}$
$\displaystyle\geq\frac{3\underline{c}_{f}^{2}r^{2}d}{4}\biggl{(}1-\frac{3}{4d}\biggr{)}^{p}+\frac{\sigma^{2}\cdot
2^{p}}{n}\biggl{(}1-2\exp\biggl{(}-\frac{n}{2^{p}}\biggr{)}\biggr{)}+(2r)^{2d}\underline{c}_{f}^{2}\biggl{(}1-\frac{1}{2^{p}}\biggr{)}^{n}.$

If $\exp(-n/2^{p})\leq 1/4$, we have

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}\geq\frac{3\underline{c}_{f}^{2}r^{2}d}{4}\biggl{(}1-\frac{3}{4d}\biggr{)}^{p}+\frac{\sigma^{2}\cdot
2^{p}}{2n}\geq c_{0}n^{\frac{\log(1-0.75/d)}{\log 2-\log(1-0.75/d)}},$ (84)

where the constant
$c_{0}:=(\sigma^{2}/2)\cdot(3\underline{c}_{f}^{2}r^{2}d/(2\sigma^{2}))^{\frac{\log
2}{\log 2-\log(1-0.75/d)}}$. On the other hand, we turn to the case
$\exp(-n/2^{p})>1/4$. Let $g(x):=\log(1-x)+2\log 2x$, $x\leq 1/2$, we find
$g^{\prime}(x)=-1/(1-x)+2\log 2\leq-1-2\log 2$. It is easy to see that
$g^{\prime}(x)>0$ when $0\leq x<1-1/(2\log 2)$ and $g^{\prime}(x)<0$ when
$1-1/(2\log 2)<x<1/2$, which yields that $g(x)$ is increasing on the interval
$(0,1-1/(2\log 2))$ and decreasing on the interval $(1-1/(2\log 2),1/2)$.
Therefore, for $0<x\leq 1/2$, there holds

$\displaystyle g(x)=\log(1-x)+2\log 2x\geq\min\\{g(0),g(1/2)\\}=0.$

Consequently, we get

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle\geq(2r)^{2d}\underline{c}_{f}^{2}(1-1/2^{p})^{n}$
$\displaystyle=(2r)^{2d}\underline{c}_{f}^{2}\exp\bigl{(}n\log(1-1/2^{p})\bigr{)}$
$\displaystyle\geq(2r)^{2d}\underline{c}_{f}^{2}\exp\bigl{(}-(2n\log
2)/2^{p}\bigr{)}$ $\displaystyle\geq(2r)^{2d}\underline{c}_{f}^{2}(1/4)^{2\log
2}:=c_{1}.$ (85)

Combining (84) with (7.3.6), we find

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}})-R^{*}_{L,\mathrm{P}}\bigr{)}\geq
c_{0}n^{\frac{\log(1-0.75/d)}{\log 2-\log(1-0.75/d)}}\vee c_{1},$

which leads to the desired assertion.

## References

  * Arzamasov et al. (2018) Vadim Arzamasov, Klemens Böhm, and Patrick Jochem.  Towards concise models of grid stability.  In _2018 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm)_ , pages 1–6. IEEE, 2018.
  * Bertin-Mahieux et al. (2011) Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere.  The million song dataset.  In _Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011)_ , 2011.
  * Biau (2012) Gérard Biau.  Analysis of a random forests model.  _The Journal of Machine Learning Research_ , 13(1):1063–1095, 2012.
  * Biau et al. (2019) Gérard Biau, Benoît Cadre, and Laurent Rouvìère.  Accelerated gradient boosting.  _Machine Learning_ , 108(6):971–992, 2019.
  * Blanchard et al. (2003) Gilles Blanchard, Gábor Lugosi, and Nicolas Vayatis.  On the rate of convergence of regularized boosting classifiers.  _The Journal of Machine Learning Research_ , 4(Oct):861–894, 2003.
  * Blaser and Fryzlewicz (2016) Rico Blaser and Piotr Fryzlewicz.  Random rotation ensembles.  _The Journal of Machine Learning Research_ , 17(1):126–151, 2016.
  * Breiman (2000) Leo Breiman.  Some infinity theory for predictor ensembles.  Technical report, Technical Report 579, Statistics Dept. UCB, 2000.
  * Breiman (2001) Leo Breiman.  Random forests.  _Machine Learning_ , 45(1):5–32, 2001.
  * Bühlmann and Yu (2003) Peter Bühlmann and Bin Yu.  Boosting with the $L_{2}$ loss: regression and classification.  _Journal of the American Statistical Association_ , 98(462):324–339, 2003.
  * Burgués and Marco (2018) Javier Burgués and Santiago Marco.  Multivariate estimation of the limit of detection by orthogonal partial least squares in temperature-modulated mox sensors.  _Analytica chimica acta_ , 1019:49–64, 2018.
  * Burgués et al. (2018) Javier Burgués, Juan Manuel Jiménez-Soto, and Santiago Marco.  Estimation of the limit of detection in semiconductor gas sensors through linearized calibration models.  _Analytica chimica acta_ , 1013:13–25, 2018.
  * Cai et al. (2020) Yuchao Cai, Hanyuan Hang, Hanfang Yang, and Zhouchen Lin.  Boosted histogram transform for regression.  In _International Conference on Machine Learning_ , pages 1251–1261. PMLR, 2020.
  * Candanedo et al. (2017) Luis M Candanedo, Véronique Feldheim, and Dominique Deramaix.  Data driven prediction models of energy use of appliances in a low-energy house.  _Energy and buildings_ , 140:81–97, 2017.
  * Chen and Guestrin (2016) Tianqi Chen and Carlos Guestrin.  XGBoost: A scalable tree boosting system.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pages 785–794, 2016.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * Dubout and Fleuret (2014) Charles Dubout and François Fleuret.  Adaptive sampling for large scale boosting.  _The Journal of Machine Learning Research_ , 15(1):1431–1453, 2014.
  * Espinoza et al. (2006) Marcelo Espinoza, Johan A.K. Suykens, and Bart De Moor.  Fixed-size least squares support vector machines: a large scale application in electrical load forecasting.  _Computational Management Science_ , 3(2):113–129, 2006.
  * Fernandes et al. (2015) Kelwin Fernandes, Pedro Vinagre, and Paulo Cortez.  A proactive intelligent decision support system for predicting the popularity of online news.  In _Portuguese Conference on Artificial Intelligence_ , pages 535–546. Springer, 2015.
  * Fonollosa et al. (2015) Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco.  Reservoir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring.  _Sensors and Actuators B: Chemical_ , 215:618–629, 2015\.
  * Freund (1995) Yoav Freund.  Boosting a weak learning algorithm by majority.  _Information and computation_ , 121(2):256–285, 1995.
  * Freund and Schapire (1997) Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  _Journal of Computer and System Sciences_ , 55(1):119–139, 1997.
  * Friedman (2001) Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  _The Annals of Statistics_ , 29(5):1189–1232, 2001.
  * Hamidieh (2018) Kam Hamidieh.  A data-driven statistical model for predicting the critical temperature of a superconductor.  _Computational Materials Science_ , 154:346–354, 2018.
  * Kawala et al. (2013) François Kawala, Ahlame Douzal-Chouakria, Eric Gaussier, and Eustache Dimert.  Prédictions d’activité dans les réseaux sociaux en ligne.  In _4ième conférence sur les modèles et l’analyse des réseaux: Approches mathématiques et informatiques_ , page 16, 2013\.
  * Ke et al. (2017) Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu.  LightGBM: A highly efficient gradient boosting decision tree.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , volume 30, pages 3146–3154, 2017.
  * Lin et al. (2019) Shao-Bo Lin, Yunwen Lei, and Ding-Xuan Zhou.  Boosted kernel ridge regression: Optimal learning rates and early stopping.  _The Journal of Machine Learning Research_ , 20(46):1–36, 2019.
  * López-Rubio (2013) Ezequiel López-Rubio.  A histogram transform for probabilitydensity function estimation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 36(4):644–656, 2013.
  * Lucas et al. (2015) DD Lucas, C Yver Kwok, P Cameron-Smith, H Graven, D Bergmann, TP Guilderson, R Weiss, and R Keeling.  Designing optimal greenhouse gas observing networks that consider performance and cost.  _Geoscientific Instrumentation, Methods and Data Systems_ , 4(1):121–137, 2015.
  * Meister and Steinwart (2016) Mona Meister and Ingo Steinwart.  Optimal learning rates for localized SVMs.  _The Journal of Machine Learning Research_ , 17(194):1–44, 2016.
  * Nesterov (1983) Yu E Nesterov.  A method of solving a convex programming problem with convergence rate $o\bigl{(}\frac{1}{k^{2}}\bigr{)}$.  _Dokl. Akad. Nauk SSSR_ , 269(3):543–547, 1983\.
  * Pace and Barry (1997) R. Kelley Pace and Ronald Barry.  Sparse spatial autoregressions.  _Statistics and Probability Letters_ , 33(3):291– 297, 1997.
  * Park et al. (2009) BU Park, YK Lee, and S Ha.  $L_{2}$ boosting in kernel regression.  _Bernoulli_ , 15(3):599–613, 2009.
  * Park and Apley (2018) Chiwoo Park and Daniel Apley.  Patchwork kriging for large-scale Gaussian process regression.  _The Journal of Machine Learning Research_ , 19(7), 2018\.
  * Park and Huang (2016) Chiwoo Park and Jianhua Z. Huang.  Efficient computation of Gaussian process regression for large spatial data sets by patching local Gaussian processes.  _The Journal of Machine Learning Research_ , 17(174):1–29, 2016.
  * Park et al. (2011) Chiwoo Park, Jianhua Z. Huang, and Yu Ding.  Domain decomposition approach for fast Gaussian process regression of large spatial data sets.  _The Journal of Machine Learning Research_ , 12(May):1697–1728, 2011.
  * Schapire (1990) Robert E Schapire.  The strength of weak learnability.  _Machine Learning_ , 5(2):197–227, 1990.
  * Schapire and Freund (1995) Robert E Schapire and Yoav Freund.  A decision-theoretic generalization of on-line learning and an application to boosting.  In _Second European Conference on Computational Learning Theory_ , pages 23–37, 1995.
  * Steinwart and Christmann (2008) Ingo Steinwart and Andreas Christmann.  _Support Vector Machines_.  Information Science and Statistics. Springer, New York, 2008.
  * Suykens et al. (2002) Johan A.K. Suykens, Tony Van Gestel, Jos De Brabanter, Bart De Moor, and Joos Vandewalle.  _Least Squares Support Vector Machines_.  World Scientific, Singapore, 2002.
  * Thomann et al. (2017) Philipp Thomann, Ingrid Blaschzyk, Mona Meister, and Ingo Steinwart.  Spatial decompositions for large scale SVMs.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pages 1329–1337. PMLR, 2017.
  * Van der Vaart and Wellner (1996) Aad W. Van der Vaart and Jon A. Wellner.  _Weak Convergence and Empirical Processes_.  Springer Series in Statistics. Springer-Verlag, New York, 1996.


# Robustness of the Tangle 2.0 Consensus

working on it at some point or another: Bing, Daria, Piotr, Andreas,
Sebastian, Gal
interested: Billy, Jonas  IOTA Foundation
Berlin, Germany
Email<EMAIL_ADDRESS>Bing-Yang Lin1, Daria Dziubałtowska1, Piotr Macek1,
Andreas Penzkofer1, Sebastian Müller12  1IOTA Foundation, Berlin, Germany
2Aix Marseille Université, CNRS, Centrale Marseille, I2M - UMR 7373, 13453
Marseille, France

###### Abstract

In this paper, we investigate the performance of the Tangle 2.0 consensus
protocol in a Byzantine environment. We use an agent-based simulation model
that incorporates the main features of the Tangle 2.0 consensus protocol. Our
experimental results demonstrate that the Tangle 2.0 protocol is robust to the
bait-and-switch attack up to the theoretical upper bound of the adversary’s
$33\%$ voting weight. We further show that the common coin mechanism in Tangle
2.0 is necessary for robustness against powerful adversaries. Moreover, the
experimental results confirm that the protocol can achieve around $1$s
confirmation time in typical scenarios and that the confirmation times of non-
conflicting transactions are not affected by the presence of conflicts.

###### Index Terms:

simulation, consensus protocol, leaderless, security, fault-tolerance,
directed acyclic graph

##  1 Introduction

Since 2009 when Bitcoin [1] was first introduced, distributed ledger
technologies (DLTs) have gained growing interest from academics, industries,
and even governments [2]. In DLTs, ledger records have no need for central
authority controls or maintenance, and the validity of each record relies on a
decentralized consensus mechanism, or globally accepted truth between
participants, also called nodes, in the network. In Bitcoin, a blockchain is
adopted as the structure to store a ledger, Proof of Work (PoW) as the Sybil
protection, and the longest chain rule as the consensus mechanism. Each block,
which contains transactions, is linked in a linear growing chain. All nodes in
the Bitcoin network are able to extend the chain by solving a numerical
challenge that consumes a considerable amount of computation power. The node
that solves the challenge first is elected as a “leader”, can add the next
block to the chain, and gain a reward. Although Bitcoin was revolutionary in
enabling DLTs in the first place, the PoW mechanism is typically slow [3] and
might demand an unsustainable energy consumption [4]. Also, the single chain
structure of the Bitcoin ledger limits its throughput [5], and has a
scalability problem [6].

As a consequence, instead of using a linear block chain to store the ledger,
many non-linear ledger structures (e.g., SPECTRE [7], Byteball [8], Algorand
[9], PHANTOM [10], Avalanche [11], Prism [12], AlephZero [13], Narwhal [14],
and IOTA [15]) were proposed to improve the performance. The consensus
mechanism in a DAG-based system can be conceptually different from the one in
a linear blockchain system, and the transaction throughput is potentially no
longer limited. In [16], the scalability and efficiency of different DAG-based
blockchain architectures were analyzed, based on their functional data
structures. We also refer to [17] for an overview of the security and
performance of several DAG-based blockchain systems.

###  1.1 Results and contribution

A recent proposal for a DAG-based consensus protocol is the Tangle 2.0
protocol, [18]. Our paper builds on the theoretical foundations and
mathematical models established in [18] and gives a first performance analysis
of the protocol in a Byzantine environment. To this end, we provide an agent-
based simulator, [19], that simulates the peer-to-peer layer, the leaderless
block creations, and the consensus finding simultaneously. In contrast to
previous DAG simulators, such as DAGSim [20], our simulator [19] allows to
consider a Byzantine environment and incorporates the main features of the
Tangle 2.0 consensus.

This work is the first paper that provides quantitative validations of the
Tangle 2.0 consensus protocol. In addition, we show that confirmation time is
in the order of a second. This good performance holds even in highly adverse
environments, where attackers are effective up to their theoretical limits.

The Tangle 2.0 consensus protocol consists of two components: the asynchronous
component, On Tangle Voting (OTV), and the synchronous part, Synchronised
Random Reality Selection (SRRS). To explore the security of these components,
an agent-based attack strategy, called Bait-and-Switch, is introduced in the
simulations. In this kind of attack, adversaries can issue double-spends at
arbitrary high frequency and aim to keep the honest nodes in an undecided
state. The simulation results show that in the worst weight distribution case,
where all the honest nodes have equal weight, the OTV protocol can still
resist the Bait-and-Switch attack when the adversary node owns up to $20\%$ of
the total weight. In addition, we also show that the SRRS protocol can further
resist the Bait-and-Switch attack, even when the adversary occupies up to
$33\%$ of the total weight, which is the theoretical upper bond.

###  1.2 Structure of the paper

In Section 2.2, we introduce the fundamentals of the Tangle 2.0 protocol. In
Section 3, we define the adversary model and describe the Bait-and-Switch
strategy. In Section 4, we describe the components considered in our
simulations and explain the setup in Section 5. The experimental results are
given in 6, and a conclusion can be found in Section 7.

##  2 Fundamentals of the Protocol

We introduce several fundamental concepts relevant to the protocol in our
context. First, we discuss the UTXO accounting model, before addressing the
block DAG that, in combination with a suitable Sybil protection facilitates
the voting schemes.

###  2.1 The UTXO Ledger and Conflicts

Tracking of funds and change of ownership between addresses is facilitated by
employing the Unspent Transaction Output (UTXO) model, e.g., [1, 21, 22]. In
this model, transactions specify the outputs of previous transactions as
inputs and spend them by creating new outputs. In contrast to the account-
based model, transactions can be verified without knowing the global state of
the system but depend only on the status of the inputs. Moreover, it
identifies conflicts as every output can only be spent once.

As consistency is the main requirement of a ledger, nodes eventually have to
resolve this kind of double-spends. The Tangle 2.0 consensus protocol, [18],
decides between the conflicting spending relying on an identity-based Sybil
protection, Section 2.3, and a voting protocol introduced in more detail in
Sections 2.4 and 2.6.

###  2.2 The Tangle

One of the basic ideas of [23] was to abolish the role of the miners or
validators, as a leader-based approach not only leads to a performance
limitation but also makes fees necessary. Instead, a cooperative approach is
followed, in which each new block validates at least two other previous blocks
by referencing them. Each participant can thus add blocks simultaneously and
asynchronously. The blocks together with the references then form a DAG, the
so-called Tangle. The Tangle is both a record of the communication between
nodes as well as facilitates a data structure for the voting schemes
introduced in the next sections.

We call the referenced and approving blocks _parents_ and _children_ ,
respectively. The reference relationship is transitive in the sense that new
nodes not only refer (or vote) for their direct parents but also indirectly
for the entire ancestral line. We call all blocks, referenced directly or
indirectly, the _past cone_ of a given block. Similarly, all blocks that refer
to the block directly or indirectly are called its _future cone_ , see Figure
1. The first block of the Tangle has no parents and is called _genesis_.
Blocks that have not been yet approved are called _tips_. In [18] there exist
different reference types that infer different past cones of a block. However,
in this paper, we consider only the most fundamental reference type which
represents approval for the block itself and its entire past cone of the
Tangle.

Every block consists of several elements, of which the most relevant are:
parent references, the signature of the issuer (the node that introduced the
block into the Tangle), and a payload. In this paper, the payload is a
transaction.

Figure 1: The Tangle, the future, and the past cone of a block are highlighted
with green and yellow triangles respectively. The orange blocks are tips.

###  2.3 Sybil Protection

Each node has a score, called weight, which serves as a Sybil protection
mechanism. Weights can be calculated in different ways, depending on the
purpose. For example, it could be utilized in the context of (delegated)
Proof-of-Stake systems. In the context of this paper, we employ it as voting
power and access to the network’s resources (share of the network throughput).

The total weight value within the network is the sum of the weights of all
nodes. We note, that in a distributed network setting nodes can go offline and
online at any time. Also, nodes may not be forced to issue blocks and use all
of their bandwidth. However, in this work, we assume that the weights of the
nodes are constant and that all nodes use their total share of the network
throughput.

###  2.4 Approval Weight, Voting, and Confirmation

In this section, we define the concept of Approval Weight (AW). It is the core
element of the consensus protocol. AW allows for measuring the endorsement of
blocks and their corresponding transactions. The confirmation of a transaction
is calculated by summing up the cumulative weight of all blocks’ issuers in
the future cone of the block that contains the transaction. It is in principle
similar to the concept introduced in [23]. There, a weight of a block is
corresponding to the amount of work put into creating a block and all blocks
in its future cone. Instead, in this implementation block weight is equal to
the issuer’s weight and is counted at most once if a block is issued in the
future cone. A block becomes confirmed whenever its accumulated weight reaches
a certain threshold $\theta$.

The On Tangle Voting (OTV), [18], allows voting on two conflicting
transactions or double spends, $A$ and $B$. A given node might receive
transaction $A$ and express its support for it (by issuing a block in the
future cone of the block containing $A$) before receiving $B$. Once the node
also receives $B$ and its future cone, it compares each transaction’s AW and
votes for the transaction with the higher weights. In case the node changes
its opinion in favor of $B$, the node’s weight is revoked from the AW of
transaction $A$, since for any pair of conflicts a node’s weight is counted at
most once.

Once a transaction is confirmed, i.e., its AW reaching $\theta$, it will stay
confirmed even if its AW falls below $\theta$. Thus, the consensus protocol
must be designed, such that the event of any two nodes confirming different
transactions out of a set of mutually conflicting transactions occurs with
negligible probability, or otherwise safety as discussed in the next section,
is violated.

###  2.5 Liveness and Safety

Every consensus algorithm should ensure the following properties:

  * •

liveness: all non-faulty nodes eventually take a decision,

  * •

safety: all non-faulty nodes agree on the same values.

The satisfaction of the two properties depends on the underlying communication
model. The most well-known communication models are synchronous, asynchronous,
and partial synchronous, describing the network’s synchronicity level.

The asynchronous model best reflects scenarios where an adversary can delay
the transmission of blocks arbitrarily long. From the famous FLP impossibility
result, [24], we know that reaching a (deterministic) agreement in an
asynchronous setting is impossible. Therefore, there is a need for a so-called
symmetry-breaking mechanism that uses a (shared) source of randomness to
ensure liveness and safety.

It is crucial that the safety property always holds (at least with high
probability). It is also essential that the progress of the protocol should
happen eventually. The main goal of the performed simulations is to determine
if it is possible to halt the termination of the voting mechanism and if the
proposed symmetry or metastability breaking mechanism, described in the next
section, ensures both the safety and liveness of the protocol can be
guaranteed.

###  2.6 Synchronised Random Reality Selection

The concept of Synchronised Random Reality Selection (SRRS) was proposed in
[18] and inspired by [25]. Because the OTV is an asynchronous protocol, a
synchronization process on the communication level is lacking between nodes to
overcome the deterministic FLP impossibility result. This synchronization of
the nodes is done in the SRRS using a shared random number that is generated
periodically. We denote $D$ as the period (epoch) time. By the end of each
epoch, every node in the network receives the newly generated random number.
This “common coin” is used to _synchronize_ the opinions of each node with the
opinions of the other honest nodes. More details on the SRRS are described in
Section 4.5.

##  3 The Adversary Model

We distinguish between two types of nodes: honest and malicious. Honest nodes
follow the protocol, while malicious nodes are trying to actively disturb the
protocol by not following protocol. We assume that the malicious nodes are
controlled by an abstract entity that we call the attacker. We assume that the
attackers are computationally limited and cannot break the signature schemes
or the cryptographic hash functions involved.

In classic consensus protocols, the communication model already covers the
adversary behaviors, as delaying blocks is essentially the only way an
attacker can influence the system. This is no longer true for the Tangle 2.0
protocol and we focus in this paper on attacks on the voting layer. In these
kinds of attacks, the attacker is in possession of some proportion of voting
power, i.e. weight $q$, and uses this weight to manipulate the votes on the
Tangle. We are interested in the problem of metastability, which aims to
affect liveness and, in extreme cases, safety. The strategy of the attacker is
then to keep the honest nodes in an undecided state.

###  3.1 Bait-and-Switch Attack

We implement several types of adversary strategies from [18] in the simulator
[19]. However, we focus here on the Bait-and-Switch attack that seems to be
the most effective strategy to attack liveness in the Tangle 2.0 protocol.
Moreover, this attack is shown in theory to be effective even when the
attacker has no control over the communication layer.

In contrast to typical balancing attacks, the Bait-and-Switch attack relies
less on keeping the conflict weights symmetrical, but rather the attacker
makes the honest nodes chase the ever-changing heaviest (measured in AW)
transaction. The attack seems to be most effective in situations where the
adversary has the largest weight among all nodes.

The attack starts with the adversary issuing a pair of conflicting
transactions on which honest nodes start to vote. Then, before any of the two
options accumulate more weight than the adversary has, the adversary issues
another transaction conflicting with the previous ones, making it the heaviest
transaction (measured in AW). The honest nodes will adapt their opinion to the
newly issued conflict, but then the adversary issues another transaction
conflicting with the previous ones and supports it with his weight. Thus, the
new conflicting transaction becomes the heaviest in AW. This process can be
repeated indefinitely unless a certain transaction accumulates more approval
weight than the adversary has.

##  4 Simulation Components

To achieve efficient exploration of the Tangle 2.0 protocol, only the
necessary components are implemented in the simulator, and some of them are
simplified. In this section, we explain the simplifications of the simulator
and the reasons for them.

###  4.1 Conflicts and Colours

Figure 2: Tracking of the supporters for AW calculation.

We encode conflicting transactions with different colors. For instance, Figure
2 presents the Tangle with two conflicting transactions: the red and blue
colors are introduced in a block by nodes $A$ and $D$, respectively.

Considering the Tangle state until time $t_{1}$ separated by the dashed line,
we can count the supporters for each branch by summing up the weights of block
issuers in the future cone of the block that introduced each branch. Thus for
$t<t_{1}$, red is supported by nodes $A$ and $B$, and for blue by node $D$.
After some time, the support changes. Notice that node $B$ changed its opinion
and attaches to the blue part of the Tangle, such that its previous vote for
the red branch is canceled.

We want to note that two types of references are introduced in [18], i.e.,
block reference and transaction reference. Here we consider only the basic
type of reference, which is a block reference. Thus, it is not allowed to
reference blocks that belong to conflicting branches (i.e., they have
different colors).

###  4.2 Communication layer

The simulated environment reflects a situation in which network participants
are connected in a peer-to-peer network, where each node has $k$ neighbors.
Nodes can gossip, receive blocks, request for missing blocks, and state their
opinions whenever conflicts occur. In order to fully control the network
topology, we produce a peer-to-peer network using a Watts-Strogatz network
[26]. In order to mimic a real-world behavior, the simulator allows specifying
the network delay and packet loss for each node’s connection.

###  4.3 Agent-based node model

In the simulation, nodes act as different independent agents asynchronously.
This means that different nodes can have different perceptions of the Tangle
at any given moment of time. Thus, nodes have their own local Tangles for
calculating the approval weights and performing the Tangle 2.0 protocol.

We assume that the number of nodes does not change during the simulation
period, and all the honest nodes are actively participating in the consensus
mechanism. With this assumption, all nodes can be considered active nodes
(i.e., their weight is accounted for during the AW calculations).

###  4.4 Weight Distribution

As explained in Section 2.3 a scarce resource is assumed as a Sybil protection
mechanism. We also consider that the node’s weight is derived from or related
to the underlying source token, which is the case in IOTA. To model the weight
of the nodes in the network we use the Zipf empirical law, which is proven to
govern an asymptotic distribution of weights near its upper tail [27]. In [28]
it was shown that in the example of $100$ IOTA’s richest nodes, they follow
approximately the Zipf law with $s=0.9$. Moreover, the Zipf law has the
advantage, i.e., by changing the parameter $s$, to model the network behavior
for varying degrees of (de)centralization. For example, a homogeneous
situation is modeled with $s=0$, while for $s$ above $1$ a more centralized
weight distribution can be investigated. Note that, in the simulator, nodes’
weights are constant over time, and thus there is no concept of weight
delegation or changes in the weight distribution caused by transactions and
events happening in the network.

###  4.5 SRRS Implementation

If the conflict cannot be resolved until time $D\textsubscript{start}$, then
at the time of $D\textsubscript{start}$ and at the end of each epoch, every
node will calculate a hash based on the opinion of the node and the random
number $x$.

In our simulations, the random variable $x$ is uniformly distributed on the
interval [0.5, 0.66], where 0.66 is the value of the confirmation threshold
$\theta$. The hash is calculated as the SHA-256 of $y$, where $y$ = $o$ \+ $c$
* $x$, and $c$ is a predefined constant value. $c$ is set to be $1000$ in our
experiments. Every node compares the AW of the different conflicting
transactions with the random threshold $x$. If one of the conflicting
transactions has more AW than $x$ it will vote for this transaction.
Otherwise, it will vote in the next $D$ period for the transaction with the
minimal hash described above. This process keeps running periodically until
all honest nodes decide on the same transactions or the maximal simulation
time of $60$s is reached.

##  5 Simulation Setup

TABLE I: Default Experimental Settings Symbol | Description | Value
---|---|---
$N$ | Node count | 100
$s$ | Zipf parameter of weight distribution | 0.9
$\theta$ | Confirmation threshold | 66%
$n_{p}$ | Parents count | 8
BPS | Blocks per second (BPS) | 100
$l$ | Packet loss | 0
$\gamma$ | Watts-Strogatz rewiring probability | 100%
$k$ | Number of neighbors | 8
$q$ | Adversary weight | 5%
$d$ | Network delay | 100ms
$t\textsubscript{max}$ | Maximum simulation time | 60s

Table I lists the default experiment setup in our simulations. The node count
is the number of nodes in the network. Each node has a weight, which
influences its impact on the algorithm. The average block issuance rate of a
node is assumed to be proportional to the weight. In addition, we assume the
block issuance time interval of nodes follows a Poisson distribution [29]. The
default confirmation threshold is set to be $\theta=66\%$.

The parents’ count (or the number of references) is set to be $n_{p}=8$. These
parents are chosen randomly (with replacement) among all visible tips. The
throughput is measured as the total number of blocks per second (BPS) of all
nodes combined; its default value is BPS=$100s^{-1}$. The packet loss is set
to be $l=0$, i.e., no packets are lost. The minimum and maximum delays are the
upper and lower latency bounds of packets between each pair of peers in the
network, respectively. Both in the honest and adverse environments, the delay
from an honest node or an adversary is set to be $d=100ms$, which is the
packet delay transmitted from one node to its neighbors. The default Watts-
Strogatz rewiring probability [26] is set to be $\gamma=1$. In addition, the
neighbor count is the number of neighbors of a node in the Watts-Strogatz
topology, whose default value is $8$. $t\textsubscript{max}$ denotes the
maximum simulation time, and the default value is set to be
$t\textsubscript{max}=60s$. The simulation will be terminated automatically
and regarded as a security failure if the conflicts cannot be resolved before
the predefined $t\textsubscript{max}$.

The adversary weight is set to be $q$, which is the percentage of the total
weight controlled by the adversary node. Figure 3 shows weight distribution
examples with $q=33\%$, $N=11$ for several values of $s$. In the figure, the
index of the adversary node is $11$, and nodes with indices $1$ to $10$ are
honest nodes. As $33\%$ of the total weight is occupied by the adversary, the
remaining $67\%$ of the total weight is distributed among the $10$ honest
nodes.

Figure 3: Node weight distribution example with $q=33\%$, $N=11$. The node
index of the adversary is 11.

Based on the different settings of the above parameters, the robustness and
efficiency of the Tangle 2.0 can be explored and simulated thoroughly.

##  6 Simulation Results

To demonstrate the robustness of the Tangle 2.0, we first explore the
consensus time distributions of the OTV protocol under adversary environments.
The consensus time is defined as the time period measured from the time that a
double spend happens to the time that all the honest nodes decided on the same
opinion, i.e., reach consensus. By measuring the consensus time, the safety
and liveness of the protocol can be analyzed. Next, we analyze the
confirmation time in expected scenarios (i.e., $N=100$ and $s=0.9$). The
confirmation time is measured in the local Tangles of all honest nodes and is
defined as the time period from the block issuance time to the time when its
cumulative AW $>\theta$. By measuring the confirmation time distributions, the
liveness of the protocol is analyzed. In the end, we show experimental results
that non-conflicting blocks are immune to attacks from adversaries.

(a) $s=0$

(b) $s=0.9$

(c) $s=2$

Figure 4: OTV consensus time distributions under Bait-and-Switch attack,
without SRRS ($N=100$).

###  6.1 OTV Protocol without SRRS

Figure 4 shows the experimental results of the OTV consensus time
distributions under the Bait-and-Switch attack and without SRRS. Different
adversary weights, ranging from 5% to 33%, and Zipf distributions,
$s\in\\{0,0.9,2\\}$, are simulated. Each experimental setting is simulated
$100$ times. For each simulation run, the consensus time of the double spend
is collected. As Fig. 4(a) shows, when $q\leq 20\%$, all of the $100$
simulation runs can successfully resist the Bait-and-Switch attack, where all
the conflicts can be resolved within $30$s. When the adversary weight $q$ is
increased to $\geq 25\%$, liveness failures occur, i.e., conflicts are failed
to be resolved within $60$s.

With increased $s$, honest nodes are more likely to follow the opinions of the
honest nodes with heavy weight, which makes the conflicts easier to be
resolved. We can observe this in Fig. 4(b), where the Zipf parameter is
increased to $s=0.9$. With the higher value of $s$ no liveness failures occur
for $q\leq 25\%$. Also, most of the runs can resist the Bait-and-Switch attack
for $q=30\%$.

Figure 4(c) shows the results of $s=2$ under the same attack. For all the
cases shown, even $q$=33%, no liveness failures occur. This provides strong
evidence of the robustness of the OTV protocol, in a more centralized setting.

###  6.2 OTV Protocol with SRRS

In this section, we add the SRRS on top of the OTV protocol, and further
investigate the robustness of the Tangle 2.0.

Figure 5 shows the experimental results of the consensus time distributions
under the Bait-and-Switch attack, and with SRRS. The parameter variations of
the adversary weights and Zipf distributions are the same as those in Section
6.1. As shown in the Fig. 5, no security failures occur in all the
simulations. For all the cases, conflicts are able to be resolved within
$20$s. Furthermore, for $s=2$, as shown in Fig. 5(c), all the conflicts are
able to be resolved within $7$s. Based on the simulation results, the Tangle
2.0 is able to resist the Bait-and-Switch attacks, even in extreme cases,
where all the honest nodes have equal weight, and the adversary node owns the
upper limit of the theoretical weight.

(a) $s=0$

(b) $s=0.9$

(c) $s=2$

Figure 5: OTV consensus time distributions under Bait-and-Switch attack, with
SRRS ($N=100$).

###  6.3 Confirmation Time Analysis

In this section, we analyze the confirmation times of honest transactions in
an honest and adverse environment.

####  6.3.1 Healthy Environment

To address the scalability of the protocol we investigate the confirmation
time distribution in an honest environment, i.e. $q=0$, for different node
counts. As Fig. 6 shows, the confirmation time increases monotonically with
increasing node counts. The reason is that when the node count increases, the
weights of nodes will be distributed across more nodes, and thus more time is
required for a block to be approved by the necessary amount of weights.

To analyze the performance with the degree of decentralization of the network,
Fig. 7 shows the confirmation time distributions for several Zipf parameters
$s$ with $N=100$. When the parameter $s$ decreases, the weights of nodes are
distributed more evenly, and a given block needs to be approved by more nodes,
which consequently leads to longer confirmation times. As Fig. 7 shows, for an
extreme case where the Zipf parameter equals $0$, all the blocks can still be
confirmed within $2$s.

Figure 8 shows the confirmation time distributions under different uniform
random network delays. The confirmation time becomes longer monotonically with
a longer network delay. Note that the delay for a modern network is around
$100$ms, where $\leq{2}$s confirmation time can be achieved in the protocol.

In a real network environment, a packet might get lost due to network
congestion and/or software/hardware issues. This will introduce the packet
failing to transmit from one peer to another. In the network layer of the IOTA
protocol, a solidification process is implemented. In the process, each node
maintains a local tangle for computing the approval weights of transactions by
tangle traversing. When a missing transaction is identified in the traversing
(i.e., the parent(s) of a transaction is missing), the node will request the
missing transaction from other peers every $5$s, until the transaction is
received and contained in its local tangle. Figure 9 shows confirmation time
distributions with different packet losses. Thanks to the solidification
process, the confirmation time can still remain $\leq{2}$s when the packet
loss is $\leq{25\%}$ for $s=0.9$ and $N=100$.

Figure 6: Confirmation time distributions with different $N$’s ($s=0.9$).
Figure 7: Confirmation time distributions for different Zipf parameters $s$
($N=100$). Figure 8: Confirmation time distributions with different uniform
random network delays ($N=100$ and $s=0.9$). Figure 9: Confirmation time
distributions with different packet losses ($N=100$ and $s=0.9$).

####  6.3.2 Adverse Environment

Figure 10 shows the confirmation time distributions of non-conflicting
transactions under the Bait-and-Switch attack, where the Zipf parameter and
the node count are $s=0.9$ and $N=100$, respectively. As shown in the figure,
most of the non-conflicting blocks can be confirmed within $1$ to $2$s, which
are not affected by the presence of conflicts. Note that there are a few
outliers. These can be explained by non-conflicting transactions (i.e., the
outliers) being orphaned because the voting powers of the honest nodes are
split to vote for the different conflicting transactions before the conflict
resolution. In the case of an orphanage, the issuers of the affected block
reattaches the transaction in a new block after $5$s. This is possible,
because the issuance of different blocks with the same transaction is not
considered a double spend but rather, on the UTXO ledger level, is considered
as the same transaction. In the IOTA 2.0 protocol, this liveness problem for
honest transactions is resolved more elegantly by the introduction of the
second type of reference, i.e., a transaction reference [18]. In addition, due
to the fixed confirmation threshold, which is $\theta=66\%$, as the adversary
occupies more weight, non-conflicting transactions might wait for a longer
time to accumulate their AW from different honest nodes.

Figure 10: Confirmation time distributions of non-conflicting transactions
with $s=0.9$ and $N=100$.

##  7 Conclusion

In this paper, we gave a first performance analysis of the Tangle 2.0
protocol. The confirmation time distributions based on different environments
and under attacks are analyzed. The experimental results show that the Tangle
2.0 can resist the Bait-and-Switch attack and achieve a short consensus time,
even in extremely adverse environments. Moreover, in common scenarios, the
protocol can achieve confirmation time in the order of seconds, and
confirmation times of most non-conflicting transactions are not affected
noticeably by the presence of conflicts.

## Acknowledgments

The authors would like to thank the developer team of the GoShimmer software,
to support this study with the prototype implementation of the Tangle 2.0
protocol.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system.” 2008.
  * [2] R. Paulavičius, S. Grigaitis, and E. Filatovas, “A systematic review and empirical analysis of blockchain simulators,” _IEEE Access_ , vol. 9, pp. 38 010–38 028, 2021.
  * [3] C. Berger and H. Reiser, “Scaling byzantine consensus: A broad analysis,” Dec. 2018, pp. 13–18.
  * [4] Y. Xiao, N. Zhang, W. Lou, and Y. T. Hou, “A survey of distributed consensus protocols for blockchain networks,” _IEEE Communications Surveys Tutorials_ , vol. 22, no. 2, pp. 1432–1465, 2020.
  * [5] A. Hari, M. Kodialam, and T. V. Lakshman, “Accel: Accelerating the bitcoin blockchain for high-throughput, low-latency applications,” in _IEEE INFOCOM 2019 - IEEE Conference on Computer Communications_ , 2019, pp. 2368–2376.
  * [6] Q. Zhou, H. Huang, Z. Zheng, and J. Bian, “Solutions to scalability of blockchain: A survey,” _IEEE Access_ , vol. 8, pp. 16 440–16 455, 2020\.
  * [7] Y. Sompolinsky, Y. Lewenberg, and A. Zohar, “Spectre: A fast and scalable cryptocurrency protocol,” Cryptology ePrint Archive, Report 2016/1159, 2016. [Online]. Available: https://ia.cr/2016/1159
  * [8] A. Churyumov, “Byteball: A decentralized system for storage and transfer of value,” 2016. [Online]. Available: https://byteball.org/Byteball.pdf
  * [9] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,” in _Proceedings of the 26th symposium on operating systems principles_ , 2017, pp. 51–68.
  * [10] Y. Sompolinsky, S. Wyborski, and A. Zohar, “Phantom and ghostdag: A scalable generalization of nakamoto consensus,” Cryptology ePrint Archive, Report 2018/104, 2018. [Online]. Available: https://ia.cr/2018/104
  * [11] T. Rocket, M. Yin, K. Sekniqi, R. van Renesse, and E. G. Sirer, “Scalable and probabilistic leaderless BFT consensus through metastability,” 2019.
  * [12] V. Bagaria, S. Kannan, D. Tse, G. Fanti, and P. Viswanath, “Prism: Deconstructing the blockchain to approach physical limits,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , 2019, pp. 585–602.
  * [13] A. Gągol, D. Leśniak, D. Straszak, and M. Świętek, “Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes,” in _Proceedings of the 1st ACM Conference on Advances in Financial Technologies_ , 2019, pp. 214–228.
  * [14] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and Tusk: A DAG-Based Mempool and Efficient BFT Consensus,” in _Proceedings of the Seventeenth European Conference on Computer Systems_ , ser. EuroSys ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 34–50. [Online]. Available: https://doi.org/10.1145/3492321.3519594
  * [15] S. Popov, H. Moog, D. Camargo, A. Capossele, V. Dimitrov, A. Gal, A. Greve, B. Kusmierz, S. Mueller, A. Penzkofer, O. Saa, W. Sanders, L. Vigneri, W. Welz, and V. Attias, “The Coordicide,” 2020.
  * [16] H. Pervez, M. Muneeb, M. U. Irfan, and I. U. Haq, “A comparative analysis of dag-based blockchain architectures,” in _2018 12th International Conference on Open Source Systems and Technologies (ICOSST)_ , 2018, pp. 27–34.
  * [17] M. Dotan, Y.-A. Pignolet, S. Schmid, S. Tochner, and A. Zohar, “Sok: Cryptocurrency networking context, state-of-the-art, challenges,” in _Proceedings of the 15th International Conference on Availability, Reliability and Security_ , ser. ARES ’20. New York, NY, USA: Association for Computing Machinery, 2020.
  * [18] S. Müller, A. Penzkofer, N. Polyanskii, J. Theis, W. Sanders, and H. Moog, “Tangle 2.0 Leaderless Nakamoto Consensus on the Heaviest DAG,” 2022. [Online]. Available: https://arxiv.org/abs/2205.02177
  * [19] IOTA Foundation. (2021) Tangle 2.0 simulator. [Online]. Available: https://github.com/iotaledger/multiverse-simulation
  * [20] M. Zander, T. Waite, and D. Harz, “Dagsim: Simulation of dag-based distributed ledger protocols,” _ACM SIGMETRICS Performance Evaluation Review_ , vol. 46, pp. 118–121, Jan. 2019.
  * [21] M. M. T. Chakravarty, J. Chapman, K. MacKenzie, O. Melkonian, M. Peyton Jones, and P. Wadler, “The Extended UTXO Model,” in _Financial Cryptography and Data Security_ , M. Bernhard, A. Bracciali, L. J. Camp, S. Matsuo, A. Maurushat, P. B. Rønne, and M. Sala, Eds. Cham: Springer International Publishing, 2020, pp. 525–539.
  * [22] S. Müller, A. Penzkofer, N. Polyanskii, J. Theis, W. Sanders, and H. Moog, “Reality-based UTXO Ledger,” 2022. [Online]. Available: https://arxiv.org/abs/2205.01345
  * [23] S. Y. Popov, “The tangle,” 2015.
  * [24] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” _Journal of the ACM (JACM)_ , vol. 32, no. 2, pp. 374–382, 1985.
  * [25] S. Popov and W. J. Buchanan, “FPC-BI: Fast Probabilistic Consensus within Byzantine Infrastructures,” _Journal of Parallel and Distributed Computing_ , vol. 147, pp. 77–86, 2021.
  * [26] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” _nature_ , vol. 393, no. 6684, pp. 440–442, 1998\.
  * [27] D. M. W. Powers, “Applications and explanations of Zipf’s law,” in _New Methods in Language Processing and Computational Natural Language Learning_ , 1998. [Online]. Available: https://aclanthology.org/W98-1218
  * [28] S. Müller, A. Penzkofer, B. Kuśmierz, D. Camargo, and W. J. Buchanan, “Fast probabilistic consensus with weighted votes,” in _Proceedings of the Future Technologies Conference (FTC) 2020, Volume 2_ , 2021, pp. 360–378.
  * [29] A. Penzkofer, O. Saa, and D. Dziubałtowska, “Impact of delay classes on the data structure in IOTA,” in _DPM/CBT@ESORICS_ , 2021.