Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer Export

@unpublished{citeulike:4217285, abstract = {We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result in [3], which relates expectations to sample averages. Second, we show that these structural upper bounds can be loose, compared to other bounds given in [3]. In particular, we demonstrate a class for which the expectation of the empirical minimizer decreases as O(1/n) for sample size n, although the upper bound based on structural properties is Ω(1). Third, we show that this looseness of the bound is inevitable: we present an example that shows that a sharp bound cannot be universally recovered from empirical data.}, author = {Bartlett, P. L. and Mendelson, S. and Philips, P.}, citeulike-article-id = {4217285}, citeulike-linkout-0 = {http://wwwmaths.anu.edu.au/~mendelso/papers/papererm.pdf}, howpublished = {(To Appear)}, journal = {ESAIM Probability and Statistics}, keywords = {bounds, data\_dependent, erm, theory}, posted-at = {2009-03-25 10:40:42}, priority = {3}, title = {Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer}, url = {http://wwwmaths.anu.edu.au/~mendelso/papers/papererm.pdf} }

TY - UNPB ID - citeulike:4217285 L3 - citeulike-article-id:4217285 N2 - We study sample-based estimates of the expectation of the function produced by the empirical minimization algorithm. We investigate the extent to which one can estimate the rate of convergence of the empirical minimizer in a data dependent manner. We establish three main results. First, we provide an algorithm that upper bounds the expectation of the empirical minimizer in a completely data-dependent manner. This bound is based on a structural result in [3], which relates expectations to sample averages. Second, we show that these structural upper bounds can be loose, compared to other bounds given in [3]. In particular, we demonstrate a class for which the expectation of the empirical minimizer decreases as O(1/n) for sample size n, although the upper bound based on structural properties is Ω(1). Third, we show that this looseness of the bound is inevitable: we present an example that shows that a sharp bound cannot be universally recovered from empirical data. JF - ESAIM Probability and Statistics TI - Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer KW - bounds KW - data_dependent KW - erm KW - theory AU - Bartlett, PL AU - Mendelson, S AU - Philips, P UR - http://wwwmaths.anu.edu.au/~mendelso/papers/papererm.pdf ER -