Sharper convergence bounds of Monte Carlo Rademacher Averages through Self-Bounding functions
arXiv:2010.12103
Abstract
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.
References in corpus (7)
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
- Statistical performance of support vector machines
- Rademacher Complexity for Adversarially Robust Generalization
- Fast Rates for General Unbounded Loss Functions: from ERM to Generalized Bayes
- Concentration in unbounded metric spaces and algorithmic stability
- Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
- Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning