A0725
Title: Optimization on the d-sphere to approximate halfspace depth
Authors: Jeremy Guerin - LTCI, Telecom Paris, Institut Polytechnique de Paris (France) [presenting]
Pavlo Mozharovskyi - LTCI, Telecom Paris, Institut Polytechnique de Paris (France)
Yann Issartel - Telecom Paris (France)
Sibsankar Singha - LTCI Telecom Paris (France)
Abstract: In a multivariate space, data depth is a statistical function that measures the centrality of a point with respect to a distribution or a data set. Thanks to desirable properties of robustness and invariance, data depth functions are currently used in a variety of tasks as a generalization of quantiles and ranks to higher dimensions and as an alternative to the distribution function, with Tukey's halfspace depth being the seminal and yet most studied in the literature. Nevertheless, its applications are impeded by the high complexity of exact algorithms (which is exponential with respect to dimension) and lack of efficient approximation methods, in particular those delivering corresponding guarantees on the approximated value. An algorithm is proposed that can efficiently compute the halfspace depth and derive the required statistical guarantees for the obtained depth value. More precisely, once in a proper attraction basin, the value of the halfspace depth can be found as a solution to a quasi-convex optimization problem. An iterative algorithm running over the surface of the unit hyper-sphere is proposed, which allows for derivation of the corresponding guarantees on the empirical halfspace depth value.
