Optimality of the ERM error bound with upper isometry remainder

From papers

Let nn be the sample size, let \cF\cF be a function class, and let P\mathbb P be a probability distribution. Write f^n\widehat f_n for the empirical risk minimizer, \cIL(n,P)\cI_L(n,\mathbb P) for the lower isometry remainder, εU2\varepsilon_U^2 for the upper-isometry error, and ε2\varepsilon_*^2 for the benchmark error. The notation ABA\gg B means that AA is asymptotically much larger than BB. Optimality conjecture. The bound of Theorem is optimal in the following way: there exist models (n,\cF,P)(n,\cF,\mathbb P) for which f^n\widehat f_n incurs an error

εU2\cIL(n,P)ε2\varepsilon_U^2 \gg \cI_L(n,\mathbb P) \gtrsim \varepsilon_*^2

or an error

\cIL(n,P)εU2ε2;\cI_L(n,\mathbb P) \gg \varepsilon_U^2 \gg \varepsilon_*^2;

and therefore the bound cannot be improved in general. This concerns the sharpness of the random-design ERM error bound by exhibiting models in which either the upper-isometry contribution or the lower-isometry contribution dominates.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gil Kur, Eli Putterman and Alexander Rakhlin, “On the Variance, Admissibility, and Stability of Empirical Risk Minimization”, arXiv:2305.18508 (2025).

Solutions 0

No solutions have been posted yet.