A Concentration Inequality for Multiple Means Based on a Polynomial-Time Computable Metric - Ribeiro, Vinícius M.; Vignatti, André L. (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.23128, 2026)
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 K a , 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.