Adaptive Data Depth via Multi-Armed Bandits

• URL: http://arxiv.org/abs/2211.03985v2
• Date: Wed, 9 Nov 2022 06:30:43 GMT
• Title: Adaptive Data Depth via Multi-Armed Bandits
• Authors: Tavor Z. Baharav, Tze Leung Lai
• Abstract summary: We develop an instance-adaptive algorithm for data depth computation. We focus on simplicial depth, developed by Liu (1990), which has emerged as a promising notion of depth. We show that we can reduce the complexity of identifying the deepest point in the data set from $O(nd)$ to $tildeO(nd-(d-1)alpha/2)$, where $tildeO$ suppresses logarithmic factors.
• Score: 6.29475963948119
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $n^d$ 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 $\alpha<2$, we show that we can reduce the complexity of identifying the deepest point in the data set (the simplicial median) from $O(n^d)$ to $\tilde{O}(n^{d-(d-1)\alpha/2})$, where $\tilde{O}$ suppresses logarithmic factors. We corroborate our theoretical results with numerical experiments on synthetic data, showing the practical utility of our proposed methods.

Related papers

• Private Geometric Median [10.359525525715421]
  We study differentially private (DP) algorithms for computing the geometric median (GM) of a dataset. Our main contribution is a pair of DP algorithms for the task of private GM with an excess error guarantee that scales with the effective diameter of the datapoints.
  arXiv  Detail & Related papers  (2024-06-11T16:13:09Z)
• Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
  We show at a physics level of rigor that Bayesian inference with a fully connected neural network is solvable. We provide techniques to compute the model evidence and posterior to arbitrary order in $1/N$ and at arbitrary temperature.
  arXiv  Detail & Related papers  (2024-05-26T17:08:04Z)
• Fast kernel half-space depth for data with non-convex supports [5.725360029813277]
  We extend the celebrated halfspace depth to tackle distribution's multimodality. The proposed depth can be computed using manifold gradient making faster than halfspace depth by several orders of magnitude. The performance of our depth is demonstrated through numerical simulations as well as applications such as anomaly detection on real data and homogeneity testing.
  arXiv  Detail & Related papers  (2023-12-21T18:55:22Z)
• On the quality of randomized approximations of Tukey's depth [0.0]
  Tukey's depth is a widely used measure of centrality for multivariate data. It is hard to compute exact approximations of Tukey's depth in high dimensions. We show that a randomized algorithm correctly approximates the maximal depth $1/2$ and depths close to zero.
  arXiv  Detail & Related papers  (2023-09-11T17:52:28Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  We show that our method computes a solution with cost at most $O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$, where $epsilon$ is the privacy guarantee. Although the worst-case guarantee is worse than that of state of the art private clustering methods, the algorithm we propose is practical.
  arXiv  Detail & Related papers  (2022-06-17T09:24:41Z)
• Eikonal depth: an optimal control approach to statistical depths [0.7614628596146599]
  We propose a new type of globally defined statistical depth, based upon control theory and eikonal equations. This depth is easy to interpret and compute, expressively captures multi-modal behavior, and extends naturally to data that is non-Euclidean.
  arXiv  Detail & Related papers  (2022-01-14T01:57:48Z)
• Depth Completion using Plane-Residual Representation [84.63079529738924]
  We introduce a novel way of interpreting depth information with the closest depth plane label $p$ and a residual value $r$, as we call it, Plane-Residual (PR) representation. By interpreting depth information in PR representation and using our corresponding depth completion network, we were able to acquire improved depth completion performance with faster computation.
  arXiv  Detail & Related papers  (2021-04-15T10:17:53Z)
• Efficient Depth Completion Using Learned Bases [94.0808155168311]
  We propose a new global geometry constraint for depth completion. By assuming depth maps often lay on low dimensional subspaces, a dense depth map can be approximated by a weighted sum of full-resolution principal depth bases.
  arXiv  Detail & Related papers  (2020-12-02T11:57:37Z)
• Balanced Depth Completion between Dense Depth Inference and Sparse Range Measurements via KISS-GP [14.158132769768578]
  Estimating a dense and accurate depth map is the key requirement for autonomous driving and robotics. Recent advances in deep learning have allowed depth estimation in full resolution from a single image. Despite this impressive result, many deep-learning-based monocular depth estimation algorithms have failed to keep their accuracy yielding a meter-level estimation error.
  arXiv  Detail & Related papers  (2020-08-12T08:07:55Z)
• Single Image Depth Estimation Trained via Depth from Defocus Cues [105.67073923825842]
  Estimating depth from a single RGB image is a fundamental task in computer vision. In this work, we rely, instead of different views, on depth from focus cues. We present results that are on par with supervised methods on KITTI and Make3D datasets and outperform unsupervised learning approaches.
  arXiv  Detail & Related papers  (2020-01-14T20:22:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.