5 papers · 1 filter
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…