Active Learning for Decision Trees with Provable Guarantees
Authors: Arshia Soltani Moakhar
Tanapoom Laoaron
Faraz Ghahremani
Kiarash Banihashem
MohammadTaghi Hajiaghayi
Venue: ICLR 2026 Poster (2026)
Keywords: Label complexity
Theory of Active Learning
Theory of Decision Tree
Disagreement coefficient
Primary area: learning theory
TL;DR: We provides the first analysis of the disagreement coefficient for decision trees, and also we develop a general active learning algorithm for binary classification that provides a multiplicative error guarantee.

Abstract: This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the **disagreement coefficient** for decision trees—a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity: (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has a regular, grid-like structure. We show these assumptions are essential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a **multiplicative error guarantee**, producing a $(1+\epsilon)$-approximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a **polylogarithmic number of label queries** in the dataset size, under the stated assumptions. Finally, we establish a label complexity lower bound, showing our algorithm’s dependence on the error tolerance $\epsilon$ is close to optimal.

Published as a conference paper at ICLR 2026
ACTIVE LEARNING FOR DECISION TREES WITH PROV- ABLE GUARANTEES
Arshia Soltani Moakhar Univeristy of Maryland asoltan3e
Tanapoom Laoaron Univeristy of Maryland 1 laoaron r @mdd edu
Faraz Ghahremani
Univeristy of Maryland fa farazgh @udd edu
Kiarash Banihashem Univeristy of Maryland ki kiarash@und. edu
MohammadTTaghi Hajiaghayi Univeristy of Maryland ha j jaghaa und. edu
ABSTRACT
This paper advances the theoretical understanding of active learning label com- plexity for decision trees binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity: (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has regular, grid-like structure. We show these assumptions are es- sential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a multiplicative error guarantee, producing (1 + -aapproximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a polylogarithmic number of label queries the dataset size, un- der the stated assumptions. Finally, establish label complexity lower bound, showing our algorithm's 's dependence on the error tolerance is close to optimal.
INTRODUCTION
Active learning a machine learning paradigm that seeks to minimize the labeling effort required to train model by strategically selecting the most informative data points for labeling Ren et al. (2022). Unlike traditional passive learning, which relies on randomly labeled data, active learning operates on unlabeled dataset and iteratively selects sample to query its label which tailors the selection process to focus on examples that contribute the most to improve model performance. Labeling complexity becomes significant challenge in scenarios where annotation requires human expertise- particularly in domains like medical applications, where labeling cannot be outsourced crowdsourcing platforms but instead relies skilled professionals. Given the limited availabil- ity and high cost of such experts, active learning emerges as an invaluable solution in domains where acquiring labeled data both expensive and cone-connuming. Examples include medical di- agnosis Budd et al. (2021), autonomous driving Feng et al. (2019), webpage classification Hanneke (2014) and natural language processing Schröderr Niekler (2020); [Zhang al. (2022). By reduc- ing the labeling cost, active learning has become cornerstone of efficient model development in inta--nttensive fields [Settles (2012). Decision trees are extensively utilized in machine learning because they inherently perform feature selection Xu et al. (2014); [Banihashem (Banhaaaaa et al. (2023), offer interpretability Gilpin et al. (2018). and achieve strong practical performance with minimal computational expense. These properties have made decision trees a core component in ensemble methods such as random forests Breiman (200I) and XGBoost CCen & Guestrin (2016). which are among the most popular algorithms in supervised learning tasks. While active learning has been applied to decision trees in various practical con- texts Ma et al. (2016); Wang et al. (2010), the existing research in this area often lacks a rigorous theoretical foundation. This gap highlights the need for deeper understanding of the theoretical aspects of applying active learning principles decision tree learning.

---

Published as a conference paper at ICLR 2026
This paper addresses significant gap in the theoretical foundations of active learning by providing the first rigorous analysis of its sample complexity for decision trees. Our analysis centers on the disagreement coefficient. key parameter in active learning theory that, until now, had not been analyzed for the decision tree class. The importance of bounding this coefficient lies in its direct impact label efficiency, it appears in many active learning algorithms. For example Hanneke (2014) get the following label complexity:
0²
1 (d 0 + Log
[log(1/ [log(1/additvve)
0(
log
addiitive
Cadditive
This investigation reveals two critical assumptions required derive a polylogarithmic bound on this coefficient: that each node in the decision tree must test feature dimension distinct from its ancestors, and that the input data exhibits structural regularity (which we model as a grid). We prove that without these assumptions, the disagreement coefficient is not effectively bounded, leading to polynomial sample complexity. Our analysis culminates in the following bound:
Theorem 1.1. Consider a decision tree classification task over dataset S of points. Let the input space be X {(a....., (.ii) Vi, a; N, 0, I w for some If every node in tree tests feature dimension distinct from its ancestors and the tree height is at most d, then the disagreement coefficient is upper bounded by = O(n" (In"(n)) and lower bounded by 8 = Q((((I(()) - c)a-1) where já-id: and c' = In(4)dim.
Next, we propose the first active learning algorithm for binary classification tasks discrete datasets that achieves a multiplicative error bound, Algorithm 2 In our framework, an algorithm is given n unlabeled data points and can adaptively query their binary labels. The objective is return (1 + --approximaaee classifier with probability at least - 6. A classifier is (1 + <)-approximate if its error at most 1 times that of the optimal classifier in the class. Our primary focus is to minimize the algorithm's 's label complexity, which is the total number of queries it performs. The performance of Algorithm is captured by the following theorem:
Theorem 1.2. For any binary classification task, Algorithm returns (1+ () -approxximatee classi- fier with probability greater than 1 - 5. It does so using
o (Inn)) In Inn
0 (VH )
Iv In 1n
queries, where n is the dataset size, VH the VC dimension of the classifier space, and is the disagreement coefficient.
The adoption of the multiplicative enror model in classification tasks is key strength of this work. enables stronger control over the classifier's accuracy compared to additive error models, provid- ing greater flexibility to achieve desirable error rates based what is achievable. For instance, in realizable settings, where the optimal classifier has zero error, this approach guarantees perfect clas- sification-a capability beyond the reach of additive models, which e-off regardless of the optimal classifier error. While the multiplicative framework has been extensively explored the context of active learning for regression (see, e.g., Musco et al. (2022); Derezinski al. (0188: Parulekar (Ceen
ct al. (2021); Chen & Price (2019) Chen & Derezinskil (2021): I): Gajjar et al (2023 2024); Chen et al. (2022) D. our work is the first introduce an algorithm for multiphcative error in classification. This aligns with broader trends in computer science, such as approximation algorithms and competitive analysis, where multiplicative error models are standard.
A crucial motivation for our work is the inadequacy of existing additive error algorithms for the multiplicative setting. A natural approach might error parameter Cadditive relative to an estimate of the optimal error 1) (i.e., Caddiiiv cr)). However, this strategy is fundamentally flawed. Estimating 7) with sufficient accuracy to provide a meaningful guarantee itself requires a number of label queries that is inversely proportional to 77. Consequently, the label complexity would become dependent on an unknown and potentially very small quantity, making the required number of labels Q(n). Alterattve strategies, such iteratively guessing and verifying n, face the same bottleneck at the verification step. In Appendix
adapt an additive algorithm by setting its
[ we formalize this argument, demonstrating that any such adaptation is inherently label-inefficient. This highlights the
2

---

Published as a conference paper at ICLR 2026
need for fundamentally different approach, like the one we propose, that is designed to be agnostic to the magnitude of the optimal error.
Our central result is new label complexity bound for actively learning decision trees, which de- rive by combining the two main contributions of this paper. By applying our general multiplicative- error Algorithm to the decision tree class and using our novel bound the disagreement coeffi- cient, we achieve a query complexity that is polylogarithmic in the dataset size. This result holds under the previously discussed assumptions on tree structure and data distribution. The algorithm's performance depends on the maximum tree depth, denoted by d, and the feature dimensionality, dim, as formalized our main theorem:
Fdim) Vi, W, NJ be with binary labeling. Algorithm 2 returns (1 + -ppprooxie classifter of an optimal decision free that each node operates on data dimension distinct from those used by its ancestors. The algorithm requires at most the following number of queries:
Corollary 1.3. Let X
dim)d - In 1)) + (n) (24(d dim) In In + In in))) of In (n) (d (n)(2())))
e²
To highlight the efficiency of our algorithm, we also establish lower bounds for the label complexity of any such active learning algorithm in Theorem 4.3 and showed that some terms, like c, can only experience logarithmic improvements.
To summarize, our contributions are as follows:
The first active learning algorithm for multiplicative error budget in classification.
The first label complexity bound for active decision learning.
Proving the necessity of the uniform-like assumption and the constraint that each node on root-to-leaf paths operates on a unique dimension for achieving loly-logarithmic label complexity in active decision tree learning.
The first label complexity lower bound for active stump learning discrete datasets.
2 RELATED WORKS
Realizable Active Learning for classification: Numerous studies have examined active learning in the context of binary classification tasks. Some of these works assume the existence a classifier with zero error El-Yaniv & Wiener (2010; 2012); HHaneeke (2012); Hopkins et al. (2020b). In trast, our approach does not rely on this assumption, which makes it more applicable to real-world scenarios where perfect classifier is not guaranteed.
Some prior research has addressed active learning in agnostic settings, where perfect classifier exists Balcan al. al. (007): Hanneke (2007): Daas gupta et al. (2007): & Nowak / (2008) 2006). Among these, algorithms based on disagreement- based active learning, such as A Balcan et al. (2006). share similarities with our approach by maintaining version space-a set of classifiers that initially includes the optimal classifier and is iteratively refined without excluding it. However, unlike prior work, our method is the first exploit signals arising when the version space fails to shrink rapidly. We use this stagnation to lower-bound the error and leverage this lower bound to identify (1 + appprxxiiaaee classifier.
Agnostic Active Learning for classification:
Notably, all these previous studies assume an additive error framework, guaranteeing that the classi- fier's error exceeds that of the optimal classifier by at most a fixed additive margin. In Appendix examine the relationship between additive and multiplicative error frameworks and algorithms, demonstrating that existing additive approaches are unsuitable for multiplicative error settings and cannot be adapted to address problem. For comprehensive survey, see Hanneke (2014).
Active Learning Regression: Active learning has been extensively studied in the context of linear regression and fp norm regression. Several papers aim to improve the label requirements of active learning and provide theoretical bounds on the minimum requirements Musco et al. (2022):
Derezinski al. (2088); Parulekar al. (202T); Chen & Price (2019); Chen & Derezinski 2021
3

---

Published as a conference paper at ICLR 2026
Woodruff )2014):
Notably, Musco al. (2022) investigates lp norm regression. Throughout our paper, we adopt the setup from Musco et al. (2022), and our algorithm returns a (1 + aapproxxmmae solution on given discrete dataset where labels are arbitrary, without any assumptions on them.
Sarlós (2006).
Theory of Decision Tree Learning: The theoretical study of decision tree learning has been
plored primarily from the perspective of time complexity in various specific contexts Ehrenfeucht & Haussler 1989;; Mehta & Raghavan (2002); Blanc et al. 2019 2022). While recent work has estab- lished sample complexity bounds for data-driven hyperparameter tuning of decision trees Balcan & Sharma (2024). there is no previous work that considers theoretical guarantees for the active learn- ing label complexity of decision trees. Additionally. in the context of learning, existing works have analyzed different properties of decision trees, including their application to sparse feature recovery. Notably, works by |Banihashem et al. (2023); Kazemitabar et al. (2017) focused on decision stump learning for regression problems, motivated by the challenge of sparse feature recovery. While these studies have contributed to our understanding of decision tree learning in settings such as sparse covery and sample complexity, they largely overlook the domain of active learning within decision tree theory.
Disagreement Coefficient of decision trees The theoretical basis for active learning of decision trees was laid by Balcan al. (2010), who showed that exis-parallel trees continuous inputs in the [0, 1 hypercuhe can be learned efficiently under the uniform distribution. Their proof relied on decomposing the class by leaf count and arguing that each subelass has finite disagreement coef- ficient. However, they only asserted finiteness without giving a way to compute the coefficient or bound quantitatively. Our work fills this gap by providing the first explicit calculation of the dis- agreement coefficient for decision trees on discrete domains, establishing the bound 0 O(I (n)).
Active Learning Using Stronger Queries: To overcome the limitations of conventional active learning methods, several studies have considered active learning with stronger query models Hop- kins et al. (2021); Kane et al. (2017); Hopkins et al. (2020a). For example, (Hopknns et al. (2021) investigates the active learning of decision trees using queries that check whether two samples be- long to the same leaf in the optimal decision tree. Similarly, Kane et al.) (2017) shows that it is possible to learn a perfect half-space using only log(dataset size) comparison queries, where the la- beler answers which sample is more positive. However, these approaches assume realizable settings, where a perfect classifier exists. contrast, our work focuses on a simpler and more practical query model that exclusively returns the label of a sample, without assuming realizability.
3 DISAGREEMENT COEFFICIENT IN DECISION TREES
The theoretical analysis of many active learning algorithms for binary classification relies on the disagreement coefficient. a parameter that measures the complexity of hypothesis class Balcann et al. ( Hanneke (2014). Intuitively, it captures how many data points have uncertain labels within set of plausible hypotheses. A smaller coefficient suggests that an active learning strategy can efficiently prune the version space. This section defines the disagreement coefficient and derives an upper bound for the class of decision trees.
3.1 FORMAL DEFINITIONS
Let I/ denote the hypothesis class (e.g., decision trees of bounded depth) and S dataset of n points. Definition 3.1 (Distance & Hypothesis Ball). The distance between two hypotheses h, E H on S is the fraction of points where they disagree:
Ds(h, h²)
II((=)) h((x)).
mES
The ball of radius r around h E H is the set
BH == (h' E H Ds h)) sr).
Definition 3.2 (Disagreement Region). For V C H, the disagreement region is the set of points in S where some pair of hypotheses in differ:
DVSs(V)= = (x E S 3h, h2 V (x) # h2(x))
4

---

Published as a conference paper at ICLR 2026
t S 21
f1 S 21
No
Yes
No
Yes
12 S 22
13 S
h,,3
f3 322
No
Yes
No
Yes
No
Yes
b,,
ln.3
1a,4
I,.3
1 - 4,,3
(a)
(b)
Figure 1: (a) A decision tree with 4 leaves (L = 4). Leaf 1 uses dimensions 1,2 so d {1,2}.
(b) LineTrees,, classifies all samples as 1 - Ln,3 except those reaching leaf of h.
These notions lead to the disagreement coefficient, which compares the size of the disagreement region to the radius of the corresponding hypothesis ball.
Definition 3.3 (Disagreement Coefficient). For h E H, the disagreement coefficient is
DISs (Bu (h,
8
== sup 0>0
rn
The disagreement coefficient for is the worst-case value: == supheh 0n.
3.2 AN UPPER BOUND DECISION TREES
establishes an upper bound on the disagreement coefficient for decision trees under certain structural and distributional assumptions. The proof proceeds by decomposing tree into simpler components, analyzing their disagreement properties, and then recombining the results, which leads us to define the notion of a LineTreee
Our first main result, Theorem 1.1
Let h be a decision tree. For each leaf i, let I denote its label and dr,; S (I,..., dim} the set of dimensions tested along the path from the root to that leaf.
Definition 3.4 (Line'Tree). For tree h and leaf i, the corresponding line tree, denoted I LineTreen, a classifier that assigns label h,, all inputs reaching leaf h, and the opposite label 44 otherwise. Figure shows example of tree f and its line tree LineTre.,..
To prove Theorem 1.1 we fix tree and bound 0n by analyzing (hrr)) for all > O.
Although DIS Bμ (h, ()) seems to depend on all pairs of classifiers in (h, or r), it can be expressed directly terms of h. By Lemma D.1 DIS( Brr (h,r)) = (x 3M E B₁ (h, r) 1/(x)) o h(r)).
We decompose this set according to the leaf i that reaches in h and the dimension set d' of the leaf
it reaches in h'. Hence, (IS(BH (h,r) is the union over all and d' C (1, dim}
{x (ineTree,,, Ln,s E de d' LineTreew",
4 A Ales # 4,3 (1)
we can replace H' E (H with an equation related to LineTreen, and LineTreen jj then can relate the analysis of trees to the analysis of line trees. In Lemma D.2 we achieve this by showing that if I, * In then Ds. (h, h') is larger than Ds, (LineTreen,, LineTrreew, when S; is the set of data points that reaches leaf in h.
Then, we use Proposition 3.5 show that the sets in Equation I each have size of O(( )d) Combining this with the fact that there are T.(dan) sets in total, we can prove Theorem 1.1
( 21((x)
dim
Proposition 3.5. a line tree classification task where each node decides based on one of the d' C 21, ... ,dim) } input dimensions, different from all of its ancestors, and the tree height is less than d, with
,dimm
X =({ Vj E N, < w. S w]
for some w; vector and the disagreement coefficient of a classifier which assigns the same labels to all data points is of O ((3 w
Using the calculated disagreement coefficient and Vn of decision tree in Lemma A.3 which is 2d (d+ In dim), completes the proof of Corollary
5

---

Published as a conference paper at ICLR 2026
S 2n
c 211
No
Yes
No
Yes
++ S 2/
0
S 22
No
Yes
No
Yes
0
1
0
(a)
(b)
Figure 2: (a) decision tree that assigns label and only if za (b) A decision tree assigning
label 1 only to X when X; = (i, i,,
3.3 NECESSITY OF ASSUMPTIONS
We now show that the assumptions in Theorem 1.1 necessary. Without them, the disagreement coefficient becomes substantially larger.
Theorem 3.6. If decision tree nodes permitted query the same dimension as their ancestors, the disagreement coefficient for trees of height 2 2 is = [2 //im for any dataset with n. distinct points.
To prove this we first consider the constant classifier fgg that labels all samples as O. Since decision tree nodes query the same dimension their ancestors, it is possible construct classifiers that are very close to hy but label an small portions the data as This allows us to build a set of classifiers within small ball around ho whose disagreement region covers large fraction of the dataset. An example of such classifier is presented in Figure 2a which classifier only data points that have x, for some specific and c.
construct such set of classifiers within radius of 2n 1n-1/dim around hy. The resulting disagreement region, DIS( B (ho, r)), can be shown to contain least 2dm_1 data points. This large disagreement region within small radius directly leads to large disagree- ment coefficient. Calculating the ratio m
More specifically,
qam
[DIS] with these values yields lower bound of ((n
Theorem 3.7. There exists a size n dataset for which the disagreement coefficient of binary deci- sion tree classifier is (nn), even if nodes are restricted to unique dimensions per root-to-leaf paths.
To prove this we first consider dataset where all points lie on the line 21 = I2 = e.g.. X; (i, i) for the ball (ho,)) contains any tree that misclassifies only one point. It is possible to construct tree that isolates and flips the label of any single point X; (Figure 26 Therefore, for any point X₁, there exists hypothesis h4 E By r) such that h.(X.) = F hx())). This implies that the entire dataset is the disagreement region D (ho, r)). yielding a coefficient of least DIS
,,. Let ho be the all-O classifier. For radius Zdim- 1/n,
3.4 RELAXING THE UNIFORMITY ASSUMPTION
The integer grid assumption for the input distribution is restrictive. We can relax it by assigning weight W; E [1, Aj to each data point X;, representing its relative importance. This modifies the distance metric to a weighted average:
Ds.w (hr, 122) En T(h((x,) # W2
Σ W
This formulation generalizes the analysis of classification errors. As prove in Theorem D.14 (which a variant Theorem 7.6 from Hanneke (2014) for discrete datasets), the disagreement coefficient for this weighted task scaled by most X compared to the unweighted case.

---

Published as a conference paper at ICLR 2026
4 A MULTIPLICATIVE-ERRR--
ACTIVE LEARNING ALGORITHM
This section introduces and analyzes an active learning algorithm designed to find a classifier with multiplicative error guarantee. That is, if the optimal classifier ht in class H has error of 7), our algorithm returns a classifier h with error less than 1y(1 + c) with high probability.
A natural first question is whether existing algorithms, which typically provide additive enror guar- antees (i.e., returning h with error at most 17 + c'), can be adapted for the multiplicative setting. However, such adaptations are fundamentally label-inefficient. Any approach based algorithm would require an estimate of the optimal error to set the additive term e' appropriately (e.g..''=en)) Estimating or verifying an emror rate of 1) with high probability requires (1(1 sam- ples. Since an effective algorithm's 's label complexity cannot depend on the unknown, and potentially very small, value of 1), additive frameworks are unsuitable for achieving multiplicative guarantees. In Appendix E we formally investigate the scenarios in which these adaptations fail, demonstrating their inherent limitations.
additive
Our approach, by contrast, is designed to circumvent this dependence algorithm's 's core logic in the simple, one-dimensional setting of a decision stump. We then generalize this framework to arbitrary binary classification tasks, yielding result whose label complexity depends on the disagreement coefficient derived in Section
We first present the
4.1 THE DECISION STUMP CASE
A decision stump for one-dimensional data is decision tree of depth one, defined by single threshold. We begin with this setting to illustrate our algorithmic approach a simple context. The main result for this section is the following label complexity bound.
Theorem 4.1. For a one-dimensional, sorted datasel of size n, Algorithm 7 returns a (1 + e)- approximate decision stump with probability at least 1 5. using total of
o (Inta) (In(I((n)) + In ))) +2
1 In
1 Öc
label queries.
Problem Setup. Our approach operates within the active learning framework of Woodruff et al. Musco et al. (022), where the algorithm has access all input samples from the outset and can adaptively query their labels. Specifically, the algorithm is given sorted vector of unlabeled data points X E RR (X; X1+1) and can adaptively query their labels from the target vector Y E (0, 1)". A stump classifier h is defined by a threshold, which we can represent by the index of the first sample classifies 1. Thus, h E (0, 1,..., n) corresponds to the rule h(xx) = T(x 2 Xx), where we define X,- -o to handle the case where all samples are labeled 1. The error of a clas- sifier on a subset of samples S" C S'T is denoted errs (h) = ST E(.n))s 1(h(z)+ # y).
Algorithm Intuition. Algorithm maintains an interval of candidate stumps [L,, R. that, with high probability, contains the optimal one. Each iteration attempts to shrink this interval by (i) sampling a few labeled points from XIL,.R,1- (ii) bounding errors of all classifiers using high-probability lower/upper bounds (Appendix A.1. and (iii) pruning any classifier h' whose lower bound is above another's upper bound.
The crucial feature is how the algorithm reacts when pruning fails: if [L, Ry] does not shrink by at least half, this signals that all classifiers in the interval incur relatively high error. Instead of wasting more iterations, the algorithm halts and directly estimates the best classifier in the range using 0 In ) additional samples. We call this last phase direct estimation phase.
Formally, in iteration we obtain bounds for each h using (ln(1188)) samples S, ensuring with probability - -8, where 8' = 5/(2 logg 2n) we have:
UB,,,,,,8)) Classifiers eliminated by these bounds shrink the interval; if the shrinkage is insufficient, the algo- rithm switches to direct estimation. Pseudocode is given in Algorithm [ We write (a, S) for a uniformly random subset of 5 of size a; that is, we choose distinct elements from S at random.
LB(S, h, 8') S L.r
UB - LB +
We empirically validated Algorithm on datasets of size n = 107 with 0.1 label noise. The results demonstrate that the algorithm achieves success rates > 90% using constants significantly smaller

---

Published as a conference paper at ICLR 2026
Algorithm Stump algorithm
Algorithm 2 General Binary Classification
1: Initialize <-0 0
1: S + All samples, H t- All classifiers
2: Initialize L, f 0, R, t- n
2: < Calculate 0 for using Definition 3.3
3: while L; S R3 do
3: i i 0
4: S1+1 - 40 (c In
(n (v) + bi, X(L..R))
4: H; <- H. + {Initial progress measure)
5:
i ++1
5: while
[H:] > do
6:
3+ +
min UB(S:, 6') AE(M--1.R--l
6: S; f (e (2 In + In ln +
bi, DIS(HH))
7:
H
{h'
R1-1]
7:
3 t min U h, 8¹)
LB(S;, 1,, < {
8:
Hi+1 + {h H, LB St h, 8') s 3
8:
I 4- min(H) R₁ t max
9:
Ti+1 f- radius( H(+1)
if RG 14 > R then
9:
10:
rf+1 7 then
10:
S' + ( (In bc X(L
11:
S'
2 (a (Vn ln + In(g)) +
b2, DIS(H.))
11:
Return arg
min R,,
UB(S', h, h, 2)
12:
Return arg minken. UB(S",
12:
end if
13:
end if
13:
end while
14:
iti+1
14:
Return I,
15:
end while
16: Return h E
than the theoretical worst-case (C1, x 3), supporting its practical viability. Full details are in Appendix
Theorem 4.2. There exist universal constants 61, C2, b,, b2 such that Algorithm Teturns a classifier with an error rate less than 77[1 + c) with probability at least 1 - 8 when provided with one- dimensional dataset.
Correctness and Label Complexity Proof Sketch. The proof proceeds in several steps. First, Lemma B.I shows that the main loop of Algorithm D executes at most log22n iterations. Then, Lemma B.2 establishes that, with probability at least 1 1 delta, all bounds produced by the algorithm hold simultaneously throughout its execution. Conditioning on this event, we next prove that the optimal classifier is never eliminated. The argument is as follows: if classifier h is suboptimal within the interval [L, R,), then h cannot be optimal over the entire dataset, as shown in Lemma B.3 Combining this with Lemma B.4 we conclude that the optimal classifier always remains in the candidate range [T,, R.). Consequently, when the algorithm terminates, the returned classifier guaranteed to be optimal among the remaining candidates.
The main subtlety arises from the two different ways the algorithm can terminate: by continuing to shrink intervals, or by entering the direct estimate phase. The key idea is that these two outcomes correspond to complementary regimes for the error the optimal classifier. When the optimal classifier has small eтror the current interval [L, R,], Lemma B.6 shows that the interval length shrinks rapidly. In fact, if the optimal error is less than 16: then the next interval [L4+1, R,41) is at most half the size of [T4, R.). Thus, in the low-error regime the algorithm never enters the direct estimate phase; instead, it keeps shrinking intervals until the candidate set is tightly localized around the optimum. In contrast, if the algorithm does enter the direct estimate phase, this indicates that the optimal error on the current interval is relatively large. In this high-error regime, approximating within factor of (1 E) becomes easier. Lemma B.7 formalizes this intuition, showing that there exist universal constants and by such that the classifier returned in the direct estimate phase always achieves error within the desired (1 e)-factor guarantee. Putting the cases together, we conclude that the algorithm always returns (1 + apprroxxeette classifier with probability at least 1 - 6, thereby proving Theorem 4.2
To establish the label complexity bound in Theorem 4.1 we first apply Lemma B.1 to show that the for loop repeats at most log22n times. During these iterations, the algorithm uses at most Oln n In ln.) label queries. If the algorithm later enters the direct estimate phase, it performs an additional O ( In ++) label queries. This completes the proof of Theorem 4.1
8

---

Published as a conference paper at ICLR 2026
4.2 LOWER BOUND
We aim to demonstrate that any active learning algorithm within the given setting has a label com- plexity of ((n(()) :)) This result establishes that it is not possible significantly improve the label complexity with respect to the term e. beyond a logarithmic factor. The result is as follows:
Theorem 4.3. Any active learning algorithm requires Q (In (5) )) queries to return (1 + +)-
approximate decision stump with probability greater than
To prove Theorem we build upon the lower bound established in Kääriäinen (006). which determines the minimum number of coin tosses required to decide whether heads is more likely than tails. We adapt this result by modeling the active learning problem as an analogous coin-tossing process: here, the "coin" provides the requested labels, and the active learning algorithm's classifier determines whether heads is more likely than tails. By applying the lower bound from Käärääien (2006) to this framework, we derive a lower bound for the label complexity of the active learning algorithm. We should mention that this result were proven for continues input spaces Hanneke (2014) but needed additional techniques for discrete datasets.
4.3 GENERALIZATION TO ARBITRARY CLASSIFIERS
We now generalize the stump algorithm to handle any binary classification task. The performance of this resulting algorithm is formally stated in Theorem [122 in the introduction. The resulting algorithm's performance depends on structural properties of the hypothesis class, captured by the VC dimension and the disagreement coefficient.
Algorithm 2 follows the same template as the stump algorithm but replaces ID-specific concepts with their general counterparts. The candidate set not an interval [L,, R:] but a general subset of hypotheses H; C H. The sampling occurs not from a data range but from the disagreement region, g This is the set of points informative for distinguishing among remaining clas- sifiers. Finally, progress is measured not by interval length but by the radius of the hypothesis set, radius(H,). which the radius of the smallest ball containing H, The pruming step remains the same: eliminate classifiers that are provably worse than another candidate. The algorithm switches to final, direct estimation phase if the radius of the hypothesis set fails to halve in an iteration.
Role of the Disagreement Coefficient. The proof of Theorem 4.4 shows that an ineffective pruning step implies a high optimal error. this general setting, "high" is relative to the disagreement coefficient. Specifically, if the radius fails to halve, the optimal error 7/2 on the disagreement region must be at least ((1/0). The disagreement coefficient 9 bridges the gap between the radius of the hypothesis ball and the size of the disagreement region, allowing us make this critical inference.
Algorithmic Details. Algorithm 2 formalizes this procedure. The core of the algorithm is an itera- tive loop that prunes the set of candidate classifiers, H. In iteration we focus on samples x E S for which there exist h1, fy E H; such that the two classifiers disagree with each other h (x) * h2(x) more formally DIS(H,). Therefore, in each iteration, sample set S, is drawn from the disagree- ment region DH,, (Line 6). Using this sample, the algorithm finds the minimum error upper bound among all classifiers in H, and then forms the next set, H4+1, by eliminating any hypoth- esis whose error lower bound exceeds 3 (Lines 7-8). This efficiently removes classifiers that are provably suboptimal based on the evidence from S..
Measuring Progress. Progress is tracked via the radius of the hypothesis set, which quantifies its size. The radius of a hypothesis set H; is then the radius of the smallest ball, under this metric, that encloses all classifiers in the set:
radius( H,) == min(r r Bv H₁ S BDG (h'rr))
Ff an iteration fails to halve this radius (r; > 1221 the algorithm transitions to its final estimation phase (Lines 10-12). This switch is justified because slow progress implies high optimal error, which allows us to select the final classifier. The correctness of the general algorithm is formally stated below.
Theorem 4.4. There exist universal constants c1, 02 by, b2 such that, for any binary classification task, Algorithm| 2 returns a classifier with error less than ry(1 + e) with probability at least 1 - 6, where n) is the error of the optimal classifier.
9

---

Published as a conference paper at ICLR 2026
The proof mirrors the stump case. We show the main loop runs only Oloogn) times (Lemma and that all probabilistic bounds hold simultaneously with high probability (Lemma B.2). Crucially, the optimal classifier h" is never pruned from H; (Lemma C.5p. The argument ties progress to the optimal error via the disagreement coefficient. Lemma C.7 shows that if the optimal error on (H, is small (below 1/(160), the radius must halve. Otherwise, Lemma C.8 ensures the direct estimate phase suffices to output (1 + -aaaproxxmatee classifier.
Finally, Corollary pendix D.I
1.3
follows directly from Theorem and Theorem 1.2 with details in Ap-
5 CONCLUSION
In this paper, we established the first rigorous theoretical foundation for actively learning decision trees, presenting an algorithm that achieves polylogarithmic label complexity in the dataset size. This result is built on two core innovations: the first analysis of the disagreement coefficient for deci- sion trees, which we bound as 0 = (In (n)). ). and proof that our underlying assumptions- feature dimensions per path and a grid-like data structure are necessary avoid polynomial com- plexity. We combined this with the introduction of the first general active learning algorithm for any binary classification task to provide work than traditional additive models whose dependence on e we show is nearly optimal. Our work bridges critical gap between the practical use decision trees and their thcoretical understanding, opening several avenues for future research, such relaxing our structural assumptions, extending the analysis to continuous data domains, and applying our general algorithmic framework to other classifier classes.
+ -)muutippicative error guarantee, more robust frame-
ACKNOWLEDGMENTS
This work is partially supported by DARPA expMath, ONR MURI 2024 award on Algorithms, Learning, and Game Theory, Army-Research Laboratory (ARL) grant W911NF2410052, NSF AF:Small grants 2218678, 2114269, 2347322.
REFERENCES
Martin Anthony and Peter L. Bartlett. Neural Network Learning Theoretical Foundations. Cam-
bridge University Press, 2002. ISBN 978-0-521-57353-5. URL http: /www cambridge. GB.
htwpoo/wwddge//oo//eeeeeeee wwtteem1154061110 54061 httpl//epee.eattteeeeee///////g/
Maria Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. In
The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Maria-Florins Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. In William W. Cohen and Andrew W. Moore (eds.), Machine Learning, Proceedings of the Twenty-
Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, volume 148 ACM International Conference Proceeding Series, pp. 65-72. ACM, 2006. doi: 144444444.1433333. 143853. U / //o/i.//...././ www.orrg/1..... 110.1114111110 1143853
Maria-Floring Balcan, Andrei Z. Broder, and Tong Zhang. Margin based active learning. In Nader H. Bshouty and Claudio Gentile (eds.), ). Learning Theory, 20th Annual Conference on Learning The- ory, COLT 2007, San Diego CA, USA, June 13-15, 2007, Proceedings, volume 4539 of Lecture doi: 10. 10.10071978-3-544-72222 10000.10000000 540-2227-3372
Notes in Computer Science, pp. 35-50 Springer, 2007.
URL httttttss//oi..orgggt
Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Mach. Learn. 1007 11t11111111111190 0000 URL phttps:///dt
2010. doi: 10. 10.1007/110994400--117444
Kiarash Banihashem, Mohammad Hajiaghayi, and Max Springer. Optimal sparse recovery with de- cision stumps. In Brian Williams, Yiling Chen, and Jennifer Neville (eds.), -eventh AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Appli- cations of Artificial Intelligence, IAAI 2023, Thirteenth Symposium Educational Advances in
10

---

Published as a conference paper at ICLR 2026
Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pp. 6745 AAAI Press, 2023, doi: 10.1609/AAALV3376.55550 URL https: http://///...o.11111000000
aaai 1.7.6.258888
Dimitri Bertsekas and John N Tsitsiklis. Introduction probability, volume Athena Scientific, 2008.
Guy Blanc, Jane Lange, and Li-Yang Tan. Top-down induction of decision trees: rigorous guarantees and inherent limitations. CoRR, abs/1911.07375 2019. URL http://arxiv.org//aa
19911.0377
Guy Blanc, Jane I Lange, Mingda Qiao, and Li-Yang Tan. Properly learning decision trees in almost
polynomial time. J. ACM, 69(6):39:133::19, 2022.
doi: 10.1145/3561047. URL https://
doi. 10.
Leo Breiman. Random forests. Mach. Leam.., 45(1):5-32, 2001. doi: 10.1023/A11010033344433 URL /tttps://doi.orgg /ttp:///0....o0/00000////////1// /tt.:///.....0022221011001222220
Samuel Budd, Emma C. Robinson, and Berharrd Kainz. A survey on active learning and human-in
the-loop deep learning for medical image analysis. Medical Image Anal., 71:102062, 2021. doi: 10.1016/J 10.1016/J.MEDDA.20000 200.A..022..000000000
URL hittps://dos Perpiiorg/1C... 1016 htt.///.ei..../mmommmmmmm..eee.e medii a. 2021.
102062
Rui M Castro and Robert D Nowak. Upper and lower error bounds for active learning. In The 44th Annual Allerton Conference on Communication, Control and Computing, volume 2, pp. 1, 2006.
Rui M. Castro and Robert D. Nowak. Minimax bounds for active learning. IEEE Trans. Inf. The- ory, 54(5):2339-255 2353, 2008. doi: 10.1109/TT.222089991183 URL httphh:///ooiii... ott./do.ooog/....
1109/TIT 2008. 920189
Cheng Chen, Yi Li, and Yiming Sun. Online active regression. In International Conference
Machine Learning, pp. 3320-3335, PMLR, 2022.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Balaji Krishnapu- ram, Mohak Shah, Alexander J. Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi (eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 785-794 ACM, 2016. doi: 10. 444///99922.229977789 URL
Xue Chen and Michal Derezinski. Query complexity of least absolute deviation regression via robust uniform convergence. Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 1144-1179, PMLR, 2021. URL RoLLhttp:2 hhtt:::/pproeeee http:://prrcceeings. mlr. w.r.ppess//ee v
html
Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Alina Beygelzimer and Daniel Hsu (eds.), Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pp. 663 663.-69.11 PMLR, 2019. URL httt:::/proceeednnneee// htw.e/dddmm.m........eeesesseeee www.pppesssvvee chenl 9a. html]
mir
Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis (eds.), Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-Fiin First Annual Conference on Neural Information Processing Systems, Van- couver, British Columbia, Canada, December 3-6, 2007, pp. 353-360, Curran Asso- ciates, Inc., 2007. URL httptppss//prooeeiigggsssss mew.eedddiinnnn.nnn....eee. cccppaper/200//aat/t html
8f
Michal Derezinski, Manfred K. Warmuth, and Daniel J. Hsu. Leveraged volume sam- pling for linear regression. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, ral Information Processing Systems 31: Annual Conference on Neural Information Pro- cessing Systems 2018, NeurtPS 2018,
and Roman Gamett (eds.), Advances in Neu-
December 3-8, 2018, Montréal, Canada, pp-
11

---

Published as a conference paper at ICLR 2026
2510 2510-2519, 2018. URL http::///ppoeediiigg...o//s//spp 22266587764533352222222662200000
Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Inf.
Comput., 82(3):231-243 1989. doi: 10100160990-4401999900--11 URL https://doi,
org 000.01116/88800 5401 (89) 90001-1
Ran El-Yaniv and Yair Wiener. On the foundations of noise-free selective classification. J. Mach.
Learn. Res., 11:1605-1641, 2010. doi: 05555//776000118999900 URL htttt::t/////to acm.
/ttp//001110.555577556000000 1t117/550066111199999 1859904
Ran Yl-vaniv and Yair Wiener. Active learning via perfect selective classification. J. Mach. Learn.
Res., 13:255 2012. doi: 10.5555/250330822883944 URL, https://ddl acm. acm.org/
org/
doi
2188344
Di Feng, Xiao Wei, Lars Rosenbaum, Atsuto Maki, and Klaus Dietmayer. Deep active learning for efficient training of lidar 3d object detector. In 2019 IEEE Intelligent Vehicles Symposium, IV 2019, Paris, France, June 12, 2019, pp. 667-674. IEEE, 2019. doi: URL httph:tt: pettps://doi.oom org 1109 2019 8814236
Aarshvi Gajjar, Christopher Musco, and Chinmay Hegde. Active learning for single neuron models with lipschitz non-linearities. In International Conference on Artificial Intelligence and Statistics, pp. 4101-4113, 13. PMLR, 2023.
Aarshvi Gajjar, Wai Ming Tai, Xu Xingyu, Chinmay Hegde, Christopher Musco, and Yi Li. Agnostic active learning of single index models with linear sample complexity. The Thirty Seventh Annual Conference on Learning Theory, pp. 1715-1754. PMLR, 2024.
Leilani H. Gilpin, David Bau, Ben Z. Yuan, Ayesha Bajwa, Michael A. Specter, and Lalana Ka- gal. Explaining explanations: An overview of interpretability of machine learning. In Francesco Bonchi, Foster J. Provost, Tina Eliassi-Rat Wei Wang, Ciro Cattuto, and Rayid Ghani (eds.), Sth IEEE International Conference on Data Science and Advanced Analytics, DSAA 2018, Turin, Italy, October 1-3, 2018, pp. 80-89. IEEE, 2018. doi: 10.1 10.11 010..0001111
URL
https:///oi.. http://doi..rg/..... 1109////..119
Steve Hanneke. A bound on the label complexity of agnostic active learning. In Zoubin Ghahramani (ed.), Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007, volume 227 of ACM International Con- ference Proceeding Series, pp. 353-3601 ACM, 2007. doi: 10.1145/1773496.1273541 URL https://doo ottpp:://oi..org/0...111 114./ /tt.:/1222234111.55.... 1273541
Steve Hanneke. Activized learning: Transforming passive to active with improved label complexity. doi: 10.5555/2503308.2345666 URL https:
Mach. Learn. Res, 13: 13:1469-1587, 2012.
7/dl. acm. org/ doi wttp://o/0..555555533333333 w0w.0005555522502222.
Steve Hanneke. Theory of disagreementt-ussed active learning. Found. Trends Mach. Learn., 7(2-3):131-309, 2014. 2200000037
doi: 10.1561/22000000377 URL https:://ci.org//DD
Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan. Noise-tolerant, reliable tive classification with comparison queries. In Jacob D. Abernethy and Shivani Agarwal (eds.), Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], vol- ume 125 of Proceedings of Machine Learning Research, pp. 1957-2006. PMLR, 2020a. URL htttp//proceedi ngs mm www.mmlrrrrsre. wrw.s//essueee. wttpss/vv5////// http2///hhhphh22// htmm1
Max Hopkins, Daniel M. Kane, Shachar Lovett, and Gaurav Mahajan. Point location and ac- tive learning: Learning halfspaces almost optimally. 2020 IEEE 61st Annual Symposium
Foundations of Computer Science (FOCS), pp. 1034-1044, 2020b. URL https://api.
semanticscho wttp://cc........oooooo...aaa.a. :ttr://oorsss::2111.. 21::::16664999
org/
Max Hopkins. Daniel Kane, Shachar Lovett, and Michal Moshkovitz. Bounded memory active learning through enriched queries. In Mikhail Belkin and Samory Kpotufe (eds.), Conference Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134
12

---

Published as a conference paper at ICLR 2026
of Proceedings of Machine Learning Research, pp. 2358 2387. PMLR, 2021. URL http:// proceedings .ml.. htw.L/pp..e////11///oo.....
html
Matti Kääriäinen. Active learning in the non-realizable case. In José L. Balcázar, Philip M. Long, and Frank Stephan (eds.), Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, Spain, October 7-10, 2006, Proceedings, volume 4264 of Lecture Notes in Computer Science pp. 63-77. Springer, 2006. doi: 10. 1894841) 9. URL https: 7/doi. wrw.//rrg11... 100 10100000001//010
Daniel M. Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang. Active classification with com- parison queries. In Chris Umans (ed.), 58th IEEE Annual Symposium Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 355-366. IEEE Computer Society, 2017. 2017.400
doi: 10.1109/FOCS.2017
URL https: /ttp:://doo..o www.ddoo.orgggoooo 1109/0000.........
S. Jalil Kazemitabar, Arash A. Amini, Adam E. Bloniarz, and Ameet Talwalkar. Variable importance using decision trees. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Ad- vances in Neural Information Processing Systems 30: Annual Conference on Neural In- formation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 426 435, 2017. URL
meurips.... CC paaprr/2017/et Abstract html
Jean-Samuel Leboeuf, Frédéric Leblanc, and Mario Marchand. Decision trees as parti- tioning machines to characterize their generalization properties. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neu- ral Information Processing Systems 2020, NearlPS 2020, December 6-12, 2020, vir- tual, 2020. URL htttp::/pproceeddngg..eell http://w....urresooccp/////////a cc//paper/222//haa..
Abst html
Liyao Ma, Sébastien Destercke, and Yong Wang. Online active learning of decision trees with evidential data. Pattern Recognit, 52:33-45, 2016. doi: TT1.://.AATCO..001....
URL
htt..//oo/g....111.paa.aa.o.o 2015: 20.0...01.......................
Dinesh P. Mehta and Vijay Raghavan. Decision approximations of boolean functions. Theor,
Compul. Sci., 270(1-2):609-623,, 2002. doi: 101006/50004-37550000011111 URL https:
10. //ool.oorg/101111////53333
(01) 00011-1
Cameron Musco, Christopher Musco, David P. Woodruff, and Taisuke Yasuda. Active linear regres- sion for bp norms and beyond. In 63rd IEEE Annual Symposium on Foundations of Computer Sci- ence, FOCS 2022, Denver, CO, USA, October 31- November 3, 2022, pp. 744-753, IEEE, 2022. 1ww.11119100C 10.1100/000054455. doi: 10. Lt..100FOC55445..222200000 00076. URL https: /tap:::/ddo:: org htt.://111111111.111 0122.00077
Aditya Parulekar, Advait Parulekar, and Eric Price. L1 regression with lewis weights subsam- pling. In Mary Wootters and Laura Sanità (eds.), Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16- 18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 LIPIcs, pp. 49:1-49:21, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021. doi: 10.4230/LIPICS. AAW.LIIICSSPPPPOOAAAAAAA APPROXRANDOM.222 LIPICS A.PIcs.APPROK. APPROX/ RANDOM. 2021.02222000 .99
URL
42307
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM Compur. Surv, 54(9):180:111880) 2022. doi: 10. 10.1145/3472291. URL | 1ttp///00111//47223939
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEEE Symposium Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley. California, USA, Proceedings, pp. 143-152. IEEE Computer Society, 2006. doi:
D0.1009/FOSS2006.333 URL WtRL.ttts::.... /tw. / /10. wtt.//....0///...........1 2006.37
13

---

Published as a conference paper at ICLR 2026
Christopher Schröder and Andreas Niekler. A survey of active learning for text classification ing deep neural networks. CoRR, abs/2008.07267, 2020. URL httph::////// /tt//aaivvvi.o// wwwxiv.org/eee /bs/
0008.07267
Burr Settles. Active Learning. Synthesis Lectures on Artificial Intelligence and Ma-
chine Learning. Morgan & Claypool Publishers, 2012. ISBN 978-3-031-00432-2 doi: 002200000222DD00000022200 5504499D1100122200777A..0
URL bttp:://aci.orc/110..
Edward Charles Titchmarsh and David Rodney Heath-Brown. The theory of the Riemann zeta- function. Oxford university press, 1986.
Shuo Wang, Jianjian Wang, Xiang-Hui Gao, and Xue-Zheng Wang. Pool-based active learning based on incremental decision tree. In International Conference on Machine Learning and Cy- bernetics, ICMLC 2010, Qingdao, China, July 11-14, 2010, Proceedings, pp. 274 278. IEEE, 2010. doi: 10.1100/CML.222005558810 2010. 5581052
URL
http:///.oooo./....// 1ttp:///..111///IMMM ICMIC.
David P. Woodruff. Sketching as tool for numerical linear algebra. Found. Trends Theor Comput. Sci., 10(1-2):11157, 2014. doi: /140000000000000 URL. https:///es org//0..116
04000000601
Zhixiang Eddie Xu, Gao Huang. Kilian Q. Weinberger, and Alice X. Zheng. Gradient boosted feature selection. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang. and Rayid Ghani (eds.), The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 14, New York, NY, USA August 24 27, 2014, pp. 522 531, ACM, 2014, doi: 10.1145/262333022226666 23222623333300.2663... URLhttps: doi org 10. 1145 211111//22333333 222333
Zhisong Zhang, Emma Strubell, and Eduard H. Hovy. A survey of active learning for natural language processing. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceed- ings of the 2022 Conference on Empirical Methody in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pp. 6166-6190. Associa- tion for Computational Linguistics, 2022. doi: 10.18653/V1/0222 EENLP-MAIN https: wtt..o.0.....1111/22221.1 emn main. 414
URL
APPENDIX OUTLINE
In Appendix A we explain how to calculate the lower and upper bounds, LB and UB, in general. Next, in Appendix A. specifically determine these bounds for stumps, and in Appendix A.2 we determine them for decision trees.
Then, we present the proof's of the theorems and lemmas from the main body, starting with the proofs of Section i. Appendix B Specifically, we first provide some required lemmas. In Appendix B.] then provide proofs for Theorem
which proves that Algorithm T is correct. Later, in Ap- pendix B.2 we prove Theorem 4.1 which determines the label complexity of Algorithm| [ Finally, Appendix B.3 we prove Theorem 4.3 which provides a lower bound on the label complexity of any active learning algorithm.
In Appendix C we provide the proofs for the theorems in Section 4.3 We first introduce and prove some required lemmas, which serve as the foundation for proving Theorem 4.4 and Theorem 1.2 These results establish the correctness of Algorithm and and analyze its label complexity, respectively.
In Appendix D we provide proofs for the lemmas introduced in Section 3 After proving these lemmas, we proceed to Theorem T.1 and Proposition 3.5) which calculate the disagreement coeff- cient for decision trees and line trees, respectively. In Appendix D.II we present the proof of our main result, Corollary 1.3] which calculated the label complexity of our algorithm for a decision tree. Additionally, in Appendix D33 we provide proofs of the necessity of our assumptions, i.e., Theorem 3.6 and Theorem (.7] Finally, in Appendix [D.4] we show how you can partially relax the uniformity assumption, though not remove it entirely.
In Appendix E we explain why additive algorithms fail multiplicative setting and explain the relation between additive and multiplicative settings and algorithms.
14

---

Published as a conference paper at ICLR 2026
In Appendix F present empirical analysis of our Stump algorithm, showing that, in practice, small values for c1, C2, b1, and b2 can be chosen while still ensuring the algorithm performs as intended.
TABLE OF NOTATION
For convenience, we provide summary of the key mathematical notations used throughout the algorithms and analysis in T
Symbol
Description
S.n n h" R(m,S)
The dataset S and its size n.
The hypothesis class (e.g.. decision trees).
The optimal classifier in H (minimizes classification error).
A uniformly random subset of S of size m (sampling without replacement).
errs(h)
The empirical error of classifier on set S: [S] Σ E(awhes I(h(x) # y)-
Ds(h,W)
The distance between two classifiers: fraction of points in S where they disagree.
r
The ball of classifiers in H within distance of h.
(V):(V)
The disagreement region: points in where at least two classifiers in V disagree.
0 VH
The disagreement coefficient.
The VC dimension of the hypothesis class H.
(B(S,
Lower bound on the error of h with confidence 1 5. Upper bound on the error of h with confidence 1 5.
UB(S,
Table 1:
Summary of notation used in Algorithms and
A CALCULATION OF ERROR BOUNDS
In this section, formally define the error metrics used to derive our bounds. For hypothesis h and a target dataset (or subset) S, we denote the true error as errs(h), representing the fraction of misclassified points in S:
errs (h)
1
I(h(z) + y) (2.0)ES
Σ
S
When the algorithm draws a random subsample S S. we calculate the empirical error eîr(h) restricted to this sample:
etr(h)
Σ
I(h(x) A
(R.v)ES'
Our algorithms do eîr(h) directly for pruning; rather, they rely high-probability Lower Bounds (L.B) and Upper Bounds (UB) derived from err(h) to estimate the true error errs(h).
To compute the lower and upper bounds (LB and UB), we leverage the following theorem from An- thony & Bartlett (2002); Balcan et al. (2006):
Theorem A.1. Let be a hypothesis class of functions mapping from X to {-1, 1}, with a finite VC-dimension VH 2 1. Let D be arbitrary, but fixed, probability distribution over X 111,1).
For any e, > 0, if a sample is drawn from D with size
12 (12)
(1))
m(c, 8, VH)
2VH In
then, with probability at least 1 8, the following holds for all h E H:
lerr(h) eir(h)) s
15

---

Published as a conference paper at ICLR 2026
derive the enror bounds. From the theorem, know that (enr(h) eir(h)] I c. Consequently, we can define the lower and upper bounds as follows:
Using Theorem A.1
LB(h) = eir(h) - and UB(h) = cir(h) + E.
These bounds are valid with probability greater than - 6.
A.1
STUMP
For decision stumps, the VC-dimension Vi known to be I, as established in Lemma A.2 Hence, applying the formula for sample size in Theorem A.I obtain the following sample size require- ment:
256
24 (24)
(1) )
m(c, 8) =
2
In
22
After sampling, compute the empirical error for each classifier. Subsequently, we define the lower and upper bounds for each classifier as:
(h = eir(h) 2 and UB(h) eir(h) (h) +
This guarantees, with probability at least 5, that for all hypotheses h, the following holds:
(B < err(h) < UB(h),
and additionally, the width of the bounds is exactly c, i.e., UB LB(h) =c
Lemma A.2. Let H denote the hypothesis class of decision stumps in one dimension, where each hypothesis h E H assigns the label to points exceeding threshold 0 IR and 0 otherwise. Then, the VC-dimension of H is
Proof. To prove that the VC-dimension of 7 is 1, we must show that there exists set of one point that can be shattered by H. but no set two points can be shattered.
Shattering single point: Consider single point 21 E R. By choosing appropriate threshold we can label #1 as either 0 or Thus, set one point can be shattered by H.
Inability to shatter two points: Now, consider a set of two points, 21, R with 21 T2- There are four possible labelings: (0, 0). (0, 1), (1, 0), (1, However, the labeling (1,0) cannot be achieved. If we choose threshold 0 such that 21 < 0 < 22, we obtain the labeling (0, 1). If we choose 0 < æ1, we get (0, 0), and we choose 2 Z2, we obtain (1, 1). Since (1, 0) is impossible, the set {x1, 22) cannot be shattered. Therefore, no set of two points can be shattered.
Since there exists a set of one point that can shattered, but no set of two points can be, the VC-dimension of H. is 1.
A.2 DECISION TREE
The VC-dimension, Vи, of decision trees with height at most d in dim-dimensional data is O (d + In dim)). as established in Leboeuf et al. (020)). Utilizing this, along with Theorem A.1 we can achieve error bounds where UB(h) LB(h) Se with the following number of samples:
o
1 ã
2d (d + In dim) In 1 In 1
More specifically, using Lemma
A.3 and Theorem A.1 we require:
256
24
20 2d(d log, dim) In (7))
In
?
3
samples.
Lemma A.3. Let H be a decision tree of height at most d, where each node uses one of dim 2 data dimensions. The VC dimension of H, Vnt is at most 10 2d log, dim).
16

---

Published as a conference paper at ICLR 2026
Proof of Lemma A.3 Based on Leboeuf al. (020)) the VC dimension Vи satisfies VH I max(m (14m dim) 2 2nm), where dim is the number of dimensions and N is the number
of internal nodes. For height d, N I 2d 1. Thus, Vи S max(m (14m dim)="-1 >
). If (14m dim)2" 2mh we simplify by assuming m 2d log, dim)c and get 14dim (d log, dim)c 2 2od+ dimje Dividing by 24, we derive:
14dim(d + loga dim)e 2 "dlee1)dim"
For 10, this inequality fails, since
1d + log, dim) 2 2h(ce11) dim
dim" =2 dim
dim + (dim" - dim).
Here, logg and logg (140) & < 8d (c 2)d, implying (1gg(140) + logz d d (c- 1).
Therefore, 140d (d-(e-1) Adding dim to both sides gives:
140d dim 22-(c-1)
Since dim > 2. and logg dim dim we get: log, dim < dim dim (e (dim 1). Adding 140dim to both sides and noting S dim we get
140dim log, dim < 140dim (a0ddim-'(d-- (d-1) < 2 dim 0-1 (dim - 1) 2d dim f- (dim - 1) <
g dim "dimm 1) 2c dim
Hence:
14dim logg dim << 2<= + Vn S 10-24 2 (d logg dim).
B STUMP PROOFS
In this section, we present the proofs associated with Section 4.1 which pertain to Algorithm D These include proofs of correctness and label complexity. Additionally, we establish lower bound for the label complexity of any active learning algorithm.
We begin by proving that the loop in Algorithm repeats at most (2g)(2n) times.
Lemma B.1. In the execution of Algorithm 7 we enter the loop at most loga times.
B. At the start of the algorithm, we have R; L; n, and this value is halved in each iteration. When it reaches the algorithm terminates- either by entering the If statement or by reducing R²- L, to 0. Therefore, the number of iterations is at most logg(2n)
Proof of Lemmal
To prove Theorem we need to establish that all lower and upper bounds are valid during the algorithm's 's execution simultaneously with probability at least 8.
Lemma B.2. In an execution of Algorithm i all estimated lower and upper bounds valid with probability at least 8. 8.
Proof of Lemma B.2 From Lemma B.1 we know that the bounds outside the If statement are evalu- ated at most log2 (2n) times. Each time, the bounds are correct with probability at least 1 - 8'. Thus, the probability of a bound being incorrect is less than 8'. Therefore, the probability at least one bound being incorrect is less than 8' (ogg(2), Using the definition of d', we know 8' (2og
so we have 8' logz
5
Additionally, the bounds inside the If statement are evaluated only once, and the probability of them being wrong is less than Combining these two factors, the overall probability of any bound being incorrect is less than 5.
Next, must prove that the optimal classifier is never eliminated if all bounds are valid. This is formalized Lemma B.4] which builds upon Lemma B.3 Since we estimate the error using ran- dom samples from the disagreement set rather than the entire dataset, must first relate the emror
17

---

Published as a conference paper at ICLR 2026
of classifiers in the disagreement set to their overall error. Lemma B.3 establishes that the error rela- tionship between two classifiers remains consistent across the disagreement set and the total dataset if all the samples on which they disagree are contained within the disagreement set. Specifically, if one classifier has a larger error within the disagreement set, it will also have a larger error on the total dataset. Consequently, the optimal classifier within the disagreement set is guaranteed to be the overall optimal classifier.
Lemma B.3. For two classifters hy and h2, if we have errs I (12), then for any subser of samples S' containing all samples where hi and b2 disagree, Le., {ar E S ha(x)) h2(x)) S S', we will have errs (h1) S errs (h2).
Proof of Lemma B.3 Applying definition of err, to our assumption errs S ehrs( we have:
Σ
(1)
Σ
I(h2(a) + fy)
(2,y)ES
(x.0)
Now, splitting into S' and its complement S'S':
Σ +1)+ (x.y)ES*
E (1n(
Σ
+1)
I(h2(x) + y)
(S
(x.9)ES²
(x.9)ES),5)
Since S' contains all the samples where hi and h2 disagree, the error S S' will be identical for both classifiers. Therefore:
[(h S Σ
I(h2(x) + v)
(N.))S
(2.8))
Hence: errg: (l)) Σ (hz)
Lemma B.4. If all bounds in the execution of Algorithm 7 are valid, the algorithu will never elimi- nate any optimal classifiers.
We prove by contradiction. Suppose that there exists an iteration in which an optimal classifier h" is eliminated, while all bounds are valid in that step. This implies that h" E [T R4-1] but h* & [T,, Rs). Thus, we have:
Proof of Lemma B.4
LB LB(S,, h", h8)h"""'""""" AE|L
min
hB,
Let W be the classifier such that: minke UB(S;, h,)") UB(S,, N',8', Then: LB h², 8') > UB(S,, 8*).
Let S' be the set of all samples in the range of valid classifiers, S'e = (X Since the bounds are assumed be correct, we know:
esTg (h*) 2 LB(S, > UB(S,, 2 erry (h')
(2)
Since both h² and W belong to the interval [T4-1: R4-1], we know that [Tg-11- R₂-1] contains all the samples where h² and h disagree. Given that h" is the optimal classifier, we have: errs(h") < errs (1t).
Using Lemma B.3 cannot be eliminttdd.
conclude: er"s:(h") S errs (h'). This contradicts Inequality 2 Thus, h*
We now aim to demonstrate that classifiers far from h" have high error rates on N,), ensuring they will be eliminated by ht. This claim is formally established in Lemma BB3 Lemma B.5. For all h E [Li R.), in any iteration i, the following inequality holds:
R.).
11 h²|
errxy,, (h)
R. L, +1 -erxx (h"),
18

---

Published as a conference paper at ICLR 2026
Proof of Lemma B.5 We begin by recalling the definition of the error function ej,, (x))
(ft):
eITX (h)
1 R, L, JE
E
I(((X)) xY)),
Without loss of generality, assume that h ht" This assumption allows to focus the data points where h and ht make different predictions. and h differ in their predictions on samples X,. where h $ J ht. Also, let M denote the number of misclassifications made by both h and he outside the range [h, h"),
). but [[,, Ra]. Since and h* behave identically on samples outside the range [h, h*), their misclassifications outside of the range equivalent.
Thus, the error of h can be expressed as:
eIT X R.) (h) R. - L,+
I(h(X)) ,,) + M jElA,N))
Σ
Because h and make different predictions on X, for E [h,h") we have:
(1 (X,) + M jE(h,A")
eIT XTT R. Li +1
Here, Ejelh,n- 1 counts the total number of samples in X[I.>>>, while Σ Eje(n, [X," # Y2) counts the number of misclasiifications made by h". Simplifying further:
ht*
2M
err R, (N) = R: L +1 R. - +1
+ R; - L, +
jE((,b")
Given that M represents the number misclassifications made by h" outside [h, h²), the error of h" can be expressed as:
1
( (h²) (h") Li +
I(h' x3) + M
jElk,
Substituting this into Equality 3
1/2 1-1
2M
etT e n.l (1) Ri T, +1
emrx R.) (11)+ + R. T.
Since M > 0, it follows that:
1/ h²
eIT R.) (h) 2
eIT ( (h*).
R. L, +1
This completes the proof of Lemma B.5
We now prove that if the optimal classifier's error is sufficiently low XII--.R,-.l the algorithm can successfully reduce the range [4,-1, R2-1] to half its size in [L, Rz). Lemma B.6. There exist universal constants C₁ and by such that in Algorithm 7 if at some iteration i, errx erxx 1. then we have:
R,-L, R 1
provided all lower and upper boundy are valid during the algorithm'ss 's execution.
19

---

Published as a conference paper at ICLR 2026
Proof of Lemma B.6 We aim demonstrate that all classifiers with distance greater than Ri-1 La-1 from h" will be eliminated by h" itself.
Define S" as the set of all samples within the range of remaining classifiers iteration i - 1, so S' - - 1.R
Given that emry e pendix A.I that for all h,
18 and by examining labels of ej & + bı samples, follows from Ap-
LB(S,, h²) ents, (h) UB(S,, and UB(S, h" LB(S,, 1
16'
provided that
256 (2 In (24) + In( (n() ai In 1 bi.
)
which will be satisfied by large enough ei and b₁. Thus, for h², we have:
1
1
UB(S,, 88) < (hT) +
16
16
Using Lemma B.5 it follows:
1h h"1
errs 2 R4-1 L1-1+1
eITss(h)) >
4
16
16"
Therefore,
3
1
LB(S,, h 8')
16
16
Hence, all classifiers h such that Pi-1 11-1-4-1111
<
h h*| will be eliminated. From this, we
determine that R₁ (H,) ht- R: -i 1+1 and L, min(H.) > h R. 1 1+1
Therefore, R. L; < Ri-1- -
Next, demonstrate that if the algorithm enters the statement and the optimal classifier has high error in the disagreement range [L,-1, R,-1], the algorithm will produce a sufficiently accurate classifier.
Lemma B.7. There exist universal constants and be such that if. in Algorithm 7
we have
eT (h*)
16
and the algorithm enters the If statement, It will return classifier like h with
errg(h) (1 c)errs(h");
provided that all lower and upper bounds are valid during the algorithm's 's execution.
Proof of Lemma
B.7 When Algorithm
Tenters the If statement, it constructs the set S', comprising:
in
+ b2
de
random samples drawn from the interval X X 1.;;
Let ht' denote the classifier returned by the algorithm, i.c.,
6 h' arg min UB(S', h1 ) he[L..R.]
From Appendix A.1 with sufficiently large 0 and by, it follows that for all h [L,, R.]:
UB(S', h, ;g) err eIT (h) + 16'
20

---

Published as a conference paper at ICLR 2026
Since h is chosen to minimize the upper bound, we know: UB(S', h1, 2. S UB(S', h2, 2). Thus:
(I (h') - UB(S", h', & 2 UB(S", hi, 1 2
s e - 16
From the definition of the error metric err, we write:
1
Σ I(H'(X)) * *X,) RI-1 1--1+ +1
Σ
1(((()) +
RR-1 4--1 -
16
Multiplying through by Ri-1 Li-1 1, we obtain:
Y,) + (R
L5-1 + 1)e
Σ IX
+ y3) S
Σ
16
JE(L:-1.R,
JE(LE-1.,
Outside the interval [15-1, R5-1]. 1 and h behave identically. Let M denote the number of samples they misclassify outside the interval [L--1, R Adding M to both sides:
((,)(x)) +Y,) (R - 11-1 + 1)e
M +
Σ T(N((,)) * Yj) s M +
Σ
16
JE(L--1.R-1I
Thus,
(X,) +Y) + (R Li-1 + 1)e
[I(((X)) # #Y))
Σ
16
JES
JES
Dividing both sides by n, and using the definition of emts obtain:
e S errs(h") + (Ri-1 Li-1 + 1)
(4)
n 16
From the assumption that the error of ht on the interval [I,-1, R is greater than 1
we have:
I6
R
- L--+ < errs(h")
= (R--1 - Li-1 + 1)
S erts (h"))
16
n
16
Using this inequality and substituting into Incquality we find:
errs(h') S errs (1 + c).
Hence, the algorithm returns a classifier h that satisfies the desired error bound.
B.1 PROVING ALGORITHMM 1 IS CORRECT
In this section we prove Algorithm is correct, meaning it returns (1 + -)aaprooxee decision stump with probability at least
Proof of Theorem 4.2 We start by noting that, by Lemma B.2 with probability at least 1 - 5, all lower/upper bounds calculated during the execution of Algorithm are valid. Furthermore, accord- ing to Lemma B.4 if these bounds are valid throughout the execution, the optimal classifier will not be eliminated at any point.
Thus, if the algorithm never enters the If statement, it will return the optimal classifier.
On the other hand, if the algorithm does enter the If statement, we can reason as follows: From Lemma B.6 we know that entering the If statement implies that the error of the optimal classifier in the interval L,-1; R2-1] is greater than T6
Furthermore, by Lemma
B.7 we know that if the error of the optimal classifier in [IL.RR.) exceeds
then:
errs(h') & emr(hh) (1 c),
21

---

Published as a conference paper at ICLR 2026
where ht is the optimal classifier and h is the returned classifier. This ensures that the classifier returned by the algorithm is an acceptable approximation to the optimal classifier.
Thus, have shown that the algorithm will always return acceptable classifier, either by directly outputting the optimal classifier or by returning classifier with an error bounded by (1 + e) times the error of the optimal classifier.
B.2 ALGORITII PIBORITIMMLABEEE LABEL COMPLEXITY
In this section we prove Theorem which bounds the label complexity of Algorithm
Proof of Theorem 4.7 By Lemma B.1 we know that the loop in Algorithm will execute at most logg 2n times. In each iteration, the algorithm queries at most the following number labels:
c In 8 + b, = c In logg
2n
+ b
algorithm enters the If statement, will check additional labels size:
1
+ bb))
Ed
Thus, the total number of label checks performed is bounded by the sum of the iterations:
(1 In
log2 2n
C2 In
log2 2n
+ b1
+
by
2
This expression simplifies to:
1 o 0 Inn Inlnn + In
In 28
7)
B.3 LOWER BOUND ON LABEL COMPLEXITY FOR ACTIVE LEARNING WITH STUMPS
In this subsection, establish the tightness of the provided algorithm by deriving lower bound on the number of queries required for active learning with decision stumps, while ignoring logarith-
mie factors. Specifically, we present Theorem 4.3 which states that at least O Iu queries are necessary to obtain (1 + -)approoximate decision stump with probability greater than 1 1-6. 6.
Proof of Theorem 4.3 We proceed by applying a well-known result from statistics, which states the following theorem Kääriäinen (2006).
Theorem B.8. Given biased coin with a head probability of either - or 1 +λ, at least Z Iu
coin tosses are required to determine with probability at least 1 - 8 which side the coin is biased toward.
To prove Theorem 4.3 we will leverage Theorem B.8 and demonstrate that the problem of deter- mining the bias of the coin can be reduces active learning algorithm attempting solve this problem.
We proceed by contradiction. Assume there exists algorithm A that returns (1+e) (lpe)-appoxximate classifier, where the classifier's 's error rate is less than errs(h (h* + c) with probability at least 1 - 8', using fewer than In 3 queries.
Now, consider a biased coin whose head probability either 1 or A. We construct the dataset { 1 < < n² and assign labels to it as following. For each data point, we toss the coin and report label of 0 if the coin lands heads, and if it lands tails.
22

---

28 Published as a conference paper at ICLR 2026
Claim B.9. If h' is the optimal stump classifier over D. for sufficiently large have
P ((ems(h')) -
A 2 1 8 2 2
Proof of Claim B.9 Without loss of generality, suppose the coin is biased toward heads, meaning the labels biased toward O. Let bu be the classifier that assigns 0 to all points (i.e., its threshold 1). Then:
P ( -
A 2 2
1 (ho) _ 2
errs(h") (ho)
Since ho misclassify all samples with label 1 and correctly classifies all samples with label 0, we have crTs(h)) x number of labels 1.
The number of labels equal to follows Binomial distribution with parameters and 1 A:
number of labels 1 Binomial(n, 1 -A). A).
Therefore,
A 2 2
1 A
1 A
P (h")
2 P
(rrss(h) S
Binomial A)
We now bound the right-hand side using Chernoff's inequality Bertsekas & Tsitsiklis 2008 implies:
which
2
1 A) < ( - (1+ 1- 2\ P Binomial(n, 2
A )
1-2X
A
n
(
A)
2 1 exp
+ 1-2X
By increasing n, we can make this probability greater than
Now we apply algorithm A with parameters c c 2/ and 8' = to dataset D to classify based on its labels.
Claim B.10. The algorithm A will return classifier with error less than ( {) (1 (1++) with probability at least
3
Proof of Claim B.10 This follows from the B.9 that with probability at least 1 6
3- we have
errs(h" < 2 2. and the fact that algorithm A returns classifier with error less than errs (h") + c) with probability at least 6 As result, the error of the returned classifier
less than (} }) (1 + e) with probability at least (1 - (
3
Claim B.11. the coin is biased toward heads (i.e., labels are biased toward 0), then for sufficiently large n, all classifiers with threshold less than 1/2 have error higher than
(
8
(1+))
with probability at least
3
Note that the similar statement holds for the case where the coin is biased toward tails as well.
Proof of Claim B.ll
To prove this, we proceed as follows:
{1_ A (1 (1+e))
P 3 B53 (h)) <
<
Σ
errs (h) S
(1 +
2
h<
23

---

Published as a conference paper at ICLR 2026
Substituting À = 3c, get:
1
3
2 2 (1+
2 c-
-
2
2
Thus,
(1 - (1 (1+)) 2
Σ
P CITs (h) < h<
Σ P b<
etty (h) 2
For every h where < 2. its probability term the summation can be upper bounded as
follows. Let us define: Z == n(errs (h)) 4T;, l ~ Bin(i, 5 -), ~ Bin(n- +
Then have:
errs (h) - - ) 2 s ml ml
Using the multiplicative Chernoff lower bound Bertsekas & Tsitsiklis (2008) on the variable for x -)) where μzz
i {(} >) + (n () +
2 + >(n 21), this probability is
Pz bounded as follows:
Pr|Z (1- a)uzl s exp uz 2z
Substituting and pz will result in:
(nz n =))² fz
Pr Z s (1 - (1-a)uz) Pr 25 n(2 -o] exp uz a²) cxp
n + Xn - -2)):
Using μ4=
2
X(1 21) + 1
(12 nl} -c))²
n.
exp
exp
I exp(
2 pz
212 + X1 ]]
2( + X)
To summarize the result so far, we have proved that for every h - t:
1 -c) - s exp( n.
P errs (h) S
2(} + A)
Finally, doing summation over all h will get to:
Σ P errs (h) s 1 - c)
2 - s exp( n c² 2( + 2)
1
h<
The last inequality holds for any sufficiently large n, because n grows linearly but exp( n-e2 decreases exponentially, making the entire term small as desired.
2 + A)
Now, based on Claim B.10 the algorithm A returns classifier with an error rate of less than
(2-2)
A (1+c)
with probability greater than 1
28. Moreover, based on Claim B.11 all classifiers on the wrong
side of & have greater than (} )) e) with probability greater than 1 - Thus, with
24

---

Published as a conference paper at ICLR 2026
the probability at least (1 - 51) ) 2 1 8, the returned hypothesis h can indicate whether the coin is biased toward heads tails, by choosing "heads" if h 2/ and "tails" if h 1 However, as established in Theorem B.8 any algorithm requires at least 9SS In (+)) algorithm A needs least:
samples. Therefore, the
X
2 In
samples to achieve this.
C GENERAL BINARY CLASSIFICATION PROOFS
In this section, we provide the proofs corresponding to Section where we extend our algorithm to general binary classification tasks as described in Algorithm The structure of the proofs closely follows the approach Appendix
To facilitate understanding the general classification algorithm, we first presented the case for stumps. Table outlines the correspondence between lemmas and theorems the stump case and their general binary classification counterparts.
Table 2: Correspondence between Stump and General Binary Classification results.
Description
Stump Version
General Binary Classification Version
Body section
Section
Section
Proofs in Appendix
Appendix
Appendix
Algorithm
Algorithm
Algorithm
Algorithm Correctness
Theorem
Theorem
Time Complexity
Theorem
Theorem
Number of Iterations
Lemma
Lemma
Bounds Validity
Lemma
Lemma
Error Comparison
Lemma
Lemma B
Optimal Classifier Not Eliminated
Lemma B.
Lemma
Lower Bound Error with h*
Lemma
Lemma
Low Optimal Error - Reiterate
Lemma
B.6
Lemma
High Optimal Error - Correct Output
Lemma
Lemma
We begin with the following lemma, which establishes that the maximum number of iterations in the loop of Algorithm i is bounded by (2m).
Lemma C.1. Algorithm will execute the loop at most log, 2n times.
Proof of Lemma C.7 Initially, have ro During each iteration, if the inequality r; > holds, the algorithm terminates immediately. Thus, for the loop to continue, it must be that T; <
If any point r 1, no two classifiers in the set H; can disagree on any samples, leaving only single classifier to be considered. In this scenario, the algorithm will again conclude. Therefore, the execution of the loop cannot surpass the threshold of iterations where r; becomes smaller than n'
n
Consequently, the number of iterations required is at most:
+ log,
logz 2n
We need to show that all lower and upper bounds valid during the algorithm's execution with probability at least 1 - ō, simultaneously.
Lemma C.2. In an execution of Algorithm g all estimated lower and upper bounds are valid with probability least
25

---

Published as a conference paper at ICLR 2026
Proof of Lemma From Lemma C.I we know that the bounds outside the If statement are evalu- ated at most logg 12 times. Each time, the bounds are correct with probability at least 1 - 8'. Thus, the probability of bound being incorrect is less than 8'. Therefore, the probability of at least one bound being incorrect is less than 8' logg(2n) Using the definition of d', we know 8' (2n)
so we have (2n) =
Additionally, the bounds inside the If statement are evaluated only once, and the probability of them being wrong is less than L. Combining these two factors, the overall probability of any bound being 28
incorrect is less than 8.
The following lemma establishes that if hed E H', then H' S BB(h", 2radius(!!'), Consequently, this implies that during iteration i, when the radius is radius(H;;) all classifiers in H; are at most distance of 2radius(Fi H.) from h".
Lemma C.3. Hf C (B(hhr) r) and h E H', then H' C BBu(h'2rr))
Proof of Lemma C.3 We aim to show that (h(, S BH(h', 2r). Consider any lt" E (b(h, By definition, we have: Ds(h, h²) S which implies: r 2 + Eves (((()) + (x))) Similarly, EEES [(((a) M(x))-
since h By (h, we have: Ps(h, hf) S r, which implies: Adding these incqualities gives:
2r
2
(Th(()) ( + M(6)) I(M()) + (x)))
72 BES
Notice that: I(h(x) * 1((x)) + I(h(x) * h((x)) > I(N(z) + h²(z)) Therefore, we have: 2r 2 ni Enes (1h((x)) + (x)). Thus, by definition of Ds, we conclude: 2r 2 Ds('', h") Hence, any h" E (h, is also in Bu (h
The following lemma helps us relate Ds J²) to DDIS(H:) h²). This relation important be- cause the final error is measured in S, but we randomly sample from DIS(H") which leads to bounds on DDISHH))
Lemma C.4. If D') 2 y for some r. and h, W. E H' where H' C Bu (h, 2r), then
DDIS(H (h,, ht') Bn 2r 2'
Proof of Lemma C.4 Given that all samples where and h' disagree are in DIS(H'), the number of disagreements in DIS(H') is equal to those in S. From the definition of Ds and since all disagree- ments are included, we know:
DDIS( (h)
Σ #EDIS(H))
I(h(x) + h((x)) [DIS(H))
ΣI((2)) # Nx()))
DIS (H')
aES
Thus,
|S| DDIS (h, (h,h') [DIS(H') (H')
(1S) II((a))+M ( +k()))
|S|
[DIS(H)) Ds(h, h²)
SS]
#ES
By assumption Ds(h, h²) 2 Y/2 and since H' S (h, 2r), it follows:
1
DDiSCH' (h,))))
B (h, 2r))
2
26

---

Published as a conference paper at ICLR 2026
The following lemma ensures that optimal classifiers eliminated if all bounds during the algorithm's 's execution are correct.
Lemma C.5. all bounds during the execution of Algorithm 2 are valid, the algorithm will eliminate any optimal classifiers if all lower/upper bounds are valid.
Proof of Lemma C.5 We use proof by contradiction. Suppose there an iteration where an optimal classifier h is eliminated despite all bounds being valid. This implies ht E Hz but h" & H1+1, which means: LB(S,, ht" , 8)) > min UB(S;, h, 8'). Suppose h achieves the minimum: mi UB(S, h, 8') UB(S,, h', 8'). Thus, we have: LB(S,, h" 88) >> UB(S,,
Let S" = (H)) With the validity of bounds:
errs (h*) 2 LB h 8') > UB,S,, 8', > errs (h))
(5)
Since h² is optimal, know e (h") e From Lemma B.3 this implies: emr:-(h)) S er (h'). This contradicts inequality thus proving that an optimal classifier cannot eliminated if all bounds are valid.
The following lemma bounds the error of classifier h. based on its distance from the optimal clas- sifier h" and the error of h" Specifically, it shows that if far from h² and h" has low error, the error of h must be high, leading /t to be eliminated.
Lemma C.6. For all h, h" E H', the following inequality holds:
errDis(ur 2 Ch, h²) errDis(H (h").
Proof of Lemma
C.6 From definition of the error function errDis HP) (h))
erTDIs(H) (h) DIS(H')
Σ
I(h(X,) + Yj),
jEDIS(!!)
Define S' as the set of samples h and h* makes different predictions. So S' = fz E S h(x) + h" h=)).. Since all samples that h and h" makes different predictions are DIS(H'), S' C DIS(H'). Assume h makes M misclassifiaatios in DIS (H'H)/S'. Since ht behave identical to h on these samples, h² also make M misclassifications DIS DI'SH')
Thus, the error of h can be expressed as:
e(Tnis(rr
Σ I(h(X,) *1,) M JES'
DIS(H'I
Because h and lt make different predictions on X, for j E S", we have:
(E II, + M
HrTDIs(Hr)()) (h) (DI((H))
JES
Here, Ejes' 1 counts the total number of samples in S", while Ejes (Xh # Y,) counts the number of misclassification made by h² in S". Simplifying further:
SS'
2M DIS(H')
( (DI(H')) [DI(('))
Σ I(h~(X)) * Yj) JES
+
(6)
Given that M represents the number of misclassifications made by h² outside S', the error of h can be expressed as:
(IT IDIS(H')
Σ
I(h((X))) # +Y) +M
JES'
27

---

Published as a conference paper at ICLR 2026
Substituting this into Equality
|S DDS H²)
2M
eTTpis(H')))) (h)
) (h*)
[H'(
Since M > 0, follows that:
|5 (DS((H))
eI (h*).
This completes the proof of Lemma C.6
Having the above Lemmas in place we provide the two main following lemmas. The following Lemma C.7 shows if the error of optimal classifier low in DIS(H,) the algorithm will reiterate the for loop.
Lemma C.7. There exist universal constunts C1, bi such thut for any iteration of A'Allorittmm 2 if
(TDDI(HH)((*)> 160
then the radius (H, < 1/2 radius (H:), provided that all lower and upper bounds are valid during the algorithm's 's execution.
Proof of Lemma C.7
T; is defined as radius(!I;). Then using Lemma C.4 we know for all H; nry 1. Using Lemma C.6 we know that
that (s(h, h²) we have (D.) (h" Z (h*
erTDis(H>) (h) DDISCH h²) eTDDs)(H))h"))
plunging DDISHH (h,
By 2
and erIDis(H)) (hi))
B (h 2r.]
nr
T6
we get,
nr;
nr;
1
CID (h) 2
B (h+ 2r:)]
2
BH(h" 2n:)
16
Bh (h' 2r:)l
16
Using definition of 0 in Definition
3.3
we
erTDIS(H)))) 2
160
From Theorem A.1 we know that if we have
64
2V In(12 160) + In ) E (0((Vi + inl (n()))))
|S =
1 TeB
then HH)) (h) LB((', h, 8') S 168 Therefore LB(S', h, 8') 2 6
Te#
Similarly since we assumed errs (h*) S Te6 and we have UB(S', (0(S",1" 8h" S errs (h*) + 166 we To therefore UB(S', h", < LB(S", 8')
have UB(S', h,, 55) < 2
So there exist C1, bj that all classifiers like h that (s h²) 2 will be removed from the H, thus, radius( H1)1 <
Lemma C.8. There exist universal constants 02 and by such that for any iteration of Algorithm if
erTDis(H.)h")) 160'
and the algorithm enters the If statement, it will return classifier like hi' where
errs(h') S errg(h")(1+++
provided that all lower and upper bounds valid during the algorithm's 's execution.
28

---

Published as a conference paper at ICLR 2026
Proof of Lemma C.8
The Algorithm
2
will build set S' consists of
c20²
Vn In ())
1
In
+ b2
22
random samples drawn from DIS
From Theorem A.1 we know using 8 erTDIs(H,) + 160 for all h. Therefore, there exists universal 02 and by such that (B(S", h. 2 that this bound holds.
2V n In 12
In( ( samples we get bounds such
rea
I63
The Algorithm returns /' arg min UB(S', h, ()) Therefore, we have eripis (H)) I (h*))( Toa- Given that eIIDis(H.) (h*) 2 1oa we have
etTDIs(H,))M) S errpIs(n,) (h*) c).
Since H E H₁ and h E H, DIS(H.) include all samples they label differently. Assume they misclassify M samples in S/DIS(H.).
ems((h))= 1
Σ T(h"(z) #
n (x.))E
Σ
I(h((x) +
Σ I(h((x) + v)
(a.y))D(S(IL))
(M + (IS(H)))eTTnsss)r))
n
Multiplying both side by 1 we get,
(1 + c))r ((
Since M 2 0
+ c)errs(h")) 2 (M + 1)(h")
(8)
Applying Inequality to Inequality
we have
(1 c)errs(h") > _
(M (DIS((I-)))ermsxx..(())) errs(h')
n
Now lets proof Algorithm correctness.
Proof of Theorem 4.4 First, in Lemma C. we establish that the loop in Algorithm runs for at most (2n) iterations. Using this result, we show in Lemma C.2 that bounds are satisfied with probability at least 1 d, ensuring that we can safely assume all lower and upper bounds are valid during the algorithm's 's execution. Next, we prove that the optimal classifier, h², is never removed, shown in Lemma C.5 assuming that all bounds hold. Then in Lemma C.7 we show that
erTDIs(H.) (h*)= ) < Tea then we will no go into the If statement. Finally in Lemma C.S we show that
errDIsCH.) (h*) 1 and we do go into the If statement then the algorithm will return a (1 + classifier.
Tea
Proof of Theorem 1.2 Theorem 4.4 let us show that Algorithm 2 returns (1 + <)aaproxxmaaee classifier with probability greater than 1- 6. For its label complexity, we apply Lemma C.I to show that the loop in the algorithm repeats at most log, 2n times, and since the If statement is executed only once, the label complexity bounded by In(n) times O (VH In 8 + In ))) plus
_ (Viz In 2 + In 4)) This concludes the proof of Theorem 1.2
29

---

Published as a conference paper at ICLR 2026
D DECISION TREE'S & CALCULATION
As the first lemma, we prove that DIS can be expressed as a relationship between a single classifier and the other classifiers in the disagreement set.
Lemma D.I. Assuming h E H, have
DIS(H) = (x EeE (xx))) h())).
Proof of Lemma D.I From the definition, we have:
DIS(H) = { 3h1 h2 E H h1(x) + h2(x)}
for some I, we have (x) * (2))),, then either h(x) + h1 or h(x) + h2(x). Therefore, 3h1, h2 H (2) h2(2), then 3h E H: (x(x) h(r).
Next, in the following Lemma, we build connection between decision trees and line trees.
Lemma D.2. For any two decision trees h, h! and any two leaves i, such that iys * I if S, {ar LineTreen.s(s) = 1,,3), then:
Ds, (LineTreen,s, LineTreew g) Dh,
Proof of Lemma D.2 If for some a we have Line = J, then 1/(x)) Iw Therefore:
fx E S, LineTreew J(()) - fo fx S; (x(x)) [
Since ln,s + w. we have:
(5 S, LineTreew, + 111t S fa E S, [xx)) hnd
Since E S₁. we have LineTreen, I1,1 As result h(z) 4,,4- Therefore:
(x E S LineTrree,, # LineTreew ((()) C {ar S Mxx) # h(xx)
Thus:
Hx E S, (ineTreep..x)) * LineTreew ( < Hx e S. h(x) + h((x))
Thus:
Ds (LineTreen,,, LineTrrew 1 18 (h,
Therefore:
Ds, (LineTreen,, LineTreew Ds,
In the following Lemma relate error of classifier in the overall dataset the enror of the classifier in a subset.
Lemma D.3. St c then Bs(h,r) S By (h, 1ST
Proof of Lemma D.3 Assume N'' E Bg(h,r). We will show h' By (h,r ())) We have:
Ds( r
Therefore:
Hx M(x) + N'(x) S Siss
Since S' C S:
Hr E S' Mx) # [()=)) < Hr S Mx) M()) & si|s
30

---

Published as a conference paper at ICLR 2026
Therefore:
|S|
t E 8' [(xx) + (x)))) Sr
|
From definition of D right side is equal to Ds (h, (h, Thus:
|||
(s, $
|
Therefore:
S
h' E (h,
8
To extend our analysis line trees which we need for Theorem 1.1 we first introduce some key definitions related to line trees.
Definition D.4. line tree is a decision tree where for each node, at least one of its children is leaf, and all leaves except the deepest leaf assign the same label, while the deepest Icaf assigns the opposite label.
Definition D.5. different from the rest of the leaves' labels.
is a line tree, then L, the label that could be the deepest leaf label and is
Definition D.6. If h is line tree, then dn S (1,2, dim} is the set of dimensions that nodes in the line tree decide based on.
Definition D.7. T. the set of all line trees with depth less than d where each node decides based on unique dimension. La is the set of all line trees with depth less than d and with d, = d'.
Definition D.8. For line tree h E Le', we define function fx. dh - {prefix, suffix}, where (a) specifies the splitting behavior of h for each dimension E dn:
fa( prefix if samples with za less than threshold are directed to the leaf with label hn-
(a) = suffix samples x with oa greater than a threshold are directed to the leaf with label ln.
Definition D.9. For a line tree h E IL, let hg denote the number of distinct values of va for which M(x) = lv. Formally:
hg = {xa x E S h(2) = 4.H--
In the following thcorem, prove that the disagreement coefficient of decision tree is OInn (n)), assuming the input distribution is uniform-like and each node in a root to leaf path works with unique dimension.
Proof of Theorem
I.J upperbound. Assume we have chosen tree h and we want to bound 0,. This
requires bounding DDS((n (h.r)) for all Using Lemma D.1 have:
nr
BI (h, = (x 3M E BH, 1())) # Mx))
Breaking this based the leaf reaches in h, we get:
(Is(Bn(hrr) U fo reaches leaf i A 3h Bn(h,r) h'(x)) # h(x)
Using the definition of a line tree, DIS(Br is equivalent to:
fo LineTree,, = In,s A 3h' e (a :1(=)) + M(x))
31

---

Published as a conference paper at ICLR 2026
Further splitting the set based the dimension set of the leaf that reaches in h', (IS(BB
equal to:
Ú
U
{or LineTreen, LA3H'' e Ba(b, reaches leaf j in (') h(z)/dwes d')
é= (1.."C(1.2....imm))
1
-U
U
t< (in))ree,,.(t) = 4/3K' E (h, r),j LineTreew (() = (N)(((((z)) o h(x)Adwss = =d
Let Sy be the set of data points that reach leaf in tree h. Formally, S; {xr LineTreen, Ini..
Then we have:
DIS(Bn((,r) C
U U
E St 3M' (h,hrr) LineTreew I (N) + h(x))dws = d'}
i=1 d' (im...
Using Lemma D.3 this equal to:
U
U
( I.S.IEM EM E Bu.s, (h. ( ).: (s)) TineTrrewsset = (wr)Ah((z) & h(x))dxs d'}
L= [Id.2((......dm)
Using the definitions of line trees, rather than first selecting general decision tree h' and sub- sequently addressing one of its line trees, we can directly consider h'' as a line tree, significantly simplifying the analysis.
Additionally, observe that if for some N. we have (h, M) S S and L F I then by Lemma D.2 follows that Ds, (h, LineTreen .) S [. Consequently, can further refine expression as:
T.
DIS(Bu((4r))
C U
e S 3h's BL (h, n S
): 11(())) = (NA)(()) + Mx)) S
i=1 (1I..(I))....i))
U
( 3h St (b,
[S (ss)
h((x) +((x)+ M(x))
i=1 (11,2_(
Since we only focused on S, and in S, and LineTreen, behave similarly, we have:
ÚUS
U
(((x)) (z)) 3h E B, (LineTreen,, [s s
1=1 di1.
Since h is a line and we only have LineTreen, and in S, LineTreen, an all-same classifier, apply Proposition 3.5 Hence, the size of each of the inner sets is of O (15/ T In w)))
Since < 2d and has dim choices, the total size of DIS(B (h, r)) of:
2d dim
ur mr(3ln)))= =0 2d dim
3
In ))
Dis(Bn())r)) <
nr
dim
0 Anroa dim (
))= (
6d Ind
Inn
s 0
(nrln"n In m)
nr
d!
dim
Therefore:
0x(r) E E 0 (In(n)d)
32

---

Published as a conference paper at ICLR 2026
We need the following Lemmas prove Proposition 3.5
Lemma D.10. Let E Lay be a line tree. Then:
1 E S h(z) 1.Hl
hg II Way
agd
agd'
where
S ((a1,..., ................................
Vi, a, N, a, S w ww.
Proof of Lemma D.10 For each dimension E d', exactly hg of the possible values of are directed to the leaf with label 4, By the definition of line tree (Definition if any Za does not lead to this leaf, the resulting label for h(z) will be 1 (b. since there is only one leaf with the label L, in a line tree.
D.....
Given that S represents all possible points, and each combination of valid values of z. corresponds to exactly one point in S, the number of points where h(x) = 44 is the product of há across all dimensions d'
Thus:
H E S h))))) 1.1
II hg
II Wa- agd'
aed'
Lemma D.11. Let be a line tree with h(x) = 1n. Then for any satisfying:
x S Ta
if fa (a) prefix
Va da,
Fa x'
if (a) suffix
we have h(x')= = In-
Proof of Lemma D.IT We know that each node in directs x toward the leaf labeled 4.. We will show that each node also directs x' to the same child.
Consider node working with dimension a E dz.
If fa) = prefix, then values lower than will also be directed toward the leaf labeled ln. Since 2/2 S Fg. x' follows the same path as x.
If (a) suffix, then values greater than va will also be directed toward the leaf labeled 4.. Since I, I x' x' follows the same path as x.
Therefore, in all nodes, x' follows the same path as æ. and hence acquires the same label In.
Lemma D.12. The number of sequences of the form (x1, (2,.......; xx) such that Visigk E N, Vigisk : I4 I we, and Ilisisk T4 I s is less than &I2ssis In(w:) 1.
Proof of Lemma D.12 We will use induction to prove this lemma. Let g(s, k, w) denote the number of such sequences.
Base Case: For & = 1, the theorem is obvious since there are only possible sequences.
Inductive Step: Assume the theorem holds for any s and kg- We need prove it for k ko+1.
Consider the possible values of #ka+1. We have:
g(s, kn + 1, 1.
Σ
( ko, w
IsiS
By the induction hypothesis, this sum is less than:
II In(w,) + =
In In(w,) +
25
25
ISiSwegt
33

---

Published as a conference paper at ICLR 2026
Using the harmonic series approximation, Eisisweat (n(wko+1) 1, we have:
Ss
In(ws) +1 (In (In(wko+11) + 25
II
In(wy) + +1
25JSkot1
This completes the induction step, and thus the lemma is proved.
In the following Proposition we show that the disagreement coefficient of line tree that assigns 0 to all samples is of O(In" w) among line trees.
Assume a line tree h E La that assigns the same label to all data points. Without loss of generality, assume this label is We want to bound ((h) sup, [DIS( (h.r))
Proof of Proposition
Fixing from Lemma D.I we have:
nr
DDS (h, = (= 3h' E BLy (h. r) 1 (x) * h(x)) fo 3h' E BL (h h'(x)) = 1}
Defining F as the set of all possible functions Sn (See Definition D.8. we have |F| = 2/d'1, We break DIS( Br. (h,, r)) based on fne:
(lh,
Uz aa fy
SEF
we define
Ayu == for 3h's E B (h,r)) = -SA =1: =1:1((x) =
Then we have
DIs(BL(h,r)) =
U
A5o + As1
fEF
Therefore,
(h, S Σ
Arrl + |Aral
FEF
We bound size of A and A,,ı separately.
Bounding the Size of Ay.0
We aim bound the cardinality of the following set:
A,.0 {x 3h E BLG (h, r), fi = f. I. 0: 11(x)) = =1].
(10)
Recall that Beg (h, r) denotes the ball radius r around within the class of Line Trees of depth most d'
Because ht' E Br.g, (h, r), it follows that D(h, < r, meaning that h differs from h on at most an r fraction of the n total points. Since the original classifier h assigns label 0 to every point, h' can label at most nr points as 1. Equivalently,
Hz h'(x) 1) s ar nr |x h'(x) 0} 2 n(1 r).
From Lemma D.10 the number of points classified as by h can be expressed as:
nn1 < Hr ((x)= 0)]
II hda
Way
aed'
agd'
where w. is the width in dimension
Now, consider a point x that is labeled by N'. By the structure of the tree, since 4, 0 there must exist a node corresponding to dimension b E d' that routes contrary to the main path. Note
34

---

Published as a conference paper at ICLR 2026
that tu denotes the threshold applied dimension b. Samples with S tw'b are directed to the left child, while those with 26 > ty are routed to the right child. So to bound the Size of As.0 future break the set (Equation IOp based dimension of the node that sample leave the path toward 4 = 0. Assuming this is dimension b, we consider two cases, depending J (b):
(b) prefix
Here, ht"h = two - 1, and (a))) only if tw S Td. Therefore,
II Wa II
ht < (Ih 1) II Wa II 1ta
agt
aed'
agd
aEd' (bb)
Since for all d' \ (b), h
< War and I Wa n, have Πaça Wa a.. Putting it all together, have
Iaedd ((b) Wa w%
n(1 - r) S (x) - 1)
which rearranges
wy r) + S zb.
Thus, for fixed b, the number possible values for 2bb is at most
Wb (wb(1 - r) + 1) wyr,
and, for each fixed b, the number of possible is
II
WhF
W
We wır.
aEd'
(b)
agd
(b) = suffix
Now, 11th = wb bN . + 1, and for 1 12xx) = we require Ty < I db so
1b S wb
Fb.
Therefore,
II agd
W. II hd
(w,
mb)
II We II Wa
"Ed'
agd'
aEd'
By using the same bounding and product arguments as above,
n(1 - r) < (wb σbb n
which simplifies
Tb < WhT.
Thus, there are at most war such wh. yielding at most ur points total for a fixed b.
Across all possible choices of b E d', the total number of such points is most
Σ nr nrld |d| S nr
bedd
where d is the depth of the Line Tree, i.e., |d' d.
Thus,
|A dnr.
Bounding the Size of Aya
We aim bound the cardinality of the following set:
Ay.1 fx Ah Bay (h, r). Sw f, bn = 1: M(x) =1).
35

---

Published as a conference paper at ICLR 2026
According to Lemma D.11 if is classified as 1 by line tree h with parameters for and l 1, then every point x' satisfying the following will also be classified as by h':
s/a S Ta Ta S x
if (ar = prefi
Va E du
if (nr suffix
we have h(z') = lp- This describes a corner- corner-aligned box in the imput space whose size depends on and the direction assignments fx-
To express the size of the box leading to under h define
if fn (a) = prefix, W/ Ia +1 if (a) suffix,
x=
Ya dv-
By this definition, for each x that classified as 1, the region of points labeled 1 under h contains least Hogaa Wa Ilae x distinct data points.
Since all such h under consideration within distance from h, which labels all points as 0, the number of points for which differs from (i.e. the number of points classified as 1 by h²) is at most nr. That is, Ezes ( 1) S Therefore, for any a such that h' h'(x) 1, the box it
produce as above must satisfy
Wa II II agd
x Snr. nr.
aed
For fixed assignment of fir, values for dimensions a d' is uniquely determined by the tuple {x" a E d' that is, knowing these values and the directions and To for a & d' fixes æ.
We now seek to bound the number of tuples (x*) such that Ila xa nr, with each x" an integer in [1, wa].
By Lemma D.12 the number of integer tuples (x"))ed that satisfy Haze wa Ia x= S nr ILa xº S nr TTaeer is at most
II (n(wa) + S nr Hage Wa (1 + In
Hage Wa aed'
Since the number of ways we can fix Fa for & d' is, Naçe Wa we have:
A nr (In 1)d.
Combining two above cases
Combining two above cases and Equation 9 we have
(BIs(Bt(h,
Σ SEF
A |A,al
Σ nrd nr(In +1 1)a s 2d nn.nddd + (In w + 1)*)
Jef
Therefore
0₂ < 2d (In(w) 1)) (2In(w) + +22 2dd
For d > and > 8 this is of
0n < 0 (3l
D.1 PROOF OF COROLLARY 1.3
Proof of Corollary 1.3 Using the calculated disagreement coefficient of decision trees in Theo-
rem 1.1 which is In(n) d and V,, decision tree in Lemma A.3 which 2d(d + In dim), we can plug these values to Theorem 1.2 which results in
36

---

Published as a conference paper at ICLR 2026
In
In(n)2d
(2 In dim) In In(n) +In
In(n) In(n)²u (d In In + In
+
8
e²
This is of
of In (n) Indim)d In ))
In (n)
2d(d dim) In In) In 2))
2²
D.2 PROOF OF LOWER BOUND OF θ
Proof of Theurem 1.7 lowerbounds. We establish lower bound by analyzing the all-zero clas- sifier, ho- From the definition of the disagreement coefficient (definition (.3), have O [DiS(Bn (ho.r)) mr
We select the specific radius wmm-d41 d+1 in
h 0n 2 Bho- where tho = sup,
which gives the bound:
DIS(BH r))l
r))l
wodim-
The n = -i data points exist on a fin-dimensional grid. We partition this grid into 2dim equal- sized orthants, assigning each point to its nearest "corner." By the symmetry of the grid, the number of points in the disagreement region, DIS (h), is identical for each orthant. We can there- fore find the count for orthant and multiply the result by 2dim, We will analyze the orthant where all Iz < w/2.
To find lower bound on this count, focus on specific, symmetric subset of points x in this orthant that have d dimensions with x; S w/4 and dim d dimensions with w/4 < 24 S w/2. By symmetry, there are (fam)) such subsets. We can count the points in just one whe-where .i,..., Zd S w/4 and Id+1.-... FFdim E (w/4, w w/2] multiply by this binomial coefficient.
point x is in DIS(B (ho. r)) if there exists a classifier h Bu Bho r) such that h h1(x)) * ho(r)) meaning (xxx = (definition 3.2). For any such x, we can construct a "line tree" / of height d that uses the first d dimensions and classifies point y as 1 if and only if y; S r, for all 1,...y d. The distance D(ho, h²) is the fraction of points h' classifies as 1. The number of points classified as 1 is (II.
æ;;) wim-- so the distance is:
D(o, h²) (II r:)) din-d
(I v:a) widm-d
widm
wd
We only count points x for which is in the ball, D(ho,h/ I r. Substituting our values for D(hg h²) and r:
Ih wi
u dim--d+1 d+1
w wiii+1
4n
4n
We can now find the total count. The number of sequences (II,...,, s.a) satisfying I; S w/ and
Il 24 w/4 has lower bound proportional to w/4 In d- (w/4) (lemma D.13) Let C" d! be this constant of proportionality. The number of sequences (Ia+1..... Zdi)) with w < Σę S w/2 is exactly (w/4)dim-d.
The total number points in the disagreement region, DIS), is lower-bounded by the product of terms:
DIS
> Ω (NNum Orthants) (Num. Groups) (Count for d dims) (Count for dim d dims))
Ω
dim
(dim)
[ (www/4) (n In In [w (4)mmmm))))
/dim)
Ω 2
C (w/4))mmmd-4 In In
(im
Ω 2 2dd+2
. dim In d (10/4)
37

---

Published as a conference paper at ICLR 2026
Simplifying and using wiim and 4dim
2 Using the lower bound (Cam) 2 (imm yd:
dim d- C² w dim d+l In (w///ww/))
DIS| 2 Ω
2 dim 24+2
Finally, we substitute this back into our inequality for 8:
[IS( ( r))l
θ 2 Ω
wdim d+1
dim d-1 1 2d++2
?
In In -nn--11w/1 (w/4)
d!
2 2im+24+4
Ind (w
d d!
2 2d44
2 2-dim
In 1-1 (n/4dim)
2 Ω
dd- an d- (n/4dim)
dd-Id! d!
So for C dd-1d
2-
and C' = -dim In 4 we have
ž C- (In()) caya-1.
Lemma D.13. Let g(s, d) be the number of positive integer sequences (I1...., vx) such that the product satisfies I Is S s. The count g(s, d) has a lower bound
gls. d) = Ω d!
In d- (8)
Proof of Lemma D.13 Let Ta( denote the d-th divisor function, defined as the number of ways to express a positive integer n as a product positive integers. We observe that the quantity g(s, d)
corresponds exactly to the summatory function of Ta(n)):
g(s. d)
Σ Ta(n).
Isn5o
The asymptotic behavior of this sum is the subject of the Piltz Divisor Problem. It is classical result analytic number theory (Titchmarsh & Heath-Brown (1886) that for -
g(s, d) = Σ Ta(n) = s(In 8) dd-1
(d 1)! + +0 (s(Ins)
The leading term implies that for sufficiently large s, the count grows the specified bound. Specif- ically, the main term dominates the еттоr term, implying:
s(In 8) d-1
g(s.d) d) N C
(d - 1)!
for some constant C 0. Thus, g(s d) 2 (d-1)) In 1nd=((s))
L
D.3 NECESSITY OF ASSUMPTIONS PROOFS
In this section, we provide the proofs from Section 3.3 Specifically, we first prove that if nodes are allowed work on the same dimension as one of their ancestors, the disagreement coefficient is of 1/dim
38

---

Published as a conference paper at ICLR 2026
Proof of Theorem 3.6 We aim to construct depth-2 decision tree that assigns label 1 to a point I Rdim if and only if Ta = c, for some fixed dimension a and constant с E R. The structure of such tree is shown in Figure 2a where the root node checks whether Ia and the second node checks whether Ta < c + 1. Because both comparisons involve only the a-th coordinate, the tree assigns label exactly the inputs satisfying Ta c, and label 0 otherwise.
Let X C Rdim be a dataset of size n,, and let the reference classifier ho be the constant-zero function. 2 n -1/dim which includes all classifiers that differ from hg on most n² 1-11ddiim datapoints.
Consider the hypothesis ball B (ho, r)) of radius
Fix a dimension a E [dim]. For each value e that appears in the a-th coordinate of the dataset, define the set (or "row") R := {a X H. = c). If RR - 2 n 1-/imm then the decision tree shown in Figure 2a labels only the points in Rt 1, and all others as 0. Such a classifier differs from ho on most 2-11/ddmm points and therefore lies in By (ho.r) r). Consequently, all points in such row RC lie within the disagreement region DIS( B (ho,r)) We call such rows light rows.
Rows R% for which RR > 2-n' I-ddii are called heavy rows. We now upper- upper-bound bound the number of heavy rows per dimension. Since each heavy row contains more than 2 . nn 1-1dim points, their total number for fixed dimension is at most:
1 1/dim
n
2
A point x X be excluded from the disagreement region only if it lies in a heavy row for every dimension. Formally, we have:
& DIS(B (ho,r))))))))))
Va [dim]: Fc such that E R and [ > 2 - 1/dim
Since there are at most / heavy rows in each dimension, the number of points that lie heavy row for all dim dimensions is most:
2 n 1/dim
2
Thus, at least
2dm
2dim
2dm
11
points belong to the disagreement region:
2dim
DDI((B r))
2dim
n2
The disagreement coefficient at radius r = -1ddmm is therefore lower bounded by:
(DIS(BH(hos' r))l
-1m
2dim -1 2/dim
2
2/22//
rn
2n 11/imm
21
This completes the proof.
Next we show that if there is no assumption on input dataset then, the disagreement coefficient is of ((n).
Consider the dataset X (X, = (i.,,..., ... Melm 1,..., n), where all data points lie along the diagonal line F1 = 22 = ... Edim- Let the reference classifier ho be the constant-zero classifier, i.c., (z)
Proof of Theorem 3.7
for all X.
Let r = 1. The hypothesis ball B (hg r) contains all decision tree classifiers such that h'' differs n.
from hg at most one point. Since each point X; is distinct and isolated, h4 E (ho, r) that outputs h, (X,) = 1 and (,( = for all x + X,,
construct tree
To isolate specific point X, (c, ... c) in the dataset, it is sufficient use decision tree of depth two that queries only the first two coordinates. This construction is illustrated in Figure 2b
The tree works follows:
39

---

Published as a conference paper at ICLR 2026
1. The root node tests whether 21 2
2. If not, the label is O.
3. Otherwise, the second node checks whether æ2 c++ 1.
4. If this true, the label is 1; otherwise, the label is again O.
Because each X; lies along the diagonal (i.e., 21 = 22 assigns label 1 only to the point Xe, and label all other X₃. Thus, even under the structural constraint that no dimension repeats along a path, we can construct such an isolating tree using only two features.
= Teim = i), this tree correctly
Hence, for every point X,, there exists h; E Bho r) such that (x,),) + ho(X;), which implies that every point X; lies the disagreement region:
BI r)) { E X 3h' e (ho.))r) s.t. h1(x) ho(x)) = X.
Therefore,
DIS(Brr (ho, r))1 = and == n
so the disagreement coefficient is at least
DIS DIs(BB((ooT) r))]
n n.
Oro sup
rn
(1/n) n
This proves that the disagreement coefficient suphen On satisfies ((n)..
D.4 RELAXING UNIFORMITY ASSUMPTION
In this section, we provide the method by which we relax the assumption of uniformity among sam- ples. As outlined in the main body of the paper, assign each sample an importance measure, denoted as S W; < x. In this context, we evaluate the classifier's error using the formula:
ΣL 1(h(X.) + Y.W,
W erry x (h)
ΣE W
We further define the distance between two classifiers in this weighted context with the following expression:
(h1, h2) En= WiThh, + h2().))
ΣE W₁
Similarly, the ball of classifiers within around given classifier is defined as:
BW (h,,) (N' E H
Similarly, the disagreement coefficient 0% of classifier h is defined as:
EIEDISBWW (hrr)) W;
0 = sup 0-r -Σ_,
The following theorem establishes a bound on the disagreement coefficient for the weighted case, showing that is most 2 times the disagreement coefficient for the unweighted case.
Theorem D.14. In any classification task where W. S for all the disagreement coefficient o. is at most X2 times the disagreement coefficient 9, in the case where all samples have equal weight.
40

---

Published as a conference paper at ICLR 2026
The proof of Theorem D.14 leverages the relationship between the weighted and unweighted dis- tances between classifiers. Specifically, we show that the weighted distance DW is bounded by times the unweighted distance D, i.e.
DW (h1,h2) S XD(h1,
This relationship implies that the set of classifiers B (h, that are within distance of classifier in the weighted case is a subset of the corresponding set in the unweighted case, Bu (h, r Therefore,
BE rh S (a(),r)
which helps us prove the theorem.
Proof of Theorem D.14 We aim to prove that for any classifier and radius 7:
DIS( (h,
EIEDIS(BY, (h.r)) W;
n(rA)
W.
First, consider any two classifiers h1 and h2. The weighted distance D (h1, h2) is given by:
(" h2) E. W,i(h,, (X,) # (x()))
Σ, W
Since W; S X, we have:
E, (X;) # h2((i))
D'(1i, h2)
E.W.
Given 1 1 W,, this further simplifies to:
D'(h,, S X E, ((h(((X))) # h2(Xi))
AD(h2, h2)
From this, we observe that D (h1,, h2) S r. then D h2) s Ar. Therefore:
(h, (h(),r
Given this inclusion, we have:
EyEDIS(B W;
Σ EIEDIS By (h.)r) W r r, W;
r -, W.
Since 1 < W, S X, it follows that:
EiEDIS (h.Ar)) W,
(HED))(R((AAr))
DIS (h,
DIS( (h, Ar)) (rd)n
r, W.
Therefore:
(A W
DIS(BH (h, (b)Ar X20
07, = sup 0<r
< X2 sup
-E, W
(rd)n
This completes the proof.
41

---

Published as a conference paper at ICLR 2026
E ADDITIVE ALGORITHMS ARE INSUFRICIENT IN MULTIPLICATIVE SETTINGS
In this section, we examine why additive algorithms fundamentally inadequate for multiplicative error settings. We outline two high-level approaches that one might consider when adapting additive algorithms for multiplicative guarantees, and demonstrate the inherent limitations of both.
Estimating the Optimal Error Rate (Without Output Verification): natural idea is to first estimate the optimal classifier's error, say to within constant factor (for example, a 2-approximation), and then use this estimate as baseline for additive algorithms. This strategy implicitly assumes either prior knowledge of access to tight estimate of the minimal achievable error. However, even if the optimal classifier is known, estimating its error rate 7) to within multiplicative factor of 2 with confidence 1 ò requires at least 1 In & samples. Since 1 is unknown in practice-
crucially, should not appear in the label complexity of the final algorithm- this approach cannot yield a label-efficient algorithm for general y/.
Verifying the Error Rate By Iterative Refinement: Alternatively, one can attempt to iteratively refine the estimate of the optimal error. For instance, starting with a guess of 7) 1/2. run the additive algorithm with e' = 1/2. If this fails to yield the desired error guarantee, halve the estimate (1) = 1 1/4,'' = 6- and continue. This approach necessitates verifying, each step, whether the returned classifier meets the guarantee
err(h) 1 +'. Such verification also requires O [In(1/6) labeled examples per attempt.
"
As before, the unknown and potentially small value of v causes the total label complexity to depend inversely 17, which is unacceptable in settings where 1) is not known.
Both searnachhs-iihher without verification (relying tion (iteratively guessing and checking) the same fundamental barrier: The number of labeled examples needed estimate verify small error rates scales inversely with the (unknown) true er- ror Because any algorithm that hopes to achieve a multiplicative error guarantee must operate efficiently even when 1) small and unknown, this unavoidable dependence is fatal. As result, additive algorithms and their naive adaptations cannot provide effective or label-efficient solutions in the multiplicative error regime.
accurate guess of 1)), with verifica-
F EMPIRICAL BEHAVIOR OF ALGORITHM CONSTANTS
C2. We conducted experiments to assess the effect of algorithmic constants C1, b1, C2. and b2 in practical scenarios. Our key findings indicate that these constants can be set to relatively small values without adversely affecting the performance or correctness guarantees of Algorithm [ In particular, we observed that values low as 3 for c1, 62, b1 and b2 are sufficient in practice, despite theoretical analysis suggesting much larger values.
Additional experimental results, code and full raw data available via our anonymous Dropbox link: http: / /bitt 1y/4583817 bttp::///b..11//511 Notably, our empirical results suggest that C1 and by have a larger impact algorithm success rates compared to 02 and by.
Experimental setup:
Sample size: n 107
The optimal classifier was selected uniformly random
Labels were assigned according to the optimal classifier with independent label noise of 0.1
Algorithm|
I was executed with 6 0.1
Each configuration of (c1, bi, 02, b2) was tested in 50 independent trials
A configuration was considered successful if the success rate exceeded 1 8 = 0.9
Each experiment was ran on a single CPU core. Each setup takes min to complete.
42

---

Published as a conference paper at ICLR 2026
Success Rate Grid for c1=3, b1=3
Success Rate Grid for c2=10, b2=10
Red: <0.9, Green: 20.9
Redi: <0.9. Green: 20.9
1.00
1.00
1.00
0.98
1005
1.00
1.00
1.00
1.00
C2 valus
1.00
0.96
1.00
1.00
1.00
1.00
1.00
1.00
3-
0.98
1.00
1.00
1.00
0.32
0.80
1.00
1.00
353
300
10
1008
(a) Success rate grid for Ci 3, bz
(b) Success rate grid for e₂ 10, b,
Figure 3: Comparison of success rate grids for various (C1, bj C22 b2) parameterizations when ning Algorithm with 0.1 (expected success rate > 90%). For each cell we run Algorithm on fixed randomly generated dataset for 50 times and calculate the success rate. evidence suggests setting each of these constants to is typically sufficient for reliable algorithm performance.
43


Reviews:
[{"review_id": "vdwTRsFwzq", "reviewer": "Reviewer_5MpN", "summary": "This paper investigates active learning for decision trees, providing theoretical bounds on the disagreement coefficient and proposing an analysis based on multiplicative error guarantees.", "questions": "See the weaknesses section.\n\nHow do you define the calligraphic R appearing in Algorithm 1 and 2?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem addressed is inherently interesting: active learning for non-linear, structured models like decision trees is a challenging and important direction.  \n\n- The choice to use multiplicative (rather than additive) bounds is conceptually appealing, as it aligns with realizable-case analyses and could, in principle, yield sharper guarantees.", "weaknesses": "- **Limited theoretical novelty and impact**  \nThe theoretical contributions are incremental. The derived bounds on the disagreement coefficient $\\theta = O((\\ln n)^d)$ are relatively weak and pessimistic: $(\\ln n)^d$ can grow very quickly even for moderately large depth, making the guarantee practically meaningless in realistic settings. Moreover, no *lower bounds* are provided, leaving it unclear whether the obtained rates are at all tight or informative.\n\n- **Strong and unrealistic assumptions**  \nThe analysis critically depends on highly restrictive assumptions: discrete and regular input domains, unique features per root-to-leaf path, and bounded tree depth. Such conditions are far from how decision trees are actually used in practice (e.g., CART, random forests, or gradient-boosted trees reuse features and operate over continuous domains). As a result, the results have very limited applicability.\n\n- **Intractable use of the disagreement region**  \nThe proposed Algorithm 2 relies on having access to disagreement regions. While this is standard in theoretical active learning, for decision trees the version space is exponentially large, and computing or even approximating $\\text{DIS}$ is computationally hard. The paper does not propose any practical surrogate or heuristic for this step, making the algorithm purely theoretical and not implementable in realistic settings.\n\n- **Lack of empirical validation**  \nWhile pure theoretical papers are completely acceptable, here the derived results are rather fragile (strong assumptions and exponential dependencies). On the other hand, no convincing experiments or simulations are provided to demonstrate the practical relevance of the theoretical claims. The “empirical study” mentioned in the appendix is neither summarized nor discussed in the main text. Without empirical evidence, it is hard to assess whether the proposed insights translate into meaningful performance gains.\n\n- **Venue suitability**  \nThis paper would be more suitable for a theoretical conference, where the focus on formal guarantees would be appreciated. However, even in that context, the work would likely be borderline due to the limited novelty, overly strong assumptions, and the lack of accompanying lower bounds.\n\nWhile the topic is of potential interest, the present paper does not substantially advance the theory. The derived guarantees are fragile, the assumptions unrealistic, and the theoretical improvements marginal. Combined with the lack of lower bounds and the poor presentation quality, the work currently falls below the bar for a strong theoretical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zNzgHDi2l1", "reviewer": "Reviewer_sttn", "summary": "This paper studies the problem of actively learning decision trees and the problem of establishing multiplicative error bounds for general binary classification in active learning. The authors provide the first rigorous analysis of the *disagreement coefficient* for decision trees, a parameter that controls the label complexity in active learning. They bound this coefficient as $O(\\ln^d(n))$, under some assumptions: (i) the input data must possess a regular, grid-like structure, and (ii) each root-to-leaf path in the decision tree must query distinct feature dimensions. The paper proves these assumptions are necessary; relaxing them leads to significantly higher (polynomial) label complexity. The authors introduce the first general active learning algorithm for binary classification that achieves a *multiplicative* error guarantee. This algorithm produces a $(1 + \\epsilon)$-approximate classifier, meaning its error is at most $(1 + \\epsilon)$ times the error of the optimal classifier. This framework offers stronger accuracy control than traditional additive error models. By combining these results, the authors design an active learning algorithm for decision trees that requires only a polylogarithmic number of label queries, provided the structural and data distribution assumptions hold.", "questions": "- Is dependence on the VC dimension in Theorem 1.2 necessary?\n\n- Is exponential dependence on $d$ in Corollary 1.3 necessary?\n\n- The algorithm boxes are a bit notation heavy.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The results are interesting and make progress on important problems in learning theory.\n\n- The techniques are interesting and non-trivial.\n\n- Overall I found the paper well-written.", "weaknesses": "- The bounds are a bit unsatisfactory.\n\n- The paper might be a bit hard to follow for some members of the ICLR community who are less on the theory side.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Evq3tOomD8", "reviewer": "Reviewer_gUF4", "summary": "This paper studies the classic pool-based active learning problem, where given a pool of unlabeled examples, one wants to design an adaptive algorithm that makes as few label queries over the pool as possible. This paper focuses on active learning for decision trees, a broadly studied class. Specifically, this paper contains two main results.\n1. For structured decision trees and structured datasets, this paper develops the disagreement coefficients of the class of decision trees, using the framework developed by prior works, which gives a label complexity upper bound for active learning decision trees.\n2. This paper generalizes the classic active learning framework, which considers additive error, to multiplicative error, and develops an algorithm for the upper bound.\n\nThese results are mathematically nontrivial, and the paper is written clearly.", "questions": "1. This paper considers learning over a discrete dataset, which is a bit different from the classic generalization setting, where one has a dataset sampled from a distribution and one considers the generalization error over the distribution. This difference looks important, since the distribution considered in this paper is uniform over an integer grid and the disagreement coefficient depends on the size of the grid. What if we consider learning a decision tree over the uniform distribution over a box? Does this blow up the disagreement coefficient?\n\n2. The above difference also makes learning upto a multiplicative error a bit confusing. Since a dataset is usually generated from a distribution, in the low-noise rate setting, it seems to me if we consider the generalization error, then learning to a $(1+\\epsilon)opt$ error is not realistic, as it needs an unbounded number of samples to achieve this. Can you comment on this?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Decision tree is an important and broadly studied class and the theory of active learning for decision trees has not been well understood yet. This paper makes progress in this direction by considering the disagreement coefficient framework proposed by Hanneke. For structured decision trees and structured distributions (uniform distribution over grid point), this paper gives an upper bound on the disagreement coefficient, which gives an upper bound on the label complexity of the problem. Furthermore, this paper also propose an algorithm that aims to achieve a multiplicative error instead of additive error, which is broadly considered in the literature. Overall, these results seem technically non-trivial and the proofs are complete.", "weaknesses": "Although technically solid, I am not sure if the contribution is significant enough. \n\n1. For the disagreement coefficient of the decision trees, this paper places structural assumptions on both the type of decision trees and the datasets. This looks a bit too strong. In particular, if the marginal distribution is structured, then the disagreement coefficient does not characterize the min-max label complexity for the problem (for example, a halfspace has disagreement coefficient $\\sqrt{d}$ under uniform distribution over the sphere, which leads to a label complexity $d^{3/2}$ using Hanneke's framework, but clearly there are algorithms with label complexity $O(d)$). This makes the motivation of bounding the disagreement coefficient a bit confusing, especially given that the bound is exponentially large and grows with respect to the size of the grid.\n\n2. The motivation for considering multiplicative error is not very clear to me. Specifically, the label complexity upper bound for considering a multiplicative error depends on the size of the dataset $n$. In the realizable setting, a hypothesis with $(1+\\epsilon)$ multiplicative error means it has $0$ prediction error over the distribution $D$, which statistically needs a dataset with unbounded size to learn, which makes the label complexity bound meaningless.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3B9HMDU7ea", "reviewer": "Reviewer_RYtN", "summary": "The paper considers the problem of active learning on decision trees. There are two main contributions of the paper. In the first contribution, the authors derive new bounds on the disagreement coefficient of the class of decision trees with a fixed depth and disjoint decision parameters at each node. This allows us to use existing algorithms and guarantees for active learning of decision trees that use the disagreement coefficient of the hypothesis class. In the second contribution, the authors propose a new algorithm for learning the optimal classifier upto a multiplicative error, as opposed to additive error, which is the common metric in learning theory. The authors provide proofs of their claims and combine the two contributions to obtain new algorithms with theoretical guarantees on sample complexity for active learning on decision trees.", "questions": "I have several questions:\n\n- I am still a bit confused about the setup. So in your setting, the learner has access to a fixed dataset $S$ consisting of $n$ unlabeled data points.  And whenever the learner wants the label of some point, it can query an oracle that returns a label $y \\sim \\mathbb{P}(y|x)$, based on some distribution?\n\n- What does curly R in the algorithms denote? (This is likely somewhat related to the previous question)\n\n- Theorem A.1. only holds when the distribution $\\mathbb{P}(Y|X)$ is sub-Gaussian. In learning theory literature, this is more commonly referred to as the Massart noise condition. In this scenario $|\\Pr(y|x) - 1/2| > \\eta$ for some $\\eta > 0$ and all $x, y$. This is something that should be clarified both in your upper and lower bound. There are also less benign noise conditions (Tsybakov conditions) where the dependence on $\\varepsilon$ will get worse.\n\n- The terms $\\mathrm{err}(h)$ and $\\widehat{\\mathrm{err}}(h)$ have not been explicitly defined.\n\n- How is the proposed algorithm for stump classifier different from a classical binary search (with repeated queries for noise)?\n\n- In typical scenarios in active learning, it is assumed that the samples come from underlying distribution. In your setting, you have sort of fixed the distribution to the empirical dataset. While this might be fine, but does it not automatically restrict the number of hypotheses your hypothesis class? Does this not make your problem simpler in some sense?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the contribution of disagreement coefficient of decision trees is an interesting and useful contribution that can help us better understand learning using decision trees. Moreover, this will allow us to better contextualize decision trees among the other widely studied hypothesis classes for learning.\n\nThe multiplicative error bounds are also interesting, especially for the cases when the error of the true hypothesis is very small (or zero).", "weaknesses": "The paper does not have any glaring weakness but I do have some questions (see next section).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)