Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems

We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (k-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O$ ( $n$ /log n ) (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that any improvement of Ehrenfeucht and Haussler's algorithm will yield $O$ (logn)-approximation algorithms for k-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for k-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for k - NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of weak learning whereas prior ones were limited to the setting of strong learning.

Authors

• Caleb Koch 0001
• Carmen Strassle
• Li-Yang Tan

Keywords

• Computer science
• Approximation algorithms
• Picture archiving and communication systems
• Decision trees
• Decision Tree
• Regression Tree
• Learning Settings
• Codeword
• Polynomial-time Algorithm
• High Probability
• Lower Bound
• Uniform Distribution
• Proof Of Theorem
• Fundamental Problem
• Set Of Covariates
• Polynomial Of Degree
• Algorithm For Problem
• Target Size
• Generator Matrix
• Sparse Vector
• Time Probability
• Coding Theory
• Linear Code
• Parity-check
• Parity-check Matrix
• Vertex Cover
• Boolean Function
• Linear Extension
• Dual Form
• Finite Field
• Line Of Work
• Constant Approximation
• learning theory
• complexity theory