Research map / Learning theory and algorithms / Clustering

Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation

ICML 2024 · Learning theory and algorithms › Clustering · approach: Subspace clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives concentration bounds for Gaussian kernel matrices under isotropic Gaussian data and uses the near-low-rank expectation to propose a hyper-parameter-free, anchor-based scalable multiple kernel clustering method (SMKC).

Problem

Multiple kernel clustering lacks statistical grounding: heuristic designs, hyper-parameters that require labels to tune, and O(n^2) cost that prevents scaling to large datasets.

Approach

Assume isotropic Gaussian views, show the expected Gaussian kernel matrix is near rank-k with a clustering structure and that the normalized empirical kernel concentrates around it; then fit a rank-k proxy to each base kernel and fuse them into a consensus rank-k matrix using anchor columns (n x s), with no tuning parameters.

Key results

• On the first six benchmarks SMKC reports the best ACC on all six datasets, e.g. 77.44% vs 72.11% for SMKKM on Handwritten.
• On large-scale datasets SMKC exceeds the best single view by 1.54%, 10.69%, 4.95%, 2.49%, and 7.18% in NMI, running in hundreds of seconds.
• Approximation error between subspaces of anchor-based and full-kernel solutions decreases with anchor number, consistent with the bound c*sqrt(1/s - 1/n).

Measured effects reported in the paper

Limitations

• Assumes equal view weights
• Relies only on the Frobenius norm for distances
• Theory tailored to Gaussian-distributed data

Experimental setup

Datasets: Synthetic3d 100Leaves Mfeat Wiki Handwritten ALOI-100 AwA Cifar10 Cifar100 YtVideo Winnipeg

Benchmarks: Synthetic3d 100Leaves Mfeat Wiki Handwritten ALOI-100 AwA Cifar10 Cifar100 YtVideo Winnipeg

Metrics: ACC NMI purity time (s)

Baselines: Single best kernel k-means MKKM ONKC MKKM-MiR LKAM LMKKM SMKKM Kernel k-means with Nystrom approximation

Builds on: kernel k-means multiple kernel k-means SMKKM Nystrom kernel approximation

Closest papers by meaning

• Hierarchical Multiple Kernel Clustering (AAAI 2021 · similarity 0.93)
• Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel (NeurIPS 2022 · similarity 0.92)
• Consistency of Multiple Kernel Clustering (ICML 2023 · similarity 0.90)
• COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025 · similarity 0.90)
• Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.88)
• Gaussian Mixture Models in Hilbert Spaces via Kernel Methods (NeurIPS 2026 · similarity 0.86)