Optimal Sparse Recovery with Decision Stumps
Authors: Kiarash Banihashem, Mohammad Hajiaghayi, Max Springer
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We further validate our theoretical results and proof methodology using computational experiments. In this section, we provide further justification of our theoretical results in the form of simulations on the finite sample count for active feature recovery under different regimes, as well as the predictive power of a single sub-tree as compared to the full tree. We additionally contrast DSTUMP with the widely studied optimal LASSO . We first validate the result of Theorem 0.1 and consider the linear design with p = 200 and design matrix entries sampled i.i.d. from U(0, 1) with additive Gaussian noise N(0, .1). Concretely, we examine the optimal number of samples required to recover approximately 95% of the active features s. This is achieved by conducting a binary search on the number of samples to find the minimal such value that recovers the desired fraction of the active feature set, averaged across 25 independent replications. In the leftmost plot of Figure 1, we plot the sample count as a function of varying sparsity levels s [5, 100] for DSTUMP with a median split, DSTUMP with the optimal split, as well as LASSO for benchmarking (with penalty parameter selected through standard cross-validation). |
| Researcher Affiliation | Academia | Kiarash Banihashem, Mohammad Taghi Hajiaghayi, Max Springer University of Maryland kiarash@umd.edu, hajiagha@cs.umd.edu, mss423@umd.edu |
| Pseudocode | Yes | Algorithm 1: Scoring using DSTUMP and A formal pseudo-code of our approach is given in Algorithm 1. and Algorithm 2: Unknown |S| |
| Open Source Code | No | The paper describes algorithms and refers to code for experiments, but does not provide concrete access to the source code for the methodology described. |
| Open Datasets | No | The paper describes generating synthetic data for experiments ("design matrix entries sampled i.i.d. from U(0, 1) with additive Gaussian noise N(0, .1)") rather than using a publicly available or open dataset with access information. |
| Dataset Splits | No | The paper does not provide specific dataset split information (percentages, sample counts, or detailed splitting methodology) for its experiments. |
| Hardware Specification | No | The paper does not provide specific hardware details (like GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library names with version numbers, needed to replicate the experiments. |
| Experiment Setup | No | The paper describes the data generation process and evaluation metric, but does not provide specific experimental setup details such as hyperparameter values, training configurations, or system-level settings for the models. |