| paper | d4-conf-aaai-2018-0565 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 2
Given \(n\) items, a distribution \(\mu\) over observable worker types \(t\), type-specific Gaussian response variances \(\sigma_t^2\), per-capita task capacities \(b_t\), a Gaussian prior with variance \(\sigma_x^2\), and a total task budget \(B\), choose query masses \(q_{ijt}\ge 0\) with \(\sum_{i<j}q_{ijt}\le b_t\mu_t\) and \(\sum_{t,i<j}q_{ijt}=B\) to maximize \(\frac12\log\det\!\left(I+\sigma_x^2\sum_{t,i<j}\frac{q_{ijt}}{\sigma_t^2}d_{ij}d_{ij}^{\top}\right)\), where \(d_{ij}=e_i-e_j\). Does this continuous design problem admit an efficient \(\varepsilon\)-optimal algorithm, and how does its optimum compare with the paper’s sequential greedy EIG rule?
A batch Bayesian design over a society of worker types with masses \(\mu_t\): allocate query mass \(q_{ijt}\) across item pairs and types, subject to per-type capacities and total budget, to maximize the Gaussian-prior log-determinant information objective.
The mirror assumes the requester can observe worker types and route task mass by type, while the paper assigns pairs to random workers whose quality is unknown; this confines the mirror to a more controlled workforce regime.
fatal: False
The mirror covers the Bayesian expected-information-gain sampling result anchored by Proposition 2 and its use in Algorithm 2. It leaves aside Theorem 1’s Hodge decomposition, Fisher-information sampling, and the topology experiments.
The strongest positive case is a narrow one: Bayesian active sampling. The closest anchor is Proposition 2, proved in the supplementary materials. Given the current posterior and a proposed pair \(i,j\), it writes the next posterior mean as a rank-one update and reduces the KL divergence between the new and current posteriors to a scalar expression. With \(d=e_i-e_j\), \(A_t=L_t+\gamma I\), and \(C=dA_t^{-1}d^\top\), the update is
\[
\mu_{t+1}=\mu_t+\frac{y_{ij}^{t+1}-d\mu_t}{1+C}A_t^{-1}d^\top.
\]
The proposition’s displayed KL formula uses \(\log(1-C)\); that appears to be a sign error, since the determinant lemma for the stated rank-one precision update gives \(\log(1+C)\). Its computational point survives: with the inverse maintained, each candidate pair’s information gain can be evaluated from scalar quantities, without a fresh matrix inversion. Algorithm 2 uses this result to choose the next pair. This is a named algorithmic result, though it is not a theorem asserting that a problem is in P or giving a formal complexity bound. If only complexity-class theorems qualify as anchors, this paper has no qualifying anchor.
A plausible continuous mirror is Continuous Population Bayesian Pairwise Sampling. The agents are crowd workers; a type \(t\) specifies their pairwise response model, noise level, and per-worker task capacity. The society is a distribution \(\mu\) over the finite set \(\mathcal T\) of worker types. For \(n\) items, let \(d_{ij}=e_i-e_j\), and let \(q_{ijt}\) be the mass of type-\(t\) workers assigned to compare items \(i,j\). Given a task budget \(B\), prior covariance \(\sigma_x^2 I\) over the HodgeRank score vector, type-specific Gaussian noise variances \(\sigma_t^2\), and per-capita capacities \(b_t\), choose \(q\) satisfying
\[
q_{ijt}\ge 0,\qquad
\sum_{i<j}q_{ijt}\le b_t\mu_t,\qquad
\sum_{t,i<j}q_{ijt}=B
\]
to maximize
\[
F(q)=\frac12\log\det\!\left(
I+\sigma_x^2\sum_{t,i<j}\frac{q_{ijt}}{\sigma_t^2}d_{ij}d_{ij}^{\top}
\right).
\]
The solution is an allocation of query mass across item pairs and worker types, with an \(\varepsilon\)-optimal allocation counting as a solution. For \(W\) workers with \(W_t/W=\mu_t\), the integer version assigns whole workers to comparisons; \(q\) is the high-multiplicity relaxation. Large online labeling tasks with many workers and a small number of stable response and capacity profiles give a plausible regime for \(W\gg\tau\).
I expect this batch mirror to be tractable: \(F\) is concave in \(q\), and the constraints are linear, so standard continuous optimization gives an \(\varepsilon\)-optimal solution in time polynomial in the instance dimensions and accuracy parameters, under the usual conditioning assumptions. The connection to Proposition 2 is that the batch information gain is the accumulated version of the one-step EIG the paper evaluates. Workers remain the population being sampled, and the goal remains spending a labeling budget to reduce uncertainty about the same global ranking. A natural next question is how the paper’s sequential greedy rule compares with the batch optimum.
The weak point is that the paper studies sequential selection of one item pair at a time, assigning it to a random worker; it does not model a distribution over worker types or solve this batch allocation problem. Worker types and capacity constraints are a plausible high-multiplicity extension of its crowdsourcing setup, but the connection is not established by Proposition 2 alone. This mirror covers the supervised EIG sampling result, not the unsupervised Fiedler-value method, the Hodge decomposition theorem, or the topology experiments.
The strongest case against starts with a mismatch in what the paper establishes. Theorem 1 is a decomposition result, and Proposition 2 gives a rank-one posterior update; neither states the complexity of a computational problem. The reported running times are experimental. Proposition 2 is useful machinery, but it does not by itself define a population-level problem whose complexity landscape the programme could chart.
The proposed batch mirror also changes the decision the paper studies. The paper chooses an item pair, then assigns it to a randomly chosen worker; it emphasizes that worker quality is heterogeneous and unknown in advance. The proposed variables \(q_{ijt}\) instead let the requester route worker mass by type, and require known type-specific noise and capacities. Those assumptions make the optimization meaningful, but they add control over the workforce that the paper does not have. Preserve random worker assignment and the type-specific capacity constraints no longer describe a choice available to the requester. If worker type is hidden, the mixture of response models may also break the Gaussian posterior and log-determinant objective. If all workers are interchangeable, the type distribution contributes little beyond a scale factor.
There is a related gap between Proposition 2 and the proposed objective. The proposition is derived for a Gaussian likelihood and prior, while the experiments use binary labels and discuss approximating their predictive distribution. Its displayed formula also has a sign error: the determinant update gives \(\log(1+C)\), not \(\log(1-C)\). Correcting that sign preserves the rank-one calculation, but it does not establish that the paper’s sequential, worker-randomized procedure is the batch allocation problem in the proponent’s formulation.
Those objections defeat the proposed formulation as a direct mirror of the paper. They do not defeat the better version of the mirror. In a large labeling workforce with observable, stable worker types, per-capita task capacities, and conditionally independent Gaussian responses, a distribution over worker types is sensible. Allocating query mass across pairs and types then gives a genuine continuous-population design problem; finite worker assignments map to mass allocations as the workforce grows. The log-determinant objective is a faithful information measure under those assumptions. That is close enough to the paper’s aim of spending labeling effort to learn a global ranking that I cannot honestly rule out every worthwhile mirror. The negative case is strongest on the gap between the paper and the proposed model; it is weak against this better, explicitly stated workforce regime.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.