- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proves that, given a frozen set of document embeddings, learning the query encoder for a bi-encoder retrieval setup can be computationally hard under the Statistical Query (SQ) model. A few recent works showed that some cases are geometrically impossible, but this work discusses a setting where it is geometrically possible, meaning good embeddings exist (a perfect query encoder exists by construction in the paper's setting), but you simply can't learn them. The SQ model closely approximates mini-batch SGD (Abbe et al., 2021). The paper also includes some experiments to demonstrate the motivation for this problem, showing that we actually do observe cases where query encoders are difficult to train.
Critical strengths
This paper explores a question I've thought about myself, and I was surprised to see they present it in a very clear way. In bi-encoder retrieval, encoding documents is relatively easy to understand; it is essentially a form of information compression. But we actually know very little about how to encode queries. In practice, all we can do is learn from massive retrieval sample data, seeing which queries correspond to which documents, and learn patterns from all those statistics. Therefore, the setting they study is very natural, and they prove that learning query encoders can actually be hard. Furthermore, the setting closely mirror real-world training practices like mini-batch SGD. To a large extent, this work deepens my understanding of how we train embedding models.
Critical weaknesses
None. I don't see any weaknesses here that would make me lean toward rejection. The authors acknowledge some limitations of this work in Appendix A.
Questions for authors
These are just out of curiosity, and overall they won't change my (positive) assessment.
- My understanding is that SGD ≈ SQ relies on the batch gradient being an average of the per-sample gradients over i.i.d. samples. In practice, however, in-batch negatives are often used, so the samples are not i.i.d. (i) Could the authors clarify whether Section 3 uses in-batch negatives? (ii) Do you expect the SQ lower bound to extend to contrastive objectives with in-batch negatives?
- I'm curious how a negative result can inform practice (in a way that is more understandable to practitioners). Are there any practical tools to diagnose whether we are in the hard regime?
- Section 3.2 says all datasets were trained for a fixed 3,000 steps, but they vary in size, e.g., BRIGHT biology only has 72 queries, fiqa has 5,500. So the number of effective epochs is very different? If you have the compute to train them properly, that would be great...
2 comments
Thanks! I'll keep my positive score. Good luck!
We're glad you found the paper interesting, thanks for the thoughtful feedback (and for your patience)! To answer each of your questions:
In-batch negatives and the SQ model. Our experiments in Section 3 use a contrastive loss with full negatives where feasible (up to 200k total documents) and randomly sample 100k documents otherwise. One of the main reasons in-batch negatives are used is to avoid re-embedding many documents in each training iteration when training query and document embedding models simultaneously; training only a query encoder on a frozen document index avoids this efficiency problem.
That being said, our SQ lower-bound argument does extend to contrastive losses with in-batch negatives (for a fixed batch size B) with minor modifications. At a high level, we instead allow the SQ oracle to return the expectation of any [-1,1]-valued function of B iid (query, gold-center) samples within tolerance τ. The intent and null distributions over samples become DA⊗B and N0⊗B, respectively, and the same orthogonality argument gives a batch version of Lemma 4.5 with nB−1 replacing n−1. The downstream effect is that our statistical query lower bound in Lemma 4.4 will have a denominator of nB−1. This is polynomial in P for a fixed batch size, so the number of required statistical queries remains exponential in P.
Useful diagnostics in practice. As we do in the paper, a useful first step is determining the geometric capacity of the frozen index to diagnose whether poor retrieval performance is a consequence of document geometry or a learning failure on a particular task. Though we have no formal diagnostic for learning failures, one interpretation of our negative result is that it represents a worst-case setting in which semantic similarity between a query and document gives essentially no useful information about relevance to an SQ learner. This may suggest that hard settings are ones where semantic similarity is a poor proxy for query/document relevance, but this is not well understood and stands as an open direction for future work.
Epoch standardization. Thanks for catching this! We initially set a fixed number of steps because some datasets are too data-limited to do proper model selection. We will scale up the number of effective epochs for the larger categories to check whether they benefit from additional training. We don’t expect substantial changes to our overall results, as test recall peaked before the end of the original horizons on all but one category.