the stopping criteria has been reached we apply the splitting algorithm recursively to these two subnodes. If the stopping criteria is reached, then the linear regression with constraints is performed on the leaves.

Regression tree formalism
-------------------------

For the learning-theoretic study of the algorithm, we need to define formally the set of possible decision functions that can be output by the learning algorithm. This set must be data-independent for classical learning-theoretic arguments to apply.

We assume that the total number of leaves is fixed and equal to $\ell$. Let $\mathcal{T}_{\ell}$ be the set of all binary (unlabeled) trees with $\ell$ leaves. For each tree $T \in \mathcal{T}_{\ell}$, denote by $T^{\circ}$ its interior nodes, and by $\partial T$ its leaves. Consider some interior node $s \in T^{\circ}$ and some splitting rule according to the algorithmic scheme in Section \[subsec: regression\_alg\]. Notice that a pair $(i_{s},t_{s}) \in [D]\times \mathbb{R}$ fully parametrizes the splitting criteria in the form $\mathbbm{1}\paren{{\psi^{i_{s}}(\bx) \geq t_{s}}}$ for some instance $\bx$. Any split corresponding to a set $A_{i,k}$ which can be obtained by the partition procedure of the PLRT algorithm can be represented as a pair $(i_s=i,t_s=\psi^{i_s}_k)$ for some $k\in [n]$. Finally, for each leaf $ L_{i} \in \partial 