Accelerating data-driven algorithm selection for combinatorial partitioning problems
Authors: Vaggos Chatziafratis
Ishani Karmarkar
Yingxi Li
Ellen Vitercik
Venue: NeurIPS 2025 spotlight ()
Keywords: data-driven algorithm selection
sub-sampling
clustering
max-cut
Goemans-williamson
Primary area: theory
TL;DR: We formalize the notion of size generalization in the context of data-driven algorithm selection and prove size generalization guarantees for three clustering algorithms and two max-cut algorithms.

Abstract: Data-driven algorithm selection is a powerful approach for choosing effective heuristics for computational problems. It operates by evaluating a set of candidate algorithms on a collection of representative training instances and selecting the one with the best empirical performance. However, running each algorithm on every training instance is computationally expensive, making scalability a central challenge. In practice, a common workaround is to evaluate algorithms on smaller proxy instances derived from the original inputs. However, this practice has remained largely ad hoc and lacked theoretical grounding. We provide the first theoretical foundations for this practice by formalizing the notion of size generalization: predicting an algorithm's performance on a large instance by evaluating it on a smaller, representative instance, subsampled from the original instance. We provide size generalization guarantees for three widely used clustering algorithms (single-linkage, k-means++, and Gonzalez's k-centers heuristic) and two canonical max-cut algorithms (Goemans-Williamson and Greedy). We characterize the subsample size sufficient to ensure that performance on the subsample reflects performance on the full instance, and our experiments support these findings.

Accelerating data-driven algorithm selection for combinatorial partitioning problems
Vaggos Chatziafratis UC Santa Cruz vaggosQucsc. edu
Ishani Karmarkar Stanford University ishanik@stanford. edu
Yingxi Li Stanford University
yingxi@stanford.co
Ellen Vitercik Stanford University vitercik@@ttanford.ccm
Abstract
Data-driven algorithm selection is a powerful approach for choosing effective heuristics for computational problems. operates by evaluating algorithms collection of representative training instances and selecting the one with the best empirical performance. However, running each algorithm on every training instance is computationally expensive, making scalability a cen- tral challenge. In practice, a common workaround is to evaluate algorithms on smaller proxy instances derived from the original inputs. However, this practice has remained largely ad hoc and lacked theoretical grounding. We provide the first theoretical foundations for this practice by formalizing the notion of size general- ization: predicting an algorithm's 's performance on a large instance by evaluating it smaller, representative instance, subsampled from the original instance. We provide size generalization guarantees for three widely used clustering algorithms (single-linkage, k-means++, and Gonzalez's ' k-centers heuristic) and two canoni- cal max-cut algorithms (Goemans- -iillams and Greedy). We characterize the subsample size sufficient ensure that performance the subsample reflects performance on the full instance, and our experiments support these findings.
candidate
Introduction
Combinatorial partitioning problems such as clustering and max-cut are fundamental in machine
learning [21 22) 39 40), finance [26) and biology [38 74]. These problems are typically NP-hard, which has prompted the development of many practical approximation algorithms and heuristics. However, selecting the most effective heuristic in practice remains key challenge. and there is little theoretical guidance on the best method to use on given problem instance or application domain. In clustering, for example, Ben-David [22) notes that algorithm selection is often performed "in very ad hoc, if not completely random, manner," which is unfortunate "given [its] crucial effect" on the resulting clustering.
To address this challenge, data-driven algorithm selection has emerged as a powerful approach, offering systematic methods to identify high-performing algorithms for the given domain [28] 36 63
73 73.84].
Gupta and Roughgarden [52] provided a formal PAC-learning framework for data-driven algorithm selection, where we given candidate algorithms A A1,...,AA and training problem instances X1 ..., X' from the application domain. value function value evaluates the algorithm's 's output quality for example, for max-cut, this is the density of the returned cut whereas for clustering, which
this is the quality the resultant clustering. The goal is then to select A E {A1,..,,AAA As)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

maximizes the empirical performance:
max JEIK]
Σ
value(AA(<
(I)
EE[N]
When N is sufficiently large, generalization bounds imply that A approximately maximizes the expected value on future wnseen problems from the same application domain [e.g..
14 18 52).
However, key computational challenge in solving Equation I is that it requires running each algorithm A, on every training instance X, Since the algorithms A, themselves often have super- linear runtime, this process quickly becomes prohibitively expensive, especially when N and the underlying training instances A; are large. Indeed, a major open direction is to design computationally
efficient data-driven algorithm selection methods [15] 24 53)
To help address this bottleneck, we introduce a new notion of size generalization for algorithm selection:
Question 1.1 (Size generalization). Given an algorithm A and problem instance X of size n, can we quickly estimate value(AA(X)) using small, representative problem instance of size m < n.?
Beyond enabling efficient data algorithm selection, size generalization has broader implica- tions, even in the absence of training instances. For example, when faced with a single large problem instance, Question I.1 provides natural framework for efficiently selecting suitable algorithm by evaluating candidate Agorithms' performance on a smaller, representative subsample.
Motivation from prior empirical work.
In discrete optimization, common heuristic for algorithm selection on large-scale problems to evaluate candidate algorithms on smaller, representative instances (e.g..3ll 35 46 51
[8]] Despite its widespread use, this approach remains ad hoc, lacking theoretical guarantees. We provide the first theoretical foundations for this practice.
1.1 Our contributions
To move towards a general theory of size generalization, we answer Question for two canonical combinatorial problems: clustering and max-cut, For clustering, we analyze three well-studied algorithms: single-linkage clustering, Gonzalez's k-centers heuristic, and k-means++. For max-cut, we analyze the classical scheme and the Greedy algorithm [47 64]. Finally, in Section 4 empirically validate theoretical findings. An exciting direction for future work is to extend this framework to other combinatorial algorithm selection problems, such integer dynamic programming [13 52)
Mainaann-illlamsoo (GW) semi-definite programming (SDP) rounding
key challenge in answering Question lies in the sequential nature of combinatorial a algorithms, which makes them highly sensitive to individual data points in clustering (Figures Saaurresannd and 9 in Ap-
pendix B.2) and specific nodes in max-cut BagguresAand555 Appendix B.2.2). This sensitivity makes it difficult to identify conditions under which algorithm's 's performance robust to subsampling.
Clustering algorithm selection. In Section we study clustering algorithm selection in the widely-studies semi-supervised setting [12
19 30 62 85), where each clustering instance X' has an underlying ground truth clustering and value(-) measures accuracy with respect to this ground truth. While the ground truth is unknown, it can be accessed through expensive oracle queries, which model interactions with a domain expert. A key advantage of data-driven clustering algorithm selection is that ground-truth information is only required for the training instances in Equation (I). Prior research bounds the number of training instances sufficient to ensure that in expectation over new clustering instances from the application domain-where the ground truth unavailable-the selected algorithm A" provides the best approximation to the unknown ground truth [2
We formalize the goal of size generalization for clustering algorithm selection as follows.
Goal 1.2 (Size generalization for clustering). Estimate the accuracy of a candidate clustering algorithm on an instance X' by running the algorithm on subsampled instance X' C X of size The selection procedure should have low runtime and require few ground-truth queries.
|X" < X
We present size generalization bounds for center-based clustering algorithms, including a variant of Gonzalez's k-centers heuristic and k-means++, as well as single-linkage clustering. For the

---

center-based algorithms, we show that under natural assumptions, the sample size sufficient to achieve Goal 1.2 is independent of [X] Meanwhile, the single- algorithm is known to be unstable in theory [29], yet our experiments reveal that its performance can often be estimated from subsample. To explain this robustness, we characterize when size generalization holds for single-linkage, clarifying the regimes in which it remains stable or becomes sensitive to deletions.
Comparison to coresets. Our clustering results complement research on coresets [e.g., 33 42 [54]
but differ fundamentally and are not directly comparable. Given a clustering instance X' with the goal of finding k centers that minimize a known objective h (such as the k-means objective), coreset a subset X. C X' such that for any set C of k centers, h(C; X) RJ ((C:X)). Coresets enable efficient approximation algorithms for minimizing h. However, we aim to minimize misclassification with respect to an unknown ground truth clustering. Thus, coresets do not provide any guarantees in our setting. We make no assumptions the ground truth clustering (c.g.. that it minimizes some objective or is approximation stable [10) is arbitrary and may even be adversarial with respect to andand we provide approximation guarantees directly with respect to the ground truth.
Max-cut algorithm selection. In Section B] we study max-cut- probleem with practical applica- tions in circuit design [20), physics [16], and data partitioning [72]with the following goal:
(Size generalization for max-cut). Estimate the performance of candidate max-cut algorithm on a graph G = (V, using a vertex-induced subgraph G[S] S c with (S] < [V].
Goal 1.3
Selecting between max-cut algorithms is non-trivial because competing methods differ sharply in solution quality and runtime. The GW algorithm outperforms the Greedy algorithm in many instances, but often, the reverse is true. Even when both produce cuts of comparable weights, Greedy has a significantly faster runtime, since GW solves the max-cut SDP relaxation-a computationally- expensive task-before performing randomized hyperplane rounding. Data-driven algorithm selection helps determine when GW's higher computational cost is justified.
To analyze GW, we prove convergence bounds for the SDP objective values under G and G[S], independent of graph structure. As such, we strengthen prior work by Barak al. [17] who provided GW SDP convergence guarantees only for random geometric graphs. We then show that the cut density produced by the GW algorithm on can be estimated using the subgraph G[S]. For Greedy, we build on prior work
(64] to bound the rate at which the cut density of G[S] converges to G.
1.2 Additional related work
Ashtiani and Ben-David study a semi- eemi-supervised approach to learning a data representation for clustering tasks. In contrast, we study algorithm selection. Voevodski et al. [22] study how to recover
a low-error clustering with respect a ground-truth clustering using few distance queries, assuming
the instance is "approximation stable" [10 meaning any clustering that approximates the k-medians objective is close to the ground truth. We make no such assumptions.
Our Max-Cut results complement theoretical work on estimating Max-Cut density using random vertex-induced subgraphs or coresets, with the aim of developing an accurate polynomial-time approximation or achieving a fast sublinear-time approximation [1H 23 43 64 (3). We build on this research in our analysis of Greedy, but these results cannot be used analyze the GW algorithm. Rather, we obtain our results by proving general guarantees for approximating the GW SDP using a subsample. Barak et al. [17] provide similar guarantees for broad class of SDPs, which includes the GW SDP; however, their results for max-cut rely on strong structural assumptions on the graph. contrast, our results for the GW SDP do not require any such graph structure assumptions. We discuss this further in Appendix B Beyond these works, there has been related work on sketch-and-solvy approximation algorithms for clustering via SDP relaxations, which is in a similar spirit to ours but in a different setting [32 68).
1.3 General notation
We use x Re y for the relation y - S x S 6. We define Σ,, to the permutations of [n] = {1...., n2. Given event E, E is the complement, and 1 (EE) is the indicator of E.
3

---

Input: Instance X' (21, 2mak) c CR k.m n Zz0. f: f - +R20
Set C¹ {(}} with oj ~ X) and ==1 11 is a counter for iterating over X
for i = 2.3...., k. do
Set x = It, d2 = dcenter (I; -1
// is a candidate cluster center
for j = 2,3....
do Set y= = It, dy dcenter (v: -0-)),-= 1++ if (
1/ is a fresh sample // I 4- y is the new candidate center
> Uniform(0, 1) then
S y and dz dy
Set C² = C U (x}
return O*
Algorithm 1: ApxSeeding m.
Size generalization for clustering algorithm selection
In this section, we provide size generalization guarantees for semi- cumi-supervised clustering algorithm selection. Section 2.1 covers k-centers and k-means+ and Section [22 covers single linkage.
We denote finite clustering instance X' Rd and let P(X) = {S S X} denote the power set of X. A collection (S1, Sk} is a k-clustering of X' if it k-partitions X' into A: disjoint subsets. We adopt the following measure of clustering quality, common in semi-supervised settings.
Definition 2.1 (5 10 121). Let C (Ci,.., Ck) be k-clustering of C. X and G (G1, .......C Gy)) be the ground-trune truth k-clustering of X. The cost of clustering C with respect to G is costg (C) == S/|S| min Exes Σje(h] [(x E Coti A x x& G3). : The accuracy of C is 1 - costy (C).
In Equation ① an algorithm's 's value in this semi-supervin supervisd setting is its clustering accuracy. We evaluate our methods by the number of queries to distance and ground-Iruth oracles. A distance oracle outputs the distance d(u, v) between queries u, X. A ground -ruth oracle, given E X and target number of clusters k. returns an index j E [A]] in constant time. The ground truth clustering G1, G...... GR is the partitioning of X' such that for all E Gj. the ground-truth oracle returns j. This oracle could represent a domain expert, as in prior work [6] 76, 80), and relevant in many real-world applications, such medicine [70), where labeling full dataset is costly. Further, it can be implemented using a same-cluster query oracle, which has been extensively studied [6 65 (6)
2.1 k-Means++ and k--Ceters clustering
We now provide size generalization bounds for center-based clustering algorithms. These al- gorithms return centers C {oi,... ..., C& R and partition X' into Si..., S₁. where each cluster is defined as S: = for i = argmin d(x,,;)) (with arbitrary tie-breaking). We de- fine deenter (x;; C) mine; d(I, G). Two well-known center-based clustering objectives are k- means, minimizing Σ deenter (x; C)2, and k-centers, minimizing max doenter((;;; (x:C). Classical ap- proximation algorithms for these problems are k-means++ 4 and Gonzalezzs heuristic (1985). respectively. Both are special cases of a general algorithm which we call Seeding. In Seeding, the first center is selected uniformly at random. Given i 1 centers C²-1, the next center e is sampled with probability x xf f(dcenter Under k-means++. ((;; 2² (following the one-step version common in theoretical analy- ses 77, and under Gonzalez's 's heuristic, which selects the farthest point from the existing centers, f(: = [(2 argmax deanter (æ; ))= Seeding terminates after rounds, requiring (1x)))) distance oracle queries. See Algorithm 3 in Appendix E.I for the pseudo-code of Seeding (X' k. f).
X'), where dictates the selection criterion.
To estimate the accuracy of Seeding with m samples, we use ApxSeeding (Algorithm D. an MCMC approach requiring only O(mk²) distance oracle queries. The acceptance probabilities are controlled by f. ensuring the selected centers approximate Seeding. ApxSeeding generalizes a method by Bachem et al. designed for k-means- to accommodate any function f. Also, unlike Bachem we provide accuracy guarantees with respect to an arbitrary ground truth.
et al.
Theorem 2.2 specifies the required sample size in ApxSeeding to achieve an e-approximation to the accuracy of Seeding. Our bound depends linearly on (x)), a parameter that quantifies the smoothness of the distribution over selected centers when sampling according to f in Seeding.

---

Ideally, if this distribution is nearly uniform, (x.)( is close to 1. However, if the distribution is highly skewed towards selecting certain points, then SR.5 (2) may be as large as n.
Theorem 2.2. Let C. IR, e, > 0. E (), and E Z Define the sample complexity m (x) log(k/e) where (x))(2() quantifies the sampling distribution's smoothness:
(k.r == max max (nf (nf(dcenterr() (x; 2): QCA:QIES ZE
Σ f(dcenter (y: Q):x) NER'
Let S and S' be the partitions of X induced by Seeding (X k. f) and ApxSeeding(Anit ki m. J) where Xmn a sample of mk points drawn uniformly with replacement from X. For any ground-truth clustering G of X, IE [costg (S")] Reg E (costg (5)]. Moreover, given S', costg (8") can be estimated to additive error e' with probability 1 - 5 using Okke' log((=1)) ground-truth queries.
Proof sketch. Let p(ay and (ca[C*=1) denote the probabilities that Seeding and ApxSeeding. respectively, select c; as the 7th center, given the first i centers C The proof's key technical insight leverages MCMC convergence rates to show that p(c, () and p' (c](C"=-) are close in total variation distance and thus the output distributions of ApxSeeding and Seeding are similar. O
Application to Gonzalez's 's k-centers heuristic. Directly applying our framework to Gonzalez's heuristic presents an obstacle: it deterministically selects the farthest point from its nearest center at each step, resulting in Se. (Xx)
and high sample complexity. We therefore analyze smoothed variant, SoftmaxCenters(2 X, k, B) = Seeding(X, [oottmaaaeCnr)te where /SoftmaxCanters (2; = exp(3z/I() It) and A = maX2.y d(x, y). This formulation introduces tradeoff with 3: larger values align the algorithm closely with Gonzalez's ' heuristic, yielding a strong k-centers approximation (Theorem 2.3 Conversely, smaller / promotes more uniform center selection, improving the mixing rate of MCMC in ApxSeeding and reducing sample complexity (Theorem 2.4p.
To address the first aspect of this tradeoff, we show that with an appropriately chosen B, SoftmaxCenters provides constant-factor approximation to the k-centers objective on instances with well- ballncelddedd k-centers solutions 88 37 61]. Formally, a clustering instance X' is (Hz, Pul-well- balanced with respect to partition SI,..., Ss if for all E [k),, Pe|x S |Sa] S Pul
Theorem 2.3. Let Zzo. Y 0 and 5 E (0, 1). Let SOPT be the partition of X induced by the optimal k-centers solution COPT, and suppose X' is (μe; (4)) wellaaaedde with respect to SOPT. Let C be the centers obtained by SoftmaxCenters with / = Ro- log (R.2 pupe -1 11-1) 8-1). With probability 1- 8, max deenter ( C*) < max deenter COPT) +%
Furthermore, Theorem 2.4 shows that (k.f can be bounded solely in terms of B. Theorem 2.4. For any B > 0, Cs.SoftmaxContter (X) S exp(233)
Setting 3 per Theorem 2.3 ensures the bound in Theorem 2.4 and thus the sample size sufficient for size generalizatinn-is independent of n and d. Moreover, our experiments (Section show that choosing smaller values of 3 still yields comparable approximations the k-centers objective.
Application to k-meanst+. Bachem et al. 7 identify conditions on X' to guarantee that Sk. +- (X) :- Ck (X) is independent of |X| and d: if X is from a distribution that satisfies mild non-degeneracy assumptions and has support contained in a ball of radius R, then St. + (X) scales linearly with 1t and k. See Theorem D.I in Appendix D.I for details.
2.2 Single-linkage clustering
We next study the far more brittle mongle-Iinkage (SL) algorithm. While SL is known to unstable ||| 29 our experiments (Section 4 reveal that its accuracy can be estimated on subsample-aid albiit larger than that of the center- based algorithms. To better understand this phenomenon, we pinpoint structural properties of X that facilitate size generalization when present and hinder it when absent.
SL (Algorithm 2 can be viewed as a version of Kruskall's algorithm for computing minimum spanning trees, treating X' as a complete graph with edge weights [d( ba)yex We define the inter-cluster distance ((,, B) == minge A B d(x, y) (see Figure 9alin in Appendix F.2.1p. Initially, each point z E X forms its own cluster. At each iteration, the algorithm increases distance threshold
5

---

Input:
Clustering instance X R2 and & Z20 Initialize ( : {C]- = {a1).... Ch {zn) ==
while | > 1 do
Set de := A. d(A, B) and Ci Ci-1
while there exist A, B E C such that d(A, B) d; do
Choose A, B E C* such that d( B) = d; and set C = C BA
if ( then
C C
// This is the algorithm's output
Set i = i+11
// Continued until |C*| 1 to define variables in the analysis
return C
Algorithm 2: (L)
d; and merges points into the same cluster if there is path between them in the graph with all edge weights at most d, The algorithm returns & clusters corresponding to the ht connected components that Kruskall's algorithm obtains. The next definition and lemma formalize this process.
Definition 2.5. The min- max distance between z, y E X is dmm (z, y: X)) minp max; d(pi, P++1), where the min is taken across all simple paths = (p1 = Z...., Ps = y) from x to y in the complete graph over X. For a subset S C X, we also define dmm (S; X) maxz,yeS dmmm (3., y; X).
Lemma 2.6. In SL(X,)), k), x. E X belong to the same cluster after iteration &. if and only if dmm( (x, yr X) $ de-
Proof sketch. The algorithm begins with each point isolated node and iteratively adds the lowest-weight edges between connected components. Nodes are connected after step if and only there is path connecting them where all edge weights are most de.
SL points X' sampled uniformly without replacement from X, so clusters merge based on dmm (I, y; X,m (rather than dmm (Ir, y; A)). Since subsampling reduces the number of paths, it can only increase min-max distance: dmm (2,, V; Xm) 2 dmm (I., y; X).. dmm (2. y; Xm) remains similar to dmm (I, y; X)) for most x, y E X, then SL(Xm, k) and SL(X', k) should return similar clusterings. We derive sample complexity bound ensuring that this condition holds which depends on ÇR.SL E (0, ra). defined as follows for clusters {Ci,..., C.. = SL(Xkk);
Suppose
Çk,SL (X) minn dmm (CUCC;;)) - max(e(s] dmm (C;;
maxxg(1] dmm (C,:
This quantity measures cluster separation by min-max distance, reflecting SL stability with respect to random deletions from X. Higher Çk. sI (X') indicates greater sensitivity to subsampling, while a lower value suggests robustness. Appendix D.2.1 provides a detailed discussion and proves ÇR.SL E (0,n).
Theorem 2.7. Let G [GI.... G be ground-trut truth clustering of X. C = {Ci,..., Ck} = SL(X', k) be the clustering obtained from the full dataset, and C' {CH..... C+}} SL(Xm, k) be the clustering obtained from random subsample Xm of size m. For
= =0((
k
n
+ (x)) log A )
min |C|
we have that TP (coste (C') Re costs (C)) 2 1 - 8. Computing C' requires (mm)) calls to the distance oracle, while computing costg (C') requires only m queries the ground-truth oracle.
Proof sketch. Let H be the event that C' is consistent with on Xm.. i.e., there is a permutation E ΣB such that for every i E [ke] C₁ C Catt)- The main challenge is to quantify how deviations from consistency affect the bottleneck distance.
H does not occur, we show that for some S C Xn,. dmm (S; Xm,) < dmm(( (S; indicating many consequential points must have been deleted. To formalize this, we lower bound the number of deletions required for this discrepancy to occur and thereby lower bound IP [H]. Conditioned on H. Hoeffding's bound implics the theorem statement. D

---

guarantees that small subsample suffices to approximate the accuracy of SL on the full dataset. Appendix [.2]] we show that the dependence on Çt,sL (X) and min [C;] in Theorem 2.7 is necessary, so our results are tight. Appendix D.2 also presents empirical studies of ÇR.SL on natural data-generating distributions.
When (x)) and 1/ min |C are small relative to Theorem 2.7
3 Max-cut
In this section, present size generalization bounds for max-cut. Section and Section 3.2 discuss the GW and Greedy algorithms, respectively. We denote a weighted graph as G = (V, E, w where Wij is the weight of edge (i, E E. The vertex set is V [n]. If G' is unweighted, we denote it as G = (V, E). We use Ag to denote the adjacency matrix, Dg for the diagonal degree matrix, and LG Da Ag for the Laplacian. The subgraph of G induced by S S V is denoted G[S]. A cut in G is represented by x E [-1,1]", and the max-cut problem is: argmax=e (-1,1)) weight (z), where weight& (z) := 1/2 E ((.)) Why 242g) is the cut weight and weight (z) /n² is its density, well-established metric in prior max-cut literature [17 64]
3.1 The -hilans-Willlamson (GW) algorithm
The GW algorithm yields a 888-approxiimation to the max-cut problem by solving the following semidefinite programming (SDP) relaxation, yielding a solution X SDDSollee()) E R to:
max 1/4 LG X subject to (e,e,) X 1 V O
(2)
GW then converts X into a cut using randomized rounding, denoted GWRound E {-1111) To do so, it generates standard normal random vector u IR" and computes the Cholesky factorization X = VVT, with V E Rax= It then defines the cut = GWRound(X) by computing the dot product between the 7th column v, of V and u: 2; = sign( o u). We denote the complete algorithm as GW) GWRound(SDPSolve(C)
E {-1,1]" (see Algorithm in Appendix E.3)
Theorem 3.1 provides a size generalization bound for the SDP relaxation objective 2 proving that the optimal SDP objective value for random subgraph G[S.] with B|][S.]] = converges to that of G as + n, without imposing any assumptions on G. Building on this result, Theorem 3.3 shows that the cut density produced by the GW algorithm G' can be estimated using just the subgraph G[S)].
Size generalization for GW SDP objective value. We begin with a size generalization bound for the SDP relaxation. Let SDP(G) denote the objective value of the optimal solution to Equation (2). We show that for a randomly sampled subset vertices S₁ with [| = t, the objective value increases. Our result holds for any graph G, unlike prior
SDP(G[S()) converges to SDP(G) work by Barak et al. [7], who proved GW SDP convergence only for random geometric graphs.
Theorem 3.1. Given G (V, E, W)), let St be a set of vertices with each node sampled from V independently with probability ; Let W = E(S)EE Wiy. Then
1 S.
1 - SDP(C)) n-t
(SDP((D)) W n2t
(DDP((())))]
n
Proof sketch. We prove this result by separately deriving upper and lower bounds on E(SDP(G(Ss)) The primary challenge is deriving the upper bound. To do so, we analyze the dual of Equation (
min
subject to
Σ yo (e,e,) = LG.
where e; E Rn denotes the all-zero vector with on index i. By strong duality, the optimal primal and dual values coincide. To produce upper bound E|SDP(G[S.). that depends the full graph G, let y be the optimal dual solution for G. Trimming y to dimensions yields a feasible but moose-solution to the dual SDP defined on G[S.). To tighten this solution, use the key observation that the portion of y corresponding to nodes in [n] \ St is superfluous for G[S.]. Lemma E. in Appendix E.3 shows that removing this component by setting ūJ = V ExEINNS. Wik yields
feasible dual solution providing tighter upper bound. Hence, Σt= 1 Ts upper bounds SDP(G
7

---

Next, to obtain lower bound that depends on the full graph G, let X be the optimal primal SDP solution induced by G. Without loss of generality, assume that S, consists of the first nodes in G. Trimming X to its t-th principal minor X [4] yields feasible solution to the primal SDP induced by G[S.]. Hence, l-a|s.) [[] a lower bound for SDP(G[S.))
As t n, the emror term goes to O. Notably, this result requires no assumptions on graph structure. The term SDP(G) - W/2 (or SDP(G) - /E for unweighted graphs) adapts to different graph structures. In unweighted sparse graphs, SDP(G) / is at most | 1/2 benefiting from sparsity. However, the bound is still vanishing for unweighted dense graphs: SDP(G) is approximately [E]/2, so SDP(G) //// approaches O. Meanwhile, in a graph with highly uneven weights, random subgraph is unlikely to represent the full graph well, and SDP(G) W/2 can be as large as W/2.
In Theorem E. in Appendix [.33 we include version of this result that holds with probability over S,. We apply McDiarmid Inequality to establish that with high probability, SDP(G[S() is close to its expectation and, therefore, close to the normalized SDP value induced by G.
Size generalization bounds for GW. We now present our size generalization bound for the GW algorithm. Given that the SDP objective values for the subsampled graph G[S,] and the full graph G converge, one might expect the GW cut values to converge at the same rate. However, Lemma 3.2 demonstrates that this is not necessarily the case: even if two distinct optimal SDP solutions have the same objective value, the resulting distributions of GW cut values after randomized rounding can differ. This arises due to the non-Lipschitz behavior of the mapping between the SDP solution and the GW cut value. See Figure 5 for an illustrative example, and Appendix E.3 for proof.
Lemma 3.2. For any 2 2, there exists graph Gn, n vertices with distinct optimal solu- tions Xn, * Yn to Equation (2) and a constant C > O such that LG, Xx, = Lo.. Yn but [[/eiight,, (GWRound(X, )) Elweight,,, (GWerguu (GWRound(Y.)))] Cn.
Nonetheless, we show that we can still use Theorem B.1 to upper and lower bound the GW cut value on the full graph as a function of SDP(G[)))). albeit with a multiplicative and additive error.
Theorem 3.3. Given G (V, E, w), let St be a ser of vertices with each node sampled from V independently with probability 4. Then,for ESDP mF (SDP(G) W) we have
0.878 t
weight& (GW(G)) E 2
IE [[SDP(G[(.)] - 0.878E E|SDP(G[S.)]]
St
t2 St
Proof sketch. By definition, weight; (GW(G)) < SDP(G), and moreover, weight, (GW(G)) 0.878. SDP(G) [47). Combining this with Theorem 3.1 which bounds the error of estimating the SDP optimal value, we obtain the theorem statement.
To interpret this result, we know that J weight (GW(G)) E 0.878 SDP(G), J.2 SDP(G)). Theo- n rem 3.3 shows that _े SDP(G) can be replaced by şेr Es, [SDP(G(s.)) which is much faster to compute-ve -with error ESDP that vanishes as + n. Thus, the GW cut value on can be estimated using the subgraph, providing an efficient way to estimate GW's performance on large graphs.
3.2 The greedy algorithm
We now present size generalization bounds for the Greedy 2-approximation algorithm. Despite its worse approximation guarantee, Greedy frequently performs comparably to-or or sometimes better than-GW (55] (66,, while requiring only linear runtime OlE Greedy iterates over the nodes in random order, denoted by the permutation a E Σ VI, and sequentially assigns each node to the side of the cut that maximizes the weight of the current partial cut (see Algorithm [5 Appendix [L.)). The next theorem shows we can approximate Greedy's 's performance with only (1)e²)) samples.
Theorem 3.4. Given an unweighted graph G (V, F.), let St be vertices sampled from V uniformly without replacement. For any e [0, 1] and t 2 2.
E weight (Greedy(G[s)))] s so(c+ log(l)
E weeegtt (Greedy(G))] n
Vn
8

---

OMNIGLOT
snhesmpled St.
means--
subhempped k-mranet
enhesmpled sifmor k. ceulees
6
Fraction of points subsampled
GM
NC
MNIST
MNIST
SL
05
subsampled
Aconcy
6.7
6.7
k means-+
subsampled
softmar cenins
subsampled
67
67
Fraction points subsampied
(a) Accuracy of clustering computed by SL, k-means++, and softmax k-centers on full data and on a subsample. Top row; n= 500 for MNIST, GM, and NC; = 40 for Omniglot (due to smaller instance size). Bottom row: n= 4000 and 10 for MNIST. Barahasi-Alhett
2000 for MNIST, GM, and NC; the final panel Barbell
Endor-Renyi
Random Geomerric
6.25
0.155
0.20
derdetitt
0075
0.23
0.130
3555
subsampled Greedy
Greedy
0.125
4035
CWW
0.955
0.255
subsampled GW
67
1
6
6
0.5
Fraction of nodes subsampled
(b) Density of cuts computed by GW and Greedy full graphs and on a subsample.
Figure 1: In the proxy algorithms' accuracies on the subsample approach those of the original algorithms on the full instance as the sample size grows. Figure shows this for clustering algorithms, and Figure Tb for max-cut algorithms. Shadows denote two standard errors about the average.
Proof sketch. At step f, we define the partial cut on the subset of nodes {o[ as 2' e {-1,0,1) VI, where zf E {-1,1} indicates node i has been assigned and z = 0 indicates it has not. To evaluate the quality Mathieu and Schudy [64]. Intuitively, &' serves as an extrapolation of x into complete (fractional) cut. It is defined by estimating how each unassigned vertex would have been assigned it had been selected at time < f,, and averaging this estimate over all possible times r. This construct allows us to compare partial and full cuts by bringing them comparative scale. Since Greedy adds nodes sequentially, the theorem statement is equivalent to bounding the difference between the densities of partial cut and the full cut. Analyzing the fictitious and partial cuts as martingales allows to bound the difference between the partial and full cuts using the fictitious cut.
partial cut, we use the concept
"fictitious"
Et, introduced by
Experiments
In this section, we present experiments validating that the best algorithm on a max-cut or clustering instance can be effectively inferred from subsample.
Clustering. We present experiments on four datasets. (1) The MNIST generator handwritten
digits with images labeled corresponding to them. (2) GM: points from 2-dimensional isotropic Gaussian mixture model sampled from N ((0, 0) 5L) or (([1, .5I) with probability 1/2 and labeled by the Gaussian from which it was sampled. (3) The Omniglot generator [3]: handwritten characters from various languages, labeled by the language. (4) The noisy circles (NC) generator [69]: points on two concentric circles (with noise level 0.05, distance factor 0.2), labeled by the circle to which they belong. All instances contain n points evenly divided into k = clusters except the last panel of the bottom row, where k 10. On the top row, for MNIST, GM, and NC, 500. For Omniglot, n 40 (instances from this dataset are inherently smaller). On the bottom row, n 2000 for all except the last panel, where
4000.

---

Figure la compares the accuracy of the proxy algorithms from Section 2 run on the full dataset (averaged across 10 trials), plotted function of the number of randomly sampled points, m. As increases, the proxy algorithms' accuracies converge to those of the original algorithms. Appendix C.2.1 includes additional experiments on softmax k-centers. We show that its k-centers objective value approximates or improves over Gonzalez's s algorithm, even for small |3.
with the original algorithms
Max-cut. test four random graph families with with n 50 vertices: Brdöös-Réyni (p - 0.7), Barbell with 5 random inter-clique edges, random geometric (radius 0.9), and Barabási-Albert (m 5). Figure [b the mean cut density over 150 trials for full and subsampled graphs versus the sampled fraction. As the sample size grows, the Greedy and GW densities the subsamples converge to the full-graph values. For the random geometric and barbell graphs, even a small subsample reveals the better-perte petter-performing algorithm, enabling low-cost algorithm selection, while on Barabási-A Albert and Frdöös-Réyni the two curves coincide, implying that the faster Greedy will achieve comparable results. These results not only corroborate theory but also demonstrate even stronger convergence behavior. Appendix [ includes additional experiments on the SDP objective value convergence and demonstrates the percentage speed-up up gain from the subsampling scheme.
Conclusion
We introduced the notion of size generalization and established rigorous bounds for classical al- gorithms for two canonical partitioning problems: clustering and max-cut. Our analysis identifies sufficient conditions under which an algorithm''s performance on large instance can be estimated using small, representative instance, addressing a key computational bottleneck in data-driven algorithm selection.
We hope that our work provides useful techniques for future work on size generalization data-drive algorithm selection. In particular, we believe would be interesting extend our results 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 new combinatorial algorithm, which structural properties guarantee that its performance large instances can be extrapolated from small ones.
Acknowledgments
We thank the reviewers for their anonymous feedback. The authors would like to thank Moses Charikar for insightful discussions during the early stages of this work. This work was supported in part by National Science Foundation (NSF) award CCF-2338226 and a Schmidt Sciences A12050 fellowship.
10

---

References
[1] Noga Alon, W Fernandez De La Vega, Ravi Kannan, and Marek Karpinski. Random sampling and approximation of max-csps. In Journal of computer and system sciences, 2003.
[2] Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: it's s all about regularity. In 38th Annual ACM Symposium on Theory of Computing (STOC), 2006.
[3] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. In Proceedings of the twenty-sevent annual ACM symposium on Theory of Computing, pages
1995.
[4] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
[5] Hassan Ashtiani and Shai Ben-David. Representation learning for clustering: a statistical framework. In st Annual Conference Uncertainty in Artificial Intelligence (UAI), 2015.
[6] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Advances in Neural Information Processing Systems 29 (NeurIPS), volume 29, 2016.
[7] Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. In AAAI Conference Artificial (AAAI), 2016.
[8] Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, and Aarti Singh. Noise thresholds for spectral clustering. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2011.
[9] Maria-Florina Balcan. Data-driven algorithm design. Beyond the worst-case analysis of al- gorithms. In Beyond the Worst-Case Analysis of Algorithms, edited by Tim Roughgarden, 2020.
[10] Maria-Florina Balcan, Avrim Blum, and Anupam Gupta. Clustering under approximation stability. Journal of the ACM (JACM), 60(2):1-34, 2013.
[1]] Maria-Florina Balcan, Yingyu Liang, and Pramod Gupta. Robust hierarchical clustering, In The Journal of Machine Learning Research, 2014.
[12] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning- theoretic foundations of algorithm configuration for combinatorial partitioning problems. In 30th Annual Conference on Computational Learning Theory (COLT), 2017.
[13] Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning link. In 7th International Conference on Learning Representations (ICLR), 2019.
[14] Maria-Florina Balcan, Dan Deblasio. Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high- pethh-reffrmiggggg algorithms? Journal of the ACM, 7 1155):1588, 2024.
[15] Maria-Florins Balcan, Christopher Seiler, and Dravyansh Sharma. Accelerating ERM for daivee algorithm design using output-sensitive techniques. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), volume 37, pages 72648- 72687, 2024.
[16] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design. In Operations Research, 1988.
[17] Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer. Subsampling mathematical relaxations and average-case complexity. In 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
[18] Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference Learning Theory (COLT), 2022.
11

---

[19] Sugato Basu, Mikhail Bilenko, and Raymond J Mooney. A probabilistic framework for semi- supervised clustering. In 10th ACM SIGKDD International Conference on Knowledge Diseovery and Data Mining (KDD), 2004.
[20] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder. Investigating the effect circuit cutting in qaoa for the maxcut problem on nisq devices. In Quantum Science and Technology, 2023.
[21] Shai Ben-David. Clustering-whal both theoreticians and practitioners are doing wrong. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[22] Shai Ben-David. Clustering - what both theoreticians and practitioners are doing wrong. In AAAI Conference on Artificial (AAAI). 2018.
[23] Aditya Bhaskara, Samira Daruki, and Suresh Venkatasubramannian. Sublinear algorithms for maxcut and correlation clustering. In arXiv preprint arXiv:/882.00699,, 2018.
[24] Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing. In Interaational Conference on Machine Learning (ICML), pages 1540-1548. PMLR, 2021.
[25] Niv Buchbinder, Moran Feldman, Joseph Seffi and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. In SIAM Journal on Computing, 2015.
[26] Fan Cai, Nhien-An Le-Khac, and Tahar Kechadi. Clustering approaches for financial data analysis: survey, arXiv preprint w:xvv:/00.0085200 2016.
[27] Haiyan Cai. Exact bound for the convergence of metropolis chains. In Stochastic Analysis and Applications, 2000.
(28) Yves Caseau, François Laburthe, and Glenn Silverstein. A meta-heuristic factory for vehicle routing problems. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, 1999.
[29] Kamalika Chaudhuri, Sanjoy Dasgupta, Samory Kpotufe, and Ulrike Von Luxburg. Consistent procedures for cluster tree estimation and pruning. In IEEE Transactions on Information Theory, 2014.
[30] Weifu Chen and Guocan Feng. Spectral clustering: semi-supervised approach. Neurocom- puling, 2012.
[31] Cheng Chi, Amine Aboussalah, Elias Khalil, Juyoung Wang, and Zoha deep reinforcement learning framework for column generation. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2022.
A
[32] Charles Clum, Dustin G Mixon, Kaiying O' O'Hare, and Soledad Villar. Sketch-and-solve ap- proaches to k-means clustering by semidefinite programming. In Information and Inference: A Journal of the IMA, 2024.
[33] Vincent
Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for Euclidean k-means. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.
[34] Artur Czumaj and Christian Sohler. Sublinear-time approximation algorithms for clustering via random sampling. In Random Structures & Algorithms, volume 30, pages 226-256. Wiley Online Library, 2007.
[35] Hanjun Dai, Elias Boutros Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combi- natorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems 30 (NeurIPS), 2017.
[36] James Demmel, Jack Dongarra, Victor Eijkhout, Erika Fuentes, Antoine Petitet, Richard Vuduc, R. Whaley, and Katherine Yelick. Self-adapting linear algebra algorithms and software. In Proceedings of the IEEE, 2005.
12

---

[37] Brian Eriksson, Gautam Dasarathy, Aarti Singh, and Rob Nowak. Active clustering: Robust and efficient hierarchical clustering using adaptively selected similarities. In 14th International Conference Artificial Intelligence and Statistics (AISTATS), 2011.
[38] Mohammad Mahdi Ershadi and Abbas Seifi. Applications of dynamic feature selection and clustering methods to medical diagnosis. In Applied Soft Computing, 2022.
[39] Absalom E Ezugwu, Amit K Shukla, Moyinoluwa B Agbaje, Olaide N Oyelade, Adán José- García, and Jeffery O Agushaka. Automatic clustering algorithms: a systematic review and bibliometric analysis of relevant literature. In Neural Computing and Applications, volume 33, pages 6247-6306. Springer, 2021.
[40] Absalom E Ezugwu, Abiodun M Ikotun, Olaide O Oyelade, Laith Abualigah, Jeffery O Agushaka, Christopher I Eke, and Andronicus A Akinyelu. A comprehensive survey of clustering algorithms: State-of-the-arr machine learning applications, taxonomy, challenges, and future research prospects. In Engineering Applications of Artificial Intelligence, 2022.
[41] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569-578, 2011.
[42] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means. PCA and projective clustering, In 29th Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), 2018
[43] W Fernandez De La Vega. Max-cut has a randomized approximation scheme in dense graphs In Random Structures & Algorithms, 1996.
[44] Dimitris Fotakis, Michael Lampis, and Vangelis Th Paschos. Sub-exponential approximation schemes for csps: From dense to almost sparse. In arXiv preprint arXiv: 2015.
[45] Jesús Garefa-Díaz, Jairo Sánchez, Ricardo Menchaca-Mendez, and Rolando Menchaca-Meiin When worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem. In Journal of Heuristics, 2017.
[46] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[47] Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):11 1000:1155-11444 1145, 1995.
[48] Oded Goldreich. Property testing. In Lecture Notes in Comput. Sci, 2010.
[49] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. In Journal of the ACM (JACM), 1998.
[50] Teofilo F, Gonzalez. Clustering to minimize the maximum intercluster distance. In Theoretical Computer Science, 1985.
[51] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), volume 33, pages 18087-18097, 2020.
[52] Rishi Gupta and Tim Roughgarden. A PAC approach to application-speeifcc algorithm selection. In SIAM Journal on Computing, 2017.
[53] Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Communications of the ACM, 63(6):87-99) -44, 2020.
[54] Sariel Par-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In 56th Annual ACM Symposium Theory of Computing (STOC), 2004.
13

---

[55] Refael Hassin and Nikita Leshenko. Greedy differencing inge-contraction heuristic for the max-cut problem. In Operations Research Letters, 2021.
[56] Alexandre Hayderi, Amin Saberi, Ellen Vitercik, and Anders Wikum. MAGNOLIA: matching algorithms via GNNs for online value-to-go approximation. In International Conference on Machine Learning (ICML), 2024.
[57] Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning (ICML), pages 13869-13890. PMIR, 2023.
[58] Borja Ibarz, Vitaly Kurin, George Papamakarios, Kyriacos Nikiforou, Mehdi Bennani, Róbert Csordás, Andrew Joseph Dudzik, Matko Bošnjak, Alex Vitvitskyi, Yulia Rubanova, et al. A generalist neural algorithmic learner. In Learning graphs conference, pages 2-1. PMLR. 2022.
[59] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. In Constraints, 2022.
[60] Sera Kahruman, Elif Kolotoglu, Sergiy Butenko, and Illya V Hicks. On greedy construction heuristics for the max-cut problem. In International Journal of Computational Science and Engineering. 2007.
[61] Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu, and Aarti Singh. Efficient active algorithms for hierarchical clustering. In 29th International Conference on Machine Learning (ICML), 2012.
[62] Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. Semi-supervised graph clustering: a kernel approach. In 22nd International Conference on Machine Learning (ICML), 2005.
[63] Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and case study on combinatorial auctions. In Journal of the ACM, 2009.
[64] Claire Mathieu and Warren Schudy. Yet another algorithm for dense max cut: Go greedy. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008
[65] Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems 30 (NeurlPS), 2017.
[66] Renee Mirka and David P Williamson. An experimental evaluation of semidefinite programming and spectral algorithms for max cut. In ACM Journal of Experimental Algorithmics, 2023.
[67] Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert E Tarjan. Clustering social networks. In International Workshop on Algorithms and Models for the Web-Graph, pages 56-67. Springer, 2007.
[68] Dustin G Mixon and Kaiying Xie. Sketching semidefinite programs for faster clustering. In IEEE Transactions on Information Theory, 2021.
[69] Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Seikit-learn: Machine learning in Python. In Journal of Machine Learning Research, 2011.
[70] Mohammad Peikari, Sherine Salama, Sharon dofech-Mozer and Anne L Martel. A cluster- then-label semi-supervised learning approach for pathology image classification. In Scientific reports, 2018
[71] Pan Peng and Yuichi Yoshida. Sublinear-time algorithms for max cut, max e2lin (q), and unique label cover on expanders. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4936-4965. SIAM, 2023,
14

---

[72] Jan Poland and Thomas Zeugmann. Clustering pairwise distances with missing data: Maximum cuts versus normalized cuts. 23rd International Conference on Machine Learning (ICML), 2006.
[73] John R. Rice. The algorithm selection problem. In Advances in Computers, 1976.
[74] Suman Kumar Roy and Bhawana Rudra. Quantum-inspired hybrid algorithm for image classifi- cation and segmentation: Q-means++ max-cut method. In International Journal of Imaging Systems and Technology, volume 34, page e23015. Wiley Online Library, 2024.
[75] Hadas Sachnai and Tami Tamir. Polynomial-tine approximation schemes. In CRC Press, 2002.
[76] Barna Saha and Sanjay Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. In arXiv preprint arXiv:1908. 04996, 2019.
[77] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a SAT solver from single-bit supervision. Proceedings of the International Conference Learning Representations (ICLR), 2019.
[78] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning to cut. In International Conference on Machine Learning (ICML), pages 9367-9376. PMLR, 2020.
[79] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In 8th International Conference on Learning Representations (ICLR), 2020.
[80] Sharad Vikram and Sanjoy Dasgupta. Interactive bayesian hierarchical clustering. In 33rd International Conference on Machine Learning (ICML), 2016.
[81] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), volume 28, 2015.
[82] Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin, Shang-Hua Teng, and Yu Xia. Efficient clustering with limited distance information. In 26th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2010.
[83] David P Williamson and David B Shmoys. The design of approximation algorithms. In Cambridge university press, 2011.
[84] L. Xu, Hutter, H.H. Hoos, and K. Leyton-Brown. SATzilla: portfolio-based algorithm selection for SAT. In Journal of Artificial Intelligence Research, 2008.
[85] Xiaojin Jerry Zhu. Semi supervipe learning literature survey. In University of Wisconsin- Madison Department of Computer Sciences, 2005.
15

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We propose a size generalization framework for more efficient algorithm selection, and we proved size generalization bounds for clustering algorithms (Selection and max-cut algorithms (Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In this paper, we thoroughly discussed our use of assumptions and compared them with previous works. For the analysis of Goemans- Williamson' algorithm of max-cut, we made no structural assumption about the graph. For the analysis of the Greedy algorithm, we assumed that the graph is unweighted, a standard assumption that is also used in the work we followed up on (64]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
16

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We stated assumptions at the beginning of Section and Section S well as in each theorem statement. We provided all omitted proofs for results in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We release our code to reproduce experiment part of our supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
17

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Yes, we provide our code to run the experiment as part of our supplement material and will include documentation for the code to facilitate better reproducibility.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
public/guides/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurIPS code and data submission guidelines (https wwweeeeeeoooeeeiseeeseeeeeeeeeee
sooiiiiiiiiiiiyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: in Section 4 specified all data/random graph generators and parameters used to generate our random instances for our experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report two standard error over the number of repetitions we ran on all of our plots.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We include as part of our supplementary material the type of CPU used to run our experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We reviewed and adhered to the NeurlPS Code of Ethics throughout the execution of this project.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
19

---

We discuss the importance of efficient algorithm selection in real-world applications, especially modern computer science applications, which our work tries to establish theoretical framework for.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work is mostly theoretical, and experiments done are proof-of-concept that use only open-sourced packages and data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: There is no use of existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
20

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowd-sourcing or human subjects are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowd-sourcing research with human subjects.
Guidelines:
21

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method in this research, a theoretical framework for faster data- algorithm selection, does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy (https://neure) /otee//eeeeeaeeeeeeee///0025 for what should or should be described.
22

---

Appendix
Table of Contents
Code Repository
24
Key Challenges and Additional Related Work
24
Additional related work
24
B.2
Illustrations of key challenges
25
Additional Experiment
27
Additional Max-Cut Results
27
Additional Discussion of Clustering Results
................................
28
An adaptive subsampling scheme for algorithm ................................
28
D Additional Theoretical Discussion
30
D.I
Sample complexity bound for MCMC k-means++
30
D.2 Additional discussion of single linkage results from Section 2.2
30 ................................
Omitted Proofs
33
Omitted Proofs from Section
Omitted Proofs from Section
36
Omitted Proofs from Section 3.
42
Omitted Proofs from Section 3.2
49
23

---

A
Code Repository
We release our code for the experiments
https://ggiimbb.com/iingggi
Size- Gete-eeenrlliiiionn
B Key Challenges and Additional Related Work
In this section of the Appendix, expand the discussion from the introduction (Section [ We first elaborate on additional related work in the context of our paper. Then, we provide figures illustrating the key challenges we mention in Section [
B.1 Additional related work
Algorithm selection. Our work follows a line of research on algorithm selection. Practitioners typically utilize the following framework: (1) sample training set of many problem instances from their application domain, (2) compute the performance of several candidate algorithms on each sampled instance, and (3) select the algorithm with the best average performance across the training set. This approach has led to breakthroughs in many fields, including SAT-solving [84), combinatorial auctions [63]. and others (2 36 733. On the theoretical side, [52] analyzed this framework from a PAC-learning perspective and applied it to several problems, including knapsack and max- mux-indeependen-see This PAC-learning framework has since been extended to other problems (for example, see [9] and the references therein). In this paper, we focus on step (2) of this framework in the context of clustering and study: when can efficiently estimate the performance of candidate clustering al algorithm with respect to a ground truth?
Size generalization: gap between theory and practice. There is large body of research using machine learning techniques such as graph neural networks and reinforcement learning for combinatorial optimization [e.g..B5] 46 59 79]. Typically, training the learning algorithm on small combinatorial problems is significantly more efficient than training on large problems. Many of these papers assume that the combinatorial instances
coming from generating distribution [e.g.. 35 46 79). such as a specific distribution over graphs. Others employ heuristics to shrink large instances [c.g..[59). These approaches are not built on theoretical guarantees that ensure an algorithm's performance on the small instances is similar to its performance on the large instances. Our goal is to bridge this gap.
Subsampling for max-cut and general CSP Subsampling for the max-cut objective has been studied in 44 in terms of property testing, which is the study of making decisions on data with only access to part of the input [48). Property testing encompasses a more general category of study, and study in this work is specific variant of it.
the notion of size generalization
flourishing line of work since the 90s aims to develop PTAS that estimate the optimal objective value of constraint satisfaction problems (CSPs) [e.g.. D 43 long-standing area of sublinear-time approximation algorithms aim to approximate the objective value of max-cut and other CSP in sub-linear time. It dates back to 1998, when constant time approximation scheme that approximates the max-cut objective for dense graphs within an error of en² was developed 49.. Many later works follow [e.g..
44
64). In similar spirit, the
For example, Bhaskara et al. show that core-sets of size O(n--6) can approximate max-cut in graphs with an average degree of n². Despite having weaker approximation guarantees compared to the GW algorithm, these algorithms can have much faster runtimes.
The goal of size generalization, however, differs fundamentally from the goal of the polynomial or 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. That said, framework could naturally be used to compare these sampling based PTAS algorithms alongside greedy and Goemans- Williamson, efficiently determining when a PTAS's high computational cost is justified.
Perhaps most related to our work, Barak et 17 study similar subsampling procedure for general CSPs, which includes the GW SDP (both with and without the triangle inequality). For A-dense
24

---

CSPs, i.c. CSPs where every variable appears in at least A constraints, they bound the accuracy of the subsampled objective within c-error. In contrast [7]. our result focuses only on the GW SDP rather than general CSPs. Furthermore, we do not make any density assumptions for our GW SDP result, such as those made in 17 and in many other works related approximating max-cut values [e.g.. 43 75
Sublincar-time algorithms for clustering The large body of sublinear-time clustering research [e.g.. 41 67 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- to-head comparison with coresets is impossible further in lines 79-87.
Coresets for clustering
Coresets for clustering have been extremely well studied in the clustering
literature (e.g.. 33 42 54). Coresets designed allow efficient optimization of specific, known objective function, such as the k-means objective. Below, we provide a detailed explanation of why the
guarantee offered by coresets do not yield meaningful results in our setting.
For illustrative purposes, consider the k-means objective and suppose we are given large original dataset X' C R In the problem of coresets for k-means, the task is to construct a small (possibly weighted) subset X' C X (this set called the coreset) such that the k-means objective is well- preserved for any choice of k centroids C1,..,, That is:
h(e1,... Cxi h(C1, .., 2²) for any C1...n Ck C Rdd
where
h(C Cz. X')
Σ
min d(ci, x)
X
TEX
(x; =
min d(c, x).
|
ZEX
Such guarantee on X" would ensure that solving the k-means problem on X' yields an approximate solution to the k-means problem on X. Indeed, if |X' is sufficiently small relative to |.') then this approach yields an efficient approximate solution to the k-means problem on X.
However, notice that in the above description of coresets, the coreset X' is only guaranteed to approximate the solution to the k-means objective. On the other hand, the ground truth clustering may be completely arbitrary and may align poorly with the k-means objective. Consequently, the coreset guarantee does yield any approximation guarantee for the ground truth labeling of X.
Thus, the key difference between our work and the prior literature on coresets that coresets assume that the target objective is known, closed-fore objective function (such as the k-means objective function). On the other hand, our task is much harder: we want to design a small set X' such that running clustering algorithm on X' is enough to estimate the algorithm's 's accuracy with respect to an arbitrary ground-trult truth labeling X. Since the ground truth labeling not known a priori, traditional guarantees from the coresets literature do not apply.
B.2
Illustrations of key challenges
B.2.1 Key challenges of clustering
Figure 2 shows example of dataset where the performance of k-means++ is extremely sensitive to the deletion or inclusion of a single point. This illustrates that on worst-case datasets (e.g.. with outliers or highly influential points) with worst-case ground truth clusterings, we cannot expect that size generalization holds.
Similarly, Figure shows that on datasets without outliers, it may be possible to construct ground truth clusterings that are highly tailored to the performance of a particular clustering algorithm (such as Single Linkage) on the dataset. The figure illustrates that this type of adversarial ground truth clustering key challenge towards obtaining size generalization guarantees for clustering algorithms.
25

---

k-means++ after deleting outlier
k-means++ keeping outlier
20
20
15
10
10
5
0
-5
10
20
0
10
20
Figure Sensitivity of k-means++ with respect single point. The example shows that the algorithm's 's accuracy can be extremely sensitive to the presence or absence of a single point, in this case, the outlier at (20, 20). Depending on how the ground truth defined, deleting the outlier can either boost or drop the accuracy by up to 50%.
1+x
n-2
Figure 3: Example of a ground truth where size generalization by subsampling fails for single linkage. The shading indicates the ground truth. The first n points are unit distance apart, while the last two points are 1 + >> distance apart. Single linkage has O cost on the full dataset. After randomly deleting a single point, the largest gap between consecutive points equally likely to occur between any consecutive points. So, the expected cost on the subsample 2 1 n2-1 (n-I-d n=200 1/2.
2i=2
B.2.2 Key challenges of max-cut
Figure 4 shows example where the performance of Goemans- Williamson is sensitive to the deletion of even one node. The figure displays samples of GW values on the full Petersen graph and the Petersen graph with only one node deletion. As shown in the plot, single node deletion completely changes the distribution of GW outputs. This can also go the other way for different examples, where node deletion might cause worse performance with greater variance.
GW Gap Distribution for Petersen
1.00
GW Gap
0.90
0.80
Full
Delete node
Figure 4: Sensitivity of Goemans- Willlamssn (GW) with respect to the deletion of one node. GW gap GW(G) calculated by SDP(G) This figure illustrates the GW gap distribution the full Peterson network and Peterson network with one node deleted. Notice that the GW gap differs drastically when we delete node from a graph.
26

---

Solution
200
200
Ouigut Frequency
100
100
80
50
(a)
(b)
Figure 5: An example graph with different optimal SDP solutions leading different GW output distribution. Figure an example graph with many distinct SDP optimal solutions. By definition, they all have the same GW SDP objective value. Figure SueeeSbjia is the distribution of cut values returned by GW over two distinct optimal GW SDP solutions for graph in Sa with 200 random hyperplanes sampled for each solution. Two optimal solutions result in very distinet GW output distribution.
different SDP optimal solutions may have the same objective function values. However, their robustness to -agmmannillliasoon rounding could be very different. For example, consider the graph in Figure 5a The optimal cut in the graph is (0, 2, 4) and f1,3, 5). and the optimal cut value (assuming unweighted) is 9. However, if we solve the SDP relaxation on the same graph, both SDP solutions follows optimal:
As pointed out in Lemma 3.2
1.000
-0.784
1.000
-0.216
-0.216
-0.784
0.784
1.000
-0.784
-0.216
-0.216
1.000
1.000
-0.784
1.000
-0.216
-0.216
-0.784
X
-0.216
-0.216
-0.216
1.000
-0.137
-.226
-02216
-0.216
-0.216
-0.137
1.000
-0.216
-0.784
1.000
-0.784
-0.216
-0216
1.000
and
X
-1
Both have an optimal value In fact, any solution in the convex combination of the two solutions
(X]aX + (1 - x"*,, a E [0, 1]} would be an optimal SDP solution. However, those solutions have distinct performance on GW. For example, GW on X will return optimal rounding with probability the draw of the random hyperplane, whereas GW X will not be consistent, see Figure 5b)
C Additional Experiment
C.1 Additional Max-Cut Results
We showcase additional max-cut experimental results in Figure 6 where instead of plotting the subsampled GW cut density, we plot the subsampled SDP objective and 0.878 times the subsampled SDP objective. In all cases, the cut density from the Greedy algorithm on subsampled graphs converges to that of the full graph, aligning with our theoretical results. Moreover, the cut density returned by GW on the full graph lies between 0.878 SDP((G(S.) and y SDP(G(())) even for small subgraphs G[S.). Thus, by computing (G[)) and running Greedy on subgraph, we can infer that Greedy and GW yield similar cut densities these graphs.
27

---

Erdos-Reuyi
Barbell
Random Geometric
Internet AS
0.65
0.
0.06
Weight
0.00
0.03
0.64
0.2
0.63
010
Fraction of nodes subsampled
Greedy
subsampled Greedy
subsampled SDP and 0,878 SDP
Figure 6: The Greedy algorithm's accuracy on the sub subsample approaches that of the algorithm on the full instance. The subsampled SDP objective value and 0.878 of the subsampled SDP objective value provide a more and more accurate prediction of the GW cut density as the sample size grows.
In Table we demonstrate that even modest levels of subsampling substantially accelerate algorithm selection for the combinatorial problems under study. For example, on max-cut instances with n 500 nodes, we report average solve times (in seconds) across subsample fractions 0.2, 0.4, 0.6, 0.8, and 1.0. We find that (1) an 80% subsample reduces GW's runtime by over 60% (from 961 s to 370 s). (2) a 60% subsample achieves roughly a 90% reduction (to 72 s), and (3) even the relatively fast Greedy algorithm exhibits noticeable speedups.
Table Runtime (s) vs. Fraction of nodes sampled
Method
0.2
0.4
0.6
0.8
1.0
GW
0.5938
12.3565
72.2823 0.1575
370.3707
961.4030
Greedy
0.0187
0.0834
0.3231
0.5781
C.2 Additional Discussion of Clustering Results
In this section, we provide additional discussion of our main results.
C.2.1 Empirical performance of SoftmaxCenters
Surprisingly, our empirical results (Section 4) show that for several datasets, SoftmaxCenters achieves a lower objective value than Gonzalez's 's heuristic, even for 3 = O(1). Intuitively, this is because Gonzalez's 's heuristic is pessimistic: assumes that each step, the best way reduce the objective value is to put a center at the farthest point. In practice, a smoother heuristic may yield a lower objective value (a phenomenon also observed by Garcfa-Díaz al.
As discussed in Section 4 Figure 7 compares the k-centers objective value of Gonzalez's 's algorithm and our softmax k-centers algorithm (averaged over 10a repetitions) sampled instance. The objective value attained by softmax algorithm closely approximates or improves Gonzalez's s algorithm even for small values of B.. Figure Sacuure&@oom compares the k-centers objective value of Gonzalez's s algorithm softmax (averaged over 10" repetitions) as function of n for fixed 3 1 on randomly sampled GM, MNIST, and NC instances of n points. Even with fixed B, the objective value of softmax continues to closely track that of Gonzalez's 's algorithm as increases.
function of 33 for a randomly
C.3 An adaptive subsampling scheme for algorithm selection
We demonstrate that random uniform subsampling provides an empirically stable approach to algorithm selection, even without access the data-dependent quantities required by theoretical bounds. Instead of relying on these quantities, we propose an adaptive subsample algorithm selection substitute: the target algorithms randomly selected subsets of increasing sizes, compare their objective values or rankings across consecutive subset sizes, and terminate once the performance curve stabilizes.
To validate this approach, we conducted experiments on the Max-Cut problem across four graph families: random geometrie,
barbell, and Barabási-Albert graphs. For each instance,
28

---

I-Centers Objective Vallee
k-Centers Objective Value
3456
Gonzalez
4.855
Softmax
Softmax
3455
4.850
3454
4.845
3453
100
10a
4
10
10
10
Bota (log scolc)
Beto (log scale)
Omniglot
NC
k-Cenbers Objective Value
Gonzalez
k-Centers Objective Value
Gonzalez
Softmax
1.840
Softmax
31.96
1.835
31.94
1.830
31.92
1.825
10
10
10-2
10
100
10a
10
10
10
10
10a
10.
Beta (log scale)
Beta (log scale)
Figure 7: Objective value of softmax algorithm and of Gonzalez's algorithm vs. B. The plot shows 95% confidence intervals for the algorithms' k-centers objective values on randomly sampled in- stances. The softmax algorithm matches improves over the objective value achieved by Gonzalez's algorithm, even for small 8.
MNIST
V-Centers Objective Value
k-Centers Objective Value
Gonzalez Softmax
3400
3300
4.6
3200
4.4
3100
Gonzalez Softmax
4.2
3000
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
NC
k-Centers Objective Value
1.825
1.800
1.775
1.750
1.725
Gonzalez
Softmax
125
175
Figure 8: Objective of softmax algorithm and of Gonzalez's algorithm vs. n for 3 = 1. The plot
shows 95% confidence intervals for the algorithms' k-centers objective values randomly sampled instances of size n. The relative performance of softmax tracks the performance of Gonzalez's algorithm extremely well grows despite keeping the temperature fixed. (Omniglot omitted this figure because the instances are small.)
29

---

(a) SL clustering of full dataset
(b) SL clustering with one missing point
Figure 9: Figure 9a shows the SL clustering of X', with three clusters C₁, C22, and C3 (left to right).
In this example, (3)) n, as (C1 C2; C2; 6 and dmml dmm(C3; X) 5. There is a single point whose deletion dramatically changes the structure of the clustering in Figure 9b
we sampled subsets of 2, 4, ...... 64 nodes from total of 100, solved each using both the Greedy and Goemans- Williamson (GW) algorithms, and averaged the objective values over 10 trials. As Gremman--iiliamson
shown in Table 2 in all cases, the relative ranking between Greedy and GW stabilized with subsets of size between 8 and 16.
Table 2: Empirical results of an adaptive subsample algorithm selection method, showcasing the stability of uniform subsampling.
Graph type
Algorithm
0.02
0.04
0.08
0.16
0.32
0.64
Full
Greedy
1.0
3.6
15.5
61.8
244.2
972.7
2381.8
Random geometric
GW
1.0
3.6
15.2
60.0
239.6
997.3
2376.9
Best
both
both
Greedy
Greedy
Greedy
GW
Greedy
Greedy
0.0
1.0
4.0
8.4
40.9
104.6
323.1
Erdös-Rénn
GW
0.0
1.0
5.0
9.0
43.7
140.6
339.8
Best
both
both
GW
GW
GW
GW
GW
Greedy
0.4
2.1
7.1
29.6
126.3
511.5
1254.7
Barbell
GW
0.4
2.1
6.5
28.2
122.9
506.5
1249.5
Best
both
both
Greedy
Greedy
Greedy
Greedy
Greedy
Greedy
0.2
0.3
3.2
11.5
34.3
130.1
307.6
Barabási-Albert
GW
0.2
0.3
3.3
12.9
36.8
141.2
328.2
Best
both
both
GW
GW
GW
GW
GW
D Additional Theoretical Discussion
D.1 Sample complexity bound for MCMC k-means++
Here, for completeness, we state the value of kr.kmmeass++ derived
Theorem D.1 (Theorems 4 and 5 by Bachem et al. (7]). Let F be distribution over IR with expectation ğ E I and variance o² := d(z, 2 F(x)dx and support Atmostt-urell, bounded by an R-radius sphere. Suppose there is a d' -dimensional, r-radius sphere B such that d' > 2, F(B) > 0, and VI, y E B, F(x) < cF(y) for some 2 (i.e., F' is non-degenerate). For n sufficiently large, with high probability over X f", Ck.k-meansr+ (X)
R ka (1.///111/d)) /(e02 // F(B)r²)
D.2 Additional discussion of single linkage results from Section 2.2
In this section, we include additional discussion of single linkage results.
30

---

D.2.1 Interpretation of (k.SL
In this section, we describe why we interpret (X)) natural measure of the stability of SL on the dataset X' with respect random deletions. First, we emphasize that Çt.SL a property of how robust single linkage is on the dataset. is not measure of how accurately SL performs with respect to the ground truth and is defined completely independently the ground truth.
First, we bound the range of SaSSL.
Lemma D.2. Čk.SL E (0, nl.
Proof. Note that C₁, Cj Ct E C are clusters in the k-clustering of X' while C, C2 inter- sects two clusters (C₃ and C2) contained in the k-clustering of X. So, Lemma 2.6 ensures that jin dmm(() (C, U Cj: X) maX dmm 2) >
Suppose ( > a for some a (0, 1]. By rearranging the expression for ÇA.SL (X)), we see that min dmm (C;
max dmm (C;; X). That is, the distance threshold required for merging C2 U into a single cluster is not too large relative to the distance threshold required to merge Ct into single cluster. This is illustrated in Figure 9a with = I, = 2, and = When we subsample from A' to build Xm. there is some probability that we distort the min-max distance so that
> dmm (C; U Cy; X. causing SL( ke) to output a clustering that contains C, GU but does not contain Ct, as in Figure 9t this occurs, we cannot expect size generalization to hold. When is larger, the difference between dmm (Ct; and dmm U Cj; Xm.) is smaller, and thus there is higher probability dmm Cr; Xm,) > dmm (C, Cý. Xm). To control the probability of this bad event, we must take larger value of m in order to obtain size generalization with high probability.
We emphasize that Ç1.5L measures the stability of SL on X' with respect to point deletion, but it is ground truth (which is what
fundamentally unrelated to the cost of SL on X' with respect ultimately aim to approximate). Any assumption that Çk.SL is small relative to does not constitute any assumptions that SL achieves good accuracy on X. Theorem 2.7 states our main result for size generalization of single linkage clustering.
D.2.2 Tightness of single-linkage analysis
In this section, we show that our dependence on cluster size minse[s] |C:| and ÇR.SL st Theorem 2.7 is necessary. We also discuss further empirical analysis of ÇR,st.
Dependence on cluster size min,e[k] |C/]. Suppose our subsample entirely misses one of the clusters in C SL(X', ()). (i.e., Xm C, 0). Then SL(X k) will cluster X,, into & clusters, while SL(X k) partitions Xm, into at most k - clusters. Consequently, we can design ground truth on which clustering costs of and C' vary dramatically.
Lemma D.3. For any odd 110 and 7 0, there exists a 2-clustering instance on nodes with ground truth clustering G such that minje([] |C,] | 1, (x.sL(X)) & and with probability .27 for m = n 1, |cost. (SL(Xm,;2)) costg (SL(X, 2)) 2 1/4.
Dependence on ÇR.L.. The dependence on ÇR.51 (XX) is also necessary and naturally captures the instability of SL on given dataset X', as depicted in Figure 9 Lemma D.4 formalizes a sense in which the dependence the relative merge distance ratio &t.SL is unavoidable.
Lemma D.4. For any > 51 with
mod there exists 2-clustering instance X' points such that Čk.SL = n, SL(X' 2) satisfies mincec [C] 2 n. .23, costs (SL(X... 2)) cost. (SL(X' 2)) 2 1/12.
6 for m = n 1. with probability
Empirical study of ÇA.SL. We observe that for some natural distributions, such as when clusters are drawn from isotropic Gaussian mixture models, we can expect ÇR.SL to scale with the variance of the Gaussians. Intuitively, when the variance is smaller, the clusters will be more separated, so Çe.5L will be smaller.
'The worst-case scenario in Figure where small number of "bridge" points connect two sub-clusters has been noted as failure case for dingle-linkape style algorithms in previous work [e.g.. Section 3.1].
31

---

Plot {2. SL vs for a Gaussian mixture 2-clustering instance
22
Sz.
10
0.00
0.25
0.75
1.0
1.50
1.75
Figure 10: Ck,SL for isotropic Gaussian mixture model. The y-axis shows the average value of (2)) averaged over 30 draws X for given choice of a.
Plot {2. 5t vs for a Noisy Circles 2-clustering instance
22 SL
0.00
0.25
0.50
0.75
1.00
1.2
1.50
175
Noise Level
Figure 11: ÇR.5L vs a for noisy circle datasets. The y-axis shows the average value of (a,s(()) averaged over 30 draws of X for a given choice of a.
We ran experiments to visualize Sk,SL (X') versus appropriate notions noise the dataset for two natural toy data generators. First, we considered isotropic Gaussian mixture models in R2 consisting of two clusters centered at (-2, 2) and (2, 2) respectively with variance o²I I (Figure 10). Second, we considered 2-clustering instances drawn from scikitlearn's 's noisy circles dataset with a distance factor of 55 and [69 with various noise levels (Figure II. In both cases, = 300 points were drawn. Moreover, both cases, we see that, as expected, ÇR.SL grows with the noise in the datasets.
32

---

E Omitted Proofs
In Section we include proofs pertaining our analysis of center-based clustering methods ( and k-centers). In Section E.2 we include omitted proof' pertaining to our analysis of single linkage clustering. In Section E.3 and Section E.4 we include omitted proofs of our analysis
of the max-cut GW and greedy algorithms from Section 3.1 and Section 3.2
E.1 Omitted Proofs from Section 2.1
In this section, we provide omitted proofs relating clustering. Throughout this section, we denote the total variation (TV) distance between two (discrete) distributions p,q Ω [0, 1] is ||p ellrv := Ewes (p(w) q(w)]. If p(x, y) is the joint distribution of random variables X and Y, px (a) and py (y) denote the marginal distributions, and (xly) or Pr|x (ylz) denote the conditional distributions of X|Y or Y|X, respectively.
results k-centers and k-means++
First, we specify the pseudocode of Seeding algorithm, Algorithm 3
Input: Instance X Rd, k E Zzo. f: x P(X) R20 Set C }c] with 6j ~ Unif(X()
for i 2.
1 do
Select C; = y E X' with probability proportional to (dcenter (y: I)-1);
Set C = Ci-1 U {x}
Return: C*
Algorithm 3: Seeding(XX, k;
Let q be arbitrary, discrete joint distributions over random variables X and Y with conditionals and marginals denoted follows: px,yy (x, v) = px (xxxx and qx,y (z. y) qx (z) (v)xz.
If [pxx - qx rv I é and ||lVIX 9r1x TV S ez. then ||pxy xx. S 61 +
Proof. For any y we have |px,Y (z, v) ax.y (z, v)
(x,
px(x)) (1)x(11=) (x(x) ()/x(
Px(xx) (rix((|0)) - (xx(0))))) px(()) mx1(1
Px(x)) (prix(ul=) (xx(1)) (xx(x) px
S px((x) |1YIx()|=) (r1x + (xx(x) px
Hence,
|lxxY - Xx.x = 2
Σ
(x,r( -xx,(xx,,))
any
px (x( 1
Σ
2
1
lax(x)) - px(x)) (x1x)
2
$ 62 te.
Theorem 2.2. Let X C Rd, c,''> 0,5 E 1), and k. E Zzo- Define the sample complexity m ((),,(()) log(k/e) where (x) quantifies the sampling distribution's 's smoothness:
max (1 (x: 2); S(denttee (y: Q);x) (x, QCX:IQ/sk ZE
max
yEX
Let S and S' be the partitions of X induced by Seeding(2* k. f) and ApxSeeding(Xmma k. m. f) where Xmn a sample mk points drawn uniformly with replacement from X. For any ground-truth clustering G of X, EE costg (S') Re E [costg (S)). Moreover, given S', costg (S') can be estimated to additive error é' with probability - å using O(ke' log(8-1)) ground-truth queries.
33

---

Proof. Let p(C) be the probability of sampling set of & centers C' in (eeSeedding(Miin k. m. f) and (C) be the probability of sampling set of centers C' Seeding k. f). Likewise, let ) and p' (" be the probability of sampling G; the i-th center given C was selected up to the (i - 1)-th step ApxSeeding(Knit k m, f) and Seeding( (Xt ; k. f) respectively.
We have that
1 A
p (CC)
I n
1
p(c/((')), and pC())
II p² pc(c((-) n2 i=2
By Corollary of [27]. ApxSeeding (Algorithm I with m OOk,, log(k/c) is such that for all Ck-1 C X with [
Sk 1,
- -x(1---) 2 k-1
By chaining Fact iver 2.... k; it follows that ||p 1/1l/ll S Now, let (Zec) and p' (Z)c)) denote the probability of selecting centers Z (22,..., 24 having selected in the first iteration of Seeding and ApxSeeding respectively. Then,
iterations i 2, ..., k; conditioned on
(((()) - (z( - p' (Zlc))) & St p(Z r'((o) + ((x(Z(a)
- (aa)))-p'''Z (Z)(
Let 2 denote the set of all subsets of size k - 1 in X. In the following, for any set of centers 7 = 21...., 2, we will use costg (Z) to denote the cost of the clustering (Voronoi partition) induced by the centers Z. Using the fact that the proportion of mislabeled points is always between 0 and 1, we then have that
E ccost (S)l = Σ
Σ ZEX
costo (a1 ((Z(a)
GEE n
1 Σ
costg (a (Z))
Σ
Σ
costy (a (()
61EX 7
12
ZEXI-1
C1E ZEX4-1
E coost (S"))
+ n
Σ Σ
(((())) - (Z costs (S') + 1p --p''llv
GE ZEXt-1
E costo +c.
By a symmetric argument, we obtain lower bound
E coots (S)]
Σ
Σ
costg (cr U p(Zee)
CLEX
ZEX
costg (ar (Z)
Σ
Σ
costa (cI (2)) (Z((e))
CLEX
-
CEE -
E [costy (S')
Σ
1(((Z))) p/ (2lez)) > E costo (8') - ||p p'llrv
CIEX -
ccost (5')l
Next, compute èg (S") as follows. Let r X [k] be the mapping corresponding to the
ground truth clustering (i.e., T(x) = i and only if x E G:,) Let X" = (z1,.., 22) be a fresh random sample of é elements selected without replacement from X, and let
Eg(S") = min Σ ΣE(a dEEn vEXiVE(M
EIEE
Sot Ax E G.).
Consider any o Eg. Then,
1
Σ
1 ( E So A2
1 1 I Soo AI Ax4 &G).
E
Σ
i
xEX"
KE(
FE KE(M]
34

---

8 Hoeffding's inequality guarantees that with probability 8/k!,
1 3
7
Σ
Σ
1 1(2 Sato Ax Gi
R. Ti iejk
1 EE
1
San Ar
#EA VE[A]
for 1 = Okk loo((k- The theorem follows by union bound over all k! permutations a
Σg.
Theorem 2.3. Let Z20. 7 >> 0 and ó E (0, 1). Let SOPT be the partition of X induced by the optimal k-centers solution COPT, and suppose X' is (Je, (pa)-wellbbalaneee with respect to SOPT. Let
-1 8 8-1). With probability C' be the centers obtained by SoftmaxCenters with / = Ry log (k² pufle"
1- 6, max deenter (r; C) S maxzex deenter (x; COPT) + 7-
Proof. Let SOPT {S1, .... } be the optimal partition according to the k-centers objective and let OPT denote the optimal k-centers objective value. Let Sa(i) E SOPT be such that C2 E Sa(s) where G C, and let C C C' denote the centers chosen in the first - iterations of SoftmaxCenters. We use S2(3) E SOPT to denote the partition such that c₁ S.() where c C. We use s; E S; to denote the optimal centers, and use ((i-) C C' to denote the centers chosen in the first i iterations of SoftmaxCenters. We will show that for any i {2...., k 1}, either m, maxrex d(æ; C(i-1)) z 40PT + 7, or else with good probability, e; belongs to different partition Si(i) than any of C1, ..., C:1 (i.e., d(i) * (()) for any j < i).
To this end, suppose my > 4OPT y, then let == {ar x E Sug for some j < i]. For notational convenience, let 3 = - log (k2 pnlei 1) We have
Pfa B} Enen exp( d(x; C(-11))
ExEx exp( (xp(8'd(x; C(-
For every j E [k], we know that ej. St() E Se()) (each point goes the same partition its closest center.) By the triangle inequality, it follows that for any E S.())
d(z; ((i-l)) < d(x, 0q) + d(e,, 8.0)) 2OPT.
Consequently, using the fact that g(z) = 2/(2 + c) an increasing function of = for c O, we have
|B| (X
[o B
B (B)e(((28OPP) + Exex, exp( ((-1))
Now, let & E [k] be the index of the cluster in which By E S with
d(y; O(i:)()))) = m, > 4OPT + T. Such is guaranteed to exist, due the assumption that m4 4OPT + Now, for S, and j < i,
(4)
d(z;))) + d(x, v) d(y;e,) 40PT +7:
d(z, v) S 20PT,
and hence d(zz, o3) 2 20PT+7, Now, note that S;nB 0. because by the definition of B, whenever S, B # ( we must have S, n B S, and consequently d(y: C(i-1)) S d(y, e²) + d(c', swy)) s 2OPT (contradicting (4). So. it follows that
Pla E B
B eexp(22'0PT)) + Sy (p' + +7))
1+
S B
exp + 7) 20PT)
B
exp(-8'n) kyn,/ μe exp( S2
K'
Now, by union bounding over = ..., l we see that with probability at least - either m; S 40PT + y for some i [k); or, (ii) # (()) for any j < i.
In the former case, the approximation guarantee is satisfied. In the latter case, note that if every e; belongs to distinct optimal cluster S,()), then every x E S.m for some i E [b:]. Consequently, by the triangle inequality, we have that for any x E S.10)
d(x; C*) < d(x; c;) S d(x,)1()) d(c; s(()) S 20PT < 4OPT + +
35

---

Step 0
Step
Step 2
Full data
A
*
AAA
AAA
Consistent subsample
A
A
A
Inconsistent
subsample
AAA
A AAA
Ct
Y
Figure 12: Examples of subsamples which induce a consistent and inconsistent clustering. The figure shows an example dataset in one dimension along with the clustering obtained by SL(X' 2) and SL(Xm. 2) on two different subsamples. Observe that second subsample produces clustering because the set (1) has a nonempty intersection with both of the clusters from the full data and (2) gets merged into single cluster Step 4, before all points from C₁ have been merged together.
inconsistent
Theorem 2.4. For any B 0, Sr,SofemaxCentess (X) S exp(23).
Proof. For any Q, let op = argmax exp (3dcenter (x; Q)). Then, we can see that exp(Sdcenter (y: Q)/R) + (#x 2
Σ
(n 1) exp (zq;
Meanwhile, exp( (I Q)/R) S exp(23). Since h(x) = (n-i)+z and g(x) [2- 1)++a
80 are
increasing in x for a > 1, we find
exp exp(BdcenterlC (2; Q))
(..5oftmaxCentes(22)) :=
max QC ZE
max
Σ BEQ
(11; Q))
exp(2
S n
S exx((23).
(n - 1) + ex3(
Lemma E.1. For any exp(3R) there is clustering instance X' C [- R, R) of size such that St.SoftmaxCenters (X) exp(3)/2.
Proof. Consider X C [-R, R| such that 0ı R and 22, .... In = 0. By taking Q = {qı (x nexp(s)
..... Qk = 0}, that ÇA. SoftmaaaeCent (X) xx1+) 2[n-1) 2 exp(8)/2.
L
E.2
Omitted Proofs from Section 2.2
In Section E.2.1
we present omitted proofs pertaining to size generalization of single linkage. In present omitted proofs of our lower bounds.
Section E.2.2
E.2.1
Size generalization of single linkage clustering
In this section, we provide omitted proofs relating to our results on single linkage clustering. We show that under natural assumptions on X, running SL on yields similar accuracy as SL on uniform random subsample Xm of X' of size m (drawn with replacement) for sufficiently large.
36

---

We approach this analysis by showing that when m is sufficiently large, the order in which clusters are merged in SL(XX, k) and SL(Xm,,)) k) similar with high probability. Concretely, we show that for any subsets S, 7 C Xm. the order in which S and T are merged is similar when we run SL(X, k) and (L k). We use d (respectively dm:)) to denote the merge distance iteration i when running SL(X, k) (respectively SL(Xm: k)). Similarly, C* (respectively C denotes the clustering at iteration L. We use 9m(S) to denote the first iteration at which all points in are merged into a common cluster (we refer to this as the merge index of S). That is, 9m. P(( + In 1] is mapping such that for any S C Xm, 9m (m) = t, where is the first iteration SL(Xm; k) such that C for some C' E Cmn Correspondingly,
dg(s) and dm...(s) denote the merge distance of S C X when running SL on X' and Xm respectively. Table summarizes the notation used in our analysis.
Notation
Informal Description
Formal Definition
g(S)
The first iteration of the outer loop in SL k) which all points in S are merged into a single cluster.
For S C X, g(S) = min{é E 2z0 3C C C such that S C CC when running SL(X,, k).
Im (S)
The first iteration of the outer loop in SL(Xm, k) at which all points in S are merged into a single cluster.
For S C. Xms (m(() minfe E Zz0 3C c Ce such that S C C} when running SL k))
de
The merge distance at iteration é of the outer loop in ,L(X'k))
max.,j , min sec!t-1) wEOft- d(r,y). running ().
when
dmp
The merge distance at iteration é of the outer loop in SL(X,, k)
mitkijj max sec((-1) running SL(XX k).
-eof weOft-n d(r,y). when
Table Single linkage clustering analysis notation. The table summarizes key notation used in our analysis of single linkage clustering
We first prove Lemma 2.6 which characterizes when two points will be merged into a common cluster in single linkage clustering.
Lemma E.2. In SL(X k), x, y E X' belong to the same cluster after iteration È if and only if dmm (1r, yr x) < de.
Proof. For the forward direction, we will induct on the size of the cluster C. In the base case, if C 2, C must be the result of merging some two clusters A = {2t}, B {I) } such that d(A, B) = d(z,,,,) S d, I de at some itcration t I l. Therefore, dmm (Z,, 2zj X) I d(z;,,z)) S de-
Now, assume that the statement holds whenever |C| < m. Then |C| must be the result of merging some two clusters A, B such that |A| < 1, [ < m 1, and d(A, B) < de < dy for some iteration ł I L. Let a; A and x, E B be two arbitrary points. Since d(A, B) S de, there exist E A, E B such that d(u,v)
de. By inductive hypothesis, dmm 6mm, u; X) < de S de and dmm (I 0; X²) < d, S de. Consequently, there exist paths p1 E PPr.uuP2 P2 E Paj,e such that Pi U (u, v) U P2 is a path between x; and zy with maximum distance between successive nodes at most de. Therefore, dmm dmm(1:; T.; X²) & de.
For the reverse direction, it is easy see that after the merging step in iteration k all nodes u, such that d(u, v) < da must be in the same cluster. Consequently, if dmm (Ii, æzz < dg, there
exists path p E P.ù where p (vi I, U2,..., Uk, Uk+1 Irÿ) with d(v 1, U2) < dj for all i E [k]. Consequently, all vertices on p must be in the same cluster, and hence Iy TG E C for some C' E Ck.
The analogous statement clearly holds for X'm as well, formalized by the following corollary.
Corollary E.3. Under SL(Xm= k)), Z, y Xm are in the same cluster after the E-th round of the outer while loop if and only if dmm (x, yi X S dmm..
Proof. We repeat the identical argument used in Lemma 2.6 on Xm-
37

---

Lemma Corollary E.3 E.3 characterize the criteria under which points in A' or Xm will be merged together in single linkage clustering. We can use these characterizations to obtain the following corollary, which relates dg(s)) and dm,(s) (see Table 33 to (S: and dmm (S; (m;Km) respectively (recall Definition (.5).
Corollary E.4. For any clustering instance X and set S C X. dg(s) max dmm (mmm(::))) (S; Likewise, for any S Xm, dm...(8) dmm (S; X.).
Proof. By definition, we know that on round (S), two sets A and B were merged where S S AUB but Z A and S I B. Moreover, dg(s) = mm d(r, y). We claim that for any z E SnA and y E S B, dmm y: X) 2 dg(s)- For a contradiction, suppose there exists 2 E S and Y SSS n B such that dmm (Ir, y; 2) < dg(s)- Then there exists path p between and y such that for all elements Us, Vi+1 on that path, d(vs, U++1) < dg(s)). However, this path must include elements We, 1 such that E A and 1++1 E B, which contradicts the fact that dgts) min B d(xr, v). Conversely, by Lemma 2.6 we know that for all I, E S, dmm [z, y X') S dg(s). Therefore, dr(s= = maxg,yes dmm({ (I, y; X The second statement follows by identical argument on Xm.. C
Our next step to use Corollary E.4 to understand when the clustering C SL(X, k) and C' SL(Xm. k) are "significantly" different. Concretely, our goal is to provide sufficient guarantees to ensure that C and C' are consistent with each other on Xy, i... that Bo Σn such that for each cluster C² E C², Of c Cot.). To aid in visualization, Figure 12 provides an example of a subsample Nm, which induces a consistent clustering and an example of a subsample Xm, which induces an inconsistent clustering.
Now, suppose, for example, that C' is not consistent with C and let Ct C be the last cluster from to be merged into a single cluster when running single linkage on the subsample X... Since C' and C are not consistent, there must be some cluster Y C' which contains points from both of two other clusters. This means that when running SL(X,, k)), dait) > dy(c) for all C E C. However, recall that since Y E C', when running SL(Xm. k), there must exist some C. E such that dmaan.y < d. Since dy(y)= > dg(C,) but dmaa.. < "mm.n(c.)" this means that when subsampling from X' points, the subsample Xm must have distorted the min-max distances restricted to C, and Y. The following Lemma E.5 formalizes this observation.
Lemma E.5. Suppose T is merged into a single cluster under SL(Xm. k) before S is merged into single cluster (i.e., Gm
(m( (S) > 9m (T)). Then there exists pair of points u, E S such that
dmm (u, v, Xm)) - dmm u, v; x)= 2 dg(r) dg(s).
Proof. First, we argue that if g(S) 2 9(T), then the statement is trivial. Indeed, if g(S) 2 g(T), then for any u, U E X, dmm (u, 0; Xm) dmm (u, v; X) 2 0 2 dg(T) - dg(s). The first inequality is because any path in Xm clearly exists in X, and the second inequality is because de is non-decreasing in f.
On the other hand, if g(S) < 9(T,, then Corollary E.4 indicates that
max 2.ES
dmm (z. y, X' dg(s) < dair
max dmm (1r, y; X). z.ETT
Meanwhile, since gm (S) > 9m (T), there exists pair of nodes u, S such that
dmm (u, v; Xm) = max dmm (I. Xm, 2
max dmm (z, yj Xm) 2 max dmm (Ir, y: X² = dg(T)- 2
NNeT
Finally, because u, U. E S, Corollary E.4 guarantees that dmm (u, vu, S do(s), we can conclude that dmm (u, U; Xmm) dmm (u, u; X) dg(T)
dg(s).
Lemma E.5 illustrates that the order in which sets in Xm, are merged in SL(X)) and SL(X..) can differ only if some min-may max distance is sufficiently distorted when points in X' were deleted to construct Xm. In the remainder of the analysis, we essentially seek to show that large distortions in min-max distance are unlikely because they require deleting many consecutive points along path. To this end, we first prove an auxiliary lemma, which bounds the probability of deleting & points when drawing a uniform subsample of size with replacement from n points.
38

---

Lemma E.6. Let S be set of n points and S' be random subsample of m points from S, drawn without replacement. Let (ti....tte te} Then,
ml (- (-
ml n
< P(TNS' =0} S exp
exp
Proof. Each sample, independently, does contain for i [6] with probability - L/n. Thus,
6 m
IP I = =0
For the upper bound, we use the property that (1 I m2/m)"" m S exp( -z))
(1-1)- (1 mL/n
m
ml
exp
m
n
Meanwhile, for the lower bound, we use the property that 1eppp-1/(11
- x)) < 1
for x E [0, 1]:
[ (1ー
-
(mm f/n
-mh
exp
8/m
exp
n1
We can utilize the bound in Lemma E.6 to bound the probability of distorting the min-max distance between a pair points by more than an additive factor 7).
Lemma E.7. For 1j > 0 and S X,
P (3u, E Xm ns: dmm(u, U; Nmm) dmm (u, U; x) 11} S exp
exp (-m(n//dos))
Proof. Suppose 3u, v E Xm S such that dmm (u, v; Xm,) - dm (u, U; X) > 17. Then, 3p (u P1, P1.P2..... .... Pt = v) E Pu.v.x P., with cost max; d(p: P;-1) ) = dmm u, X; Since S n and u E S, deleting any node E p can increase the cost of this path by at most dg(s)- Consequently, Xm must have deleted at least s = [n/dg(s] consecutive points along There are at most n distinct sets consecutive points in p. Let E, be the event that Z1, I, & Xm. Then, by Lemma E.6
(- ms
P [x1,.... Vg $ Xm S exp
n
The statement now follows by union bound over the distinct sets of consecutive points in p and over the at most n² pairs of points E S.
Finally, we can apply Lemma E.5 and Lemma inconsistent.
E.7 bound the probability that C' and C are
Lemma E.8. Let C [Ci,..., C.) = SL(X k) and C' = (Ch,..., C.) = SL(XM, k). Let ar = d(g(C,uC;)) and a; dg(C.). Let E be the event that there exists C₁2 such that C/2 of Cj all j E [k] (i.e., that C' is inconsistent with C; see Figure 12 Then,
P ({E} < (kn)3 exp
m
nC
Proof. Let S; = Nem for f E [k]. Without loss of generality, we can assume that i = 1. So, let Eaby be the event that C4 C. + 0 o C₁ C2 and
Im (C)) gm (S,), and g(5)) < <g()))
By Lemma E.5 this implics that there exists a u, U E Sy such that
dmm (u, v; Xm, dmm (u, 0; X) 2 dg(c;) dg(S,)-
Since C., Co C. know that g(C)) g(C1 C2). Meanwhile, g(S,) aj, so have dmm (u, v; Xm)) dmm (u, 0; X²) 2 aab - Oj.
39

---

By Lemma E.7 it follows that
PP (Fabbst S n
max exp
(Gab a3))
1) )
(kn) 3
exp
m
a.b.j(kk]
n
aj
nCCk.LL
Now, E = Va.. Ba..... By union bound over the at most he configurations of a, b, the lemma follows.
Finally, we can condition on the event that C and C' are consistent to obtain our main result.
Theorem 2.7. Let G = [G1,.... G be ground-truth clustering of X, C = {Ci,... Ckk = SL k) be the clustering obtained from the full dataset, and C' = (C' C²,}3 SL(Xms k) be the clustering obtained from random subsample Xm of size m. For
m = (6((
min4e[k] |C,] + (2.)L())) log A 7)
n
6 +
we have that IP {coste (C") ~. cost. (c)) 2 1-6 Computing C' requires O(m²) calls to the distance oracle, while computing costg (C") requires only mn queries the ground-truth oracle.
Proof. Let F be as defined in Lemma E.8 and let F be the event that X n C. = 0 for some i E X.
Let H E V F. P (H) S P (F) P [F) where, by Lemma R.6
m
(e) [Ca]
P < l max PP px = 0} S exxp
And by Lemma E.8 we have that
P P & (nk)² exp
CR.SL
We also have that
P (coste (C") Re costs (C)} 2 IP (ootto (C') Re, costs (C)
Now, let X' + [k]] be the mapping such that ((x) i if and only if x G,, Consider any permutation a : [R] + [k). If H occurs, then we know that every C² C Cj for some ji E [k]. and we know that each Cj n Km * 0 for each j [k]. Consequently, there exists permutation p: [k] + [k] such that C₁ C Cp(s)- Without loss of generality, we can assume that p is the identity, i.e., that E C. > I C₁ for any x E Xm. (or else reorder the sets in C such that this holds). So, conditioning on H, we have
1 Σ Σ
CI A2 = 1 ΣΣ
1
xE C2t A GAAZEN 2m) 1
ZEX KEj
#EX sE[A]
Σ
1(x Coca Ax Aa
m
xE sE(k)
E 1 m7 xEXm sE(R]
I A
1 Σ Σ
E
1(EECaAA Xm)
ZEX iE[M]
1 m
E [
REX jE]k]
So. by Hoeffding's 's inequality and union bound over the permutations
f/cost. (C') - costg (C) S < } 2 (I:!) exp 2-22m) 2 1 - R*t exp (-2e2m).
Consequently, by taking m O (ke 2 log 1k)- we can ensure that
P (costo (C') Re costo (C)lH} 2 1 6/2. n
By taking m 2 0 max (()) log (nkd-1),
log (8 (6-1)) we can also ensure
min]e(e]]
[ > 1 6/2. Hence, P {costo (C') ~ costo (C)} > 1-6. 6.
40

---

E.2.2 Lower bounds for size generalization of single linkage clustering
We now turn our attention to proving the lower bound results in Section 2.2 In the following, we use the notation (x)=) := {z E R 2| 2|l, I <} to denote an c-ball centered at 2 and consider clustering with respect to the standard Euclidean metric d(x, v) := || y112-
Lemma E.9, For any odd n 2 110 and y > 0, there exists a 2-clustering instance on n nodes with a ground truth clustering G such that min;e[K] |C,| = 1, <4.5L S and with probability .27 for m n 1, |costo (SL(Xm;))) 2)) costs (SL(X' 2)) 2 1/4.
Proof. Consider 0 < 1/2 and the 2-clustering instance X' = { 1.1..... In- InJ I2 where I1, .1,,..., 1)/2 E (0), Ixx- (xx-1)/(x200 1)--))>-/ In-1 E (3), and In = 6. Suppose g = {G1, G2) where G = [T1...,;nnnl], and G2 = {.n).
It is easy to see that costg (SL( = O, since is sufficiently far from 0 and 3 to ensure that In will be the last point be merged with any other point. Consider m n 1. Whenever In & Xm. Imm n B, (0) 2 n/4, and (m n (3)) 2 n/4 we have that costg (SL(Xm)) 2 1/4, as the algorithm will separate the points Ba (0) from those (3). We can lower bound the probability of this event as follows.
By Lemma E.6
P fan E 2m S 100--y33 exp( -1) S 0.63.
By a Chernoff bound,
E{12 (1Ba(3) Xmal S n1
= { (B)(0) n Xml -
P
4
4
(n
1)²
2n²
[Ba n Km/
2n
4(n - 1)
(n - 1)3
$
[B)(0) n nx 1
2/3
2n
(n - -))
S exp
S .05.
36n
Thus, P [costs (SL(X))) 2 1/4) 2 1 0.73 = .27. Moreover, note that because the failure
probabilities analyzed above are independent of a, we can ensure that Çk.SL S 7 without affecting any of the failure probabilities, which are independent.
Lemma E. For any n 2 51 with n 1 mod 3, there exists a 2-clustering instance X on n points such that CR.SL n; C = SL(XX 2) satisfies mincec [C] 2 8; and for m - 1, with probubility .233 ccost (SL(Xm, 2)) cost, (SL 2)) 1/12.
R. where the left points x E L satisfy x 0. The middle points x M satisfy x 2o, and the right points x E R satisfy æ 2-a + B. |[| = |M| [ n The "bridge" point a. Here,
Proof. Take a > 0 and 2a > B > a. Suppose X' is composed of four sets X' = LU
3.
C. (X) n (=((3 a)
n.
Suppose the ground truth clustering 9 is defined as G1 = (bb and G2 = R. Since 8 > a, single linkage achieves a cost of 0 on X. Mcanwhile, suppose that b & X Then, because the minmax distance between any point in L and M is now 2n > 3, single linkage run on X,, will create one cluster for I, and one cluster for M U R. Provided that X,, contains at least --1 points in M, this implies that single linkage will have a cost greater than or equal to 1/12 on Xm. now remains to bound the probability of these simultaneous events. Let E1 be the event that b & Xm, and let Es be the event that [M n Xm
> 2-1 -- We have
P A E2) = (EE))
> ((E))
This is because E₁ is the event of not including certain elements in Xm and Eg is the probability of including certain elements in Xm, so, P ((E Ei] 2 IP [Ez). Now, consider m = 1. By Lemma E.6
1 ) = exp(-1) 2 .36. (n (-m(n
IP (E1) 2 exp
-m
1)
41

---

Input: X is feasible matrix for 2 Initialize u E R,, sampled from the n n-dimennsonal standard Gaussian distribution
Compute VVT = X
// Compute the Cholesky factorization of X
for {1, 2, .... n do
= sign( (f u), where v; is the i-th column of matrix V
return Zu
Algorithm 4: Rounding Procedure GWRound(XX)
Meanwhile, to analyze P {E2] we can use Chemoff bound to see that whenever n we have >> m > 2/3n, and consequently,
πt
P(E) = 1- P
Xm nM <
6
= 1 - P
Xm 0 nM| <
n
m7
(n 1)
2m
3n
2m 12
m(n 1)
= 1 - P
Am M <
2m
3n
(2m n
m
2 1 - exp
2(2m) )2
6
(n 2)²
(12
1 exp
8(n 1)²
(n 2)²
1 exp
48(n 1)
where, in the fourth line, we substituted m - > m m that the argument in the exponential least Hence,
Then, whenever n 2 51, we have
6
IP [ A E2) exp(-1) (1 exp(-1)) -23.
So, the lemma follows by a union bound.
E.3 Omitted Proofs from Section 3.1
This section provides omitted proofs relating to results and discussions on the GW algorithm.
The following lemma shows that GW SDP attains strong duality, included here for completeness. Lemma E.11. The GW SDP relaxation of the max-cut problem (Equation (2) and its dual problem (Equation 3) attain strong duality.
Proof. Notice that any PSD matrix X E R with 1 the diagonal is feasible Equation (2) Thus, we can find at least two distinct feasible solutions to Equation (2). Any convex combination of the is solution in the non-empty interior of the primal.
To find a feasible solution of the dual, notice that we can always choose y = 2 E, wiy + where
0 to make the matrix S Σn (ete7) T)
y/- L diagonally dominant matrix as shown below:
S 2 Σ Wis + Σ wij Σ Wi.j + + + 5 Σ |
Any diagonally dominant matrix is PSD. We choose distinct X and A2 to construct feasible y1 and yo- Any convex combination of yı and y2 is solution in the non-empty interior of the dual problem. Because both primal and dual problems are feasible and have interiors, by Slater's 's condition, strong duality holds.
42

---

Lemma E.12. Suppose we have graph G = E, w) Let C CV. Let y" be the optimal solution the dual problem ) induced by G. Let yi Vi EkEViS Wik. Then y is feasible solution to the dual problem induced by G[St].
Proof. Let the set of node V in G' be indexed with St as its first t elements. The optimal objective value of SDP does not depend on the node indexing, nor does the dual objective value (by strong duality).
Let y² be the optimal dual solution. satisfies the following dual constraint:
a Σ (e,e,") vi -12 LG 0.
1
where e; E R" denotes the all-zero vector with index i. Therefore, e,e; is the all-zero matrix with on the (i. index. In other words, Σi=1 (e:e;") ) y is the diagonalization of the vector y".
Let LG denote the t-th principle minor of Lg. ie. the upper left t-by-t sub-matrix of LG. To
distinguish between e; RR. and es IR", for the rest of the proof, use Cn,i to denote the the former n--imensiinal vector and Ct,i to denote the latter 1-dimensional vector. By Sylvester's criterion, because Σ (e, 3) y Let Lais.) denote the Laplacian of G[S,]. We thus have:
Lo 2 O, we have that Ei= (et,aet,i ") ot 1 L 2 0.
t Σ (ec,ter vs 1 Lass
1 (Li- LG(s)) 0.
By the definition of Laplacian matrices, Lg and La(s.) are both t-by-t matrices with the same off-diagona values, as shown below:
ELev v Wsk
Wij
Eres.
wi
Wij
Lig
and
LG(S.)
Way
Wij
Moreover, (I's - Lais.) is diagonal matrix with (i, i)th element Σvev Wik - Ekee, Wik ENEV'S, Wak
Thus, we have
Σ (er,eet,s)) vi
1 Laisa 1 Losss)) 2
e,, ") 33 LLais11 -
Σ (er,ee,,i 7)
1
Σ
Wisk 2 0
1=1
LEViS.
(e, ")
Σ
Lais)) 2
Wikk
4
REV
Let ūi - - (s Wik. We have just shown that ÿ satisfies the constraint of the GW SDP dual problem induced by G[S.). It is therefore feasible solution to the GW SDP dual problem induced by G[S.].
Lemma E.13. Given G = EV, w). let be a set of vertices with each node sampled from V
independently with probability 4. The expected value oSP (SDP(GG(S)) can be upper-bounded by:
E|SDP(G[SA)] L SDP(G) 1n1 - 1) W
S,
n² 2
with W EcEE We, i.e. the sum of all edge weights in G.
43

---

Proof. From Lemma E.12 we know that y is feasible SDP dual solution induced by G[S,]. Let ÿ be the optimal solution to Equation 3 Then, we have that for any Sy
SDP(G[S.)
EE> Th-
iE iES.
Taking the expectation over the random sample St on both sides, have:
B[SDP(G[s.)] =
B
Vi
Σ
Wile
iES.
REVIS.
Σ SEV
Lii E Si}
Σ
Winh
4
kEViS
Σ LEV
EiE S.)u
1( S
Σ
Wikk
IEV
REVi8
Because each node in St sampled independently with probability t/m, the probability that St, & & S₁ is the product of probability that E S, and k & Sc, i.e. ((-1)) We use this fact to finish
upper bounding s, (S))()
1kk S.) )]
E[(DP(G[S.)]
<
Σ
Pii S.lvt
E
Σ
1ii SOT
Σ KEV
LiEV
Σ v
ΣΣ
Pli St, k & Silwar
n
iEV
iEV l(n
KEV
W
SDP(G)
n
n² 2
with W = -. We, iee the sum of all edge weights in G.
Lemma E.14. Given G = (V, E, w), let Sy be a set of vertices with each node sampled from V independently with probability t. The expected value of SDP(((S)) can be lower-bounded by:
t²
E|SDP(G(SD)] S,
2 SDP(G).
n2
Proof. Let the set of node V in G' be indexed with S, as its first t elements. The optimal objective value of SDP does depend on the node indexing. Let X E m=ax denote the optimal solution for SDP induced by G and X RlS. x (S.) denote the optimal solution for SDP induced by G Let X5, denote the [S, |-th principle minor of X*. By the Slater's condition, X3, is PSD. It is therefore feasible solution to the GW SDP induced by G[S:]:
[[SDP(G[(.)]
E [LGss) Xs.] Z ELGSS) X3,]. 5;
5
We re-write the objective value in terms of the Cholesky decomposition of X", which we denote by of for all V. Note that X w. oTTo": m7: 2
(DPP()(). S,
T [Laas. x S.
W1y(1 vz7 o;T03)) 07))
E
ijeS.
F S.
Σ
1(ee E Se,j E Se)wiy(1 vz vzT
(iJ)EE
44

---

By independence of the sampling of nodes and j. we have:
1
||SDP(G|S.]] 2
Σ Pli E S., E S1
- 00, 02)1
5,
(1,))EB
Pli E S.j E S.JDDP(G) 12 SDP(G).
-DP(())
n
Theorem 3.1. Given G = (V. E, w), let St be set of vertices with each node sampled from V independenlyy with probability 5. Let W ((d)EE Wai- Then
1 B/SDP(G[S.)
1 SDP(G)
n n- 1 &
W (SDP(G)- n²t
-22
12 S.
n²
Proof. Combining Lemma E.13 and Lemma E.14 and basic algebraic manipulation gives us this result.
Theorem gives us size generalization bound in expectation over the draw of S.. We are also interested in whether is possible to attain bound with probability over one draw of S.. do so, we first introduce the McDiarmid's Inequality.
Theorem E.15 (McDiarmid's Inequality). Let f X1 X X2 X Xu R satisfy:
sup (I f (21, T.)] S c.
</Exi
Then consider independent r.. X1, X2,.,, where X₃ E firor all i. For e 0,
26a Σ o
Pllf(1, .... X.,) E[f(XI,.... X.)) 2 2cxp
We wish to apply McDiarmid's inequality to provide high probability bound for how different SDP(G(())) can be from [[SDP(G(S.)) In order to do so, we consider SDP(.) as a function of list of indicator variables, say .1.---, Un [0, 1)", indicating whether node is in subsample S, We need a result that bound the maximum change in objective value we add a node & S; to S, or delete node j E S, from S.. The following lemma states that this maximum change in objective can at most be the degree of the node added or deleted.
Lemma E.16. Suppose we have a graph = (V, E) with [V]. Let S S V be subset of nodes and k E S. Let S' = S {k.. Then,
SDP(G[S)) SDP(G[ST) - deg(k).
By symmetric argument, let k E V and k & S. Let S' = S + {k). Then we also have
SDP(G[S)) SDP(G < deg(k).
Proof. Note that by a symmetric argument, the change in the SDP objective value after adding a node is the same as the change in the SDP objective value after deleting node (those are the same argument with the definition of S and S flipped). Thus, it is sufficient to prove the first part of the statement assuming S has node and S' does not.
We first show that SDP(G(()) 2 SDP(G(S')) GW SDP is permutation invariant, so suppose is indexed last in the set of nodes S. Let t (S]. Let X gtxt be the optimal SDP solution induced by G[S) and X' E (((1))x(I--) the optimal solution induced by G[S"). Padding X' with on X,, and off-diagonal on the 1-th dimension results in a feasible solution for GW SDP induced by G[S], because a block-diagonal matrix in which each block is PSD is also PSD (by Cramer's
45

---

rule). Therefore, we know that adding node will only increase the objective value of SDP, i.c. SDP(G[S)) 2 SDP(G(ST). Thus,
-
- SDD(GI(SS) -SDP(G[S) - -DP(()("))
We notice that the (t- 1)-h principal minor of X is feasible solution to the GW SDP problem induced by G[S*] (because it is PSD and has on the diagonal), Because X is the optimal solution the GW SDP objective induced by G[S*)
SDP(G[S") = Σ
1 2
(1
(1-2)))
Σ
1 Waj (1 xzz).
2
2
(g
(K,))
Applying those facts, show that [SDP(G[S) SDP(G[S")) -SDP(G[S)) - -DDP(G(S))
Σ
wis (1 - -21)) - Σ
w (1 x'yz)
2
(iJ)EEs
(g)))Eg/
Σ
2 Wi xxi)) Σ
Wii (1 Iij).
2
(1J)
(g.))
Let Es be the set of edges in G[S] and Es be the set of edges in G[S"). Because the set S contains all nodes in except for the node k, we know that the edge set Eg contains all edges Es V}. thus split the sum over Es two parts, Eg and the set k(i,k) E Es Eg::EE: :VE
except {(i, k) E Es
SDP(G(S)) SDP(G
Σ (kJ)
1 -1-11-0 xx1) +
Σ
1
w/ (1 2zhh
2
2
(
Σ
Wij (1 - -xis)
2
(i.))
Σ
Wil (1 Kikk
2
(s
Σ
Wi
deg(k).
(i.))E
With Lemma E. and Lemma 3.1 we can put together a size generalization result for SDP with probability over the draw of S..
Theorem E.17. Given G (V, E), let St be set of vertices with each node sampled from V independently with probability 4. With probability 8 over the draw of St.
1 SDP(G) n2
1 SDP(G(()))
n-t (SDP(C) <
[2]
n3
log
n²t
V
Proof. By McDiarmid's Inequality, we have that
2c2
P[|SDP(G[S.) -E|SP(G((]]]]] 2 2 2xxp
Σ
(
We upper bound the sum of weighted degrees over all nodes by
46

---

7
deg(i)²
(n 1) deg(()
(n 1)
Thus, we can also rewrite the upper bound as
c²
P[[SDP(G[S.) E[SDP(G(S.) 2 S exxp
('n 1)
We now combine this and the expectation bound for SDP size generalization: with probability
1 2 exp
Bi(a
SDP(G) -
1 SDP(C(ss))
SDP(G)
1
B|SDP(G[S.)]
n22
n2
12
1
1
+
R[SDP(G[([]]
SDP(([(s))
f2
(SDP(G) W) +
net
We set
2²
5 = 2exp
(n - 1)1 E
(8)
+ log
2 = (n E)
2
S (n 1) log 2 8
# 2 = (n E) log
Thus, with probability 1 1-66 8,
SDP SDP()
1
n-1 1 (SDP(G) W) + 6 n²t
n
(SDP(G) W) + 3322 log 22
n²t
n t
(SDP(G) W) + 3/2 n2t
log
12
Below, we generalize Theorem E.17 to apply weighted graphs.
Theorem E.18. Given G = (V, F, w), let S, be set of vertices with each node sampled from V independently with probability &. Let W EesE we- With probability 8 over the draw of S.,
1 SDP(G) t2 SDP(G[())) 2
n - <
(SDP(G)
E
W
+
log
n²t
2
22
Proof. We modify the previous proof slightly to get this result. In the weighted version, we upper bound the sum the weighted degrees squared by
deg(1)² < max deg(i) Σ deg(i) = deg(i) < W
This is tight because we can imagine allocating all edge weights to the neighboring edges of just one node.
The rest of the calculation follows that in the proof of Theorem E.17
47

---

Lemma E.19. For any 2 2. there exists a graph Gn on vertices with distinct optimal so- lutions X, & Y, Equation
( and a constant C 0 such that LG. Xn LG. Yn, but B/ (GWRound (X,)) E B. (GWRound(Y.))) Cn.
Proof. Let Gn with n = (2. 4, 6,8, .... be unweighted complete graphs with n vertices. Let Xn Rax be n X n. matrix with on the diagonal and
n-1 off the diagonal. Let
Yn
-1 -1 ... Buxn
We start by verifying that both X, and y, are optimal solutions through finding their dual optimal certificates that satisfy the KKT condition. Let Z [n/4, ..., n/4/² R" We check that this is valid dual certificate for KKT condition:
Dual feasibility: diagz, Lo. is the all matrix in Rox", therefore also PSD, satisfying dual feasibility.
Same objective value: Σie(n) Zei = n² LG Xn.
Complementary slackness: Tr (ídiagz, LG, lx,) = 0.
Primal feasibility: X, is PSD and has on the diagonal.
Therefore, have valid dual certificate for the optimality of X,, ,, is the optimal solution for GW SDP induced by G.-
We check the same thing for Y,, Let By [n/4, ..... n/4/T E R". Notice that since we are using the same dual certificate, we do not need to check for dual feasibility anymore. Because LG.. Xn, LG., Yn, we also won't need to check that the objective values match. We only check that:
Complementary slackness: Tr ([diagz, LG,! (x) Eiev Zyo n(n 1) +1 2(n/2)(n/2 1) (-1) (n/2)² 0.
Primal feasibility: Y, is PSD and has all on the diagonal.
Hence, Y, is also optimal.
However, we see that the expected value of GW using those two solutions differ by gap that does not close oo:
E[GW(())) E E.G((X))
Σ arccos(Y, aarcoss (X,)
π
1
n(n
Arrcoo(-11
arccos
π
2
2
2
T2 -
n²
nnn
arccos
4
2x
as - 0c
4m
Hence, choose C x-2 1x we have proven the statement.
Theorem 3.3. Given G (V, E, w), , let S, be set of vertices with each node sampled from V
independently with probability &. Then, for ESDP n-t (SDP(G) W) have
00.888 t²
n weight (GW(G))
E(SDP(G[(s.) S:
E
0. 0.878cxpr. 22 B(SDP(G(S.))]
48

---

Proof. We start by lower bounding 0.878SDP(G) v weight, (GW(G)):
na weight (GW(G)) using the fact that for any graph G,
1
1
0.878
weight (GW(G)) n
SDP(G)
n
0.878
0.878 SDP(G)
0.878
E
[|SDP(G[s.)]]
E E(SDP(G(S.))
n²
t²
St
0.878
R
[[SDP((().)] 0.878EsDP
f2
We then upper bound ni weight (GW(G)) using the fact that for any graph G, weight, (GW(G)) - SDP(G):
weight (GW(G)) < SDP(G)
n2
n
1 R[SDP(C(S.))
SDP(G) +
E [((DP(G[Ss))
n
f2 s. 1
[[SDP(G[S.)] + SDP(G) [|SDP(G[(.))
ta St
n
ta S:
1
[[SDP(((S.))
1
E.4 Omitted Proofs from Sectionn.2
Input: Max-cut instance G = (V, E); V = sampled uniformly from En, for t =1, {1,2, 2.., n do
Place each node oft] on the side that maximizes the number of crossing edge according to node placement
Set Zg/4 be
Return:
Algorithm 5: Greedy(G')
E.4.1 Notations and preliminaries
we focus on the implementation in Algorithm as it is perhaps the most canonical and illustrative. For the greedy algorithm, we use a 2 -dmmension vector æ to describe a cut: let E (1, 2} denote the sides of the cut, denote the node placement time step, then
Although there are many variants of the Greedy algorithm for max-cut 22
60
64
1 if node is placed on the side at time step t.
2//0
0 if node is not placed on the side at time step f
if node has been placed time step l.
Intuitively, we can view our max-cut problem as problem of trying to maximize the number of crossing edges (or minimize the number of non-crossing edges) where crossing edge is edge {u, v} such that u on side i and is on side j. Let au. ,1, = 1/2 if (ul, u2) E and i = i2 and 0 otherwise. Then the objective function
be formulated as:
2xx)
Σ 1su1 Sn $1.22
Oui dig Fuzzia-
Let a' in 1/2 if (ul, u2) E and objective function as follows:
* is and 0 otherwise. Another way to formulate the
w(xx)
Σ
dug Wa Pur Sa
1SSL.355 Sn (1.22
49

---

It will be useful for later calculations to define w(x) = A'x with A' a) defined as:
A' A'(x(1) (2
E
(2) wn 22 "2,52
S 11.22((1.2)
Notice that =(x) is the sum of weights of the non-crossing edges in cut æ; and if both sides of an edge not placed, this edge will also be counted non-crossing.
Let b(x) of dimension 2n denote the partial derivative of (x)) and (xx) denote the partial derivative of w (x). Since bu Luz,is dui fi d2 we can see that b,, denote the increase in (z if we were to increase Tu,, from 0 to 1. Thus, we define the greedy step Ju,i as follows:
1 if arg min, (x or arg max, by, ((,,(((''))
fu
0 if = arg max; bu (zxi((x' or arg min, ((x'(()))))
0 if is not yet considered or has been considered
And finally, we define the fictitious cut: Definition E.20. (Mathieu and Schudy (64]) The fictitious cut a of a partial cut xly is defined as
if placed before time step
otherwise.
Notice that w(-) is the same function as weighta (.). We will be proving the size generalization result using w(+) as our objective, but [64] uses z(-) as the max-cut objective throughout their paper. Some of their results written in terms of z(-) are not directly transferrable to be a result written in terms of w(-)) Thus, if we use those results from 64], we will explicitly provide proof' for them.
E.4.2 Proof of Theorem
Proof of Theorem 3.4 can be divided into two parts. the first part, we prove that the difference between fictitious cut at time step to and is bounded. Then, show that the normalized difference between fictitious cut and the actual cut at time step is bounded.
The following lemma says that taking one time step, the change in fictitious cut shall be bounded by the difference in b-values, i.e, the partial derivative the cut value.
Lemma E.21 (Lemma 2.2 64
B[2(#') 2(
4n
+
n
E 2[bbat-1 - ("=
t2
t(n
t
Lemma E.22 (Lemma 2.6 in 64
B
( n-t (bur(āt)
bee ber(Fz")) is martingale with step
size bounded by n-t'
we have it under absolute value here because though (64] doesn't 't have it in their statement, they proved everything under an absolute value sign. Using we show the following lemma:
Lemma H.22 does not exactly agree with the statement of Lemma 2.6
64
Lemma F.23. For every I, we have [[b( - b (2 = O(a), where a = O n
Proof. Because Bi = n-t (bre(#²)) ber("))) xx=²)) is martingale step size bounded by 4n
n-1- we
know that + 1(()-1)- b ((x==11) a martingale with step size bounded by 4n n-t"
We apply Azuma- Azuma-Hooffding'" inequality:
50

---

| - ( 2 =P
b(("-1) b n (6- ())
2 -
A²62 (n - t)²
S 2exp
32m 3/m/1/(n 1)22
A2L
s 2eap
32n
Let 0 vi
then we shall have:
12 1 -b -x 21 s 2erp
(-or)
With Lemma E.21 and Lemma E..3 we are now ready to bound the difference between the fictitious cuts given two distinct time steps.
Lemma E.24. For every t tor we have E[2(*')] E[[((*')] O ( n 1. log(t)))
Proof.
B[=(a'))
E[²(6"))]
= Σ E[z(#") =(x =($=-1)]
r 11
4n
n
b(0 - -b
+2
2
E
(5)
72
T(n - + 1)
+=
4n²
n
n2²
72
T(n
T +
VF
r=to+1
The second equality uses Lemma E.21 and the third equality uses Lemma F.23 Now we look at the first term and the second term of separately. The first term of (5) can bounded by:
4n² 72
Rd
2
(
-
poo
73
dr
= 4n²
- -
1/
+
r=1
The second term of (5) can be bounded by:
51

---

0 n²
Σ
2
= 2n²0
n
T(n 1)
/T)
T 1. (n ++11
+=to+1
r=
n/2
-2 0
Σ
pl.6(n - +
11. (n 7 +
r=ta+1
T=
n/2
$ 0
Σ
+
1
T1.5
70.5 (0 (n-
r=
T=n/2
n/2
I 22n²
Σ
+
11.5
vn/2
+=lo+1
r=n/2
1/2
2 2 0
dr +
- dr
-1.5
Vn/2 J=n/2 n
1
1
= =2n 0
+
(log(t) -log(n/2))
Vta+1 +1
Vn/2
vn/2
0
n²
+ n 1.5 (log()) -1))
Therefore,
n
n²
B[x(*') - B[2(6*0) () 0
+
n (log(t) - 1)
to
via
= =0
n²
+ 1.5 (log(!) - -1)
vTo
We show that the same result holds for the other objective w(-): Lemma E.25. For every t 2 to. we have ((w((")) B[w((tt)] = ( ( + n nz (log(())(tt) -1)
Proof. Notice that for any fictitious cut a', w((') + x(x') = EE}. Therefore,
E (*)) [[2(
B[z(E') =(6'')]
= B|[ w(x') - (| wn((""))
Bl(w w(+')]
= =o ( n²
+ 1.5 (log(t) -1)
Vtu
Now we have a bound on the change of fictitious cut weight from one time step to another. We will now bound the normalized difference between fictitious cut weight and the actual cut weight at fixed time step.
We start by stating the following facts:
Lemma E.26 (Lemma 3.4 and 3.5 in (64). For any a 2 0, let (X
0,
-0 f0² }. Let and a by positive constant and X and Y be random variables. Then:
52

---

X E C(o), then aX C(ao)
If x E C(a) and Y S X, then Y C(a)
The random variable with constant value is in C(a)
xf E C(oa) and Y E C(ay), then X +Y C(ox + +
Then, show that B is also martingale.
Lemma E.27 (Lemma 2.5 in (64). Z -- (n/t)x²)) is martingale.
Lemma E.28. B
(bbi(at b' (x(())))) is martingale with step size bounded by
An
Proof. Let 11, 12 2). Because by Uu = = L 02. iig B is martingale following Lemma E.27 by linearity. We also bound the step size by linearity with Z which would be at most
n-1
Lemma E.29 (Lemma 3.6 (64) in terms w(x)). For a fixed cut y
P
Th (
(0im))
2 + 2 se =
where
σ n
Vt
Proof. Let Fy w (f w (B(1)) Define (///y)) We can show that (drop in the next chunk calculation for simplicity)
F
F(n))
(2(z)
(7)
n1
Σ
d Ausii (s Juzz2 - Tug Fugg
01,21,022.62
=(7) )
n1
1
(n t) n (xx ②))
Let D A'( x² + x)) A' 4(22-1_00 5" x 1 + x(-1). then n-t
n-1
A'( x² 5 xt + x')
DD -ED'SD + Σ E
n -
By Lemma E.26 it is sufficient to show each of these two terms in C' (0
The first term martingale with step O カ because, each time step, there could at most change of in objective value (in that case node aft) has f outgoing edges connecting to nodes that have been placed and all of them placed that all edges added to the cut). We can apply Azuma-Hoede Axeff-inoss'inn's inequality knowing the step size and in that case a (ύ-
21a
When both
and 2. we can show that 21 (n-0)² dominated by O (n2 V
n-t and thus by O (F in
simply
because
The second term can be re-written as:
53

---

x
xx
x=-1 x'-1
(x'-1 x
A'
x1-1
+ +A'
+ x + x-11_ x
11
n --t+1
n - t +
x² x²
x' x'-1
-- n m-t+1 +A'
a + oz
+
+ x
x
(6)
Notice that if we expand the first term of (6. each element indexed by u, is martingale difference z'-ø' -=-1_-a-1 times constant (because we conditioning on S*-1), ) and martingale difference
n-t n-1+1
has an expected value of zero. The third term bounded by O ((=z).
The second term of (6) rewrite as:
A' (x'-1 - xt-1
t t 10 + Ø² x.-1 at-1
xt + x. + xr 1
6' (8')) b1 (xaaa))
n(n t)
By Lemma E.28 we know that [6(('-1) - ( ) E C(O(n /vt)).
Now that every thing is in C(O(n² (oo(n///))), by Lemma E.26 we have that w (fzi w (z) (B'm))
C(0()2//I)-
Lemma E.30. For fixed y.
( ("alw)) w (0(v)) )1 O(o)
max yEV
where a = 00.
Proof. Using Lemma E.29
we integrate P
w ( - w (a(w:)) 2 20 over to co, which
gets us O
Theorem 3.4. Given an unweighted graph G (V, E), let S, be vertices sampled from V uniformly without replacement. For any e [0, and t +
E weighttss (Greedy(G[[..)) so(e+ log(t)
E weight& (Greedy(G)))
Vn
Proof.
1
1
[lw(x")] n
B[w(x()]
n12 w w(x")
12 w
1
n22 w (6t)
22 w w(x')
<
(("))
n2 w w(+')
nz w((')
82 w(xx)
n
1
E [w(#") w( )0
+
E w wo ar6)
2
By lemma F.25 we can bound the first term by
[w((") w(( _ E, [lw(**) w(
< 0
+ n (log(t) - 1)) V
54

---

Let y be the cut found on the first t element of by algorithm 5 second term by
By lemma E.30
we can bound the
E
w( n2 [0)) E [
n - w
(
0
n2
V7
Combining the results above gives us:
1 B[w((=))
1
n²
B[w(((')
0
+ n
(log(t) 1)
n² 82
n²
Vt
=0
+
(log(t) - 1)
v8
vn
log(t)
+
Vi
vn
Lastly, solve for the sample complexity bound. Set
v then when / 2 t. get
<0
log(t)
E
"]
12
[(((x'))
c+
n
12
vi
55


Reviews:
[{"review_id": "bv4B7RywbD", "reviewer": "Reviewer_74EK", "summary": "This paper introduces and tackles the task of \"size generalization\", which is estimating algorithms' performance on a large dataset by running it on a much smaller subset of instances. This task is meaningful because it provides a principled way to accelerate algorithm selection, which would be extremely costly if every candidate algorithm is run on every instance. Specifically, the authors provide size generalization guarantees for three clustering algorithms and two max-cut algorithms. \n\nTo model the generalization behaviour of k-means++ and Gonzalez’s k-centers heuristic, the paper builds an MCMC-based surrogate and proves a sample bound in terms of a smoothness parameter $\\varsigma_{k,f}$ that quantifies how sharply the seeding distribution concentrates. Notably, the sub-sample size needed to obtain the bound is independent of the total sample size. To analyse linkage-based clustering algorithms, the paper tracks how min–max path distances shift under subsampling and introduces a separation parameter $\\varsigma_{k,\\mathrm{SL}}$; size generalization holds when this remains moderate. For Goemans–Williamson max-cut, the paper compares the SDP objective on an induced subgraph to that on the full graph via a dual-pruning argument, then obtains accuracy guarantees. For the Greedy differencing heuristic, the paper casts the evolving cut weight as a martingale, applies concentration inequalities, and shows that sampling $t = O(\\varepsilon^{-2})$ vertices suffices to approximate the full-graph cut within $O(\\varepsilon)$. \n\nExperiments on four image or synthetic datasets and four random-graph families confirm that the proxy algorithms’ accuracies and cut densities rapidly approach those on the full instances, often allowing the preferred heuristic to be identified from a tiny fraction of the data.", "questions": "- How applicable are the size generalization bounds and proving techniques on other combinatorial problems and algorithms? Is there a more general framework we can extract out of the separated bounds and proofs in this paper?\n\n- Can the bounds developed in this paper guide us in selecting sub-sample sizes in real-world scenario? Is there a good way to decide or guess the smoothing parameters or other data assumptions?", "limitations": "Please see the weakness section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The task of size generalization formalizes a indeed very practical question. In fact, most people in the field of machine learning test their models on small datasets, and implicitly assumes size generalization in most times. It is good to see efforts in providing theoretical supports of size generalization, first on combinatorial algorithmic tasks.\n\n2. The paper develops several set of tools for obtaining size generalization bounds, which can be inspiring to more combinatorial algorithms. However, I am curious whether these techniques are directly applicable to a larger set of problems and algorithms.\n\nWeaknesses\n\n1. All size generalization bounds in the paper rely on some data assumptions, such as the smoothness parameters $\\vartheta_{k,f}$ and $\\vartheta_{k,\\mathrm{SL}}$, yet the authors provide little guidance on how to estimate or upper bound these quantities before running experiments. This limitation prevents people from directly using the bounds to plan computation budgets in real world scenarios. For example, when the data condition is unknown, I wonder if there is a naive workaround with a probe and stop strategy: run the target algorithm on randomly selected subsets of size 1, 2, 4, 8, 16, \\dots, compare the objective values or algorithm rankings between consecutive subset sizes, and terminate when the performance curve stabilises within a predefined tolerance. If we can prove the objective converges before reaching certain size, then this empirical scheme can act as a pragmatic substitute for the theoretical sample complexity.\n\n2. In this paper, basically each algorithm needs a set of new analysis. This approach is intrinsically limited in scope, because extending size generalization results to more / unknown combinatorial algorithms will likely require a more general framework.", "was_revised": true, "final_justification": "I will keep my rating of 4. Reasons explained in another comment.", "rebuttal": "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.\n\n**W1: “A pragmatic substitute for the theoretical sample complexity”** \n\nThis 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:\n\n|           \t| number of nodes sampled |  2 | 4 | 8 | 16 | 32 | 64 | 100 |\n|------------------|-----------|------------:|------------:|------------:|-------------:|-------------:|-------------:|----------:|\n| **Random Geometric**| Greedy| 1.0 |     3.6 |   15.5 |   61.8 |    244.2 |   972.7 |\t2381.8 |\n|                     \t| GW    |   1.0 |   3.6 |    15.2 |   60.0 |    239.6 |   997.3 |\t2376.9 |\n|                     \t| **Best**  | Greedy, GW  | Greedy, GW  | \tGreedy  | \tGreedy   | \tGreedy   |      \tGW  |\tGreedy  |\n| **Erdős–Rényi**     \t| Greedy\t|     \t0.0 |     \t1.0 |     \t4.0 |      \t8.4 |     \t40.9 |    \t104.6 | \t323.1 |\n|                     \t| GW    \t|     \t0.0 |     \t1.0 |     \t5.0 |      \t9.0 |     \t43.7 |    \t140.6 | \t339.8 |\n|                     \t| **Best**  | Greedy, GW  | Greedy, GW  |    \tGW   |    \tGW\t|    \tGW\t|    \tGW\t|  \tGW\t|\n| **Barbell**         \t| Greedy\t|     \t0.4 |     \t2.1 |     \t7.1 |     \t29.6 |    \t126.3 |    \t511.5 |\t1254.7 |\n|                     \t| GW    \t|     \t0.4 |     \t2.1 |     \t6.5 |     \t28.2 |    \t122.9 |    \t506.5 |\t1249.5 |\n|                     \t| **Best**  | Greedy, GW  | Greedy, GW  | \tGreedy  | \tGreedy   | \tGreedy   | \tGreedy   |\tGreedy  |\n| **Barabási–Albert** \t| Greedy\t|     \t0.2 |     \t0.3 |     \t3.2 |     \t11.5 |     \t34.3 |    \t130.1 | \t307.6 |\n|                     \t| GW    \t|     \t0.2 |     \t0.3 |     \t3.3 |     \t12.9 |     \t36.8 |    \t141.2 | \t328.2 |\n|                     \t| **Best**  | Greedy, GW  | Greedy, GW  |    \tGW   |    \tGW\t|    \tGW\t|    \tGW\t|  \tGW\t|\n\nWe will include these results and a brief discussion in the camera-ready version and continue scaling to more instances.\n\n**W2 & Q1. On “extending size generalization results to more combinatorial algorithms [with] a more general framework”**\n\nThank 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. \n\nMoreover, 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). \n\nThat 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:\n\n*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.*\n\n**Q2: Ways to “decide or guess the smoothing parameters”**\n\nThis 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.\n\nWe sincerely thank you again for your detailed review and thoughtful questions. In the camera-ready version, we will incorporate:\n\n- The probe‑and‑stop subsampling experiment (W1)\n- Explicit future‑work directions on a unified toolkit and SDP extensions (W2, Q1) in the Conclusion\n\nPlease 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!"}, {"review_id": "vX2Rs6eE9J", "reviewer": "Reviewer_mGbx", "summary": "This paper addresses the central challenge of **scalability in data-driven algorithm selection**. Data-driven algorithm selection is a powerful approach that evaluates candidate algorithms on a representative set of training instances and empirically chooses the best-performing one. However, running each algorithm on all training instances is computationally expensive, making it impractical for large or numerous instances.\n\nTo resolve this computational bottleneck, it is common practice to **evaluate algorithms on smaller surrogate instances** derived from the original input, but this practice has **lacked theoretical justification** until now .\n\nThis research provides the first theoretical foundation for this practice and formalizes a new concept called **\"size generalization\"** . Size generalization refers to the question (Question 1.1) of whether \"the performance of an algorithm on large instances can be quickly estimated by evaluating it on smaller, representative instances subsampled from the original instance\" .\n\nThe **main contributions** of this paper are as follows:\n\n*   **Formalization and provision of a theoretical foundation for size generalization** :\n    *   It introduces the new concept of \"size generalization\" to address the computational bottleneck in data-driven algorithm selection .\n    *   It provides the first **formal basis and theoretical guarantees** for the concept that an algorithm's performance on large instances can be estimated by evaluating it on smaller, representative subsamples .\n    *   This offers a natural framework for efficiently selecting algorithms for a single large problem instance, even when training instances are unavailable .\n*   **Size generalization guarantees for key combinatorial optimization problems** :\n    *   For **clustering problems**, it provides size generalization guarantees for three widely used algorithms: **single linkage, k-means++, and Gonzalez's k-center heuristic** .\n        *   For center-based algorithms (smoothed variants of Gonzalez's k-center heuristic and k-means++), it shows that, under appropriate assumptions, the required sample size does not depend on the size of the original instance .\n        *   For single linkage, it characterizes the conditions under which its performance can be estimated from subsamples, despite its theoretical instability .\n    *   For the **Max-cut problem**, it analyzes size generalization guarantees for two representative algorithms: **Goemans-Williamson (GW) and Greedy** .\n        *   For the GW algorithm, it proves a convergence bound for the SDP objective value without assumptions on the graph structure, strengthening prior work . This demonstrates that GW's performance can be efficiently estimated using subgraphs .\n        *   For the Greedy algorithm, building on prior work, it identifies the rate at which the cut density of a subgraph converges to that of the full graph .\n*   **Characterization of sufficient subsample sizes** :\n    *   It characterizes the sufficient subsample size for the performance on a subsample to reflect the performance on the complete instance .\n*   **Experimental validation** :\n    *   Experiments in both clustering and max-cut problems validate that the best-performing algorithm on subsamples can effectively predict the best algorithm on the full dataset . This demonstrates the proposed theoretical insights .", "questions": "The problem awareness and approach of this paper were highly intriguing. As pointed out in the third weakness, while the paper focuses on two major combinatorial optimization problems—clustering and Max-cut—it does not seem to provide a concrete direction for extending the framework to other combinatorial optimization problems such as integer programming or dynamic programming. Is that a correct understanding?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\nAddressing computational bottlenecks in data-driven algorithm selection: This paper tackles the primary challenge in data-driven algorithm selection, where running candidate algorithms on all training instances becomes computationally expensive. It introduces a new concept called \"size generalization\", demonstrating that an algorithm's performance on large instances can be efficiently estimated by evaluating it on smaller, representative instances. This significantly enhances the efficiency of algorithm selection.\n\nEstablishing a theoretical foundation for size generalization and applying it to a wide range of algorithms: This work provides the first formal theoretical justification for the common practice of evaluating algorithms on smaller proxy instances. Specifically, it presents size generalization guarantees for three widely used clustering algorithms: single linkage, k-means++, and Gonzalez's k-centers heuristic, as well as for two canonical Max-cut algorithms: Goemans-Williamson (GW) and Greedy. Furthermore, it strengthens prior work by providing convergence guarantees for the Goemans-Williamson SDP for Max-cut without imposing any assumptions on the graph structure.\n\nComprehensive empirical validation and reproducibility of theoretical findings: The theoretical discoveries in the paper are supported by extensive experiments using diverse datasets (MNIST, GM, Omniglot, noisy circles) and random graphs (Erdös-Réyni, Barbell, random geometric, Barabási-Albert). Experimental results show that as sample size increases, the accuracy or cut density of proxy algorithms converges to the performance of the original algorithms, highlighting the alignment between theory and practice. Additionally, code to reproduce the main experimental results is provided, ensuring the transparency and reproducibility of the research.\n\nWeaknesses\nHigh sample complexity or theoretical instability in some algorithms:\n\nGonzalez's k-centers heuristic: Directly applying the framework to this algorithm 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.\n\nSingle linkage: This algorithm 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.\n\nLimitations regarding algorithm-specific assumptions:\n\nMax-cut Greedy algorithm: The analysis of the Greedy algorithm is limited to unweighted graphs.\n\nGoemans-Williamson (GW) algorithm: 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.\n\nLimited scope of combinatorial optimization problems addressed: This paper focuses on two major combinatorial optimization problems: clustering and Max-cut. While it establishes a powerful framework for size generalization, its 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.", "was_revised": true, "final_justification": "After reading the authors' rebuttal, the important concerns I had during the review have been resolved, so I have raised my evaluation by one level.", "rebuttal": "We thank the reviewer for their review and detailed summary of our work. Below, we address their comments.\n\n**W1: trade-off characterized by smoothed Gonzalez's k-centers heuristic** \n\n> 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. \n\nIn 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.\n\nIn 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).\n\nTo 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. \n\n**W2: SL potentially requiring large subsamples** \n\n> “[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.”\n\nIt 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.\nMoreover, 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.\n\n\n**W3: Analysis of the Greedy algorithm is limited to unweighted graphs** \n\nIndeed, 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. \n\n**W4: non-Lipschitzness of GW objective leading to multiplicative and additive errors** \n\n> 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.\n\nWe 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. \n\n**W5: The current application does not include what’s listed in the future directions** \n\n> “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.”\n\nWe 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.\n\n**Q1: Extension to other combinatorial problems**\n\nIn 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. \n\nMoreover, 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). \n\nThat 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:\n\n*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.*\n\n\nWe 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."}, {"review_id": "cvR727EvsH", "reviewer": "Reviewer_uRvU", "summary": "This work introduces the concept of *size generalization*, which means predicting an algorithm’s performance on a large instance by evaluating it on a smaller subsample drawn from that instance. This work establishes size generalization bounds when using smaller instances—sampled either uniformly or randomly from the original data—for three widely used clustering algorithms (single-linkage, k-means++, and Gonzalez’s k-centers heuristic) as well as two max-cut algorithms (Goemans-Williamson and Greedy).", "questions": "* *Size generalization* aims to predict an algorithm’s performance on a large instance by evaluating it on a smaller subsample, thereby improving efficiency. I wonder why the timing performance of both the subsampled and the original algorithms was not reported in the experiments.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n* This work introduces the notion of *size generalization*, which has practical significance in many scenarios.\n* It also provides size generalization bounds when using smaller instances—sampled either uniformly or randomly from the original data—for three widely used clustering algorithms and two max-cut algorithms.\n\n## Weaknesses\n\n* The experimental section is overly simplistic for real‐world applications. In the clustering experiments, every instance is partitioned into k=2 clusters—an inappropriate choice given the complexity of the datasets. Moreover, even for large datasets, the authors fix the problem size at n=500, which contradicts their stated goal of addressing big-data scalability. Finally, the results do not demonstrate whether the proposed algorithms can reliably approximate the ground-truth cost when the sampled data size is very small (for example, sublinear in\nn).\n\n* The proposed method requires two “oracles” to run in a semi-supervised fashion: (1) a distance oracle that returns the distance between any two points, and (2) a ground-truth oracle that provides the true clustering or cut value for any subset—each assumed to answer in constant time. Such idealized oracles are rarely available in practical, real-world settings, calling into question the method’s feasibility.\n\n* The authors should compare their fast-selection framework against existing sublinear-time solutions for k-means, k-center, and Max-Cut—such as “Sublinear Time Approximate Clustering, Mishra et al, SODA'01” “Sublinear Algorithms for Greedy Selection in High Dimensions, Chen et al, UAI'22”, “Sublinear Algorithms for MAXCUT and Correlation Clustering, Bhaskara et al., ICALP'18”, and many other results in this \"sub-linear time algorithms\" area (two good surveys from Ronitt Rubinfeld & Asaf Shapira,  and  Artur Czumaj & Christian Sohler). Although these works optimize a different cost function, they directly address sublinear-time solution of the original problem; if one can compute an approximate solution in sublinear time, the need for a separate fast-selection step may be less compelling.\n\n* There appears to be an error in Fig. 1(a) that may cause confusion: the legends for the original clustering algorithm and the subsampled version seem to be swapped.", "was_revised": true, "final_justification": "After the rebuttal and discussion stage, I will maintain my original score. I agree that this paper introduces some new ideas for fast evaluating algorithmic performance. However, there are still several significant limitations. \n\n1. The application scope is relatively narrow. Like the clustering part, the method can only handle **greedy selection based** clustering algorithms, not all possible clustering algorithms. As I emphasized in my previous feedback, k-means++ and Gonzalez are already two well-accepted clustering algorithms, and there is not much need to consider other types of greedy selection based clustering algorithms. \n\n2. Another major concern is the parameter $\\zeta$. The authors argued that this value is analogous to condition number in numerical linear algebra. But,  condition number is much more natural and easy to interpret in geometry. In contrast, the parameter $\\zeta$ is too complicated and not that natural to understand. More importantly, for different \"f\", the value of $\\zeta$ could be totally different. That means, $\\zeta$ depends not only the input distribution, **but also each individual tested algorithm**. This is very different with the condition number, which only depends on the input matrix. This \"f\"-dependence property also significantly weakens the theoretical value and elegance of this paper. \n\n3. The experimental part is very limited. This point is also mentioned by other reviewers. I suggest the authors to greatly enlarge this part in future.", "rebuttal": "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: \n\n**W1: Clustering experiment with n = 500 and k = 2 is simplistic.** \n\nThank 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:\n\n- MNIST, Gaussian Mixture (GM), Noisy Circle (NC) with $n=2000$, $k=2$\n- MNIST with $n=3000$, $k=5$ (we omit due to space constraint)\n- MNIST with $n=4000$, $k=10$.\n\nIn 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\n$n  = 2000$, $k = 2$:\n|            | Fraction of nodes sampled\t| 0.2       \t| 0.4       \t| 0.6       \t| 0.8       \t| 1         \t|\n|--------|------------|---------------|---------------|---------------|---------------|---------------|\n| mnist   | SL     \t| 0.521 (0.013) | 0.513 (0.009) | 0.510 (0.008) | 0.508 (0.004) | 0.500     \t|\n|   | k-centers  | 0.651 (0.089) | 0.648 (0.088) | 0.650 (0.090) | 0.648 (0.089) | 0.638 (0.092) |\n|   | k-means++  | 0.661 (0.102) | 0.667 (0.102) | 0.667 (0.103) | 0.660 (0.105) | 0.669 (0.102) |\n| GM  \t| SL     \t| 0.511 (0.011) | 0.511 (0.007) | 0.511 (0.009) | 0.505 (0.004) | 0.501     \t|\n|  \t| k-centers  | 0.712 (0.090) | 0.715 (0.090) | 0.710 (0.091) | 0.710 (0.091) | 0.715 (0.087) |\n| \t| k-means++  | 0.707 (0.091) | 0.711 (0.091) | 0.710 (0.090) | 0.707 (0.087) | 0.712 (0.089) |\n| NC  \t| SL     \t| 0.513 (0.009) | 0.513 (0.007) | 0.509 (0.005) | 0.505 (0.003) | 0.501     \t|\n| \t| k-centers  | 0.609 (0.081) | 0.604 (0.084) | 0.594 (0.083) | 0.594 (0.085) | 0.577 (0.084) |\n|  \t| k-means++  | 0.629 (0.061) | 0.625 (0.063) | 0.628 (0.062) | 0.625 (0.063) | 0.624 (0.065) |\n\n\n$n  = 4000$, $k = 10$:\n|    | Fraction of nodes sampled| 0.2       | 0.4       | 0.6       | 0.8       \t| 1         |\n|---------|------------|---------------|---------------|---------------|---------------|---------------|\n| mnist   | SL     \t| 0.12 (0.005)  | 0.113 (0.004) | 0.108 (0.004) | 0.104 (0.001) | 0.101     \t|\n|   | k-centers  | 0.299 (0.045) | 0.29 (0.045)  | 0.287 (0.045) | 0.283 (0.047) | 0.288 (0.044) |\n|   | k-means++  | 0.352 (0.039) | 0.352 (0.039) | 0.352 (0.037) | 0.351 (0.039) | 0.351 (0.037) |\n\n\n\nIn all settings—even $n = 4000$, $k = 10$—rankings stabilize by 40–60 % subsampling, confirming size-generalization at scale. \n\n\n**W2: Can we approximate ground‑truth with sublinear samples?** \n\nThank 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): \n\n|    | number of nodes sampled  \t| $n^{1/2} $   \t| $n^{3/4}$    \t| $n^{5/6} $   \t| $n^{7/8}$    \t| $n^{9/10}$   \t| $n$          \t|\n|---------|-------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| mnist   | k-means++   | 0.724 (0.122)  | 0.727 (0.121)  | 0.722 (0.122)  | 0.722 (0.123)  | 0.723 (0.122)  | 0.722 (0.121)  |\n|   | k-centers   | 0.745 (0.101)  | 0.726 (0.101)  | 0.721 (0.101)  | 0.718 (0.101)  | 0.717 (0.105)  | 0.706 (0.104)  |\n|   | SL      \t| 0.574 (0.043)  | 0.537 (0.026)  | 0.518 (0.020)  | 0.512 (0.013)  | 0.508 (0.007)  | 0.501      \t|\n| NC  \t| k-means++   | 0.627 (0.061)  | 0.630 (0.060)  | 0.628 (0.062)  | 0.628 (0.062)  | 0.629 (0.061)  | 0.626 (0.062)  |\n| \t| k-centers   | 0.616 (0.063)  | 0.623 (0.062)  | 0.618 (0.063)  | 0.621 (0.061)  | 0.622 (0.061)  | 0.620 (0.063)  |\n|  \t| SL      \t| 0.650      \t| 0.803      \t| 1.0 (0)    \t| 1.0 (0)    \t| 1.0 (0)    \t| 1.0        \t|\n| GM  \t| k-means++   | 0.730 (0.094)  | 0.732 (0.093)  | 0.730 (0.094)  | 0.729 (0.095)  | 0.731 (0.092)  | 0.731 (0.093)  |\n|  \t| k-centers   | 0.728 (0.095)  | 0.733 (0.094)  | 0.725 (0.095)  | 0.728 (0.096)  | 0.726 (0.094)  | 0.729 (0.093)  |\n|  \t| SL      \t| 0.645 (0.070)  | 0.538 (0.023)  | 0.522 (0.023)  | 0.517 (0.013)  | 0.518 (0.011)  | 0.502      \t|\n\nIn 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.\n\nEven 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}$:\n\n|    Fraction of nodes sampled | 0.2 \t| 0.4  \t| 0.6  \t| 0.8   \t| 1    \t|\n|--------|---------|----------|----------|-----------|----------|\n| GW \t| 0.5938  | 12.3565  | 72.2823  | 370.3707  | 961.4030 |\n| Greedy | 0.0187  | 0.0834   | 0.1575   | 0.3231\t| 0.5781   |\n\nWe observe that:\n\n- An **80% subsample** cuts GW’s runtime by over **60%** (from 961s to 370s)\n- A **60% subsample** cuts GW’s runtime by roughly **90%** (to 72 s)\n- Even the very fast Greedy enjoys relative speedups\n\nBecause 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.\n\n**W3: Concern about the two-oracle setting not available in practice** \n\nOur 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. \n\n\n**W4: Comparison to the sublinear-time algorithm literature** \n\nThank you for your feedback! We will expand our related work section (Section 1.2 and Appendix B.1) as follows:\n\nOur 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. \n\nThe 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. \n\nThat 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. \n\nThe 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. \n\n**W5:  typo in figure legend of Fig. 1(a)**\n\nThank you for catching this. We will correct the legend in the camera-ready version.\n\n**Q1: The timing performance of both the subsampled and the original algorithms should be reported in the experiment.**\n\n\nThank 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. \n\nWe 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:\n\n- Correct the typo in Fig. 1(a) legend (W5)\n- Scale up the clustering experiments (W1)\n- Include runtime statistics for all subsample sizes with new figures (Q1)\n- Expand related work on sublinear‑time algorithms (W4)\n\nPlease 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!"}, {"review_id": "vyIlssa5qg", "reviewer": "Reviewer_orjk", "summary": "The paper introduces *size generalization*, the problem of predicting the accuracy on the full dataset given a subset of it. They then analyze this for several different classical tasks, such as $k$-center, $k$-means, single-linkage clustering and max-cut. They prove bounds on the sizes of the samples and the numbers of accesses to ground truth labels required to achieve the size generalization.", "questions": "My primary question is regarding the similarities and differences between the proof techniques for the various optimization problems. Are there common themes that can be extracted and applied more generally? If not, why not?", "limitations": "I think a formal limitations discussion would be helpful. The current discussed limitations are oriented around technical details of the proof techniques. However, the paper's primary limitation seems to actually be that size-generalization is most actively studied in the deep learning community right now (with scaling laws being the most extreme example) but the paper does not interface with that literature at all. Which is perfectly fine! But worth mentioning.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- I am honestly quite shocked that this direction does not have more literature on it. I am familiar with coresets for clustering and, separately, with a lot of topics in deep learning research. So when I saw the description in the introduction, I thought there must surely be significant work on this idea of predicting the accuracy on a full dataset using only a subset of it. After all, I know a similar thing is done for coresets (but different in that coresets attempt to find a sample which preserves the cost), and the field of deep learning is actively interested in analyzing which training run will land where (in a more empirical sense). However, after spending time on a literature review, I could not find papers discussing this specific task of size generalization done in a theoretically rigorous way. This is quite surprising to me and implies that the paper is filling a nice gap in the literature. Unless I am mistaken and have missed something, I consider this a significant strength of the paper.\n- The resulting bounds feel consistent with what one might expect given familiarity with sublinear-time algorithms, sensitivity sampling, etc.\n- Some of the proof techniques are quite nice. I particulalry like the continuous extension of k-center and the analysis of the minimax distance with respect to sampling.\n\nWeaknesses:\n- I found this paper quite difficult to read and wish the results were presented differently. As it stands, this paper feels like three papers: size generalization for center-based clustering, size generalization for single-linkage and size generalization for max-cut. These results are presented by giving the proof techniques specific to each problem case. However, I find myself wanting an understanding of the general themes inherent to the task of size generalization. That is, I cannot see much overlap at all between the methods employed by the proof sketches in, for example, Theorems 2.2, 2.7 and Theorem 3.4. Even if these are, in fact, quite separate approaches, it would be good to have an overview somewhere after the introduction which describes the general techniques one might expect and how to approach a size-generalization problem. How does this relate to PAC-learning techniques? Are there techniques which can consistently be applied to size generalization and, if not, why not?\n- While I strongly commend the general topic of size generalization (as discussed in the strengths), I find the chosen motivation for studying these specific algorithms... detached from the state of the field. That is to say, I do not actually see the primary use case for size-generalization to be in combinatorial algorithms or clustering: there is usually sufficient compute to run k-means on any size dataset required.\n  - Instead, it feels much more relevant to me to study these ideas on neural networks, where training runs are *significantly* more expensive and where the empirical utility is much higher. Indeed, at least half of the list of empirical use cases for size-generalization listed on lines 43-46 are about neural network convergence. This is not counting the entire field of scaling laws which has seen huge growth in the last 3-4 years and is oriented *precisely* around the topic of size-generalization.\n  - Complete nitpick: as a person who has dipped toes into both TCS and the more empirical side of machine learning, I find it frustrating when TCS paper introductions motivate algorithms by saying they are used for tasks when, in reality, they are no longer used for that task. For example, clustering is never used for image segmentation anymore and the reference to chip design is from 1988.\n\nIn summary, I consider the task of studying size-generalization a very relevant one and the paper's results feel clean. However, it seems that the utility of the topic would be better suited to other algorithms and the paper did not provide blueprints which would explain which (if any) of the proof techniques can be extended to the topic of size-generalization more broadly. Of course, I am not requesting that the authors prove additional size-generalization bounds for new optimization problems -- I am moreso explaining why the clarity and significance scores are not higher given my praise for this paper's strengths.", "was_revised": true, "final_justification": "I believe this paper is interesting and presents a nice theoretical way to think about predicting an algorithm's success. However, the lack of a unified framework for studying size generalization and the chosen algorithms prevent me from giving this paper a stronger acceptance score.", "rebuttal": "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.\n\n\n**W1 & Q1: On developing a general technique for size-generalization**\n\n\nThank 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. \n\nMoreover, 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). \n\nThat 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:\n\n*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.*\n\n**W2: Size generalization seems especially relevant for neural network training.**\n\nWe 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. \n\nThe 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. \n\n**W3: Outdated references for application of clustering and max-cut**\n\nWe think this is a great point. We will modify the first sentence in the Introduction with more recent applications of clustering and max-cut: \n\n“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).”\n\nThank 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:\n\n- Add the discussion about future‑work directions on a unified toolkit and SDP extensions (W1, Q1) in the Conclusion.\n- Expand our motivation in the Introduction to highlight more recent combinatorial optimization use cases (W3).\n\nPlease 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!"}]

Author rebuttal:

Meta-review: This paper tackles the primary challenge in data-driven algorithm selection, where running candidate algorithms on all training instances becomes computationally expensive. It introduces a new concept called "size generalization", demonstrating that an algorithm's performance on large instances can be efficiently estimated by evaluating it on smaller, representative instances. This significantly enhances the efficiency of algorithm selection. The paper addresses a handful of comobinatorial optimization partition problems w,r,t, some common optimization algorithms. The main criticism of the submission refers to the relatively limited scope of the analysis.
Decision: Accept (spotlight)