Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T07:27:15.675Z Has data issue: false hasContentIssue false

On the Optimality of Sample-Based Estimatesof the Expectation of theEmpirical Minimizer* **

Published online by Cambridge University Press:  29 October 2010

Peter L. Bartlett*
Affiliation:
Computer Science Division and Department of Statistics, 367 Evans Hall #3860, University of California, Berkeley, CA, 94720-3860, USA
Shahar Mendelson
Affiliation:
Centre for Mathematics and its Applications (CMA), The Australian National University Canberra, Canberra, ACT, 0200, AustraliaDepartment of Mathematics, Technion I.I.T., Haifa, 32000, Israel
Petra Philips
Affiliation:
Friedrich Miescher Laboratory of the Max Planck Society, Tübingen, 72076, Germany
*
Corresponding author: bartlett@cs.berkeley.edu
Get access

Abstract

We study sample-based estimates of the expectation of the functionproduced by the empirical minimization algorithm. We investigate theextent to which one can estimate the rate of convergence of theempirical minimizer in a data dependent manner. We establish threemain results. First, we provide an algorithm that upper bounds theexpectation of the empirical minimizer in a completelydata-dependent manner. This bound is based on a structural resultdue to Bartlett and Mendelson, which relates expectations to sampleaverages. Second, we show that these structural upper bounds can beloose, compared to previous bounds. In particular, we demonstrate aclass for which the expectation of the empirical minimizer decreasesas O(1/n) for sample size n, although the upper bound based onstructural properties is Ω(1). Third, we show that thislooseness of the bound is inevitable: we present an example thatshows that a sharp bound cannot be universally recovered fromempirical data.

Information

Type
Research Article
Copyright
© EDP Sciences, SMAI, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable