Selective inference after convex clustering with $\ell_1$ penalization

François Bachoc, Cathy Maugis-Rabusseau, Pierre Neuvial

Abstract: Classical inference methods notoriously fail when applied to data-driven test hypotheses or inference targets. Instead, dedicated methodologies are required to obtain statistical guarantees for these selective inference problems. Selective inference is particularly relevant post-clustering, typically when testing a difference in mean between two clusters. In this paper, we address convex clustering with $\ell_1$ penalization, by leveraging related selective inference tools for regression, based on Gaussian vectors conditioned to polyhedral sets. In the one-dimensional case, we prove a polyhedral characterization of obtaining given clusters, than enables us to suggest a test procedure with statistical guarantees. This characterization also allows us to provide a computationally efficient regularization path algorithm. Then, we extend the above test procedure and guarantees to multi-dimensional clustering with $\ell_1$ penalization, and also to more general multi-dimensional clusterings that aggregate one-dimensional ones. With various numerical experiments, we validate our statistical guarantees and we demonstrate the power of our methods to detect differences in mean between clusters. Our methods are implemented in the R package poclin.

Introduction

In data science, a common pitfall is using the same dataset to both discover patterns and test their significance. This "double dipping"—formally known as selective inference—often leads to deceptively small p-values and spurious "significant" results, even in pure noise. For instance, if an algorithm identifies two clusters and a standard t-test is then used to compare their means, the test fails to account for the fact that the clusters were specifically chosen to be different based on that very data.

The Challenge of Post-Clustering Inference

Post-clustering inference is difficult because the "event" of selecting specific clusters is mathematically complex. Traditional tests assume groups are pre-defined. When groups are data-driven, the selection process must be accounted for to avoid high Type I error rates. This paper focuses on convex clustering with an $\ell_1$ penalty, a method that treats clustering as a convex optimization problem, offering more stability and mathematical tractability than heuristic methods like K-means.

Polyhedral Characterization and the Regularization Path

The authors leverage the Polyhedral Lemma, showing that for 1D convex clustering with an $\ell_1$ penalty, the event of obtaining specific clusters corresponds to the data vector falling into a polyhedron (a set defined by linear inequalities). This characterization allows for the development of a computationally efficient regularization path algorithm.

The regularization path for 1D convex clustering shows how observations merge into clusters as the penalty parameter $\lambda$ increases.

As shown in the regularization path, as the penalty $\lambda$ increases, individual data points merge into larger clusters. The authors' algorithm solves this for all $\lambda$ values simultaneously, providing a significant speedup over general-purpose solvers. While standard packages like genlasso struggled with just 100 data points, the authors' method handled $n=100,000$ points with ease.

Statistical Guarantees and Conditioning

To derive valid p-values, the researchers compare the observed difference between cluster means to a Gaussian distribution truncated to the polyhedral set. A key aspect of their 1D characterization involves conditioning the test on the order of observations.

The 1D clustering process can be viewed as partitioning ordered observations into groups, defined by specific boundary indices $t_j$.

While conditioning on the order slightly reduces the test's power, it makes the polyhedral characterization possible. This framework is then extended to multi-dimensional data by aggregating 1D results, taking advantage of the "separability" of the $\ell_1$ norm across features.

Results and Performance

Numerical experiments on synthetic Gaussian datasets validated the statistical guarantees. While naive Student's t-tests were "severely anti-conservative"—rejecting the null hypothesis nearly 100% of the time in noise—the proposed poclin method maintained the correct 5% error rate. The test showed high power to detect real signals when the difference between cluster means was large, though power decreases as correlation between variables increases due to the restrictive conditioning set.

Conclusion

The paper provides a rigorous framework for valid inference after convex clustering. By characterizing the selection event as a polyhedron, the authors ensure that discovered differences are statistically sound. Future work may address the challenges of unknown noise parameters and extending these results to the non-separable $\ell_2$ penalty. The methods are available in the R package poclin.

Summary updated

Abstract

Classical inference methods notoriously fail when applied to data-driven test hypotheses or inference targets. Instead, dedicated methodologies are required to obtain statistical guarantees for these selective inference problems. Selective inference is particularly relevant post-clustering, typically when testing a difference in mean between two clusters. In this paper, we address convex clustering with $\ell_1$ penalization, by leveraging related selective inference tools for regression, based on Gaussian vectors conditioned to polyhedral sets. In the one-dimensional case, we prove a polyhedral characterization of obtaining given clusters, than enables us to suggest a test procedure with statistical guarantees. This characterization also allows us to provide a computationally efficient regularization path algorithm. Then, we extend the above test procedure and guarantees to multi-dimensional clustering with $\ell_1$ penalization, and also to more general multi-dimensional clusterings that aggregate one-dimensional ones. With various numerical experiments, we validate our statistical guarantees and we demonstrate the power of our methods to detect differences in mean between clusters. Our methods are implemented in the R package poclin.
BibTeX
@inproceedings{bachoc2025selective,
  author = {François Bachoc and Cathy Maugis-Rabusseau and Pierre Neuvial},
  title = {{Selective inference after convex clustering with $\textbackslash\{\}ell\_1$ penalization}},
  booktitle = {ESAIM},
  year = {2025},
  doi = {10.1051/ps/2025004},
}
Figure