Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm

By Hervé Cardot, P. C'enac, Pierre-André Zitt. 2011

129 citations recorded by the source corpus.

With the progress of measurement apparatus and the development of automatic sensors it is not unusual anymore to get thousands of samples of observations taking values in high dimension spaces such as functional spaces. In such large samples of high dimensional data, outlying curves may not be uncommon and even a few individuals may corrupt simple statistical indicators such as the mean trajectory. We focus here on the estimation of the geometric median which is a direct generalization of the real median and has nice robustness properties. The geometric median being defined as the minimizer of a simple convex functional that is differentiable everywhere when the distribution has no atoms, it is possible to estimate it with online gradient algorithms. Such algorithms are very fast and can deal with large samples. Furthermore they also can be simply updated when the data arrive sequentially. We state the almost sure consistency and the L2 rates of convergence of the stochastic gradient estimator as well as the asymptotic normality of its averaged version. We get that the asymptotic distribution of the averaged version of the algorithm is the same as the classic estimators which are based on the minimization of the empirical loss function. The performances of our averaged sequential estimator, both in terms of computation speed and accuracy of the estimations, are evaluated with a small simulation study. Our approach is also illustrated on a sample of more 5000 individual television audiences measured every second over a period of 24 hours.

Subfields: Artificial Intelligence, Control and Systems Engineering, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Control and Systems Engineering

In Statistics and Probability

Citations in the corpus

Distributed Statistical Machine Learning in Adversarial Settings (2017, methodology): “Geometric median is a generalization of median in one-dimension to multiple dimensions, and has been widely used in robust statistics [5, 13, 21, 24].”
Geometric median and robust estimation in Banach spaces (2013, methodology): “For other approaches to fast numerical evaluation of the geometric median, see [6,13,15,37] and references therein.”
On the rates of convergence of parallelized averaged stochastic gradient algorithms (2017, positive): “, p and k ≥ 1 by [23] mi,k+1 = mi,k + γk Xi,k+1 − mi,k ∥∥Xi,k − mi,k∥∥ .”
Optimal non-asymptotic bound of the Ruppert-Polyak averaging without strong convexity (2017, methodology): “Nevertheless, if we assume for the sake of simplicity that the support of X is bounded (which is not assumed in the initial works of [CCZ13, CCGB17]), then following the arguments of [Kem87], the median is uniquely deﬁned as soon as the distribution of X is not concentrated on a single straight…”