Research map / Learning theory and algorithms / Clustering
Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS
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 |
|---|---|---|---|
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=1×10^7, d=10, k=5, ε=0.20) | sample-size reduction factor: 94.4 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=2.5 × 10^6, d=10, k=5, ε=0.20) | sample-size reduction factor: 90.2 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=2 × 10^6, d=10, k=20, ε=0.20) | sample-size reduction factor: 83.2 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · MNIST | sample-size reduction factor: 26.9 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Fashion | sample-size reduction factor: 17.5 | Helped |
| Select a sweet-spot prefix of kmeans++ centroids for one2all rather than always using the worst-case centroid count | Adaptive one2all · Clustering sample construction | sample size | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=5×10^5, d=10, k=5, ε=0.10) | sample-size reduction factor: 20.0 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=5×10^5, d=10, k=5, ε=0.20) | sample-size reduction factor: 73.3 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=2 × 10^6, d=10, k=20, ε=0.10) | sample-size reduction factor: 20.7 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=2 × 10^6, d=10, k=50, ε=0.20) | sample-size reduction factor: 33.5 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=2×10^6, d=10, k=100, ε=0.20) | sample-size reduction factor: 16.2 | Helped |
| Use adaptive one2all sampling instead of the worst-case coreset size | Clustering sample construction · Mixture of Gaussians (n=1×10^6, d=20, k=10, ε=0.10) | sample-size reduction factor: 18.9 | Helped |
Closest papers by meaning
- A Sampling-Based Approach for Efficient Clustering in Large Datasets (CVPR 2022 · similarity 0.91)
- Gradient Based Clustering (ICML 2022 · similarity 0.90)
- Simple, Scalable and Effective Clustering via One-Dimensional Projections (NeurIPS 2023 · similarity 0.90)
- Improved Learning-augmented Algorithms for k-means and k-medians Clustering (ICLR 2023 · similarity 0.90)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.88)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 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.