2020/10/22 by Leonardo Pellegrina, Pellegrina, Leonardo · 1 citation
Computer Science · Decision Sciences · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Probability (math.PR) #Risk and Portfolio Optimization #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2010.12103
openalex publication_date 2020/10/22 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We derive sharper probabilistic concentration bounds for the Monte Carlo\nEmpirical Rademacher Averages (MCERA), which are proved through recent results\non the concentration of self-bounding functions. Our novel bounds are\ncharacterized by convergence rates that depend on data-dependent characteristic\nquantities of the set of functions under consideration, such as the empirical\nwimpy variance, an essential improvement w.r.t. standard bounds based on the\nmethods of bounded differences. For this reason, our new results are applicable\nto yield sharper bounds to (Local) Rademacher Averages. We also derive improved\nnovel variance-dependent bounds for the special case where only one vector of\nRademacher random variables is used to compute the MCERA, through the\napplication of Bousquet's inequality and novel data-dependent bounds to the\nwimpy variance. Then, we leverage the framework of self-bounding functions to\nderive novel probabilistic bounds to the supremum deviations, that may be of\nindependent interest.\n