Learning bounded subsets of L_p

2020/02/04 by Shahar Mendelson, Mendelson, Shahar
Computer Science · Engineering · #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2002.01182

openalex publication_date 2020/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• On the Complexity of Labeled Datasets
• The Sample-Complexity of General Reinforcement Learning
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• On the Complexity of Learning from Label Proportions
• Fine-Grained Distribution-Dependent Learning Curves