Query-Efficient Correlation Clustering with Noisy Oracle

• URL: http://arxiv.org/abs/2402.01400v2
• Date: Sun, 03 Nov 2024 11:54:13 GMT
• Title: Query-Efficient Correlation Clustering with Noisy Oracle
• Authors: Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi, Wei Chen,
• Abstract summary: We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB) We design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation and study their theoretical guarantees. Our results are the first examples of clustering-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.
• Score: 17.11782578276788
• License:
• Abstract: We study a general clustering setting in which we have $n$ elements to be clustered, and we aim to perform as few queries as possible to an oracle that returns a noisy sample of the weighted similarity between two elements. Our setting encompasses many application domains in which the similarity function is costly to compute and inherently noisy. We introduce two novel formulations of online learning problems rooted in the paradigm of Pure Exploration in Combinatorial Multi-Armed Bandits (PE-CMAB): fixed confidence and fixed budget settings. For both settings, we design algorithms that combine a sampling strategy with a classic approximation algorithm for correlation clustering and study their theoretical guarantees. Our results are the first examples of polynomial-time algorithms that work for the case of PE-CMAB in which the underlying offline optimization problem is NP-hard.

Related papers

• Sample-Efficient Clustering and Conquer Procedures for Parallel Large-Scale Ranking and Selection [0.0]
  In parallel computing environments, correlation-based clustering can achieve an $mathcalO(p)$ sample complexity reduction rate. In large-scale AI applications such as neural architecture search, a screening-free version of our procedure surprisingly surpasses fully-sequential benchmarks in terms of sample efficiency.
  arXiv  Detail & Related papers  (2024-02-03T15:56:03Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  We build on widely adopted $k$-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets. We arrive at the first efficient approximation algorithm for constrained $k$-center with the best possible ratio of 2.
  arXiv  Detail & Related papers  (2024-01-23T07:16:32Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  We devise an efficient algorithm that recovers clusters using the observed labels. We present Instance-Adaptive Clustering (IAC), the first algorithm whose performance matches these lower bounds both in expectation and with high probability.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  State-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS) We revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
  arXiv  Detail & Related papers  (2021-04-18T07:46:28Z)
• Clustering with Penalty for Joint Occurrence of Objects: Computational Aspects [0.0]
  The method of Hol'y, Sokol and vCern'y clusters objects based on their incidence in a large number of given sets. The idea is to minimize the occurrence of multiple objects from the same cluster in the same set. In the current paper, we study computational aspects of the method.
  arXiv  Detail & Related papers  (2021-02-02T10:39:27Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.