Tree Learning: Optimal Sample Complexity and Algorithms
Authors: Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we empirically verify our theoretical findings by evaluating the prediction accuracy of binary trees constructed from labeled triplets on the unlabeled triplets from the same distribution. |
| Researcher Affiliation | Academia | Dmitrii Avdiukhin 1, Grigory Yaroslavtsev 2, Danny Vainstein 3, Orr Fischer 4, Sauman Das5, Faraz Mirza5 1 Indiana University, Department of Computer Science 2 George Mason University, Department of Computer Science * 3 Tel-Aviv University, Blavatnik School of Computer Science 4 Weizmann Institute of Science, Department of Computer Science and Applied Mathematics 5 Thomas Jefferson High School for Science and Technology |
| Pseudocode | No | The paper describes algorithmic approaches and refers to algorithms from other works (e.g., Aho et al. (1981)), but it does not present any pseudocode or clearly labeled algorithm blocks for its own methods. |
| Open Source Code | No | The paper does not provide any specific repository links or explicit statements about making its source code publicly available. |
| Open Datasets | Yes | For the realizable case, we perform experiments on randomly generated trees and on Image Net (Deng et al. 2009) hierarchy . For non-binary tree experiments (see the full version), we use the full hierarchy (48,860 points), while for binary tree experiments, we sample 256 leaves that induce a binary subtree. |
| Dataset Splits | No | The paper describes sampling triplets for experiments and mentions using subsets of datasets (e.g., 'sample 256 leaves', 'subset of the Spambase dataset of size n'), but it does not specify explicit training, validation, or test dataset split percentages or counts. |
| Hardware Specification | No | The paper describes experiments but does not provide any specific details about the hardware (e.g., CPU, GPU models, memory, or cloud instances) used to run them. |
| Software Dependencies | No | The paper does not provide specific version numbers for any key software components or libraries used in the experiments. |
| Experiment Setup | No | The paper describes the high-level approach for tree construction and constraint generation, but it does not provide specific experimental setup details such as hyperparameter values, learning rates, batch sizes, or optimizer settings. |