Lower Bounds for the Empirical Minimization Algorithm
Shahar Mendelson · IEEE Transactions on Information Theory · 2008
In this correspondence, we present a simple argument that proves that under mild geometric assumptions on the classFand the set of target functionsT, 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 fromTthat cause the slow uniform error rate are clearly exhibited.