An optimal unrestricted learning procedure

We study learning problems in the general setup, for 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 is, procedures that are free to choose functions outside the given class $F$. We present a new unrestricted procedure that is optimal in a very strong sense: it attains the best possible accuracy/confidence tradeoff for (almost) any triplet $(F,X,Y)$, including in heavy-tailed problems. Moreover, the tradeoff the procedure attains coincides with what one would expect if $F$ were convex, even when $F$ is not; and when $F$ happens to be convex, the procedure is 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. The notion of optimality we consider is problem specific: our procedure performs with the best accuracy/confidence tradeoff one can hope to achieve for each individual problem. As such, it is a significantly stronger property than the standard `worst-case' notion, in which one considers optimality as the best uniform estimate that holds for a relatively large family of problems. Thanks to the sharp and problem-specific estimates we obtain, classical, worst-case bounds are immediate outcomes of our main result.