Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies machine learning in settings where where classes have rare subcategories (potentially as small as one example in the training set).

The paper creates a data model, and shows that while a model that properly learns features can achieve very high performance, models that do not learn these features have very low accuracy. Error bounds are derived for this data model, and experiments showing similar behavior with other models are performed.
strength_and_weaknesses: Strengths

 - The model is relatively straightforward to understand, and it is relatively intuitive to understand why it is critical to learn the features.
 - The performance differences between learning and not learning the features are  very dramatic.

Weaknesses

 - The theoretical section of the paper is somewhat difficult to follow. There are many variables that I had to look back to recall, and the derivations sometimes lack descriptive text around it to help guide the reader.
 - The model is somewhat synthetic. While it does highlight the importance of learning categories in this particular data model, it is relatively unclear to me how directly this generalizes to other NLP problems and image problems.

clarity,_quality,_novelty_and_reproducibility: The motivation and data model of this paper are very clear, while the formal claims and derivations could be improved.

To the best of my knowledge, the data model and results are novel, and the results seem reproduceable.
summary_of_the_review: The paper introduces a data model where the performance of machine learning heavily depends on learning the categories of each word. While the results do highlight the importance of feature learning in this data model, my impression is that the data model is still relatively far from real problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper derives generalization error bounds that are non-asymptotic and relatively tight against long-tailed problems, within the context of our data model, through mathematical analysis and partial empirical evidence.
strength_and_weaknesses: Strength: 
1. The effectiveness of the method has been proved by mathematical analysis and empirical experience.
2. The method can be used for long-tailed problems in the field of both CV and NLP.
3. The paper puts novel theoretical results that can inspire future theoretical research on long-tail problems.

Weaknesses:
1. The experimental results are too few to illustrate the effectiveness of the method.
2. Although the detailed proof process is given in the appendix, the idea of the text is a bit jumpy.
3. The method in this paper is based on the nearest neighbor or SVM, which requires neural networks to extract features for learning. However, the extraction process is a black-box model, and it is difficult to combine the features extracted by the deep network with the method in this paper without mathematics analysis and experimental verification in this regard.

clarity,_quality,_novelty_and_reproducibility: The clarity and quality of the text are ordinary. Specifically, the logic of the proof and reasoning process in the text is not clear, and the necessary reasoning process is lacking in the main text
However, the novelty and originality are good, the idea given is inspiring and novel.

summary_of_the_review: Being a novel research in the field of CV and NLP, especially some parts do not have strict mathematical analysis, but rely on experience, and more experimental results should be provided to support the conclusion. In addition, the legends in the article are not rich, which is not conducive to reading and understanding. More graphical explanations should be added appropriately. Finally, as a very mathematical article, important reasoning procedures should be included in the main text rather than all listed in the appendix.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a simple data model of a classification task (a model that generates a training and testing set), and use it to demonstrate the theoretical importance of learning task-specific features (transformation of input features) to achieve good generalization performance on a specific task. The model relates to the commonly encountered long-tail distribution of data, by assuming a low number of examples in the train set for each category/class and test set containing unobserved before examples (not present in train set), what is common for a long-tail (the unbalanced that is also a characteristic for long-trail distributions is not touched here). In such a setting, intuitively learning features is required to achieve a good result. First, the authors use their model to confirm that by showing that on a given task, the nearest neighbor classifier achieves a perfect score when given optimal features representation results using experimental comparison. Later the authors show that it's not possible to find feature representation that will generalize well for all tasks from a set of all possible (with the assumed data model with the same parameters) when using the nearest neighbor classification. The authors derive the bond on the expected error on a task from a set of all possible ones. Finally, these findings are confirmed by empirical experiments, where the authors compare the performance of two settings. In the first, a neural network was used to learn features for a specific task, and mean performance on these tasks is reported, as expected, this gives low mean error. In the second setting, one general feature map is used for all tasks, as expected, resulting in a very high mean error.
strength_and_weaknesses: Strengths:
+ The paper is well-written, mostly easy to understand, and technically sound.
+ The theoretical findings are nicely confirmed by empirical experiments.
+ The very comprehensive appendix nicely explains the proofs and some other details (unfortunately, I haven't yet had time to go through everything).
+ The paper matches the main themes of the conference very well.

Weaknesses:
- The main conclusions of the work are not surprising, I believe this is the well-known fact that tail-distributions require better feature learning and was kind of confirmed empirically in many domains. While I find this as a nice theoretical confirmation, at the moment, I don't see any other application/implications of this work. The derived error bound is just for the proposed model, which is too simple to be used as a model for any real dataset.
- Based on the abstract I was hoping that the authors will use the model to try to answer some more interesting questions like: what error can we expect if we will use the same feature for a set of similar tasks?
- Among all the nice proofs and details in the appendix, I lack the proof for Theorem 2.
- Some important details are in the appendix. e.g., the experimental section is much clearer after reading the corresponding appendix section. I would suggest moving the description of parameters to the appendix and describing the better experimental protocol in the main paper.

NITs:
- In section 2, the example with 3 concepts could use different colors to mark words from the same concept, I believe this would make it even easier to read/understand quickly.
- Some small language mistakes I noticed:
  - from a different point view -> from a different point of view
  - intances -> instances
  - The former represent/the latter represent -> represents?
  - data generative process itself more coherent -> data generative process itself is more coherent 
  - We would like to emphasis one more time -> We would like to emphasize one more time
  - one just need -> one just needs
  - Our experiments shows -> Our experiments show
  - There are missing comas in phrases like "In ...," in some places.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly-written and technically sound. The idea of using a data model that is simple enough that can be analyzed in a combinatorial way is simple. But I don't know many papers that are doing that. So in this sense, I find this work original and more interesting to read than more common works about a new algorithm improvement that brings another eta improvement on some benchmark. The experiments should be easy to reproduce from the description + the code is provided by the authors.

summary_of_the_review: I find this paper very difficult to rate, I think it is interesting, from the point of view of the technique and the proof, maybe because I'm not very familiar with similar works. On the other hand, I'm not sure how this work may impact further research. Convinced by the high quality of the writing, at the moment, I'm leaning toward accepting this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel model of data, and shows that under the proposed model, a model can only succeed if it performs feature learning. Specifically, the primary data model proposed in the paper involves a set of concepts, each with an equal number of vocabularies. There is an $R$ number of categories (or classes). Each category contains two sequences of concepts. The first concept sequence, $c_r'$, is “unfamiliar” which accounts for a small portion of the generated data (i.e., long tail of the distribution) and the second concept sequence, $c_r$, is “familiar” which accounts for the majority of generated data (i.e., the head of the distribution). At training time, for each sample, the model first samples a concept sequence, and then generates a sequence of vocabularies corresponding to the concept sequence uniformly. At test time, the model only samples from the tail of the distribution. The paper then proceeds to show that on this data model, generalization error on the test distribution be lower bounded by a combinatorial quantity and using this lower bound, the paper shows in certain configurations of the data distribution, the test error can be arbitrarily high. Finally, the paper demonstrates, through simple experiments on an instantiation of the proposed data model, that the test error of models which do not learn features is much higher than neural networks which learn features.
strength_and_weaknesses: ### Strength
1. The paper proposes a fairly novel model for deep learning in certain long-tailed distributions that argues for the importance of feature learning
2. The theoretical result is sound as far as I can tell and the proof techniques are novel for this area (although I did not have the time to go through all the details of the appendix given the short period of review).
3. The story is convincing, and I can tell that the authors have taken great care to make the paper as clear as possible in spite of its highly complicated nature and novelty (although there are still parts of the paper that are unclear)

### Weakness
1. It is unclear how well the proposed model reflects real world problems. Some empirical evidence would strengthen the paper.
2. There seems to be a disconnect between the theoretical part and empirical verification (please correct me if I am wrong).
     - Based on my understanding, the theoretical result precludes **any** feature map $\psi$ that maps the sentence to features, which presumably includes those learned by neural networks so it is weird that the experiments suggest something otherwise. In a similar vein, I find the claim to be too strong to be useful. 
    - I spent a lot of time trying to understand the previous point and I came to the conclusion that (I believe) the tasks used in the experiments only have a single $\varphi$. Is this correct? If that is the case, how does the experimental section fits into the theoretical framework which uses $\Phi$ that include **all** partition functions.
    - How does the theory change if I have only **one** partition function $\varphi$?
    - I am concerned that this disconnect makes the theoretical results less useful than it appears to be.
3. The test error is not iid but in practice the model would presumably still get most of the data correct if the test distribution is the same as training distribution.
4. The paper doesn’t have a conclusion.

### Questions
1. Can you provide more explanation on how one should interpret the optimal feature map $\psi^\star$?
clarity,_quality,_novelty_and_reproducibility: **Clarity** The paper is pretty clear although some aforementioned points can be improved.

**Quality** The quality of paper is above average but there are some problems which I brought up above. 

**Novelty** The paper as far as I can tell is very novel but it resembles previous works in some of the long-tail assumptions.

**Reproducibility** The paper contains sufficient details for the experiments to be reproduced.

summary_of_the_review: The paper proposes a very interesting data model that advocates for the importance of learning features and shows models that do not learn features cannot do well on the tail of the distribution. However, currently, there seems to be a gap between the theoretical results and empirical results which I could not resolve after reading the paper multiple times. As such, my current assessment of the paper is slightly below the threshold and look forward to hearing the authors’ response.


## Update
The paper is much clearer after the revision and I think the paper is definitely interesting enough for the theoretical community. I decide to increased my score to 8.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the importance of learning features to achieve good generalization in the setting where the data distribution has a long tail. 

The reviewers agreed the paper provides a detailed theoretical study, under a simple long-tailed data model, to study the importance of learning features to achieve good generalization. Such an intuition seems to have been known empirically, and is highly practically relevant, and this appears to be the first work to give a framework in which to formalize this intuition.

If accepted, we encourage the authors take the reviewers' feedback into consideration, especially with regards to clarity and further discussion around the relevance and impact of these theoretical results.

justification_for_why_not_higher_score: Reviewers had some reservations of the impact on wider ML community, which may make this less appropriate for a spotlight/oral.
justification_for_why_not_lower_score: Solid theoretical contribution about a known empirically observed phenomenon. In the discussions, all reviewers were willing to accept (although some of them may not have updated their scores).
Decision: Accept: poster