Research map / Learning theory and algorithms / Prediction and decision losses
Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees
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.
Gives a deterministic fully-dynamic algorithm that maintains an approximate greedy decision tree (Gini, information, or variance gain) with worst-case per-update time polylogarithmic in n and linear in d.
Problem
Maintaining a greedy decision tree under an adversarial sequence of insertions and deletions while bounding the worst-case (not amortized) update time, which prior work only achieved amortized.
Approach
Introduces decision rules and epsilon-approximate decision trees, reduces the fully-dynamic problem to a delayed construction problem solved per vertex with periodic rebuilds spread over the next epsilon|S| updates, so each update does bounded work instead of recomputing the whole tree.
Key results
- Maintains a Gini-gain epsilon-feasible decision tree with O(d log^4 n / eps^3) worst-case operations per update, versus amortized O(d log^3 n / eps^2) of prior work.
- Information gain bound O(d log^7 n / eps^3) and variance gain bound O(d c^2 log^4 n / eps^3) worst-case per update.
- Delayed approximate tree algorithm uses O(h log n (h + d log n / eps + f(n)/(eps n))) operations per update, with h the tree height.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use fudy-wc to maintain an ε-feasible Gini-gain tree with worst-case rather than amortized update guarantees | Fully-dynamic decision trees · Gini gain, binary labels | operations per update: O\!\left(\frac{d \log^3 n}{\min(\alpha,\beta)^2}\right) -> O\!\left( \frac{d \log^4 n}{\min(\alpha,\beta)^3} \right) | Mixed |
Limitations
- Bounds are theoretical; no experimental evaluation is reported.
- Worst-case bounds carry a poly(log n / eps) overhead relative to the amortized prior result.
- Information gain and variance gain bounds are worse than Gini by additional log factors or c^2 dependence.
Experimental setup
Metrics: worst-case operations per update approximation guarantee (epsilon-approximate / epsilon-feasi
Baselines: Cesari et al. fully-dynamic epsilon-feasible decision tree algorithm
Builds on: ID3 C4.5 epsilon-feasibility (Cesari et al.) Hoeffding trees
Closest papers by meaning
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.85)
- SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration (NeurIPS 2025 · similarity 0.85)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.84)
- TTTS: Tree Test Time Simulation for Enhancing Decision Tree Robustness against Adversarial Examples (AAAI 2024 · similarity 0.84)
- Robust Loss Functions for Training Decision Trees with Noisy Labels (AAAI 2024 · similarity 0.84)
- Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.