Local Complexities for Empirical Risk Minimization
Abstract
We present sharp bounds on the risk of the empirical minimization algorithm under mild assumptions on the class. We introduce the notion of isomorphic coordinate projections and show that this leads to a sharper error bound than the best previously known. The quantity which governs this bound on the empirical minimizer is the largest fixed point of the function $\xi_{n}(r)=\mathbb{E}{\rm sup}\{|\mathbb{E}f-\mathbb{E}_{n}f|:f\in F,\mathbb{E}f=r\}$ . We prove that this is the best estimate one can obtain using “structural results”, and that it is possible to estimate the error rate from data. We then prove that the bound on the empirical minimization algorithm can be improved further by a direct analysis, and that the correct error rate is the maximizer of ξ ′_ n ( r ) − r , where $\xi'_{n}(r)=\mathbb{E}{\rm sup}\{\mathbb{E}f-\mathbb{E}_{n}f:f\in F,\mathbb{E}f=r\}$ .
Cite
Text
Bartlett et al. "Local Complexities for Empirical Risk Minimization." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_19Markdown
[Bartlett et al. "Local Complexities for Empirical Risk Minimization." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/bartlett2004colt-local/) doi:10.1007/978-3-540-27819-1_19BibTeX
@inproceedings{bartlett2004colt-local,
title = {{Local Complexities for Empirical Risk Minimization}},
author = {Bartlett, Peter L. and Mendelson, Shahar and Philips, Petra},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {270-284},
doi = {10.1007/978-3-540-27819-1_19},
url = {https://mlanthology.org/colt/2004/bartlett2004colt-local/}
}