Learning without Concentration
This work addresses the challenge of heavy-tailed data in statistical learning, offering improved theoretical guarantees for a broad class of problems.
The paper tackles the problem of bounding the performance of Empirical Risk Minimization for convex classes with squared loss, without requiring boundedness or light-tailed assumptions, by using a small-ball method that handles heavy-tailed functions and targets. The results provide sharp estimates that scale correctly with noise and improve known bounds in classical scenarios.
We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used here relies on a `small-ball' assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets. The resulting estimates scale correctly with the `noise level' of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.