A0307
Title: A polynomial-time algorithm for optimization-based depths
Authors: Jeremy Guerin - LTCI, Telecom Paris, Institut Polytechnique de Paris (France) [presenting]
Pavlo Mozharovskyi - LTCI, Telecom Paris, Institut Polytechnique de Paris (France)
Abstract: Data depth is a statistical function which, by introducing centrality-based ordering, generalizes concepts of median and quantiles to higher dimensions. It has undergone substantial theoretical developments and is renowned for its attractive properties, such as affine invariance or robustness. In its variety of depth notions, data depth has become a universal methodology in statistics with numerous applications. However, using such functions in practice is limited by the computational complexity of algorithms which are exponential in data dimension. To cope with this computational intractability, we introduce a novel class of depth functions: depths that can be written as a polynomial (on a properly chosen domain) optimization problem. This class is sufficiently large to contain some of the most commonly used depth notions. In order to compute these depth functions, we suggest using a hierarchy of semidefinite programming relaxations. This method relies on the use of the sum-of-squares certificates of positivity. The goal is to obtain algorithms able to compute such functions in time that are polynomial in both size and dimension of the data set at hand. Finally, a simulation study explores in detail the properties of the proposed family of algorithms.
