Evaluating representations by the complexity of learning low-loss predictors
Authors: William F Whitney
Min Jae Song
David Brandfonbrener
Jaan Altosaar
Kyunghyun Cho
Venue:  (2021)
Keywords: representation learning
representation evaluation
unsupervised learning
self-supervised learning

Abstract: We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest. To this end, we introduce two measures: surplus description length (SDL) and $\varepsilon$ sample complexity ($\varepsilon$SC). To compare our methods to prior work, we also present a framework based on plotting the validation loss versus dataset size (the "loss-data" curve). Existing measures, such as mutual information and minimum description length, correspond to slices and integrals along the data-axis of the loss-data curve, while ours correspond to slices and integrals along the loss-axis. This analysis shows that prior methods measure properties of an evaluation dataset of a specified size, whereas our methods measure properties of a predictor with a specified loss. We conclude with experiments on real data to compare the behavior of these methods over datasets of varying size.

Under review as a conference paper at ICLR 2021
EVALUATING REPRESENTATIONE BY THE COMPLEXITY OF LEARNING LOW-LOSS PREDICTORS
Anonymous authors Paper under double-bling review
ABSTRACT
We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning predictor top of the representation that achieves low loss on a task of interest. To this end, we introduce two measures: surplus description length (SDL) and sample complexity (=SC). To compare methods prior work, we also present a framework based on plotting the validation loss versus dataset size (the "loss-data" curve). Existing measures, such mutual information and minimum description length, correspond to slices and integrals along the data- axis of the loss-data curve, while ours correspond to slices and integrals along the loss-axis. This analysis shows that prior methods measure properties of an evaluation dataset of a specified size, whereas our methods measure properties of a predictor with specified loss. We conclude with experiments on real data to compare the behavior of these methods over datasets of varying size.
INTRODUCTION
One of the first steps in building machine learning system is selecting a representation of data. Whereas classical machine learning pipelines often begin with feature engineering, the advent of deep learning has led many to argue for pure end-to-end learning where the deep network constructs the features (LeCun al., 2015). However, huge strides in unsupervised learning (Hénaff et al., 2019; Chen et al., 2020; He et al., 2019; van den Oord et al., 2018; Bachman et al., 2019; Devlin et al., 2019; Liu et al., 2019; Raffel et al., 2019; Brown et al., 2020) have led to a reversal of this trend in the past two years, with common wisdom now recommending that the design of most systems start from a pretrained representation. With this boom in representation learning techniques, practitioners and representation researchers alike have the question: Which representation is best for my task?
This question exists as the middle step of the representation learning pipeline. The first step is representation learning, which consists of training representation function training set using an objective which may be supervised or unsupervised. The second step, which this paper considers, is representation evaluation. In this step, one uses measure of representation quality and labeled evaluation dataser to see how well the representation performs. The final step is deployment, in which the practitioner or researcher puts the learned representation to use. Deployment could involve using the representation on a stream of user-provided data to solve a variety of end tasks (LeCun, 2015), or simply releasing the trained weights of the representation function for general use. In the same way that BERT (Devlin et al., 2019) representations have been applied to whole host of problems, the task or amount of data available in deployment might differ from the evaluation phase.
We take the position that the best representation is the one which allows for the most efficient learning of a predictor solve the task. We will measure efficiency in terms of either number of samples or information about the optimal predictor contained in the samples. This position is motivated by practical concerns; the more labels that are needed to solve a task in the deployment phase, the more expensive to and the less widely applicable representation will be.
We build on a substantial and growing body of literature that attempts to answer the question of which representation is best. Simple, traditional means of evaluating representations, such as the validation accuracy of linear probes (Ettinger et al., 2016; Shi et al., 2016; Alain & Bengio, 2016), have been widely criticized (Hénaff et al., 2019; Resnick et al., 2019). Instead, researchers have taken

---

Under review as a conference paper at ICLR 2021
up variety of alternatives such as the validation accuracy (VA) of nonlinear probes (Conneau et al., 2018; Hénaff et al., 2019), mutual information (MI) between representations and labels (Bachman al., 2019; Pimentel et al., 2020), and minimum description length (MDL) of the labels conditioned on the representations (Blier & Ollivier, 2018; Yogatama et al., 2019; Voita & Titov, 2020).
VA, A
eSC, A
Representation Naisy labels Raw pixels
VA, B
eSC,
2
MI,
SDL, A
MI, B
SDL, B
MDL,
Small Large
MDL,
Loss
0.24
0.1
10
100
1,000
10.000
Small
Large
Infinite
Dataset size
Dataset size
Dataset size
(a) Existing measures
(b) Proposed measures
(c) Illustrative experiment
Each measure for evaluating representation quality is simple function of the "loss-data" curve shown here, which plots validation loss of a probe against evaluation dataset size. Left: Validation accuracy (VA), mutual information (MI), and minimum description length (MDL) measure properties of given dataset, with VA measuring the loss at finite amount of data, MI measuring at infinity, and MDL integrating it from zero to n. This dependence on dataset size can lead to misleading conclusions the amount of available data changes. Middle: Our proposed methods instead measure the complexity of learning a predictor with a particular loss tolerance. é sample complexity (eSC) measures the number of samples required to reach that loss tolerance, while surplus description length (SDL) integrates the surplus loss incurred above that tolerance. Neither depends on the dataset size. Right: simple example task which illustrates the issue. One representation. which consists of noisy labels, allows quick learning, while the other supports low loss in the limit of data. Evaluating either representation at particular dataset size risks drawing the wrong conclusion.
Figure 1:
We find that these methods all have clear limitations. As can be seen in Figure 1, VA and MDL are liable choose different representations for the same task when given evaluation datasets of different sizes. Instead we want an evaluation measure which depends on the data distributtio, not a particular dataset dataset size. Furthermore, VA and MDL lack a predefined notion of success in solving task. In combination with small evaluation datasets, these measures may lead to premature evaluation by producing judgement distinguish one representation from another. Meanwhile, MI measures the lowest loss achievable by any predictor irrespective of the complexity of learning it. We note that while these methods do not correspond to our notion of best representation, they may be correct for different notions of "best".
when there is not enough data to solve the task meaningfully
To eliminate these issues, we propose two measures. In both of our measures, the user must specify tolerance E so that population loss of less than E qualifies as solving the task. The first measure is the surplus description length (SDL.) which modifies the MDL. to measure the complexity of learning an e-loss predictor rather than the complexity of the labels in the evaluation dataset. The second is the E-sample complexity (sSC) which measures the sample complexity of learning an s-loss predictor.
To facilitate our analysis, we also propose framework called the loss-data framework, illustrated Figure 1, that plots the validation loss against the evaluation dataset size (Talmor et al., 2019; Yogatama et al., 2019; Voita & Titov, 2020). This framework simplifies comparisons between measures. Prior work measures integrals (MDL) and slices (VA and MI) along the data-axis. Our work proposes instead measuring integrals (SDL) and slices (=SC) along the loss-axis. This illustrates how prior work makes tacit choices about the function to learn based on the choice of dataset size. Our work instead makes explicit, interpretable choice of threshold e and measures the complexity of solving the task to E eтrоr. We experimentally investigate the behavior of these methods, illustrating the sensitivity of VA and MDL, and the robustness of SDL and sSC, dataset size.
Efficient implementation.
To enable reproducible and efficient representation evaluation for rep- resentation researchers, have developed highly optimized open source Python package (see
2

---

Under review as a conference paper at ICLR 2021
supplementary materials). This package enables construction of loss-data curves with arbitrary repre- sentations and datasets and is ligrary-.gnostic, supporting representations and learning algorithms implemented in any Python ML library. By leveraging the JAX library (Bradbury et al., 2018) to parallelize the training of probes on a single accelerator, our package constructs loss-data curves in around two minutes one GPU.
THE LOSS-DATA FRAMEWORK FOR REPRESENTATION EVALUATION
In this section formally present the representation evaluation problem, define loss-data framework, and show how prior work fits into the framework.
Notation. We bold letters to denote random variables. A supervised learning problem is defined by a joint distribution 'D over observations and labels (X, Y) in the sample space X' x y with density denoted by p. Let the random variable D be sample of i.i.d. (X, Y) pairs, realized by D = (X" ) = {II; 3))}=1 Let R denote a representation space and é X + R representation function. The methods we consider all use parametric probes, which are neural networks Po R + P(Y) parameterized by E IR that are trained on D to estimate the conditional distribution p(y x). We often abstract away the details of learning the probe by simply referring A()(D")). Abusing notation, we denote the composition of with by Ag. Define the population loss and the expected population loss for ý = (D"),, respectively as
to an algorithm A which returns predictor:
L( D
logp(Y X), (X
E
L(A,,n) ((AA.D)).
(1)
D
In this section we will focus on population quantities, but note that any algorithmic implementation must replace these by their empirical counterparts.
The representation evaluation problem. The representation evaluation problem asks us to define real-valued measurement of the quality of a representation ó for solving solving the task defined by (X, Y). Explicitly, each method defines real-valued function m(á. D, A. v) of representation Φ data distribution D. probing algorithm A, and some method-specifie set of hyperparameters V. By convention, smaller values of the measure correspond to better representations. Defining such measurement allows us to compare different representations.
2.1 DEFINING THE LOSS-DATA FRAMEWORK.
The loss-data framework is lens through which contrast different measures of representation quality. The key idea, demonstrated Figure 1, is to plot the loss L(Ag, n)) against the dataset size n. Explicitly, each n,, we train probing algorithm A using representation and then plot the loss of ý against n. Similar amalysis has appeared in Voita & Titov (2020); Yogatama al. (2019): Talmor al. (2019). We can represent each of the prior measures as points on the curve at fixed x (VA, MI) or integrals of the curve along the z-axis (MDL). Our measures correspond to evaluating points fixed y (eSC) and integrals along the y-axis (SDL).
produce a predictor
2.2 EXISTING METHODS IN THE LOSS-DATE FRAMEWORK
Nonlinear probes with limited data. A simple strategy for evaluating representations is to choose a probe architecture and train it on limited amount of data from the task and representation of interest (Hénaff et al., 2019; Zhang & Bowman, 2018). On the loss-data curve, this corresponds to evaluation at x = n, so that
mvA (b. D. D,A, m) = L(As, m).
(2)
Mutual information. Mutual information (MI) between representation ((X) and targets Y is another orten-proposed metric for learning and evaluating representations (Pimentel et al., 2020: Bachman al., 2019). In terms of entropy, mutual information is equivalent the information gain about Y from knowing (XX):
T(o(X): Y) (YY H(Y o (X)).
(3)
3

---

Under review as a conference paper at ICLR 2021
In general mutual information is intractable to estimate for high- digensiiensio continuous continuous-valued variables (McAllester & Stratos, 2020), and a common approach is to use very expressive model for p and maximize variational lower bound:
(((()); Y) 2 H(Y)
E logp(Y ((X).. (X.)
(4)
Since HY) is not a function of the parameters, maximizing the lower bound is equivalent to minimizing the negative log-likelihood. Moreover, we assume that f is expressive enough to represent p and take - co, this inequality becomes tight. As such, MI estimation can be seen special case nonlinear probes as described above, where instead of choosing some particular setting of n push it to infinity. We formally define the mutual information measure of representation as
(0 D,
lim n).
(5)
12-000
A decrease in this measure reflects an increase in the mutual information. On the loss-data curve, this corresponds to evaluation x oo.
Minimum description length. Recent studies (Yogatama et al., 2019; Voita & Titov, 2020) propose using the Minimum Description Length (MDL) principle (Rissanen, 1978; Grünwald, 2004) to evaluate representations. These works use online prequential code (Blier & Ollivier, 2018) to encode the labels given the representations. The codelength of y given ((X") is then defined as
{(Y" o(X"))
Σ ( (xx))),
(6)
where P; is the output of rumning pre-specified algorithm A on the dataset up element d: D = (XT v..) Taking an expectation over the sampled datasets for each i, we define a population variant of the MDL measure (Voita & Titov, 2020)
MMDL D, = e(Y" o(x)))
= -(A,))
1=1
Thus, MMDL measures the area under the loss-data curve on the interval x E [0.
3
LIMITATIONS OF EXISTING METHODS
Each of the prior methods, VA, MDL, and MI, have limitations that we attempt to solve with our methods. this section we present these limitations.
3.1 SENSITIVITY TO DATASET SIZE IN VA AND MDL
As seen in Section 2.2, the representation quality measures of VA and MDL both depend the size of the evaluation dataset. Because of this dependence, the ranking of representations given by these evaluation metries change increases. Choosing to deploy another by comparing these metrics at arbitrary n may lead to premature decisions in the machine learning pipeline since larger dataset could give different ordering.
representation rather than
A theoretical example. Let (0. be fixed binary vector and consider data generation process where the {0, 1} label of data point is given by the parity on s. i.e., y: = {a,, s) mod where yı {0, }} and E [0, Let yd {ir y be the given labels and consider the following two representations: (1) Noisy label: 2; = (I,, 8) + e, mod 2, where e; E {0,1) random bit with bias < 1/2, and (2) Raw data: Z4.
For the noisy label representation, guessing yi = 2, achieves validation accuracy optimal. On the other hand, the raw data representation will
a for any
which, is information-thhorrtiiee achieve perfect validation accuracy once the evaluation dataset contains d linearly independent x; In this case, Gaussian elimination will exactly recover The probability that set of n > d random vectors in {0, 1)dd does not contain d linearly independent vectors decreases exponentially n Hence, the expected validation accuracy for sufficiently larger than d will be exponentially close
4

---

Under review as a conference paper at ICLR 2021
to 1. As result, the representation ranking given by validation accuracy and description length favors the noisy label representation when n < d, but the raw data representation will be much better in these metrics when n > d. This can be misleading. Although this is concocted example for illustration purposes, our experiments in Section show dependence of representation rankings on n.
3.2 INSENSITIVITY TO REPRESENTATION QUALITY & COMPUTATIONAL COMPLEXITY IN MI
MI considers the lowest validation loss achievable with the given representation and ignores any concerns about statistical or computational complexity of achieving such accuracy, This leads to some counterintuitive properties which make MI an undesirable metric:
1. MI is insensitive to statistical complexity. Two random variables which are perfectly predictive of one another have maximal MI, though their relationship may be sufficiently complex that it requires exponentially many samples to verify (McAllester & Stratos, 2020).
2. MI is insensitive to computational complexity. For example, the mutual information between intercepted encrypted message and the enemy's 's plan is high (Shannon, 1948; Xu et al., 2020), despite the extreme computational cost required to break the encryption.
3. MI is insensitive to representation. By the data processing inequality (Cover & Thomas, 2006), any & applied to can only decrease its mutual information with Y; no matter the query, MI always reports that the raw data is at least as good as the best representation.
3.3 LACK OF PREDEHNED NOTION SUCCESS
All three prior methods lack predefined notion of successfully solving task and will always return some ordering representations. When the evaluation dataset is too small or all of the representations poor, it may be that representation can yet solve the task. Since the order of representations change as more data is added, any judgement would be premature. Indeed, there is often an implicit minimum requirement for the loss representation should achieve to be considered meaningful. As we show in the next section, our methods makes this requirement explicit.
4 SURPLUS DESCRIPTION LENGTH & SAMPLE COMPLEXITY
The methods discussed above measure property of the data, such the attainable accuracy points, by learning an unspecified function. Instead, we propose to precisely define the function of interest and measure its complexity using data. Fundamentally about the inputs of an algorithm, like VA and MDL do, to a statement about the outputs.
shift from making statement
4.1 SURPLUS DESCRIPTION LENGTH (SDL)
Imagine trying to efficiently encode large number of samples of a random variable e which takes values in {1 ... K} with probability p(e). An optimal code for these events has expected length' E[((e)] = E.{ log)(e) = (e). If this data is instead encoded using probability distribution p. the expected length becomes (e)) + DxI. (p p). We call DKL. (p p) the surplus description length (SDL. from encoding according instead of p:
DKt. (p p)
E emp
[log log ((c))
(8)
When the true distribution is delta, the entire length of a code under و is surplus since log 1 = 0.
Recall that the prequential code for estimating MDL computes the description length of the labels given observations in dataset by iteratively creating tighter approximations f1... P.. and integrating area under the curve. Examining Equation (7), we see that
(MDL( D,A.n) (e,
Σ
T(A 2
H(Y ((X)).
(9)
in nats
5

---

Under review as a conference paper at ICLR 2021
If HY ((X)) O, MDL grows without bound the size of the evaluation dataset n increases.
Instead, we propose to measure the complexity of a learned predictor p ((X)) by computing the surplus description length of encoding infinite stream of data according to the online code instead of the true conditional distribution.
Definition 1 (Surplus description length of online codes). Given random variables X, Y D, representation function o, and a learning algorithm A. define
MSDLL A)
i) x))
(10)
We generalize this definition to measure the complexity of learning an approximating conditional distribution with loss rather than the true conditional distribution only:
Definition (Surplus description length of online codes with an arbitrary baseline). Take random variables X. Y D, a representation function é, a learning algorithm A, and a loss tolerance & 82 H X). Let [c]+ denote max(0, c) and then we define
mSDL (,
i)
(11)
In our framework, the surplus description length corresponds to computing the area between the loss-data curve and a baseline set by y = E. Whereas MDL measures the complexity a sample of points, SDL measures the complexity of function which solves the task to tolerance.
Estimating the SDL. Naively computing SDL would require unbounded data and the estimation of L(As,) i) for every i. However, if we assume that algorithms are monotonically improving so that L(A, + 1) s L(A, i). SDL only depends on up to the first point where L(A, n) I E. Approximating this integral can be done efficiently by taking log-uniform partition of the dataset size and computing the Riemann sum as in Voita & Titov (2020). Crucially, if the tolerance is implementation is able to
set too low or the maximum amount of available data is insufficient, report that the given complexity estimate is only a lower bound. In Appendix A we provide a detailed algorithm for estimating SDL,, along with theorem proving its data requirements.
4.2 SAMPLE COMPLEXITY (=SC)
In addition to surplus description length we introduce a second, conceptually simpler measure of representation quality: e sample complexity.
Definition 3 (Sample complexity of an e-loss predictor). Given random variables X, Y ~ D, a
representation function learning algorithm A, and a loss tolerance 2 H(Y ((X)), define
mesc(á, D, min {u E N: I(A,, n) se].
(12)
Sample complexity measures the complexity of learning an E-loss predictor by the number of samples it takes find it. In our framework, sample complexity corresponds to taking horizontal slice of the loss-data curve at y = e, analogous to VA. VA makes statement about the data (by setting n) and reports the accuracy of some function given that data. contrast, sample complexity specifies the desired function and determines its complexity by how many samples are needed to learn it.
Estimating the =SC. Given an assumption that algorithms are monotonically improving such that L(A, n + 1) < L(A,n), sSC can be estimated efficiently. With finite samples in the dataset, an algorithm may estimate eSC by splitting the data into uniform-sizen bins and estimating L(A, dk/o) for i E {1. k}. By recursively performing this search the interval which contains the transition from L > = to L < E, we can rapidly reach a precise estimate or report that mcsc(ó. (ó, A, =) > n. more detailed examination of the algorithmic considerations of estimating cSC is in Appendix B.
Using objectives other than negative log-likelihood. Our exposition of =SC uses negative log- likelihood for consistency with other methods, such as MDL, which require it. However, it is straightforward to extend ESC to work with whatever objective function is desired under the assump- tion that said objective monotone with increasing data when using algorithm A.

---

Under review as a conference paper at ICLR 2021
4.3 SETTING
A value for the threshold corresponds to the set of e-loss predictors that representation should make easy to learn. Choices of = 2 HY X) represent attainable functions, while selecting HH X) leads unbounded SDL and =SC for any choice of the algorithm A.
For evaluating representation learning methods in the research community, we recommend using SDL and establishing benchmarks which specify (1) a downstream task, in the form of dataset; (2) a criterion for success, in the form of a setting of E; (3) a standard probing algorithm A. The setting of be done by training a large model on the representation of the full dataset and using its validation loss as e when evaluating other representations. This guarantees that & 2 H(Y X) and the task is feasible with good representation; in turn, this ensures that SDL bounded.
In practical applications, e should be part of the design specification for a system. As an example, a practitioner might know that an object detection system with 80% per-frame accuracy is sufficient and labels are expensive. For this task, the best representation would be one which enables the most sample efficient learning of predictor with error 0.2 using a loss.
Representation
CIFAR
Pixels
VAE
60
Val loss
0.88
1.54
0.70
Representation CIFAR
MDL
122.75
147.34
93.8
Pxxes
SDL,, 5=1
65.33
87.34
40.75
600.2
110.75
135.34
81.8
Test loss
eSC, s=1
60
> 60.0
38
aSC, ==0.2
60.0
> 60.0
>
60.0
20398
Val loss MDL
0.05
0.11
0.14
0.1
1607.95
3876.88
3360.49
SDL, s=1
65.33
93.06
40.75
SDL, ==0.2
153.49
800.16
278.95
100
1,000
10,000
Dataset size
eSC, c=1
60
147
38
eSC, ==0.2
884
8322
3395
Figure 2: Results using three representations on the MNIST dataset.
EXPERIMENTS
We empirically show the behavior of VA. MDL, SDL, and =SC with two sets of experiments on real
data. For the first, shown in Figure the last hidden layer of a small convolutional network pretrained on CIFAR-10 0; (2) raw pixels; and (3)
evaluate three representations MNIST classification: (1)
variational autoencoder (VAE) (Kingma & Welling, 2014; Rezende et al., 2014) trained on MNIST.
For the second experiment, shown in Figure 3, we compare the representations given by different layers of pretrained ELMo model (Peters al., 2018) using the part-of-speech task introduced by Hewitt & Liang (2019) and implemented by Voita & Titov (2020) with the same probe architecture and other hyperparameters as those works. Note that in each experiment we omit MI as for any finite amount of data, the MI measure is the same validation loss. Details of the experiments, including representation training, probe architectures, and hyperparameters, are available in Appendix C.
These experiments demonstrate that the issue of sensitivity to evaluation dataset size in fact occurs in practice, both on small problems (Figure 2) and at scale (Figure 3): VA and MDL both choose different representations when given evaluation sets of different sizes. Because these measures are a function of the dataset size, making a decision about which representation to use with small evaluation dataset would be premature. By contrast, SDL and =SC are functions only of the data distribution, not a finite sample. Once they measure the complexity of learning an e-loss function, that measure invariant the size of the evaluation dataset. Crucially, since these measures contain

---

Under review as a conference paper at ICLR 2021
notion of success in solving task, they able to avoid the issue of premature evaluation and notify the user if there is insufficient data to evaluate and return lower bound instead.
ELMo layer
0
2
461
Val loss
0.73
0.72
0.85
Representation
MDL
1213.98
1313.75
1320.52
ELMo ayee 0
ELMo ayer
SDL, ==0.5
283.75
334.43
366.35
Mo
SDI,, ==0.1
472.15
522.83
554.75
Test loss
eSC, ==0.5
461
> 461
461
eSC, ==0.1
> 461
> 461
461
0.2-
474838
Val loss MDL
0.17
0.08
0.09
92403.41
52648.50
65468.54
SDL, ==0.5
338.48
365.25
450.84
100
1,000
10,000
100,000
SDL, ==0.1
> 42162.47
2922.04
8734.11
Dataset size
<SC, =05
1256
854
1446
eSC, 6=0.1
> 474838
149946
474838
Figure Results using three representations on a part of speech classification task.
RELATED WORK
Zhang & Bowman (2018) and Hewitt & Liang (2019) propose random baselines for linguistic tasks provide context for how much linguistic structure readily accessible representations. To show separation between the validation accuracy achieved by these random baselines and representations pretrained on genuine linguistic labels, they have to limit the amount of training data or restrict the capacity of probes. As an alternative, Voita & Titov (2020) propose using the MDL framework, which measures the description length of the labels given the observations, to demonstrate the separation between pretrained representations and random baselines. An earlier work by Yogatama et al. (2019) also uses prequential codes to evaluate representations for linguistic tasks. Foundational work by Blier & Ollivier (2018) introduces prequential codes as measure of the complexity of a deep learning model. Talmor et al. (2019) look at the loss-data curve (called "learning curve" in their work) and use weighted average of the validation loss at various training sizes evaluate representations.
DISCUSSION
In this work we have introduced the loss-data framework for comparing representation evaluation measures and used it diagnose the issue of sensitivity evaluation dataset size in the validation accuracy and minimum description length measures. We proposed two measures, surplus description length and sample complexity, which eliminate this issue by measuring the complexity of learning a predictor which solves the task of interest to E tolerance. Empirically we showed that sensitivity evaluation dataset size occurs in practice for VA and MDL, while SDL and cSC are robust the amount of available data and are able to report when it is insufficient to make judgment.
Each of these measures depends on choice of algorithm A, including hyperparameters such as probe architecture, which could make the evaluation procedure less robust. To alleviate this, future work might consider a set of algorithms A {A: J.K and a method of combining them, such as the model switching technique of Blier & Ollivier (2018); Erven et al. (2012) a Bayesian prior.
Finally, while existing measures such as VA, MI, and MDL do not measure our notion of the best representation for task, under other settings they may be the correct choice. For example, if only a fixed set of data will ever be available, selecting representations using VA might be a reasonable choice; and if unbounded data is available for free, perhaps MI is the most appropriate measure. However, in many cases the robustness and interpretability offered by SDL and eSC make them practical choice for practitioners and representation researchers alike.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alain, G. and Bengio, Y. Understanding intermediate layers using linear classifier probes. Interna- tional Conference on Learning Representations, 2016.
Bachman, P., Hjelm, R. D., and Buchwalter, W. Learning representations by maximizing mutual
information actoss views. In Advances in Neural Information Processing Systems, 2019.
Blier, L. and Ollivier, Y. The description length of deep learning models. In Advances in Neural Information Processing Systems, 2018.
Bradbury, J., Frostig. R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., and Wanderman- Milne, JAX: composable transformations of Python+NumPy programs, 2018. URL http: //github. soom/googlee jax.
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P. Sastry, G., Askell, A., Agarwal, S., Perbert-Vosss A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCand lish, S., Radford, A., Sutskever, I,, and Amodei, D. Language Models are Few-Shot Learners. arXiv preprint arXiv:2005. 2020.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, E. A simple framework for contrastive learning of visual representations. arXiv preprint 2rXiv:2002.05709, 2020.
Conneau, A., Kruszewski, G., Lample, G., Barrault, L.,, and Baroni, M. What you cram into single $&!#* vector: Probing sentence embeddings for linguistic properties. In Annual Meeting of the Association for Compulational Linguistics, pp. 2126-2136, 2018.
Cover, T. M. and Thomas, J. Elements of information theory. Wiley, 2006.
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Association for 2019.
Computational Linguistics, pp.
Erven, T.. Grünwald, P., and Rooij. S. Catching up faster by switching sooner: A predictive approach to adaptive stimation with an application the aic-bic dilemma. Journal of the Royal Statistical Society. Series B (Statistical Methodology), 74, 06 2012.
Ettinger, A., Elgohary, A., and Resnik, P. Probing for semantic evidence of composition by means of simple classification tasks. In Workshop on Evaluating Vector-Space Representations for NLP, pp. 134-139, 2016.
Grünwald, A tutorial introduction the minimum description length principle. arXiv preprint math:0406077, 2004.
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Momentum contrast for unsupervised visual representation learning. arXiv preprint 1rXiv:1911.05722. 2019.
Hénaff, J., Razavi, A., Doersch, C., Eslami, S. M. A., and van den Oord, A. Data-efficient image recognition with contrastive predictive coding, arXiv preprint NXXi:1905000972 2019.
Hewitt, and Liang, Designing and interpreting probes with control tasks. In Empirical Methods Natural Language Processing and International Joint Conference on Natural Language Processing, pp. 2733-2743, 2019.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. CoRR, abs/1412.6698 2015.
Kingma, D. P. and Welling, M. Auto-encoding variational Bayes. International Conference on Learning Representations, 2014.
LeCun, Y.
Deep learning convolutional networks.
URL: https://
hwt.hips............oo 24 http:h/ccc...ciooooooooooooo/oaa
htwub//cC7.222 190 150.:o/wwhiitttooaaaeeeaaaaaaeee 2015.

---

Under review as a conference paper at ICLR 2021
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature, 521(7553):436 444, 2015.
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L.., and Stoyanov, V. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXiv; pet.:.907.11110 2019.
McAllester, D. and Stratos, K. Formal limitations on the measurement of mutual information. International Conference on Artificial Intelligence and Statisties, 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J.. Chanan, G., Killeen, T., Lin, Z.. Gimelshein,
N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., Vito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang. L.., Bai, and Chintala, S. Pytorch: An imperative style, fighperformance deep learning library. In NewrlPS, 2019.
Peters, M.. Neumann, M. lyyer, M., Gardner, M., Clark, C., Lee, K., and Zeitlemoyer, L. Deep con- textualized word representations. North American Chapter of the Association for Computational Linguistics, pp. 2227-2237, 2018.
Pimentel, T., Valvoda, J., Maudslay, R. H., Zmigrod, R., Williams, A., and Cotterell, R. Information- theoretic probing for linguistic structure. arXiv preprint arXiv:2004.0306/ 2020.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: 1910. 10683, 2019.
Resnick, C., Zhan, Z., and Bruna, J. Probing the state of the art: A critical look at visual representation evaluation. arXiv preprint arXiv:1912.00215. 2019.
Rezende, D. J., Mohamed, S., and Wierstra, D. Stochastic backpropagation and approximate inference in deep generative models. In International Conference Machine Learning, 2014.
Rissanen, J. Modeling by shortest data description. Automatica, 14:465-471, 1978.
Shannon, C. A mathematical theory of communication. Bell Syst. Tech. J., 27:379-423, 1948.
Shi, X., Padhi, I., and Knight, K. Does string-based based neural MT learn source syntax? In Empirical Methods in Natural Language Processing, pp. 1526-1533 2016.
Talmor, A., Elazar, Y., Goldberg, Y., and Berant, J. oLMpics-on what language model pre-training captures, arXiv preprint 1rXiv:1912.13285 2019.
van den Oord, A., Li, Y., and Vinyals, O. Representation learning with contrastive predictive coding. arXiv preprint arXiv: /807.03778 2018
Voita, E. and Titov, I. information-tthoreet probing with minimum description length. arXiv preprint 20Xi::0003.12298, 2020.
Xu, Y., Zhao, S., Song, J., Stewart, R., and Ermon, S. A theory of usable information under computational constraints. In International Conference on Learning Representations, 2020.
Yogatama, D., d' Autume, C. d. M., Connor, J., Kocisky, T., Chrzanowski, M., Kong, L.,, Lazaridou, A., Ling, W., Yu, L., Dyer, C., et al. Learning and evaluating general linguistic intelligence. arXiv preprint arXiv: 1901. 1173, 2019.
Zhang, K. and Bowman, S. Language modeling teaches you more than translation does: Lessons learned through auxiliary syntactic task analysis. In EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 359-361- 2018.
10

---

Under review as a conference paper at ICLR 2021
APPENDIX A
ALGORITHMIC DETAILS FOR ESTIMATING SURPLUS DESCRIPTION LENGTH
Recall that the SDL is defined
MSDL (,,,, - Σ [(Ab.n)
-
(13)
n=1
For simplicity, we assume that L bounded in [0, 1]. Note that this can be achieved by truncating cross-entropy loss.
Algorithm 1: Estimate surplus error
Input: tolerance e, max iterations M, number of datasets K, representation o, data distribution D, algorithm A Output: Estimate fn of m(0, D,,,A) and indicator / of whether this estimate is tight lower bound
Sample K datasets DS D of size M
for n to M do
For each is E [K], run A on D [1][1 n] to produce predictor pi Take K test samples (Ix: yk)) = D [M + 1]
Evaluate Ln 1 Ek=1 E Tk.
Set EM - +e+
L.M & 5//2 then Set I t ght else Set / lower bound; return m.
In experiments replace Di n] of Algorithm I with sampled subsets of size from single evaluation dataset. Additionally, we use between 10 and 20 values of n instead of evaluating L(A,, n)) at every integer between 1 and M. This strategy, also used by Blier Ollivier (2018) and Voita & Titov (2020), corresponds to the description length under a code which updates only periodically during transmission of the data instead of after every single point.
Theorem 4. Let the loss function be bounded in [0, 1] and assume that it is decreasing in n. With (M + 1)K datapoints, if the sample complexity is less than M, the above algorithm returns estimate in such that with probability at least 8
log log(2M/()
Im - ml, S My
(14)
2K
K > log(1/6) and the algorithm returns t tht then with probability at least 1 the sample 22
complexity is less than M and the above bound holds.
Proof. First we apply a Hoeffding bound to show that each i,, is estimated well. For any n, we have
(L
log log(2M/0) 2K
< 2eepp
-2K
- 2K log (2M/))
2
5
8
(15)
2K
2M
M
since each Elitt Fk. yk) is independent variable, bounded in [0,1] with expectation I(Ag,n).
11

---

Under review as a conference paper at ICLR 2021
Now when sample complexity is less than M, a union bound to translate this to high probability bound on error of m, so that with probability at least
M
mm - m(6, E, =
Σ
Lnn - =|++ [L(A,, 12) - =]+
(16)
n=1
M
[Ln =E++ [L(Ap, n2) - -E4+
(17)
n=1
Σ
Ln n()
(18)
(2g)2
SMV
(19)
2K
This gives us the first part of the claim.
We want to know that when the algorithm returns t tight, the estimate can be trusted (i.c. that we set M large enough). Under the assumption of large enough K, and by an application of Hoeffding, we have that
P P(I(A,, LMs > e/2 s exp (-2Ke²)
(
log(110) 2²
x²) = )²
exp -
(20)
If LM S E//2, this means that L(Ag, M) S with probability at least - 8. By the assumption of decreasing loss, this means the sample complexity less than M, so the bound on the error r holds.
APPENDIX B ALGORITHMIC DETAILS FOR ESTIMATING SAMPLE COMPLEXITY
Recall that sample complexity (sSC) is defined
min fIE:: e)
se).
(21)
We estimate mesc via recursive grid search. To be more precise, we first define search interval [1, NN. where N a large enough number such that L(Ag. N) < Then, we partition the search interval in to 10 sub-intervals and estimate risk of hypothesis learned from D ~ D with high confidence for each sub-interval. We then find the leftmost sub-interval that potentially contains m.sc and proceed recursively. This procedure is formalized in Algorithm 2 and its guarantee is given by Theorem 5.
Theorem 5. Let the loss function bounded in [0, 1] and assume that decreasing in n. Then, Algorithm 2 returns an estimate in that satisfies mesc(Ó D, A, S in with probability at least 1 8.
Proof. By Hoeffding, the probability that 1.n L(Ag, n)] 2 E/2, where İ is computed with S 2 loog(200 (20k / independent draws of D Dr and (x. y) DD is less than 6/ 6/(10)). The algorithm terminates after evaluating Î on at most 10k different n By union bound, the probability that [ L(As, n:) S e/2 for all used by the algorithm at least 5. Hence, i.n S 8/2 implies L n)) < E with probability at least 1 8 8.
L
APPENDIX C EXPERIMENTAL DETAILS
In each experiment we first estimate the loss-data curve using a fixed number of dataset sizes and multiple random seeds, then compute each measure from that curve. Reported values of SDL correspond the estimated area between the loss-data curve and the line y using Riemann sums with the values taken from the left edge of the interval. This is the same as the chunking procedure of Voita & Titov (2020) and is equivalent to the code length of transmitting each chunk of data using
12

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Estimate sample complexity via recursive grid search
Input: Search upper limit N, parameters E, confidence parameter ó, data distribution D, and learning algorithm A.
Output: Estimate in such that mesc(Ø, D,A, vn with probability -
let S = 2 (0lgo(0k/6)///
and let [f, u| be the search interval initialized at N. for j = to 10 do
for r = to & do Partition [e, u) into 10 equispaced bins and let A be the length of each bin.
Set m = (+jA
Compute Ln Ei ((A(D)), 24, 24) for S independent draws of D and test
sample (z, y).
Ln S e/2 then
Set u and f= n A A.
break
return m = u, which satisfies mesc( D, A, S vn with probability 6, where the randomness is over independent draws of D and test samples (x, v).
fixed model and switching models between intervals. Reported values of =SC correspond to the first measured which the loss is less than e.
All of the experiments were performed on single server with 4 NVidia Titan X GPUs, and on this hardware no experiment took longer than an hour, All of the code for our experiments, as well that used to generate plots and tables, is included in the supplement.
C.1 MNIST EXPERIMENTS
For our experiments on MNIST, we implement a figghl-peefformnn vectorized library in JAX to construct loss-data curves. With this implementation it takes about minute to estimate the loss-data curve with one sample at each of 20 settings of n. We approximate the loss-data curves at to
20 settings of log-uniformly spaced on the interval [10, 50000] and evaluate loss on the approximate the population loss. At each dataset size n we perform the same number of updates to the model; we experimented with early stopping for smaller n but found that it made no difference on this dataset. In order to obtain lower-variance estimates of the expected risk at each n, we run 8 random seeds for each representation at each dataset size, where each random seed corresponds to random initialization of the probe network and a random subsample of the evaluation dataset.
Probes consist of wwo-hideen-layer MLPs with hidden dimension 512 and ReLU activations. All probes and representations are trained with the Adam optimizer (Kingma & Ba, 2015) with learning rate 10-4
Each representation is normalized to have zero mean and unit variance before probing ensure that differences scaling and centering not disrupt learning. The representations of the data we evaluate are implemented follows.
Raw pixels. The raw MNIST pixels are provided by the Pytorch datasets library (Paszke et al., 2019). It has dimension 28 x 28 784.
The CIFAR representation is given by the last hidden layer of convolutional neural network trained the CIFAR-10 dataset. This representation has dimension 784 to match the size of the raw pixels. The network architecture as follows:
CIFAR.
nn nn. (1, 32, 3, 1),
nn. nn.ReLU (), nn Mn.MaxPool2d
(n.Con2dd 64, 1),
nn.ReLU nn.MaxPoll2d (2),
13

---

Under review as a conference paper at ICLR 2021
nn.Flatten Ln.Linear (1600, 784)
nn.ReLU()
In. (784, 10)
In.ioggSottaa ()
VAE. The VAE (variational autoencoder; Kingma & Welling (2014); Rezende et al. (2014)) repre- sentation given by a variational autoencoder trained to generate the MNIST digits. This VAE's latent variable has dimension 8. We use the mean output of the encoder as the representation of the data. The network architecture is as follows:
self. eeld_eeccder_aaeer nn. Sequential mn Ln.Linear (784, 400),
nn.ReLU
Ln.Linear (400, 400), nn.ReLU (), In. (400, 400), (n.
self mean nn. (400, 8) self.varianes nn.Linear (400, 8)
self. self.decoder_ dayeeedereerr_eeeess layers nn.Sequential nn Ln.ein (8, 400),
nn.ReLU(),
Ln.Line (400, 400), nn.ReLU In. (400, 784),
C.2 PART OF SPEECH EXPERIMENTS
We follow the methodology and use the official code? of Voita & Titov (2020) for part of speech experiments using EL (Peters et al., 2018) pretrained representations. In order to obtain lower- 4 random seeds for each representation
variance estimates of the expected risk each n., at each dataset size, where each random seed corresponds to a random initialization of the probe network and random subsample of the evaluation dataset. We approximate the loss-data curves at 10 settings of n log-uniformly spaced on the range of the available data E [10, 10%] To more precisely estimate eSC, we perform one recursive grid search step: we space 10 settings over the range which in the first round saw L(Ag, n)) transition from above to below
Probes consist of the MLP-2 model of Hewitt & Liang (2019); Voita & Titov (2020) and all training parameters are the same as in those works.
Phttps:/ wttp./coo//eea--otttaa/a///////a ot 1n
14


Reviews:
[{"review_id": "fZlgfBFBzPm", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary of the paper:\nThe paper discusses new measures to evaluating the quality of representations.\nThey present two new measures namely SDL and $\\epsilon$-sample complexity, describe their benefits and apply experimental study, comparing these measures to standard baselines.\n\n* Comments\nThe suggested measures are simple modifications of existing baselines (MDL,MI).\nThe authors emphasize that their measures are independent of dataset size $n$, but this only applies when $n$ is large enough and when $\\epsilon$ is a good estimate of the conditional entropy.\n\nThe authors also mention two issues regarding existing measures (MDL,MI)\n- They are insensitive to statistical complexity\n- They are insensitive to computational complexity\nwhile these are true for the theoretical measures, I don't see what is the benefit of the current measures in this context. This is since old and new measures are leaning on an approximate  computation of $L(A,i)$.\n\n\n*Summary of review\nI don't see any clear benefit of the suggested measures.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RSRyFi7TPoH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors address the issue of evaluating the quality of representations based on performance of a classifier for a downstream task. The premise is that conventional metrics for the downstream classifier such as Validation Accuracy, MDL or MI are flawed due to dependence on the size of the dataset (VA, MDL) or because they ignore statistical/computational complexity of the classifier (MI).\nThe alternatives proposed in the paper SDL/\\epsilon-SC, which attempt to measure the complexity of learning the classifier to \\epsilon-tolerance.\n\nThe core premise is reasonable. The metric/evaluation of the representation should not depend on the amount of data available for the downstream task. However, it seems like the proposed alternative replaces an arbitrary dataset size, with an arbitrary loss threshold (small values of \\epsilon may lead no measurement (infinity for both SDL and \\epsilon-SC), while larger values of \\epsilon may also lead to arbitrariness. The authors do say that the they want an evaluation measure which depends on the data distribution, but seem to not pay sufficient attention to the \"distribution\" part (measurements are noisy, and we should understand what is noise, and what is a significant improvement, possibly by computing confidence intervals). The authors specifically mention a downside of MI is that it ignores computational complexity of the classifiers, but that seems to be a valid complaint of their approach as well (presumably more (computationally) complex classifiers can achieve a loss threshold), though their approach does address the issue with statistical complexity. \nThere are other issues - there are typically many tasks that we might want to use a common representation for. The arbitrariness of epsilon makes combining evaluations across different tasks difficult. Further, we typically have a fixed amount of data for each downstream task - it would seem that the approach proposed here would require an arbitrary amount of data for each task, which may not be feasible.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AQCkrWrrtc8", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission addresses the problem of representation evaluation from the perspective of efficient learning of downstream predictors. Leveraging the introduced loss-data curve framework, the paper studies and demonstrates the limitations of the existing methods in terms of their implicit dependency on evaluation dataset size. Motivated by practicality and interpretability of the measures for choosing the best representations, the paper introduces two novel methods, $\\epsilon$ sample complexity ($\\epsilon$SC) and surplus description length (SDL), which are well-motivated and supported both theoretically and empirically. The paper also delivers efficient implementation.\n\nThe paper has excellent motivation and discussion about how existing methods are inconsistent with representation quality, computational complexity and are not robust when evaluation dataset size changes—thus deeming them inapt to answer practical questions. For example, how hard is it to learn a predictor on the given representation? How many samples with given the representation are needed to achieve a specified performance? Is it even possible to reach a specified performance given this representation?\nThe proposed methods are designed to handle these questions and are robust to the evaluation dataset size secured against precipitate decisions on which representation is best. The paper considers the best representation to be the one that allows the most efficient learning of a downstream predictor.\n\nAlthough I do not immediately see weak points, yet the following things should be taken into account when applying the proposed methods — the assumption of monotonically improving predictors, the dependency of the proposed and existing methods for representation evaluation on the probe design, and potential disagreement between $\\epsilon$SC and SDL (as seen in Figure 3 for $\\epsilon=0.5$).\nAlthough very plausible, the assumption might not hold when there is a sufficient shift between training and validation data. There might be situations when representations may overfit to training data and not reflect properties of validation set points, potentially causing problems in both proposed methods. While dependency on the predictors is addressed in the paper as a separate problem and a direction for future work, it would help if the authors discussed the cases when there is a disagreement between $\\epsilon$SC and SDL.\n\nOverall, this submission seems to be a solid contribution and should be accepted as it rigorously addresses a problem of representation evaluation, which is of broad interest to the ICLR community.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of evaluating representations and proposes two new metrics: surplus description length and epsilon sample complexity.

Pros:
- A good overview of existing methods and their corresponding weaknesses (i.e. sensitivity to dataset size and insensitivity to representation quality and computational complexity).
- The proposed procedures seem to be well-supported conceptually.
- Has an efficient implementation.

Cons:
- While the theoretical results in the Appendix are appreciated and do provide some insight into the procedures, they more or less seem straightforward and don't answer some important questions (i.e. what is the sample size necessary in terms of epsilon? is it exponential in some dimension?). 
- More insight could have been provided into where the noisy measurements come from in these metrics as there appear to be many components in the calculations that could be contributing to the noise (i.e. dataset distribution, dataset size, bootstrap samples, probe initializations, etc).
- The methods make an assumption that the performance is monotonic in the dataset size, which is often not the case (i.e. there is a subfield regarding removing noisy label examples to improve performance; moreover there are investigations in the active learning literature that suggest sometimes performance degrades with more training data).
- It appears that the proposed metrics are based on data efficiency (i.e. least number of samples to get obtain a desired performance). However, such may have more of a dependence on the distribution of the data and how the examples are chosen (i.e. they can be actively chosen) moreso than the actual representation. This may or may not be an issue but may deserve at least some discussion.

Overall, the reviewers appreciated the new methods proposed and how they relate and improve upon previous methods; however, as currently presented, most were unconvinced about its significance which was a key reason for rejection. 

Decision: Reject