Learning Bounded Subsets of Lₚ
Shahar Mendelson · IEEE Transactions on Information Theory · 2021
We study learning problems in which the underlying class is a bounded subset of Lpand the target Y belongs to Lp. 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.