This paper builds on the motivation that context vectors from a language model, such as BERT, often cluster into separate groups for the same next word. These clusters may correspond to different senses of the word, and often have varying variances. The authors argue that a traditional softmax is not expressive enough to capture these clusters. A similar argument was made by Yang et al in their Mixture of Softmax (MoS) paper. The solution presented here is quite different though -- to allocate multiple senses to each word in the output embedding table, and to use a parameterized kernel to model the variance. The ideas are pretty neat, and as far as i know, original.

This work proposes an approach to accommodate multiple senses of words as different embeddings. Reviewers' positive assessment was influenced by the additional experiments and results provided in the authors' response, so authors are definitely expected to incorporate those (or results to the same effect) in the final version.

Weaknesses: - My major concern is why the problem is difficult. Assumption 1 literally enforces that the adversary cannot pick arbitrary S, but only those such that a constant alpha-fraction of the observations are hidden/removed. Thus, suppose before removal we have a total of m samples (a, y). After removal it reduces to alpha * m pairs (a, y), which still suffices for accurate recovery provided that m O(k log n). - It is not convincing to me that the sample complexity in Theorem 3.1 is near-optimal. I know that O(k log n) is near-optimal, but does your result really imply such bound?

The truncated setting is interesting both in practice and theoretically. The reviewers uniformly felt that this is an interesting paper, and a good contribution to the community.

Weaknesses: I believe the paper could present more context around the results in sections 4.2 through 4.4. What other results exist in these settings? Similarly, the numerical experiments are not discussed at all and are hard to interpret. I find it hard to draw conclusions from these experiments. I would recommend the description of the algorithm be moved ahead of section 4. Section 4 is hard to judge on the first read as the algorithm generating the claimed results is not yet presented.

Three referees reviewed the paper, and initially raised several concerns. However, the rebuttal did address and overcome the reviewer's objections, leading to a unanimous final decision to accept the paper.

Clarity: The paper writing is very good, but I find several small problems related to notations, which could make confusion: - Between line 108-109, the authors use both the \bf\xi with a supscript "t" and the \bf\xi without a supscript "t", I guess for the latter the authors mean a general batch of samples does not depend on "t", but it is not explained clearly. Also, sometimes it has "i" in the supscript while othertimes it has "i" in the subscript. However, the reuse of the same notation really makes me confused for a while since it looks like \xi is some element belong to \bf\xi or \bf\xi'. Is this a proof artifact? It makes more sense that if we want to do an averaging here, the w_t's should better have different weights such that the recent updates get higher score.

The paper is a theoretical analysis of the behaviour of "echoed gradients" in convex optimization. The investigation is timely, and will cast light on an interesting area of current practice. More than one reviewer believes the paper should explicitly handle the non-convex case. I disagree, and side with the authors that the convex case is sufficient. The relevant non-convex optimizers generally contain convex stepping as a subprogram, so this analysis is reasonable.

Originality As far as I can tell, the authors' claim that this is the first such work is correct. Previous work has been done is describing heuristics or empirical understandings of such behaviour, but the work is nonetheless original in proving a theoretical basis for this. Quality The authors' exposition of the problem and the solution is well thought out and expertly laid out in a logical and convincing form. However, the excellent technical contribution is somewhat lacking in discussion, particularly given the authors aim to bridge the gap between theory and practice; such claims as "This new consequence may serve an important guide for practical considerations" warrant a standalone discussion section which is not provided. Further, the results predicted in theory could have been compared to empirical experiments to show tightness in practice, and phase transitions could be shown in experiments as a demonstration.

This is a very interesting paper, which presents a comprehensive theoretical analysis of metric dimensionality reduction. It describe existing distortion measures in terms of moments of distortions and give an average case performance guarantee for these moments of distortion. Also, an approximate algorithm with provable guarantees on metric dimensionality reduction is introduced. The main objection on this paper was the absence of empirical evidence to support the claims. The authors have conducted additional experiments in the rebuttal phase but there are missing details regarding the experiments. The authors are advised to improve the quality of their paper in light of the reviewers' comments and incorporate their recommended changes.