2018/12/22 by Yaniv Fogel, Meir Feder, Fogel, Yaniv +1
Computer Science · Mathematics · #Anomaly Detection Techniques and Applications #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #cs.IT #cs.LG #math.IT #stat.ML
paper · pdf · doi:10.48550/arxiv.1812.09520
arxiv created 2018/12/22 · openalex publication_date 2018/12/22 · arxiv updated 2018/12/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Universal supervised learning is considered from an information theoretic point of view following the universal prediction approach, see Merhav and Feder (1998). We consider the standard supervised "batch" learning where prediction is done on a test sample once the entire training data is observed, and the individual setting where the features and labels, both in the training and test, are specific individual quantities. The information theoretic approach naturally uses the self-information loss or log-loss. Our results provide universal learning schemes that compete with a "genie" (or reference) that knows the true test label. In particular, it is demonstrated that the main proposed scheme, termed Predictive Normalized Maximum Likelihood (pNML), is a robust learning solution that outperforms the current leading approach based on Empirical Risk Minimization (ERM). Furthermore, the pNML construction provides a pointwise indication for the learnability of the specific test challenge with the given training examples