Adaptive Data Depth via Multi-Armed Bandits
Authors: Tavor Baharav, Tze Leung Lai
JMLR 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We corroborate our theoretical results with numerical experiments on synthetic data, showing the practical utility of our proposed methods. Keywords: multi-armed bandits, data depth, adaptive computation, simplicial depth |
| Researcher Affiliation | Academia | Tavor Z. Baharav EMAIL Department of Electrical Engineering Stanford University Stanford, CA 94305, USA Tze Leung Lai EMAIL Department of Statistics Stanford University Stanford, CA 94305, USA |
| Pseudocode | Yes | Algorithm 1 Adaptive Simplicial Median Algorithm 2 Adaptive top-k Data Depth Algorithm 3 Adaptive Data Depth Meta Algorithm |
| Open Source Code | Yes | Our code is publicly available on Github at https://github.com/Tavor B/ada Simplicial Depth to enable the broader use of Simplicial Depth in data-scientific applications, as well as to reproduce the empirical results in this paper. |
| Open Datasets | No | We simulate our adaptive simplicial median computation scheme on synthetic data sets and show the empirical performance improvement afforded by adaptivity. By adaptively approximating the simplicial depth of points in our data set to the necessary accuracy, we are able to obtain significant computational improvements. All experimental results can be reproduced from our publicly available code: https://github.com/Tavor B/ada Simplicial Depth. As shown in Figure 1a, our adaptive algorithm dramatically outperforms both exact computation and the geometric but nonadaptive solution of Rousseeuw and Ruts, yielding superior scaling with n. Plotting the runtime of these different methods in log-log scale, we observe that the brute force algorithm has a wall clock time scaling theoretically as O(n4), but empirically as roughly O(n3.4), due to the efficiency of batch operations in computation of whether n points are contained within a simplex, which practically scales sublinearly in n. Rousseeuw s algorithm has a runtime which theoretically scales as O(n2), and is practically validated as such with an empirical slope of 2.0. Our algorithm has an instance dependent runtime, where for isotropic Gaussians the runtime scales approximately as O(n1.5). Full experimental details are detailed in Appendix B. |
| Dataset Splits | No | The paper states that data was generated as 'n independent samples from an isotropic gaussian' for each experiment and uses '10 random data sets' for Figure 1a and 'the same randomly generated data set' for Figure 1b, but it does not specify explicit training/test/validation splits in the traditional sense. |
| Hardware Specification | Yes | All experiments were run on one core of an AMD Opteron Processor 6378 with 500GB memory (no parallelism within a trial). |
| Software Dependencies | No | The paper mentions 'BLAS (Basic Linear Algebra Subprograms)' but does not provide specific version numbers for any software dependencies. |
| Experiment Setup | Yes | All adaptive experiments are run with 20 trials per point. As simple Hoeffding-based confidence intervals are known to be overly conservative for multi-armed bandits in practice, to obtain tighter confidence intervals we set tr = .2 2 r log(4nr2/δ) in all our simulations. The threshold for exact computation was determined as whether tr n log n. |