Optimality of the ERM error bound with upper isometry remainder

At least 2 years old · documented by

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 A≫BA\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.