Optimality of the ERM error bound with upper isometry remainder
Optimality of the ERM error bound with upper isometry remainder
Let be the sample size, let be a function class, and let be a probability distribution. Write for the empirical risk minimizer, for the lower isometry remainder, for the upper-isometry error, and for the benchmark error. The notation means that is asymptotically much larger than . Optimality conjecture. The bound of Theorem is optimal in the following way: there exist models for which incurs an error
or an error
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
Sign in to submit a solution.
No solutions have been posted yet.