Model-agnostic Measure of Generalization Difficulty
Authors: Akhilan Boopathy
Kevin Liu
Jaedong Hwang
Shu Ge
Asaad Mohammedsaleh
Ila R Fiete
Venue: Submitted to ICLR 2023 (2023)
Keywords: generalization
inductive bias
information theory
manifold
complexity

Abstract: 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 task 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.

Under review as a conference paper at ICLR 2023
MODEL-AGNOSTIC MEASURE OF GENERALIZATION DIFFICULTY
Anonymous authors Paper under double-blind review
ABSTRACT
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 learn- ing 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 task minus the information provided by the data. It does 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 polyno- mially 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- letanlla generalization diffi- culties against each other. We show that applied empirically, it formally quantifies intuitively expected trends, e.g. that in terms of required inductive bias, MNIST CIFARIÓ < 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.
INTRODUCTION
Researchers have proposed many benchmarks to train machine learning models and test their general- ization abilities, from ImageNet (Krizhessky et al. 2012) for image recognition to Atari games Belle mare et al. (2013) for reinforcement learning (RL). More complex benchmarks promote the develop- ment of more sophisticated learning algorithms and architectures that can generalize better.
However, lack rigorous and quantitative measures of the generalization difficulty of these bench- marks. Generalizing on task requires both training data and a model's inductive biases, which are any constraints a model class enabling generalization. Inductive biases can be provided by a model designer, including the choice of architecture, learning rule or hyperparameters defining model class. While prior work has quantified the training data needed generalize on task (sample complexity), analysis of the required inductive biases has been limited. Indeed, the concept of inductive bias itself has not been rigorously and quantitatively defined in general learning settings.
In this paper, we develop a novel information-theonn theoretic framework to measure a task's 's inductive bias complexity, the information content of the inductive biases. Just as sample complexity a property inherent to model class (without reference to specific training set), inductive bias complexity is property inherent to a training set (without reference to a specific model class). To our knowledge, our measure is the first quantification of inductive bias complexity. As we will describe, our measure quantifies the fraction of the entire hypothesis space that is consistent with inductive biases for a task given that hypotheses interpolate the training data; Fig [ for an illustration and Definition D for formal definition. We use this inductive bias complexity measure as a measure of the generalization difficulty; hope measure guide the development of tasks requiring greater inductive bias.

---

Under review as a conference paper at ICLR 2023
Nighammppe
hypotherk space
inductive bus complhdty
ger tarbon
Mugha Rudaaa
XXX
-kg
Seinduathee
1000
lonolingle camplendty
genterlliee
Figure 1: Dividing the hypothesis space of a task. (a) plots the trade-off between the amount of training data required (sample complexity) vs. the amount of inductive bias required (inductive bias complexity) to generalize well. Achieving a lower sample complexity for fixed generalization performance target requires higher inductive bias complexity further restrict the hypothesis space. While many papers have quantified sample complexity, we quantify inductive bias complexity. (b) categorizes hypotheses by whether or not they fit the training data or contain particular inductive biases. Both training data and inductive biases are required to generalize well. (c) shows how inductive bias complexity is computed: we quantify inductive bias complexity as negative log the fraction of hypotheses that generalize well among the hypotheses that fit the training data.
As one concrete, but applicaapl suggestion, we find that adding Gaussian noise to the inputs of task can dramatically increase its required inductive bias. We summarize our contributions as
We propose feature-based task framework to analyze generalization difficulty in various learning problems, including supervised learning, RL and meta-learning.
We provide a formal, information-theoreti definition of inductive bias complexity.
We develop a novel and to our knowledge first quantifiable measure of inductive bias complexity, which propose using measure of the generalization difficulty of task. This measure also allows us to quantify the relative inductive biases of different model architectures applied to task.
We propose a practical algorithm to estimate and compare the inductive bias complexities of tasks across the domains of supervised learning. RL and few-shot meta-learning tasks. Empirically, we find that 1) partially observed RL environments require much greater inductive bias compared to fully observed ones and 2) simple few-shot meta-learning tasks can require much greater inductive bias than complex, realistic supervised learning tasks.
2 RELATED WORK
2.1 MODEL ORIENTED GENERALIZATION DIFFICULTY
The generalizability of machine learning models is traditionally quantified with learning curves, which relate the generalization
on task amount of training data (i.e. sample complexity) (Cortes)
eet al., 1994; Murata et al. 1992 Amari 1993. Hestness et al. 2017). Generalization error can be bounded by model class capacity measures, including Rademacher complexity (Koltchinskii & Panchenko 2000) and VC dimension (Blumer et al. 1989), with simpler model classes achieving lower generalization error. While valuable, these measures often provide only loose, non-specific generalization bounds on particular tasks because they typically do not leverage task's 's structure.
More recently proposed delendent generalization bounds yield tighter bounds on generalization emoor (Negrea al., 2019 RRginsky et al., [2016] Kawaguchi et al. 2022 Lei et al. [003)] Jiang et al.
2021
These measure leverage the properties of a dataset show that particular model classes will generalize well on the dataset. Relatedly, recent work neural network scaling laws (Bahri et al.
2021 Hutter 2
Sharma & Kaplan 2022) has modeled learning as kernel regression to show
An anonymized version of our code can he found at: https::/anonymouu 4open. scí ince/r///
task Pask-diffe
disk-difficuly---oo
2

---

Under review as a conference paper at ICLR 2023
among other results that sample complexity scales exponentially with the intrinsic dimensionality of data. Our approach is aligned in spirit to this line of work; however, instead of leveraging the structure of task to bound generalization error or sample complexity, instead bound the inductive bias complexity of a task; see Figure[] We helieve inductive bias complexity is a more appropriate measure of task's difficulty compared to sample complexity. Notably, sample complexity assumes specific model class; it is not model-agnostic. Thus, sample complexity only quantifies the contribution of training data towards solving a task given a particular model class; does not quantity the difficulty of choosing an appropriate model class (e.g. a model architecture).
2.2 INFORMATION THERRETIC MEASURES OF GENERALIZATION DIFFICULTY
Recent works have analyzed the properties of neural networks using information theory; for instance, information bottleneck can be used to extract well generalizing data representations (Shwartz-Ziv & Tishby 2017: Saxe et al. 2019 Shamir et al. 2008). DIME (Zhang et al.) 2020) uses information theory to estimate task difficulty, bounding the best case error rate achievable by any model dataset given the underlying data distribution. Achille et al. (202T) defines task difficulty based on the Kolmogorov complexity required to model the relationship between inputs and outputs. Although these measures can be related to generalization. they do not directly quantify the information needed to generalize. A Alternatively, generalization difficulty can be expressed the amount of information required to perform a task in addition to any training data provided to a learning system (Chollet 2019). This aligns with other literature assessing the prior knowledge contained in a learning system whether through specific abilities (Hernáádez-Orallo) (2116), biases (Haussler) 1988), or model architectures (Du et al.] 2018 Li et al.) 2021). In this work, we take a similar approach, defining generalization difficulty as the amount of information in inductive biases required on top of training data in order to solve a task within the hypothesis space.
FEATURE- -BASED TASK FRAMEWORK
It is well known that generalization from limited data can be viewed in a mathematically unified way for many learning problems including regression, clas- sification and unsupervised learning (Vapnik) 1999). To analyze the generalization difficulty of many learn- ing problems using common notation, we provide a unified notational framework that explicitly reveals the dimensions along which a learning system needs to generalize. Tab summarizes our notation.
Table 1:
Table of symbols.
Symbol ((
Meaning
Function from hypothesis space, paramctenzeed by
P
Inpot distribution, denotes the test distribution Input distritation, denotes the training distrihution Emor of f(:00) on inpur distributian Lass function
Event that hypothesis Event that the hypothesis fits inductive biases Desired test erroe
training dataset
K
Inductivv blas camplexity Set of hypotheses that the training dataset Lipschitz constant for C Le
Constant used in second-urder condition Intrinsic dinxnniomiily of data Number suhmunifolds
3.1 SETUP AND NOTATION
Radius of the sphere on which datopoints lie Dinensiceality of the model outpul fon single component of
We define task consisting of instances x and actions y, a learning system aims to learn a map- ping from instances to actions. We assume that each instance x is described by a set of features: x has K, continuous features C1. C2 ...Ck, and K2 discrete features d1, d2.-..dk. Finally, we assume that the features uniquely describe all possible points x: there exists invertible function A such that:
d
Upper bound If #)1l Size of training dazaset
n.
M
Maximum frequency of eigenfunctions considered
Sputial resolution of equal 2nr
K.
Maximum integer satisfying / /KQK + 1f M # of eigenfunctions with froquency M; O(A)))
R
di, dk..))
for all possible values of z and the features on their respective manifolds. Note that such decom- position of & always exists by using a single feature ei = x or d1 = xx; tasks with a more complex structure may have instances with further decomposition reflecting the task structure.
We assume that for each instance x, there is a unique desired action y E y among the set of possible actions )) the optimal mapping is denoted by y (z). In general, learning the exact mapping f* may be intractable. Instead, it may be feasible to closely match the function f" within some error. Given loss function L. we define the error of function f under particular distribution p over as:
é(S p) (x)()(()))))))
(2)
3

---

we further Under review as a conference paper at ICLR 2023
3.2 MAPPING THE FRAMEWORK TO DIVERSE LEARNING SETTINGS
Although the task framework above used notation that resembled supervised learning, our framework incorporates many different learning scenarios including unsupervised, reinforcement and meta learning. We summarize the notational mapping between our framework and various learning scenarios in Tab 6 Further details of this mapping are given in App
Our framework reveals the dimensions along which a task requires generalization. We use this in Section 4 where we quantify the difficulty of generalizing on a task. However, our framework may conceal aspects of a task relevant to other notions of difficulty. For instance, in online RL, we do not capture the policy-dependence of the training data; thus, exploitation trade-off. However, our framework captures exactly the generalization-rell releevan aspects of task: in RL, for instance, generalization can be viewed in much the same way as supervised learning, except with different policies inducing different distributions during training and testing (Kakade 2003). Importantly, in our analysis, we do not require that training and testing must be done on the same distribution (see Section 4.2): thus, we believe our framework applies to studying generalization in situations like online RL and beyond where the training and test distributions may be quite different.
cannot quantify the exploration-
MEASURING INFORMATION CONTENT OF INDUCTIVE BIASES
It is well known by the No Free Lunch theorem (Wolpert 1996) that learning algorithm can perform well on any task; only learning algorithms that possess appropriate inductive biases relevant to a particular task(s) can be expected to generalize well given a finite amount of data. Thus, generalizing on a task requires both training data and inductive biases (i.e. a choice of model class) (see [.. In Section [ we formally define inductive bias complexity as the amount of inductive bias required to generalize. In Section 4.2, we exactly bound this quantity in terms of the desired error rate of a task and distance between training and test distributions. In Section 4.3 approximate the bound to produce a practically computable estimate.
4.1 FORMALLY DEFINING INDUCTIVE BIAS COMPLEXITY
We formally relate inductive biases and generalization using the concept of a hypothesis space. Hypotheses may or may not satisfy a training set or a set of inductive biases (see Fig [ (b)); generalization fundamentally requires both inductive biases and training data to specify a set of well-generalizing hypotheses. Note that there is a trade-off between the amount of training data and inductive bias required to generalize (see Fig ! (a)). We aim to quantify the level of inductive bias required for generalization given a fixed amount of training data. We call this measure the inductive bias complexity (see Fig] T (c)). Just as sample complexity quantifies the amount of training data required to generalize given a fixed inductive bias (i.e. fixed model class), inductive bias complexity measures the amount of inductive bias required given a fixed amount of training data.
We begin by defining a (very broad and general) hypothesis space, consisting of functions f(x; 0) parameterized by a vector 0. The hypothesis space is not the same as the model class (e.g. neural net- works) used solve a task. Instead, the hypothesis space ideally massive space that encompasses all possible model classes that might reasonably be used to solve a task. We view the hypothesis space constructed here simply as mathematical tool analyze the properties of the task itself rather than relating to the actual models trained on task. We use a Bayesian framework, assuming that f drawn from some distribution and that the prior distribution of is uniform (which can generally be made to hold by reparameterizinng. We assume that the true (target) function to be learned is expressible within this large hypothesis space, and we define to be given by (*xx) = [xx; 0*) Thee generalization error of specific 0 and input distribution p is denoted e(0. p) (=; p). We aim to find a hypothesis achieving generalization error below a threshold e: e(0. p) S s. The training data and inductive biases both provide constraints the hypothesis space; we wish quantify how much the inductive biases need to constrain the space to yield a well-generalizing set of hypotheses.
Intuitively, the inductive bias required to achieve particular error rate is related to additional information required by the inductive biases beyond any telk-aelevant information provided by training data. Specifically, inductive bias complexity can be viewed as the additional information
4

---

Under review as a conference paper at ICLR 2023
required to specify the gell-eenera hypotheses given the of hypotheses that fit the training data. Thus, we formally define inductive bias complexity I as follows:
Definition 1. Suppose a probability distribution is defined over a set of hypotheses, and let random variable 0 correspond to a sample from this distribution. Given an error threshold e which models are optimized to reach on the training set, the inductive bias complexity required to achieve error rate e is on task
7- P(c(O. S c(0,g) SC
Observe that this is exactly the information content of the probabilistic event that a hypothesis that fits the training set also generalizes well. For case of analysis, we define "fitting" the training set as perfectly interpolating it (setting = 0). A well-generalizing hypothesis, achieving a low but non-zero error rate, might not interpolate the training set. Nevertheless, the regime of perfect interpolation can be relevant for training overparameterized deep networks; we leave other regimes as future work and briefly outline how to extend these regimes in App G
4.2 AN EXACT UPPER BOUND ON INDUCTIVE BIAS COMPLEXITY
We are able to provide an exact upper bound on the inductive bias complexity given above, under some technical assumptions. These assumptions may not hold in all settings; nevertheless, we believe they hold in many common settings (e.g. when the loss function is a square loss and the model f' is twice differentiable with bounded inputs and parameters); App C discusses the validity of these assumptions. Assume that the imput, parameter, and output spaces equipped with standard distance metrics d(:,)) and norms || ||. Let p denote the test distribution, g denote the training distribution, and W(, denote the 1- W-Wasserttein distance. Additionally define O {0 e(0, 0) to be the set of hypotheses that perfectly interpolate the training dataset.
Theorem 1. Suppose that the loss function satisfies C(y, x)) 2 O, and equality holds if and only if y (x). Suppose that the loss function is invariant to shifts in in the sense that Lly + (x2) (x(2)), = L(y, 1 for all y, F1, x2. We also has a Lipschitz constant Lg:
Lly 8, L(y. x) S L2|lo|1
(4)
for all y, 8, x. We also assume a second-order condition on f for some constant Ly:
11( 01) f(11; 02) f 01) f(z 02) S xx)((1, 62)
(5)
for all X2, 01, 11,02 O2 Then we have the following upper bound on the inductive hias complexity:
is log ((0,0') S LeL, 10
(6)
The bound depends on the following key quantities: desired error rate interpolating hypothesis space O2 and W-Wasserstein distance between the training and test distributions W(p, q). See App B for proof. Observe that the proof is quite general: it does not rely any specific assumptions on
the hypothesis space, nor does it assume any relationship between the test and training distributions.
4.3 EMPIRICAL INDUCTIVE BIAS COMPLEXITY APPROXIMATION
We now apply a series of approximations on the general bound of Theorem I to achieve practically computable estimate. We present this approximation in the setting of supervised classification, but note that it can be applied other settings on our empirical computation). As we propose the first measure of inductive bias complexity, our focus is on capturing general trends (scalings) rather than producing precise estimates. We hope future work may further refine these estimates or further relax our assumptions.
show in our experiments (see App for full details
Supervised Classification Setting We assume data points x lie on non-overlapping m-spheres of radius r. where each sphere corresponds to class. Furthermore, assume that the test distribution p is uniform over all the m-spheres and the training distribution q is the empirical distribution of n points drawn i..dd from p. This approximation captures key characteristics of data distributions in actual classification tasks: 1) bounded domain, 2) similar density over all points, 3) non-overlapping distributions for different classes. We assume the dimensionality of f(x;;) is d, the number of
5

---

Under review as a conference paper at ICLR 2023
classes. Let 6 be constant such that [x; 0)] I b for all z, 8. Let ö be the "spatial resolution" of f. defined such that perturbing the input x by amounts less than ó does not significantly change the output f(;; 0) (i.e. ö is the minimum change that is sensitive to). In our case of supervised classification, 8 corresponds to the distance between classes.
Parametrization of Hypotheses In order to compute Equation 6 we must make a specific choice of parameterization for (() Recall from Section that we wish to select a broad and general hypothesis space encompassing all model classes practically applicable may not want to consider include functions which are sensitive to changes on x below the task relevant resolution 0. Thus, consider only bandlimited functions with frequencies less than M 2
task. Hypotheses that
More formally. to construct a basis of functions below a certain frequency on a sphere, we use the approach in McRae et al. (2020), which parameterises functions linear combination of cigenfunctions of the Sapllace-ellrami operator on the manifold. The Haplace-Beltrann operator is a generalization of the Laplacian to general manifolds; eigenfunctions of this operator are analogous to Fourier basis functions in Euclidean space. See Fig O for visualization in the Euclidean case.
For each nonnegative integer k. the Laplace- Laplace-Beltrami operator on the m-sphere has (" (m=+h + eigenfunctions with frequency v /k(k integer k such that / /kk + m - 1] I M, there are m k m
1) (Dai & Xu 2013). Taking K to be the maximum
m k 2
m (
m K
m
m
m
k=
eigenfunctions with frequency most M. Note that for large M, E scales as O(M") since K scales as M. Since each coefficient has a real and imaginary part, the dimensionality of the parameterization of single component fx is 2E. There are d components each of submanifolds, so the dimensionality of the full parameterization 0 is 2d Fach training point constrains the dimensionality of the possible values of ( by d. Therefore, the dimensionality of O, is 2d E nd. Next, we obtain a bound on ||@] If the parameters a component fa are fg. Parseval's identity (Stein & Shakarchi 2011 l) states that ||0x equals the average value of fl 0x) which bounded by b2. Since there are de components, we have ||0|| < bd.
Next, approximate the volume of Og we must make an assumption on the shape of O,- Given that we have bound on 0, simply approximate O, as disk of dimensionality 2d F. nd and radius bd; note that the disk is embedded in 2d E dimensional space. This disk approximation retains key properties of interpolating manifolds (low-dimensionaltty and boundedness) while being analytically tractable; see App C.3 for further discussion.
The set (o E O, d(0,0") S LEL,W is disc with radius Leb, (p.q) Therefore,
2d E-d
(d(880)) LeL, IBEO)) =
Le Ly (p.o)
(8)
bd
To arrive at this approximation, we set the hypothesis space linear combination of eigenfunctions of the Saplace-Beltrane operator on the manifold, and then approximated volumes in the hypothesis space as balls. Since we do not make specific assumptions on the manifold of x to construct our hypothesis space, we expect the overall scaling of our result to hold for general tasks.
Approximating Wasserstein Distance We obtain a simple scaling result for the Wasserstein distance W ((P g). the expected transport distance in the optimal transport between p and q. In the optimal transport plan, each training point is associated with a local region of the sphere; the plan moves probability density between each point and the local region around each point. These regions must be equally sized, disjoint, and tile the entire sphere. Although the regions' shapes depend on the specific distribution q, if q is near uniform, we expect these regions to be similarly shaped.
We approximate these regions as hypercubes because they are the simplest shape capable of tiling m-dimensional space. In order to fill the full area of the sphere, the hypercubes must have side length
2n (m 11/2
1/m
2nT (m
1/m
m
rn 1/m
(9)
T

---

Under review as a conference paper at ICLR 2023
The expected distance between two randomly chosen points in hypercube is at most sy m/6 (Anderssen et al., 1976). We use this distance as an approximation of the optimal transport distance between each point and its associated local hypercube. The final W (pp.g) q) can then simply be approximated as the optimal transport distance corresponding to each point:
1/m
m amm
2n (m 1)/2
W(p. 9) 8
mn 1/m V
(10)
r
m++1
2
In Apple C.4 we empirically compute Wasserstein distances on sphere and find that the distances follow this approximation. Although this particular approximation is valid when the empirical training distribution q is drawn i.i.d. from uniform underlying data distribution p. our framework can be applied to non-i.i.d. settings by simply modifying our Wasserstein distance approximation to reflect the train-test distributional shift.
Final Approximation Since f is a linear combination of basis functions with coefficients 0, L upper bounds the norm of the gradient the basis functions, A basis function with a single output and frequency / /ki(k + m - 1) has a gradient with magnitude at most k/r. Since f's output has dimensionality d, we can take I, K Kvd/ r. Substituting the result of Equation along with our approximation for W(p,)) q) into Equation 6 gives approximated inductive bias complexity of
3 I (2d nd) loogb + log d + log K log log E
1
+ loge). LL
(11)
2
1/m
where V 2n (m+11/2 T( m+]1
which is roughly constant for large intrinsic dimensionality m.
Recall that is the number of classes, n is the number of training data points, é is the target error, Le the Lipschitz constant the loss function, b a bound on the model output, and K and functions of m and the maximum frequency M = 2Tr/5.
Properties of Inductive Bias Complexity The dominant term in our expression, Equation I1 for inductive bias complexity is 2d E E-nd. Since E E O(M"), inductive bias complexity is exponential in the data's s intrinsic dimensionality m (see A for further intuition). Additionally, M = 2 /5, so for fixed m, inductive bias complexity is polynomial in 1/6. Thus, 8 impacts inductive bias complexity less than m, but can still be significant for large m. Inductive bias complexity increases roughly linearly in Z and D, these values have less impact than and 5. Inductive bias complexity decreases roughly linearly with the number of training points n; intuitively, this is because each training point provides a roughly equal amount of information. Finally, inductive bias complexity increases logarithmically as the desired error ε decreases. Intuitively, the inductive bias complexity depends on the desired performance level: achieving the performance of random classifier on classification task is trivial, for example.
5 EMPIRICAL GENERALIZATION DIFFICULTY OF BENCHMARKS
Here, we use our quantification of inductive bias complexity as a measure of the generalization difficulty of task (or task difficulty). Inductive bias complexity corresponds the effort that a model designer must apply to generalize on task, while sample complexity corresponds to the contribution of the training data; thus, inductive bias complexity is an appropriate measure of the generalization difficulty of task from model designer's perspective. We empirically validate our measure on several supervised classification, meta-learning, and RL tasks. We also quantify the relative inductive biases of different model architectures on different tasks and empirically show task difficulty trends over parametric task variations.
Computing the difficulty/ i of Equation| 11 for specific tasks specifying several parameters. The target generalization error is fixed at level based on the type of the task (see D the data dimensionality m by relating the decay rate of nearest neighbor distances in the training set to intrinsic dimensionality (Pope al. 20221). The required detail (resolution) per dimension is set to the inter-class margin for classification tasks and a scale at which state perturbations do not significantly affect trajectories for RL tasks. See App for full details.
Tab 3). We estimate
7

---

Under review as a conference paper at ICLR 2023
5.1 TASK DIFFICULTY OF STANDARD BENCHMARKS
Image classification We estimate the task difficulty of the commonly used image classification benchmarks MNIST, SVHN (Netzer al. 201T), CIFARIO (Krizhevsky et al., 2009). and Ima- geNet (Deng et al. 2009). As shown in Fig models solving these tasks encode large amounts of inductive bias, with more complex tasks requiring models with more inductive bias.
Few-shot learning We estimate the task difficulty of 1- shot, 20-way classification on Omniglot (Lake et al., 2015).
The model must learn function f mapping dataset of 20 images from an alphabet to a classifier g. which itself maps an image to probability distribution over 20 classes. Both
Task Difficuity (bits)
10
20
10
the inputs and outputs of f have much larger dimensionality than for typical image classification. This yields very large task difficulties: Omniglot has task difficulty = 10 bits (vs. 10 for ImageNet); see Fig 2
10a
10as
MNIST
SVHN
CIFARIO
ImageNet
Reacher
Hopper
Half- Cheetan
Omniggia
RL We find the task difficulty of the Reacher, Hopper, and Half-Cheetall control tasks in MuloCo (Todorov et al.] 2012 Duan et al. 2016). F that more complex en- vironments with higher dimensional observation and action spaces have higher task difficulties intuitively expected. Moreover, the range of task difficulties is comparable with image classification: task difficulties are comparable across domains.
Figure Task difficulties of various benchmark tasks across domains.
5.2 INDUCTIVE BIAS CONTRIBUTED BY DIFFERENT MODELS TO VARIOUS TASKS
Although our task difficulty measure is model-agnostic, we can bias different models contribute to various tasks. To do this, we find the test set performance of a trained model from the model class (e.g. test set accuracy for classification tasks). We then use this performance level to compute in the task difficulty expression in Eguation not directly use the test set data). This method is motivated by the idea that model class enables generalization by providing an inductive bias, and its generalization ability can be quantified using test set performance. Thus, we quantify model class's inductive bias as the minimum inductive bias required to achieve the performance of the model class: greater performance requires greater inductive bias. As observed in Tab (see Tab 7 for full results), the increase information content resulting from using better model architecture (such switching from ResNets (He et al. (016) to Vision Transformers (Dosovitskiy et al.) 2021)) ) is generally larger for more complex tasks. In other words, more complex tasks extract more of the inductive bias information present in model.
compare how much inductive
(importantly, we do
Table 2: The inductive bias information contributed by different model architectures for image classification tasks. (FC-N refers to fully connected network with N layers.)
CIFARIO
ImageNet
Mod:l
Inforatation
Model
Information
Content 1x 10 bis)
Content Ox10" bas)
Nishimtee
2,250
Karpatyy 2012
2.00
AlexNer Kapllenk
2,700
AlecNet Knnren Pay
2.200
ResNet-iin Wicemme
3.105
Ron (ee af Aup
2,307
B (K0 minker stmn 2020
W.451
BIT
Kole e 2020
2.11
[VT Doseviskay coll 021
3,513
VIT-8214
Unsombskyy 2011
2,401
5.3 TRENDS OF TASK DIFFICULTY
In this section, we consider how task difficulty changes as we parametrically vary aspects of task. Please see App F for additional task variations.
Varying training data We vary the amount of training data provided in ImageNet and find Fig Ba that the task difficulty decreases with more training points. Observe that when training data is increased by many orders of magnitude, the scale of task difficulty remains large, suggesting that training data provides relatively little information solve task relative inductive biases. Intuitively,
8

---

Under review as a conference paper at ICLR 2023
this is because in the absence of strong inductive biases, training data only provides information about the approximated function in a local neighborhood around each training point; inductive biases, by contrast, can provide global constraints the function. See G for further discussion.
1c41
1e25
Varying desired error rate In Fig [bb] we vary the de-
Task Diffcultty (Bits)
3.60
Tosk Dificuity (bits)
3.55
sired error on the Reacher task
3.50
and find that task difficulty de- creases with desired error rate as expected. As with vary- ing training data, the scale of task difficulty remains large even when dramatically reduc- ing the desired error rate.
3.45
105
10'
1015
1047
10-7
10-5
10-3
10-1
Number Samples
Desired Error Rate
(a) Varying training data on ImageNet
(b) Varying desired error
on Reacher
1040
Taik Dificitty (bits)
10:4.
10
Varying intrinsic dimension We consider a noisy version
1032
1ga0.
10a7
1024.
of Cartpole (Florian 2007),
1070
10%
10
an inverted pendulum control task where agents apply binary forces to control a pole. In noisy Cartpole, the agent ob- serves a noisy version of the pole's angular position and ve- locity, requiring possibly mul- tiple observations find the optimal action. The agent must learn function with a higher-dimensional input, making the task more difficult. As Fig showss. task difficulty exponential in the number of observations needed to find the optimal action. We also increase the intrinsic dimensionality of ImageNet classification by adding perturbations
10
10a
3 Number of Observations
80 Intrinsic Dimensions
60
100
(c) Varying intrinsic dim Caripole
(d) Varying intrinsic dim ImageNet
Figure 3: Task difficulties variations of benchmark tasks.
the images outside the original image manifold; creating classifiers robust to such perturbations is known theoretically and empirically to be difficult (Madry et al.) [201]] Yin iet al. 2019). Fig [d shows that task difficulty drastically increases with added intrinsic dimensions. Thus, increasing the intrinsic dimension of a task is powerful way of increasing its difficulty.
6 DISCUSSION
For all tasks, inductive bias complexities are quite large, much larger than practical model sizes. This due to the vast size of the hypothesis space constructed in Section 4.3; it includes any bandlimited function below a certain frequency threshold. Specifying a well-generalizing subset in such a massive hypothesis space requires massive amounts of information. See App G for further discussion.
Our measure reveals that tasks with inputs on higher dimensional manifolds require far more inductive bias relative other variations of tasks. This yields counter-intuitive findings: meta-learning on simple Omniglot handwritten characters requires far more inductive bias than than classification of complex, realistic ImageNet images. These findings suggest that construct tasks requiring high inductive bias, prioritizing generalization over many degrees of variation is more important than increasing the richness of the task within each dimension of variation. Good benchmarks would require generalization over high dimensional spaces, but, like Omniglot, may appear simple. Examples of such benchmarks include fho- learning, adversarially robust image classification, and MDPs with very limited observations. Our measure provides quantitative guide to designing such benchmarks. As a specific, but -ppadly- example of increasing the number dimensions of variation, suggest adding Gaussian noise to task inputs.
To our knowledge, we provide the first measure of inductive bias complexity; thus, is not designed to be quantitatively precise. We hope future work may be able to further refine estimates. Never- theless, we hope our measure may encourage the development tasks requiring gellraenera architectures and learning rules with many built-in inductive biases.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alessandro Achille, Giovanni Paolini, Glen Mbeng, and Stefano Soatto. The information complexity of learning tasks, their structure and their distance. Information and Inference: A Journal of the IMA, 10(1):51-72, 2021.
Shunichi Amari. A universal theorem on learning curves. Neural Networks, 6(2):161-166, 1993. ISSN 0893-6080. doi:
Sanghyeon An, Minjun Lee, Sanglee Park, Heerin Yang, and Jungmin So. An ensemble simple convolutional neural network models for mnist digit recognition. arXiv preprint ar arXiv:2008. 10400, 2020.
R. S. Anderssen, R. P. Brent, D. J. Daley, and P. A. Moran. -.....So (1î (
Concerning
... ..... x 1/2 dr -.... dr and a Taylor series method. SIAM Journal on Applied Mathematics, 30(1)222-30, 1976. doi: 10. 10.1137/0130003
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.067000 2021.
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling, The arcade learning environment: An evaluation platform for general agents, JAIR, 47:253-279, Jun 2013. doi: 1/.ai333/air..112.
Anselm Blumer, A. Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the vapmik-chervonenkis dimension. ACM, (6(4):929-996 oct 1989. doi: 10. 10.1 10.1777763397767771
François Chollet. On the measure of intelligence. arXiv preprint, 2019.
Dan Ciregan, Ueli Meier, and Jürgen Schmidhuber. Multi-column deep neural networks for image classification. In CVPR, 2012.
Corinna Cortes, L. D. Jackel, Sara Solla, Vladimir Vapnik, and John Denker. Learning curves: Asymptotic values and rate of convergence. In NeurIPS, 1994.
Feng Dai and Yuan Xu. Approximation theory and harmonic analysis spheres and balls, volume 23. Springer, 2013.
A. L. M. Dekkers, J. H. J. Einmahl, and L. De Haan. A moment estimator for the index of an extreme-value distribution. The Annals of Statistics, 1989.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, (46)):41-144 2012.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image worth 16x 16 words: Transformers for image recognition scale. ICLR, 2021.
Simon S. Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Aarti Singh. How many samples are needed estimate a convolutional recurrent neural network? NeurlPS, 2018.
Yan Duan, Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In ICML,, 2016.
Razvan V Florian. Correct equations for the dynamics of the cart-pole system. Center for Cognitive and Neural Studies (Coneural), Romania, 2007.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
10

---

Under review as a conference paper at ICLR 2023
Ian J Goodfellow, Yaroslav Bulatov, Julian Ibarz, Sacha Arnoud, and Vinay Shet. Multi-digit number recognition from street view imagery using deep convolutional neural networks. arXiv preprint arXiv:1312.6082, 2013.
David Haussler. Quantifying inductive bias: Ai learning algorithms and valiant's learning framework. Artificial Intelligence, 36(2):177-221, 1988.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
José Hemández--Oralo. Evaluation in artificial intelligence: from task-oriented to ability-orientel measurement. Artificial Intelligence Review, Aug 2016.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md. Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Marcus Hutter. Learning curve theory. arXiv preprint arXiv:2102.04077 2021.
Yiding Jiang, Parth Natekar, Manik Sharma, Sumukh K Aithal, Dhruva Kashyap, Natarajan Subra- manyam, Carlos Lassance, Daniel M Roy, Gintare Karolina Dziugaite, Suriya Gunasekar, et al. Methods and analysis of the first competition in predicting generalization of deep learning. In NeurIPS 2020 Competition and Demonstration Track, 2021.
Sham Machandranath Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
Andrej Karpathy. Breaking linear classifiers on imagenet. Andrej Karpathy blog. 2015.
Kenji Kawaguchi, Zhun Deng, Kyle Luh, and Jiaoyang Huang. Robustness implies generalization via data-dependent generalization bounds. In ICML, 2022.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. ICLR, 2017.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (BiT): General visual representation learning. In ECCV, 2020.
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. High Dimensional Probability II, pp. 443 2000. doi: 10.1007
978-1-4612-1358-11
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 and cifar- 100 datasets. 2009. URL toronto.oooooooooo..
hittps://ww... wttp::/w..s...ooo.oo.oo
//ci///aar..///////// html
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In NeurIPS, 2012.
B. Lake, R. Salakhutdinov, and J. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350:1332- 1338, 2015.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2322 1998. doi: 10. 10.7799...77691.
Chen-Yu Yu Lee, Saining Xie, Patrick Gallagher, Zhengyou Zhang, and Zhuowen Tu. Deeply-supervised nets. In AISTATS, 2015.
Yunwen Lei, Urun Dogan, Alexander Binder, and Marius Kloft. Multi-class svms: From tighter data-dependent generalization bounds novel algorithms. NewrIPS, 2015.
11

---

Under review as a conference paper at ICLR 2023
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. NeurIPS, 2018.
Zhiyuan Li, Yi Zhang, and Sanjeev Arora. Why are convolutional nets more sample-efficient than fully-connected nets? ICLR, 2021.
Zhouhan Lin, Roland Memisevic, and Kishore Konda. How far can we go without convolution:
Improving fully-connected networks. arXiv preprint, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 106i::1706.000000 2017.
Lukas Mauch and Bin Yang. A novel layerwise pruning method for model reduction of fully connected deep neural networks. In ICASSP, 2017.
Andrew McRae, Justin Romberg, and Mark Davenport. Sample complexity and effective dimension for regression on manifolds. NeurlPS, 2020.
Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In AAAI, 2017.
mrgrhn. Alexnet with tensorllow, 2021.
URL https://medium.comm cww.swlh///////cc/c.m
alexnet withhtensooffor Sow.eeL0o-o-633655666666 46f366559ce8
Noboru Murata, Shuji Yoshizawa, and Shun-ichi Amari. Learning curves, model selection and complexity of neural networks. In NeurIPS, 1992.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. Eetormation-theoreee generalization bounds for sgld via data-dependent estimates. NeurIPS, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning, NeurIPS, 2011.
Bruno Fidi Nishimoto.
Linear classifier,
2018.
URI. https://github.com
brunoni wwwiotoo//iii i
Tomaso Poggio, Kenji Kawaguchi, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix,
Jack Hidary, and Hrushikesh Mhaskar. Theory of deep learning ii:: explaining the non-overfitting puzzle. arXiv preprint arXiv: /00iv.880..000 1801,00173, 2017.
Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrinsic dimension of images and its impact on learning. ICLR, 2021.
Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu. Information- theoretic analysis of stability and bias of learning algorithms. In IEEE Information Theory Workshop (ITW), 2016.
Jorge Sánchez and Florent Perronnin. High-dimensional signature compression for large-scale image classification. In CVPR, 2011.
Andrew M Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan D Tracey, and David D Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12): 2019.
Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. In ALT, 2008.
Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. JMLR, 23:9-1, 2022.
Ravid Shwartz- Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv: arXiv:/703. 7003.008/0 2017.
12

---

Under review as a conference paper at ICLR 2023
E.M. Stein and R. Shakarchi. Fourier Analysis: An Introduction. Princeton lectures in analysis. Princeton University Press, 2011. ISBN 9781400831234.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq. Timothy Lillicrap, and Martin Riedmiller. Deepmind control suite. arXiv preprint, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model- control. In IROS, 2012.
François Treves. Topological Vector Spaces, Distributions and Kernels: Pure and Applied Mathemat- ics, Vol. 25, volume 25. Elsevier, 2016.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10(5):988-90) 999999 1999.
Lokesh Veeramacheneni, Moritz Wolter, Reinhard Klein, and Jochen Garcke. Canonical convolutional neural networks. arXiv preprint arXiv:2206.0/5509 2022.
Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training procedure in timm. arXiv preprint 10.04:2100.0046,, 2021.
David H Wolpert. The lack of a priori distinctions between learning algorithms. Neural computation, 8(7):1441-330,, 1996.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In ICMI., 2019.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Avnish Narayan, Hayden Shively, Adithya Bellathur, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. CoRL, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 16 2016.
Peiliang Zhang, Huan Wang, Nikhil Naik, Caiming Xiong, and Richard Socher. information-theoree difficulty measure for AI datasets. NeurIPS Workshop DL-IG, 2020.
DIME: An
13

---

Under review as a conference paper at ICLR 2023
A SETTINGS OF THE FEATURE-BASER TASK FRAMEWORK
In this section, provide detailed descriptions of the mapping of various learning settings to framework.
Supervised classification In a supervised classification setting, instances can be viewed as con- sisting of two features: a discrete feature di corresponding to class and a continuous feature ei specifying particular example within the class:
r A(c1.d1).
(12)
The optimal action function to output the class (x) = d1 Observe that the continuous feature Ci irrelevant the task; the goal of this task is to learn from training data how to extract the feature dj while maintaining invariance to Ct.
As concrete example, consider the MNIST (Deg 2012 classification dataset; here labels corre- spond to d1, and 01 corresponds to all other information necessary to specify each image (e.g. line width, rotation, overall size). In general, ej may not directly extractable from images; one method of estimating representation of c1 is to train a class-conditional autoencoder on MNIST images, and extract the latent representation of each image as C1.
Meta-learning for few-shot supervised classification In a few-shot meta-learning setting, in- stances be viewed consisting of two features: continuous feature с₁ corresponding a set of related classes, and a continuous feature 22 corresponding to a set of samples from those classes.
A(c1, 02)
(13)
The objective is to output a function g such that g maps inputs set of classes to corresponding labels: (*) g. Note that g here depends only on C₁; the desired function f is invariant to co. Typically, a meta-learning system will receive instances from a subset of cj values, and will be asked to generalize to different subset within the same distribution. To allow the meta-learning system to associate instances with classes on the unseen Cj values, a few inputs with the unseen C₁ are provided for each class.
An example of such a meta- leeanlea problem is few-shot classification on the Omniglot Lake et al. 2015) dataset. Here, ea corresponds to alphabet, and 02 corresponds to set of sample images within that alphabet.
Reinforcement learning In reinforcement learning setting, instances can be viewed as consisting of a single feature specifying all the information in an instance. the language of reinforcement learning, instances may typically correspond to the state of an environment for fully-observed Markov decision process (MDP), or a sequence of observations for a partially-observed MDP. The single feature describing the instance may in general be discrete or continuous; for notational purposes, we default to continuous features when features may be either continuous or discrete.
A(c1)
(14)
Here, (x) denotes the optimal action take given state or observation sequence C1. The goal of the learning system is to generalize over unseen states or observation sequences. However, note that the agent is not asked to generalize over parameters of the underlying MDP: the MDP may fixed.
Note that our framework does not capture certain important aspects of RL settings; for instance, for online RI, does not capture the fact that instances observed during may depend on the previous actions of the agent. This dependence is important to analyze the auploration-exploitttiio tradcoff of an RL task, for instance. Nevertheless, our framework sufficient to assess the difficulty of generalizing in RL. The fact that the set of states observation sequences over which is trained depends on the behavior of the agent has limited relevance to the generalization difficulty of the task.
As example, consider the Cartpole continuous control task from the MuJoCo suite (Tassa et al.) 2018). Here, ej corresponds to the observed state of the environment from which the agent is trained extract the optimal action.
14

---

Under review as a conference paper at ICLR 2023
Unsupervised autoencoding In unsupervised autoencoding, the optimal action function f (2) is simply the identity function (x) = x. The goal is to generalize on test set after observing a set of training instances. Usually, this is non-trivial as the learning system is constrained such that learning an identity function infeasible. However, we highlight that our measure is model-agnostie; in this case the task difficulty be viewed measure of complexity of the instance set. A specific example of such problem may be unsupervised autoencoding of MNIST digits, each of which has a single continuous valued feature.
Meta-reinforcemeet learning In a meee-reeinorreement learning setting, instances correspond to trajectories through environments, which consist of two features: a continuous feature parameteriz- ing the environment and continuous feature C2 corresponding to the specific trajectory within the environment. Both features may in general be discrete or continuous; we use continuous features for our notation:
x C2)
(15)
The objective is to output a policy g such that g that maps states in an environment to actions: f (x) g- Note that g depends only on c1; the desired function f is invariant to <2- The learning system is required to learn from the set of C1 in the training set and generalize to an unseen set of C1-
As an example, consider the Meta- Woold (Yu et al. 2019) meta- mmeta-reinforcement learning benchmark in which an agent controlling a robotic arm must generalize from a set of training skills to an unseen of test skills. The skills include simple manipulations such as pushing, turning, placing etc. In our formulation, corresponds to the skill and corresponds to specific trajectories of the arm performing the skill.
B PROOF OF THEOREM
Proof. Note that for any 21, x2, 0, we have
C(f(z1;0),z) ((((22))) + - fxz2;
(f(x1;0")
(f(m1:0) (1);0") f(x2;; (102;00)),
(16)
$ L (((=)))))(((((())))) f(xz;; f(zz; 201)
Lellf((z1; - f(11;0)) fz2; 0) + f(222
(17)
$ (f(22))),
+ Lellf((r: f(z1; -1) f(x=; + fIz2 0*)
(18)
$ [(f(2))) 0), + [=_
(19)
where equation is a result of the Lipschitz condition on L, equation 18 is a result of the shift- invariance of L and equation 19 is a result of our condition This allows us bound the difference
e(0.p) - e(0, 4) = [x] 0), - E,(
(20)
as follows: let y be distribution on (2) with marginal distributions p and g, respectively. Then
e(0,p) c(0.g) = -
(21)
< E [,),,,
(22)
By the definition of Wasserstein distance, e(0.p) - e(0,)) < LgLyd((0, 0*) inf E. (d(1, x2)) = I.
q),
(23)
where the infimum is taken over all distributions y with marginal distributions p. g. Therefore, for all 0 E O, with d(0,0") < (p.g'' we have e(0,p) p) S e(0,g) + = E (since e(0, g) = 0). Recall that we assume uniform prior on 0. Note that this can typically be made hold with an appropriate choice of reparameterization if our original density on 0 is P(0). then we may choose new parameters ē (0) satisfying |det( Ogi0)
(ee()) )
P(0) to yield uniform density over 0.
15

---

Under review as a conference paper at ICLR 2023
Using the uniform prior assumption on 8, this gives
I = log P(c(H. I c(0,g) = =0)
(24)
v log P (d(00)) - LeL,W(P.g) 10E
E
(25)
as desired.
C VALIDITY OF THEORETICAL ASSUMPTIONS
To arrive at our final expression for task difficulty in Equation IT we make a number of assumptions. In this section, we further discuss the validity of each of our assumptions.
C.I SHIFT-INVARIANCE OF Loss FUNCTION
In many supervised classification and regression settings, the shift invariance assumption is satisfied by squared error loss function. For clarity, in supervised regression, we denote inputs æ and outputs as y. A squared error loss function is constructed as L(y,x) = bl f (z)] 12 which is shift invariant since
x1)
-(y,,)))) (26)
Next, in few-shot meta-learning setting, there are reasonably broad conditions under which shift- invariance holds: Instances correspond to datasets and actions correspond to functions mapping from inputs to the outputs of the inner loop task. For clarity, we define the inner task inputs and outputs as i and o; the goal is to learn mapping from datasets
functions y that map suppose a loss function L(o, i) is defined for the inner loop task. Then, suppose the meta-loss function is defined L(y, x) Ei--r | [y((i), i)] We assume that functions y are additive in the following sense: for any V1, y2, x, (81 + 32) (z) = y/ (x) + (z)).. Finally, we assume generalized version of shift-invee invariancee for the inner loss function L:
v(1). Furthermore,
Eimar [L)) i))] = E,-z, (L((t) + (1)) ff (x))
(27)
This then implies shift-invariance for the meta-loss L: Cly, x2) C(v + (12)
(28)
The shift invariance assumption implies addition is defined over the action space. We believe that such additivity is reasonable for most learning problems. For instance, in classification settings, action spaces typically correspond to vector of logits over all classes; these action spaces are Euclidean and actions can be added. Similarly, in reinforcement learning, both continuous and discrete action spaces are often additive, with the logits of a probability distribution over possible actions outputted the discrete case. Moreover, shift-invariance a property of the commonly used squared error loss, and indeed any loss function that has the form L(y. x) Gly f (z)) for some function G.
At the same time, we note that many loss functions may not satisfy shift invariance. For example the error rate (computed as the fraction of incorrectly classified points in supervised classification), is neither differentiable nor shift-invariant. Thus, during training, differentiable proxy loss functions such squared error cross-entre cross-entropy loss often used, to similar effect. In other words, shift- invariant proxies can exist for non-shiff--nnee correspond to Q function computing the cumulative negative reward over an episode conditioned on taking a particular action. In this case, loss functions often cannot be written in closed form, making it difficult to show shift invariance for these functions even if they are actually shift invariant.
losses. In reinforcement learning. loss functions may
For these reasons, we believe shift-invariance a useful approximation that allows us to theoretically prove properties of task difficulty. We further note that the result of Theorem 1, which used shift-invariance to prove, may hold even for loss functions without without shift invariance:
((f - ((f(22; 02) S 2cL)d((1,22)d(0.)
(29)
Intuitively, it states that when parameters are near their optimal values, small changes in inputs x yield only small changes in the loss, and this feels like very simple and general requirement.
16

---

Under review as a conference paper at ICLR 2023
C.2 SECOND-ORDER CONDITION ON MODEL
The second order condition in Equation 4 (I](;;; f(x 02) [xz;; 01) (122 02)1l S L ) 02)) assumes that changes in the model f can be bounded when the inputs and parameters of f change small amount. First, observe that if f is twice differentiable, then the condition always holds for some choice of L assuming r and 0 are defined on a bounded domain. As concrete example, consider the case of image classification with a Tanh activated neural network where each input pixel is bounded in range [0, 1] and network parameters are bounded by large radius (the bounded parameter assumption is reasonable since practically speaking, trained neural network parameters can be bounded by some radius depending on the amount of training).
As an example of a function that does not satisfy the condition, note that neural networks with the ReLU activation function may not satisfy Equation 8. However, it has been observed that ReLU networks behave like neural networks with smooth, polynomial activation functions (Poggio et al. 2017; thus, it may be reasonable to apply assumption even to ReLU networks.
C.3 SHAPE OF INTERPOLATING HYPOTHESIS SPACE
Regarding our approximation of the interpolating hypothesis space, we first note that the dimension- ality of the interpolating hypothesis lower than the full dimensionality of the hypothesis space. Taking an interpolating hypothesis and slightly perturbing it in an arbitrary direction will likely break interpolation. By contrast, we expect that there exists some subspace in which perturbations along the subspace maintain interpolation (i.e. there is continuous manifold of interpolating hypotheses). This analogous to how in neural networks, local minima can often he in flat regions which perturbing parameters along those directions does not significantly affect the loss (Keskar et al. 2017).
We approximate the interpolating hypothesis space as disk in the overall hypothesis space (for clarity, we have revised our terminology from "ball" to "disk"); this disk has lower dimensionality than the overall hypothesis space but is embedded in a higher dimensional space. The disk assumption preserves key properties that we may reasonably expect of interpolating hypothesis spaces, namely 1) low-dimensionality and 2) boundedness, while being analytically tractable.
Finally, emphasize that the disk approximation is made to approximate the volume of the interpolating hypothesis space. The detailed shape of the interpolating hypothesis space is not itself central to our result, but rather the scaling of its volume is more important. We believe the disk assumption captures the key scalings: the dependence of the volume on b and d.
C.4 EMPIRICALLY VALIDATING WASSERSTEIN DISTANCE APPROXIMATION
In this section, we empirically validate our approximation of Wasserstein distance made in Section D Recall that We approximate the Wasserstein distance between a uniform distribution p on a sphere of radius 4 and an empirical distribution 9 of n randomly sampled points on the sphere as:
W (p. q) E O(rm///m)
(30)
Note that this expression grows linearly with r and decays sub- lineainy with n, with a slower decay with larger m for which more points may be required for all regions to be within fixed radius of any point. Theoretically, we may expect this approximation to hold for large n to achieve near uniform g. If this scaling holds, then we would expect log W (p, q) to decrease linearly with log n (with slope -1/m). Similarly, we would expect log W (p. g) to decrease linearly with 1/m (with slope - log n)).
We conduct experiments on unit sphere (r = 1). We approximate uniform distribution by sampling 10000 points unit sphere and calculate the exact Wasserstein distance between the empirical distribution of 10000 points and the empirical distribution of < 10000 points (we vary n from 10 to 500). Distances are computed for varying choices of varied from 3 to 19.
As illustrated in Figure 4 we find that the relationship between log W (p. g) and log n is linear with a steeper slope for small m, expected. We also observe that the relationship between log W (p, q) and log m is nonlinear, with distances for large m being larger than expected by a linear trend-line. Nevertheless, linear trend-line still produces a strong fit to the empirical data.
17

---

Under review as a conference paper at ICLR 2023
1.2
1.2
10
1.0
n 20
log Wip. q)
log W(p. q)
1.0
n 50
0.8
0.8
0.6
m = 3
0.6
0.4
11
19
0.2
0.4
3
5
6
0.1
0.2
0.3
log n
1/m
Figure Wasserstein distance estimates between a uniform and empirically sampled uniform distribution unit sphere function of the dimensionality of the sphere and the number of sampled points n. Results are shown for five trials in each setting, and linear trend-lines are fitted to the results.
D EMPIRICALLY APPROXIMATING TASK DIFFICULTY
In Section 4.3 presented inductive bias complexity approximation for supervised classification. Here, we provide more details on how to apply and compute our approximation to other settings.
First, we write slightly modified version of our task difficulty approximation
I nd (2dzE - -nd) log b + 2
log = + logd + log K log n log
E
+ loge).
(31)
Lc
1/m
2x (m+13/2
where c
and and E are functions m and the maximum frequency M 2mr/8. supervised classification settings, 2
/ T
In general settings, the parameters controlling task difficulty (m, Lz. b, d, 2) can be interpreted as follows: m is the intrinsic dimensionality of the manifold on which instances lie. n is the number of training points. & is the desired error rate on the task. Le is the Lipschitz constant of the loss function; for tasks without an explicit, differentiable loss function (such as in reinforcement learning), it can be interpreted the overall sensitivity of the loss with respect the model output. and b is are bound on the size the model input and output respectively. d corresponds to the dimensionality of the model output. corresponds to the number of submanifolds each combination of discrete features instances corresponding to a submanifold). In supervised classification settings, the number of submanifolds is simply the number of classes, which is why is set equal to d in these settings.
which instances lie (with
In order to compute the difficulty i of task, we must determine the values of these parameters. For all tasks, we e/ L/ as the desired performance level, which is the distance the output space corresponding to an еrror of s. For each task, we set a fixed desired performance level corresponding the category of the task (i.e. a fixed error rate of 1.0% for image classification tasks and fixed error rate of 0.001 for RL tasks); see Table However, because typical well-performing models in the literature trained on MNIST//mageNet achieve error significantly better/worse performance than 1.0%, we adjust the desired error rate to 0.1% and 10.0% for MNIST and ImageNet respectively. This is done to properly quantify the difficulty of these tasks the error rate regimes in which these tasks typically used. However, our task difficulty numbers choice of desired performance level: using a fixed error rate of 1.0% for all tasks, we find that the scale of task difficulties do not significantly change. Specifically, task difficulty falls incrementally for MNIST from 1.09 x 10 bits to 9.03 x 10 bits, and rises incrementally for ImageNet from 2.48 x 43 bits 2.81 10 bits.
relatively insensitive to the precise
While intrinsic dimensionality m is known for some tasks (e.g. MuJoCo (Du et al. 2018 tasks), must be estimated for others; use the nearest neighbors estimation approach described in Pope
18

---

Under review as a conference paper at ICLR 2023
Table 3: Desired error rates for different tasks used to compute a measure of inductive bias complexity, For each task, desired error rate is set as the performance of typical well-performing models proposed in the literature trained on the task. For classification tasks, error rate corresponds test set accuracy. For Cartpole, error rate corresponds to the probability of making an incorrect action at any given time step. For MuJoCo continuous control tasks with continuous action spaces, error rate corresponds to desired distance in from the optimal action.
Quantity
MNIST
SVHN
CIFAR-10
ImageNet
Omniglot
Caripole
Reacher
Hopper
Half-cheetah
Eroo rate
0.1 %
1.0
%
10.0 %
%
0.001
0.001
0.001
0.001
et al. 2021
The spatial resolution 8 is set based on the nature of each task. For classification tasks, natural set the spatial resolution as the margin between classes. For RL tasks, it is set scale which trajectories with perturbations of size ó are not likely to be meaningfully different. For all tasks, we approximate r to the maximum norm of training data points.
D.1 EMPIRICALLY COMPUTING CLASSIFICATION TASK DIFFICULTY
For an image classification task, the model output a probability distribution on the classes so to be 1. We set to be the minimum distance between points of different classes, this is the minimum distance between inputs that f must be able to distinguish. For large datasets where computing 5 exactly is impractical, Appendix
estimate it using statistical methods. This procedure is explained in
We estimate using the technique described by Pope et (2021), which gives MLE estimate based on distances to nearest neighbors. We use h = 5 nearest neighbors for our estimation. For large datasets where computing nearest neighbors for all points is impractical, we use the anchor approximation from [Pope et al. (2021), selecting a random sample of points to use anchors and finding their nearest neighbors in the entire dataset. To estimate m for ImageNet, we randomly select 2000 points to be our anchors. See Table 4 for our estimates of m and 5 for image classification benchmarks.
Table 4: Estimated and å for various image classification benchmarks. These estimates used to estimate the amount of inductive bias required to solve each task.
Quantity
MNIST
SVHN
CIFAR-10
ImageNet
m
14
19
27
48
8
2.4
1.6
2.8
65
D.2 EMPIRICALLY COMPUTING META-LEARNING TASK DIFFICULTY
The Omniglot sho- classification task is to identify the class of an image given an example image of each of 20 letters. Thuss the meta-learning task is to learn function that maps a set of 20 images to a function g that can map a single image to a probability distribution over 20 classes. the following discussion, for quantities such 2, d, and E, subscript f will be used to denote that we are considering these values for the function f. and a subscript g will be used to denote that we are considering these values for the function g.
In our framework, the input to / has no discrete features, so 2 1. Since g is the output of f. d equals the dimensionality of the parameterization of g. which is 2g. The function classifies an image among 20 classes, so 2g = 20 and dy = 19. We can compute Eg as a function of Mg = 2xrg/6, fy and my- As with image classification tasks, of an image in the dataset and 5y to be the minimum distance between images of different classes. We set my to be the dimensionality my of image drawn from single alphabet. This is done by estimating the dimensionality of each alphabet in the dataset and averaging the results.
set rg be the maximum norm
Since the input to f is 20 images, ry = 22.. To compute my. let m, > my be the dimensionality of an image drawn from the entire dataset. Then the dimensionality of the alphabet underlying
19

---

For evaluating task difficulty for reinforcement learning tasks, we use some different approximations than for the supervised classification that are more suited particular setting; in particular, use a different assumption for the manifold on which instances lie and a different approximation for Wasserstein Under review as a conference paper at ICLR 2023
the input to is my ma, and the dimensionality of the images themselves is 20mg- Therefore, , = mi + 19mg. We want f to be sensitive to change only one of the 20 images, so we set 6 6g. 0g.
The training dataset consists several alphabets. We write l, for the number of letters in alphabet We set be the number of sets of 20 images that be drawn from the training dataset that represent 20 different letters in the same alphabet. Since the training dataset contains 20 images representing each letter,
max 201) 20
(32)
20
where the sum is taken over all training alphabets a.
Finally, by is the maximum norm of f's output, which contains the parameterization of g. We found .. We have already computed 2g and dg. and since g outputs probability distribution, bg We then use the values 2y. dy, my, Ey, n, by. and the state-of-the-an error rate e/ L/ to compute the task difficulty.
that this can be bounded by by /ggg.
D.3 EMPIRICALLY COMPUTING REINFORC LEARNING TASK DIFFICULTY
distance W (p.g).
We first write our general version of the task difficulty expression without applying the Wasserstein distance approximation in Section 4.3
i (2d=F- nd) loggb + log + log d + log K logr log W(p.)) log
(33)
Lc
In the reinforcement learning tasks we evaluate, z = 1, so we can write:
= (2dE - -nd) [logb b log d + log K logr + log (p. log
E
(34)
Lc
The input to í is m-dimensioonl observation, which can be considered as point in the hypercube [-m, n, x| after scaling. Parameterizing if as a sum of cigenfunctions of the Saplace-Beltranne operator,
f(z; 0)
0pe00
(35)
PEZm
Treves (0166). The wavelength the component corresponding to is 3///|p|| so we restrict our parameterization to components satisfying ||||| < / Thus, we have L, 2n /5. The number of eigenfunctions E is the number of vectors E td satisfying ||pl| S 2T/5, which we approximate as the volume of m-dimensional ball with radius 2 giving
2T 8
E RM
Vm:
(36)
where Vn,
m2
is the volume of an m-dimensional ball with radius 1. We now find the
+1]
Wasserstein distance W(p. q). In the optimal transport, each training data point is associated with an equally-sized region of the hypercube. We approximate these regions as hypercubes with side length = 2nn 1/m The expected distance between two randomly chosen points in one of these hypercubes is at most m//6 Anderssen et al. 1976). so
m 2nn 1/m
W 4) Re
(37)
Finally, note that f's output is force in [-1,+1] in the discrete case and element of [-1, 1]d in the continuous case. Therefore, we can set b vd in all cases. Using these values, we find
i R dl 2 2T 8
log 4x²
E
Vn Tm/)
log d +
log m log 5 loo n log
(38)
/6
2
L
20

---

Under review as a conference paper at ICLR 2023
Recall that d is the dimensionality of the output space, and is the dimensionality of the observation space. In the noisy Cartpole task, T observations may be needed to determine the optimal action. Each observation is a two-dimensional state (containing the pole's angular position and velocity), so we set m 27. For fully observed tasks, note that T = 1.
It remains choose values for the parameters n, 6, and e/Lg. We choose the relatively small value of 0.001 for and // LC for all tasks. We choose a small value for because small changes in initial conditions can lead large changes over time, and we choose small value for Le because agents should be able to perform near-optimal actions to achieve the task's goal. In the noisy Cartpole task, we set n 10000, corresponding to observing 100 episodes with 100 timesteps each. In the MuJoCo environments, we set n 1000000, corresponding to observing 1000 episodes with 1000 timesteps each. We emphasize that the most important factor contributing to task difficulty m, which determined by the task specification.
E ESTIMATING å FOR CLASSIFICATION TASKS
If we cannot compute 8 exactly, we estimate it using extreme value theory Dekkers et al. (1989).
We wish find the maximum value distribution, in this case the distribution the reciprocal of the distance between random pair of points from different classes. The extreme value distribution is characterized by the extreme value index y. Let XI...., ,, X, be values drawn from the distribution, and let X1, .... S X be these values in sorted order. For a fixed k < n, define
- = K
(log Xn-i, log X Xn-k,n)"
(39)
Then estimate " as
(
-1
In = M +
1 2
(40)
M!?
Empirically, we typically find 9n > O. In this case, we estimate ō by estimating the quantile corresponding to the top 1/P of the distribution, where P is the number of pairs of training data points from different classes. By assuming that training data points are evenly distributed among the classes, we approximate P as n²2 - 1/C), where C is the number of classes. If a, kP/n, this gives an estimate of
a. 1 fn
Mn + -nnkkn
(41)
for 1/5.
The theoretical results Dekkers et al. 1989) require that k and n/A go to infinity as n - co. For ImageNet, we choose 40000 and k = 200. To reduce the noise in estimation, compute 10 estimates for 1/6 and average the results to obtain our final estimate for 1/6.
F ADDITIONAL TASK VARIATIONS
In this section, order to provide more intuition for our empirical results on inductive bias complexity, we compute the inductive bias complexity of additional variations of tasks.
F.I TASK COMBINATIONS
Setup We first consider inductive bias complexities of task combinations. We assume we are given two tasks, corresponding to the mapping between instances I to yı = fi (z1) and 22 to 2/2 f (22) respectively. Furthermore, we assume that training and test distributions g1, and
P2. Q2 are provided. We then construct a combination of the two tasks as the mapping from (I1 x2) to 22) (ft (z (x2)). The test distribution of instances for the new task is constructed
as:
x2) p1 (21))2(32)
(42)
21

---

Under review as a conference paper at ICLR 2023
And the training distribution constructed as:
(411 22) 92 (21))2
(43)
Note that if qu and 92 each correspond to training sets of size ni and 122, 9 corresponds to training set of size 71 We assume that the two tasks have loss functions L1 and L2 respectively. For the purposes of our analysis in this section, we assume that the loss functions satisfy Cyy,, x)) 2 and equality holds if and only if (z) for i = 2, We construct the loss function C for the combined task as:
C((y: 92). x2)) = (v1, v1) + (1 a) (V22
(44)
for a parameter a in (0, 1). We denote a hypothesis as parameterizing a function that inputs (x1, x2) and outputs the predictions for each task: f(x1, I22 8) (fi (21, 22; 22; 0), f2 22; 02; Then, the
generalization error of a particular hypothesis 0 under distribution p (and analogous for q) is:
e(0, p) = e(((; =
=cE,ICi(f 21)] + (1 -),,, (45)
For notational convenience, we will also define e; (0, p) as (and analogous for q):
(..0.) p) (fi
(46)
for 1,2. Thus, we may express e(0, p) as:
c(f., p) 0e, (0.p) + a))2((.))
(47)
Note that (0, p) and e2(0. p) do not correspond to errors of hypothesis of 9 on tasks 1 and
directly because @ parameterizes function which takes both ø and 22 input. Instead, e1 (0.p) (and analogously for ez (2) corresponds to the error of a variant of task where instances 21 are augmented with distractor input 22 which is irrelevant to the task (producing instances (æ1, 222)), )), but the task output y1 is constructed the same way as V1 = ft For clarify, we define this mapping as yı f (ar ( 222) (and analogously for the variant of task 2). Importantly, note that this variant of task has an input with larger intrinsic dimensionality.
Now, we consider the inductive bias complexity of the combined task corresponding to f". Recall that we define inductive bias complexity as:
log ((e(O. p) S c(f. =)
(48)
We relate this inductive bias complexity to the inductive bias complexities of tasks corresponding to Ji and fz:
i, log ((, S E (e.
(49)
where 7. corresponds the inductive bias complexity for the task corresponding to fe- Under certain conditional independence assumptions, we are able to relate I and the I.. Specifically, we assume that if 0 interpolates task 1, then additionally interpolating task 2 does not change the probability that 0 will generalize on task (and vice versa). We also assume that if 0 interpolates both task and task 2, then generalizing on task does not affect the probability that 0 generalizes on task 2 (and vice versa). This is reasonable if we consider task and task 2 to constructed independently fi (æ1, 22) and vice versa; being able to
in the sense that inputs 22 do not provide information interpolate or generalize on one task does not affect the case of generalization on the other. Thus, we able make the following statement:
Theorem 2. Assume the following conditional independencies:
(0,0)) Se E 1 e2) (0, =
(50)
e2(0 <e Le 0)e2((0,)) =0
(51)
(0. < e 1 ez (0.p) (0, 0, (2.. =
(52)
Then,
- logle- 11 +e 12) < 1 i +
(53)
22

---

Under review as a conference paper at ICLR 2023
Proof. First, that by conditional independence:
Sel -))(ee200)P(()))))))) S <=le(0,0)=00
=P(e:(0. S Sen <e se((00,)) = 0) (54)
Note that e(0,p) S = S Sc This implies:
P(e(0, p) s c(0,g) q) = 0) 2 (f( S <=le(0,g) = (55)
Also, observe that e(0,p) < = <
< 8. This implies:
((er(6,p) S c(0.g) = 0) P(e2(0,p) < 0) 2 P()(O, S | 0) (56) Next, using our first two conditional independence assumptions:
p() S (1 q) = <= = 0) = P(e(0, S ((,)) = (57)
(0, S ei (0, g) = 0) + P(e2 S e2 q) = 0) 2 P(e(0. 5= 0)
(58)
Finally, taking the negative log of both sides:
log(e 1 +e + < < ī +1
(59)
as desired.
Note that - loo(e- +c- = min Iy]. Thus, the statement intuitively says that the combined task requires inductive bias up the total inductive bias of the two tasks treated individually, and requires at least the inductive bias of the casier task. We emphasize again that 1, does not correspond to the inductive bias required to solve task i, but rather the inductive bias required to solve a variant of task with distractor added to instances provided from the other task.
Experiments Next, we empirically compute inductive bias complexities for combinations of image classification tasks. To do this, we compute the task difficulty of a version of each task with task-irrelevant distractor from the other task appended each instance (I₃ I2 described above).
We then report the upper bound I + In and lower bound - log(e 1 + - o.
In order to compute task difficulties for tasks with distractor-appendee instances, we first revisit our generalized approximation of inductive bias complexity from Equation 31
i Rd (2d=F= - -nd) (log b log = + log + log K log n log LE + loge)-
(60)
m
1/m
where c
TI
(m 13/2
which is roughly constant for large intrinsic dimensionality m.
Recall that dl is the output dimensionality, = is the number of manifolds that the input data lie on, is the number of training data points, e is the target error, Lg is the Lipschitz constant of the loss function, and K and É are functions of and the maximum frequency M 2 Typically for classification problems, = d is set as the number of classes.
When we append task-irrelevant distractors the instances of task, five key parameters change: the number of training points n, the intrinsic dimensionality m, the number of manifolds = and the bound on model output 6 and bound on model input r. Importantly, all other parameters stay fixed (namely, 6, d, and Lc). The number of training points scales with the number of different distractor instances; task with n, training points augmented with instances from task 2 with n2 training points, the new task has n2 training points. Also, the new intrinsic dimensionality of the task is the sum of the intrinsic dimensionalities of the individual tasks since the combined manifold of (I1, is the product of the manifolds of æ and 22 individually. Thus, if task has intrinsic dimensionality mi and task 2 has intrinsic dimensionality m2, the intrinsic dimensionality of the augmented task is mi + m2. The number of manifolds of the input of the combined task is the number of manifolds corresponding to (01,22), R2), which is simply 2 21 if task and task 2 have 2; and 22 classes respectively. If task and task have model outputs bounded by by and by respectively,
23

---

Under review as a conference paper at ICLR 2023
then the combined model is bounded by Vbj + by. Similarly, the new value of is vri + r We may then compute the task difficulty of destractor-appender task using the formula above.
We compute task difficulties for pairwise combinations of MNIST. SVHN and CIFAR-10 (which have individual task difficulties (in bits) of: 1 x 10 x 10S1, 3 x 10 As found in Table combined task difficulties are significantly greater than the difficulties of individual tasks. As very rough rule of thumb, the combined task difficulty is approximately the product of the individual task difficulties. This makes sense since the task difficulty scales exponentially with the intrinsic dimension of the data and combining together two tasks #adds* together the intrinsic dimensionality of the two tasks (and thus multiplies their task difficulties).
Table 5: Combined task difficulty bounds (in bits) for combinations of image classification tasks. Difficulties are reported as "lower bound / upper bound." Individual task difficulties of MNIST, SVHN and CIFAR-10 10 are (in bits): x 10 x 10 3 x 10 respectively.
MNIST
SVHN
CIFAR-10
MNIST
1 x 2026 /3 x 1026
6 x 1039 1 x 1046
3 x 10 /8 x 10th
SVHN
4 x 1054 /8 x 1054
4 1050 /4 x 1061
CIFAR-10
x 10as /3 x 1035
Why does combining together two simple tasks like MNIST result in a much more difficult task? This is because separating the two parts of the combined task requires a lot of inductive bias. Without this inductive bias, solving combination of two tasks looks like solving single task with a higher dimensional input, which correspondingly requires much greater inductive bias. This also suggests how practical model classes like neural networks may be able to provide such vast amounts of inductive bias to a task: namely, by breaking down the input into lower-dimensional components.
F.2 PREDICTING ZERO-OUTPUT
To gain intuition for the properties of task difficulty, we compute task difficulties for task in which the target function always has output O: f"xx). To compute the task difficulty, we return to the definition of inductive bias complexity from Definition
i - log((c((H.p) p) S e(0, 5c)
|
(61)
Keeping e = as we have done throughout the paper, observe that just as with the general case, the inductive bias complexity is based on the fraction of interpolating hypotheses that generalize well. In the case of zero output, generalizing well means that f(: 0) should be sufficiently close to 0 on the distribution p. Note that interpolating hypotheses may not necessarily have near-zero output over distribution p; thus, solving the a zero-output task may require significant levels of inductive bias.
The key to determining the difficulty of zero-output task is setting the hypothesis space. Recall that in Section 4.3, we constructed the hypothesis space to be linear combinations of set of basis functions sensitive to a task-relevant resolution (or larger). In the case of zero-output, all resolutions are task-irrelevant: the true output f (2x is not sensitive to any changes in the input. Thus, if we were to use the approach of Section 4.3 to construct hypotheses, we would find that there is only a single hypothesis in the hypothesis space, namely fx. Since f" interpolates the training data and perfectly generalizes, the probability of generalizing given interpolation is 1. Thus, the task difficulty is O.
However, other choices of the base hypothesis space may lead to very large task difficulties. Consider version of ImageNet in which all inputs are mapped to a 1000-dimensional zero vector. If we construct the base hypothesis space in the same way as for the original ImageNet task, assuming wish to achieve the same generalization error target as we set for the original ImageNet task, the task difficulty approximation for the zero-output ImageNet would be the same as for the original ImageNet: 3.55 x 10 bits.
How can the inductive bias required to generalize on ImageNet stay the same even when the target function is made much simpler (assuming the hypothesis space is kept the same)? This is because
24

---

Under review as a conference paper at ICLR 2023
Task Difficulty (bits)
10
Task Difficulty (bits)
10
1049
1040
1039
1042
10
10
0
500 Number of Classes
1000
50
75
100
5
(a) Varying number of classes ImageNet
(b) Varying spatial resolution on ImageNet
Figure 5: Task difficulties on parametric variations of benchmark tasks.
inductive bias complexity corresponds to the difficulty of specifying generalizing set of hypotheses from the interpolating hypotheses. Due to the large size of the base hypothesis space, the size of the interpolating hypothesis space can be expected to be the same for both the true ImageNet target function and the zero target function: we may expect the same fraction of hypothesis to satisfy the zero target training samples the true ImageNet training samples. The base hypothesis space does not over-represent hypotheses near the zero target function relative to other hypotheses. Then, given similarly sized interpolating hypothesis spaces, the difficulty of specifying the true hypothesis is similar for the two tasks.
F.3 PREDICTING RANDOM TARGETS
Next, consider variation of ImageNet where the ImageNet target function is replaced with random function selected from the base hypothesis space used for the original ImageNet. In this case, the training set would appear to be version of ImageNet with randomized outputs for each image. Importantly, note that this is different than independently selecting a random output for each point in the training set: would training points that sufficiently close (with distances around the spatial resolution 8 or smaller) to have similar outputs. We consider this formulation of randomizing the outputs of ImageNet instead of selecting independent random targets for each ImageNet input since constructing independently chosen random targets for all possible input of ImageNet may not correspond to well-defined target function.
Assume we wish to achieve the same generalization error rate for the original ImageNet task. The parameters governing task difficulty would remain the same as in Equation TT namely, the parameters specific to the input distribution (m, n, d, r), model output and loss function (6, Lc) and error rate (e) would remain the same. Thus, the task difficulty would be the same as for the original ImageNet: 3.55 10 bits.
How can solving randomized version of ImageNet require no more inductive bias than the original task despite having less structured target function? Intuitively, this is because the base hypothesis space considers all hypothesis equally: it does not over-represent structured hypotheses (such as the target function of ImageNet) relative to other ones. Thus, the difficulty of specifying a well generalizing region in the hypothesis space is the same for both the randomized and original versions of ImageNet.
F.4 VARYING NUMBER OF CLASSES
We vary the number classes ImageNet (while keeping all other task parameters fixed including the number of training points and find in Figure 5a that task difficulty grows with the number of classes. As the number classes increased from 10 to 1000, the task difficulty increases by roughly orders of magnitude. This is primarily due to the increased size of the input space when more classes
25

---

Under review as a conference paper at ICLR 2023
added. The results indicate that adding more classes classification task can be moderately powerful way of increasing the difficulty of task, although not as powerful as increasing the intrinsic dimensionality of task.
F.5 VARYING SPATIAL RESOLUTION
We vary the spatial resolution used to construct the base hypothesis space of ImageNet (while keeping all other task parameters fixed) and find in Figure 5 that task difficulty drastically shrinks with the spatial resolution. This makes sense: as the spatial resolution used to construct the hypothesis space grows, the hypothesis space shrinks, and becomes much more difficult to specify regions in the hypothesis space. These results emphasize the critical effect of the selection of base hypothesis space on task difficulty.
G ADDITIONAL DISCUSSION
G.1 HOW TO EXTEND THE INDUCTIVE BIAS COMPLEXITY MEASURE TO THE NON-INTERPOLATING CASE?
One limitation of our work is that we only consider interpolating hypotheses (in other words, we only consider training error e = Definition D. Although we will leave a formal extension of our results to non-interpolating hypotheses future work, we briefly outline how are results might be extended:
First, we may provide an analogous result to Theorem in the non- non-interpolating case by arguing that non-interpolating hypotheses may generalize well as long as they are within a smaller radius of the true hypotheses (relative to the radius for interpolating hypotheses). Specifically, we may expect the more general expression for the radius to W(.g)
e-e
Next, in order to quantify probabilities in the hypothesis space and find practical estimate for inductive bias complexity, we must quantify the size of the hypothesis space that fits the training data up to error e. Intuitively, we may expect it to be region around the interpolating hypothesis space with dimensionality equal to that of the base hypothesis space. We may expect the size of this region to scale polynomially with As with the interpolating case, we can then estimate the fraction of the near-interpolating hypothesis space that close enough the true hypothesis to find generalized, expression for task difficulty.
G.2 WHY DOES INDUCTIVE BIAS EXPONENTIALLY DEPEND DATA DIMENSION?
Intuitively, inductive bias scales exponentially with data dimension because inductive bias scales with the dimensionality of the hypothesis space, and the dimensionality of the hypothesis space scales exponentially with data dimension.
First, consider the intuition for why inductive bias scales with the dimensionality of the hypothesis space: recall that generalizing requires specifying a specific set of well-generalizing hypotheses in the hypothesis space. The amount of information needed specify point in an m dimensional space scales with m since it is simply the number of coordinates of the point. Thus. assuming well-generalizing hypotheses are concentrated required to specify the region also scales with the dimensionality of the hypothesis space.
region around a point, the amount of information
Next, we consider the intuition for why the dimensionality of the hypothesis space scales with data dimensionality: consider a very simple "grid-based" method of constructing hypotheses in which the input manifold divided into equally sized hypercubes that tile the entire manifold. A hypothesis consists of mapping between hypercubes and outputs. Note that the dimensionality of each hypothesis scales with the number of hypercubes since each hypothesis can be specified by its output at each hypercube. The number of hypercubes scales exponentially with the dimensionality of the input manifold; thus the hypothesis space dimensionality also scales exponentially with the dimensionality of the input manifold.
26

---

Under review as a conference paper at ICLR 2023
We view this exponential dependence fundamental: generalizing over more dimensions of variation significantly expands the hypothesis space regardless of how we parameterize hypotheses, and thus dramatically increases inductive bias complexity.
G.3 WHY DO TRAINING POINTS PROVIDE SO LITTLE INDUCTIVE BIAS?
Experimentally, we observe that changing the amount of training data, even by many orders of magnitude. does not significantly affect the amount of inductive bias required to generalize. We can interpret this as training data providing relatively little information on which to generalize. Why do training points provide so little information? Intuitively, it because in the absence of strong constraints on the hypothesis space, training points only provide information about the function aim to approximate in a local neighborhood around each training point. By contrast, inductive biases the hypothesis space than dramatically reduce the size of
provide more global constraints the hypothesis space and allow for generalization. Without strong inductive biases, training points need cover large regions of the input manifold to allow for generalization. With high dimensional manifolds, this can require very large numbers of training points.
Through simple scaling arguments, alize on ImageNet in the absence of strong inductive biases. We estimate the intrinsic dimensionality of ImageNet be 48 and the task-relevant resolution of ImageNet to be 65. We can then estimate the number of training points needed to generalize as the number such that any region on the manifold within radius of a training point. With n training points, we can expect to cover volume of about n6548 on the manifold. Given a manifold of volume about (255 224 x /3)45 (corresponding the [0, 255] pixel range and 224 x 224 x 3 extrinsic dimensionality of ImageNet images), we would then require about (255 x 224 x /3/65)44 x 10 points to generalize. Indeed, following the linear trend of 3 we may expect to approximately halve the required inductive bias with this number of training points. However, with only 1047 points, strong inductive biases would be necessary to generalize as indicated in Figure
estimate the number of training samples need to gener-
G.4
WHY IS THE SCALE OF INDUCTIVE BIAS COMPLEXITY SO LARGE?
Across all settings, our measure yields very large inductive information content, many orders of magnitude larger than parameter dimensionalities of practical models. These large numbers can be attributed the vast size of the hypothesis space constructed in Section 4.3 it includes any bandlimited function on the data manifold below a certain frequency threshold. Typical function classes may already represent only a very small subspace of the hypothesis space: for instance, neural networks have biases toward compositionality and smoothness that may significantly reduce the hypothesis space (seel Li et al. (2018): Mhaskar et al. (2017)) with standard initializations and optimizers further shrinking the subspace. Moreover, functions that can be practically implemented by reasonably sized programs on our computer hardware and software may themselves occupy a small fraction of the full hypothesis space. Future work may use base hypothesis space that already includes some of these constraints, which could reduce the scale of our measured task difficulty.
27

---

Under review as a conference paper at ICLR 2023
H
ADDITIONAL TABLES AND FIGURES
Table 6: Mapping notation in the feature- based task framework to different learning settings.
Setting
Features
(x)
Supervised classification
input
di class instance within class
class
Reinforcement learning
state or observation sequence
state or
desired action
observation sequence
Meta-learning for few-shot classification
samples from set related classes
oj: a set of related classes 0g: choice samples et
classifier mapping inputs to their class
Unsupervised autoencoding
input
c1: input
Meta-reinforcement learning
trajectories through environments
cy environment
policy mapping states to desired actions
cg: trajectory within environment
1
1
Interpolating hypotheses
2
ff
f*
3
2
3
Hypothesis space
F*
Figure 6: An example of constructing hypothesis space for a binary-classificttion task with 1 dimensional input. The black line indicates the data manifold and the blue and red dots on the line indicate training points. The hypothesis space is constructed using basis functions of three different frequencies; observe that the highest frequency is chosen to have scale corresponding to the minimum distance between classes. Two specific hypothesis the true hypothesis (in orange), f* and another hypothesis f (in purple). Both can be expressed as linear combinations of the basis functions, and thus correspond to points in the hypothesis space as illustrated. The f' hypothesis fits the training data, and thus is part of the interpolating hypothesis set indicated by the light orange oval.
illustrated in the hypothesis space,
28

---

Under review as a conference paper at ICLR 2023
Table 7: The inductive bias information contributed by different model architectures for image classification tasks. (FC-N refers fully connected network with N layers.)
MNIST
Model
Information Content (x10 bits]
Model
Information
Content (x 10 bits)
FC-6 MMuch Yang, 2017
0.870
Linear (Lecun et al 1998
0,703
AlexNei Veeranachenentt
FC-3 (Leuun al. 1998
0.817
AlexNei (mrernn
0.888
Deep CNN (Lnodlreloow al 2013
1.049
LeNet.5 (CNN) ( Lezun et al. 1998
(Lee al. 2015
0.907
0,076
DSN (Lee al. 2013
DenseNar (Hungg al 2017
1.080
1.075
MCDSN (Ciregan el 2012
1,020
WRN- Zagurayko Komodakis
1.077
Ensembled CNN (An ct 2020
1.08
WRN 28 10 Forer nl. 1020
1.114
ImageNet
CIFAR10
Model
Information Content (> 10 bits)
Information Content (x10'2 bits)
Linear Karpathy 2013
2,063
Linear (Nishimoto 2018
2,250
SIFT
FVs (anchez & Perronnin
2.261
PC-4 ([ et al 2015
2.354
2011
MCDNN (Cireaan et
2,704
AlexNet Krizhevsky et al. 2012
2.200
AlexNpt (nzhevsky
2012
2.703)
DenseNet 121 (Huang et 2017
2.348
DSN (Lee am 2013
2,756
ResNet-50 [e
2.302
DenseNer (Huane al. 2017
3.010
DenseNei- 201 (Tuann el af
2017
2.363
ResNat-50 50 [Wiphlman
1021
3.195
WRN-50-22 F7RN-50-2-oollkams Zapouuko & Ko
2.305
B:T-L (Kolesmkov el all 2020
3.453
modalkis 2016
VIT-H/14 (Desoviskiy al
3.513
Bri-L Kojesnkov et 2020
2.419
VIT-H/1 Dosovitskly 2021
2.461
29


Reviews:
[{"review_id": "jdf5OBEexr", "reviewer": "Reviewer_FUck", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This submission tackles the problem of measuring inherent difficulty of a learning task, independent of a learning algorithm and model class. Formally, a learning task is defined as a training set of instances and corresponding actions sampled from a training distribution. The goal of a learner is to generalize well to instances sampled from a possibly related test distribution. It is assumed that there is a ground-truth mapping from instances to actions. It is also assumed that one has access to a large hypothesis set (different from the model class) with a uniform prior on it, that includes the ground truth mapping. The authors show that common learning settings, such as supervised classification, reinforcement learning, meta-learning for few-shot classification, and meta-reinforcement learning can be formulated in this framework.\n\nWithin this framework, the authors introduce a measure of task difficulty that quantifies the minimum “amount of inductive biases\" needed to generalize well. This boils down to computing the fraction of interpolating hypotheses that have a desired level of performance on the test distribution. As it is hard to compute this quantity exactly, the rest of the paper makes a series of simpliciations and assumptions in order to compute an upper bound for this quantity. The final section of the paper computes this upper bound for a few standard learning tasks and examines the trends of it with different aspects of learning tasks.\n", "summary_of_the_review": "In summary, while I like the problem and the perspective of this submission, I find the paper not ready for publication.", "strength_and_weaknesses": "#### **Strengths**\n\n* This submission focuses on an important problem that was not addressed much to my best knowledge.\n* The proposed notion of inductive bias complexity is interesting.\n\n#### **Weakness 1: limitations**\n\n1. The proposed task difficulty depends on a large hypothesis set with a uniform prior on it. It is unclear how to select this hypothesis set and how it affects the findings.\n2. A uniform distribution might not exist for some of such large hypothesis sets.\n3. Even when a uniform prior can exist, it is still an arbitrary choice, as it disregards the geometry of the space. Maybe a more appropriate choice would be the Jeffreys prior.\n4. In the meta-learning setting this hypothesis set needs to be a set of mappings from datasets to functions. It is unclear how even distributions are defined on such spaces. Could you please elaborate on this?\n5. The proposed task depends only on the set of interpolating hypotheses. As mentioned in the paper, there might be well-generalizing but non-interpolating hypotheses. \n\n#### **Weakness 2: unrealistic assumptions and simplifications**\n1. In Thm 1, “Suppose that the loss function is invariant to shifts $L(y_1 + y, y_2 + y) = L(y_1, y_2)$ for all $y_1, y_2, y$.”:  This assumes that there is an addition operation defined on the action space. How does this hold in the settings of supervised classification or meta-learning for few-shot classification?\n2. The assumption of Eq. (8) seems too strong. Can you give examples of large hypothesis sets for which this assumption holds?\n3. In Sec 4.2, the data distribution is approximated as a mixture of uniform distributions on disjoint spheres. In particular, in a supervised classification setting, it is assumed that examples of the same class have a uniform distribution on a sphere.\n\n#### **Weakness 3: It is hard to validate the experiment findings.**\n1. Since there are no baselines presented and the proposed approach does many simplifications, it is hard to judge the validity of the experimental findings.\n2. I recommend designing some sanity checks for validating the results.  For example, how does the difficulty of union of two related (or independent) tasks compare to those of the individual tasks?\n3. In Figure 3(a), ImageNet training data is hypothetically increased to the size more than $10^{17}$, but we see that the approximated task difficulty remains roughly the same. It seems that with so many training examples, the set of interpolating solutions should contain only the ground-truth function (or extremely similar ones), therefore making the task difficulty close to zero. This entails that we should at least see a large drop in the approximated task difficulty when the number of examples is so large.\n\n\n**One related paper:** Achille et al. [1] also define information-theoretic model-agnostic task complexities.\n\n#### **References**\n\n[1] Achille, A., Paolini, G., Mbeng, G. and Soatto, S., 2021. The information complexity of learning tasks, their structure and their distance. Information and Inference: A Journal of the IMA, 10(1), pp.51-72.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Zle-vaYwbnZ", "reviewer": "Reviewer_Du5K", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors introduces a notion of task difficulty, which they coin \"inductive bias complexity\". Intuitively, it is the fraction of interpolating hypotheses (in the space of all possible functions) that also generalize well. After introducing the formal definition, the authors use a series of approximations to come up with a computationally tractable approximation. Then, they apply it on various tasks and argue that this measure of complexity matches with expectations; e.g. MNIST < CIFAR10 < ImageNet. ", "summary_of_the_review": "I think the direction is novel but the approach the authors use is very similar to recent works that study scaling law estimators. In that line of work, the goal is to understand power laws in overparaemterized models. In this work, the goal is to quantify the difficulty of a task but the approach is questionable for several reasons as I mention above. The paper would benefit from providing a stronger motivation that highlights clearly how this measure of complexity can be useful to the community (either by providing new insights or practice applications).", "strength_and_weaknesses": "*Strengths*:\n- The authors pursue a novel direction, which is to provide a model-agnostic measure of task difficulty. However, the final outcome (Equation 11) is quite similar to several recent works that study scaling laws, which use much simpler arguments.\n\n*Weaknesses*:\n- Under the hood, \"inductive bias complexity\" corresponds to the fraction of interpolating hypotheses that also generalize well; i.e. the probability that an interpolating hypothesis would also generalize. When this is taken as a definition, we obviously have that interpolating functions would generalize well on simple tasks and perform poorly on more difficult tasks; but this is really somewhat tautological. I don't think the definition offers any insight that can be useful in practice. \n- The authors argue that the definition is model-agnostic. However, the definition does assume that one can (somehow) parameterize the space of all possible hypotheses.\n- If we consider simpler arguments used in the scaling laws literature, we deduce that difficulty of a task is roughly $O(m^{-1/d})$, where $m$ is the size of the training set and $d$ is the intrinsic dimension of the data manifold. This follows from a partitioning argument; see for example [1, 2, 3]. It's not clear if the proposed \"inductive bias complexity\" in Theorem 1 would offer any additional insight beyond such simpler measures of complexity. In fact, the series of approximations that the authors propose are similar in spirit to previous arguments and also lead to similar conclusions (see for example Equation 11).\n- The definition that the authors use involves a loss $\\epsilon$. In Appendix C, the authors use different values of  $\\epsilon$ for different tasks (e.g. they use a very small value in MNIST and a much larger value in ImageNet) even though they also show that \"inductive bias\" is sensitive to the choice of this parameter (Figure 3b). I'm not sure if this makes the comparison between datasets meaningful. \n\n[1] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.\n\n[2] Marcus Hutter. Learning curve theory. arXiv preprint arXiv:2102.04074, 2021.\n\n[3] Utkarsh Sharma and Jared Kaplan. Scaling laws from the data manifold dimension. JMLR, 23(9):1–34, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UL8pHOHt72", "reviewer": "Reviewer_eajX", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes a novel notion called \"inductive bias complexity\". Just as sample complexity captures the number of samples required for learning a problem (upto a desired error) given a fixed inductive bias, the \"inductive bias complexity\" refers to the minimum amount of \"inductive bias\" required for learning a problem (upto a desired error) given a fixed number of training data. This notion is interesting because it, to some extent, explains the amount of prior knowledge (or handcrafted arts) one needs to set in order to solve a problem with the given amount of data. \n\nAfter introducing the notion of \"inductive bias complexity\", this work further provides a bound on it based on a set of conditions, which are somewhat strong but are also quite standard in learning theory. Finally, some empirical results are provided to verify the theoretical predictions. ", "summary_of_the_review": "At this point I am very positive to this work. The authors reply on my questions can help me better understand the work. ", "strength_and_weaknesses": "# Strength\n1. I find the paper written in a very clear manner. I have enjoyed a lot reading the paper!\n2. The notion of \"inductive bias complexity\" is very novel to my knowledge, and is also very interesting. \n3. Both theory and experiments are provided for understanding the proposed inductive bias complexity, which form the work in a rather mature shape. \n\n# Questions\nI think the work is very interesting and is worthy getting more attention from the community. I have the following questions/suggestions:\n\n1. I think Appendix C is crucial for understand the empirical results. Perhaps it is worthy to summarizing some of the important quantities (e.g., $m, \\\\delta, \\\\epsilon$), as well as the methodology for estimating them, and adding them into main text?\n\n2. I feel the \"inductive bias\" could have been formally defined. Based on my understanding, it refers to a restricted set of models (as a subset of the full hypothesis class) that can be outputted by some fixed procedures/code (or algorithms, with some fixed or tunable hyperparameters?). \n\n3. It might also be worthy to discussing the sources of randomness. To my understanding the randomness is from the randomly drawing of the training samples (correct me if not). How does the framework account the randomness in the learning algorithm? For example, people believe that the random nature of SGD encodes certain inductive bias. \n\n4. While I understand that the current theory might be in their ultimate sharp version, I would like to see some discussion on why the inductive bias complexity has an exponential dependence on the data dimension. Would you say this exponential dependence is fundamental and un-improvable or just technical? Could you discuss some intuition on the exponential dependence?\n\n5. Some discussion in Section 5.2 is not very clear. In particular, how do you use test data in computing the inductive bias complexity? Do you treat the test error as the $\\\\epsilon$ in your formula?\n\n6. I am curious how useful is the inductive bias complexity in practice, even though I think it is already very interesting in terms of theory. Let us say we are given with a training set and a task, what else do we need to compute the inductive bias complexity? Or how do we compare the inductive bias complexity to that of other dataset+task? What implication can we get, if we obtain some bounds/estimations on the inductive bias complexity?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DF5GUK3en6P", "reviewer": "Reviewer_NEm3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the amount of inductive bias needed to fit a dataset and derives a computationally feasible proxy for such a measure. In contrast to sample complexity, this metric aims to measure the difficulty of learning a given dataset, i.e. how much inductive bias needs to be present in order to achieve a certain level of generalization at a given sample size. The derived metric is largely agnostic to the model space and works for a very broad set of tasks, enabling the comparison of seemingly very remote tasks such as standard supervised learning on ImageNet and reinforcement learning.\n", "summary_of_the_review": "The idea of this work is very interesting, having a notion to estimate the amount of implicit bias needed to learn a dataset is very important and could lead to some new insights. In its current version however, I find this work very difficult to read and follow, large parts of the arguments are presented rather informally and the great generality of the result with only minimal assumptions on the data distribution seems somewhat surprising. More empirical evaluations for intuitively comparable setting would help the understanding as well. In summary, I have to recommend rejection of this work as in its current form, I find myself unable to confirm its validity, both theoretically and empirically. It is however very much possible that I have misunderstood parts of this work and I am happy to change my score if the authors can answer my questions.", "strength_and_weaknesses": "**Strengths**\n\n1. The idea to reverse roles and instead assess the difficulty of a task in a way agnostic to the model class used is very interesting. The term \"inductive bias” has been used very vaguely in the deep learning literature and a theoretically grounded measure for it is a very important contribution.\n\n2. The studied setting is very general and not many assumptions are made to arrive at a tractable metric for inductive bias. This makes this work applicable to a wide variety of problems.\n\n**Weaknesses**\n\n1. One of the major weaknesses of this work is its readibility. Large parts of the paper are very informally written (especially the entire section 4.2), which makes it very difficult to assess the validity of the results. I have listed my specific questions in the clarity section. I would greatly appreciate if the authors could clarify my concerns.\n\n2. While the great level of generality is certainly a strength of this work, it is also one of its bigger weaknesses. The data model which encapsulates a wide variety of tasks is very unintuitive and not easy to follow. While the authors explain in more detail how this model captures more specific settings in the appendix, I think more time could be spent in the main text to familiarize the reader with the framework. Walking through a simpler setting (i.e. supervised learning and Euclidean space) would be very helpful here.\n\n3. The setting of this work is extremely broad, the task considered can range from supervised learning to reinforcement learning, no assumptions on the training nor the test distribution are made, and the constructed hypothesis space also seems very general. While this is certainly a great feature of this work, it also remains unclear to me how much inductive bias can really be captured if so little assumptions are made on the data distribution. What happens for instance if instead of using clean targets on ImageNet, we study randomized targets, or varied the number of classes? What happens if we add Gaussian noise to input images and thus inflate the intrinsic dimensionality of the manifold? Do we really need to pay such a high price in terms of inductive bias? I think the results of this work would be easier to put into perspective if such settings were considered. It is not clear to me why Omniglot would require way more inductive bias than ImageNet as it is not so clear how to compare these two tasks intuitively. The authors give some insights by varying the sample size on the same task but somewhat un-intuitively, the amount of needed inductive bias does not decrease too much.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject