- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies whether statistically equivalent learning problems can nevertheless have different streaming-memory complexity.
The setting is the following. Suppose we observe a sequence of labeled samples generated from an unknown target parameter , and we would like to recover or learn in a streaming setting with limited working memory.
The authors construct two learning problems that provide essentially the same statistical information about , but require different amounts of memory to learn. In the easy problem, the target can be recovered in one pass using bits of memory and polynomially many samples. In contrast, for the hard problem, any fixed-pass streaming learner requires bits of memory unless it uses exponentially many samples.
This shows that statistical equivalence does not necessarily imply similar streaming-memory complexity.
Critical strengths
- The problem is interesting, and the authors provide an explicit construction establishing the negative result.
Critical weaknesses
- The presentation is technically dense and may be difficult to follow for readers who are not already familiar with this area.
Questions for authors
see weaknesses
2 comments
Thank you for the response and the revision. I will keep my original positive score.
Response to Reviewer S4mx
We agree, and most of the revision addresses this. The introduction now builds up from the learning model, two elementary learners and the parity example, and explains Le Cam distance in words before the theorem (pp. 1–2). A new Section 1.1 explains what each block of the construction is for, and why the field-equation block is cheaper to store, before the technical sections (pp. 3–4). Undefined terms are glossed, clashing symbols renamed, and repetitions removed.
The review lists no specific soundness concern; if there is one, we would be glad to address it.