Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning
Authors: Yijun Dong
Hoang Phan
Xiang Pan
Qi Lei
Venue: NeurIPS 2024 poster (2024)
Keywords: Data selection
Finetuning
Sketching
Johnson-Lindenstrauss transform
Primary area: learning_theory
TL;DR: We present a theory on data selection for high-dimensional ridge regression that inspires a fast and effective data selection algorithm for finetuning.

Abstract: We revisit data selection in a modern context of finetuning from a fundamental perspective. Extending the classical wisdom of variance minimization in low dimensions to high-dimensional finetuning, our generalization analysis unveils the importance of additionally reducing bias induced by low-rank approximation. Inspired by the variance-bias tradeoff in high dimensions from the theory, we introduce Sketchy Moment Matching (SkMM), a scalable data selection scheme with two stages. (i) First, the bias is controlled using gradient sketching that explores the finetuning parameter space for an informative low-dimensional subspace $\mathcal{S}$; (ii) then the variance is reduced over $\mathcal{S}$ via moment matching between the original and selected datasets. Theoretically, we show that gradient sketching is fast and provably accurate: selecting $n$ samples by reducing variance over $\mathcal{S}$ preserves the fast-rate generalization $O(\dim(\mathcal{S})/n)$, independent of the parameter dimension. Empirically, we concretize the variance-bias balance via synthetic experiments and demonstrate the effectiveness of SkMM for finetuning in real vision tasks.

Sketchy Moment Matching: Toward Fast and Provable
Data Selection for Finetuning
Yijun Dong" Courant Institute New York University yd1 31 90nyu. edu
Hoang Phan" Center of Data Science New York University hvp201 1 1@nyu. edu
Xiang Pan" Center Data Science New York University x xiangpanenyu.eed edu
Qi Lei
Center Data Science New York University q15188nyu. edu
Abstract
We revisit data selection in modern context of finetuning from fundamental perspective. Extending the classical wisdom of variance minimization low dimensions to high-dimensional finetuning, our generalization analysis unveils the importance additionally reducing bias induced by low-rank approximation. Inspired by the variance-bias tradeoff in high dimensions from the theory, intro- duce Sketchy Moment Matching (SKMM), a scalable data selection scheme with stages. (i) First, the bias is controlled using gradient sketching that explores the finetuning parameter space for an informative low-dimensional subspace S; (ii) then the variance is reduced over S via moment matching between the original and selected datasets. Theoretically. we show that gradient sketching fast and provably accurate: selecting n samples by reducing variance over S preserves the fast-rate generalization ((dim(S) (S)/n.. independent of the parameter dimension. Empirically, we concretize the variance-bias balance via synthetic experiments and demonstrate the effectiveness of SkMM for finetuning in real vision tasks.
Introduction
As the data volume and training cost explode with the unprecedented model performance, the long- standing problem of data selection 2 is getting increasing attention in the modern context of deep learning from various perspectives, including data pruning 3 4 coreset selection [
g 9],
12 13). A common goal shared by these perspectives is to train a model from scratch on less data to learn high-quality representations and achieve competitive generalization. However, empirical observations also suggest the limitation of data removal during pre-training: seemingly inevitable tradeoff between less computation and higher-quality representations [14] [15]. While existing works data selection have dominating focus the training-frone from-sccacch setting, the sensitivity of representation learning to data and the growing availability of powerful pre-trained models calls for attention to less studied [16] but equally important problem: data selection for finetuning.
and data filtering 2 T0
In the simplest finetuning setting-linear probing on low-dimensional representations data selection falls the classical frames of coreset selection for linear regression [77
23 29 where the generalization gap can be
18 19
20
21
22
24 and optimal experimental design [25] 26 27
28
"Equal contribution.
'Throughout this work, refer "low-dimension" the setting where the number of finetuning parameters r smaller than the selected downstream sample size n, while "high-dimension" refers to the opposite, r > n.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

reduction
Variance reduction
Gradient sketching: low dimennioonal 8
Moment matching in & variance-biss tradeoff
Finetuning paramster space R' with >
ng =
8
R
Ry
(b)
(c)
(d)
Figure I: Controlling variance-bias tradeoff data selection for high-dimensional finetuning via gradient sketching moment matching (SKMM). Consider toy dataset with N samples (in blue) whose finetuning gradients lie in a nigh-dimensional parameter space R' (visualized in 3D) with a low intrinsic dimension (e.g., three clusters). The goal is select n1 +2 + Rg samples for finetuning. (a) Bias reduction focuses on minimizing the low-rank approximation error, resulting in uniform selection across clusters regardless of their variance. (b) Variance reduction places more emphasis on high-variance clusters and could lead to large bias by missing low-anriance ones. (c) Gradient sketching efficiently finds low-dimensional subspace S (where dim(S) < n) with small bias. (d) Moment matching in S controls the variance within the low-bias subspace, leading to variance-bias balance with fast-rate generalization (ddim())/n).
reduced by selecting data that minimize the associated variance. However, for high-dimensional finetuning, variance minimization alone is insufficient to characterize the generalization due the overparametrized nature of modern architectures. Even for linear probing, when the parameter dimension r is higher than the sample size n, the selected data necessarily fails capture subspace of the parameter space with dimension at least r n, leading to errors in addition to variance. Nevertheless, the prevailing empirical and theoretical evidence [14 30 on the ubiquitous intrinsic
low- -ow-dimeniional structures of nigh-dimensional data/model motivates a natural question:
Can the low intrinsic dimension be leveraged in data selection for high high-dimensiioal finetuutnnn
Low intrinsic dimension leads to pariance-bias tradeoff in data selection. We provide a positive answer to this question through a variance-bias tradeoff perspective. Intuitively, we consider low-dimensional subspace S in the finetuning parameter space where the model learns the necessary knowledge for the downstream task. The generalization gap can be controlled by simultaneously reducing the bias (redundant information) by "exploring" the finetuming parameter space to find suitable S and the variance by "exploiting" " the useful knowledge S.
Given the high-dimensional nature of the finetuning parameter space, direct search for such suitable subspace S is computationally infeasible in general. This leads follow-up question:
How to explore the intrinsic low-dimensional structure efficiently for data selection?
We propose a two-stage solution-Sketchy Moment Matching (SKMM): (i) dimensionality reduction via gradient sketching to efficiently explore the finetuning parameter space, and (ii) variance control via moment matching to exploit useful knowledge in the oowddimesiional subspace.
Gradient sketching finds a good low-dimensional subspace fast and provably. First, we con- struct a low-dimensional parameter subspace S by sketching the model gradients. Sketching [7 is a well-established dimensionality reduction tool known for affordable and accurate low-rank approximations 332 B3 In deep learning, sketching recently extends its empirical applications to scalable estimations of influence functions for data selection [16] 34]. We make a first step toward the theoretical guarantee of gradient sketching for data selection: gradient sketching efficiently finds a low-dimensional subspace S with small bias such that selecting n samples by reducing variance over S is sufficient preserve the fast-rate generalization (ddi((S)/n linear in the low intrinsic dimension dSm(S) while independent of the high parameter dimension r.
Moment matching in low dimension selects data that control the variance. Second, we select data that reduce variance in the low- oi--imensional subspace S via moment matching. The variance of data selection is characterized by matching between the sketched gradient moments of the original
Most classical variance reduction methods are tailored only for low-dimensional settings with n > r. Here, we intuitively refer to "variance reduction" as the direct extension of low-dimensional variance reduction to high dimensions, without careful control of the bias (vide Section 4. for some concretizations).

---

and selected datasets, Σ, Es. formally tr( tr(Eg)). This objective involves optimizing over the inversions of (potentially) ill-conditioned matrices, leading to a challenging discrete optimization
problem 28 35 Under a common heuristic assumption that >, Σs commute 336 37,, we introduce
continuous relaxation with quadratic objective and linear constraints that is numerically stable (free of pseudoinverse) and can be efficiently optimized via projected gradient descent.
The contributions of this work are summarized as follows:
We provide rigorous generalization analysis data selection for finetuning, illustrating the critical role of dimensionality by unveiling the variance-bias tradeoff in high dimensions.
We show that gradient sketching provably finds -ww-dimessional parameter subspace S with small bias, reducing variance over which preserves the fast-rate generalization (n) Techniques used in analyzing gradient sketching for data selection are agnostic to the selection method or the finetuning setting and could be of independent interest.
We introduce SkMM, scalable two-stage data selection method for finetuning that simultane- ously "explores" the high-dimensional parameter space via gradient sketching and "exploits" the information in the low-dimensional subspace via moment matching.
1.1 Related Works
Coreset selection and low-rank approximations. From the variance- bias tradeoff perspective, data selection for high-dimensional finetuning can be viewed as combination of (i) variance reduction in coreset selection for linear regression 17
18 21
23 24
with low-dimensional
features, and (ii) bias reduction via sample-wise low-rank approximation for high-dimensional
matrices 38 40
43 45 46].
Gradient sketching. Gradient sketching
Saansson-Lindenstrauss transforms (ILT's [7) has achieved impressive recent successes in efficient data selection [16] and attribu- tion (34). Despite the empirical success, theoretical understanding of the effect of gradient sketching on generalization remains limited. We make a first step toward this in the context of data selection leveraging existing theories on sketching (vide Remark 3.1 and Appendix C
32 based
Moment matching and optimal experimental design. Moment matching is an intuitive idea for selecting -iw-immesionall data (i.e., overdetermined with coreset size n larger than data/representaatoon
dimension r), bearing various objectives like the A/V-optimality [28 29 from optimal experimental
design (OED) 25 26 277. While classical OED studies the overdetermined scenario with n 2 r. efforts have been made to extend the notion of V-optimality beyond the overdetermined setting [4 49]. Nevertheless, these works focus on the general overparametrized setting without considering potential special structures in data. In the context of data selection, this can lead to pessimistic sample complexity, especially for learning problems with low-intrinsic dimensions.
For multimodal contrastive learning, recent works 12 13 illustrated the effectiveness of moment matching via tailored data selection criteria for CLIP 50) Distinct from our setting of general finetuning in both low and high dimensions, these works focus on data filtering (with n > r) for pretraining from scratch.
(Unsupervised) data selection. In this work, we focus on unsupervised data selection that in- stead of relying on label=)) leverages the geometry of the feature space and aims select samples that are spread out, with a broad spectrum of concretizations including herding [5] [2], k-center greedy (53), leverage score sampling
55 adaptive sampling 44 56 and volume sam-
pling 33 41)
An inspiring recent work [57] investigates the generalization of weakly supervised data selection via independent sampling in the low- (n + co with fixed r) and high-dimensional (n, + co with n/r + constant) asymptotics. Instead of the asymptotic regime, we consider a realistic setting with finite n and without specific assumptions on the data/feature distribution other than the low intrinsic dimension. Along this line, (weakly) supervised data selection commonly make choices based on the uncertainty [58] 59 60 or sensitivity of the loss to samples (e.g., influence function 4 61 62] sensitivity scores
65 and heuristics based on losses and their
gradients 66 67
68 69
'From the theory perspective, data selection for finetuning is less sensitive to labels compared to training from scratch. especially given suitable pre-trained models with reasonable zero- zero-shot accuracy (e.g., Assumption 2.2

---

1.2 Notations
Given any E 2.., we denote [n] = {1...., Let en be the n-th canonical basis of the conformable dimension; In be the entries equal to zero and one, respectively. Let S = {x E IR" | = be the unit sphere in IR", and A := {p [0, 11 ||p|| = = be the dimension-n probability simplex. We adapt the standard asymptotic notations: for any functions f.g R+ Rt, we write f = (g) or < g if there exists some constant C > 0 such that f(z) I Cg(æ) for all E R4: (g) or 2 if = (f): x if f O (g) and 9 (g). For any matrix A E Ra let (rank(A)(A) 2 be the singular values; and A be the Moore- Peoore-eenrose pseudoinverse. Additionally for any l: S rank (A), let (A)x argmill rank(B) < || A B be the optimal rank- approximation of A (characterized by the rank-k truncated SVD). For any symmetric matrices B is positive semidefinite.
identity matrix; and On In R being vectors with all
$1 (A) 2
A, B E Rdxd we write A > B A B > 0f A
2 Data Selection for Finetuning
Given a data space X' C Rd and label space y C R, let = ((x,,))) E x [N]] be a large dataset, with matrix form y) E IR. Nxd x TRN, for some downstream task where the performance is measured by loss function L y 20
Finetuning. Let F be a class of prediction functions where each f= = pressed as the composition of an expressive representation function & and a prediction head h. We consider a pre-trained model & that yields high-quality representations for some downstream tasks on D and denote Fig S F as the class of finetuned models based on é. Assume that for every (x,, Us) E D. y: (y xx) i...d. such that there exists f Fis with respect to & satisfying (i) E lys é (xx)] = 1 (x.), and (ii) V [ys o (x:)) S o² for some (which will be formalized later in respective settings).
d F can be ex-
Data selection. Instead finetuning on the entire dataset D, we aim to select a small coreset Ds S D of size < N where the generalization is close. Precisely, let Dg be indexed by S C [N] and denoted as ys) E Raxd x R". With LD₃ (J) (x.r)e {J((x), v) and regularization
R: Flg Bg0 associated with hyperparameter
0, want fs argmin LDs (f)
R (f) provide a low excess risk over D: ER (fs) EM fx.,
2.1 Low-dimensional Linear Probing: Variance Minimization
Warming up with linear probing, we concretize the general assumption on the ground truth (i.e., [ys (x:) 1 (x;) (x.) 0. and V [y: è (x:)) v a²) follows:
Assumption 2.1 (linear probing ground truth). Assume = 6 (X) 0. for some O, E R. where (..,... _N]] E N consists i.i.d. entries with E. [z] Ox and E [zz] x IN.
Consider the pre-trained representations (XX) R and ((Xs) Rx with respective moments " = 1 (X) @ (X) and ΣS == 2 Xxs
Φ (Xs). )- For low-dimensional linear probing with S (s.I. rank } r). the linear regression 0g argming 4 (Xx) 0 -ysl1 has a unique
solution with excess risk ER (0s) = ||0s 0, > controlled by ΣΦ and >g analogous to the V-optimality criterion
28
29
in optimal experimental design:
o² n
E ER (0s)
tr tr (Eg))1))))))
(1)
If Ds satisfies L6 < cg ΣS for some cs 2 N. then E ER (As)) S cs d²r (proof in Appendix B.1).
where es characterizes the variance controlled by Ds, i.e. smaller cs implies lower variance.
Despite its simplicity, uniform sampling is often observed in practice to serve strong baseline for data selection D. especially when n is large. In the -iwednmnnioona linear probing scenario, provides a theoretical justification for such effectiveness of uniform sampling:
Forr any E IT,, ||ul|g: Vu D the seminorm associated with 인 0.

---

Proposition 2.1 (Uniform sampling for wow-dimensional linear probing (Appendix B 2. Assume
there exists (i) B 0 such that 110(x)]12 I B V E D: and (ii) 7 with - > I, For S
sampled uniformly (with replacement) over D, with probability at least - 5 over S. Σ x 2 for any es > 1 if
r+
(1-1/cs)*
That is, for linear probing with sufficiently low dimension r < n, under mild regularity assumptions on data, uniform sampling enjoys a near-optimal generalization O(r/n).
2.2 High-dimension Finetuning with Low Intrinsic Dimension: Variance- Biss Tradeoff
Extending the analysis to general finetuning, we consider set of finetuming parameters 0 R (potentially with r " n) over a pre-trained model Φ (e.g., 0 can be the parameters of the last layer (i.e., linear probing), last few layers, the entire network, or the LoRA [70] matrices).
Let Fie { (:; 0) : X' + R 0 E IR"} be the finetuning function class. Without loss of generality, we assume zero initialization of O such that / (:; 0-) corresponds to the pre-trained model. Analogous to the assumption in [T6], under locality constraint on (e.g.. ||0]|2 < 1), the dynamics of finetuning falls in the kernel regime [7] where f can be approximated by its first-order Taylor expansion:
o (x; 0) ~ o (x:0,) + fo (x:0,, 0,) 0. Then, we formalize the ground truth as follows:
Assumption 2.2 (Finetuning ground truth). Given the pre-trained é. there exists a bounded ground truth 0. E R" with |00.|] llg < 1 such that for all (x, E DD (i) E by & (x)] = 5 (x) = l O.).
and (ii) V [y Φ (x) S for some some a >
Intuitively, Assumption 2.2 implies that the pre-trained model fo (-: 0,)) has a reasonable zero-shot performance. Given any S C [N] with |S| = n, let f (X s; 0) E R and V (Xs;0) RRar be the evaluation of fo (x; 9) and its Jacobian over X O. We observe that with = f 0.). Assumption 2.2 implies y - f 0,) s GO, + where E [z] = ON and E [zz] J V onIN: while
G = -oVof 8 0,) E TR: Nxr is the Jacobian over D initialization.
Then in the kernel regime [71]. the finetuning objective minøER A || f1 (Xs: ys 1s + 10 can be well approximated by a ridge regression problem:
1
Vol (Xs;0,) 0 (ys - 1 (Xs; 0,))112 t 0 11012-
0s argmin
AER n
Recall G Vof [: 0,) E RN and Gs Voff(Xs:) 0,) E Raxr. With the moments E G G and ΣS G Gs, the excess risk ER (0s) = |00g 0 1 satisfie
Theorem 2.2 (Main result I: variance-bias tradeoff (Appendix B.3 Given S, let Ps E &R be an
orthogonal projector onto some subspace S C Range Eg), and P I Ps be its orthogonal complement. Under Assumption 2.1 there exists an a > O such that 2 satisfies E |ER (0s)] S
variance + bias with (i) variance 20 tr (E (P PP)) and (ii) bias 2 tr Σ E 00.12
Specifically, the variance-bias tradeoff' is controlled by the unknown S: expanding S leads to higher variance but lower bias. Reducing the generalization gap involves finding suitable S in the high- dimensional parameter space, a computationally challenging problem addressed in Section 3.1
is worth highlighting that Theorem 2.2 encapsulates both the low- and high-dimensional finetuning. For low-dimensional linear probing, is special case of Theorem 2.2 (up to constants) with Ps = I,.. While in high dimension, an intrinsic oow-dimensional structure (e.g., Assumption 2.3 is
necessary for the effectiveness of data selection ?
'Notice that is the dimension of the finetuning parameter space. For linear probing in Section same the pre-trained representation dimension: but for general finetuning, can he much larger.
2.1 is the
'Notice that for lincar probing, f (x; 0) f (x: 0,) + Vafa (x; 0.)) 0 with Vof (x: 0,) の (x).
Therefore, the finetuning objective can be exactly formulated (2. and the excess risk of high-dimensional
lincar probing satisfies Thcorem 2.2 with x = n Φ (X) & (X) and ΣS = +. d (Xs)² á (Xs).
$ *Otherwise, if all directions Range Σ are equally important, with < r, 0s learned from Ds necessarily fails to capture the orthogonal complement of Range( ) and therefore E [ER (0s) n.
5

---

Assumption 2.3 (Low intrinsic dimension). Consider the second moment EΦ > O over 'D with N samples. Let F == min(t E [r] tr ( (x*)), S tr (I*) /N) be the intrinsic dimension. Assume that Ed has a low intrinsic dimension: F < min (
When the high-dimensional finetuning parameter space has a low intrinsic dimension F min (N,r), r). Theorem 2.2 can be further concretized with suitable Ds and associated S:
Corollary 2.3 (Exploitation + exploration (Appendix B.3
Under the same setting as Theorem 2.2
and Assumption 2.3 if S satisfies for some subspace S
C Range( Egg) with rank (Ps) and
cs 2 N that (i) Ps 25 Σ Ps > 0 and (ii) tr P
PS))
5)
N n
tr (r)),) then
E [ (0s) < variance + bias S n2
cgg + tr (20) 10.
(3)
In particular, with cs. 0 S L. 11..12 < 1, and tr( x T (depending only on the low intrinsic dimension), the generalization achieves a fast rate O(F/n). independent of r >>> r.
In B. (i) bias is reduced by exploring the parameter space for an S with small low-rank approximation error tr E P )= I 1 tr (E)); while (ii) variance is reduced by exploiting information in S through
moment matching, Ps (c Σ P ž O, where smaller ey means better exploitation.
3 Sketchy Moment Matching
A gap between Corollary and and practice is how to find a suitable S efficiently in the high-dimensional parameter space. In this section, we introduce a simple scalable algorithm for constructing S and Ds that satisfies the exploration and exploitation conditions in Corollary 2.3
3.1 Find Low Intrinsic Dimension via Gradient Sketching
For high-dimensional finetuning with >> ni, a critical limit of Theorem 2.2 and Corollary 2.3 is that the large moment matrices Ed Σg are not invertible, storable, or even directly computable, due to the prohibitive cost. As remedy, sketching 32) via Johnson-Lindenstraule is a classical dimensionality reduction strategy that gets increasing recent attention for gradient approximation in large-scale scale machine learning problems [16 34
transforms []]
Remark 3.1 (Gradient sketching). In the dime--die setting with > n, to reduce the dimensionality of the gradients G = Voj (X;0,) E Nxx with a low intrinsic dimension F & min (N,r r) (Assumption 2.3), we draw a Johnsson-Lindensttene Definition C.I r E Rrxi that projects the dimension-r gradients to lower dimension m. x T & TRRN Nxm. One of the most common constructions of JLT is the Gaussian embedding
transform [31y (JLT, formally in
G GG E (i.e., a Gaussian random matrix with i.i.d. entries Tsj ~ N 1/m) discussed in Lemmal C.3 vide Remark
for Remark[..Ifor
brief overview of various (fast) JLT's and their efficiency).
While sketching is known for preserving Fuclidean distances 31 and providing accurate low-rank approximations 17 32 33), whether gradient sketching can convert Theorem to an efficiently computable form without compromising the generalization guarantee? We answer this question affirmatively with the following theorem.
Theorem 3.1 (Main result II: gradient sketching (formally in Theorem C.I ). Under Assump- tion 2.2 and 2.3 with a low intrinsic dimension F < min rN,r), draw Gaussian embedding
I Rrxm (Lemma C.3) with m 11F. Let E := r I and ΣS := T I be the sketched gradient moments. For any Ds with n > m samples such that rank (ES) n., and the
[1.1r]-th largest eigenvalue sp1.1 (E)) 2 Is for some rs > 0, with probability at least 0.9 over I, there exists a > O where ( satisfies E [ER (0s) S variance + sketching error + bias
with (i) variance =
o² tr E E (),, (ii) sketching error o²
mss Σ 112ttr and
(iii) bias
1 -1 (Eg) tr Σ 10..1 12
We note that contrast to the classical slow rate O(1//n) in low dimension (when n r), ridge regression on Ds in the high-dimensional finetuning (with n < r) achieves a fast rate 0(1/n). This is granted by the now-rankness of >g. which enables a more fine ane-grained analysis of the regularization (vide Appendix B.3). We highlight a key nuance here: for fast influence function approximation in [16, 34), the gradient of the loss function is sketched, whereas in setting, we sketch the gradient of the pre-trained model f 0z).

---

If S further satisfies Σe cs g for some cs 2 N with m - max tr //s/ 11F),
E [ER (0s)] < variance + sketching error + bias S cs (o²m + (20) 10.
(4)
n
Comparing with (3 we observe that by controlling the variance with n < cs 3 in low
dimension m F < r, gradient sketching preserves the fast-rate generalization (mm/n) (
up constants. That is, gradient sketching implicitly finds random subspace S _ Range( (vide ( that satisfies the exploration assumption in Corollary [2.3] Meanwhile, the choice of sketching size balances the tradeoff between variance and sketching error: larger reduces the sketching error at the cost of higher variance. Such tradeoff is optimized
v /tr (E9)/78-
3.2 Control Variance via Moment Matching
Given the intrinsic low-dimensional structure with small bias in Section 3.1 Theorem 3.1 connects generalization to the variance controlled by the matching between ΣΦ and Σ S. Specifically, when the selected data Dy satisfies D es 2g for some es N. have tr Σ (Eg) cym and
| ) ll2 - es upper bounded, leading to the fast-rate generalization in
Algorithm 3.1 Sketchy Moment Matching (SkMM)
1: Input: f (:;0,), & N, m < n, cs E [N 1].
2: Draw (fast) Soannson-iidenstruuus transform I E R (Remark 3.1b
3: Compute gradient sketching G = Vol 0,
R Nxm (Remark
4: Compute the spectral decomposition of Σ = G G >
=AV where
(a) V [VI...., Vm] IR mm consists of the orthonormal eigenvectors, and
(b) = diag (A1,-.. Am) contains descending eigenvalues A 2 ... 2 Am 2 0.
5: Initialize s [s1,.... sN]] with 8; 1 on n uniformly sampled i's and s; 0 elsewhere.
x
6: Let diag(s) E RNN be diagonal matrix with s on diagonal. Optimizing:
m
min SEAN
min y 1Tm Jm.
VJ T diag (s) Gv, - "Yi X1)
JER
(5)
1=1
s.t. 0 5 s < L/nnii [N],
Nj 2 1/cs V E [m].
7: Output: S [N] by sampling data from E AN without replacement.
While directly minimizing tr (EEEEEE involves integer programming and pseudoinverse, causing hard and numerically unstable optimization, Σ6 & Eg has straightforward relaxation (vide Remark (.2), leading to the simple and stable moment matching objective (5) in Algorithm 3.1
Remark 3.2 (Relaxing De cs Ed
Given the spectral decomposition Σx -VAV,, Σ
S cs S can be rewritten as V G og AA and (5) is relaxation: (i) instead of enforcing
S < es S strictly, constraints are only imposed on the diagona 11 (GGGGs) 2 X//cs,
j E [m]; and (üi the selection of S is relaxed to a weight vector s E AN with linear constraints s; < 1/n. Free of integer constraints and pseudoinverse, the quadratic data selection objective with linear constraints in (5) can be solved efficiently and stably via projected gradient descent.
Alternative to the moment matching heuristic in Remark 3.2 variance reduction by controlling EΔ ($E))t in the low-dimensional subspace can be realized via various methods, including leverage score sampling [8 19 72 73, 74] and V-optimal experimental design [28 29 We provide brief discussions on these alternatives in Appendix A.2 A.2
Remark 3.3 (es controls strength of moment matching). In Algorithm 3.1 smaller es enforces Eg
to exploit more information in Σd, bringing lower variance and better generalization. While the lower bound cs could be tight (vide Remark B.Ty, in practice, the smallest feasible es depends on the data distribution and tends to be larger (e.g., C5 Rs 1 in the experiments).
"This is equivalent to assuming that 3 Σg commute. While such assumption does not hold in general, it is valuable heuristic whose effectiveness has been demonstrated in various domains [36] 37
7

---

Remark 3.4 (Computational efficiency of SKMM). SKMM is efficient in both memory and com- putation. Consider the two stages in Algorithm B. (i) Gradient sketching can be computed in parallel with input-xparsity time and on the fly without storing the (potentially) high-dimensional gradients (vide Remark C.T). (ū) After gradient sketching, variance reduction via moment matching happens in the low dimension m, with a low memory footprint (Nm), taking O(m²) for the spectral decomposition and mm) per iteration for optimizing the moment matching objective (
4
Experiments
4.1 Synthetic High-dimensional Linear Probing
To ground the theoretical insight on variance-bias tradeoff high-dimensional finetuning, we simulate linear probing with synthetic underdetermined ridge regression problem 12
Variance-bias bias balance
Bias reduction
Varianco reduction
SKMM, n-80, risk 3.00e-03
Adeptive, n-80, risk 3.51e-03
Uniform, n n-80, 80, risk 7.79e-01
60
40
%
20
-40
-40
-20
20
40
-40
-20
20
40
-40
-20
20
40
R-leverage, n=80,
K-center. n=80, risk=6.51e-03
Herding, n=80, 7.4k=7.400+02
60
40
7
20
Figure 2: Selecting = 80 data (colored in red) from the GMM dataset. Intuitively, a coreset Ds with low bias contains at least one sample per cluster, whereas a low-variance Ds selects more data from clusters with larger variance. We recall from Theorem 2.2 that the variance-biis biia balance is essential for good generalization.
Setup. We consider a set of N = 2000 samples with high-dimensional pre-trained representations 2400, modeled by a Gaussian mixture model (GMM) consisting of F 8
<(X) E Nxr well-separated clusters, each with random sizes and variances (vide Figure 2 Samples within each cluster share the same randomly generated label. We solve the ridge regression problem ( over the selected coreset of n samples with hyperparameter a tuning. The empirical risk is evaluated over the full dataset LD = N | (x))0s 21l2 (vide Appendix D.1 for implementation details).
Data selection. For SkMM (Algorithm 3.1.. we use sketching dimension m 47 = 32 and set cs = 0.999. We optimize 10 iterations and sample S from Ax with the lowest objective value.
(5) via Adam [5] with constraint projection under learning rate 10 for
We compare SkMM to representative unsupervised data selection methods for regression, including uniform, leverage score 18 19
72 73 74,, adaptive sampling 44 56), herding [51] 52), and
and ridge leverage score sampling (R- (evergge can be viewed as different ways of variance-bias balancing; (ii) adaptive sampling (Adapt ive) and k-center greedy (K center) focus on bias reduction (i.e., providing good low-rank approximatiin/Clusternng for o oX)); while (iii) Herding and uniform sampling (oom) reduce variance (vide Appendix D.2 for baseline details).
k-center greedy [53]. Specifically, (i) SKMM, truncated leverage score (T-levera
We observe from Figure 2 and Table T that balancing the variance- -ias tradeoff is crucial for the generalization of data selection in high dimensions. In particular, SkMM achieves the best empirical
12 Our experiment code is available http::://ithub.coom///// Paana///iiiaaaaaaataaaathh Pan/sketchy mooentt matchhng
8

---

Table I: Empirical risk (0) the GMM dataset various n, under the same hyperparameter tuning where ridge regression over the full dataset 'D with N = 2000 samples achieves LD O (0 2.95c-3. For methods involving sampling, results reported over 8 random seeds.
48
64
80
120
400
800
1600
Berding
7,40e+3
7.40=-2
7,40e+2
7.40e+2
7,38c+2
1.17ee2
2.95e-3
Unaform
2.
2
0.29
(3.13
0.140-3
(2.99
0.03
(2.96
0.00e-
00000)-3
R-center
(1.23 1: 0.400e22
(9.53
0.0022
(1.12
0.43)-2
(2:73
1880e22
(5.93
4.80e-2
01.18 066x-1
Adept live
(3x1 + 0.65)-3
(3.79
+ 1.37)-3
(4:83
+ 1.90p-3
(4.03
+ 1 355--
(3.40
0.67)-1
(7.34
197j--
(3.19
099---..0 -.166-1
7-1 eve rage
(0.99 + 1.65e=2
(3.3
+ 0499-33
(3.30
0.30je-3
(3.24
+ 0.141e3
(2.8%
0.00
(2.% 0.01ja3
(2.95 + 0.000-3
Rageverage
1.58)=3
043k-3
(3.25
0.31e3
(3.09 0.06x-3
(3.00
0.02e-3
(2.97
001x-3
0.00)-3
SKMM
0.51)e.3
(3.31 0.15e-3
(3.12 0.07e-33
(3.07 0.08
(2.98 0.02).33
(2.96 0.01)e3
0.00)-33
risk across different coreset sizes especially when is small. While as n/N + 1, uniform sampling provides a strong baseline, coinciding with common empirical observations 1
4.2 Experiments on Regression Tasks
We further validate the effectiveness of SKMM on UTKFace [7]. a real-world regression dataset for age estimation. We finetune randomly initialized classification head top of the feature representation of CLIP [50] with Adam [75] and learning rate 10 We also retain those baselines from the above synthetic setup in this experiment.
Table Mean Absolute Error (the lower the better) on UTKFace with a linear regressor trained on top of frozen features from pre-trained CLIP (ViT-B/32). We use the bold font to indicate the best method for each coreset size.
Method
100
200
500
1000
2000
3000
Uniform Sampling
10.55 1 3.09
3.448
6.09 1 0.42
4.70 0.23
3.92 10.16
3.68 0.15
Adaptive
6,02 0.53
0.14
1.40
N/A
N/A
N/A
Greedy
10.40 1.21
0.18
0.09
5.51 0.11
4.87 : 0.03
4.37 0.08
Herding
0.00
13.41
1.00
5.79
0.01
4.19 1 0.01
3.53 0.01
R-leverage
5.44 - 0.01
0.00
1.00
3,86
1.01
3.61 1 0.01
3.53 1: 0.04
SkMM
5.57 +: 0.38
4.70
4.22
4.02
3.54 0.19
3.25 - 0.10
The results for linear probing are provided in Table 2 where our method remarkably outperforms comparative baselines on FTCee For every coreset size, SkMM improves the performance of CLIP compared to uniform sampling. Especially for small coreset size n = 100, 200, it achieves a Mean Absolute Error reduction of approximately 50%.
4.3 Experiments on Image Classification Tasks
While analysis focuses data selection for finetuning regression models, natural question is whether the idea of SkMM applics to broader scopes. To answer this, we extend our empirical consider imbalanced classification task: Stanford- Cars (77] with 196 classes, 8144 training samples, and 8041 testing samples where the classes are highly imbalanced with training sample sizes ranging from 24 to 68.
investigation to classification. In partieular,
Finetuning. We consider two common ways of finetuning: (i) linear probing (LP) over the last layer and (ii) funetuning (FT) over the last few layers, covering both the low- (i.e., n 2 r for LP) and nigh-dimensional (i.e.,
for FT) settings. For LP, we learn the last layer over the embeddings from a CLIP -aee-pretaained ViT-B/32 (50) with learning rate of 100 For FT we finetuning the last two layers of an ImageNet--retrraned ResNet18 [84] with learning rate of 10-2 In both settings, we optimize via Adam for 50 epochs. Due to space limit constraints, detailed results for fine-tuning deferred to the appendix.
Data selection. For SKMM-LP, the gradients (of the last layer) are given by the pretrained features from CL.P. For SKMM-FT, the gradients (of the last two layers) are calculated based on a random classification head. We tune the sketching dimension m E {32, 64, 128, 256, 512} and the lower bound for slackness variables es E (0.6, 0.7, 0.8, 0.9}. Within suitable ranges, smaller m and larger es lead to better performance in the low data regime. Intuitively, smaller encourages variance reduction a more compressed subspace, and larger e, leads to easier optimization.
We notice that finetuning the last few layers of strong pretrained models like CLIP can distort the features and hurt the performance, studied in [83 Therefore, we stay with weaker pretrained model for finetuning.

---

Table 3: Accuracy and F1 score (%) of LP over CLIP StanfordCars
2000
2500
3000
3500
4000
Acc
67.63 + 0.17
70.59 + 0.19
72.49 + 0.19
74.16 0.22
15.40 + 0.16
Uniform Sampling
F1
64.54 + 0.18
67.79 1 0.23
70.00 : 0.20
71.77 = 0.23
73.14
Herding ST
Acc
67.22 + 0.16
71.02 + 0.13
73.17 # 0.22
74.64 = 0.18
75.71 :
68.28
70.64
72.22
73.26 0.39
Contextual Diversity
78
Acc
67.64 +:
70.82
72.66
74.46
F1
64.51 = 0.17
68.18 + 0.25
70.05 = 0.11
72.13 0.15
73.35 = 0.07
Glister 79
Acc
67.60 = 0.24
70.85 + 0.27
73.07 = 0.26
74.63 = 0.21
76.00 1:000:00 0.20
F1
64.50 + 0.34
68.07 + 0.38
70.47 + 0.35
72.18 0.25
0.24 73.69
GraNd h6
Acc
67.27 + 0.07
70.38 +: 0.07
72.56 + 0.05
74.67 = 0.06
75.77 0.12
F1
64.04 =
67.48 +
69.81
72.13
73.44 0.13
Acc
67.59 + 0.10
70.99 + 0.05
72.54 + 0.07
74.81 0.05
75.74 0.01
Forgetting 80
F1
64.85 = 0.13
68.53 + 0.07
70,30 + 0.05
72,59 = 0.04
73.74 = 0.02
Acc
67.77 = 0.29
70.73 + 0.22
73.24 + 0.22
74.57 = 0.23
75.71 0.15
DeepPool 81
64.16 +: 0.68
68,49 + 0.53
70.93
72.44 0.27
73.79 0.15
Acc
73.28
75.02
75.82
Entropy
F1
64.55 = 0.10
67,95 + 0.12
70.68 + 0.12
72.46 0.12
73.29 0.04
Acc
67.53 = 0.14
71.19 + 0.09
73.09 + 0.14
74.66 = 0.11
75.57 0.13
0.13
Margin
F1
64.16 + 0.15
68.33 +: 0.14
70.37 + 0.17
72.03 + 0.11
73.14 :: 0.20
Leust Confidence 82
Acc
67.68 + 0.11
70,99 + 0.14
73.04 + 0.05
74.65 + 0.09
75.58
0.08
F1
64.09 + 0.20
68.03 +
70.30
72.02 0.10
73.15 0.12
SKMM-LP
Acc
68.27 + 0.03
71.53 1 0.05
73.61 0.02
75.12 0.01
76.34 0.02
F1
65.29 + 0.03
68,75 + 0.06
71.14 + 0.03
72.64 0.02
74.02 0.10
We compare SkMM to various unsupervised and (weakly) supervised data selection methods for
classification, including uniform sampling, herding [51], Contextual Diversity [78). Glister [79].
GraNd [66], Forgetting 80) DeepFool [81. as well as three uncertainty- methods, Entropy,
Margin, and Least Confidence [2).
Observations. We first observe that for both LP (Table 3 and FT (Table SkMM achieves competitive finetuning accuracy StanfordCars. Since SkMM is an unsupervised process agnostic of true class sizes, the appealing performance of SkMM on the imbalanced StanfordCars dataset echoes the ability of SkMM handle data selection among clusters of various sizes through variance- bias balance (cf. synthetic experiments in Figure 2). Meanwhile, for LP in the low-dimensional setting (Table 3) uniform sampling provides surprisingly strong baseline. This coincides with the theoretical insight from Proposition 2.1 and the empirical observations in .
5 Discussion, Limitations, and Future Directions
We investigated data selection for finetuning in both low and high dimensions from a theoretical perspective. Beyond variance reduction in low dimension, our analysis revealed the variance-bias tradeoff in data selection for high-dimensional finetuning with low intrinsic dimension F, balancing which led to a fastt-raa raae generalization (F//n). For efficient control of such variance-biat tradeoff in practice, we introduced SkMM that first explores the high-dimensions gradient sketching and then exploits the resulting low-dimensional subspace via moment matching. Theoretically, we showed that the low-dimensional subspace from gradient sketching preserves the fast-rate generalization. Moreover, we ground the theoretical insight on balancing the variance-bias tradeoff via synthetic experiments, while demonstrating the effectiveness of SkMM for finetuning real vision tasks.
parameter space via
In this work, we focus only on moment matching via optimization inspired by the analysis for variance reduction after gradient sketching. Nevertheless, there is remarkable variety of existing low-dimensional data selection strategies (e.g., via greedy selection or sampling) that could potentially be extended to high dimensions leveraging sketching as an efficient pre-processing step. In linear algebra, sketching has been widely studied for accelerating, as well as stabilizing, large-scale low-rank approximations and linear solvers. However, the intuitions and theories there may or may not be directly applicable to the statistical learning regime. light of the high-dimensional nature of deep learning where sketching brings an effective remedy, we hope that providing a rigorous generalization analysis for sketching in data selection would make a step toward bridging the classical wisdom of sketching and the analogous challenges in modern learning problems.
10

---

Acknowledgments
The authors wish to thank Yunzhen Feng, Julia Kempe, and Christopher Musco for insightful discus- sions. QL was partially supported by the NYU Research Catalyst Prize and the Department Energy under ASCR Award DE-SC0024721. YD was supported by the NYU Courant Instructorship.
References
[1] Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selection in deep learning. In International Conference Database and Expert Systems Applications, pages 181-195, Springer, 2022.
[2] Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang, Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong. selection for language models. arXiv preprint urXiv:2402.168// 2024.
survey on data
[3] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 1e:11922-11558 2022.
[4] Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu, Mingming Sun, and Ping Li. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.09329, 2022.
[5] Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric coreset selection for high pruning rates. arXiv preprint arXiv:2210.158000 2022.
[6] Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate coreset: universal method of data selection for real-world data-efficient deep learning. In The Eleventh International Conference on Learning Representations, 2022.
[7] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning, pages 6950-6960. PMLR, 2020.
[8] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33:14879- 14890, 2020.
[9] Krishnateja Killamsetty, Xujiang Zhao, Feng Chen, and Rishabh Iyer. Retrieve: Coreset selection for efficient and robust emiisuuprvised learning. Advances in neural information processing systems, 34:14488 1448841445151,, 2021.
[10] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, et al. Laion- 5b: An open large-scale dataset for training next generation image-text models. Advances in 2022.
Neural Information Processing Systems,
[11] Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang, Jonathan Hayase, Georgios Smyrnis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. Advances in Neural Information Processing Systems, 36, 2024.
[12) Yiping Wang, Yifang Chen, Wendan Yan, Kevin Jamieson, and Simon Shaolei Du. Variance alignment score: A simple but tough-to-heat data selection method for multimodal contrastive learning, arXiv preprint arXiv:2402.02203 2024.
[13] Siddharth Joshi, Arna Jain, Ali Payani, and Baharan Mirzasoleiman. Data-efficient con- trastive language-image pretraining: Prioritizing data quality over quantity. arXiv preprins 1rXiv:2403.12267, 2024.
[14] Armen Aghajanyan, Luke Zettlemoyer, and Sonal Gupta. Intrinsic dimensionality explains the effectiveness of language model fine-tuning, arXiv preprint arXi::0012.13255, 2020.
11

---

[15] Sachin Goyal, Pratyush Maini, Zachary C Lipton, Aditi Raghunathan, and J Zico Kolter. Scaling laws for data filtering data curation cannot be compute agnostic. arXiv preprint arXiv:2404.07177, 2024.
[16] Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. Less: Selecting influential data for targeted instruction tuning. arXiv preprint arXiv:2402.04333 2024.
[17] David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157. 2014.
[18] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS'06) 066), pages
143-152. IEEE, 2006.
[19] Ahmed Alaoui and Michael W Mahoney. Fast randomized kemnel ridge regression with statistical guarantees. Advances in neural information processing systems, 28, 2015.
[20] Garvesh Raskutti and Michael W Mahoney. A statistical perspective randomized sketching for ordinary squates Journal of Machine Learning Research, 17(213)1-31, 2016
[21] Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Conference Learning Theory, pages 663-695. PMLR, 2019.
[22] Brett W Larsen and Tamara G Kolda. Sketching matrix least squares via leverage scores estimates. arXiv preprini arXiv: 10638 2022.
[23] Michat Dereziński, Manfred K Warmuth, and Daniel Hsu. Unbiased estimators for random design regression. Journal of Machine Learning Research, 23(167): 2022.
[24] Atsushi Shimizu, Xiaoou Cheng, Christopher Musco, and Jonathan Weare. Improved active learning via dependent leverage score sampling. arXiv preprint arXiv:2310.04966 2023.
[25] Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical science, pages 273-304, 1995.
[26] Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
[27] Valerii Vadimovich Fedorov. Theory of optimal experiments. Elsevier, 2013.
[28] Yining Wang, Adams Wei Yu, and Aarti Singh. On computationally tractable selection of experiments in measurement-constraiiee regression models. Journal of Machine Learning Research, 18(143):1 -1, 2017.
[29] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimiza- tion for experimental design: regret minimization approach. arXiv preprint 171.4.1711.05144. 2017.
[30] Madeleine Udell and Alex Townsend. Why are big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 1(1):144-160, 2019.
[31] William B Johnson. Extensions of lipshitz mapping into hilbert space. In Conference modern analysis and probability, 1984, pages 189-206, 1984.
[32] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217-288, 2011 1.
[33] Per-Gunnar Martinsson and Joel A Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29:403-572. 2020.
[34] Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclere, and Aleksander Madry. Trak: Attributing model behavior at scale. arXiv preprint arXiv:2303.14188 2023.
12

---

[35] Michal Cerný and Milan Hladík. Two complexity results on c-optimality in experimental design. Computational Optimization and Applications. 51(3):1397-1408. 2012.
[36] Helge Blaker. Minimax estimation in linear regression under restrictions. Journal of statistical planning and inference, 90(1):35-55 55, 2000.
[37] Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In International Conference on Machine Learning, pages 6164-6174, PMLR, 2021.
[38] Michael W Mahoney and Petros Drineas. Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106(3):697-702, 2009.
[39] Amit Deshpande, Luis Rademacher, Santosh S Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. Theory of Computing, 2(1):225 247, 2006.
[40] Sergey Voronin and Per-Gunnar Martinsson. Efficient algorithms for cur and interpolative matrix decompositions. Advances in Computational Mathematics, 43:495-516, 2017.
[41] Michal Derezinski and Michael W Mahoney, Determinantal point processes in randomized numerical linear algebra. Notices of the American Mathematical Society, 68(1):34-45 2021.
[42] Michal Derezinski, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and a multiple-deseent curve for column subset selection and the nystrom method. Advances in Neural Information Processing Systems, 05:4953-49644 2020.
[43] Yijun Dong and Per-Gunnar Martinsson. Simpler better: a comparative study of randomized pivoting algorithms for cur and interpolative decompositions. Advances in Computational Mathematics, 49(4))66, 2023.
[44] Yifan Chen, Ethan N Epperly, Joel A Tropp. and Robert J Webber. Randomly pivoted cholesky: Practical approximation of a kernel matrix with few entry evaluations. arXiv preprint wwXiv:2207.06503, 2022.
[45] Yijun Dong, Chao Chen, Per-Gunnar Martinsson, and Katherine Pearce. Robust blockwise random pivoting: Fast and accurate adaptive interpolative decomposition. arXiv preprint arXiv:23309 6000, 2023.
[46] Katherine J Pearce, Chao Chen, Yijun Dong, and Per-Gunnar Martinsson. Adaptive paral- lelizable algorithms for interpolative decompositions via partially pivoted lu. arXiv preprint a3Xiv:23 10.09417, 2023.
[47] Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 563-568, 2008.
[48] Kai Yu, Jinbo Bi, and Volker Tresp. Active learning via transductive experimental design. In Proceedings of the 23rd international conference on Machine learning, pages 1081-1088, 2006.
[49] Neta Shoham and Haim Avron. Experimental design for overparameterized learning with application to single shot deep active learning. IEEF Transactions on Puttern Analysis and Machine Intelligence, 45(10): 766--17777 2023.
[50] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning. pages 9748-8763. PMLR, 2021.
[51] Max Welling. Herding dynamical weights to learn. Proceedings of the 26th annual interna- lional conference on machine learning, pages 1121-1128, 2009.
[52] Yutian Chen, Max Welling, and Alex Smola. Super-samples from kerel herding, arXiv preprint arXiv:1203.3472. 2012.
[53] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: core-set approach. arXiv preprint arXXiv1708..00 00489, 2017.
13

---

[54] Samprit Chatterjee and Ali S Hadi. Influential observations, high leverage points, and outliers linear regression. Statistical science, pages 379-393, 1986.
[55] Petros Drineas, Michael W Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2):219- 2011.
[56] Amit Deshpande and Santosh Vempala. Adaptive sampling and fast low-rank matrix approxima- tion. International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 292-303. Springer, 2006.
[57] Germain Kolossov, Andrea Montanari, and Pulkit Tandon. Towards a statistical theory of data selection under weak supervision. arXiv preprint arXiv:2309. /4563, 2023.
[58] Dennis V Lindley. On measure of the information provided by an experiment. The Annals of Mathematical Statistics, 27(4):986-100 1005, 1956.
[59] H Sebastian Seung. Manfred Opper, and Haim Sompolinsky. Query by committee. In Pro- ceedings of the fifth anmual workshop on Computational learning theory, pages 287-294, 1992.
[60] David D) Lewis. A sequential algorithm for training text classifiers: Corrigendum and additional data. In Aem Sigir Forum, volume 29, pages 13-19. ACM New York, NY, USA, 1995.
[61] Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. Advances in neural information processing systems, 31, 2018.
[62] Hai Ying Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression, Journal of the American Statistical Association, 1 113(522):829 844, 2018.
[63] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David Woodruff. On coresets for logistic regression. Advances in Neural Information Processing Systems, 31, 2018.
[64] Tung Mai, Cameron Musco, and Anup Rao. Coresets for cuassification-ssmpliiii and strength- ened. Advances in Neural Information Processing Systems, 34:1 1643-116544 2021.
[65] Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David Woodruff, and Michael Wunder. Data-efficient learning via clustering- based sensitivity sampling: Foundation models and beyond. arXiv preprint 17327 2024.
[66] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34:20596-20677, 2021.
[67] Angela H Jiang. Daniel L-K Wong, Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary Lipton, al. Accelerating deep learning by focusing on the biggest losers. arXiv preprint 191.v:1910.00762. 2019.
[68] Kailas Vodrahalli, Ke Li, and Jitendra Malik. Are all training examples created equal? an empirical study. arXiv preprint arXiv: 18/ 125669, 2018.
[69] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference on Leurning Representations.
[70] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2/06.09663 2021.
[71] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[72] Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan. Relative-error cur matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30(2):4448811, 2008.
14

---

[73] Mu Li, Gary L Miller. and Richard Peng. Iterative row sampling. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 127-136. IEEE, 2013.
[74] Michael B Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1758-1777. SIAM, 2017.
[75] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXi: 2014.
[76] Zhifei Zhang, Yang Song, and Hairong Qi. Age progression/regression by conditional adver- sarial autoencoder. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5810-5818, 2017.
[77] Jonathan Krause, Jia Deng, Michael Stark, and Li Fei-Fei. Collecting large-scale dataset of fine-grained cars. 2013.
[78] Sharat Agarwal, Himanshu Arora, Saket Anand, and Chetan Arora. Contextual diversity for active learning. In Computer EsiionECCY 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XVI 16, pages 137-153. Springer, 2020.
[79] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based data subset selection for efficient and robust learning. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8110-8118, 2021.
[80] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint 1rXiv:1812.051133 2018
[81] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2574-2582 2016.
[82] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint arXiv: 1xkiv:/906, 1906. / 1829, 2019.
[83] Ananya Kumar, Aditi Raghunathan, Robbie Jones, Tengyu Ma, and Percy Liang. Fine- tuning can distort pretrained features and underperform out-of-distribution. arXiv preprint arXiv:2202.1005. 2022.
[84] Kaiming He, Xiangyu Zhang, Shaoging Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[85] Roman Vershynin. High-dimensionn probabilityy An introduction with applications data science, volume 47. Cambridge university press, 2018
[86] Martin J Wainwright. Hime-dime statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[87] Daniel Kane and Jelani Nelson. Sparser johnson- transforms. Journal of the ACM (JACM), (1(1):1-23, 2014.
[88] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium Theory of computing, pages 604 613, 1998.
[89] Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pages 117-126. IEEE, 2013.
15

---

[90] Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation matrices. Applied and Computational Harmonic Analysis, 25(3):335- 366, 2008.
[91] Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02): 111-1115--6111 126, 2011.
[92] Kazushige Goto and Robert Van De Geijn. blas. ACM Transactions on Mathematical Software (TOMS), 35(1):1-14, 2008.
implementation of the level-3
[93] Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 91-100, 2013.
[94] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[95] Michael Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-sevnnth annual ACM-SIAM symposium Discrete algorithms, pages 278-287) SIAM, 2016.
[96] Joel A Tropp, Alp Yurtsever, Madeleine Udell, and Volkan Cevher. Fixed-rank approximation of a posidiie-semidefinite matrix from streaming data. Advances in Neural Information Processing Systems, 30, 2017.
[97] Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 62(12): 1707-1999
[98] Daniel B Szyld. The many proofs of an identity the norm of oblique projections. Numerical Algorithms, 42:309-323, 2006.
16

---

A Additional Discussions
A.1 Additional Notations
Given any matrix A E RR'd along with indices E [n]. j E [4], I S [n], and J S [d]. let [A], [A] be the jith entry of A, [A]; be the i-th row (or the i-th entry if A E R= is a vector), and [A] J.s be the j-th column; A₃ = [A], consists of rows in A indexed by I; and let AI,J = [A],,] be the submatrix of A with rows indexed by and columns indexed by J.
A.2 Alternatives to Moment Matching Heuristic in Remark 3.2
In addition to the moment matching heuristic in Remark 3.2 variance in the resulting -i--immensioal
subspace from gradient sketching can be controlled by > (Eg) via alternative methods like leverage
score sampling and V-optimal experimental design.
Remark A.1 (Leverage score sampling). Leverage score sampling 188 19
73
74] provides
arguably one of the most intuitive ways for selecting data based on E R.Nxm. In particular. fI7 drawn i.i.d. with replacement via leverage score sampling over G, cy S (1+ m with probability at least
Theorem 17] implies that for coreset of size at least n. 92(m log(m/5)e
T&N
where Ts E [0, 1] the minimum leverage score of G over the coreset S can render the upper bound of cs vacuous when T5 + 0.
14 Such dependence on TS
Nevertheless, when Ts is reasonably large, leverage score sampling based on G can be computed more efficiently than SkMM in ONNm²) time and can provide good control cg. While both SKMM and leverage score sampling can facilitate variance reduction in the dinedimensiona subspace, SKMM provides better empirical performance (cf. Section 4.1) slightly higher cost in the low intrinsic dimension m. (vide Remark 3.4 as il is tailored for optimizing moment matching.
Remark A.2 (V-optimal experimental design). Variance in the low-dimensional subspace can also be controlled by applying the V-optimal experimental design methods [28] 29 G E Nxm. For example, (29] provides a polynomial
algorithm to find a (1 + e)-esiimation of the V-optimal design for G with a coreset of size at least = [(me and cs is effectively controlled by the V-optimality criterion tr " (EE)))
While such V-optimal design methods can provide good control over cs with nearly optimal sample complexity, they are computationally more expensive than SKMM (or leverage score sampling) and tend to suffer from numerical instability issues in practice. For example, the algorithu in (29) consists of two stages: (i) solving continuous relaxation of the original discrete optimization problem posed by V-optimality, and (ii) rounding the continuous solution via regret minimization. While the cost of rounding is negligible, solving the continuous relaxation of V-optimality (in contrast to leveraging fast and stable heuristics like the one in SkMM, cf. Remark 3.2) is challenging, both in terms of computational complexity and numerical stability.
B Proofs for Section 2.1
B.1 Proofs of (I)
Proof of (1) and beyond. Under the assumption rank (6 (Xx)) = r, both Φ (Xx) & (X) have full column rank. Therefore & (Xs)) Φ (Xs) = o (x)' & (X) = I,, and Os ob (Xx)) ys. Then, since
y = (X) 0, + z and ys = Φ (xg) 0. + ng, we have
0g - 0. = ò ys - 0. = (xs) ò (Xs) O, - 0.) + (Xs) us = o (Xs) zs
14 NNttiee that appears because samples in S are equally weighted in the data selection setting, in contrast the standard leverage score sampling where samples weighted by the respective sampling probabilities.
17

---

which leads to
E ER (0s)) = E 11 (x) (0s -0)
(x)) o (xx) 6 (Xxs) [ (x(x)) ")
x (x() o (xxs)
=0²
2 tr
Now we explain the necessity of assuming es 2 n/N for Ed o cs
Remark B.1 (Lower bound of es). Since (X) à (X) x o (Xs) & (Xs), we observe that NE 7 n. which implies Σ 7 N L. Therefore, E * es Di is only possible when es 2 n/N.
Notice that this lower bound of es is light, e.g. when G consists of N rows of zeros.
Low-dimensional linear probing with moment matching. Recall from TT that E [RR (0s)]
4 Σ3 ) Further assuming suitable selection of Ds with E Co Eg. have
o² tr
tr E [S -1 S esst (I,) csT
o²r and therefore, E ER (0s)) S cs
n
B.2 Proof of Proposition
2.1
Proof of Proposition 2.7
Let ES == (Σ*)
-1/2
The goal of Σd $ os Eg can be
re-expressed as 6g E >
I,., or equivalently when cs
1,
S With uniform
sampling, since
Es
ΣS = Es
Σ XES
+ (X) Φ
(x)
Ex (X) (X) (x)
Σd
n
I, For any fixed unit vector z 5- let Z, =T (20)) -1/2 Φ (x:) be
we have Eg >>
random variables with randomness on i [N]. Since [[x(x)]1 S Bg D and Σd > 7I, we observe that
Zz <
1/2 Σ
(xx
B Φ <
Vie [N]
bounded. Therefore, Z, is
SubGaussian, and
(Z3 E
[z+]
2
Σ I, is
B2 16 -uuexponential. Then, by Bernstein's inequality
83 Theorem 2.8.2 86
Section 2.1.3), for
any < 6 S 16B3/r
e72
z
ΣS
I
z z 9 $
exp
16 B
(6)
By recalling that |S I, can be extended to the entire unit sphere g through e-net argument follows. Recall that for
Equation ( for a fixed z E Sr { I,
= max u
18

---

any E2 > O, there exists an Eg-net 2 C gr-1 such that [
11 + 2)
Then, by the union bound,
Gr2
P
max u ued/
(Si - 1, u > 61
S 1 1
exp
2
16
2
= exp
rlog
1
6
162 B
That is, with probability at least 1 8, maXuel u
( - Ir)
u
S E1 when
512B4 @ 2 T2
2
+ log ( )
rloo
1
62
By the construction of the e2-net U for all v E S"-1, there exists u E U such that | - 11vl222- S c2. Therefore, for any E S"11, we have
Σ
=u T
S0 I,
u u (v - u) (SS
( ( 1.) (v (v- u) -u) T (53 - -I,) u
Se +
So I
(c) + 202),
which implies
واا - I
$ f 2- By taking as small constant (e.g., <2 = v3/2 1),
| I,
we have
< 1
when
cs
B1 r log (1/8) n 2
72 (1 1/cs)/
B.3 Proof of Theorem
2.2
Proof of Theorem 2.2 With 3
1 TG, we have
E |R (0s)
E
1 N
G (0s 0.)11 E [[10s 0.1
Observing that by the optimality of Os. we have
G (Gs0s ys) + 2a0s 0,.
Recalling that DS = G Gs, this implies
02 = G Gs + al,
GGyys
"
L + al,)
G (Gs0, + +2s)
ES aI,
ESO. 1
(
[ + aI,)
GJZs.
n Therefore, with Eg [z] ON. E ER (0s)] can be decomposed the bias term and variance terms as follows:
ER (0s)] = |0s - 0. 1
2 (((22
+ aI,) )
ESz I,
0, +
cg + al,)
Σ
((xg + al, -1
12
Σg I 0,
+ Ez
G52s E + aa,))
n
Σ
Bias
Vuriance
19

---

Since Ez [2szs] < o the variance term can be bounded as
Variance
tr y + aI,)) -1
E
IS + al,) =al,)²
tr o و + al,) a )
where the second inequality follows from the fact that
(>g + al,)
adl,
11.
Recall that Ps E I2"x is an orthogonal projector onto any subspace of Range [ and Ps = L Ps is the orthogonal projector onto its orthogonal complement. By observing that Eg + aI, > P + aP g, since Range (Ps) 1 Range (Ps),, we have
nS + aII, aI.)'' & (P&DPPS) + -p.
a
Therefore,
d² ir Edd (PSD)Ps)) + ir (
Variance S
n
For the bias part, we first observe that
-1 Eg + at,)) +al,)
IS a (>g + +ol.)
I,
Therefore.
Bias- = |1(23 + +aI,)
-1 DS I, 0.
-1.00.
|a DS + a -1 '0.0
D
D
=02 2 Ir
E + oI,)
E Ed +al,) 0.0,
" D + aI, -2) 100112
<a² tr
Since
[g + aI.)
> (P&ISPS + aII,)
> 2a P&ESPs + a S. we have
E +
(P3DPPs)
1 P
x 2a
and thus
a tr
(PSISPs)) - ) 110.12.
Bias <
2
Combining the bias and variance terms, we have
~ σ²
(PsIPPs) )))
1 tr (
E ER
(0s)]
tr
a
n
(PSEPS) )) tr (M 100 2
+
tr
6d
(PSDEPs)
+ (2 110113
n
10.11 tr r (P<IgPs)) )')
tr
( +
2
20

---

( (10211
E (PSDIPs) ')) we have
By taking a, V
x² tr (DPP')
110.12 tr Ee (PSEPS)) )
1 8²
tr (E)PA) ta,
a, n
2
0²
10.12 tr Ed (PSDEPs))
2
tr
0² tr
(PSEPPS) + (E 10.13)
< 2
Ed
n
Therefore overall, we have
20 tr E ER (0s)]
nd (PsDNPs)) + 2tr (M* 110.12.
Proof of Corollary 2.3
Given (s - PS d and rank (Ps) x T. the variance term is
asymptotically upper bounded by
20²
Ed (PSDEPs))
o²
variance
S
esT. .gT.
Meanwhile, given tr( S term can be asymptotically upper bounded by
t (T)) and Er E
( S (E+) /N, the bias
2 Lr (E*) 0..
bias 2tr (E 00.
n
The result follows from Theorem 2.2 by combining the variance and bias terms.
C Proofs for Section 3.1
C.1 Formal Statement and Proof of Theorem 3.1
Theorem C.1 (Formal version of Theorem 3.I). Under Assumption 2.2 and 2.3 small intrinsic dimension F & min NNr}, for any 8 E (0, 1), draw a Gaussian random matrix T E Rrxm with i..d. entries from N (0, 1/m) where x k for some k 2 1.1F. Let Σ r T and ES = I I be the sketched gradient moments. For any S C [N] with
samples such
that (i) rank(2 ΣS) = n, and (ii) the k-th largest eigenvalue 8y ( 2 7s for some is > 0, with
probability least 8 over there exists a O where (2) satisfies
0²
E ER (0s)]
tr
(5S)
(variance)
+ 2²
1
tr (Σ+) 50 (5
(sketching error)
n mys
1
3 tr (Σ*) 1
(bias).
If S further satisfies $0 - Cg Eg for some cs 2 No taking m = max (E0))//, leads
EE (0s)) & variance + sketching error + bias S cs (0 (o'm+tr(2 + tr (IO) ||0.
(8)
n
We start by introducing some helpful notations for the proofs. Let G Vof (X; (X;
E R Nxr and
G5 G g E x be the original gradients of and Ds. respectively. Recall that n G G/N and ف G Ggg/ are the corresponding second moments.
We consider Lainsonn-indesstrauss transform (JLT) 31 r E rx" as follows:
21

---

Definition C.1 (JLT [88] (adapting 17 Definition 3})), For any <> 0, E (0,1), and n N. xm random matrix I E R is a (c, wow.lloonsoo-nnnnnnttttnnn transform ((c, (, k)-JTT) for any
UE I consisting of k orthonormal columns in R,, with probability at least
- TurruUu Se.
Definition C.2 (JL second moment property 187 (adapting 11 Definition 12))). For any e > 0, ò E (0, 1), random matrix r Rrxm satisfies the (e, ()- second moment property if
(IIT ull2 12-11 11- $ 20 VuES
Lemma C.2 (Approximated matrix-matric multplication 88 (adapting 17 Theorem 13])), Given 0, E (0, 1/ 122, and a random matrix I E <R= satisfying the (e, -eco moment property (Definition C.2) for any matrices A, B each with r rows,
Pr ||| T A A > 3E A
B s 6.
One of the most classical constructions of a JLT with JL second moment property is the Gaussian embedding:
Lemma C.3 (Gaussian embedding [1 Theorem 6)). For any >> 0, E (0,1), Gaus-
sian random matrix r E R with i..d. entries Tij ~ (0/) (i) is a (c, 6, k) --L if m Z (k + Log(1 =2; and (ii) satisfies the (e, 5)-. second moment property if Z 28-1
Proof of Lemma C.3 The (c, 6, k)-JLT condition follows directly from Theorem 6].
To show the (f, 6)-1I second moment property, we observe that for any E S | u 1|
u JJTTT is average of m independent x² random variables with mean and variance 2, we have
u [ 1 and its variance is E (II 1 -1) ]]] 2/m. Therefore, m 2 226-1 leads
E
to the (e, 6)-L second moment property.
transforms). While we mainly focus on the Gaussian embedding the analysis for simplicity, there is rich spectrum of JLTTs with the JL. second moment property 188 89 90 9I1. some of which enjoy remarkably better efficiency than the Gaussian embedding without compromising accuracy empirically. We refer interested readers to [17 32 33) for in-depth reviews different JLTs and their applications, while briefly synopsizing two common choices and their efficiency as follows.
Remark C.1 ((Fast)
(a) Subgaussian embedding [88] is random matrix I E Brxm with i..d. entries from zero- mean subgaussian distribution with variance 1 1/m. Common choices include the Rademacher distribution and Gaussian distribution (i.e., Gaussian embedding).
Applying subgaussian embeddings takes ( A )m) & ((Nrm) time, while the involved matrix-matrix multiplication can be computed distributedly in parallel leveraging the efficiency of Level 3 BLAS (92). In practice, generating and applying Rademacher random matrices tend to be slightly faster than Gaussian embeddings due to the simple discrete support.
N X matrix A with mnz(A) NT nonzero entries
(b) Sparse sign matrix {89
931 is a sparse random matrix r = V
E ET E
with ii.d. rows "/ E Rd each consisting of È non-zero entries at uniformly random coordinates filled with Rademacher random variables. When E 1, I is known as CountSketch 1949 and requires as many as m = (k2) columns to satisfy the JLT property with constant distortion. Increasing the sparsity slightly, (95] showed that m Ok k) is sufficient for constant- distortion JLT when = Olog k). In practice, [96] suggested that a small constant sparsity & 2 8 is usually enough for many applications like low-rank approximations.
The sparse sign matrix can applied to an N x r mairix with nnz(A) nonzero entries in O(niz( A ) S O(Nrg) time, independent of the sketching size With careful implementation, sketching via sparse sign matrices can be significantly faster than the subgaussian embeddings in practice 33 43).
22

---

Let G == GT E R Nxm and G5 = GGT E Rexm be the sketched gradients such that
E G
G - - Gs/n E R=
In particular, for Gaussian embedding r, when (ank(>)) rank(Gs) = n1 rank Es) rank(G = m almost surely.
Recall the low intrinsic dimension F from Assumption 2.3 For any &e E N with 1.17 S k < m, let Ps E Rx be an orthogonal projector onto a dimension-k subspace S S Range( (
Ps- ==
= (
and - -. be its orthogonal complement. Throughout the proof of Theorem C.1 we assume the following:
Assumption C.1. Let min (N.r)
n > k 2 1.1r such that rank Egg We consider
Gaussian embedding (Lemma C.3
r
E
R xm with m x k such that sk (Eg) 2 7s for some ns >
Proof of Theorems
3.1 and C.1
We first recall from Theorem 2.2 that
20²
tr Σ (PsEgPs)) )) 2tr (E 10-12
E ER (0s)] I
Lemma C.4 suggests that for m x k/6, with probability at least 1 - 8/2,
tr " (PoDDPs) )) St (5 + n tr (I'P!)
mys
Therefore,
o²
tr (59
02 ( +100,1) tr (EOPS).
E
ERR (g)]
n
mys
Then, applying Lemma C.7 with the union bound, we have
tr )
デ 13 tr (I*))
n
with probability at least
8. This implies
E |R (0s)
tr
ΣΦ
+
tr (r(3*)
n
mns
tr (x 110.12-
n
If S further satisfies D Cs
n for some cs 2 N then we have
tr S ( S tr (こ))) < csm,
| 1
scs. Scs.
Therefore, can be further simplified as
csa"
tr (20) mys
E ER (0s))
(Σ)) 110.112.
n
On the right-hand-side, the first (variance) term is minimized at m = vtr (E*)/s where m + tr (Σ*) (myys) < 2 2 (E*) //s- 2m. In addition, incorporting the assumption that m x k/8 for some 2 1.17, we take m = max / tr //s)/ 1.1F/8} and get
2 2
m + CS tr ) ||0 1|
cs (o'm + tr (Σ*) 110.12)
E ERR (0s)]
Theorem 3.1 is simplified from Theorem C.I by taking A [1.17] and 8 0.1.
23

---

C.2 Upper Bounding Variance
Lemma C.A. For any å E (0, 1), let T E Rr be a Gaussian embedding (Lemma C.3) m k/6 columns. Then, with probability least over r,
with
tr E (PSDEPs) S (D (3g))
+ n tr (IOP.). mys
Proof of Lemma
C.4 We first observe that since rank (E3) implies Gs = In. = (Gs)k:
GsPs G5G. ( (Gs) GsT = (Gs)
and therefore, G zeRNin |Z|| s.t. Z E argminz | | GGZGGB
5 sl
and
G(G argmin |||| s.t. Z E argmin II(G ZGsPs)DIj
ZER
Xm
z
an approximated solution from sketched least square problem.
Accuracy of sketched least square residual. For m x k/(e"0), Lemma C.3 implies that Gaussian embedding I is (1/2, 6/2, k)-JLT (Definition C.I with (O(e/vk). 8/2)-JL second
moment property (Definition C.2) Then, since rank (GsPs k, by Lemma C.5 with probability at least 1 - over r,
[[ G&Ps s - (GGPP)
Since GsPs = GGG (G))
(GsPs) (GsPs)
G
Gs Ps.
Therefore,
(C(GsPs)--GCC - ((G))))) GsPs 2
22| 2
(10)
Accuracy of sketched least square solution. first observe from (I0) that
To upper bound
G(GsPs) ( G
< 2 |
GsPsG = (Gs) (Gs) GsG.. Since rank (Gs) n, Lemma C.6 implies that for Gaussian
embedding r, GsG. 0 m GsIT
GJ with high probability. Therefore,
m GsPs > 0 (m) G = o (m) (Gs)
Recall that (5g) = (G))) (GS) and (5g) 2 7s. we have
[|s 112 = GG || o (=))
( (GG))((Gs))
m7s
Therefore, applying union bound gives that with probability at least 1 - 8 over T,
?
G(GGPs)* - GG 50
||GP
(11)
mys
To upper bound || s) p. we observe that by
| <2 G
G
+2
|
?
|
mys
24

---

Finally, normalizing by multiplying n/N on both sides gives
') S tr { (5S)))) + + (E
Σ
P PSSSPP
mys
Taking any small constant 0 completes the proof.
Lemma C.5 (Adapting 17 Theorem 23]). any and 5 (0, let E R b (1/2, 8/2, k))JLT (Definition
C.1 with (O(e/ ////kk),, 8/2)J second moment property (Definition C.2 k and B E IX*N let
Given A E R with rank
W argmin
|| s.t. W argmin | (AW -B)I WER"XN
W. argmin |W]
2
P s.t. W argmin
AW BlE
WER
W
Then, with probability at least 8 o,
A(W W.)
SellAW. BB|
Analogous the proof of 17 Theorem 23), let A QR be a reduced QR decomposition of A such that Q Te*k is an orthonormal basis for Range(A), and R R
Proof of Lemma
Reparametrizing Z R.W and Z. RW., .. up to constant scaling of it is sufficient to show
Q(2 z.) = || z.11 0 QZ. - -Bl
Since r E Rrxk an (1/2, 6/2, k)-IIT we have | - - T 0112 $ 1/2 with probability at
least 1 - 8/2 and
|| Z.
Q rr T Q( -
Q rr
Q(Z -Z.) -Z) Z.)
Q TTT Q Z.
+ I Q rr Q112
2 Z.
F
Q IT Q z.)
2 Z + +1/
F
which implies 1 z.
2 Q rr Q(Ž - z.)//
with probability at least - 8/2.
By the normal equation of the sketched least square problem, IT QŽ= Q T Thus,
[ z.
| 22 T (QZ. - -B)
Since Q T (QZ. -B) QT -I-QQQ)) B 0sxN and I has (c/Vk,5/2)-JB second moment property, Lemma C.2 implies that with probability at least 1 8/2,
| T rr (QZ. -B).-BB]l= s e (</vk)
|Q P |QZ, - BlI O(e) | -B]
Then, by the union bound, with probability at least 1 - 8 over I, we have
2 2-z. Z. < 2 I (QZ. -B)// <<
-BllE
with suitable choice of the constant for ((e).
Lemma C.6 (7)). For a random matrix Ω E Raxm (n > m) consisting of i.i.d. subgaussian entries with mean zero and variance one, with high probability.
((Vi vm)²) I, 7N2 (00T=(((1)) s((m+ ( )
25

---

C.3 Upper Bounding Low-rank Approximation Error
Lemma C.7. Under Assumption 2.3 let r E Rrxm be Gaussian embedding (Lemma C.3 such that there exists m 1.1r satisfying 8% ES 7s for some 75 O. Then, with probability at least 1 - cxp (-2(()):
tr (E = ال tr (x²).
Proof of Lemma C.7 Here we follow a similar proof strategy as 43 Theorem 1]. Let IIş [INss E R=*N
N be the selection matrix associated with S S [N]. We introduce the following N x N oblique projectors:
Ms GG (Gs) Is. Ms = G
In particular, Ms and Ms are the oblique projectors since with I = Gs and GG = In,
M = GG GGs (Gs) Gs) Iss
= GG (Gs) (Gs) Ms.
and with II.G Gs.
M G G = Ms.
Recalling Ps from observe the following identities:
= = GG GG) GPs:
(12)
since GsG I
MsM MMM---GGCC--..CCCC.CCCCC C( = Ms:
(13)
and
G (Gs)
G G (GS)..
(14)
Combining 12
13
and 14). we have
GPs G GPs = (IN Ms) G
(by
IN Ms) (IN - Ms) G
(by 13
IN Ms) GP (by 12
IN Ms) (IN G (Gs) GP3s
(by 14
Since |/
1, this implies
(E
1
[GP
s
1
1 N
| Ms) [IN -
GP
|
N
1
G (Gs) G ?
LN Mg
N
By the operator norm identity for projectors
998 we have
IN Ms
Ms
|
G
I1s || | : - 1
and therefore,
tr (E'P))
1 3
(
(Gs) G 2
n
2/
Since G(GG)) G is rank-k orthogonal projector onto
Range (ā(Gs))) = Range (T(T))))
26

---

and Gaussian embeddings are rotationally invariant, G(G (G)) Gt shares the same distribution as (GN) (GΩ) for a x & Gaussian embedding Ω with [Rk, ~ (0 1/k) iid. Then, we observe that (I G(Gs) & ( I is the rank-k randomized range-finder error of G, which can with probability least 1 exp (-S2(F)),
be controlled according to Lemma C.8
N n
Ir (E+P3) H
Σ
|G
-G)
Σ
ir (I9- (E")))
By the definition of F in Assumption
2.3 tr [2 - (Σ0) tr (2*)
/ and thus,
tr (E*P3)
-
tr tr
Lemma C.8 (Randomized range-finder error (simplifying 32 Theorem 10.7)), Let Q E Rr*k be Gaussian embedding with [S) (0 1/k) i.i.d.. For any G E R and E N such that 1.1F < k < min (N,r), with probability al least exp (-)())())
(IN (GR) G x -G)
D Experiment Details for Section 4.1
D.1 Implementation Details
Synthetic data generation. We consider set of N 2000 samples with high-dimensional pre-trained representations <(X) R where 2400, modeled by Gaussian mixture model (GMM) consisting of F well-separated clusters, each with random sizes and variances. Specifically, we generate the GMM dataset as follows:
Randomly partition the N samples into clusters with sizes (N, j E [r]}.
For each j E [F]. generate the cluster mean μt; E R' with μ, = (2,7) e, where Z, Unif((F) and variance o Z -max where Z/ Uni 1]) and max 0.04.
Generate representations {Ø(x;) ~ (N),, 1 i [N5]] i.i.d. for each cluster j e [F].
Draw a latent label generator 0g (O, ((O,,,,), I,). For each cluster [F]. assign the same label
yt = u1 0y for all samples [Ny] within the cluster.
Ridge regression. We solve the ridge regression problem over the selected coreset Ds of samples and tune the regularization hyperparameter a via grid search over 100 linearly spaced values in [10-2, 10a] with 2-fold cross-validation.
D.2 Baselines
We compare SkMM the following unsupervised data selection methods for regression:
(a) Uniform sampling (Uni (Uniform) selects n samples uniformly at random from the full dataset D.
(b) Herding 51 [52)
(Herding) selects data greedily to minimize the distance between the centers of the coreset Dy and the original dataset 'D Notice that although herding aims to reduce the "bias" of the coreset center, it fails to control our notion of bias in the low-rank approximation sense. Given the construction the GMM dataset, herding has more emphasis on variance reduction, illustrated in Figure 2
(c) K-center greedy (53 (K- (K-center) provides greedy heuristic for the minimax facility location problem that aims to minimize the maximum distance between any non-coreset sample and the nearest coreset sample.
(d) Adaptive sampling 44 56 (Adaptive) iteratively samples data based on their squared norms and adaptively updates the distribution by eliminating the spanning subspace of the selected samples from the dataset. It is proved in the recent work 44 that adaptive sampling achieves nearly optimal sample complexity for low-rank approximations, matching that of volume sampling [39 41 (with the best know theoretical guarantee) up to logarithmic factor.
27

---

In practice, adaptive sampling generally achieves comparable accuracy to volume sampling for low-rank upproximations, with considerably better efficiency 44 45 Due to the prohibitive cost of volume sampling in high dimensions, we choose adaptive sampling in the comparison.
(e) Truncated 18 72 and ridge leverage score sampling 19
(T/R- (T/R-leverage) are the extensions of classical leverage score sampling [54] to high dimensions. In particular, leverage score sampling is originally designed for now-dimensional linear regression, while degenerating to uniform sampling in high dimensions. Consider the high-dimensional representations o( () R (r N) in our setting, for each E [M],
73
leverage score: 4 := (xx;) ((x:))((()))) (x()) ((X)) (x;;),
(((()))))(()))))))))( truncated leverage score: (mm)) = (xx)) ((0()) (6()) (xxx)) for given truncation rank m, and
ridge leverage score: 1.th == o(x,) (
(X) + مI (xx;) for given regularization
parameter p > 0. Larger p brings ridge leverage score sampling closer to uniform sampling.
Therefore, both truncated and ridge leverage score sampling balance the variance-biis tradeoff by adjusting the truncation rank y and regularization parameter p. respectively.
Baseline details. For both Herding and K-center, we adopt the DeepCore implementation M the implementation Notice that He reding is deterministic algorithm. For Adapti ive, from 45 For T-leveren rage, we use a rank-m truncated SVD to compute the leverage scores, with 47 32 in SkMM (i.e., providing both methods approximately the same amount of information and compute). For R Leverage, we choose 10
E
Additional Experiments and Details for Section 4.3
Table 4: Accuracy and Fl score (%) of FT over (the last two layers of) ResNet18 on StanfordCars
2000
2500
3000
3500
4000
29.19
0.37
32,83
+ 0.19
35.69 + 0.35
38.31 + 0.16
40.35 = 0.26
Uniform Sampling
F1
26.14
0.39
29.91 = 0.16
32.80 + 0.37
35.38 + 0.19
37.51 = 0.23
Herding 51
Acc
0.21
32.42 + 0.16
35,83 + 0.24
38.30 0.19
40.51 = 0.19
F1
0.24 25.90
29.48 + 0.23
32.89 + 0.27
35.50 + 0.22
37.56 = 0.21
Contextual Diversity
78
Acc
0.34
32.66 0 0.27
35.67 + 0.32
38.31 0.15
40.53 = 0.18
Fl
25.65 0.40
29.79 0.29
32,86 0.31
35.55 1 0.14
37.81 = 0.23
Glister
32.91 + 0.19
36.03 + 0.20
38.16 0.12
40,47 0.16
F1
+ 0,19 26.33
30.05 + 0.28
33.26 + 0.18
35.41 + 0.14
37.63 = 0.17
GraNd 66
Acc
28.59 0.17
32.67 + 0.20
35.83 0.16
38.58 0.15
40.70 = 0.11
25.66
0.115
29.70 - 0.22
0.16 0.16
37.83 0.15
0.11
28.61 0.31
32.48 0.28
38.18 0.24
37.78 0.22
40.24 0.13
Forgetting 30
F1
25.64
14440.22
29.58 = 0.30
32.38 + 0.20
35.16 0.18
37.41 = 0.14
DeepFool
Acc
24.97
0.20
29.02 0.17 26.08
32.60 + 0.18
35.59 + 0.24
38,20 = 0.22
22.11 + 0.11 F1
0.29
29.83 + 0.27
32.92 + 0.33
35.47 + 0.22
Ace
0.13 28.87
32.84 + 0.20
35.64 + 0.20
37.96 0.11 0.11
40.29 = 0.27
Entropy
82
Fl
25.95 0.17
30.03 0.17
32.85 + 0.23
35.19 - 0.12
37.33 = 0.34
Margin 82
0.12
32.73 + 0.15
35.67 + 0.30
38.27 1 0.20
40,58 0.06
F1
26.15 + 0.12
29.66 + 0.05
32,86 + 0.30
35.61 + 0.17
37.77 + 0.07
Least Confidence 82
Acc
29.05 + 0.07
32.88 + 0.13
35.66 + 0.18
38.25 + 0.20
39,91 = 0.09
F1
26.18
0.04
30.03 + 0.14
32.79 + 0.15
35 - 0.16
37.14 = 0.12
SkMM-FT
Acc
29.44 0.09
33.48
0.04
36.11 + 0.12
39.18 + 0.03
41.77 = 0.07
F1
26.71
0.10
30.75 0.05
33.24 0.05
36.38 + 0.05
39.07 0.10
Implementation details. For CLIP standard transform, we transform the image size to 224, with normalization mean (0.48145466. 0.4578275, 0,40821073) and std (0.26862954, 0.26130258, 0.27577711).
Parameter Count. We show the parameter sizes for the two-layer fine-tuning experiments in ??.
The representation dimension d is 512 for ResNet18, the number of classes K' is 10 for CIFAR-10 and 196 for Stanford Cars. The last layer parameter size is 5130 for CIFAR-10 and 100548 for Stanford Cars. The second but last layer parameter size is 2364426 for CIFAR-10, 10. When we do
28

---

Table Classification accuracy (%) of LP over CLIP on CIFAR- 10.
1000
2000
3000
4000
Uniform Sampling
91.68 + 0.45
92.22 + 0.25
92.60 = 0.14
92.79 0.12
Herding [
91.68 + 0.27
92.20 0.17
92.72
0.51
93.00 0.45
Contextual Diversity
91.98 + 0.11
0.003
92.81 0.25
92.99 = 0.24
Glister 77
91.09
91.83 9.26
91.87 0.09
GraNd 66
88.48 + 0.90
88.89 0.53
89.04
89.54 0.46
Forgetting 80
91.51
12.15=0.00
=2.1100001
92.81 = 0.01
DeepFool
81
91.68 + 0.32
91.78 + 0.79
91.93
92.18 0.70
Entropy 82
88.66 + 1.01
89.96 = 0.42
00.27
91.06 = 0.75
Margin
82
91.22 + 0.64
91.60 + 0.92
91.94 0.83
92.09 0.81
Least Confidence
89.38 + 1.73
90.49 + 1.47
90.83 = 1.43
91.26 1.30
SkMM-LP
92.96 + 0.07 93.38 + 0.01
93.67 - 0.01
93.78 0.04
Table 6: Accuracy of FT over ResNet18 on CIFAR-10.
2500
3000
3500
4000
Uniform Sampling
77.55 + 0.16
78.04 + 0.18
78.46 + 0.09
78.83 + 0.15
Herding [51
77.58
0.17
77.74
78.37
0.14
78.39 0.11
Contextual Diversity 78
77.24 -:244::00 0.08
7
78.17 + 0.07
78.22 0.11
Glister 79
77.46 0.13
0.15
78.19
78.49 + =
GraNd
77.22
0.007
78.31
0.11
Forgetting 80
77.32
77.87
78.05
+ 0.04
78.53 + 0.09
DecpFool
81
77.25
7.21
78.04
78.41 + 78.46
Entropy
77.55 0.21
0.112
78.23
0.20
Margin 82
77.24
77.81
0.23
78.32 + 0.17
78.52 = 0.15
LeastConfidence
82
0.23 77.46
77.93
78.21 + 0.17
78.60 + 0.10
SKMM-FT
77.75
0.08
78.12 + 0.04
78.66 + 0.06
79.11 + 0.02
the last two layers fine-tuning, the total parameter size 8398858 for CIFAR-10 and 2459844 for Stanford Cars.
StanfordCars Baselines. For DeepCore baselines, there are some methods that require warmup training before the finetuning (e.g. Uncertainty-Entropy) training (freezing other layers) in the warmup training for linear probing selection and two-layer finetuning selection. The warmup training is done with Adam optimizer with learning rate 0.01 for 10 epochs.
use one-layer training and two-layer
Finetuning Details We finetune the model for 50 epochs for both linear probing and finetuning using Adam optimizer with learning rate 0.01.
29

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification:
We summarized our contributions the end of the introduction (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 NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals motivation long is clear that these goals attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed limitations and future directions in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors 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 well-specification, 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 a speech-to to-tttt-tttt system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
30

---

For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Question:
Answer: [Yes]
Justification: The assumptions are clearly stated in place with the theoretical results, while the proofs are deferred to the appendices, with clear hyperlink references.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide clear pseudocode and experiment setups in the main text, as well as implementation details in the appendices.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer to this question will not be perceived well by 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 the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might
example, if the contribution suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g.. in the of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily 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 a way to access this model for reproducing the results or a way to reproduce the model (c.g., with open-source dataset instructions for how to construct the dataset).
31

---

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.- to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
Open access to data and code
Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our experiment code for both the synthetic and real data available at https//woooyooooooosopp..ccccccd
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please
see
the NeurIPS code and data submission for more details.
guidelines
While we encourage the release code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines for more details.
The authors should provide instructions on data access and preparation, including how to access the data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce experimental results for the new proposed method and baselines. only subset of experiments reprodueible, 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 as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We specify the experiments setting the main context (subsection 4.1 (suseec tion 4.3) and appendix (subsection D.I subsecction D.2) opensourced our code and scripts at
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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, or as supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about statistical significance of the experiments?
Answer: [Yes]
32

---

Justification:
We reported the stand error with 5 seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence 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 are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the enror bar is the standard deviation or the standard enror of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 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 show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: All the experiments could be done with A40 smaller GPUs. We workers and 32 GB Memory.
Guidelines:
The answer NA means that the paper does 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 of compute required for each of the individual experimental runs as 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 't make it 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 http:://eerrisscccmpiiichttctttt
Answer: [Yes]
Justification: Yes, we follow the NeurIPS Code of Ethics.
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 a deviation from the Code of Ethics.
33

---

The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This a learning theory paper with no societal impact.
Guidelines:
The answer NA means that there is societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment 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 par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
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 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 to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This a learning theory paper with no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
34

---

Answer:
[Yes]
Justification: We use the open-sourced dataset (CIFARIO) and models (CLIP), they are open for research usage.
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 or dataset.
The authors should state which version of the
used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, ppaerrsitheode httpe//wwwhhoo..co//dattaaaeee 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 the derived asset (if it has changed) should be provided.
If this information creators.
available online, the authors are encouraged reach out the asset's
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel part of their sub- missions via structured templates. This includes details about training, license, limitations,
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects.
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 contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should paid least the minimum wage in the country of the data collector.
35

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed 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:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
36


Reviews:
[{"review_id": "njJrk7R99V", "reviewer": "Reviewer_NGFs", "summary": "This paper studies the problem of data selection in the over-parametrized fine-tuning regime, i.e. when the number of fine-tuning parameters $r$ is larger than the amount $N$ of available examples. We want to subsample $n\\ll N$ examples that form a representative set to train on, and hopefully achieve quality as close as possible to fine-tuning on the whole set.\n\nThe idea is to compute the gradients $G\\in \\mathbb{R}^{N\\times r}$ of all examples wrt the fine-tuning params and then select a subsample $S\\subseteq [N]$ such that the Gram matrix of the gradients is approximated: $c\\cdot \\Sigma_S := c \\cdot G^\\top I_S G \\approx G^\\top G := \\Sigma$. However, this is not possible to achieve since the model is over-parameterized. Fortunately, if the spectral approximation holds on a low-dimensional subspace of the parameter space, this is good enough, so the authors project the gradients on a random low-dimensional space. The proof goes through under the assumption that the singular values of the gradient matrix are well-concentrated on a small enough (<10%) support.\n\nThe experimental results include fine-tuning on a synthetic linear task, as well as fine-tuning a vision transformer on CIFAR-10 image classification.", "questions": "In Remark 3.2 the authors write that their goal is to achieve the constraint $\\tilde{G}^\\top \\tilde{G} \\preceq c_S \\cdot \\tilde{G}^\\top I_S \\tilde{G}$ (1). They subsequently relax this problem and solve the resulting constrained convex optimization problem using projected gradient descent. However, it seems to me that (1) might be equivalent to $U^\\top I_S U \\succeq c_S^{-1} \\cdot I$, where $U\\Lambda^{1/2} V^\\top$ is the SVD of $\\tilde{G}$. Here $U\\in {N\\times \\bar{r}}$ is a tall and thin matrix. This is a spectral sparsification task which could be solved using leverage score sampling on the rows of $U$. Furthermore, this is the same as sampling examples proportional to the squared $\\ell_2$ norms of the rows of $U$. Maybe, I'm missing something, so please correct me if I'm wrong.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The authors study the data selection for fine-tuning problem from first principles\n- The writing is overall good and math looks sound, even though I didn't check details.\n- The experimental results look promising since SkMM beats a variety of algorithms including leverage scores.\n- The idea of spectral approximation on a subspace of the parameter space is interesting.", "weaknesses": "- Important details on the experimental setup are missing or unclear. Specifically, what is the optimization process after the data is subsampled? For the image classification experiments, what is being fine-tuned, is it all the ViT parameters? For how many epochs? \n- The algorithm requires computing the gradients of all samples, which can be computationally expensive. Besides, if we are computing all gradients, why can't we just train one epoch on all datapoints? Why is data selection useful in this case?\n- The literature review could be expanded, including relevant papers such as BADGE [1], Coreset-based sensitivity sampling [2].\n- In the experimental results, the authors should also compare with margin sampling (in addition to entropy sampling), as well as uniform sampling for the image classification task.\n- Computing the moment-matching subset in Algorithm 3.1 seems overly complicated, see questions\n\n[1]: Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds\n\n[2]: Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their constructive questions and suggestions, and we are glad that they found this work interesting and well-presented. On the questions raised in the review:\n1. __Cost of gradient computation and SkMM:__\n    First, we kindly emphasize the __ubiquitous role of gradients in most data selection methods__. For linear probing, the gradients (of the finetuning model instead of the loss) are essentially the last-layer features from the pre-trained model, which can be computed without backward propagation. Such information is necessary for all unsupervised data selection methods discussed in \"1.1 Related Works\" including leverage score sampling and influence function. Beyond linear probing, gradient computation can bring asymptotically similar costs as *one epoch* of training on the full data set. Notice that this is more efficient compared to methods with *several epochs* of warmup training (eg, [1,15,38,52,56,69,83] in submission, including all methods we compared against in the real-data experiments except uniform sampling and herding). Such cost of gradient computation or warmup training is acceptable because the selected data have their own importance (eg, finetuning similar models with limited memory and computation). Moreover, we refer to General Response 1 that SkMM based on gradient sketching is highly efficient in both memory and computation. As mentioned in Algorithm 3.1, the gradients can be computed and compressed (via sketching) in parallel and on the fly without storage, while all the subsequent steps for moment matching are conducted in the lower dimension $m \\ll r$. We will make sure to clarify these points further in the revision.\n\n    Second, we highlight that __training for one epoch on the full dataset is generally insufficient for finetuning__. For example, when finetuning CLIP via linear probing on CIFAR-10 (Table 2), training for one full epoch leads to test accuracy of only $91.94 \\pm 0.17$ (cf. $92.96 \\pm 0.07$ learned with as few as $1000$ selected data via SkMM).\n\n2. __Sketchy moment matching v.s. sketchy leverage score sampling__:\n    Up to proper scaling $U^\\top diag(\\frac{N}{n} s) U \\succcurlyeq c_S^{-1}$ (where $s \\in \\{0,1\\}^N$, $\\|s\\|_0 = n$), we agree with the reviewer that leverage score sampling based on the sketched gradients $\\widetilde{G}$ can also provide good control over $c_S$ with high probability. However, such control comes with nuance dependence on matrix coherence and can render the upper bound vacuous in the worst case (vide General Response 2).\n\n    This is exactly the major motivation for the comparison with the truncated and ridge leverage score sampling (T/R-leverage) in the synthetic data experiments. In particular, leverage score sampling based on the sketched gradients is effectively equivalent to T-leverage (ie, when the original gradient dimension $r$ is too high for the exact computation of SVD for $G \\in \\mathbb{R}^{N \\times r}$, randomized SVD based on sketching is generally used as an approximation, in which case leverage scores of $\\widetilde{G}$ is exactly T-leverage). In experiments, we also confirmed the indistinguishable behaviors between the two, and therefore only reported one of them. As discussed in Sec 4.1, __while SkMM and T/R-leverage both encourage variance-bias balance__ (by controlling $c_S$) and therefore provide among-the-best risks in Table 1, __SkMM shows better performance on average as it is tailored for optimizing__ $c_S$. Nevertheless, we agree that with very limited computation (ie, even optimizing (5) in low dimension $m$ is infeasible), sketchy (ridge) leverage score sampling would be a more affordable alternative to SkMM.\n\n    Motivated by this insightful question, we will extend Sec 3.2 based on the above discussions on the connection between SkMM and leverage score sampling in the revision.\n\n3. __Improvements on related works, experiment setup, and more comprehensive experiments__:\n    Many thanks for the constructive suggestions on related works and experiments. We will include discussions on the suggested literature in the next version. In addition, we will provide more experiments on real data with more comprehensive baselines (including margin sampling) in the revision. (Please refer to General Response 3 for the results and details of the additional experiments.) We will also provide more detailed experimental setups in the revision as follows.\n    * After data selection, we fine-tune the model in two different settings: (a) linear probing over CLIP-pre-trained ViT (vide Tables 1 and 3 in the attached PDF) and (b) non-linear finetuning of the last two layers in an ImageNet-pre-trained ResNet18 (vide Tables 2 and 4). Please refer to Table 5 in the attached PDF for detailed configurations like parameter dimensions.\n    * The fine-tuning parameters are optimized via Adam with a learning rate $10^{-2}$, for 200 epochs over CIFAR10 (following [29] in submission, Tables 1 and 2) and 50 epochs over StanfordCars (Tables 3 and 4).\n\nWe are happy to answer any further questions you may have. If our responses above help address your concerns, we would truly appreciate a re-evaluation accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KqSMi2CHYm", "reviewer": "Reviewer_iMuZ", "summary": "This paper concerns the data selection problem: given a collection of $N$ embeddings of dimension $r$ for $r\\gg N$, the goal is to pick a subset $S$ of points of size $n$ so that one could run any downstream algorithm on $S$ with a regularization term, so that the empirical risk is small even on the entire finetuning set. Assuming the model is $y=\\phi(X) \\theta_*+z$ where $\\phi: \\mathbb{R}^d\\rightarrow \\mathbb{R}^r$ and $z$ is an i.i.d. noise vector with zero mean and bounded variance, then there exists a subspace that one could project onto and decompose the empirical risk as a bias and a variance term. Further, under the assumption that the second moment matrix has low intrinsic dimension, then one could find a good subspace via gradient sketching: draw a JL matrix $\\Gamma\\in \\mathbb{R}^{r\\times m}$ for $m\\ll r$, then as long as one has $\\Gamma^\\top \\Sigma^{\\phi} \\Gamma \\preceq c_S \\cdot \\Gamma^\\top \\Sigma^{\\phi}_S \\Gamma$, then the error could be decomposed into a bias, variance and a sketching error term. A sketching gradient, moment-matching algorithm is proposed, involves applying sketching to the gradient, form the Jacobian and solve a quadratic relaxation. Experiments are performed on both synthetic datasets and CIFAR10.", "questions": "What is the runtime efficiency of your proposed method? It seems the performance is slightly better than ridge leverage score sampling, but ridge leverage score sampling could be implemented in input sparsity time, see the algorithm due to Cohen, Musco and Musco, SODA'17. Their algorithm is based on recursive uniform sampling, so could be implemented efficiently in practice.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The main theoretical contribution is that for over-parametrized setting where $r\\gg n$, one could provably show the existence of a subspace that one could project onto and perform data selection on that subspace. Moreover, if the second moment in addition has low intrinsic dimension, then one could use standard dimensionality reduction techniques (in $\\ell_2$ norm) to sketch the high-dimensional gradient. In the sketchy moment-matching algorithm proposed in the paper, the authors first sketch the gradient then use uniform sampling  to construct $S$.", "weaknesses": "The core results of this paper are not technically very novel and surprising, the algorithm could be interpreted as a generalization of the leverage score sampling via JL trick due to Spielman and Srivastava, STOC'08. The analysis largely draws inspirations from the over-parametrization literature, which makes sense as finetuning is essentially training in an over-parametrized setting. Another point that is a bit unsatisfactory is the sketchy moment-matching algorithm utilizes quadratic relaxation to solve the program efficiently with projected gradient descent, but all analysis is based upon *not solving the quadratic programs*. The authors should try to provide some theoretical justifications of sketchy moment-matching, as that's one of the key contributions of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the insightful questions and suggestions from the reviewer. However, we believe there have been misunderstandings regarding the focus and contribution of this work. We hope that the following responses will help clarify these confusions.\n1. __Our theoretical contributions are explanatory instead of instrumental__:\n    As discussed in the related works, prior theoretical studies on data selection are conducted either in the low-dimensional linear regression setting or in the asymptotic regime, neither of which aligns with the fine-tuning in practice that manages to learn high-dimensional parameters with much fewer samples. (Although we analyze fine-tuning in the kernel regime following [83], the over-parametrization literature is generally out of the data selection setting.) To fill the gap, we provided\n    * __a generalization bound of data selection for high-dimensional fine-tuning with low intrinsic dimension__ in the non-asymptotic regime that unveils the possibility of learning a fine-tuning model with a sample complexity proportional to the low intrinsic dimension (instead of the high parameter dimension), and\n    * __a practical data selection framework inspired by the analysis__, SkMM, that finds such coresets efficiently via gradient sketching + moment matching.\n    \n    Instead of proposing an instrumental theory, we use the existing theoretical tools from sketching and statistical learning to provide __an explanatory theory for the sample efficiency of data selection for fine-tuning that generally admits low intrinsic dimensions in practice__ and __an efficient method for selecting such data__.\n\n    While we agree that gradient sketching shares a similar high-level idea as the JL trick in Spielman and Srivastava, STOC'08 (which is ubiquitous in the sketching literature, cf. [30,81] in submission), leveraging such a fundamental theoretical framework should not compromise the novelty of an explanatory theory.\n\n2. __The quadratic relaxation is a practical realization of SkMM instead of the only solution__:\n    As elaborated in General Response 2, after gradient sketching, moment matching in the resulting low-dimensional subspace can be realized via various methods, including leverage score sampling and existing polynomial-time heuristics of discrete optimization for experimental design:\n    * Our main motivation for exploring beyond leverage score sampling is the empirical observation that (truncated/sketched) leverage score sampling can perform poorly, especially in the low data regime (cf. Table 1). This can be explained by the dependence of the moment matching guarantee of leverage score sampling on the matrix coherence (vide General Response 2).\n    * Discrete optimization for the V-optimality is an alternative to leverage score sampling. However, such optimization is known to be hard: the best available polynomial-time heuristic with a theoretical guarantee ([4] in submission) involves matrix inversion in each optimization step, bringing instability issues and compromising the practical application.\n    \n    Our proposal of SkMM can be interpreted as a quadratic relaxation of moment matching $\\widetilde{\\Sigma} \\preccurlyeq c_S \\widetilde{\\Sigma}_S$ by assuming that $\\widetilde{\\Sigma}, \\widetilde{\\Sigma}_S$ commute (i.e., are simultaneously diagonalizable). This relaxation improves computational efficiency and avoids numerical instability by eliminating the need for matrix inversion. Although the assumption that the two matrices commute does not hold in general, it is a valuable heuristic for designing efficient algorithms, as demonstrated empirically across various domains. For example, in optimization, this approach is used to simplify certain SDP relaxations and approximate solutions effectively (Lu, Monteiro, 2005). In handling distributional shifts, it is used to design optimization formulations to obtain minimax risks efficiently (Blaker, 2000; Lei et al., 2021). We will further clarify this in the revision.\n    \n4. __Efficiency of SkMM__:\n    As ridge leverage score approximation via recursive sampling, gradient sketching in SkMM can be computed efficiently in input sparsity time, and the following moment matching stage takes place in the low dimension $m$ (vide General Response 1).\n    As discussed in General Response 2, while (ridge) leverage score sampling also facilitates moment matching as SkMM and enjoys a slightly better runtime in the moment matching stage (in a lower-order term), with experiments (cf. Table 1), we show that SkMM tends to provide better performance as it is tailored for optimizing moment matching.\n\nWe are happy to answer any further questions you may have. If our responses above help address your concerns, we would truly appreciate a re-evaluation accordingly.\n\nReferences:\n* Lu, Z., Monteiro, R. D. C. (2005). \"Primal-dual interior-point methods for semidefinite programming using inexact step directions.\" Mathematical Programming, 103(2), 453-485.\n* Blaker, Minimax estimation in linear regression under restrictions, annals of statistics 2000\n* Lei et al, Near-optimal linear regression under distribution shift. ICML 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3e1oer2fvh", "reviewer": "Reviewer_gV74", "summary": "The authors study the task of data selection. They extend the classical variance reduction to the high dimensional case and provide a variance-bias tradeoff analysis. Based on the theoretical results, they propose sketchy moment matching, which first utilizes gradient sketchy to form a low-dimensional space and then uses moment matching to reduce the variance.", "questions": "For the convenience of the readers, could you list the number of parameter fine-tuned for the Cifar-10 linear-probing task and the number of samples of Cifar-10? (I know this is something that can be looked up online, but these seems to be important numbers to show that the experiment setting is high dimensional)\n\nAlso, could you scale up the synthetic experiment, like increasing sample count/rank/number of clusters? Testing on Cifar-100 is also another way to evaluate the performance on a larger number of clusters.", "limitations": "Yes, the authors discuss the limitations.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The proposal is a reasonable improvement over the baselines which often only consider bias or variance reduction. The theoretical analysis is also a decent contribution of the paper.", "weaknesses": "The experiment focuses on linear probing, which already limits the scope of the evaluation. Furthermore, even under this limited scope, the setting does not seem to be challenging. For the synthetic setup, the sample count is 2000 while the rank is 2500, so it seems not to be a very high-dimension setup (the rank is not so much larger than the sample count). Also, the cluster count seems to be low for both tasks, 8 for synthetic, while the number of class is 10 for Cifar-10.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their helpful questions and suggestions, and we are glad that they found this work well-presented and theoretically sound. Nevertheless, we believe there have been misconceptions regarding some key notions and the focus of this work. Before diving into the specific questions, we want to emphasize the following two main theoretical/algorithmic contributions of this work:\n* a generalization bound of data selection for high-dimensional fine-tuning with a low intrinsic dimension that unveils the possibility of learning a fine-tuning model with a sample complexity proportional to the low intrinsic dimension (instead of the high parameter dimension), and\n* SkMM, a practical data selection framework inspired by the analysis that finds such coresets efficiently via gradient sketching + moment matching.\n\nMeanwhile, we recall the key notion of \"high-dimensional finetuning\" as explained in the introduction (footnote 1): the over-parametrized setting where the number of finetuning parameters $r$ is larger than the selected downstream sample size $n$. That is, __“high-dimensional” refers to the relative magnitude $r>n$, instead of the absolute data/model size__.\n\nOn the questions raised in the review:\n1. __Scaling up linear probing on synthetic data does not change the takeaway information__:\n    While we agree with the reviewer that more experiments on larger scales would intuitively be preferred, scaling up the synthetic data experiments is not a reasonable choice because (i) our current synthetic data experiments readily lie in the “high-dimensional”/over-parametrized regime with $n < r$ even though the absolute sample/model sizes are not huge; and (ii) scaling up linear probing experiments on synthetic data generally does not change the takeaway information, as shown below.\n\n    Consider a set of $N=2000$ samples in a higher dimension $r=4000$ generated from a GMM with $\\overline{r}=12$ clusters where ridge regression over the full dataset achieves $L(\\theta_{[N]})=1.18e-2$. We show the results in the table below, which are consistent with the synthetic data experiments in the submission. The main takeaways remain unchanged: SkMM achieves among the best empirical risks across different coreset sizes $n$, especially for small $n$; while methods that facilitate variance-bias balance (SkMM and T/R-leverage) tend to outperform the rest baselines. (Notice that for $n \\ge 120$, data selection can bring even lower empirical risk than learning over the full dataset, which coincides with the recent theory and observation in [41] in submission.)\n\n    | n | 48 | 64 | 80 | 120 | 400 | 800 | 1600 |\n    |---|---|---|---|---|---|---|---|\n    | Herding | 4.04e+03 | 4.04e+03 | 4.04e+03 | 3.87e+03 | 3.74e+03 | 3.67e+03 | 1.76e+03\n    | Uniform | (1.24 $\\pm$ 1.19)e2 | (0.81 $\\pm$ 1.18)e2 | (0.76 $\\pm$ 1.11)e2 | (0.74 $\\pm$ 1.11)e2 | (9.92 $\\pm$ 0.18)e-3 | (9.56 $\\pm$ 0.03)e-3 | (1.64 $\\pm$ 0.39)e-2 |\n    | K-center | (6.64 $\\pm$ 0.22)e-1 | (4.72 $\\pm$ 2.79)e-1 | (3.98 $\\pm$ 0.81)e-2 | (1.71 $\\pm$ 2.62)e-1 | (3.12 $\\pm$ 0.67)e-2 | (1.29 $\\pm$ 2.29)e-1 | (2.04 $\\pm$ 0.62)e-1 |\n    | Adaptive | (2.19 $\\pm$ 1.27)e-2 | (2.78 $\\pm$ 3.34)e-2 | (2.51 $\\pm$ 2.02)e-2 | (1.88 $\\pm$ 1.63)e-2 | (2.39 $\\pm$ 4.25)e-2 | (9.52 $\\pm$ 0.05)e-3 | (1.71 $\\pm$ 2.72)e-1 |\n    | T-leverage | (1.06 $\\pm$ 8.15)e2 | (7.21 $\\pm$ 8.25)e1 | (5.44 $\\pm$ 7.70)e2 | (5.44 $\\pm$ 7.70)e2 | __(8.27 $\\pm$ 1.62)e-3__ | __(8.66 $\\pm$ 1.79)e-3__ | (1.09 $\\pm$ 0.37)e-2 |\n    | R-leverage | (3.52 $\\pm$ 7.63)e1 | (1.92 $\\pm$ 1.77)e-2 | (1.19 $\\pm$ 2.18)e-2 | __(1.03 $\\pm$ 0.05)e-2__ | (9.48 $\\pm$ 0.50)e-3 | (9.54 $\\pm$ 0.02)e-5 | (1.17 $\\pm$ 0.47)e-2 |\n    | SkMM | __(2.13 $\\pm$ 1.28)e-2__ | __(1.65 $\\pm$ 1.30)e-2__ | __(1.11 $\\pm$ 0.06)e-2__ | __(1.03 $\\pm$ 0.03)e-2__ | (9.34 $\\pm$ 0.13)e-3 | (9.41 $\\pm$ 0.11)e-3 | __(1.08 $\\pm$ 0.42)e-2__ |\n\n    To further investigate the effect of problem size on the data selection performance, instead of scaling the synthetic data experiments, we will provide more extensive empirical evaluations of our method on real data, as elaborated below and in General Response 3.\n\n2. __More comprehensive experiments on real vision tasks__:\n   Thanks to the constructive suggestion, in the revision, we will extend the empirical evaluation to\n   * real vision tasks with a larger number of classes (ie, StanfordCars with 16,185 images in 196 imbalanced classes of cars, in addition to CIFAR-10 with 60,000 images in 10 balanced classes) and\n   * fine-tuning settings beyond linear probing with parameters of much higher dimension (ie, finetuning the last two layers of an ImageNet-pre-trained ResNet18 with $r=2,364,426$ parameters, versus linear probing on CLIP with $r=5,130$ parameters, vide Table 5 in the attached PDF for detailed configurations). We will make sure to include these experimental details in the revision.\n\n   Please refer to General Response 3 for the results and more details of the additional experiments. \n   \nWe are happy to answer any further questions you may have. If our responses above help address your concerns, we would truly appreciate a re-evaluation accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fAPsAm13fq", "reviewer": "Reviewer_dwk6", "summary": "This paper addresses the problem of data selection for finetuning large pre-trained models. The key contributions are:\n\n1. A theoretical analysis of data selection for finetuning that reveals a variance-bias tradeoff in high dimensions.\n2. A provable result showing that gradient sketching can efficiently find a low-dimensional subspace that preserves fast-rate generalization.\n3. A practical two-stage algorithm called Sketchy Moment Matching (SkMM) that uses gradient sketching to explore the parameter space and moment matching to exploit the low-dimensional structure.\n4. Empirical validation on synthetic and real datasets demonstrating the effectiveness of the approach.", "questions": "1. Does the approach extend naturally to other finetuning scenarios beyond linear probing (e.g., adapters, full finetuning)?\n2. How does the computational cost of SkMM compare to other data selection methods as the dataset/model size increases?", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a rigorous generalization analysis for data selection in both low and high-dimensional settings. The proofs are detailed and appear sound.\n2. The proposed SkMM method is simple to implement and scalable to large models/datasets. Experiments on both synthetic and real data demonstrate the effectiveness of the approach.", "weaknesses": "1. Some of the theoretical results rely on assumptions (e.g., low intrinsic dimensionality) that may not always hold in practice. More discussion of the implications when these assumptions are violated would be valuable.\n2. The method introduces new hyperparameters (e.g., sketching dimension, moment matching strength) without much guidance on how to set them optimally.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their insightful questions and suggestions. We are glad that they found our theory solid and our method effective. On the questions raised in the review:\n1. __Low intrinsic dimensions of fine-tuning__: \n    Recalling the references [2,72] from the introduction, we highlight that the __low intrinsic dimension of fine-tuning is an extensively observed phenomenon in practice with theoretical rationale__. In particular, [2] demonstrates the surprisingly low intrinsic dimensions of fine-tuning language models in practice; while [72] provides a theoretical justification for the ubiquity of low-rank structures in natural data. One of the main goals of this work is to leverage such low intrinsic dimensions via data selection and enable learning with a sample complexity independent of the high parameter dimension $r$.\n\n    As explained in footnote 7 (page 5), such __a low intrinsic dimension is necessary for sample-efficient learning__. Intuitively, if all the $r$ directions in the high-dimensional parameter space are equally important, when the coreset size $n < r$, the learned parameter $\\theta_S$ must fail to capture the orthogonal complement of the space spanned by the coreset and lead to $\\mathbb{E}[ER(\\theta_S)] \\gtrsim r-n$. We will further elaborate on these assumptions in the revision.\n\n2. __Choices of hyperparameters__:\n    The two hyperparameters in SkMM (Algorithm 3.1) are the sketching dimension $m$ and the constant $c_S$ that controls the moment matching strength.\n    * __Theorem 3.1 provides theoretical guidance for the choice of sketching dimension__: $m = O(\\overline{r})$ where $\\overline{r}$ is the low intrinsic dimension. In practice, choosing $m$ to be a small constant multiple of $\\overline{r}$ (eg, $m = 2\\overline{r}$) is generally sufficient. (Notice that such pessimistic constants in theory compared to practice are ubiquitous in sketching, cf. [30,49,81] in submission.)\n    * On the choice of $c_S$, we first __recall from Remark 3.3 that the lower $c_S$ corresponds to the stronger moment matching, resulting in harder optimization of (5), but up on convergence, leading to a better generalization guarantee__. In practice, we start by choosing $c_S$ close to one to ensure the solvability of (5) and then gradually decrease $c_S$ until the optimization of (5) fails or takes too long to converge. Specifically, we fix $c_S = 0.999$ in the synthetic experiments as reported in Sec 4.1 (line 264); while for experiments on real data, we explore $c_S = 0.99, 0.9, 0.8, 0.7, 0.6$ in the respective order for the minimum feasible $c_S$.\n\n    We will include the above discussion on hyperparameter tuning (especially for $c_S$) in the revision.\n\n3. __Extension beyond linear probing__: \n    Thanks for the constructive question. In the revision, we will extend the empirical evaluation beyond linear probing. In particular, we demonstrate the effectiveness of SkMM in data selection for __finetuning the last two layers__ of an ImageNet-pre-trained ResNet18 on two datasets: CIFAR-10 with 10 well-balanced classes and StanfordCars with 196 imbalanced classes. Please refer to General Response 3 for the results and details of the additional experiments.\n    \n4. __Computational efficiency of SkMM__:\n    SkMM is efficient in both memory and computation while scaling well with the model and data sizes. Please refer to General Response 1 for a detailed discussion on the computational efficiency of SkMM.\n\nWe are happy to answer any further questions you may have. Thanks again for the helpful feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First, we would like to thank all the reviewers for their time, efforts, and valuable suggestions. In the general response, we address some common questions raised in the reviews and summarize important revisions we made
1. __Computational efficiency of SkMM__:
    SkMM is efficient in both memory and computation. Consider the two stages in SkMM:
    * The dimensionality reduction via __gradient sketching__ can be computed __in parallel with input-sparsity time__ and __on the fly without storing the (potentially) high-dimensional gradients__. In particular, let $nnz(G) \le Nr$ be the number of nonzero entries in the (high-dimensional) gradients $G \in \mathbb{R}^{N \times r}$, as discussed in Remark C.1, sketching via a (sub)Gaussian embedding $\Gamma \in \mathbb{R}^{r \times m}$ can be computed in $O(nnz(G) m)$ time, while a sparse embedding (Remark C.1 (b)) can further accelerate the sketching process to $O(nnz(G))$ time. Only the sketched gradients $\widetilde{G} = G \Gamma$ needs to be stored, requiring just $O(Nm)$ memory (recall that $m \ll r$ is a small number proportional to the low intrinsic dimension). For linear probing, $G$ is simply the last-layer feature of the pre-trained model. Beyond linear probing, computing the gradients costs no more than one full training epoch, much cheaper than many data selection methods based on a few epochs of warmup training (eg, [1,15,38,52,56,69,83] in submission, including all methods we compared against in the real-data experiments except uniform sampling and herding).
    * After gradient sketching, __variance reduction via moment matching happens in the low dimension__ $m$, with a low memory footprint $O(Nm)$, taking $O(m^3)$ for the spectral decomposition and $O(Nm)$ per iteration for optimizing the moment matching objective (5).

    We will highlight the computational efficiency of SkMM further in the main text of the revision.

2. __Different methods for moment matching__:
    As mentioned in the limitations and future directions, after gradient sketching, __variance reduction in the resulting low-dimensional subspace via moment matching can be realized using various methods__, among which leverage score sampling based on the sketched gradients $\widetilde{G}$ is arguably the most intuitive approach. Alternatively, we proposed an optimization-based method in Algorithm 3.1 that solves a quadratic relaxation (Remark 3.2) as a practical heuristic. In the synthetic data experiments, we show that __SkMM provides a better variance-bias balance and hence better performance than leverage score sampling__ (T-leverage).

   To better clarify the connection with leverage score sampling, in the revision, we will add __a brief review of the theoretical guarantee for leverage score sampling and explain why an alternative could be desired__. In particular, Theorem 17 of [81] (in submission) implies that leverage score sampling on $\widetilde{G}$ provides $c_S \le \frac{(1+\epsilon) m}{\tau_S N}$ with probability at least $1-\delta$ for a coreset size $n = O(m \log(m/\delta) / \epsilon^2)$, where $\tau_S \in [0,1]$ is the minimum leverage score of $\widetilde{G}$ over the coreset $S$ ($\tau_S$ appears because samples in $S$ are equally weighted in the data selection setting). __Such dependence on matrix coherence can render the upper bound vacuous in the worst case__. Nevertheless, leverage score sampling based on the sketched gradients can be computed more efficiently than SkMM in $O(Nm^2)$ time and can provide good control over $c_S$ when $\tau_S$ is reasonably large. Overall, as pointed out in Sec 4.1, both SkMM and leverage score sampling facilitate variance-bias balance in data selection, while __SkMM is tailored for optimizing moment matching, providing better empirical performance at a slightly higher cost in the low intrinsic dimension__ $m$.

3. __Additional experiments__:
    Thanks to the reviewers' suggestions, we will extend the empirical evaluation on real vision tasks in the revision from the following two aspects:
    * We explore two real vision tasks with different scales and structures: (a) CIFAR-10 with 60,000 images in 10 balanced classes (vide Tables 1 and 2 in the attached PDF) and (b) StanfordCars with 16,185 images in 196 imbalanced classes (vide Tables 3 and 4). (Notice that we expanded the original CLIP linear probing experiments on CIFAR-10 with more comprehensive baselines.)
    * We investigate different fine-tuning settings including (a) linear probing over CLIP-pre-trained ViT (vide Tables 1 and 3) and (b) non-linear finetuning of the last two layers in an ImageNet-pre-trained ResNet18 (vide Tables 2 and 4). We summarize the detailed configurations like the parameter counts in Table 5. (Notice that finetuning the last few layers of strong pre-trained models like CLIP can distort the features and hurt the performance significantly, as studied in (Kumar et al., 2022). Therefore, we choose a weaker pre-trained model, ResNet18, for finetuning beyond linear probing.)

    For both fine-tuning settings on the two datasets, SkMM demonstrates appealing generalization across different coreset sizes. In particular, SkMM tends to outperform the other baselines by a larger margin on the imbalanced StanfordCars dataset compared to the well-balanced CIFAR-10, manifesting the effectiveness of SkMM in balancing the variance-bias trade-off in data selection as suggested by the theory and in the synthetic data experiments.


References:
* Kumar, Ananya, et al. "Fine-tuning can distort pretrained features and underperform out-of-distribution." arXiv preprint arXiv:2202.10054 (2022).

Meta-review: This paper studies the problem of selecting a small subset of a given dataset whilst preserving enough information to perform a downstream fine tuning task. The strategy consists in drawing gaussian projections of the gradients of the datapoints w.r.t. the parameters and matching the dataset variance (cf. Eq. (5)). It is shown that if the data has low intrinsic dimension, the algorithm enjoys a favorable excess risk bound. Many experiments are run on both synthetic and real world data which demonstrate the efficiency of the proposed method.

After the author-reviewer discussion, **the reviewers unanimously agree on acceptance**. However, **reviewer iMuZ** did have some **legitimate concerns** regarding the presentation and the perceived similarity of the method with JL trick in classical spectral sparsification literature the similarity of the proof techniques with  the overparametrization literature. I have followed up with the reviewer in further discussion regarding the proofs, and it seems like the concerns are not that bad: the proofs merely use standard techniques but do not borrow large chunks from any single source. Whilst I agree with the reviewer that the method is similar to the JL trick in the sparsification literature, applying it to a new problem is a **valid contribution**. Thus, overall, it seems that the level of novelty is not as high as it looks at first glance, but is still at a reasonable level. 
Still, in the camera ready version the authors should better explain the relationship between their method and the *sparsification literature* [1] and better explain the  *quadratic relaxation*, which  used in the experiments.  The authors promised many such changes to reviewer iMuZ and they should be sure to incorporate all of them. I do have reasonable confidence in the authors' sincerity, since the **rebuttal** was very **thorough** and they have added many **new experiments** at the rebuttal stage, further strengthening the contribution. 



**Reference**

[1] Daniel A. Spielman, Nikhil Srivastava, "Graph Sparsification by Effective Resistances". STOC 2008.
Decision: Accept (poster)