Optimal Sample-Based Estimates of the Expectation of the Empirical Minimizer
Peter L. Bartlett, Shahar Mendelson, Petra Philips · 2005
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