Scalable Exemplar Clustering and Facility Location via Augmented Block Coordinate Descent with Column Generation.

Ian En-Hsu Yen, Dmitry Malioutov, Abhishek KumarAISTATS 2016 · OpenReview

Abstract: In recent years exemplar clustering has become a popular tool for applications in document and video summarization, active learning, and clustering with general similarity, where cluster centroids are required to be a subset of the data samples rather than their linear combinations. The problem is also well-known as facility location in the operations research literature. While the problem has well-developed convex relaxation with approximation and recovery guarantees, the number of variables grows quadratically with the number of samples. Therefore, state-of-the-art methods can hardly handle more than 10^4 samples (i.e. 10^8 variables). In this work, we propose an Augmented-Lagrangian with Block Coordinate Descent (AL-BCD) algorithm that utilizes problem structure to obtain closed-form solution for each block sub-problem, and exploits low-rank representation of the dissimilarity matrix to search active columns without computing the entire matrix. Experiments show our approach to be orders of magnitude faster than existing approaches and can handle problems of up to 10^6 samples. We also demonstrate successful applications of the algorithm on world-scale facility location, document summarization and active learning.

Introduction

Exemplar clustering, or the $k$-medoids problem, is a fundamental task where cluster centroids must be selected from the data points themselves. This is critical for domains like genomics or natural language processing, where calculating a "mean" is nonsensical. While convex relaxations offer global optimality, they suffer from a quadratic growth in variables ($O(N^2)$). For a dataset of one million points, this translates to a trillion variables, creating a "memory wall" that standard solvers cannot overcome beyond roughly 10,000 samples.

Methodology: ALGCD

To address these scalability challenges, we introduce ALGCD, an algorithm combining Augmented Lagrangian methods with greedy column generation.

  1. AL-BCD Framework: We utilize an Augmented Lagrangian with Block Coordinate Descent. By carefully structuring the optimization, we derive closed-form solutions for each block sub-problem, enabling rapid updates without expensive matrix operations.
  2. Greedy Column Generation: Recognizing that most points are unsuitable as exemplars, we use a greedy oracle to identify only the most promising candidates. This avoids the need to compute or store the full $N \times N$ dissimilarity matrix.
  3. Low-Rank Exploitation: For many distance metrics, the dissimilarity matrix $D$ can be represented in a low-rank format ($D = UV^T$). This allows the search for new exemplars to scale linearly ($O(N)$) rather than quadratically.

Experimental Results

We evaluated ALGCD against state-of-the-art methods like ADMM and standard LP solvers across various benchmarks. As shown in the results table, ALGCD consistently achieves orders-of-magnitude speedups while maintaining high solution quality.

Comparison of runtime across various datasets for different optimization methods.

Notably, on the Covtype dataset (581,012 samples), ALGCD completed in approximately 36 minutes, whereas competing methods either failed to scale or exceeded memory limits. The algorithm successfully handled problems with up to $10^6$ samples, effectively optimizing over a trillion potential assignments in about 2 hours.

Applications: Active Learning

The scalability of ALGCD enables its use in downstream tasks like active learning. In document classification experiments on the OHSUMED dataset, our method was used to select informative documents for labeling. By balancing uncertainty (picking hard-to-classify points) and diversity (picking points that represent different parts of the data), the algorithm achieved higher accuracy with significantly fewer labels compared to random sampling.

Accuracy vs. training set size for active learning strategies.

Conclusion

ALGCD represents a significant leap in the scalability of exemplar clustering. By exploiting the underlying mathematical structure of dissimilarity and focusing on active exemplar candidates, we bypass the quadratic memory bottleneck. While performance depends on the low-rank nature of the data and requires some hyperparameter tuning, the ability to solve trillion-variable problems on a single machine opens new possibilities for large-scale data summarization and facility location.

Summary updated

Abstract

In recent years exemplar clustering has become a popular tool for applications in document and video summarization, active learning, and clustering with general similarity, where cluster centroids are required to be a subset of the data samples rather than their linear combinations. The problem is also well-known as facility location in the operations research literature. While the problem has well-developed convex relaxation with approximation and recovery guarantees, it has number of variables grows quadratically with the number of samples. Therefore, state-of-the-art methods can hardly handle more than 10^4 samples (i.e. 10^8 variables). In this work, we propose an Augmented-Lagrangian with Block Coordinate Descent (AL-BCD) algorithm that utilizes problem structure to obtain closed-form solution for each block sub-problem, and exploits low-rank representation of the dissimilarity matrix to search active columns without computing the entire matrix. Experiments show our approach to be orders of magnitude faster than existing approaches and can handle problems of up to 10^6 samples. We also demonstrate successful applications of the algorithm on world-scale facility location, document summarization and active learning.
BibTeX
@inproceedings{yen2016scalable,
  author = {Ian En-Hsu Yen and Dmitry Malioutov and Abhishek Kumar},
  title = {{Scalable Exemplar Clustering and Facility Location via Augmented Block Coordinate Descent with Column Generation.}},
  booktitle = {AISTATS},
  year = {2016},
  url = {https://openreview.net/forum?id=80N_2INCEM9},
}
Figure