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 routine, only univariate depths need to be computed. For any {\boldsymbol{u}}\in\mathbb{S}^{d-1} , let \mathbb{R}\ni y={\boldsymbol{z}}^{\top}{\boldsymbol{u}} and \mathbb{R}^{n}\ni{\boldsymbol{y}}={\boldsymbol{X}}^{\top}{\boldsymbol{u}}\equiv\{{\boldsymbol{x}}_{1}^{\top}{\boldsymbol{u}},...,{\boldsymbol{x}}_{n}^{\top}{\boldsymbol{u}}\} , such that a depth satisfying the projection property can be written as \inf D(y|{\boldsymbol{y}}) . A depth satisfying the projection property can then be expressed as \inf D(y|\mathbf{y}) . Among the various depths that satisfy the projection property, we will focus on three robust and geometrically affine-invariant notions throughout this article: • Halfspace depth : D_{H}(y|{\boldsymbol{y}})=\frac{1}{n}\min\bigl\{\#({\boldsymbol{y}}\leq y),\#({\boldsymbol{y}}\geq y)\bigr\}\,, where \# denotes the cardinal of a set, with the vector-scalar operation applicable element-wise. • Projection depth : D_{P}(y|{\boldsymbol{y}})=\Bigl(1+\frac{|y-\text{med}({\boldsymbol{y}})|}{\text{MAD}({\boldsymbol{y}})}\Bigr)^{-1}\,, where \text{med}({\boldsymbol{y}}) denotes the (usual) univariate median and \text{MAD}({\boldsymbol{y}})=\text{med}\bigl(|{\boldsymbol{y}}-\text{med}({\boldsymbol{y}})|\bigr) stands for the median absolute deviation for the median. • Asymmetric projection depth : D_{AP}(y|{\boldsymbol{y}})=\Bigl(1+\frac{\bigl(y-\text{med}({\boldsymbol{y}})\bigr)_{+}}{\text{MAD}_{+}({\boldsymbol{y}})}\Bigr)^{-1}\,, where (a)_{+}=\max\{a,0\} and \text{MAD}_{+}({\boldsymbol{y}}) is the median of the positive deviations from the median. It is noteworthy that all three of the aforementioned univariate notions are computable with the best achievable complexity of \mathcal{O}(n) . However, implementation details may reveal important differences, as we will discuss in Section 4 . 3 Massive Parallel Computation of Data Depth We propose a viable methodology to compute the depth of a point considering a large number of directions and samples in the data set. A projection-based notion follows three (main) operations to compute the final depth: 1. Generating k directions in \mathbb{S}^{d-1} . 2. Projecting the data onto these directions. 3. Computing the univariate depth within each projection. The time importance of each operation is illustrated in Figure 1 . Here, directions are randomly generated following a uniform distribution in \mathbb{S}^{d-1} ( i.e. , without refinements). The univariate depth is computed using three depth notions: D_{H} in blue lines, D_{P} in red lines, and D_{AP} in black lines. The left graph shows the time percentage of each operation with respect to the number of directions ( k ), with the space dimension d fixed at 150 and the data set {\boldsymbol{X}} containing 1,000 samples. We note that the time percentage remains nearly constant for all k , as the time for both main operations (direction generation and projection) grows proportionally with the number of directions. Overall, projection operations dominate the runtime, being the most time-consuming step. The right graph, using 1,000 directions and a data set with 1,000 samples, examines the effect of the space dimension on time percentage. Here, D_{P} and D_{AP} show a greater emphasis on univariate depth computation, as these notions rely on (practically) more time-consuming operations like the median. In contrast, D_{H} relies solely on value comparisons, making it less computationally intensive in this context. Figure 1 : The time breakdown for computing projection depth on CPU without parallelization is illustrated as follows: blue lines represent the time spent generating directions in the unit sphere, following a normal distribution; red lines represent the time spent projecting onto these directions; black lines represent the time spent computing the univariate (projection) depth. Left graph: Displays the percentage of time spent on each operation, with n (number of points) fixed at 1,000 and d (space dimension) to 150. Right graph: Displays the percentage of time spent on each operation with respect to the space dimension d , with n and k (number of directions) fixed at 1,000. The time complexity of these three operations depends on the number of points n , directions k , and space dimensions d , reflecting their computational significance. 1. Generating directions: This operation has a time complexity of \mathcal{O}(kd) and is the least computationally intensive among the three, as it involves generating k random directions in a d -dimensional space. 2. Projecting data: This step has a time complexity of \mathcal{O}(knd) , which grows with the space dimension d due to the tensor multiplications required to project the data onto the generated directions. This operation is more computationally demanding than generating directions. 3. Computing univariate depths: The time complexity of this operation depends on the chosen depth notion. For instance, in the case of projection depth ( D_{P} ), the complexity is \mathcal{O}(kn) . For a generic depth notion, the complexity is denoted as \mathcal{O}(\mathcal{D}) . This step can be computationally significant, especially for depth notions that involve more complex calculations, such as the median. With a resulting time complexity of \mathcal{O}(kd)\cup\mathcal{O}(knd)\cup\mathcal{O}(\mathcal{D}) , the objective of this article is to develop a method for massive parallelization of the rate-determining operation, \mathcal{O}(knd) , using an optimization routine called Refined Random Search (RRS). This approach aims to significantly reduce computational time while maintaining the precision of the algorithm. Several optimization methods have been used to identify the direction that minimizes the depth of a point, including (best performing) RRS, coordinate descent, and the Nelder-Mead method [ Dyckerhoff et al. 2021 ] . Among these methods, we selected RRS due to its balance of precision and parallelization potential, making it the most suitable for constructing our framework methodology. This algorithm is further explored in Section 4 . Our approach leverages the complete parallel computation of depth, including both projection and univariate depth calculation, for a point with respect to different directions within the same refinement. By focusing on data projection, this approach allows our framework to decompose \mathcal{O}(knd) into synchronous, parallel calculations. Let us introduce our approach with the following model. All mentioned operations result in a characteristic time T_{C} , where each operation has an associated cost and respective time complexity. We denote the total number of directions per refinement as m , where m=\left\lceil{\frac{k}{r}}\right\rceil , T_{C} can be written as: T_{C}=C_{c}+r\cdot\left(C_{rv}\cdot m\cdot d+C_{p}\cdot m\cdot n\cdot d+C_{d_{(1)}}\cdot\mathcal{D}\right), (1) where C_{c} is a constant computational cost, C_{rv} is the cost of generating random directions, C_{p} is associated with projecting data, C_{d_{(1)}} represents the additional multiplicative factor of the univariate depth computation. These operations have distinct computational characteristics and are parallelized in different ways. Our goal is to break down each of these steps into multiple simple tasks suitable for massive parallel ( e.g. , with GPU) computation. Most of these operations can be reduced to tensor multiplication(s), floating-point operations (FLOPS), and conditional statements. In parallel computing, these operations are referred to as embarrassingly parallel , as most of their steps can be performed concurrently [ Navarro et al. 2014 ] . In g -massive parallel computation ( e.g. , in a GPU with g computing units): • generating random directions can be performed in \left\lceil{\frac{m\cdot d}{g}}\right\rceil steps, • depth computation can be completed in \left\lceil\frac{\mathcal{D}}{g}\right\rceil steps, • projecting data can be executed in \left\lceil{\frac{m\cdot n\cdot d}{g}}\right\rceil steps. Let us denote with the term \left\lceil{\frac{d}{d(m,n)_{max}}}\right\rceil the breakdown of the inner product ( {\boldsymbol{x}}{\boldsymbol{u}}^{\top} ). Depending on the size of the vectors, vector multiplication might be further divided into smaller kernels to accommodate memory usage: \boldsymbol{x}\boldsymbol{u}^{\top}=\sum_{i=1}^{d}x_{i}\cdot u_{i}=\sum_{i=1}^{p}x_{i}\cdot u_{i}+\sum_{j=p+1}^{d}x_{j}\cdot u_{j}. Further, let \lambda denote the ratio between the massive parallel frequency ( e.g. , a GPU core frequency) and the basic (non-parallel) frequency ( e.g. , a CPU core frequency) to be considered in the parallel time equation. With the frequency ratio \lambda=\frac{f_{CPU}}{f_{GPU}} , characteristic time for our parallel approach T_{G} can be written as: T_{G}=C_{c}+r\cdot\lambda\cdot\Biggl(C_{rv}\cdot\left\lceil{\frac{m\cdot d}{g}}\right\rceil+C_{p}\cdot\left\lceil{\frac{d}{d_{max(m,n)}}}\right\rceil\cdot\left\lceil{\frac{m\cdot n}{g}}\right\rceil+C_{d_{(1)}}\cdot\left\lceil{\frac{\mathcal{D}}{g}}\right\rceil\Biggr). (2) Following Amdahl’s law for parallel speedup, we can construct a theoretical time ratio to model the behavior of our approach in a system with g massively-parallel ( e.g. , GPU) cores [ Amdahl 2007 , Gustafson 1988 , Marowka 2012 ] . Speedup ( S_{p} ) is formalized as the ratio between characteristic times, expressed as: S_{p}=\frac{T_{C}}{T_{G}}. (3) After formalizing these equations, we now propose an optimized algorithmic framework for massively-parallel depth parallelization. 4 Algorithmic framework for massive parallelization Refined Random Search algorithm combines purely random approximation, using independent directions uniformly distributed over the unit sphere, with an optimization element. Specifically, this optimization routine consists of three steps, repeated within each refinement. A brief explanation of the main operation is provided in Algorithm 1 . For more details on the RRS algorithm, see Dyckerhoff et al. 2021 and Section A in the Supplementary Material. Algorithm 1 Classical refined random search Input: {\boldsymbol{X}}\in\mathbb{R}^{n\times d} , {\boldsymbol{z}}\in\mathbb{R}^{d} , k , r , \alpha . Step 1. Set {\boldsymbol{p}}=\boldsymbol{\mathrm{e}}_{1} , D_{min}=1 , m=\lceil\frac{k}{r}\rceil , \epsilon=\frac{\pi}{2} . Step 2. Loop for each refinement: For l=1 to r : Step 3. Minimize depth in the \epsilon -region: For j=1 to m : (a) Generating direction: \mathbb{R}^{d}\ni{\boldsymbol{u}}_{j}\sim\mathcal{U}(\mathbb{S}^{d-1}) inside an \epsilon -region around {\boldsymbol{p}} . (b) Projecting the data: {\boldsymbol{y}}_{j}={\boldsymbol{X}}^{\top}{\boldsymbol{u}}_{j} and y_{j}={\boldsymbol{z}}^{\top}{\boldsymbol{u}}_{j} . (c) Computing univariate depth: D_{j}=D(y_{j}|{\boldsymbol{y}}_{j}) . Step 4. Minimal depth D_{l}=\min_{j\in\{1,...,m\}}D_{j} and its respective direction \boldsymbol{u_{l}} . Step 5. Reevaluate depth: if D_{l}