How quickly can a given class of concepts be learned from examples? It is
common to measure the performance of a supervised machine learning algorithm by
plotting its "learning curve", that is, the decay of the error rate as a
function of the number of training examples. However, the classical theoretical
framework for understanding learnability, the PAC model of Vapnik-Chervonenkis
and Valiant, does not explain the behavior of learning curves: the
distribution-free PAC model of learning can only bound the upper envelope of
the learning curves over all possible data distributions. This does not match
the practice of machine learning, where the data source is typically fixed in
any given scenario, while the learner may choose the number of training
examples on the basis of factors such as computational resources and desired
accuracy.
In this paper, we study an alternative learning model that better captures
such practical aspects of machine learning, but still gives rise to a complete
theory of the learnable in the spirit of the PAC model. More precisely, we
consider the problem of universal learning, which aims to understand the
performance of learning algorithms on every data distribution, but without
requiring uniformity over the distribution. The main result of this paper is a
remarkable trichotomy: there are only three possible rates of universal
learning. More precisely, we show that the learning curves of any given concept
class decay either at an exponential, linear, or arbitrarily slow rates.
Moreover, each of these cases is completely characterized by appropriate
combinatorial parameters, and we exhibit optimal learning algorithms that
achieve the best possible rate in each case.
For concreteness, we consider in this paper only the realizable case, though
analogous results are expected to extend to more general learning scenarios.

本文研究了一种更贴近于实际机器学习应用的学习模型，但仍然在学习可能性方面提供了完整的理论，并通过探索万能学习问题的学习曲线发现，每个概念类的学习曲线都以指数、线性或任意缓慢的速率衰减，并提出了最优学习算法来实现每种情况下最佳的可能速率。

普适性学习理论

A Theory of Universal Learning

Linear regression is a classical paradigm in statistics. A new look at it is
provided via the lens of universal learning. In applying universal learning to
linear regression the hypotheses class represents the label $y\in {\cal R}$ as
a linear combination of the feature vector $x^T\theta$ where $x\in {\cal R}^M$,
within a Gaussian error. The Predictive Normalized Maximum Likelihood (pNML)
solution for universal learning of individual data can be expressed
analytically in this case, as well as its associated learnability measure.
Interestingly, the situation where the number of parameters $M$ may even be
larger than the number of training samples $N$ can be examined. As expected, in
this case learnability cannot be attained in every situation; nevertheless, if
the test vector resides mostly in a subspace spanned by the eigenvectors
associated with the large eigenvalues of the empirical correlation matrix of
the training data, linear regression can generalize despite the fact that it
uses an ``over-parametrized'' model. We demonstrate the results with a
simulation of fitting a polynomial to data with a possibly large polynomial
degree.

通过通用学习的角度重新审视线性回归问题，研究了标签 y 和特征向量 x^T 的线性组合表达式及其学习可行性，证明在训练数据的相关矩阵特征向量构成的子空间上，即使参数个数 M 多于样本个数 N，线性回归也可以具有很好的推广性能。

一种新的旧问题视角：线性回归的通用学习方法

A New Look at an Old Problem: A Universal Learning Approach to Linear  Regression

The Predictive Normalized Maximum Likelihood (pNML) scheme has been recently
suggested for universal learning in the individual setting, where both the
training and test samples are individual data. The goal of universal learning
is to compete with a ``genie'' or reference learner that knows the data values,
but is restricted to use a learner from a given model class. The pNML minimizes
the associated regret for any possible value of the unknown label. Furthermore,
its min-max regret can serve as a pointwise measure of learnability for the
specific training and data sample. In this work we examine the pNML and its
associated learnability measure for the Deep Neural Network (DNN) model class.
As shown, the pNML outperforms the commonly used Empirical Risk Minimization
(ERM) approach and provides robustness against adversarial attacks. Together
with its learnability measure it can detect out of distribution test examples,
be tolerant to noisy labels and serve as a confidence measure for the ERM.
Finally, we extend the pNML to a ``twice universal'' solution, that provides
universality for model class selection and generates a learner competing with
the best one from all model classes.

研究了深度神经网络模型类中预测归一化极大似然（pNML）方案及其相关可学习性度量，发现在对抗攻击方面具有鲁棒性，可用于检测样本类别分布不均、噪声标签等情况，且可作为基准学习者竞争的学习器生成 “两次通用” 的解决方案。