A Concentration Inequality for Multiple Means Based on a Polynomial-Time Computable Metric
Resumo
This paper introduces a novel concentration inequality for k empirical means that is independent of k. Unlike previous approaches that rely on NP-hard measures such as VC dimension or Rademacher Averages, we introduce the metric Ka, which is computable in polynomial time. This metric is obtained directly from the sample and represents the number of estimators effectively updated during the sampling process. By adapting uniform convergence proofs from statistical learning theory, we generalize these results to empirical means of real-valued variables without resorting to worst-case sample metrics like VC dimension or pseudodimension. Our approach contributes to the development of more efficient randomized algorithms with robust theoretical guarantees.
Referências
Bartlett, P. L. and Mendelson, S. (2002). Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463–482.
Cousins, C. and Riondato, M. (2020). Sharp uniform convergence bounds through empirical centralization. Advances in Neural Information Processing Systems, 33:15123–15132.
Koltchinskii, V. and Panchenko, D. (2000). Rademacher processes and bounding the risk of function learning. In High dimensional probability II, pages 443–457. Springer.
Linial, N., Mansour, Y., and Rivest, R. L. (1991). Results on learnability and the vapnik-chervonenkis dimension. Information and Computation, 90(1):33–49.
Mitzenmacher, M. and Upfal, E. (2017). Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press.
Pellegrina, L. and Vandin, F. (2023). Silvan: estimating betweenness centralities with progressive sampling and non-uniform rademacher bounds. ACM Transactions on Knowledge Discovery from Data, 18(3):1–55.
Pollard, D. (2012). Convergence of stochastic processes. Springer Science & Business Media.
Preti, G., De Francisci Morales, G., and Riondato, M. (2023). Maniacs: Approximate mining of frequent subgraph patterns through sampling. ACM Transactions on Intelligent Systems and Technology, 14(3):1–29.
Riondato, M. and Vandin, F. (2020). Misosoup: Mining interesting subgroups with sampling and pseudodimension. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1–31.
Vapnik, V. N. and Chervonenkis, A. Y. (2015). On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pages 11–30. Springer.
