6 papers · 1 filter
The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
El Mehdi Saad, Victor Thuot, Nicolas Verzelen
We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with…
Nonparametric Kernel Clustering with Bandit Feedback
Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar +1
Clustering with bandit feedback refers to the problem of partitioning a set of items, where the clustering algorithm can sequentially query the items to receive noisy observations.…
Phase Transition for Stochastic Block Model with more than Communities (II)
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
A fundamental theoretical question in network analysis is to determine under which conditions community recovery is possible in polynomial time in the Stochastic Block Model (SBM).…
Low-degree lower bounds via almost orthonormal bases
Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud +1
Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical-computational gaps across a variety of high-dimensional statistical models [Wein25]…
Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
Maximilian Graf, Victor Thuot, Nicolas Verzelen
We study the problem of clustering a set of items based on bandit feedback. Each of the items is characterized by a feature vector, with a possibly large dimension . The ite…
Optimal level set estimation for non-parametric tournament and crowdsourcing problems
Maximilian Graf, Alexandra Carpentier, Nicolas Verzelen
Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of experts on questions. In this paper, we assume that both the…