Near-Optimal Decision Trees in a SPLIT Second

Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer · 2025

Read Near-Optimal Decision Trees in a SPLIT Second by Varun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15988.txt.

Description

Varun Babbar and co-authors chase decision trees that are nearly optimal yet built at greedy speed. Their 2025 paper addresses a standing trade-off in interpretable machine learning: greedy tree growing is fast but provably suboptimal, while exact search finds the best small trees at crushing cost. Their SPLIT family of algorithms looks ahead where it matters.

The key insight is that the deep parts of the tree need not be solved exactly, since greediness suffices near the leaves. Skipping exactness there prunes an exponential blowup, buying orders of magnitude in speed. The authors pitch the method as a step toward trees that regulators can read and engineers can still afford.

Catalog record

CREATORVarun Babbar, Hayden McTavish, Cynthia Rudin, Margo Seltzer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE139 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-15988

Browse the full library · About the Tower of Babel