# Gradient Boosted Binary Histogram Ensemble
for Large-scale Regression

Hanyuan Hang<EMAIL_ADDRESS>
Department of Applied Mathematics, University of Twente
7522 NB Enschede, The Netherlands
Tao Huang<EMAIL_ADDRESS>
Institute of Statistics and Big Data, Renmin University of China
100872 Beijing, China
Yuchao Cai<EMAIL_ADDRESS>
Hanfang Yang<EMAIL_ADDRESS>
School of Statistics, Renmin University of China
100872 Beijing, China
Zhouchen Lin<EMAIL_ADDRESS>
Key Lab. of Machine Perception (MOE), School of EECS, Peking University
100871 Beijing, China

###### Abstract

In this paper, we propose a gradient boosting algorithm for large-scale
regression problems called Gradient Boosted Binary Histogram Ensemble (GBBHE)
based on binary histogram partition and ensemble learning. From the
theoretical perspective, by assuming the Hölder continuity of the target
function, we establish the statistical convergence rate of GBBHE in the space
$C^{0,\alpha}$ and $C^{1,0}$, where a lower bound of the convergence rate for
the base learner demonstrates the advantage of boosting. Moreover, in the
space $C^{1,0}$, we prove that the number of iterations to achieve the fast
convergence rate can be reduced by using ensemble regressor as the base
learner, which improves the computational efficiency. In the experiments,
compared with other state-of-the-art algorithms such as gradient boosted
regression tree (GBRT), Breiman’s forest, and kernel-based methods, our GBBHE
algorithm shows promising performance with less running time on large-scale
datasets.

Keywords: Large-scale regression, binary histogram partition, random rotation,
gradient boosting, ensemble learning, regularized empirical risk minimization,
learning theory

##  1 Introduction

Over the past two decades, boosting has become one of the most successful
algorithms in the machine learning community (Bühlmann and Yu, 2003). After
the idea of iterative utilization of weak learners from a certain function
space to generate a strong one, which is called boosting, first came out in
Schapire (1990); Freund (1995), it gains a lot of attention, and a wealth of
literature has applied it to a large number of datasets. During this period,
many boosting algorithms with impressive performance have been proposed. The
first boosting algorithm dates back to the Adaboost for classification by
Schapire and Freund (1995); Freund and Schapire (1997). Another important
boosting algorithm for regression called Gradient Boosted Regression Tree
(GBRT) was proposed by Friedman (2001). GBRT takes advantage of tree-based
learners to capture complex data structures.

In addition to the great success of these boosting algorithms, a lot of
attempts have been made to establish their theoretical foundations. For
example, from the perspective of statistical analysis, Bühlmann and Yu (2003)
derived an exponential bias-variance trade-off for linear regression to
illustrate the almost resistance to overfitting for $L_{2}$-boosting in a
fixed design setting. Moreover, Park et al. (2009) and Lin et al. (2019)
established the theoretical analysis of boosting methods using Nadaraya-Watson
kernel estimates and kernel ridge regression estimates as base learners,
respectively. However, these methods are of little value in practice since
they fail to capture the complex data dependencies in applications. In the
prior work of this paper (Cai et al., 2020), we proposed a boosting algorithm
for regression problems called boosted histogram transform for regression
(BHTR) with sound theoretical guarantees and satisfactory empirical
performance. However, since it utilizes the ordinary histogram transforms as
base learners, the number of partition cells grows exponentially with the
dimension, and thus is hard to adapt to high-dimensional data.

Moreover, despite the success in achieving desirable performance, boosting
procedures can encounter heavy computational costs in the computations of the
features and the selection of the weak learner, both of which depend on the
number of features and the number of training examples. Therefore, boosting
algorithms cannot be directly applied to large-scale high-dimensional data.
Efforts have been made to further enhance the efficiency of boosting
algorithms in large-scale scenarios. For example, Dubout and Fleuret (2014)
utilized an adaptive sampling approach to sample features at every boosting
step, so as to reduce computational cost. Other works focus on enhancing the
efficiency of boosting through engineering optimizations: Chen and Guestrin
(2016) came up with the eXtreme Gradient Boosting (XGBoost), which achieves
excellent experimental performance. Ke et al. (2017) speeds up the training
process of conventional GBRT by up to over 20 times. More recently, Biau et
al. (2019) incorporates the Nesterov’s accelerated gradient descent technique
(Nesterov, 1983) to accelerate GBRT. Unfortunately, none of the above-
mentioned boosting works for large-scale regression presents a satisfactory
statistical theoretical guarantee.

Under such background, this paper aims to establish a new boosting algorithm
for large-scale and high-dimensional regression, which is not only with
satisfactory performance but also with solid theoretical foundations. To be
specific, motivated by the random rotation ensemble algorithms (López-Rubio,
2013; Blaser and Fryzlewicz, 2016) and binary histogram partition (Biau,
2012), we propose gradient boosted binary histogram ensemble (GBBHE) for
regression, where we for the first time combine two ensemble methods, i.e.
gradient boosting and base learner aggregation, to enhance effectiveness and
computational efficiency. First of all, we apply a random rotation to the
input space and apply the binary histogram partition, with the help of which
we obtain piecewise constant base learners. Then at each iteration, we
generate several independent base learners and ensemble them by taking the
arithmetic average, where we call the ensemble estimator rotated binary
histogram ensembles. The iterative process to fit residuals is started with
the help of a sequence of rotated binary histogram ensembles by a natural
adaption of gradient descent boosting algorithm.

It is worth mentioning that GBBHE enjoys four advantages. Firstly, our
obtained regression function can be globally smooth thanks to the diversity of
different base learners resulting from the randomness of both random rotations
and binary histogram partitions. Secondly, under binary histogram partitions,
all cells are split to the same depth, which ensures the fast convergence of
our algorithm. Thirdly, compared with ordinary histograms, our binary
histogram partition split at the midpoint of only one selected side at each
iteration, so the cells will not be too small and thus it applies better to
high dimensional data. Finally, GBBHE applies well to the large-scale
scenarios since the more accurate base ensembles, enjoying high computational
efficiency with the help of parallel computing, can effectively reduce the
number of iterations in boosting.

As follows are the contributions of this paper.

(i) Aiming at solving the large-scale regression problem, we propose a novel
boosting algorithm named Gradient Boosted Binary Histogram ensemble (GBBHE),
where the binary histogram regressors are used as base learners and the
ensemble method performed on base learners helps improve its computational
efficiency by reducing the number of boosting iterations. We claim that the
binary histogram partition is adapted well to high-dimensional data, compared
with ordinary histogram partitions.

(ii) From the theoretical perspective, we first of all investigate a special
case of GBBHE, that is, GBBHE without ensemble (abbreviated as GBBH), where
the number of base learners in an ensemble is set to be $1$. Under the
assumption that the target function resides in $C^{0,\alpha}$ and $C^{1,0}$,
respectively, by decomposing the error term into approximation error and
sample error, we establish the fast convergence rates of GBBH in the space
$C^{0,\alpha}$. Moreover, for the subspace $C^{1,0}$ consisting of smoother
functions, we are able to show that GBBH can attain the asymptotical
convergence rate $O(n^{-1/(2+d\log 2)})$ whereas the lower bound of the
convergence rates for its base learner binary histogram is merely of the order
$O(n^{\log(1-0.75/d)/(\log 2-\log(1-0.75/d))})$. As a result, we succeed to
prove that the boosted regressor GBBH can achieve faster convergence rates
than the base learner in the subspace $C^{1,0}$ when $d\geq 6$, which confirms
the benefits of the proposed boosting procedure.

(iii) We further prove that GBBHE has the same convergence rates as that of
GBBH in both $C^{0,\alpha}$ and $C^{1,0}$. However, compared with the results
for GBBH, where the number of iterations $T_{n}$ is required to be of the
order $n^{1/(8+4d\log 2)}$ to achieve the convergence rate, for GBBHE, we only
require that $T_{n}K_{n}$ is of the same order $n^{1/(8+4d\log 2)}$, where $K$
denotes the number of ensembles at each iteration. In other words, we can
reduce the number of iterations $T$ by enlarging the number of base learners
for ensemble $K$. It is well known that boosting algorithms with a large
number of iterations can be quite time-consuming, since acceleration
techniques such as parallel computing are not directly available. Therefore,
by combining ensemble methods, which enjoy high computational efficiency with
the help of parallel computing, we successfully save the running time of GBBHE
by reducing the number of iterations $T$.

(iv) In the experiments, several numerical experiments are designed to study
the parameters including the depth of the binary histogram transform $p$, the
number of iterations of boosting $T$, the number of binary histograms in each
iteration $K$, and learning rate $\rho$. And we empirically verify the
theoretical results that ensemble methods can reduce the number of iterations
$T$ to achieve the fast convergence rate. Moreover, we compare our GBBHE with
state-of-the-art large-scale regressors including GBRT, Breiman’s forest, and
LiquidSVM on both moderate-sized and large-scale real datasets. It turns out
that our GBBHE shows comparable or even better performance than the compared
methods, while enjoys higher computational efficiency with less running time
required.

This paper is organized as follows. In Section 2, we introduce the methodology
of this paper, where we construct our main algorithm GBBHE. Then in Section 3,
we present the theoretical results built for GBBHE and its special case GBBH
in Hölder space consisting of $(k,\alpha)$-Hölder continuous functions. We
conduct numerical experiments including parameter analysis and real data
comparisons with other state-of-the-art large-scale regression algorithms in
Section 4. Finally, we present our comments and discussions in Section 5. We
put the error analysis for Section 3 in Section 6 and the related proofs in
Section 7.

##  2 Methodology

In this section, we build the main algorithm Gradient Boosted Binary Histogram
Ensemble (GBBHE) for regression. We first introduce some notations in Section
2.1 and show the basics of least square regression in Section 2.2. Then in
Section 2.3, we introduce the (rotated) binary histogram, which is an
essential part in establishing the main algorithms. In Section 2.4, we show a
special case of GBBHE where the number of ensembles equals to $1$, called
GBBH. Finally, in Section 2.5, we present the main algorithm of GBBHE.

###  2.1 Notations

Regression is to predict the value of an unobserved output variable $Y$ based
on the observed input variable $X$, based on a dataset
$D:=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ consisting of i.i.d.
observations drawn from an unknown probability measure $\mathrm{P}$ on
$\mathcal{X}\times\mathcal{Y}$. Throughout this paper, we assume that
$\mathcal{X}\subset\mathbb{R}^{d}$ and $\mathcal{Y}\subset\mathbb{R}$ are
compact and non-empty.

For any fixed $r>0$, we denote $B_{r}$ as the centered hyper-cube of
$\mathbb{R}^{d}$ with size $2r$, that is,
$B_{r}:=[-r,r]^{d}:=\\{x=(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{i}\in[-r,r],i=1,\ldots,d\\}$.
Recall that for $1\leq p<\infty$, the $L_{p}$-norm of $x=(x_{1},\ldots,x_{d})$
is defined by $\|x\|_{p}:=(|x_{1}|^{p}+\cdots+|x_{d}|^{p})^{1/p}$, and the
$L_{\infty}$-norm is defined by $\|x\|_{\infty}:=\max_{i=1,\ldots,d}|x_{i}|$.

In the sequel, the notation $a_{n}\asymp b_{n}$ means that there exists some
positive constant $c\in(0,1)$, such that $a_{n}\geq cb_{n}$ and $a_{n}\leq
c^{-1}b_{n}$, for all $n\in\mathbb{N}$. Similarly, the notation $a_{n}\lesssim
b_{n}$ denotes that there exists some positive constant $c\in(0,1)$, such that
$a_{n}\leq cb_{n}$ and $a_{n}\gtrsim b_{n}$ denotes that there exists some
positive constant $c\in(0,1)$, such that $a_{n}\geq c^{-1}b_{n}$. For any
$x\in\mathbb{R}$, let $\lfloor x\rfloor$ denote the largest integer less than
or equal to $x$. Moreover, the following multi-index notations are used
frequently. For any vector $x=(x_{i})^{d}_{i=1}\in\mathbb{R}^{d}$, we write
$\lfloor x\rfloor:=(\lfloor x_{i}\rfloor)_{i=1}^{d}$,
$x^{-1}:=(x_{i}^{-1})_{i=1}^{d}$, $\log(x):=(\log x_{i})^{d}_{i=1}$,
$\overline{x}=\max_{i=1,\ldots,d}x_{i}$, and
$\underline{x}=\min_{i=1,\ldots,d}x_{i}$.

###  2.2 Least Square Regression

It is legitimate to consider the least square loss
$L:\mathcal{X}\times\mathcal{Y}\to[0,\infty)$ defined by
$L(x,y,f(x)):=(y-f(x))^{2}$ for our target of regression. Then, for a
measurable decision function $f:\mathcal{X}\to\mathcal{Y}$, the risk is
defined by
$\mathcal{R}_{L,\mathrm{P}}(f):=\int_{\mathcal{X}\times\mathcal{Y}}L(x,y,f(x))\,d\mathrm{P}(x,y)$
and the empirical risk is defined by
$\mathcal{R}_{L,\mathrm{D}}(f):=\frac{1}{n}\sum^{n}_{i=1}L(x_{i},y_{i},f(x_{i}))$.
The Bayes risk, which is the smallest possible risk with respect to
$\mathrm{P}$ and $L$, is given by
$\mathcal{R}_{L,\mathrm{P}}^{*}:=\inf\\{\mathcal{R}_{L,\mathrm{P}}(f)|f:\mathcal{X}\to\mathcal{Y}\text{
measurable}\\}$.

In what follows, it is sufficient to consider predictors with values in
$[-M,M]$. To this end, we introduce the concept of clipping for the decision
function, see also Definition 2.22 in Steinwart and Christmann (2008). Let
$\wideparen{t}$ be the clipped value of $t\in\mathbb{R}$ at $\pm M$ defined by
$-M$ if $t<-M$, $t$ if $t\in[-M,M]$, and $M$ if $t>M$. Then, a loss is called
clippable at $M>0$ if, for all $(y,t)\in\mathcal{Y}\times\mathbb{R}$, there
holds $L(x,y,\wideparen{t})\leq L(x,y,t)$. According to Example 2.26 in
Steinwart and Christmann (2008), the least square loss $L$ is clippable at $M$
with the risk reduced after clipping, i.e.,
$\mathcal{R}_{L,\mathrm{P}}(\wideparen{f})\leq\mathcal{R}_{L,\mathrm{P}}(f)$.
Therefore, in the following, we only consider the clipped version
$\wideparen{f}_{\mathrm{D}}$ of the decision function as well as the risk
$\mathcal{R}_{L,\mathrm{P}}(\wideparen{f}_{\mathrm{D}})$.

###  2.3 Binary Histogram for Regression

In the following, we use the tilde notation to distinguish between the
transformed space and the original input space.

####  2.3.1 Random Rotation

To give a clear description of one possible construction procedure of rotated
random histograms, we start with the random rotation matrix $R$, which is a
real-valued $d\times d$ orthogonal square matrix with unit determinant, that
is

$\displaystyle R^{\top}=R^{-1}\quad\text{ and }\quad\det(R)=1.$ (1)

Then we define the rotation transformation $H:\mathcal{X}\to\mathcal{X}$ by

$\displaystyle H(x):=R\cdot x.$ (2)

In the following we will assume that each individual histogram is constructed
in the transformed space $\tilde{\mathcal{X}}:=H(\mathcal{X})$.

Here we describe a practical method for the construction of the random
rotation transformations we are confined to in this study. Starting with a
$d\times d$ square matrix $M$, consisting of $d^{2}$ independent univariate
standard normal random variates, a Householder $QR$ decomposition is applied
to obtain a factorization of the form $M=R\cdot W$, with orthogonal matrix $R$
and upper triangular matrix $W$ with positive diagonal elements. The resulting
matrix $R$ is orthogonal by construction and can be shown to be uniformly
distributed. Unfortunately, if $R$ does not feature a positive determinant
then it is not a proper rotation matrix according to definition (1). In this
case, we can change the sign of the first column of $R$ to construct a new
rotation matrix $R^{+}$ that satisfies the condition (1).

####  2.3.2 Binary Histogram Partition

It is well known that the classical histogram partition is an effective
algorithm by grouping samples into the bins with the same shape. However,
ordinary histogram partition is plagued by the curse of dimensionality. That
is, the number of bins grows exponentially with the dimension $d$, in which
case many bins will contain few or even no samples, leading to unacceptable
and unnecessary computational costs. Therefore, we propose the binary
partitioning technique to build the high-dimensional histogram, namely binary
histogram.

To be specific, Let
$\tilde{A}_{0}=\\{A_{0}^{1}:=[-r,r]^{d}\\}\subset\tilde{\mathcal{X}}$ be the
rectangular cell in the transformed space $\tilde{\mathcal{X}}$ and $p$ be a
deterministic parameter, fixed beforehand by the user, and possibly depending
on $n$. In the first step, we choose one of the coordinates
$X=(X_{1},\ldots,X_{d})$ with the $j$-th feature having a probability $1/d$ of
being selected, and then split $[-r,r]^{d}$ into two rectangular cells along
the midpoint of the chosen side. In other words, there exist $1\leq\ell\leq d$
such that $[-r,r]^{d}=\tilde{A}_{1}^{1}\cup\tilde{A}_{1}^{2}$, where
$\tilde{A}_{1}^{1}=\\{(x,y)\in[-r,r]^{d}:x_{\ell}\leq 0\\}$ and
$\tilde{A}_{1}^{2}=[-r,r]^{d}\setminus A_{1}^{1}$. In this way, we get a
partition with two rectangular cells. Moreover, we denotes
$\tilde{A}_{1}:=\\{\tilde{A}_{1}^{1},\tilde{A}_{1}^{2}\\}$ as the collection
of partitions with two rectangular cells. Note that the total number of
possible partitions after the first step is equal to the dimension $d$.
Suppose after $i-1$ steps of the recursion, $1\leq i\leq p$ we have obtained a
partition $\tilde{A}_{i-1}$ of $[-r,r]^{d}$ with $2^{i-1}$ rectangular cells.
In the $p$-th step, further partitioning of the region is defined as follows:

  * (i)

For each rectangular cell $\tilde{A}_{i-1}^{j}$, $1\leq j\leq 2^{i-1}$, a
coordinate of $X=(X_{1},\ldots,X_{d})$, namely $Z_{i,j}$ is selected, with the
$\ell$-th feature having a probability $1/d$ to be chosen, that is,

$\displaystyle\mathrm{P}(Z_{i,j}=\ell)=1/d,\qquad\text{ for }1\leq\ell\leq d.$
(3)

  * (ii)

For each rectangular cell $\tilde{A}_{i-1}^{j}$, $1\leq j\leq 2^{i-1}$, once
the coordinate is selected, the split is at the midpoint of the chosen side.
As a result, each rectangular cell $\tilde{A}_{i-1}^{j}$ is divided into two
new ones, namely $\tilde{A}_{i}^{2j-1}$ and $\tilde{A}_{i}^{2j}$. We denote
the set of all these cells $\\{\tilde{A}_{i}^{j},\,1\leq j\leq 2^{i}\\}$ by
$\tilde{A}_{i}$.

(a) Rotated binary histogram induced by $H_{1}$.

(b) Rotated binary histogram induced by $H_{2}$

Figure 1: Illustrations of rotated binary histogram partition with $p=2$.

Such a partition obtained by $p$ recursive steps is called a binary histogram
partition of $[-r,r]^{d}$ with depth $p$ in the transformed space, and we say

$\displaystyle A_{p}:=\\{A_{p}^{j}:=H^{-1}(\tilde{A}_{p}^{j}),\,1\leq j\leq
2^{p}\\}\cup\\{A_{p}^{0}:=\mathcal{X}\setminus H^{-1}([-r,r]^{d})\\}$ (4)

an rotated binary histogram with depth $p$ in the input space $\mathcal{X}$,
where $H^{-1}(A):=\\{x\in\mathcal{X}:H(x)\in A\\}$ for the set
$A\subset\tilde{\mathcal{X}}$. The complete process is presented in Algorithm
1 and an illustration is shown in Figure 1.

Input: Depth of the binary histogram $p$;

The random rotation transformation $H(x)=R\cdot x$;

$\tilde{A}_{0}=\\{\tilde{A}_{0}^{1}:=[-r,r]^{d}\\}$ in the transformed space
$\tilde{\mathcal{X}}=H(\mathcal{X})$.

for $i=1$ to $p$ do

for $j=1$ to $2^{i-1}$ do

For rectangular cell $\tilde{A}_{i-1}^{j}$, randomly choose one dimension
coordinate $Z_{i,j}$ whose probability distribution is given by (3);

Divide the cell $\tilde{A}_{i-1}^{j}$ into two subregions, that is,
$\tilde{A}_{i-1}^{j}=\tilde{A}_{i}^{2j-1}\cup\tilde{A}_{i}^{2j}$, along the
midpoint of the dimension $Z_{i,j}$;

end for

Get $\tilde{A}_{i}=\\{\tilde{A}_{i}^{j},\,1\leq j\leq 2^{i}\\}$.

end for

Output: Rotated binary histogram
$A_{p}=\\{A_{p}^{j}=H^{-1}(\tilde{A}_{p}^{j}),\,1\leq j\leq 2^{p}\\}$, where
$H^{-1}(A):=\\{x\in\mathcal{X}:H(x)\in A\\}$ for the set
$A\subset\tilde{\mathcal{X}}$.

Algorithm 1 Binary Histogram with Rotation

For any $x\in H^{-1}(B_{r})$, the histogram bin containing $x\in\mathcal{X}$
in the input space is

$\displaystyle A_{p}(x):=\\{x^{\prime}\ |\exists 1\leq i\leq 2^{p}\text{ such
that }H(x)\in\tilde{A}_{p}^{i},\,H(x^{\prime})\in\tilde{A}_{p}^{i}\\}$ (5)

and we further denote all the bins as $\\{A_{p}(x):x\in\mathcal{X}\\}$ with
the repetitive bin counted only once, and $\mathcal{I}_{p}$ as the index set.
In other words, the set $\pi_{p}=\\{A_{j}\\}_{j\in\mathcal{I}_{p}}$ forms a
partition of $H^{-1}(B_{r})$.

####  2.3.3 Binary Histogram Regressor

We consider the following function set $\mathcal{F}^{p}$ defined by

$\displaystyle\mathcal{F}^{p}:=\biggl{\\{}\sum_{j\in\mathcal{I}_{p}}c_{j}\boldsymbol{1}_{A_{j}}:c_{j}\in[-M,M]\biggr{\\}}.$
(6)

In order to constrain the complexity of $\mathcal{F}^{p}$, we penalize on the
depth $p$ of the partition $\pi_{p}$. Then the Binary Histogram with rotation
can be produced by the regularized empirical risk minimization (RERM) over
$\mathcal{F}^{p}$, i.e.

$\displaystyle(f_{\mathrm{D}},h^{*})=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}^{p},\,p\in\mathbb{N}_{+}}\Omega(p)+\mathcal{R}_{L,\mathrm{D}}(f),$
(7)

where $\Omega(p):=\lambda\cdot 4^{p}$. It is clear to see that the penalty on
the depth $p$ of the partition helps to control the bin width of the
rectangular cells.

We mention that when the rotation matrix $R$ is deterministic as the identity
matrix, we call the algorithm in Algorithm 1 and the regressor in (7) binary
histogram without rotation.

###  2.4 Gradient Boosted Binary Histogram (GBBH) for Regression

Boosting is the task of converting inaccurate weak learners into a single
accurate predictor. To be specific, we define a restricted family of functions
$\mathcal{F}$ be a set of base learners and a general boosting algorithm is
combining a sequence of functions $\\{f_{t}\\}_{t=1}^{T}$ from $\mathcal{F}$
to minimize a certain empirical loss. Then the final predictor can be
represented as

$\displaystyle F=\sum^{T}_{t=1}w_{t}f_{t},$

where $w_{t}\geq 0$, $t=1,\ldots,T$, are weights and $f_{t}\in\mathcal{F}$,
$t=1,\ldots,T$. From a functional gradient descent viewpoint in statistics
(Friedman, 2001), boosting is reformulated as a stage-wise optimization
problem with different loss functions. In this scenario, gradient boosting
requires computing the negative functional gradient as the response

$\displaystyle U_{i}=-\frac{\partial L(y_{i},f(x_{i}))}{\partial
f(x_{i})}\bigg{|}_{f(x_{i})=\hat{f}(x_{i})}$

and select a particular model from the allowable class of functions at each
boosting iteration to update the predictor.

In this work, we mainly focus on the boosting algorithm equipped with
(rotated) binary histogram regressors as base learners since they are weak
predictors and enjoy computational efficiency in high dimensional spaces.
Before we proceed, we need to introduce the function space that we are most
interested in to establish our learning theory. Assume that
$\\{R_{t}\\}_{t=1}^{T}$ is an i.i.d. sequence of random rotation matrix drawn
from some probability measure $\mathrm{P}_{R}$ and $\\{Z^{t}_{i,j},1\leq i\leq
p,1\leq j\leq 2^{i-1},1\leq t\leq T\\}$ is an i.i.d. sequence of selected
coordinate to split drawn from the probability measure $\mathrm{P}_{Z}$ given
by (3). For $1\leq t\leq T$, given rotation transformation $H_{t}$ and select
coordinates $Z_{t}:=\\{Z^{t}_{i,j},1\leq i\leq p,1\leq j\leq 2^{i-1}\\}$, we
define the function space $\mathcal{F}_{t}:=\mathcal{F}^{p}_{t}$,
$t=1,\ldots,T$ according to (6). Then for $r>0$, we define the function space
$E$ by

$\displaystyle
E:=\biggl{\\{}f:B_{r}\to\mathbb{R}\,\bigg{|}\,f=\sum_{t=1}^{T}w_{t}f_{t},\,f_{t}\in\mathcal{F}_{t}\biggr{\\}}.$
(8)

Moreover, for $f\in E$, we define

$\displaystyle\|f\|_{E}:=\inf\biggl{\\{}\sum_{t=1}^{T}|w_{t}|^{2}\text{ with
}f=\sum_{i=1}^{T}w_{t}f_{t},\,f_{t}\in\mathcal{F}_{t}\biggr{\\}}.$ (9)

Then for any $f\in E$, by the Cauchy-Schwarz inequality, we immediately get

$\displaystyle\|f\|_{\infty}\leq M\sum_{t=1}^{T}|w_{t}|\leq
M(T\|f\|_{E})^{1/2}.$

In fact, $(E,\|\cdot\|_{E})$ is a function space that consists of measurable
and bounded functions.

As is mentioned above, boosting methods may be viewed as iterative methods for
optimizing a convex empirical cost function. To simplify the theoretical
analysis, following the approach of Blanchard et al. (2003), we ignore the
dynamics of the optimization procedure and simply consider minimizers of an
empirical cost function to establish the oracle inequalities, which leads to
the following definition.

###### Definition 1

Let $E$ be the function space (8) and $L$ be the least square loss. Given
$\lambda_{1}>0$, $\lambda_{2}>0$, we call a learning method that assigns to
every $D\in(\mathcal{X}\times\mathcal{Y})^{n}$ a function
$f_{\mathrm{D},B}:\mathcal{X}\to\mathbb{R}$ such that

$\displaystyle(f_{\mathrm{D},B},h^{*})=\operatornamewithlimits{arg\,min}_{f\in
E,\,p\in\mathbb{N}_{+}}\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{D}}(f)$ (10)

a gradient boosted binary histogram (GBBH) algorithm for regression with
respect to $E$, where $\Omega_{\lambda}(f)$ is defined by

$\displaystyle\Omega_{\lambda}(f):=\lambda_{1}\Omega_{1}(f)+\lambda_{2}\Omega_{2}(f):=\lambda_{1}\|f\|_{E}+\lambda_{2}\cdot
4^{p}.$ (11)

The regularization term defined in (11) consists of two components. The first
term is motivated by the fact the early boosting methods such as Adaboost may
overfit in the presence of label noise. It helps control the degree of
overfitting by the $L_{2}$-norm of the weights of the composite estimators and
helps achieve the consistency and convergence results. The second term is
added to control the bin width of the binary histogram, which has been
discussed in subsection 2.3. In fact, it is equivalent to adding the
$L_{p}$-norm of the base learners $f_{t}$, since piecewise constant functions
are applied on the rectangular cells.

To conduct the theoretical analysis, we also need the infinite sample version
of Definition 1. To this end, we fix a distribution $\mathrm{P}$ on
$\mathcal{X}\times\mathcal{Y}$ and let the function space $E$ be as in (8).
Then every $f_{\mathrm{P},B}\in E$ satisfying

$\displaystyle\Omega_{\lambda}(f_{\mathrm{P},B})+\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P},B})=\inf_{f\in
E}\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)$

is called an infinite sample version of GBBH with respect to $E$ and $L$.
Moreover, the approximation error function $A(\lambda)$ is defined by

$\displaystyle A(\lambda)=\inf_{f\in
E}\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}.$
(12)

With all these preparations, we now present a general form of algorithm for
GBBH in Algorithm 2. Indeed, the randomness of rotation matrix and binary
histogram splitting rule provides an effective procedure for carrying out
boosting. With the help of (rotated) binary histogram regressor, we repeat the
least squares fitting of residuals. We mention that when the rotation matrix
is determined as the identity matrix, we call the algorithm in Algorithm 2
GBBH without rotation. Moreover, we introduce the learning rate $\rho$ to
dampen the move on the gradient descent update, which is related to the
regularization through shrinkage.

Input: Training data $D:=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$;

Depth of binary histogram $p$;

Learning rate $\rho>0$;

Initialization: $U_{i}=y_{i}$, $i=1,\ldots,n$. $\widehat{F}_{0}(x)=0$.

for $t=1$ to $T$ do

Compute the random rotation transformation  $\displaystyle
H_{t}(x):=R_{t}\cdot x.$

Apply rotated binary histogram in Algorithm 1 to the transformed space;

Apply constant functions to each cell, i.e., fit residuals with function
$f_{t}$ such that  $\displaystyle
f_{t}=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}_{t}}\frac{1}{n}\sum^{n}_{i=1}L(U_{i},f(x_{i})),$
where $\mathcal{F}_{t}$ is defined as in (6) with respect to $H_{t}$ and
selected coordinates $Z_{t}$.

Update: $\widehat{F}_{t}(x)=\widehat{F}_{t-1}(x)+\rho f_{t}(x)$.

Compute residuals $U_{i}=U_{i}-\widehat{F}_{t}(x_{i})$, $i=1,\ldots,n$.

end for

Output: Gradient boosted binary histogram regressor is
$f_{\mathrm{D},B}(x)=\widehat{F}_{T}(x)$.

Algorithm 2 Gradient Boosted Binary Histogram (GBBH) for Regression

###### Remark 2

In fact, the Gradient Boosting Algorithm 2 converges to the empirical risk
minimizer of the mean squared error with respect to the function space $E$
defined by (8)

$\displaystyle\frac{1}{n}\sum^{n}_{i=1}(y_{i}-F(x_{i}))^{2},$ (13)

which is illustrated as below:

  1. (i)

In the least-square regression setting, the goal of a gradient boosting
algorithm with $T$ stages is to fit a function $F$ of the form
$F(x)=\sum^{T}_{t=1}f_{t}(x)$ to minimize (13).

  2. (ii)

At stage $t\ (1\leq t\leq T)$, our algorithm should add some new estimator to
improve some imperfect model $F_{t-1}$ to correct the errors of its
predecessor. For regression problems, we observe that residuals are the
negative gradients (with respect to $F(x)$) of the squared error loss function
$(y-F(x))^{2}/2$. Then gradient boosting will fit $f_{t}$ from the hypothesis
space defined as in (6) to the residuals $U_{i}=y_{i}-F_{t-1}(x_{i})$.

  3. (iii)

Algorithm 2 does so by starting with a model $F_{0}(x)=0$, and incrementally
expands it in a greedy fashion. The main idea is to apply a (functional
gradient) descent step to this minimization problem to solve the
computationally infeasible optimization problem in general.

  4. (iv)

The regularization of gradient boosting methods is realized by shrinkage which
consists of modifying the update rule with learning rate as shown in Algorithm
2 to improve the generalization ability of the model.

In summary, in accordance with the empirical risk minimization principle,
gradient boosting algorithm tries to find an approximation $F(x)$ that
minimizes the average value of the loss function on the training set, i.e.,
minimizes the empirical risk with respect to the space $E$ defined by (8).

###  2.5 Gradient Boosted Binary Histogram Ensemble (GBBHE) for Large-scale
Regression

For large-scale regression problems, however, GBBH may be of low computational
efficiency since it requires a large number of boosting iterations in
practical applications. As a result, it is important to find some ways to
speed up the applications of GBBH. An intuitive idea is to increase the
accuracy of the base learner and thus reduce the number of iterations. To be
specific, we proposed a modified boosting algorithm using the ensemble of
(rotated) binary histogram regressors as base learners. Recall that in
Algorithm 2, at $t$-th round of boosting iteration, gradient boosting requires
computing the negative functional gradient as the response

$\displaystyle U^{t}_{i}=-\frac{\partial L(y_{i},f(x_{i}))}{\partial
f(x_{i})}\bigg{|}_{f(x_{i})=\widehat{F}_{t-1}(x_{i})}$ (14)

and select a particular model to fit residuals to update the current predictor
$F^{t-1}(x)$.

Before we proceed, we denote the number of boosting iterations as $T$ and the
number of learners for ensemble at each boosting iteration as $K$. Moreover,
we assume that $\\{R_{t}^{k},1\leq t\leq T,1\leq k\leq K\\}$ is an i.i.d.
sequence of random rotation matrix drawn from some probability measure
$\mathrm{P}_{R}$ and $\\{Z^{t,k}_{i,j},1\leq i\leq p,1\leq j\leq 2^{i-1},1\leq
t\leq T,1\leq k\leq K\\}$ is an i.i.d. sequence of selected coordinate to
split drawn from the probability measure $\mathrm{P}_{Z}$ given by (3). For
$1\leq t\leq T$ and $1\leq k\leq K$, given the rotation transformation
$H_{t}^{k}$ and select coordinates $Z_{t}^{k}:=\\{Z^{t,k}_{i,j},1\leq i\leq
p,1\leq j\leq 2^{i-1}\\}$, we define the function space $\mathcal{F}^{k}_{t}$
according to (6). In the scenario of gradient boosted binary histogram
ensemble for large-scale regression, at $t$-th round of boosting iteration,
let $D_{t}:=\\{(x_{1},U_{1}^{t}),\ldots,(x_{n},U_{n}^{t})\\}$ be the training
data with $U_{i}^{t}$, $1\leq i\leq n$ defined by (14). For $1\leq k\leq K$,
we write

$\displaystyle
f_{\mathrm{D}}^{t,k}:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}^{k}_{t}}\mathcal{R}_{L,\mathrm{D}_{t}}(f).$
(15)

Then the ensemble of the (rotated) binary histogram regressor at $t$-th round
of boosting is defined by

$\displaystyle\bar{f}_{t}:=\frac{1}{K}\sum_{k=1}^{K}f^{t,k}_{\mathrm{D}}.$

It is clear to see that $\bar{f}_{t}$ belongs to the function space
$\bar{E}_{t}$ given by

$\displaystyle\bar{\mathcal{F}}_{t}:=\biggl{\\{}f:B_{r}\to\mathbb{R}\,\bigg{|}\,f=\frac{1}{K}\sum_{k=1}^{K}f_{t}^{k},\,f_{t}^{k}\in\mathcal{F}_{t}^{k}\biggr{\\}}.$
(16)

Then we define the function space $\bar{E}$ by

$\displaystyle\bar{E}:=\biggl{\\{}f:B_{r}\to\mathbb{R}\,\bigg{|}\,f=\sum_{t=1}^{T}w_{t}\bar{f}_{t},\,\bar{f}_{t}\in\bar{\mathcal{F}}_{t}\biggr{\\}}.$
(17)

Moreover, for $f\in\bar{E}$, we define

$\displaystyle\|f\|_{\bar{E}}:=\inf\biggl{\\{}\sum_{t=1}^{T}|w_{t}|^{2}\text{
with
}f=\sum_{i=1}^{T}w_{t}\bar{f}_{t},\,\bar{f}_{t}\in\bar{\mathcal{F}}_{t}\biggr{\\}},$

which is similar as (9) where (rotated) binary histogram regressors are used
as base learners.

To simplify the theoretical analysis, by similar arguments in Section 2.4, we
ignore the dynamics of the optimization procedure and simply consider
minimizers of an empirical cost function to establish the oracle inequalities
for GBBHE, which leads to the following definition.

###### Definition 3

Let $\bar{E}$ be the function space (17) and $L$ be the least square loss.
Given $\lambda_{1}>0$, $\lambda_{2}>0$, we call a learning method that assigns
to every $D\in(\mathcal{X}\times\mathcal{Y})^{n}$ a function
$\bar{f}_{\mathrm{D},B}:\mathcal{X}\to\mathbb{R}$ such that

$\displaystyle(\bar{f}_{\mathrm{D},B},h^{*})=\operatornamewithlimits{arg\,min}_{f\in\bar{E},\,p\in\mathbb{N}_{+}}\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{D}}(f)$
(18)

a gradient boosted binary histogram ensemble (GBBHE) algorithm for regression
with respect to $E$, where $\bar{\Omega}_{\lambda}(f)$ is defined by

$\displaystyle\bar{\Omega}_{\lambda}(f):=\lambda_{1}\bar{\Omega}_{1}(f)+\lambda_{2}\bar{\Omega}_{2}(f):=\lambda_{1}\|f\|_{\bar{E}}+\lambda_{2}\cdot
4^{p}.$ (19)

Note that when the rotation matrix is determined as the identity matrix, we
call the algorithm in Definition 3 GBBHE without rotation.

Compared with the regularization term of (11), the first component of (19) is
replaced by $L_{2}$-norm of the weights of the composite estimators, that is,
the ensemble of the (rotated) binary histogram regressors to achieve the
consistency and convergence rates.

To conduct the theoretical analysis, we also need the infinite sample version
of Definition 3. Let the function space $\bar{E}$ be as in (8). Then every
$\bar{f}_{\mathrm{P},B}\in\bar{E}$ satisfying

$\displaystyle\bar{\Omega}_{\lambda}(\bar{f}_{\mathrm{P},B})+\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{P},B})=\inf_{f\in\bar{E}}\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)$

is called an infinite sample version of GBBHE with respect to $\bar{E}$ and
$L$. Moreover, the approximation error function $\bar{A}(\lambda)$ is defined
by

$\displaystyle\bar{A}(\lambda)=\inf_{f\in\bar{E}}\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}.$
(20)

With all these preparations, we now present a general form of the algorithm
for GBBHE in Algorithm 3. Indeed, the randomness of (rotated) binary histogram
provides an effective procedure for carrying out boosting. Moreover, the
ensemble of (rotated) binary histogram regressors helps to improve the
accuracy of each base estimator. As a result, fewer iteration rounds are
required to achieve satisfying performance in practical applications.

Input: Training data $D:=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$;

Depth of binary histogram $p$;

Learning rate $\rho>0$;

Number of ensembles $K>0$;

Initialization: $U_{i}=y_{i}$, $i=1,\ldots,n$. $\widehat{F}_{0}(x)=0$.

for $t=1$ to $T$ do

for $k=1$ to $K$ do

Compute the random rotation transformation  $\displaystyle
H_{t}^{k}(x):=R_{t}^{k}\cdot x.$

Apply rotated binary histogram in Algorithm 1 to the transformed space;

Apply constant functions to each cell, i.e., fit residuals with function
$f_{t}$ such that  $\displaystyle
f_{t}^{k}=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}_{t}^{k}}\frac{1}{n}\sum^{n}_{i=1}L(U_{i},f(x_{i})),$
where $\mathcal{F}_{t}^{k}$ is defined as in (6) with respect to $H_{t}^{k}$
and selected coordinates $Z_{t}^{k}$.

end for

Compute  $\displaystyle\bar{f}_{t}=\frac{1}{K}\sum^{K}_{k=1}f_{t}^{k}.$

Update: $\widehat{F}_{t}(x)=\widehat{F}_{t-1}(x)+\rho\bar{f}_{t}(x)$.

Compute residuals $U_{i}=U_{i}-\widehat{F}_{t}(x_{i})$, $i=1,\ldots,n$.

end for

Output: Boosted ensemble of rotated binary histogram regressor
$\bar{f}_{\mathrm{D},B}(x)=\widehat{F}_{T}(x)$.

Algorithm 3 Gradient Boosted Binary Histogram Ensemble (GBBHE) for Large-scale
Regression

##  3 Theoretical Results

In this section, we build theoretical results for GBBH and GBBHE in Hölder
space $C^{k,\alpha}$ consisting of $(k,\alpha)$-Hölder continuous functions of
different order of smoothness. To be specific, Section 3.1 shows the
fundamental assumption. In Section 3.2 and 3.3, we show the convergence rates
for GBBH in $C^{0,\alpha}$ and $C^{1,0}$, respectively. Then in Section 3.4
and 3.5, we show the convergence rates for GBBHE in $C^{0,\alpha}$ and
$C^{1,0}$, respectively.

###  3.1 Fundamental Assumption

We assume that the Bayes decision function resides in the Hölder space.

###### Definition 4

We say that a function $f:\mathcal{X}\to\mathbb{R}$ is $\alpha$-Hölder
continuous, namely $f(x)\in C^{0,\alpha}$ for $0<\alpha\leq 1$, if there
exists a finite constant $c_{L}>0$ such that for any $x,y\in\mathcal{X}$, we
have $|f(x)-f(y)|\leq c_{L}\|x-y\|^{\alpha}$. Moreover, if $f(x)$ is
differentiable at every $x\in\mathcal{X}$ such that $\|\nabla f(x)\|\leq
c_{L}$, we say that $f\in C^{1,0}$.

From Definition 4 we see that the functions contained in the space
$C^{0,\alpha}$ with larger $\alpha$ enjoy higher level of smoothness. It is
worth pointing out that $C^{1,0}$ is a proper subset of $C^{0,1}$ since there
exist Lipschitz continuous functions that are not everywhere differentiable.

Note that according to the definition of the function class $\mathcal{F}^{p}$
in (6), given an rotated binary histogram partition and $f\in\mathcal{F}^{p}$,
there holds $f(x)=0$ for $H(x)\notin[-r,r]^{d}$. As a result, to derive
consistency and convergence rates of boosted estimators, we further assume
that $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r,d}:=[-r/\sqrt{d},r/\sqrt{d}]^{d}$ in the theoretical results. For the
sake of brevity, we write
$\mathrm{P}_{R,Z}:=\mathrm{P}_{R}\otimes\mathrm{P}_{Z}$ in the following
sections.

###  3.2 Convergence Rates for GBBH in $C^{0,\alpha}$

###### Theorem 5

Let $f_{\mathrm{D},B}$ be the GBBH regressor defined by (10). Moreover,
suppose that the Bayes decision function $f_{L,\mathrm{P}}^{*}\in
C^{0,\alpha}$ and $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Furthermore, let
$\\{\lambda_{1,n}\\}$, $\\{\lambda_{2,n}\\}$ and $\\{p_{n}\\}$ be chosen as

$\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 $\delta:=1/(d\cdot 2^{p})$. Then for sufficiently large $n$, 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{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{-\alpha})+2d\log 2}}$ (21)

with probability $\mathrm{P}^{n}$ equal to one.

In particular, if $f^{*}_{L,\mathrm{P}}\in C^{0,1}$, then for sufficiently
large $n$, 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{3}{3(2-\delta)+4d\log 2}}$

with probability $\mathrm{P}^{n}$ equal to one.

######  Remark 6 (Convergence rate)

Under mild assumption that the target function is $\alpha$-Hölder continuous,
i.e., $f_{L,\mathrm{P}}^{*}\in C^{0,\alpha}$, we derive the convergence rate
of GBBH with probability one. In particular, when $\alpha=1$, the convergence
rate is $n^{-0.75/(1.5+d\log 2)}$. We will show in the next subsection that
GBBH attains faster convergence rate in the subspace $C^{1,0}$.

######  Remark 7 (Effect of Rotation)

We remark that the rotation transformation does not affect the order of
convergence rates. That is, in Theorem 5, when the rotation matrix is
determined as the identity matrix, the convergence rate of GBBH is the same
order as in (21). We mention that the effect of rotation also holds for
Theorems 9, 14, and 16.

######  Remark 8 (Effect of the number of iterations $T$)

In Theorem 5, we establish a uniform upper bound for the excess risk
regardless of the number of iterations $T$. In other words, from the
perspective of convergence rate, we cannot demonstrate the advantage of the
boosting estimator over its base learners. Therefore, in the next subsection,
we turn to the subspace $C^{1,0}$ to show the effect of boosting with the help
of a lower bound for the convergence rate of the base learners.

###  3.3 Convergence Rates for GBBH in $C^{1,0}$

###### Theorem 9

Let $f_{\mathrm{D},B}$ be the GBBH regressor defined by (10). Moreover,
suppose that the Bayes decision function $f_{L,\mathrm{P}}^{*}\in C^{1,0}$ and
$\mathrm{P}_{X}$ is the uniform distribution on
$B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Furthermore, let
$\\{\lambda_{1,n}\\}$, $\\{\lambda_{2,n}\\}$, $\\{T_{n}\\}$ and $\\{p_{n}\\}$
be chosen as

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

where $\delta:=1/(d\cdot 2^{p})$. Then for sufficiently large $n$, there holds

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

with probability $\mathrm{P}^{n}$ equal to one.

######  Remark 10 (Convergence rate)

As is shown in Theorem 9, when $f_{L,\mathrm{P}}^{*}\in C^{1,0}$, GBBH attains
the asymptotically convergence rate $n^{-1/(2+d\log 2)}$. Compared with Remark
6, we find that GBBH converges faster in the subspace $C^{1,0}$ than in the
space $C^{0,1}$.

######  Remark 11 (Effect of the number of iterations $T$)

Different from the results in Theorem 5, where we derive a uniform upper bound
for the excess risk regardless of the change of $T$, the excess risk decreases
as $T_{n}$ increases at first, and then achieves its minimum when the number
of iterations $T_{n}$ attains a certain level when $f_{L,\mathrm{P}}^{*}\in
C^{1,0}$. This indicates that our proposed GBBH tends to perform better when
the target function is of higher order of smoothness.

To demonstrate the advantage of boosting, we show a lower bound for the
convergence rate of the base learners in the following theorem. In this case,
let $H$ be the identity map in the rotated binary histogram defined by
Algorithm 1, that is, we leave out the randomness of the transform. Moreover,
we suppose that $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r}:=[-r,r]^{d}$ instead of on $B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$
mentioned above.

###### Theorem 12

Let the rotated binary histogram $A_{p}$ be defined by Algorithm 1 with the
identity map $H(x)=x$. Moreover, let the binary histogram regressor
$f_{\mathrm{D}}$ be defined as in (7) and the regression model be defined by
$Y:=f(X)+\varepsilon$, where $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r}=[-r,r]^{d}$ and $\varepsilon$ is independent of $X$ such that
$\mathbb{E}(\varepsilon)=0$ and $\mathrm{Var}(\varepsilon)=\sigma^{2}<\infty$.
Moreover, assume that $f\in C^{1,0}$ and there exists a constant
$\underline{c}_{f}\in(0,\infty)$ such that $\|\nabla f\|\geq\underline{c}_{f}$
and $\|f\|_{\infty}\geq\underline{c}_{f}$. Then we have

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{R}}\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},$ (23)

where $c_{0}$ and $c_{1}$ are constants depending on $r$, $d$,
$\underline{c}_{f}$ and $\sigma$ which will be specified in the proof.

######  Remark 13 (Benefits of boosting)

In Theorem 12, we show that for some $f\in C^{1,0}$, the excess risk of the
binary histogram regressor attains $n^{(\log(1-0.75/d))/(\log
2-\log(1-0.75/d))}$. In particular, when the dimension $d\to\infty$, the lower
bound shown in (23) turns out to be $n^{-0.75/(0.75+d\log 2)}$. Note that if
$d\geq 6$, then the upper bound of the convergence rate (22) for GBBH will be
smaller than the lower bound (23) for binary histogram regression, which
explains the benefits of the boosting procedure.

###  3.4 Convergence Rates for GBBHE in $C^{0,\alpha}$

###### Theorem 14

Let $\bar{f}_{\mathrm{D},B}$ be the GBBHE regressor defined by (18). Moreover,
suppose that the Bayes decision function $f_{L,\mathrm{P}}^{*}\in
C^{0,\alpha}$ and $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Furthermore, let
$\\{\lambda_{1,n}\\}$, $\\{\lambda_{2,n}\\}$ and $\\{p_{n}\\}$ be chosen as

$\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 $\delta:=1/(d\cdot 2^{p})$. Then for sufficiently large $n$, 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{2(1-4^{-\alpha})}{(4-2\delta)(1-4^{-\alpha})+2d\log 2}}$

with probability $\mathrm{P}^{n}$ equal to one.

In particular, if $f^{*}_{L,\mathrm{P}}\in C^{0,1}$, then for sufficiently
large $n$, 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{3}{3(2-\delta)+4d\log 2}}$

with probability $\mathrm{P}^{n}$ equal to one.

######  Remark 15 (Convergence rate)

When $f_{L,\mathrm{P}}^{*}\in C^{0,\alpha}$, we derive the convergence rate of
GBBHE with probability one. In particular, when $\alpha=1$, the convergence
rate turns out to be of the order $n^{-3/(6+4d\log 2)}$. We notice that GBBHE
attains the same convergence rate with the same parameter selections of
$\lambda$ and $p$ as GBBH in the space $C^{0,1}$.

###  3.5 Convergence Rates for GBBHE in $C^{1,0}$

###### Theorem 16

Let $\bar{f}_{\mathrm{D},B}$ be the GBBHE regressor defined by (18). Moreover,
suppose that the Bayes decision function $f_{L,\mathrm{P}}^{*}\in C^{1,0}$ and
$\mathrm{P}_{X}$ is the uniform distribution on
$B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Furthermore, let
$\\{\lambda_{1,n}\\}$, $\\{\lambda_{2,n}\\}$, $\\{T_{n}\\}$, $\\{K_{n}\\}$ and
$\\{p_{n}\\}$ be chosen as

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

where $\delta:=1/(d\cdot 2^{p})$. Then, for sufficiently large $n$, there
holds

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

with probability $\mathrm{P}^{n}$ equal to one.

######  Remark 17 (Convergence rate)

When $f_{L,\mathrm{P}}^{*}\in C^{1,0}$, GBBHE attains the asymptotically
convergence rate $n^{-1/(2+d\log 2)}$, which is the same as that of GBBH.

######  Remark 18 (Effect of ensemble)

Recall that for GBBH in Theorem 3.3, to achieve the convergence rate, we
require the number of iterations $T_{n}$ to be of the order $n^{1/(8+4d\log
2)}$. On the other hand, for GBBHE, to achieve the same convergence rate, we
require that $T_{n}K_{n}$ is of the order $n^{1/(8+4d\log 2)}$, which
indicates that we can reduce the number of iterations $T$ by enlarging the
number of base learners for ensemble $K$. Note that boosting algorithms with a
large number of iterations can be quite time-consuming, while acceleration
techniques such as parallel computing is not directly available. On the
contrary, by combining ensemble methods, which enjoy high computational
efficiency with the help of parallel computing, we reduce the running time of
GBBHE by reducing the number of iterations $T$.

######  Remark 19 (Inclusive framework)

Theorem 16 applies to both pure gradient boosting algorithm and pure ensemble
algorithm. To be specific, when $K=1$, the Theorem 16 corresponds to Theorem
5. When $T=1$, Theorem 16 shows the convergence rate for the algorithm of
ensembling the base learners.

##  4 Numerical Experiments

In this section, we conduct numerical experiments including parameter analysis
and comparisons with other state-of-the-art large-scale regression algorithms.
Aiming at empirically evaluating the large-scale application of our algorithm,
we conduct the experiments following Algorithm 3. Yet in this part, the split
points in the binary histogram partition are selected as the mean point of
data from a randomly selected dimension, since the support of real data is
usually unknown in the high-dimensional space. We mention that in this way our
proposed GBBHE actually enjoys more adaptivity to various datasets. This
section is organized as follows. In Section 4.1, we conduct parameter analysis
of the four important parameters in Algorithm 3. Then in Section 4.2, we
compare our GBBHE with other state-of-the-art methods for large-scale
regression on moderate-sized and large-scale real datasets.

###  4.1 Parameter Analysis

In this subsection, we apply parameter analysis to explore the effects of
hyper-parameters in the proposed gradient boosted binary histogram transform
ensemble (GBBHE) algorithm. In this part, we conduct experiments with GBBHE
without random rotation. The reasons are bifold. Firstly, here we are mainly
interested in the behavior of the binary histogram partition, the boosting
procedure, and the ensemble. Secondly and more importantly, rotations
introduce extra randomness that may affect the performance of the algorithm.
Therefore, to conduct parameter analysis, we control this factor and let the
transformation $H$ be the identity matrix. The data set we used for parameter
analysis is the Physicochemical Properties of Protein Tertiary Structure Data
Set (${\tt PTS}$) from the UCI machine learning repository (Dua and Graff,
2017), which contains $45,730$ samples of dimension $9$.

There are four hyper-parameters to be discussed, including the number of
iteration $T$, the learning rate $\rho$, the number of binary histograms in
each iteration $K$, and the depth of binary histograms $p$. We randomly split
the ${\tt PTS}$ data set into $70\%$ training set and $30\%$ testing set and
repeat the experiments for $50$ times in each hyper-parameter setting.

####  4.1.1 Regularization under Different Numbers of Binary Histograms

Firstly, we would like to show our surprising finding that ensemble of binary
histograms in each iteration of the proposed GBBHE can greatly boost the
numerical performance with easier hyper-parameter selection in the empirical
aspect. To illustrate this, we vary the number of iteration
$T\in\\{1,10,100,200,500,1000,2000\\}$ and the learning rate
$\rho\in\\{0.1,0.3,0.5,0.7,1.0\\}$, fix the depth of binary histograms $p=8$,
and plot the test error curves under different numbers of binary histograms
$K=1$ and $K=10$. Results are shown in Figure 2 and Figure 3 respectively.

In Figure 2, only when the number of iteration $T$ is large enough and the
learning rate $\rho$ is small enough does the boosted rotated binary
histograms without ensemble in each iteration have good performance. This
verifies the common phenomenon that there is a trade-off between the number of
iterations $T$ and the learning rate $\rho$ in gradient boosting. However, it
is very difficult to determine the optimal $T$ and $\rho$ because the trade-
off is quite sensitive when the number of hists $K=1$.

By contrast, when ensemble is introduced in each iteration of boosted rotated
binary histograms, e.g., $K=10$, the trade-off between the number of iteration
$T$ and the learning rate $\rho$ is much less sensitive, see Figure 3 in
detail. Although the performance of GBBHE will slightly worse when $T$ and
$\rho$ become too large, i.e, the trade-off between the number of iteration
$T$ and the learning rate $\rho$ illustrated in Figure 2 also exists, we find
that the performance is satisfactory among a wide range of $T$ and $\rho$.
Moreover, it is well worth mentioning that the boosting performance when
$K=10$ converges faster than that of $K=1$ compared with Figure 2, resulting
in better performance. This exactly corresponds to the theoretical result in
Theorem 16 that ensemble can reduce the number of iterations $T$ to achieve
the fast convergence rate. To conclude, the introduced ensemble with $K=10$
not only stabilizes the hyper-parameter selection of $T$ and $\rho$, but also
boosts the convergence of the boosting algorithm.

Figure 2: Test error curves when the number of binary histograms $K=1$.

Figure 3: Test error curves when the number of binary histograms $K=10$.

####  4.1.2 Parameter Analysis about the Learning Rate

Secondly, we would like to discuss the tendency of the learning rate $\rho$
among different number of iterations $T$. We fix the number of binary
histograms $K=10$ and the depth of binary histograms $p=8$, and then vary the
choice of the learning rate $\rho\in\\{0.1,0.3,0.5,0.7,1.0\\}$ among four
different $T\in\\{200,500,1000,2000\\}$.

Figure 4: Test error curves among various $\rho$ under fixed $K=10$ and $p=8$.

From Figure 4 we see that the test error decreases to an optimal value and
then increases as the learning rate $\rho$ increases from $0.1$ to $1.0$.
Besides, we observe that the optimal $\rho$ varies by different numbers of
iterations. To be specific, smaller $T$ leads to larger optimal $\rho$, while
the optimal $\rho$ goes down with larger $T$. For example, the optimal $\rho$
when $T=200$ is $1.0$, while the optimal $\rho$ when $T=2000$ is $0.3$.
Moreover, as the number of iteration $T$ goes up, the test error under optimal
$\rho$ consistently decreases, which shows empirically that larger $T$ with
smaller $\rho$ yields better numerical performance.

####  4.1.3 Parameter Analysis about the Number of Binary Histograms

Secondly, we discuss the choice of the number of binary histograms $K$, which
controls how ensemble is used in the algorithm GBBHE: larger $K$ means more
binary histograms built in each iteration of boosting. To be specific, we fix
the number of iterations $T=100$ and the depth of binary histograms $p=8$, and
then vary $K\in\\{1,2,5,10,20,50,100,200\\}$ among different learning rates
$\rho\in\\{0.1,0.3,0.5,0.7,1.0\\}$.

Figure 5 and Figure 6 show the accuracy performances and the running times
under different numbers of binary histograms $K$ respectively. As is shown, on
the one hand, as $K$ goes up, the performances of regression continue to rise,
only with the cost of higher computation times. On the other hand, the
marginal increase of performance drops as $K$ becomes larger. This phenomenon
is consistent regardless of the learning rate $\rho$ varies. Therefore,
considering the trade-off between accuracy and running time, $K=100$ shows a
satisfactory performance with tolerable running time. Moreover, Figure 5
suggests that ensemble is especially beneficial for large learning rate
$\rho$. This to some extent corresponds to the numerical result shown in
Section 4.1.2 that ensemble helps improve performance and the stability of
$\rho$.

Figure 5: Test error curves among various $K$ under fixed $T=100$ and $p=8$.

Figure 6: Running time among various $K$ under fixed $T=100$ and $p=8$.

####  4.1.4 Parameter Analysis about the Depth of Binary Histograms

One more hyper-parameter we need to discuss is the depth of binary histograms
$p$. The depth $p$ controls the denseness of binary histogram partition: the
total cells of each binary histogram is $2^{p}$, and larger $p$ means more
partitions for each binary histogram. To numerically analyze the effect of
different depths of binary histograms $p$, we fix the number of iterations
$T=100$ and the number of binary histograms in each iteration $K=100$, and
vary the depth $p\in\\{2,4,6,8,10,12,14\\}$ among different learning rate
$\rho\in\\{0.1,0.3,0.5,0.7,1.0\\}$.

Figure 7 and Figure 8 show the accuracy performances and the running times
under different depths of binary histograms $p$ respectively. As the depth
increases, the accuracy performance first goes up and reaches its optimum, and
then deteriorates when the depth of binary histograms becomes too large, with
the running time monotonically increasing. This phenomenon is consistent
regardless of the learning rate $\rho$ varies. It may attribute to the fact
that splitting more in each binary histogram helps to build up binary
histograms with local adaptivity, but if $p$ is too large, the partitions of
binary histograms will be too dense and it is at the risk of over-fitting.
Besides, it would be too time-consuming to adopt such large $p$. This also
verifies the theoretical results in Theorem 14 and 16 that there exists an
optimal order of depth $p$.

Figure 7: Test error curves among various $p$ under fixed $T=100$ and $K=100$.

Figure 8: Running time among various $p$ under fixed $T=100$ and $K=100$.

###  4.2 Numerical Comparisons

In this subsection, we conduct numerical studies to evaluate the effectiveness
of our proposed Gradient Boosting Binary Histogram Transforms Ensemble (GBBHE)
algorithm on moderate and large-scale real data sets. In this part, we
consider the rotation transform as an option, i.e., we compare both GBBHE
without random rotation (GBBHE w.o. Rotation) and standard GBBHE with random
rotation (GBBHE w. Rotation) as is shown in Algorithm 3 with other state-of-
the-art large-scale regression algorithms.

####  4.2.1 Experimental Setups

Comparisons are conducted among

  * •

Gradient Boosting Regression Tree (GBRT): Gradient Boosting Regression Trees
is a well-known ensemble method for regression proposed by Friedman (2001).
However, different from random forest, trees in GBRT are fitted in a
sequential manner. We use the scikit-learn implementation in Python. Three
hyper-parameters are considered, including the number of iteration times $T$,
learning rate shrinking the contribution of each tree $\rho$, and the minimum
number of samples required to split an internal node min_samples_split. We use
a validation set containing $10\%$ of the training samples to find the best
$T\in\\{100,200\\}$, $\rho\in\\{0.1,0.2,\ldots,0.9,1.0\\}$, and ${\tt
min\\_samples\\_split}\in\\{2,5,10,20,50,100,200,500\\}$.

  * •

Random Forest: Random forest is a well-known ensemble algorithm for regression
proposed by Breiman (2001). As each tree is fitted in parallel, random forest
is naturally suitable in large-scale applications. We use the scikit-learn
implementation in Python. Two hyper-parameters are the number of estimators in
the forest $T$ and the minimum number of samples required to split an internal
node min_samples_split. We use a validation set containing $10\%$ of the
training samples to find the best $T\in\\{100,200,500\\}$ and ${\tt
min\\_samples\\_split}\in\\{2,5,10,20,50,100,200,500\\}$.

  * •

LiquidSVM: Support vector machines for regression being a global algorithm is
impeded by super-linear computational requirements in terms of the number of
training samples in large-scale applications. To address this, Meister and
Steinwart (2016) employs a spatially oriented method to generate the chunks in
feature space, and fit LS-SVMs for each local region using training data
belonging to the region. This is called the Voronoi partition support vector
machine (VP-SVM). We use the implementation provided by the authors in Python.
In each local region, we conduct five-fold cross-validation (CV) to find the
best hyper-parameters $C$ and $\epsilon$.

As for the hyper-parameter tuning of our method, we use a validation set to
find the number of iterations $T\in\\{100,200,500\\}$, the number of binary
histograms $K\in\\{10,100,200\\}$, best learning rate
$\rho\in\\{0.1,0.3,0.5,0.7,1.0\\}$ and the best depth parameter
$p\in\\{4,6,8,10,12\\}$.

For moderate-sized datasets, we also randomly split $70\%$ of the data set for
training and the other $30\%$ for testing. We scale each feature individually
to the range $[0,1]$ on the training set. Hyper-parameters are selected by
validation and experiments are repeated $50$ times. For the large-scale data
sets, the partition of the training set and the testing set is specified in
their detailed descriptions in Section 4.2.2, and we repeat the experiments
$20$ times. We record and summarize the average and the standard deviation of
the mean squared error, the mean absolute error, and the running time under
the best hyper-parameter setting over all experiments. All experiments are
conducted on a 64-bit machine with 40-cores Intel Xeon 2.0GHz CPU (E5-4620)
and 256GB main memory.

####  4.2.2 Description of Datasets

We use for the evaluation seven moderate-sized datasets and five well-known
large-scale datasets from the UCI machine learning repository (Dua and Graff,
2017), LIBSVM Data111LIBSVM Data: Classification, Regression, and Multi-label.
https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/, and Delve
Datasets222Delve Datasets: Collections of data for developing, evaluating, and
comparing learning methods.
https://www.cs.toronto.edu/~delve/data/datasets.html. Details of these data
sets, including size and dimension, are summarized in Table 1.

Table 1: Description over Real Data Sets | datasets | size | dimension
---|---|---|---
Moderate-sized | EGS | $10,000$ | $12$
AEP | $19,735$ | $27$
CAD | $20,640$ | $8$
SCD | $21,263$ | $81$
HPP | $22,784$ | $8$
ONP | $39,644$ | $58$
PTS | $45,730$ | $9$
Large-scale | MSD | $515,345$ | $90$
BUZ | $583,250$ | $77$
GHG | $955,167$ | $15$
GTM | $3,843,160$ | $18$
DGM | $4,208,261$ | $16$

  * •

EGS: The Electrical Grid Stability Simulated Data Set (EGS) (Arzamasov et al.,
2018) is available on the UCI Machine Learning Repository. It contains
$10,000$ samples in total. $12$ attributes are used to predict the maximal
real part of the characteristic equation root.

  * •

AEP: The Appliances Energy Prediction Data Set (AEP) (Candanedo et al., 2017),
available on UCI Machine Learning Repository, contains $19,735$ samples of
dimension $27$ with attribute “date” removed from the original data set. The
data is used to predict the appliances energy use in a low-energy building.

  * •

CAD: The California Housing Prices Data Set (CAD) is avaliable on the LIBSVM
Data. This spacial data can be traced back to Pace and Barry (1997). It
consists $20,640$ observations on housing prices with $8$ economic covariates.
Note that for the sake of clarity, all house prices in the original data set
have been modified to be counted in thousands.

  * •

SCD: The Superconductivity Data Set (SCD) (Hamidieh, 2018), available on the
UCI Machine Learning Repository, is supported by the NIMS, a public
institution based in Japan. This database has $21,263$ samples with $81$
features. The goal is to predict the critical temperature based on the
features extracted.

  * •

HPP: The House Price Prototask Data Set (HPP) is originally taken from the
census-house dataset in the DELVE Datasets. We use the house-price-8H
prototask, which contains $22,784$ observations. We use $8$ features to
predict the median house prices from $1990$ US census data. Similar to the
data preprocessing for CAD, all house prices in the original data set have
been modified to be counted in thousands.

  * •

ONP: The Online News Popularity Data Set (ONP) (Fernandes et al., 2015),
available on the UCI Machine Learning Repository, is a database summarizing a
heterogeneous set of features about articles published by Mashable in a period
of two years. It contains $39,644$ observations with $58$ predictive
attributes. This data set is used to predict the number of shares of the
online news.

  * •

PTS: Physicochemical Properties of Protein Tertiary Structure Data Set (${\tt
PTS}$) is available on the UCI Machine Learning Repository. It contains
$45,730$ samples of dimension $9$. The regression task is to predict the size
of the residue.

  * •

MSD: The Year Prediction MSD Data Set (MSD) (Bertin-Mahieux et al., 2011) is
available on the UCI Machine Learning Repository. It contains $463,715$
training samples and $51,630$ testing samples with $90$ attributes, depicting
the timbre average and timbre covariance of songs released between the years
1922 and 2011. The main task is to learn the audio features of a song and to
predict its release year.

  * •

BUZ: Buzz in Social Media Data Set (BUZ) (Kawala et al., 2013) is available on
the UCI Machine Learning Repository. It contains examples of buzz events from
two different social networks: Twitter, and Tom’s Hardware. We select the
Twitter part, which contains $583,250$ samples of dimension $77$ and the last
column is for prediction. We use the first $450,000$ samples for training, and
use the remaining $133,250$ samples for testing.

  * •

GHG: The Greenhouse Gas Observing Network Data Set (GHG) (Lucas et al., 2015)
is available on the UCI Machine Learning Repository. It contains $955,167$
samples of dimension $15$, which are time series of GHG tracers released from
$14$ distinct spatial regions in California and one outside of California. The
main task is to predict emissions of greenhouse gas. We use the first
$800,000$ samples for training, and use the remaining $155,167$ samples for
testing.

  * •

GTM: The Gas Sensor Array Temperature Modulation Data Set (GTM) (Burgués et
al., 2018; Burgués and Marco, 2018) is available on the UCI Machine Learning
Repository. We use the readings of $14$ temperature-modulated metal oxide
semiconductor gas sensors, a temperature sensor, and a humidity sensor, as
well as the values of mass flow rate and the heater voltage to predict the
concentration level of CO. The total number of samples is $3,843,160$ and the
feature dimension is $18$. We use the first $3,500,000$ samples for training
and the remaining $343,160$ samples for evaluation.

  * •

DGM: The Gas Sensor Array Under Dynamic Gas Mixtures Data Set (DGM) (Fonollosa
et al., 2015) is available on the UCI Machine Learning Repository. Two gas
mixtures are generated in this data set: Ethylene and Methane in air, and
Ethylene and CO in air. We select the ethylene-CO mixture in the experimental
section, with $4,208,261$ samples in total. We use readings of $16$ chemical
sensors to predict the concentration level of CO. In the experiments, we use
the first $3,500,000$ samples for training and the remaining $708,261$ samples
for testing.

####  4.2.3 Results

The comparing results of the average MSE and MAE on seven moderate datasets
EGS, AEP, CAD, SCD, HPP, ONP, PTS and five large-scale datasets MSD, BUZ, GHG,
GTM, and DGM are presented in Figures 2 and 3. Moreover, we point out that the
Wilcoxon test for paired samples with significance level $\alpha=0.05$ are
applied.

Table 2: Average MSE over Moderate and Large-scale datasets

| Ours (w.o. Rotation) | Ours (w. Rotation) | Random Forest | LiquidSVM | GBRT
---|---|---|---|---|---
EGS | $1.40\text{e-}4(8.04\text{e-}6)$ | $1.01\text{e-}4(4.40\text{e-}6)$ | $1.42\text{e-}4(4.85\text{e-}6)$ | $\mathbf{7.38\text{e-}5(3.73\text{e-}6)}$ | $9.12\text{e-}5(3.23\text{e-}6)$
AEP | $\mathbf{5078.88(319.57)}$ | $6596.43(364.30)$ | $5184.99(312.02)$ | $6728.02(398.056)$ | $6006.91(335.37)$
CAD | $2582.74(77.07)$ | $2980.76(101.08)$ | $2434.30(73.60)$ | $2996.90(91.70)$ | $\mathbf{2308.72(65.28)}$
SCD | $\mathbf{84.21(3.21)}$ | $89.89(3.22)$ | $90.67(3.50)$ | $110.02(5.89)$ | $103.93(3.17)$
HPP | $\mathbf{1100.14(68.62)}$ | $1218.92(70.13)$ | $1125.47(73.79)$ | $1262.78(81.57)$ | $1211.36(69.17)$
ONP | $\mathbf{123.68(47.63)}$ | $125.04(47.80)$ | $125.75(47.26)$ | $125.65(47.64)$ | $127.60(46.60)$
PTS | $\mathbf{11.38(0.18)}$ | $12.40(0.19)$ | $12.60(0.17)$ | $13.73(0.23)$ | $16.69(0.22)$
MSD | $80.45(0.04)$ | $\mathbf{77.42(0.07)}$ | $85.72(0.04)$ | $85.33(0.73)$ | $81.84(0.01)$
BUZ | $1.38\text{e}4(40.15)$ | $\mathbf{1.28e4(65.12)}$ | $1.44\text{e}4(41.49)$ | $2.99\text{e}4(124.23)$ | $1.43\text{e}4(56.64)$
GNG | $389.00(0.08)$ | $\mathbf{261.16(0.03)}$ | $267.70(0.04)$ | $272.98(5.28)$ | $261.56(0.00)$
GTM | $\mathbf{3.44(0.00)}$ | $12.73(0.08)$ | $4.79(0.02)$ | $13.45(0.16)$ | $4.80(0.00)$
DGM | $8.08e3(38.57)$ | $\mathbf{6.23e3(45.00)}$ | $1.39e4(68.16)$ | $1.00e4(102.17)$ | $8.19e3(0.00)$

  * •

* The best results are marked in bold, and the standard deviation is reported in the parenthesis beside each value.

Table 3: Average MAE over Moderate and Large-scale datasets

| Ours (w.o. Rotation) | Ours (w. Rotation) | Random Forest | LiquidSVM | GBRT
---|---|---|---|---|---
EGS | $8.92\text{e-}3(2.88\text{e-}4)$ | $7.35\text{e-}3(1.46\text{e-}4)$ | $9.17\text{e-}3(1.43\text{e-}4)$ | $\mathbf{5.98\text{e-}3(1.67\text{e-}4)}$ | $7.09\text{e-}3(1.18\text{e-}4)$
AEP | $\mathbf{34.06(0.94)}$ | $40.92(0.83)$ | $34.40(0.84)$ | $42.69(0.85)$ | $41.04(0.84)$
CAD | $34.63(0.40)$ | $36.82(0.52)$ | $\mathbf{32.10(0.41)}$ | $37.33(0.47)$ | $32.43(0.42)$
SCD | $\mathbf{4.97(0.07)}$ | $5.24(0.08)$ | $5.32(0.08)$ | $6.09(0.18)$ | $6.30(0.09)$
HPP | $17.23(0.27)$ | $18.65(0.31)$ | $\mathbf{17.10(0.28)}$ | $18.90(0.36)$ | $18.31(0.27)$
ONP | $\mathbf{3.01(0.08)}$ | $3.07(0.07)$ | $3.06(0.07)$ | $3.18(0.06)$ | $3.05(0.11)$
PTS | $\mathbf{2.27(0.03)}$ | $2.37(0.02)$ | $2.41(0.02)$ | $2.59(0.02)$ | $3.05(0.02)$
MSD | $6.29(0.00)$ | $\mathbf{6.08(0.00)}$ | $6.52(0.01)$ | $6.47(0.02)$ | $6.37(0.00)$
BUZ | $38.70(0.06)$ | $\mathbf{38.68(0.05)}$ | $39.70(0.03)$ | $47.33(0.49)$ | $40.37(0.02)$
GNG | $13.90(0.03)$ | $\mathbf{12.54(0.00)}$ | $12.69(0.00)$ | $12.66(0.02)$ | $12.55(0.00)$
GTM | $\mathbf{1.09(0.00)}$ | $2.16(0.01)$ | $1.28(0.00)$ | $2.24(0.02)$ | $1.32(0.00)$
DGM | $55.89(0.47)$ | $\mathbf{44.24(0.41)}$ | $69.63(0.23)$ | $47.93(1.84)$ | $60.15(0.00)$

  * •

* The best results are marked in bold, and the standard deviation is reported in the parenthesis under each value.

Table 4: Performance Comparisons w.r.t. Accuracy and Running Time on MSD Dataset Algorithms | MSE | MAE | Running Time
---|---|---|---
Ours (w.o. Rotation), $T=100$, $K=100$ | $81.34(0.06)$ | $6.341(0.00)$ | $377.33(6.41)$
Ours (w.o. Rotation), $T=200$, $K=100$ | $80.66(0.08)$ | $6.301(0.00)$ | $737.06(8.74)$
Ours (w. Rotation), $T=100$, $K=100$ | $78.07(0.06)$ | $6.121(0.00)$ | $539.08(4.89)$
Ours (w. Rotation), $T=200$, $K=100$ | $77.42(0.07)$ | $6.083(0.00)$ | $1070.29(7.02)$
Random Forest, $T=100$ | $85.98(0.06)$ | $6.533(0.00)$ | $223.79(4.37)$
Random Forest, $T=200$ | $85.82(0.05)$ | $6.526(0.00)$ | $417.46(4.32)$
Random Forest, $T=500$ | $85.72(0.04)$ | $6.525(0.01)$ | $1009.95(21.03)$
LiquidSVM | $85.33(0.73)$ | $6.475(0.02)$ | $380.99(6.99)$
GBRT, $T=100$ | $84.21(0.00)$ | $6.490(0.00)$ | $1072.73(21.03)$
GBRT, $T=200$ | $83.01(0.00)$ | $6.435(0.00)$ | $2430.94(28.41)$
GBRT, $T=500$ | $81.84(0.00)$ | $6.373(0.00)$ | $6286.47(89.26)$
Table 5: Performance Comparisons w.r.t. Accuracy and Running Time on GTM Dataset  Algorithms | MSE | MAE | Running Time
---|---|---|---
Ours (w.o. Rotation), $T=100$, $K=100$ | $3.46(0.01)$ | $1.08(0.00)$ | $1375.34(3.39)$
Ours (w.o. Rotation), $T=200$, $K=100$ | $3.44(0.00)$ | $1.08(0.00)$ | $2575.51(63.14)$
Ours (w. Rotation), $T=100$, $K=100$ | $12.78(0.08)$ | $2.16(0.01)$ | $1557.91(45.96)$
Ours (w. Rotation), $T=200$, $K=100$ | $12.73(0.08)$ | $2.17(0.01)$ | $3054.23(74.22)$
Random Forest, $T=100$ | $4.82(0.03)$ | $1.28(0.00)$ | $255.23(0.12)$
Random Forest, $T=200$ | $4.81(0.02)$ | $1.28(0.00)$ | $452.59(8.89)$
Random Forest, $T=500$ | $4.79(0.02)$ | $1.28(0.00)$ | $1106.80(10.45)$
LiquidSVM | $13.45(0.16)$ | $2.24(0.02)$ | $3734.02(53.02)$
GBRT, $T=100$ | $5.46(0.00)$ | $1.45(0.00)$ | $1850.05(68.79)$
GBRT, $T=200$ | $4.80(0.00)$ | $1.32(0.00)$ | $3442.05(19.90)$
Table 6: Performance Comparisons w.r.t. Accuracy and Running Time on DGM Dataset Algorithms | MSE | MAE | Running Time
---|---|---|---
Ours (w.o. Rotation), $T=100$, $K=100$ | $8077.41(38.57)$ | $57.36(0.79)$ | $745.06(10.50)$
Ours (w.o. Rotation), $T=200$, $K=100$ | $8116.47(109.24)$ | $55.89(0.47)$ | $1795.54(5.95)$
Ours (w. Rotation), $T=100$, $K=100$ | $6234.73(45.00)$ | $44.24(0.41)$ | $1232.47(14.21)$
Ours (w. Rotation), $T=200$, $K=100$ | $6242.31(42.92)$ | $44.45(0.40)$ | $2486.76(24.15)$
Random Forest, $T=100$ | $13930.05(105.56)$ | $69.50(0.31)$ | $202.14(3.84)$
Random Forest, $T=200$ | $13907.25(64.86)$ | $69.64(0.24)$ | $365.03(0.09)$
Random Forest, $T=500$ | $13902.79(68.16)$ | $69.63(0.23)$ | $905.94(0.23)$
LiquidSVM | $10040.21(102.17)$ | $47.93(1.84)$ | $2201.74(5.89)$
GBRT, $T=100$ | $8214.59(0.00)$ | $60.18(0.00)$ | $820.83(15.58)$
GBRT, $T=200$ | $8192.71(0.00)$ | $60.15(0.000)$ | $1622.61(19.46)$

In Tables 2 and 3, we observe that our method with the optimal rotation
strategy can reach the comparable or even the best performance in many
moderate-sized and large-scale datasets. Here we take the rotation transform
as an option, where we can select the best strategy through validation in
practice. At a significance level of $0.05$, our method is significantly
different from other methods in most cases. This means that with the
combination of boosting and ensemble, we come to a conclusion that our method
shows promising performance compared to the efficient algorithms such as
boosting-based algorithm GBRT, forest-based algorithm Random Forest, and
kernel-based algorithm LiquidSVM.

Furthermore, Table 4, 5, and 6 record the MSE, MAE, and running time
performance of each method under different parameter settings on three large-
scale data sets MSD, GTM and DGM. It can be seen in the tables that our GBBHE
algorithm significantly outperforms other compared methods w.r.t. accuracy.
Yet the running time of our method, with rotation or not, is comparable among
other algorithms in large-scale circumstances. For example, on MSD, the
running time our GBBHE algorithm (w.o. Rotation) with $T=100$ and $K=100$ is
comparable with Random Forest ($T=500$) and GBRT ($T=100$). Nonetheless, the
MSE of our GBBHE (w.o. Rotation) is $1.37$ less than Random Forest ($T=500$)
and is $2.00$ less than GBRT ($T=100$). On the other hand, when compared with
GBRT, our method turns out to converge faster. For example, on the GTM
dataset, the MSE of our GBBHE (w.o. Rotation) drops by only $0.02$ when $T$
changes from $100$ to $200$, while the MAE is nearly the same, which indicates
convergence of our algorithm. By contrast, the MSE of GBRT decreases by a
large margin from $5.46$ to $4.80$ when $T$ changes from $100$ to $200$.
Besides, the MAE decreases from $1.45$ to $1.32$. Moreover, despite with
$T=200$, where more running time is consumed, GBRT still shows worse
performance than our GBBHE (w.o. Rotation). This exactly demonstrates the
faster convergence to a better performance of our algorithm.

##  5 Comments and Discussions

###  5.1 Comparisons with the Prior Work

In the prior work of this paper (Cai et al., 2020), we take ordinary histogram
transforms as the base learner in the gradient boosting algorithm and proposed
the Boosted Histogram Transform for Regression (BHTR). The convergence rate is
proved to be $n^{-2\alpha/(4\alpha+d)}$ in the space $C^{0,\alpha}$ and
$n^{-2(1+\alpha)/(2(1+\alpha)+d)}$ in the space $C^{1,\alpha}$. Moreover, a
lower bound of convergence rates for the base learner is proved to be
$n^{-2/(2+d)}$ which demonstrates the advantage of boosting. In this paper, we
take a step further to analyze the behavior of an algorithm that applies
better to the regression problem with large-scale and especially high-
dimensional data. To be specific, we introduce additional randomness to GBBH
by utilizing the rotated binary histogram as the base learner and manage to
derive fast convergence in the Hölder function space. Unfortunately, the GBBH
converges slightly slower than BHTR. However, it is worth pointing out that
the major shortcoming of ordinary histogram partition is that the number of
splits grows exponentially with dimension $d$. Thus, it is difficult for BHTR
to apply to high-dimensional data. Therefore, in this paper, we adopt the
binary histogram partition to deal with this problem, and further use the
ensemble method to improve the computational efficiency for large-scale
regression.

###  5.2 Comments on Theoretical Results

Previous theoretical works about boosting algorithms for regression include
Bühlmann and Yu (2003) and Lin et al. (2019), where linear regressors and
kernel ridge regressors are used as the base learners. These works analyze the
learning performance by using the integral operator approach and prove the
optimal convergence rate. However, this analysis turns out to be inapplicable
to our method. In this paper, we conduct analysis under the framework of
regularized empirical risk minimization (RERM).

Throughout the ensemble learning algorithms, perhaps the most related work to
ours is Biau (2012), where they investigate a random forest model with a
midpoint splitting rule which coincides with the construction procedure of our
binary histogram. The convergence rate of their proposed algorithm is proved
to be $n^{-0.75/(0.75+d\log 2)}$ in the space $C^{0,1}$. As for this paper,
the convergence rate of our GBBH when the target function lies in the space
$C^{0,1}$ turns out to be $n^{-0.75/(1.5+d\log 2)}$, slower than that of Biau
(2012)’s. However, for smoother functions in the subspace $C^{1,0}$, the
convergence rate of GBBH $n^{-1/(2+d\log 2)}$ is actually faster than that of
Biau (2012)’s when $d\geq 5$, which indicates that our GBBH can deal better
with smoother target functions.

###  5.3 Comments on Large-scale Regression

In the literature, there have been many efforts on solving the large-scale
regression problem. For example, the mainstream solutions fall into two
categories, the _horizontal methods_ and the _vertical methods_. The former
partitions the data set into several disjoint subsets, implements a certain
learning algorithm to each data subset to obtain a local predictor, and
finally synthesizes a global output. However, this approach suffers from its
own inherent disadvantages that the local predictor may be quite different
from the global optimal predictor. On the other hand, vertical methods divide
the feature space into multiple non-overlapping cells through different
partition methods, e.g. Suykens et al. (2002); Espinoza et al. (2006); Biau
(2012). Then a predictor is embedded on each partitioning cell, such as
Gaussian process regression (Park et al., 2011; Park and Huang, 2016; Park and
Apley, 2018), support vector machines (Meister and Steinwart, 2016; Thomann et
al., 2017), etc.

In this paper, our algorithm is inspired by the vertical methods. However, we
notice that previous vertical methods for large-scale regression usually adopt
kernel-based approaches to ensure sound theoretical properties and enhance the
performance, especially under high-dimensional scenarios. By contrast, instead
of resorting to kernel methods, we achieve comparable or even better
performance by combining two ensemble learning methods. Moreover, our
algorithm adopts the binary histogram partition, which enjoys high
computational efficiency compared with kernel methods even on high-dimensional
data. As is shown in Table 2 and 3, GBBHE enjoys the lowest testing error
measured by both MSE and MAE. Moreover, our GBBHE turns out to be more
computationally efficient than these kernel-based methods. For example, in
Table 4, 5, and 6, our method runs faster than the kernel-based LiquidSVM.

Previous works on boosting algorithms for solving large-scale regression often
adopt acceleration techniques mainly from the perspective of optimization. For
example, in Biau et al. (2019), the computational efficiency is enhanced by
incorporating an accelerated gradient descent technique. By contrast, our
GBBHE for the first time reduces the computational cost by accelerating the
convergence with respect to $T$, which is guaranteed by statistical learning
theory. To be specific, we show that in Theorem 16 to achieve the same
convergence rate, we require $T_{n}K_{n}$ (instead of $T_{n}$) to be of the
order $n^{1/(8+4d\log 2)}$. That is, we can enhance the computational
efficiency of our proposed gradient boosting algorithm through theoretically
proved reduction of the number of iterations $T$.

##  6 Error Analysis

This section provides more comprehensive error analysis for the theoretical
results in Section 3. In Subsection 6.1, we present some fundamental lemmas
and propositions for the properties of the binary histogram transform and the
sample error analysis. Then, in Subsections 6.2 and 6.3, we conduct
approximation error analysis for the boosted regressor $f_{\mathrm{D},B}$
under the assumption that the Bayes decision function $f^{*}_{L,\mathrm{P}}$
lies in the Hölder spaces $C^{0,\alpha}$ and $C^{1,0}$, respectively.

###  6.1 Fundamental Lemmas and Propositions

####  6.1.1 Properties of Binary Histogram Transform

Throughout the proof of this paper, we will make repeated use of the following
two facts proposed by Biau (2012).

###### Fact 20

For $x\in H^{-1}(B_{r})$, let $A_{p}(x)$ defined by (5) be the rectangular
cell of the rotated binary histogram containing $x$ and $S_{p}^{j}(x)$ be the
number of times that $A_{p}(x)$ is split on the $j$-th coordinate
($j=1,\ldots,d$) in the transformed space. Then conditionally on the rotation
transformation $H$, $S_{p}^{j}(x)$ has binomial distribution with parameters
$p$ and probability $1/d$ and satisfies

$\displaystyle\sum_{j=1}^{d}S^{j}_{p}(x)=p.$

Moreover, let $A_{p}^{j}(x)$ be the size of the $j$-th dimension of
$H(A_{p}(x))$ in the transformed space. Then we have

$\displaystyle A_{p}^{j}(x)|R\overset{\mathcal{D}}{=}2r\cdot
2^{-S_{p}^{j}(x)},$ (25)

where $\cdot|R$ denotes the probability distribution conditionally on the
rotation transformation $H(x)=R\cdot x$ and $\overset{\mathcal{D}}{=}$
indicates that variables in the two sides of the equation have the same
distribution.

###### Fact 21

Let $\mu$ be the Lebesgue measure. For $x\in H^{-1}(B_{r})$, let $N_{p}(x)$ be
the number of samples falling in the same cell as $x$, that is,

$\displaystyle N_{p}(x)=\sum_{i=1}^{n}\boldsymbol{1}_{\\{X_{i}\in
A_{p}(x)\\}}.$

By construction, we have

$\displaystyle\mu(A_{p}(x))=(2r)^{d}\cdot 2^{-p}.$ (26)

Before we proceed, we present the following lemma, which helps to bound the
diameter of the rectangular cell $A_{p}(x)$.

###### Lemma 22

Suppose that $x_{i}>0$, $1\leq i\leq d$ and $0<\alpha\leq 1$. Then we have

$\displaystyle\biggl{(}\sum^{d}_{i=1}x_{i}\biggr{)}^{\alpha}\leq\sum^{d}_{i=1}x_{i}^{\alpha}.$
(27)

Combining Lemma 22 with Fact 21, it is easy to derive the following lemma
which plays an important role to bound the approximation error of the
estimator.

###### Lemma 23

Let the diameter of the set $A\subset\mathbb{R}^{d}$ be defined by

$\displaystyle\mathrm{diam}(A):=\sup_{x,x^{\prime}\in A}\|x-x^{\prime}\|_{2}.$

Then for any $x\in\mathcal{X}$ and $0<\beta\leq 2$, there holds

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

For any $x\in B_{r}$, let $\underline{a}_{p}^{j}(x)$ and
$\overline{a}_{p}^{j}(x)$ be the minimum and maximum values of the $j$-th
entries of points in $H(A_{p}(x))$. Then, 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)].$

The next theorem gives an explicit form of the distance between $x_{i}$ and
the center of the interval
$[\underline{a}_{p}^{j}(x),\overline{a}_{p}^{j}(x)]$, which is used to derive
the lower bound for the error of single binary histogram regressor.

###### Lemma 24

Let the rotated binary histogram $A_{p}$ be defined as in Algorithm 1 with
identity map $H(x):=x$. Moreover, let $A_{p}(x)$ defined by (5) be the
rectangular cell containing $x$ and $S^{j}_{p}(x)$ be the number of times that
$A_{p}(x)$ is split on the $j$-th coordinate ($j=1,\ldots,d$) in the
transformed space. For any $x\in B_{r}$, let $x_{j}$ be the $j$-th entry of
$x$. If $S_{p}^{j}(x)=k$, $0\leq k\leq q$, then we have

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

where

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

####  6.1.2 Bounding the Sample Error Term

To derive bounds on the sample error of regularized empirical risk minimizers,
let us briefly recall the definition of VC dimension measuring the complexity
of the underlying function class.

######  Definition 25 (VC dimension)

Let $\mathcal{B}$ be a class of subsets of $\mathcal{X}$ and
$A\subset\mathcal{X}$ be a finite set. The trace of $\mathcal{B}$ on $A$ is
defined by $\\{B\cap A:B\subset\mathcal{B}\\}$. Its cardinality is denoted by
$\Delta^{\mathcal{B}}(A)$. We say that $\mathcal{B}$ shatters $A$ if
$\Delta^{\mathcal{B}}(A)=2^{\\#(A)}$, that is, if for every $\tilde{A}\subset
A$, there exists a $B\subset\mathcal{B}$ such that $\tilde{A}=B\cap A$. For
$k\in\mathrm{N}$, let

$\displaystyle
m^{\mathcal{B}}(k):=\sup_{A\subset\mathcal{X},\,\\#(A)=k}\Delta^{\mathcal{B}}(A).$
(28)

Then, the set $\mathcal{B}$ is a Vapnik-Chervonenkis class if there exists
$k<\infty$ such that $m^{\mathcal{B}}(k)<2^{k}$ and the minimal of such $k$ is
called the VC dimension of $\mathcal{B}$, and abbreviate as
$\mathrm{VC}(\mathcal{B})$.

To prove Lemma 26, we need the following fundamental lemma concerning with the
VC dimension of the tree-based partitions of $\mathbb{R}^{d}$ with $s$
internal nodes, that is, we use $s$ hyper-planes without intersections between
each other to split $\mathbb{R}^{d}$ into $s+1$ sub-regions. In fact, the
histogram transform partition $A_{p}$ proposed in Section 2.3 is a binary
tree-based partition with $s=2^{p}-1$ internal nodes. The key of the lemma 26
follows the idea put forward by Breiman (2000) of the construction of purely
random forest. To this end, let $s\in\mathbb{N}$ be fixed and
$\tilde{\pi}_{s}$ be a tree-based partition of $\mathbb{R}^{d}$ with $s$
internal nodes.

###### Lemma 26

Let $\mathcal{B}_{s}$ be defined by

$\displaystyle\mathcal{B}_{s}:=\biggl{\\{}B:B=\bigcup_{j\in
J}A_{j},J\subset\\{0,1,\ldots,s\\},A_{j}\in\tilde{\pi}_{s}\biggr{\\}}.$ (29)

Then the VC dimension of $\mathcal{B}_{s}$ can be upper bounded by $ds+2$.

To investigate the capacity property of continuous-valued functions, we need
to introduce the concept VC-subgraph class. To this end, the _subgraph_ of a
function $f:\mathcal{X}\to\mathbb{R}$ is defined by

$\displaystyle\textit{sg}(f):=\\{(x,t):t<f(x)\\}.$

A class $\mathcal{F}$ of functions on $\mathcal{X}$ is said to be a VC-
subgraph class, if the collection of all subgraphs of functions in
$\mathcal{F}$, which is denoted by
$\textit{sg}(\mathcal{F}):=\\{\textit{sg}(f):f\in\mathcal{F}\\}$ is a VC class
of sets in $\mathcal{X}\times\mathbb{R}$. Then the VC dimension of
$\mathcal{F}$ is defined by the VC dimension of the collection of the
subgraphs, that is,
$\mathrm{VC}(\mathcal{F})=\mathrm{VC}(\textit{sg}(\mathcal{F}))$.

Before we proceed, we also need to recall the definitions of the convex hull
and VC-hull class. The symmetric convex hull $\mathrm{Co}(\mathcal{F})$ of a
class of functions $\mathcal{F}$ is defined as the set of functions
$\sum_{i=1}^{m}\alpha_{i}f_{i}$ with $\sum_{i=1}^{m}|\alpha_{i}|\leq 1$ and
each $f_{i}$ contained in $\mathcal{F}$. A set of measurable functions is
called a VC-hull class, if it is in the pointwise sequential closure of the
symmetric convex hull of a VC-class of functions.

We denote the function set $\mathcal{F}$ as

$\displaystyle\mathcal{F}:=\bigcup_{p\in\mathbb{N}_{+},R\sim\mathrm{P}_{R}}\mathcal{F}_{p},$
(30)

which contains all the functions of $\mathcal{F}_{p}$ induced by all possible
rotation transformations $R$ with the size parameter $p$. The following lemma
presents the upper bound for the VC dimension of the function set
$\mathcal{F}$.

###### Lemma 27

Let $\mathcal{F}$ be the function set defined as in (30). Then $\mathcal{F}$
is a $\mathrm{VC}$-subgraph class with

$\displaystyle\mathrm{VC}(\mathcal{F})\leq d\cdot 2^{p+1}.$

To further bound the capacity of the function sets, we need to introduce the
following fundamental descriptions which enables an approximation of an
infinite set by finite subsets.

######  Definition 28 (Covering Numbers)

Let $(\mathcal{X},d)$ be a metric space, $A\subset\mathcal{X}$ and
$\varepsilon>0$. We call $A^{\prime}\subset A$ an $\varepsilon$-net of $A$ if
for all $x\in A$ there exists an $x^{\prime}\in A^{\prime}$ such that
$d(x,x^{\prime})\leq\varepsilon$. Moreover, the $\varepsilon$-covering number
of $A$ is defined as

$\displaystyle\mathcal{N}(A,d,\varepsilon)$
$\displaystyle=\inf\biggl{\\{}n\geq 1:\exists
x_{1},\ldots,x_{n}\in\mathcal{X}\text{ such that
}A\subset\bigcup_{i=1}^{n}B_{d}(x_{i},\varepsilon)\biggr{\\}},$

where $B_{d}(x,\varepsilon)$ denotes the closed ball in $\mathcal{X}$ centered
at $x$ with radius $\varepsilon$.

The following lemma follows directly from Theorem 2.6.9 in Van der Vaart and
Wellner (1996). For the sake of completeness, we present the proof in Section
7.1.2.

###### Lemma 29

Let $\mathrm{Q}$ be a probability measure on $\mathcal{X}$ and

$\displaystyle\mathcal{F}:=\bigl{\\{}f:\mathcal{X}\to\mathbb{R}:f\in[-M,M]\bigr{\\}}.$

Assume that for some fixed $\varepsilon>0$ and $v>0$, the covering number of
$\mathcal{F}$ satisfies

$\displaystyle\mathcal{N}(\mathcal{F},L_{2}(\mathrm{Q}),M\varepsilon)\leq
c\,(1/\varepsilon)^{v}.$ (31)

Then there exists a universal constant $c^{\prime}$ such that

$\displaystyle\log\mathcal{N}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{Q}),M\varepsilon)\leq
c^{\prime}c^{2/(v+2)}\varepsilon^{-2v/(v+2)}.$

The next theorem shows that covering numbers of $\mathcal{F}$ grow at a
polynomial rate.

###### Proposition 30

Let $\mathcal{F}$ be a function set defined as in (30). Then there exists a
universal constant $c_{0}<\infty$ such that for any $\varepsilon\in(0,1)$ and
any probability measure $\mathrm{Q}$, we have

$\displaystyle\mathcal{N}(\mathcal{F},L_{2}(\mathrm{Q}),M\varepsilon)\leq
c_{0}d\cdot 2^{p+1}(16e)^{d\cdot 2^{p+1}}\varepsilon^{2-d\cdot 2^{p+2}}.$

The following theorem gives an upper bound on the covering number of the
$\mathrm{VC}$-hull class $\mathrm{Co}(\mathcal{F})$.

###### Proposition 31

Let $\mathcal{F}$ be the function set defined as in (30). Then there exists a
constant $c_{1}$ such that for any $\varepsilon\in(0,1)$ and any probability
measure $\mathrm{Q}$, there holds

$\displaystyle\log\mathcal{N}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{Q}),M\varepsilon)\leq
c_{1}2^{p/2}\cdot\varepsilon^{1/(d\cdot 2^{p})-2}.$ (32)

Next, let us recall the definition of entropy numbers.

######  Definition 32 (Entropy Numbers)

Let $(\mathcal{X},d)$ be a metric space, $A\subset\mathcal{X}$ and $m\geq 1$
be an integer. The $m$-th entropy number of $(A,d)$ is defined as

$\displaystyle e_{m}(A,d)=\inf\biggl{\\{}\varepsilon>0:\exists
x_{1},\ldots,x_{2^{m-1}}\in\mathcal{X}\text{ such that
}A\subset\bigcup_{i=1}^{2^{m-1}}B_{d}(x_{i},\varepsilon)\biggr{\\}}.$

Moreover, if $(A,d)$ is a subspace of a normed space $(E,\|\cdot\|)$ and the
metric $d$ is given by $d(x,x^{\prime})=\|x-x^{\prime}\|$, $x,x^{\prime}\in
A$, we write $e_{m}(A,\|\cdot\|):=e_{m}(A,E):=e_{m}(A,d)$. Finally, if $S:E\to
F$ is a bounded, linear operator between the normed space $E$ and $F$, we
denote $e_{m}(S):=e_{m}(SB_{E},\|\cdot\|_{F})$.

It is well-known that entropy numbers are closely related to the covering
numbers. To be specific, entropy and covering numbers are in some sense
inverse to each other. More precisely, for all constants $a>0$ and $q>0$, the
implication

$\displaystyle e_{i}(T,d)\leq ai^{-1/q},\quad\forall\,i\geq
1\quad\Longrightarrow\quad\ln\mathcal{N}(T,d,\varepsilon)\leq\ln(4)(a/\varepsilon)^{q},\quad\forall\,\varepsilon>0$
(33)

holds by Lemma 6.21 in Steinwart and Christmann (2008). Additionally, Exercise
6.8 in Steinwart and Christmann (2008) yields the opposite implication, namely

$\displaystyle\ln\mathcal{N}(T,d,\varepsilon)<(a/\varepsilon)^{q},\quad\forall\,\varepsilon>0\quad\Longrightarrow\quad
e_{i}(T,d)\leq 3^{1/q}ai^{-1/q},\quad\forall\,i\geq 1.$ (34)

For a finite set $D\in\mathcal{X}^{n}$, we define the norm of an empirical
$L_{2}$-space by

$\displaystyle\|f\|^{2}_{L_{2}(\mathrm{D})}=\mathbb{E}_{\mathrm{D}}|f|^{2}:=\frac{1}{n}\sum_{i=1}^{n}|f(x_{i})^{2}|.$

If $E$ is the function space (8) and $\mathrm{D}\in\mathcal{X}^{n}$, then the
entropy number $e_{m}(\mathrm{id}:E\to L_{2}(\mathrm{D}_{X}))$ equals the
$m$-th entropy number of the symmetric convex hull of the family
$\\{(f_{i}),f_{i}\in\mathcal{F}_{i}\\}$, where $\mathrm{id}:E\to
L_{2}(\mathrm{D}_{X})$ denotes the identity map that assigns to every $f\in E$
the corresponding equivalence class in $L_{2}(\mathrm{D}_{X})$.

###  6.2 Error Analysis for $f^{*}_{L,\mathrm{P}}\in C^{0,\alpha}$

First of all, we introduce some definitions and notations. For a given rotated
binary histogram $H$ and split coordinates $Z$, we write

$\displaystyle
f_{\mathrm{P}}^{p}:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}^{p}}\mathcal{R}_{L,\mathrm{P}}(f).$
(35)

In other words, $f_{\mathrm{P}}^{p}$ is the function that minimizes the excess
risk $\mathcal{R}_{L,\mathrm{P}}(f)$ over the function set $\mathcal{F}_{p}$.
Then, elementary calculation yields

$\displaystyle
f_{\mathrm{P}}^{p}=\mathbb{E}_{\mathrm{P}}(f_{L,\mathrm{P}}^{*}(X)|A_{p}(x))=\sum_{j\in\mathcal{I}_{p}}\frac{\int_{A_{j}}f_{L,\mathrm{P}}^{*}\,d\mathrm{P}_{X}}{\mathrm{P}_{X}(x\in
A_{j})}\cdot\boldsymbol{1}_{A_{j}}=\sum_{j\in\mathcal{I}_{p}}\frac{\int_{A_{j}}\mathbb{E}(Y|X)\,d\mathrm{P}_{X}}{\mathrm{P}_{X}(x\in
A_{j})}\cdot\boldsymbol{1}_{A_{j}}.$

Moreover, we write

$\displaystyle
f_{\mathrm{D}}^{p}:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}^{p}}\mathcal{R}_{L,\mathrm{D}}(f)$
(36)

for the empirical version, which can be further presented as

$\displaystyle
f_{\mathrm{D}}^{p}=\sum_{j\in\mathcal{I}_{p}}\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}}.$

The following proposition shows that the $L_{2}$ distance between
$f_{\mathrm{P}}^{p}$ and $f^{*}_{L,\mathrm{P}}$ behaves polynomial in the
regularization parameter $\lambda$ if we choose the size of binary histogram
partition $p$ appropriately.

###### Proposition 33

Let the rotated binary histogram $A_{p}$ be defined in Algorithm 1 with depth
$p$. Moreover, suppose that the Bayes decision function
$f^{*}_{L,\mathrm{P}}\in C^{0,\alpha}$. Then, for any fixed $\lambda>0$, there
holds

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

where $c$ is some constant depending on $\alpha$, $d$ and $r$.

####  6.2.1 Upper Bound of Convergence Rate of GBBH

###### Theorem 34

Let the rotated binary histogram $A_{p}$ be defined as in Algorithm 1 with
depth $p$. Furthermore, let $f_{\mathrm{D},B}$ be the GBBH regressor defined
by (10) and $A(\lambda)$ be the corresponding approximation error defined by
(12). Then for all $\tau>0$, with probability
$\mathrm{P}^{n}\otimes\mathrm{P}_{R,Z}$ not less than $1-3e^{-\tau}$, we have

$\displaystyle\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\leq
12A(\lambda)+3456M^{2}\tau/n+3c_{0}^{\prime}T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2},$

where $c_{0}^{\prime}$ is a constant, $\delta=1/(d\cdot 2^{p})$ and
$\delta^{\prime}=1-\delta$.

####  6.2.2 Upper Bound of Convergence Rate of GBBHE

###### Theorem 35

Let the rotated binary histogram $A_{p}$ be defined as in Algorithm 1 with
depth $p$. Furthermore, let $\bar{f}_{\mathrm{D},B}$ be the GBBHE regressor
defined by (18) and $\bar{A}(\lambda)$ be the corresponding approximation
error defined by (20). Then for all $\tau>0$, with probability
$\mathrm{P}^{n}\otimes\mathrm{P}_{R,Z}$ not less than $1-3e^{-\tau}$, we have

$\displaystyle\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(\bar{f}_{\mathrm{D},B})-\mathcal{R}_{L,\mathrm{P}}^{*}\leq
12\bar{A}(\lambda)+3456M^{2}\tau/n+3c_{0}^{\prime}T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2},$

where $c_{0}^{\prime}$ is a constant, $\delta=1/(d\cdot 2^{p})$ and
$\delta^{\prime}=1-\delta$.

###  6.3 Error Analysis for $f^{*}_{L,\mathrm{P}}\in C^{1,0}$

A drawback to the analysis in $C^{0,\alpha}$ is that the usual Taylor
expansion involved techniques for error estimation may not apply directly. As
a result, we fail to prove the exact benefits of the boosting procedure.
Therefore, in this subsection, we turn to the function space $C^{1,0}$
consisting of smoother functions. To be specific, we study the convergence
rates of $f_{\mathrm{D},B}$ to the Bayes decision function
$f_{L,\mathrm{P}}^{*}\in C^{1,0}$. To this end, there is a point in
introducing some notations.

For fixed $p\in\mathbb{N}_{+}$, let $\\{A_{p,t}\\}_{t=1}^{T}$ be rotated
binary histograms with depth $p$ and split coordinates $Z_{t}$,
$t=1,\ldots,T$. Moreover, let $\\{f_{\mathrm{P}}^{p,t}\\}_{t=1}^{T}$ and
$\\{f_{\mathrm{D}}^{p,t}\\}_{t=1}^{T}$ be defined as in (35) and (36),
respectively. For $x\in\mathcal{X}$, we define

$\displaystyle
f_{\mathrm{P},\mathrm{E}}(x):=\frac{1}{T}\sum_{t=1}^{T}f_{\mathrm{P}}^{p,t}(x)$
(37)

and

$\displaystyle
f_{\mathrm{D},\mathrm{E}}(x):=\frac{1}{T}\sum_{t=1}^{T}f_{\mathrm{D}}^{p,t}(x).$
(38)

Moreover, in the scenario of gradient boosted binary histogram ensemble for
large-scale regression, we write

$\displaystyle
f_{\mathrm{P}}^{p,t,k}:=\operatornamewithlimits{arg\,min}_{f\in\mathcal{F}_{t}^{k}}\mathrm{R}_{L,\mathrm{P}}(f).$
(39)

Furthermore, we define

$\displaystyle\bar{f}_{\mathrm{P}}^{p,t}:=\frac{1}{K}\sum_{k=1}^{K}f_{\mathrm{P}}^{p,t,k},$
(40)

and

$\displaystyle\bar{f}_{\mathrm{P},\mathrm{E}}:=\frac{1}{T}\sum^{T}_{t=1}\bar{f}_{\mathrm{P}}^{p,t}.$
(41)

In particular, for the binary histogram regressor, we are concerned with the
lower bound for $f_{\mathrm{D}}^{p}$. In this case, we suppose that
$\mathrm{P}_{X}$ is the uniform distribution on $B_{r}:=[-r,r]^{d}$. As a
result, it is sufficient for us to consider the fixed transformation $H(x)=x$
to apply binary histogram partition on $B_{r}$. Consequently, we make the
error decomposition

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}}^{p})-\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}}^{p}(X)-f^{*}_{L,\mathrm{P}}(X)\bigr{)}^{2}$
$\displaystyle=\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}\bigl{(}f_{\mathrm{D}}^{p}(X)-f_{\mathrm{P}}^{p}(X)\bigr{)}^{2}$
$\displaystyle\phantom{=}+\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\mathbb{E}_{\mathrm{P}_{X}}\bigl{(}f_{\mathrm{P}}^{p}(X)-f_{L,\mathrm{P}}^{*}(X)\bigr{)}^{2}.$
(42)

It is important to note that both of the two terms on the right-hand side of
(42) are data- and partition-independent due to the expectation with respect
to $\mathrm{P}^{n}$ and $\mathrm{P}_{Z}$ respectively. Loosely speaking, the
first error term corresponds to the expected estimation error of the estimator
$f_{\mathrm{D}}^{p}$, while the second one demonstrates the expected
approximation error.

####  6.3.1 Upper Bound of Convergence Rate of GBBH

The next proposition presents the upper bound of the $L_{2}$ distance between
the boosted regressor $f_{\mathrm{P},\mathrm{E}}$ and the Bayes decision
function $f_{L,\mathrm{P}}^{*}$ in the Hölder space $C^{1,0}$.

###### Proposition 36

Let $f_{\mathrm{P},\mathrm{E}}$ be defined by (37). Moreover, let the Bayes
decision function $f_{L,\mathrm{P}}^{*}\in C^{1,0}$ and $\mathrm{P}_{X}$ be
the uniform distribution on $B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Then we
have

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P},\mathrm{E}})-\mathcal{R}^{*}_{L,\mathrm{P}}\bigr{)}\leq\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{)}.$
(43)

####  6.3.2 Upper Bound of Convergence Rate of GBBHE

The next proposition presents the upper bound of the $L_{2}$ distance between
the boosted rotated binary histogram ensemble
$\bar{f}_{\mathrm{P},\mathrm{E}}$ and the Bayes decision function
$f_{L,\mathrm{P}}^{*}$ in the Hölder space $C^{1,0}$.

###### Proposition 37

Let $\bar{f}_{\mathrm{P},\mathrm{E}}$ be defined by (41). Moreover, let the
Bayes decision function $f_{L,\mathrm{P}}^{*}\in C^{1,0}$ and $\mathrm{P}_{X}$
be the uniform distribution on $B_{r,d}=[-r/\sqrt{d},r/\sqrt{d}]^{d}$. Then we
have

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

####  6.3.3 Lower Bound of Convergence Rate of Binary Histogram Regression

The following two propositions present the lower bound of approximation error
and sample error of GBBH Regression, respectively.

###### Proposition 38

Let the rotated binary histogram $A_{p}$ be defined as in Algorithm 1 with the
identity map $H(x)=x$ and the regression model be defined by

$\displaystyle Y:=f(X)+\varepsilon$ (45)

with $f\in C^{1,0}$. Furthermore, suppose that $\mathrm{P}_{X}$ is the uniform
distribution on $B_{r}=[-r,r]^{d}$ and $\varepsilon$ is independent of $X$
such that $\mathbb{E}(\varepsilon)=0$. Moreover, suppose that there exists a
fixed constant $\underline{c}_{f}\in(0,\infty)$ such that

$\displaystyle\|\nabla f\|\geq\underline{c}_{f}.$ (46)

Then we have

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

###### Proposition 39

Let the rotated binary histogram $A_{p}$ be defined as in Algorithm 1 with the
identity map $H(x)=x$. Furthermore, let the regression model be defined as in
(45) such that $f\in C^{1,0}$ and $\|f(x)\|_{\infty}\geq\underline{c}_{f}>0$.
Moreover, suppose that $\mathrm{P}_{X}$ is the uniform distribution on
$B_{r}=[-r,r]^{d}$ and $\varepsilon$ is independent of $X$ such that
$\mathbb{E}(\varepsilon)=0$ and $\mathrm{Var}(\varepsilon)=:\sigma^{2}\leq
4M^{2}$. Then we have

$\displaystyle\mathbb{E}_{\mathrm{P}^{n}\otimes\mathrm{P}_{Z}}\bigl{(}\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{D}}^{p})-\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p})\bigr{)}\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}.$

##  7 Proofs

###  7.1 Proofs Related to Section 6.1

####  7.1.1 Proofs Related to Section 6.1.1

Proof [of Lemma 22] For any $1\leq i\leq n$, it is easy to see that

$\displaystyle 0<\frac{x_{i}}{\sum^{d}_{i=1}x_{i}}<1.$

Since $0<\alpha\leq 1$, we have

$\displaystyle\frac{\sum^{d}_{i=1}x_{i}^{\alpha}}{(\sum^{d}_{i=1}x_{i})^{\alpha}}=\sum^{d}_{i=1}\biggl{(}\frac{x_{i}}{\sum^{d}_{i=1}x_{i}}\biggr{)}^{\alpha}\geq\sum^{d}_{i=1}\frac{x_{i}}{\sum^{d}_{i=1}x_{i}}=\frac{\sum^{d}_{i=1}x_{i}}{\sum^{d}_{i=1}x_{i}}=1.$

Consequently, we get

$\displaystyle\biggl{(}\sum_{i=1}^{d}x_{i}\biggr{)}^{\alpha}\leq\sum_{i=1}^{d}x_{i}^{\alpha}.$

Thus we complete the proof.

Proof [of Lemma 23] By definition, we have

$\displaystyle\mathrm{diam}(A_{p}(x)):=\biggl{(}\sum_{j=1}^{d}A_{p}^{j}(x)^{2}\biggr{)}^{1/2}.$

Consequently, (25) in Fact 20 implies

$\displaystyle\mathrm{diam}(A_{p}(x))^{\beta}=(2r)^{\beta}\biggl{(}\sum^{d}_{j=1}2^{-2S_{p}^{j}(x)}\biggr{)}^{\beta/2}.$

Applying Lemma 22, we get

$\displaystyle\mathrm{diam}(A_{p}(x))^{\beta}\leq(2r)^{\beta}\sum^{d}_{j=1}2^{-\beta
S_{p}^{j}(x)}.$

Therefore, we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{Z}}\bigl{(}\mathrm{diam}(A_{p}(x))^{\beta}\big{|}R\bigr{)}$
$\displaystyle\leq\mathbb{E}_{\mathrm{P}_{Z}}\biggl{(}(2r)^{\beta}\sum^{d}_{j=1}2^{-\beta
S_{p}^{j}(x)}\bigg{|}R\biggr{)}=(2r)^{\beta}\sum^{d}_{j=1}\mathbb{E}_{\mathrm{P}_{Z}}\biggl{(}2^{-\beta
S_{p}^{j}(x)}\bigg{|}R\biggr{)}$
$\displaystyle=(2r)^{\beta}d\biggl{(}1-\frac{1-2^{-\beta}}{d}\biggr{)}^{p}\leq(2r)^{2\alpha}d\exp\biggl{(}\frac{(2^{-\beta}-1)p}{d}\biggr{)}.$

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

Proof [of Lemma 24] If $S_{p}^{j}(x)=k$, by the construction of rotated binary
histogram partition, we have

$\displaystyle\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\in
Q_{k}.$ (47)

By the definition of $Q_{k}$, for any $q^{*}\in Q_{k}$, there holds

$\displaystyle\biggl{|}q^{*}-\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\biggr{|}\geq\frac{r}{2^{k-1}}.$

Since $x\in A_{p}(x)$, we have

$\displaystyle\biggl{|}x_{j}-\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\biggr{|}\leq\frac{r}{2^{k}}.$
(48)

Therefore, using the triangular inequality, we obtain

$\displaystyle|x_{j}-q^{*}|\geq\Biggl{|}\biggl{|}x_{j}-\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\biggr{|}-\biggl{|}q^{*}-\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\biggr{|}\Biggr{|}\geq\frac{r}{2^{k}}.$

This together with (48) implies that

$\displaystyle|x_{j}-q^{*}|\geq\biggl{|}x_{j}-\frac{\underline{a}_{p}^{j}(x)+\overline{a}_{p}^{j}(x)}{2}\biggr{|}$

holds for any $q^{*}\in Q_{k}$. Combining this with (47), we get

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

which leads to the desired assertion.

####  7.1.2 Proofs Related to Section 6.1.2

Proof [of Lemma 26] This proof is conducted from the perspective of geometric
constructions.

$p=1$

$p=2$

$p=2k$

Figure 9: We take one case with $d=3$ as an example to illustrate the
geometric interpretation of the VC dimension. The yellow balls represent
samples from class $A$, blue ones are from class $B$ and slices denote the
hyper-planes formed by samples.

We proceed by induction. Firstly, we concentrate on partition with the number
of splits $s=1$. Because of the dimension of the feature space is $d$, the
smallest number of sample points that cannot be divided by $s=1$ split is
$d+2$. Concretely, owing to the fact that $d$ points can be used to form $d-1$
independent vectors and hence a hyperplane in a $d$-dimensional space, we
might take the following case into consideration: There is a hyperplane
consisting of $d$ points all from one class, say class $A$, and two points
$s_{1}^{B}$, $s_{2}^{B}$ from the opposite class $B$ located on the opposite
sides of this hyperplane, respectively. We denote this hyperplane by
$H_{1}^{A}$. In this case, points from two classes cannot be separated by one
split (since the positions are $s_{1}^{B},H_{1}^{A},s_{2}^{B}$), so that we
have $\mathrm{VC}(\mathcal{B}_{1})\leq d+2$.

Next, when the partition is with the number of splits $s=2$, we analyze in the
similar way only by extending the above case a little bit. Now, we pick either
of the two single sample points located on opposite side of the $H_{1}^{A}$,
and add $d-1$ more points from class $B$ to it. Then, they together can form a
hyperplane $H_{2}^{B}$ parallel to $H_{1}^{A}$. After that, we place one more
sample point from class $A$ to the side of this newly constructed hyperplane
$H_{2}^{B}$. In this case, the location of these two single points and two
hyperplanes are $s_{1}^{B},H_{1}^{A},H_{2}^{B},s_{2}^{A}$. Apparently, $s=2$
splits cannot separate these $2d+2$ points. As a result, we have
$\mathrm{VC}(\mathcal{B}_{2})\leq 2d+2$.

Inductively, the above analysis can be extended to the general case of number
of splits $s\in\mathbb{N}$. In this manner, we need to add points continuously
to form $s$ mutually parallel hyperplanes where any two adjacent hyperplanes
should be constructed from different classes. Without loss of generality, we
consider the case for $s=2k+1$, $k\in\mathbb{N}$, where two points (denoted as
$s_{1}^{B}$, $s_{2}^{B}$) from class $B$ and $2k+1$ alternately appearing
hyperplanes form the space locations:
$s_{1}^{B},H_{1}^{A},H_{2}^{B},H_{3}^{A},H_{4}^{B},\ldots,H_{(2k+1)}^{A},s_{2}^{B}$.
Accordingly, the smallest number of points that cannot be divided by $s$
splits is $ds+2$, leading to $\mathrm{VC}(\mathcal{B}_{s})\leq ds+2$. This
completes the proof.

Proof [of Lemma 27] Recall that for an histogram transform splitting rule, we
construct the binary tree-based partition on the hypercube $[-r,r]^{d}$ with
depth $p$, which leads to $s=2^{p}-1$ internal nodes of the partition.
Consequently, applying lemma 26, we get

$\displaystyle\mathrm{VC}(\mathcal{F})\leq d(2^{p}-1)+2\leq d\cdot 2^{p+1}.$

Thus we complete the proof.

Proof [of Lemma 29] Let $\mathcal{F}_{\varepsilon}$ be an $\varepsilon$-net
over $\mathcal{F}$. Then, for any $f\in\mathrm{Co}(\mathcal{F})$, there exists
an $f_{\varepsilon}\in\mathrm{Co}(\mathcal{F}_{\varepsilon})$ such that
$\|f-f_{\varepsilon}\|_{L_{2}(\mathrm{Q})}\leq\varepsilon$. Therefore, we can
assume without loss of generality that $\mathcal{F}$ is finite.

Obviously, (31) holds for $1\leq\varepsilon\leq c^{1/v}$. Let
$v^{\prime}:=1/2+1/v$ and $M^{\prime}:=c^{1/v}M$. Then (31) implies that for
any $n\in\mathbb{N}$, there exists $f_{1},\ldots,f_{n}\in\mathcal{F}$ such
that for any $f\in\mathcal{F}$, there exists an $f_{i}$ such that

$\displaystyle\|f-f_{i}\|_{L_{2}(\mathrm{Q})}\leq M^{\prime}n^{-1/v}.$

Therefore, for each $n\in\mathbb{N}$, we can find sets
$\mathcal{F}_{1}\subset\mathcal{F}_{2}\subset\cdots\subset\mathcal{F}$ such
that the set $\mathcal{F}_{n}$ is a $M^{\prime}n^{-1/v}$-net over
$\mathcal{F}$ and $\\#(\mathcal{F}_{n})\leq n$.

In the following, we show by induction that for $q=7v/2$ and $n,k\geq 1$,
there holds

$\displaystyle\log\mathcal{N}\bigl{(}\mathrm{Co}(\mathcal{F}_{nk^{q}}),L_{2}(\mathrm{Q}),c_{k}M^{\prime}n^{-v^{\prime}}\bigr{)}\leq
c^{\prime}_{k}n,$ (49)

where $c_{k}$ and $c^{\prime}_{k}$ are constants depending only on $c$ and $v$
such that $\sup_{k}\max\\{c_{k},c^{\prime}_{k}\\}<\infty$. The proof of (49)
will be conducted by a nested induction argument.

Let us first consider the case $k=1$. For a fixed $n_{0}$, let $n\leq n_{0}$.
Then for $c_{1}$ satisfying $c_{1}M^{\prime}n_{0}^{-v^{\prime}}\geq M$, there
holds

$\displaystyle\log\mathcal{N}\bigl{(}\mathrm{Co}(\mathcal{F}_{nk^{q}}),L_{2}(\mathrm{Q}),c_{k}M^{\prime}n^{-v^{\prime}}\bigr{)}=0,$

which immediately implies (49). For a general $n\in\mathbb{N}$, let
$m:=n/\ell$ for large enough $\ell$ to be chosen later. Then for any
$f\in\mathcal{F}_{n}\setminus\mathcal{F}_{m}$, there exists an
$f^{(m)}\in\mathcal{F}_{m}$ such that

$\displaystyle\|f-f^{(m)}\|_{L_{2}(\mathrm{Q})}\leq M^{\prime}m^{-1/v}.$

Let $\pi_{m}:\mathcal{F}_{n}\setminus\mathcal{F}_{m}\to\mathcal{F}_{m}$ be the
projection operator. Then for any
$f\in\mathcal{F}_{n}\setminus\mathcal{F}_{m}$, there holds

$\displaystyle\|f-\pi_{m}f\|_{L_{2}(\mathrm{Q})}\leq M^{\prime}m^{-1/v}$

Therefore, for $\lambda_{i},\mu_{j}\geq 0$ and
$\sum_{i=1}^{n}\lambda_{i}=\sum_{j=1}^{m}\mu_{j}=1$, we have

$\displaystyle\sum_{i=1}^{n}\lambda_{i}f^{(n)}_{i}=\sum_{j=1}^{m}\mu_{j}f^{(m)}_{j}+\sum_{k=m+1}^{n}\lambda_{k}\bigl{(}f^{(n)}_{k}-\pi_{m}f^{(n)}_{k}\bigr{)}.$

Let $\mathcal{G}_{n}$ be the set

$\displaystyle\mathcal{G}_{n}:=\\{0\\}\cup\\{f-\pi_{m}f:f\in\mathcal{F}_{n}\setminus\mathcal{F}_{m}\\}.$

Then we have $\\#(\mathcal{G}_{n})\leq n$ and for any $g\in\mathcal{G}_{n}$,
there holds

$\displaystyle\|g\|_{L_{2}(\mathrm{Q})}\leq M^{\prime}m^{-1/v}.$

Moreover, we have

$\displaystyle\mathrm{Co}(\mathcal{F}_{n})\subset\mathrm{Co}(\mathcal{F}_{m})+\mathrm{Co}(\mathcal{G}_{n}).$
(50)

Applying Lemma 2.6.11 in Van der Vaart and Wellner (1996) with
$\varepsilon:=\frac{1}{2}c_{1}m^{1/v}n^{-v^{\prime}}$ to $\mathcal{G}_{n}$, we
can find a $\frac{1}{2}c_{1}M^{\prime}n^{-v^{\prime}}$-net over
$\mathrm{Co}(\mathcal{G}_{n})$ consisting of at most

$\displaystyle(e+en\varepsilon^{2})^{2/\varepsilon^{2}}\leq\biggl{(}e+\frac{ec_{1}^{2}}{\ell^{2/v}}\biggr{)}^{8\ell^{2/v}c_{1}^{-2}n}$
(51)

elements.

Suppose that (49) holds for $k=1$ and $n=m$. In other words, there exists a
$c_{1}M^{\prime}m^{-v^{\prime}}$-net over $\mathrm{Co}(\mathcal{F}_{m})$
consisting of at most $e^{m}$ elements, which partitions
$\mathrm{Co}(\mathcal{F}_{m})$ into $m$-dimensional cells of diameter at most
$2c_{1}M^{\prime}m^{-v^{\prime}}$. Each of these cells can be isometrically
identified with a subset of a ball of radius $c_{1}M^{\prime}m^{-v^{\prime}}$
in $\mathbb{R}^{m}$ and can be therefore further partitioned into

$\displaystyle\bigg{(}\frac{3c_{1}M^{\prime}m^{-v^{\prime}}}{\frac{1}{2}c_{1}M^{\prime}n^{-v^{\prime}}}\bigg{)}^{m}=(6\ell^{v^{\prime}})^{n/\ell}$

cells of diameter $\frac{1}{2}c_{1}M^{\prime}n^{-v^{\prime}}$. As a result, we
get a $\frac{1}{2}c_{1}M^{\prime}n^{-v^{\prime}}$-net of
$\mathrm{Co}(\mathcal{F}_{m})$ containing at most

$\displaystyle e^{m}\cdot(6\ell^{v^{\prime}})^{n/\ell}$ (52)

elements.

Now, (50) together with (51) and (52) yields that there exists a
$c_{1}M^{\prime}n^{-v^{\prime}}$-net of $\mathrm{Co}(\mathcal{F}_{n})$ whose
cardinality can be bounded by

$\displaystyle
e^{n/\ell}\bigl{(}6\ell^{v^{\prime}}\bigr{)}^{n/\ell}\biggl{(}e+\frac{ec_{1}^{2}}{\ell^{2/v}}\biggr{)}^{8\ell^{2/v}c_{1}^{-2}n}\leq
e^{n},$

for suitable choices of $c_{1}$ and $\ell$ depending only on $v$. This
concludes the proof of (49) for $k=1$ and every $n\in\mathbb{N}$.

Let us consider a general $k\in\mathbb{N}$. Similarly as above, there holds

$\displaystyle\mathrm{Co}(\mathcal{F}_{nk^{q}})\subset\mathrm{Co}(\mathcal{F}_{n(k-1)^{q}})+\mathrm{Co}(\mathcal{G}_{n,k}),$
(53)

where the set $\mathcal{G}_{n,k}$ contains at most $nk^{q}$ elements with norm
smaller than $M^{\prime}(n(k-1)^{q})^{-1/v}$. Applying Lemma 2.6.11 in Van der
Vaart and Wellner (1996) to $\mathcal{G}_{n,k}$, we can find an
$M^{\prime}k^{-2}n^{-v^{\prime}}$-net over $\mathrm{Co}(\mathcal{G}_{n,k})$
consisting of at most

$\displaystyle\bigl{(}e+ek^{2q/v-4+q}\bigr{)}^{2^{2q/v+1}k^{4-2q/v}n}$ (54)

elements. Moreover, by the induction hypothesis, we have a
$c_{k-1}M^{\prime}n^{-v^{\prime}}$-net over
$\mathrm{Co}(\mathcal{F}_{n(k-1)^{q}})$ consisting of at most

$\displaystyle e^{c^{\prime}_{k-1}n}$ (55)

elements. Using (53), (54), and (55), we obtain a
$c_{k}M^{\prime}n^{-v^{\prime}}$-net over $\mathrm{Co}(\mathcal{F}_{nk^{q}})$
consisting of at most $e^{c^{\prime}_{k}n}$ elements, where

$\displaystyle c_{k}$ $\displaystyle=c_{k-1}+\frac{1}{k^{2}},$ $\displaystyle
c^{\prime}_{k}$
$\displaystyle=c^{\prime}_{k-1}+2^{2q/v+1}\frac{1+\log(1+k^{2q/v-4+q})}{k^{2q/v-4}}.$

Form the elementary analysis we know that if $2q/v-5=2$, then there exist
constants $c^{\prime\prime}_{1}$, $c^{\prime\prime}_{2}$, and
$c^{\prime\prime}_{3}$ such that

$\displaystyle\lim_{k\to\infty}c_{k}$
$\displaystyle=c^{-1/v}n_{0}^{(v+2)/2v}+\sum_{i=2}^{\infty}1/i^{2}\leq
c^{\prime\prime}_{1}c^{-1/v}+c^{\prime\prime}_{2},$
$\displaystyle\lim_{k\to\infty}c^{\prime}_{k}$
$\displaystyle=1+c\sum_{i=1}^{\infty}2(2/i)^{2q/v}i^{5}\leq
c^{\prime\prime}_{3}.$

Thus (49) is proved. Taking $\varepsilon:=c_{k}M^{\prime}n^{-v^{\prime}}/M$ in
(49), we get

$\displaystyle\log\mathcal{N}(\mathrm{Co}(\mathcal{F}_{nk^{q}}),L_{2}(\mathrm{Q}),M\varepsilon)\leq
c^{\prime}_{k}c_{k}^{1/v^{\prime}}(M^{\prime})^{1/v^{\prime}}M^{-1/v^{\prime}}\varepsilon^{-1/v^{\prime}}.$

This together with

$\displaystyle(M^{\prime})^{1/v^{\prime}}=(c^{1/v}M)^{1/v^{\prime}}=c^{2/(v+2)}M^{1/v^{\prime}}$

yields

$\displaystyle\log\mathcal{N}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{Q}),M\varepsilon)\leq
c^{\prime}c^{2/(v+2)}\varepsilon^{-2v/(v+2)},$

where the constant $c^{\prime}$ depends on the constants
$c^{\prime\prime}_{1}$, $c^{\prime\prime}_{2}$ and $c^{\prime\prime}_{3}$.
This finishes the proof.

Proof [of Proposition 30] A direct application of Theorem 2.6.7 in Van der
Vaart and Wellner (1996) yields the assertion.

Proof [of Proposition 31] The assertion follows directly from Lemma 29 with

$\displaystyle c:=c_{0}d\cdot 2^{p+1}(16e)^{d\cdot 2^{p+1}}\qquad\text{ and
}\qquad v:=2(d\cdot 2^{p+1}-1).$

Then we have

$\displaystyle
c^{2/(v+2)}=(c_{0}\delta^{-1}(16e)^{1/\delta})^{\delta}=16e(c_{0}d\cdot
2^{p+1})^{1/(d\cdot 2^{p+1})}.$

Let $g(t):=(c_{0}t)^{1/t}$, $t=d\cdot 2^{p+1}\geq 4d$, then we have
$g^{\prime}(t)=(c_{0}t)^{1/t}(1-\log(c_{0}t))/t^{2}$. Therefore, there exists
$c_{1}^{\prime}$ only depending on $d$ and $c_{0}$ such that $g(t)\leq c_{1}$
for all $t\geq d\cdot 2^{p+1}$. Consequently, we have

$\displaystyle\log\mathcal{N}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{Q}),M\varepsilon)\leq
16ec_{1}^{\prime}\varepsilon^{1/(d\cdot 2^{p})-2}\leq 16ec_{1}^{\prime}\cdot
2^{p/2}\varepsilon^{1/(d\cdot 2^{p})-2}.$

Hence we obtain the assertion with $c_{1}:=16ec_{1}^{\prime}$.

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

Proof [of Proposition 33] The assumption $f_{L,\mathrm{P}}^{*}\in
C^{0,\alpha}$ implies that for any $x\in\mathcal{X}$, there holds

$\displaystyle|f_{\mathrm{P}}^{p}(X)-f_{L,\mathrm{P}}^{*}|$
$\displaystyle=\biggl{|}\frac{1}{\mathrm{P}_{X}(A_{p}(x^{\prime}))}\int_{A_{p}(x^{\prime})}f_{L,\mathrm{P}}^{*}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)\,d\mathrm{P}_{X}(x^{\prime})\biggr{|}$
$\displaystyle\leq\frac{1}{\mathrm{P}_{X}(A_{p}(x^{\prime}))}\int_{A_{p}(x^{\prime})}|f_{L,\mathrm{P}}^{*}(x^{\prime})-f_{L,\mathrm{P}}^{*}(x)|\,d\mathrm{P}_{X}(x^{\prime})$
$\displaystyle\leq\frac{1}{\mathrm{P}_{X}(A_{p}(x^{\prime}))}\int_{A_{p}(x^{\prime})}\mathrm{diam}(A_{p}(x))^{\alpha}\,d\mathrm{P}_{X}(x^{\prime})$
$\displaystyle=\mathrm{diam}(A_{p}(x))^{\alpha}.$

Therefore, we get

$\displaystyle\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p})-\mathcal{R}_{L,\mathrm{P}}^{*}=\mathbb{E}_{\mathrm{P}_{X}}(f_{\mathrm{P}}^{p}(X)-f_{L,\mathrm{P}}^{*})^{2}\leq\mathbb{E}_{\mathrm{P}_{X}}\mathrm{diam}(A_{p}(x))^{2\alpha}.$

Consequently we obtain

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\lambda
h^{-2d}+\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle\leq\lambda\cdot
4^{p}+\mathbb{E}_{\mathrm{P}_{R,Z}}(\mathbb{E}_{\mathrm{P}_{X}}\mathrm{diam}(A_{p}(x))^{2\alpha})$
$\displaystyle=\lambda\cdot
4^{p}+\mathbb{E}_{\mathrm{P}_{X}}(\mathbb{E}_{\mathrm{P}_{R,Z}}\mathrm{diam}(A_{p}(x))^{2\alpha}).$

Applying Lemma 23, we get

$\displaystyle\mathbb{E}_{\mathrm{P}_{R,Z}}\bigl{(}\lambda\cdot
4^{p}+\mathcal{R}_{L,\mathrm{P}}(f_{\mathrm{P}}^{p})-\mathcal{R}_{L,\mathrm{P}}^{*}\bigr{)}$
$\displaystyle\leq\lambda\cdot
4^{p}+(2r)^{2\alpha}d\exp\biggl{(}\frac{(4^{-\alpha}-1)p}{d}\biggr{)}$
$\displaystyle=\lambda\cdot
4^{p}+(2r)^{2\alpha}d(2^{-p})^{\frac{1-4^{-\alpha}}{d\log 2}}$
$\displaystyle\leq c\lambda^{\frac{1-4^{-\alpha}}{2d\log 2+(1-4^{-\alpha})}},$

by choosing

$\displaystyle p=\frac{d}{2d\log
2+1-4^{-\alpha}}\log\biggl{(}\frac{(2r)^{2\alpha}d}{\lambda}\biggr{)},$

where the constant $c:=((2r)^{2\alpha}d)^{\frac{d\log 2}{1-4^{-\alpha}+2d\log
2}}$.

####  7.2.1 Proofs Related to Section 6.2.1

Proof [of Theorem 34] Denote

$\displaystyle
r^{*}:=\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-R^{*}_{L,\mathrm{P}},$

and for $r>r^{*}$, we write

$\displaystyle\mathcal{F}_{r}$ $\displaystyle:=\\{f\in
E:\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\leq
r\\},$ $\displaystyle\mathcal{H}_{r}$ $\displaystyle:=\\{L\circ f-L\circ
f^{*}_{L,\mathrm{P}}:f\in\mathcal{F}_{r}\\}.$

Note that for $f\in\mathcal{F}_{r}$, we have $\lambda_{1}\|f\|_{E}\leq r$,
that is,

$\displaystyle\sum_{i=1}^{T}|w_{i}|^{2}\leq r/\lambda_{1}.$

Then, by the Cauchy-Schwarz inequality, we get

$\displaystyle\sum_{i=1}^{T}|w_{i}|\leq\biggl{(}T\sum_{i=1}^{T}|w_{i}|^{2}\biggr{)}^{1/2}\leq(rT/\lambda_{1})^{1/2}.$

Consequently, we have $\mathcal{F}_{r}\subset(rT/\lambda_{1})^{1/2}B_{E}$.
Since $L$ is Lipschitz continuous with $|L|_{1}\leq 4M$, we find

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}e_{i}(\mathcal{H}_{r},L_{2}(\mathrm{D}))$
$\displaystyle\leq
4M\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\mathcal{F}_{r},L_{2}(\mathrm{D}))$
$\displaystyle\leq
8M(rT/\lambda_{1})^{1/2}\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(B_{E},L_{2}(\mathrm{D}))$
$\displaystyle\leq
8M(rT/\lambda_{1})^{1/2}\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{D})).$

Let $\delta:=1/(d\cdot 2^{p})$, $\delta^{\prime}:=1-\delta$, and
$a:=c_{1}^{1/(2\delta^{\prime})}M$. Then (32) together with (34) implies that

$\displaystyle
e_{i}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{D}))\leq(3c_{1})^{1/(2\delta^{\prime})}(2^{p})^{1/(2\delta^{\prime})}i^{-1/(2\delta^{\prime})}$

Taking expectation with respect to $\mathrm{P}^{n}$, we get

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{D}))\leq
c_{2}^{\prime}(2^{p})^{1/(2\delta^{\prime})}i^{-1/(2\delta^{\prime})},$ (56)

where $c_{2}^{\prime}:=(3c_{1})^{1/(2\delta^{\prime})}$. Moreover, we easily
find

$\displaystyle\lambda_{2}\cdot
4^{p}=\Omega(h)\leq\Omega_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\leq
r.$

Therefore, (56) can be further estimated by

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{D}))\leq
c_{2}^{\prime}(r/\lambda_{2})^{1/(4\delta^{\prime})}i^{-1/(2\delta^{\prime})},$

which leads to

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{m}(\mathcal{H}_{r},L_{2}(\mathrm{D}))\leq
8c_{2}M(rT/\lambda_{1})^{1/2}(r/\lambda_{2})^{1/(4\delta^{\prime})}i^{-1/(2\delta^{\prime})}.$

For the least square loss, the superemum bound

$\displaystyle L(x,y,t)\leq
4M^{2},\qquad\forall\,(x,y)\in\mathcal{X}\times\mathcal{Y},\,t\in[-M,M],$

and the variance bound

$\displaystyle\mathbb{E}(L\circ g-L\circ f_{L,\mathrm{P}}^{*})^{2}\leq
V(\mathbb{E}(L\circ g-L\circ f^{*}_{L,\mathrm{P}}))^{\vartheta}$

holds for $V=16M^{2}$ and $\vartheta=1$. Therefore, for $h\in\mathcal{H}_{r}$,
we have

$\displaystyle\|h\|_{\infty}\leq 8M^{2},\qquad\mathbb{E}_{\mathrm{P}}h^{2}\leq
16M^{2}r.$

Then Theorem 7.16 in Steinwart and Christmann (2008) with
$a:=8c_{2}M(rT/\lambda_{1})^{1/2}(r/\lambda_{2})^{1/(4\delta^{\prime})}$
yields that there exist a constant $c_{0}^{\prime}>0$ such that

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}\mathrm{Rad}_{D}(\mathcal{H}_{r},n)$
$\displaystyle\leq
c_{0}^{\prime}\max\Bigl{\\{}r^{3/4}T^{\delta^{\prime}/2}\lambda_{1}^{-\delta^{\prime}/2}\lambda_{2}^{-1/4}n^{-1/2},r^{(2\delta^{\prime}+1)/(2\delta^{\prime}+2)}(T/\lambda_{1})^{\delta^{\prime}/(1+\delta^{\prime})}\lambda_{2}^{1/(2+2\delta^{\prime})}n^{-1/(1+\delta^{\prime})}\Bigr{\\}}$
$\displaystyle=:\varphi_{n}(r).$

Simple algebra shows that the condition $\varphi_{n}(4r)\leq
2\sqrt{2}\varphi_{n}(r)$ is satisfied. Since $2\sqrt{2}<4$, similar arguments
show that there still hold the statements of the Peeling Theorem 7.7 in
Steinwart and Christmann (2008). Consequently, Theorem 7.20 in Steinwart and
Christmann (2008) can also be applied, if the assumptions on $\varphi_{n}$ and
$r$ are modified to $\varphi_{n}(4r)\leq 2\sqrt{2}\varphi_{n}(r)$ and
$r\geq\max\\{75\varphi_{n}(r),1152M^{2}\tau/n,r^{*}\\}$, respectively. It is
easy to verify that the condition $r\geq 75\varphi_{n}(r)$ is satisfied if

$\displaystyle r\geq
c_{0}^{\prime}T^{2\delta^{\prime}}\lambda_{1}^{-2\delta^{\prime}}\lambda_{2}^{-1}n^{-2},$

where $c_{0}^{\prime}$ is a constant, which yields the assertion.

####  7.2.2 Proofs Related to Section 6.2.2

Proof [of Theorem 35] Denote

$\displaystyle\bar{r}^{*}:=\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-R^{*}_{L,\mathrm{P}},$

and for $r>\bar{r}^{*}$, we write

$\displaystyle\bar{\mathcal{F}}_{r}$
$\displaystyle:=\\{f\in\bar{E}:\bar{\Omega}_{\lambda}(f)+\mathcal{R}_{L,\mathrm{P}}(f)-\mathcal{R}^{*}_{L,\mathrm{P}}\leq
r\\},$ $\displaystyle\bar{\mathcal{H}}_{r}$ $\displaystyle:=\\{L\circ f-L\circ
f^{*}_{L,\mathrm{P}}:f\in\mathcal{F}_{r}\\}.$

Note that for $f\in\bar{\mathcal{F}}_{r}$, we have
$\lambda_{1}\|f\|_{\bar{E}}\leq r$, that is,

$\displaystyle\sum_{i=1}^{T}|w_{i}|^{2}\leq r/\lambda_{1}.$

Then, by the Cauchy-Schwarz inequality, we get

$\displaystyle\sum_{i=1}^{T}|w_{i}|\leq\biggl{(}T\sum_{i=1}^{T}|w_{i}|^{2}\biggr{)}^{1/2}\leq(rT/\lambda_{1})^{1/2}.$

Consequently, we have
$\bar{\mathcal{F}}_{r}\subset(rT/\lambda_{1})^{1/2}B_{\bar{E}}$. Since $L$ is
Lipschitz continuous with $|L|_{1}\leq 4M$, we find

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}e_{i}(\bar{\mathcal{H}}_{r},L_{2}(\mathrm{D}))$
$\displaystyle\leq
4M\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\bar{\mathcal{F}}_{r},L_{2}(\mathrm{D}))$
$\displaystyle\leq
8M(rT/\lambda_{1})^{1/2}\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(B_{\bar{E}},L_{2}(\mathrm{D}))$

By the definition of $\bar{E}$ in (17), we have
$B_{\bar{E}}\subset\mathrm{Co}(\mathcal{F})$. Consequently, we find

$\displaystyle\mathbb{E}_{D\sim\mathrm{P}^{n}}e_{i}(\bar{\mathcal{H}}_{r},L_{2}(\mathrm{D}))\leq
8M(rT/\lambda_{1})^{1/2}\mathbb{E}_{D\sim\mathrm{P}_{X}^{n}}e_{i}(\mathrm{Co}(\mathcal{F}),L_{2}(\mathrm{D})).$

Through the similar arguments in the proof of Theorem 34, we are able to
obtain the desired assertion. Thus, we omit the details here.

####  7.2.3 Proofs Related to Section 3.2

Proof [of Theorem 5] It is easy to see that $f_{\mathrm{P},\mathrm{E}}$
defined by (37) satisfies $f_{\mathrm{P},\mathrm{E}}\in E$ and