- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies fixed-budget crowdsourced clustering, proposes PSPCI combining posterior sampling with Hedge-style allocation, and proves that its posterior error exponent matches an instance-dependent information lower bound.
Critical strengths
- With fixed budget, unknown , and unknown number of clusters, the paper gives a universal lower bound on the posterior error exponent and shows PSPCI attains the same exponent with no asymptotic multiplicative gap.
- Different partitions pool observations differently, and an incorrect partition may fit with parameters other than . Bernoulli KL is unbounded near the boundary; the paper handles this via KL clipping, tempered posterior, and vanishing exploration.
- The motivation for fixed-budget crowdsourced clustering is natural: each pairwise query incurs a cost, so a budget constraint fits the crowdsourcing scenario. The related-work positioning is clear and the writing is clean.
Critical weaknesses
-
Algorithm-to-implementation gap. Exact projection and full-partition normalization in Eq. (8) are infeasible for Birds20 (); Sec. 6.2 omits the approximations used, hyperparameter choices, and whether theorem conditions still hold. Provide implementation/complexity details and a small- exact-vs-approximate comparison.
-
Oracle/baseline details and finite-budget scope. The oracle solver, computation budget, relation to , and near-global-optimality are unclear; add a uniform-query exact-posterior baseline on small . The main results are asymptotic ( fixed, ); discuss finite-budget error rates and whether experimental scales fall in the valid regime.
-
Narrow empirical support and small margins. Missing ablations: the individual contributions of KL clipping, projection, tempering, and exploration are not ablated, and no runtime/complexity is reported; the hyperparameters and are not assigned values, the experiments do not report the values used, and there is no sensitivity analysis. Narrow evidence: only one real dataset (Birds20), the real-data metric is pairwise error rather than exact recovery, and the advantage over the strongest active baseline is about 0.7 percentage points; PSPCI's early pairwise error is higher than that of the other active methods, the paper acknowledges "early performance leaves room for improvement" but does not explain why. Additional real datasets or larger-scale synthetic experiments, together with a discussion of the early-phase disadvantage, would strengthen the empirical support.
Questions for authors
See Weaknesses.
2 comments
A Gentle Follow-up on Our Response
Dear Reviewer 1M36,
As the discussion period draws to a close, we wanted to follow up on our response above. We have provided implementation details and runtime measurements, the requested exact-versus-variant and uniform-query comparisons, ablations of all four components, and additional Dogs3-derived experiments. We have also clarified the oracle baseline and the scope of our theoretical guarantees.
We would appreciate hearing whether these additions address your concerns, or whether any specific issues remain that we can clarify during the remaining discussion period.
Thank you again for your time and constructive feedback.
Rebuttal to Reviewer 1M36
Thank you for the constructive review. Our focus is theoretical: a universal posterior-error lower bound and a matching PSPCI upper bound establish the optimal almost-sure posterior error exponent.
1. Algorithm-to-implementation gap.
Thank you for identifying this presentation gap. The small synthetic experiments implement Algorithm 1 exactly. For Birds20 (N=125), we use a variant with two substitutions: local Hamming projection and neighborhood-normalized posterior recommendation. These substitutions avoid direct enumeration of all BN partitions, where BN is the Bell number, which makes the full-enumeration implementation impractical at this scale. The tempered-posterior competitor sampling, clipped KL gains, Hedge updates, and prescribed uniform exploration are retained. These two substitutions preserve the asymptotic posterior-error upper bound established in Theorem 2.
Projection: warm start, strict unweighted Hamming descent over all merges/singleton splits to local optimality, deterministic ties. It runs initially and after majority-sign changes. Recommendation uses ordinary posterior weights on the anchor plus its complete merge/split neighborhood. We will add pseudocode/settings.
Correct signs ensure recovery: mixed clusters admit improving singleton splits and truth fragments improving merges. Neighborhood reduction preserves the exponent.
Exact/variant and ablations: N=6, truth 1,2,34,5,6, p=.6,q=.4,T=5000, 50 runs, uniform priors; defaults α=.25,cB=1,κT=T,ηT=T−1/2, BT=cBlog(T+1). Cumulative exact-recovery curves closely track to about 90%. Exact vs. variant
For K=N(N−1)/2, gain scans cost O(K). Integer loss in [0,K] permits at most K improving moves: O(K2) per projection. Hedge: O(K) per round. For M clusters of sizes sj,
H=M(M−1)/2+∑j=1M(2sj−1−1).
Direct weight evaluation costs O(KH) per pass. Splits remain exponential in cluster size; restrictions are additional approximations. One Birds20 profile: H=3050, 43 ms/recommendation (1.7 ms/query, amortized over the evaluation grid).
2. Oracle, uniform baseline, and finite budgets.
Oracle allocation uses true parameters and all merge/split neighbors; SciPy/HiGHS solves its max-min LP. Decoupling shared alternative parameters gives the pairwise-KL lower-bound relaxation of Eq. (2). Numerical optimality applies only to this LP, not Eq. (2). Queries use its fixed allocation; recommendation is weighted projection of observed counts. LP settings/timing/optimality checks will be added.
Uniform querying retains Algorithm 1's ordinary full-partition posterior recommendation, isolating allocation. At N=6,T=700, Algorithm 1 reaches about 81% versus uniform's 74%. Uniform baseline Original experiments use finite T=5000; theory is asymptotic.
3. Ablations and empirical support.
Same protocol, one component varied; cumulative exact-recovery accuracy at T=5000:
Projection needs substitution: its anchor defines competitors and pooling. Effects are small here. One instrumented run: max unclipped KL 4.2 nats (default clip 8.5). Two runs without forced exploration: minimum pair counts 279–283 (uniform expectation 333). Clipping bounds gains; forced exploration ensures coverage.
Dogs3 simulations use worker-log estimates of per-pair one-vote probabilities [1]: 20 sub-instances, 3 breeds × 2 images, 4 seeds each (80 runs). At T=5000, exact Algorithm 1 attains 94.8% cumulative exact recovery; exact/scalable versions outperform Track-and-Stop and passive spectral Dogs3 recovery. Early performance may be limited by uncertainty in the partition and shared response parameters, requiring more pairwise observations before posterior-based allocation and recommendation become reliable.
If we have addressed your concerns, we would appreciate your consideration of a higher score.
[1] Chen, Yi, Ramya Korlakai Vinayak, and Babak Hassibi. "Crowdsourced clustering via active querying: Practical algorithm with theoretical guarantees." Proceedings of the AAAI Conference on Human Computation and Crowdsourcing. Vol. 11. 2023.