is typically done in building a decision tree. At each node in the tree, a split is chosen in the $\mathcal{X}^{'}$ space so as to minimize the empirical least square errors of linear predictors in the $\mathcal{X}$ space after splitting.

Let ${\mathcal{J}}$ be a subset of indices of the training dataset, corresponding to instances present at a given tree node. For all $(i,k) \in [D]\times {\mathcal{J}}$ denote $A_{i,k}=\{ j \in {\mathcal{J}}:  \psi_{j}^{i} \geq \psi_{k}^{i} \}$ and $A^{c}_{i,k}= {\mathcal{J}}\setminus A_{i,k}$ corresponding to the subsets obtained after a split according to the $i$-th feature coordinate and threshold $\psi^i_{k}$. Define the matrix $\bX_{A_{i,k}}$ of dimensions $(|A_{i,k}|,d)$ whose lines are given by $(\bx^t_{l}, l \in A_{i,k})$, and similarly $\bX_{A^{c}_{i,k}}$ of dimensions $(|A^c_{i,k}|, d)$. Define label vectors $Y_{A_{i,k}}=\paren[1]{y_{l}: l \in A_{i,k}}^t$ and $Y_{A^{c}_{i,k}}=\paren[1]{y_{l}: l \in A^{c}_{i,k}}^t$ of dimension $|{A_{i,k}}|$, $|{A^{c}_{i,k}}|$ respectively.

For every $(i,k) \in [D] \times {\mathcal{J}}$ consider the optimal cumulative penalized loss of linear predictors after splitting: $$\begin{gathered}
\label{eq:L_diff}
L^\lambda_{i,k}= \min_{w_{i,k} \in \mathbb{R}^{d}} \paren{ \norm[1]{\bX_{A^{}_{i,k}}{w}^{}_{i,k}-Y_{A^{}_{i,k}}}_{P}^{2} + \lambda \| w_{i,k} - w_0\|^2_Q}  \\ + \min_{w^c_{i,k} \in \mathbb{R}^{d}} \paren{\norm[1] {\bX_{A^{c}_{i,k}}{w}^{c}_{i,k}-Y_{A^{c}_{i,k}}}_{P}^{2} + \lambda \| {w}^{c}_{i,k} - {w}_0\|^2_Q},\end{gathered}$$ where $\norm{x}^{2}_{P}:= x^{\top}Px$ and $w_{0}$ may be any vector, though in the following we set $w_0$ to be the 