A Scalable Deterministic Global Optimization Algorithm for Clustering Problems

Kaixun Hua, Mingfei Shi, Yankai CaoICML 2021 · OpenReview

Executive Summary

Researchers have developed a new deterministic global optimization algorithm for the Minimum Sum-of-Squares Clustering (MSSC) problem that scales to datasets 100 times larger than previous state-of-the-art global solvers. By reformulating the problem to branch only on cluster centers rather than individual data points, the algorithm can find provably optimal (or near-optimal) clusters for datasets with over 200,000 samples.

Introduction: The Limits of Heuristic Clustering

Clustering is a cornerstone of unsupervised learning, and the most common objective is Minimum Sum-of-Squares Clustering (MSSC)—the mathematical foundation behind the famous k-means algorithm. While k-means is fast and widely used, it is fundamentally a heuristic. It often gets stuck in "local optima," meaning it finds a decent solution but misses the best possible mathematical grouping.

For applications where precision is critical, researchers rely on global optimization—algorithms that provide a mathematical guarantee that the solution found is the absolute best. However, traditional global solvers struggle with the "curse of dimensionality." As the number of data points ($S$) increases, the number of decision variables in standard models explodes, making global optimization computationally impossible for anything beyond a few thousand samples. This paper aims to break that scalability barrier.

Methodology: Reduced-Space Branch-and-Bound

To overcome the limitations of standard solvers, the authors introduce a tailored reduced-space branch-and-bound (BB) algorithm. The breakthrough relies on restructuring the underlying mathematics:

  1. Two-Stage Reformulation: The algorithm treats the cluster centers as "first-stage" variables and the point-to-cluster assignments as "second-stage" variables.
  2. Reduced-Space Branching: Crucially, the algorithm only performs "branching" (splitting the search space) on the cluster centers. Because the number of centers ($k$) is usually small and independent of the number of data points, the complexity of the search tree no longer explodes as the dataset grows.
  3. Advanced Bounding: To prune the search tree efficiently, the team developed several ways to calculate lower and upper bounds:
  4. Scenario-based grouping: Bundling data points together to solve smaller sub-problems.
  5. Lagrangian Decomposition: A technique to "relax" difficult constraints and turn them into penalties, providing tighter lower bounds.
  6. Parallel Implementation: The algorithm is implemented in Julia and designed to be easily parallelized across multiple CPU cores to further accelerate convergence.

Core Insights

  • Decoupling Complexity from Sample Size: The most significant insight is that guaranteeing a global optimum does not require branching on every single data point. By focusing the search space exclusively on the cluster centers, the problem remains manageable even as datasets scale to hundreds of thousands of points.
  • The "Optimality Gap" as a Benchmark: Unlike k-means, which simply outputs a final cluster assignment, this algorithm provides an "optimality gap." This metric acts as a mathematical certificate, telling the user exactly how far the current best solution could possibly be from the true global optimum.
  • Heuristics vs. Reality: The paper reveals that while k-means is often "good enough," it can be significantly sub-optimal on complex datasets. A scalable global solver allows researchers to finally quantify exactly how much performance is sacrificed when relying on heuristics.

Results and Performance

The authors evaluated their algorithm on both synthetic datasets (ranging from 300 to 210,000 samples) and real-world benchmarks (such as Iris, Seeds, and Glass Identification).

  • Massive Scalability: The algorithm successfully handled a synthetic dataset with 210,000 samples. This represents a 100x improvement over the previous state-of-the-art global solver, which historically maxed out around 2,300 samples.
  • Superiority over Standard Solvers: On a dataset of 42,000 samples, the industry-standard solver CPLEX failed to find any feasible solution within 4 hours. In contrast, the proposed algorithm successfully found a solution with a small, certified optimality gap.
Comparison of clustering methods on synthetic datasets
  • Efficiency through Parallelization: On the Iris and Seeds datasets, the algorithm converged to a tight 0.1% optimality gap in about an hour using 20 cores.
  • Solving the "Unsolvable": For the Glass Identification dataset—which previous specialized global algorithms could not solve—this new approach reached a 0.1% gap within 1 hour.

Limitations and Future Directions

While this algorithm represents a massive leap in scalability for global optimization, it remains computationally intensive compared to heuristics like k-means. It is designed for high-stakes scenarios where finding the exact right answer justifies hours of computation, rather than seconds. Additionally, the current framework assumes the number of clusters ($k$) is known beforehand.

Looking forward, the authors suggest that their bounding techniques could be adapted to handle more complex cost functions beyond simple sum-of-squares. This could potentially extend their deterministic, scalable approach to a much broader range of unsupervised learning tasks.

Summary updated

Abstract

The minimum sum-of-squares clustering (MSSC) task, which can be treated as a Mixed Integer Second Order Cone Programming (MISOCP) problem, is rarely investigated in the literature through determini...
BibTeX
@inproceedings{hua2021scalable,
  author = {Kaixun Hua and Mingfei Shi and Yankai Cao},
  title = {{A Scalable Deterministic Global Optimization Algorithm for Clustering Problems}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=L4H4_pfOQAF},
}
Figure