Error Bounds of Median-of-Means Estimators with VC-Dimension

Abstract

We obtain the upper error bounds of robust estimators for mean vector, using the median-of-means (MOM) method. The method is designed to handle data with heavy tails and contamination, with only a finite second moment, which is weaker than many others, relying on the VC-dimension rather than the Rademacher complexity to measure statistical complexity. This allows us to implement MOM in covariance estimation, without imposing conditions such as $L$-sub-Gaussian or $L_{4}-L_{2}$ norm equivalence. In particular, we derive a new robust estimator, the MOM version of the half-space depth, along with error bounds for mean estimation in any norm.

Keywords

VC-dimension / Robustness / Median of means / Heavy tails / 62G35 / 62H12

References

[1] Aloupis G. Geometric measures of data depth. DIMACS Ser. Discret. Math. Theoret. Comput. Sci., 2006, 72: 147.

[2] Boucheron, S., Lugosi, G., Bousquet, O.: Concentration inequalities. In: Summer School on Machine Learning, pp. 208–240. Springer (2003)

[3] Brownlees C, Joly E, Lugosi G. Empirical risk minimization for heavy-tailed losses. Ann. Stat., 2015, 43(6): 2507-2536.

[4] Catoni, O., Giulini, I.: Dimension-free pac-Bayesian bounds for matrices, vectors, and linear least squares regression. arXiv preprint arXiv:1712.02747 (2017)

[5] Catoni O. Challenging the empirical mean and empirical variance: a deviation study. Ann. l’IHP Probab. Stat., 2012, 48: 1148-1185

[6] Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’04, pp. 430–436. Society for Industrial and Applied Mathematics, USA (2004)

[7] Chen M, Gao C, Ren Z. Robust covariance and scatter matrix estimation under Huber’s contamination model. Ann. Stat., 2018, 46(5): 1932-1960.

[8] Cheng, Y., Diakonikolas, I., Ge, R.: High-dimensional robust mean estimation in nearly-linear time. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2755–2771. SIAM (2019)

[9] Dalalyan AS, Minasyan A. All-in-one robust estimator of the Gaussian mean. Ann. Stat., 2022, 50(2): 1193-1219.

[10] Depersin J. Robust subgaussian estimation with vc-dimension. Ann. l’Inst. Henri Poincare B Probab. Stat., 2024, 60: 971-989

[11] Depersin J, Lecué G. On the robustness to adversarial corruption and to heavy-tailed data of the Stahel–Donoho median of means. Inf. Inference A J. IMA, 2023, 12(2): 814-850

[12] Devroye L, Lerasle M, Lugosi G, Oliveira RI. Sub-gaussian mean estimators. Ann. Stat., 2016, 44(6): 2695-2725.

[13] Hampel FR, Ronchetti EM, Rousseeuw PJ, Stahel WA. Robust Statistics, 2005. New York, Wiley.

[14] Hopkins SB. Mean estimation with sub-gaussian rates in polynomial time. Ann. Stat., 2020, 48(2): 1193-1213.

[15] Huber P. Robust estimation of a location parameter. Ann. Math. Stat., 1964, 35: 73-101.

[16] Ke Y, Minsker S, Ren Z, Sun Q, Zhou W-X. User-friendly covariance estimation for heavy-tailed distributions. Stat. Sci., 2019, 34(3): 454-471.

[17] Lecué G, Mendelson S. Regularization and the small-ball method ii: complexity dependent error rates. J. Mach. Learn. Res., 2017, 18(1): 5356-5403

[18] Lecué G, Mendelson S. Regularization and the small-ball method i: sparse recovery. Ann. Stat., 2018, 46(2): 611-641.

[19] Lei, Z., Luh, K., Venkat, P., Zhang, F.: A fast spectral algorithm for mean estimation with sub-gaussian rates. In: Proceedings of 33rd Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 125, pp. 2598–2612. PMLR (2020)

[20] Lerasle, M., Oliveira, R.I.: Robust empirical mean estimators. arXiv preprint arXiv:1112.3914 (2011)

[21] Lugosi, G., Mendelson, S.: Multivariate mean estimation with direction-dependent accuracy. arXiv preprint arXiv:2010.11921 (2020)

[22] Lugosi G, Mendelson S. Regularization, sparse recovery, and median-of-means tournaments. Bernoulli, 2019, 25(3): 2075.

[23] Lugosi G, Mendelson S. Mean estimation and regression under heavy-tailed distributions: a survey. Found. Comput. Math., 2019, 19(5): 1145-1190.

[24] Lugosi G, Mendelson S. Sub-gaussian estimators of the mean of a random vector. Ann. Stat., 2019, 47(2): 783-794.

[25] Lugosi G, Mendelson S. Near-optimal mean estimators with respect to general norms. Probab. Theory Relat. Fields, 2019, 175(3–4): 957-973.

[26] Mendelson, S.: An optimal unrestricted learning procedure. arXiv preprint arXiv:1707.05342 (2017)

[27] Mendelson S, Zhivotovskiy N. Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence. Ann. Stat., 2020, 48(3): 1648-1664.

[28] Minsker S. Geometric median and robust estimation in Banach spaces. Bernoulli, 2015, 21(4): 2308.

[29] Minsker S. Sub-gaussian estimators of the mean of a random matrix with heavy-tailed entries. Ann. Stat., 2018, 46(6A): 2871-2903.

[30] Rousseeuw P, Van Driessen K. A Fast Algorithm for the Minimum Covariance Determinant Estimator, 1999. Milwaukee, American Society for Quality Control.

[31] Rousseeuw PJ, Hubert M. Depth in an arrangement of hyperplanes. Discret. Comput. Geom., 1999, 22(2): 167-176.

[32] Rousseeuw PJ, Ruts I. Constructing the bivariate Tukey median. Stat. Sin., 1998, 8(3): 827-839

[33] Sen B. A gentle introduction to empirical process theory and applications. Lect. Notes Columbia Univ., 2018, 11: 28-29

[34] Small CG. A survey of multidimensional medians. Int. Stat. Rev. Rev. Int. Stat., 1990, 58: 263-277.

[35] Tukey, J.W.: Mathematics and the picturing of data. In: Proceedings of the International Congress of Mathematicians, Vancouver, vol. 2, pp. 523–531 (1975)

[36] Van Der Vaart A, Wellner JA. A note on bounds for vc dimensions. Inst. Math. Stat. Collect., 2009, 5: 103.

[37] Vapnik V. The Nature of Statistical Learning Theory, 2013. Cham, Springer

[38] Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)

[39] Wei, X., Minsker, S.: Estimation of the covariance structure of heavy-tailed distributions. In: Advances in Neural Information Processing Systems vol. 30 (2017)

[40] Zwald, L., Blanchard, G.: On the convergence of eigenspaces in kernel principal component analysis. In: Advances in Neural Information Processing Systems, vol. 18, pp. 1649–1656 (2005)

RIGHTS & PERMISSIONS

School of Mathematical Sciences, University of Science and Technology of China and Springer-Verlag GmbH Germany, part of Springer Nature