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

DOI10.3150/11-BEJ390zbMATH Open1259.62068arXiv1101.4316MaRDI QIDQ89452FDOQ89452

Pierre-André Zitt, Peggy Cénac, Hervé Cardot, Pierre-André Zitt, Peggy Cénac

Publication date: 1 February 2013

Published in: Bernoulli (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1101.4316

Recommendations

• Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: \(L^p\) and almost sure rates of convergence
• Recursive estimation of the conditional geometric median in Hilbert spaces
• Online estimation of the geometric median in Hilbert spaces: nonasymptotic confidence balls
• Stochastic approximation for multivariate and functional median
• Fast estimation of the median covariation matrix with application to online robust principal components analysis

zbMATH Keywords

functional data\(L^{1}\)-medianCLTgeometric quantileshigh dimensionsonline algorithmsrecursive estimationRobbins-Monro algorithmspatial median

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Asymptotic distribution theory in statistics (62E20) Probability theory on linear topological spaces (60B11) Sequential estimation (62L12)

Cites Work

• A Newton-Raphson version of the multivariate Robbins-Monro procedure
• Multivariate location estimation using extension of \(R\)-estimates through \(U\)-statistics type approach
• Stochastic approximation methods for constrained and unconstrained systems
• \(M\)-estimation, convexity and quantiles
• Trimmed means for functional data
• The averaged Robbins-Monro method for linear problems in a Banach space
• Design-based estimation for geometric quantiles with application to outlier detection
• Online learning algorithms
• Gaussian processes: Inequalities, small ball probabilities and applications
• On a Geometric Notion of Quantiles for Multivariate Data
• Robust functional estimation using the median and spherical principal components
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Acceleration of Stochastic Approximation by Averaging
• An invariance principle for the Robbins-Monro process in a Hilbert space
• Stochastic algorithms for computing means of probability measures
• Title not available (Why is that?)
• A fast and recursive algorithm for clustering large datasets with \(k\)-medians
• Title not available (Why is that?)
• The multivariate L ₁ -median and associated data depth
• Asymptotic Almost Sure Efficiency of Averaged Stochastic Algorithms
• Convergent estimators for the l₁-median of banach valued random variable
• Title not available (Why is that?)
• Note on the median of a multivariate distribution
• Robust Statistics
• Exact \(L_{2}\)-small ball asymptotics of Gaussian processes and the spectrum of boundary-value problems
• Concavity and estimation
• Robust estimation and classification for functional data via projection-based depth notions

Cited In (40)

• Robust Bregman clustering
• A stochastic algorithm finding generalized means on compact manifolds
• Affine-equivariant inference for multivariate location under \({L_p}\) loss functions
• Optimal non-asymptotic analysis of the Ruppert-Polyak averaging stochastic algorithm
• Choices and intervals
• On the rates of convergence of parallelized averaged stochastic gradient algorithms
• The spatial sign covariance operator: asymptotic results and applications
• Depth-based nonparametric description of functional data, with emphasis on use of spatial depth
• The geometric median and applications to robust mean estimation
• Non asymptotic controls on a recursive superquantile approximation
• L^p and almost sure rates of convergence of averaged stochastic gradient algorithms: locally strongly convex objective
• Robust simultaneous inference for the mean function of functional data
• Convergence in quadratic mean of averaged stochastic gradient algorithms without strong convexity nor bounded gradient
• A \(k\)-points-based distance for robust geometric inference
• The spatial distribution in infinite dimensional spaces and related quantiles and depths
• Functional spherical autocorrelation: a robust estimate of the autocorrelation of a functional time series
• Spatial depth-based classification for functional data
• Robust and Scalable Bayes via a Median of Subset Posterior Measures
• Recursive estimation of the conditional geometric median in Hilbert spaces
• Online bootstrap inference for the geometric median
• Stochastic approximation algorithms for superquantiles estimation
• Improved similarity-based modeling for the classification of rotating-machine failures
• Extreme geometric quantiles in a multivariate regular variation framework
• On the Behavior of Extreme d-dimensional Spatial Quantiles Under Minimal Assumptions
• Online estimation of the asymptotic variance for averaged stochastic gradient algorithms
• Robust functional principal components for sparse longitudinal data
• Convergence of Markovian stochastic approximation with discontinuous dynamics
• Spatial quantiles on the hypersphere
• An introduction to recent advances in high/infinite dimensional statistics
• Functional data analysis: an introduction and recent developments
• The deepest point for distributions in infinite dimensional spaces
• Kmedians
• Fast estimation of the median covariation matrix with application to online robust principal components analysis
• Estimating the geometric median in Hilbert spaces with stochastic gradient algorithms: \(L^p\) and almost sure rates of convergence
• Multivariate \(\rho \)-quantiles: a spatial approach
• Geometric median and robust estimation in Banach spaces
• Online stochastic Newton methods for estimating the geometric median and applications
• Multi-sample comparison using spatial signs for infinite dimensional data
• Robust optimal estimation of location from discretely sampled functional data
• Robust functional sliced inverse regression

Uses Software

• R
• AS 78

This page was built for publication: Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q89452)