Adaptive Data Depth via Multi-Armed Bandits
Tavor Baharav, Tze Leung Lai; 24(155):1−29, 2023.
Abstract
Data depth is an important tool in data science, robust statistics, and computational geometry. However, many common measures of depth are computationally intensive, making them less practical for broader use. This paper presents a novel instance-adaptive algorithm for adaptive data depth computation. The algorithm reduces the problem of computing depths to a stochastic multi-armed bandit problem, which can be efficiently solved. The focus is on simplicial depth, a promising notion of depth due to its interpretability and asymptotic properties. The proposed algorithm provides general data-dependent theoretical guarantees and can be applied to other common measures of data depth. The complexity of identifying the deepest point in a data set is reduced from O(n^d) to ~O(n^(d-(d-1)α/2)), where α<2 and ~O suppresses a logarithmic factor. Numerical experiments on synthetic data validate the practical utility of the proposed methods.
[abs]