Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary.

This work tries to understand why features from trained language models can be used to solve classification tasks effectively. A language model (LM) in the analysis is modeled as a feature map $f : S \rightarrow \mathbb{R}^d$, a word embedding $\Phi \in \mathbb{R}^{d \times V}$, and a trained language model is thought of as $\epsilon$-optimal in terms of its cross-entropy (from the true distribution over S). The work shows that for classification tasks approximately solvable by linear functions over the distributions of the next token the best linear classifier based on $(f, \Phi)$ will suffer error of $O(\sqrt{\epsilon})$. The authors also propose an additional assumption where the log partition function is quadratic in $f$ based on which some improvements can be obtained. Being inspired by this assumption, a new objective function Quad where the partition function is directly replaced by a quadratic of $f$ is proposed. Experiments seem to support key assertions in the theoretical analysis.

Strengths.

1. The authors’ approach to a well-posed question seem original to me. In particular, some proposed concepts such as the refined transferability coefficient, conditional mean features, substitutability matrix might be useful for future studies.
2. The article is precise, well-written and cautious in its tone. The accompanying experiments are informative and supportive of the main theoretical claims. I enjoy the overall journey the authors presented and would love to see more well-reasoned articles like this in ICLR.

Weaknesses.

1. The presentation can be improved by allocating more space to ideas in the Extensions section. This part seems more creative (perhaps a little less coherent but expected for “a mathematical exploration”) but is too compressed as it stands. (See Suggestion1)

Minor issues.

1. Consider to replace “partial sentences” with prefixes, which is more technically accurate.
2. The many notations involving $p$ has inconsistent meanings for their subscripts. I would suggest to consolidate them to reduce confusion. For example, consider to use notations of this form $p(w|s; \theta)$. Perhaps boldface for when it is viewed as a vector. Similarly for $\ell$. (See Suggestion2)
3. Below section 2.1, “trained to learn” -> “trained to fit”.

Suggestions.

1. I think a moderate revision reducing some (parallel) elaboration on “unconstrained language model” should provide the space needed for Extensions (and other novel ideas). After all, I found results on unconstrained LMs somewhat trivial and I suspect that you hope to use it only as an instructional tool. Perhaps a serial layout would save space and even improve the perceived emphasis.
2. I strongly suggest a review of the notations and to adopt a more consistent scheme. One trick I found useful is to follow the notational convention of a textbook or a classic paper. The current notation has too much overloading and variability. 

Questions.

1. It seems to me that the central question lacks strong practical motivation. The NLP community seems to move to prefer a _natural_ answer (in the form of a generated sentence) instead of a label (from a classifier). As you have argued, many classification tasks can be framed as predicting the next token (perhaps in the presence of a prompt). What is your opinion? 
2. How realistic is the $\epsilon$-optimality condition on cross-entropy for LMs? Can you comment on any associated sample complexity bounds? 

// Post-rebuttal update:
Thank you for replying to my questions. I am still concerned about the sample complexity associated with $\epsilon$-optimality in cross-entropy (even in the trivial case, and perhaps impossible for some low-dim representations) as LMs are over a countably infinite extended alphabet.
review_title: A very interesting exploration indeed

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of review:

There have been lots of interests to understand why self-supervised learning approaches such as the next word prediction task learn a useful representation for downstream tasks. This paper provides a mathematical framework to understand this question. One novel finding of this paper is that the distribution of the next word, conditional on the context, can provide a strong discriminative signal for the downstream task. In particular, using a carefully selected subset of "prompt" words, the authors observe that learning a linear predictor over the next word distributions of these words achieves performance close to a pre-trained GPT-2 model.

Setting and Main Result:

This paper focuses on classification tasks, and the bulk of the work goes into how to model the next word distributions as features or representations. For this purpose, the authors introduced the definition of a "natural" task. Informally , a task is defined as natural if, just by using the next word distributions as features, the downstream task can be solved with a small loss.

Result 1: Under the above assumption over the downstream task, this paper provides a bound on the empirical loss of the downstream prediction task. This bound consists of two parts:
- The first part measures how "natural" the task is, that is, how well can the task be solved using the next word distributions as features.
- The second part measures the difference between the "empirical" next word distributions and the "optimal" next word distributions.

Result 2: The authors further extend this result to word embedding features, which are obtained by a weighted average of word embedding vectors based on the next word distributions.

There are several follow-up results built on these two results, such as a new loss objective for predicting the downstream task, but to the best of my understanding, these two results are the main claims of this paper.

A key parameter that occurs in obtaining the above results is a worst-case coefficient that bounds the distributional shift between language model distributions of the training dataset and that of the downstream task. Intuitively, this parameter arises from translating the "natural" task assumption, which only guarantees transfer on average to the downstream task.

Pros:

- A new framework for understanding why learning how to predict the next word helps the downstream task. This paper finds that the next word distributions of a subset of "prompt" words contain discriminative signals and are good features. This seems to be a novel finding and may help inspire future work in this important direction.

Cons:

- The main result (Thm 4.1) applies to next/conditional word distributions that are very close to the optimal distribution. It is unclear to me how the authors are going to justify this "assumption". Should we expect the empirical distribution to converge to the true distribution when there are an infinite amount of samples?

- Secondly, this main result depends on the worst-case coefficient, which is also unclear to me. For the transferability coefficient proposed in Section 5.1, is it possible to measure it in experiments? How large should we expect this coefficient to be?

Writing:

The writing is overall clear and easy to follow, although it took me quite some time to map out the definitions of various notations. Many of the notations look cumbersome and I suspect that there is still room for making the notations more accessible for new readers.


Detailed comments:

- P2, Sec 1.1: "analyze the efficiency language model features" -> analyze the efficiency of language model features

- P2, Sec 2: you started introducing these notations without explaining what they mean. For example, the $p^{\star}$ notation is also defined in Sec 2.1.

- P2, Sec 2: "where $p^{\star}_{\cdot | s}$ is used as a vector on the left and distribution on the right". What does this sentence mean?

- P3, Sec 2.2: "... achieve lower test perplexity than traditional n-gram models" Why is this true? Could you add a reference?

- P5, Sec 4.1: "The result suggests that small test cross-entropy (hence test perplexity)..." Same question as above.

- P6, Sec 4.3: "In fact, $f$ almost always performs better than ..." This part seems intriguing despite the linear relationship shown in figure 1. Could you discuss this more here?

- P8, Table 2: The results from using Quad look worse than the above two. Could you explain the significance of this result again?

- P24, Figure 2: What are the x and y axis, and what does each dot mean in this figure?
review_title: An interesting mathematical framework towards understanding language model representations

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper presents an explanation of why pretraining on language modeling (LM) helps performance on downstream text classification tasks. The explanation relies on formulating classification tasks as next word prediction tasks (i.e. language modeling). They use their theoretical results to design the Quad objective and experiment with it on SST and AG news, finding that it performs close but slightly worse than standard cross entropy training of classifiers.

Overall, this work contributes an interesting framework for analysis. However, I have one large conceptual concern about the framework. Central to the proposed explanation is the ability to formulate text classification tasks as next word prediction, possibly with a prompt appended to the input (e.g. for sentiment analysis of movie reviews, “This movie is “). In a trivial sense, this is always possible: We can simply append the task definition to the end of an input as a question (e.g. “Is the sentiment of the review positive?”) and check the probabilities of “yes”/”no”. Then predicting the answer to this prompt is equivalent to performing the task, and a perfect LM is of course able to perform the task perfectly. This formulation makes Sections 3 and 4.1 feel trivially true. Though, to the authors’ credit, they do have to do additional work to extend an LM that is eps-optimal in next word cross entropy (i.e. on average) to optimality on the specific task formulation. 

However, the authors don’t mention this trivial reformulation strategy and instead base their argument on the existence of heuristic words (e.g. for sentiment analysis, the probability of “:)” or “:(“ after a review). This strategy introduces the potential for spurious correlations: The heuristics might be strongly correlated with the task in general, but might be off due to other factors like sarcasm. Additionally, relying on these single-word heuristics seems a bit off to me, as many text classification tasks don’t readily admit single words that encapsulate the task definition or label semantics. There’s an argument, then, that the theory described here doesn’t apply to these tasks (i.e. they’re not (t, B)-natural), but what’s frustrating about this argument is that this theory doesn’t provide us a way to distinguish which tasks fall in the category of single-word predictable or how to find such words other than trial and error. 

It is very likely I am misunderstanding something about this paper. I am not sure what it means for a task to “lie in the row span of word embeddings”.

review_title: Interesting analysis framework and results but some conceptual concerns

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper studies why language model pre-training has been such an effective technique in improving downstream performance across a wide range of NLP tasks recently.  In particular, it considers language models which compute a probability distribution over the next word in a text, given the previous context.  Then, taking inspiration from recent work that shows that many downstream tasks can be reframed as sentence completion tasks, it defines a “natural task” as one on which a sparse linear model over the output of the “true” language model (next word probability distribution, conditioned on context) attains strong performance.  Theoretically, it shows that language models which are close to the “true” language model are guaranteed to attain strong performance on natural tasks.  Empirically, it demonstrates that several NLP tasks are “natural”.


**Strengths**
- The paper is generally quite clearly written and the claims are well-validated.
- The definitions, models, and assumptions in the paper are intuitive and clear (e.g., natural task).
- The analysis which builds on these definitions/models/assumptions provides meaningful theoretical insight into why language model pre-training may be so beneficial for downstream training.  It provides a nice theoretical framework for thinking about the connection between language models and downstream tasks, which future work could build on.
- The empirical validation is thoughtful and relatively thorough.  Even though the results don’t show that the proposed loss function and proposed “conditional mean features” give improvements over baselines, the empirical results show that the basic assumptions and definitions in the theoretical analysis are relatively realistic.  For example, Figure 4 validates Assumption 4.1 (log-partition function is roughly quadratic in theta), and Table 1 shows many real tasks are approximately “natural”.  Furthermore, when there is a gap between the empirical results and the theoretical results (e.g., validation of Lemma 4.3 at the end of Section 4), the paper makes these limitations clear, which I appreciated very much as a reader (paper does not over-claim its contributions).

**Weaknesses**
* Unclear if there are real practical applications to the insights from this paper.  Neither the proposed “Quad” loss function, nor the theoretically inspired “conditional mean features”, perform better than the baselines.
* The current analysis doesn’t apply directly to BERT, which is trained to predict masked words in a sentence, instead of the next word.  Furthermore, BERT doesn’t predict these masked words using a linear softmax model over a contextual embedding for the whole sentence, which is the assumed structure for the softmax language models considered in the analysis.  (This limitation is acknowledged in the conclusion, which is good).
* The paper doesn’t explain why learning a linear model directly on the context embeddings f(s) performs better than using the contextual mean embeddings.
  * One idea I had here: Could you define a natural task as one for which there exists a sparse linear model over the *logits* of p*( . | s) which performs well, instead of a model directly over p*( . | s)?  Due to the very “flat” portions of the softmax function, there can be meaningful differences between the logits corresponding to 2 different words, but the LM probabilities for those words are extremely similar (and thus, harder for a linear model to distinguish).  With this definition, a linear model of the logits is also a linear model over the context embeddings f(s) directly.
* There are some points in the paper that could be made clearer.
  * I think it should be discussed earlier (in intro/related work) why the paper focuses on language models which do next word prediction via linear softmax models over fixed dimensional context embeddings, and that BERT is out of scope.
  * I think there should be more discussion about the implications of Proposition 2.2.  As I understand it, this result shows that any part of p_f(s) orthogonal to row-span(Phi) doesn’t affect the cross-entropy of the language model (first order optimality condition would still be satisfied).  However, this doesn’t necessarily imply that p_f(s) will be in span(Phi) for all contexts s.  In particular,  the architecture of the embedding model f likely constrains f in such a way that makes it impossible for p_f(s) to be in span(Phi) for all contexts s.  Furthermore, at the end of section 3 it should be better explained why the assumption that p_f(s) is in span(Phi) for all s implies that Definition 3.2 should only consider sparse models v which are in this span as well (decompose v = v_in + v_out (component of v in the span, and orthogonal to the span), v^T p = (v_in + v_out)^T p = v_in^T p).
  * I found the discussion in Section 4.1 pretty confusing.  In particular the part that argued why B = O(1/alpha).

Overall, I really enjoyed reading this paper, and found it to be quite insightful.  It provided me with a much more thoughtful explanation for why language model pre-training improves downstream task performance, beyond simply “it helps learn good general representations of language using large amounts of unlabeled text data” (my previous reasoning).  As a result, I recommend acceptance for this paper.

NIT: 
- Grammar last sentence of Section 1.1 (“…analyze the efficiency *of* …”)
- Proposition 2.2: Maybe write “\forall s \in S” instead of “\forall s ~ p_L”.
- Section 3: ...append a prompt like “This movie is” (the final quotation mark is on the next line).
- Equation (5).  Use “sup” instead of “max”.
- Discussion in Section 4.1
- I think Figure 4 should be explained in more detail (in caption and/or text).
- Using capital and lower case tau in Theorem 4.2 is confusing notation.
- Similarly, using bold and not-bold B in Theorem 5.2 is confusing notation.
- After definition 5.1, what does Omega[w] = Omega[w’] mean?
- In Table 1, can you explain more explicitly (in caption and text) what “subset” and “class words” means? Also, can you add a column where a dense linear model over p_f(s) is used?
review_title: Insightful theoretical analysis on the benefits of language model pre-training.

final_score: rating: 7: Good paper, accept
review_content: **Summary**
This work relates a pre-training performance with a downstream performance for tasks that _can_ be reformulated as next word prediction tasks. The authors show that for such tasks, if the pre-training objective is $\epsilon$-optimal, then the downstream objective of a linear classifier is $\mathcal{O}(\sqrt{\epsilon})$-optimal.

**Strengths**
- To the best of my knowledge, this is the first work that _mathematically_ justifies the connection between the pre-training objective and the downstream performance.
- The proof technique (pre-training performance $\to$ covariance of pre-training errors $\to$ covariance of downstream errors $\to$ downstream performance) is itself interesting. If the paper is accepted I am looking forward to seeing a high-level proof sketch in the main part as is done in Section 2.1 of [Arora et al. (2015)](https://arxiv.org/abs/1502.03520). A three-line explanation at the end of Section 4.1 seems a bit scarce to me.
- The paper is well written: it gives an appropriate context, presents the main theoretical results, and verifies _some_ of the claims experimentally.

**Major concern**
If I understand correctly (and please correct me if I am wrong), in Theorem B.1, the ratio between the downstream error $\ell_\mathcal{T}(\\{p_{\cdot\mid s}\\}) - \tau$ and the pre-training error $\ell_\text{xent}(\\{p_{\cdot\mid s}\\})-\ell_\text{xent}^\ast$ is _hidden_ in the $\gamma(p_{\mathcal{T}}; \\{p_{\cdot\mid s}\\})$ coefficient. Let me elaborate on this:
1. In Lemma D.1 (with the help of Lemma D.9) you show that $\frac{1}{\gamma(p_{\mathcal{T}}; \\{p_{\cdot\mid s}\\})}$ is an upper bound for the ratio $\frac{\boldsymbol{v}^\top\Sigma_{p_{\mathcal{T}}}\boldsymbol{v}}{\boldsymbol{v}^\top\Sigma_{p_{L}}\boldsymbol{v}}$
2. The latter ratio seems proportional to the ratio $\frac{\ell_\mathcal{T}(\\{p_{\cdot\mid s}\\}) - \tau}{\ell_\text{xent}(\\{p_{\cdot\mid s}\\})-\ell_\text{xent}^\ast}$. I am not sure on this---my intuition is based on your Lemma D.2 and the fact that for a $p_{\cdot\mid s}$ with full support a non-precise reverse version of [Pinsker's inequality](https://en.wikipedia.org/wiki/Pinsker%27s_inequality#Inverse_problem) holds.

In a nutshell, aren't you showing that
$$\text{downstream error}=\mathcal{O}\left(\sqrt{\text{pre-training error}\cdot\frac{\text{downstream error}}{\text{pre-training error}}}\right)\qquad ?$$

**Issues**
- Why don't you verify the main claim---$\epsilon$-optimality in pre-training propagates as $\mathcal{O}(\sqrt{\epsilon})$-optimality on downstream---empirically?For this, you may want to vary the language modeling performance (e.g. by pruning the language model) and then verifying that the downstream loss increase is indeed $\mathcal{O}(\sqrt{\text{pre-training loss increase}})$. I believe such an experiment will definitely make the submission stronger.
- I don't see why your theory does not generalize to a _masked_ language modeling (MLM). Why do we need to treat $s$ as the left-context only? Given the success of MLM as a powerful pre-training objective, please consider formulating your claims in a more general way.

**Minor issues**
- At the beginning of Section 2.3, $p_{\mathcal{T}}$ is introduced as a distribution over $\mathcal{S}\times\\{\pm1\\}$, but later (e.g. in formula (5)), it is used as a distribution over $\mathcal{S}$ only. Please clarify/fix this.
- What is the "margin of task $\mathcal{T}$" mentioned on p.5? Is it a margin of an SVM classifier that solves $\mathcal{T}$?

**Limitations**
- The authors admit that their work is limited to a particular type of downstream tasks. Indeed, it is not clear how one can reformulate e.g. linguistic tasks (like POS-tagging or dependency parsing) as a next word prediction task.

**Update (after the author's response)**: During the rebuttal, the authors clarified my major concern, as well as provided additional experiments that verify the main claim of the paper. I am totally satisfied with the author's response, hence I am changing the score 6 $\to$ 7
review_title: A well-written paper that mathematizes an empirical fact

Meta-review: The paper attempts to provide a theoretical explanation for benefit of language model pretraining on downstream classification task. In this regard, the authors provide a mathematical framework which seems to indicate that the distribution of the next word, conditional on the context, can provide a strong discriminative signal for the downstream task. The reviewers found the formulation insightful, interesting, and novel. Also reviewers enjoyed reading the well written paper and appreciated its cautious in its tone. As correctly pointed out by reviewers, the proposed framework might not directly align with techniques used in practice. Applicability of the framework to other pre-training approaches is limited.  Also, there are some unresolved concerns about $O(\sqrt{\epsilon})$ assumption still. Nevertheless, reviewers reached a consensus that the framework would be beneficial for the community and attract follow-up works. Thus, I recommend an acceptance to ICLR. Following reviewer suggestion, it is strongly recommended that extensions section be expanded in the revised version using the extra page.
Decision: Accept (Poster)