A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Ray Li Percy Liang Stephen Mussmann




A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
    Ray LiDepartment of Computer Science, Stanford University.  Research supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE - 1656518. Email:  ,
Percy LiangDepartment of Computer Science, Stanford University. Email:  ,
Stephen MussmannDepartment of Computer Science, Stanford University. Research supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE - 1656518. Email: 
    December 30, 2023
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






Decision Tree is a classic formulation of active learning: given n hypotheses with nonnegative weights summing to 1 and a set of tests that each partition the hypotheses, output a decision tree using the provided tests that uniquely identifies each hypothesis and has minimum (weighted) average depth. Previous works showed that the greedy algorithm achieves a O(log n) approximation ratio for this problem and it is NP-hard beat a O(log n) approximation, settling the complexity of the problem. 

However, for Uniform Decision Tree, i.e. Decision Tree with uniform weights, the story is more subtle. The greedy algorithm's O(log n) approximation ratio was the best known, but the largest approximation ratio known to be NP-hard is 4-ε. We prove that the greedy algorithm gives a O(log n/log C_) approximation for Uniform Decision Tree, where C_ is the cost of the optimal tree and show this is best possible for the greedy algorithm. As a corollary, we resolve a conjecture of Kosaraju, Przytycka, and Borgstrom <cit.>. Our results also hold for instances of Decision Tree whose weights are not too far from uniform. Leveraging this result, for all α∈(0,1), we exhibit a 9.01/α approximation algorithm to Uniform Decision Tree running in subexponential time 2^Õ(n^α). As a corollary, achieving any super-constant approximation ratio on Uniform Decision Tree is not NP-hard, assuming the Exponential Time Hypothesis. This work therefore adds approximating Uniform Decision Tree to a small list of natural problems that have subexponential time algorithms but no known polynomial time algorithms. Like the analysis of the greedy algorithm, our analysis of the subexponential time algorithm gives similar approximation guarantees even for slightly nonuniform weights.
A key technical contribution of our work is showing a connection between greedy algorithms for Uniform Decision Tree and for Min Sum Set Cover. 




§ INTRODUCTION


In Decision Tree (also known as Split Tree), one is given n hypotheses with nonnegative weights p_1,…,p_n summing to 1 and a set of m K-ary tests that each partition the hypotheses, and must output a decision tree using the provided tests that uniquely identifies each hypothesis and has minimum (weighted) average depth.[We require such a decision tree always exists in a valid Decision Tree instance.]
Decision Tree is a classic problem that arises naturally in active learning <cit.> and hypothesis identification <cit.>. 
Active learning with a well-specified and finite hypothesis class with noiseless tests is precisely Decision Tree where the tests are data points and the answers are their labels.
Decision Tree was first proved to be NP-hard by Hyafil and Rivest <cit.>.
Since then, a large number works have provided algorithms for this question
<cit.>.

A natural algorithm for Decision Tree is the greedy algorithm, which creates a decision tree by iteratively choosing the test that most evenly splits the set of remaining hypotheses.
For binary tests (K=2), there is a natural notion of “most even split,” but for K>2, there are multiple possible definitions (see discussion in Section <ref>).
It is well known that the greedy algorithm achieves an O(log n) approximation ratio for Decision Tree assuming all weights are at least 1/(n). 
It was first shown for binary tests and uniform weights (p_h = 1/n for all h) <cit.>, then K-ary tests <cit.>, and finally, general non-uniform weights <cit.>. Furthermore, it is NP-hard to achieve a o(log n) approximation ratio for Decision Tree <cit.>, settling the complexity of approximating Decision Tree.

However, there are still gaps in our knowledge.
For Uniform Decision Tree, i.e. Decision Tree with uniform weights, the O(log n) approximation given by the greedy algorithm was previously the best known approximation achievable in polynomial time.
Chakaravarthy et al. <cit.> proved that it is NP-hard to give a (4-ε) approximation, giving the best known hardness of approximation result, and they asked whether the gap between the best approximation and hardness results could be improved.
Previously, it was not even known whether the greedy algorithm could beat the O(log n) approximation ratio in previous analyses: the best lower bound on the greedy algorithm's approximation ratio is Ω(log n/loglog n) <cit.>. 
In the setting where the optimal solution to Uniform Decision Tree has cost O(log n), Kosaraju et al. <cit.> showed that the greedy algorithm indeed gives an O(log n/loglog n) approximation,
and they conjectured that the greedy algorithm gives an O(log n/loglog n) approximation in general.

For an extended discussion of related works, see Section <ref>.


 §.§ Our contributions
 
We summarize the main contributions of our work below. The approximation guarantees of our algorithms are captured in Figure <ref>.


  * Greedy algorithm.
We give a new analysis of the greedy algorithm, showing that it gives an O(log n/log C_ + logp_max/p_min) approximation for Decision Tree, where C_ is the cost of the optimal tree, p_max=max_h p_h, and p_min=min_hp_h.
This implies an O(log n/log C_) approximation for instances of Uniform Decision Tree and of Decision Tree whose weights are close to uniform.
As C_≥log_K n always, this proves the conjecture of Kosaraju et al. <cit.>.


  * Subexponential time algorithm.
Leveraging the above greedy analysis, for α<1, we give a subexponential[Throughout this work, subexponential means 2^n^α for some absolute α∈(0,1). We make a distinction when referring to 2^n^o(1) runtimes.] 2^Õ(n^α)-time 9.01/α approximation algorithm for Uniform Decision Tree. 
Assuming the Exponential Time Hypothesis (ETH) <cit.>[ETH states that there are no 2^n^o(1) time algorithms for 3SAT.], this algorithm implies that any superconstant approximation of Uniform Decision Tree is not NP-hard.
Our work adds approximating Uniform Decision Tree to a small list of natural problems whose time complexity is known to be subexponential (and, for some approximation ratios, 2^n^o(1)) but not known to be polynomial.
Examples of such problems include Factoring <cit.>, Unique Games <cit.>, Graph Isomorphism <cit.>, and approximating Nash Equilibrium <cit.>, with the later two having 2^n^o(1)-time algorithms.
Like in our analysis of the greedy algorithm, our subexponential time algorithm gives a similar approximation guarantee even for slightly nonuniform weights, in particular when p_max/p_min≤ 2^O(1/α).


  * Approximation ratio tightness.
We prove that the O(log n/log C_) approximation ratio for the greedy algorithm is tight for Uniform Decision Tree.
We also prove that the O(logp_max/p_min) term in the approximation ratio for the greedy algorithm is necessary, in the sense that no algorithm can give a o(logp_max/p_min) approximation for Decision Tree when p_max/p_min = n^r for some r∈(0,1) unless P=NP.


  * Repeatable, noisy tests. <cit.> provides a method to convert a solution for Decision Tree into a solution for a variant of Decision Tree that handles noisy, repeatable tests. An immediate corollary of our result for the greedy algorithm is that the cost of a solution for the noisy problem derived from the greedy algorithm is at most C_· O(log n loglog n). 
Previously, this cost was bounded by C_· O(log^2 n loglog n). 





 §.§ Techniques

Our work gives a new analysis of the greedy algorithm for Decision Tree.
A key technical contribution of this work is to leverage upper bounds of Min Sum Set Cover and Set Cover for (Uniform) Decision Tree.
Previously, only connections in the reverse direction (i.e. lower bounds) were known between these problems: NP-hardness of attaining a 4-ε-approximation for Uniform Decision Tree was proved by reduction from Min Sum Set Cover, and NP-hardness of attaining a o(log n) approximation for Decision Tree was proved by reduction from Set Cover <cit.>.

At a high level, our analysis goes as follows.
By a simple double counting argument, we can compute the cost of a tree by summing the “weights” of the tree's interior vertices, rather than summing the depths of the hypotheses.
However, rather than accounting for all the interior vertices at once, we separately analyze the vertices with “imbalanced” splits and those with “balanced” splits.
Carefully choosing the definition of balanced and imbalanced is a key idea of the proof: previous analyses of the greedy algorithm <cit.> either make no distinction between interior vertices or use a different distinction.
A global entropy argument accounts for the vertices with balanced splits.
For the vertices with imbalanced splits, we use the fact that the greedy algorithm gives a constant factor approximation for Min Sum Set Cover <cit.>.
For Uniform Decision Tree, putting the two bounds together gives the desired approximation result.
For the general Decision Tree problem, we additionally prove and use a generalization of a result on the greedy algorithm's performance for Set Cover <cit.>.

For the subexponential time algorithm, we leverage our new result that the greedy algorithm gives an O(log n/log C_) approximation.
We first run the greedy algorithm. If the greedy algorithm returns a tree with cost at least n^3α/4, we return the greedy tree knowing we have an O(1/α) approximation. Otherwise, we find by brute force the “optimal tree up to depth n^α” in time 2^Õ(n^α), then recurse.







 §.§ Organization of paper


In Section <ref>, we formally introduce notation used throughout the paper.
In Section <ref>, we state our results.
In Section <ref>, we sketch a proof of Theorem <ref>, that the greedy algorithm gives an O(log n/log C_ + logp_max/p_min) approximation on Decision Tree.
Since the proof of Theorem <ref> is involved, we prove the special case of Theorem <ref> for Uniform Decision Tree with binary tests in Section <ref>, and give the full proof in Appendix <ref>.
In Section <ref>, we state the subexponential time approximation algorithm and give a sketch of the analysis, and we give a formal analysis in Section <ref>.
In Section <ref>, we describe some related work.
In Section <ref>, we conclude with some open problems.

We leave some details to the appendices.
A lemma on the greedy algorithm's performance in a generalization of Set Cover that is used in the proof Theorem <ref> is proved in Appendix <ref>.
In Appendix <ref>, we prove Propositions <ref> and <ref>, which show two ways that Theorem <ref> is tight.
In Appendix <ref>, we demonstrate a rounding trick that allows us to assume p_min≥1/(n) without changing the difficulty of approximating Decision Tree.






§ PRELIMINARIES



For a positive integer a, let [a]={1,…,a}.
All logs are base 2 when the base is not specified.
The Decision Tree problem is as follows: given a set of hypotheses [n] with probabilities p_1,…,p_n summing to 1, and m distinct K-ary tests, output a decision tree 𝒯 with hypotheses as leaves, such that the weighted average of the depth of the leaves is minimal. 
Formally, a K-ary test is a map τ:[n]→ [K].
We refer to K as the branching factor of the test τ, and the elements of [K] as the possible answers to the tests.
We think of a test τ as defining a K-way partition of [n].
A decision tree 𝒯 is a rooted tree such that each interior vertex v has the index j_v ∈ [m] of some test, and the edge to the i-th child of v is labeled with i ∈ [K].
We say that a hypothesis h∈[n] is consistent with a vertex v if, in the root-to-v path, the edge following any vertex u has label τ_j_u(h).
We let L(v) denote the set of hypotheses h that are consistent with v.
We say a decision tree 𝒯 is complete if, for all h∈[n], there exists a (unique) leaf v∈𝒯 such that L(v)={h}, and for a complete decision tree 𝒯, let d_𝒯(h) denote the depth of this vertex v.
The cost of a complete decision tree 𝒯 is defined to be the average depth of the leaves, weighted by p_h, i.e.
    C(𝒯)      ∑_h∈ [n]^ p_h d_𝒯(h).

We set 𝒯_ to be a complete decision tree that minimizes C(𝒯_) (in general, there may be more than one optimal decision tree), and abbreviate C_ C(𝒯_).

This paper is concerned with the greedy algorithm for Decision Tree.
We call a decision tree greedy if the test τ_j_v of each interior vertex v minimizes the (weighted) number of hypotheses of the largest partition in τ_j_v's partitioning of L(v).
Formally, a decision tree 𝒯 is greedy if, for all interior vertices v∈𝒯, we have

    j_v ∈_j( max_k∈[K]p(L(v)∩τ_j^-1(k)) ),

where p(S) = ∑_h∈ S^ p_h for S⊆[n].
Given a Uniform Decision Tree instance, we let 𝒯_G be a complete, greedy decision tree, choosing one arbitrarily if there is more than one.
For brevity, we write C_G  C(𝒯_G).

We remark that, when K>2, our notion of a “greedy” algorithm for Decision Tree is not the only one.
As mentioned in the previous paragraph, our definition of greedy chooses, at each vertex in the decision tree, the test that minimizes the (weighted) number of candidate hypotheses, assuming a worst-case answer to the test. Our definition corresponds to the definition by <cit.>, but other choices include maximizing the (weighted) number of pairs of hypotheses that are distinguished <cit.> and maximizing the mutual information between the test and the remaining hypotheses <cit.>. 
For binary tests, K=2, these definitions are all equivalent.

Define (R) as Decision Tree with the guarantee that p_max/p_min≤ R. 
In this notation, (1) is Uniform Decision Tree. 




§ OUR RESULTS





 §.§ Greedy algorithm


The main driver of this paper is Theorem <ref>, which relates the cost of the greedy algorithm to the optimal cost for Decision Tree.


  
  For any instance of Decision Tree on n hypotheses, we have
  
    C_G ≤(12·log(1/p_min)/log C_ + ln( p_max/p_min) )· C_.


Our theorem holds for any branching factor K, and when C_G is the cost of an arbitrary tree produced by the greedy algorithm above.
As C_≥log_K n always, our result implies that the greedy algorithm always gives an O(log n/loglog n) approximation for Uniform Decision Tree when the branching factor is a constant, resolving the conjecture of <cit.>.
Additionally, if C_ is Ω(n^α) for constant α and the weights are uniform, then the greedy algorithm obtains a constant O(1/α) approximation.
We use this fact crucially in designing our subexponential time approximation algorithms.

For the simpler case when K=2 and the weights p_h are uniform, we give a sketch of the proof in Section <ref> and a full proof in Section <ref>.
This full result is sketched in Section <ref> and proven in full in Appendix <ref>.
For Uniform Decision Tree, the constant 12 can be improved to 6, and, when n is sufficiently large, 4+ε, so that greedy gives a (4+ε)log n/log C_ approximation (see Section <ref>).

Note that the terms log(1/p_min) and ln(p_max/p_min) in the approximation ratio can be arbitrarily large.
However, a rounding trick before running the greedy algorithm <cit.> allows us assume that all the weights are at least 1/n^2, and hence log(1/p_min)≤ 2log n and ln(p_max/p_min)≤ 2ln n in (<ref>).
The details are given in Appendix <ref>.

 


 §.§ Subexponential time algorithm



Using Theorem <ref>, we give a subexponential time algorithm that achieves a constant factor approximation for the Decision Tree problem when the weights are close to uniform.


For any α∈(0,1) and R≥ 1, there exists an (25/α+log R) approximation algorithm for (R) with runtime 2^O( n^αlog(Rn) log m).
For Uniform Decision Tree, for any ε>0, we can achieve a 9+ε/α approximation in the same runtime.

In Section <ref>, the subexponential time algorithm is stated and an analysis is sketched.
The analysis is given formally in Section <ref>.
Importantly, this result implies that achieving a super-constant approximation ratio is not NP-hard, given the Exponential Time Hypothesis. 
As an informal proof, suppose for contradiction there was a polynomial reduction from 3-SAT to achieving a f(n) approximation ratio for Uniform Decision Tree for some f(n)→∞ as n→∞. 
By Theorem <ref>, there exists a 2^n^o(1)-time algorithm to achieve a f(n) approximation for Uniform Decision Tree, and thus a 2^n^o(1)-time algorithm to solve 3-SAT, contradicting the Exponential Time Hypothesis.
This adds approximating Uniform Decision Tree to a list of interesting natural problems that have subexponential or 2^n^o(1) time algorithms but are not known to be in P.
Figure <ref> illustrates the contrast between Decision Tree and Uniform Decision Tree.




 §.§ Approximation ratio tightness

We also show that the O(log n/log C_) approximation ratio is tight up to a constant factor for the greedy algorithm by generalizing the example given by <cit.>. 
The proof is given in Appendix <ref>.


There exists an n_0 such that for all n≥ n_0 and any C^*∈[log n,n], there exists an instance of Uniform Decision Tree with branching factor 2 for which

    C_G≥C^* log n/16log C^*,     and    
      C_≤ 8C^*.



We also show that, when the weights are non-uniform, the ln(p_max/p_min) term in the approximation ratio of Theorem <ref> is computationally necessary.


Let r∈(0,1). Then, for n sufficiently large, approximating (2n^r log n) to a factor of r/12log n is NP-hard.

In other words, even if the ratio p_max/p_min is guaranteed to be O(n^r) for a constant r∈(0,1), one cannot give a o(log n) approximation algorithm unless P=NP. 
The proof is given in Appendix <ref>.










 §.§ Decision tree with noise


Theorem <ref> implies an improved black-box result for a noisy variant of Decision Tree.
 <cit.> considers a variant of Decision Tree with binary tests where the output of each test may be corrupted by i.i.d. noise. 
Formally, there exists ε>0 such that querying any test τ on any hypothesis h, outputs the correct answer τ(h) with probability 1-δ_τ,h and the wrong answer with probability δ_τ,h, for some δ_τ,h∈[0,1/2-ε).
Tests are repeatable, with each one producing different draws of the noise.
 <cit.> gives an algorithm that turns a decision tree of cost C for the noiseless problem into a decision tree with cost O(Clog Cloglog C) for the noisy problem by repeating queries sufficiently many times.

Combining 's result with the greedy algorithm for Uniform Decision Tree gives an algorithm for the noisy problem using an average of O(C_Glog C_G loglog C_G) queries.
Previously, using the bound C_G≤max(C_· O(log n), n), the noisy problem's cost was bounded by C_· O(log^2nloglog n).
However, by Theorem <ref>, we have C_G≤ C_· O(log n/log C_), so we in fact have cost at most C_· O(log nloglog n), improving the cost ratio to the optimal solution of the noiseless problem by a nearly quadratic factor.




















§ SKETCH OF PROOF OF THEOREM <REF>



In this section, we sketch a proof of Theorem <ref>.
We first sketch the proof assuming that the branching factor is 2, so that 𝒯_G is a binary tree, and that the distribution is uniform (p_h=1/n for all h∈[n]).
Since the proof of Theorem <ref> is involved, we give the details of this easier result in Section <ref>.
At the end of the section, we give the additional ideas necessary to complete the full proof of Theorem <ref>.
The details of the full proof are given in Appendix <ref>.




 §.§ Uniform weights and binary tests


Recall that p(v)∑_h∈ L(v)^ p_h and that, as the weights are uniform, p_h=1/n for all h∈[n].
By a simple double counting argument (Lemma <ref>), we can compute the cost of the greedy tree by summing the weights of the vertices rather than summing the depths of leaves.
That is,

    C_G
     =  ∑_v∈𝒯_G^o^ p(v),

where the sum is over the interior vertices of 𝒯_G.



  
Defining balanced and imbalanced vertices.
We then define balanced and imbalanced vertices with respect to a parameter δ∈(0,1), which we eventually set to O(1/C_).
These definitions are crucial to the proof.
A vertex is imbalanced[We remark that imbalanced vertices can have p(v^-) arbitrarily close to p(v)/2, so the hypotheses at vertex v are not necessary split in an imbalanced way. However, as we show (Lemma <ref>), all balanced vertices are in fact split in a balanced way with p(v^-)/p(v)≥δ/2, hence the terminology.] if there exists an integer s (called the level) such that p(v) > 2δ^s and p(v^-)≤δ^s. 
Here, v^- is the child of v containing a smaller weight of hypotheses in its subtree. We say v is balanced if it is not imbalanced.
Note that imbalanced vertices exist only for s≤ s_max, where s_maxlog n/log1/δ.
We prove a structural result (Lemma <ref>) that shows that the level-s imbalanced vertices of 𝒯_G can be partitioned into downward paths, which we call chains, such that, for all s, each leaf has vertices from at most one level-s chain among its ancestors.
The parameter δ quantifies how many chains we consider: smaller δ means fewer, longer chains, and larger δ means more, shorter chains.
We optimize the choice of δ at the end of this proof sketch.
In the remainder of the proof, we bound the weight of the balanced and imbalanced vertices separately.



  
Bounding the weight of balanced vertices.
To bound the weight of balanced vertices, we use an entropy argument.
We consider the random variable corresponding to a uniformly random hypothesis from [n].
On one hand, this random variable has entropy log n.
On the other hand, we can take a uniformly random hypothesis from [n] by an appropriate random walk down the decision tree. 
Starting from the root, at each vertex, we step to a child with probability proportional to the number of hypotheses in that child's subtree.
The total entropy of this process is given by ∑_v∈𝒯_G^ p(v)ℍ(v), where ℍ(v)ℍ(p(v^-)/p(v)) is the entropy of the random walk's step at v.
A simple argument (Lemma <ref>) shows that, for all balanced vertices v, we have p(v^-)/p(v) ≥δ/2 and hence ℍ(v) ≥ℍ(δ/2) ≥δ/2log2/δ.
We thus have

    log n    =  ∑_v∈𝒯_G^ p(v)ℍ(v) ≥∑_v balanced^ p(v)ℍ(v) ≥δ/2log(2/δ)∑_v balanced^ p(v).

Hence,

    ∑_v balanced^ p(v)     ≤ log n/log2/δ·2/δ.




  
Bounding the weight of imbalanced vertices.
To bound the cost of imbalanced vertices, we crucially use a connection to Min Sum Set Cover (MSSC).
In MSSC, one is given a universe S and sets A_1,…,A_M, and needs to construct an ordering σ:[M]→[M] of the sets that minimizes the cost: the cost of a solution σ is the average of the cover times of the elements in the universe S.
That is, the cost (σ) of a solution σ is

    (σ)
        1/n∑_h∈ S^min{ℓ: h∈ A_σ(ℓ)}.

A result by Feige, Lovasz, and Tetali shows that the greedy algorithm gives a 4 approximation of MSSC, and they show this is tight by proving that finding a (4-ε) approximation of MSSC is NP-hard.
On the lower bound side, a connection between MSSC and Decision Tree was already known: Chakaravarthy et al. <cit.> proved that it is NP-hard to approximate Uniform Decision Tree with ratio between than 4-ε by a reduction to MSSC.
The key technical contribution of our work is showing that there is also a connection on the upper bound side.
Bounding the weight of imbalanced vertices works as follows.

  
  * For each chain P, define a corresponding instance P
    (Definition <ref>) of 
 Min Sum Set Cover induced by the chain P=(P_1,…,P_|P|) as follows:



  * Universe S L(P_1), the set of all hypotheses that are consistent with P_1.

  * For j=1,…,m, the set A_j is the set of hypotheses in S that give the minority answer of test j with respect to hypotheses S. (See Figure <ref>).

  * For each h=1,…,n, a set A_m+h{h}∩ S. These tests are included for technical reasons.

Note we have a total of m + n sets, so that a solution is a permutation σ:[m+n]→[m+n].
The sets A_j for j=1,…,m are chosen so that the second step below holds.


  * Prove that the weight of a chain P is bounded by the cost of a greedy solution to MSSCP (Lemma <ref>), and hence, using a result of Feige, Lovasz, and Tetali (Theorem <ref>), by 4 times the optimal cost of MSSCP (Corollary <ref>).
That is, there exists a greedy solution σ_G to P such that

    ∑_v∈ P^ p(v) 
       ≤ P(σ_G)
       ≤ 4P(σ_OPT)

This step is somewhat technical, as one must show that the greediness of the greedy decision tree 𝒯_G produces a greedy solution to P.
The choice of σ_G is natural: for ℓ=1,…,|P|, let σ_G(ℓ) be the index of the test used at vertex P_ℓ in the chain P (see Figure <ref>).
However, showing that this σ_G is in fact a greedy solution to P is a subtle argument that depends on the carefully chosen definition of a chain.



  * Prove that, for any integer s, the sum, over all level-s chains P, of optimal cost of MSSCP, is bounded by C_OPT (Lemma <ref>).
Hence,

    ∑_P∈𝒫_s^P(σ_OPT)
       ≤ C_OPT.

This step is also technical, as one must draw the connection between the optimal MSSC solution and the optimal decision tree.


  * In total, we have

    ∑_v level s^ p(v)
          =  ∑_P∈𝒫_s^∑_v∈ P^ p(v)
       ≤ ∑_P∈𝒫_s 4P(σ_OPT)
       ≤  4C_OPT,

where the first inequality is by part 2 and the second inequality is by part 3.
In other words, for any integer s, the sum of the weights of all level s chains is at most 4C_OPT.
Hence, the sum of the weights of vertices in any chain, and thus the total weight of all imbalanced vertices, is at most 4s_maxC_OPT (Lemma <ref>), where s_max is the number of levels.
As s_max≤log n/log1/δ, we have

    ∑_v imbalanced^ p(v)  ≤ 4log n/log1/δ· C_OPT.



To finish the proof, we bound

    C_G
       =  ∑_v∈𝒯_G^o^ p(v)
       =  ∑_v balanced^ p(v) + ∑_v imbalanced^ p(v)
       ≤ log n/log2/δ·2/δ + 4log n/log1/δ· C_OPT.

The above is optimized roughly when δ=1/C_OPT, giving the desired bound of C_G≤6log n/log C_OPT· C_OPT.
If n is sufficiently large, taking δ=10/ε C_OPT yields C_G≤(4+ε)log n/log C_· C_OPT.


















 §.§ General weights and larger K

The proof of the general Theorem <ref> follows similarly to the specific case given above.
The two differences are that Theorem <ref> is stated for general K and for general, not-necessarily-uniform distributions p_1,…,p_n.

Adapting the proof to general K is the easier step.
The main difference is the definition of an imbalanced vertex.
Now, we say a vertex v is imbalanced if there is an integer s such that p(v)>2δ^s and p^-(v)≤δ^s, where p^-(v) is the total weight of hypotheses in the subtrees of all children of v except the majority vertex, v^+, the child of v with the largest weight of hypotheses.
Under this definition, a similar analysis follows.
Note that p^-(v) could be much larger than p(v^+) in this case, but this does not affect the proof much.
A little more care needed in the entropy argument for balanced vertices, and with the MSSC instance defined by a path P now taking A_j to be all hypotheses that do not take the majority answer of τ_j with respect to the MSSC universe.
Note that, if we specialize to K=2, the value p^-(v) is simply p(v^-).

In the weighted case, we again define v to be imbalanced if there is an integer s such that p(v)>2δ^s and p^-(v)≤δ^s.
We again bound the cost of the balanced vertices by an entropy argument, and the cost of the imbalanced vertices via a connection to Min-Sum-Set-Cover.
However, because the entities are now weighted, we need to consider the greedy algorithm for a weighted generalization of MSSC called Weighted Min-Sum-Set-Cover (WMSSC).
In order to make the condition between the greedy decision tree and the greedy solution to WMSSC, we need a somewhat technical definition:
call a vertex v is h-heavy if h is consistent with v and p_h>p^-(v).
Define q(v) = p_h if there exists h such that v is h-heavy, and set q(v)=0 otherwise.
One can easily check that, for any vertex v, there is at most one h such that v is h-heavy, so q(v) is well defined.
Now, we follow the argument in the uniform case, bounding

    ∑_v imbalanced^ (p(v) - q(v))
          ≤ ∑_s=1^s_max∑_P∈𝒫_s^∑_v∈ P^ (p(v) - q(v)) 
       ≤ ∑_s=1^s_max∑_P∈𝒫_s^P(σ_GP) 
        ≤ ∑_s=1^s_max∑_P∈𝒫_s^ 4P(σ_OPTP) 
       ≤ ∑_s=1^s_max C_OPT =  s_maxC_OPT,

where σ_GP and σ_OPTP are the greedy solution and optimal solution, respectively, to the corresponding WMSSC.
The first inequality holds because p(v) - q(v)≥ 0 for all v and every imbalanced vertex is in some chain[It is inequality because some imbalanced vertices may be in multiple chains].
The second inequality holds by a technical lemma (Lemma <ref>) comparing the greedy decision tree with a greedy solution to WMSSC.
Just as for MSSC, the greedy algorithm gives a 4 approximation for WMSSC, so the third inequality holds.
Additionally, for all s=1,…,s_max, we can still bound ∑_P∈𝒫_s^P(σ_OPT), the sum of all WMSSC costs in a single level, by C_OPT, so the fourth inequality holds.
To finish:

    ∑_v imbalanced^ p(v)
       ≤ s_maxC_OPT + ∑_v∈𝒯_G^ q(v)
       ≤ s_maxC_OPT + ( 1+lnp_max/p_min) C_OPT.

The last inequality (Lemma <ref>) comes from comparing, for fixed h, the vertices v of the greedy tree 𝒯_G that are h-heavy to an appropriate SET-COVER instance, and using the fact that the greedy algorithm on a weighted generalization of SET-COVER gives a 1+ln( p_max/p_min) approximation (Theorem <ref>).



§ SKETCH OF PROOF OF THEOREM <REF>




 §.§ Algorithm

We describe the algorithm that achieves a 25/α + log R approximation for (R).
In Section <ref>, we give the details and describe how the same algorithm with minor adjustments gives an improved approximation guarantee for Uniform Decision Tree.

The key idea in the algorithm is that, if the optimal tree has cost at least n^3α/4, then the greedy algorithm gives an O(1/α) approximation by Theorem <ref>. 
Fix b(12log n +log R)n^α.
Our algorithm first computes the greedy tree.
If the cost of the greedy tree is at least n^-α/4b, we simply return the greedy tree. 
Otherwise, we perform an exhaustive search over decision trees of depth at most b such that all hypotheses not consistent with vertices at depth b are uniquely distinguished.
We choose such a tree 𝒯 with minimum cost (see definition of C(𝒯; H) below).
Finally, at each leaf v of 𝒯 at depth b, we recursively compute a decision tree that distinguishes the hypotheses consistent with v.
The runtime of this algorithm is dominated by the exhaustive search, which we can solve in time 2^Õ(n^α) using a divide-and-conquer algorithm. 

Let C(𝒯; H) denote the cost of a decision tree 𝒯 with respect to hypothesis set H, given by

    C(𝒯; H) 1/p(H)∑_h∈ H^ p_h d_𝒯(h),

where d_𝒯(h) is the depth of the deepest vertex of 𝒯 consistent with h.
In this way, we have C(𝒯) = C(𝒯; [n]).
To solve the Decision Tree instance, we run Fulltree_α([n]) below.




 §.§ Analysis sketch

We now sketch an analysis of the algorithm.
First, it is easy to check that FullTree_α([n]) returns a valid decision tree.
By Theorem <ref>, when the greedy tree is used in the recursive call FullTree_α(H), it gives an O(1/α) + log R approximation to the (R) instance induced by H.
Hence, by careful bookkeeping, the greedy trees included in the output tree contribute at most (O(1/α)+log R)C_OPT to the cost (Lemma <ref>).
If the greedy tree is not used, then, in the optimal tree, the weighted average depth of the hypotheses is at most n^3α/4. 
Hence, by a simple counting argument, at each recursive call, the fraction of undistinguished hypotheses shrinks by a factor of n^α/4, so the maximum depth of recursive calls is O(1/α) (Lemma <ref>).
Careful bookkeeping shows that, for any i=1,…,O(1/α), the outputs to PartialTree(H,b) called from the ith level of recursion collectively contribute at most C_OPT to the cost of the output tree (Lemma <ref>).
Hence, the trees computed by exhaustive search across all levels of recursion contribute a cost of O(C_OPT/α).
Hence, the cost of our output tree is (O(1/α)+log R)C_OPT.




§ PROOF OF THEOREM <REF> FOR UNIFORM WEIGHTS AND K=2




We prove a special case of Theorem <ref> when K=2 and the weights p_1=⋯=p_n=1/n are uniform, that is, we show that the Uniform Decision Tree with binary tests gives an O(log n/log C_) approximation.
Throughout this section, we have a Uniform Decision Tree instance with hypotheses [n] and tests τ_1,…,τ_m:[n]→[2].

  
  For any instance of the Uniform Decision Tree problem on n hypotheses with branching factor  2, and any greedy tree 𝒯_G with average cost C_G, we have
  
    C_G
            ≤ 6log n/log C_· C_.






 §.§ Notation



We use the following notation for our proof.
These notations help us reason about the greedy tree.
We write v∈𝒯_G to mean that v is a vertex of tree 𝒯_G, and we write v∈𝒯_G^o to mean that v is a interior vertex.
We say the length of a path in the tree is the number of edges along the path.
For v,u∈𝒯_G, we say v is an ancestor of u if there is a (possibly degenerate) path from v to u going down the tree.
In particular, v is an ancestor of v.
We write this as u⊑ v.
We call u a descendant of v if and only if v is an ancestor of u.
For v∈𝒯_G, let L(v)⊆[n] denote the set of hypotheses consistent with v.
For a subset S⊆ [n] of hypotheses, denote its weight or cost by p(S) ∑_h∈ S^ p_h = |S|/n. 
For brevity, let p(v) p(L(v)), denoting the weight of vertex v, and we say the weight of a set of vertices is the sum of the weights of the individual vertices in the set.



 §.§ The basic argument

The following lemma shows that, rather than accounting the cost of the greedy tree by summing the depths of the leaves associated with the hypotheses, we can instead account the cost by summing the weights of vertices of the tree.

  
  We have C_G =  ∑_v∈𝒯_G^o^ p(v). 


  We have,
  
    C_G
            =  ∑_h∈[n]^ p_hd_𝒯_G(h) 
         =  ∑_h∈[n]^∑_v∈𝒯_G^o
     h⊑ v^ p_h
         =  ∑_v∈𝒯_G^o^∑_h∈ L(v)^ p_h
         =  ∑_v∈𝒯_G^o^ p(v),

  where, in the third equality, we switched the order of summation.


At a high level, our proof defines balanced and imbalanced vertices (next subsection) using a parameter δ and bound the weight of the balanced and imbalanced vertices separately.
We bound the weight of the balanced vertices by an entropy argument, and the weight of the imbalanced vertices by partitioning the imbalanced vertices into paths, called chains, and bounding the weights of each chain separately.
Overall, we get the following bound.
  
    C_G
         =  ∑_v∈𝒯_G^o^ p(v) 
         =  ∑_v balanced^ p(v) + ∑_v imbalanced^ p(v)
         ≤ log n/log2/δ·2/δ + 4log n/log1/δ· C_.
 
  Choosing δ=1/C_ gives C_G≤6log n/log C_· C_.

For the rest of the proof, fix δ=1/C_.
Additionally, for convenience and without loss of generality, assume that our instance is nontrivial, i.e. there is some test j such that both of τ^-1_j(1) and τ^-1_j(2) have at least 2 hypotheses, as otherwise the greedy tree is optimal and C_G = C_ and the theorem is true.




 §.§ More notation: Majority and minority answers

We define majority (minority) answers, edges, children.
These definitions are useful for defining balanced and imbalanced vertices.
We later show that imbalanced vertices form paths whose edges are majority edges.
We call these paths chains.
We then analyze the balanced and imbalanced vertices separately, and in particular analyze each path of majority edges separately.


For each vertex v in the greedy tree, let j_v denote the test used at v.
For each vertex v, label its children by v^+ and v^- so that p(v^+)≥ p(v^-), with ties broken[any tiebreaking procedure suffices, as long as the tiebreaking is consistent with the k_j,S^+ and k_j,S^- notation in the next paragraph.] by labeling v^+ by the vertex corresponding to a test outputting 1.[it is possible to have a vertex that has one child, namely a test that doesn't distinguish any pairs of hypotheses at a vertex, but such a test is useless and never appears in either the greedy or optimal tree, so we assume such vertices don't exist.]
Accordingly, we have p(v) = p(v^+) + p(v^-) for all v∈𝒯_G^o.
Call the edge from v to v^+ a majority edge, and the edge from v to v^- a minority edge. 
This is illustrated in Figure <ref>.

In order to reason about the greedy tree precisely, we use the following notation which is more technical.
For test j∈[m] and hypotheses S⊆[n], let k^+_j,S∈[2] be the answer to test τ_j that accounts for the maximum weight of hypotheses in S, and let k^-_j,S be the other index, with ties broken by k^+_j,S=1.
In other words, k^+_j,S and k^-_j,S are chosen so that |τ_j^-1(k^+_j,S)∩ S|≥ |τ_j^-1(k^-_j,S)∩ S|.
We call k^+_j,S the majority answer of test j with respect to hypothesis set S.
Call the other answer k^-_j,S the minority answer of test j with respect to hypothesis set S.
For all j∈[m] and S⊆ [n], let

    I_j,S^+   τ_j^-1(k^+_j,S),
          
      I_j,S^-   τ_j^-1(k^-_j,S).

We think of I_j,S^+ (I_j,S^-) as the set of hypotheses that, under test j, output the majority (minority) answer to test j with respect to set S.
Note that, with the above notation, we have L(v^+) = I_j_v,L(v)^+∩ L(v) and L(v^-) = I_j_v,L(v)^-∩ L(v).

The following is a key property of the greedy tree 𝒯_G: the weight of hypotheses consistent with the minority child v^- decreases as we descend the tree.

  For any vertices u of v with u a descendant of v, we have p(v^-)≥ p(u^-).



  Because 𝒯_G was constructed greedily, for all v∈𝒯_G^o, the test j_v was chosen to maximize the weight of I_j_v,L(v)^-∩ L(v), the hypotheses in L(v) giving the minority answer k_j_v,L(v)^-.
  Hence, any other test, in particular, the test j_u chosen at vertex u, has a smaller weight of hypotheses of L(v) that give the minority answer of j_u with respect to hypotheses L(v).
  Hence, we have p(v^-) ≥ p(I_j_u,L(v)^-∩ L(v)).
  Hence,
  
    p(v^-)
         ≥ p(I_j_u,L(v)^-∩ L(v)) 
         ≥ p(I_j_u,L(v)^-∩ L(u))  
         ≥   p(u^-).

  The second inequality holds because L(u)⊆ L(v).
  The third inequality holds because test j_u defines a partition of [n] into two parts, and I_j_u,L(v)^- is one of the two parts, so I_j_u,L(v)^-∩ L(u) is one of L(u^-) or L(u^+).









 §.§ Defining balanced and imbalanced vertices

In the following definition, we identify balanced vertices and imbalanced vertices.
By Lemma <ref>, we can separately bound the weights of the balanced and imbalanced vertices.

  
  Let s be a positive integer.
  
  
  * We say a vertex v∈𝒯_G^o is level-s imbalanced if p(v^-) ≤δ^s and p(v) > 2δ^s.
  
  * We say a vertex v is imbalanced if it is level-s imbalanced for some s, and balanced otherwise.
  
  * We say a level-s imbalanced vertex v is minimal if no descendant of v is also level-s imbalanced vertex, and a level-s imbalanced vertex v is maximal if no ancestor of v is level-s imbalanced.
  

Let 

    s_maxlog n/log1/δ

and note that level-s imbalanced vertices exist only for s≤ s_max.
The following lemma proves a structural result about balanced vertices, with the punchline being item (iii), which permits Definition <ref>.
For an illustration, see Figure <ref>.

  
  Let s be a positive integer.

  
  (i) If v is a level-s imbalanced vertex, then, among the children of v, only v^+ can be a level-s imbalanced vertex.
  
  (ii) Additionally, if v and u are level-s imbalanced vertices and v is an ancestor of u, then every vertex on the path from v to u is a level-s imbalanced vertex.
  
  (iii) Finally, the set of level-s imbalanced vertices can be partitioned into vertex disjoint paths, each of which connects a maximal level-s imbalanced vertex to a minimal level-s imbalanced vertex and contains only majority edges.



  For (i), note that if v is level-s imbalanced, then p(v^-)≤δ^s < 2δ^s, so v^- cannot be level-s imbalanced.
  Hence, among the children of v, only v^+ can be level-s imbalanced.

  For (ii), let v⊒ w⊒ u be three vertices in the tree.
  Suppose that v and u are level-s imbalanced.
  We know that p(v) ≥ p(w) ≥ p(u) > 2δ^s, and Lemma <ref> gives δ^s ≥ p(v^-)≥ p(w^-)≥ p(u^-).
  Hence w is level-s imbalanced.
  
  For (iii), note that each level-s imbalanced vertex has a maximal level-s imbalanced ancestor (possibly itself), so we may partition the level-s imbalanced vertices into sets based on their maximal level-s imbalanced ancestor.
  We claim each set in the partition is a connected path.
  Let v_1 be the (unique) maximal level-s imbalanced vertex in a set P.
  For ℓ=1,2,…, if v_ℓ has a level-s imbalanced child, let v_ℓ+1 be that child, which is unique by the first item and in P by definition.
  Let ℓ_P be the largest index such that v_ℓ_P is defined.
  Then v_ℓ_P has no level-s imbalanced children.
  We claim v_1,…,v_ℓ_P are the only vertices in the set P.
  Suppose not.  Let ℓ be the largest index such that v_ℓ has a level-s imbalanced descendant u not among v_1,…,v_ℓ_P.
  Then, by the second item, every vertex on the path from v_ℓ to u is level-s imbalanced.
  If ℓ=ℓ_P, this means v_ℓ_P has a level-s imbalanced child, a contradiction of the maximality of ℓ_P.
  Otherwise, as ℓ is maximal, v_ℓ+1 is not on the path from v_ℓ to u, in which case, by (ii), v_ℓ^- is level-s imbalanced, which contradicts (i).
  Thus, we always have a contradiction, so P is the path v_1,…,v_ℓ_P.
  By (i), every edge along P is a majority edge.
  This completes the proof.


Lemma <ref> motivates the following definition.

  
  Let s be a positive integer.
  A level-s chain, P=(P_1,…,P_|P|), is a path of level-s imbalanced vertices starting at a maximal level-s imbalanced vertex and ending at a minimal level-s imbalanced vertex.
  By Lemma <ref>, the level-s chains partition the level-s imbalanced vertices.
  We therefore let 𝒫_s denote the set of level-s chains.

In general, for s≠ s', a level-s chain might overlap with a level-s' chain.



 §.§ Bounding the weight of balanced vertices

We first prove a lemma that justifies the choice of the word “balanced”.

  For every balanced vertex v, we have p(v^-)≥δ/2p(v).
  


Assume for contradiction that p(v^-) < δ/2p(v).
Let s'>1 be the real number such that p(v^-) = δ^s' n.
In this way, p(v^-) ≤δ^s'n.
Then

    p(v) > 2/δp(v^-) = 2/δδ^s'n = 2δ^s'-1n > 2δ^s'n.

This implies that v is level-s' imbalanced, so v is imbalanced, a contradiction.

We now bound the contribution of the balanced vertices to the weight using an entropy argument.


  We have
  
    ∑_v balanced^ p(v) ≤log n/log2/δ·2/δ.



  For a vertex v with a test of index j, let X_v denote the binary random variable equal to τ_j(h) for an hypothesis h chosen uniformly at random from the hypotheses of L(v).
  Let ℍ(·) denote the entropy of a random variable.
  The entropy of a uniformly random hypothesis in [n] equals log n.
  On the other hand, we can pick a uniformly random hypothesis in [n] by starting at the root vertex v, sampling an answer X_v∈[2] for the test at v, stepping to u, the child of v corresponding to the chosen answer, and repeating with v=u, until we reach a leaf.
  In this process, at any vertex v, the probability of stepping to a child u is exactly p(u)/p(v).
  Hence, by a simple induction, the probability of reaching any vertex v in the tree during this process is exactly p(v). 
  The total entropy of this process is thus ∑_v∈𝒯_G^ p(v)·ℍ(X_v), as p(v) is the probability of reaching vertex v.
  For a balanced vertex v, Lemma <ref> implies δ/2≤ p(v^-)≤1/2.
  Hence,
  
    ℍ(X_v)
         =  p(v^+)log1/p(v^+) + p(v^-)log1/p(v^-) ≥ p(v^-)log1/p(v^-) ≥ δ/2log2/δ.

  We conclude
  
    log n
            =  ∑_v∈𝒯_G^ p(v)·ℍ(X_v) 
         ≥ ∑_v balanced^ p(v) ·ℍ(X_v)
         ≥ ∑_v balanced^ p(v)·δ/2log2/δ,

  and rearranging gives the desired result.






 §.§ Bounding the weight of imbalanced vertices


We now bound the weight of imbalanced vertices using a connection to MSSC.



  §.§.§ Defining Min Sum Set Cover

Recall that I_j,S^+ = τ_j^-1(k_j,S^+) and I_j,S^- = τ_j^-1(k_j,S^-) for all j∈[m] and S⊆[n].
 
  
Let P denote the instance of Min Sum Set Cover that is induced by the chain P=(P_1,…,P_|P|). 
This instance is given by


  * universe S L(P_1),

  * for j=1,…,m, sets A_j  I_j,S^-∩ S, and

  * for each h=1,…,n, a singleton set A_m+h{h}∩ S.[Some of these sets are empty, but we include them for notational convenience.]

Note we have a total of m + n sets.
A solution to the instance P is a permutation σ:[m+n]→ [m+n] corresponding to an ordering of the sets, and the cost P(σ) of a solution is the average of the cover times of the elements in the universe S.
Formally,

    P(σ)
        1/n∑_h∈ S^min{ℓ: h∈ A_σ(ℓ)} =  ∑_ℓ=1^m+n p( S ∖ (A_σ(1)∪⋯∪ A_σ(ℓ-1)) ).

  Note that the cost of any solution is finite, as each hypothesis h∈ L(v) is in some set A_j.
We sometimes refer to a solution σ by the sets A_σ(1),…,A_σ(m+n).


  
Since the initial Uniform Decision Tree instance always has a solution, any two hypotheses can be distinguished by one of the m tests.
Hence, there is at most one hypothesis h∈ S such that, for all j=1,…,m, we have h∉ A_j. In other words, all but one of the sets A_m+h for h∈[n] is not used.



We say a solution σ:[m+n]→[m+n] to P is greedy at index ℓ if the set A_σ(ℓ) covers the maximum number of elements not covered by sets A_σ(1),…, A_σ(ℓ-1).
We say a solution σ:[m+n]→[m+n] is greedy if it is greedy at index ℓ for all ℓ∈[m+n],

Note that, in the case of ties, there may be multiple greedy solutions to P. 
Note also that, for any partial assignment σ(1),…,σ(ℓ), one can always complete the solution greedily, so that σ:[m+n]→[m+n] is greedy at indices ℓ+1,ℓ+2,…,m+n.
Definition <ref> lets us leverage the following theorem, due to Feige, Lovász, and Tetali. 

  
  The greedy algorithm gives a 4-approximation to the MSSC problem.
  Formally, let σ_G be any greedy solution to the instance P, and let σ_ denote an optimal solution to P.
  We have
  
    P(σ_G) ≤ 4·P(σ_).







  §.§.§ Bounding chain weight above by MSSC cost

The section shows that the weight of a chain P is bounded by the cost of its corresponding MSSC instance.
To do this, we need the following technical lemma which shows that following the choices of the greedy tree yields a greedy solution to the MSSC, and hence the two weights are comparable.

  Let s be a positive integer and let P be a level-s chain.
  Then there exists a greedy solution σ:[m+n]→[m+n] to P, such that
  
  
    ∑_v∈ P^ p(v)
        ≤P(σ) .



  Let P=(P_1,…,P_|P|).
  Let S=SP be the universe and A_1,…, A_m+n be the sets of the instance P.
  For ℓ=1,…,|P|, let j_ℓ be the test used at vertex P_ℓ.
  Define a solution σ:[m+n]→[m+n] to P by setting σ(ℓ)=j_ℓ for ℓ=1,…,|P|, and completing the solution greedily.
  We claim σ is a greedy solution.
  To prove this, we show the following. 

  
  (i) For all j∈[m] and 1≤ℓ≤ |P|, the majority answer for test j with respect to S=L(P_1) is the same as the majority answer for test j with respect to L(P_ℓ).
  Equivalently, for all j∈[m] and 1≤ℓ≤ |P|, we have A_j=I_j,S^-∩ S = I_j,L(P_ℓ)^-∩ S.
  As an immediate consequence, we know A_j_ℓ contains all of L(P_ℓ^-) and none of L(P_ℓ^+).
  
  (ii) The set of hypotheses of S not covered by A_j_1, …,A_j_ℓ-1 is exactly L(P_ℓ).
  
  (iii) For each 1≤ℓ≤ |P|, among sets A_1,…,A_m+n, the set A_j_ℓ covers the maximum number of hypotheses in L(P_ℓ). i.e. we have
  
    p(A_j_ℓ∩ L(P_ℓ))=max_j∈[m+n]p(A_j∩ L(P_ℓ)).


  These points suffice, as (ii) and (iii) tell us that σ is greedy at indices 1,…,|P|, so by construction σ is greedy.

  To show (i), fix j∈[m] and ℓ∈{1,…,|P|}.
  As P_ℓ is level-s imbalanced, we also have p(P_ℓ)>2δ^s and p(P^-_ℓ) ≤δ^s and p(P^+_ℓ) > δ^s, so k_j,L(P_ℓ)^+ accounts for more than half of the hypotheses in L(P_ℓ).
  On the other hand, as P_1 is level-s imbalanced, we have p(I_j,S^-∩ L(P_ℓ)) ≤ p(I_j,S^-∩ S) ≤ p(P^-_1) ≤δ^s, so the majority answer for test j with respect to hypothesis set S also accounts for more than half of the hypotheses in L(P_ℓ).
  Hence k_j,S^+ = k_j,L(P_ℓ)^+ for all j∈[m] and 1≤ℓ≤ |P|.

  Item (ii) follows because L(P_ℓ) is the set of hypotheses consistent with P_ℓ, which was obtained by following the majority edges from P_1.
  This means L(P_ℓ) contains all the hypotheses of S not consistent with a minority child of one of P_1,…,P_ℓ-1.
  By (i), this is exactly S∖ (A_j_1∪⋯∪ A_j_ℓ-1).

  For (iii), at vertex P_ℓ in the greedy decision tree, the test index j=j_ℓ maximizes the weight p(I_j,L(P_ℓ)^-∩ L(P_ℓ)).
  By (i), this index j equivalently maximizes p(A_j∩ L(P_ℓ)), as desired.
  This completes the proof that σ is greedy.

  We now return to the proof of Lemma <ref>.
  Take the greedy solution σ given above.
  For 1≤ℓ≤ |P|, the set of vertices of S not covered by A_σ(1),…,A_σ(ℓ-1) is exactly L(P_ℓ), which has weight p(P_ℓ).
  Hence, by (<ref>),
  
    P(σ)
            ≥ ∑_ℓ=1^|P|  p( S∖(A_σ(1)∪⋯∪ A_σ(ℓ-1)) )
         =  ∑_ℓ=1^|P| p(P_ℓ),

  as desired.


By Theorem <ref>, we have the following immediate corollary.


  Let P be any chain, and σ_ be the optimal solution to P.
  Then
  
    ∑_v ∈ P^ p(v)
        ≤ 4P(σ_) .









  §.§.§ Bounding MSSC cost above by C_

We now show that the optimal MSSC solution can be compared to the optimal decision tree cost, C_.
For all chains P, let σ_GP:[m+n]→[m+n] be a greedy solution to P given by Lemma <ref>, and let σ_P be an optimal solution to P.


  
  Let s be a positive integer.
  We have
  
    ∑_P∈𝒫_s^P(σ_P)
        ≤ C_.



  Let SP be the universe of the instance P, and let A_1,…, A_m+n be the sets.
  Construct a path w_1,…,w_ℓ in 𝒯_ such that w_1 is the root and w_ℓ is a leaf, which is identified with some hypothesis h, and, for ℓ=1,…,ℓ-1, if the test at vertex w_ℓ has index j_ℓ, the edge to its child w_ℓ+1 corresponds to the answer k_j_ℓ,SP^+, the majority answer of test j_ℓ with respect to set SP.
  Since we follow the edges with label k^+_j_ℓ,SP, this corresponds to following the path for an hypothesis contained in I_j_ℓ,SP^+. 
  In other words, we have, for ℓ=1,…,ℓ-1,
  
    L(w_ℓ+1) ∩ SP =  (L(w_ℓ)∩ SP) ∖ I_j_ℓ,SP^-
         =  (L(w_ℓ)∩ SP) ∖ A_j_ℓ.

  Thus the sequence A_j_1,…,A_j_ℓ, A_m+h covers SP, and thus gives a valid solution σ_TREE to the instance P, where σ_TREE(1) = j_1, σ_TREE(2)=j_2,…,σ_TREE(ℓ)=j_ℓ, σ_TREE(ℓ+1)=m+h, and σ_TREE on larger indices is arbitrarily chosen.
  Note that the depth of the leaf for hypothesis h is at least the number of vertices of w_1,…,w_ℓ that are on the root-to-leaf path of h, and this number is min{ℓ:h∈ A_j_ℓ}, except for h^*, in which case it is 1 smaller.
  Furthermore, for some h∈ SP, the depth of leaf h is at least min{ℓ:h∈ A_j_ℓ}+1, because otherwise all the branches leaving the path have one leaf, which can only happen if our Uniform Decision Tree instance is trivial, and it is not trivial by assumption.
  Thus,
  
    1/n∑_h∈ SP^ d_𝒯_(h) 
            ≥ -1/n + 1/n + 1/n∑_h∈ SP^min{ℓ:h∈ A_j_ℓ}
        ≥ P(σ_TREE)  
         ≥ P(σ_).

  The -1/n and 1/n account for the lower order terms described above.
  Summing (<ref>) over P∈𝒫_s gives
  
    C_    =  1/n∑_h∈[n]^ d_𝒯_(h)
         ≥ 1/n∑_P∈𝒫_s^∑_h∈ SP^ d_𝒯_(h)
         ≥ ∑_P∈𝒫_s^P(σ_),

  where in the first inequality, we used that every leaf has at most one maximal level-s imbalanced ancestor, and hence it is in at most one MSSC universe SP.





  §.§.§ Bounding imbalanced vertex weight above by C_

We now finish our bound of the weight of imbalanced vertices.


  We have 
  
    ∑_v imbalanced^ p(v)
         ≤ 4log n/log1/δC_.



  Each imbalanced vertex v is level-s imbalanced for some positive integer s, so it is part of some level-s chain, P.
  Hence,
  
    ∑_v imbalanced^ p(v) 
         ≤ ∑_s=1^s_max∑_P∈𝒫_s^∑_v ∈ P^ p(v) 
            ≤ ∑_s=1^s_max∑_P∈𝒫_s^  4P(σP_) 
        ≤ ∑_s=1^s_max 4C_ =  4log n/log1/δC_

  The first inequality is not equality because some vertices may be level-s imbalanced for more than one integer s.
  The second inequality is by Corollary <ref>.
  The third inequality is by Lemma <ref>.



















 §.§ Finishing the proof


  We have
  
    C_G
         =  ∑_v∈𝒯_G^o^ p(v) 
            =  ∑_v balanced^ p(v) + ∑_v imbalanced^ p(v)
         ≤ log n/log2/δ·2/δ + 4log n/log1/δC_
        =  2log n/log 2C_· C_ + 4log n/log C_ C_ <  6log n/log C_· C_,
 
  as desired. 
  In the first inequality, we used Lemma <ref> and Lemma <ref>.





§ PROOF OF THEOREM <REF>




For the entirety of this section, fix α<1, R≥ 1, and an instance of (R).
We first analyze Algorithm <ref>, showing that running FullTree_α([n]) gives a (25/α+log R) approximation for (R), and then describe how the algorithm can be modified to give a 9.01/α approximation for Uniform Decision Tree in subexponential time.





 §.§ Runtime


Algorithm <ref> runs in time O(n (Km)^b+1).


  Each call to Algorithm <ref> calls at most mK recursive calls with one less depth. This means the total number of recursive calls is O((Km)^b). Since the local runtime of each call is O(nmK), the total runtime is O(n (Km)^b+1).




Algorithm <ref> runs in time O(n^3 (Km)^b+1) = 2^O(n^αlog (Rn) log m).


  The cost is dominated by the cost of Algorithm <ref>. The depth of recursive calls is at most n and the width of the recursive call tree is at most n, thus the total runtime is at most n^2 times the runtime of Algorithm <ref>. Thus the runtime is O(n^3 (Km)^b+1) 




 §.§ Notation

To formally analyze the approximation guarantees of Algorithm <ref>, we need to generalize some earlier definitions. 
We say a decision tree 𝒯 is complete with respect to hypothesis set H up to depth b if, for all hypotheses h∈ H, either there exists a leaf v of 𝒯 with L(v)∩ H = {h}, or d_𝒯(h) ≥ b.
Note that 𝒯 is complete with respect to hypothesis set H if it is complete up to depth b for all b.

Given the tests τ_1,…,τ_m:[n]→[2] and a subset H of hypotheses, let Φ_H be the (R) instance induced by H. 
It is given by hypotheses H and the tests τ_1,…,τ_m: H → [2] restricted to domain H.
It is easy to check that, for this instance, we indeed have p_max'/p_min'≤ R.
We let 𝒯_G(H) denote a greedy tree for the instance Φ_H.
We let 𝒯_(H) denote an optimal tree for instance Φ_H.
We also define the optimal tree for Φ_H up to depth b by

    𝒯_(H, b) _𝒯 complete w.r.t. H
    up to depth b C(𝒯 ; H).

Importantly, 𝒯_(H,b) is computable by a straightforward recursive algorithm in time O(n(mK)^b) by Algorithm <ref>.
For convenience, let

    C_G(H)      C(𝒯_G(H); H)
      
    
      C_(H)      C(𝒯_(H); H)
      
    
      C_(H, b)      C(𝒯_(H, b); H).

In this way, we have

    C_(H, b)  ≤ C_(H)  ≤  C_G(H).






 §.§ Approximation guarantee

It is easy to see that PartialTree(H,b) computes 𝒯_(H,b) (or one such tree, if there are several).
Let ℱ_i be the family of hypothesis sets H such that FullTree_α(H) is called at the ith level of recursion and the greedy tree 𝒯_G(H) is not returned. We consider FullTree_α([n]) to be the 0th level of recursion so that ℱ_0 = {[n]}.
Let ℱ_ denote the family of hypothesis sets H such that FullTree_α(H) is called and 𝒯_G(H) is returned in that call.
Let ℱ_ = ℱ_1∪ℱ_2 be a partition such that H∈ℱ_2 if and only if p(H)<1/n^2
We know that, for any H and H', if FullTree_α(H') is called recursively from FullTree_α(H), then H'⊆ H.
Thus, under these definitions, we know that, for all i, the hypothesis sets of ℱ_i are pairwise disjoint, and the hypothesis sets of ℱ_ are pairwise disjoint.

By a double-counting argument, the cost of the output tree is the weighted sum of the partial trees and greedy trees computed in the recursion.
Formally, if 𝒯_out is the output tree,

    C(𝒯_out,[n]) = ∑_i ∑_H ∈ℱ_i p(H) C_(H, b) + ∑_H ∈ℱ_ p(H) C_G(H).

Our proof bounds the depth of the recursion, as well as the summand components. 



Let {H_i} be a collection of disjoint subsets of [n]. Then ∑_i p(H_i) C_(H_i) ≤ C_


   Recall that 𝒯_𝒯_([n]) is the optimal tree of the (R) instance.
   By optimality of 𝒯_(H_i) for the instance instance induced by H_i, we have  C_(H_i) = C(𝒯_(H_i); H_i)≤ C(𝒯_; H_i).
   Hence,
   
    ∑_i=1^ℓ p(H_i) C_(H_i)
               ≤ ∑_i=1^ℓ p(H_i) C(𝒯_; H_i)
            =  ∑_i ∑_h ∈ H_i p_h · d_𝒯_(h) 
        ≤ ∑_h ∈ [n] p_h · d_𝒯_(h) 
            =  C_.






We have

    ∑_H ∈ℱ_ p(H) C_G(H) ≤(17/α+log R)· C_



  For all hypothesis sets H∈ℱ_1, Algorithm <ref> guarantees that C_G(H) ≥ (12 log n + log R) n^3α/4.
  By Theorem <ref>, the greedy algorithm gives a (12log n + log R) approximation on the (R) instance induced by H.
  Hence, C_(H)≥ n^3α/4 for all H∈ℱ1.
  By Theorem <ref> again, for all H∈ℱ1, we have
  
    C_G(H)
            ≤ (12log(|H|)/log C_(H) + c/α) C_(H)
         ≤ (16/α+log R) · C_(H).

  Hence,
  
    ∑_H ∈ℱ1 p(H) C_G(H) 
              ≤ (16/α+log R) ∑_H ∈ℱ1 p(H) C_(H)
           ≤ (16/α+log R) · C_
    ∑_H ∈ℱ2 p(H) C_G(H) 
              <  ∑_H ∈ℱ21/n^2· n  < 1 < 1/α· C_.

  The last inequality is by Lemma <ref> and the fact that the H∈ℱ_ are disjoint.
  Adding (<ref>) and (<ref>) gives the desired result




For all i=0,1,…, we have

    ∑_H ∈ℱ_i p(H) C_(H, b)≤ C_



  For any H ∈ℱ_i, we have C_(H, b) ≤ C_(H).
  Summing over all H ∈ℱ_i, we have
  
    ∑_H ∈ℱ_i p(H) C_(H, b)
             ≤∑_H ∈ℱ_i p(H) C_(H) 
          ≤ C_

  where the last inequality follows from Lemma <ref> and that H∈ℱ_i are disjoint.




The maximum recursion depth in Algorithm <ref> is at most 8/α


We show by induction that, for all i,

    ∑_H∈ℱ_i^ p(H)≤ n^-iα/4.

This suffices, as then, for i=⌊ 8/α⌋ +1, we have ∑_H ∈ℱ_i p(H) < 1/n^2.
By Algorithm <ref>, we have p(H)≥1/n^2 for all H∈ℱ_i (otherwise we take the greedy tree). 
Thus, the maximum depth of the recursion in Algorithm <ref> is less than ⌊ 8/α⌋.

Note that equality holds in (<ref>) for i=0, so the base case is true.
For the inductive step, fix i≥ 1, and let H∈ℱ_i.
Note that

    n^-α/4b
           ≥ C_G(H) ≥ C_(H) ≥ C_(H, b)

Consider a random variable X equal to the depth in tree 𝒯_(H, b) of a random hypothesis in H where h∈ H is chosen with probability proportional to p_h.
By above, [X]≤ n^-α/4b.
Hence, by Markov's inequality, [X≥ b] ≤[X]/b≤ n^-α/4.
Thus, the total weight of hypotheses in H that are in the next recursive call, i.e. in H' for some H'∈ℱ_i+1, is at most n^-α/4p(H).
This holds for any H, so we conclude

    ∑_H ∈ℱ_i p(H)    ≥ n^α/4∑_H' ∈ℱ_i+1 p(H').

This completes the induction, proving the lemma.



  
Let 𝒯_out be the tree returned by FullTree_α([n]).
Then C(𝒯_out, [n]) ≤ (25/α+log R) C_.


By (<ref>) and Lemmas <ref>, <ref>, and <ref>, we have

    C(𝒯_out,[n])    = ∑_i=1^⌊ 8/α⌋∑_H ∈ℱ_i p(H) C_(H, b) + ∑_H ∈ℱ_greedy p(H) C_G(H) 
       ≤(∑_i=1^⌊ 8/α⌋ C_) + (17/α + log R) C_≤(25/α +log R ) C_.





 §.§ Uniform Decision Tree

We now describe how to modify Algorithm <ref> to give a 9+ε/α approximation for Uniform Decision Tree in subexponential time.
By the remark at the end of Theorem <ref>, for all ε>0 there exists an n_0 = n_0(ε) such that for all n≥ n_0, the greedy algorithm gives a (4+2/3ε)log n/log C_ approximation on Uniform Decision Tree.
Hence, the following modified greedy algorithm runs in polynomial time and gives a (4+2/3ε)log n/log C_ approximation: for n≥ n_0, run the greedy algorithm, and for n < n_0, compute the optimal tree by brute force in constant time.
For Uniform Decision Tree, set b=(4+2/3ε)log(n)n^α, use the modified greedy algorithm instead of the greedy algorithm, and return the output of the modified greedy algorithm if C(𝒯_G(H); H)≥ n^-α/3b (rather than n^-α/4b) and keep the rest of Algorithm <ref> the same.
Lemma <ref> still holds.
For uniform weights, we have F_2=∅, so ℱ_1=ℱ_.
Similar to Lemma <ref>, we are guaranteed that C_(H)≥ n^2α/3 for all H∈ℱ_, and thus

    ∑_H∈ℱ_^ p(H)C_G(H) ≤∑_H∈ℱ_^(4+ε)log(|H|)/log(C_(H))· C_(H) ≤6+ε/α· C_.

Lemma <ref> still holds.
In Lemma <ref> the maximum depth of recursion is now 3/α as the weight of hypotheses at each recursive call shrinks by a factor of n^α/3 and the weight of hypotheses at each nonempty level is at most 1/n.
Hence, the cost of the output tree has a contribution of at most 6+ε/αC_ from the greedy trees and at most 3/αC_ from the outputs of the PartialTree, for a total cost of at most 9+ε/αC_.




§ RELATED WORK



There have been several other works analyzing Decision Tree and they analyze it in a variety of cases to achieve the gold standard O(log n). While we examined the case with K-ary tests and non-uniform weights, we assumed that the tests had equal costs. Other works <cit.> analyze the case where the test costs are non-uniform. <cit.> shows that the greedy algorithm yields O(log n) when either the costs are non-uniform or the weights are non-uniform (with the rounding trick) but not both. <cit.> introduces a new algorithm that achieves O(log n) with both non-uniform weights and costs.

In this work we studied the average depth of decision trees. We remark that, in the worst-case decision tree problem, where the cost of a tree is defined to be the maximum depth of a leaf in the tree, the approximability is known.
The greedy algorithm gives an O(log n) approximation <cit.>, and obtaining a o(log n) approximation is NP-hard <cit.>.

For the worst-case decision tree problem, there is a line of work that examines the absolute query rate rather than the query rate relative to the optimal. In this line of work, the chief goal is to identify conditions where the greedy algorithm achieves the information-theoretically optimal rate O(log n). 
One such condition that ensures the O(log n) rate is “sample-rich” <cit.>,
which states that every binary partition of the hypotheses has a test with matching pre-images.
<cit.> introduced the more lenient
k-neighborly condition, which requires that every two tests be connected by a sequence of tests
where neighboring tests disagree on at most k hypotheses. An even more general condition is the split-neighborly condition <cit.>, which is satisfied if every two tests are connected by a sequence of tests where neighboring tests must have every subset of the disagreeing hypotheses be evenly split by some other test.




§ CONCLUSION


There are several open questions left by our work.


  * Could one prove hardness of approximation results for Uniform Decision Tree for ratios larger than 4-ε? It would be interesting to prove either NP-hardness results for larger constant factor approximations, or fine-grained complexity results for larger approximation ratios such as in <cit.>. 

  * On the flip side, could one find faster, perhaps polynomial time algorithms for approximating Uniform Decision Tree for ratios where we now have subexponential time algorithms?

  * On can also consider a generalization of Decision Tree when the test costs are non-uniform. <cit.> Could one obtain similar results in this setting?




§ ACKNOWLEDGEMENTS

The authors thank Joshua Brakensiek for helpful discussions and feedback on an earlier draft of this paper.
The authors thank Mary Wootters for helpful feedback on an earlier draft of this paper.
The authors thank  anonymous reviews for helpful feedback on an earlier draft of this paper.

alpha






§ PROOF OF THEOREM <REF>



We now give a proof of Theorem <ref>, highlighting the differences with the proof of the special case in Section <ref>, and suppressing parts of the proof that are identical.



 §.§ Notation

We reuse all of the notation in Section <ref>.
The only difference is that, in this section, p(S)∑_h∈ S^ p_h is not necessarily equal to |S|/n.
Just as in Section <ref>, fix δ=1/C_.




 §.§ The basic argument

Lemma <ref> is still true, and we restate it for completeness.

  
  We have C_G =  ∑_v∈𝒯_G^o^ p(v). 


At a high level, our proof defines balanced and imbalanced vertices (next subsection) using the parameter δ and bound the weight of the balanced and imbalanced vertices separately.
We bound the weight of the balanced vertices by an entropy argument, and the weight of the imbalanced vertices by partitioning the imbalanced vertices into paths, called chains, and bounding the weights of each chain separately.
If a vertex v has a heavy hypothesis h (defined in Section <ref>), we set q(v)=p_h, and otherwise we set q(v)=0.
To bound the cost of imbalanced vertices, we also need to bound the costs of heavy hypotheses q(v).
Overall, we make get the following bounds.
  
    C_G
            =  ∑_v∈𝒯_G^o^ p(v) 
        =  ∑_v balanced^ p(v) + ∑_v imbalanced^ p(v) 
        ≤ log n/log 2C_· 2C_ + (4s_max(C_+1) + ∑_v∈𝒯_G^o^ q(v)) 
        ≤ log n/log 2C_· 2C_ + 4·log1/p_min/log1/δ· (C_+1) + ( 1 + lnp_max/p_min)· C_
        <  (12log1/p_min/log C_ + lnp_max/p_min)· C_.




 §.§ More notation: Majority and minority answers

Again, we define majority (minority) answers, edges, children, which are useful for defining balanced and imbalanced vertices.

For each vertex v in the greedy tree, let j_v denote the test used at v.
For each vertex v, label its children by v^+ and v^1,-, v^2,-,…, so that p(v^+)≥ p(v^ℓ,-) for all ℓ, with ties broken[any tiebreaking procedure suffices, as long as the tiebreaking is consistent with the k_j,S^+ and k_j,S^- notation in the next paragraph.] by labeling v^+ by the vertex corresponding to the largest answer.[it is possible to have a vertex that has one child, namely a test that doesn't distinguish any pairs of hypotheses at a vertex, but such a test is useless and never appears in either the greedy or optimal tree, so we assume it doesn't exist.]
Call the edge from v to v^+ a majority edge[Here, we may have p(v^+) < 1/2p(v), so the weight of hypotheses consistent with v^+ do not necessarily constitute a majority. However, this does difference does not affect the proof, and we keep the wording to stay consistent with Section <ref>.], and the edges from v to v^ℓ,- minority edges. 
Call v^+ the minority child of v and call v^1,-,v^2,-,…, the minority children of v.
Let L^-(v)∪_ℓL(v^ℓ,-) be the hypotheses consistent with the minority children of v, and let their weight be p^-(v) = p(L^-(v)).
Accordingly, we have p(v) = p(v^+) + p^-(v) for all v∈𝒯_G^o.
This is illustrated in Figure <ref>.



In order to reason about the greedy tree precisely, we use the following notation which is more technical.
For test j∈[m] and hypotheses S⊆[n], let k^+_j,S∈[K] be the answer to test τ_j that accounts for the maximum weight of hypotheses in S, with ties broken by choosing the largest indexed answer k^+_j,S.
We call k^+_j,S the majority answer of test j with respect to hypothesis set S.
Call the other answers the minority answers of test j with respect to hypothesis set S.
For all j∈[m] and S⊂ [n], let

    I_j,S^+   τ_j^-1(k^+_j,S),
          
      I_j,S^-   [n] ∖ I_j,S^+.

We think of I_j,S^+ (I_j,S^-) as the set of hypotheses that, under test j, output the majority (minority) answer to test j with respect to set S.
Note that, with the above notation, we have L(v^+) = I_j_v,L(v)^+∩ L(v) and L^-(v) = I_j_v,L(v)^-∩ L(v).
Under these more general definitions, a generalization of Lemma <ref> holds.
The proof is identical to that of Lemma <ref>, so we omit it.

  
  For any vertices u of v with u a descendant of v, we have p^-(v)≥ p^-(u).






 §.§ Defining balanced and imbalanced vertices

In the following definition, we identify balanced vertices and imbalanced vertices.
By Lemma <ref>, we can separately bound the weights of the balanced and imbalanced vertices.

  
  Let s be a positive integer.
  
  
  * We say a vertex v∈𝒯_G^o is level-s imbalanced if p^-(v) ≤δ^s and p(v) > 2δ^s.
  
  * We say a vertex v is imbalanced if it is level-s imbalanced for some s, and balanced otherwise.
  
  * We say a level-s imbalanced vertex v is minimal if no descendant of v is also level-s imbalanced vertex, and a level-s imbalanced vertex v is maximal if no ancestor of v is level-s imbalanced.
  

Let 

    s_maxlog1/p_min/log1/δ

and note that interior level-s imbalanced vertices exist only for s≤ s_max.
The following lemma proves a structural result about balanced vertices, with the punchline being item (iii), which permits Definition <ref>.
The proof of Lemma <ref> is nearly identical to that of Lemma <ref>.
We include a proof of item (i) because of a subtle difference to the proof of item (i) of Lemma <ref>.
However, the proofs of the other two parts are identical, so we omit them.

  
  Let s be a positive integer.
  
    
  (i) If v is a level-s imbalanced vertex, then, among the children of v, only v^+ can be a level-s imbalanced vertex.
    
  (ii) Additionally, if v and u are level-s imbalanced vertices and v is an ancestor of u, then every vertex on the path from v to u is a level-s imbalanced vertex.
    
  (iii) Finally, the set of level-s imbalanced vertices can be partitioned into vertex disjoint paths, each of which connects a maximal level-s imbalanced vertex to a minimal level-s imbalanced vertex and contains only majority edges.
  


  Note that if v is level-s imbalanced, then p^-(v)≤δ^s, which means every u different from v^+ satisfies p(u)≤ p^-(v)≤δ^s < 2δ^s, so such u cannot be level-s imbalanced.
  Hence, among the children of v, only v^+ can be level-s imbalanced.

Lemma <ref> motivates the following definition.

  
  Let s be a positive integer.
  A level-s chain, P=(P_1,…,P_|P|), is a sequence of level-s imbalanced vertices starting at a maximal level-s imbalanced vertex and ending at a minimal level-s imbalanced vertex.
  By Lemma <ref>, the level-s chains partition the level-s imbalanced vertices.
  We therefore let 𝒫_s denote the level-s chains.

In general, for s≠ s', a level-s chain might overlap with a level-s' chain.










 §.§ Bounding the weight of balanced vertices

Under these definitions, a generalization of Lemma <ref> is still true.
The proof is identical to that of Lemma <ref>, so we omit it.

  
  For every balanced vertex v, we have p^-(v)≥δ/2p(v).

We now bound the contribution of the balanced vertices to the weight using an entropy argument.
Now, in the general case, the entropy argument requires a little more care when bounding the entropy of a single K-ary test.


  We have
  
    ∑_v balanced^ p(v) ≤log n/log2/δ·2/δ.



  For a vertex v with a test of index j, let X_v denote the random variable supported on [K] that is equal to τ_j(h) for an hypothesis h chosen randomly from the elements of L(v), where the probability of choosing h is proportional to p_h.
  Let ℍ(·) denote the entropy of a random variable, and by abuse of notation, let ℍ(v)ℍ(X_v).
  By abuse of notation, for nonnegative α_1,…,α_K summing to 1, let ℍ(α_1,…,α_K) = ∑_i=1^K -α_ilogα_i where 0log 0 is taken to be 0.
  The entropy of a random element [n] chosen according to the prior distribution =(p_1,…,p_n) is at most log n.
  On the other hand, we can pick a random hypothesis in [n] according to the distribution  by setting v to the root of 𝒯_G, sampling an answer X_v∈[K] for the test at v, setting v to the child of v corresponding to the chosen answer X_v, and repeating, until we reach a leaf.
  In this process, at any vertex v, the probability of stepping to a child u is exactly p(u)/p(v).
  Hence, by a simple induction, the probability of reaching any vertex v in the tree during this process is exactly p(v). 
  The total entropy of this process is thus ∑_v∈𝒯_G^ p(v)·ℍ(v), as p(v) is the probability of reaching vertex v and ℍ(v) is the entropy of the random variable X_v chosen at vertex v.

  Fix a balanced vertex v.
  We claim that ℍ(v)≥δ/2log2/δ.
  Let ℛ⊂ℝ^K denote the region given by the constraints 0≤α_k≤α_1≤ 1 for all k=2,…,K, and α_1+⋯+α_K=1, and α_2+⋯+α_K≥δ/2. 
  We claim that the minimum of ℍ(α_1,…,α_K) for (α_1,…,α_K)∈ℛ is ℍ(1-δ/2,δ/2).
  To see this, note first that this region ℛ is closed and bounded, so the function ℍ(α_1,…,α_k) obtains a minimum.
  Furthermore, note that, for (α_1,…,α_K)∈ℛ, by concavity of -xlog x, for any k=2,…,K and any ε≤α_K, setting (α_1',…,α_K')=(α_1+ε,α_2,…,α_k-1,α_k-ε,α_k+1,…,α_K) gives ℍ(α_1,…,α_K) > ℍ(α_1',…,α_K'). 
  Similarly pushing α_k and α_k' apart by the same positive ε also decreases the value of H.
  Hence, the maximum cannot be obtained when two of α_2,…,α_K are positive, nor can it be obtained when α_2+⋯+α_K > δ/2.
  It follows that the only local minima in the region occur when some α_k is δ/2 and α_1=1-δ/2.

  For k=1,…,K, let α_k denote the probability that X_v=k. 
  By Lemma <ref>, when v is balanced, (α_1,…,α_K) must, up to a permutation in coordinates, be in region ℛ.
  Hence, by the above we have
  
    ℍ(v)
         =  ℍ(X_v) 
         =  ℍ(α_1,…,α_k)
         ≥ H( δ/2, 1-δ/2) > δ/2log2/δ.


  Putting the above two paragraphs together, we conclude
  
    log n
            ≥ ∑_v∈𝒯_G^ p(v)·ℍ(v) 
         ≥ ∑_v balanced^ p(v) ·ℍ(v)
         ≥ ∑_v balanced^ p(v)·δ/2log2/δ,

  and rearranging gives the desired result.









 §.§ Bounding the weight of imbalanced vertices


We now bound the weight of imbalanced vertices using a connection to Weighted Min Sum Set Cover.
For each hypothesis h, let u_h^ denote the leaf in the greedy tree 𝒯_G for which hypothesis h is consistent.
Since 𝒯_G is complete, this leaf exists and is unique.



  §.§.§ Technical definition: heavy vertices


We need the following technical definition to make the connection between the greedy decision tree and a greedy WMSSC solution.

  For a vertex v and an hypothesis h∈[n], we say v is h-heavy if h is consistent with v and p_h > p^-(v).



  Let h∈[n] be a hypothesis.
  
  
  (i) If v is h-heavy, then every vertex on the path from v to leaf u_h^ is h-heavy.
  
  (ii) Additionally, if v is h-heavy, then every edge on the path from v to leaf u_h^ is a majority edge.
  
  (iii) Lastly, for any vertex v, there exists at most one hypothesis h such that v is h-heavy.
  


  Item (i) is true by Lemma <ref>, which says that p^-(v) decreases as one descends the tree.

  For (ii), it suffices to prove, by the first part, that for every h-heavy vertex v, the first edge on the path from v to h is a majority edge.
  Suppose for contradiction that there exists h and an h-heavy vertex v with a minority child u such that h is a descendant of u.
  Then p^-(v) ≥ p(u) ≥ p_h, which contradicts the definition of v being h heavy.

  For (iii), suppose for contradiction there exists two hypotheses h and h' such that v is both h-heavy and h'-heavy.
  Since our Decision Tree instance is well defined, there exists some test j that distinguishes h and h', 
  i.e. τ_j(h)≠τ_j(h').
  As v is h-heavy, we have p_h > p^-(v). 
  Hence the answer for hypothesis h under test j is k^+_j,L(v), the answer to τ_j accounting for the maximum weight of hypotheses in L(v): if not choosing test j at vertex v would make the weight of hypotheses consistent with a minority child v to be ≥ p_h. 
  This is a contradiction as p_h>p^-(v) and the tree 𝒯_G is greedy.
  However, as v is also h'-heavy, we have, by the same reasoning, that τ_j(h')=k^+_j,L(v).
  This is a contradiction, as test j was chosen to distinguish h and h'.

We now define some notation for dealing with non-uniform weights p_h, which are well-defined by Lemma <ref>.

  For hypothesis h∈[n], let u_h^⊤ be the maximal ancestor of h that is h-heavy.
  For vertex v, if there exists an h such that v is h-heavy, let q(v)=p_h, and otherwise let q(v)=0.








  §.§.§ Defining Weighted Min Sum Set Cover

Recall I_j,S^+ = τ_j^-1(k_j,S^+) and I_j,S^- = [n] ∖ I_j,S^+.
 
Let P denote the instance of weighted min sum set cover that is induced by the chain P=(P_1,…,P_|P|). 
This instance is given by


  * universe S L(v_1) with weights (p_h)_h∈ S,

  * for j=1,…,m, sets A_j  I_j,S^-∩ S, and

  * for each h=1,…,n, a set A_m+h{h}∩ S consisting of one element.[Some of these sets are empty, but we include them for notational convenience.]

Note we have a total of m + n sets.
A solution to the  problem is a permutation σ:[m+n]→ [m+n] corresponding to an ordering of the sets, and the cost P(σ) of a solution is the weighted sum of the cover times of the elements in the universe S.
Formally,

    P(σ)
        ∑_h∈ S^ p_h·min{ℓ: h∈ A_σ(ℓ)} =  ∑_ℓ=1^m+n p( S ∖ (A_σ(1)∪⋯∪ A_σ(ℓ-1)) ).

Note that this instance is well defined, as each hypothesis h∈ L(v) is in some set A_j.
We sometimes refer to a solution σ by the sets A_σ(1),…,A_σ(m+n).


  
Since the initial Decision Tree instance is well defined, any two elements can be distinguished by one of the m tests.
Hence, there is at most one element h∈ L(v) such that, for all j=1,…,m, we have h∉ A_j. In other words, all but one of the sets A_m+h for h∈[n] are unnecessary.



We say a solution σ:[m+n]→[m+n] to P is greedy at index ℓ if the set A_σ(ℓ) covers the maximum number of elements not covered by sets A_σ(1),…, A_σ(ℓ-1).
We say a solution σ:[m+n]→[m+n] is greedy if it is greedy at index ℓ for all ℓ∈[m+n],

Note that, in the case of ties, there may be multiple greedy solutions to P. 
Note also that, for any partial assignment σ(1),…,σ(ℓ), one can always complete the solution greedily, so that σ:[m+n]→[m+n] is greedy at indices ℓ+1,ℓ+2,…,m+n.
Definition <ref> lets us leverage the following theorem, due to Golovin and Krause, which generalizes Theorem <ref>.[In fact, <cit.> considers an even more general problems called Adaptive Stochastic Min-Sum Cover.]

  
  The greedy algorithm gives a 4-approximation to the WMSSC problem.
  Formally, let σ be any greedy solution to P, and let σ_ denote an optimal solution.
  We have
  
    P(σ) ≤ 4·P(σ_).





  §.§.§ Bounding chain weight above by WMSSC cost



  Let s be a positive integer and let P=(P_1,…,P_|P|) be a level-s chain.
  Then there exists a greedy solution σ:[m+n]→[m+n] to P, such that
  
    P(σ) ≥∑_ℓ=1^|P|(p(P_ℓ) - q(P_ℓ)).



  Let S be the universe of the instance P, and let A_1,…, A_m+n be the sets.
  For ℓ=1,…,|P|, let j_ℓ be the test used at vertex P_ℓ.
  Let ℓ_0≤|P| be the largest index such that P_ℓ_0 is not h-heavy for any h, or 0 if no such index exists.
  If ℓ_0 < |P|, let h_0 be the hypothesis such that P_ℓ_0+1 is h_0-heavy.
  By Lemma <ref>, all the edges along the path P are majority edges.
  By Lemma <ref>, for all ℓ_0 < ℓ≤ |P|, vertex P_ℓ is h_0-heavy.
  Define a solution σ:[m+n]→[m+n] to P as follows.
  
  
  * If ℓ_0 = |P|, for ℓ=1,…,|P|, let σ(ℓ)=j_ℓ and complete the solution σ greedily.
  
  * Otherwise, for 1≤ℓ≤ℓ_0, let σ(ℓ)=j_ℓ, let σ(ℓ_0+1)=m+h_0, let σ(ℓ+1)=j_ℓ for ℓ_0 < ℓ≤ |P|, and complete the solution σ greedily.
  
  We claim σ is a greedy solution.
  To prove this, we show the following. 
  
  
  (i) For all j∈[m] and ℓ=1,…,|P|, the majority answer for test j with respect to vertex P_1 is the same as the majority answer for test j with respect to vertex P_ℓ.
  Equivalently, for all j∈[m] and ℓ=1,…,|P|, we have A_j=I_j,S^-∩ S = I_j,L(P_ℓ)^-∩ S.
  As an immediate consequence, we know A_j_ℓ contains all the hypotheses in L^-(P_ℓ) and none of the hypotheses in L(P_ℓ^+).
  
  (ii) The set of hypotheses of S not covered by A_j_1, …,A_j_ℓ-1 is exactly L(P_ℓ).
  
  (iii) For each 1≤ℓ≤ |P|, among sets A_1,…,A_m, set A_j_ℓ covers the maximum weight of hypotheses in L(P_ℓ), i.e. we have
  
    p(A_j_ℓ∩ L(P_ℓ))=max_j∈[m]p(A_j∩ L(P_ℓ)).

  
  (iv) For each 1≤ℓ≤ℓ_0, among sets A_1,…,A_m+n, set A_j_ℓ covers the maximum weight of hypotheses in L(P_ℓ).
  
  (v) If ℓ_0<|P|, then, among sets A_1,…,A_m+n, set A_m+h_0={h_0} covers the maximum weight of hypotheses in L(P_ℓ_0+1).
  
  (vi) If ℓ_0<|P|, then, for ℓ_0 < ℓ≤|P|, among sets A_1,…,A_m+n, set A_j_ℓ covers the maximum weight of hypotheses in L(P_ℓ)∖{h_0}.
  
  These points suffices for proving that σ is greedy.
  If ℓ_0=|P|, items (ii) and (iv) tell us that σ is greedy at indices 1,…,|P|, so by construction σ is greedy.
  If ℓ_0<|P|, then (iv), (v), and (vi) tell us that σ is greedy at indices 1,…,|P|+1, so σ is greedy.

  To show (i), fix j∈[m] and ℓ∈{1,…,|P|}.
  As P_ℓ is level-s imbalanced, we also have p(P_ℓ)>2δ^s and p^-(P_ℓ) ≤δ^s and p(P_ℓ^+) > δ^s, so k_j,L(P_ℓ)^+ is the unique answer in [K] accounting for more than half of the weight of hypotheses in L(P_ℓ).
  On the other hand, as vertex P_1 is level-s imbalanced, we have p(I_j,S^-∩ L(P_ℓ)) ≤ p(I_j,S^-∩ S) ≤ p^-(P_1) ≤δ^s, so the majority answer k_j,S^+ for test j with respect to hypothesis set S is exactly the answer described in the previous sentence. 
  Hence k_j,S^+ = k_j,L(P_ℓ)^+.

  Item (ii) follows because L(P_ℓ) is the set of hypotheses consistent with P_ℓ, which was obtained by following the majority edges from P_1.
  This means L(P_ℓ) contains all the hypotheses of S not a consistent with a minority child of one of P_1,…,P_ℓ-1.
  By the last paragraph, this is exactly S∖ (A_j_1∪⋯∪ A_j_ℓ-1).

  For (iii), at vertex P_ℓ in the greedy decision tree, the test index j=j_ℓ maximizes the weight p(I_j,L(P_ℓ)^-∩ L(P_ℓ)).
  By (i), this index j equivalently maximizes p(A_j∩ L(P_ℓ)), as desired.

  For (iv), at step ℓ for ℓ≤ℓ_0, by (i), the set A_j_ℓ covers a p^-(P_ℓ) weight of hypotheses in L(P_ℓ), which is more than p_h_0 by definition of ℓ_0. 
  By (iii), A_j_ℓ covers at least as much weight of hypotheses in L(P_ℓ) as any of A_1,…,A_m, and, by Remark <ref> and the previous sentence, at least as much as any of A_1,…,A_m+n.
  
  For (v), by maximality of ℓ_0, we have p_h_0 > p^-(P_ℓ_0+1).
  Hence, the singleton {h_0} covers more weight of hypotheses in L(P_ℓ_0+1) than any of A_1,…,A_m, and thus, by Remark <ref>, than any of A_1,…,A_m+n.
  
  For (vi), if there exists h_0 such that some P_ℓ is h_0-heavy, then, for any j=1,…,m, we have h_0∉ A_j and A_j∩ L(P_ℓ) = A_j∩ (L(P_ℓ)∖{h_0}).
  Hence the A_j among A_1,…,A_m that covers the most weight of L(P_ℓ)∖{h_0} is A_j_ℓ by (iv).
  By Remark <ref>, the only set among A_m+1,…,A_m+n that could cover a larger weight of L(P_ℓ)∖{h_0} is {h_0}, but it in fact covers 0 weight of L(P_ℓ)∖{h_0}, so among sets A_1,…,A_m+n, set A_j_ℓ covers the maximum weight of hypotheses in L(P_ℓ)∖{h_0}.
  This completes the proof that σ is greedy.

  We now return to the proof of Lemma <ref>.
  Take the greedy solution σ given above.
  If ℓ_0=|P|, then the set of vertices of S not covered by A_σ(1),…,A_σ(ℓ-1) is exactly L(P_ℓ), which has weight p(P_ℓ).
  Hence, by (<ref>),
  
    P(σ)
            ≥ ∑_ℓ=1^|P| p(P_ℓ)
         =  ∑_ℓ=1^|P| (p(P_ℓ) - q(v)).

  Now suppose ℓ_0<|P|.
  Recall that the definition of ℓ_0 implies P_ℓ_0+1,P_ℓ+2,…,P_|P| are all h_0-heavy.
  Hence, we have q(P_ℓ) = 0 for 1≤ℓ≤ℓ_0, and q(P_ℓ)=p_h_0 for ℓ_0 < ℓ≤ |P|.
  Thus,
  
    P(σ)
            ≥ ∑_ℓ=1^|P|+1  p( S∖(A_σ(1)∪⋯∪ A_σ(ℓ-1)) ) 
        =  ∑_ℓ=1^ℓ_0+1 p(P_ℓ) + ∑_ℓ=ℓ_0+1^|P| p(L(P_ℓ)∖{h_0}) 
        >  ∑_ℓ=1^ℓ_0 p(P_ℓ) + ∑_ℓ=ℓ_0+1^|P| p(L(P_ℓ)∖{h_0}) 
        =  ∑_ℓ=1^|P|(p(P_ℓ) - q(P_ℓ))

  as desired.
  In the last equality, we used that h_0∈ L(P_ℓ) for ℓ=1,…,|P|.

Let σ_GP:[m+n]→[m+n] be the greedy solution to P given by Lemma <ref>, and let σ_P be an optimal solution to P.





  §.§.§ Bounding WMSSC cost above by C_


  
  Let s be a positive integer.
  We have
  
    C_≥ -1 + ∑_P∈𝒫_s^P(σ_P).



  Let SP be the universe of the instance P, and let A_1,…, A_m+n be the sets.
  Construct a path w_1,…,w_ℓ in 𝒯_ such that w_1 is the root, w_ℓ is a leaf for hypothesis h, and, for ℓ=1,…,ℓ-1, if the test at vertex w_ℓ has index j_ℓ, the edge to its child w_ℓ+1 corresponds to the answer k_j_ℓ,SP^+, the majority answer of test j_ℓ with respect to set SP.
  Suppose the test at vertex w_ℓ in the optimal tree has index j_ℓ.
  Since we follow the edges with label k^+_j,SP, this corresponds to following the path for an hypothesis contained in I_j_ℓ,SP^+. 
  In other words, we have, for ℓ=1,…,ℓ-1,
  
    L(w_ℓ+1) 
         =  L(w_ℓ)∖ I_j_ℓ,SP^-
         =  L(w_ℓ)∖ A_j_ℓ.

  Thus the sequence A_j_1,…,A_j_ℓ, {h} covers [n], and hence SP, and thus gives a valid solution σ_TREE to the instance P, where σ_TREE(1) = j_1, σ_TREE(2)=j_2,…,σ_TREE(ℓ)=j_ℓ, σ_TREE(ℓ+1)=m+h, and σ_TREE on larger indices is arbitrarily chosen.
  Note that the depth of a hypothesis h in the tree is at least the number of vertices of w_1,…,w_ℓ that are on the root-to-leaf path of h, and this number is min{ℓ:h∈ A_j_ℓ}, except for h^*, in which case it is 1 smaller.
  Then we have
  
    ∑_h∈ SP^ p_h· d_(h) 
         ≥ -p_h +∑_h∈ SP^ p_h·min{ℓ:h∈ A_j_ℓ}    ≥ P(σ_TREE) - p_h
        ≥ P(σP_) - max_h∈ SPp_h.

  Summing over P∈𝒫_s gives
  
    C_ ≥ ∑_P∈𝒫_s^( P(σP_) - max_h∈ SPp_h ) ≥ -1 + ∑_P∈𝒫_s^( P(σP_) ).





  We have 
  
    ∑_v imbalanced^ p(v)
         ≤ 4s_max(C_+1) + ∑_v∈𝒯_G^o^ q(v).



  Each imbalanced vertex v is level-s imbalanced for some positive integer s, so it is part of some level-s chain, P.
  Note that p(v) - q(v) ≥ 0 for all vertices v.
  Hence,
  
    ∑_v imbalanced^ p(v) - ∑_v∈𝒯_G^o^ q(v)
            ≤ ∑_v imbalanced^ (p(v) - q(v)) 
        ≤ ∑_s=1^s_max∑_P∈𝒫_s 
     P=(P_1,…,P_|P|)^∑_ℓ=1^|P|(p(P_ℓ) - q(P_ℓ)) 
        ≤ ∑_s=1^s_max∑_P∈𝒫_s 
     P=(P_1,…,P_|P|)^P( σ_GP ) 
        ≤ ∑_s=1^s_max∑_P∈𝒫_s^ 4P(σP_) 
        ≤  4s_max(C_+1)

  The first inequality is because q(v)≥ 0 for all v.
  The second inequality is because p(v)-q(v) ≥ 0 for all v, and that every imbalanced v is in some chain.
  The third inequality is by Lemma <ref>.
  The fourth inequality is by Theorem <ref>.
  The fifth inequality is by Lemma <ref>.
  Rearranging gives the desired result.





 §.§ Bounding the cost contribution of heavy vertices


We bound the cost contribution of the heavy vertices via a connection to SET-COVER.
A theorem due to Lovasz <cit.>, Johnson <cit.>, Chvatal <cit.>, and Stein <cit.> states that, in any instance of SET-COVER where no set covers more than h elements, the greedy algorithm gives a 1+ln h approximation.
We show a generalization of this result, based on the following the definition.

  Let Φ be an instance of SET-COVER with a universe S and sets A_1,…,A_m.
  Let =(p_h)_h∈ S be a sequence of weights assigned to the elements of S.
  A -weighted greedy algorithm for SET-COVER is repeatedly chooses the set A_j that minimizes ∑_h∈ A_j∩ S'^ p_h, where S' is the set of uncovered elements.


  Let Φ be an instance of SET-COVER with a universe S and sets A_1,…,A_m.
  Let =(p_h)_h∈ S be a sequence of weights assigned to the elements of S.
  Then, if the optimal solution to Φ has uses at most ℓ_ sets, then the -weighted greedy algorithm uses at most (1 + lnp^*/min_h p_h)ℓ_ sets, where p^*max_j∈[m]∑_h∈ A_j^ p_h.
  

While this argument may be known, we are not aware of a known reference, so we provide a proof for completeness in Appendix <ref>.


We now bound ∑_v∈𝒯_G^o^ q(v).

  
  For all h ∈[n], we have
  
    d_𝒯_G(u_h^) - d_𝒯_G(u_h^⊤) ≤(1 + ln( p_max/p_min))· d_(h).



  Fix h.
  Let v_1=u_h^⊤,…,v_ℓ_G=u_h^ denote the path from vertex u_h^⊤ to leaf u_h^ in the greedy tree. 
  Let h denote the SET-COVER instance with the following parameters:
  
  
  * Universe S=L(u_h^⊤)∖{h}
  
  * For j=1,…,m, sets A_j=I_j,S^-∩ S.
  
  Let ℓ_ denote the cost of the optimal solution to h, and for ℓ=1,…,ℓ_G, let j_ℓ denote the test at vertex v_ℓ.

  We make the following observations.
  First, by definition of u_h^⊤, for all j∈[m], the set I_j,S^- does not contain hypothesis h: vertex u_h^⊤ satisfies p^-(u_h^⊤) < p_h so the answer k^+_j,S of a test j that accounts for the largest weight of hypotheses in S always contains the hypothesis h, as any other answer, by the definition of the greedy algorithm, has weight at most p^-(u_h^⊤).
  
  Second, the sets A_j_1, A_j_2,…, A_j_ℓ_G form a -weighted greedy solution for this SET-COVER instance h, where =(p_h)_h∈ S.
  For ℓ≤ℓ_G, the first ℓ-1 sets in the above sequence cover all of S except the elements of L(v_ℓ).
  In the greedy decision tree, the index j=j_ℓ that maximizes p(I_j,L(v_ℓ)^-∩ L(v_ℓ)).
  Note that, for any j, the set I_j,L(v_ℓ)^- are the hypotheses for the K-1 answers of τ_j that exclude hypothesis h.
  However, the set I_j,S^- also contains exactly the hypotheses for the K-1 answers of τ_j that exclude hypothesis h.
  Hence I_j,L(v_ℓ)^-∩ S = I_j,S^-∩ S = A_j, so j=j_ℓ maximizes p(A_j∩ L(v_ℓ)).
  Thus, sets A_j_1, A_j_2,…, A_j_ℓ_G form a -weighted greedy solution for this SET-COVER instance h.
  Hence, we may apply Theorem <ref>.
  Since max_j∈[m]p(A_j)=p^-(u_h^⊤) < p_h≤ p_max and min_h∈ Sp_h ≥ p_min, we have, by Theorem <ref>,
  
    d_𝒯_G(u_h^) - d_𝒯_G(u_h^⊤)
         =  ℓ_G-1
         ≤ (1+lnp_max/p_min)ℓ_.

  
  It remains to prove ℓ_≤ d_(h).
  Let w_1,…,w_ℓ_T=h be the root-to-leaf path for hypothesis h in the optimal tree 𝒯_.
  For ℓ=1,…,ℓ_T-1, set j_ℓ' to be the test chosen at vertex w_ℓ in the optimal tree.
  By the first point, the set I_j,S^- contains the hypotheses for the K-1 answers of test τ_j that exclude hypothesis h.
  As the optimal tree is a decision tree, any test is distinguished from h by one of tests j_1,…,j_ℓ_T-1, so A_j_1', A_j_2',…,A_j_ℓ_T-1' cover all of [n]∖{h}, and thus covers S. 
  Furthermore, ℓ_T-1=d_(h), so there is a solution to h of size d_(h).
  Hence, d_(h)≥ℓ_, as desired.

As a corollary, we have


  
    ∑_v∈𝒯_G^o^ q(v) 
            ≤ ( 1 + lnp_max/p_min)C_.



  We have
  
    ∑_v∈𝒯_G^o^ q(v)
            =  ∑_h∈[n]^ p_h· (d_𝒯_G(u_h^) - d_𝒯_G(u_h^⊤)) 
        ≤ ∑_h∈[n]^( 1 + lnp_max/p_min)· d_(h) 
        =  ( 1 + lnp_max/p_min)· C_.

  The first equality uses Lemma <ref>, which tells us that every vertex between u_h^⊤ and h is h-heavy, and no such vertex is h'-heavy for h'≠ h.
  Furthermore, these are the only h-heavy vertices as u_h^⊤ is the maximal h-heavy vertex.
  The inequality is by Lemma <ref>.








 §.§ Finishing the proof


  We have
  
    C_G
            =  ∑_v∈𝒯_G^o^ p(v) 
        =  ∑_v balanced^ p(v) + ∑_v imbalanced^ p(v) 
        ≤ log n/log2/δ·2/δ + ∑_v imbalanced^ p(v)  
                (Lemma <ref>)
        ≤ log n/log 2C_· 2C_ + 4s_max(C_+1) + ∑_v∈𝒯_G^o^ q(v)
                (Lemma <ref>)
        ≤ log n/log 2C_· 2C_ + 4·log1/p_min/log1/δ· (C_+1) + ( 1 + lnp_max/p_min)· C_    (Lemma <ref>)
        <  (12log1/p_min/log C_ + lnp_max/p_min)· C_,

  as desired.
  In the last inequality, we used that (i) log 2C_ > log C_, (ii) log n ≤log1/p_min, (iii) 1+C_ < 2C_, and 1 ≤log1/p_min/log C_.










§ PROOF OF THEOREM <REF>


We closely follow the argument of Chvatal <cit.>.
Suppose the p⃗-weighted greedy algorithm uses ℓ_G sets.
By re-indexing the sets, we may assume without loss of generality that the -weighted greedy algorithm chooses sets A_1,…,A_ℓ_G in that order.
For r=1,…,ℓ_G and j=1,…,m, let A_jr denote the elements of set A_j not covered by the first r-1 chosen sets.
For r=1,…,ℓ_G and j=1,…,m, let ρ_jr = ∑_h∈ A_jr^ p_h denote the sum of the weights of the elements of A_jr.
For h=1,…,n, let y_h=1/ρ_rr, where r is the index at which element h is first covered.
Equivalently, r is the unique index such that h∈ A_rr.
In this way, we have

    ∑_h∈ [n]^ p_h y_h = ∑_r=1^ℓ_Gρ_rr·1/ρ_rr = ℓ_G,

and, for all j=1,…,m,

    ∑_h∈ A_j^ p_hy_h 
          =  ∑_r=1^ℓ_jρ_jr-ρ_jr+1/ρ_rr,

where ℓ_j is the largest index such that ρ_jℓ_j > 0.
Hence using that ρ_j1,ρ_j2,…,ρ_jℓ_j is a non-increasing sequence, we have

    ∑_h∈ A_j^ p_hy_h 
          =  ∑_r=1^ℓ_jρ_jr-ρ_jr+1/ρ_jr =  1 + ∑_r=1^ℓ_j-1ρ_jr-ρ_jr+1/ρ_jr
        ≤ 1 + ∑_r=1^ℓ_j-1∫_ρ_jr+1^ρ_jrdx/x =  1+∫_ρ_jℓ_j^ρ_j1dx/x =  1+lnρ_j1/ρ_jℓ_j ≤ 1+lnp_max/p_min.

Let J⊂ [m] denote the indices of the optimal cover for Φ.
Applying (<ref>) and summing (<ref>) for j∈ J, we have

    ℓ_G 
          =  ∑_h∈ [n]^ p_hy_h
       ≤ ∑_j∈ J^∑_h∈ A_j^ p_hy_h
       ≤ |J|·( 1+lnp_max/p_min)
       =  ℓ_·( 1+lnp_max/p_min)

as desired.








§ TIGHTNESS OF THEOREM <REF>


In this section, we prove Propositions <ref> and <ref>, which show two ways that Theorem <ref> is tight.


 §.§ Proof of Proposition <ref>



We prove Proposition <ref> with the stronger guarantee that C_≤ 4C^* when C^* is an integer.
Then, taking (C^*)' = C^*≤ 2C^* gives the desired result.

When n is sufficiently large, for C^*≥ n^1/4, the statement is trivial, as any instance for which C_OPT∈[1/4 C^*,4C^*], satisfies the requirements.
Number the hypotheses 1,…,n^*.
Let n^*∈(n-C^*,n] be such that C^*|n^*. 
Place the hypotheses 1,…,n^* in a grid with C^* columns and rn^*/C^* rows, numbered 1,…,r, so that each grid square contains at most 1 hypothesis.
Recursively identify a family of good sets of rows as follows: [r] is good, and for every good set A' containing r'>1 rows, create a partition A'=A'_1∪ A'_2 such that |A'_1| = 1+r'/C^* and |A'_2| = r' - |A_1'|, and identify A'_1 and A'_2 as good.
Define three types of tests: 


  * For each of h=n^*+1,…,n, a test that outputs 1 if the hypothesis is h and 2 otherwise.

  * For each column c, a tests that outputs 1 if the hypothesis is in column c and 2 otherwise.

  * For each column c and t∈[0,log r], a test that outputs 1 if the hypothesis is in column c and the tth digit of the row number's binary expansion is a one, and 2 otherwise.

  * for each good set A', a test that outputs 1 if the row of h is in A' and 2 otherwise.


Let h be the unknown hypothesis.
There is a strategy that first checks whether h is one of n^*+1,…,n, for a total of at most n-n^* < C^* queries.
If not, the strategy identifies the column containing h in at most C^* queries using tests of type 2 and then identifies the corresponding row using tests of type 3, which takes log r < log n≤ 2C^* queries. 
We thus need at most 4C^* queries for each hypothesis, so here

    C_OPT≤ 4C^*.


The greedy strategy uses tests of type 4, trying to first find the row containing h.
This is because, for tests 1, 2, and 3, one answer accounts for at least 1-1/C^* fraction of the remaining hypotheses (it accounts at least 1-1/C^* fraction of the columns in the grid), and if the candidate set of rows containing h is a good set A', under the membership test for the good set A_1', all answers account for less than 1-1/C^* fraction of the remaining hypotheses.

When h is chosen uniformly at random from 1,…,n^*, the row containing h is a uniformly random row.
While there are at least C^* candidate rows containing h, each test gives at most ℍ(2/C^*) bits of information about the row containing h in expectation (over the randomness of h).
Since the row containing h has at least log r  = log (n^*/C^*) > 1/2log n bits of information, and the row has at most log C^* bits of information when there are at most C^* candidate rows remaining, we have, by an analysis similar to Lemma <ref>, the greedy algorithm takes at least 1/2log n - log C^*/ℍ(2/C^*) queries to identify the row containing h on average.
Hence,

    C_G 
      ≥n^*/n·1/2log n - log C^*/ℍ(2/C^*)≥1/2·1/4log n/ℍ(2/C^*)≥C^*log n/16log C^*

as desired.
In the last inequality, we used that ℍ(2x) ≤ -4xlog(x) for x∈[0,1].




 §.§ Proof of Proposition <ref>



In this appendix, we use that it is NP-hard to approximate Set Cover to within a factor of 1/2log n_0 <cit.>.

Let r∈(0,1). 
Then, for n sufficiently large, approximating (2 n^r log n) to a factor of 1/12log(n^r) is NP-hard.


We design a reduction from Set Cover to (2n^r log n).
Suppose we are given a Set Cover instance with n_0 elements, M sets {S_i} where S_i ⊆ [n_0], and an optimal cover of size B_OPT.
In polynomial time, we construct a (2n^rlog n) instance on n≤ n_0^1/r hypotheses such that, if C_OPT is the optimal decision tree cost, then, for some q,

    1/2 qB_OPT< C_OPT< 3q B_OPT.

The theorem follows as a 1/2log n_0 approximation to Set Cover is NP-hard, and here n^r≤ n_0.

Let q = 1/rlog n_0. 
Let ℓ = n_0^1/r / (n_0 q + 1).
Identify the hypotheses by elements of [ℓ] × ([q] × [n_0] ∪{⊥}).
In this way, there are n ∼ n_0^1/r hypotheses.
Let the elements of [ℓ]×{⊥} have weight 1/2n + 1/2ℓ, and let p_h=1/2n for all other hypotheses h∈[ℓ]× [q]× [n_0].
In this way, for n sufficiently large, we have p_max/p_min = 1 + n/ℓ≤ 2n^r log n.
Create tests of the following forms:

    
  * For each i_1 ∈[ℓ], i_2 ∈ [q], j ∈ [M], define a test that outputs 1 on hypotheses (h_1,h_2,h_3) if and only if i_1=h_1,i_2=h_2,h_3 ∈ S_j.
    
  * For each i_1 ∈[ℓ], i_2 ∈ [q], j ∈ [M], and t∈[0,log n_0], define a binary test that outputs 1 if and only if i_1=h_1,i_2=h_2,h_3∈ S_j, and the tth bit of h_3's binary representation is 1.
    
  * For each t∈[0, logℓ], define a binary test on (h_1,*) that outputs 1 if and only if the tth bit of h_1's binary representation is 1.


Consider a cover of [n_0] using B_OPT of the M sets.
We can define a tree that, given a hypothesis h=(h_1,*), first determines h_1 using tests of type 3.
Then, in each subtree, the set of consistent hypotheses is exactly {h_3}× ([q]× [n_0]∪{⊥}).
In each subtree, one can isolate the ⊥ hypothesis in qB_OPT queries, using tests of type 1, and use tests of type 2 to identify the remaining hypotheses in 1+log n_0 tests each.
In each subtree, all of the hypotheses of the form (h_1,⊥) have weight at most 1/ℓ and depth at most qB_OPT, and all other hypotheses have weight 1/2n and depth at most qB_OPT + 1+log n_0, so their total contribution to the cost of the tree is at most qB_OPT + 1 + log n_0.
Assuming n_0 is sufficiently large,

    C_OPT ≤ 1+logℓ + 2q B_OPT + log n_0
     <  3q B_OPT.


Now suppose we are given a solution to the (2n^rlog n) with cost C_OPT.
In the optimal tree, for all hypotheses (h_1,⊥), at least qB_OPT tests of type-1 or type-2 must appear on the root-to-leaf path of (h_1,⊥): if not, there exists h_2∈[q], such that at most B_OPT-1 tests of type-1 with parameters (h_1,h_2,j) or type-2 with parameters (h_1,h_2,j,t) were used. By taking the indices j used in these tests, there are at most B_OPT-1 sets covering [n_0], which is a contradiction.
Thus, each hypothesis (h_1,⊥) has depth at least qB_OPT.
Since the hypotheses (h_1,⊥) account for at least half of the weight of the hypotheses, we have

    C_OPT≥1/2qB_OPT.

This completes the proof.







§ ROUNDING WEIGHTS




Suppose a Decision Tree instance has weights p_1,…,p_n and a cost function C(·). Then, there exist weights p_1',…,p_n' such that min_i p_i' ≥1/n(n-1) and the cost function C'(·) of the associated instance satisfies |C'(𝒯) - C(𝒯)| ≤ 1 for all decision trees 𝒯.


Let w_i'=max(p_i, 1/(n-1)^2) and define W' = ∑_i w_i'. 
We have W' ≥ 1 and W' ≤ 1 + n-1/(n-1)^2 = n/n-1.
Let p_i' = w_i'/W', so that p_i' ≥1/n(n-1) for all i.
Hence, for all decision trees 𝒯,

    C'(𝒯)     =  1/W'∑_i w_i' d_𝒯(i) ≥1/W'∑_i p_i d_𝒯(i)  ≥n-1/n C(𝒯) ≥ C(𝒯)-1 
    
    C'(𝒯)     =  1/W'∑_i w_i' d_𝒯(i) ≤∑_i (p_i + 1/n^2) d_𝒯(i)  ≤ C(𝒯) + ∑_i 1/n^2 n ≤ C(𝒯) + 1.









