63 citations
- Institut National de Recherche pour l'Agriculture, l'Alimentation et l'EnvironnementFR44 papers
- Institut national de recherche en sciences et technologies du numériqueFR22 papers
- Centre National de la Recherche ScientifiqueFR15 papers
- Université de MontpellierFR15 papers
- Institut Agro MontpellierFR14 papers
- Institut Agro Montpelier10 papers
- Université Paris-SaclayFR9 papers
- Centre Inria d'Université Côte d'AzurFR7 papers
- Institut Élie Cartan de LorraineFR6 papers
- Institut Montpelliérain Alexander GrothendieckFR6 papers
- Université de LorraineFR6 papers
- Centre de Mathématiques Appliquées de l'École polytechniqueFR5 papers
83 papers
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.…
Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals
Bertrand Cloez, Adrien Cotil, Jean-Baptiste Menassol +1
We propose a novel family of model-free algorithms for node clustering and parameter inference in graphs generated from the Stochastic Block Model (SBM), a fundamental framework in…
Phase Transition for Stochastic Block Model with more than Communities
Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen
Predictions from statistical physics postulate that recovery of the communities in the Stochastic Block Model (SBM) with a fixed number of communities is possible in polynomial…
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]…
Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
Bertrand Even, Christophe Giraud, Nicolas Verzelen
In many high-dimensional problems,polynomial-time algorithms fall short of achieving the statistical limits attainable without computational constraints. A powerful approach to pro…