This Github repository provides the accompanying code for the paper "Adaptive Data Depth via Multi-Armed Bandits" by Tavor Z. Baharav and Tze Leung Lai (arxiv link). The premise of this work is that for many computationally intensive measures of data depth, computational savings can be had by approximating each point's depth adaptively to efficiently recover information regarding the relative ordering of the points.
In this repository we focus on the notion of simplicial depth, and provide algorithms for efficient simplicial median computation (the point in the dataset with the deepest simplicial depth).
The provided code is organized as follows
This file contains python code for our adaptive simplicial median computation method, ada_simplicial_median, which can be imported from this file and called. This file also contains code for the geometric 2d simplicial depth computation method of Rousseeuw and Ruts, 1996.
This file contains the python script for generating the figures contained in the paper. This includes timing for 1) brute force method, 2) state of the art geometric method, 3) our adaptive algorithm. The desired parameters can be found and edited at the bottom of the file, so that to generate simulation results one simply needs to run
python parallelizedBandit.py
This jupyter notebook reads in the simulation results generated by parallizedBandit.py and generates the figures presented in the paper.