Pair-Matching: Links Prediction with Adaptive Queries
- URL: http://arxiv.org/abs/1905.07342v3
- Date: Tue, 5 Mar 2024 17:45:35 GMT
- Title: Pair-Matching: Links Prediction with Adaptive Queries
- Authors: Christophe Giraud and Yann Issartel and Luc Leh\'ericy and Matthieu
Lerasle
- Abstract summary: We show that sublinear regret is achievable in the case where the graph is generated according to a Block Model (SBM) with two communities.
The paper is concluded by a conjecture regarding the optimal regret when the number of communities is larger than 2.
- Score: 7.22341371511072
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The pair-matching problem appears in many applications where one wants to
discover good matches between pairs of entities or individuals. Formally, the
set of individuals is represented by the nodes of a graph where the edges,
unobserved at first, represent the good matches. The algorithm queries pairs of
nodes and observes the presence/absence of edges. Its goal is to discover as
many edges as possible with a fixed budget of queries. Pair-matching is a
particular instance of multi-armed bandit problem in which the arms are pairs
of individuals and the rewards are edges linking these pairs. This bandit
problem is non-standard though, as each arm can only be played once.
Given this last constraint, sublinear regret can be expected only if the
graph presents some underlying structure. This paper shows that sublinear
regret is achievable in the case where the graph is generated according to a
Stochastic Block Model (SBM) with two communities. Optimal regret bounds are
computed for this pair-matching problem. They exhibit a phase transition
related to the Kesten-Stigum threshold for community detection in SBM. The
pair-matching problem is considered in the case where each node is constrained
to be sampled less than a given amount of times. We show how optimal regret
rates depend on this constraint. The paper is concluded by a conjecture
regarding the optimal regret when the number of communities is larger than 2.
Contrary to the two communities case, we argue that a statistical-computational
gap would appear in this problem.
Related papers
- Graph Feedback Bandits with Similar Arms [9.701475722399646]
We study the multi-armed bandit problem with graph feedback.
We introduce two UCB-based algorithms: D-UCB with problem-independent regret upper bounds and C-UCB with problem-dependent upper bounds.
arXiv Detail & Related papers (2024-05-18T04:20:14Z) - Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
This paper considers the problem of community detection on multiple potentially correlated graphs from antheoretical perspective.
We first put forth a random graph model, called the multi-view information block model (MVSBM), designed to generate correlated graphs on the same set of nodes.
arXiv Detail & Related papers (2024-01-17T13:39:38Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM)
We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$.
Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
arXiv Detail & Related papers (2023-10-02T08:15:52Z) - Efficient Algorithms for Exact Graph Matching on Correlated Stochastic
Block Models with Constant Correlation [7.914348940034351]
We propose an efficient algorithm for matching graphs with community structure.
Our algorithm is the first low-order-time algorithm achieving exact matching between two correlated block models.
arXiv Detail & Related papers (2023-05-31T09:06:50Z) - 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) - Deep Probabilistic Graph Matching [72.6690550634166]
We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints.
The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
arXiv Detail & Related papers (2022-01-05T13:37:27Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
We investigate the problem dependent regime in the Thresholding Bandit problem (TBP)
The objective of the learner is to output, at the end of a sequential game, the set of arms whose means are above a given threshold.
We provide upper and lower bounds for the probability of error in both the concave and monotone settings.
arXiv Detail & Related papers (2021-06-18T15:01:01Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector.
The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures.
Two efficient algorithms are developed based on textttEXP3.
arXiv Detail & Related papers (2020-12-10T15:40:07Z)
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.