  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.
