1-2.

\[condition 1\] There exists $c_1\in [0,1]$, such that for all $A\subset\Omega$, $\sup_{1\le j\le q} M_{A,j} \ge c_1 M_A^*.$

Condition \[condition 1\] relates the impurity decrease in non-redundant features to the oracle impurity decrease. The strength of the condition is dependent on the value of $c_1$. If $c_1=0$, the condition does not impose any restrictions; if $c_1 =1$, partitions in non-redundant features can fully explain the oracle impurity decrease. Here we give some examples of models with different $c_1$ values.

Let $\Omega = [0,1]^d$ and the marginal distribution of $\mathbb{P}_\alpha$ be the uniform distribution on $\Omega$. Suppose $\mathbb{E}(Y|X)= \phi(a^T X + b),$ where $\phi(\cdot)$ is a monotonically increasing function, $a\in\mathbb{R}^d$ and $b\in\mathbb{R}$. Let $A_{y1}, A_{y2}$ be measurable sets having $A_{y1}\cap A_{y2}=\emptyset$ and $A_{y1}\cup A_{y2} = \Omega$, which achieve the oracle impurity decrease $M_A^*$, and let $\min\{\mathbb{P}_\alpha(A_{y1}), \mathbb{P}_\alpha(A_{y2})\}=h$. Then the constant $c_1$ in Condition 1 satisfies $c_1 \ge (\sqrt{2}-1)h + o(h)$ if $h \le 1/d!$ and $c_1 \ge F_{d-1}(F_d^{-1}(h)-h) - F_{d-1}(F_d^{-1}(h)-2h)$ if $h>1/d!$, where $F_d(z) = \frac{1}{d!} \sum_{k=0}^{\lfloor z\rfloor}(-1)^k {d\choose k} (z-k)^{d-1}$ is the cumulative distribution function for the Irwin-Hall distribution with parameter $d$.

Let $\Omega = [0,1]^2$ and $\mathbb{P}_X$ be the uniform distribution on $\Omega$. Let $A_1 = [0,1/2]\times[0,1/2],$ $A_2 