Research map / Learning theory and algorithms / Clustering
Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
Shusen Wang, Alex Gittens, Michael W. Mahoney
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase sketch size c from 100 to 1600 (ablation) | Nystrom kernel k-means · MNIST8M (s=20) | NMI: 0.3833 -> 0.4069 | Improved |
| increase sketch size c from 400 to 1600 (ablation) | Nystrom kernel k-means · MNIST8M (s=80) | NMI: 0.4101 -> 0.4233 | Improved |
| increase sketch size c from 100 to 1600 (ablation) | Nystrom kernel k-means · MNIST8M (s=20) | total runtime (s): 227.4 -> 2785.4 | Hurt |
| increase target dimension s from 10 to 80 (ablation) | Nystrom kernel k-means · MNIST8M (c=1600) | NMI: 0.3852 -> 0.4233 | Improved |
| increase target dimension s from 80 to 160 (ablation) | Nystrom kernel k-means · MNIST8M (c=1600) | NMI: 0.4233 -> 0.4086 | Hurt |
| increase target dimension s from 10 to 320 (ablation) | Nystrom kernel k-means · MNIST8M (c=1600) | total runtime (s): 2840.9 -> 3537.5 | Hurt |
| increase compute nodes from 8 to 32 (ablation) | Nystrom kernel k-means · MNIST8M (c=400, s=20) | total runtime (s): 3201.5 -> 867.9 | Improved |
| increase compute nodes from 32 to 128 (ablation) | Nystrom kernel k-means · MNIST8M (c=400, s=20) | total runtime (s): 867.9 -> 828.2 | No clear effect |
| increase compute nodes from 32 to 128 (ablation) | Nystrom kernel k-means · MNIST8M (c=400, s=80) | total runtime (s): 940.6 -> 1232.4 | Hurt |
| use Nystrom instead of random feature maps | approximate kernel k-means · medium-scale datasets (MNIST, Mushrooms, PenDigits) | NMI and objective | Improved |
| use Nystrom or RFM instead of the two-step method | approximate kernel k-means · medium-scale datasets | NMI and objective | Improved |
| vary target rank s (k, sqrt(ck), c) (ablation) | Nystrom kernel k-means · medium-scale datasets | NMI and objective | No clear effect |
Closest papers by meaning
- Randomized Clustered Nystrom for Large-Scale Kernel Machines (AAAI 2018 · similarity 0.92)
- Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.91)
- Nyström Method with Kernel K-means++ Samples as Landmarks (ICML 2017 · similarity 0.90)
- SimpleMKKM: Simple Multiple Kernel K-Means (TPAMI 2022 · similarity 0.90)
- Unified K-Means Clustering with Label-Guided Manifold Learning (ICML 2025 · similarity 0.88)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
