Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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).
The alternatives proposed in the paper SDL/\epsilon-SC, which attempt to measure the complexity of learning the classifier to \epsilon-tolerance.

The 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. 
There 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.



review_title: Review for "Evaluating representations by the complexity of learning low-loss predictors"

final_score: rating: 4: Ok but not good enough - rejection
review_content: *Summary of the paper:
The paper discusses new measures to evaluating the quality of representations.
They present two new measures namely SDL and $\epsilon$-sample complexity, describe their benefits and apply experimental study, comparing these measures to standard baselines.

* Comments
The suggested measures are simple modifications of existing baselines (MDL,MI).
The 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.

The authors also mention two issues regarding existing measures (MDL,MI)
- They are insensitive to statistical complexity
- They are insensitive to computational complexity
while 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)$.


*Summary of review
I don't see any clear benefit of the suggested measures.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: 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.

The 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?
The 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.

Although 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$).
Although 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.

Overall, 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.
review_title: Good discussion and motivation, well grounded methods, accept

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