Nicolas Verzelen

activity

20102026

collaborators

Showing math.STShow all

8 papers · 1 filter

math.ST2026

Low-degree Lower bounds for clustering in moderate dimension

Alexandra Carpentier, Nicolas Verzelen

We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $R^{d}$ . Specifically, we investigate the requisite…

math.ST2025

Statistical and computational challenges in ranking

Alexandra Carpentier, Nicolas Verzelen

We consider the problem of ranking $n$ experts according to their abilities, based on the correctness of their answers to $d$ questions. This is modeled by the so-called crowd-sour…

math.ST2025

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…

math.ST2025

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…

math.ST2024

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…

math.ST2024

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…

math.ST2024

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…

math.ST2010

Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons

Nicolas Verzelen

Consider the standard Gaussian linear regression model $Y = X θ + ε$ , where $Y \in R^{n}$ is a response vector and $X \in R^{n * p}$ is a design matrix. Numerous work have been devoted to bu…