Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
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 allow obtaining sharper bounds to (Local) Rademacher Averages. We also derive novel variance-aware bounds for the special case where only one vector of Rademacher random variables is used to compute the MCERA. Then, we leverage the framework of self-bounding functions to derive novel probabilistic bounds to the supremum deviations, that may be of independent interest.
READ FULL TEXT