- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies statistical analysis in a situation where we receive sampled truth assignments and a Boolean query over the variables, and we wish to predict the probability that the query is true. This is the case, for example, in query evaluation over probabilistic databases. Using a synthetic benchmark with 16 binary variables divided into four dependency groups of four variables, the paper examines how much prediction error is unavoidable because of limitations in the information supplied to the model, and how well different prediction models learn true dependencies among variables from the sampled assignments. The authors derive error bounds and compare neural models with statistical methods.
Critical strengths
- The paper seems to study a fundamental problem in statistical analysis.
- The paper includes a thorough set of experimental results.
Critical weaknesses
-
The paper studies a very narrow problem: the probability of a monotone DNF over four variables, in the context of the specific benchmark that consists of a total of 16 variables. The theoretical propositions are, in fact, specific to this setting.
-
I found the presentation quite misleading. The paper presents itself as discussing Boolean queries over relational data, and references Dalvi and Suciu, who coined the term and opened a rich line of research. This reference appears in the introduction, and the terminology is already apparent in the title. Yet, the paper has very little to do with probabilistic databases. It applies to DNF inference, which is used in probabilistic databases, but it analyzes the case of 16 variables (corresponding to databases with 16 tuples).
-
The theoretical analysis is very basic and provides little insight. These are essentially short calculations within the chosen sampling mechanism.
-
The paper is very hard to read. Even the abstract is very difficult to grasp. It uses very technical terms and does not seem to address the ICLR audience.
Questions for authors
None.
2 comments
Thank you for the feedback
I received your feedback and plan to consult the other referees about the implications for the recommendation.
The theoretical scope must be distinguished from the experimental dimensions. The two-point bound applies to task pairs with equal input laws and different targets, independent of the number of variables (§3.1; Appendix A). The exchangeable-law characterization is stated for arbitrary finite n (§3.3). Consequently, the assertion that the theoretical propositions are specific to four query variables and a 16-variable benchmark is not a valid restriction on those results as now stated. The standard four-variable parity construction and the finite experimental design do not impose that restriction. This establishes scope, not theoretical novelty or computational tractability.
The task is probability estimation from sampled binary worlds. Possible-world databases provide related semantics; they are not a database-engine evaluation in this paper (§§1–2, 7). The revised abstract and introduction state the actual task explicitly. The appropriate remaining question is whether this task and its diagnostic findings have sufficient significance, rather than whether the paper delivers general database inference.
Standard ingredients do not settle the contribution assessment. We do not claim to invent the squared-loss identity, parity construction or reliability polynomial. Section 2 and Table 23 also credit usable information, PVI and OpenRFM. The specific contribution to assess is the protocol: establish equal available inputs, confirm a target gap, and obtain a risk floor for every predictor restricted to that input. A loss comparison between fitted candidates alone does not establish such a floor.
The revision tests this beyond exact synthetic targets: held-out query outcomes from a school recording confirm 88 of 160 selected encoding-collision pairs (§6.1; Table 5). This is a finite recorded population with generated queries and deliberate encodings, not proof of a deployed model bottleneck. The public-model intervention and audit-inspired selector both have adverse results (§§6.2–6.3; Figure 3); neither is presented as an improvement. Broad practical utility remains open.
Readability has been revised at the entry point. Figure 1 explains probabilities 1/4 and 3/4, their forced common prediction 1/2, and equal-pair MSE 1/16. Figure 2 sets out discovery and confirmation. Proposition 2 and Appendix A.1 specify the extra workload weights and partial-outcome assumptions. The more complex construction moves to the appendix.
We ask that the scope restriction be reconsidered against the stated results, and that any remaining rejection rationale identify which contribution is insufficient after these clarifications and additions. A judgment of limited novelty is distinct from a claim that the results only apply to four variables.
A concrete accuracy decision. For aligned/crossed queries under common shock, Set-shape has probability MSE 0.02105 against an analytic floor of 0.020625. Thus, an MSE target of 0.01 is unattainable for every predictor restricted to that shape interface on this balanced task population, regardless of further training. Set-full with named incidence reaches 0.004814, with a paired difference of -0.01624 and 95% interval [-0.01841, -0.01413] (§5.1, Table 3). The certificate identifies a constraint on attaining a specified accuracy.
An empirical insight about model evaluation. On the support-collision pair, adding incidence increases fitted-model risk by 0.000234, with 95% interval [0.000124, 0.000378], although richer information cannot increase Bayes risk (§5.1). This reversal shows how learner excess can obscure the value of input refinement. The controlled benchmark makes that discrepancy quantitatively checkable.
A procedure when exact targets are unavailable. After fixing the interface and selecting pairs on discovery data, independent confirmation draws supply query-outcome gap bounds. On the school recording, the strongest confirmed gap is at least 0.2284, yielding an equal-pair MSE floor of at least 0.01304 (§6.1, Table 5). The recorded queries use 4-12 variables and connected supports, extending the test beyond the original seven templates. The target population is uniform sampling from the finite recorded bins. This supplies a certificate from observed outcomes under explicit sampling assumptions.
A precise workload-level output. Proposition 2 converts within-class gaps into a weighted catalog-risk certificate using the declared query weights and full encoding-class masses, including overlapping pairs. Proposition 4 extends confirmation to incomplete outcomes through sound truth bounds. These results make the required inputs, scope and confidence explicit. The mathematical tools are established. The contribution claim concerns their specified diagnostic use, controlled calibration and recorded-outcome confirmation. We ask that the significance assessment address these outputs and findings.