Universal Supervised Learning for Individual Data
This work addresses robust learning for specific individual data points, offering a novel method that is incremental in improving upon existing approaches like ERM.
The paper tackles the problem of universal supervised learning in an individual data setting, proposing the Predictive Normalized Maximum Likelihood (pNML) scheme, which outperforms Empirical Risk Minimization (ERM) by competing with a genie that knows the true test label.
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