  The measure of a machine learning algorithm is the difficulty of the tasks it
can perform, and sufficiently difficult tasks are critical drivers of strong
machine learning models. However, quantifying the generalization difficulty of
machine learning benchmarks has remained challenging. We propose what is to our
knowledge the first model-agnostic measure of the inherent generalization
difficulty of tasks. Our inductive bias complexity measure quantifies the total
information required to generalize well on a task minus the information
provided by the data. It does so by measuring the fractional volume occupied by
hypotheses that generalize on a task given that they fit the training data. It
scales exponentially with the intrinsic dimensionality of the space over which
the model must generalize but only polynomially in resolution per dimension,
showing that tasks which require generalizing over many dimensions are
drastically more difficult than tasks involving more detail in fewer
dimensions. Our measure can be applied to compute and compare supervised
learning, reinforcement learning and meta-learning generalization difficulties
against each other. We show that applied empirically, it formally quantifies
intuitively expected trends, e.g. that in terms of required inductive bias,
MNIST < CIFAR10 < Imagenet and fully observable Markov decision processes
(MDPs) < partially observable MDPs. Further, we show that classification of
complex images < few-shot meta-learning with simple images. Our measure
provides a quantitative metric to guide the construction of more complex tasks
requiring greater inductive bias, and thereby encourages the development of
more sophisticated architectures and learning algorithms with more powerful
generalization capabilities.
