acceptodds
Under review as a conference paper at ICLR 2027

Input Information and the Learning Boundary

Abstract

Learning can fail because the input is insufficient, even when representation, optimization, and computation pose no obstacle. We study the corresponding information-theoretic learning boundary, which is the threshold at which the observations themselves become sufficient. Exact recovery makes this boundary observable by requiring an optimal learner to identify a finite structured target exactly. We show that exact recovery depends on two distinct properties of the input. The observations must distinguish the candidate set in total, and decisive evidence must reach every hidden coordinate. In forced-satisfiable planted -SAT, we characterize this boundary at window precision. At clauses, the complete version space is with high probability a random subcube, and its number of unresolved coordinates converges to a Poisson random variable with mean . This geometry separates two notions that are often conflated in learning. The data may permit an optimal learner to recover the planted target before they determine it uniquely. The limiting uniqueness probability is , whereas Bayes-optimal and minimax exact recovery converge to . At every fixed success level, uniqueness therefore requires asymptotically more clauses. The same window law persists under bounded non-uniform coordinate coverage. Equal marginal coverage minimizes the occupancy clock exactly at every finite sample size, and uniform weights attain it within the conditional product family. Calibrations across five further learning families and finite-size experiments show when total information predicts the boundary and when coordinate coverage becomes decisive. Together, the theory and experiments show that the learning boundary for exact recovery depends on both the amount of input information and its allocation across hidden coordinates.

Primary area:
learning theory
Keywords:
Learning Boundary, Information, Planted k-Sat, Exact Recovery

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_cZj3OpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  1. 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
  1. 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.
  2. 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?
  3. 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?
  4. 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?
  5. 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
AuthorsOpenReview ↗

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.

  1. The complete version space inside the recovery window. Thm. 4.1 shows that, with probability 1 − O(ln n / n), the set of all assignments consistent with the data is exactly the subcube spanned by the uncovered coordinates. This requires excluding every consistent assignment at every Hamming distance, including those with no surviving single flip. For the Motoki and Uehara model, the first-order uniqueness threshold was established in the original work (Motoki and Uehara, 1999). To our knowledge, the recovery window, its limit law and the geometry of the full solution set have not been characterized previously.
  2. A sharp separation between certifying and recovering the target. From this geometry, the probability that the data determine the target uniquely converges to exp(−e^{−x}), while Bayes and minimax exact recovery converge to exp(−e^{−x}/2). An optimal learner therefore recovers the target ln 2 · (2^k − 1) n / k clauses before the data certify it, an explicit Θ(n) budget that is invisible at first order.
  3. How the allocation of evidence moves the boundary. Thm. 4.3 carries the geometry and both limit laws to non-uniform scope laws through the occupancy clock Λₘ, and Cor. 4.4(c) turns this into a clause budget, under which a two-block skew at equal information per clause costs a factor w̄/β more clauses.

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.

  • (a) The full-cube structure event under non-uniform scopes. Alternatives at distance r ≥ 2 are eliminated by multi-coordinate patterns whose probabilities depend on joint scope inclusions, through elementary symmetric polynomials of the weights. These events are not cells of the categorical draw, so the three-region exclusion had to be carried out with heterogeneous weights. Without it, the occupancy count says nothing about which targets remain consistent with the data.
  • (b) The consequences for the learner. With the full-cube structure event, the occupancy count becomes the dimension of the posterior support, which yields items 2 and 3 above.

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.

AuthorsOpenReview ↗

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.

n3001,0003,00010⁴
η_n = n^{−1/2}0.0580.0320.0180.010
single-letter N1 load λ_N10.890.870.860.87
measured λ*7.988.448.949.81
per-coordinate (N2) calculation7.968.409.009.81
measured λ* / ln n1.401.221.121.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).
AuthorsOpenReview ↗

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.

λ61014182430
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.7132.9115.2108.0100.298.5
measured (half B, Fig. A.8a of the paper)217.3134.4116.8106.8100.295.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".

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

The paper studies the problem of recovering a hidden target exactly from observations from an information theoretic perspective. The main result concerns the planted (k)-SAT problem. Near the recovery threshold, the authors show that the remaining satisfying assignments can be described by freely varying a small set of unresolved coordinates. This gives a precise distinction between recovering the planted assignment with a given probability and having enough observations to identify it uniquely. The authors extend the result to a family of non-uniform sampling distributions. They also present several simpler learning examples and experiments on synthetic data and CIFAR-10H annotations.

Critical strengths

The main SAT result seems interesting and substantial. The paper proves that, near the planted kk-SAT recovery threshold, all satisfying assignments agree on most bits, while the remaining bits can vary independently, with high probability. The paper quantifies the difference between recovery and uniqueness at the same desired success probability, which provides more insight than locating only the leading-order threshold.

The non-uniform extension strengthens the paper. It provides a setting where individual observations carry the same amount of information, but changing how they cover the coordinates changes recovery.

The presentation is generally careful about what is established. The authors distinguish their new results from classical ingredients, explain that some experimental quantities are proxies for actual recovery, and acknowledge limitations of the real-data study. The experimental protocols are also described in considerable detail.

Critical weaknesses
  1. N1 bounds the joint information using the number of observations times the information in one observation. The missing logarithmic factor shows that this particular Fano calculation is insufficient. Joint information itself depends on coverage, as Appendix C.15 explains. Can you please make this distinction clear in the main text?

  2. The larger SAT experiments measure single-coordinate statistics and selected failure modes. Complete solution-space checks stop at (n=22), where the reported structure-failure rate remains around 30% at the center of the window (Table A.5). Since the main contribution concerns the entire solution set, direct checks at the sizes used in the main figures would be more informative.

  3. The Cifar-10H study measures particular decoders using channels calibrated against known gold labels. Appendix H attributes part of the error floor to the combination rule and incorrect labels. These results demonstrate heterogeneous decoder errors, but provide limited evidence for the paper’s information-theoretic interpretation. What are your thoughts on this?

Questions for authors

Following from the weaknesses section above,

  1. What role does positive noise play in the N1 bound for indexing? With zero noise, Example C.5 gives a bound that misses the logarithmic factor even though the coordinate index is still observed. How does this fit the explanation in Section 5.3?

  2. How stable are the CIFAR-10H recovery-budget predictions when subset selection and channel estimation use separate annotations? How much of the error floor remains under a different image–annotation combination rule?

  3. Should the equal-likelihood condition in Theorem 2.2 apply only to candidates with positive likelihood?

3 comments
AuthorsOpenReview ↗

Rebuttal (1/3)

We sincerely thank the reviewer for a careful and constructive review, and for recognizing the SAT result as substantial, the non-uniform extension as a strength, and the care with which the paper separates what is established from what is a proxy. Several points led to new computations and experiments, which are reported in the new App. J and in App. H.

W1 (N1 single-letterizes, joint information depends on coverage). The revision makes this distinction explicit in Sec. 2.1. N1 bounds the joint information by m · I₁, and this single-letter step discards its dependence on coverage. The revised Sec. 2.1 also states how large that dependence is. App. C.15 gives I(σ; Z₁:ₘ) = n ln 2 − E ln|Sol|, and inside the window, on the structure event, ln|Sol| = W ln 2 with E[W] → e^{−x}. Coverage therefore moves the joint information by O(1) nats, while Fano at constant error tolerates a slack of P_e · n ln 2 nats. Fano with the exact joint information thus still certifies only Θ(n) clauses, and the logarithm appears in a statement about the worst coordinate, which is what N2 provides. App. J.2 (Tab. A.15) confirms this numerically.

W2 (complete solution-set checks at the main-figure sizes). We now certify the complete solution set exactly at n = 50 to 800, not only by enumeration up to n = 22. The setting is k = 3, window x ∈ [−2, 3] in steps of 0.25. For each instance, a SAT solver proves that no satisfying assignment lies outside the subcube generated by the surviving single flips, a direct check confirms that no clause cuts the subcube, and |Sol| is counted exactly when either check fails.

This gives the true uniqueness probability P(|Sol| = 1) and the true Bayes success E[1/|Sol|], with no proxy.

n50100200400800
instances per window point1,0001,0001,000600400
structure failure at x = 016.4 %12.5 %6.2 %4.8 %1.5 %
max over x of |P(|Sol|=1) − P(W=0)|0.0100.0050.0030.0000.000
max over x of |E[1/|Sol|] − E[2^{−W}]|0.0490.0240.0130.0080.004

At every size the failure rate is within Monte Carlo error of the detectable-mode rates of Tab. A.6, and it falls from 16.4 % at n = 50 to 1.5 % at n = 800, following the predicted ln n / n decay. Failures almost never occur when W = 0, so the true uniqueness curve coincides with P(W = 0), and at n = 200, the size of Fig. 1, the true Bayes curve stays within 0.013 of E[2^{−W}]. |Sol| was counted exactly up to 4,096, a cap reached only at x ≤ −1.25, where 1/|Sol| < 2.5 × 10⁻⁴.

Fig. 2 shows the two-block non-uniform model of Thm. 4.3, also at n = 200, and we certified it in the same way at exactly its (β, m) points, 800 instances each. Every instance is the full weighted model, with scopes drawn from the conditional product law, not the single-flip reduction that the figure plots.

β (weight of half the coordinates)1½¼
clauses at Λₘ = 1 (ratio to uniform)2470 (1.00)3215 (1.30)5319 (2.15)
structure failure at Λₘ = 17.4 %4.5 %2.8 %
max over the 9 Λₘ points of |P(|Sol|=1) − P(W=0)|0.0010.0000.000
max over the 9 Λₘ points of |E[1/|Sol|] − E[2^{−W}]|0.0130.0060.005

The curves plotted in Fig. 2 are therefore, to within 0.013, the true uniqueness and Bayes curves of the full weighted model.

The revision adds both tables to App. J.1 (Tabs. A.12 and A.13) and uses them in Secs. 5.1 and 5.2.

AuthorsOpenReview ↗

Rebuttal (2/3)

W3 (CIFAR-10H as evidence). The CIFAR-10H study tests the central distinction of the paper on a measured channel in which nothing is planted. The theory separates the amount of information an input carries from its allocation across the hidden coordinates, and Thm. 4.3 proves that the same information per observation, allocated differently, gives a different boundary. CIFAR-10H asks the same question of real crowd annotations. A pooled description of the annotation channel keeps only the average annotation error of 5.14 % and predicts essentially no errors at n = 10⁴ and λ = 18, with exact brackets of 0.0008–0.006 erring items for the symmetric channel and 0.014–0.019 for the class-conditional one. The measured count on half B is 107, and the item-level description, estimated on half A, predicts 108. On this channel, exact recovery is decided by how the errors are allocated across items, not by the average error rate. The four points raised do not change this reading.

  • Particular decoders. The comparison holds the decoder fixed and varies only the description of the input channel, so the gap between the pooled and item-level predictions is a gap between descriptions of the input. The floor is also shared by very different decoders. The never-recovered count at λ = 30 is 14.6 for annotations alone and 14.8 to 15.6 with ResNet-18, ResNet-50 or ViT-B/16 (Tab. A.7), and 17.6 to 18.6 under an overdispersed combination rule (Q2b below).
  • Calibration against the gold labels. Measuring exact-recovery failures on real data requires the gold labels in any design, so the question the study can ask is which description of the input predicts those failures. The pooled and the item-level descriptions are estimated from the same half-A annotations and scored against the same gold labels, and only the item-level one predicts the floor, so the calibration cannot account for the difference.
  • The combination rule. App. H attributes to the product rule the hard items that the combined decoder loses against the models alone, from 47–57 recovered by the models to 34.5–35.8 at λ = 30, because a rule that treats the annotation channel as item-homogeneous lets the annotations outvote the image on exactly these items. It traces the floor itself to the items on which both channels leave the gold label short of a plurality. The new runs confirm both parts. An overdispersed rule recovers 7 to 12 more hard items and does not shrink the never-recovered count (Q2b below).
  • Incorrect gold labels. Four of the 13 items on which both channels disagree with the gold label are gold-label errors, and App. H reports them separately. Removing them lowers the measured count at λ = 30 by at most 4, from 95.7 to at least 91.7 erring items, against 1.1–1.2 × 10⁻⁵ for the class-conditional pooled channel.

The CIFAR-10H study thus supports two statements of the paper on real data, each tied to a theorem. On the near-homogeneous band, the exact-recovery budget λ*(n) grows with ln n, the coverage requirement of N2. On the full pool, the floor follows the allocation of evidence across items, the real-data counterpart of Thm. 4.3. Both are statements about which description of the measured channel predicts exact-recovery failures, the question RQ4 asks (Sec. 5.4). This 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 revised Sec. 5.4 states both links and the robustness of the floor to the combination rule, and App. H reports the new baselines, split and rules (Tabs. A.8–A.11).

AuthorsOpenReview ↗

Rebuttal (3/3)

Q1 (positive noise in N1 for indexing). The sentence in Sec. 5.3 and Example C.5 both concern noisy indexing with η > 0, where Example C.5 gives the order-tight bound. Setting η = 0 in its formula gives the case in the question, where N1 loses the logarithm. What separates the two is whether single observations are decisive. Positive noise is what keeps them from being decisive.

  • η > 0. The per-sample log-likelihood ratio is bounded by L = ln((1 − η)/η). If one observation's law differs between two candidates only on an event of probability ≤ p, then I(Y; Z₁) ≤ max_{θ,θ'} KL(P_θ‖P_θ') ≤ pL. Indexing has p = 2/n, so I₁ = O(1/n) and N1 keeps n ln n. Example C.5's exact leading term, I₁ = (1 − 2η) L / (n + 1), lies within this bound.
  • η = 0. One sample at coordinate j is decisive: under Y = τ_j it removes σ and every τ_i at once. Then I₁ = h₂(1/(n + 1)) ≈ ln n / n carries a ln n "surprise", and N1 falls to Θ(n), exactly as for SAT clauses.

Numerically, the single-letter N1 load stays at 0.32–0.38 for n = 300 to 10⁴ at η = 0, while the measured load λ* at which exact recovery reaches ½ equals the coverage value ln n − ln(2 ln 2), and at η = 0.1 the N1 load grows with ln n, from 1.24 to 2.23 (App. J.3, Tab. A.16).

The revised Sec. 5.3 adds this condition as the quantitative form of its metadata description: single observations that are coordinate-local and not decisive. App. C.20 states the bound I(Y; Z₁) ≤ pL as Lem. C.18.

Q2a (separate annotations for selection and channel estimation). Separating the annotations does not degrade the predictions. With band selection, channel estimation and measurement on three disjoint thirds of every item's annotations, the predicted budget λ*(n) differs from the measured one by 7% on average over the 5 split seeds and the subset sizes from 30 to 3000, and by 3–12% on each seed, against 9% for the paper's half-A prediction in Fig. A.8b. On the same thirds, predicting from the selection third raises the error to 17–20% on every seed, so the reuse, not the separation, is what costs accuracy. Under every split and seed the predicted λ*(n) grows with ln n, which is what the paper relies on. App. H of the revision reports these numbers.

Q2b (a different image–annotation combination rule). Nearly all of it remains. As in App. H, the floor is the set of items that no trial decodes correctly at λ = 30 on the full pool. We replaced the product rule by an overdispersed Dirichlet-multinomial annotation likelihood, with one concentration α = 13.05 fitted on half A against the gold labels, the same retrospective footing as the paper's confusion matrix. This rule recovers 7–12 more of the 86 hard items than the product rule, 55–65% of the gap to the models alone. The never-recovered count is nevertheless 17.6–18.6 against 14.8–15.6, and over the 15 models 89% of the items the product rule never recovers are still never recovered. Rerunning the product rule itself on an independent trial stream keeps 87% of them, so changing the rule moves no more items out of the floor than rerunning the same rule does. All numbers use 500 trials, and the counts are means over 5 seeds. Both rules decode the same votes as Tab. A.7, so the product-rule counts are the paper's.

ResNet-18ResNet-50ViT-B/16
hard items correct, model alone (no annotations)47.056.852.2
hard items correct, product rule (paper's rule)34.535.835.4
hard items correct, overdispersed rule41.647.446.2
never recovered in 500 trials, product → overdispersed14.8 → 17.815.0 → 18.615.6 → 17.6

Q3 (equal likelihood only for positive-likelihood candidates?). Yes. In the proof (App. C.3, linkage step) the hypothesis enters only through Σ_θ ω_z(θ)/(K_θ + 1) ≥ Σ_θ ω_z(θ)/|L(θ)|, where L(θ) is the set of candidates with the same likelihood as θ. Candidates with P_θ(z) = 0 have posterior weight ω_z(θ) = 0 and contribute to neither side. The revised Thm. 2.2 states the hypothesis for candidates with positive likelihood, and App. C.3 adds this one-line justification.

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

This paper works on finding the information-theoretic learning boundary below which there is not enough data for exact recovery of a finite structured target, even for a Bayes-optimal learner with infinite resources. The authors show that there needs to be a Fano-type count, i.e. enough information overall to distinguish the targets (N1), and also there needs to be enough evidence supporting each hidden coordinate (N2). They characterize this boundary for the planted k-SAT problem where the learner wants to learn a σ∈{0,1}n\sigma\in\{0,1\}^n with mm random clauses that σ\sigma satisfies. N1 says that Ω(n)\Omega(n) clauses are needed, but an extra log⁡n\log n factor is needed for the threshold at which the best learner can have exact recovery. Thm 4.1 shows that for mm around nlog⁡nn\log n, the set of satisfying assignments looks like a subcube whp, and the set of single flips that cannot be ruled out (WW) is Poisson(e−x)\text{Poisson}(e^{-x}). Thm 4.2 then shows that the probability that the answer is unique approaches ee−xe^{e^{-x}}, and Bayes and minimax success approaches e−e−x/2e^{-e^{-x}/2}. This shows that uniqueness requires around Δm≈nln⁡2⋅2k−1k\Delta m\approx n\ln2\cdot \frac{2^k-1}k many extra samples than recovery.

Their bounds recover Δm=73nln⁡n\Delta m=\frac 73n\ln n of Motoki-Uehara for k=3k=3.

Critical strengths

S1: I think this paper studies a fundamental problem in finding the thresholds at which the input data is enough to admit a unique solution, and when a learner can find the correct solution, for the planted kk-SAT problem.

S2: While I wasn't able to read the full appendix proofs, I think the method is instructional for me. The subcube structure appearing in Thm 4.1 is quite interesting for me.

S2: The experiments are limited, but they seem to support the theoretical claims on the asymptotics.

Critical weaknesses

W1: The weakness I can think of, is that the framing of the paper might be a bit too general. The N1 vs N2 framing is classical, as the authors pointed out, see for example [Candès-Tao, The power of convex relaxation: near-optimal matrix completion, IEEE ToIT 2010]. So I think the framing should be around kk-SAT results around Theorem 4.1 and 4.2 which are the new theorems in this work, instead of learning in general. Can the authors provide some discussion on this concern?

Questions for authors

See W1 above.

3 comments

We sincerely thank the reviewer for the thoughtful review and the positive assessment. We are glad that the reviewer finds the question fundamental and the subcube structure of Thm. 4.1 interesting and instructive.

W1 (framing too general, N1/N2 classical). Thms. 4.1 and 4.2 are the new theorems, together with their non-uniform extension Thm. 4.3, and the abstract, the introduction and the contribution list present them as the main results. General learning plays a different role in the paper. It states the question that these theorems answer, and it makes their content a statement about learning rather than about satisfiability alone. The revision makes this division of roles explicit.

Role of the learning question. The paper asks when a learner fails because the input itself is insufficient, and which property of the input decides this. This question serves three purposes.

  • It defines the object of study. The learning boundary is a property of the input: the point at which the observations themselves become sufficient for an optimal learner. This separates failures caused by the input from failures of representation, optimization or computation.
  • It turns the SAT theorems into statements about learners. Uniqueness asks whether a learner can certify its answer, and Bayes success asks whether the best learner outputs the target. Certifying therefore costs Θ(n) more samples than learning (Thms. 4.1 and 4.2), and at equal information per observation the allocation of evidence across coordinates moves the boundary (Thm. 4.3).
  • It organizes results beyond SAT. Tables 1 and 2 place five further learning families under the two requirements and check the predicted cost ratios. Sec. 5.4 measures the allocation effect on a real annotation channel (CIFAR-10H), where a pooled description of the channel misses the error floor by more than three orders of magnitude while an item-level description predicts it.

Classical and new parts. N1 and N2 formalize the two candidate answers to this question: the amount of information, and its allocation across the hidden coordinates. The coverage half is the same coupon-collector necessity that gives the log n factor in Candès–Tao's matrix-completion lower bound, which the revision now cites (Sec. 1, App. A). Planted k-SAT is the instance where the question can be answered completely, and the new results are there.

A coupon-collector argument gives a first-order necessity statement: below the threshold some coordinate is uncovered, so recovery fails. Thms. 4.1 and 4.2 give two things it does not.

  1. The complete solution set is exactly the subcube generated by the uncovered coordinates, with probability 1 − O(ln n / n). This requires ruling out every satisfying assignment at Hamming distance ≥ 2, including those with no surviving single flip. The covering count W is silent on these.
  2. This geometry yields two different limit curves inside the window: uniqueness exp(−e^{−x}), and Bayes and minimax exact recovery exp(−e^{−x}/2). The observations therefore allow an optimal learner to recover the planted target about ln 2 · (2^k − 1) n / k clauses before they determine it uniquely, a Θ(n) gap that is invisible at first order. For k = 3 the first-order threshold, shared by both curves, is Motoki and Uehara's (7/3) n ln n. Uniqueness then needs a further ln 2 · (7/3) n clauses on top of it.

Changes in the revision (shown in blue):

  • The contribution list (Sec. 1) and Sec. 4.2 now state that certifying the target costs Θ(n) more samples than recovering it, reading Thms. 4.1 and 4.2 as statements about learners.
  • A new paragraph in App. A places the paper among sample-complexity results for learning hidden structure. The paper asks the information-theoretic version of that question and answers it exactly in planted k-SAT.
  • Candès–Tao is cited as the classical source of the coverage half of N2 (Sec. 1, App. A).

Thank you very much for your clarifications, especially with the Thm 4.3. I think the updated version does a better job with the positioning of the paper. Also, during my first round of review I had missed the point that Thm 4.3 makes.

In my eyes, at least theoretically the work looks interesting. However, as I mentioned in the review, I have no direct research experience with the area. But still, I think the contributions of this work are interesting and passes the acceptance threshold. I will retain my score.

Thank you for your follow-up and for recognizing our clarifications, particularly regarding Thm. 4.3. We are glad that the revision improves the paper's positioning and clarifies the role of the non-uniform extension. We appreciate your assessment that the work is theoretically interesting and meets the acceptance threshold. Thank you for your continued support.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.