Reproduce “Popular decision tree algorithms are provably noise tolerant” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
This research from Stanford and MIT establishes provable noise tolerance for popular impurity-based decision tree algorithms like ID3, C4.5, and CART. The work demonstrates that these algorithms can achieve low error rates with controlled tree sizes even under the strong adversarial 'nasty noise' model, providing near-optimal bounds for their resilience and, in specific cases like monotone decision trees, delivering state-of-the-art performance.
Key insights
- Popular impurity-based decision tree algorithms, such as ID3, C4.5, and CART, are inherently noise-tolerant, even to strong adversarial "nasty noise", justifying their long-observed empirical success.
- Robustness to nasty noise is formally equivalent to robustness against general distributional shifts (measured by Total Variation distance), broadening the applicability of these guarantees.
- The practical greedy heuristics used in these algorithms can achieve theoretical guarantees that are competitive with, or even surpass, those previously known for more complex theoretical constructions for learning decision trees in noisy environments.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.