Abstract
We study learning problems in which the underlying class is a bounded subset of L_p and the target Y belongs to L_p. Previously, minimax sample complexity estimates were known under such boundedness assumptions only when p=∞. We present a sharp sample complexity estimate that holds for any p > 4. It is based on a learning procedure that is suited for heavy-tailed problems.