16 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…
Low-degree Lower bounds for clustering in moderate dimension
Alexandra Carpentier, Nicolas Verzelen
We study the fundamental problem of clustering points into groups drawn from a mixture of isotropic Gaussians in . Specifically, we investigate the requisite…
Nonparametric Kernel Clustering with Bandit Feedback
Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar +1
Clustering with bandit feedback refers to the problem of partitioning the arms of an -armed stochastic bandit according to their underlying distributions, based on noisy observa…
Statistical and computational challenges in ranking
Alexandra Carpentier, Nicolas Verzelen
We consider the problem of ranking experts according to their abilities, based on the correctness of their answers to questions. This is modeled by the so-called crowd-sour…
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).…
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…
Computational lower bounds in latent models: clustering, sparse-clustering, biclustering
Bertrand Even, Christophe Giraud, Nicolas Verzelen
In many high-dimensional problems, like sparse-PCA, planted clique, or clustering, the best known algorithms with polynomial time complexity fail to reach the statistical performan…
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…
Seriation of Toeplitz and latent position matrices: optimal rates and computational trade-offs
Clément Berenfeld, Alexandra Carpentier, Nicolas Verzelen
In this paper, we consider the problem of seriation of a permuted structured matrix based on noisy observations. The entries of the matrix relate to an expected quantification of i…
Active clustering with bandit feedback
Victor Thuot, Alexandra Carpentier, Christophe Giraud +1
We investigate the Active Clustering Problem (ACP). A learner interacts with an -armed stochastic bandit with -dimensional subGaussian feedback. There exists a hidden partiti…
Minimax optimal seriation in polynomial time
Yann Issartel, Christophe Giraud, Nicolas Verzelen
We consider the seriation problem, whose goal is to recover a hidden ordering from a noisy observation of a permuted Robinson matrix. We establish sharp minimax rates under average…
Computation-information gap in high-dimensional clustering
Bertrand Even, Christophe Giraud, Nicolas Verzelen
We investigate the existence of a fundamental computation-information gap for the problem of clustering a mixture of isotropic Gaussian in the high-dimensional regime, where the am…
Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons
Nicolas Verzelen
Consider the standard Gaussian linear regression model , where is a response vector and is a design matrix. Numerous work have been devoted to bu…