A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree

Ray Li, Percy Liang, Stephen Mussmann

TL;DR

This paper provides a breakthrough analysis of the classic greedy algorithm for the Uniform Decision Tree (UDT) problem, proving it achieves a tighter approximation ratio of $O(\frac{\log n}{\log C_{OPT}})$. Leveraging this, the authors introduce the first subexponential-time algorithm that achieves a constant-factor approximation for UDT, suggesting the problem is likely not NP-hard to approximate within super-constant factors.

What Problem Does This Paper Address?

The Decision Tree problem is a fundamental task in active learning and hypothesis testing. Given $n$ hypotheses and a set of tests, the goal is to build a decision tree that uniquely identifies each hypothesis while minimizing the average number of tests required (the average depth).

For the general version with non-uniform weights, the complexity is well-understood: the greedy algorithm gives an $O(\log n)$ approximation, and beating this is NP-hard. However, for the Uniform Decision Tree (UDT)—where every hypothesis is equally likely—a significant gap remained. While the best known polynomial-time algorithm (greedy) achieved $O(\log n)$, the best known hardness result was only $4 - \epsilon$.

This paper bridges that gap by asking: Can we do better than $O(\log n)$ for UDT, and just how hard is this problem really?

Methods

The authors employ two primary strategies: a novel analysis of the greedy algorithm and a hybrid subexponential-time algorithm.

  1. Tighter Greedy Analysis: The authors decompose the cost of the greedy tree by looking at its interior vertices. They categorize these vertices as either "balanced" (where the test splits the hypotheses relatively evenly) or "imbalanced."
    • Balanced Vertices: Handled using an entropy argument, showing that these nodes efficiently reduce uncertainty.
  2. Imbalanced Vertices: The key innovation here is establishing a formal connection to the Min Sum Set Cover (MSSC) problem. By showing that chains of imbalanced vertices in a greedy decision tree correspond to greedy solutions for MSSC, they apply known constant-factor approximation bounds from the MSSC literature to the UDT setting.
  3. Subexponential Algorithm: The authors design an algorithm that switches strategies based on the performance of the greedy approach.
  4. If the greedy algorithm returns a "deep" tree, the new analysis proves it is already a good approximation.
  5. If the greedy tree is "shallow," the algorithm uses brute-force search to find the optimal tree up to a certain depth and then recurses. Because the depth is limited, this search runs in subexponential time $2^{\tilde{O}(n^\alpha)}$.

Datasets

Not discussed in the paper. This is a theoretical work focused on computational complexity and algorithm design; no empirical evaluation on specific datasets was performed.

Key Insights and Ideas

  • The MSSC Connection: The most significant technical contribution is the "upper bound" connection between UDT and Min Sum Set Cover. Previously, only "lower bound" reductions (showing UDT is at least as hard as MSSC) were known.
  • Resolving a Conjecture: The new analysis proves a 20-year-old conjecture by Kosaraju et al., confirming that the greedy algorithm's performance is indeed $O(\frac{\log n}{\log \log n})$ when the optimal cost is $O(\log n)$.
  • Complexity Class Shift: By providing a subexponential algorithm for constant-factor approximations, the authors show that UDT belongs to a rare class of "intermediate" problems. Like Graph Isomorphism or Unique Games, it sits in a grey area: harder than typical polynomial-time problems, but likely not NP-hard in certain approximation regimes.

Key Results

The paper's findings are summarized in the complexity landscape shown in Figure 1:

Figure 1: Approximation ratio differences between Decision Tree (DT) and Uniform Deci- sion Tree (UDT). The thicker lines represent the contributions of this work. The yellow approx- imation region is not NP-hard assuming the Exponential Time Hypothesis (ETH).
  • Greedy Performance: The greedy algorithm achieves an approximation ratio of $O(\frac{\log n}{\log C_{OPT}})$. The authors also prove this bound is tight—meaning you can't prove a better ratio for the greedy algorithm itself.
  • Constant Approximation: For any $\alpha \in (0, 1)$, there exists a $\frac{9.01}{\alpha}$ approximation algorithm for UDT that runs in $2^{\tilde{O}(n^\alpha)}$ time.
  • ETH Implications: Assuming the Exponential Time Hypothesis (which posits that 3-SAT cannot be solved in subexponential time), the existence of this algorithm implies that achieving any super-constant approximation ratio for UDT is not NP-hard.

Limitations and Future Work

  • Hardness Gap: While the paper shows super-constant approximation isn't NP-hard, it doesn't settle whether a constant approximation (like a factor of 5 or 10) can be achieved in polynomial time. The gap between the $4-\epsilon$ hardness and the $O(\frac{\log n}{\log \log n})$ polynomial-time greedy bound remains.
  • Non-Uniform Test Costs: The current work assumes all tests have equal cost. Extending these subexponential results to scenarios where tests have different costs is an open challenge.
  • Fine-Grained Complexity: The authors suggest that future work could explore even tighter hardness results or faster algorithms for specific approximation ratios using fine-grained complexity analysis.

Summary updated

Abstract

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-\varepsilon$. We prove that the greedy algorithm gives a $O(\frac{\log n}{\log C_{OPT}})$ approximation for Uniform Decision Tree, where $C_{OPT}$ 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. Leveraging this result, for all $α\in(0,1)$, we exhibit a $\frac{9.01}α$ approximation algorithm to Uniform Decision Tree running in subexponential time $2^{\tilde O(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. All our results hold for Decision Tree with weights not too far from uniform. A key technical contribution of our work is showing a connection between greedy algorithms for Uniform Decision Tree and for Min Sum Set Cover.
BibTeX
@inproceedings{li2020tight,
  author = {Ray Li and Percy Liang and Stephen Mussmann},
  title = {{A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree}},
  booktitle = {SODA},
  year = {2020},
  doi = {10.1137/1.9781611975994.7},
}
Figure