- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies the minimum memory required by a sequential estimator when observations about past states may arrive late. For the class of finite-state HMMs considered, the results establish matching upper and lower bounds on the persistent memory needed for any prescribed estimation accuracy.
Critical strengths
This paper raises an interesting distinction between prediction and revision by studying information unnecessary for a predictive task but not for later corrections. The matching upper and lower bounds derived substantiates the technical contributions.
Critical weaknesses
-
I think the writing is ok but could be better. There are multiple disclaimer statements such as "proof establishes the existence of constant; it does not provide numerical threshold" that can be collectively put in a single section in the appendix as opposed to scattered in the main text. On the other hand, the paper could be improved by stating the exact set of assumptions for each statement, as well as elaborating on proof intuitions.
-
The scope is relatively narrow. Main results apply to a restrictive observation and dynamics class assuming known, positive, invertible finite-state transitions and locally rich on-time likelihood fields
Questions for authors
How representative are the histories and late observations driving the lower bound under the model’s observed distribution? Since the packing construction uses a neighborhood that shrinks with horizon, does comparable memory requirements persist when allowing a small probability of estimation failure?
Response to Reviewer BiQJ
Thank you for the positive assessment and for the question about failure probability, which our appendix addresses directly. All results cited below are already in the paper; we ran no new experiments for this reply.
Q. Do comparable memory requirements persist when a small probability of failure is allowed, and how representative are the packing histories? Yes. The lower bound does not rely on a shrinking neighborhood of rare histories.
typical, appendix). Suppose a deterministic B-bit state is ϵ-accurate for every legal continuation on a set of histories of probability at least 1−δ, with any 0≤δ<1. Then for each 1≤n≤D+1, B≥nlog2(1/ϵ)−O(nlog(1/η))+⋯+log2(1−δ). The failure allowance enters only through the additive log2(1−δ).generalhistory). The same holds with a bound of the form B≥qnlog2(1/ϵ)−⋯+log2(1−δ). For a fixed model, K and δ<1, this gives Θ(qmin{D+1,x}x) as x=log2(1/ϵ)→∞, together with the uniform upper bound.randomqueryand 10,generalquery). If the baseline and post-query TV errors exceed ϵ with probabilities at most δ0,δ1, the bound has the same form, with a term log2s where s=1−δ0−δ1/(pβ)>0. These bounds need explicit outcome/query conditions to be positive.So the packing is carried by a set of histories of probability at least 1−δ, not by a vanishing-probability neighborhood. What is lost is the explicit constant. The log2(1−δ) and log2s terms cost only lower-order bits.
Weakness 1: scattered disclaimers, and stating assumptions and intuition. We agree and have made three changes in the revised first ten pages.
Weakness 2: narrow scope. We agree the main theorem is for a known, positive, invertible finite-state model, and Table 2 states this. Scope has been widened in two ways within that setting: finite on-time alphabets with informative late fields (Theorem 8, D≥1), and a growing-K reset family with explicit contraction ≤4/9. Extending beyond these classes, including unknown models and general growing-K families, is not claimed and is listed as a limitation.
Thank you again for the constructive review.