Research map / Learning theory and algorithms / Clustering
Sharper Generalization Bounds for Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Replace Rademacher-complexity bound (O(K/√n)) with local clustering Rademacher complexity and covering-number assumption (logarithmic covering number, Assumption 2) | excess clustering risk bound for clustering framework · theoretical excess risk bound | convergence rate of excess clustering risk: from O(K/√n) to e O(K^2/n) | Helped |
| Bound clustering Rademacher complexity by max per-coordinate complexity with factor sqrt(K) instead of K (Foster & Rakhlin-based refinement) | clustering Rademacher complexity bound · theoretical excess risk bound | convergence rate of excess clustering risk: from O(K/√n) to O(√K/√n) for hard clustering (L=1) | Helped |
| Use covering-number assumptions with the improved K-dependence (Lipschitz L∞ assumption) in the local Rademacher bound | hard clustering (k-means, kernel k-means) excess risk bound · theoretical excess risk bound | convergence rate of excess clustering risk: from O(K^2/n) to e O(K/n) | Helped |
| Bounded-support assumption only (no covering number) with Rademacher-based bound for hard clustering | hard clustering (k-means, kernel k-means) excess risk bound · bounded hypothesis functions | convergence rate of excess clustering risk: from O(K/√n) to O(√K/√n) | Helped |
Closest papers by meaning
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.88)
- Generalization Performance of Ensemble Clustering: From Theory to Algorithm (ICML 2025 · similarity 0.86)
- Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants (AAAI 2025 · similarity 0.86)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.86)
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.85)
- Slicing Mutual Information Generalization Bounds for Neural Networks (ICML 2024 · similarity 0.84)
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.