Technical Summary: Why Greedy Search Produces Optimal Clustering Outcomes? A Fixed-Core Assignment Theory

Problem Statement

Existing clustering methods predominantly rely on a set-oriented definition, where a cluster is viewed as a set of similar points defined by point-to-point similarity or distance functions. While effective for compact, homogeneous clusters, this paradigm struggles with irregular shapes, varying densities, and multi-scale structures. Even sophisticated methods like Spectral Clustering and Deep Clustering face fundamental limitations because their assumed cluster structures (e.g., centroids or Gaussian distributions) often mismatch the true underlying data distributions. Furthermore, many of these methods suffer from high computational complexity (worse than quadratic) or rely on complex optimization procedures (e.g., Expectation-Maximization, eigen-decomposition) that are sensitive to initialization.

In contrast, 'Cluster-as-Distribution' (CaD) Clustering (e.g., Kernel-Bounded Clustering, Isolation Distributional Kernel Clustering) treats each cluster as a set of independent and identically distributed (i.i.d.) samples generated from an unknown distribution. CaD methods utilize distributional kernels to assign points to cluster proxies without parametric estimation or density estimation. Empirically, CaD methods achieve superior clustering outcomes using a simple greedy search (one-pass assignment) compared to deep learning or EM-based methods. However, a theoretical justification for why a greedy approach outperforms complex optimization in this context has been lacking.

Methodology

The paper provides a theoretical framework analyzing CaD clustering from two angles: statistical approximation and combinatorial optimization.

1. Error Analysis of Kernel Mean Embedding (KME) Approximation

The authors analyze the discrepancy ($\Delta$) between the true distribution embedding ($\mu_P$) and the empirical embedding of a core cluster ($\hat{\mu}_G$) in a Reproducing Kernel Hilbert Space (RKHS). They decompose this error into three components:

• Truncation Bias: The error introduced by approximating the full distribution $P$ with a truncated high-density region $Q$. This depends on the distribution's shape (e.g., tails, skewness).
• Estimation Bias: The error arising from estimating the embedding of the truncated region $Q$ using a finite sample $U$. This converges at a rate of $O(1/\sqrt{s})$, where $s$ is the sample size.
• Core Bias: The error resulting from selecting a specific subset of points as the "core" $G$ to represent the sample $U$. This depends on the geometric proximity of the core to the samples and the balance of the core selection.

The total error bound is shown to be controlled by these three factors, with the bandwidth parameter $\sigma$ of the Gaussian kernel playing a central role in balancing local structure preservation against approximation robustness.

2. Combinatorial Optimization via Partition Matroids

The paper models the one-pass assignment phase of CaD clustering as a maximum-weight basis selection problem on a partition matroid.

• Ground Set: The set of all possible point-to-cluster assignments.
• Constraints: Each data point must be assigned to at most one cluster (partition constraint).
• Objective: Maximize the total similarity (weight) between points and their assigned cluster proxies, where weights are defined by the inner product in RKHS.

By mapping the assignment problem to a partition matroid, the authors invoke the Rado-Edmonds Theorem, which guarantees that a greedy algorithm (selecting the locally optimal assignment for each point) yields a globally optimal solution for the fixed-core assignment subproblem.

Key Contributions

1. Error Decomposition: The paper decomposes the distribution-to-core embedding approximation error into truncation, estimation, and core selection terms. It establishes that the quality of the core selection is the primary factor affecting approximation quality.
2. Fixed-Core Assignment Optimality: It formulates the one-pass assignment with fixed cores as a problem on a partition matroid, proving that the greedy rule is optimal for the CaD clustering objective. This explains why a simple greedy search can outperform iterative optimization methods (like EM) once the distributional proxies are established.
3. Near-Optimality and Label Recovery: The authors link the KME approximation error to the clustering objective, providing a near-optimality guarantee. They derive a margin-based condition showing that if the embedding error is smaller than half the distribution score margin, the greedy assignment guarantees exact label recovery.
4. Diagnostic Validation: Through synthetic experiments, the paper validates the error decomposition, demonstrating that the theoretical bounds hold and that the core bias bound, while conservative, correctly captures the decay trends of approximation errors as sample size increases.

Results

• Theoretical: The analysis proves that CaD clustering via greedy search is optimal for the assignment step given fixed cores. It provides a theoretical basis for why CaD methods can discover clusters of arbitrary shapes, densities, and sizes, whereas set-oriented methods fail.
• Empirical:
  • Experiments on five synthetic datasets (including non-convex shapes like Two-Moons and Concentric Rings) show that as sample size increases, estimation and truncation biases decrease, and Normalized Mutual Information (NMI) converges to 1.
  • Comparisons with Kernel k-means (KKM) reveal that while KKM's objective value may decrease, it often fails to recover ground-truth clusters on non-convex data due to poor representation by mean vectors. In contrast, CaD methods (using distributional proxies) achieve perfect clustering (NMI=1, Total Error=0) on these datasets.
  • The "warm start" provided by CaD's distributional representation allows KKM variants guided by CaD to converge faster and to better solutions than vanilla KKM.

Significance and Claims

The paper claims to provide the first theoretical understanding of why CaD clustering via greedy search is effective from both statistical and combinatorial perspectives.

• Overcoming Impossibility Theorems: The authors note that existing impossibility theorems for clustering (e.g., Kleinberg's) are derived based on the set-oriented view. By shifting to the "Cluster-as-Distribution" view, CaD clustering circumvents these limitations, making correct cluster identification possible where set-oriented methods fail.
• Simplicity vs. Complexity: The work demonstrates that complex optimization (deep learning, EM, eigen-decomposition) is not strictly necessary for optimal clustering if the problem is framed correctly (as a distributional assignment on a matroid). The "greedy" nature of the assignment is not a heuristic compromise but a mathematically optimal strategy for the fixed-core subproblem.
• Practical Implications: The findings suggest that the reliability of CaD clustering depends on the representativeness of the core clusters and sufficient sample size. It provides a mathematical guarantee that a one-pass assignment is reliable under these conditions, offering a robust alternative to iterative, initialization-sensitive methods.

The paper concludes that the "Cluster-as-Distribution" assumption renders the proof of greedy optimality straightforward, offering a new paradigm that resolves the mismatch between assumed cluster structures and actual data distributions.