acceptodds
Under review as a conference paper at ICLR 2027

Optimal Posterior Sampling for Fixed-Budget Cluster Identification through Pairwise Observations

Abstract

We study fixed-budget cluster identification from noisy pairwise observations. A collection of items is partitioned into an unknown number of clusters. Querying a pair produces a Bernoulli response with an unknown mean if the items belong to the same cluster and otherwise. We establish an instance-dependent lower bound on the posterior probability of an incorrect clustering that holds for every adaptive sampling rule. Its exponent is given by a max–min allocation problem that maximizes the minimum weighted Bernoulli KL divergence between the true instance and alternatives with incorrect clusterings. We propose an adaptive algorithm that combines posterior sampling over neighboring alternatives, an exponential-weights learner over pairs, and vanishing uniform exploration. We prove an upper bound on the algorithm's posterior error probability that matches the lower bound at the exponential scale. The algorithm therefore achieves the optimal instance-dependent posterior error exponent almost surely. Experiments on synthetic instances and real-world datasets demonstrate competitive cluster identification performance against existing baselines.

Primary area:
reinforcement learning
Keywords:
Active clustering, fixed-budget identification, multi-armed bandits, posterior sampling

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_1M36OpenReview ↗
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
  1. With fixed budget, unknown p,qp,q, 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.
  2. Different partitions pool observations differently, and an incorrect partition may fit with parameters other than (p∗,q∗)(p^{*},q^{*}). Bernoulli KL is unbounded near the boundary; the paper handles this via KL clipping, tempered posterior, and vanishing exploration.
  3. 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
  1. Algorithm-to-implementation gap. Exact projection and full-partition normalization in Eq. (8) are infeasible for Birds20 (N=125N=125); Sec. 6.2 omits the approximations used, hyperparameter choices, and whether theorem conditions still hold. Provide implementation/complexity details and a small-NN exact-vs-approximate comparison.

  2. Oracle/baseline details and finite-budget scope. The oracle solver, computation budget, relation to Γ∗(θ∗)\Gamma^*(\theta^*), and near-global-optimality are unclear; add a uniform-query exact-posterior baseline on small NN. The main results are asymptotic (NN fixed, T→∞T\to\infty); discuss finite-budget error rates and whether experimental scales fall in the valid regime.

  3. 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 α\alpha and cBc_B 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
AuthorsOpenReview ↗

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=125N=125), we use a variant with two substitutions: local Hamming projection and neighborhood-normalized posterior recommendation. These substitutions avoid direct enumeration of all BNB_N partitions, where BNB_N 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=6N=6, truth 1,2,34,5,6\\{1,2,3\\}\\{4,5,6\\}, p=.6,q=.4,T=5000p=.6,q=.4,T=5000, 50 runs, uniform priors; defaults α=.25,cB=1,κT=T,ηT=T−1/2\alpha=.25,c_B=1,\kappa_T=\sqrt T,\eta_T=T^{-1/2}, BT=cBlog⁡(T+1)B_T=c_B\log(T+1). Cumulative exact-recovery curves closely track to about 90%. Exact vs. variant

For K=N(N−1)/2K=N(N-1)/2, gain scans cost O(K)O(K). Integer loss in [0,K][0,K] permits at most KK improving moves: O(K2)O(K^2) per projection. Hedge: O(K)O(K) per round. For MM clusters of sizes sjs_j,

H=M(M−1)/2+∑j=1M(2sj−1−1).H=M(M-1)/2+\sum_{j=1}^M(2^{s_j-1}-1).

Direct weight evaluation costs O(KH)O(KH) per pass. Splits remain exponential in cluster size; restrictions are additional approximations. One Birds20 profile: H=3050H=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=700N=6,T=700, Algorithm 1 reaches about 81% versus uniform's 74%. Uniform baseline Original experiments use finite T=5000T=5000; theory is asymptotic.

3. Ablations and empirical support.

Same protocol, one component varied; cumulative exact-recovery accuracy at T=5000T=5000:

  • Clipping: cB∈0.1,0.25,1,4,10c_B\in\\{0.1,0.25,1,4,10\\}, plus off: 89.5–89.9%. KL clipping
  • Tempering: κ∈1,10,T,T\kappa\in\\{1,10,\sqrt T,T\\}: 89.5–89.7%. Tempering
  • Projection: exact/local/profile likelihood/Pivot: 89.5/89.4/89.7/88.7%. Projection
  • Exploration: α∈0.1,0.25,0.4\alpha\in\\{0.1,0.25,0.4\\}, plus off: 89.8/89.5/89.5/89.5%. Exploration

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=5000T=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.

AuthorsOpenReview ↗

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.

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

This paper studies the cluster identification problem under pairwise queries. The goal is to minimizes the posterior error under a fixed budget of observations. Matching instance-wise upper and lower bounds have been established, thus the algorithm is optimal . Experimental results also show improvment over existing benchmarks. It appears that this is a solid paper with strong theoretical results. The problem fall within the scope of ICLR and matching upper and lower bounds are very interesting.

I will recommand to accept this paper but I also have a minor concern about the paper's presentation quality. The paper is overall very technical and not easy to follow for readers not working in related directions. The algorithm parts lack intuition and comparisons with prior work, making it difficult to grasp the technical contributions. Although the lower bound result was prominently presented the paper, the techniques used to establish it were not introduced or sketched in the main text.

Critical strengths

Strong theory paper with sufficient technical depth. The matching upper and lower bounds are impressive.

Critical weaknesses

none

Questions for authors
  1. What is your main technical contribution in proving the lower bound?
  2. Do you have any upper bounds for finite T? Namely, for a fixed budget T, what kind of misclassification error bound can you obtain?
1 comment
AuthorsOpenReview ↗

Rebuttal to Reviewer DqAx

Thank you for the constructive feedback.

Clarity and intuition. The min-learner proposes a competing partition and response parameters that explain the data; the max-learner shifts queries toward pairs that distinguish this competitor from the empirical reference. Merge alternatives concern pairs across current clusters, while split alternatives concern pairs within a cluster. This implements the min-max information-allocation objective. Projection supplies a valid anchor, tempering moderates posterior concentration, clipping bounds KL gains, and exploration ensures pair coverage.

Posterior sampling and exponential weights are established tools, also used in the Gaussian linear framework of Li et al. (2024); the merge/split reduction follows Teo et al. [2]. Our analysis addresses partition-dependent pooling, unknown shared Bernoulli parameters, and KL boundary effects. We will add this intuition and a lower-bound proof overview before the formal statements.

Q1. Main technical contribution to the lower bound.

We extend Russo's posterior-convergence framework [1] to fixed-budget latent partition identification with unknown shared response probabilities. Russo's theorem does not apply directly: the pair means satisfy μe(c,p,q)=q+(p−q)1c(i)=c(j)\mu_e(c,p,q)=q+(p-q)\mathbf{1}\\{c(i)=c(j)\\}. Their induced prior lies on a finite union of families of dimension at most two, and is singular in the ambient pair-mean space when ∣I∣>2|\mathcal I|>2, violating the full-dimensional density assumption in [1].

For each fixed candidate partition cc, we integrate out its shared parameters:

mT(c)=∫LT(c,p,q),νp(dp)νq(dq).m_T(c)=\int L_T(c,p,q)\\,\nu_p(dp)\nu_q(dq).

Each partition pools observations differently, potentially mixing samples generated under p∗p^{\ast} and q∗q^{\ast}. We establish the exponent of this integrated evidence.

For any adaptive sampling rule, on a common probability-one event, along every subsequence with λ^Tk→λ\widehat\lambda_{T_k}\to\lambda,

\to J_c(\lambda) :=\inf_{p\in\mathcal P,q\in\mathcal Q} \sum_e\lambda_e d(\mu_e^{\ast},\mu_e(c,p,q)).$$ Pooled likelihood-integral estimates and a local prior-mass argument establish this result for the fixed full-support product priors of Theorem 1, without requiring prior densities. The argument covers zero-weight pools and infima approached at $1/2$. Bayes' rule combines finitely many partition evidences. Since the partition prior is positive and fixed and $J_{c^{\ast}}(\lambda)=0$, the posterior error exponent along this subsequence is $\min_{c\nsim c^{\ast}}J_c(\lambda)$. A martingale law supplies the common event; compactness removes the need for convergence of the full allocation sequence, yielding $$\limsup_{T\to\infty}-\frac1T\log\Pi_T(\operatorname{Alt}(\theta^{\ast})) \le\sup_{\lambda\in\Delta(\mathcal I)} \min_{c\nsim c^{\ast}}J_c(\lambda)=\Gamma^{\ast}(\theta^{\ast}) \quad\text{a.s.}$$ Thus [2] supplies the population merge/split reduction, while our contribution connects integrated partition evidence to the posterior error bound. **Q2. Finite-budget upper bound.** Yes. Under Theorem 2's settings, Appendix B.4 gives, for each fixed instance and all $T\ge T_{\rm inst}$, where $T_{\rm inst}$ is finite and instance-dependent, $$\mathbb{P}_{\theta^{\ast}}\\!\left( \Pi_T(\operatorname{Alt}(\theta^{\ast}))\le e^{-T[\Gamma^{\ast}(\theta^{\ast})-\xi_T]} \right)\ge1-\frac4{T^3}.$$ Here $\xi_T\to0$ is the explicit deterministic remainder $$\xi_T=\frac{R_T^{\max}+R_T^{\min}}T+r_T^{\rm ps} +B_T\left(\bar\gamma_T+r_T^{\rm tr}+\frac{2s_T}T\right) +2r_T^\ell+\frac{\log J_0}T.$$ Here $\bar\gamma_T=T^{-1}\sum_{t=1}^T\gamma_t$. These terms account for learner regret, sampling/reference errors, exploration, allocation tracking, initial recovery, and marginal-likelihood approximation; $J_0$ counts incorrect canonical partitions. For the ordinary posterior-draw recommendation, the unconditional misclassification probability equals the expected posterior mass on incorrect partitions. Splitting this expectation over the good event and its complement gives $$\mathbb{P}_{\theta^{\ast}}(\widehat c_T\nsim c^{\ast}) \le\min\left\\{1,e^{-T[\Gamma^{\ast}(\theta^{\ast})-\xi_T]}+\frac4{T^3}\right\\}.$$ We will state this consequence explicitly. Our optimality claim concerns the almost-sure posterior error exponent; sharper finite-budget guarantees remain open. [1] Russo, Daniel. "Simple bayesian algorithms for best-arm identification." Operations Research 68.6 (2020): 1625-1647. [2] Teo, Rachel SY, et al. "Almost Asymptotically Optimal Active Clustering Through Pairwise Observations." arXiv preprint arXiv:2602.05690 (2026).
Reviewer_4fBhOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the problem of clustering a given set of objects using noisy pairwise observations. In particular, the oracle returns a positive answer with probability p>1/2p>1/2 if two objects belong to the same cluster, and with probability q<1/2q<1/2 if they belong to different clusters. Repeating a query gives a fresh independent observation. In the literature, this problem has typically been studied from the other side, where the goal is to minimize the number of queries required to recover the clustering with a prescribed confidence. In this paper, the authors instead focus on what is the best that can be achieved given a fixed budget of TT queries.

An interesting question in this setting is how to formalize what an algorithm should compete against. The authors consider the posterior probability assigned to all incorrect clusterings, and more specifically, the exponent governing how quickly this probability decreases with the query budget. They formalize the optimal rate through a max-min information allocation problem and prove that no adaptive sampling algorithm can achieve a larger exponent.

Their main algorithmic contribution is an adaptive algorithm that achieves this rate without knowing the ground-truth clustering or the oracle's error probabilities. Roughly speaking, the algorithm maintains a current guess of the clustering and a distribution over possible queries. It samples a plausible alternative from a family of nearby clusterings and uses a multiplicative-weights update rule to prioritize queries that help distinguish the two. The analysis combines regret bounds with concentration arguments to establish the optimal posterior error exponent.

Critical strengths
  1. The paper is well-written and conceptually clean, and the objective is natural. The general problem is also relevant.

  2. The main algorithm effectively combines Hedge with posterior sampling and known structural results about the information allocation problem to achieve the optimal posterior error exponent. While the individual ingredients are largely known, the overall approach is elegant, and the analysis is technically interesting.

Critical weaknesses

None.

Questions for authors

None.

1 comment
AuthorsOpenReview ↗

Rebuttal to Reviewer 4fBh

We thank the reviewer for the positive evaluation. We appreciate the recognition that the paper is well-written and conceptually clean, the overall approach is elegant, and the analysis is technically interesting.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.