×

Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm. (English) Zbl 1259.62068

Summary: With the progress of measurement devices and the development of automatic sensors, it is not unusual anymore to get large samples of observations taking values in high-dimensioal 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 on the estimation of the geometric median which is a direct generalization of the real median in metric spaces and has nice robustness properties. It is possible to estimate the geometric median, being defined as the minimizer of a simple convex functional that is differentiable everywhere when the distribution has no atom, 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 \(L^{2}\) 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 than 5000 individual television audiences measured every second over a period of 24 hours.

MSC:

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

Software:

AS 78; R

References:

[1] Arnaudon, M., Dombry, C., Phan, A. and Yang, L. (2010). Stochastic algorithms for computing means of probability measures. Preprint. Available at . · Zbl 1262.60073 · doi:10.1016/j.spa.2011.12.011
[2] Benveniste, A., Métivier, M. and Priouret, P. (1990). Adaptive Algorithms and Stochastic Approximations. Applications of Mathematics ( New York ) 22 . Berlin: Springer. · Zbl 0752.93073
[3] Bottou, L. (2010). Large-scale machine learning with stochastic gradient descent. In Compstat 2010 (Y. Lechevallier and G. Saporta, eds.) 177-186. Heidelberg: Springer.
[4] Cadre, B. (2001). Convergent estimators for the \(L_{1}\)-median of a Banach valued random variable. Statistics 35 509-521. · Zbl 0996.62051 · doi:10.1080/02331880108802751
[5] Cardot, H., Cénac, P. and Chaouch, M. (2010). Stochastic approximation to the multivariate and the functional median. In Compstat 2010 (Y. Lechevallier and G. Saporta, eds.) 421-428. Heidelberg: Springer.
[6] Cardot, H., Cénac, P. and Monnez, J.M. (2012). A fast and recursive algorithm for clustering large datasets with \(k\)-medians. Comput. Statist. Data Anal. 56 1434-1449. · Zbl 1243.62087
[7] Chaouch, M. and Goga, C. (2010). Design-based estimation for geometric quantiles with application to outlier detection. Comput. Statist. Data Anal. 54 2214-2229. · Zbl 1284.62042
[8] Chaudhuri, P. (1992). Multivariate location estimation using extension of \(R\)-estimates through \(U\)-statistics type approach. Ann. Statist. 20 897-916. · Zbl 0762.62013 · doi:10.1214/aos/1176348662
[9] Chaudhuri, P. (1996). On a geometric notion of quantiles for multivariate data. J. Amer. Statist. Assoc. 91 862-872. · Zbl 0869.62040 · doi:10.2307/2291681
[10] Cuevas, A., Febrero, M. and Fraiman, R. (2007). Robust estimation and classification for functional data via projection-based depth notions. Comput. Statist. 22 481-496. · Zbl 1195.62032 · doi:10.1007/s00180-007-0053-0
[11] Dippon, J. and Walk, H. (2006). The averaged Robbins-Monro method for linear problems in a Banach space. J. Theoret. Probab. 19 166-189. · Zbl 1106.65047 · doi:10.1007/s10959-006-0007-4
[12] Duflo, M. (1997). Random Iterative Models. Applications of Mathematics ( New York ) 34 . Berlin: Springer. Translated from the 1990 French original by Stephen S. Wilson and revised by the author. · Zbl 0868.62069
[13] Fraiman, R. and Muniz, G. (2001). Trimmed means for functional data. Test 10 419-440. · Zbl 1016.62026 · doi:10.1007/BF02595706
[14] Gervini, D. (2008). Robust functional estimation using the median and spherical principal components. Biometrika 95 587-600. · Zbl 1437.62469 · doi:10.1093/biomet/asn031
[15] Gower, J.C. (1974). Algorithm as 78: The mediancentre. J. R. Stat. Soc. Ser. C Appl. Stat. 23 466-470.
[16] Haberman, S.J. (1989). Concavity and estimation. Ann. Statist. 17 1631-1661. · Zbl 0699.62027 · doi:10.1214/aos/1176347385
[17] Haldane, J.B.S. (1948). Note on the median of a multivariate distribution. Biometrika 35 414-417. · Zbl 0032.03601 · doi:10.1093/biomet/35.3-4.414
[18] Huber, P.J. and Ronchetti, E.M. (2009). Robust Statistics , 2nd ed. Wiley Series in Probability and Statistics . Hoboken, NJ: Wiley. · Zbl 1276.62022
[19] Jakubowski, A. (1988). Tightness criteria for random measures with application to the principle of conditioning in Hilbert spaces. Probab. Math. Statist. 9 95-114. · Zbl 0669.60010
[20] Kemperman, J.H.B. (1987). The median of a finite measure on a Banach space. In Statistical Data Analysis Based on the \(L_{ 1 }\)-norm and Related Methods ( Neuchâtel , 1987) 217-230. Amsterdam: North-Holland.
[21] Koltchinskii, V.I. (1997). \(M\)-estimation, convexity and quantiles. Ann. Statist. 25 435-477. · Zbl 0878.62037 · doi:10.1214/aos/1031833659
[22] Kushner, H.J. and Clark, D.S. (1978). Stochastic Approximation Methods for Constrained and Unconstrained Systems. Applied Mathematical Sciences 26 . New York: Springer. · Zbl 0381.60004
[23] Kushner, H.J. and Yin, G.G. (2003). Stochastic Approximation and Recursive Algorithms and Applications , 2nd ed. Applications of Mathematics ( New York ) 35 . New York: Springer. · Zbl 1026.62084
[24] Li, W.V. and Shao, Q.M. (2001). Gaussian processes: Inequalities, small ball probabilities and applications. In Stochastic Processes : Theory and Methods. Handbook of Statist. 19 533-597. Amsterdam: North-Holland. · Zbl 0987.60053 · doi:10.1016/S0169-7161(01)19019-X
[25] Ljung, L., Pflug, G. and Walk, H. (1992). Stochastic Approximation and Optimization of Random Systems. DMV Seminar 17 . Basel: Birkhäuser. · Zbl 0747.62090
[26] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. In Proc. Fifth Berkeley Sympos. Math. Statist. and Probability ( Berkeley , Calif. , 1965 / 66), Vol. I : Statistics 281-297. Berkeley, CA: Univ. California Press. · Zbl 0214.46201
[27] Nazarov, A.I. (2009). Exact \(L_{2}\)-small ball asymptotics of Gaussian processes and the spectrum of boundary-value problems. J. Theoret. Probab. 22 640-665. · Zbl 1187.60025 · doi:10.1007/s10959-008-0173-7
[28] Pelletier, M. (2000). Asymptotic almost sure efficiency of averaged stochastic algorithms. SIAM J. Control Optim. 39 49-72 (electronic). · Zbl 1015.60028 · doi:10.1137/S0363012998308169
[29] Polyak, B.T. and Juditsky, A.B. (1992). Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30 838-855. · Zbl 0762.62022 · doi:10.1137/0330046
[30] R Development Core Team (2010). A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria.
[31] Ruppert, D. (1985). A Newton-Raphson version of the multivariate Robbins-Monro procedure. Ann. Statist. 13 236-245. · Zbl 0571.62072 · doi:10.1214/aos/1176346589
[32] Smale, S. and Yao, Y. (2006). Online learning algorithms. Found. Comput. Math. 6 145-170. · Zbl 1119.68098 · doi:10.1007/s10208-004-0160-z
[33] Small, C.G. (1990). A survey of multidimensional medians. International Statistical Review/Revue Internationale de Statistique 58 263-277.
[34] Vardi, Y. and Zhang, C.H. (2000). The multivariate \(L_{1}\)-median and associated data depth. Proc. Natl. Acad. Sci. USA 97 1423-1426 (electronic). · Zbl 1054.62067 · doi:10.1073/pnas.97.4.1423
[35] Walk, H. (1977). An invariance principle for the Robbins-Monro process in a Hilbert space. Z. Wahrsch. Verw. Gebiete 39 135-150. · Zbl 0342.62060 · doi:10.1007/BF00535182
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.