Lower Bounds for the Empirical Minimization Algorithm

Date

Authors

Mendelson, Shahar

Publisher

Institute of Electrical and Electronics Engineers (IEEE Inc)

Abstract

In this correspondence, we present a simple argument that proves that under mild geometric assumptions on the class F and the set of target functions Τ, the empirical minimization algorithm cannot yield a uniform error rate that is faster than 1√k in t

Keywords

Keywords: Control theory; Error analysis; Learning systems; Class-f; Empirical minimization; Error Rate; Function learning; Functionals; Lower bounds; Minimization algorithms; Statistical learning theory; Target functions; Learning algorithms Empirical minimization; Function learning; Lower bounds; Statistical learning theory

URI

http://hdl.handle.net/1885/31331

Collections

ANU Research Publications

Source

IEEE Transactions on Information Theory

Type

Journal article

DOI

10.1109/TIT.2008.926323

Restricted until

2037-12-31

Downloads

File

Description

01_Mendelson_Lower_Bounds_for_the_Empirical_2008.pdf (332.03 KB)