Sketchy Moment Matching: Toward Fast and Provable Data Selection for Finetuning

Authors: yijun  dong
hoang  phan
xiang  pan
qi  lei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 03:44:56

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.

Main paper: 
 introduction: 
 As the data volume and training cost explode with the unprecedented model performance, the longstanding problem of data selection [1, 2] is getting increasing attention in the modern context of deep learning from various perspectives, including data pruning [3, 4] , coreset selection [1, 5, 6, 7, 8, 9] , and data filtering [2, 10, 11, 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: a seemingly inevitable tradeoff between less computation and higher-quality representations [14, 15] . While existing works on data selection have a dominating focus on the training-from-scratch setting, the sensitivity of representation learning to data and the growing availability of powerful pre-trained models calls for attention to a less studied [16] but equally important problem: data selection for finetuning.In the simplest finetuning setting-linear probing on low-dimensional representations 2 , data selection falls in the classical frames of coreset selection for linear regression [17, 18, 19, 20, 21, 22, 23, 24] and optimal experimental design [25, 26, 27, 28, 29] where the generalization gap can be reduced by selecting data that minimize the associated variance. However, for high-dimensional finetuning, variance minimization alone is insufficient to characterize the generalization due to 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 to capture a 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-dimensional structures of high-dimensional data/model motivates a natural question:Can the low intrinsic dimension be leveraged in data selection for high-dimensional finetuning?Low intrinsic dimension leads to variance-bias tradeoff in data selection. We provide a positive answer to this question through a variance-bias tradeoff perspective. Intuitively, we consider a 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 finetuning parameter space to find a suitable S and the variance by "exploiting" the useful knowledge in 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 to a 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 low-dimensional subspace.Gradient sketching finds a good low-dimensional subspace fast and provably. First, we construct a low-dimensional parameter subspace S by sketching the model gradients. Sketching [17, 31] is a well-established dimensionality reduction tool known for affordable and accurate low-rank approximations [32, 33] . 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 to preserve the fast-rate generalization O(dim(S)/n), linear in the low intrinsic dimension dim(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-dimensional subspace S via moment matching. The variance of data selection is characterized by matching between the sketched gradient moments of the original and selected datasets, Σ, Σ S , formally tr( Σ Σ † S ). 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 [36, 37] , we introduce a continuous relaxation with a 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 a rigorous generalization analysis on 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 a low-dimensional parameter subspace S with small bias, reducing variance over which preserves the fast-rate generalization O(dim(S)/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, a scalable two-stage data selection method for finetuning that simultaneously "explores" the high-dimensional parameter space via gradient sketching and "exploits" the information in the low-dimensional subspace via moment matching.Coreset selection and low-rank approximations. From the variance-bias tradeoff perspective, data selection for high-dimensional finetuning can be viewed as a combination of (i) variance reduction in coreset selection for linear regression [17, 18, 19, 21, 23, 24] with low-dimensional features, and (ii) bias reduction via sample-wise low-rank approximation for high-dimensional matrices [38, 39, 40, 41, 42, 43, 44, 45, 46] .Gradient sketching. Gradient sketching [17, 32] based on Johnson-Lindenstrauss transforms (JLTs) [31, 47] has achieved impressive recent successes in efficient data selection [16] and attribution [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).Moment matching and optimal experimental design. Moment matching is an intuitive idea for selecting low-dimensional data (i.e., overdetermined with coreset size n larger than data/representation dimension r), bearing various objectives like the A/V-optimality [28, 29] from optimal experimental design (OED) [25, 26, 27] . While classical OED studies the overdetermined scenario with n ≥ r, efforts have been made to extend the notion of V-optimality beyond the overdetermined setting [48, 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 instead of relying on labels 4 , leverages the geometry of the feature space and aims to select samples that are spread out, with a broad spectrum of concretizations including herding [51, 52] , k-center greedy [53] , leverage score sampling [24, 54, 55] , adaptive sampling [44, 56] , and volume sampling [39, 41] .An inspiring recent work [57] investigates the generalization of weakly supervised data selection via independent sampling in the low-(n → ∞ with fixed r) and high-dimensional (n, r → ∞ with n/r → constant) asymptotics. Instead of the asymptotic regime, we consider a realistic setting with finite n and r, 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 [5, 63, 64, 65] , and heuristics based on losses and their gradients [66, 67, 68, 69] ).Given any n ∈ Z + , we denote [n] = {1, • • • , n}. Let e n be the n-th canonical basis of the conformable dimension; I n be the n × n identity matrix; and 0 n , 1 n ∈ R n being vectors with all entries equal to zero and one, respectively. Let S n-1 := {x ∈ R n |∥x∥ 2 = 1} be the unit sphere in R n , and ∆ n := p ∈ [0, 1] b ∥p∥ 1 = 1 be the dimension-n probability simplex. We adapt the standard asymptotic notations: for any functions f, g : R+ → R + , we write f = O (g) or f ≲ g if there exists some constant C > 0 such that f (x) ≤ Cg(x) for all x ∈ R + ; f = Ω (g) or f ≳ g if g = O (f ); f ≍ g if f = O (g) and f = Ω (g). For any matrix A ∈ R n×d , let s 1 (A) ≥ • • • ≥ s rank(A) (A)≥ 0 be the singular values; and A † be the Moore-Penrose pseudoinverse.Additionally for any k ≤ rank (A), let ⟨A⟩ k = argmin B: rank(B)≤k ∥A -B∥ F be the optimal rankk approximation of A (characterized by the rank-k truncated SVD). For any symmetric matricesA, B ∈ R d×d , we write A ≽ B or A -B ≽ 0 if A -B is positive semidefinite. 
data selection for finetuning: 
 Given a data space X ⊆ R d and a label spaceY ⊆ R, let D = {(x i , y i ) ∈ X × Y | i ∈ [N ]} be a large dataset, with matrix form (X, y) ∈ R N ×d × R N , for some downstream task where the performance is measured by a loss function ℓ : Y × Y → R ≥0 .Finetuning. Let F be a class of prediction functions where each f = h • ϕ ∈ F can be expressed 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 F |ϕ ⊆ F as the class of finetuned models based on ϕ. Assume that for every(x i , y i ) ∈ D, y i ∼ P (y | x i ) i.i.d. such that there exists f ϕ * ∈ F |ϕ with respect to ϕ satisfying (i) E [y i | ϕ (x i )] = f ϕ * (x i ), and (ii) V [y i | ϕ (x i )] ≤ σ 2for some σ > 0 (which will be formalized later in respective settings).Data selection. Instead of finetuning on the entire dataset D, we aim to select a small coreset D S ⊆ D of size n ≪ N where the generalization is close. Precisely, let D S be indexed by S ⊂ [N ] and denoted as(X S , y S ) ∈ R n×d × R n . With L D S (f ) = 1 n (x,y)∈D S ℓ (f (x), y) and a regularization R : F |ϕ → R ≥0 associated with a hyperparameter α ≥ 0, we want f S = argmin f ∈F |ϕ L D S (f ) + α • R (f ) to provide a low excess risk over D: ER (f S ) := 1 N N i=1 ℓ(f S (x i ), f ϕ * (x i )).Warming up with linear probing, we concretize the general assumption on the ground truth (i.e.,E [y i | ϕ (x i )] = f ϕ * (x i ) = ϕ (x i ) ⊤ θ * and V [y i | ϕ (x i )] ≤ σ 2 ) as follows: Assumption 2.1 (linear probing ground truth). Assume y = ϕ (X) θ * + z for some θ * ∈ R r where z = [z 1 , • • • , z N ] ⊤ ∈ R N consists of i.i.d. entries with E [z] = 0 N and E zz ⊤ ≼ σ 2 I N .Consider the pre-trained representations ϕ(X) ∈ R N ×r and ϕ(X S ) ∈ R n×r with respective momentsΣ ϕ := 1 N ϕ (X) ⊤ ϕ (X) and Σ ϕ S := 1 n ϕ (X S ) ⊤ ϕ (X S ). For low-dimensional linear probing with r ≤ n (s.t. rank(Σ ϕ S ) = r), the linear regression θ S = argmin θ 1 n ∥ϕ (X S ) θ -y S ∥ 2 2 has a unique solution with excess risk ER (θ S ) = ∥θ S -θ * ∥ 2 Σ ϕ5 controlled by Σ ϕ and Σ ϕ S , analogous to the V-optimality criterion [28, 29] in optimal experimental design:EQUATIONIf D S satisfies Σ ϕ ≼ c S Σ ϕ S for some c S ≥ n N , then E [ER (θ S )] ≤ c S σ 2 r n (proof in Appendix B.1), where c S characterizes the variance controlled by D S , i.e., smaller c S implies lower variance.Despite its simplicity, uniform sampling is often observed in practice to serve as a strong baseline for data selection [1] , especially when n is large. In the low-dimensional linear probing scenario, (1) provides a theoretical justification for such effectiveness of uniform sampling: Proposition 2.1 (Uniform sampling for low-dimensional linear probing (Appendix B.2)). Assume there exists (i) B ϕ > 0 such that ∥ϕ(x)∥ 2 ≤ B ϕ ∀ x ∈ D; and (ii) γ > 0 with Σ ϕ ≽ γI r . For S sampled uniformly (with replacement) over D, with probability at least 1 -δ over S,Σ ϕ ≼ c S Σ ϕ S for any c S > 1 if n ≳ B 4 ϕ γ 2 • r+log(1/δ) (1-1/c S ) 2 .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).Extending the analysis to general finetuning, we consider a set of r finetuning parameters θ ∈ R r 6 (potentially with r ≫ n) over a pre-trained model ϕ (e.g., θ can be the parameters of the last layer (i.e., linear probing), last few layers, the entire network, or the LoRA [70] matrices).Let F |ϕ = f ϕ (•; θ) : X → R θ ∈ R r be the finetuning function class. Without loss of generality, we assume zero initialization of θ such that f ϕ (•; 0 r ) corresponds to the pre-trained model. Analogous to the assumption in [16] , under locality constraint on θ (e.g., ∥θ∥ 2 < 1), the dynamics of finetuning falls in the kernel regime [71] where f ϕ can be approximated by its first-order Taylor expansion:f ϕ (x; θ) ≈ f ϕ (x; 0 r ) + ∇ θ f ϕ (x; 0 r ) ⊤ θ.Then, we formalize the ground truth as follows:Assumption 2.2 (Finetuning ground truth). Given the pre-trained ϕ, there exists a bounded ground truth θ * ∈ R r with ∥θ * ∥ 2 < 1 such that for all (x, y) ∈ D, (i)E [y | ϕ (x)] = f ϕ * (x) = f ϕ (x; θ * ), and (ii) V [y | ϕ (x)] ≤ σ 2 for some σ > 0.Intuitively, Assumption 2.2 implies that the pre-trained model f ϕ (•; 0 r ) has a reasonable zero-shot performance. Given any S ⊂ [N ] with |S| = n, let f ϕ (X S ; θ) ∈ R n and ∇ θ f ϕ (X S ; θ) ∈ R n×r be the evaluation of f ϕ (x; θ) and its Jacobian over X S at θ. We observe that with z := y -f ϕ (X; θ * ), Assumption 2.2 implies y -f ϕ (X; 0 r ) ≈ Gθ * + z where E [z] = 0 N and E zz ⊤ ≼ σ 2 I N ; while G := ∇ θ f ϕ (X; 0 r ) ∈ R N ×r is the Jacobian over D at initialization.Then in the kernel regime [71] , the finetuning objective min θ∈R r 1 n f ϕ (X S ; θ) -y S 2 2 + α ∥θ∥2 2can be well approximated by a ridge regression problem:EQUATIONRecall G := ∇ θ f ϕ (X; 0 r ) ∈ R N ×r and G S := ∇ θ f ϕ (X S ; 0 r ) ∈ R n×r . With the momentsΣ ϕ = 1 N G ⊤ G and Σ ϕ S = 1 n G ⊤ S G S , the excess risk ER (θ S ) = ∥θ S -θ * ∥ 2 Σ ϕ satisfies 7 :Theorem 2.2 (Main result I: variance-bias tradeoff (Appendix B.3)). Given S, let P S ∈ R r×r be an orthogonal projector onto some subspace S ⊆ Range(Σ ϕ S ), and P ⊥ S = I r -P S be its orthogonal complement. Under Assumption 2.1, there exists an α > 0 such that (2) satisfies E [ER (θ S )] ≤ variance + bias with (i) variance = 2σ 2 n tr(Σ ϕ (P S Σ ϕ S P S ) † ) and (ii) bias = 2 trΣ ϕ P ⊥ S ∥θ * ∥ 2 2. 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 a suitable S in the highdimensional parameter space, a computationally challenging problem addressed in Section 3.1.It is worth highlighting that Theorem 2.2 encapsulates both the low-and high-dimensional finetuning. For low-dimensional linear probing, (1) is a special case of Theorem 2.2 (up to constants) with P S = I r . While in high dimension, an intrinsic low-dimensional structure (e.g., Assumption 2.3) is necessary for the effectiveness of data selection 8 . 6 Notice that r is the dimension of the finetuning parameter space. For linear probing in Section 2.1, r is the same as the pre-trained representation dimension; but for general finetuning, r can be much larger. 7 Notice that for linear probing, f ϕ (x; θ) = f ϕ (x; 0r) + ∇ θ f ϕ (x; 0r) ⊤ θ with ∇ θ f ϕ (x; 0r) = ϕ (x). Therefore, the finetuning objective can be exactly formulated as (2) , and the excess risk of high-dimensional linear probing satisfies Theorem 2.2 with Σ ϕ := 1 N ϕ (X) ⊤ ϕ (X) and Σ ϕ S := 1 n ϕ (XS) ⊤ ϕ (XS). 8 Otherwise, if all directions of Range(Σ ϕ ) are equally important, with n ≪ r, θS learned from DS necessarily fails to capture the orthogonal complement of Range(Σ ϕ S ) and therefore E [ER (θS)] ≳ r -n. EQUATIONIn particular, with c S , σ ≲ 1, ∥θ * ∥ 2 2 < 1, and tr(Σ ϕ ) ≍ r (depending only on the low intrinsic dimension), the generalization achieves a fast rate O(r/n), independent of r ≫ r.In (3), (i) bias is reduced by exploring the parameter space for an S with small low-rank approximation error tr(Σ ϕ P ⊥ S ) ≤ 1 n tr(Σ ϕ ); while (ii) variance is reduced by exploiting information in S through moment matching, P S (c S Σ ϕ S -Σ ϕ )P S ≽ 0, where smaller c S means better exploitation. 
sketchy moment matching: 
 A gap between Corollary 2.3 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 D S that satisfies the exploration and exploitation conditions in Corollary 2.3.For high-dimensional finetuning with r ≫ n, a critical limit of Theorem 2.2 and Corollary 2.3 is that the large moment matrices Σ ϕ , Σ ϕ S are not invertible, storable, or even directly computable, due to the prohibitive cost. As a remedy, sketching [17, 32] via Johnson-Lindenstrauss transforms [31] is a classical dimensionality reduction strategy that gets increasing recent attention for gradient approximation in large-scale machine learning problems [16, 34] 10 . Remark 3.1 (Gradient sketching). In the high-dimensional setting with r ≫ n, to reduce the dimensionality of the gradients G = ∇ θ f ϕ (X; 0 r ) ∈ R N ×r with a low intrinsic dimension r ≪ min {N, r} (Assumption 2.3), we draw a Johnson-Lindenstrauss transform [31] (JLT, formally in Definition C.1) Γ ∈ R r×m that projects the dimension-r gradients to a lower dimension m ≍ r ≪ r: G = GΓ ∈ R N ×m . One of the most common constructions of JLT is the Gaussian embedding (i.e., a Gaussian random matrix with i.i.d. entries Γ ij ∼ N (0, 1/m) discussed in Lemma C.3, vide Remark C.1 for a brief overview of various (fast) JLTs and their efficiency).While sketching is known for preserving Euclidean distances [31] and providing accurate low-rank approximations [17, 32, 33] , whether gradient sketching can convert Theorem 2.2 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.1)). Under Assumption 2.2 and 2.3 with a low intrinsic dimension r ≪ min {N, r}, draw a Gaussian embeddingΓ ∈ R r×m (Lemma C.3) with m ≥ 11r. Let Σ ϕ := Γ ⊤ Σ ϕ Γ and Σ ϕ S := Γ ⊤ Σ ϕ S Γbe the sketched gradient moments. For any D S with n > m samples such that rank(Σ ϕ S ) = n, and the ⌈1.1r⌉-th largest eigenvalue s ⌈1.1r⌉ ( Σ ϕ S ) ≥ γ S for some γ S > 0, with probability at least 0.9 over Γ, there exists α > 0 where (2EQUATIONComparing ( 4) with (3), we observe that by controlling the variance with Σ ϕ ≼ c S Σ ϕ S in low dimension m ≍ r ≪ r, gradient sketching preserves the fast-rate generalization O(m/n) = O(r/n) up to constants. That is, gradient sketching implicitly finds a random subspace S ⊆ Range(Σ ϕ S ) (vide ( 9)) that satisfies the exploration assumption in Corollary 2.3. Meanwhile, the choice of sketching size m balances the tradeoff between variance and sketching error: a larger m reduces the sketching error at the cost of higher variance. Such tradeoff is optimized at m = tr (Σ ϕ )/γ S .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 dataD S satisfies Σ ϕ ≼ c S Σ ϕ S for some c S ≥ n N , we have tr( Σ ϕ ( Σ ϕ S ) † ) ≤ c S m and ∥ Σ ϕ ( Σ ϕ S ) † ∥ 2 ≤ c S upperbounded, leading to the fast-rate generalization in (4).Algorithm 3.1 Sketchy Moment Matching (SkMM)1: Input: f ϕ (•; 0 r ), n ≪ N , m < n, c S ∈ [ n N , 1]. 2: Draw a (fast) Johnson-Lindenstrauss transform Γ ∈ R r×m (Remark 3.1). 3: Compute gradient sketching G = ∇ θ f ϕ (X; 0 r ) Γ ∈ R N ×m . (Remark 3.4) 4: Compute the spectral decomposition of Σ ϕ = 1 N G ⊤ G ≽ 0: Σ ϕ = VΛV ⊤ where (a) V = [v 1 , • • • , v m ] ∈ R m×m consists of the orthonormal eigenvectors, and (b) Λ = diag (λ 1 , • • • , λ m ) contains descending eigenvalues λ 1 ≥ • • • ≥ λ m ≥ 0. 5: Initialize s = [s 1 , • • • , s N ] with s i = 1n on n uniformly sampled i's and s i = 0 elsewhere. 6: Let diag(s) ∈ R N ×N be a diagonal matrix with s on diagonal. Optimizing:EQUATION7: Output: S ⊂ [N ] by sampling n data from s ∈ ∆ N without replacement.While directly minimizing tr( Σ ϕ ( Σ ϕ S ) † ) involves integer programming and pseudoinverse, causing hard and numerically unstable optimization, Σ ϕ ≼ c S Σ ϕ S has a straightforward relaxation (vide Remark 3.2), leading to the simple and stable moment matching objective (5) in Algorithm 3.1.Remark 3.2 (Relaxing Σ ϕ ≼ c S Σ ϕ S to (5)). Given the spectral decomposition Σ ϕ = VΛV ⊤ , Σ ϕ ≼ c S Σ ϕ S can be rewritten as V ⊤ ( 1 n G ⊤ S G S )V ≽ 1 c S Λ, and (5) is a relaxation: (i) instead of enforcing Σ ϕ ≼ c S Σ ϕ S strictly, constraints are only imposed on the diagonal 11 : v ⊤ j ( 1 n G ⊤ S G S )v j ≥ λ j /c S , j ∈ [m]; and (ii) the selection of S is relaxed to a weight vector s ∈ ∆ N with linear constraints 0 ≤ s i ≤ 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 Σ ϕ ( Σ ϕ S ) † in the low-dimensional subspace can be realized via various methods, including leverage score sampling [18, 19, 72, 73, 74] and V-optimal experimental design [28, 29] . We provide brief discussions on these alternatives in Appendix A.2.  
experiments 4.1 synthetic high-dimensional linear probing: 
 To ground the theoretical insight on variance-bias tradeoff in high-dimensional finetuning, we simulate linear probing with a synthetic underdetermined ridge regression problem 12 .Figure 2 : Selecting n = 80 data (colored in red) from the GMM dataset. Intuitively, a coreset D S with low bias contains at least one sample per cluster; whereas a low-variance D S selects more data from clusters with larger variance. We recall from Theorem 2.2 that the variance-bias balance is essential for good generalization. Setup. We consider a set of N = 2000 samples with high-dimensional pre-trained representations ϕ(X) ∈ R N ×r , r = 2400, modeled by a Gaussian mixture model (GMM) consisting of r = 8 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 (2) over the selected coreset of n samples with hyperparameter α tuning. The empirical risk is evaluated over the full datasetEQUATION2 (vide Appendix D.1 for implementation details). Data selection. For SkMM (Algorithm 3.1), we use a sketching dimension m = 4r = 32 and set c S = 0.999. We optimize (5) via Adam [75] with constraint projection under learning rate 10 -7 for 10 4 iterations and sample S from s ∈ ∆ N with the lowest objective value.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 k-center greedy [53] . Specifically, (i) SkMM, truncated leverage score (T-leverage), and ridge leverage score sampling (R-leverage) can be viewed as different ways of variance-bias balancing; (ii) adaptive sampling (Adaptive) and k-center greedy (K-center) focus on bias reduction (i.e., providing good low-rank approximation/clustering for ϕ(X)); while (iii) Herding and uniform sampling (Uniform) reduce variance (vide Appendix D.2 for baseline details).We observe from Figure 2 and Table 1 that balancing the variance-bias tradeoff is crucial for the generalization of data selection in high dimensions. In particular, SkMM achieves the best empirical risk across different coreset sizes n, especially when n is small. While as n/N → 1, uniform sampling provides a strong baseline, coinciding with common empirical observations [1] .We further validate the effectiveness of SkMM on UTKFace [76] , a real-world regression dataset for age estimation. We finetune a randomly initialized classification head on top of the feature representation of CLIP [50] with Adam [75] and learning rate 10 -1 . We also retain those baselines from the above synthetic setup in this experiment. The results for linear probing are provided in Table 2 , where our method remarkably outperforms comparative baselines on UTKFace. 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%.While our analysis focuses on data selection for finetuning regression models, a natural question is whether the idea of SkMM applies to broader scopes. To answer this, we extend our empirical investigation to classification. In particular, we consider an 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.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 ≥ r for LP) and high-dimensional (i.e., r > n for FT) settings. For LP, we learn the last layer over the embeddings from a CLIP-pretrained ViT-B/32 [50] with a learning rate of 10 -1 . For FT 13 , we finetuning the last two layers of an ImageNet-pretrained ResNet18 [84] with a 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 are deferred to the appendix.Data selection. For SkMM-LP, the gradients (of the last layer) are given by the pretrained features from CLIP. For SkMM-FT, the gradients (of the last two layers) are calculated based on a random classification head. We tune the sketching dimension m ∈ {32, 64, 128, 256, 512} and the lower bound for slackness variables c S ∈ {0.6, 0.7, 0.8, 0.9}. Within suitable ranges, smaller m and larger c S lead to better performance in the low data regime. Intuitively, smaller m encourages variance reduction in a more compressed subspace, and larger c s leads to easier optimization. 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-based methods, Entropy, Margin, and Least Confidence [82] .Observations. We first observe that for both LP (Table 3 ) and FT (Table 4 ), SkMM achieves competitive finetuning accuracy on 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 to handle data selection among clusters of various sizes through variancebias balance (cf. synthetic experiments in Figure 2 ). Meanwhile, for LP in the low-dimensional setting (Table 3 ), uniform sampling provides a surprisingly strong baseline. This coincides with the theoretical insight from Proposition 2.1 and the empirical observations in [1] .5 Discussion, Limitations, and Future DirectionsWe 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 r, balancing which led to a fast-rate generalization O(r/n). For efficient control of such variance-bias tradeoff in practice, we introduced SkMM that first explores the high-dimensional parameter space via 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.In this work, we focus only on moment matching via optimization inspired by the analysis for variance reduction after gradient sketching. Nevertheless, there is a 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. In 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.Given any matrixA ∈ R n×d , along with indices i ∈ [n], j ∈ [d], I ⊆ [n], and J ⊆ [d], let [A] i,jbe the (i, j)-th entry of A, [A] i be the i-th row (or the i-th entry if A ∈ R n is a vector), and [A] :,j be the j-th column; A I = [A] I,: consists of rows in A indexed by I; and let A I,J = [A] I,J be the submatrix of A with rows indexed by I and columns indexed by J.A.2 Alternatives to Moment Matching Heuristic in Remark 3.2In addition to the moment matching heuristic in Remark 3.2, variance in the resulting low-dimensional subspace from gradient sketching can be controlled by Σ ϕ ( Σ ϕ S ) † via alternative methods like leverage score sampling and V-optimal experimental design.Remark A.1 (Leverage score sampling). Leverage score sampling [18, 19, 72, 73, 74] provides arguably one of the most intuitive ways for selecting data based on G ∈ R N ×m . In particular, [17, Theorem 17] implies that for a coreset of size at least n = Ω(m log(m/δ)ϵ -2 ) drawn i.i.d. with replacement via leverage score sampling over G, c S ≤ (1 + ϵ) m τ S N with probability at least 1 -δ, where τ S ∈ [0, 1] is the minimum leverage score of G over the coreset S. 14 Such dependence on τ S can render the upper bound of c S vacuous when τ S → 0.Nevertheless, when τ S is reasonably large, leverage score sampling based on G can be computed more efficiently than SkMM in O(N m 2 ) time and can provide good control over c S . While both SkMM and leverage score sampling can facilitate variance reduction in the low-dimensional subspace, SkMM provides better empirical performance (cf. Section 4.1) at a slightly higher cost in the low intrinsic dimension m (vide Remark 3.4) as it 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] on G ∈ R N ×m . For example, [29] provides a polynomial-time algorithm to find a (1 + ϵ)-estimation of the V-optimal design for G with a coreset of size at least n = Ω(mϵ -2 ); and c S is effectively controlled by the V-optimality criterion tr( Σ ϕ ( Σ ϕ S ) † ).While such V-optimal design methods can provide good control over c S 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 algorithm in [29] consists of two stages: (i) solving a 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.1B.1 Proofs of (1)Proof of (1) and beyond. Under the assumption rank (ϕ (X S )) = r, both ϕ (X S ) , ϕ (X) have full column rank. Therefore ϕ (X S ) † ϕ (X S ) = ϕ (X) † ϕ (X) = I r , and θ S = ϕ (X S ) † y S . Then, since y = ϕ (X) θ * + z and y S = ϕ (X S ) θ * + z S , we haveθ S -θ * = ϕ (X S ) † y S -θ * = ϕ (X S ) † ϕ (X S ) θ * -θ * + ϕ (X S ) † z S = ϕ (X S ) † z S ,which leads toE [ER (θ S )] = E 1 N ∥ϕ (X) (θ S -θ * )∥ 2 2 = tr 1 N ϕ (X) ⊤ ϕ (X) ϕ (X S ) † E z S z ⊤ S ϕ (X S ) † ⊤ =σ 2 tr 1 N ϕ (X) ⊤ ϕ (X) ϕ (X S ) ⊤ ϕ (X S ) -1 = σ 2 n tr Σ ϕ Σ ϕ S -1.Now we explain the necessity of assuming c S ≥ n/N for Σ ϕ ≼ c S Σ ϕ S : Remark B.1 (Lower bound of c S ). Since ϕ (X) ⊤ ϕ (X) ≽ ϕ (X S ) ⊤ ϕ (X S ), we observe that N Σ ϕ ≽ nΣ ϕ S , which implies Σ ϕ ≽ n N Σ ϕ S . Therefore, Σ ϕ ≼ c S Σ ϕ S isE S Σ ϕ S = E S 1 n x∈S ϕ (X) ϕ (X) ⊤ = E x ϕ (X) ϕ (X) ⊤ = Σ ϕ ,we have E S Σ ϕ S = I r . For any fixed unit vector z ∈ S r-1 , letZ i := z ⊤ Σ ϕ -1/2 ϕ (x i ) be random variables with randomness on i ∈ [N ]. Since ∥ϕ(x)∥ 2 ≤ B ϕ ∀ x ∈ D and Σ ϕ ≽ γI r , we observe that |Z i | ≤ Σ ϕ -1/2 ϕ (x i ) 2 ≤ B ϕ √ γ ∀ i ∈ [N ] is bounded. Therefore, Z i is B 2 ϕ γ-subGaussian, and Z 2 i -E Z 2 i = z ⊤ Σ ϕ S -I r z is 16EQUATIONBy recalling that Σ ϕ S -I r= max u∈S r-1 u ⊤ Σ ϕ S -I r u, Equation ( 6) for a fixed z ∈ S r-1 can be extended to the entire unit sphere S r-1 through an ϵ-net argument as follows. Recall that for any ϵ 2 > 0, there exists an ϵ 2 -net U ⊂ S r-1 such that |U| ≤ 1 + 2 ϵ2 r . Then, by the union bound,P max u∈U u ⊤ Σ ϕ S -I r u > ϵ 1 ≤ 1 + 2 ϵ 2 r exp - n 2 • ϵ 2 1 γ 2 16 2 B 4 ϕ = exp r log 1 + 2 ϵ 2 - n 2 • ϵ 2 1 γ 2 16 2 B 4 ϕ . That is, with probability at least 1 -δ, max u∈U u ⊤ Σ ϕ S -I r u ≤ ϵ 1 when n ≥ 512B 4 ϕ γ 2 ϵ 2 1 r log 1 + 2 ϵ 2 + log 1 δ .By the construction of the ϵ 2 -net U, for all v ∈ S r-1 , there exists u ∈ U such that ∥u -v∥ 2 ≤ ϵ 2 . Therefore, for any v ∈ S r-1 , we havev ⊤ Σ ϕ S -I r v =u ⊤ Σ ϕ S -I r u + (v -u) ⊤ Σ ϕ S -I r (v -u) + 2 (v -u) ⊤ Σ ϕ S -I r u ≤ϵ 1 + Σ ϕ S -I r 2 ϵ 2 2 + 2ϵ 2 , which implies Σ ϕ S -I r 2 ≤ ϵ1 2-(1+ϵ2) 2. By taking ϵ 2 as a small constant (e.g.,ϵ 2 = 3/2 -1), we have Σ ϕ S -I r 2 ≤ 1 -1 c S when n ≳ B 4 ϕ γ 2 • r + log (1/δ) (1 -1/c S ) 2 .Proof of Theorem 2.2.With Σ ϕ = 1 N G ⊤ G, we have E [ER (θ S )] = E 1 N ∥G (θ S -θ * )∥ 2 2 = E ∥θ S -θ * ∥ 2 Σ ϕ ,Observing that by the optimality of θ S , we have2 n G ⊤ S (G S θ S -y S ) + 2αθ S = 0 r . Recalling that Σ ϕ S := 1 n G ⊤ S G S , this implies θ S = 1 n G ⊤ S G S + αI r -1 1 n G ⊤ S y S = 1 n Σ ϕ S + αI r -1 G ⊤ S (G S θ * + z S ) = Σ ϕ S + αI r -1 Σ ϕ S θ * + 1 n Σ ϕ S + αI r -1 G ⊤ S z S . Therefore, with E z [z] = 0 N , E [ER (θ S )] can be decomposed the bias term and variance terms as follows:E [ER (θ S )] = E ∥θ S -θ * ∥ 2 Σ ϕ =E z Σ ϕ S + αI r -1 Σ ϕ S -I r θ * + 1 n Σ ϕ S + αI r -1 G ⊤ S z S 2 Σ ϕ = Σ ϕ S + αI r -1 Σ ϕ S -I r θ * 2 Σ ϕ Bias + E z 1 n Σ ϕ S + αI r -1 G ⊤ S z S 2 Σ ϕ.Since E z z S z ⊤ S ≼ σ 2 I n , the variance term can be bounded asVariance ≤ σ 2 n tr Σ ϕ S + αI r -1 Σ ϕ Σ ϕ S + αI r -1 Σ ϕ S ≤ σ 2 n tr Σ ϕ Σ ϕ S + αI r -1, where the second inequality follows from the fact that Σ ϕ S + αI r -1Σ ϕ S 2 ≤ 1.Recall that P S ∈ R r×r is an orthogonal projector onto any subspace S of Range Σ ϕ S , and P ⊥ S = I r -P S is the orthogonal projector onto its orthogonal complement. By observing that Σ ϕ S + αI r ≽ P S Σ ϕ S P S + αP ⊥ S , since Range (P S ) ⊥ Range P ⊥ S , we haveΣ ϕ S + αI r -1 ≼ P S Σ ϕ S P S † + 1 α P ⊥ S .Therefore,Variance ≤ σ 2 n tr Σ ϕ P S Σ ϕ S P S † + 1 α tr Σ ϕ P ⊥ S .For the bias part, we first observe thatI r -Σ ϕ S + αI r -1 Σ ϕ S = α Σ ϕ S + αI r -1.Therefore,Bias = Σ ϕ S + αI r -1 Σ ϕ S -I r θ * 2 Σ ϕ = α Σ ϕ S + αI r -1 θ * 2 Σ ϕ =α 2 tr Σ ϕ S + αI r -1 Σ ϕ Σ ϕ S + αI r -1 θ * θ ⊤ * ≤α 2 tr Σ ϕ Σ ϕ S + αI r -2 ∥θ * ∥ 2 2 .Since , we have1 α * • σ 2 n tr Σ ϕ P ⊥ S + α * • ∥θ * ∥ 2 2 2 tr Σ ϕ P S Σ ϕ S P S † ≤2 σ 2 n tr Σ ϕ P ⊥ S • ∥θ * ∥ 2 2 2 tr Σ ϕ P S Σ ϕ S P S † ≤ 1 √ 2 σ 2 n tr Σ ϕ P S Σ ϕ S P S † + tr Σ ϕ P ⊥ S ∥θ * ∥ 2 2 .Therefore overall, we haveE [ER (θ S )] ≤ 2σ 2 n tr Σ ϕ P S Σ ϕ S P S † + 2 tr Σ ϕ P ⊥ S ∥θ * ∥ 2 2 .Proof of Corollary 2.3. Given P S (c S Σ ϕ S -Σ ϕ )P S ≽ 0 and rank (P S ) ≍ r, the variance term is asymptotically upper bounded byvariance = 2σ 2 n tr Σ ϕ P S Σ ϕ S P S † ≲ σ 2 n • c S r.Meanwhile, given tr(Σ ϕ P ⊥ S ) ≤ N n tr(Σ ϕ -⟨Σ ϕ ⟩ r ) and tr(Σ ϕ -⟨Σ ϕ ⟩ r ) ≤ tr Σ ϕ /N , the bias term can be asymptotically upper bounded by bias = 2 trΣ ϕ P ⊥ S ∥θ * ∥ 2 2 ≤ 2 n tr Σ ϕ ∥θ * ∥ 2 2 .The result follows from Theorem 2.2 by combining the variance and bias terms. . Under Assumption 2.2 and 2.3 with a small intrinsic dimension r ≪ min {N, r}, for any δ ∈ (0, 1), draw a Gaussian random matrix Γ ∈ R r×m with i.i.d. entries from N (0, 1/m) where m ≍ k/δ for some k ≥ 1.1r. Let Σ ϕ := Γ ⊤ Σ ϕ Γ and Σ ϕ S := Γ ⊤ Σ ϕ S Γ be the sketched gradient moments. For any S ⊆ [N ] with n > m samples such that (i) rank(Σ ϕ S ) = n, and (ii) the k-th largest eigenvalue s k ( Σ ϕ S ) ≥ γ S for some γ S > 0, with probability at least 1 -δ over Γ, there exists α > 0 where (2) satisfiesE [ER (θ S )] ≲ σ 2 n tr Σ ϕ ⟨ Σ ϕ S ⟩ † k (variance) + σ 2 n 1 mγ S Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ (sketching error) + 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ ∥θ * ∥ 2 2(bias) .If S further satisfies Σ ϕ ≼ c S Σ ϕ S for some c S ≥ n N , taking m = max{ tr (Σ ϕ )/γ S , 1.1r/δ} leads toEQUATIONWe start by introducing some helpful notations for the proofs. Let G := ∇ θ f ϕ (X; 0 r ) ∈ R N ×r and G S = [G] S ∈ R n×r be the original gradients of D and D S , respectively. Recall that Σ ϕ = G ⊤ G/N and Σ ϕ S = G ⊤ S G S /n are the corresponding second moments. We consider a Johnson-Lindenstrauss transform (JLT) [31] Γ ∈ R r×m as follows:Definition C.1 (JLT [18] (adapting [17, Definition 3])). For any ϵ > 0, δ ∈ (0, 1), and n ∈ N, a random matrix Γ ∈ R r×m is a (ϵ, δ, k)-Johnson-Lindenstrauss transform ((ϵ, δ, k)-JLT) if for any U ∈ R r×k consisting of k orthonormal columns in R r , with probability at least 1 -δ,I k -U ⊤ ΓΓ ⊤ U 2 ≤ ϵ.Definition C.2 (JL second moment property [87] (adapting [17, Definition 12] )). For any ϵ > 0, δ ∈ (0, 1), a random matrix Γ ∈ R r×m satisfies the (ϵ, δ)-JL second moment property ifE Γ ⊤ u 2 2 -1 2 ≤ ϵ 2 δ ∀ u ∈ S r-1 .Lemma C.2 (Approximated matrix-matrix multplication [87] (adapting [17, Theorem 13])). Given ϵ > 0, δ ∈ (0, 1/2), and a random matrix Γ ∈ R r×m satisfying the (ϵ, δ)-JL second moment property (Definition C.2), for any matrices A, B each with r rows,Pr A ⊤ ΓΓ ⊤ B -A ⊤ B F > 3ϵ ∥A∥ F ∥B∥ F ≤ δ.One of the most classical constructions of a JLT with JL second moment property is the Gaussian embedding:Lemma C.3 (Gaussian embedding [17, Theorem 6] ). For any ϵ > 0, δ ∈ (0, 1), a Gaussian random matrix Γ ∈ R r×m with i.i.d. entriesΓ ij ∼ N (0, 1/m) (i) is a (ϵ, δ, k)-JLT if m ≳ (k + log(1/δ)) ϵ -2 ; and (ii) satisfies the (ϵ, δ)-JL second moment property if m ≳ ϵ -2 δ -1 .Proof of Lemma C.3. The (ϵ, δ, k)-JLT condition follows directly from [17, Theorem 6] .To show the (ϵ, δ)-JL second moment property, we observe that for any u ∈ S r-1 , Γ ⊤ u 2 2 = u ⊤ ΓΓ ⊤ u is an average of m independent χ 2 random variables with mean 1 and variance 2, we haveE Γ ⊤ u 2 2 = 1 and its variance is E Γ ⊤ u 2 2 -1 2 = 2/m. Therefore, m ≳ ϵ -2 δ -1 leadsto the (ϵ, δ)-JL second moment property.Remark C.1 ((Fast) Johnson-Lindenstrauss transforms). While we mainly focus on the Gaussian embedding in the analysis for simplicity, there is a rich spectrum of JLTs with the JL second moment property [88, 89, 90, 91] , 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 on different JLTs and their applications, while briefly synopsizing two common choices and their efficiency as follows.(a) Subgaussian embedding [88] is a random matrix Γ ∈ R r×m with i.i.d. entries from a zeromean subgaussian distribution with variance 1/m. Common choices include the Rademacher distribution and Gaussian distribution (i.e., Gaussian embedding).Applying subgaussian embeddings to an N × r matrix A with nnz(A) ≤ N r nonzero entries takes O(nnz(A)m) ≤ O(N rm) 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.(b) Sparse sign matrix [89, 93] is a sparse random matrixΓ = r ξ [γ 1 , • • • , γ r ] ⊤ ∈ R r×m (ξ ∈ N)with i.i.d. rows γ j ∈ R m each consisting of ξ non-zero entries at uniformly random coordinates filled with Rademacher random variables. When ξ = 1, Γ is known as CountSketch [94] and requires as many as m = O(k 2 ) columns to satisfy the JLT property with constant distortion. Increasing the sparsity slightly, [95] showed that m = O(k log k) is sufficient for constantdistortion JLT when ξ = O(log k). In practice, [96] suggested that a small constant sparsity ξ ≥ 8 is usually enough for many applications like low-rank approximations.The sparse sign matrix can be applied to an N × r matrix A with nnz(A) nonzero entries in O(nnz(A)ξ) ≤ O(N rξ) time, independent of the sketching size m. With careful implementation, sketching via sparse sign matrices can be significantly faster than the subgaussian embeddings in practice [33, 43] .Let G := GΓ ∈ R N ×m and G S = G S Γ ∈ R n×m be the sketched gradients such thatΣ ϕ := Γ ⊤ Σ ϕ Γ = G ⊤ G/N ∈ R m×m , Σ ϕ S := Γ ⊤ Σ ϕ S Γ = G ⊤ S G S /n ∈ R m×m .In particular, for a Gaussian embedding Γ, when rank(Σ ϕ S ) = rank(G S ) = n, rank( Σ ϕ S ) = rank( G S ) = m almost surely.Recall the low intrinsic dimension r from Assumption 2.3. For any k ∈ N with 1.1r ≤ k < m, let P S ∈ R r×r be an orthogonal projector onto a dimension-k subspace S ⊆ Range(Σ ϕ S ):EQUATIONand P ⊥ S = I r -P S be its orthogonal complement. Throughout the proof of Theorem C.1, we assume the following:Assumption C.1. Let min {N, r} ≫ n > m > k ≥ 1.1r such that rank(Σ ϕ S ) = n. We consider a Gaussian embedding (Lemma C.3) Γ ∈ R r×m with m ≍ k such that s k ( Σ ϕ S ) ≥ γ S for some γ S > 0.Proof of Theorems 3.1 and C.1. We first recall from Theorem 2.2 thatE [ER (θ S )] ≤ 2σ 2 n tr Σ ϕ P S Σ ϕ S P S † + 2 tr Σ ϕ P ⊥ S ∥θ * ∥ 2 2 .Lemma C.4 suggests that for m ≍ k/δ, with probability at least 1 -δ/2,tr Σ ϕ P S Σ ϕ S P S † ≲ tr Σ ϕ ⟨ Σ ϕ S ⟩ † k + n mγ S tr Σ ϕ P ⊥ S .Therefore,E [ER (θ S )] ≲ σ 2 n tr Σ ϕ ⟨ Σ ϕ S ⟩ † k + σ 2 mγ S + ∥θ * ∥ 2 2 tr Σ ϕ P ⊥ S .Then, applying Lemma C.7 with the union bound, we havetr Σ ϕ P ⊥ S ≲ 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕwith probability at least 1 -δ. This impliesE [ER (θ S )] ≲ σ 2 n tr Σ ϕ ⟨ Σ ϕ S ⟩ † k + 1 mγ S Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ + 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ ∥θ * ∥ 2 2 .If S further satisfies Σ ϕ ≼ c S Σ ϕ S for some c S ≥ n N , then we havetr Σ ϕ ⟨ Σ ϕ S ⟩ † k ≤ tr Σ ϕ ( Σ ϕ S ) † ≤ c S m, Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 ≤ Σ ϕ ( Σ ϕ S ) † 2 ≤ c S .Therefore, ( 7) can be further simplified asE [ER (θ S )] ≲ c S σ 2 n m + tr Σ ϕ mγ S + c S n tr Σ ϕ ∥θ * ∥ 2 2 .On the right-hand-side, the first (variance) term is minimized at m = tr (Σ ϕ )/γ S where m + tr Σ ϕ /(mγ S ) ≤ 2 tr (Σ ϕ ) /γ S = 2m. In addition, incorporting the assumption that m ≍ k/δ for some k ≥ 1.1r, we take m = max{ tr (Σ ϕ )/γ S , 1.1r/δ} and getE [ER (θ S )] ≲ c S σ 2 n m + c S n tr Σ ϕ ∥θ * ∥ 2 2 = c S n σ 2 m + tr Σ ϕ ∥θ * ∥ 2 2 .Theorem 3.1 is simplified from Theorem C.1 by taking k = ⌈1.1r⌉ and δ = 0.1.Lemma C.4. For any δ ∈ (0, 1), let Γ ∈ R r×m be a Gaussian embedding (Lemma C.3) with m ≍ k/δ columns. Then, with probability at least 1 -δ over Γ,tr Σ ϕ P S Σ ϕ S P S † ≲ tr Σ ϕ ⟨ Σ ϕ S ⟩ † k + n mγ S tr Σ ϕ P ⊥ S .Proof of Lemma C.4. We first observe that since rank(Σ ϕ S ) = n implies G S G † S = I n , G S P S Γ = G S G † S ⟨ G S ⟩ k ⟨ G S ⟩ † k G S Γ = ⟨ G S ⟩ k ⟨ G S ⟩ † k G S = ⟨ G S ⟩ k , and therefore, G(G S P S ) † = argmin Z∈R N ×n ∥G -ZG S P S ∥ 2 F + ∥Z∥ 2 F and G⟨ G S ⟩ † k = argmin Z∈R N ×n = ∥(G -ZG S P S )Γ∥ 2 F + ∥Z∥ 2 Fis an approximated solution from a sketched least square problem. EQUATION.SinceEQUATIONAccuracy of sketched least square solution. To upper bound G(G S P S ) † -G⟨ G S ⟩ † k F, we first observe from (10) thatG(G S P S ) † -G⟨ G S ⟩ † k 2 F ≤ ϵ 2 (G S P S ) † 2 2 GP ⊥ S 2 F . G S P S G ⊤ S = ⟨ G S ⟩ k ⟨ G S ⟩ † k G S G ⊤ S . Since rank (G S ) = n, Lemma C.6 implies that for a Gaussian embedding Γ, G S G ⊤ S ≽ O m n G S ΓΓ ⊤ G ⊤S with high probability. Therefore,G S P S G ⊤ S ≽ O m n ⟨ G S ⟩ k ⟨ G S ⟩ † k G S G ⊤ S = O m n ⟨ G S ⟩ k ⟨ G S ⟩ ⊤ k . Recall that ⟨ Σ ϕ S ⟩ k = 1 n ⟨ G S ⟩ ⊤ k ⟨ G S ⟩ k and s k ( Σ ϕ S ) ≥ γ S , we have (G S P S ) † 2 2 = (G S P S G ⊤ S ) † 2 ≤ O n m ⟨ G S ⟩ ⊤ k ⟨ G S ⟩ k † 2 ≤O n m 1 nγ S = O 1 mγ S .Therefore, applying a union bound gives that with probability at least 1 -δ over Γ,EQUATIONTo upper bound G(G S P S ) † 2 F , we observe that by (11) ,G(G S P S ) † 2 F ≤2 G⟨ G S ⟩ † k 2 F + 2 G(G S P S ) † -G⟨ G S ⟩ † k 2 F ≲ G⟨ G S ⟩ † k 2 F + ϵ 2 mγ S GP ⊥ S 2 F .Finally, normalizing by multiplying n/N on both sides givestr Σ ϕ P S Σ ϕ S P S † ≲ tr Σ ϕ ⟨ Σ ϕ S ⟩ † k + ϵ 2 n mγ S tr Σ ϕ P ⊥ S .Taking any small constant ϵ > 0 completes the proof.Lemma C.5 (Adapting [17, Theorem 23] ). For any ϵ > 0 and δ ∈ (0, 1),let Γ ∈ R r×m b a (1/2, δ/2, k)-JLT (Definition C.1) with (ϵ/ √ k, δ/2)-JL second moment property (Definition C.2). Given A ∈ R r×n with rank(A) = k and B ∈ R r×N , let W = argmin W Γ ⊤ (AW -B) 2 F + ∥W∥ 2 F , W * = argmin W ∥AW -b∥ 2 F + ∥W∥ 2 F .Then, with probability at least1 -δ over Γ, A( W -W * ) F ≤ ϵ ∥AW * -B∥ F .Proof of Lemma C.5. Analogous to the proof of [17, Theorem 23] , let A = QR be a reduced QR decomposition of A such that Q ∈ R r×k is an orthonormal basis for Range(A), and R ∈ R k×n . Reparametrizing Z = R W and Z * = RW * , up to constant scaling of ϵ, it is sufficient to showQ( Z -Z * ) F = Z -Z * F ≤ O(ϵ) ∥QZ * -B∥ F . Since Γ ∈ R r×k is an (1/2, δ/2, k)-JLT, we have I k -Q ⊤ ΓΓ ⊤ Q 2 ≤ 1/2 with probability at least 1 -δ/2 and Z -Z * F ≤ Q ⊤ ΓΓ ⊤ Q( Z -Z * ) F + Q ⊤ ΓΓ ⊤ Q( Z -Z * ) -( Z -Z * ) F ≤ Q ⊤ ΓΓ ⊤ Q( Z -Z * ) F + I k -Q ⊤ ΓΓ ⊤ Q 2 Z -Z * F ≤ Q ⊤ ΓΓ ⊤ Q( Z -Z * ) F + 1/2 Z -Z * F which implies Z -Z * 2 F ≤ 2 Q ⊤ ΓΓ ⊤ Q( Z -Z * ) 2 F with probability at least 1 -δ/2.By the normal equation of the sketched least square problem,Q ⊤ ΓΓ ⊤ Q Z = Q ⊤ ΓΓ ⊤ B. Thus, Z -Z * 2 F ≤ 2 Q ⊤ ΓΓ ⊤ (QZ * -B) 2 F . Since Q ⊤ (QZ * -B) = -Q ⊤ I r -QQ ⊤ B = 0 k×N and Γ has (ϵ/ √ k, δ/2)-JL second moment property, Lemma C.2 implies that with probability at least 1 -δ/2, Q ⊤ ΓΓ ⊤ (QZ * -B) 2 F ≤ O ϵ 2 /k ∥Q∥ 2 F ∥QZ * -B∥ 2 F = O(ϵ 2 ) ∥QZ * -B∥ 2 F .Then, by the union bound, with probability at least 1 -δ over Γ, we haveZ -Z * 2 F ≤ 2 Q ⊤ ΓΓ ⊤ (QZ * -B) 2 F ≤ O(ϵ 2 ) ∥QZ * -B∥ 2 F .Lemma C. 6 ([97] ). For a random matrix Ω ∈ R n×m (n > m) consisting of i.i.d. subgaussian entries with mean zero and variance one, with high probability,O √ n - √ m 2 I n ≼ ΩΩ ⊤ ≼ O √ n + √ m 2 I n .Lemma C.7. Under Assumption 2.3, let Γ ∈ R r×m be a Gaussian embedding (Lemma C.3) such that there exists m > k ≥ 1.1r satisfying s k ( Σ ϕ S ) ≥ γ S for some γ S > 0. Then, with probability at least 1 -exp (-Ω(r)), trΣ ϕ P ⊥ S ≲ 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ .Proof of Lemma C.7. Here we follow a similar proof strategy as [43, Theorem 1] . Let Π S := [I N ] S ∈ R n×N be the selection matrix associated with S ⊆ [N ]. We introduce the following N × N oblique projectors:M S := GG † S ⟨ G S ⟩ k ⟨ G S ⟩ † k Π S , M S := G⟨ G S ⟩ † k Π S .In particular, M S and M S are the oblique projectors since withΠ S G = G S and G S G † S = I n , M 2 S =GG † S ⟨ G S ⟩ k ⟨ G S ⟩ † k G S G † S ⟨ G S ⟩ k ⟨ G S ⟩ † k Π S =GG † S ⟨ G S ⟩ k ⟨ G S ⟩ † k Π S = M S , and with Π S G = G S , M 2 S = G⟨ G S ⟩ † k G S ⟨ G S ⟩ † k Π S = G⟨ G S ⟩ † k Π S = M S .Recalling P S from (9), we observe the following identities:EQUATIONsinceEQUATIONandEQUATIONCombining ( 12), (13) , and ( 14), we haveEQUATION)EQUATION.Since P ⊥ S 2 2 = 1, this implies tr Σ ϕ P ⊥ S = 1 N ∥GP S ∥ 2 F = 1 N I N -M S I N -G⟨ G S ⟩ † k ⟨ G S ⟩ k G † GP † S 2 F ≤ 1 N I N -M S 2 2 I N -G⟨ G S ⟩ † k ⟨ G S ⟩ k G † G 2 F .By the operator norm identity for projectors [98] , we haveI N -M S 2 2 = M S 2 2 = G⟨ G S ⟩ † k Π S 2 2 = G⟨ G S ⟩ † k 2 2 = N n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2, and therefore,tr Σ ϕ P ⊥ S ≤ 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 I N -G⟨ G S ⟩ † k ⟨ G S ⟩ k G † G 2 F . Since G⟨ G S ⟩ † k ⟨ G S ⟩ k G † is a rank-k orthogonal projector onto Range G⟨ G S ⟩ † k = Range G Γ⟨ G S ⟩ † k and Gaussian embeddings are rotationally invariant, G⟨ G S ⟩ † k ⟨ G S ⟩ k G † shares the same distribution as (GΩ)(GΩ) † for a r × k Gaussian embedding Ω with [Ω] i,j ∼ N (0, 1/k) i.i.d.. Then, we observe that ∥(I N -G⟨ G S ⟩ † k ⟨ G S ⟩ k G † )G∥ 2F is the rank-k randomized range-finder error of G, which can be controlled according to Lemma C.8: with probability at least 1 -exp (-Ω(r)), trΣ ϕ P ⊥ S ≲ 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 ∥G -⟨G⟩ r ∥ 2 F = N n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ -⟨Σ ϕ ⟩ r .By the definition of r in Assumption 2.3, tr Σ ϕ -⟨Σ ϕ ⟩ r ≤ tr Σ ϕ /N and thus,tr Σ ϕ P ⊥ S ≲ 1 n Σ ϕ ⟨ Σ ϕ S ⟩ † k 2 tr Σ ϕ .Lemma C.8 (Randomized range-finder error (simplifying [32, Theorem 10.7])). Let Ω ∈ R r×k be a Gaussian embedding with [Ω] i,j ∼ N (0, 1/k) i.i.d.. For any G ∈ R N ×r and r ∈ N such that 1.1r ≤ k ≪ min {N, r}, with probability at least 1 -exp (-Ω(r)),I N -(GΩ)(GΩ) † G F ≲ ∥G -⟨G⟩ r ∥ F .D Experiment Details for Section 4.1 D.1 Implementation Details Synthetic data generation. We consider a set of N = 2000 samples with high-dimensional pre-trained representations ϕ(X) ∈ R N ×r where r = 2400, modeled by a Gaussian mixture model (GMM) consisting of r = 8 well-separated clusters, each with random sizes and variances. Specifically, we generate the GMM dataset as follows:• Randomly partition the N samples into r = 8 clusters with sizes {N j | j ∈ [r]}.• For each j ∈ [r], generate the cluster mean µ j ∈ R r with µ j = (Z j r) • e j where Z j ∼ Unif([r]) and variance σ j = Z ′ j • σ max where Z ′ j ∼ Unif([0, 1]) and σ max = 0.04.• Generate representations ϕ(x i ) ∼ N (µ j , σ 2 j I r ) i ∈ [N j ] i.i.d. for each cluster j ∈ [r].• Draw a latent label generator θ g ∼ N (0 r , I r ). For each cluster j ∈ [r], assign the same label y i = µ ⊤ j θ g for all samples i ∈ [N j ] within the cluster. Ridge regression. We solve the ridge regression problem over the selected coreset D S of n samples and tune the regularization hyperparameter α via grid search over 100 linearly spaced values in [10 -2 , 10 2 ] with 2-fold cross-validation.We compare SkMM to the following unsupervised data selection methods for regression:(a) Uniform sampling (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 D S 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 of the GMM dataset, herding has more emphasis on variance reduction, as illustrated in Figure 2 .(c) K-center greedy [53] (K-center) provides a 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 a logarithmic factor.In practice, adaptive sampling generally achieves comparable accuracy to volume sampling for low-rank approximations, 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, 73, 74] (T/R-leverage) are the extensions of classical leverage score sampling [54] to high dimensions. In particular, leverage score sampling is originally designed for low-dimensional linear regression, while degenerating to uniform sampling in high dimensions. Consider the high-dimensional representations ϕ(X) ∈ R N ×r (r > N ) in our setting, for each i ∈ [N ],• leverage score:l i := ϕ(x i ) ⊤ (ϕ(X) ⊤ ϕ(X)) † ϕ(x i ),• truncated leverage score:l (m) i := ϕ(x i ) ⊤ (⟨ϕ(X)⟩ ⊤ m ⟨ϕ(X)⟩ m ) † ϕ(x i )for a given truncation rank m, and • ridge leverage score: l (ρ) i := ϕ(x i ) ⊤ (ϕ(X) ⊤ ϕ(X) + ρI r ) † ϕ(x i ) for a given regularization parameter ρ > 0. Larger ρ brings ridge leverage score sampling closer to uniform sampling. Therefore, both truncated and ridge leverage score sampling balance the variance-bias tradeoff by adjusting the truncation rank m and regularization parameter ρ, respectively.Baseline details. For both Herding and K-center, we adopt the DeepCore implementation [1] . Notice that Herding is a deterministic algorithm. For Adaptive, we use the implementation from [45] . For T-leverage, we use a rank-m truncated SVD to compute the leverage scores, with m = 4r = 32 as in SkMM (i.e., providing both methods approximately the same amount of information and compute). For R-leverage, we choose ρ = 10 3 . Finetuning Details We finetune the model for 50 epochs for both linear probing and finetuning using Adam optimizer with a learning rate 0.01.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?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 be numbered and cross-referenced.• All assumptions should be clearly stated or 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 are encouraged to provide a 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.Question: Does the paper fully disclose all the information needed to reproduce the main experimental 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 or 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.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a 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 to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a 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 (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to 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 to have some path to reproducing or verifying the results. 
open access to data and code: 
 Question: 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? Answer: [Yes] Justification: Our experiment code for both the synthetic and real data is available at https://anonymous.4open.science/r/data_pruning.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an 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 run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to 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 to understand the results?Answer: [Yes]Justification: We specify the experiments setting in the main context (subsection 4.1 ,subsection 4.3) and appendix (subsection D.1, subsection D.2) opensourced our code and scripts at https://anonymous.4open.science/r/data_pruning.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 a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes]• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a learning theory paper with no societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If 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., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This is a learning theory paper with no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? 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 asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Justification: https://anonymous.4open.science/r/data_pruning.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.• The paper should discuss whether and how consent was obtained from people whose asset is used.• At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: 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 as 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 be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: 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 on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we 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 applicable), such as the institution conducting the review.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 Section4.1 for some concretizations).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-shot accuracy (e.g., Assumption 2.2).For any u ∈ R r , ∥u∥ Σ ϕ := u ⊤ Σ ϕ u is the seminorm associated with Σ ϕ ≽ 0.We note that in 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 O(1/n). This is granted by the low-rankness of Σ ϕ S , which enables a more fine-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 our setting, we sketch the gradient of the pre-trained model f ϕ (x; 0r).This is equivalent to assuming that Σ ϕ , Σ ϕ S commute. While such assumption does not hold in general, it is a valuable heuristic whose effectiveness has been demonstrated in various domains[36,37].Our experiment code is available at https://github.com/Xiang-Pan/sketchy_moment_matchingWe notice that finetuning the last few layers of strong pretrained models like CLIP can distort the features and hurt the performance, as studied in[83]. Therefore, we stay with a weaker pretrained model for finetuning.Notice that τS appears because samples in S are equally weighted in the data selection setting, in contrast to the standard leverage score sampling where samples are weighted by the respective sampling probabilities. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

The 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.

The experimental results include fine-tuning on a synthetic linear task, as well as fine-tuning a vision transformer on CIFAR-10 image classification.
strength_weakness: strength_weakness: - 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? 
- 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?
- The literature review could be expanded, including relevant papers such as BADGE [1], Coreset-based sensitivity sampling [2].
- 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.
- Computing the moment-matching subset in Algorithm 3.1 seems overly complicated, see questions

[1]: Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds

[2]: Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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)

Also, 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: limitations: Yes, the authors discuss the limitations.
paper_summary: paper_summary: This paper addresses the problem of data selection for finetuning large pre-trained models. The key contributions are:

1. A theoretical analysis of data selection for finetuning that reveals a variance-bias tradeoff in high dimensions.
2. A provable result showing that gradient sketching can efficiently find a low-dimensional subspace that preserves fast-rate generalization.
3. 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.
4. Empirical validation on synthetic and real datasets demonstrating the effectiveness of the approach.
strength_weakness: strength_weakness: 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.
2. The method introduces new hyperparameters (e.g., sketching dimension, moment matching strength) without much guidance on how to set them optimally.
questions: questions: 1. Does the approach extend naturally to other finetuning scenarios beyond linear probing (e.g., adapters, full finetuning)?
2. How does the computational cost of SkMM compare to other data selection methods as the dataset/model size increases?
limitations: limitations: yes

Comments: comment: Thank you for your response on the questions! After reading the other reviews, I would like to keep my current score of 6.
Many thanks for the reply and the valuable suggestions. We will make sure to incorporate all the modifications described in the responses carefully in the revision.
I've raised my score to 5 in light of authors' responses. However, I do believe the paper would benefit a lot by one more careful iteration based on the revisions proposed by authors.
We are happy that our responses have addressed your concerns. Many thanks for the reply and all the constructive suggestions.
Thanks a lot for your response, as well as for all the helpful feedback.
I would like to thank the authors for their efforts to answer all of my questions. I have increased my score.
As the deadline for the discussion phase approaches, we would greatly appreciate it if the reviewer could provide some feedback on our responses, which we believe have addressed all the questions in the review. As a summary of important updates we made thanks to the valuable suggestions from the reviewer: 
* In Response 1 and General Response 1, we provided further clarification on the computational efficiency of SkMM and comparison with other data selection methods.
* In Response 2 and General Response 2, we discussed the connection and difference between SkMM and leverage score sampling in terms of moment matching, where such difference comes from, and why we may want an alternative to leverage score sampling.
* In Response 3, General Response 3, and the attached PDF, we provided stronger empirical evidence on (i) more real vision tasks and (ii) fine-tuning settings (beyond linear probing) with much higher dimensions, with (iii) more comprehensive baselines (including margin sampling) and (iv) more detailed experimental setup.

We value the opportunity to improve our work based on these constructive suggestions and are always happy to provide further clarifications if needed. Thanks again for your time.
Thanks for the additional experiments. I am raising my score to 5.
As the deadline for the discussion phase gets close, we would greatly appreciate it if the reviewer could provide some feedback on our responses, which we believe have addressed all the concerns raised in the review regarding the limited scope of the experiments. 

In particular, we kindly re-highlight the additional experiments in General Response 3 and the attached PDF where we provided stronger empirical evidence on (i) real data with more classes and class imbalance, as well as (ii) fine-tuning settings (beyond linear probing) with much higher dimensions (i.e., the highly over-parametrized settings). Meanwhile, we improved the comprehensiveness of our experimental details thanks to the suggestions from the reviewers (vide General Response 3).

We value the opportunity to improve our work based on these constructive suggestions and are always happy to provide further clarifications if needed. Thanks again for your time.
Many thanks for the timely response. We kindly refer the reviewer to the general responses for the list of important revisions we made, which we believe have accommodated all the suggestions and questions from the reviewers. If the reviewer found any unaddressed concerns, we would greatly appreciate it if they could specify them during the discussion phase. We are always happy to provide further clarifications and improve our work based on the constructive feedback from the reviewers.
I thank authors for the comments. I'll keep my score as I believe the paper will benefit from a significant amount of revisions by incorporating all reviewers' comments.