Research map / Learning theory and algorithms / Prediction and decision losses
Nested Mini-Batch K-Means
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 |
|---|---|---|---|
| Nested mini-batches with triangle-inequality bounds (nmbatch) instead of uniform mini-batches (mbatch) | nmbatch · 3 dense datasets | time to reach 2% of E*: 10x to 100x earlier | Helped |
| nmbatch instead of mbatch on sparse RCV1 | nmbatch · RCV1 | time to reach 0.5% of E*: 0.5% | Helped |
| nmbatch versus exact algorithms (lloyd, yinyang) on final energy | nmbatch · all datasets | final validation energy | No clear effect |
| Large doubling threshold rho in {10,100,1000} with bounds (ablation) | nmbatch · all datasets | time-energy: 10^2 vs 10^3 | No clear effect |
| Use rho=10 instead of larger rho with bounds disabled (ablation) | nmbatch.deact · all datasets | time-energy: 10^1 vs 10^2, 10^3 | Helped |
| Remove old assignments in mbatch (mbatch.remove) (ablation) | mbatch · all datasets | time-energy | Helped |
| Deactivate bound test in nmbatch (nmbatch.deact) (ablation) | nmbatch · all datasets | time-energy | Hurt |
| nmbatch.deact versus mbatch.remove (ablation) | nmbatch.deact · all datasets | time-energy | Mixed |
| Own mbatch implementation versus scikit-learn on INFMNIST | mbatch · INFMNIST | time (s): 20.6 -> 12.4 | Helped |
| Own mbatch implementation versus scikit-learn on RCV1 | mbatch · RCV1 | time (s): 63.6 -> 15.2 | Helped |
| Own mbatch implementation versus sofia on RCV1 | mbatch · RCV1 | time (s): 23.3 -> 15.2 | Helped |
Closest papers by meaning
- Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations (ICLR 2023 · similarity 0.86)
- Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.86)
- Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS (AAAI 2018 · similarity 0.86)
- Simple, Scalable and Effective Clustering via One-Dimensional Projections (NeurIPS 2023 · similarity 0.85)
- Near-Linear Time Approximation Algorithms for k-means with Outliers (ICML 2024 · similarity 0.85)
- Power k-Means Clustering (ICML 2019 · similarity 0.85)
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.