Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
This work provides incremental improvements in statistical learning theory by offering tighter bounds for Rademacher averages, which are useful for researchers in machine learning theory and algorithm analysis.
The paper tackles the problem of deriving sharper probabilistic concentration bounds for Monte Carlo Empirical Rademacher Averages (MCERA) by using self-bounding functions, resulting in convergence rates that depend on data-dependent quantities like empirical wimpy variance, which improves upon standard bounded differences methods.
We derive sharper probabilistic concentration bounds for the Monte Carlo Empirical Rademacher Averages (MCERA), which are proved through recent results on the concentration of self-bounding functions. Our novel bounds are characterized by convergence rates that depend on data-dependent characteristic quantities of the set of functions under consideration, such as the empirical wimpy variance, an essential improvement w.r.t. standard bounds based on the methods of bounded differences. For this reason, our new results are applicable to yield sharper bounds to (Local) Rademacher Averages. We also derive improved novel variance-dependent bounds for the special case where only one vector of Rademacher random variables is used to compute the MCERA, through the application of Bousquet's inequality and novel data-dependent bounds to the wimpy variance. Then, we leverage the framework of self-bounding functions to derive novel probabilistic bounds to the supremum deviations, that may be of independent interest.