Superconstant Inapproximability of Decision Tree Learning

• URL: http://arxiv.org/abs/2407.01402v1
• Date: Mon, 1 Jul 2024 15:53:03 GMT
• Title: Superconstant Inapproximability of Decision Tree Learning
• Authors: Caleb Koch, Carmen Strassle, Li-Yang Tan,
• Abstract summary: We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree $T$ is required to be optimally small, is NP-hard. We show that the task indeed remains NP-hard even if $T$ is allowed to be within any constant factor of optimal.
• Score: 7.420043502440765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothesis tree $T$ is required to be optimally small, is NP-hard. Their work leaves open the question of whether the task remains intractable if $T$ is only required to be close to optimal, say within a factor of 2, rather than exactly optimal. We answer this affirmatively and show that the task indeed remains NP-hard even if $T$ is allowed to be within any constant factor of optimal. More generally, our result allows for a smooth tradeoff between the hardness assumption and the inapproximability factor. As Koch et al.'s techniques do not appear to be amenable to such a strengthening, we first recover their result with a new and simpler proof, which we couple with a new XOR lemma for decision trees. While there is a large body of work on XOR lemmas for decision trees, our setting necessitates parameters that are extremely sharp, and are not known to be attainable by existing XOR lemmas. Our work also carries new implications for the related problem of Decision Tree Minimization.

Related papers

• Properly Learning Decision Trees with Queries Is NP-Hard [5.117810469621253]
  We prove that it is NP-hard to properly PAC learn decision trees with queries. We simplify and strengthen the best known lower bounds for a different problem of Decision Tree Minimization.
  arXiv  Detail & Related papers  (2023-07-09T04:29:43Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  We prove, under randomized ETH, superpolynomial lower bounds for two basic problems. Our results imply new lower bounds for distribution-free PAC learning and testing of decision trees. We show our lower bound for learning decision trees can be improved to $nOmega(log s)$.
  arXiv  Detail & Related papers  (2022-10-12T16:25:48Z)
• On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
  "sufficient reasons" are a kind of explanation in which given a decision tree $T$ and an instance $x$, one explains the decision $T(x)$. Our paper settles the computational complexity of $delta$-sufficient-reasons over decision trees. We identify structural restrictions of decision trees that make the problem tractable, and show how SAT solvers might be able to tackle these problems in practical settings.
  arXiv  Detail & Related papers  (2022-06-30T21:58:31Z)
• There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazes [64.05903267230467]
  Interpretability is an essential building block for trustworthiness in reinforcement learning systems. We show that in certain cases, one can achieve policy interpretability while maintaining its optimality.
  arXiv  Detail & Related papers  (2022-06-09T04:23:26Z)
• Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
  We propose an efficient algorithm that takes into account metrics related to the depths of the leaves in a decision tree. In experiments on 16 datasets, our algorithm yields better results than decision-tree clustering algorithms.
  arXiv  Detail & Related papers  (2021-12-29T18:22:28Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  We give an $nO(loglog n)$-time membership query algorithm for properly and agnostically learning decision trees. Our algorithm shares similarities with practicals for learning decision trees. We show how every decision tree can be "pruned" so that every variable in the resulting tree is influential.
  arXiv  Detail & Related papers  (2021-09-01T22:12:47Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank. The worst constraint-violation rate we observe is 24%.
  arXiv  Detail & Related papers  (2020-10-06T08:31:14Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  We develop an efficient programming based algorithm for sound verification of ensemble stumps. We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
  arXiv  Detail & Related papers  (2020-08-20T03:42:40Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  We present techniques that produce optimal decision trees over a variety of objectives. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
  arXiv  Detail & Related papers  (2020-06-15T19:00:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.