{"id":"0eb0c9c3-6da9-4208-a487-315029b657e6","arxiv_id":"2501.19285","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"OneBatchPAM runs FasterPAM-style local search on an objective estimated from one random log-sized batch, cutting dissimilarity complexity to O(n log n) while matching FasterPAM quality on tested datasets.","lead":"This paper introduces OneBatchPAM, a k-medoids clustering algorithm that estimates the clustering objective from a single small random batch of data points, reducing pairwise dissimilarity computations from O(n^2) to O(n log n). It matters because it promises large-scale k-medoids clustering with quality close to the standard PAM method but at a fraction of the runtime.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof does not control the ranking of improving swaps, so OneBatchPAM can pick a different medoid for the same data point; exact same-medoid guarantee is unproven.","rationale":"I read the paper in good faith. The proof's Eq. (11) step is actually valid because 4 log(2Tn/delta) >= 2 log(2Tn^2/delta) for all T >= 1, delta <= 1, so the reader's algebra concern is a red herring. However, a more serious gap exists: the proof controls only whether each evaluated swap is better or worse than the current medoid set, not whether the empirical best swap for a fixed data point coincides with the true best. Since Algorithm 2 picks l* = argmax_l G_i^l for each i, sampling noise can make a suboptimal improving swap look best, producing a different medoid set. This event is outside the union bound over P_t. The paper's own limitation section concedes the algorithm usually does not return exactly the same medoids, which is consistent with this gap. The theorem could be repaired by proving a stronger margin condition (gap between best and second-best swaps) or by weakening the claim to an objective-approximation guarantee; either way the current Theorem 1 is not established. The empirical results are useful and the algorithm is plausible, so I recommend conditional acceptance rather than rejection.","tokens_in":21173,"tokens_out":24435,"duration_ms":231767,"concrete_test":"Synthetic test: build n=1000 points, k=2, D=1, with a first-step configuration where two swaps for the same data point improve the objective by 0.51 and 0.50 (all other swaps have loss >= 10, so Delta = 0.50). Set delta=0.01, T=1; the theorem gives m ~ 195. Draw X_m uniformly, run OneBatchPAM and FasterPAM from identical random initialization, and record whether the final medoid sets are identical; repeat 10,000 times. If the exact-match frequency is below 0.99, Theorem 1's guarantee fails in this regime, confirming the ranking/argmax gap.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 1 (Appendix B) bounds, for each swap pair evaluated by FasterPAM, the probability that the empirical objective crosses the current objective. For the selected improving pair, it bounds P(hat{L}(M_t^{x_t,x'_t}) >= hat{L}(M_t)); for rejected pairs in P_t, it bounds P(hat{L}(M_t^{x,x'}) <= hat{L}(M_t)). This is insufficient because Algorithm 2 (and FasterPAM) for a fixed data point x_i chooses the medoid l* with the largest gain, i.e., the smallest empirical objective among all k candidate swaps. The proof never controls the probability that a different improving swap at the same x_i has a larger empirical gain than the true best swap. Since the Hoeffding error C can exceed the true gain margin between the best and second-best improving swap, OneBatchPAM may pick a different medoid and diverge from FasterPAM's trajectory. This event is not covered by the union bound over P_t, because those pairs are not in P_t (they are improving, just not maximal). The reader's claimed algebraic gap in Eq. (11) is not real: 4 log(2Tn/delta) >= 2 log(2Tn^2/delta) holds for all T >= 1 and delta in (0,1]. The genuine gap is the omitted ranking control; the theorem as stated is therefore not proven. Repairing the proof requires either a margin Delta' = min gap between the best and second-best candidate objectives (which can be arbitrarily smaller than Delta) or a weaker guarantee (objective approximation rather than exact same medoids).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces OneBatchPAM, a k-medoids local-search algorithm that estimates the PAM objective using a single random batch of size m drawn once from the dataset. The authors claim (Theorem 1) that m = O(log n) suffices, with probability at least 1 - delta, to reproduce the exact sequence of swaps of FasterPAM, yielding a time complexity of O((p + T)n log n) (Corollary 2). The empirical section compares OneBatchPAM variants against FasterPAM, BanditPAM++, FasterCLARA, k-means++ and related methods on small- and large-scale real datasets, reporting that OneBatchPAM (especially the NNIW variant) achieves objectives within about 2% of FasterPAM while running substantially faster.","tokens_in":21512,"tokens_out":4574,"duration_ms":46954,"significance":"If the main theorem were correct, the result would be significant: it would give a k-medoids local-search method with near-PAM quality at O(n log n) dissimilarity computations, improving on FasterPAM's O(n^2) and BanditPAM's O(T n log n). The empirical study is a genuine strength: the authors provide code, use public datasets, report standard deviations, and show consistent speedups with small objective degradation. The paper also honestly discusses limitations, including the dependence on the unknown margin Delta and the risk of overfitting on imbalanced data, which is commendable. However, the central theoretical guarantee is not proven as stated, and the authors' own limitation section concedes that in practice the algorithm does not return exactly the same medoid set as FasterPAM.","major_comments":[{"comment":"The proof does not establish the claim that OneBatchPAM performs the same swaps as FasterPAM. For each data point i, Algorithm 2 (line 17) selects the medoid l* maximizing the empirical gain G_i^l, so the decision depends on the ranking of the k candidate swaps at that point. The proof bounds, for each rejected pair (x,x') in P_t, the probability that its empirical objective falls below the current empirical objective, and for the single selected pair (x_t,x'_t) the probability that its empirical objective rises above the current one. These are pairwise bounds; they do not control the event that a different improving pair at the same x_i has a larger empirical gain than the true best pair. The union bound in Eq. (25) covers only pairs in P_t (non-improving pairs) and the selected pair, not the improving-but-not-selected pairs whose empirical gains could be inflated by sampling error. Consequently, the event that OneBatchPAM picks a different medoid for the same data point, or a different data point, is not included in A, and the theorem is not proven. A repair would require a margin between the best and second-best candidate gains, or a weakened guarantee such as high-probability closeness of the objective value.","section":"Appendix B, proof of Theorem 1"},{"comment":"The paper's own limitation paragraph states that if two objectives are close, OneBatchPAM 'may estimate that adding x to the set of medoids instead of x′ is more efficient while FasterPAM may do the opposite,' and that in experiments OneBatchPAM 'provides close objectives compared to FasterPAM (around 2% error) but not exactly the same.' This directly contradicts the exact same-medoid conclusion of Theorem 1 and indicates that the theorem's guarantee is not achieved by the practical algorithm with the heuristic batch size m = 100 log(kn). The authors should either revise Theorem 1 to state a weaker, defensible claim (e.g., high-probability approximation of the objective) or provide a proof that the exact-swap event holds under the stated sample-size condition.","section":"Discussion and Limitations, 'Minimum sample size of OneBatchPAM derived in Theorem 1'"},{"comment":"Corollary 2 asserts time complexity O((p + T)n log(n)) from the logarithmic batch size, but the bound in Theorem 1 is m ≥ (4D²/Δ²) log(2Tn/δ), where Δ is an instance-dependent margin that can be arbitrarily small. Thus the logarithmic dependence on n comes with a constant that is not uniform over instances and can be enormous when near-tie swaps exist. The paper acknowledges in the Discussion that the exact value of Eq. (4) 'may be disproportionate' and that in practice m is chosen heuristically proportional to log n. Given that, the clean complexity statement of Corollary 2 is not justified by the theorem as written; the conditional dependence on Δ should be stated explicitly in the corollary.","section":"Corollary 2 and complexity statement"}],"minor_comments":[{"comment":"The derivation 'It can be noticed that m ≥ 2D²/Δ² log(1/δ̃)' from Eq. (7) is valid because 4 log(2Tn/δ) ≥ 2 log(2Tn²/δ) for T ≥ 1 and δ ∈ (0,1], but the algebra is not shown; writing the intervening inequality would prevent reader confusion.","section":"Appendix B, Eq. (11)"},{"comment":"The definition of Δ uses an absolute value and includes pairs with equal objectives, so Δ can be zero; the proof requires Δ > 0. This assumption should be stated explicitly in the theorem statement rather than only implicitly in the Discussion.","section":"Theorem 1 statement"},{"comment":"The condition 'if G_i > 0' compares the empirical gain to zero, whereas FasterPAM's true improvement condition is L(M_t) > L(M_t \\ {x} ∪ {x′}); the algorithm description should clarify how the empirical quantities relate to the true objective and whether strict vs. non-strict improvement is used.","section":"Algorithm 2, line 19"},{"comment":"There is a typo: 'FatserPAM' should be 'FasterPAM'.","section":"Discussion and Limitations"},{"comment":"The entry for FasterCLARA is difficult to read: 'I (p + T )k2 + pkn' lacks formatting clarity, and the k-means++ entry lists 'log(k)' as the approximation factor without indicating the usual O(log k)-approximation notation.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The empirical contribution is solid and the paper is clearly written, but the central theoretical claim (Theorem 1) has a genuine proof gap that the authors' own limitation section tacitly acknowledges. I recommend major_revision rather than reject because the algorithmic idea is plausible and the experiments support a practical speed/accuracy trade-off; a corrected theorem with a weaker guarantee (e.g., high-probability near-optimal objective, or an added margin assumption for exact swaps) may be within scope. The reviewer should also note that the algebraic concern about Eq. (11) raised in the reader's report is not correct; the real issue is the omitted ranking control."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this for the algorithm, not the theorem. OneBatchPAM is a simple and genuinely useful idea: draw one batch of size m = O(log n), compute distances from all n points to the batch once, then run the FasterPAM swap logic on that precomputed matrix with the full candidate set. That gives O((p+T)n log n) time and O(n log n) memory, and the experiments show it lands within ~2% of FasterPAM on real data while running several times faster—sometimes on scales where FasterPAM can't run at all. The code is available, the baselines are the right ones, and the Pareto-front analysis is a nice touch. That part is solid.\n\nNow the theory. The reader's flagged algebra gap in Eq. (11) is not real: 4 log(2Tn/δ) ≥ 2 log(2Tn^2/δ) holds for T ≥ 1 and δ ∈ (0,1]. The actual gap is more serious and sits in the proof's event structure. FasterPAM and OneBatchPAM don't just decide whether a swap is improving; for each data point x_i the algorithm picks the medoid with the largest gain among all k candidates. The proof only bounds the probability that a rejected swap looks better than the current objective on the batch, and that the selected swap looks worse. It never controls the relative ordering of two improving swaps at the same x_i. Batch noise can flip the empirical ranking between the best and second-best improving medoid, so OneBatchPAM picks a different medoid and the trajectories diverge. That event is not covered by the union bound. The theorem as stated is therefore unproven. Fixing it requires either a margin on the gap between best and second-best candidate gains—which can be much smaller than Δ—or a weaker guarantee about achieving a similar objective rather than identical medoids. The authors actually hint at this in the limitations: near-tie swaps can flip, and the result is close performance rather than identical medoids.\n\nThe paper's own limitations section is commendably honest about Δ-dependence and the heuristic choice of m. The empirical claim of 'close to FasterPAM' is well supported. The formal claim of 'same set of medoids with high probability' is not. This is a fixable or reframable flaw, not a fundamentally broken approach. I'd send it to peer review with a request to repair the theorem or soften it. For a reading group, the ranking gap is worth a session. I'd cite it as a fast k-medoids heuristic, not for the guarantee.","headline":"Good practical paper with honest experiments; the main theorem's proof misses the ranking between improving swaps, so the exact-match guarantee is unproven.","tokens_in":22037,"tokens_out":4446,"would_cite":true,"duration_ms":43884,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"OneBatchPAM claims that a single random batch of $O(\\log n)$ points suffices to reproduce FasterPAM's medoid selection with probability $1-\\delta$, cutting dissimilarity computations from $O(n^2)$ to $O((p+T)n\\log n)$.","keywords":["k-medoids","PAM local search","subsampling","FasterPAM","batch estimation","dissimilarity computation","clustering","coresets"],"falsifier":"Synthesize a metric dataset with two candidate swaps whose true objective improvements differ by a controlled small $\\Delta$, fix $m=c\\log n$ below the theorem's bound for that $\\Delta$, and repeat OneBatchPAM many times; the empirical frequency of diverging from FasterPAM's swap sequence should exceed the theorem's $\\delta$ if the bound is doing the claimed work.","tokens_in":20986,"feed_emoji":"⚡","tokens_out":8938,"duration_ms":77857,"temperature":0.7,"pith_summary":"OneBatchPAM is a k-medoids algorithm that tries to show that the expensive local-search swaps of FasterPAM do not need all $n^2$ pairwise dissimilarities. The paper claims that a single random batch of $m=O(\\log n)$ points, with distances computed from every data point to that batch, is enough for the algorithm to select the same medoid set as FasterPAM with probability at least $1-\\delta$. If true, this turns the $O(n^2)$ dissimilarity bottleneck of PAM-style methods into $O(n\\log n)$, making k-medoids practical for very large datasets and costly dissimilarity functions. The experiments on image and UCI datasets report objectives within about 2% of FasterPAM at a fraction of the running time, a trade-off the paper positions between exact local search and subsampling methods like CLARA.","feed_headline":"A random O(log n) batch reproduces FasterPAM swaps","feed_subtitle":"k-medoids local search drops to O(n log n) dissimilarity computations and stays within ~2% of the full method.","key_machinery":"The load-bearing object is the batch estimator $\\hat{L}(M)=\\frac{1}{m}\\sum_{j=1}^m d(x_{\\sigma(j)},M)$, computed once from a uniformly drawn batch $X_m$. The algorithm feeds this estimator into FasterPAM's swap-evaluation loop, so every swap decision is made on the same $m\\times n$ dissimilarity matrix. The proof uses Hoeffding's inequality to show that with $m=O(\\log n)$ the estimation error stays below half the minimum objective gap $\\Delta/2$, so the estimated ordering of swaps matches the true ordering; this is the same concentration argument used for BanditPAM, but here the batch is drawn once and reused for all $T$ swaps rather than re-estimated at every iteration.","core_discovery":"In the paper's own terms, OneBatchPAM replaces the full-data objective $L(M)=\\frac{1}{n}\\sum_i d(x_i,M)$ with the batch estimate $\\hat{L}(M)=\\frac{1}{m}\\sum_{j=1}^m d(x_{\\sigma(j)},M)$, while keeping the whole dataset $X_n$ as the candidate set for medoid swaps. Theorem 1 states that if $m \\ge \\frac{4D^2}{\\Delta^2}\\log(2Tn/\\delta)$, where $D$ is the largest dissimilarity and $\\Delta$ the smallest absolute objective difference among all swaps FasterPAM evaluates, then OneBatchPAM returns the same set of medoids as FasterPAM with probability at least $1-\\delta$. Because $m$ depends on $n$ only logarithmically, the total dissimilarity work is $O((p+T)n\\log n)$, and the approximation factor inherited from PAM local search remains 5.","pith_inferences":["Inference: The theorem's $\\Delta$ is defined along FasterPAM's random trajectory; a dataset with near-duplicate points will have tiny $\\Delta$, and the $1/\\Delta^2$ factor can push the required batch above realistic values, so the practical regime is when objective gaps are not extremely small.","Inference: The fixed-batch design suggests a streaming extension: after the initial $m\\times n$ pass, each newly arrived point needs only $m$ distance computations, so the algorithm could maintain the same guarantee on a growing dataset without recomputing old distances.","Inference: The paper's overfitting warning on imbalanced data points to a testable fix—make the batch adaptive by adding points whose nearest batch neighbor is atypically far, reusing all distances already computed, and compare the resulting objective on skewed datasets."],"forward_implications":["If Theorem 1 holds, k-medoids local search ceases to require an $O(n^2)$ dissimilarity matrix, because the same $O(n\\log n)$ batch distances are reused across every swap iteration.","OneBatchPAM inherits the 5-approximation guarantee of PAM-style local search, unlike pure subsampling methods whose approximation factor doubles to 10.","On the paper's experiments, OneBatchPAM matches FasterPAM within about 2% objective while running roughly 7 times faster on small datasets, and it scales to datasets where FasterPAM cannot finish.","The memory footprint drops from $O(n^2)$ to $O(n\\log n)$ for stored dissimilarities, at the price of more memory than BanditPAM's $O(n)$.","The nearest-neighbor importance-weighting variant (NNIW) gives the best objective in experiments and costs almost no extra time, since the required distances are already computed."],"supporting_citations":[{"why":"Supplies the proof framework for Theorem 1 and defines the BanditPAM baseline that OneBatchPAM improves upon.","marker":"Tiwari et al. 2020"},{"why":"Defines FastPAM and FasterPAM, the exact local-search algorithm whose swap sequence OneBatchPAM aims to reproduce, and gives the $O(n^2)$ complexity baseline.","marker":"Schubert and Rousseeuw 2021"},{"why":"Provides the official Python implementation of FasterPAM used in the experiments.","marker":"Schubert and Lenssen 2022"},{"why":"Establishes the 5-approximation ratio for PAM-style local search that OneBatchPAM inherits.","marker":"Arya et al. 2001"},{"why":"Shows that random subsamples of size $O(k\\log n)$ preserve clustering objectives, the theoretical backdrop for the batch-size argument.","marker":"Mishra, Oblinger, and Pitt 2001"},{"why":"Provides the nearest-neighbor importance weighting used by the NNIW variant, which gives the best objective in the experiments.","marker":"Loog 2012"},{"why":"Provides the lightweight coreset construction used by the LWCS variant of OneBatchPAM.","marker":"Bachem, Lucic, and Krause 2018"}],"fun_headline_variants":["One random batch of O(log n) matches FasterPAM","K-medoids in O(n log n) with a single batch","Log-size sample gives FasterPAM-level k-medoids","Batch of O(log n) points slashes k-medoids cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee assumes every swap FasterPAM would reject is worse than the swap it accepts by at least a positive margin $\\Delta$, and that choosing $m$ from the bound keeps $m=O(\\log n)$; when the best swaps are nearly tied, the required batch size can grow far beyond $\\log n$.","fun_headline_variants_meta":{"raw":{"variants":["One random batch of O(log n) matches FasterPAM","K-medoids in O(n log n) with a single batch","Log-size sample gives FasterPAM-level k-medoids","Batch of O(log n) points slashes k-medoids cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00022,"raw_usage":{"total_tokens":1420,"prompt_tokens":894,"completion_tokens":526,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":510,"completion_tokens_details":{"reasoning_tokens":454}},"tokens_in":510,"tokens_out":526,"duration_ms":5859,"temperature":1.0,"reasoning_tokens":454,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:41:32.945141+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Synthesize a metric dataset with two candidate swaps whose true objective improvements differ by a controlled small $\\Delta$, fix $m=c\\log n$ below the theorem's bound for that $\\Delta$, and repeat OneBatchPAM many times; the empirical frequency of diverging from FasterPAM's swap sequence should exceed the theorem's $\\delta$ if the bound is doing the claimed work.","supporting_citations":[{"cited_title":"J.; Mayclin, J.; Thrun, S.; Piech, C.; and Shomorony, I","cited_arxiv_id":null,"evidence_quote":"Supplies the proof framework for Theorem 1 and defines the BanditPAM baseline that OneBatchPAM improves upon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines FastPAM and FasterPAM, the exact local-search algorithm whose swap sequence OneBatchPAM aims to reproduce, and gives the $O(n^2)$ complexity baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the official Python implementation of FasterPAM used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the 5-approximation ratio for PAM-style local search that OneBatchPAM inherits."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that random subsamples of size $O(k\\log n)$ preserve clustering objectives, the theoretical backdrop for the batch-size argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the nearest-neighbor importance weighting used by the NNIW variant, which gives the best objective in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the lightweight coreset construction used by the LWCS variant of OneBatchPAM."}],"review_version":1}