An Unrestricted Learning Procedure
Shahar Mendelson · Journal of the ACM · 2019
We study learning problems involving arbitrary classes of functions F , underlying measures μ, and targets Y . Because proper learning procedures, i.e., procedures that are only allowed to select functions in F , tend to perform poorly unless the problem satisfies some additional structural property (e.g., that F is convex), we consider unrestricted learning procedures that are free to choose functions outside the given class. We present a new unrestricted procedure whose sample complexity is almost the best that one can hope for and holds for (almost) any problem, including heavy-tailed situations. Moreover, the sample complexity coincides with what one could expect if F were convex, even when F is not. And if F is convex, then the unrestricted procedure turns out to be proper.