Abstract

This paper focuses on efficient algorithms for single and multi-view spectral clustering with a convex regularization term for very large scale image datasets. In computer vision applications, multiple views denote distinct image-derived feature representations that inform the clustering. Separately, the regularization encodes high level advice such as tags or user interaction in identifying similar ob jects across ex- amples. Depending on the specific task, schemes to exploit such infor- mation may lead to a smooth or non-smooth regularization function. We present stochastic gradient descent methods for optimizing spectral clus- tering ob jectives with such convex regularizers for datasets with up to a hundred million examples. We prove that under mild conditions the local convergence rate is where T is the number of iterations; further, our analysis shows that the convergence improves linearly by in- creasing the number of threads. We give extensive experimental results on a range of vision datasets demonstrating the algorithm’s empirical behavior.