Research map / Learning theory and algorithms / Clustering

Accelerating data-driven algorithm selection for combinatorial partitioning problems

NeurIPS 2025 · Learning theory and algorithms › Clustering · approach: Clustering approximation algorithms · 1 citations (OpenAlex)

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.

Introduces "size generalization" theory showing that the performance of clustering (k-means++, k-centers via softmax, single-linkage) and max-cut (Goemans-Williamson, Greedy) algorithms on a large instance can be estimated from a random subsample, with sample-size guarantees, and validates it experimentally.

Problem

Data-driven algorithm selection requires running every candidate algorithm on every training instance, which is expensive; there is no theory for when performance on small proxy (subsampled) instances predicts performance on the full instance for combinatorial partitioning problems.

Approach

Formalize size generalization: estimate an algorithm's value on a large instance by running it on a random subsample, and derive sample-size bounds for center-based clustering (via MCMC approximation of seeding and a softmax k-centers variant), single-linkage (via a min-max distance stability parameter), and max-cut (SDP convergence under subsampling for GW, and a martingale-based bound for Greedy

Key results

• On max-cut graphs with n=50, GW and Greedy densities on subsamples converge to full-graph values as sample fraction grows; for random geometric and barbell graphs a small subsample identifies the better algorithm.
• Runtime table at n=500: an 80% subsample reduces GW runtime from 961 s to 370 s, and a 60% subsample to 72 s.
• Softmax k-centers with small beta (O(1)) often achieves a lower k-centers objective than Gonzalez's heuristic on tested datasets.

Measured effects reported in the paper

Surprising findings

• Softmax k-centers with fixed beta=1 tracks Gonzalez's objective as n grows, and sometimes beats it, since Gonzalez's deterministic farthest-point rule is pessimistic.
• Lemma shows GW rounding is not Lipschitz in the SDP solution: two optimal SDP solutions with equal objective can yield GW cut distributions differing by Omega(n), so SDP-value convergence alone does not give GW cut convergence.

Limitations

• Single-linkage size generalization requires a sample size depending on the instance-specific stability parameter zeta, which can be as large as n for worst-case instances.
• Center-based bounds require well-balanced clusters and an assumption on softmax beta; theory is for the one-step k-means++ variant.
• Experiments are small-scale (n up to 4000 for clustering, n=50 for max-cut graph families).

Experimental setup

Datasets: MNIST Omniglot Gaussian mixture (synthetic) noisy circles (synthetic) random graphs: Erdos-Renyi, Barbell, random geometric, Barabasi-Albert (synthetic)

Benchmarks: MNIST clustering Omniglot clustering Gaussian mixture clustering noisy circles clustering random max-cut graphs (n=50)

Metrics: clustering accuracy max-cut density k-centers objective runtime

Baselines: k-means++ Gonzalez's k-centers heuristic single-linkage Goemans-Williamson Greedy

Builds on: PAC-learning for data-driven algorithm selection k-means++ Goemans-Williamson MCMC k-means++ (Bachem et al.)

Closest papers by meaning

• Learning to Branch (ICML 2018 · similarity 0.88)
• Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.87)
• Bayesian Optimization of Combinatorial Structures (ICML 2018 · similarity 0.87)
• On Controlling the Size of Clusters in Probabilistic Clustering (AAAI 2018 · similarity 0.86)
• Accelerating ERM for data-driven algorithm design using output-sensitive techniques (NeurIPS 2024 · similarity 0.86)
• Optimal Algorithms for Learning Partitions with Faulty Oracles (NeurIPS 2024 · similarity 0.85)