All common treatment of PAC bounds based on Rademacher complexity assume a bounded loss function (for a self-contained treatemnt, see this handout by Schapire. However, I could not find any result for unbounded losses (with finite moments or possibly subgaussian). The only paper I know of is Cortes et al, but it is about relative bounds, not absolute ones. Does anyone know of a result that explicitly covers Rademacher bounds for general loss functions?
Asked
Active
Viewed 554 times
5
-
This question seems under-specified to me. Bounded loss is assumed so that McDiarmid’s Inequality holds when concentrating the sample risk. Unbounded losses are too hard in the sense that you can use the example from No Free Lunch Theorem to create an unlearnable problem. When you say "finite moments or possibly subgaussian," are you referring to your losses? With those assumptions PAC bounds would be vacuous, no? – VF1 Jan 14 '18 at 20:45
-
I may not know the NFL theorem well enough, but I don't think it applies here. A recent paper of Kontorovich (http://proceedings.mlr.press/v32/kontorovicha14.pdf) extends Rademacher bounds to certain unbounded loss functions. – gappy Jan 15 '18 at 22:58
-
My point was, like in the Kontorovich paper, you'll definitely need some substitute for boundedness, so the question seemed to be asking, "what are the conditions under which we have a McDiarmid-like inequality?" The suggested one, subgaussian losses, seemed vacuous to me, though perhaps like the Kontorovich paper you meant that the input distribution was subgaussian and the loss is smooth. Was my interpretation of what you're asking correct, or are you asking about the general case, to bound arbitrary losses with Rademacher complexity? – VF1 Jan 16 '18 at 02:14
-
The interpretation is correct. One needs additional conditions on the loss function and its tail behavior over the joint distribution of (X, Y) for an analogous result to hold. Kontorovitch's result is a step in that direction. – gappy Jan 17 '18 at 03:57