Timezone: »

Uniform Concentration Bounds toward a Unified Framework for Robust Clustering
Debolina Paul · Saptarshi Chakraborty · Swagatam Das · Jason Xu

Recent advances in center-based clustering continue to improve upon the drawbacks of Lloyd's celebrated $k$-means algorithm over $60$ years after its introduction. Various methods seek to address poor local minima, sensitivity to outliers, and data that are not well-suited to Euclidean measures of fit, but many are supported largely empirically. Moreover, combining such approaches in a piecemeal manner can result in ad hoc methods, and the limited theoretical results supporting each individual contribution may no longer hold. Toward addressing these issues in a principled way, this paper proposes a cohesive robust framework for center-based clustering under a general class of dissimilarity measures. In particular, we present a rigorous theoretical treatment within a Median-of-Means (MoM) estimation framework, showing that it subsumes several popular $k$-means variants. In addition to unifying existing methods, we derive uniform concentration bounds that complete their analyses, and bridge these results to the MoM framework via Dudley's chaining arguments. Importantly, we neither require any assumptions on the distribution of the outlying observations nor on the relative number of observations $n$ to features $p$. We establish strong consistency and an error rate of $O(n^{-1/2})$ under mild conditions, surpassing the best-known results in the literature. The methods are empirically validated thoroughly on real and synthetic datasets.

Author Information

Debolina Paul (Indian Statistical Institute)

I am Debolina Paul and I am an M.Stat 2nd year student at the Indian Statistical Institute, Kolkata, India. I completed B.Stat (Hons.) from the same institute. I will be joining the Department of Statistics, Stanford University as a PhD student in fall 2021. I was also a summer research scholar at the Department of Statistical Science, Duke University, NC, USA, from May to July, 2019 and from May to August, 2020 (online due to COVID).

Saptarshi Chakraborty (University of California, Berkeley)

I'm Saptarshi Chakraborty, a first-year Ph.D. student in Statistics at the Department of Statistics, University of California, Berkeley. Prior to joining Berkeley, I completed my Master's (M.Stat) and Bachelor's (B. Stat (Hons.)) degrees in Statistics from Indian Statistical Institute, Kolkata, India. Previously, I was a visiting scholar at the Department of Statistical Science, Duke University, NC, USA. I was also a summer exchange student at the Big Data Summer Institute, University of Michigan, USA in 2018, where I worked on the application of Machine Learning algorithms on medical data.

Swagatam Das (Indian Statistical Institute)
Jason Xu (Duke University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors