- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper asks which properties of the input decide exact recovery and organizes its answer around two necessity principles: N1, a localized Fano bound, and N2, a coordinate-coverage converse. The paper itself calls their role organizational. The main technical object is forced-satisfiable planted k-SAT, the Motoki and Uehara model. At m = n(2^k-1)(ln n + x)/k clauses, Thm. 4.1 says that with high probability the full solution set is the subcube generated by the surviving single flips, and that the number W of surviving flips is Poisson with mean e^-x. Uniqueness therefore converges to exp(-e^-x), while Bayes and minimax recovery converge to exp(-e^-x/2), so uniqueness costs ln 2 times n(2^k-1)/k extra clauses. Thm. 4.3 extends the window to bounded non-uniform scope weights through the occupancy clock Λm = Σ(1-qi)^m. Cor. 4.4 uses Jensen to show that equal marginals minimize the clock at every finite m, and it computes the clause premium w̄/β for a two-block law. Table 1 places five further families under the two principles: hidden pixel, one-edge Ising, a one-hidden-unit RBM, noisy indexing and erasure. Table 2 checks the predicted cost ratios in small simulations. A CIFAR-10H study, framed by the authors as descriptive and retrospective, compares per-item and pooled channel summaries with and without image models. Conjecture G.1 proposes a second-order window for noisy indexing.
Critical strengths
-
The SAT window is proved fully and correctly, and it describes the whole version space, not just a count. Thm. 4.1 rules out every satisfying assignment outside the subcube in three distance regimes. Lem. C.10 and the partial-survivor bound give the 1 - O(ln n/n) rate, and I checked that the leading multi-pattern term is ((k-1)/2)e^-2x ln n/n, which matches the "one unit" share the appendix attributes to size-two patterns at k = 3. The rate sweep in Table A.6 agrees with the predicted 3 ln n/n law from n = 100 upward. The authors themselves note a finite-size discrepancy at n = 50 and that the statistic is only a detectable subset of failures. This gives the field a precise, citable statement: uniqueness and Bayes recovery share the n ln n scale yet differ by a Θ(n) clause budget inside the window. That is a useful corrective for anyone who equates identifiability with recoverability.
-
The empirical work is unusually candid about what it does and does not show. The authors separate the exactly computable W-proxies from the true curves and enumerate the full cube up to n = 22. There they report that the true separation still sits about a sixth below ln 2. Their own Table A.4 would have hidden this, since its numbers reproduce to five decimals from the E[z^W] formula. This kind of finite-size candor is rare, and the main-text and appendix tables I recomputed all hold up.
Critical weaknesses
- The technical advance is narrower than the framing suggests. To be fair to the authors, App. A scopes the novelty precisely: the new contribution is the connection of the covering process to the complete posterior and to the recovery window, not the count or the optimality of equal coverage, p. 13 line 669. That claim holds up, and Thm. 4.1 is the paper's best result. But the tools behind it are standard.
- By Lem. C.15, W is the number of empty cells in a categorical draw with a null cell. I believe its Poisson limit under bounded-ratio cell probabilities is classical occupancy theory, as in the non-equiprobable allocation schemes of Kolchin, Sevastyanov and Chistyakov. So Schilling and Henze, which the paper cites as the directly relevant precedent, are not the closest one for the count in Thm. 4.3. Unequal-probability collector limits are closer, such as Doumas and Papanicolaou 2016, who obtain Gumbel laws for collection times and hence for P(W = 0).
- The subcube proof is a careful first-moment argument: a negative-association product bound over three distance regions, plus a partial-survivor series. It is correct and complete, but it is not a new technique. The recovery curve is E[2^-W] on the structure event, and Cor. 4.4(a) is Jensen, explicitly the first moment of the ordering of Anceaume et al.
- N1 and N2 are a single-letterized Fano bound and a posterior-multiplicity count, and the appendix calls their contribution organizational, p. 14 line 703. The main text still says they diagnose which requirement binds, p. 2 line 93. Yet the paper notes that a logarithm alone does not reveal its source, p. 4 line 185, and in noisy indexing N1 already gives n ln n. Sec. 5.3 does offer an a priori cue, whether an observation names the coordinate it concerns, but the cue is informal and was checked only on families whose answer was already known. In my judgment that leaves the dichotomy closer to a post hoc classification than a predictive tool.
For ICLR, the payoff to learning theory beyond planted SAT is not shown.
- The CIFAR-10H study is carefully scoped, but its coverage reading does not match the paper's own definition. The authors present it as a descriptive diagnostic rather than a theorem instance, p. 9 line 469, and as retrospective because the channels are calibrated against gold labels, p. 39 line 2095. So I do not hold it to theorem standards. My concern is narrower.
- N2 defines an uncovered coordinate as one receiving no decisive evidence, p. 3 line 130. The floor in Fig. 3a comes from items whose per-item channel points away from gold. That is 86 items by the half-A plurality criterion, 107 erring items measured at n = 10000 and λ = 18, and 14.6 items on average that are never recovered at λ = 30. On those items, more votes converge to the wrong label. That is evidence that is decisive in the wrong direction, or gold-label noise. The paper concedes that four of the 13 doubly wrong items are gold-label errors, p. 39 line 2082. Calling this the coverage signature, p. 2 line 88 and p. 9 line 475, stretches the term.
- The per-item predictor is fit on half A of each item's votes and evaluated on half B, so its tracking is close to a split-half reliability check.
- The homogeneous baseline is a symmetric channel that spreads the pooled 5.14 percent error evenly over nine classes, the weakest homogeneous choice. The class-conditional pooled confusion matrix already used in the image-assisted decoder would be the natural baseline. My conjecture is that it would also miss the floor, since it is item-homogeneous too. That would keep the qualitative point but shrink the four-orders-of-magnitude headline.
Only the ln n growth of λ*(n) on the near-homogeneous band speaks to coverage in the paper's sense, and that is the standard union-bound effect. I judge the curves from their captions and the App. H numbers only.
Questions for authors
- Beyond the full-cube structure event, what in Thm. 4.3 goes beyond classical occupancy limits for categorical draws with unequal, bounded-ratio probabilities? Please compare with that literature and with Doumas and Papanicolaou 2016, not only with Schilling and Henze.
- Can the metadata cue of Sec. 5.3 be used before the answer is known? Can you give one family where N1 and N2 predict the binding requirement a priori, and the prediction is then confirmed?
- Why is a floor caused by items whose channel mode differs from gold called coverage, given the definition in Thm. 2.2? How large is the gap between the per-item prediction and a class-conditional, item-homogeneous confusion baseline?
- App. G.1 says λtilt is about 17 at n = 10000. With η = 0.1 I get λ e^-Cη of 13.8 at λ = ln n/a, 12.2 at the conjectured centre y = 0, and 11.0 at the measured crossing. A value of 17 would need aλ near 11.3, above ln n. Your companion statement does reproduce: with exact Poisson loads, EN e^y is 1.020 times c_η at y = 0. For the parity constants at t = 1600, the exact binomial prefactor differs from eq. 4 by 0.05 percent at η = 0.1, 0.13 percent at η = 0.2 and 0.64 percent at η = 0.35. A Richardson extrapolation from t = 400 and t = 1600 comes within 0.044 percent at η = 0.35. Which quantity was compared, and is 17 a typo?
- Does the subcube geometry survive clause laws with more than one forbidden pattern? The Model RB plateau near 0.486 suggests it does not.
6 comments
Rebuttal (2/4)
W1c / Q2 (N1/N2 as a predictive tool and an a priori test). The cue can be used before the answer is known. The revision gives it a quantitative form that depends only on the law of a single observation (Sec. 5.3 and Lem. C.18 in App. C.20), and we tested it on a new family whose answer was not known in advance. App. A calls N1 and N2 organizational because neither is a new inequality, while the diagnosis in Sec. 1 uses them together with this channel condition, which the revised contribution statement and App. A now state.
Condition. Suppose one observation's law differs between any two candidates of the localized family only on an event of probability ≤ p, and the log-likelihood ratio there is bounded by L. Then I(Y; Z₁) ≤ max_{θ,θ'} KL(P_θ‖P_θ') ≤ pL, so N1 gives m ≥ [(1 − P_e) ln(N + 1) − ln 2] / (pL).
- Coordinate-local and non-decisive observations (p = O(1/n), L = O(1)). N1 already contains the ln n, and coverage sharpens only the constant. Noisy indexing at fixed η is this case, the sample that names its coordinate in Sec. 5.3. Ex. C.5 computes I₁ = (1 − 2η) L / (n + 1) to leading order, within the bound pL = 2L / n.
- Decisive observations (L large). The bound no longer controls I₁, and I₁ is then computed directly from the law of one observation, still before any experiment. In every such family we have computed, N1 stops at Θ(n) and the logarithm comes from coverage. These are planted SAT clauses, which rule out alternatives without naming them (Sec. 5.3), noiseless indexing (η = 0 in Ex. C.5), and the vanishing-noise family below.
A priori test. We took a new family, noisy indexing with vanishing noise η_n = n^{−1/2}. Here the log-likelihood ratio grows, L = ½ ln n, so the bound pL no longer keeps the logarithm. Before running anything, we predicted that N1 stops at Θ(n) and that coverage sets the ln n scale. The measurements use per-coordinate Bayes decoding with 1,500 trials per point. λ* is the load at which exact recovery reaches ½, and the per-coordinate (N2) calculation solves n · E[perr(Poi(λ))] = ln 2.
| n | 300 | 1,000 | 3,000 | 10⁴ |
|---|---|---|---|---|
| η_n = n^{−1/2} | 0.058 | 0.032 | 0.018 | 0.010 |
| single-letter N1 load λ_N1 | 0.89 | 0.87 | 0.86 | 0.87 |
| measured λ* | 7.98 | 8.44 | 8.94 | 9.81 |
| per-coordinate (N2) calculation | 7.96 | 8.40 | 9.00 | 9.81 |
| measured λ* / ln n | 1.40 | 1.22 | 1.12 | 1.065 |
The outcome is as predicted. The single-letter N1 load stays at 0.86–0.89, about a tenth of the measured λ*, while λ* stays within 0.06 of the per-coordinate calculation at every n and λ*/ln n falls from 1.40 to 1.065 toward 1, so coverage is the binding requirement. The window for constraints with t forbidden patterns (Q5 below) was likewise placed from coverage alone before it was measured. App. J reports both tests (Tabs. A.14 and A.16).
W1d (payoff to learning theory beyond planted SAT). Beyond planted SAT, the paper gives learning theory two results.
- A test of which requirement binds. The channel condition of W1c / Q2 depends only on the law of one observation and tells, before any experiment, whether the logarithm in the exact-recovery sample complexity comes from the amount of information or from coverage. Its prediction was confirmed on a new family.
- Allocation moves the boundary. At equal information per observation, the allocation of evidence across coordinates changes how many observations exact recovery needs. Thm. 4.3 proves this in planted SAT (item 3 of W1), and the CIFAR-10H study measures it on a real annotation channel, where the pooled description misses the measured count of erring items by a factor of 5,500 or more while the item-level description predicts it (W2b and W2c below).
Rebuttal (3/4)
W2, W2a / Q3a (why "coverage" for the CIFAR-10H floor). The paper used "coverage signature" for the coordinate-level side of its central distinction, that exact recovery fails on particular items rather than through the pooled error rate. This is broader than the uncovered coordinates of Thm. 2.2, and the revision separates the two mechanisms in Sec. 5.4.
- The band: coverage in the sense of Thm. 2.2. On the near-homogeneous band, items fail because they have not yet received enough annotations, and λ*(n) grows with ln n. This is the coverage requirement of N2 in the same sense as in SAT.
- The floor: allocation of evidence across items. For a small set of items the annotation channel points away from the gold label, as Sec. 5.4 of the paper already states. Under the item-homogeneous channel that the decoders use, more votes move these items further toward another class, and part of the set reflects gold-label errors (4 of the 13 doubly wrong items, reported separately in App. H). This is item-level heterogeneity of the annotation channel. The pooled error rate is the same however the errors are spread over items, but where they sit decides which items can be recovered. That is the real-data counterpart of Thm. 4.3, where the same information per observation, allocated differently, gives a different boundary.
This item-level heterogeneity agrees with the CIFAR-N study of Wei et al., Learning with Noisy Labels Revisited: A Study Using Real-World Human Annotations (ICLR 2022), which found real human annotation noise to be instance-dependent rather than class-dependent. The revision replaces "coverage signature" on p. 2 and in Sec. 5.4 with "item-level floor".
W2b (split-half). The tracking does rest on the stability of each item's channel across the two halves, and that stability is the finding. Each item keeps its own error pattern from half A to half B, so the errors are allocated across items in a stable way that a pooled summary averages away. Both kinds of summary are estimated on half A and evaluated on half B, so only the description of the channel differs. At n = 10⁴ and λ = 18 the item-level summary predicts 108 erring items against 107 measured, while the symmetric and class-conditional pooled summaries predict 0.0008–0.006 and 0.014–0.019 (W2c below).
App. H now describes the predictor as a held-out test of the item-level summary.
W2c / Q3b (class-conditional baseline). At n = 10⁴ and λ = 18, the class-conditional baseline predicts 0.014–0.019 erring items, against 108.0 predicted per item and 106.8 measured, a factor of 5,500–7,600, about 3.8 orders of magnitude. The symmetric channel of the paper misses by 4.3 to 5.1 orders. The class-conditional channel gives each item the row of its gold class in the pooled half-A confusion matrix, the matrix the image-assisted decoder already uses. We computed both pooled channels with exact error brackets, not 120-trial Monte Carlo. The bracket is [LB, UB] with LB = Σᵢ max_c sᵢc and UB = Σᵢ Σ_c sᵢc, where sᵢc = P(N_c > N_gold) + ½ P(N_c = N_gold). The table gives the expected number of erring items at n = 10⁴ under plurality decoding.
| λ | 6 | 10 | 14 | 18 | 24 | 30 |
|---|---|---|---|---|---|---|
| symmetric channel (paper's baseline) | [30.8, 98.8] | [0.82, 4.1] | [0.024, 0.16] | [0.0008, 0.006] | [5e−6, 4e−5] | [3e−8, 3e−7] |
| class-conditional, item-homogeneous | [47.5, 106] | [2.5, 5.3] | [0.17, 0.29] | [0.014, 0.019] | [3.8e−4, 4.4e−4] | [1.1e−5, 1.2e−5] |
| per-item prediction (half A, Fig. A.8a of the paper) | 214.7 | 132.9 | 115.2 | 108.0 | 100.2 | 98.5 |
| measured (half B, Fig. A.8a of the paper) | 217.3 | 134.4 | 116.8 | 106.8 | 100.2 | 95.7 |
For the symmetric channel, the exact value at λ = 18 is 0.0008–0.006. The 0.008 in the paper is a 120-trial Monte Carlo estimate. The revision adds the class-conditional baseline with exact brackets to App. H (Tab. A.8), states the measured values in Sec. 5.4 and the ratio in App. H, and replaces the Monte Carlo 0.008 by the exact bracket. The headline on p. 2 now reads "more than three orders of magnitude, even when the pooled channel is class-conditional", in place of "four orders of magnitude".
Rebuttal (1/4)
We thank the reviewer for recognizing the correctness of our theory and the reliability of our experiments. We address your concerns one by one below.
W1, W1a, W1b / Q1 (technical contribution and the occupancy literature). The paper asks when a learner fails because the input itself is insufficient, and which property of the input decides this. Planted k-SAT is the instance where this question can be answered completely, and doing so requires the complete set of targets consistent with the data together with its limit law inside the recovery window. We derive both with classical tools, namely occupancy limits for the number W of uncovered coordinates, first-moment bounds under negative association that exclude consistent assignments at every Hamming distance, and Jensen's inequality for the ordering of occupancy clocks (Cor. 4.4(a)). Because these tools are classical, the results rest on well-established foundations rather than on new machinery built for the proof. The contribution of the paper lies in the three results they establish.
W1a / Q1 (the occupancy literature). The contribution of Thm. 4.3 lies in the full-cube structure event under non-uniform scopes and in what it yields for the learner.
Beyond the full-cube structure event, Thm. 4.3 takes the limit of the count W from classical occupancy theory, which, as with the tools above, keeps the result on well-established foundations. Kolchin, Sevastyanov and Chistyakov (Random Allocations, 1978) give its Poisson limit for non-equiprobable allocations, and Doumas and Papanicolaou (ESAIM P&S 20, 2016) give the Gumbel limit of the unequal-probability collection time, hence P(W = 0). Schilling and Henze cover group drawings only under deviations of order 1/log n from the uniform law, so the first two are the closer precedents, and the revised App. A cites them as such. This is the scope that App. A states and that the reviewer finds to hold up in W1, where the new contribution is the connection of the covering process to the complete posterior and to the recovery window, not the count or the optimality of equal coverage.
W1b (the proof technique). The contribution of the subcube proof lies in its result, the full-cube structure event of item 1. The proof itself is a first-moment argument under negative association, and Cor. 4.4(a) is the first-moment form of the ordering of Anceaume et al., as App. A states. As with the occupancy limits, these classical techniques keep the result on well-established foundations, and the reviewer finds the argument correct and complete.