the Appendix.

Problem setup {#sec:prob_setup_new}
=============

Regression algorithm {#subsec: regression_alg}
--------------------

Let $\mathcal{X} = \mathbb{R}^{d}$, equipped with euclidean norm $\norm{\cdot}_{2}$ and $\mathcal{Y} \subset \mathbb{R}$ be some (closed) interval of the real line. Denote through $\mathbf{S}=\{\bx_{i},y_{i}\}_{i=1}^{n}$ the i.i.d. sample of of size $n$ from some unknown distribution $\mathbb{P}_{{X, Y}}$ over the space $\mathcal{X}\times \mathcal{Y}$. For some input $x \in \mathcal{X}$ we also consider its feature representation in some feature space $\mathcal{X}^{'}$ and denote it as $\psi(x)$. In this work we consider the case where $\mathcal{X}^{'} = \mathbb{R}^{D}$ and denote for an arbitrary point $\bx_{i}$ its representation $\psi(\bx_{i}) := \psi_{i} = \paren{\psi_{i}^{1},\ldots,\psi_{i}^{D}}$ with $d \ll D$, where as usual through $\psi_{i}^{k}$ we denote the $k$-th coordinate of the feature representation $\psi_{i}$. Therefore, in our work we consider the *extended sample* $\mathbb{S} =\{\bx_{i},y_{i},\psi_{i}\}_{i=1}^{n}$. Lastly, we assume (for the simplicity of the theoretical analysis) that the distribution of $\norm{X}_{2}$ has bounded support in the interval $[0,K]$. We will use the notation $[D]$ for the integer interval $\set{1,\ldots,D}$.

We investigate both the theoretical properties and empirical performance of a general form piecewise linear regressor with regularization constraints built via the the following regression tree algorithm. The proposed algorithm proceeds in a top-down greedy fashion as 