Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time Guarantees
Authors: Marco Bressan, Mauro Sozio
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first algorithm with strong guarantees on both the quality of the tree and the worst-case update time (the maximum number of operations the algorithm performs between two dataset updates). For instance, we can maintain a tree where each node has Gini gain within β of the optimum, while guaranteeing an update time O d β 3 log4 n , where d is the number of features and n the maximum size of the dataset. This is optimal up to polylogarithmic factors, as any dynamic algorithm must have update time in Ω(d). Similar guarantees hold for the variance and information gain, for classification and regression, as well as for boosted trees. ... Conditional lower bounds based on 3SUM and OVH (Section 6). |
| Researcher Affiliation | Academia | 1Department of Computer Science, University of Milan, Italy. 2Institut Polytechnique de Paris, Telecom Paris. Correspondence to: Marco Bressan <marco.bressan@unimi.it>, Mauro Sozio <sozio@telecom-paris.fr>. |
| Pseudocode | Yes | Algorithm 1 GREEDYρ ... Algorithm 2 FUDY-WC ... Algorithm 3 DELAY-APX |
| Open Source Code | No | The paper does not mention the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore it does not refer to any publicly available or open datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on specific datasets, therefore it does not provide information about training/test/validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and describes algorithms, but does not provide specific software dependencies or version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and theoretical guarantees. It does not describe any empirical experimental setup with hyperparameters or system-level training settings. |