Robust Discriminative Clustering with Sparse Regularizers
This work addresses clustering challenges in high-dimensional data for machine learning practitioners, offering incremental improvements through sparse extensions and faster algorithms.
The paper tackles the problem of clustering high-dimensional data by jointly performing clustering and dimension reduction, showing equivalence to existing frameworks and proposing a sparse extension with theoretical performance guarantees and an efficient algorithm. It achieves scalings of d=O(√n) for affine invariant cases and d=O(n) for sparse cases, with an algorithm running in O(nd²) time.
Clustering high-dimensional data often requires some form of dimensionality reduction, where clustered variables are separated from "noise-looking" variables. We cast this problem as finding a low-dimensional projection of the data which is well-clustered. This yields a one-dimensional projection in the simplest situation with two clusters, and extends naturally to a multi-label scenario for more than two clusters. In this paper, (a) we first show that this joint clustering and dimension reduction formulation is equivalent to previously proposed discriminative clustering frameworks, thus leading to convex relaxations of the problem, (b) we propose a novel sparse extension, which is still cast as a convex relaxation and allows estimation in higher dimensions, (c) we propose a natural extension for the multi-label scenario, (d) we provide a new theoretical analysis of the performance of these formulations with a simple probabilistic model, leading to scalings over the form $d=O(\sqrt{n})$ for the affine invariant case and $d=O(n)$ for the sparse case, where $n$ is the number of examples and $d$ the ambient dimension, and finally, (e) we propose an efficient iterative algorithm with running-time complexity proportional to $O(nd^2)$, improving on earlier algorithms which had quadratic complexity in the number of examples.