$a_n\le \bar{a}_n = O(\sqrt{n})$. The time complexity is $$O(dn\log n) + \sum_{m=1}^{ a_n} O(d^2+md+n'd) \le O(dn\log n + \sqrt{n}d^2 + nhd),$$ where we use the fact that $\sum_{m=1}^{ a_n} n' \le nh$. This shows the efficiency of Algorithm 1.

Theoretical Properties
======================

In this section, we will discuss the consistency of our classification tree obtained from Algorithm 1 in two aspects: the first is estimation consistency – as sample size goes to infinity, a generalized distance between SVR-Tree and the oracle classifier converges to zero; the other is feature selection consistency – for redundant features that are conditionally independent of $Y$ given the other features, the probability of SVR-Tree excluding these features converges to one.

Estimation Consistency
----------------------

We define a generalized metric on the space of all nonrandom classifiers, introduce classifier risk, and define our notions of classifier consistency.

For any weight $\alpha$ and classifier $f:\Omega \to \{0,1\}$, we define the risk as $$R(f) = \mathbb{E} \left[\alpha \max(Y-f(X),0) + \max(f(X)-Y,0)\right],$$ where the expectation is taken over probability measure $\mathbb{P}$ for random variables $(X,Y)$.

Let $\mathscr{F}$ be the collection of all measurable functions from $\Omega$ to $\{0,1\}$. Then the oracle classifier and minimal risk are defined as $f^* = \arg\min_{f\in\mathscr{F}} 