Volume 14, 2010
|Page(s)||315 - 337|
|Published online||29 October 2010|
Computer Science Division and Department of Statistics, 367 Evans Hall #3860, University of California, Berkeley, CA, 94720-3860, USA
2 Centre for Mathematics and its Applications (CMA), The Australian National University Canberra, Canberra, ACT, 0200, Australia
3 Department of Mathematics, Technion I.I.T., Haifa, 32000, Israel
4 Friedrich Miescher Laboratory of the Max Planck Society, Tübingen, 72076, Germany
Corresponding author: Corresponding author: firstname.lastname@example.org
Revised: 26 September 2008
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 due to Bartlett and Mendelson, which relates expectations to sample averages. Second, we show that these structural upper bounds can be loose, compared to previous bounds. 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.
Mathematics Subject Classification: 62G08 / 68Q32
Key words: Error bounds; empirical minimization; data-dependent complexity
© EDP Sciences, SMAI, 2010
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.