acceptodds
Under review as a conference paper at ICLR 2027

Statistical Equivalence Does Not Determine Streaming Memory

Abstract

Can asymptotically equivalent statistical experiments have different streaming-memory complexity? For every fixed , we construct explicit finite realizable learning problems with concepts on uniformly sampled points, where . Their labeled-sample experiments have Le Cam distance at most uniformly over the sample count, while their base Gram matrices and robust-SQ profiles agree exactly up to radius . Nevertheless, one problem admits exact one-pass learning with samples and bits, whereas for every fixed ordered pass count , the other requires bits or samples, even for improper learners with error . Rare field equations and binary parity observations have identical pairwise correlations but different storage costs, separating unrestricted statistical simulation from fixed-pass streaming simulation.

Primary area:
learning theory
Keywords:
learning theory, memory-constrained learning, streaming algorithms, statistical query dimension, Le Cam distance, memory-sample tradeoffs

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_S4mxOpenReview ↗
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 θ\theta, and we would like to recover or learn θ\theta in a streaming setting with limited working memory.

The authors construct two learning problems that provide essentially the same statistical information about θ\theta, but require different amounts of memory to learn. In the easy problem, the target can be recovered in one pass using O(R2/log⁡R)O(R^2/\log R) bits of memory and polynomially many samples. In contrast, for the hard problem, any fixed-pass streaming learner requires Ω(R2)\Omega(R^2) 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
AuthorsOpenReview ↗

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.

Thank you for the response and the revision. I will keep my original positive score.

Reviewer_sRePOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper constructs two finite realizable learning problems whose labeled-sample experiments have uniformly small Le Cam distance over all sample counts, with identical base Gram matrices and matching robust-SQ profiles over a growing range of reweighting radii. Despite this statistical closeness, they have different streaming-memory requirements. The construction refutes the fixed-accuracy interpretation of Gonen et al.’s proposed characterization and distinguishes unrestricted statistical simulation from learning under a memory constraint.

Critical strengths

I consider this an interesting and substantial theoretical contribution. I particularly appreciate how rare-block substitution is combined with a common identifiable component: short sample sequences are close because rare observations are unlikely, while long sequences allow an unrestricted simulator to identify the target and resample. Matching the statistical profiles while retaining different storage requirements is an elegant construction. The result clarifies an important limitation of the statistical summaries under consideration, and I consider its technical contribution sufficient for acceptance.

Critical weaknesses

My main concern is presentation, particularly the introduction. I found it much harder to follow than Gonen et al. (2020), which progressively introduces the learning model, elementary sample–memory trade-offs, and the characterization question. Here, several statistical comparison objects and the full separation theorem appear in rapid succession, before the reader has enough context to understand their respective roles. The connection between the original conjecture, its fixed-accuracy interpretation, and the claimed separation should also be made explicit.

Although the paper includes proof sketches and an explanation of the mechanism, these are too compressed to provide a clear roadmap through the construction. The roles of the common observations, rare blocks, and profile matching should be distinguished before the technical assembly. In particular, the reason field equations can be stored more compactly than the corresponding binary parity constraints deserves an accessible explanation.

My current recommendation is 2 — Weak Reject because these presentation issues substantially hinder understanding. The concrete writing improvements described here would be sufficient for me to raise the recommendation to 3 — Weak Accept or 4— Accept.

Questions for authors

Could the authors restate Gonen et al.’s conjecture and explain explicitly which fixed-accuracy interpretation Theorem 1.1 rules out? Presenting the basic memory/sample baselines before the theorem would also help readers understand the significance of the separation.

Could the introduction provide a concise construction roadmap explaining why both common identifiability and rare substitution are needed, how profile matching fits into the argument, and where the memory saving comes from? A simple explanation of the field-equation versus binary-parity storage costs would be particularly helpful.

2 comments
AuthorsOpenReview ↗

Response to Reviewer sReP

Thank you for the concrete suggestions; we followed them closely.

Introduction (W1). It is rebuilt in the order of Gonen et al.: the model (p. 1, l. 32–39), the elementary trade-offs (l. 40–49), the characterization question (p. 1, l. 51 – p. 2, l. 70), then the theorem. Each comparison object is introduced once in the introduction, with its role: the SQ dimension and the profile with the conjecture, Le Cam distance and the Gram matrix just before the theorem (p. 2, l. 71–80).

Q1(a): the conjecture and the reading we refute (p. 2, l. 59–70). Gonen et al. call a family of classes bounded-memory learnable at error ϵ\epsilon if some learner uses (∣C∣/ϵ)o(1)(|\mathcal C|/\epsilon)^{o(1)} samples and o(log⁡∣C∣(log⁡∣X∣+log⁡(1/ϵ)))o(\log|\mathcal C|(\log|\mathcal X|+\log(1/\epsilon))) bits. With RC,P(μ)\mathcal R_{\mathcal C,P}(\mu) the largest SQdimQ(C)\mathrm{SQdim}_Q(\mathcal C) over P/μ≤Q≤μPP/\mu\le Q\le\mu P, their Conjecture 1 states

C bounded-memory learnable at error ϵ  ⟺  RC,P(poly(1/ϵ))≤poly(1/ϵ).\mathcal C\ \text{bounded-memory learnable at error}\ \epsilon \iff \mathcal R_{\mathcal C,P}(\mathrm{poly}(1/\epsilon))\le\mathrm{poly}(1/\epsilon).

In the fixed-accuracy reading, ϵ\epsilon and both polynomials are fixed while the class grows, so the right side asks that the profile at one constant radius μ0\mu_0 be bounded. Theorem 1.1 refutes this for every ϵ≤1/64\epsilon\le1/64. Once Ms≥μ0M_s\ge\mu_0, the right side holds for both families or for neither. With ∣C∣=∣X∣=N|\mathcal C|=|\mathcal X|=N, learnability means No(1)N^{o(1)} samples and o(R2)o(R^2) bits; the easy family qualifies (ROB(1)R^{O_B(1)} samples, O(R2/log⁡R)O(R^2/\log R) bits) and the hard one does not (Ω(R2)\Omega(R^2) bits or NΩ(1)N^{\Omega(1)} samples). So the equivalence fails for one of the two families.

Q1(b): baselines are on p. 1, l. 40–49 (storing examples, enumerating concepts, and parities with Raz's bound), and p. 2, l. 102–105 explain why a factor log⁡R\log R is enough.

W2/Q2: roadmap and storage costs. This is the new Section 1.1.

  • Rare substitution handles short samples. The problems differ only on a block of probability ζ\zeta, so a kernel that keeps common examples errs with probability at most mζm\zeta (p. 3, l. 135–138).
  • Common identifiability handles long samples, where that bound fails. Shared blocks separate every two targets with probability at least 1/161/16, so after O(R)O(R) samples an unrestricted kernel identifies the target and resamples (l. 139–147).
  • Profile matching (p. 4, l. 166–185). A constant block caps both profiles below 4μ4\mu, and a profile code makes both sides attain the same cap for μ≤K/8\mu\le K/8.
  • Storage costs (p. 3, l. 149 – p. 4, l. 164). With q=2sq=2^s, one equation ⟨a,u⟩=y\langle a,u\rangle=y over Fq\mathbb F_q is ss independent binary constraints on the n=ksn=ks bits of uu, yet it takes (k+1)s(k+1)s bits, about as many as one binary constraint. Elimination over Fq\mathbb F_q keeps kk rows, k(k+1)sk(k+1)s bits, while a parity basis takes about n2=k2s2n^2=k^2s^2 bits, and Lyu et al. (2023) show that, for a fixed number of passes, Ω(n2)\Omega(n^2) bits are needed unless 2Ω(n)2^{\Omega(n)} samples are used. With n=Θ(R)n=\Theta(R) and s=Θ(log⁡R)s=\Theta(\log R), this is O(R2/log⁡R)O(R^2/\log R) against Ω(R2)\Omega(R^2).

Thank you for the substantial revisions, which have largely addressed my concerns about the presentation. I will raise my presentation score to 2 and my overall recommendation to 3 (Weak Accept).

Reviewer_WoYHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies whether statistically equivalent learning problems can have different streaming-memory complexity. The authors construct two finite realizable learning problems, each with NN concepts over NN uniformly sampled domain points, whose labeled-sample experiments have Le Cam distance at most R−BR^{-B} for every sample count, where R=log⁡2NR=\log_2 N and B>0B>0 is any fixed constant. Moreover, the two problems have identical Gram matrices, and their robust-SQ dimension profiles agree exactly over a growing range of reweighting radii.

Despite these similarities, the easy problem admits a proper exact one-pass learner using O(R2/log⁡R)O(R^2/\log R) bits and polynomially many samples, while the hard problem requires either Ωp(R2)\Omega_p(R^2) bits or NΩp(1)N^{\Omega_p(1)} samples for any fixed number of passes pp, even for improper learners with constant error.

Technically, the memory separation comes from designing two "rare blocks" in the respective learning problems: On the easy side, some observations provide linear equations in the unknown target over a finite field, allowing one to learn the target; on the hard side, observations provide binary parity equations, and learning the target inherits the known quadratic-memory lower bound for parity learning. The two rare blocks are designed to have identical pairwise correlations, yielding identical Gram matrices for the two learning problems.

Critical strengths

I appreciate the technical aspects of the construction. The authors manage to simultaneously achieve identical Gram matrices, asymptotically vanishing Le Cam distance uniformly over the sample count, and a separation in streaming-memory complexity. In particular, the construction nicely embeds appropriate "rare blocks", which provides either linear equations that enables learning the target, or binary parity equations which inherits the existing hardness result of learning. The exposition is clean and sufficient, while carrying sufficient details and non-trivial technical ideas.

Critical weaknesses

My main concern about this paper is the motivation and significance of the result. To my understanding, the main motivations is to refute Conjecture 1 proposed by Gonen et al., which roughly states that bounded-memory learnability can be characterized by whether the robust-SQ profile remains bounded by poly⁡(1/ϵ)\operatorname{poly}(1/\epsilon) for all multiplicative reweighting factors up to poly⁡(1/ϵ)\operatorname{poly}(1/\epsilon), where ϵ\epsilon is the target error. This paper, however, shows that two problems can have identical robust-SQ profiles for all reweighting factors up to Θ(log⁡N/log⁡log⁡N)\Theta(\sqrt{\log N/\log\log N}), yet differ in their bounded-memory learnability. I think this is a technically interesting refutation. However, I am less clear about its broader significance: e.g., how much it changes our understanding of bounded-memory learning, and in particular what implications it has for developing alternative characterizations.

Beyond this, much of the technical effort in the construction seems to be establishing something stronger: the authors construct an easy and a hard problem such that (1) their robust-SQ profiles agree, (2) their Gram matrices are identical, and (3) the Le Cam distance between their labeled-sample experiments vanishes asymptotically. While achieving all these properties simultaneously is technically nontrivial, I find the motivation for requiring the additional properties less clear. For example, intuitively, the message that Le Cam equivalence does not imply equivalence in streaming-memory complexity does not seem especially surprising. Le Cam theory studies when one statistical experiment can simulate another, without imposing computational or memory limitations. It seems natural that an unrestricted simulator can perform operations that a streaming algorithm cannot.

Questions for authors

See the weakness section (e.g. "I am less clear about its broader significance: how much it changes our understanding of bounded-memory learning, and in particular what implications it has for developing alternative characterizations.")

2 comments
AuthorsOpenReview ↗

Response to Reviewer WoYH

Significance (W1). At fixed accuracy, bounded-memory learnability is not determined by the base Gram matrix together with the robust-SQ profile on any bounded window: our two families agree on both, on a window [1,Ms][1,M_s] with Ms→∞M_s\to\infty, yet only one is bounded-memory learnable, for every ϵ≤1/64\epsilon\le1/64. In particular, Conjecture 1 of Gonen et al. fails in its fixed-accuracy reading (p. 2, l. 59–70), and any characterization must also separate some families whose sample experiments are asymptotically equivalent (p. 3, l. 115–118).

For alternative characterizations, our reading, which is not a theorem: the two rare blocks have identical correlations but different storage costs, since one Fq\mathbb F_q equation carries ss binary constraints in the space of one. A successful invariant must therefore see how observations combine into stored constraints. Corollary 6.1 makes one version precise: converting hard examples into easy ones within a fixed-pass stream, with constant total-variation error, needs Ωp(R2)\Omega_p(R^2) bits or 2Ωp(R)2^{\Omega_p(R)} examples, although an unrestricted conversion has error R−BR^{-B} (p. 3, l. 119–121). Readings in which ϵ\epsilon shrinks quickly with NN are not addressed by the theorem (p. 2, l. 69–70), and neither is any positive characterization.

Why the extra properties (W2). We agree that small Le Cam distance alone is not surprising, and the paper now says so (p. 2, l. 107 – p. 3, l. 108). The extra properties make the example bear on the criteria that have been proposed, which are built from correlations. A Le Cam-only example would not (p. 3, l. 108–111): an easy rare block whose rows reveal single bits of uu also gives small Le Cam distance, but there two targets disagree on a fraction that depends on their Hamming distance, while distinct parities always disagree on half, so the Gram matrices would differ and correlation-based criteria could separate the problems.

  • Gram equality makes every statistic of the correlations under PP, such as SQdimP\mathrm{SQdim}_P, equal on the two problems. Exact equality matters, because SQ dimensions are integers defined by thresholds (p. 3, l. 112–115).
  • Profile equality defeats the criterion of Conjecture 1 itself.
  • Le Cam closeness makes the two problems almost interchangeable for unrestricted statistical decisions: for every loss in [0,1][0,1], the optimal Bayes and minimax risks agree within R−BR^{-B}. So a characterization must also separate some asymptotically equivalent families (p. 3, l. 115–117).

In our construction the memory gap is a factor log⁡R\log R at polynomial sample budgets, which crosses the o(R2)o(R^2) threshold in the definition of Gonen et al. (p. 2, l. 102–105).

Thank you for your clarification! I think I now have a better understanding of the paper's contribution. I therefore retain my positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers. Reviewers sReP and S4mx ask for a clearer presentation, and Reviewer WoYH asks what the result changes and why the additional properties are needed. We have uploaded a revision in which every added or changed word is blue; the main text ends on page 10. The main changes:

  1. The abstract now opens with the learning model and states the consequence for the conjecture. The introduction follows the order of Gonen et al. (2020): the learning model, the elementary memory–sample trade-offs, Conjecture 1 restated with the fixed-accuracy reading that Theorem 1.1 refutes, and only then Le Cam distance and the Gram matrix (pp. 1–2). Theorem 1.1 is unchanged.
  2. A new paragraph after the theorem says what it adds beyond small Le Cam distance (p. 2, l. 107 – p. 3, l. 121).
  3. A new Section 1.1 explains the construction before the technical sections (p. 3, l. 124 – p. 4, l. 191).
  4. The proof sketch, the "Proof mechanism" paragraph and four repeated statements of the main claim are removed. Clashing symbols are renamed (C→VC\to V, H→WH\to W and four more), and Blum et al. (1994) is cited for the SQ dimension.
  5. To make room, the proofs of Lemma 3.1 and Corollary 6.1 moved to Appendices C and D, and the size, encoding and sampling bookkeeping in the proof of Proposition 4.3 became Lemma A.2. Moved text is verbatim up to the renamed symbols and is also shown in blue. No statement changed except for renamed symbols, and no new result is claimed.

Cross-references now print capitalized names; this typographic change is not colored.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.