# Adaptive Data Depth via Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2211.03985 · HTML: https://mlsanity.com/paper/2211.03985/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 72 references that are in the map.
- First posted on arXiv 8 Nov 2022.

## Builds on (most cited first, 22 of 22)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime](https://mlsanity.com/paper/1702.05186/) (2017)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)
- [Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits](https://mlsanity.com/paper/1902.00197/) (2019)
- [Adaptive Sampling for Coarse Ranking](https://mlsanity.com/paper/1802.07176/) (2018)
- [Adaptive Estimation for Approximate k-Nearest-Neighbor Computations](https://mlsanity.com/paper/1902.09465/) (2019)
- [Learning Nearest Neighbor Graphs from Noisy Distance Samples](https://mlsanity.com/paper/1905.13267/) (2019)
- [Approximate Function Evaluation via Multi-Armed Bandits](https://mlsanity.com/paper/2203.10124/) (2022)
- [Approximating the Simplicial Depth](https://mlsanity.com/paper/1512.04856/) (2015)
- [Query Complexity of k-NN based Mode Estimation](https://mlsanity.com/paper/2010.13491/) (2020)
- [Adaptive Learning of Rank-One Models for Efficient Pairwise Sequence Alignment](https://mlsanity.com/paper/2011.04832/) (2020)
- [From Crossing-Free Graphs on Wheel Sets to Embracing Simplices and Polytopes with Few Vertices](https://mlsanity.com/paper/1812.01595/) (2018)

## Built on by (most cited first, 1 of 1)

- [seMCD: Sequentially implemented Monte Carlo depth computation with statistical guarantees](https://mlsanity.com/paper/2507.06227/) (2025)

## Abstract (arXiv)

Data depth, introduced by Tukey (1975), is an important tool in data science, robust statistics, and computational geometry. One chief barrier to its broader practical utility is that many common measures of depth are computationally intensive, requiring on the order of nd operations to exactly compute the depth of a single point within a data set of n points in d-dimensional space. Often however, we are not directly interested in the absolute depths of the points, but rather in their relative ordering. For example, we may want to find the most central point in a data set (a generalized median), or to identify and remove all outliers (points on the fringe of the data set with low depth). With this observation, we develop a novel and instance-adaptive algorithm for adaptive data depth computation by reducing the problem of exactly computing n depths to an n-armed stochastic multi-armed bandit problem which we can efficiently solve. We focus our exposition on simplicial depth, developed by Liu (1990), which has emerged as a promising notion of depth due to its interpretability and asymptotic properties. We provide general instance-dependent theoretical guarantees for our proposed algorithms, which readily extend to many other common measures of data depth including majority depth, Oja depth, and likelihood depth. When specialized to the case where the gaps in the data follow a power law distribution with parameter α<2, we show that we can reduce the complexity of identifying the deepest point in the data set (the simplicial median) from O(nd) to tildeO(nd-(d-1)α/2), where tildeO suppresses logarithmic factors. We corroborate our theoretical results with numerical experiments on synthetic data, showing the practical utility of our proposed methods.