2026-07-21T12:31:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14738 2024-03-06T10:54:47Z ddc:004 open_access

Decision Tree Heuristics Can Fail, Even in the Smoothed Setting Blanc, Guy Lange, Jane Qiao, Mingda Tan, Li-Yang decision trees learning theory smoothed analysis Greedy decision tree learning heuristics are mainstays of machine learning practice, but theoretical justification for their empirical success remains elusive. In fact, it has long been known that there are simple target functions for which they fail badly (Kearns and Mansour, STOC 1996). Recent work of Brutzkus, Daniely, and Malach (COLT 2020) considered the smoothed analysis model as a possible avenue towards resolving this disconnect. Within the smoothed setting and for targets f that are k-juntas, they showed that these heuristics successfully learn f with depth-k decision tree hypotheses. They conjectured that the same guarantee holds more generally for targets that are depth-k decision trees. We provide a counterexample to this conjecture: we construct targets that are depth-k decision trees and show that even in the smoothed setting, these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy. We also show that the guarantees of Brutzkus et al. cannot extend to the agnostic setting: there are targets that are very close to k-juntas, for which these heuristics build trees of depth 2^{Ω(k)} before achieving high accuracy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guy Blanc and Jane Lange and Mingda Qiao and Li-Yang Tan 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.45 urn:nbn:de:0030-drops-147386 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.45 eng https://creativecommons.org/licenses/by/4.0/legalcode