Massive parallelization of projection-based depths
Leonardo Leone · 2025
Read Massive parallelization of projection-based depths by Leonardo Leone (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-08262.txt.
Introduction
Leonardo Leone and co-authors massively speed up projection-based data depth on graphics processors, in a paper from two thousand twenty-five. Data depth grades how central a point sits in a cloud, but high dimensions make it costly. Their framework rests on a refined random search algorithm.
Speedups reached about seven thousand times on graphics hardware. Synthetic tests showed better precision in less time. The method suits large-scale work that once priced depth out. The algorithm and other depth tools ship in a public Python library, data-depth. Ready examples invite reuse and extension, the authors note.
Catalog record
| CREATOR | Leonardo Leone |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-08262
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Massive parallelization of projection-based depths Leonardo Leone Abstract This article introduces a novel methodology for the massive parallelization of projection-based depths, addressing the computational challenges of data depth in high-dimensional spaces. We propose an algorithmic framework based on Refined Random Search (RRS) and demonstrate significant speedup (up to 7,000 times faster) on GPUs. Empirical results on synthetic data show improved precision and reduced runtime, making the method suitable for large-scale applications. The RRS algorithm (and other depth functions) are available in the Python -library data-depth with ready-to-use tools to implement and to build upon this work. Keywords: Data Depth, Parallel Computing, Projection-Based Depths, Refined Random Search, GPU Acceleration. 1 Introduction The concept of data depth has become a cornerstone in multivariate statistics, offering a non-parametric measure of centrality and outlyingness in high-dimensional spaces. Introduced by Tukey 1975 , data depth functions quantify the centrality of a point within a data set, providing a robust alternative to traditional distance-based metrics. However, the computational complexity of calculating data depth, especially in high-dimensional settings, has hindered its practical application. Current work addresses these challenges by introducing a novel methodology for the massive parallelization of projection-based depths, significantly enhancing computational efficiency and scalability. Projection-based depths, such as halfspace depth, projection depth, and asymmetric projection depth, are particularly well-suited for high-dimensional data analysis due to their affine invariance and robustness. These depths satisfy the weak projection property, allowing multivariate depths to be computed as the minimum of univariate depths across projections in all directions. However, exploring all possible directions in high-dimensional spaces is computationally unfeasible, necessitating optimization routines like the Refined Random Search (RRS). While RRS has shown promise, it is often limited by sequential computation, failing to fully leverage modern parallel computing architectures. In this article, we propose an algorithmic framework that harnesses GPU acceleration to achieve massive parallelization of projection-based depths. Our approach builds upon the RRS algorithm and extends it by decomposing the computation into highly parallelizable tasks suited for GPU architecture. First, we formalize characteristic time equations for both our parallel approach ( T_{G} ) and the standard approach ( T_{C} ), and derive speedup equations ( S_{p} ) for RRS inspired by Amdahl’s law [ Amdahl 2007 ] . The theoretical speedup S_{p} is expressed as a quotient involving \lambda\cdot d , where \lambda is the ratio of CPU to GPU frequency ( \lambda=\frac{f_{CPU}}{f_{GPU}} ), d is the dimension, and g is the number of available GPU cores. This reevaluation of Amdahl’s law highlights speedup limitations due to core speed, core quantity, and sequential operations. Second, we decompose the computation of projection-based depths into parallelizable tasks, achieving significant speedups of up to 7,000 times faster than state-of-the-art methods, particularly when implemented on GPUs like the NVIDIA GeForce RTX 4080 (see [ Dyckerhoff and Mozharovskyi 2016 , Fojtík et al. 2023 ] , and for projection depth [ Zuo and Lai 2011 ] ). The key innovation lies in the parallelization of the three main operations involved in depth computation: direction generation, data projection, and univariate depth calculation. By breaking these operations into simple, embarrassingly parallel tasks, we achieve efficient use of GPU resources, resulting in dramatic reductions in runtime without sacrificing precision. Third, we provide insights into hyperparameter fine-tuning, such as the selection of spherical cap shrinkage, the number of refinements, and directions, to optimize convergence and runtime. These findings ensure the robustness and adaptability of our method across different data sets and dimensionalities. The center-outward ordering precision, evaluated through ranking correlation techniques, confirms the reliability of our approach in high-dimensional data analysis. Our contributions are multifold. First, we introduce a novel algorithmic framework for the massive parallelization of projection-based depths, achieving significant speedups on GPUs. Second, we provide a comprehensive analysis of the computational challenges associated with data depth and demonstrate the effectiveness of our approach in overcoming these challenges. Third, we explore hyperparameter fine-tuning for the RRS algorithm, providing insights into optimal parameter selection for large-scale scenarios. Finally, we conduct a thorough runtime analysis, demonstrating the empirical speedup achieved by our method and validating our theoretical model. These contributions not only advance the state-of-the-art in data depth computation but also pave the way for broader adoption of depth-based methods in practical applications. By overcoming the computational bottlenecks, we enable researchers and practitioners to leverage the full potential of data depth in large-scale, high-dimensional settings, opening new avenues for robust statistical analysis. The remainder of the paper is organized as follows. Section 2 provides a detailed background on data depth, focusing on projection-based depths and their computational challenges. Section 3 introduces our methodology for massive parallelization, detailing the parallelization of each operation and the theoretical underpinnings of our approach. Section 4 presents the complete massively-parallel algorithm, including the integration of parallel directions generation, projection, and depth computation. In Section 5 , we explore hyperparameter fine-tuning for the RRS algorithm, providing insights into optimal parameter selection for large-scale scenarios. Section 6 conducts a thorough runtime analysis, demonstrating the empirical speedup achieved by our method and validating our theoretical models. Finally, Section 7 evaluates the precision of our approach through center-outward ordering and depth benchmarking, confirming its effectiveness in high-dimensional data analysis. Section 8 concludes. 2 Background on data depth In this section, we review the most relevant aspects of data depth from an optimization perspective. For simplicity, we focus on the empirical version of data depth throughout this article. Following Tukey’s seminal idea [ Tukey 1975 ] , data depth is a statistical function that measures the degree to which an arbitrary observation belongs to a data set. Consider a data set {\boldsymbol{X}}=\{{\boldsymbol{x}}_{1},...,{\boldsymbol{x}}_{n}\}\subset\mathbb{R}^{d} (using set notation for convenience, though ties are generally not excluded) and a point {\boldsymbol{z}}\in\mathbb{R}^{d} . Definition 1 . Data depth is a function D\,:\,\mathbb{R}^{d}\times\mathbb{R}^{n\times d}\rightarrow[0,1]\,,\,({\boldsymbol{z}},{\boldsymbol{X}})\mapsto D({\boldsymbol{z}}|{\boldsymbol{X}})\,, which satisfies the properties of affine invariance, vanishing at infinity, monotonicity on rays originating from the deepest point, and upper-semicontinuity. For a comprehensive and formal discussion on data depth and its axiomatics, we refer the reader to Zuo and Serfling 2000 and Mosler and Mozharovskyi 2022 . In this article, we focus on a property that is particularly relevant to our current analysis: the weak projection property . Let \mathbb{S}^{d-1}=\{{\boldsymbol{x}}\in\mathbb{R}^{d}\,:\,\|{\boldsymbol{x}}\|=1\} denote the unit sphere and ⊤ be the transposition operator. Definition 2 ( Dyckerhoff 2004 ) . The function D from Definition 1 satisfies the weak projection property if for any {\boldsymbol{z}}\in\mathbb{R}^{d},{\boldsymbol{X}}\subset\mathbb{R}^{d} , it holds: D({\boldsymbol{z}}|{\boldsymbol{X}})=\inf_{{\boldsymbol{u}}\in\mathbb{S}^{d-1}}D({\boldsymbol{z}}^{\top}{\boldsymbol{u}}|{\boldsymbol{X}}^{\top}{\boldsymbol{u}})\,. In the following, we will omit the term “weak”, and simply refer to depths that satisfy the projection property . These include Mahalanobis [ Mahalanobis 2018 ] , halfspace [ Tukey 1975 ] , zonoid [ Koshevoy and Mosler 1997 ] , projection [ Zuo and Serfling 2000 ] , asymmetric projection [ Dyckerhoff 2004 ] , (continuous) expected convex hull [ Cascos 2007 ] , geometrical [ Dyckerhoff and Mosler 2011 ] depths. Definition 2 leads to the following computationally important corollary: Corollary 1 . Let {\boldsymbol{u}}_{1},...,{\boldsymbol{u}}_{k}\subset\mathbb{S}^{d-1} , then: D({\boldsymbol{z}}|{\boldsymbol{X}})\leq\min_{j=1,...,k}D({\boldsymbol{z}}^{\top}{\boldsymbol{u}}_{k}|{\boldsymbol{X}}^{\top}{\boldsymbol{u}}_{k})\,. In other words, multivariate data depths can be computed as the minimum of univariate depths across projections in all directions. Since exploring all possible directions (an infinite set) is computationally infeasible, a finite subset must be examined using an optimization routine. Within this