Research map / Learning theory and algorithms / Prediction and decision losses

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

AAAI 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Optimal decision tree learning · 3 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Studies parameterized and kernelization complexity of decision tree learning with a bounded number of outlier examples (DTSO/DTDO), showing W[1]-hardness, FPT results with the outlier budget as parameter, and several compression lower and upper bounds.

Problem

Learning small decision trees (minimum size or depth) that may misclassify up to t training examples; prior exact parameterized results do not allow outliers, and a single outlier can make hard instances trivial.

Approach

Generalizes DTS and DTD to DTSO and DTDO by allowing t outlier examples, shows W[1]-hardness for the parameters s+δmax and d+δmax via a reduction from Partial Vertex Cover, and recovers FPT by adding t as a parameter through an extended minimal-support-set branching algorithm.

Key results

• DTSO and DTDO are W[1]-hard when parameterized by s+δmax and d+δmax respectively, and remain W[1]-hard by s and d even when δmax ≤ 3.
• DTSO and DTDO are FPT when parameterized by s+δmax+t and d+δmax+t respectively.
• DTS and DTD admit a trivial polynomial kernel parameterized by Dmax+|F| when δmax is constant, while DTD parameterized by d+|F| has no polynomial compression even with δmax ≤ 3 (unless NP ⊆ coNP/poly).

Surprising findings

• Even with a single outlier allowed, a W[1]-hard instance for DTS/DTD becomes trivially solvable (depth/size 0), so small slack can drastically reduce complexity.

Limitations

• Purely theoretical; no experiments or implementation reported.
• FPT for DTSO/DTDO still depends on δmax and t; FPT by s+|F| (without t) left open.
• Incompressibility results rule out polynomial kernels for several parameterizations, leaving DTS by s+|F| open.

Experimental setup

Baselines: DTS DTD YaDT

Builds on: Eiben et al. FPT algorithms for DTS and DTD Ordyniak and Szeider W[1]-hardness reductions Partial Vertex Cover W[1]-hardness sunflower lemma

Closest papers by meaning

• Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.92)
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.91)
• Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.89)
• Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.89)
• Symbolic Regression Enhanced Decision Trees for Classification Tasks (AAAI 2024 · similarity 0.89)
• Learning Small Decision Trees for Data of Low Rank-Width (AAAI 2024 · similarity 0.89)