Rademacher Margin Complexity
Abstract
The Rademacher complexity [1] of a function class F is defined as $R_n(F) = \underset{x_1,...x_n \atop\sigma_1,...\sigma_n}{E} \left[\sup_{f\in F}\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_i f(x_i)\right|\right]$ where σ _1,... σ _ n are iid Rademacher random variables. R _ n ( F ) characterizes the extent to which the functions in F can be best correlated with a Rademacher noise sequence. A number of generalization error bounds have been proposed based on Rademacher complexity [1,2].
Cite
Text
Wang and Feng. "Rademacher Margin Complexity." Annual Conference on Computational Learning Theory, 2007. doi:10.1007/978-3-540-72927-3_44Markdown
[Wang and Feng. "Rademacher Margin Complexity." Annual Conference on Computational Learning Theory, 2007.](https://mlanthology.org/colt/2007/wang2007colt-rademacher/) doi:10.1007/978-3-540-72927-3_44BibTeX
@inproceedings{wang2007colt-rademacher,
title = {{Rademacher Margin Complexity}},
author = {Wang, Liwei and Feng, Jufu},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2007},
pages = {620-621},
doi = {10.1007/978-3-540-72927-3_44},
url = {https://mlanthology.org/colt/2007/wang2007colt-rademacher/}
}