Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper asks the question “what makes a feature representation good for a target task?” In order to tackle this question, it introduces the concepts of local alignment (examples similar in feature space -> same labels), and congregation (how much examples generally embed close to each other). It uses them to produce bounds on achievable accuracy on binary classification problems which seem to be correlated with actual accuracy on real binary tasks.

main_review: Minor Comments

The paper is well written. The concepts presented are intuitive and seem useful. And their transferability to the empirical tasks chosen seems well demonstrated. As an empiricist, I defer to other reviewers when it comes to reviewing the theoretical proofs, but I can speak to the paper’s claims of practical application.

My main concern is that the empirical tasks chosen are very constrained classification problems (made into binary tasks by choosing pairs of classes; no multi-class fine-grained classification tasks as is more realistic). I understand the desire to start with a simple settings, especially in a theoretical paper, but it makes it hard to justify the paper’s claims of testing “what makes a [good] feature representation” and “impact[ing] practical decisions”.

Another question: how does one know if an embedding is not “congregated” unless there is a less-congregated frame of reference? The paper alludes that “congregation” might help explain the success of contrastive learning, so it’s disappointing to see no experiments trying to demonstrate this.

I also believe the paper would have been improved if the authors explicitly encouraged/discouraged local alignment/congregation when optimizing models, and showing that this changes the metrics introduced accordingly.

summary_of_the_review: This is a well-written paper that investigates a narrow task setting which unfortunately does not justify its claims of practical applicability. This could change with more extensive experiments in realistic datasets/settings.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work studies the relation between properties of the feature extractor, and the downstream performance on binary classification tasks.
The authors identify two key properties, namely "local alignment" and "congregation", which can be used to derive lower bound on the test accuracy and generalization bounds.
The theoretical results are verified empirically on CIFAR10 and CUB200.
main_review: Strength: the paper is clearly written and easy to follow. The observations make intuitive sense.

Questions:
  - How does the correlation between your lower bound and test loss compare with the correlation between kNN accuracy and the test loss?
  - How are the values of $p_{a}^{\phi}, p_{c}^{\phi}$ distributed empirically?
  - Empirically, how well can the lower bound predict the performance, when the learned representations are far from being clustered (for example, on representations from some lower layer of a network)?
  - For few-shot transfer, how would the performance change if we vary the number of training samples per class?
  - Do you have any recommendations on how to increase $p_{a}^{\phi}$ and decrease $p_c^{\phi}$ in practice?

Minor point: in equation (24), $\Delta$ should be $\epsilon$.
 

summary_of_the_review: The paper is clear and well justified.
However, I find the results unsurprising, since local alignment and congregation together mean that the features should be well clustered, which is intuitive and well known.
Personally I think the paper would need more technical contributions to be accepted.

=== Post rebuttal update ===

Based on the authors clarifications and additional experimental results, I have raised my score to 5. While I agree that the paper has improved after the revision and I acknowledge the contributions, it's still below the bar to me though only marginally.

Specifically, I am now convinced that the intuitive connection with knn is a plus, though I still think the theoretical novelty is limited.
Given the theoretical contribution, I'd expect stronger empirical results for the proposed method to be convincing. Potential improvements, as also mentioned by other reviewers, include 1) comparing with more baseline methods with a larger variety of features (e.g. expand Table 1 with results from other self-supervised methods, including non-contrastive ones), and 2) better justifying the criteria for model selection (i.e. the sum of the lower bound in Thm 1 and the upper bound in Thm 2) as it currently seems arbitrary.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper addresses the question of what makes a representation suitable or "good" for a particular task. The submission includes three data-dependent bounds: a lower bound on the average accuracy and two upper bounds on generalization. The analysis is based on the simple and intuitive concepts of local alignment and degree of congregation of the data points within a representational space and according to a binary labeling of the points. Two experiments support the theoretical claims.
main_review: strengths:

- The paper is very well written. The exposition is clear. The introduction makes very clear the specific challenges to be addressed in the paper and the approach taken.
- The description of the relationship to previous work is thorough and precise.
- Addresses an important question

weaknesses:

- limitations not well acknowledged/discussed. (As in any work of this sort) the presented results address a question that is narrower in scope than the one posed in the introduction. For example, the analysis assumes the relevant task is a classification task and so the results may not be relevant for reconstruction tasks or other regression tasks. The assumption that the scoring function is W -Lipschitz narrows what is meant by "good representation". It seems to imply that a good rep is one that is already appropriately disentangled, rather than one that can be disentangled by, say, a neural network (which would violate the assumption), to do something useful (or several useful things). A small point.
- Pearson seems more appropriate than Spearman correlation here since the the losses and errors are on an interval rather than ordinal scale.
- No statistical tests or confidence intervals on the correlations presented in the results.

minor comments:

- missing primes on x and y in second loss in the text between equations 7 and 8
- would be good to know to what extent your correlations are driven by the concentrations at the extremes in Figure 3.
- I don't think you need the line "Theoretical bounds are useless if they do not impact practical decisions."
- Not clear what representations were tested in the experiments without consulting the appendix. Consider moving a basic description to the main text.
- Consider adding subpanel titles (CUB-200, CIFAR-10) to Figure 4 to make it easier to grok. You could also include a more informative plot that a bar plot, e.g. show the distribution with box & whisker or violin plot, etc.
summary_of_the_review: The submission seems like a clear accept. It makes a clear contribution to an important topic and is very well written and clearly described. The statistical analysis of the empirical results could be improved. I made a number of minor comments that I think can be easily addressed to improve the quality of the paper. I have no major complaints.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents two properties, "local alignment" (eq 3) and "degree of congregation" (eq 4) which are claimed to be good predictors of downstream (classification) task performance. These properties are used to derive bounds on the error of downstream classifiers (under a number of assumptions, including a linea
r classifier with Lipshitz constraints), and are investigated empirically for pairwise classification tasks derived from the CIFAR-10 dataset, and for model selection on a few-shot task.
main_review: Defn 1: This should be defined more carefully, with (x,y)(x',y') ~ D. Also, not
e that this quantity could be defined conditional on x.

Defn 2: This should be defined more carefully, with x, x' ~ D.  Figure 1 contrasts lower (left 2 plots) and higher (right 2 plots) degree of concentration. However, as defined, p_c^{\phi}(\alpha) would depend on the scaling of the feature space. Although at the start of sec 3 we are told ||phi(x)|| \le B, this is never used below, so in fact this definition just serves to set the scale of the
 feature space. For example, it is easy to see that for a Gaussian p(x) in 1-d,
 this quantity will depend on the standard deviation of the distribution (and it is easy to extend the analysis to a multivariate Gaussian.) I suspect that the notion that is wanted here the entropy of p(x) relative to a Gaussian with the same mean and covariance, i.e. the negentropy https://en.wikipedia.org/wiki/N
egentropy , as the Gaussian has maximum entropy for a given mean and covariance
.

Notice also that a Lipshitz constraint only makes sense relative to the scale of the feature space. If we double its scale, then we need to half the Lipshitz 
constant to retain the same semantics.

Comment: I believe that the intuition behind Defn 1 is relevant to the issue of
 "what makes a feature representation good for a target task?", but am rather unconvinced by the subsequent analyses, for reasons explained below.


Claim 1: The derivation of eq 7 from eq 6 is incorrect -- the inequality in eq 
6 could also imply h(phi(x)) \le 1 + h(phi(x')) .  However I believe the claim in eq 5 is correct. Consider the functions \ell(h,+1) and \ell(h,-1) as a function of h. Eq 6 says that |h(phi(x) - h(phi(x')| \le 1, so we can "slide" one of these functions in h by (-1,1) relative to the other. The result is then intuitive.

However, I doubt that Claim 1 is of great practical use. The loss function (eq 2) is introduced because "the zero-one loss ... is difficult to analyze". However, Claim 1 depends critically on the "margin" for l(h,\pm 1) extending to h=\pm 1, and indeed the Lipshitz condition is specifically designed to exploit this margin to obtain eq 5. Thus I don't believe that this property is relevant to the zero-one loss we actually care about.

Theorem 1:

Written out more carefully, the required statement is Pr( ||phi(x) - phi(x')|| < 1/W AND y \neq y') = 
Pr( ||phi(x) - phi(x')|| < 1/W) \times Pr( y \neq y') | ||phi(x) - phi(x')|| < 1/W) .

We start my making the above statements *conditional on x* as mentioned for Defns 1 and 2 above, giving Pr( ||phi(x) - phi(x')|| < 1/W AND y \neq y' | x) = p^{phi}_c(alpha;x) \times (1 - p^{phi}_a(alpha;x)) , where the notation ;x indicates dependence on a particular x.

We can now try to average the expression p^{phi}_c(alpha;x) \times (1 - p^{phi}_a(alpha;x)) wrt D ~ x but an issue arises with the product term E_x [p^{phi}_c(alpha;x) p^{phi}_a(alpha;x)] which cannot be reduced to the product of the individual expectations.

Hence I believe there is a "bug" in this derivation for Theorem 1 as stated.

Another issue is that Theorem 1 depends only on the losses obtained when ||phi(x) - phi(x')|| < 1/W AND y \neq y', so other losses will be sustained for situations where this condition does not apply, so the bound may be very loose. Also as noted above it depends critically on the loss function used in eq 2, and so may have little relevance to the zero-one loss of interest.

Experiment 7.1: I am unclear if the loss you are reporting on the y-axis is the loss as per eq 2, or 0/1 loss -- please clarify. Also you don't state the alpha used (or how it was chosen), or the size of the training and test sets -- please expand (remember -- reproducible science!).

I realize that this is mainly a theory paper, but I believe the analysis of the experiments can be much improved. For a start you are only carrying out experiments on one dataset -- while for a more experimental paper we would probably look for say 10 datasets.

For the CIFAR-10 data, for each of the 45 tasks we have 18 different representations. For EACH of the 45x10 trials, one can compare the training and test losses for each of the 18 representations against the bounds. Strong evidence for the efficacy of the bound would be that the ordering of the observed losses would correlate well with the ordering of the bounds, over most of the 45x10 replications. So for example you could compute your Spearman's rho on the 18 datapoints, and make a histogram of the values obtained over the 450 expts.  As it is, such a fine-grained comparison is "washed out" in the plots in Fig 3.

The claim that a rho of 0.61 is much better than 0.56 is, I'm sorry to say, pretty silly -- just look how similar the plots in Fig 5 are.

Sec 7.2 considers a few-shot task -- here for model selection the new bounds are shown to give better performance than the H-score and TransRate. It is notable that these last two methods can perform worse than the Random baseline.

Further comments: It is worth noting that the "purity" of the classes in a given ball of radius alpha around phi(x) (as in Defn 1) is something that also arises in the "RadiusNeighborsClassifier" version of k-nearest neighbors, see e.g.  https://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbors-classification -- for this paper the radius is given by alpha.


Summary: While the intuition behind Definition 1 makes quite a lot of sense, there seem to be some errors in the derivation of Theorem 1. Also, importantly, it is not so clear that bounds on the loss from eq 2 will be well correlated with the 0/1 loss. (This could be investigated experimentally in sec 7.) The experiments could be carried out more thoroughly (as described above) to gain a better understanding of what is going on. Overall, my judgment is that this paper is not of ICLR standard.

** Other points

Eq 18: Is the 1/2W in eq (18) a typo for 1/W?

Eq 24: enhance readability by using larger brackets the P() statement on the LHS, as per the RHS.

p 7 para 2, defn of Rademacher complexity should contain \sum_i \sigma_i h(x_i) not \sum_i h(x_i)

== post rebuttal ===

I have already made comments on revised manuscript  (on 27 Nov) and the authors have responded to these.

Pros:

* the idea of relating performance/generalization to p_a and p_c seems useful.

* I like the new Fig 3 (as suggested by some of the reviewers and now implemented.)

Cons:

* As I've made clear before, I believe Thm 1 is unlikely to be of much import, as it makes use of the specifics of the "margin" of the
  loss in eq 2. I'd like to see more focus on 0/1 loss in the expts,  rather than the margin loss. (I note 0/1 loss results are promised
  for the camera ready version.)

* As I understand it, Thms 2 and 3 are not particularly novel (my understanding here is from other reviewers, I am not a learning theory
expert.)

* As pointed out by many reviewers, there does not seem to be a good  justification for the use of 100*lower bound + upper bound as a
  basis for model selection.

I am sticking with my updated score of 6.


  

summary_of_the_review: While the intuition behind Definition 1 makes quite a lot of sense, there seem to be some errors in the derivation of Theorem 1. Also, importantly, it is not so clear that bounds on the loss from eq 2 will be well correlated with the 0/1 loss. (This could be investigated experimentally in sec 7.) The experiments could be carried out more thoroughly (as described above) to gain a better understanding of what is going on. Overall, my judgment is that this paper is not of ICLR standard.

==updated===
see post-rebuttal summary.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to study how feature representations are transferable to downstream tasks. It presents a theoretical characterization of such transfer, in terms of relatively intuitive concepts of congregation and alignment. Specifically, it presents various bounds on classifier's expected error, probability of high-error inputs, and Rademacher complexity. The paper validates these theoretical observations by experiments with transfer in visual settings, between supervised tasks, or to few-shot (+unlabeled data) transfer. 
main_review: This paper is clearly written, and the bounds are fairly intuitive and well presented. However, I think that the paper would be improved with better experimental evaluation, and more discussion of the existing literature. 

Experimental evaluation
-------------------------

* The authors restrict their analyses to convenient representations they have from other work. While I share the author's desire for statistically rigorous experiments, the paper would be made much stronger if the authors demonstrated the validity of their approach with some existing representations, especially trained in different paradigms e.g. unsupervised. Even if the authors can't find multiple trained versions of the same architecture, just showing that their metrics e.g. predict how well SimCLR representations perform on different downstream tasks would improve the paper substantially. This would still allow a controlled comparison, since the source representations would be the same; it would just add another dimension of experiments to complement the present ones.

* Relatedly, this paper does not compare to the work of Nguyen et al. (2020) because it "assumes that representations come from classification tasks." This seems like a rather weak justification, since the present paper only evaluates representations pre-trained on classification (even if they sometimes do joint coarse + fine classification, one could apply the method of Nguyen et al. to the joint labels I believe). There may be other justifications for why the present method is superior (e.g. making use of unlabelled data); but demonstrating such benefits experimentally would improve the paper.

* While it can be useful to have transfer bounds that don't depend on training, computing the probabilities used in the bounds exactly involves pairwise comparisons, i.e. $O(N^2)$ computations over the data. For large supervised datasets it seems like the transfer estimates might be better from spending an equivalent amount of compute actually training a classifier on the data and seeing how well it did. I believe similar strategies are used in neural architecture search, because performance after e.g. one epoch of training is fairly strongly correlated with asymptotic performance. It would be useful for the paper to compare to such methods.

* I would also like to see some more analysis of how important the unlabelled data is in the few-shot setting, as this is fairly non-standard in the meta-learning literature. For example, the authors could vary the amount of unlabelled data, and plot the % accuracy drop correspondingly.


Literature
-----------

This paper would benefit from situating further within the existing theoretical literature on transfer. This work seems in several places to overlook prior theory work that considers generalization in ways that could be (or are) applied to understanding representations and transfer. Some of these papers may not conflict with this work or impact its novelty, but nevertheless might still be worth discussing. I've ordered the works that seem related to me in roughly what I see as the order of importance for addressing them.

* Petina & Lampert (2014) consider lifelong learning from a PAC-Bayesian perspective, including a representation transfer setting similar to that considered here. It would be useful to discuss any relationship between the bounds they express (taking the one-prior-task case from their work) and the present work.

* Arora et al. (2019, distinct from Arora's work cited in the paper) explore a "data-dependent complexity measure" that discriminates at least between random and true label distributions on real tasks, and is based on a characterization of failure probability in terms of Lipschitz functions. I haven't read this paper in detail, but superficially it seems very relevant to the present work, and it should probably be discussed.

* Cohen et al. (2020) consider object representation manifolds, and explore classification capacity in terms of the structure, extent, and relationships between these manifolds. These seems quite related to the notions used in this paper.

* Galanti et al. (2016) extend PAC bounds to the case of transfer and consider a few different cases. Their notion of transfer is a little different than explored in this work, since they consider simultaneous training with shared weights rather than classification of trained representations. However, it seems worth discussing.

* By making simplifying assumptions of linear hidden layers Advani et al. (2020) and Lampinen & Ganguli (2019) analyze learned representations and generalization in deep networks. The latter also consider some kind of transfer between tasks, though again shared weights rather than classification on trained representations. These results seem somewhat relevant, although they are within a simplified regression setting rather than classification.

* Schwartz-Ziv & Tishby (2017) explore representations in terms of their mutual information with the inputs and outputs, and the dynamics of how this MI evolves over training. While MI is less directly relevant to transfer, it could at least provide a lower bound th1at might be worth considering (i.e. transfer is impossible if no mutual information), and this work suggests it might be interesting to consider transferability partway through learning (e.g. perhaps representations are more transferable before the "compression" phase the authors describe).

It's also quite possible that there are even more relevant papers I've missed; I hope the other reviewers will share some. 

References
-----------

Advani, M. S., Saxe, A. M., & Sompolinsky, H. (2020). High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132, 428-446.

Arora, S., Du, S., Hu, W., Li, Z., & Wang, R. (2019, May). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning (pp. 322-332). PMLR.

Cohen, U., Chung, S., Lee, D. D., & Sompolinsky, H. (2020). Separability and geometry of object manifolds in deep neural networks. Nature communications, 11(1), 1-13.

Galanti, T., Wolf, L., & Hazan, T. (2016). A theoretical framework for deep transfer learning. Information and Inference: A Journal of the IMA, 5(2), 159-209.

Lampinen, A. K., & Ganguli, S. (2019). An analytic theory of generalization
dynamics and transfer learning in deep linear networks. International Conference
on Learning Representations

Pentina, A., & Lampert, C. (2014, June). A PAC-Bayesian bound for lifelong learning. In International Conference on Machine Learning (pp. 991-999). PMLR.


Shwartz-Ziv, R., & Tishby, N. (2017). Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810.


summary_of_the_review: The paper is clear and seems moderately useful; broader experimental evaluation and more engagement with the literature would improve it substantially.
review_title: null

Meta-review: In this paper, authors introduce two properties of feature representations, namely local alignment and local congregation, and show how these properties can be predictive of downstream performance. The paper has a heavier focus on providing theoretical statements using these properties but authors also empirically evaluate their suggested method.

**Strong Points**:
- The paper is well-written and easy to follow.


- The proposed concepts (local alignment and local congregation) are intuitive.


- The theoretical statements and their proofs are correct.


- The proposed metric shows some advantage against a few baselines.


- Prior work on feature representations and transferability are discussed.


**Weak Points**:


- **The connections to prior work on K-nearest neighbors and linear classifiers are not properly discussed.** This is very important because authors assume that the network that outputs the feature representations is trained on a different data and they reduced the analysis to that of a binary linear classifier. Hence, all classical learning theory results on binary classifiers apply in this setting. Furthermore, KNN methods and analysis can be simply applied on the features as well. In light of this and the lack of discussion on this matter, the significance of the theoretical and empirical results are not clear.


- **The main proposed properties could be improved further**. It looks like the defined properties (local alignment and local congregation) could be improved by merging them into one property about separability of data? The current properties are sensitive to scaling which is undesirable given that classification performance is invariant to scaling of the features. It seems like local congregation is mostly capturing the scale so some normalized version of local alignment might be able to capture the main property of interest.


- **The theoretical results in their current form are not very significant.** One limiting factor on the theoretical results is that since the analysis is done only on the classification layer, it does not say anything about the relationship of the upstream and downstream tasks. But perhaps the most important limitation is that the properties are defined based on the downstream task distribution as opposed to downstream training data. That makes it difficult to measure them in practical settings where we have a limited number of data points. Classical results on learning theory avoid this and only use measures that depend on the given training set.


- **The empirical evaluation could benefit from stronger baselines** Authors mentioned "We therefore consider only baselines that make minimal assumptions about the pre-trained feature representation and the target task" and hence avoided comparing to many prior methods. However, I think the appropriate approach would be to compare the performance of the proposed method to strong baselines but then explain how they differ in terms of their assumptions, etc. Moreover, there are other simple heuristic baselines to consider, eg. K-NN (which is not computationally expensive in the few-shot settings) or a classifier that is trained by initializing it to be the sum of feature vectors in the first class (assuming binary classification) minus sum of feature vectors in the second class and doing a few SGD updates on it. Therefore, I believe authors could improve the empirical section significantly by taking these suggestions into account.


**Final Decision Rationale**:

This is a borderline paper. While the paper has a nice combination of theoretical and empirical contributions, both theoretical and empirical contributions have a lot of room for improvement (and a clear path to get there) as pointed above. In particular, I believe having either strong theoretical contributions or strong empirical contributions would have been enough for acceptance and I hope authors would take the above suggestions into account and submit the improved version of this work again!
Decision: Reject