Towards a statistical theory of data selection under weak supervision
Authors: Germain Kolossov
Andrea Montanari
Pulkit Tandon
Venue: ICLR 2024 oral (2024)
Keywords: Data Selection
Empirical Risk Minimization
Influence Functions
High dimensional asymptotics
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Given a sample of size $N$, it is often useful to select a subsample of smaller size $n<N$ to be used for statistical estimation or learning.  Such a data selection step is useful to reduce the requirements of data labeling and the computational complexity of learning. We assume to be given $N$ unlabeled samples $x_{i}$, and to be given access to a  'surrogate model' that can predict labels $y_i$ better than random guessing. Our goal is to select a subset of the samples, to be denoted by {$x_{i}$}$_{i\in G}$, of size $|G|=n<N$. We then acquire labels for this set and we use them to train a model via regularized empirical risk minimization. By using a mixture of numerical experiments on real and synthetic data, and mathematical derivations under low- and high- dimensional asymptotics, we show that: $(i)$ Data selection can be very effective, in particular beating training on the full sample in some cases; $(ii)$ Certain popular choices in data selection methods (e.g. unbiased reweighted subsampling, or influence function-based subsampling) can be substantially suboptimal.

Published as a conference paper at ICLR 2024
TOWARDS A STATISTICAL THEORY OF DATA SELECTION UNDER WEAK SUPERVISION
Germain Kolossov, Andrea Montanari, Pulkit Tandon
Granica Computing, Inc.
{germain. kolkkkoooooooo andrea andrea. http://ww.aaaaaaataaaaa.aaaaaaaa
ABSTRACT
Given sample of size N, it is often useful select subsample of smaller size n < N to be used for statistical estimation or learning. Such a data selection step is useful reduce the requirements of data labeling and the computational complexity of learning. We assume to be given N unlabeled samples (x: Jen, and to be given access
"surrogate model' that predict labels y, better than random guessing. Our goal is to select a subset of the samples, to be denoted by Hæe of size |G| = n N. We then acquire labels for this and we use them to train a model via regularized empirical risk minimization. By using a mixture of numerical experiments on real and synthetic data, and mathematical derivations under low- and high- dimensional asymptotics, we show that: (+) Data selection can very effective, in particular beating training on the full sample in some cases; (ti) Certain popular choices in data selection methods (e.g. biased reweighted subsampling, or influence function- subsampling) can be substantially suboptimal.
INTRODUCTION
Labeling is notoriously laborious task in machine learning. possible approach towards reducing this burden is to select small subset of training samples that are most valuable for training.
Data selection beasee learning consists of two steps - (i) Data Selection: given feature vectors X
(æs)igN, select subset G C [N] of size n (or close to rt); (ii) Training: having acquired labels for the selected subset bea, train a model f((:;) RP I (with parameters 0) on the labeled
data { hte. Throughout this paper will focus methods with the following structure.
In the first step, set G generated by selecting each datapoint independently with probability n, n (m:)) Namely
II E Gly, X) = TT, independently for i S N.
(1.1)
The second step (training) is carried out by (weighted) empirical risk minimization (ERM) over the selected set G. Namely, given loss function f R R + ER and regularizer Ω RP + R, we solve
arg min min
(0),
( = N
Σ w; C(y, (a 0)) + X (0
(1.2)
iEG
The weights wi can depend on the feature vectors, and are designed as to reduce the error. A popular choice is w; = cst/n; because the resulting (() ) is an unbiased version of the full empirical risk.
Throughout this paper, will assume data (a,, yi) to be i.i.d. samples from common distribution Pe Rdd x R. and will evaluate a data selection procedure via the test error:
Rec (0) = E lve (Ynow I (Nnew; 0))
(1.3)
where expectation taken with respect to the test sample (Iaews Byen)) P. We will denote the (training) population risk by R(0) E (v: f(x;0) 0)).
Data selection has been extensively studied in a variety of settings, including experimental design, active learning, leaminng algorithms and data optimization. While some heuristics (e.g., focus

---

Published as a conference paper at ICLR 2024
Full data
Unblased, Weak surrogate
Misclassification Rate
12%
Unbiased, Strong surragate
Blased, Weak surragate
Bissed, Strong surregate
11%
Randern samp lnn
10%
9%
complng
8%
20%
40%
60%
80%
Percentage of data subsampled
Figure Misclassification error in an image classification problem after data selection (logistic regression on SwAV embeddings). Left: N = 34345 samples, p = 2048 dimensions. We use surrogate models trained on small separated fraction of the data ('strong": : No, 14720, 'weak': No. 1472). Right plots: subsampling schemes optimized over ridge regularization X; exponent a the data selection scheme (larger a select 'harder' samples); biased vs unbiased selection; and strength of the surrogate. Constant strategy: biased selection with À 0.01, 0.5, and weak surrogate. Top: = 3434; bottom N 34345. See Section
samples that are most difficult to predict) have resurfaced from different viewpoints, their imple- mentation and effectiveness depends the problem formulation. Unlike the most common active learning scenario, we crucially assume to be given a fixed data sample [æsJign (without labels) and carry out single data selection step, often referred 'Pool-based active learning' (Settles 2012).
Before summarizing our contributions, it is useful to mention some of the existing approaches.
Bayesian methods. Within Bayesian setting, select the subsample G is minimize the ditional entropy of 0 given the data Lindley (1956); SSung et al. (1992). This is a first example of "uncertainty sampling." " We refer to Houlsby al. (2011): Gal al. (2017) for recent pointers, with a focus on online active learning. See Cui et al. (2021) for a recent exception.
Heuristic approaches. Several groups developed measures of the impact of each sample on the model: Lewis & Gale (1994) use probabilities predicted by single current model; Vodrahalli et al. 2018 use the norm of Vol f(z,, Tijg al. (2019) use the loss itself Ely: f(z O)).
Leverage scores have been used for long time in statistics as measure of importance of a data point E NN. linear regression (Chatterjee & Hadi 1986). Recall that the leverage of sample 2; is defined as Hú; := [x - Their study was reinvigorated by a numerical linear algebra perspective (Drineas & Mahoney| 2006 Drineas et al., (201]). Statistical analyses of leverage score-based data selection was developed in Ma et al. 2014); Raskutti & Mahoney (2016); Ma et al. 20022). These works all assume w; 1/TT, for unbiasedness.
D4.
Influence functions. Let 0, = arg ming R(0) denote the population minimizer. For M- estimators (.2 (under regularity conditions) approximate linearity holds
oc for p
fixed (van der Vaart 2000)
0 0- 0.
Σ wob(w, vi) or(1/vn), IEG
the so-called influence function. This approximation can be used to select the probabilities т; and weights w,. Several authors have developed this approach in the context of generalized linear models, while assuming unbiasedness w; 1/T,, resulting in the choice n. & [, 31)]l2 (Ting& & Brochu 2018 Wang et al. 2018 Ai et al. (202)). Wang et al. (2020) shows potential for improvement by using biased schemes. These works assume a specific asymptotics in which 1 < < N. In many applications, would like the generalization error achieved from the nusubsampl to be comparable to the one with full sample and hence focus on the case >N, 7 @(1)
where RP
2

---

Published as a conference paper at ICLR 2024
Margin-based selection. In a recent paper Sorscher et perceptron, under a noiseless teacher-student distribution, selecting samples far from the margin is beneficial in nigh-dimensional
(2022) show that, in the case of the binary
data-poor regime. This is in stark contrast with influence- function and related approaches that upsample data points whose labels are more difficult to predict. While our results confirm these findings, measuring uncertainty in terms of distance from the margin is somewhat specific to binary classification under certain distributional assumptions [
2
DEFINITIONS
Since our objective is to alleviate the need to label data, will focus on data selection schemes that do not use the labels (Wi)seN. On the other hand, we will assume to have access to a surrogate model (c)(()) which is a probability kernel from Rd to R. We will consider two settings (i) Ideal surrogate: In this case P.. (dylar) [z)] P(dylaz) is the actual conditional distribution of the labels. Of course this is the very object we want to learn. Since learning scheme is constrained, the (tt) Imperfect surrogates: In this case P (dylzz) (z)) is predictive of the actual value of the labels, but does not coincide with the Bayes predictor.
problem is nevertheless non-trivial and informative.
The selection probabilities тं and weights w, can depend æ; and (- la:;) (the conditional distribution of Yi given 2; under the surrogate). We will omit the dependence of the surrogate predictions unless needed, and write मं = (2;)). wy = w(x)).
It is convenient to encode a general data selection process into random variables S. 2 0 which depend on æ;, P.. lae,), and also on additional randomness independent across different sample We recover the original formulation by setting (z;)) w(x;) 1ee, P(i E G| y) T (2;). We can thus rewrite the empirical risk (1.2) as:
N
R (
Σ
(x 1(0;0;,2;) x.) + A y();y, = Ely. fa: 0))
(2.1)
We will enforce that the target sample size n is achieved in expectation, namely
Σ BT(W)), T(x,) :- P(, 0 x,
(2.2)
Definition 2.1. data selection scheme unbiased if E((()))) X, y) 1. We denote the set of unbiased data selection schemes by U.
Throughout, we consider n. N + oo, with converging ratio n/N + E 1). We refer to ry as the "subsampling fraction.' We are interested in 7 bounded away from 0 because want keep the accuracy close to the full sample accuracy. Standard notations are summarized in Appendix A
3 SUMMARY OF RESULTS
Our theory is based two types of asymptotics, that capture complementary regimes. In Section 4 we will study the fow-dimensional asymptotics, whereby is fixed as n. N + co. This analysis applies fairly general data distributions and models [(:: ) In Section 5 will instead assume - oo as NN + co, with N/p + d E (0, cc). In this case we study convex M-estimators, for models that linear in the features H,. Namely, L(O: yi, x;) ((0, (e)):;)). with L. convex in its first argument, and x; standard Gaussian. We next summarize some of the insights from our work and illustrate them in Figure (experiments with real data, described in Section 7
Unbiased subsampling can be suboptimal. As mentioned in the introduction, the majority of theoretical studies assumes unbiased subsampling: w, x 1/T,. We show both theoretically and em- pirically that this can lead to potentially unbounded loss in accuracy with respect to biased schemes.
Sorscher et al. 2022 proposes also schemes that are empirically effective more generally, but the connec- tion with their mathematical analysis is indirect.
Formally, (x,, sU,, n. where is deterministic function and (U))gx aaddd Unif ((0, 1))-
3

---

Published as a conference paper at ICLR 2024
Low-diments -ow-dimensional asymptotics provide compelling explanation: estimation error is inversely pro- portional to the curvature of the expected risk. Unbiased methods do not change the curvature, while biased methods
increase the curvature. In fact, will prove that unbiased methods are subop- timal under a broad set of conditions. This result illustrated in Figure [ In particular, in Figure we compare a biased and unbiased scheme (with selection probabilities which approximate the influence-function scheme).
Optimal selection depends on the subsampling fraction. Popular data selection methods are in- dependent of subsampling fraction in the sense that the selection probabilities т; can be computed without knowing the target sampling fraction n/N, except from the overall normalization that en- (.2). In contrast, we will see that optimal schemes depend in non-trivial way on n/N. This is very natural: the utility of sample (ar, yi) depends on the other selected samples.
forces the constraint
Better surrogate models do not always lead to better selection. How to proceed in absence of the labels ys? A natural idea would be to start from selection probabilities that use the labels, To(ys, æz)), and then take a conditional expectation with respect to yi. under the surrogate model: T (æ;) = E { To (Yi, u.)[æ;; We show that this is not always optimal, and in particular better surrogate models do not always lead to better selection (if used in plugin fashion as described).
Uncertainty-based subsampling is effective. The simplest rule of thumb emerging from our work confirms earlier research: subsampling schemes based on how uncertain surrogate predictions are, often perform well. On the other hand, influence-based subsampling is not generally optimal. First:
in low-dimension, stronger bias towards hard examples is beneficial, cf. Section 4.2 Second: in certain nigh-dimensional cases, this bias must be reversed, and 'easier' examples should be selected, Section (in agreement with horshhrrr et al. (2022)) Third, adding nuance the previous point, selecting the 'hardest' or 'easiest" even in high dimension, is not always optimal, see e.g. Section 6
Data subsampling can beat full-sample training. Our objective is to select fraction Y E (0. 1) of the data such that, training on the selected subset yields test error close to training on the whole dataset. To our surprise, see Figure [ we discover that good data selection can actually reduce the test error below the one obtained from the full sample for as small as 0.4. A naive explanation would be that information being passed from the surrogate model to the trained model via data selection. While this is of course true, the effect is more subtle. Indeed, we achieve reduction in test error even when the surrogate model is trained on significantly less than (1 - > random samples (so that overall, we are using significantly less than N labels). Recent empirical studies (Nakkiran et al., 202I; Guo et al. [022; Yang et al. 2022, Sorscher et al., [2022] Gadre et al.) al.| (2224) have observed similar phenomenon for deep models with real data but we show that this is true even for simpler settings.
4 LOW-DIMENSIONAL ASYMPTOTICS
In this section we study the classical asymptotics in which is fixed as n, N - co. The asymptotics of Ô depends on the expectation of the empirical risk (
(+) = S{S(z) L(0;
(4.1)
(In this notation, the argument S indicates the dependence on the function that defines the sub- sampling procedure.) The conditional gradient covariance, and conditional Hessian will play an important role, and are defined below (recall that 0, = arg mingg(()))
G(z) = E v.
x)
|
H H(x) : E( x))
(4.2)
We consider weighted quadratic error ||0 - 1.1 = (0 (0-01 1 0.)). where Q E RPxp. This covers both the standard & estimation error (by setting Q = I) and, under smoothness conditions, the test error Riza () (setting Q = R (f.)). We define the asymptotic error coefficient via
E 0 0. 11 p(S: Q)/N + Opp(N)).
(4.3)
In other words, p(S: Q) lim NE θ 0. 0.11) A general formula for p(S: follows from standard arguments (see Appendix B). In the next two sections, we discuss optimal choices of the subsampling procedure under this asymptotics.
4

---

Published as a conference paper at ICLR 2024
4.1 UNBIASED DATA SELECTION
We begin by considering unbiased schemes, cf. Definition 2.1 This case is covered by earlier work Ting Brochu (2018): Wang al. (2018): Ai et al. (2021), but provides useful context.
The key simplification is that, in the unbiased case, the matrix Hs (see Appendix
B does not
depend on S, namely H = H. where
H = R())).. R(O) = (L y.
(4.4)
We thus recover the standard subsampling scheme based on influence functions. (See Appendix
G
Proposition 4.1. Under the assumptions of Proposition B.
further assume Q > O, H > 0. Then
p(S: Q) is minimized among unbiased data selection schemes by scheme of the form: Sun(
Tamb (x) with probability (z) and Sunt (x) = O otherwise, where:
Tinb (2)) min ( 2(z)1/33
Z(x) := Tr(G QH = v. [z)
Here the constant c(t) is defined so that (x) (x)) = 7
Finally the the optimal coefficient Punt QQ == inssew p(S; Q) = =p((Sum Q) is given by
Punb Q inf Ex(x)==
E (<)))/((<)) E max /c2))
(4.5)
Denote by Smnnd random subsampling, i.e. Sama(() 1/7 with probability 7, and Sama (
else
(Stand is unbiased). We next establish some basic properties of Puno Pun (Q:7), cf. Appendix D
Proposition 4.2. Write Pum (Q:7) for the optimal unbiased coefficient when the subsampling frac-
tion equals 7, Then: (1) Punb (Q) S Prane (Q) with the inequality being strict unless Z(x) is almost
surely constant or 7 1; (2) 7 > Punn Q;7) is monotone non-increasing (for z 0).
Proof of this proposition is provided in Appendix D While monotonicity may appear intuitively obvious, we will see in the Section 4.3 that does not hold for biased subsampling.
Remark 4.1 (Connection with influence functions). Under the assumptions of Proposition 4.1 the influence function is (xx 9) = - H - VoL(O (0.:0. a)) and therefore we can rewrite (omitting the capping at 1) (xx;) oc [ [ (x; 11 xc 1/2 We recovered influence function-based subsam-
pling Ting & Brochu 20188;; Wang et al. (2018); Ai et al.) (202T). Interestingly, the optimal way to deal with unknown ys is to take conditional expectation of the square of the sampling probability:
we compute (xs,, vi Q xe )1/2 instead of [E{ (1v[((;;; ys y:)llgla:; [x:) See also Appendix C
Example 4.2 (Generalized linear models). We assume my to be centered vector and
P(dy ax;) = exp {yr (0,, v;)) - ((0((((0)) a.))) vo vody)))
(4.6)
Here Vo is the reference measure, e.g. Mu = 841 + 8_1 for logistic regression. We fit a model of the same type and train via the loss L(0: y, = ( x) of (0,z)) Hence VoL(0; y, x:)
- (y o' ())x))))=' and V2 R(0)) = E(0" (0, ())x)) } = H. A simple calculation yields:
Z(x) :e (0,,,, (1x H QH
(4.7)
In what follows, we will consider also a generalization of this model whereby (here, for each z, P(- is a probability distribution over R):
Pl Alæ;) P(A](0o) ax)))
(4.8)
Example 4.3 (Linear regression). Setting vo (dyy
sxp(-v//2)/4 /2T. <bt) f2/2 above,
obtain linear regression: L(0; y, x) = L @0 x)) = (y) - 2 Equation (4.7) yields (xx) x E "Q=-Ql "1)). and, for prediction error (Q = Σ), Z(x) x (x. E a)): we recover a population version of the leverage score.
5

---

Published as a conference paper at ICLR 2024
4.2 BIASED DATA SELECTION
We now consider biased subsampling schemes S. It is straightforward to see that the weights can always be chosen be deterministic (see Appendix F In other words, S(x) = w((x) with proba- bility (ar), and S(x) 0 otherwise, for two deterministic functions w, n. We can identify these data selection scheme with the pair (I,, w), hence we will also write p( wi Q) for p(S: Q)
Among these, we focus on 'nonrrewiighting schemes' that are defined by the additional condition and denote them by N. -on-reewig schemes are practically convenient since they do not require to modify the training procedure. Optimal non-reweighting schemes have a simple structure, as stated below. (See Appendix F))
Proposition 4.3. Under the assumptions of Proposition B. 1 further assume = 0.
0, ] O, and + G(z), H (xx) to be contimuous. Define G2 == G,
E(VaL(0,, y. x)(=)
म = E, (x)) where E,, f(x) == Ef ((x) / (()) Finally define the function
-(E;T) == -r(( "H,") 2T) "HH, "
(4.9)
Then there exists The achieving the minimum of the asymptotic error over non-reweighting schemes p(Turs Q) = sew p(S; Q). Further, if H mm > 0 strictly, then Tue takes the form
if Z (x;; War X
Th
< X, if Z (z; Ta)
if 7 [x; Ta)
(4.10)
[bxx) E [0,
= A.
where X and b(x)) are chosen so that (xTn(()) 7. The resulting optimal asymptotic error is (Q) 7 Tr(- H 1HHQHHII Run) 7-' Brr Tr(G,, H
In many cases of interest, the set far ((x; }} has zero measure (e.g. if x has a den- sity). Roughly speaking, the above implies that, under the non-reweighing scheme (and in the low- dimensional asymptotics) we should select the n examples with largest score ('hardest" examples).
Another important difference compared to the unbiased case is that the score is now computed with respect to the selected data, namely H is replaced by H As anticipated Section 3 the selected set depends y in nontrivial way.
We compare Par and Punb. proving that unbiased sampling can be arbitrarily worse than non- reweighting. (See Appendix G
Theorem 1, Consider least-squares under the model y; = (0., 2;) + Es, with ((E?l x.) = 72. For
any M, there is a distribution of x; and a 1) such that Puna E; 7)/ Pur Ein) M.
4.3 DATA SELECTION CAN BEAT SAMPLE ESTIMATION
One striking phenomenon illustrated in Figure 1 is that ERM with respect to selected subset of < N samples out of N total produces better model than ERM the full dataset. This is the case even when the surrogate model is trained on samples, with n., + n is significantly below N.
the non-monotonic behavior compatible with theoretical expectations? The answer depends on the data selection scheme (see Appendix H for details and an illustration): (i) Unbiased data selection always monotone, cf. Section 222 The optimal data selection scheme with reweighting also monotone by simple reduction argument. However, for n N, this scheme does not reduce to unweighted ERM, but to optimally weighted ERM. (iii) Finally, non-monotyyycity is possible in a neighborhood of
for non-reweighting schemes, established below (see Appendix D
Theorem 2. Assume æ; ~ N(O, Ia), and yi distributed according to Eq. (4.8). Lei Q H 2 R(O.). Then both for linear and logistic regression there exists P( ((A(t) such that y + Pa (Q:7) is monotone increasing in a non-empty interval (70. 1).
4.4 UNBIASED SUBSAMPLING EVER OPTIMAL?
We will next prove that, in natural setting, unbiased subsampling is always suboptimal below certain subsampling ratio. (The last condition is likely to be a proof artifact, cf. Appendix (J) We show in Appendix that the conditions below hold generically for generalized linear models.

---

Published as a conference paper at ICLR 2024
Theorem 3. Consider the setting of Proposition B. and consider the prediction error under test loss equal to training loss (i.e. Q= H := V²R (.)), Further assume: A1. For G(z) and H (x) defined as in Eqs (4.2), we have G(z) (x). (This is for instance the case in maximum likeli- hood); A2. G(x)) is almost surely non-zero has an almost sure upper bound; A3. The distribution of (T) H-)1/ is not not supported on any strict affine subspace of the set of d x d symmetric matrices. A4. E(VoL(O y, x) xx) 0.
Then there exists "o > O such that, for any E (0,7m) there is a biased subsampling scheme asymptotcallly outperforming the best unbiased scheme.
4.5 IMPERFECT SURROGATES
In a more realistic setting, the surrogate model P..(dy) does not coincide with the actual condi- tional distribution of Yi given T,. We model this situation using a minimax point of view. Namely, we assume that the actual conditional distribution is in neighborhood of the surrogate model, and study the worst case error in this neighborhood. The minimax theorem then implies that we should use data selection schemes that are optimal for the worst data distribution in this neighborhood. We will not pursue the construction of minimax optimal data selection schemes in this paper. However, point out that the broad conclusion is consistent with some of our empirical findings in Section Namely, in certain cases using a less accurate surrogate model yields better data selection. Theorems and examples are presented in Appendix K
5 HIGH-DIMENSIONAL ASYMPTOTICS: GENERALIZED LINEAR MODELS
We next study a high dimensional setting whereby the number of samples N and the dimension diverge simultaneously. More precisely, we assume ni N,P - oo with n/N + 7,, N/p - do for some 7, 6g E (0, oo). We will restrict ourselves to the case of (potentially misspecified) generalized linear models already introduced in Example 4.2 As we will see in this section and the next, the high-dimensional setting allow us to unveil few interesting phenomena, namely: (i) Biasing data selection towards hard samples (those that are uncertain under the surrogate model) can be suboptimal; (ti) Even when biasing towards hard samples is effective, selecting the top hardest one can lead to poor behavior at small 7; (iti) A one parameter family of selection probabilities introduced in the next section is broadly effective.
5.1 SETTING
Since our focus is on the surrogate model, we consider data distribution in which the covariates carry little or no information about the value of a sample. We assume x; ~ NO, I Ip), and (potentially misspecified) responses yi that depend on one-dimensional projection of the data, as per Eq. (4.8) This includes the general misspecified binary response model: y/: E (11,, and P(y = +1/x,)
I((0s. x;)) 11- P(y l1
We specialize the ERM procedure of Eq. 2. to
R~
1 1/2 N M
S,0 L(() vi) 1101
(5.1)
is a loss function (we abuse notations here). This is a special case of Eq. [2.1] in two ways: first, the loss depends on 0, x, only through (0)))) and, second, we focus on ridge regularizer. Our characterization will require to be convex in its first argument. As before, is understood that S:((0" s 2x;)) depends on some additional i.i.d. randomness. Denoting by
where L, R X
0, := arg min, Rx we will consider test error of the form R (0x) = EL... Tum)) Vnew).
Because of the rotational invariance the behavior of the empirical risk minimization 5.1) depends on the surrogate model only through two parameters (P)) is the projector orthogonal to 0o):
0o)
Bo =
B,
= lim
|
(5.2)
N 00
1
N.p
'The population risk minimizer 0. does coincide necessarily with Og. We have O. c. c.00/ 10ol|-
7

---

Published as a conference paper at ICLR 2024
5.2 ASYMPTOTICS OF THE ESTIMATION ERROR
The high-dimensional asymptotics of the test error is determined by saddle point of the following Lagrangian (here and below (aKn Oss 0 B = (5o, BB, 0), Or0,- = (oo, Okay 0)):
Laa, p. w)
X ||ll 2 G= G-oo, G. G1) N(O, 13).
E min HER
S(13. L() L((ao, +u.))+++++ - |
260
Y~ P( P(-1110|])
(5.3)
(Expectation with respect the randomness in S is implicit in the symbol E.)
Theorem 4. Assume u L(u.8) y) is convex, continuous, with most quadratic growth, and X 0.
Further denote by x", 11" the solution of the following minimax problem (a* uniquely defined by this condition)
min max L (o,
(5.4)
Then the following hold in the limit N.p- + oc, with N/p - 8o: If (u, 2) + (u; P)dy))) is continuous function with at most quadratic growth, we have
p-lim Resa (0x) ELus (añGo + (aa22² + (a)) N.p
(5.5)
where expectation is taken with respect the joint distribution of Eq. 5.3 subsampling fraction is given by n/N + = (PS(33 + B,G,) > 0).
Further, the asymptotic
The proof of Theorem 4 is deferred to Appendix [ which also contains corollaries for special cases
(see also Appendix M
6 NUMERICAL RESULTS: SYNTHETIC DATA
In this section we present numerical simulations within the synthetic data model introduced in Sec- tion 5.1 for binary labels y; {+1, -1. Summarizing, we generate isotropic feature vectors a; N,O, I,), and labels with P(y: = +1 S((0.. mz)). We then perform data selection, with selection probability
TI (Tx)) min (c(T) 100 a.) p((0", mn)))) 1):
(6.1)
where p((0" xx,) (1 20 = 1 is the probability of y: +1 under the surrogate model. We fix the constant c(7) so that EiSN (xx,)= n..
Hence, a > 0 upsamples data points with higher uncertainty under the surrogate model ('difficult' data), while < 0 upsamples data points with lower uncertainty ('easy' data). We then fit ridge regularized logistic regression to the selected data (cf. Eq. (5.1)) and evaluate misclassification error on hold-out test set. For large-dimng dimensinnnnion d, ciltencce-uunctonn based subsampling essentially corresponds to the case a = 1/2 of Eq. 66. (see Appendix for proof).
Figure 2 compare the results of simulations (circles) and theoretical predictions (continuous lines) for different 5o, X. We consider two misspecified models defined by (here r = 0.95 = 17. <= 0.7 (): 77.400 f2(2) = (1.-- u.5 + ( + (os=<u.s) + (1,20.5.
[1()) =
we report similar plots both for well- specified and misspecified models, exploring the effect of signal strength and of imperfect surrogates (cf. Figure
Here we use an ideal surrogate: 0 = Oo. In Appendix N
The agreement between theoretical predictions and simulation results is excellent in all the experi- ments. Theory correctly predicts that, for a suitable choice of a, the non-reweighted data selection scheme of Eq. 6..1 achieves nearly identical test error as full data, while using few 40% of the
*The code reproduce theory and simulations with synthetic data be found the github repo
8

---

Published as a conference paper at ICLR 2024
30%
A- D.1.PYY 11
A-0.1, PLY-
1at-1--------0 560
D.1.PPY 1i -is---1-----
A-0.1, FIY 1pd 560
45%
23/h-
Misclacificaloon
608
48%
23%
40%
475
1.95
30%
2.05
35%
7. 0. 01, PY-1jjt 11yy111p--- 1j2t-ff0 100
- 01. 110 100--500
7.- 0.00 11) 1121-1i0
-- 01. PY 1000-100--00000 5600
3995
6.9%
2315
Mise Matteiitaaaionn
6.%
48%
23%
407
15%
30%
48%
10%
45%
A000003, PW (uy) (11)
A- PW (110
1-0.003./1Y
35%
6.%
25%
45%
4.%
29%
40%
35%
47%
15%
1.0%
43%
80% Percentage subsampled
Percentage subsampled
subsampled
Percentage subsampled
Figure Misclassification error for logistic regression after non-reweighted subsampling, cf. Eq. (..1). under misspecified model F(y 1|=) == f(z), where (0n, æ).. Circles are results of numerical simulations, and continuous lines are theoretical predictions. Colors represent different values of the exponent a in Eq. (..1). Left plot: N 34345, 932: Right plot: N 6870, p 3000. Each panel corresponds a different choice of f. X. (See main text.)
samples. The optimal choice of a is highly dependent on the setting, with < broadly outper- forming a > 0 when the number of samples per dimension is smaller (Figure 6). Also, we observe qualitatively different behaviors for misspecified model. Notably: (i) Learning after data selection often outperforms learning on the full sample; (ti) Upsampling 'hard' datapoints (i.e. using a 0) most often the optimal strategy with respect the well-specified case. (iii) Upsampling "easy" datapoints can be beneficial in the small y regime; (iv) For small and certain choices of on, a we observe interesting non-monotonicities of error: smaller sample sizes lead to lower misclassification
error. This is related to suboptimality of that value of a and scheme (6.1) (see Section 4.3)
7 NUMERICAL RESULTS: REAL DATA
For our real-data experiments we used an Autonomous Vehicle (AV) dataset and a binary classifica- tion task. As for synthetic data, use ridge regularized logistic regression and study data selection under the one-parameter scheme of Eq. (6. This model was trained and tested on unsupervised features extracted from image data. Appendix O provides the details of the dataset and experiments, and further empirical results supporting the claims.
Figure I (left) shows test error for optimal À and 0.5 fixed, for unbiased and non-reweighted (biased) subsampling, using 'weak' and 'strong' surrogate models. Note that: (i) Restricting to 'un- biased' data selection unnecessary and sometimes harmful; (ii) The efficacy of weakly supervised data-selection methods is not highly sensitive to the quality of the surrogate (see also Figure 9 in Appendix O
Figure I (right) shows test error for the optimal parameters {X, surr, bias}, selected by minimizing the misclassification rate on the validation set. The reported results are computed on the test set. We compare this optimal choice by a "constant strategy' that uses À = 0.01, = 0.5, non-reweighted subsampling and weak surrogate models. This constant strategy performs almost optimally when N is large, and still provides consistent improvements over random subsampling when N is smaller. This strategy reflects cefluence-functtio based subsampling. although without reweighting and using weak surrogate model. This figure highlights that: (t) Selection criteria based the 'uncertainty" associated to the label data point are effective, however influence function can be suboptimal; (ii) Learning after data selection outperform learning on the full sample.

---

Published as a conference paper at ICLR 2024
REFERENCES
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization error in neural networks. Neural Networks, 132:428 446, 2020.
Mingyao Ai, Jun Yu, Huiming Zhang, and Ying Wang. Optimal subsampling algorithms for big data regressions. Statistica Sinica, 31(2):749-772, 2021.
Stéphane Boucheron, Gáhor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory Independence. Oxford University Press, 2013.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.
Unsupervised learning of visual features by contrasting cluster assignments, 2021.
Samprit Chatterjee and Ali Hadi. Influential observations, high leverage points, and outliers in linear regression. Statistical science, pp. 379-393, 1986.
Hugo Cui, Luca Saglietti, and Lenka Zdeborovà. Large deviations in the perceptron model and consequences for active learning. Machine Learning: Science and Technology, 2(4):045001, 2021.
Petros Drineas and Michael W Mahoney. Sampling algorithms for 1 2 regression and applications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 127 1136, 2006.
Petros Drineas, Michael W Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische mathematik, 117(2)221-249)) 2011.
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 Neural Information Processing Systems, 36, 2024.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International conference on machine learning, pp. 1883-192. PMLR, 2017.
Chengeheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A comprehensive library for coreset selec- tion in deep learning. In International Conference on Database and Expert Systems Applications, pp. 181-195. Springer, 2022.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986 2022.
Neil Houlsby, Ferenc Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv:1112.5745, 2011.
Angela H Jiang, Daniel L-K Wong, Giulio Zhou, David Andersen, Jeffrey Dean, Gregory Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, and Zachary C Lipton. Accelerating deep learning by focusing on the biggest losers. 1wXi::9110000722 2019.
David D Lewis and William A Gale. A sequential algorithm for training text classifiers. In SIGIR 94; Proceedings of the Seventeenth Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, organised by Dublin City University, pp. 3-12. Springer, 1994.
Yiyi Liao, Jun Xie. and Andreas Geiger. KITTI-360: A novel dataset and benchmarks for urban scene understanding in 2d and 3d. Pattern Analysis and Machine Intelligence (PAMI), 2022.
Friedrich Liese and Klaus-J Miescke. Statistical decision theory. In Statistical Decision Theory: Estimation, Testing, and Selection, pp. 1-52. Springer, 2008
Dennis V Lindley. On a measure of the information provided by an experiment. The Annals of Mathematical Statistics, 1044) 1956.
10

---

Published as a conference paper at ICLR 2024
Ping Ma, Michael Mahoney, and Bin Yu. A statistical perspective algorithmic leveraging. In International conference on machine learning, pp. 91-99. PMLR, 2014.
Ping Ma, Yongkai Chen, Xinlian Zhang, Xin Xing, Jingyi Ma, and Michael W Mahoney. Asymptotic analysis of sampling estimators for randomized numerical linear algebra algorithms. The Journal of Machine Learning Research, 23(1):970-8014, 2022.
Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4):2313 2335, 2021.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, (121(12):24003, 2021.
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau. M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Garvesh Raskutti and Michael Mahoney. statistical perspective on randomized sketching for ordinary least-squares. The Journal of Machine Learning Research, 17(1):750--755 2016.
Burr Settles. Active learning. Morgan & Claypool, 2012. Volume 6 of synthesis lectures artificial intelligence and machine learning.
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 287-294, 1992.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neu- ral scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 15:33-9919 2022.
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. Regularized linear regression: A precise analysis of the estimation error. Proceedings of Machine Learning Research, 40: 10:1663-7709, 2015.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8):5592-566 2018.
Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. Advances in neural information processing systems, 31, 2018.
Aaad W van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000.
Kailas Vodrahalli, Ke Li, and Jitendra Malik. Are all training examples created equal? an empirical 2018.
study.
Yaig Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. Journal of the American Statistical Association, 113(522):829-8k) 844, 2018.
Zifeng Wang, Hong Zhu, Zhenhua Dong, Xiuqiang He, and Shao-Lun Huang. Less is better: Un- weighted data subsampling via influence function. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 6340-6347, 2020.
Shuo Yang, Zeke Xie, Hanyu Peng, Min Xu. Mingming Sun, and Ping Li. Dataset pruning: Re- ducing training data by examining generalization influence. arXiv preprint arXiv:2205.09322 2022.
11

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
Standard notations
13
B Low-dimensional general asymptoties: Ideal surrogate
13
Proof Proposition 4.1
Proof Proposition 4.2
E Biased data selection: Definitions
15
Proof of Proposition 4.3
16
Differences between unbiased and biased data selection: Examples
17
Linear regression: Proof Theorem
Generalized linear models
H
Monotonicity properties of biased data selection
19
Beating full-sample estimation using data selection: Low-dimensional asymptotics
20
L.1 Proof of Theorem 5
20
1.2 Proof of Theorem
21
1.3 Proof Theorem
22
Proof of Theorem 3
24
K
dineeiinnl asymptotics: Imperfect surrogates
24
K 1 Plugin schemes
25
Minimax formulation
25
Duality and its consequences
26
L High nigh-dimenniooal asymptotics: General version Theorem
28
M High-dimensional asymptotics: The case of misspecified linear regression
33
M.I Proof of Proposition M.2
34
Synthetic data numerical experiments
34
Real data numerical experiments
37
Dataset
37
0.2
Experiment Setup
37
0.3 Additional results
37
Some useful formulas for binary classification
39
12

---

Published as a conference paper at ICLR 2024
A STANDARD NOTATIONS
The unit sphere in dimensions is denoted by 3d-1, Given two symmetric matrices A, B E Rdxd, we write A = B if A B positive semidefintte, and A Bf A strictly positive definite. We denote by p-lim,,-s Xn the limit in probability of sequence of random variables (Xn)n21- We use Op( ), op(.) and so on for the standard Oh-notation in probability. For instance, given sequence of random variables XN, and deterministic quantities by, we have
Xx
XN =
p-lim N bn
0.
(A.1)
B LOW-DIMENSIONAL GENERAL ASYMPTOTICS: IDEAL SURROGATE
Recall, the asymptotics of θ depends on the population risk associated to sampling scheme (that the expectation of the empirical risk (2.
(2 (() L()
(B.1)
(In this notation, the argument S indicates the dependence the function that defines the sub- sampling procedure.) The conditional gradient covariance, and conditional Hessian will play an important role, and are defined below:
G(x)) = E (VoT(0.: x:) V
1x) H F=):= x))
(B.2)
Our result characterizes the error under weighted quadratic losses |1-0,113 = 10-0.QQ0 Ow)),
for Q E RPXP, This covers both the standard f estimation error (by setting Q = =1) and, under smoothness conditions, the test error Rexx(0).
We define the asymptotic error coefficient via
sS: Q) : :- | 0.1l2:
(B.3)
No
whenever the limit exists. The next result is an application of textbook asymptotic statistics, as detailed below.
Proposition B.1. Assume the following:
A1. Rs(0) (0) is uniquely minimized at 0 = O..
A2. 0 + L(0: y. x)) is non-negative, lower semicontinuous. Further, for every SP-1, define Lao (w: y. x) E [o)
Loo x) = lim inf L(0:v,z), 0
(B.4)
0/110 -u
and assume inf (E(S()) v. x) (o.).
A3. 0 + L(O; y, a) is differentiable at O. for P-almost every (y, x). Further, for neigh- borhood of o..
S(w)2 L(0 v, L(f2: 00
E sup
10,
0211
A4. 0 Rs(0) is twice differentiable 0., with (².s(O.) ({)) 0.
Then, for any Q E TRXx symmetric, the limit of Eq.
B.3 exists and is given by
E{S(x) Tr Tr(G )
p(S:Q)= B{S(x))
(B.5)
13

---

Published as a conference paper at ICLR 2024
where
BfS(x)
H [(S(z) H())
(B.6)
E [{S()))
[{S(x))
In particular, if b Rien ( is twice continuously differentiable at 0., with V R (..) = 0, then
Rass ( = Reeal + N P(S:Quu) + op(1/N)
(B.7)
Rica (0.)
(B.8)
Remark B.1. Key for Proposition B. to hold is condition A1, which requires the minimizer of the subsampled population risk Rs to coincide with the minimizer of the original risk R. This amounts to say that the data selection scheme is not so biased as to make empirical risk minimization inconsistent. If does not hold, then the resulting error ||0 0.113 1l will be, in general, of order one.
Proof of Proposition B.1 Write Si(x,) s(x,, U2) where (Ui)seN aiid Unif 1]) the independent random seed used to compute St (we omit the dependence on the surrogate model). For ||||| 1, define ( c(([El)) &. where c(r) = 1/(1 - and, with abuse of notation,
(E(E) = Rs(0( (O))). Finally
ss(a,, U.) ((O
if E < 1. if | =
Ls(E: Z,)
(B.9)
(s( U.) Loe (5: U/. xi)
Z, == (U1. Vi, x..)
(B.10)
so that Rs(E) = (L Z) and (E) = N N Ls(E; Zi) are defined for & E B²(1) (the unit ball in 12P). If E = arg (F Ry (E), and &. = arg minge Rs({) (the latter is unique by Assumption A1), by van der Vaart (2000) Theorem 5.13). we have & - &. almost surely. By Assumption A2, we further have |[| < strictly, Therefore, almost surely, 0 0. O
Using van Vaart 2000 Theorem 5. 1.4 (whose assumptions follow from A3, A4), we get
1 N
0- 0.
H
op
(B.11)
whence
p(S: Q) E (4 (5500)--TT((001000202000000:1110
(B.12)
The claim follows simply by substituting the expression for VoLs(0.;
C PROOF OF PROPOSITION
As mentioned in the main text, this result (in slightly different form) appears already in the literature
(Ting & Brochu 2018 Wang et al. 2018 Ai ct al. 202I). We nevertheless present proof for the reader's ' convenience.
First of all notice that, for S unbiased we have E{S(x) x = 1 and therefore H = H. Eq. B.5 yields
p(S: Q) = [(((()) 7(x)) = Tr Tr(
We can always write S(x) 5,, (z) I(x), where S_ > almost surely and, conditionally on æ,
S4 (z) is independent of / (xx) E (0, 1) with ((((r) 1|x) = Tx:). The unbiasedness constraint
translates into (x)+(*))xr = 1/m( Hence
p(S: Q)
> (E (x) )
((x)
{
14

---

Published as a conference paper at ICLR 2024
where the lower bound holds with equality if and only if (+ 1//((x) almost surely.
The optimal π is determined by the convex optimization problem
((x)
minimize
(C.1)
subj. to [x)( 7
(C.2)
<(x:) E [0, Vz.
(C.3)
By duality, there exists constant À X(7), such that the optimum of the above problem is the solution of
minimize IP 2(())
[T(x)) >m(aa))
(C.4)
subj. to <xx) E [0, Vr.
(C.5)
This yields the claimed optimum Tunb-
Remark C.I. Besides computing expectations with respect to the conditional distribution of y given a, evaluating the score Z requires be able approximate H E H (x))- However, this can
be consistently estimated e.g. using the empirical mean A == N Σ (x.)). We will neglect errors involved in such approximations.
D PROOF OF PROPOSITION 4.2
For claim (1), it is easy to compute Prana (Q) -Z).. Therefore, the gain derived from optimal subsampling can be written as
Pubb Q) (B(Z/ uub ) Tuub))
S 1.
(D.I)
Prand
Q) E((Z/ Tmh)) Tumb))
The inequality above is due to the fact that Tuo and Z/ Z/T are both non-decreasing functions of Z. It is strict unless the following happens with probability one, for i.idd. copies Z1, Ze of Z: min(1; cZ,/2) = min(1; cZ, or max( Z1; 2//²2 /c) = max(Z2; Z2 /c) However, this happens only if either Z is almost surely a constant
cZ S 1 almost surely. The latter implies 7 =
To prove claim (2), note that the mapping ग + 3(Z(a)/<(x)) appearing in Eq. (4.5) is monotone with respect to the partial ordering of pointwise domination. Therefore, we can replace the constraint Ex(x) = by ET (x) < whence monotonicity trivially follows.
E BIASED DATA SELECTION: DEFINITIONS
Among data selection schemes, a special role is played by those schemes in which the only ran- domness is the choice of whether not select certain sample i. We refer to these schemes as 'simple.'
Definition E.1 (Simple data selection schemes). A scheme simple there exist function w, such that
S(w) = {
(w(x)) with probability क (ar),
(E.I)
otherwise
We denote the set of simple sampling schemes by 3 S A, where of the set of all data selection schemes.
As reminder, we can identify any simple data selection scheme with the pair (T,, w), hence we will occasionally abuse notation and write p( R, Q) for p(S: Q).
Lemma E.2. For Q ž O, we have: inf p(S; Q) inf se.7 p(S;
(S: Q) = inf p)S:Q). Seal
inf
(E.2)
SE.
We therefore restrict ourselves to simple schemes without loss.
15

---

Published as a conference paper at ICLR 2024
Proof of Lemma E.2
As in the previous section, (z) > almost surely and, conditionally on æ, S+ (x) is independent of [(x) E {0, 1). Further
always S(x) S+(x) I(x), where
P([(#) - 1/2) - T (a))()))aa) w(x))
(E.3)
(E.4)
Simple schemes correspond the case in which S+ w(x) non-random
Recall the formula B.5) for the asymptotic error coefficient p(S; Q), which we rewrite here as
p Q) = Tr (T
QH m.
(E.5)
H H == ([
(E.6)
By Jensen inequality (using the fact that G( war Q = 0), we get
(S; Q) 2 Tr
QH w.a
(F.7)
and simply note that the right hand side is achieved by the simple scheme.
F PROOF OF PROPOSITION 4.3
Recall the general formula (B.5) for the asymptotic error coefficient p(S; Q). For a non-reweighting scheme with selection probability m. with abuse of notation write p(S; Q) p(=; Q) (we also used p(T,, 1; Q) in the main text). Explicitly
Q(
Q) = Tr ((
(F.1)
Notice that this is defined for (<)( > 0. We extent it it B( (x) 2 by letting
p(T;; Q) lim
Q (x)))
X-
(F2)
We want to minimize this function over π subject the convex constraints ET(x)) = 7, π (a) E [0,
for all æ.
We claim that a minimizer Tue always exists. To this end, we view p(T;; Q) F(v) as a function of the probability measure v(dx) π (<x))(dx)/7> In other words F is function of the space of probability measures, whose Radon-Nikodym derivative with respect to IP is upper bounded by 1/7. This domain is uniformly tight. Further, if v, is sequence in this space and V,, Voc (weak convergence), it follows by the Portmanteau's theorem that Vic has also Nikooym derivative with respect to IP that upper bounded by 1/7. Hence this domain is compact by Prokhorov's theorem. Finally - f G(z) v(dæ:) and v + (x) v(dæ) are continuous in the topology of weak convergence (because G(ar), H (xx) are continuous by assumption), and therefore
F(v)
is lower semi-continuous. Hence, there exists a minimizer Vn (dæ) = Tax (x) P P(dx) with (x)
[0, 1].
Given any minimizer Tu, and any other feasible let me == (1 t) + tr. By assumption H mm strictly. Then
pm Q) = p( Q) + (अ(x) m.(())) 2(;; n.)) P(dx) + o(t).
(F3)
Therefore it must be true that, for any feasible ा.
J(T;; nm)) = / (T((²) Tha (1:) (x=; R..) P(dx) 0.
(F4)
Let Q. == (x E Rd T (x) E (=,1-E)} The claim 4..00 is is implied by the following statement:
7 (a:; mT.) is almost surely constant Q: for each
0. Assume by contradiction that there exists
16

---

Published as a conference paper at ICLR 2024
> 0 and 20 E R such that P( Qe Z( 20)
=4 > 0, (a E Qe (x: Tux) 20)
p- > 0. Let Q+ = {a E Q+ (( 2 20). Q-
{ Q:: [(x; TT) < 20) Define
(T( P-E
if Q++
T②))
(a) +PE (x)
if Q-, otherwise.
It is easy to check that ı is feasible and
Z(x; Tm) P4ē / ((x; mm) P(dæ)
J [T;; Mi -
0q_
q-
-PP+p- (m) x E EQ+) -((2(;; Fi.) E Q-)] <0,
thus yielding a contradiction with Eq. (F.4
Finally, we note that the stated form of Per follows from Eq.
Remark F.1. The condition EfVoL(O.:: y, ||) 0 (almost surely) could be eliminated the cost of enforcing the constraint E ( y, x) (x)} = O. This would result in a more compli- cated expression for the data selection rule: we will not pursue this generalization.
G DIFFERENCES BETWEEN UNBIASED AND BIASED DATA SELECTION: EXAMPLES
We provide concrete examples for optimal biased data selection schemes for two specific cases contrasting with optimal biased data selection schemes under low-dimensional asymptotics.
G.1 LINEAR REGRESSION: PROOF OF THEOREM II
Continuing from Example 4.3 note that the condition E(VoL [x) 0 holds. We
have G( = 7 xxx H (() væ Since rescaling G does not change the selection rule, we can redefine G(x) æw whence H G. E., where Σ, is the population covariance of the
subsampled feature vectors.
simple calculation shows
Z(x; (z. Σ QΣ 1 ())²)))...) x)
(G.1)
if (z. Σ 2 x)
T (x)
(G.2)
0 if (z. Σ QΣ
In other words, this scheme selects data that lay outside certain ellipsoid. The shape of the ellipsoid is determined self-consistently by the covariance Σ,., of points outside the ellipsoid.
Let emphasize two differences with respect to the standard leverage-score approach of Section
(1) As for general non-reweighing schemes, selection is essentially deterministic, (x) E {0, 1} (in particular, if the distribution of has density, then ग.. (x+) E {0, 1} with proba- bility one).
(ii) The original covariance Σ replaced by the covariance of selected data Σ,, As anticipated in Section 3 the selected set depends on in nontrivial way.
Given that the leverage score of datapoint æ; measures how different is æ; from the other data, the modified score of Eq. (G.I) can interpreted as measuring how different is I; from selected data. Example G.1 (One-dimensional covariates). In order to get more concrete understanding of the difference with respect to unbiased data selection, consider one-dimensional covariates Iú Pxx with Px of mean zero. We study prediction error, i.c. Q Σ. Let XM be the supremum of the support of P [x which we assume finite, and sample from Px. this case ((x) = r²x²/> Provided y < [| [XX//MM. M. we have c(7) = 7( (r X and the optimal asymptotic error for unbiased subsampling
7
{E )
Punh EΣ)
(G.3)
E E
17

---

Published as a conference paper at ICLR 2024
On the other hand, assumiig Px has density, the optimal non-reweighting rule takes the form
(x) = [[]=] 2 r(7)). The coefficient r = r(7) is fixed by 7 = P[[ 2 r). The optimal
asymptotic error for non-reweighting subsampling is
B(X2)
Pu P=(=)==+
(G.4)
1(X211x122)
The ratio of biased to unbiased error then takes the form
(2)
E [(X3)) r)
E| X
7 75
(G.5)
Punb (Σ)
(EX
easy to come up with examples in which this ratio smaller than one. For instance Px Unif([-XM, X Xms)). then
Per
47
1
r 2=
(G.6)
Punb (
3(1
More generally, as 7 O, we get
Par Σ
B(X2)2
(B| o[1),
-
(G.7)
Publ (Σ)
Notice that this ratio is always smaller than one (by Hölder's inequality) and can be arbitrarily small. then the above ratio is
For instance (x(dx) = | 11g|=|s
(2)
a - 2 X
a+
X + o(1)
(G.8)
Pur
(Σ)
3
To be concrete, for - 4, XM 10. unbiased is suboptimal by factor larger than 30.
Example G.2 (Elliptical covariates). The one-dimensional example above easily generalized to higher dimensions. Consider x; 1/2 z; where 2; are spherically symmetric, namely z; T:4 with (r,, uz) Pn @ Unif(Sd-11 d)) we consider test error (and therefore Q Σ), then it is symmetry argument shows that, for optimal π the modified leverage score (..I) coincides with the original one
(( (x. Σ
|| = ?
(G.9)
We therefore recover the one-dimensional case with P x replaced by Pn-
G.2 GENERALIZED LINEAR MODELS
Continuing from Example 4.2 B(VoI((f.; æx) ar) = O. Further
we note that E(y[=) = x)).
Therefore
G(x) = ( Φ ((0 x))) ra = ("((0.,)))
x. = H(x).
(G.10)
whence we have the following generalization of the score G.I
7(x; TT) (0((""(.0)) ((0.,z)) (z. HH
(G.11)
Note that this is similar to the score derived in the unbiased case, ef. Eq. 4.7 with two important differences that we already encountered for linear regression: (i) The selection process is essentially deterministic: datapoint is selected if Z(æ;; TT) À and not selected if ((x m) < x; (it) The score is computed with respect to the selected data, namely is replaced by H., The effect of toy data distribution in Figure
replacing H by H, is illustrated
We observe that at high y,, the two selection procedures are very similar. contrast, at low Y selection based H is always biased towards selecting "hard samples" (in directions roughly orthogonal to 0.), whereas selection based on H, takes into account geometry of selected subset and keeps samples in more diverse set of directions.
18

---

Published as a conference paper at ICLR 2024
N 989)
FT 903
mm0000
n-300 n--200
g
using PC: Hetr
Figure 3: Data selection in logistic model (here optimize error with respect to log-loss). Covariates are bi-dimensional and uniformly distributed over the letter g. The red arrow corresponds the true parameter vector 0". Selected points are dark yellow (circles) and non selected ones light yellow (crosses). Top row: selecting data with largest value of the influence function. Bottom: optimal nonreeweighting selection scheme.
Test
Error
Unbiased
Non-rewwiighed Optimal
n/N
Figure 4: Cartoon of the monotonicity properties of various data-selection schemes.
We also note that, for GLMs, the optimal asymptotic error coefficient of Proposition 4.3 takes the particularly simple form
Per (Q) inf Tr(E)
(G.12)
7 x: 3:
In the case of well-specified GLMs, biased data selection cannot improve over full sample estima- tion. Indeed, Par (Q) (T)
Q), and (( (x)) = (z)) On the other hand, it is clear that P.. (Q) S Prmn (Q) (because Prana (amn(() (Q) corresponds
special choice of on the right-hand side of Eq. (G.12). Further, the inequality is strict (namely, pm (Q) < Praaa (Q)) except (possibly) the degenerate
in which Z (æ:; л) constant set of positive measure.
H MONOTONICITY PROPERTIES OF BIASED DATA SELECTION
Figure provides cartoon illustration of the following monotonicity properties:
For unbiased (reweighted) data selection, we saw Section that the asymptotic test error is always monotone in the size of the subsample n (at least within the low-dimensional setting studied here). In particular, full sample data ERM cannot have worse test error than ERM selected data.
Consider then the optimal data selection scheme with reweighting. We claim that this is also monotone. Indeed given target sample sizes my < n2, can simulate data selection
19

---

Published as a conference paper at ICLR 2024
at sample size nı by first selecting m2 samples and then setting to 0 the weights of m2 nn samples.
However, for nt = N, this scheme does not reduce to unweighted ERM, but to optimally weighted ERM. As consequence, this monotonicity property does not imply that original unweighted ERM on the full sample has better test error than weighted ERM on a data- selected subsample.
The main result of the next section will be proof that non-monotonicity is possible in neighborhood of y for non-reweighting schemes.
I BEATING FULL-SAMPLE ESTIMATION USING DATA SELECTION: LOW-DIMENSIONAL ASYMPTOTICS
We next state theorems and corresponding proofs showing that non-monotonicity possible in neighborhood of for non-reweighting schemes under low cow-dimensional asymptotics. Theorem 5. Under the setting of Proposition 4.3 further assume H (x))(( oo,
(+)[H()))l co. Then, there exists a constant C such that, for any X E such that
((Z 1) < A) > 0, we have
Pa(Q: 5 Pm - (1 ZQ (z; 1) Zo 1) < A} + C(1 7/8//2
-
(L.1)
Zo 1) - Tr(G(z)H QH }} + 2Tr H QH GH QH '
(1.2)
Further
(a) 1f0,pm(Q;1) -sss inf (a(:; 1). (Note that this is potentially equal to +
(b) (1; 0) O, then there exists "r (c) < 1 such that
E (no(d),) 1) = Par (Q:7) < pmr (Q;
(1.3)
We next construct specific cases in which P(Zo 1) 0) > 0 for the case of misspecified línear model, namely æ;;) E R Rd with
Ply E A(x,) = x;)),
(I.4)
where Oo Fdd is fixed vector. We will show that both in the case of linear regression and logistic regression, there are choices of the conditional distribution P. for which y + p(Q; 7) is strictly increasing near y 1. In this cases, training
selected subsample provably helps.
Theorem 6. Assume x; N(O, Ia), and yi distributed according to Eq. (4.8). Lel Q H
2 ((O)), ), (as before, O_ =
arg ming R(O)). Then in each of the following cases, there exists
P(A]t) such that Eq. I.3) holds:
(a) Least squares, i.e. L(0;y.x) = (y- (0,z))2/2, Lisa = L.
(b) Logistic regression, whereby y: E {+1, 11}, L(0; x.) -v;(0. + (())))))), <(t) = log(e' t)="), Lus L.
The proofs of Theorem 5 and Theorem 6 are presented next.
1.1 PROOF OF THEOREM
Write G_ ((G()))(()), and similarly for H.. Defining x(Φ) - --7(x), and using
[[T(2)} = 1- - we get
G. G - (x)
[B(G(a))())| E(] 1/4(11 7//// (I.5)
and similarly for f..
Using the form of Per in Proposition and Taylor expansion (recall H 0 by assumption), we get, for any π satisfying ET ET(x) = 7
Per (Q:7) < Pa Q; 1) + E +(13())))) + E (<)))(()))
pm pm (()
20

---

Published as a conference paper at ICLR 2024
where [z; 1) is defined in the statement of the theorem.
For as in the statement, and all (1 -2) small enough, we can take ((x) = =(1 (113)/P(Zo(2) <
A) if (o(x; 1) < X, and ग. ((x) 0 otherwise. This immediately implies Eq. whence point (b)
follows.
In order prove point (a), note that, by definition, for any À ess inf ZQ(x),, we have P(Zq(x)
A) > 0 and therefore Eq. (III implies, for all - y small enough
Pa (Q:7) S (Q; + A(1 - + -(1-)))/1 This implies (Q;1) -À and therefore Per (Q: 2 ess inf Zz
(1.6)
Alternatively, assume ess inf Zo(x) - X > -00. Let Ter,y achieve the infimum in Proposition
4.3 (Proposition 4.3 ensures that such THr, exists). By the above argument (letting (,,,(
(x))(()))
Per (ia)= Pr
+((())(())))))))) + |E (B))))))_))II)))))))))))))))())) (+())
P (m;1) (0(1-)))))(
This yields Pmr 1:1) - -
1.2 PROOF OF THEOREM 6
Both claims of the theorem follow we can provide an example such that ZQ 1) < with strictly positive probability. in the Q H. Specializing that case, have
Zh (æ; 1) == -T((G()))HH + 2Tr
GH
(I.7)
In the following we will simplify notations and write Z(x) ZH 1).
We next consider the linear regression setting of point (a). Without loss of generality, will
assume |000|| = 1. By rotation invariance, the population risk minimizer has the form 0 = a 0- The coefficient as is fixed by
0 == VRs(a,0) 0n) = Ef a, (0.. x))xx.
The only non-zers component of this equation the one along O.. Projecting along this direction, we get (for G ~ N(O, Y P( IG):
E((Y G)) =0
We next compute
G(x)) E (y (0.. x))² x xx
H(x) xx
(I.8)
Note that we can rewrite the first equation as
G(æ) = s((00, x²) xx
(1.9)
f(t) / (u a.t a.t P(dytt)
(I.10)
Taking expectation with respect
G aIa + 00 a = 1 G)))
H Id.
(I.11)
b: b: B(
(I.12)
Substituting in Eq. (.7)) get Z(x)) - -(((0, a)) |=)1|=111+ 2a 20 + 21,00,
=On, 2;)² (() +2E[J()GG1
(I.13)
+ Pb 0: 1 =
easy to construct examples in which ess inf Z(x)) -o. For instance, take P(- RR(1) I((1) = = 1 e(13 - 31) for some e >>> (no noise). Then we get a and f(() = 2² (18 21)². Let to be such that f(t) > GE f(G) for all t to. Then the claim follows since
P x:: (0. .)) E [to, to + 1). P 21122 > M) > 0,
(I.14)
for any M, and Eq. (.13) yields Z(x) < 0 on the above event for all M large enough. In fact, we also have (()) -c for any c, by taking M sufficiently large.
21

---

Published as a conference paper at ICLR 2024
1.3 PROOF OF T)
We next consider a misspecified generalized linear model with yı E [+1, -1] and
P(+1[=) = -(--1())=
(1.15)
We set u(t) = 2f(() 1. is simple compute
VR(0) B (u((00. ((((0x))))z)
In particular VR(0) = - [E( d(G))G) where expectation is with respect to G ~
N(0, 1). We will impose the condition
B[Gu(G)) = (G)
so that the empirical risk minimizer is 0, Og.
Next we compute
G(x) 9((0,, xx
H(x) h((0,,2)) xx
(L.16)
where
+1 u(t)², h(t) = 1- (1) (()) = (u(t) - (1)))2
(1.17)
Performing the Gaussian integral, we get
G = a =
= l-nnla + 0.0.0
(I.18)
where og = Bg(G)) b, = Rey" (G), and similarly for H. We thus get
=c
H' =2la+
(I.19)
for some constants c, c..ck that are iaiiensioonindepeddeen functions of an, by, aG, ba. Substituting in the formula for Z(x) ZH (z: 1), cf. Eq. (L. we get
((x) == (0), (x. Ic + +c0.0.)))) 2h((O-, x)) (x, (c2La + c0)
(I.20)
For large d, we have
(x, ((,,0)))) cd ocd+))))))
(I.21)
and therefore
7 -c1g(((0,, + c2h((0., m)) op(d).
(I.22)
Note that G (0., N(O.1). 1). particular, its distribution d-independent. therefore sufficient to prove that -c + (e) < 0 with strictly positive probability, since this implies Z (xx) with strictly positive probability for all large enoug. It is simple to compute ej = 1/as.
02 ac/aj, Therefore it is sufficient to prove the following
Claim: We can choose f so that Eq. (L.6 is satisfied and strictly positive probability.
< 0 with
To prove this claim, it is convenient to define the random variables W (') M =(G)) and note that the distribution of W symmetric around 0, and has support (-1,1). 1).
We have g(G) (M w)² + 1 M², hGG) 1- W Therefore, the conditions of the claim are equivalent to (the second condition is understood to hold with strictly positive probability)
E( (M W (W)) 0,
(I.23)
aи : [(M w)² + 1 - M²] > 2ag [1 - W
(I.24)
where 3i - (functional inverse), and
ag = 13 w)2 + - M2}, an 1(11 222
(I.25)
22

---

Published as a conference paper at ICLR 2024
We will further restrict ourselves to construct these random variables that 2ag a.z i.e.
E - W 4W w)) =0
(I.26)
Next define op R R p(z)) u(x) o' (xx), whenee M ( W d'(G) tanh(G).
Therefore, is sufficient to construct yp R + R such that, for some To E R, E > 0,
([p(G) (anh(G)) = bo
(1.27)
B[y(G)G) 0:
(I.28)
(xx)² + + 1 tanh(x)² for all x (za- - sy + +)),
(I.29)
-1 - tamh(x) < ((x) < 1 -tanh(r)
for all x E R.
(I.30)
where bo E tanh(C))) is constant bo E (0.1/4). Note that Eq. 1.29 is sufficient
because the law of G is supported on the whole real line. Simplifying Eq. (1.29. and assuming is continuous, we are led
Efp(G) tanh(G)) bo.
(1.31)
B[p(G)G) = 0,
(I.32)
xxp(x) <
for some x E IR, for all x E R.
(I.33)
-1 -1-taah(r)) < ((x) < tanh(x)
(I.34)
We complete the proof by the following result.
Lemma 1.1. There exists sp IR + continuous satisfying conditions L.31 to L.34 above.
Proof. We define F: (N((,, 1)) + 2 by F(p) = tallo(GG))n)()))
and
c==fp E C(T): Vor E TR max( (1 - tanh) -1) < x(x) min(1 - tanh(x),1)) 1) (I.35)
In particular, any yp E C satisfies condition 1.34). We claim that there exists open set B C IR,, such that (by. 0) E and F(C) 2 B (i.e., for every x E B, there exists yp E such that F(y) = x)).
In order to prove this claim, note that F is continuous linear map and C is convex, whence F(C) is convex. Hence, it is sufficient to exhibits points Φ0, P2, Ps E C (the closure is in L (N 1)) of C) such that (bo, 0) is in the interior of the convex hull of (F((::) : S 3]. We use the following functions:
yp (x) = F((91 (0, 0)-
2. (2())) = sign(x) - (an))
Fi () = ([tann [G tanh [G]) =: b, > bn F2(122 [][ tanh [G])] > 0,
(1.36)
(I.37)
(Numerically, bi 0.16168, 6o x 0.15143.)
3. pa(()) (2((1) 112 q(x M). where g(z) is a continuous non-negative function supported on [-1, 1], with ((x) dæ > 0. We have Fi((s)) Fi((2) 9 and F2((p)) = (2 - (22) Hence for a sufficiently large M, F (Pp) > bo. F2( < O.
This proves the claim, and in particular we can satisfy conditions B. order to show that we can satisfy also condition (L33), let y be defined as above and further such that ((x) < 1/2 for all æ. Consider the sequence of functions indexed by & E N:
I.34j, since (bu, 0) E
(*)) = (x(x) - g(x k).
(I.38)
First note that, if y E C, then y satisfies conditions (I33).
1.34 Therefore, we are left to prove
that, for some k, there exists F E C that satisfies
F = by + E(g - kk) tanh(G)) =: bo + $1,6
(I.39)
F2 (2(x)) E(g(G k) G) =: 62
(I.40)
By dominated convergence, have d₁ (61 62,x) 0 as + and therefore (bu, 0) + 6g
B for all ie sufficiently large, whence the existence of u. for such à follows from the first part of the proof.
23

---

Published as a conference paper at ICLR 2024
J PROOF OF THEOREM 3
Let Tunb be the optimal unbiased sampling probability (see Proposition with corresponding weight Wann (x) 1 und (z:). Since ((z) HH (x) is almost surely bounded (Assumption A2), is bounded as well. Therefore, there exists % > such that, for 7 E (0, 70). Tum (2) = <(>)
follows that (xx) (r(G(z))
For bounded function (p, consider the alternative weight we (x) (1 + ex((x)) (æ)), which is well defined for all small enough. Recall that we denote by p(TT, w; Q) the asymptotic estimation error coefficient for the simple scheme (T,, w). To linear order in E, we have
p Tub: we; H) P(Tuub: Wo; H) 2: ((((a))((a))) +
(I.1)
where
W(x) Tr(EEg
(G(())
G(a²)
H H H Tr
( H 1
G( Tunb (
(J.2)
Tunb (xx))
Assume by contradiction p(T., Wei H)
(TT,, w_; H)) for every io, E such that we 2 0. By for P-almost every Using assumption A1, and defining
Eq. J.I.. this implies W(x)
M(x) = H G(x) 1/2 we get
(xx) Tunh (2:"
M(x')
W(x) Tr Enr
M(x))
Tr(M
(I.3)
(x))
we have (2:) coc)TTr(M(()))) 1/2 and therefore W(xx) = Wo(x)) Tr Tr(M(x)) 1/2 /c(7), where
M(x')
M(x)
Wo(x) Tr Tr(Bur
E
Tr(M(('') 122)
Tr(M(x))) 1/2)
(J.4)
=Tr(W- W(x)) -1
Here we defined W(x) == ((2)/TT(M(()) 1/2 W = EW)
Since W(x) almost surely, and G(x)) + almost surely (by assumption A2), must have Tr(W- (zx)
almost surely, which contradicts the assumption of (()) 1-11/ not lying on an affine subspace (Assumption A3).
Example J.1 (Generalized linear models). Consider again the GLM model of Example 4.2 (log- likelihood loss). Recall that in this case
G(z) H(x) ("((0..))) xx_
(J.5)
Hence condition A1 of Theorem 3 is satisfied, and A4 is also always satisfied. Pfd is supported
on ||œ||| < M, and (p = 0) = 0 then condition A2 is also satisfied. (Note that @²(t) > for any
t 0 unless 1i & is point mass, which is degenerate case.) Finally, for condition A3 note that
G(x)
(I.6)
Tr(G(z))
(æ., H
Therefore, sufficient condition for A3 is that the support of P(dæ)) contains arbitrarily small ball (x E) C Idd.
K LOW-DIMENSIONAL ASYMPTOTICS IMPERFECT SURROGATES
In this section, discuss the imperfect surrogates under low-dimensional asymptotics. The main conclusion of this section is that plug-in schemes can be suboptimal and weaker surrogate models indeed lead better data selection.
Throughout, we will use the notation E,,, (F [x) = F(yy. x)) (dy(()))) and similarly for (..(..):).
24

---

Published as a conference paper at ICLR 2024
K.1 PLUGIN SCHEMES
The simplest approach to utilize an imperfect surrogate proceeds as follows: (t) Choose a data selection scheme under the assumption of ideal surrogate; (fi) Replace the conditional expectations (fF(y. in that scheme by expectations with respect to the surrogate model E., { [ly x) x
(iit) Replace expectations over by expectation over the data sample.
In particular, revisiting the schemes of Sections and 4.2 we obtain the following:
Plugin unbiased data selection. We form
G (x: == Em V (
y. v. VoL U. x:) 1
(K.1)
H.. (x:) = E.. { V (0 x
(K.2)
and subsample according to
<Φx) min (1 (x)
(K.3)
Zu (z) Tr
QH 1,m)
(K.4)
11, (x))
(K.5)
We then reweight each selected sample proportionally to 1 (xx( Note that:
The 'true' parameters vector 0, appearing in VoL(. æ) by an estimate obtained from the surrogate model. In certain applications 0" can 'read off" the surrogate model itself. In general, we can define via 0 arg min EN L(0; vf", æ.), where (g"") are drawn independently according to ys ~ P P..( (1x))
VOL( æ) was replaced
The matrix 1.. can be replaced its empirical version 11,= == N -' H=,
Plugin new-rewwig data selection. this case we select samples such that Zma(x; > X, cf.
Eq. 4.10), where
((x; (T) QH 2Tr QH G H
(K.6)
and H H (Z)) replaced by averages over the N samples.
and similarly for G G. Again, expectations over are
Plugin approaches are natural and easy to define, and fact we will use them in our simulations. However, we will show that they can be suboptimal. Before doing that, we need to make more explicit the notion of optimality that is relevant here.
K.2 MINIMAX FORMULATION
We want formalize the idea that we do not know the conditional distribution of y given æ, but we have some information about it coming from the surrogate model P... With this in mind, we introduce a of probability kernels
X. Xx B2 Rd + [0, 1] probability kernel
(K.7)
Informally, Xi is neighborhood of the surrogate model P P... and captures our uncertainty about the actual conditional distribution: we know that IP u/a E Ky. For instance, we could consider, for some r E [0, 1).
= (P: E. Pm (-)=) S sr).
(K.8)
We will assume Xa (and its variant .N introduced below) to be convex. Namely, for all À [0, 1],
Po. P1 E Ma + (x(dy/x) = -1 AdPu(dy/a=) + (Pi()y)x) E Ha.
(K.9)
We are interested a data selection scheme that works well uniformly over the uncertainty encoded
in Ha.
25

---

Published as a conference paper at ICLR 2024
Given probability kernel P(dylæ) (i.e. P BR R + [0, we write P(P) for the data distribution (on Rd x R) induced by Namely Er(p) (y. x) == Eol (y, x) P(dy/z))
Let Russe ( ne (:y. x)) be the test error with respect certain target distribution P. Given an estimator 0, we let (3. X) denote its output when applied to data y. X in conjunction with data selection scheme S. For clarity of notation, we define
R4 (S; X) == Rusc (0s(y, X)).
(K.10)
We define the minimax risk Ra (xa) by (here we recall that sf is the set of all data selection methods)
R. (S; =- sup Ey. (S: X);
(K.11)
PE-Ka
Rana Ram(( = inf R. (S;
(K.12)
SEal
We seek near optimal data selection schemes S, namely schemes such that (S; Ka) Rust (Ha). We note that the expectation in Eq. (K.11 includes expectation over the randomness in S.
Remark K.1. The set Xa provides information about 0.. This information can be exploited in other ways than via data selection. For instance, could restrict the empirical risk minimization of Eq. (1.2) to a set that is "compatible" with Xx. However, we are only interested in procedures that follow the general data selection framework defined in the previous sections and hence not necessarily optimal against this broader set.
K.3 DUALITY AND ITS CONSEQUENCES
We can apply Sion's minimax theorem to relaxation of RMN (a)). Namely,
We replace Ha by set of probability kemells R-x to RN;
HN.a S HR = :p: x R Nxd_ + [0, 1] probability kernel }
(K.13)
such that each marginal of E HN.. is in Va. other words, we allow for entries of y be conditionally dependent, given X. Generalizing the notations above, IP()x) denotes the induced distribution on y, X.
We replace the space of data selection schemes of by the set e of probability kernels Q such that, for any A S [N], and any X E Nxd Q(AI is the conditional probability of selecting data in the set A given covariate vectors X. In other words, consider more general selectinn schemes in which the selected set allowed to depend on all the data points.
The following result is application of the standard minimax theorem in statistical decision theory, see e.g. Liese & Miescke (2008) Section 3.7).
Theorem 7. Assume that any PN E HA, is supported on |glll S M, and that (y,X) X) + R(OA(y, X)) is continuous for any A. Define
Rexna ( = inf (S; = inf sup Ex. Rw (S: X).
(K.14)
SEE
Seæ PeEKa,
Then we have
Pansa (Ha) sup inf Ey xxxx-P(Px) RB (S:y. X).
(K.15)
PNEXA SeW
Further, assume Mиа achieves the supremum over Wa above. Then any
SAM E arg min Ey PPP R4 (S; X) SE
(K.16)
achieves the minimax error.
26

---

Published as a conference paper at ICLR 2024
As is common in estimation theory, the minimax theorem can be difficult to apply since computing the supremum over P E Xa is in general very difficult. Nevertheless, the theorem implies the following important insight. We should not perform data selection by plugging in the surrogate conditional model for given a for the actual one. Instead, we should optimize data selection as if labels were distributed according to the 'worst' conditional model in neighborhood of the surrogate.
Below work a toy case to illustrate this insight. Instead of studying the minimax problem for the finite-sample risk ft we will consider its asymptotics defined in Proposition B. We define the asymptotic minimax coefficients (= .a) and Pan Paa (Xa) in analogy with Eqs. (K.11) and (K.
Example K.2 (Discrete covariates). Consider taking values in [k] (1..... k). with probabilities
P) P(x = f), and taking values in {0, 1}, with P(y = 1 = 0" whereby 0" (0i...., 0f) is
vector of unknown parameters. We estimate 0 using empirical risk minimization with respect to log-loss
L( y. x) = yy log 0₂ - (1 -1-11 -)) log(1 - 0z).
(1-y)
(K.17)
We are interested in the quadratic estimation error |@ lle with Q = diag( 92........................ 9z). We consider non-reweighting subsampling scheme whereby sample with covariate is retained inde- pendently with probability w.. Either applying Proposition B.T or by a straightforward calculation, obtain:
[(110* - 101
1
p(T; 0" "0)))")00000""""
+ O(1NN),
(K.18)
N
p(:: 0" Q) (1 87)
qs
(K.19)
TxPx
(Here we made explicit the dependence on 0* )) For X C R convex set, we then defing 5
P (T; Q == sup E.x
p(:;; 0" Q), Pa Q) == inf (T; Q)
(K.20)
We will assume that X is closed (hence compact) and convex. We can apply the minimax theorem Eq. K.20):
Panm (K (Q) max min p(T;; 0", QQ)
(K.21)
Hence, the minimax optimal data selection strategy is obtained by selecting the optimum π for the worst case 0, to be denoted by 0MM, A simple calculation yields
(c(7) V yn OMM OMM); (1-0M)
Th
MM
min
(K.22)
Pz
@MM
arg
max
(c7)) Ve -0z): Qx fz 0z))
(K.23)
DE
Pz
where c(7) is obtained by solving
k
min (cr7)) - -8MM): Ps)
Y
(K.24)
The above formulas have a clear interpretation (for simplicity we neglect the factor (z). Note that @MM - (MM) can be interpreted measure of uncertainty in predicting Vnew a test point Tnew under the minimax model OMM We select data so that the fraction of samples with H; x is proportional to the square root of this uncertainty. Assuming that the inner maximum in Eq. (K23) achieved on the first argument, the minimax model itself is the one that maximize total uncertainty within the set X.
'Nttcee that we are not taking the infimum over all randomized data selection schemes in Theorem For simplicity, we are restricting the minimization to non-reweighting schemes. The substance of Theorem does not change since this set is convex.
27

---

Published as a conference paper at ICLR 2024
For instance, if X 18,,1 c, 0m,1 +E] x.... ......X -B,, 0m, +E] 10. then 0N for all z. We then obtain
u, +
min (0(2) V aa (0 + +c) Mu - -);
MM
(K.25)
Pz
In other words, we should not use the uncertainties computed within the surrogate model, but within the most uncertain model in its neighborhood.
L HIGH-DIMENSIONAL ASYMPTOTICS, GENERAL VERSION OF THEOREM 4
In this section, we present the complete version of the Theorem followed by the proof.
Theorem 8. Assume u L(u, y) is convex, continuous, with at most quadratic growth, and X > 0. Further denote by x", 1t" the solution of the following minimax problem (a" uniquely defined by this condition)
min max ((c, 11). #20
(L.1))
Then the following hold in the limit N,p - with N/p - 5o: If (u, + J Luw P(dyl)) is a continuous function with at most quadratic growth, we have
p-lim Reca (0x) = EL (gjGo + (az)2 (a
(L.22
N.p
where expectation is taken with respect to the joint distribution of Eq. (.3
(b) If 0, E arg minnReu()) then the excess risk is given by
p-lim Reso ELnea (aoGo + (aa))²((a))2))))
Elues (c.Goit..
(L.3)
(See Footnote for defmittio c..)
(c) Letting Po be the projector orthogonal to Og and p- the projector orthogonal to span (0, 0"),
we have
Ox.
(0,
p-lim N.0
0g
p-lim Nop-0
a
p-lim N.p-000
|P-O211 a²
(L.4)
|000
P
(d) Further, the asymptotic subsampling fraction given by
n
P + 3,G.) 0).
(L.5)
We can further specialize the above formulas to the classes of data selection schemes studied before: unbiased and non-reweighting schemes.
Unbiased data selection. In this case S.((0" ...)) 1/0((0", .m:) with probability л =((0", .=:)) and S, T xz)) otherwise. The Lagrangian reduces
+ 1 fbi + E min [L(aGG + G.GG YY + 2 ( L(a, : |al 250
X
1
wER
Non-reweighting data selection. In this case S,((0", xx)) 1 with probability =((0", xx:)) and
S,(0"" x.)) = otherwise. The Lagrangian reduces to
L(a,
> : L(a,1))==
1all 25p
Ea + H8 (E(T((B,0)) g)) min WER
ManGo++aa aa, - Y) + (u a (
Gi)
(L.6)
We further provide simple expressions in the case of misspecified linear regression, already studied in Section 4.3 in Appendix M
28

---

Published as a conference paper at ICLR 2024
Proof of Theorem 8 This proof is based on Gordon Gaussian comparison inequality, following a well established technique, see Thrampoulidis et al. (2015 2018); Miolane Montanari (2021).
Our presentation will be succinct, emphasizing novelties with respect to earlier derivations of this type.
Recall that consider test error of the form
Rosa x = E Le (allaa((())))) (0)x, Fnew); Ynen),
(L.7)
where 0₂ arg Ryg)) We will also consider the excess enror (0x)
(xx
info (0).
Define
(r,, Oo) 10012
(c. P00"
Go,; =
G =
9. = P- z2
(L.8)
| 0 ll2
where we recall that Po the projector orthogonal 0g and p is the projector orthogonal to span(O.. 0 0")). Further define
(0,0)
(0, PO
0g 00
022
0
(L.9)
P 0 2
With slight abuse of notation, we can then identify the empirical risk
(ag 0tss Ø1)= N 1=1
Σ
(B + B,G. U,) Lan a, vi)+
A
(ag + a + |a_ (L.10)
2
We can identify T and 9, with (p 2) -)-mmenssoonal vectors. For any closed set Ω C RP, let
RN == min (ny (ao, 0gs σ1) E EΩ
(L.11)
Further define
(2))
min min max 200) (ao, a,, []:
(L.12)
(ap,a,, Jef eER" CER
min max min 2000 (ap, [.;;)
(L.13)
(am,a, Jen CERN wele
where
(ag, Cg, [1: = = (g. +1Ei(,,, (v.E) + > ( a + ||a]l²)
7
2
(L.
N + N
BBo + B,GGsr U,) Loa L + o. Go, + W:)
and the identity of the two lines of Gordon's 's inequality and using Gaussian concentration (Boucheron et al. 2013). we obtain the following.
L.12 L.13) holds by the minimax theorem. By an application
Lemma L.1. There exist subgaussian enror terms, err, (Nr, (with (N, z CN- such that:
1. For any closed set Ωr
Rx( > RQ( + erri (N).
2. For any closed convex set Ω:
RN RG) + (Nr)(N).
29

---

Published as a conference paper at ICLR 2024
Proof. This follows from application of Gordon's inequality and using Gaussian concentration (Thampoullidis et al. 2015 2018 Miolane & Montanari (021). In applying Gordon's 's inequality, need to check that the minimizer lie with high probability in compact set Bx. This is immediate for by strong convexity of Rx-
Note that, subject to the constraints ||يي|| = a.i || = p/vN, the minimization over æ and maximization over & can be performed before the other optimizations. This yields the reduced Lagrangian, with argument a == (av, a1))
2 (ac u. v) : |bll
aLPD + 1 IOLLL - + A "|aa11 2
(L.15)
VN
N
Σ
SBoGo + B,G,, Ui) Loa + a.G. + v.)
For A E IR2 x Rz0. let QA = {(a0, aes a E RP: (ao. at. aill) AA, and write
(A,N(A) = (NAA) min ax,
as (oo, Csi a 11 E A]
(L.16)
RG (A) = (1A))
(L.17)
We then have
RC R (A)=
min max min (a0,as,a1)e JEA PER VER"
2 (au, ag aLiH,
(L.18)
Finally, we take the limit N,p mization over a random variable V. Namely, let (S,F, P) be a probability space on which the ran- dom variables (Go, G., G1, U, Y) are defined with the same joint law of (Go,1, 91,11 U1, V1). Namely (Go, G,, G U) 1)0, 83 @ Unif ((0, 1)), and Y|Go, G.,, G, U P(- 1 Go) For V another random variable in the same space, taking values in the extended real line R, and letting a = (Oo, Cx2 (.),, define
In this limit, the minimization
is replaced by mini-
fla;p, = mapn + Bi -V))juu
(L.19)
Vo
2 |a]l2 + + = B,G U) LlanGo + a,G. G,
Theorem 9. With the definitions given above, and under the assumptions of Theorem the follow- ing hold:
1. For any compact set A 5 R R2o
lim Nap
AG (A) Ro (A) == min max min L(a: V).
(L.20)
aEA MERz0 VEMF
2. For any closed set A.
lim inf Rx,N(A) (A).
(L.21)
N
3. For any closed convex set A,
lim inf (A) (A). No000
(L.22)
4. Further, denoting by a² (o oz) the minimizer of
(a)a)) max min
PERgo VemF L(a;
Conclusions (a) to (d) of Theorem 4 hold.
30

---

Published as a conference paper at ICLR 2024
Proof.
Note that rewrite (A) min(R A}, where
N
A
1
min
|
2
s(9GGo B,Gas, Maa asGos + U4 (4)
Rg.x(a)
2
N
subj. to
a 1p_g1
- u S |
(L.23)
Further, this can be written as as a function of the joint empirical distribution of {Go,, G. 91,6 U1, Vs. t-))- Namely, defining
NN
N E
(L.24)
have (with Epx denoting expectation with respect to PN)
min
+ 2 |all + Epn {s($oGo + B,G,, U) Llaguu + V.u))
Epx ( | N a
subj. to
(L.25)
Let Rg(cx (ox) be the same quantity, in which minimization over v is replaced by minimization over random variables (Go, G., G Y, V) with GG, G1 U,Y) Y) having the prescribed N oo distribution, and ||a||//N is replaced by 1/6g. In fact, se define slight generalization
G.,
A |a 22 B(s B,G., U) LonGo + a,G, + Vv
min
(ox;))
2
subj. to
E Go s (1 - =)o
(L.26)
Let Pi be the joint distribution of that achieves the above minimum at finite N. By tightness, PN = 1¹ along subsequences, and further the limit satisfies ([ V}3 S <a./ / by Fatou's. ss.. Therefore
lim inf (a) 2 R
(L.27)
N
almost surely. On the other hand, if (Go, Go, G1. GL. achieves the minimum define Ry ()) E > 0, let (Go,s, Go GL, Un, yr, v.), S N be i.i.'s vectors from this distribution. Of course this v is almost surely feasible for problem ( for all N large enough. Therefore
Gg,
lim sup (p)))(a)) ft (Oge), N
(L.28)
Finally, we claim that lime +0+ R& (a;e) = R2 (o:; 0), thus yielding
lim (()) Piw (a;; :
(L.29)
G1 1 v113 S a² then V/8 = (1-8)V 8G1 To prove the claim notice that, if V satisfies EflaiGi-Vai
satisfies ([(a) G 1 Vı]²} < (1 s))d with 28 82, Further, the objective is continuous as by continuity of L, whence the claim follows.
Next we claim that a + (a)) Lipschitz continuous for a A, where a compact set, on the high probability event
N 2
G =
Σ Co. + G2,, G.,) 10N
< [1l2 < 2N
(L.30)
To prove this claim, note that this event, define = s(BGGo, + B,G.,i. U.), a;(a) = Gn +
G,Gaa Tu(u)
(u v:). ||b]//V.. such that ||s|], ||a|| 5 CVN, 1/2 < < 2, is
31

---

Published as a conference paper at ICLR 2024
sufficient to prove that + F(a) is Lipschitz on A where
F(a) == min (((avv) : uE s(a))
(L.31)
1 H(a,v) = N Σ s L((a((a)) - u.) S(a) == {v: 1 air1e S SaIVNj.
(L.32)
On the event 9 above, |H v1) Ha2 v2)l I Ca - azll C - 22ll/ 12ll/v/ /N and dist(S(aa), - CVN ozl The claim follows from these bounds.
Since (()) + R (a) for each a E A, a + R4.N (a) is almost surely Lipschitz continuous with Lipshitz constant C' independent of N, for all N large enough, we have suPecA [R Ry (a)) 0, and therefore, for any compact A,
lim R N (A) R (A). N-00
(L.33)
For À >>0 0, both R4.N and R uniformly strongly convex and therefore the last claim extend any closed A. (Because eventually almost surely arg min (a)x(a) E B for some compact B.) Finally, by introducing Lagrange multiplier for the constraint Ry (a) = min max Llac,
VemJ PERSO
max
min
L L(a
PERzo VEmF
This concludes the proof of point I (Eq. L.20)).
Points 2 and 3 follow from the previous one by applying Lemma
Finally, the proof of point 4 is also straightforward. Indeed by taking A = far E R² x Rxo
|| α || 2 }} and A 1 x R20 and applying points and 3 for arbitrary
implies
Eq. thus establishing claim (c) of Theorem
Claims (a). (b). to (d) of Theorem 4 follow from the previous one by noting that 02 is uniformly random, conditional (0o, Ox), (0" 02). ||
The proof of Theorem 4 is completed by showing the following.
Lemma L.2. Under the assumptions of Theorem have the following equivalent characteriza-
tions of R& (ax) (where
the shorthand (b) s(b, for ~ Unif([0, 1))):
AC # (ax) = max min (),
(L.34)
MERso V Emm
min
+ |all + B
aa, V.
(a)) (a)
2
(L.35)
subj. to
B[ vF] < añ
RG((a)
(a)
max (). #20
(L.36)
Proof. The equivalence of Eq. L.34 and (L.35 was already established in the proof of Theorem 9 As for Eq. (L.3)). the equivalence with (L.35) follows by introducing a Lagrange multiplier for the inequality Ef Ea G - v23] s of, whence RG (a:) max,20 L L(a.)) (1)
#
x ||
1
L(a,,11
250 mo
2
+(r))
+ min VemF
= 2
|a||
200 f +
E
min WER
|S G)) L(anG + G,G, u v. + (a
For S2 C RRN, let dist = sup=ees, suPages, ||| xz|l.
32

---

Published as a conference paper at ICLR 2024
which yields the desired claim.
M HIGH-DIMENSIONAL ASYMPTOTICS: THE CASE OF MISSPECIFIED LINEAR REGRESSION
We revisit the case of misspecified linear regression, already studied in Section 4.3
We assume
non-reweighting data-selection scheme, whose asymptotic behavior is characterized by the La- grangian (L.6).
In the case of square loss, the inner minimization over is easily solved and then perform the maximization over in Theorem 4 analytically. This calculation yields the following Lagrangian
2
(a) :1 (
-a.
a
+
(M.1)
voo
We then have the following consequence of Theorem
Corollary M.1. Assume the misspecified generalized linear model of Section sider the of square loss L(0: y. x) = (y (6, x))² Let a* (a ag ai)
5.1 and further con-
be the unique
minimizer of the Lagrangian Lo. Then claims (a) to (d) of Theorem hold.
The next statement gives a particularly simple expression the case of perfect surrogate, and ridge- less limit À - O. For n > this is standard least squares, while for n S this is minimum & norm interpolation. Its proof deferred to Appendix [M.]
Proposition M.2. Assume the misspecified generalized linear model of Section 5.1 and further consider the case of square loss T(O: y, æ)) = (y (0, 2 and further consider the case of perfect surrogate which, without loss of generality, we assume normalized: 0" 00//|0ool- Define the quantilies
A = 1 [G)] B :===EEGYTGG.)
C == E
(M.2)
where expectation is with respect to G N(O,1) and Y P(- In particular, we let A B C1 be the quantities defined above with (t) = 1 identically.
Then the asymptotic excess risk of ridgeless regression as follows (here 8 = 607 = -limm,p- (n/p)):
For 8 >
B1
B
2
B2
lim p-lim Rew (xx) X-0 N-p
+
Cx
(M.3)
A1
A
8 -
Ax
2. For 8 < 1:
B1
B,8
B2
8(1 - -8) (1 (1- A,8)2
lim p-lim Rev (0x) A No00
+ Ax
(M.4)
A
1 8 +
A
8
B2
1 C₂
A
Remark M.1 (Random data selection). In the case of no data selection, T(x) = 7, we have A_ A 1, B, B C₂ Cj, and recover the result of ordinary ridgeless regression Advani et al. 2020 Hastie et al. 2022)
B²
8> 1 :
lim p-lim Rese Rox( 8-1 X- No00000
(C)
(M.5)
A
8
B²
8< 8<1:
lim p-lim Ruc (ox B²(1 x N000
+
C₁
(M.6)
A
33

---

Published as a conference paper at ICLR 2024
M.1 PROOF OF PROPOSITION M.2
Since we are assuming perfect surrogate, Ot = 0, by applying Theorem we get
p-lim R(Ox) = 1B Go ai {[))
N-0000
=1 - -2B + 2 + (ai))
(M.7)
whence the excess error is
p-lim min Res (0s) = (4) A No
2 - (a
(M.8)
Simplifying the Lagrangian [M. in the case of perfect surrogate, we get (recalling that d = 607)
1 Lu (ap a1) 2 VV - 2B000 + a + +0
a1
+ 1
v8
27
2 G(a)) + 27
In the limit - 00 a= = [ag: a²) given by
a arg min ||a|| a E arg mig G(a))
(M.9)
Depending on the value of d, the solution of this problem is achieved in different domains of the plane:
For > arg min aeR G(a)² is uniquely achieved when G((x) > 0, and hence
satisfies VG((a) = 0, G((a) > Simple calculus yields
B
0
(M.
A
1 C.
B
a
1
(M.11)
An
For 8 < I, arg wogminnget aix G(a) Sp:= (a: G(ar) 0}, and it easy to see that (for
To = C - -B2/An))
So a1) R20: Q(a) = - -1ja An An(00
B
ro 0)
Ar
(M.12)
Hence we as solves (for Lagrange multiplier )
vQ(a) = E Q(a) = 0,
(M.13)
which are easily solved.
The proof is completed by substituting this solution in Eq. (M.8)
N SYNTHETIC DATA NUMERICAL EXPERIMENTS
It is instructive to compare the scheme described in Eq. 1 with influence function -unetion-based data selection, cf. Example 4.2 Within the present data model, the population Hessian takes the form
( "[[""(10 ([[+)]])), b+ ([d"((] ()) 1)}. The score of Example 4.2 (cf. Eq. 4.7) reads (an overall factor da_ is immaterial and introduced for convenience)
H a I + b, 0
| where a+
||0;12 b_ (0. xx.)2
7(x;)) 8² ("00,, mil)
(N.1)
do 10
34

---

Published as a conference paper at ICLR 2024
28%
201
(10
H6:tasPPttonn Rate
2.54
5.0%
1.4
1.9%
1-5:L115 (15://100
J 200, 10
1256
MiStNSPPCCtt Ratt.
206
45% 62%
80%
20%
40% 65%
60%
40% 60% Aareeitage cuncampphl
30%
Aaroweoge of 390 (uccappe)
A61001333 0a13 Succamples
Figure 5: Misclassification error for logistic regression after rewereeeegtted subsampling under the scheme of Eq. (6.I). Here 34345, = 932. Circles are results of numerical simulations, and continuous lines theoretical predictions. Each panel corresponds different choice of |[0p]l.
A.
1-00000, [-U)
Rocastocttin Rate
4554
40%
Miscass Miscassicaton Picttont 2330
45%
40%
20%
1=:0
10:11=20
MiccasFicaa Frattin Rate
35%
30%
20%
427
62%
80%
70%
10%
62%
42%
20% 10% Cms. 80%
Nacontage andoumpped
Narorraaga data vntoumpted
Figure 6: Same as Figure with N 6870 and p = 3000.
35

---

Published as a conference paper at ICLR 2024
1,
0.0.I.N.. PTY fyce)
No. 4p. MY Ajei 6i
Micclassifica fiaatiiiiatiinn Rate
23%
20%
10%
7- 01 N. PLY
0.03. Rp. PIY 1,00
A 0.001, Na. Sp. 6129
Misclacefiaaiin Rate
25%
15%
10%
20%
60%
80%
80%
20% 40%
60%
80%
2015
40%
800
80%
Percentage of data subssampeed
Percentage data subsampled
Percentage go of data subsampled
Figure 7: Misclassification enror for logistic regression after non-reweighted subsampling with data generated according to the same misspecified model as in Figure 2 Circles: simulations. Continuous
lines: theory. Here N = 34345, p = 932. Unlike in Figure we use an imperfect surrogate 0 that fit on Na samples from the same distribution. Top row: No. 4p. Bottom row: No, 8p. The values of À indicated in the plot titles are used when learning on the selected subsample.
where a = 1/a4, b_ (a+ + +b+)-1 144)-1112 1/a.. For large dimension d, [
and (Oo, æ.) (P()). We therefore get
7(x;) = d"((,, 2;)) (1+
(N.2)
Therefore ceatteecceffnnctioo based subsampling essentially corresponds to the case 1/2 of Eq. (6.1)
Figures and report results of simulations (circles) and thcoretical predictions (continuous lines), respectively in a lower-dimensional setting (N = 34345, p = 932) and higher-dimensional setting (N 6870, p 3000). Simulation results medians over 10 realizations. Theoreti- cal predictions are computed by evaluating the saddle point formula of Theorem 4 Finally, while all previous figures use a perfect surrogate, Figure explores the impact of an imperfect surrogate. Namely, we estimate 0" by using Na, independent samples from the same distribution as the training samples. We train ê" using ridge-regularized logistic regression, with an oracle choice of the reg- ularization parameter x. This setting gives an intuitive understanding of the 'cost' of the surrogate model. We choose N... 4p (top row) or N_ Sp (bottom row), corresponding to N../NN Rs 10.9% or / 21.7%. respectively.
The agreement between theoretical predictions and simulation results is again excellent. Also, we observe behaviors that are qualitatively new with respect to the previous setting that assumes well- specified data and a perfect surrogate. Most notably:
1. Learning after data selection often outperforms learning the full sample.
2. Upsampling 'hard' datapoints (i.c. using > 0) is often the optimal strategy. This appears to be more common than in the well-specified case.
3. As shown in Figure the performance data selection- based learning degrades gracefully with the quality of the surrogate.
4. In particular, we observe once more the striking phenomenon of Figure I cf. bottom row, rightmost plot of Figure 7 At subsampling fraction n/N = 60%, learning on selected data outperforms learning the full data, even if the surrogate model only used additional N_, /N z 21.7% samples. As shown in next section, this effect even stronger with real data.
36

---

Published as a conference paper at ICLR 2024
O REAL DATA NUMERICAL EXPERIMENTS
0.1 DATASET
We use subset of images obtained from the KITTI-360 train set (Liao et al. 2022 The KITTI- 360 train comprises 1408 376 dimensional 8-bit stereo images, with 2D semantic and instance labels. These images are sourced from 9 distinct continuous driving trajectories. We only consider the left stereo image for our dataset. To adapt this dataset for binary classification task, we initially center-crop the images to dimensions of 224 224 pixels. Subsequently, we assign binary labels, by setting y4 = +1 if the count of pixels containing the semantic label in a certain class surpasses a predefined threshold. We choose 'car' as the label and the pixel cutoff threshold is set at 50, resulting in chance accuracy of approximately 0.69.
We then extract SwAV embeddings of the images swav :ea:i'mann. 'resnet50') as the base the 2048 dimensional outputs from the penultimate layer (head) the SWAV
as feature vectors (Caron et al. 2021). We
use torch. hub. load 'facebookresear" model and features. Following common practice, we normalize the images before computing feature vectors, using mean and standard deviations of the images calculated on ImageNet. This results in a dataset with total of N = 61, 280 images with p = 2048 dimensional features with binary labels indicating the presence or absence of a car.
O.2 EXPERIMENT SETUP
We randomly partition this dataset into four disjoint sets: Nuai = 34, 345 images to perform sub- sampling and train models, N = 14, 720 images to train surrogate models, No. 3665 images for validation and Nea = 8550 images for reporting the final experiment results. Prior to model training. we center and normalize each of the features using mean and standard deviation calculated from Maai and N
We proceeded by training a rigue-regul logistic regression model without intercept. The train- ing utilized the L-BFGS optimization algorithm with cap of 10,000 iterations implemented using the scikit-learn library (Pedregosa et al. 2011). Surrogate models are trained on a fraction of the surrogate set (N..)) where & (10%, 50% 100%) using 5-fold cross validation to choose the regularization parameter x. Note that, the sample sizes used for these surrogate models correspond to (4.2%, 21.4%, 42.8% of Numin (but
disjoint set of data).
We use the data selection procedure introduced in the previous section, cf. Eqs. (6.1). show empirical results for E {-2, 1, -0.5, 0, 0.5, 0,5, 1, where subsampling and positive (negative) values a correspond to upsampling hard (easy) examples respectively. To ensure numerical stability for negative values of modify the definition of in Eqs. (6.I). by limiting (0",,,) to in [-10, 10).
(6.1). We corresponds to random
We also perform experiments in which we select the samples with the largest (or smallest) values of p00 .x,) v(0"",, ,æ,))). This corresponds to the limit cases - oo and + -o0 respectively. We will refer to these limit cases as 'Hard topk' and 'Eas topK', respectively.
O.3 ADDITIONAL RESULTS
All experiments repeated across five random subsamplings when the data selection scheme is probabilistic and across three different surrogate models when the surrogate model is trained an a strict subset of the N... samples reserved for this.
We vary four different parameters in our experiments:
The ridge regularization parameter X. This is either fixed or selected optimally by tak- ing X" = arg min x Rm,(O (0x), where Ru is the risk on the validation set and A = {0.001, 0.01, 0.03, 0.06, 0.1, 10
Formally, we replace (0" m)) by T((0", ,x))), where T(x) min (max(æ, -00), 10).
37

---

Published as a conference paper at ICLR 2024
Unbiased data selection
Non-reweighting data selection
23%
duta
Full s0ta
Essy took
Misclassification Rate
20%
220
20%
6 2.0
11.
-1.
18%
0.5
Misclassification
18%
0.5
05
15%
15%
(random)
12%
12%
10%
10%
Percentage of data subsampled 100%
Percentage of data subsampled
Figure 8: Test error image classification task, for model trained after data subsampling. Effect of changing a in the subsampling probabilities, cf. Eq. 6.1). Here we use both unbiased (left) and non-reweighting (right) subsampling schemes with Tharr tain
4.2%.
Full data
13%
Full data
20%
Weak
Weak
Misccassification Rate
12%
18%
Strong
Strong
Random sampling
Misclassification
11%
Random sampling
16%
12%
8%
05
20%
40%
60%
60%
100%
0%
20%
40%
60%
80%
100%
Percentage of data subsampled
Percentage of data subsampled
Figure 9: Test error on image classification task. Here X 0.001, 0.5, and newerehegg subsampling. Left plot: N = 3434, p 2048; right plot: N 34345, p 2048. Various curves correspond to different surrogate models.
The exponent that parameterizes the subsampling probabilities.
The 'strength' of the surrogate model, surr, namely, the sample size n [0, Nar) used to learn 0 We will report the ratio / as this provides direct measurement of how much information is required to train the surrogate model. In particular, we will qual- itatively refer surrogate models in results and figures as 'weak', 'medium' and 'strong' for the cases where: nuuu//Nraain 4.2%, / 21.4% and Rowr/N respectively.
42.8%
A binary parameter bias indicating whether we are using unbiased or non-reweighted sub- sampling (referred to biased sampling in Fig.
Figure reports the misclassification rate on the test set as a function of the subsampling fraction for various values of the exponent a. We consider both unbiased and non-reweighting subsampling and use 'weak" surrogate models. In this case, we select À optimally, as described above. We observe that subsampling with a outperforms training on the full sample down subsampling ratios 2 0.4. This is most significant with non-reweighing subsampling, as anticipated by the asymptotic theory of Section 4.1 Further, above this value of 7, the test error fairly insensitive to the choice of a 0. The situation changes dramatically at smaller subsampling fractions. In particular, for non-reweighting subsampling and for < 0.3, soft subsampling a 0.5 outperforms substantially Negative (upsampling easy examples) always underperforms with respect to
2 and random in this case.
Figure g investigates the effect of the strength of the surrogate model. In both subplots, fix 0.001, a 0.5, and subsampling with no-reweighting The two subplots correspond to dif- ferent regimes of the number of camples-to-prameterr ratio. The left subplot uses 10% of the total
38

---

Published as a conference paper at ICLR 2024
available training set (i.e. N = 0.1 x Nuai 3434) as 100% train data, while the right subplot uses the entire training set (i.e. N aan = 34, 345). Each subplot shows subselection performance for three different surrogate models- 'weak', 'medium' and 'strong' described above.
We observe that at larger sample size N (right subplot), the test error of the model learnt after subsampling is insensitive the accuracy of the surrogate model. We recover the results of Figure X irrespective of the strength the surrogate. This is encouraging because indicates that weak supervision is sufficient for effective data selection. Even more surprising is the behavior at smaller sample size (left plot). In this case the weak surrogate outperforms medium and strong surrogates. similar phenomenon was derived in a minimax setting in Section 4.5
SOME USEFUL FORMULAS FOR BINARY CLASSIFICATION
In line with the model introduced in the main text, we consider y E [+1,-1] and
P(y + +1/x,) f((Ou, xz,). (In other words, P(+1(2) = 1
(P.1)
fz2). We use logistic loss
L(y; 2) = yz + log(e + e*). Formulas below are obtained by specializing the results of Section
(P.2)
Unbiased subsampling. The Lagrangian takes the form
L(a, n) = 2 a 250 ua?
(P.3)
1 + E s(100|/)))) min Mo + + +1) + 2 ((
+ (1 f(((ou]loo) min [L(aGGu a.G, + u; -1) (((((B))(u HER
Non-reweighted data selection.
In this case Lagrangian reduces
L(a, A 1 250 uai
(P.4)
1
+ E (() g)) min [LagG a,G, + u; +1) + zd (u - a_ G1)
WER
+ (1 (1- +11-((100](0)) g))
min uek
eelunGn++ssoe - w; 11 + 3 u - a G )1]
Misclassification error. For Liz (yi 1 <));
R(A;0) 2 2
E (2f([0oll2G) (2 G) - 113.
:: V a²
4
(P.5)
39


Reviews:
[{"review_id": "e9fRBgLKj0", "reviewer": "Reviewer_Vo45", "summary": "The paper considers a problem of selecting a subset of the data that results in a best performance under the empirical risk minimization setting. Further, labels are considered to be unknown, with an available surrogate model that can be used for estimating the labels. The task is accomplished by finding selection probabilities and a corresponding reweighting scheme that depends on the input data without labels. There are multiple results, that showcase properties of different selection schemas, their applicability and general recommendations for designing subsampling procedures.", "questions": "- To clarify the assumptions, how applicable is the method to models with multiple local minimas? (non-convex losses and models)\n- Related to the previous question, how applicable is the method to various non-linear models? For example, any model that contains non-trivial non-linearity, such as a two-layer network?\n- Is it possible to use gradient-based and similar approximate procedures that require low subsampling error over the whole parameters space to converge (difference between Loss under subsampled data and full data to be small not only at the optimal values of parameters)? \n- There is an extensive theory of data selection in the case when labels are known (in that case there are methods that guarantee low multiplicative or additive error over whole parameters space, far from optimum, when comparing full and subsampled datasets); would it be possible to evaluate the proposed model against such prior art, for example, considering a \"perfect oracle\" that exactly predicts the labels in the proposed setting?", "limitations": "", "rating": 10, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "A thorough study is performed about the general properties, that are beneficial for all subsampling schemes. Importantly, model generalization was well studied, in addition to the task of just solving an optimization problem. Biased to unbiased sampling comparison was very insightful, as there are many works where only unbiased sampling is considered, which appeared to be suboptimal under the presented setting.\n\nAdditional note after the Reviewer-Authors discussion (review score raised): \n\nThe paper reveals properties of data selection schemes, unusual in the well-established fields of data selection, such as the field of coresets. This is in part accomplished by formulating a different goal (such as the equation 4.3 in section 4) of data selection compared to one of the common goals of replicating the ERM loss on the full labeled data. It is expected that the paper will have a broader impact on the field of data selection under a variety of practical settings.", "weaknesses": "My main concern is the applicability in general setting and the assumptions in the paper:\n- There is a concern in that (to my understanding) only the behavior exactly at the the optimum was considered (or at least in a small neighbourhood of the optimum), for example, refering to the equation B.3 (definition of the error based only on optimal values of the parameters); and the assumption B.1.A1. (lack of multiple optimal values). In most non-trivial non-linear models an iterative optimization procedure must be considered, which results in parameters passing through a range of values in addition to the final minima (global or local). In this case, even having a low error at the optimal paramter values will not help the optimization procedure.\n- There appears to be a dependency of some calculated values on the value of optimal parameters that are to be estimated (\\theta^*) starting from the equation 4.2. It was unclear for me whether we can use estimates of such parameters and how correct would be the final results when the assumptions are violated or some values are replaced with estimates (in case if closed form solutions are unavailable).\n- Since the paper is aimed at establishing a new branch of the data selection theory, would be nice to state applicability limits (to my understanding, only linear models were considered in the examples, including linear models with simple single non-linearity, such as generalized linear models)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "R5bPvBiJl9", "reviewer": "Reviewer_NBpo", "summary": "This work studies the problem of data selection: given a large unlabeled dataset of size $N$, we would like to select a subsample of smaller size $n$ to be used for statistical analysis; e.g., one could collect only $n$ instead of $N$ labeled examples and perform statistical estimation only with this subset of data.\n\nThe authors assume access to $N$ unlabeled examples $\\\\{x_i\\\\}$ and to a \"surrogate model\", which is a weak-learner for the actual labeling problem (labels data better than random guessing) and hence can be used to predict the label $y_i$ of $x_i$.  We then select a subset $G \\subset \\\\{x_i\\\\}$ of size $n < N$ of the examples, we label the data of $G$ using the \"surrogate model\" and finally train a parameterized model with that data via regularized ERM. The question is how to select $G$ so that the trained model is actually \"good\".  \n\nThe paper presents both theoretical results and practical evidence of interesting phenomena for data selection mechanisms (in both low- and high-dimensional settings). For instance, data selection can beat training on the full sample in some cases and unbiased data selection can be highly sub-optimal compared to biased mechanisms.", "questions": "(1) How does the provided results in semi-supervised learning (where one has a small labeled dataset and many unlabeled examples but uses both for training) compare with the setting of the paper?\n\n(2) The improvement in the ERM generalization using a well-selected subsample holds even for imperfect surrogate models (from Figure 1). Is there a result that compares the weakness of the surrogate model with the improvement (for some specific examples)?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper provides various results that I find interesting: \n\n(i) While a standard method for data selection is unbiased sub-sampling, Theorem 1 shows that the error coefficient of unbiased schemes can be arbitrarily larger than that of biased ones. Hence, in many cases, unbiased subsampling is sub-optimal (e.g., Figure 1).\n\n(ii) Figure 1 and Theorem 2 provide a setting where ERM using a selected subset of the data can lead to a better model than ERM on the full dataset.\n\n(iii) The surrogate model is an important component in data selection. The authors give an example where better surrogate models do not lead to better selection.\n\nI think that the above results (among others appearing in the paper) paint an interesting picture for data selection and open nice research directions. While most of the results are based on toy examples motivating the underlying phenomena, I find this paper a good fit for ICLR and I vote for acceptance.", "weaknesses": "I think that some parts of the paper are hard to follow and could be more clearly written (for instance, Sections 4-5). I understand that due to space constraints, presentation could be more challenging. \n\nI do not find some other significant weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "nbIBIdie9J", "reviewer": "Reviewer_fDUv", "summary": "The paper studies the following problem.\nSuppose we are given $N$ unlabeled samples where each of them has an underlying label and a surrogate model that predicts labels better than random guesses.\nWe would like to select a small subset of these $N$ samples of size $n$ and use the surrogate model to obtain their corresponding labels.\nThen, we train a model based on these $n$ selected samples and their corresponding labels.\nThe question is: How do we select this subset?\nThe authors showed that if this subset is selected \"correctly\" then training on it can beat training on the full dataset in some cases.\nAlso, the authors showed that some popular choices of data selection can be suboptimal.", "questions": "Note:\n\n- Page 1 second paragraph \"close to $n$\": $n$ is not defined at this point. It is a bit weird to say close to $n$.\n\n- Paragraph below (1.2): What is cst?\n\n- In (1.3): Is $\\ell_{\\text{test}}$ a new loss function? Or should $\\ell_{\\text{test}}$ be $\\ell$?\n\n- Section 2: What is $dy$? Is it the label predicted by the surrogate model?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem seems well-motivated.", "weaknesses": "- The presentation is quite technical.\nReaders who are not experts in this area may find this paper hard to follow.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "cWnwtaq4H0", "reviewer": "Reviewer_NQ88", "summary": "This paper investigates subsampling in supervised learning. It begins by assuming a collection of labeled data points, denoted as $\\left(x_i, y_i\\right)_{i \\leq N}$, which are drawn as independent and identically distributed (i.i.d.) samples from a given distribution, denoted as $P$. Additionally, they introduce a surrogate model, denoted as $\\hat{P}(y \\vert x)$, which is capable of predicting labels more effectively than random guessing. The central objective, in the absence of access to the true labels of the data points, is to leverage the surrogate model to perform subsampling on the training data, resulting in a reduced dataset of size $n = \\gamma N$, where $\\gamma$ is a parameter in the range of $(0,1)$. This reduced dataset is then used to train the final model.\n\nThe experiments conducted by the authors have shown some intriguing outcomes. Firstly, the choice of subsampling strategy seems to have a significant impact, offering more than mere randomness in the process of reducing the samples. Secondly, in specific cases, subsampling can actually yield lower estimation errors during testing. It's worth noting that this study is supported by a solid framework of theoretical guarantees.\n\nWhile the authors have made notable strides in their experimental validations, I believe some theoretical aspects remain unaddressed through analytical tools. Several propositions and theorems presented inside the paper are scattered and might be considered as ancillary results. Nevertheless, this paper is still a solid theoretical work with robust mathematical underpinnings. The theoretical formulation of the problem and the experimental observations collectively present a nice contribution to the field, which makes this work a nice addition to ICLR. My vote is in favor of acceptance, and I am open to revising my evaluation should the authors give convincing responses to the questions raised in the Questions and Weaknesses sections.", "questions": "- **Why $\\Omega:\\mathbb{R}^p\\rightarrow \\mathbb{R}$**: In other words, why the dimensionality of parameter $\\theta$ has been assumed to be the same as that of the input vector $\\boldsymbol{x}$. Obviously, this assumption makes sense when using a linear model. However, does it alter the generality of the presented framework in any shape or form?\n\n- **In Figure 1, how do you justify the reduction in estimation error after subsampling?** The way I have understood the experiment: \"Full data\" curve uses all the 34345 data samples with **true** labels. On the other hand, the proposed scheme (in the case of a weak surrogate model) \n- - 1) First, uses only 1472 samples (with true labels) from another fraction of the dataset in order to train a surrogate model. \n- - 2) You use the above-mentioned surrogate model to select, say, 50% of the dataset (without seeing their true labels, right?), and then \n- - 3) The training procedure considers the true labels, only for the above-mentioned selected samples, and uses them for training the main model. \n\nAt the end, the main model outperforms the \"Full data\" curve. Is it because the surrogate model has been trained too good? can you please also report the estimation error of the weak and strong surrogate models? Also, it should be noted that Theorem 2 only shows that there \"exists\" cases for which $\\rho_{\\mathrm{nr}}$ is not monotonic. But it does not prove error can become lower than that of a full data ERM.\n\n- **Assumption A.1 (in Proposition B.1)**: I am a little confused here... In Proposition 4.1, do we have to assume that A.1 (of Proposition B.1) holds? Or the subsampling strategy that is guaranteed to minimize $\\rho_{\\mathrm{unb}}$ automatically satisfies this condition? (i.e., forcing the minimizers of $R_S$ and $R$ to coincide with each other)\n\n- **What (or should I say: Where) is $b(x)$ in Proposition 4.3**?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The problem setup is straightforward and easily comprehensible, yet it leads to intriguing and intricate implications from both theoretical and experimental standpoints.\n\n- Notably, the experimental findings presented in Figure 1, particularly when subsampling effectively reduces estimation errors compared to utilizing all data points, are highly intriguing.\n\n- The authors have explored a wide range of subsampling schemes, including both biased and unbiased methods. Additionally, the asymptotic analysis in this work covers scenarios in both low-dimensional and high-dimensional regimes.\n\n- The paper provides a substantial foundation of solid mathematical guarantees. I did not find any notable mathematical errors, and the theoretical results exhibit a commendable level of mathematical rigor. However, these results don't always align seamlessly with the compelling experimental findings, appearing as somewhat scattered attempts to tackle a very challenging problem.\n\n- The authors have asserted that they've uncovered intriguing connections between an almost universally unbiased subsampling scheme and a method based on \"influence functions\" from prior research, as mentioned in Remark 4.1.\n\n- The paper is well-written and is easy to read.", "weaknesses": "- The primary limitation of this paper, to the best of my understanding, is that all mathematical analyses beyond Section 4 assume that the surrogate model is equivalent to the optimal Bayes conditional distribution. In other words, the sample selection process somewhat presumes knowledge of the true label distributions. Consequently, the authors have not been able to provide a sound theoretical justification for the \"magic\" effects claimed in Figure 1. This drawback significantly affects the significance of the work, in my opinion.\n\n- Theorem 1 asserts that $\\rho_{\\mathrm{unb}}/\\rho_{\\mathrm{nr}}$ can grow arbitrarily large by selecting the feature vectors' distribution in an adversarial manner. However, can the same be said for $\\rho_{\\mathrm{nr}}/\\rho_{\\mathrm{unb}}$? What happens when the feature vectors' distribution is more generic, such as Gaussian? Without additional guarantees in these respects, the theorem may lack substantial significance.\n\n- All the mathematical analyses in this work are based on asymptotic conditions ($n,N\\rightarrow\\infty$ with $n/N\\rightarrow\\gamma$), which remain intriguing but could be expanded to encompass a broader scope. For instance, non-asymptotic guarantees and cases where $n/N\\rightarrow 0$ could be explored. \n\n- The section related to high-dimensional analysis exclusively considers a linear model with Gaussian feature vectors. Additionally, it assumes that $N/p$ converges to a known constant. These assumptions offer room for extension and relaxation.\n\n- This paper is densely packed with intricate mathematical statements, often presented in a dense manner. Many results, sometimes unrelated, may require more context and explanation than a \"9-page limit\" can accommodate. In this regard, the authors might consider submitting their work to a journal to allow for a more comprehensive presentation.\n\n- Paper has no conclusions section.\n\n**Minor comments**:\n- In Theorem 2: \"an non-empty\" -> \"a non-empty\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (oral)