Reproduce “Properly Learning Decision Trees with Queries Is NP-Hard” on OpenResearch

About this paper

Caleb Koch, Carmen Strassle, Li-Yang Tan

The paper demonstrates that properly PAC learning decision trees with queries is NP-hard, even for small constant error, resolving a long-standing open problem in computational learning theory. This result challenges the intuition that query access might render the problem tractable and contrasts with efficient learning under uniform distributions, highlighting the critical role of distributional assumptions.

Key insights

• Properly learning decision trees remains NP-hard even with powerful query access, fundamentally limiting the efficiency of finding optimal decision tree hypotheses in the worst-case.
• The choice of distribution (or lack thereof, in the distribution-free setting) dramatically impacts the tractability of decision tree learning, as highlighted by the contrast with efficient learning under uniform distributions.
• Novel techniques like "hardness distillation" offer a general framework for connecting optimization problems to learning hardness and analyzing decision tree complexity on specific input subsets.

Summary by alphaXiv.