Accelerating data-driven algorithm selection for combinatorial partitioning problems

Thank you for carefully reading our paper, conducting a thorough literature survey, and providing such insightful comments. We’re delighted that you view our work as filling “a nice gap in the literature” and were surprised to find no prior theoretical analysis of this question. We are also encouraged that you liked some of our proof techniques and think they are “quite nice”. Below, we address each point.

W1 & Q1: On developing a general technique for size-generalization

Thank you for raising the question of whether a unified framework guides the analysis of size generalization. In our paper, we deliberately chose a diverse set of canonical algorithms—ones that perform well in practice. These algorithms range from SDP‑based methods (Goemans–Williamson) to purely combinatorial heuristics (Gonzalez’s k‑centers, greedy max‑cut), showcasing size‑generalization behavior across fundamentally different paradigms and providing a proof-of-concept to guide future research. We view this breadth as one of our paper’s strengths.

Moreover, we believe some of the methods developed in this paper can extend to a wider class of combinatorial optimization problems. For instance, the primal–dual analysis used for Max‐Cut SDP should apply to any SDP formulation with strong duality (e.g., correlation‐clustering rounding, sensor‐network localization).

That said, we fully agree that a general theoretical toolkit for size generalization would greatly inspire future work. We will make this and the SDP extensions explicit in the Conclusion by adding:

Future work includes extending size‐generalization guarantees to broader classes of optimization problems, such as integer programming and additional SDP‐based algorithms (e.g., randomized rounding for correlation clustering). Another exciting direction for future work is to formulate a unified theoretical toolkit for size generalization—one that prescribes, given a new combinatorial algorithm, which structural properties to verify to guarantee that its performance on large instances extrapolates from small ones.

W2: Size generalization seems especially relevant for neural network training.

We thank the reviewer for highlighting the rich developments in size‐generalization for neural network training and scaling laws. However, our motivation comes from a pressing computational bottleneck in combinatorial optimization: even polynomial‑time algorithms, such as those used by SDP solvers, can be intractable on moderately large instances. For example, modern SDP solvers (as used in the GW algorithm) have worst‑case runtimes on the order of $O(n^{3.5})$ per iteration, requiring hours or days for graphs with only a few thousand nodes.

The standard paradigm in ML for combinatorial optimization is to train a model or design a heuristic on problem instances of modest size (where exact or near‑exact solutions are feasible) and then deploy it on much larger problems—e.g., routing, scheduling, or integer programs with thousands more variables—without retraining. The works cited in line 45 are about accelerating combinatorial algorithms and solvers, rather than neural network training. This strategy has seen orders‑of‑magnitude speedups in solvers for large MILPs, but there are no existing theoretical guarantees. Our work takes the first step in filling this gap by providing a theoretical framework for size generalization.

W3: Outdated references for application of clustering and max-cut

We think this is a great point. We will modify the first sentence in the Introduction with more recent applications of clustering and max-cut:

“Combinatorial partitioning problems such as clustering and max-cut are fundamental in machine learning (Ben-David ’18; Ezugwu et al. ’22), finance (Soloviev et al. ’25), and biology (Roy, Rudra ’24).”

Thank you very much for the careful review and inspiring discussion. We are grateful for your thoughtful questions, which allowed us to clarify key aspects and better highlight our contributions. In the camera-ready version, we will:

• Add the discussion about future‑work directions on a unified toolkit and SDP extensions (W1, Q1) in the Conclusion.
• Expand our motivation in the Introduction to highlight more recent combinatorial optimization use cases (W3).

Please let us know whether we have addressed your concerns and what can be further improved; we are happy to continue the discussion anytime until the end of the discussion period. We respectfully ask that if you feel more positively about our paper, to please consider updating your score. Thank you!

Thank you very much for your insightful review! We appreciate your constructive comments and are encouraged to find that you think the notion of size generalization has “practical significance in many scenarios”, and that we can provide a guarantee for a spectrum of canonical algorithms: “three widely used clustering algorithms and two max-cut algorithms”. We address the reviewer's questions below:

W1: Clustering experiment with n = 500 and k = 2 is simplistic.

Thank you for the suggestion. We have strengthened our experiments by including larger, more complex clustering instances, and will update the Experiment section in the camera-ready version:

• MNIST, Gaussian Mixture (GM), Noisy Circle (NC) with $n=2000$, $k=2$
• MNIST with $n=3000$, $k=5$ (we omit due to space constraint)
• MNIST with $n=4000$, $k=10$.

In each setting, we sample at fractions ${0.2,0.4,0.6,0.8,1.0}$ and report mean accuracy ± std over 10 trials.

$n = 2000$, $k = 2$:

$n = 4000$, $k = 10$:

In all settings—even $n = 4000$, $k = 10$—rankings stabilize by 40–60 % subsampling, confirming size-generalization at scale.

W2: Can we approximate ground‑truth with sublinear samples?

Thank you for raising this question! The short answer is yes: we subsampled at sizes $n ^ {\alpha}$ with $\alpha = 1/2, 3/4, 5/6, 7/8, 9/10, 1$ and measured mean accuracy with std (10 runs each):

In almost all cases, a sublinear sample size is enough to approximate the ground-truth accuracy. For example, k‑means++ and Gonzalez’s k‑centers recover 98–99% of full‑data accuracy by $n^{3/4}$. Single‑linkage shows higher variance but still converges near the ground truth.

Even when sublinear sampling isn’t sufficient, we find that any degree of subsampling still speeds up algorithm selection for the combinatorial problems we analyze. For example, on max‑cut instances with $n=500$ nodes, we measure average solve times (in seconds) at subsample fractions ${0.2, 0.4, 0.6, 0.8, 1.0}$:

We observe that:

• An 80% subsample cuts GW’s runtime by over 60% (from 961s to 370s)
• A 60% subsample cuts GW’s runtime by roughly 90% (to 72 s)
• Even the very fast Greedy enjoys relative speedups

Because our bounds vary smoothly with the subsample fraction, practitioners can trade a small accuracy loss for large compute savings while still reliably selecting the best algorithm.

W3: Concern about the two-oracle setting not available in practice

Our use of the distance and the ground-truth oracle matches the query‑based semi‑supervised clustering literature (e.g., Dasgupta, Long ’05; Balcan, Blum, Gupta ’09). Moreover, as we state in lines 136-137 in Section 2, the ground‑truth oracle can be instantiated by the same‑cluster query oracle, an oracle that is well-studied in prior work (Ashtiani, Kushagra, Ben-David ’16; Mazumdar and Saha, ’17; Saha, Subramanian ’19). Thus, we argue that our model does not rely on any stronger or more “idealized” oracles than those already accepted by prior work.

W4: Comparison to the sublinear-time algorithm literature

Thank you for your feedback! We will expand our related work section (Section 1.2 and Appendix B.1) as follows:

Our work is related in spirit to the long-standing area of sublinear-time algorithms, though with several key distinctions. Sublinear time approximation for max-cut dates back to 1998, when a constant time approximation scheme that approximates the max-cut objective for dense graphs within an error of $\epsilon n^2$ was developed (Goldreich, Holdwasser, Ron ’98). Many later works follow (Frieze, Kannan, ’99; Bhaskara, Daruki, Venkatasubramanian ’18). For example, Bhaskara et al. show that core-sets of size $O(n^{1 - \delta})$ can approximate max-cut in graphs with average degree $n^{\delta}$. Despite having weaker approximation guarantees compared to the GW algorithm, these algorithms can have much faster runtimes.

The goal of size generalization for max-cut, however, differs fundamentally from the goal of sublinear time approximation algorithms. Rather than estimating the optimal cut value, we directly estimate the empirical performance of specific heuristics. This enables principled algorithm selection among the best-performing methods, instead of defaulting to the fastest algorithm with looser guarantees. We note that Reviewers 74EK and orjk emphasized this objective is well-motivated by practical applications and fills an important gap in the literature.

That said, our framework could naturally be used to compare these sampling-based sublinear time algorithms alongside greedy and GW, efficiently determining instances where the sublinear time algorithms offer a comparable approximation to the more expensive algorithms and are thus preferable. Our results also don’t make restrictive assumptions on graph structure (e.g., density), unlike the sublinear approximation methods referenced, which we view as a strength.

The large body of sublinear‑time clustering research (e.g., Mishra et al ’01; Czumaj, Sohler ’06; Feldman et al. ’13; Chen et al. ’22) also pursues a different goal from our paper: approximating the optimal clustering cost under specific cost models (e.g., k‑means or k‑center), often with structural assumptions (bounded dimension, cluster separation) and via uniform sampling or coreset constructions. We discuss our cost model and why head-to-head comparison with coresets is impossible further in lines 79-87.

W5: typo in figure legend of Fig. 1(a)

Thank you for catching this. We will correct the legend in the camera-ready version.

Q1: The timing performance of both the subsampled and the original algorithms should be reported in the experiment.

Thank you for your suggestion! In combination with your suggestion in W1, we are scaling up our experiments and including runtime figures in addition to the accuracy or weight convergence plot in the Experiment section of the camera-ready version. Please refer to W2 for preliminary solve times experiment and analysis.

We sincerely thank the reviewer for their thoughtful comments, which have helped us clarify and strengthen our work. In the camera-ready version, we will incorporate the following revisions to the Experiment section:

• Correct the typo in Fig. 1(a) legend (W5)
• Scale up the clustering experiments (W1)
• Include runtime statistics for all subsample sizes with new figures (Q1)
• Expand related work on sublinear‑time algorithms (W4)

Please let us know whether we have addressed your concerns and what can be further improved; we are happy to continue the discussion anytime until the end of the discussion period. We respectfully ask that if you feel more positively about our paper, to please consider updating your score. Thank you!

Thank you for carefully reading our responses.

W1: We understand your preference not to expand the “core” experimental section during the rebuttal. Rather, our goal was to clarify that our results are not tied to the small-$n$ or $k = 2$ regime. Importantly:

• We emphasize that our main contributions are theoretical. Our theory applies to arbitrarily large $n$ (dataset size), with sample size $m$ independent of $n$ in several cases (Theorems 2.2, 2.7, 3.4). As such, our scalability claim is based on provable bounds, not only on empirical scaling trends.
• The goal of these simulations is to validate our guarantees in a controlled setting, as is common in theory-focused NeurIPS papers, since the primary focus is analytical. Datasets of these sizes are common in such papers [Shinde, Narayanan, Saunderson ’21; Yau, Karalias, Lu, Xu, Jegelka ’24], as are the specific datasets we chose (e.g., MNIST, CIFAR-10, Omniglot) [Balcan, Dick, Lang ’19; Baykal, Dikkala, Panigrahy, Rashtchian, Wang ’22]. We welcome the reviewer’s suggestions on specific datasets and scales that would be most convincing.

W4: We appreciate this perspective and agree that ideas from sublinear-time algorithms (e.g., sketching, coresets) are highly relevant. We will make this connection explicit in our Related Work section.

Our contribution, however, targets a different objective: instance-specific algorithm selection. This objective is largely orthogonal to the traditional goals of sublinear-time methods. While sublinear approaches can yield fast approximations for a single target problem, they are not designed to evaluate or compare a given set of candidate algorithms.

We also note that Reviewer 74EK emphasized in their latest response that this ability to evaluate candidate algorithms "is the key feature of the proposed size generalization scenario"; we refer you to their illustrative example. Adapting sublinear tools to this evaluation/selection objective is non-trivial for several reasons:

Max-cut: We emphasize that our goal is to estimate the empirical performance of the Goemans-Williamson (GW) algorithm—the state-of-the-art approximation algorithm—and the greedy algorithm, a classic heuristic with very different trade-offs.

We did not aim to estimate the performance of sublinear-time approximation algorithms. Although this is an interesting direction, it is outside the scope of our work.

That said, the approaches are complementary: in future work, sublinear-time approximation algorithms could be included as additional candidates in our selection framework, and bounds could be developed to determine the optimal probe size needed to compare their empirical performance to GW or greedy.

Clustering: We emphasize that the critical distinction between our work and the literature on sublinear-time clustering is that these works target specific clustering objectives (k-means, k-median, k-center) [Bachem, Lucic, Hassani, Krause ’16; Har-Peled, Mazumdar ’18; Cohen-Addad, Saulpic, Schwiegelshohn ’22]. Crucially, our framework works with arbitrary/adversarial ground truth, which we do not assume minimizes any known clustering objective. Thus, it is impossible to provide a head-to-head comparison.

Once again, we appreciate your thoughtful comments. Please let us know if you have any further questions or suggestions before the end of the rebuttal period, and we will be happy to address them.

We thank the reviewer for their review and detailed summary of our work. Below, we address their comments.

W1: trade-off characterized by smoothed Gonzalez's k-centers heuristic

Directly applying the framework … poses a challenge due to its deterministic nature, leading to high sample complexity (ϑk,f(X) = n). While a smoothed variant (SoftmaxCenters) is introduced to address this, it creates a trade-off with the algorithm's strict approach.

In Section 2.1, we analyze the exact trade-off that the reviewer has pointed out. Indeed, this trade-off is the focus of our analysis in Section 2.1 (Lines 172–192), where we show exactly how smoothing (i.e., the choice of $\beta$) affects both the sample complexity and the approximation quality.

In Theorem 2.3, we provide an approximation guarantee for the k-centers objective of SoftmaxCenters, showing that this smoothed variant has nearly the same approximation ratio as Gonzalez’s k-centers heuristic. Empirically (Figure 7, Appendix C.1), we further demonstrate that even for vanishingly small $\beta$, SoftmaxCenters outperforms Gonzalez’s algorithm, achieving lower objective values. This behavior is consistent with prior observations that smoothing can improve heuristic performance (García-Díaz et al. ’17).

To make these results more visible, we will use our extra camera-ready page to move these experimental results into the main text, providing a compelling demonstration of the performance of SoftmaxCenters.

W2: SL potentially requiring large subsamples

“[Single linkage] is known to be theoretically unstable, and its sample complexity for size generalization (Theorem 2.7) depends on factors such as cluster separability (ϑk, SL(X)) and minimum cluster size, potentially requiring large subsamples when these values are high.”

It is well known (and we explicitly cite in lines 198-199) that single linkage can be unstable when clusters are poorly separated. Our Theorem 2.7 does not introduce this limitation—it precisely characterizes the stability of SL to deletions of individual datapoints. Moreover, as we describe in lines 238-240, in Appendix C.3, we show that our sample complexity bounds are tight. To ensure these insights are front and center, we will move both the theorem statement and its matching lower bound into the main body of the camera‐ready version. We believe that clarifying the exact regimes in which SL remains stable versus when it becomes deletion‐sensitive represents a valuable contribution of this section.

W3: Analysis of the Greedy algorithm is limited to unweighted graphs

Indeed, our max‑cut Greedy analysis (Theorem 3.1) assumes unweighted graphs. However, this assumption is standard in the literature (e.g., Feige, Karpinski, Langberg ’02; Mathieu, Schudy ’08; Fotakis, Lampis, Paschos ’15; Wang, Wu, Zuo ’24) and clearly stated in Sec. 3.2. Extending to general weights is orthogonal to our main goal of illustrating distinct size‑generalization behaviors across algorithmic paradigms. We will add the references mentioned here to our camera-ready version to more clearly illustrate this point.

W4: non-Lipschitzness of GW objective leading to multiplicative and additive errors

While the SDP objective value converges, the distribution of GW cut values after random rounding can differ even with different optimal SDP solutions, indicating non-Lipschitz behavior between the SDP solution and the GW cut value. This implies that estimating the cut value itself, in addition to the SDP value, involves both multiplicative and additive errors.

We see this not as a weakness but rather a summary of Theorem 3.3. Rather than a drawback, proving that no purely multiplicative bound exists—and then developing a combined multiplicative and additive estimator—is a technical advancement (Sec. 3.3). If the GW cut value were Lipschitz in the SDP solution, a purely multiplicative guarantee would be trivial. Our work tackles the hard, non‑Lipschitz regime. Thus, the fact that we are able to provide a bound despite this non-Lipschitzness is a strength of our analysis, not a weakness of our result.

W5: The current application does not include what’s listed in the future directions

“Extension to other combinatorial optimization problems, such as integer programming and dynamic programming, is mentioned as 'interesting future directions', implying that its current applicability is limited.”

We respectfully disagree. We already cover five canonical methods (three clustering, two max‑cut) to demonstrate our framework’s breadth (Sec. 1.1). Proposing future directions—integer programming and dynamic programming among them—is a standard practice to inspire follow‑up work and does not diminish our current contributions.

Q1: Extension to other combinatorial problems

In our paper, we deliberately chose a diverse set of canonical algorithms—ones that perform well in practice. These algorithms range from SDP‑based methods (Goemans–Williamson) to purely combinatorial heuristics (Gonzalez’s k‑centers, greedy max‑cut), showcasing size‑generalization behavior across fundamentally different paradigms and providing a proof-of-concept to guide future research. We view this breadth as one of our paper’s strengths.

Moreover, we believe some of the methods developed in this paper can extend to a wider class of combinatorial optimization problems. For instance, the primal–dual analysis used for Max‐Cut SDP should apply to any SDP formulation with strong duality (e.g., correlation‐clustering rounding, sensor‐network localization).

That said, we fully agree that a general theoretical toolkit for size generalization would greatly inspire future work. We will make this and the SDP extensions explicit in the Conclusion by adding:

Future work includes extending size‐generalization guarantees to broader classes of optimization problems, such as integer programming and additional SDP‐based algorithms (e.g., randomized rounding for correlation clustering). Another exciting direction for future work is to formulate a unified theoretical toolkit for size generalization—one that prescribes, given a new combinatorial algorithm, which structural properties to verify to guarantee that its performance on large instances extrapolates from small ones.

We hope this clarifies that each point raised either restates known properties or actually highlights our innovations—the $\zeta$‑smoothness mechanism, tight SL bounds, and the novel treatment of non‑Lipschitz rounding. We thank the reviewer again for their feedback and would be happy to discuss further.

Thank you very much for your careful reading and encouraging feedback. We’re delighted that you find our formalization of size‑generalization both practically meaningful—“people in the field of machine learning test their models on small datasets, and implicitly assume size generalization most of the time”—and “inspiring to more combinatorial algorithms.” Your questions also led to an exciting new experiment that we will include in the camera-ready version. Below, we address each point.

W1: “A pragmatic substitute for the theoretical sample complexity”

This is a great point! We agree that an adaptive “probe‐and‐stop” strategy could serve as a pragmatic complement to our sample‐complexity bounds. To validate this idea, we ran preliminary experiments on four max‐cut problems (random geometric, Erdős–Rényi, barbell, and Barabási–Albert graphs) with $n=100$ nodes. For each instance, we drew 2, 4, 8, …, 64 nodes, solved the problem using both Greedy and Goemans–Williamson (GW), and averaged the objective over 10 trials. In every case, the relative ranking of Greedy vs. GW stabilized by 8–16 samples:

We will include these results and a brief discussion in the camera-ready version and continue scaling to more instances.

W2 & Q1. On “extending size generalization results to more combinatorial algorithms [with] a more general framework”

Thank you for raising the question of whether a unified framework guides the analysis of size generalization. In our paper, we deliberately chose a diverse set of canonical algorithms—ones that perform well in practice. These algorithms range from SDP‑based methods (Goemans–Williamson) to purely combinatorial heuristics (Gonzalez’s k‑centers, greedy max‑cut), showcasing size‑generalization behavior across fundamentally different paradigms and providing a proof-of-concept to guide future research. We view this breadth as one of our paper’s strengths.

Moreover, we believe some of the methods developed in this paper can extend to a wider class of combinatorial optimization problems. For instance, the primal–dual analysis used for Max‐Cut SDP should apply to any SDP formulation with strong duality (e.g., correlation‐clustering rounding, sensor‐network localization).

That said, we fully agree that a general theoretical toolkit for size generalization would greatly inspire future work. We will make this and the SDP extensions explicit in the Conclusion by adding:

Future work includes extending size‐generalization guarantees to broader classes of optimization problems, such as integer programming and additional SDP‐based algorithms (e.g., randomized rounding for correlation clustering). Another exciting direction for future work is to formulate a unified theoretical toolkit for size generalization—one that prescribes, given a new combinatorial algorithm, which structural properties to verify to guarantee that its performance on large instances extrapolates from small ones.

Q2: Ways to “decide or guess the smoothing parameters”

This point relates closely to W1—please also see our response there for an implementation of the reviewer’s subsampling method. Moreover, if by “smoothing parameter” you are referring to the $\zeta$ terms in our sample complexity bound, Theorem 2.4 shows that they can be bounded in terms of the data radius and the choice of $\beta$. Likewise, Theorem C.1 (see Line 193 for the forward reference in the main body) shows, under a high‑dimensional Gaussian data model, that one can bound the term for $k$-means++. Single‐linkage is more challenging due to its instability; in practice, one could estimate $\zeta$ from a pilot sample. If we have misunderstood your question, please let us know, and we will be happy to clarify further during the discussion period.

We sincerely thank you again for your detailed review and thoughtful questions. In the camera-ready version, we will incorporate:

• The probe‑and‑stop subsampling experiment (W1)
• Explicit future‑work directions on a unified toolkit and SDP extensions (W2, Q1) in the Conclusion

Please let us know whether we have addressed your concerns and what can be further improved; we are happy to continue the discussion anytime until the end of the discussion period. We respectfully ask that if you feel more positively about our paper, to please consider updating your score. Thank you!