An optimal unrestricted learning procedure
This provides a foundational solution for machine learning practitioners dealing with arbitrary or non-convex function classes, offering optimal performance without structural assumptions.
The paper tackles the problem of learning with arbitrary function classes, distributions, and targets by introducing an unrestricted learning procedure that can choose functions outside the given class, achieving optimal sample complexity that matches the best possible even for non-convex classes and heavy-tailed situations.
We study learning problems involving arbitrary classes of functions $F$, distributions $X$ 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 that is optimal in a very strong sense: the required sample complexity is essentially the best one can hope for, and the estimate holds for (almost) any problem, including heavy-tailed situations. Moreover, the sample complexity coincides with the what one would expect if $F$ were convex, even when $F$ is not. And if $F$ is convex, the procedure turns out to be proper. Thus, the unrestricted procedure is actually optimal in both realms, for convex classes as a proper procedure and for arbitrary classes as an unrestricted procedure.