Lower Bounds for the Empirical Minimization Algorithm

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 T , the empirical minimization algorithm cannot yield a uniform error rate that is faster than 1/radic (k) in the function learning setup. This result holds for various loss functionals and the target functions from T that cause the slow uniform error rate are clearly exhibited.