- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors study the memory required t generate a distribution P over n spins, focusing on the Curie-Weiss model. They define as the minimal number of hidden states of a time-inhomogeneous HMM that generates a distribution Q within total variation distance of P. For exact generation (), they show that equals the maximal cut rank, and construct a generator attaining it. For fixed , they show that at the critical point , whereas at any fixed noncritical .
Critical strengths
The fixed- scaling at criticality, versus away from criticality, is an interesting and potentially novel result.
Critical weaknesses
The authors seem largely unaware of the large relevant literature on closely related problems, including minimal and positive realization of HMMs (e.g., Anderson 1999; Huang, Ge, Kakade & Dahleh 2014), computational mechanics (Shalizi & Crutchfield 2001), predictive state representations (Singh, James & Rudary 2004), and the memory required for approximate prediction (Sharan, Kakade, Liang & Valiant 2018). Many results recover standard ones: the cut-rank bound (Lemma 7) is the classical HMM realization bound, and Thm 2 is its specialization to this family; the observation in App. E that counting distinct conditional laws does not lower-bound non-unifilar generators is the distinction between statistical and generative complexity; and the discontinuity of exact complexity under small perturbations (Thm 5) is well known. Given lack of literature review in other areas, it is unclear to what extend the scaling result rediscover existing bounds on Curie-Weiss.
Finally, the paper is very hard to read. It seems written by AI and uses non-standard terminology (e.g., "retained-state generator with a free clock and read-only kernels" for a time-inhomogeneous HMM) and various disclaimers in place of explanation. The connection to ICLR topics is also thin.
Questions for authors
No questions that would change my assessment.
Suggestions for future work:
- The authors may want to look into Bialek, Nemenman & Tishby 2001, I feel like the O(n^1/4) scaling is related to their analysis of scaling of mutual information.
- Relating the results to learned autoregressive models (HMMs, RNNs/state-space models, etc.) would make the work more relevant to ICLR.