Introduction
Training on ever-larger datasets is expensive, and not all samples contribute equally: careful pruning can improve how performance scales with dataset size [30 ] . Data selection formalizes this idea: given a training set S S S of n n n samples and a learning algorithm A \mathcal{A} A , find a subset I ⊆ S I \subseteq S I ⊆ S of size m < n m < n m < n such that training on I I I alone performs as well as training on all of S S S . Besides reducing computation and storage, selection is a concrete instance of the data-centric view of machine learning [40 ] , in which the dataset, rather than the model, is the object to curate.
There is a vast body of work on data selection algorithms [21 ] , which differs in what the data selection algorithm has access to and in how it uses this information. Bi-level optimization approaches [17 , 37 , 24 ] select subsets of the training set based on the error on a held-out validation set, and training-data based methods use only information stemming from the training set and the learning dynamics induced by a learning algorithm (Toneva et al., 2019; Paul et al., 2021; Killamsetty et al., 2021a; Cohen-Addad et al., 2026. Despite this empirical progress, the statistical limits of data selection remain poorly understood.
There has also been a recent line of theoretical work on the statistical aspects of data selection. For instance, data memorization is inherently related to data selection, since memorization identifies training examples that a learner cannot afford to discard. The work of Feldman [7 ] shows theoretically that on long-tailed distributions, rare examples may provide the only information about subpopulations that collectively carry substantial test mass, making their memorization necessary for near-optimal accuracy. Empirically, Feldman and Zhang [8 ] show that on standard image benchmarks memorized examples often improve accuracy on related test points, so dropping rare samples may degrade the test accuracy. In recent work, Hanneke et al. [11 ] study the following fundamental question: for empirical risk minimizers, given a set of training samples, does there exist a (smaller) good subset such that training on it performs nearly as well as training on all the samples? Their main result is to give affirmative answers in various settings. Another line of work ([18 ] ) identifies settings in which selection improves over full-sample training, and provides settings where popular selection methods like unbiased reweighting and influence-based rules are suboptimal. Neither work, however, asks what a selector can identify from the samples alone. In this work, we complete this picture by asking: when the training sample contains a subset on which training yields an accurate model, what can a data selection algorithm infer about this subset from finite training (and possibly validation) samples?
To make this question precise, let S = ( Z 1 , … , Z n ) S = (Z_1, \ldots, Z_n) S = ( Z 1 , … , Z n ) be i.i.d. samples from an unknown distribution P P P , and let A \mathcal{A} A be a learning algorithm. For I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] , write R P ( A ( S I ) ) R_P(\mathcal{A}(S_I)) R P ( A ( S I )) for the population risk under P P P of the model trained on S I = ( Z i ) i ∈ I S_I = (Z_i)_{i \in I} S I = ( Z i ) i ∈ I , and R P ⋆ R_P^\star R P ⋆ for the Bayes error. Given a budget m m m , let I ^ ⊆ [ n ] \widehat{I} \subseteq[n] I ⊆ [ n ] with ∣ I ^ ∣ = m |\widehat{I}| = m ∣ I ∣ = m be the subset chosen by our data selection algorithm, and let I ⋆ ∈ arg min I ⊆ [ n ] , ∣ I ∣ = m R P ( A ( S I ) ) I^\star\in\arg\min_{I \subseteq[n], |I|=m} R_P(\mathcal{A}(S_I)) I ⋆ ∈ arg min I ⊆ [ n ] , ∣ I ∣ = m R P ( A ( S I )) be the best subset with the same budget. Writing A ( S I ^ ) \mathcal{A}(S_{\widehat{I}}) A ( S I ) to denote the hypothesis learned from S I ^ S_{\widehat{I}} S I , we consider two ways of decomposing the excess risk, R P ( A ( S I ^ ) ) − R P ⋆ R_P(\mathcal{A}(S_{\widehat{I}})) - R_P^\star R P ( A ( S I )) − R P ⋆ :
R P ( A ( S I ⋆ ) ) − R P ⋆ ⏟ compression error + R P ( A ( S I ^ ) ) − R P ( A ( S I ⋆ ) ) ⏟ selection error , (1) \underbrace{R_P(\mathcal{A}(S_{I^\star})) - R_P^\star}_{\text{compression error}} + \underbrace{R_P(\mathcal{A}(S_{\widehat{I}})) - R_P(\mathcal{A}(S_{I^\star}))}_{\text{selection error}}, \tag*{(1)} compression error R P ( A ( S I ⋆ )) − R P ⋆ + selection error R P ( A ( S I )) − R P ( A ( S I ⋆ )) , (1)
and
R P ( A ( S ) ) − R P ⋆ ⏟ full-data excess risk + R P ( A ( S I ^ ) ) − R P ( A ( S ) ) ⏟ faithfulness gap . (2) \underbrace{R_P(\mathcal{A}(S)) - R_P^\star}_{\text{full-data excess risk}} + \underbrace{R_P(\mathcal{A}(S_{\widehat{I}})) - R_P(\mathcal{A}(S))}_{\text{faithfulness gap}}. \tag*{(2)} full-data excess risk R P ( A ( S )) − R P ⋆ + faithfulness gap R P ( A ( S I )) − R P ( A ( S )) . (2)
The first decomposition separates two questions: whether the realized training sample contains a good subset of size at most m m m (a question that Hanneke et al. [11 ] studies), and whether the data selection algorithm can identify one. In our statistical setting, however, the comparator A ( S I ⋆ ) \mathcal{A}(S_{I^\star}) A ( S I ⋆ ) is not available to the data selection algorithm, because I ⋆ I^\star I ⋆ depends on the unknown distribution P P P . The second decomposition replaces this inaccessible comparator with the full-data model A ( S ) \mathcal{A}(S) A ( S ) ; both A ( S I ^ ) \mathcal{A}(S_{\widehat{I}}) A ( S I ) and A ( S ) \mathcal{A}(S) A ( S ) can be trained on the observed data. This motivates two questions: (1) When are there more good subsets of size m m m exist, can a data selection algorithm find a good subset, and do so using only the training sample and a validation set of moderate size? (2) When this is impossible, can the algorithm use the training data alone to ensure faithfulness to full-data training, and can it optimize this faithfulness at scale?
Contributions
A statistical limit on the selection error. We separate the existence of a good subset from the ability of a data selector to find it. For every compression fraction λ ∈ ( 0 , 1 ) \lambda\in(0,1) λ ∈ ( 0 , 1 ) , training-set size n n n , and validation-set size v v v , we construct a finite family P λ , n , v \mathcal{P}_{\lambda,n,v} P λ , n , v of zero-Bayes-error classification problems with two properties (Theorem 2.1 ). First, the family is not degenerate: there is a learner A ⋆ \mathcal{A}^\star A ⋆ that, on every problem in the family, attains vanishing excess risk both when trained on all n n n examples and when trained on its best subset of size m = ⌊ λ n ⌋ m = \lfloor\lambda n \rfloor m = ⌊ λn ⌋ , so an accurate subset always exists. Second, no
selector can find one: for every learner A \mathcal{A} A and every selector Π \Pi Π that sees only the training sample and a validation set of size v v v , some problem in the family forces
E [ R P ( A ( S I m ⋆ ) ) − R P ⋆ ⏟ compression error + R P ( A ( S I ^ m ) ) − R P ( A ( S I m ⋆ ) ) ⏟ selection error ] ≥ Ω λ ( n n + v ) . \mathbb{E}\left[\underbrace{R_P\left(\mathcal{A}(S_{I_m^\star})\right)-R_P^\star}_{\text{compression error}}+\underbrace{R_P\left(\mathcal{A}(S_{\widehat{I}_m})\right)-R_P\left(\mathcal{A}(S_{I_m^\star})\right)}_{\text{selection error}}\right] \geq\Omega_\lambda\left(\frac{n}{n+v}\right). E compression error R P ( A ( S I m ⋆ ) ) − R P ⋆ + selection error R P ( A ( S I m ) ) − R P ( A ( S I m ⋆ ) ) ≥ Ω λ ( n + v n ) .
Hence every learner whose compression error vanishes, A ⋆ \mathcal{A}^\star A ⋆ among them, pays a selection error of order n / ( n + v ) n/(n+v) n / ( n + v ) with every selector: a validation set of v / n → ∞ v/n \to\infty v / n → ∞ is required to make it vanish.
Faithfulness, with a training-data only proxy. The negative result points to the second decomposition: we ask for a faithful subset, one whose training approximates the same distribution over models as training on S S S . By modeling training dynamics of gradient-based methods with the Unadjusted Langevin Algorithm (ULA), we bound the faithfulness by the trajectory-accumulated gradient discrepancy G T ( I ) G_T(I) G T ( I ) (Theorem 4.1). This gives a faithfulness proxy for any candidate subset. In Figure 1 we show that the trajectory gradient discrepancy G T G_T G T correlates with the faithfulness gap for SGD-trained models.
Figure 1. Empirical Faithfulness gap R ^ P ( A ( S I ) ) − R ^ P ( A ( S ) ) \widehat{R}_{P}(\mathcal{A}(S_I))-\widehat{R}_{P}(\mathcal{A}(S)) R P ( A ( S I )) − R P ( A ( S )) versus the estimate of G ^ T ( I ) / 2 \sqrt{\widehat{G}_T(I)}/2 G T ( I ) /2 for CIFAR-10 / ResNet-18 (left) and CIFAR-100 / VGG-16 (right) at retention fraction 0.1. Each point represents a subset from a data selection method, and A \mathcal{A} A represents the SGD training procedure. Subsets with large G T ( I ) G_T(I) G T ( I ) are the ones with the largest gap. The inset (right) zooms in on the dotted region. Points in the upper-right corner correspond to EL2N (EL2N in Figure 2 achieves lower accuracy), confirming the theoretical prediction of Theorem 4.2.
A simple algorithm with an improvement guarantee. Minimizing G T ( I ) G_T(I) G T ( I ) is NP-hard, and we do not claim to solve it optimally. Existing gradient-based selectors only optimize relaxations of it, for instance by matching gradients at a single training iterate or by scoring examples independently (Remark 4.3 ), so none directly target the quantity our bound controls. Instead, we give a simple swap-based local search algorithm that, starting from any subset, halts or identifies a subset I I I that decreases G T ( I ) G_T(I) G T ( I ) . One can start from the full training data, or aim to refine the output of another selector (Theorem 4.6 ). Its cost is dominated by per-example gradients, which we approximate using a single early checkpoint, yielding an estimate G ^ T \widehat{G}_T G T of G T G_T G T . On CIFAR-10 and CIFAR-100, this simple method is on par with existing static data selection baselines. This opens up avenues for improving the optimization of G T ( I ) G_T(I) G T ( I ) as a way to improve data selection.
Statistical Limits of Optimal Subset Selection
In this section, we start by defining the task of finding the optimal subset in the training set. A natural comparator (or goal) is as follows: Fix a possibly randomized learning algorithm A = { A n } n ∈ N \mathcal{A}=\{\mathcal{A}_n\}_{n\in\mathbb{N}} A = { A n } n ∈ N , where A m \mathcal{A}_m A m is the learner applied to samples of size m m m and a training sample S = ( Z 1 , … , Z n ) ∼ P n S=(Z_1,\ldots,Z_n)\sim P^n S = ( Z 1 , … , Z n ) ∼ P n . Assume that we have a budget of size m m m for data selection. For every index set I ⊆ [ n ] I\subseteq[n] I ⊆ [ n ] , let S I = ( Z i ) i ∈ I S_I=(Z_i)_{i\in I} S I = ( Z i ) i ∈ I , with the indices in increasing order. Let
I m ⋆ ∈ arg min I ⊆ [ n ] ∣ I ∣ = m R P ( A m ( S I ) ) , (3) I_m^\star\in\underset{\substack{I\subseteq[n]\\ |I|=m}}{\arg\min}\ R_P\left(\mathcal{A}_m(S_I)\right), \tag*{(3)} I m ⋆ ∈ I ⊆ [ n ] ∣ I ∣ = m arg min R P ( A m ( S I ) ) , (3)
with ties broken canonically. Thus R P ( A m ( S I m ⋆ ) ) R_P\left(\mathcal{A}_m(S_{I_m^\star})\right) R P ( A m ( S I m ⋆ ) ) is the risk of the best subset that an oracle with access to P P P can find in the realized sample. Importantly, the oracle must use the same learner A \mathcal{A} A as the data selector.
Let V ∼ P v V\sim P^v V ∼ P v be an independent validation set, and let Π : Z n × Z v ⟶ { I ⊆ [ n ] : ∣ I ∣ = m } \Pi:\mathcal{Z}^n\times\mathcal{Z}^v\longrightarrow\{I\subseteq[n]:|I|=m\} Π : Z n × Z v ⟶ { I ⊆ [ n ] : ∣ I ∣ = m } be a (possibly randomized) data selection algorithm. Write I ^ m : = Π ( S , V ) \widehat{I}_m:=\Pi(S,V) I m := Π ( S , V ) for the selected subset. Letting A = A m \mathcal{A}=\mathcal{A}_m A = A m denote the learning algorithm fed m m m samples, the excess risk of the hypothesis A ( S I ^ m ) \mathcal{A}(S_{\widehat{I}_m}) A ( S I m ) can be decomposed into the compression error and selection error as in Equation (1) . Both terms in this decomposition are nonnegative: the first asks whether the training sample contains a good size-m m m subset for A m \mathcal{A}_m A m , and the second measures the cost of finding one using Π \Pi Π . As we will show, there exists a class of problems for which we have a dichotomy: every size-m m m subset has large compression error for A m \mathcal{A}_m A m , or a good subset exists, but Π \Pi Π cannot identify it.
Theorem 2.1. Consider multiclass classification with ordinary 0 0 0 –1 1 1 loss. Fix any compression fraction λ ∈ ( 0 , 1 3 ) \lambda\in(0,\frac{1}{3}) λ ∈ ( 0 , 3 1 ) , set γ : = 1 3 − λ \gamma:= \frac{1}{3} - \lambda γ := 3 1 − λ , and set K : = 2 ⌈ 8 / γ ⌉ K := 2^{\lceil8/\gamma\rceil} K := 2 ⌈ 8/ γ ⌉ . Let the label space be [ K ] [K] [ K ] . There exist n λ ∈ N n_{\lambda} \in\mathbb{N} n λ ∈ N and C λ > 0 C_{\lambda} > 0 C λ > 0 , depending only on λ \lambda λ , with the following property: For every integer n ≥ n λ n \ge n_{\lambda} n ≥ n λ and integer validation size v ≥ 0 v \ge0 v ≥ 0 , setting m = ⌊ λ n ⌋ m = \lfloor\lambda n \rfloor m = ⌊ λn ⌋ , there is a finite family P λ , n , v \mathcal{P}_{\lambda,n,v} P λ , n , v of deterministic-label K K K -class classification distributions, together with an explicit deterministic learner A ∗ \mathcal{A}^{*} A ∗ , such that, (1) every member of the family has zero Bayes risk and the risk of the model learned by A ∗ \mathcal{A}^{*} A ∗ converges to zero; (2) for every pair consisting of a learner A m \mathcal{A}_{m} A m and a data selector Π \Pi Π , there exists P ∈ P λ , n , v P \in\mathcal{P}_{\lambda,n,v} P ∈ P λ , n , v such that, for independent samples S ∼ P n S \sim P^{n} S ∼ P n and V ∼ P v V \sim P^{v} V ∼ P v ,
E S [ R P ( A m ( S I m ∗ ) ) − R P ∗ ] + E S , V , Π [ R P ( A m ( S I ^ m ) ) − R P ( A m ( S I m ∗ ) ) ] ≥ λ γ 2 264 n n + v , (4) \mathbb{E}_{S}\left[R_{P}\left(\mathcal{A}_{m}(S_{I_{m}^{*}})\right)-R_{P}^{*}\right]
+\mathbb{E}_{S,V,\Pi}\left[R_{P}\left(\mathcal{A}_{m}(S_{\widehat{I}_{m}})\right)-R_{P}\left(\mathcal{A}_{m}(S_{I_{m}^{*}})\right)\right]
\ge\frac{\lambda\gamma^{2}}{264}\frac{n}{n+v}, \tag*{(4)} E S [ R P ( A m ( S I m ∗ ) ) − R P ∗ ] + E S , V , Π [ R P ( A m ( S I m ) ) − R P ( A m ( S I m ∗ ) ) ] ≥ 264 λ γ 2 n + v n , (4) where I ^ m = Π ( S , V ) \widehat{I}_{m} = \Pi(S,V) I m = Π ( S , V ) satisfies ∣ I ^ m ∣ = m |\widehat{I}_{m}| = m ∣ I m ∣ = m , and I m ∗ I_{m}^{*} I m ∗ minimizes R P ( A m ( S I ) ) R_{P}(\mathcal{A}_{m}(S_{I})) R P ( A m ( S I )) over I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] with ∣ I ∣ = m |I| = m ∣ I ∣ = m . Moreover, these families and the corresponding learners can be chosen so that, for every n ≥ n λ n \ge n_{\lambda} n ≥ n λ and for every P ∈ P λ , n , v P \in\mathcal{P}_{\lambda,n,v} P ∈ P λ , n , v
n + v n E S [ R P ( A ∗ ( S ) ) − R P ∗ ] ≤ C λ log n , (5) \frac{n+v}{n}\mathbb{E}_{S}\left[R_{P}\left(\mathcal{A}^{*}(S)\right)-R_{P}^{*}\right] \le\frac{C_{\lambda}}{\log n}, \tag*{(5)} n n + v E S [ R P ( A ∗ ( S ) ) − R P ∗ ] ≤ log n C λ , (5) n + v n E S [ R P ( A ∗ ( S I m ∗ ) ) − R P ∗ ] ≤ C λ log n . (6) \frac{n+v}{n}\mathbb{E}_{S}\left[R_{P}\left(\mathcal{A}^{*}(S_{I_{m}^{*}})\right)-R_{P}^{*}\right] \le\frac{C_{\lambda}}{\log n}. \tag*{(6)} n n + v E S [ R P ( A ∗ ( S I m ∗ ) ) − R P ∗ ] ≤ log n C λ . (6) In Equation (6) , I m ∗ I_{m}^{*} I m ∗ is the optimal subset for A ∗ \mathcal{A}^{*} A ∗ .
The full proof is given in Section B. Let us unpack the implications of this result:
Accurate subsets exist: Bayes risk is zero, and there exists an algorithm for the class of problems (A ∗ \mathcal{A}^{*} A ∗ in Theorem 2.1 ) that achieves vanishing error on both the full sample and a distribution-aware oracle subset of at most ⌊ λ n ⌋ \lfloor\lambda n \rfloor ⌊ λn ⌋ examples. Thus the problem is non-degenerate.
Sample-based selection is hard: Finding such a subset can nevertheless be statistically hard: for fixed λ \lambda λ and v = O ( n ) v = O(n) v = O ( n ) , for every selector-algorithm pair such that the algorithm has small compression error, the selection error is bounded below by a constant even with unlimited computation.
Tightness: Our lower bound in Theorem 2.1 is tight in its dependence on the number of training samples. Specifically, conditional on the training sample S S S , running A m \mathcal{A}_{m} A m on all subsets of S S S of size m m m induces a finite hypothesis class of size at most ( e n / m ) m (en/m)^{m} ( e n / m ) m . Standard generalization bounds (Shalev-Shwartz and Ben-David, [28 ] ) guarantee that a validation set of size v = Θ ( λ n / ε 2 ) v = \Theta(\lambda n/\varepsilon^{2}) v = Θ ( λn / ε 2 ) suffices to achieve selection error ε \varepsilon ε .
Remark 2.2 (long-tail distributions in practice). The family of distributions in our lower bound shares the long-tail structure of Feldman [7 ] : there are as many rare subpopulations as training examples, so many of them appear once or never in the training set. There, the subpopulations are unrelated, so one that is absent from the training set cannot be predicted, even by full-data training or by an oracle that knows the distribution. Our main technical contribution is to relate rare subpopulations to one another. This is why an accurate subset of size m m m exists: an oracle that knows which rare subpopulations will matter at test time keeps only the examples needed to reconstruct them.
Proof overview of Theorem 2.1 . The natural starting point is to consider a long-tailed distribution from Feldman [7 ] with Θ ( n ) \Theta(n) Θ ( n ) rare subpopulations, so that accurate prediction requires retaining a large amount of information from the training sample. The immediate difficulty is twofold: in a sample of size n n n , a constant fraction of the subpopulations never appear at all, so even full-data training fails on them; and if predicting well requires storing more than m m m pieces of information, then a population-aware oracle with budget m m m fails as well. Our construction resolves this difficulty by identifying the subpopulations with the edges of a cubic graph G G G of logarithmic girth (using Erdős–Sachs) and coupling their labels through parity constraints: each edge carries a label in F 2 \mathbb{F}_2 F 2 , and the labels of the three edges at every vertex sum to zero.
To create a gap between the oracle and the selector, we partition the edges into small groups and designate one hidden active edge in each group; the test distribution places its hard inputs only on active edges. Most examples are clear : they reveal a uniformly random edge together with its label. A small fraction are masked : their input shows an active edge but hides its label. Since masked examples are rare, most groups receive none of them in ( S , V ) (S,V) ( S , V ) , and for these groups the selector cannot tell which edge is active.
This is what makes selection hard. The parity constraints impose only 2 N / 3 2N/3 2 N /3 equations on N ≈ n N \approx n N ≈ n edges, so the labels still carry about 1 3 N B \frac{1}{3}NB 3 1 N B bits of information. A selector that does not know the active edges must preserve all of it, yet a subset of m = ⌊ λ n ⌋ m=\lfloor\lambda n\rfloor m = ⌊ λn ⌋ examples conveys at most n + m B n+mB n + m B bits. When λ < 1 / 3 \lambda<1/3 λ < 1/3 , this gap forces any selector–learner pair to err on Ω ( γ n ) \Omega(\gamma n) Ω ( γ n ) edges, and since the active edge of each group is hidden, these errors translate into test risk.
The same graph structure allows full-data training and the oracle to succeed. Each edge is missing from S S S with probability about e − 1 < 1 / 2 e^{-1}<1/2 e − 1 < 1/2 , so in the cubic graph G G G the missing edges form small components, which are trees because G G G has large girth. Summing the parity constraints over one side of such a tree expresses the label of a missing edge as a sum of observed labels on its boundary. Every edge therefore has a small certificate in S S S that determines its label, except with probability O ( 1 / log n ) O(1/\log n) O ( 1/ log n ) . Full-data training contains every certificate, while an oracle that knows the active edges keeps only theirs, which fit within the budget m m m .
Faithful data selection
The previous section studied the conventional goal of data selection: returning a subset of the training sample whose population error nearly matches that of the best subset I m ∗ I_m^* I m ∗ in Equation (3) . However, our results show that for every pair consisting of a learning algorithm and a data selection algorithm, there exists a scenario in which the data selection algorithm incurs a non-vanishing selection error unless it has ω ( n ) \omega(n) ω ( n ) validation samples, even though a simple learner trained on all of S S S succeeds there. We therefore change the goal.
The selection error in Equation (1) compares the chosen subset with I m ∗ I_m^* I m ∗ , which depends on the data distribution P P P and is unknown to the selector. Instead, let us consider comparisons to the model trained on all of S S S , which the selector can access. In particular, consider the decomposition of the excess risk of the selected subset described in Equation (2) . The first term (full-data excess risk) does not involve the selector and is typically small in practice, since data selection is usually applied when training on the full sample already performs well. Therefore, excess risk of the selected subset is then essentially the second term: the faithfulness gap. Motivated by this, we seek a subset on which training yields a model that closely tracks the full-data model.
Remark 3.1. We do not claim that we can overcome the fundamental lower bound in Theorem 2.1 , since the result provides a lower bound on the excess error directly. Indeed, the hard class of distributions we introduced is such that the faithfulness gap is large. When the gap is small, perhaps we can find and optimize faithful subsets. As we show next, we provide a practical proxy that can be computed from the training set and has the property that, if the proxy is small, we know that the faithfulness gap is small.
From faithfulness to KL divergence
How can we control the faithfulness gap? The faithfulness gap in Equation (2) is the difference between the averages of one function, θ ↦ R P ( θ ) \theta\mapsto R_P(\theta) θ ↦ R P ( θ ) , under two distributions over trained parameters: the law A n ( S ) \mathcal{A}_n(S) A n ( S ) of the model trained on S S S and the law A m ( S I ) \mathcal{A}_m(S_I) A m ( S I ) of the model trained on the subset. We cannot evaluate this function, since P P P is unknown, but we do not need to: if the two laws are close, every bounded function of θ \theta θ has nearly the same average under both, whatever P P P is. We therefore call a subset faithful if training on it produces nearly the same distribution over models as training on S S S . This requirement is stronger than a small faithfulness gap, and usefully so: it controls the gap under every data distribution at once, and it controls every other bounded evaluation of the trained model, which we call a query . Examples include accuracy on a subgroup or on a rare subpopulation, accuracy under distribution shift, and the loss or prediction at a single test point as in data attribution (Ye et al., 2024). The next result, whose proof (Section C) is simply based on the variational representation of total variation distance and Pinsker’s inequality, formalizes this intuition:
Proposition 3.2. Let a , b ∈ R a, b \in\mathbb{R} a , b ∈ R and n , m ∈ N n, m \in\mathbb{N} n , m ∈ N such that 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n . Let q : R d → [ a , b ] q : \mathbb{R}^{d} \to[a,b] q : R d → [ a , b ] be a measurable bounded function. Fix S ∈ Z n S \in\mathcal{Z}^{n} S ∈ Z n as a training set of size n n n and let I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] be an arbitrary subset of [ n ] [n] [ n ] such that ∣ I ∣ = m |I| = m ∣ I ∣ = m . Then, for every randomized algorithm A = { A m } m ∈ N \mathcal{A} = \{\mathcal{A}_m\}_{m\in\mathbb{N}} A = { A m } m ∈ N , we have:
∣ E θ ∼ A n ( S ) [ q ( θ ) ] − E θ ′ ∼ A m ( S I ) [ q ( θ ′ ) ] ∣ ≤ ( b − a ) 2 2 D K L ( A n ( S ) ∥ A m ( S I ) ) . \left|\mathbb{E}_{\theta\sim\mathcal{A}_n(S)}[q(\theta)]-\mathbb{E}_{\theta'\sim\mathcal{A}_m(S_I)}[q(\theta')]\right|
\le\sqrt{\frac{(b-a)^2}{2}D_{\mathrm{KL}}\left(\mathcal{A}_n(S)\mathbin\Vert\mathcal{A}_m(S_I)\right)}. E θ ∼ A n ( S ) [ q ( θ )] − E θ ′ ∼ A m ( S I ) [ q ( θ ′ )] ≤ 2 ( b − a ) 2 D KL ( A n ( S ) ∥ A m ( S I ) ) .
Note that A n \mathcal{A}_n A n and A m \mathcal{A}_m A m should both share the same initialization distribution.
Practical Data Selection using Langevin Algorithm
Theorem 3.2 reduces faithfulness to a single number, D K L ( A n ( S ) ∥ A m ( S I ) ) D_{\mathrm{KL}}(\mathcal{A}_n(S)\mathbin\Vert\mathcal{A}_m(S_I)) D KL ( A n ( S ) ∥ A m ( S I )) . How can we turn this result into a faithful data selection algorithm? To select subsets with it, we need two things: an upper bound on this divergence that can be evaluated based on the training set, and a form of that bound that can be minimized over subsets.
In this section, we focus on gradient-based learning algorithms that are often used in practice. To operationalize the KL bound, we approximate gradient-based training by the Unadjusted Langevin Algorithm (ULA). This approximation lets us bound the divergence in closed form and then turn the bound into a practical and scalable algorithm.
More precisely, assume we have a fixed loss function L S ( θ ) = 1 ∣ S ∣ ∑ x ∈ S ℓ ( θ , x ) L_S(\theta)=\frac{1}{|S|}\sum_{x\in S}\ell(\theta,x) L S ( θ ) = ∣ S ∣ 1 ∑ x ∈ S ℓ ( θ , x ) and let d d d be the number of parameters. Fix a number of iterations T ≥ 1 T\ge1 T ≥ 1 , step sizes h 0 , … , h T − 1 > 0 h_0,\ldots,h_{T-1}>0 h 0 , … , h T − 1 > 0 , inverse temperatures β 0 , … , β T − 1 > 0 \beta_0,\ldots,\beta_{T-1}>0 β 0 , … , β T − 1 > 0 . On a training set S ′ S' S ′ , ULA starts from an initialization distribution θ 0 ∼ μ 0 \theta_0\sim\mu_0 θ 0 ∼ μ 0 and, for t = 0 , … , T − 1 t=0,\ldots,T-1 t = 0 , … , T − 1 , let
θ t + 1 = θ t − h t ∇ L S ′ ( θ t ) + 2 h t β t ξ t + 1 , (7) \theta_{t+1}=\theta_t-h_t\nabla L_{S'}(\theta_t)+\sqrt{\frac{2h_t}{\beta_t}}\xi_{t+1}, \tag*{(7)} θ t + 1 = θ t − h t ∇ L S ′ ( θ t ) + β t 2 h t ξ t + 1 , (7)
where ξ 1 , ξ 2 , … \xi_1,\xi_2,\ldots ξ 1 , ξ 2 , … are i.i.d. N ( 0 , I d ) \mathcal{N}(0,I_d) N ( 0 , I d ) and independent of θ 0 \theta_0 θ 0 . We write μ t S ′ \mu_t^{S'} μ t S ′ for the law of θ t \theta_t θ t , and we take the learner to be ULA stopped at iteration T T T , that is, A k ( S ′ ) : = μ T S ′ \mathcal{A}_k(S'):=\mu_T^{S'} A k ( S ′ ) := μ T S ′ for every sample S ′ S' S ′ of size k k k . ULA is gradient descent with injected Gaussian noise, and its stochastic-gradient version is the SGLD algorithm of Welling and Teh [36 ] . ULA is an approximation of how models are trained in practice. Our guarantees are proven for ULA, and § 6 shows that the resulting selection rule remains effective when models are trained with SGD.
Before stating our results, we define a quantity that we refer to as the trajectory gradient discrepancy ,
G T ( I ) : = ∑ t = 0 T − 1 β t h t 4 E θ t ∼ μ t S [ ∥ ∇ L S I ( θ t ) − ∇ L S ( θ t ) ∥ 2 ] , (8) G_T(I):=\sum_{t=0}^{T-1}\frac{\beta_t h_t}{4}\mathbb{E}_{\theta_t\sim\mu_t^S}\left[\left\|\nabla L_{S_I}(\theta_t)-\nabla L_S(\theta_t)\right\|^2\right], \tag*{(8)} G T ( I ) := t = 0 ∑ T − 1 4 β t h t E θ t ∼ μ t S [ ∥ ∇ L S I ( θ t ) − ∇ L S ( θ t ) ∥ 2 ] , (8)
the squared distance between the subset and full-data gradients, accumulated along the full-data training trajectory. The proof is deferred to Section D.
Proposition 4.1. Fix T ≥ 1 T \ge1 T ≥ 1 , step sizes h 0 , … , h T − 1 > 0 h_0,\ldots,h_{T-1} > 0 h 0 , … , h T − 1 > 0 , inverse temperatures β 0 , … , β T − 1 > 0 \beta_0,\ldots,\beta_{T-1} > 0 β 0 , … , β T − 1 > 0 , integers 1 ≤ m ≤ n 1 \le m \le n 1 ≤ m ≤ n , a training set S ∈ Z n S \in\mathcal{Z}^n S ∈ Z n , and I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] with ∣ I ∣ = m |I| = m ∣ I ∣ = m , and assume that ℓ ( ⋅ , z ) \ell(\cdot,z) ℓ ( ⋅ , z ) is continuously differentiable for every z ∈ Z z \in\mathcal{Z} z ∈ Z . Assume furthermore that E θ ∼ μ t S [ ∥ ∇ ℓ ( θ , Z i ) ∥ 2 ] < ∞ \mathbb{E}_{\theta\sim\mu_t^S}\left[\lVert\nabla\ell(\theta,Z_i)\rVert^2\right] < \infty E θ ∼ μ t S [ ∥ ∇ ℓ ( θ , Z i ) ∥ 2 ] < ∞ for all i ∈ [ n ] , 0 < t ≤ T − 1 i \in[n], 0 < t \le T-1 i ∈ [ n ] , 0 < t ≤ T − 1 . Run ULA on S S S and on S I S_I S I with these schedules. Then, D K L ( A n ( S ) ∥ A m ( S I ) ) ≤ G T ( I ) D_{\mathrm{KL}}(\mathcal{A}_n(S)\mathbin\Vert\mathcal{A}_m(S_I)) \le G_T(I) D KL ( A n ( S ) ∥ A m ( S I )) ≤ G T ( I ) .
Corollary 4.2 (Faithfulness proxy under ULA). Under the assumptions of Theorem 4.1, for all a < b a < b a < b and every measurable q : R d → [ a , b ] q:\mathbb{R}^d \to[a,b] q : R d → [ a , b ] ,
∣ E θ ∼ A n ( S ) [ q ( θ ) ] − E θ ∼ A m ( S I ) [ q ( θ ) ] ∣ ≤ ( b − a ) G T ( I ) / 2 . \left|\mathbb{E}_{\theta\sim\mathcal{A}_n(S)}[q(\theta)]-\mathbb{E}_{\theta\sim\mathcal{A}_m(S_I)}[q(\theta)]\right| \le(b-a)\sqrt{G_T(I)/2}. E θ ∼ A n ( S ) [ q ( θ )] − E θ ∼ A m ( S I ) [ q ( θ )] ≤ ( b − a ) G T ( I ) /2 .
The path-space identity behind Theorem 4.1 is the same quantity that appears as “gradient incoherence” in information-theoretic generalization bounds for SGLD ([23 , 10 ] ), and KL divergences between Langevin chains on neighbouring datasets drive Langevin unlearning ([3 , 13 ] ) and leave-one-out distinguishability ((Ye et al., 2024)).
Our contribution is not the bound but its use: we read G T G_T G T as an estimable, distribution-free proxy for the selection objective (we show in § 6 that an estimate of G T G_T G T can predict the downstream test accuracy). A notable property is that the expectation in equation 8 is over the full-data chain only, so G T ( I ) G_T(I) G T ( I ) can be estimated for every candidate subset from the same full-data training runs, using per-example gradients; this requires no training on any subset and no access to P P P or to held-out data. In Figure 1 , we estimate G T G_T G T using a single full training run for a stochastic gradient descent (SGD) trajectory and show that it still correlates with the faithfulness error.
Based on the trajectory gradient discrepancy, we define the following quadratic integer programming problem (more details in Section E):
Definition 4.4 (Selection as a quadratic program). In the setting of Theorem 4.1, write ζ i ( θ ) : = ∇ ℓ ( θ , Z i ) − ∇ L S ( θ ) \zeta_i(\theta) := \nabla\ell(\theta,Z_i)-\nabla L_S(\theta) ζ i ( θ ) := ∇ ℓ ( θ , Z i ) − ∇ L S ( θ ) for the centered per-example gradients and define C ∈ R n × n C \in\mathbb{R}^{n\times n} C ∈ R n × n by C i j : = ∑ t = 0 T − 1 β t h t m E θ ∼ μ t S ⟨ ζ i ( θ ) , ζ j ( θ ) ⟩ C_{ij} := \sum_{t=0}^{T-1}\frac{\beta_t h_t}{m}\mathbb{E}_{\theta\sim\mu_t^S}\langle\zeta_i(\theta),\zeta_j(\theta)\rangle C ij := ∑ t = 0 T − 1 m β t h t E θ ∼ μ t S ⟨ ζ i ( θ ) , ζ j ( θ )⟩ . Then C C C is positive semidefinite, C 1 = 0 C\mathbf{1}=0 C 1 = 0 , and G T ( I ) = 1 m 2 1 I T C 1 I G_T(I)=\frac{1}{m^2}\mathbf{1}_I^\mathsf{T}C\mathbf{1}_I G T ( I ) = m 2 1 1 I T C 1 I for every I ⊆ [ n ] I\subseteq[n] I ⊆ [ n ] with ∣ I ∣ = m |I|=m ∣ I ∣ = m . Consequently, minimizing G T ( I ) G_T(I) G T ( I ) over subsets of size m m m is the integer quadratic program
min α ∈ B m D ( α ) ≜ 1 m 2 α T C α , \min_{\alpha\in\mathcal{B}_m} D(\alpha) \triangleq\frac{1}{m^2}\alpha^\mathsf{T}C\alpha, α ∈ B m min D ( α ) ≜ m 2 1 α T C α , where B m : = { α ∈ { 0 , 1 } n : 1 T α = m } \mathcal{B}_m := \{\alpha\in\{0,1\}^n:\mathbf{1}^\mathsf{T}\alpha=m\} B m := { α ∈ { 0 , 1 } n : 1 T α = m } .
Algorithm 1 Gradient-ranked swap descent
Require: products v ↦ C v v \mapsto Cv v ↦ C v ; budget 1 ≤ m ≤ n − 1 1 \le m \le n-1 1 ≤ m ≤ n − 1 ; initial subset I 0 ⊆ [ n ] I_0 \subseteq[n] I 0 ⊆ [ n ] with ∣ I 0 ∣ = m \lvert I_0\rvert=m ∣ I 0 ∣ = m
Ensure: subset I o u t ⊆ [ n ] I_{\mathrm{out}} \subseteq[n] I out ⊆ [ n ] with ∣ I o u t ∣ = m \lvert I_{\mathrm{out}}\rvert=m ∣ I out ∣ = m
s 0 ← 2 m 2 C 1 I 0 s_0 \leftarrow\frac{2}{m^2}C\mathbf{1}_{I_0} s 0 ← m 2 2 C 1 I 0 \hfill s 0 = ∇ D ( 1 I 0 ) s_0=\nabla D(\mathbf{1}_{I_0}) s 0 = ∇ D ( 1 I 0 )
for k = 0 , 1 , 2 , … k=0,1,2,\ldots k = 0 , 1 , 2 , … do
i k ∈ arg max i ∈ I k s k ( i ) i_k \in\arg\max_{i\in I_k}s_k(i) i k ∈ arg max i ∈ I k s k ( i ) \hfill drop
j k ∈ arg min j ∉ I k s k ( j ) j_k \in\arg\min_{j\notin I_k}s_k(j) j k ∈ arg min j ∈ / I k s k ( j ) \hfill add
I ′ ← ( I k ∖ { i k } ) ∪ { j k } I' \leftarrow(I_k\setminus\{i_k\})\cup\{j_k\} I ′ ← ( I k ∖ { i k }) ∪ { j k }
s ′ ← 2 m 2 C 1 I ′ s' \leftarrow\frac{2}{m^2}C\mathbf{1}_{I'} s ′ ← m 2 2 C 1 I ′
if G T ( I ′ ) < G T ( I k ) G_T(I')<G_T(I_k) G T ( I ′ ) < G T ( I k ) then \hfill G T ( I ) = 1 2 1 I T s G_T(I)=\frac{1}{2}\mathbf{1}_I^{\mathsf{T}}s G T ( I ) = 2 1 1 I T s
( I k + 1 , s k + 1 ) ← ( I ′ , s ′ ) (I_{k+1},s_{k+1})\leftarrow(I',s') ( I k + 1 , s k + 1 ) ← ( I ′ , s ′ )
else
return I o u t : = I k I_{\mathrm{out}}:=I_k I out := I k
Subset selection via gradient swaps
How can we solve the program in Theorem 4.4 when n n n is large? Three facts rule out the obvious approaches. First, exact minimization of the program in Theorem 4.4 is NP-hard even for T = 1 T=1 T = 1 and d − 1 d-1 d − 1 by reduction from fixed-cardinality subset sum (and general MIQP is NP complete; [26 ] ). Second, forming C C C requires Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) inner products at every point of the trajectory, and storing it requires Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) memory. Third, relaxing α \alpha α to [ 0 , 1 ] n [0,1]^n [ 0 , 1 ] n is uninformative: since C 1 = 0 C\mathbf{1}=0 C 1 = 0 , the fractional point m n 1 \frac{m}{n}\mathbf{1} n m 1 has objective value zero and says nothing about which subset to select. These observations prompt us to focus on designing an algorithm that requires only matrix–vector products with C C C , keeps every iterate a subset of size m m m , and never increases G T G_T G T . Algorithm 1 is such a method: a local search that exchanges one selected example for one unselected example at a time.
Overview of Algorithm 1. Fix a subset I I I of size m m m and let s : = 2 m 2 C 1 I s:=\frac{2}{m^2}C\mathbf{1}_I s := m 2 2 C 1 I . Since 1 m ∑ j ∈ I ζ j = ∇ L S I − ∇ L S \frac{1}{m}\sum_{j\in I}\zeta_j=\nabla L_{S_I}-\nabla L_S m 1 ∑ j ∈ I ζ j = ∇ L S I − ∇ L S , the entry s i s_i s i equals 2 m \frac{2}{m} m 2 times the trajectory average, weighted as in Equation (8) , of ⟨ ζ i , ∇ L S I − ∇ L S ⟩ \langle\zeta_i,\nabla L_{S_I}-\nabla L_S\rangle ⟨ ζ i , ∇ L S I − ∇ L S ⟩ : it measures how strongly example i i i is aligned with the current gradient error of the subset. Exchanging i ∈ I i \in I i ∈ I for j ∉ I j \notin I j ∈ / I , so that I ′ = ( I ∖ { i } ) ∪ { j } I' = (I \setminus\{i\}) \cup\{j\} I ′ = ( I ∖ { i }) ∪ { j } , changes the objective by exactly
G T ( I ′ ) − G T ( I ) = s j − s i + C i i + C j j − 2 C i j m 2 . (9) G_T(I') - G_T(I) = s_j - s_i + \frac{C_{ii} + C_{jj} - 2C_{ij}}{m^2}. \tag*{(9)} G T ( I ′ ) − G T ( I ) = s j − s i + m 2 C ii + C j j − 2 C ij . (9)
The pair ( i k , j k ) (i_k, j_k) ( i k , j k ) minimizes the first-order term s j − s i s_j - s_i s j − s i over all m ( n − m ) m(n-m) m ( n − m ) exchanges: it drops the selected example most aligned with the error and adds the unselected example most opposed to it. The second term is the weighted squared distance between the gradients of examples i i i and j j j along the trajectory. It is nonnegative, so the first-order prediction is optimistic, and the algorithm therefore evaluates the exact objective before accepting the exchange. Every accepted exchange lowers G T G_T G T , and with it the faithfulness proxy G T ( I ) / 2 \sqrt{G_T(I)/2} G T ( I ) /2 of Theorem 4.2. Whether the algorithm starts from a uniformly random subset or from the output of another selection method, it returns a subset whose G T G_T G T is at least as small as that of its starting point. Note that although G T G_T G T is defined along a full-data training run, § 6 shows that a single early checkpoint suffices in practice.
Theorem 4.6 (Swap descent decreases the faithfulness bound). In the setting of Theorem 4.4, let 1 ≤ m ≤ n − 1 1 \le m \le n - 1 1 ≤ m ≤ n − 1 . For every initial subset I 0 ⊆ [ n ] I_0 \subseteq[n] I 0 ⊆ [ n ] with ∣ I 0 ∣ = m \lvert I_0\rvert= m ∣ I 0 ∣ = m and every tie-breaking rule in the choice of ( i k , j k ) (i_k,j_k) ( i k , j k ) , Algorithm 1 generates subsets I 0 , I 1 , … I_0, I_1, \ldots I 0 , I 1 , … of size m m m and returns I o u t I_{\mathrm{out}} I out such that:
(i) every accepted swap strictly decreases the objective, G T ( I k + 1 ) < G T ( I k ) G_T(I_{k+1}) < G_T(I_k) G T ( I k + 1 ) < G T ( I k ) , and the algorithm terminates after finitely many iterations;
(ii) if I 0 I_0 I 0 is drawn uniformly from the subsets of [ n ] [n] [ n ] of size m m m , then E [ G T ( I o u t ) ] ≤ n − m m ( n − 1 ) ∑ t = 0 T − 1 β t h t 4 V t , \mathbb{E}[G_T(I_{\mathrm{out}})] \le\frac{n-m}{m(n-1)} \sum_{t=0}^{T-1} \frac{\beta_t h_t}{4} V_t, E [ G T ( I out )] ≤ m ( n − 1 ) n − m ∑ t = 0 T − 1 4 β t h t V t , where V t : = 1 n ∑ i = 1 n E θ ∼ μ t ∥ ∇ ℓ ( θ , Z i ) − ∇ L S ( θ ) ∥ 2 V_t := \frac{1}{n}\sum_{i=1}^{n} \mathbb{E}_{\theta\sim\mu_t}\lVert\nabla\ell(\theta,Z_i) - \nabla L_S(\theta)\rVert^2 V t := n 1 ∑ i = 1 n E θ ∼ μ t ∥ ∇ ℓ ( θ , Z i ) − ∇ L S ( θ ) ∥ 2 and the expectation is over the initialization.
The proof alongside the construction of the algorithm is detailed in Section F.
Relation to prior work. G T G_T G T is not submodular, so greedy combinatorial algorithms and facility-location surrogates [34 , 14 ] carry no guarantee for it. Swap descent is thus a way to propose swaps from first-order scores but accepts them using the exact quadratic, so accepted swaps never increase G T G_T G T (Theorem 4.6 ).
Experiments
We evaluate an SGD-based estimate G ^ T \widehat{G}_T G T of G T G_T G T and our swap algorithm (Algorithm 1) around three questions: (i) how much of the full-data trajectory is needed to estimate G T G_T G T ? (ii) does G ^ T \widehat{G}_T G T track the quality of the subsets it scores? and (iii) does optimizing G ^ T \widehat{G}_T G T via local search match established selectors in accuracy?
Experimental setup
Datasets and models. We use CIFAR-10 and CIFAR-100 (Krizhevsky, [19 ] ) with three architectures: ResNet-18 (He et al., 2016), VGG-16 (Simonyan and Zisserman, [29 ] ), and Inception (Szegedy et al., [31 ] ). The same datasets and architectures are used for every selection method. Models are trained using SGD with Nesterov momentum 0.9, initial learning rate 0.01, and weight decay 5 × 10 − 4 5 \times10^{-4} 5 × 1 0 − 4 . The learning rate follows a cosine schedule for 300 epochs, with batch size 128 and cross-entropy loss. The same optimizer and schedule are used both to train the full-data reference trajectory and to retrain on a selected subset.
Estimating G T G_T G T . We do not compute G T G_T G T exactly; we estimate it and denote the estimate by G ^ T \widehat{G}_T G T . We train the full-data reference model once on a fixed random 90%/10% train/validation split and store checkpoints θ k \theta_k θ k (caveat in Section G.1). The expectation over μ t S \mu_t^S μ t S in the definition of G T G_T G T is replaced by this single realized trajectory, and the sum over steps by a weighted sum over the stored checkpoints. Neither C C C nor per-example gradients are ever formed. Writing u I k = ∑ i ∈ I ∇ ℓ ( θ k , Z i ) u_I^k = \sum_{i\in I}\nabla\ell(\theta_k, Z_i) u I k = ∑ i ∈ I ∇ ℓ ( θ k , Z i ) and g ˉ k = ∇ L S ( θ k ) \bar{g}_k = \nabla L_S(\theta_k) g ˉ k = ∇ L S ( θ k ) , we have
G ^ T ( I ) = ∑ k w k ∥ u I k / m − g ˉ k ∥ 2 , \widehat{G}_T(I) = \sum_k w_k \left\|u_I^k/m - \bar{g}_k\right\|^2, G T ( I ) = k ∑ w k u I k / m − g ˉ k 2 ,
so only one aggregate gradient per checkpoint is stored. The cost is still linear in the number of checkpoints, which makes swaps expensive for long horizons T T T , since aggregate gradients need to be recomputed after each swap. For selection we therefore use τ ∈ { 1 , 4 , 10 , 15 , 20 } \tau\in\{1, 4, 10, 15, 20\} τ ∈ { 1 , 4 , 10 , 15 , 20 } checkpoints: τ = 1 \tau= 1 τ = 1 is a single-checkpoint estimate (epoch 1), and larger τ \tau τ approaches the full trajectory average of the theory. In Figure 1 , G ^ T \widehat{G}_T G T is evaluated once per subset with no swap sweeps, so we use all 300 stored checkpoints. We refer to Algorithm 1 as Gradient Swap and add a second stopping criterion, a maximum of 200 allowed swaps.
Baselines. We compare against six static data-selection methods: Herding [35 ] , Moderate Coreset [38 ] , Facility Location and GraphCut [14 ] , EL2N [25 ] , and MoSo [32 ] . We also include random selection, which draws a uniform subset. We omit Grad-Match [16 ] and CRAIG [20 ] , since they are adaptive methods that reselect the subset periodically during training, whereas we focus on static selection, where a single subset is chosen before training.
Evaluation protocol. Each method selects a subset at four retention fractions of the training pool (10%, 20%, 40%, 50%), and the model is then retrained on the selected subset from scratch. Our main metric is the test accuracy of the retrained model, averaged over five seeds. To assess whether G T G_T G T is a meaningful target, we compare the estimated bound G ^ T ( I ) / 2 \sqrt{\widehat{G}_T(I)/2} G T ( I ) /2 to the faithfulness gap R P ( A ( S I ) ) − R P ( A ( S ) ) R_P(\mathcal{A}(S_I)) - R_P(\mathcal{A}(S)) R P ( A ( S I )) − R P ( A ( S )) for subsets produced by different selection methods at retention 0.1, where A \mathcal{A} A is SGD, and report Pearson correlation.
Results
A single early checkpoint is enough to estimate G T G_T G T . Table 1 reports the test accuracy of the selected subsets for τ ∈ { 1 , 4 , 10 , 15 , 20 } \tau\in\{1, 4, 10, 15, 20\} τ ∈ { 1 , 4 , 10 , 15 , 20 } . No two settings in a column differ by more than roughly one standard error of their difference, and there is no monotone trend in τ \tau τ . Additional checkpoints thus buy no detectable improvement while costing proportionally more, so we use τ = 1 \tau= 1 τ = 1 in all remaining experiments. This echoes the finding of Paul et al. [25 ] that relevant examples can be identified in the early stages of training. Results for other settings are reported in Section J.
Table 1. Test accuracy (%) on CIFAR-10 with ResNet-18 as a function of the number of retained checkpoints τ \tau τ , at three retention fractions
G ^ T \widehat{G}_T G T separates faithful subsets from unfaithful ones. Figure 1 plots the faithfulness gap against the estimated bound G ^ T ( I ) / 2 \sqrt{\widehat{G}_T(I)/2} G T ( I ) /2 . Subsets with large G ^ T \widehat{G}_T G T are the ones with the largest gap, with a Pearson correlation of r = + 0.98 r = +0.98 r = + 0.98 for ResNet-18 on CIFAR-10 and r = + 0.80 r = +0.80 r = + 0.80 for VGG-16 on CIFAR-100. This holds even though G T G_T G T is derived for ULA while the estimate G ^ T \widehat{G}_T G T is computed from SGD and the subset models are also retrained with SGD.
Gradient Swap matches established selectors. Figure 2 shows test accuracy against retention fraction. Across datasets and architectures, Gradient Swap performs on par with the static baselines: its accuracy falls within the spread of the baselines at every retention fraction, and it is neither consistently ahead of nor behind them. This is notable because Gradient Swap is a plain local search. We do not read these results as an argument for this particular algorithm. They show that a simple attempt at optimizing the estimate G ^ T \widehat{G}_T G T already matches established selectors, which, together with the correlation above, suggests that G T G_T G T is a good target for developing stronger selection algorithms. Furthermore, the spread of the selectors in Figure 2 is in line with the DeepCore benchmark (Guo et al. [9 ] ), which concludes that random selection remains a strong baseline. Swap descent can also refine bad selectors: warm-starting it from GraphCut, Herding, Random or EL2N lowers G ^ T \widehat{G}_T G T in every case and raises EL2N’s accuracy by 2.6 points, while leaving the other three unchanged (Appendix § 16 ).
Figure 2. Test accuracy of the retrained model versus retention fraction on CIFAR-10 (top row) and CIFAR-100 (bottom row), averaged over five seeds (std in shaded area). Gradient Swap uses τ = 1 \tau= 1 τ = 1 (epoch 1). It is competitive with static baselines while being the only method that optimizes the estimated G T G_T G T .
Discussion and Limitations
In this paper, we revisited the theoretical and practical foundations of data selection from first principles. We established a fundamental statistical limitation: even when the training sample contains an accurate subset, no selector can reliably identify one from the training sample and a validation set of comparable size (Theorem 2.1 ). This impossibility result motivated a shift from population risk minimization to faithfulness —ensuring subset training closely tracks the full-data parameter distribution. By modeling gradient-based learning via ULA, we bounded the faithfulness gap by the trajectory gradient discrepancy G T ( I ) G_T(I) G T ( I ) , a training-only quantity whose off-diagonal structure captures redundancy. Although minimizing G T G_T G T is NP-hard, our swap descent algorithm guarantees a decrease of the bound at every step. Empirically, an efficient single-checkpoint implementation matches established static heuristics on CIFAR-10/100 test accuracy.
While our algorithm performs on par with existing methods on average accuracy, this is highly encouraging: (1) it validates that directly optimizing our mathematically principled proxy (G T G_T G T ) is sufficient to match top-tier heuristics, and (2) minimizing G T ( I ) G_T(I) G T ( I ) guarantees faithfulness across all bounded downstream queries (Theorem 4.2), providing robustness guarantees where average-case heuristics fail.
Our work opens up many directions for investigation. Our lower bound suggests a deeper connection between data selection and various forms of data memorization ([2 , 1 ] ). Our guarantee is proven for ULA and is one-sided; a faithfulness bound for SGD or Adam would close the gap between analysis and practice. G T G_T G T is a difference of submodular functions ([22 , 6 ] ), so stronger solvers apply to the same objective directly, and random projections (Section K) and proxy models ([5 ] ) point to selection at scale.
Notation
Let Z \mathcal{Z} Z denote the space of data points and P ∈ P ( Z ) P \in\mathcal{P}(\mathcal{Z}) P ∈ P ( Z ) denote the underlying data distribution. We consider the standard learning problem where we have i.i.d. training samples S = ( Z 1 , … , Z n ) ∼ P n S = (Z_1,\ldots,Z_n) \sim P^n S = ( Z 1 , … , Z n ) ∼ P n from an unknown data distribution P P P . For I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] , write S I : = ( Z i ) i ∈ I S_I := (Z_i)_{i\in I} S I := ( Z i ) i ∈ I . A data selection procedure with budget m m m identifies an index set I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] with cardinality ∣ I ∣ ≤ m |I| \leq m ∣ I ∣ ≤ m . Models are parameterized by a vector θ ∈ R d \theta\in\mathbb{R}^d θ ∈ R d , and the loss incurred on an individual sample Z i Z_i Z i is given by ℓ ( θ , Z i ) \ell(\theta,Z_i) ℓ ( θ , Z i ) . The full-dataset empirical risk is defined as L S ( θ ) : = 1 n ∑ i = 1 n ℓ ( θ , Z i ) L_S(\theta) := \frac{1}{n}\sum_{i=1}^n \ell(\theta,Z_i) L S ( θ ) := n 1 ∑ i = 1 n ℓ ( θ , Z i ) , while the corresponding subset empirical risk is denoted by L S I ( θ ) : = 1 ∣ I ∣ ∑ i ∈ I ℓ ( θ , Z i ) L_{S_I}(\theta) := \frac{1}{|I|}\sum_{i\in I}\ell(\theta,Z_i) L S I ( θ ) := ∣ I ∣ 1 ∑ i ∈ I ℓ ( θ , Z i ) . For a given (randomized) learning algorithm A \mathcal{A} A mapping a dataset to a distribution over R d \mathbb{R}^d R d , the population risk of a hypothesis θ ∼ A ( S I ) \theta\sim\mathcal{A}(S_I) θ ∼ A ( S I ) trained on S I S_I S I is defined as R P ( A ( S I ) ) : = E Z ∼ P , θ ∼ A ( S I ) [ ℓ ( θ , Z ) ] R_P(\mathcal{A}(S_I)) := \mathbb{E}_{Z\sim P,\theta\sim\mathcal{A}(S_I)}[\ell(\theta,Z)] R P ( A ( S I )) := E Z ∼ P , θ ∼ A ( S I ) [ ℓ ( θ , Z )] , while the Bayes-optimal population risk is given by R P ∗ : = inf f E Z ∼ P [ ℓ ( f , Z ) ] R_P^* := \inf_f \mathbb{E}_{Z\sim P}[\ell(f,Z)] R P ∗ := inf f E Z ∼ P [ ℓ ( f , Z )] , the infimum being over all measurable predictors. For iterative learners, μ t S I \mu_t^{S_I} μ t S I denotes the law of the iterate θ t \theta_t θ t when training on S I S_I S I , and A ( S I ) = μ T S I \mathcal{A}(S_I) = \mu_T^{S_I} A ( S I ) = μ T S I at the final iteration T T T .
Proof of Selection Lower Bound
Lower bound
Recall γ = 1 3 − λ > 0 \gamma= \frac{1}{3} - \lambda> 0 γ = 3 1 − λ > 0 and m = ⌊ λ n ⌋ m = \lfloor\lambda n \rfloor m = ⌊ λn ⌋ . Throughout, “for large n n n ” means n ≥ n λ n \ge n_{\lambda} n ≥ n λ for a threshold depending only on λ \lambda λ .
The subpopulations of the construction are the edges of a cubic graph whose cycles are long, so that the neighborhood of every edge is a tree. The girth cannot be made arbitrarily large, since a cubic graph of girth L L L has at least 2 L / 2 2^{L/2} 2 L /2 vertices, but logarithmic girth suffices for our purposes. We use the classical fact that for every integer L ≥ 3 L \ge3 L ≥ 3 there is a simple cubic graph with girth at least L L L and fewer than 2 L + 1 2^{L+1} 2 L + 1 vertices, where the girth is the length of the shortest cycle. Rather than using a single graph of this kind, we take G G G to be a disjoint union of copies of a small one, which allows us to control the number of edges precisely; in particular, we make it a multiple of the group size
k g r o u p : = ⌊ 10 λ ⌋ , k_{\mathrm{group}} := \left\lfloor\frac{10}{\lambda} \right\rfloor, k group := ⌊ λ 10 ⌋ ,
whose value is justified below, when the groups are introduced. Let
L : = ⌊ log 2 n 3 k g r o u p ⌋ , L := \left\lfloor\log_2 \frac{\sqrt{n}}{3k_{\mathrm{group}}} \right\rfloor, L := ⌊ log 2 3 k group n ⌋ ,
which is at least 3 3 3 for large n n n , and let G 0 G_0 G 0 be a cubic graph with girth at least L L L and fewer than 2 L + 1 2^{L+1} 2 L + 1 vertices, hence fewer than 3 ⋅ 2 L ≤ n / k g r o u p 3 \cdot2^L \le\sqrt{n}/k_{\mathrm{group}} 3 ⋅ 2 L ≤ n / k group edges. We take G G G to be the disjoint union of ⌊ n / ( k g r o u p ∣ E ( G 0 ) ∣ ) ⌋ \left\lfloor n/(k_{\mathrm{group}}|E(G_0)|)\right\rfloor ⌊ n / ( k group ∣ E ( G 0 ) ∣ ) ⌋ copies of G 0 G_0 G 0 (Figure 3), and write N : = ∣ E ( G ) ∣ N := |E(G)| N := ∣ E ( G ) ∣ for its number of edges. Since L L L and k g r o u p k_{\mathrm{group}} k group depend only on ( λ , n ) (\lambda,n) ( λ , n ) , so does G G G ; in particular, G G G does not depend on v v v .
Figure 3. The graph G G G is a disjoint union of copies of a small cubic graph G 0 G_0 G 0 of large girth. The Petersen graph, which has girth 5, is shown for illustration; the actual G 0 G_0 G 0 has girth L ≈ 1 2 log 2 n L \approx\frac{1}{2}\log_2 n L ≈ 2 1 log 2 n . Taking a multiple of k g r o u p k_{\mathrm{group}} k group copies ensures k g r o u p ∣ N k_{\mathrm{group}} \mid N k group ∣ N and n − n < N ≤ n n-\sqrt{n}<N\le n n − n < N ≤ n .
Lemma B.1 (Properties of G G G ). For large $n:
(a) G G G is cubic: every vertex has exactly three incident edges. Hence ∣ V ( G ) ∣ = 2 N / 3 |V(G)| = 2N/3 ∣ V ( G ) ∣ = 2 N /3 .
(b) The girth of G G G is at least L L L , and L ≥ 1 2 log 2 n − log 2 ( 6 k g r o u p ) L \ge\frac{1}{2}\log_2 n-\log_2(6k_{\mathrm{group}}) L ≥ 2 1 log 2 n − log 2 ( 6 k group ) .
(c) n − n < N ≤ n n-\sqrt{n}<N\le n n − n < N ≤ n and k g r o u p ∣ N k_{\mathrm{group}}\mid N k group ∣ N . In particular, N ≥ n / 2 N\ge n/2 N ≥ n /2 .
(d) Every connected set of fewer than L L L edges of G G G forms a tree.
Proof. (a) Disjoint copies of a cubic graph form a cubic graph, and counting edge endpoints gives 3 ∣ V ( G ) ∣ = 2 N 3|V(G)| = 2N 3∣ V ( G ) ∣ = 2 N . (b) A cycle of G G G lies in a single copy of G 0 G_0 G 0 , so it has length at least L L L . The bound on L L L follows from ⌊ x ⌋ ≥ x − 1 \lfloor x\rfloor\ge x - 1 ⌊ x ⌋ ≥ x − 1 . (c) Write E 0 : = ∣ E ( G 0 ) ∣ E_0 := |E(G_0)| E 0 := ∣ E ( G 0 ) ∣ . Then N = k g r o u p ⌊ n / ( k g r o u p E 0 ) ⌋ E 0 N = k_{\mathrm{group}}\lfloor n/(k_{\mathrm{group}}E_0)\rfloor E_0 N = k group ⌊ n / ( k group E 0 )⌋ E 0 , which lies in ( n − k g r o u p E 0 , n ] (n - k_{\mathrm{group}}E_0,n] ( n − k group E 0 , n ] , and k g r o u p E 0 ≤ n k_{\mathrm{group}}E_0 \le\sqrt{n} k group E 0 ≤ n . The number of copies is a multiple of k g r o u p k_{\mathrm{group}} k group , so k g r o u p ∣ N k_{\mathrm{group}} \mid N k group ∣ N . (d) A connected set of edges that contains a cycle has at least as many edges as that cycle, so at least L L L edges by (b).
The lower bound uses only parts (a) and (c) of Theorem B.1; part (d), which is a consequence of the girth, is used in the upper bound in Section B.2.
We now define the labels and the active edges. We fix a partition of E ( G ) E(G) E ( G ) into J : = N / k g r o u p J := N/k_{\mathrm{group}} J := N / k group groups G 1 , … , G J \mathcal{G}_1,\ldots,\mathcal{G}_J G 1 , … , G J of k g r o u p k_{\mathrm{group}} k group edges each, writing G j = { e ( j , 1 ) , … , e ( j , k g r o u p ) } \mathcal{G}_j = \{e(j,1),\ldots,e(j,k_{\mathrm{group}})\} G j = { e ( j , 1 ) , … , e ( j , k group )} ; like G G G , the partition depends only on ( λ , n ) (\lambda,n) ( λ , n ) and is known to the learner. Each distribution in the family is indexed by a pair ( Θ , h ) (\Theta,h) ( Θ , h ) . The first component, Θ = ( Θ e ) e ∈ E ( G ) \Theta= (\Theta_e)_{e\in E(G)} Θ = ( Θ e ) e ∈ E ( G ) , assigns to each edge e e e a label Θ e ∈ F 2 B \Theta_e \in\mathbb{F}_2^B Θ e ∈ F 2 B , subject to the parity constraints
Θ e 1 + Θ e 2 + Θ e 3 = 0 at every vertex, where e 1 , e 2 , e 3 are its three edges (10) \Theta_{e_1}+\Theta_{e_2}+\Theta_{e_3}=0 \quad\text{at every vertex, where } e_1,e_2,e_3 \text{ are its three edges} \tag*{(10)} Θ e 1 + Θ e 2 + Θ e 3 = 0 at every vertex, where e 1 , e 2 , e 3 are its three edges (10)
(Figure 4 , left). We identify the label set [ n c l a s s ] [n_{\mathrm{class}}] [ n class ] with F 2 B \mathbb{F}_2^B F 2 B , so that there are n c l a s s : = 2 B n_{\mathrm{class}} := 2^B n class := 2 B classes and an incorrect B B B -bit string counts as a single mistake. The label length B B B governs the comparison, made in the lower bound, between the number of bits carried by the selected sample and the number of bits needed to describe the labels. Besides m B mB m B bits of labels, the selected sample conveys up to n n n bits through the choice of the index set, and the argument spends up to n n n further bits on locating the mistakes of the learner. These overheads do not grow with B B B , whereas the entropy of the labels grows linearly in B B B , so they become negligible when B B B is large compared with 1 / γ 1/\gamma 1/ γ . At the same time, B B B must not depend on n n n , so that the number of classes n c l a s s = 2 B n_{\mathrm{class}} = 2^B n class = 2 B depends only on λ \lambda λ . We take
Figure 4. Left: the parity constraint equation (10) at one vertex; over F 2 \mathbb{F}_2 F 2 , any two labels at a vertex determine the third. Right: in a graph of girth at least L L L , the ball of radius less than L / 2 L/2 L /2 around any vertex is a tree. Edges missing from S S S (red, dashed) form components surrounded by observed edges (green), and by Theorem B.1(d), components with fewer than L L L edges are trees.
B : = ⌈ 8 γ ⌉ . B := \left\lceil\frac{8}{\gamma} \right\rceil. B := ⌈ γ 8 ⌉ .
The second component, h = ( h 1 , … , h J ) ∈ [ k g r o u p ] J h = (h_1,\ldots,h_J) \in[k_{\mathrm{group}}]^J h = ( h 1 , … , h J ) ∈ [ k group ] J , selects one active edge e ( j , h j ) e(j,h_j) e ( j , h j ) in each group; the risk will be incurred only on active edges, so that an oracle that knows h h h needs information about a single edge per group. Choosing k g r o u p = ⌈ 10 / λ ⌉ k_{\mathrm{group}} = \lceil10/\lambda\rceil k group = ⌈ 10/ λ ⌉ ensures that the J = N / k g r o u p J = N/k_{\mathrm{group}} J = N / k group active edges require at most 3 λ n < m \frac{3}{\lambda}n < m λ 3 n < m certificate examples in expectation (Theorem B.8), while losing only a factor of 1 / k g r o u p = Θ ( λ ) 1/k_{\mathrm{group}} = \Theta(\lambda) 1/ k group = Θ ( λ ) when converting prediction errors across a group into test risk. Throughout, the edge e e e plays the role of a subpopulation identity, which is part of every input, whereas its label Θ e \Theta_e Θ e is unknown.
We next describe the distribution P Θ , h P_{\Theta,h} P Θ , h of a single example. An input is a pair ( e , z ) (e,z) ( e , z ) with e ∈ E ( G ) e \in E(G) e ∈ E ( G ) and z ∈ F 2 B ∪ { ⊥ } z \in\mathbb{F}_2^B \cup\{\perp\} z ∈ F 2 B ∪ { ⊥ } . Given the masking probability p m a s k e d ∈ ( 0 , 1 ) p_{\mathrm{masked}} \in(0,1) p masked ∈ ( 0 , 1 ) , specified below, an example Z = ( X , Y ) ∼ P Θ , h Z=(X,Y)\sim P_{\Theta,h} Z = ( X , Y ) ∼ P Θ , h is drawn as
Z = ( X , Y ) = { ( ( e , Θ e ) , Θ e ) , e ∼ Unif ( E ( G ) ) , w.p. 1 − p m a s k e d (clear) , ( ( e ( j , h j ) , ⊥ ) , Θ e ( j , h j ) ) , j ∼ Unif ( [ J ] ) , w.p. p m a s k e d (masked) . Z=(X,Y)=
\begin{cases}
((e,\Theta_e),\Theta_e), & e\sim\operatorname{Unif}(E(G)),\quad\text{w.p. }1-p_{\mathrm{masked}}\quad\text{(clear)},\\
((e(j,h_j),\perp),\Theta_{e(j,h_j)}), & j\sim\operatorname{Unif}([J]),\quad\text{w.p. }p_{\mathrm{masked}}\quad\text{(masked)}.
\end{cases} Z = ( X , Y ) = { (( e , Θ e ) , Θ e ) , (( e ( j , h j ) , ⊥ ) , Θ e ( j , h j ) ) , e ∼ Unif ( E ( G )) , w.p. 1 − p masked (clear) , j ∼ Unif ([ J ]) , w.p. p masked (masked) .
Since the input of a clear example contains its label, a learner can predict correctly on clear inputs by copying z z z , and the risk is therefore determined by the masked inputs, which present an active edge with ⊥ \perp ⊥ in place of its label. The two kinds of examples play different roles in ( S , V ) (S,V) ( S , V ) . Clear examples fall on uniformly random edges, independently of h h h , and thus reveal labels but carry no information about the active edges. A masked example, in contrast, reveals the active edge of its group, since only active edges are masked. As explained above, p m a s k e d p_{\mathrm{masked}} p masked should be large, because it multiplies the risk, but small enough that most groups receive no masked example in ( S , V ) (S,V) ( S , V ) . We take
p m a s k e d : = γ 8 k g r o u p ⋅ n n + ν . p_{\mathrm{masked}} := \frac{\gamma}{8k_{\mathrm{group}}}\cdot\frac{n}{n+\nu}. p masked := 8 k group γ ⋅ n + ν n .
so that the expected number of masked examples in ( S , V ) (S,V) ( S , V ) is ( n + v ) p m a s k e d = γ n / ( 8 k g r o u p ) (n+v)p_{\mathrm{masked}}=\gamma n/(8k_{\mathrm{group}}) ( n + v ) p masked = γ n / ( 8 k group ) , which is at most a γ / 4 \gamma/4 γ /4 fraction of the J ≥ n / ( 2 k g r o u p ) J\ge n/(2k_{\mathrm{group}}) J ≥ n / ( 2 k group ) groups, irrespective of the validation size v v v . Since k g r o u p ≥ 31 k_{\mathrm{group}}\ge31 k group ≥ 31 and γ < 1 3 \gamma<\frac{1}{3} γ < 3 1 , we also have
p m a s k e d ≤ γ 8 k g r o u p < 1 720 . (11) p_{\mathrm{masked}}\le\frac{\gamma}{8k_{\mathrm{group}}}<\frac{1}{720}. \tag*{(11)} p masked ≤ 8 k group γ < 720 1 . (11)
Training, validation and test examples are i.i.d. from P Θ , h P_{\Theta,h} P Θ , h , and the family P λ , n , v \mathcal{P}_{\lambda,n,v} P λ , n , v consists of all such P Θ , h P_{\Theta,h} P Θ , h . It is finite, its number of classes n c l a s s n_{\mathrm{class}} n class depends only on λ \lambda λ , and R P ⋆ = 0 R^{\star}_{P}=0 R P ⋆ = 0 because the label is a function of the input.
For the lower bound, we place a prior on the family, the meta-distribution , under which ( Θ , h ) (\Theta,h) ( Θ , h ) is uniform over all valid pairs. To describe it, note that for a fixed bit position k k k , the bit-plane ( Θ e [ k ] ) e ∈ E ( G ) (\Theta_{e}[k])_{e\in E(G)} ( Θ e [ k ] ) e ∈ E ( G ) satisfies equation (10) exactly when it lies in the cycle space
C ( G ) : = { x ∈ F 2 E ( G ) : x e 1 + x e 2 + x e 3 = 0 at every vertex } . \mathcal{C}(G):=\left\{x\in\mathbb{F}_{2}^{E(G)}:x_{e_1}+x_{e_2}+x_{e_3}=0\text{ at every vertex}\right\}. C ( G ) := { x ∈ F 2 E ( G ) : x e 1 + x e 2 + x e 3 = 0 at every vertex } .
This is the solution set of ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ homogeneous linear equations in N N N unknowns, so dim C ( G ) ≥ N − ∣ V ( G ) ∣ = N / 3 \dim\mathcal{C}(G)\ge N-|V(G)|=N/3 dim C ( G ) ≥ N − ∣ V ( G ) ∣ = N /3 by Theorem B.1(a). Under the meta-distribution, Θ \Theta Θ and h h h are independent, h h h is uniform on [ k g r o u p ] [k_{\mathrm{group}}] [ k group ] , and the B B B bit-planes of Θ \Theta Θ are i.i.d. uniform on C ( G ) \mathcal{C}(G) C ( G ) . Although the parity constraints make the labels dependent, Θ \Theta Θ is uniform over ∣ C ( G ) ∣ B = 2 B dim C ( G ) |\mathcal{C}(G)|^B=2^{B\dim\mathcal{C}(G)} ∣ C ( G ) ∣ B = 2 B d i m C ( G ) values, and hence
H ( Θ ) = B ⋅ dim C ( G ) ≥ N B 3 (in bits) . (12) H(\Theta)=B\cdot\dim\mathcal{C}(G)\ge\frac{NB}{3}\quad\text{(in bits)}. \tag*{(12)} H ( Θ ) = B ⋅ dim C ( G ) ≥ 3 N B (in bits) . (12)
Since the family is finite, it suffices to show that the risk averaged over this prior is large.
Main argument
Fix a learner A m \mathcal{A}_m A m and a selector Π \Pi Π . Draw ( Θ , h ) (\Theta,h) ( Θ , h ) from the meta-distribution, then S ∼ P Θ , h n S\sim P_{\Theta,h}^{n} S ∼ P Θ , h n and V ∼ P Θ , h v V\sim P_{\Theta,h}^{v} V ∼ P Θ , h v , with independent internal randomness for Π \Pi Π and A m \mathcal{A}_m A m , and let f ^ : = A m ( S I ^ m ) \hat{f}:=\mathcal{A}_m(S_{\hat{I}_m}) f ^ := A m ( S I ^ m ) . In this subsection, P \mathbb{P} P , E \mathbb{E} E , H H H and I I I refer to all of this randomness, and our goal is
E [ R P Θ , h ( f ^ ) ] ≥ λ γ 2 264 ⋅ n n + v . (13) \mathbb{E}\left[R_{P_{\Theta,h}}(\hat{f})\right]\ge\frac{\lambda\gamma^{2}}{264}\cdot\frac{n}{n+v}. \tag*{(13)} E [ R P Θ , h ( f ^ ) ] ≥ 264 λ γ 2 ⋅ n + v n . (13)
The argument conditions on everything except the labels. Let W W W consist of the edges e 1 , … , e n + v e_1,\ldots,e_{n+v} e 1 , … , e n + v of all examples in ( S , V ) (S,V) ( S , V ) , the indicators of which of these examples are masked, and the internal randomness of Π \Pi Π and A m \mathcal{A}_m A m . We emphasize that W W W excludes the inputs themselves, since the input of a clear example contains its label.
Lemma B.2 (Properties of W W W ).
(i) W W W is independent of Θ \Theta Θ (but not of h h h ).
(ii) ( S , V ) (S,V) ( S , V ) , I ^ m \widehat{I}_m I m and f ^ \hat{f} f ^ are functions of ( W , Θ ) (W,\Theta) ( W , Θ ) .
(iii) Let M : = ( I ^ m , ( Y i ) i ∈ I ^ m ) M := (\widehat{I}_m,(Y_i)_{i\in\widehat{I}_m}) M := ( I m , ( Y i ) i ∈ I m ) . Given W W W , the selected sample S I ^ m S_{\widehat{I}_m} S I m is a function of M M M ; hence f ^ \hat{f} f ^ is a function of ( W , M ) (W,M) ( W , M ) .
Proof. (i) The edges and the mask indicators are drawn independently of Θ \Theta Θ ; the masked edges depend on h h h . (ii) Given W W W , example i i i equals ( ( e i , Θ e i ) , Θ e i ) ((e_i,\Theta_{e_i}),\Theta_{e_i}) (( e i , Θ e i ) , Θ e i ) if it is clear and ( ( e i , ⊥ ) , Θ e i ) ((e_i,\perp),\Theta_{e_i}) (( e i , ⊥ ) , Θ e i ) if it is masked, and the selector and the learner are deterministic given their internal randomness, which is part of W W W . (iii) For i ∈ I ^ m i\in\widehat{I}_m i ∈ I m , W W W provides e i e_i e i and the mask indicator, so Z i Z_i Z i is recovered from ( i , Y i ) (i,Y_i) ( i , Y i ) : X i = ( e i , Y i ) X_i=(e_i,Y_i) X i = ( e i , Y i ) if example i i i is clear and X i = ( e i , ⊥ ) X_i=(e_i,\perp) X i = ( e i , ⊥ ) if it is masked.
A masked example in ( S , V ) (S,V) ( S , V ) reveals the active edge of its group, so the selector can be uncertain about h j h_j h j only if no masked example from G j \mathcal{G}_j G j occurs. We call a group G j \mathcal{G}_j G j resolved if some example in ( S , V ) (S,V) ( S , V ) is a masked example from G j \mathcal{G}_j G j , and unresolved otherwise. Let U ⊆ [ J ] U\subseteq[J] U ⊆ [ J ] be the set of unresolved groups and E U : = ⋃ j ∈ U G j E_U:=\bigcup_{j\in U}\mathcal{G}_j E U := ⋃ j ∈ U G j ; both are functions of W W W . We count the mistakes of f ^ \hat{f} f ^ on all edges of unresolved groups,
Q : = { e ∈ E U : f ^ ( e , ⊥ ) ≠ Θ e } . Q:=\{e\in E_U:\hat{f}(e,\perp)\ne\Theta_e\}. Q := { e ∈ E U : f ^ ( e , ⊥ ) = Θ e } .
The edges of resolved groups are excluded from this count, and the choice of p m a s k e d p_{\mathrm{masked}} p masked ensures that they form a small fraction of all edges, namely at most
p r e s o l v e d : = γ 4 p_{\mathrm{resolved}}:=\frac{\gamma}{4} p resolved := 4 γ
in expectation, a quarter of the gap γ \gamma γ .
Lemma B.3 (Few groups are resolved). For large n n n and every j j j , P ( j ∉ U ) ≤ p r e s o l v e d \mathbb{P}(j\notin U)\le p_{\mathrm{resolved}} P ( j ∈ / U ) ≤ p resolved . Hence E ∣ E ( G ) ∖ E U ∣ ≤ p r e s o l v e d N \mathbb{E}|E(G)\setminus E_U|\le p_{\mathrm{resolved}}N E ∣ E ( G ) ∖ E U ∣ ≤ p resolved N .
Proof. A single example is a masked example from G j \mathcal{G}_j G j with probability p m a s k e d / J p_{\mathrm{masked}}/J p masked / J . A union bound over the n + v n+v n + v examples, together with ( n + v ) p m a s k e d = γ n / ( 8 k g r o u p ) (n+v)p_{\mathrm{masked}}=\gamma n/(8k_{\mathrm{group}}) ( n + v ) p masked = γ n / ( 8 k group ) , J = N / k g r o u p J=N/k_{\mathrm{group}} J = N / k group and N ≥ n / 2 N\ge n/2 N ≥ n /2 , gives
P ( j ∉ U ) ≤ ( n + v ) p m a s k e d J = γ 8 ⋅ n N ≤ γ 4 = p r e s o l v e d . \mathbb{P}(j\notin U)\le(n+v)\frac{p_{\mathrm{masked}}}{J}=\frac{\gamma}{8}\cdot\frac{n}{N}\le\frac{\gamma}{4}=p_{\mathrm{resolved}}. P ( j ∈ / U ) ≤ ( n + v ) J p masked = 8 γ ⋅ N n ≤ 4 γ = p resolved .
Finally, E ∣ E ( G ) ∖ E U ∣ = k g r o u p ∑ j P ( j ∉ U ) ≤ k g r o u p J p r e s o l v e d = p r e s o l v e d N \mathbb{E}|E(G)\setminus E_U|=k_{\mathrm{group}}\sum_j\mathbb{P}(j\notin U)\le k_{\mathrm{group}}Jp_{\mathrm{resolved}}=p_{\mathrm{resolved}}N E ∣ E ( G ) ∖ E U ∣ = k group ∑ j P ( j ∈ / U ) ≤ k group J p resolved = p resolved N .
Although the risk involves only the active edge of each group, every mistake counted by Q Q Q contributes to it, because the active edge of an unresolved group is uniformly distributed given everything on which f ^ \hat{f} f ^ depends.
Lemma B.4 (Risk lemma). E [ R P Θ , h ( f ^ ) ] ≥ p m a s k e d n E [ Q ] \mathbb{E}[R_{P_{\Theta,h}}(\hat{f})]\ge\frac{p_{\mathrm{masked}}}{n}\mathbb{E}[Q] E [ R P Θ , h ( f ^ )] ≥ n p masked E [ Q ] .
Proof. We first show that h j h_j h j is uniform on [ k g r o u p ] [k_{\mathrm{group}}] [ k group ] given ( W , Θ ) (W,\Theta) ( W , Θ ) for every j ∈ U j \in U j ∈ U . Given ( Θ , h ) (\Theta,h) ( Θ , h ) , the law of W W W does not depend on Θ \Theta Θ , and it depends on h j h_j h j only through the masked examples from G j G_j G j , of which there are none if j ∈ U j \in U j ∈ U . Since h h h is uniform and independent of Θ \Theta Θ , the claim follows from Bayes’ rule, while f ^ \hat{f} f ^ is determined by ( W , Θ ) (W,\Theta) ( W , Θ ) by Theorem B.2(ii).
Restricting the risk to the masked inputs of unresolved groups, each of which has probability p m a s k e d / J p_{\mathrm{masked}}/J p masked / J , gives
R P Θ , h ( f ^ ) ≥ ∑ j ∈ U p m a s k e d J 1 { f ^ ( e ( j , h j ) , ⊥ ) ≠ Θ e ( j , h j ) } . R_{P_{\Theta,h}}(\hat{f}) \ge\sum_{j\in U} \frac{p_{\mathrm{masked}}}{J} \mathbb{1}\{\hat{f}(e(j,h_j),\perp) \ne\Theta_{e(j,h_j)}\}. R P Θ , h ( f ^ ) ≥ j ∈ U ∑ J p masked 1 { f ^ ( e ( j , h j ) , ⊥ ) = Θ e ( j , h j ) } .
Averaging over the uniform h j h_j h j , conditionally on ( W , Θ ) (W,\Theta) ( W , Θ ) , turns the j j j -th term into
p m a s k e d J k g r o u p ∑ ℓ = 1 k g r o u p 1 { f ^ ( e ( j , ℓ ) , ⊥ ) ≠ Θ e ( j , ℓ ) } . \frac{p_{\mathrm{masked}}}{Jk_{\mathrm{group}}} \sum_{\ell=1}^{k_{\mathrm{group}}} \mathbb{1}\{\hat{f}(e(j,\ell),\perp) \ne\Theta_{e(j,\ell)}\}. J k group p masked ℓ = 1 ∑ k group 1 { f ^ ( e ( j , ℓ ) , ⊥ ) = Θ e ( j , ℓ ) } .
Summing over j ∈ U j \in U j ∈ U and using J k g r o u p = N ≤ n Jk_{\mathrm{group}} = N \le n J k group = N ≤ n ,
E [ R P Θ , h ( f ^ ) ∣ W , Θ ] ≥ p m a s k e d N Q ≥ p m a s k e d n Q . \mathbb{E}[R_{P_{\Theta,h}}(\hat{f}) \mid W,\Theta] \ge\frac{p_{\mathrm{masked}}}{N}Q \ge\frac{p_{\mathrm{masked}}}{n}Q. E [ R P Θ , h ( f ^ ) ∣ W , Θ ] ≥ N p masked Q ≥ n p masked Q .
and taking expectations proves the lemma.
It remains to show that E [ Q ] \mathbb{E}[Q] E [ Q ] is of order γ n \gamma n γ n , and it is at this step that the restriction to m m m selected examples enters. By Theorem B.2, conditionally on W W W we have the Markov chain
Θ ⟶ ( S , V ) ⟶ M = ( I ^ m , ( Y i ) i ∈ I ^ m ) ⟶ f ^ , (14) \Theta\longrightarrow(S,V) \longrightarrow M = (\hat{I}_m,(Y_i)_{i\in\hat{I}_m}) \longrightarrow\hat{f}, \tag*{(14)} Θ ⟶ ( S , V ) ⟶ M = ( I ^ m , ( Y i ) i ∈ I ^ m ) ⟶ f ^ , (14)
in which ( S , V ) (S,V) ( S , V ) is a function of Θ \Theta Θ , M M M is computed from ( S , V ) (S,V) ( S , V ) by the selector, and f ^ = F ( W , M ) \hat{f} = F(W,M) f ^ = F ( W , M ) for a fixed function F F F . Although the selector may use every label in ( S , V ) (S,V) ( S , V ) , the learner has access to these labels only through M M M , and the next lemma quantifies the resulting loss.
Lemma B.5 (Bits lemma). For n ≥ n λ n \ge n_\lambda n ≥ n λ , it holds that E [ Q ] ≥ ( 1 3 − p r e s o l v e d ) N − m − 2 n B \mathbb{E}[Q] \ge\left(\frac{1}{3} - p_{\mathrm{resolved}}\right)N - m - \frac{2n}{B} E [ Q ] ≥ ( 3 1 − p resolved ) N − m − B 2 n .
Proof. Recall that M = ( I ^ m , ( Y i ) i ∈ I ^ m ) M = (\hat{I}_m,(Y_i)_{i\in\hat{I}_m}) M = ( I ^ m , ( Y i ) i ∈ I ^ m ) . The proof is based on comparing the conditional entropy H ( Θ ∣ W ) H(\Theta\mid W) H ( Θ ∣ W ) from above and below. Since I ^ m ⊆ [ n ] \hat{I}_m \subseteq[n] I ^ m ⊆ [ n ] takes at most 2 n 2^n 2 n values and, given I ^ m \hat{I}_m I ^ m , the labels ( Y i ) i ∈ I ^ m ∈ ( F 2 B ) ∣ I ^ m ∣ (Y_i)_{i\in\hat{I}_m} \in(\mathbb{F}_2^B)^{|\hat{I}_m|} ( Y i ) i ∈ I ^ m ∈ ( F 2 B ) ∣ I ^ m ∣ take at most 2 m B 2^{mB} 2 m B values, we have
H ( M ∣ W ) ≤ n + m B . (15) H(M \mid W) \le n + mB. \tag*{(15)} H ( M ∣ W ) ≤ n + m B . (15)
The contribution of I ^ m \hat{I}_m I ^ m cannot be omitted, since a selector that observes all labels can encode information about the unselected labels in its choice of indices; the choice of B B B makes it negligible compared with N B NB N B .
Next, we upper bound H ( Θ ∣ W , f ^ ) H(\Theta\mid W,\hat{f}) H ( Θ ∣ W , f ^ ) . Let χ ∈ { 0 , 1 } E ( G ) \chi\in\{0,1\}^{E(G)} χ ∈ { 0 , 1 } E ( G ) be the error indicator vector defined by χ e = 1 { e ∈ E U and f ^ ( e , ⊥ ) ≠ Θ e } \chi_e = \mathbb{1}\{e \in E_U \text{ and } \hat{f}(e,\perp) \ne\Theta_e\} χ e = 1 { e ∈ E U and f ^ ( e , ⊥ ) = Θ e } , so that ∥ χ ∥ 0 = Q \|\chi\|_0 = Q ∥ χ ∥ 0 = Q . Notice that, conditioned on ( W , f ^ , χ ) (W,\hat{f},\chi) ( W , f ^ , χ ) , the label Θ e \Theta_e Θ e is determined by f ^ ( e , ⊥ ) \hat{f}(e,\perp) f ^ ( e , ⊥ ) for every e ∈ E U e \in E_U e ∈ E U with χ e = 0 \chi_e = 0 χ e = 0 ; hence Θ \Theta Θ is uniquely determined by specifying the Q Q Q labels { Θ e : e ∈ E U , χ e = 1 } \{\Theta_e : e \in E_U,\ \chi_e = 1\} { Θ e : e ∈ E U , χ e = 1 } together with the ∣ E ( G ) ∖ E U ∣ |E(G) \setminus E_U| ∣ E ( G ) ∖ E U ∣ labels on the resolved groups, Θ E ( G ) ∖ E U \Theta_{E(G)\setminus E_U} Θ E ( G ) ∖ E U , where E U E_U E U is a function of W W W . Since χ \chi χ takes at most 2 N 2^N 2 N values and each label is a B B B -bit string, the chain rule of entropy gives
H ( Θ ∣ W , f ^ ) ≤ H ( χ ∣ W , f ^ ) + H ( Θ ∣ W , f ^ , χ ) ≤ N + B E [ Q ] + B E ∣ E ( G ) ∖ E U ∣ ≤ n + B E [ Q ] + p r e s o l v e d N B , (16) \begin{aligned}
H(\Theta\mid W,\hat{f}) &\le H(\chi\mid W,\hat{f}) + H(\Theta\mid W,\hat{f},\chi)\\
&\le N + B\mathbb{E}[Q] + B\mathbb{E}|E(G)\setminus E_U| \le n + B\mathbb{E}[Q] + p_{\mathrm{resolved}}NB, \tag*{(16)}
\end{aligned} H ( Θ ∣ W , f ^ ) ≤ H ( χ ∣ W , f ^ ) + H ( Θ ∣ W , f ^ , χ ) ≤ N + B E [ Q ] + B E ∣ E ( G ) ∖ E U ∣ ≤ n + B E [ Q ] + p resolved N B , (16)
where the last step uses Theorem B.3 and N ≤ n N \le n N ≤ n . Inequality equation (16) is a coordinatewise analogue of Fano’s inequality H ( Θ ∣ Θ ^ ) ≤ h ( P e ) + P e log ( ∣ X ∣ − 1 ) H(\Theta\mid\hat{\Theta}) \le h(P_e) + P_e \log(|\mathcal{X}| - 1) H ( Θ ∣ Θ ^ ) ≤ h ( P e ) + P e log ( ∣ X ∣ − 1 ) : the term N N N , which accounts for the error pattern, corresponds to h ( P e ) h(P_e) h ( P e ) , the term B E [ Q ] B\mathbb{E}[Q] B E [ Q ] corresponds to P e log ( ∣ X ∣ − 1 ) P_e \log(|\mathcal{X}| - 1) P e log ( ∣ X ∣ − 1 ) , and the term p r e s o l v e d N B p_{\mathrm{resolved}}NB p resolved N B accounts for the resolved groups, on which mistakes are not counted.
Finally, we compare the two bounds. Since Θ \Theta Θ is independent of W W W by Theorem B.2(i), equation (12) gives H ( Θ ∣ W ) = H ( Θ ) ≥ N B / 3 H(\Theta\mid W) = H(\Theta) \ge NB/3 H ( Θ ∣ W ) = H ( Θ ) ≥ N B /3 . Conversely, since f ^ \hat{f} f ^ is a deterministic function of ( W , M ) (W,M) ( W , M ) by Theorem B.2(iii), the chain rule and the fact that conditioning reduces entropy give
H ( Θ ∣ W ) ≤ H ( M ∣ W ) + H ( Θ ∣ W , f ^ ) . H(\Theta\mid W) \le H(M \mid W) + H(\Theta\mid W,\hat{f}). H ( Θ ∣ W ) ≤ H ( M ∣ W ) + H ( Θ ∣ W , f ^ ) .
Combining these two bounds with equation (15) and equation (16) , we obtain
N B 3 ≤ ( n + m B ) + ( n + B E [ Q ] + p r e s o l v e d N B ) , \frac{NB}{3} \le(n + mB) + (n + B\mathbb{E}[Q] + p_{\mathrm{resolved}}NB), 3 N B ≤ ( n + m B ) + ( n + B E [ Q ] + p resolved N B ) ,
and dividing by B B B proves the lemma. □
We can now complete the proof of the lower bound.
Proof of Theorem 2.1 Lower Bound. By Theorem B.1(c), N > n − n N > n - \sqrt{n} N > n − n . Moreover, m ≤ λ n m \le\lambda n m ≤ λn , p r e s o l v e d = γ / 4 p_{\mathrm{resolved}} = \gamma/4 p resolved = γ /4 , and 2 / B ≤ γ / 4 2/B \le\gamma/4 2/ B ≤ γ /4 since B ≥ 8 / γ B \ge8/\gamma B ≥ 8/ γ . Hence Theorem B.5 gives, for large n n n ,
E [ Q ] ≥ ( 1 3 − λ − p r e s o l v e d − 2 B ) n − n ≥ γ 2 n − n ≥ γ n 3 . \begin{aligned}
\mathbb{E}[Q] \ge\left(\frac{1}{3} - \lambda- p_{\mathrm{resolved}} - \frac{2}{B}\right)n - \sqrt{n} \\
&\ge\frac{\gamma}{2}n - \sqrt{n} \\
&\ge\frac{\gamma n}{3}.
\end{aligned} E [ Q ] ≥ ( 3 1 − λ − p resolved − B 2 ) n − n ≥ 2 γ n − n ≥ 3 γ n .
By Theorem B.4 and k g r o u p ≤ 10 / λ + 1 ≤ 11 / λ k_{\mathrm{group}} \le10/\lambda+ 1 \le11/\lambda k group ≤ 10/ λ + 1 ≤ 11/ λ ,
E [ R P Θ , h ( f ^ ) ] ≥ p m a s k e d n ⋅ γ n 3 = γ 2 24 k g r o u p ⋅ n n + v ≥ λ γ 2 264 ⋅ n n + v , \mathbb{E}\left[R_{P_{\Theta,h}}(\hat{f})\right] \ge\frac{p_{\mathrm{masked}}}{n} \cdot\frac{\gamma n}{3} = \frac{\gamma^2}{24k_{\mathrm{group}}} \cdot\frac{n}{n+v} \ge\frac{\lambda\gamma^2}{264} \cdot\frac{n}{n+v}, E [ R P Θ , h ( f ^ ) ] ≥ n p masked ⋅ 3 γ n = 24 k group γ 2 ⋅ n + v n ≥ 264 λ γ 2 ⋅ n + v n ,
which is equation (13) . The left-hand side is the average over the meta-distribution of E S , V , Π , A m [ R P ( f ^ ) ] \mathbb{E}_{S,V,\Pi,\mathcal{A}_m}[R_P(\hat{f})] E S , V , Π , A m [ R P ( f ^ )] with P = P Θ , h P = P_{\Theta,h} P = P Θ , h , so some P ∈ P λ , n , v P \in\mathcal{P}_{\lambda,n,v} P ∈ P λ , n , v satisfies the bound. This P P P may depend on ( A m , Π ) (\mathcal{A}_m,\Pi) ( A m , Π ) , whereas the family does not. □
Upper bound
We now fix an arbitrary member P = P Θ , h P = P_{\Theta,h} P = P Θ , h of P λ , n , v \mathcal{P}_{\lambda,n,v} P λ , n , v . Probabilities in this subsection are over S ∼ P n S \sim P^n S ∼ P n only, and all bounds are uniform over the family.
The learner A ∗ \mathcal{A}^* A ∗ knows the graph G G G and the label length B B B , which depend only on ( λ , n ) (\lambda,n) ( λ , n ) , but not ( Θ , h ) (\Theta,h) ( Θ , h ) . Given a training sample, it discards the masked examples and forms a linear system over F 2 \mathbb{F}_2 F 2 in the unknowns Θ \Theta Θ , consisting of
Θ e 1 + Θ e 2 + Θ e 3 = 0 at every vertex \Theta_{e_1} + \Theta_{e_2} + \Theta_{e_3} = 0 \quad\text{at every vertex} Θ e 1 + Θ e 2 + Θ e 3 = 0 at every vertex
parity equation 10
and
Θ e = z for each clear ( e , z ) in the sample . \Theta_e = z \quad\text{for each clear } (e,z) \text{ in the sample}. Θ e = z for each clear ( e , z ) in the sample .
observations
It computes one solution by Gaussian elimination with a fixed pivoting rule, setting free variables to zero (if there is no solution, it takes Θ = 0 \Theta= 0 Θ = 0 ). On a clear input ( e , z ) (e,z) ( e , z ) it outputs z z z , and on a masked input ( e , ⊥ ) (e,\perp) ( e , ⊥ ) it outputs the value of Θ e \Theta_e Θ e in the computed solution. The analysis of A ∗ \mathcal{A}^* A ∗ rests on the following two observations.
Lemma B.6 (Two basic facts).
(i) For every I ⊆ [ n ] I \subseteq[n] I ⊆ [ n ] , R P ( A ∗ ( S I ) ) ≤ p m a s k e d R_P(\mathcal{A}^*(S_I)) \le p_{\mathrm{masked}} R P ( A ∗ ( S I )) ≤ p masked .
(ii) Say that S I S_I S I determines Θ e \Theta_e Θ e if all solutions of its linear system agree on Θ e \Theta_e Θ e . If S I S_I S I determines Θ e \Theta_e Θ e , then A ∗ ( S I ) \mathcal{A}^*(S_I) A ∗ ( S I ) is correct on ( e , ⊥ ) (e,\perp) ( e , ⊥ ) , and so is A ∗ ( S I ′ ) \mathcal{A}^*(S_{I'}) A ∗ ( S I ′ ) for every I ′ ⊇ I I' \supseteq I I ′ ⊇ I .
Proof. (i) A ∗ \mathcal{A}^* A ∗ copies the displayed label, so it is correct on every clear input, and masked inputs have total probability p m a s k e d p_{\mathrm{masked}} p masked . (ii) The true Θ \Theta Θ satisfies every equation obtained from S S S , so it is one of the solutions, and all solutions agree on Θ e \Theta_e Θ e . A larger subsample only adds equations that the true Θ \Theta Θ satisfies, which cannot enlarge the solution set.
By Theorem B.6, both upper bounds reduce to exhibiting, for each active edge, a small set of examples that determines its label. For an edge that appears in S S S , a single example suffices, and the other edges require the parity constraints. We call an edge observed if S S S contains a clear example of it, and missing otherwise. For a missing edge e e e , let T e T_e T e be the connected component containing e e e in the subgraph of missing edges, with ∣ T e ∣ |T_e| ∣ T e ∣ edges (and T e : = ∅ T_e := \emptyset T e := ∅ for an observed edge), and let ∂ T e \partial T_e ∂ T e be the set of edges outside T e T_e T e that share a vertex with T e T_e T e . The boundary edges are all observed, since a missing edge sharing a vertex with T e T_e T e would belong to T e T_e T e .
We truncate at component size
s : = ⌊ L / 2 ⌋ , s := \left\lfloor L/2 \right\rfloor, s := ⌊ L /2 ⌋ ,
so that 1 8 log 2 n ≤ s ≤ log 2 n \frac{1}{8}\log_2 n \le s \le\log_2 n 8 1 log 2 n ≤ s ≤ log 2 n for large n n n by Theorem B.1(b). Since s < L s < L s < L , Theorem B.1(d) shows that every component with at most s s s edges is a tree; meanwhile, s s s is large enough that larger components occur with probability O ( 1 / log n ) O(1/\log n) O ( 1/ log n ) (Theorem B.7(iii)), yet small enough (s ≪ n s \ll\sqrt{n} s ≪ n ) to control the variance of the oracle’s budget (Theorem B.8).
The certificate of an edge e e e is the set I e ⊆ [ n ] I_e \subseteq[n] I e ⊆ [ n ] consisting of the smallest index of a clear example of e e e if e e e is observed; of the smallest index of a clear example of each edge of ∂ T e \partial T_e ∂ T e if e e e is missing and ∣ T e ∣ ≤ s |T_e| \le s ∣ T e ∣ ≤ s ; and I e : = ∅ I_e := \emptyset I e := ∅ if e e e is missing and ∣ T e ∣ > s |T_e| > s ∣ T e ∣ > s , in which case we say that the certificate fails . The use of smallest indices makes I e I_e I e a canonical subset of [ n ] [n] [ n ] determined by S S S , which the oracle retains in the proof of Theorem 2.1 ; Theorem B.8 does not depend on this choice, since it involves only the set of observed edges.
Lemma B.7 (Certificates). For every edge e e e and every P ∈ P λ , n , v P \in\mathcal{P}_{\lambda,n,v} P ∈ P λ , n , v :
(i) If the certificate of e e e does not fail, then every subsample of S S S containing S I e S_{I_e} S I e determines Θ e \Theta_e Θ e .
(ii) ∣ I e ∣ ≤ ∣ T e ∣ + 3 |I_e| \leq|T_e| + 3 ∣ I e ∣ ≤ ∣ T e ∣ + 3 , ∣ I e ∣ ≤ s + 3 |I_e| \leq s + 3 ∣ I e ∣ ≤ s + 3 , and E ∣ I e ∣ ≤ 6 \mathbb{E}|I_e| \leq6 E ∣ I e ∣ ≤ 6 .
(iii) The certificate of e e e fails with probability at most 3 / s 3/s 3/ s .
Proof. (i) If e e e is observed, the subsample contains the equation Θ e = z \Theta_e = z Θ e = z . Otherwise T e T_e T e is a tree, and removing e e e splits it into two trees (Figure 5 ). Let V 1 V_1 V 1 be the vertex set of one of them (possibly a single vertex), and add up the parity equations at the vertices of V 1 V_1 V 1 . Every edge with both endpoints in V 1 V_1 V 1 appears twice and cancels, so the labels of the edges with exactly one endpoint in V 1 V_1 V 1 sum to zero. One of these edges is e e e ; every other edge of T e T_e T e has either both or no endpoints in V 1 V_1 V 1 , so the remaining edges in the sum lie in ∂ T e \partial T_e ∂ T e , and the subsample contains a clear example of each of them. Hence
Figure 5. A missing edge e e e (red) in a component T e T_e T e of missing edges (dashed), surrounded by the observed boundary edges ∂ T e \partial T_e ∂ T e (green). Removing e e e splits the tree into two parts; summing the parity equations over the vertex set V 1 V_1 V 1 of one part cancels every edge inside V 1 V_1 V 1 and expresses Θ e \Theta_e Θ e as the sum of the labels of the boundary edges leaving V 1 V_1 V 1 .
Θ e = ∑ f ∈ ∂ T e : ∣ f ∩ V 1 ∣ = 1 Θ f \Theta_e = \sum_{\substack{f \in\partial T_e:\\ |f \cap V_1|=1}} \Theta_f Θ e = f ∈ ∂ T e : ∣ f ∩ V 1 ∣ = 1 ∑ Θ f
is determined.
For (ii) and (iii), we first bound the probability that given edges are missing. A training example is a clear example of a fixed edge with probability ( 1 − p m a s k e d ) / N (1-p_{\mathrm{masked}})/N ( 1 − p masked ) / N . Since N ≤ n N \leq n N ≤ n (Theorem B.1(c)) and p m a s k e d < 1 / 720 p_{\mathrm{masked}} < 1/720 p masked < 1/720 by equation 11, for any k k k distinct edges,
P ( all k edges are missing ) = ( 1 − k ( 1 − p m a s k e d ) N ) n ≤ e − k ( 1 − p m a s k e d ) ≤ ( 3 8 ) k (17) \mathbb{P}(\text{all } k \text{ edges are missing}) = \left(1-\frac{k(1-p_{\mathrm{masked}})}{N}\right)^n \leq e^{-k(1-p_{\mathrm{masked}})} \leq\left(\frac{3}{8}\right)^k \tag*{(17)} P ( all k edges are missing ) = ( 1 − N k ( 1 − p masked ) ) n ≤ e − k ( 1 − p masked ) ≤ ( 8 3 ) k (17)
because e − 719 / 720 ≈ 0.3684 < 3 8 e^{-719/720} \approx0.3684 < \frac{3}{8} e − 719/720 ≈ 0.3684 < 8 3 . Next, every edge of T e T_e T e is the last edge of a simple path in G G G that starts with e e e and consists of missing edges: take a shortest chain of edges of T e T_e T e from e e e to it in which consecutive edges share a vertex; by minimality, non-consecutive edges of the chain share no vertex, so the chain is a simple path. Since G G G is cubic, for every ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 at most $2^\ell$ simple paths with ℓ \ell ℓ edges start with $e ({xref}Figure 6). Applying equation {xref}17` to the ℓ \ell ℓ edges of each path gives
E ∣ T e ∣ ≤ ∑ ℓ ≥ 1 2 ℓ ( 3 8 ) ℓ = ∑ ℓ ≥ 1 ( 3 4 ) ℓ = 3. (18) \mathbb{E}|T_e| \leq\sum_{\ell\geq1} 2^\ell\left(\frac{3}{8}\right)^\ell= \sum_{\ell\geq1} \left(\frac{3}{4}\right)^\ell= 3. \tag*{(18)} E ∣ T e ∣ ≤ ℓ ≥ 1 ∑ 2 ℓ ( 8 3 ) ℓ = ℓ ≥ 1 ∑ ( 4 3 ) ℓ = 3. (18)
(ii) If e e e is missing and ∣ T e ∣ ≤ s |T_e| \leq s ∣ T e ∣ ≤ s , then T e T_e T e is a tree with ∣ T e ∣ + 1 |T_e|+1 ∣ T e ∣ + 1 vertices, each of degree three in G G G , and its edges use 2 ∣ T e ∣ 2|T_e| 2∣ T e ∣ of the 3 ( ∣ T e ∣ + 1 ) 3(|T_e|+1) 3 ( ∣ T e ∣ + 1 ) edge–vertex incidences at these vertices. Hence ∣ I e ∣ = ∣ ∂ T e ∣ ≤ ∣ T e ∣ + 3 ≤ s + 3 |I_e| = |\partial T_e| \leq|T_e| + 3 \leq s + 3 ∣ I e ∣ = ∣ ∂ T e ∣ ≤ ∣ T e ∣ + 3 ≤ s + 3 . If e e e is observed, then ∣ I e ∣ = 1 |I_e| = 1 ∣ I e ∣ = 1 and ∣ T e ∣ = 0 |T_e| = 0 ∣ T e ∣ = 0 ; if the certificate fails, then ∣ I e ∣ = 0 |I_e| = 0 ∣ I e ∣ = 0 . Thus ∣ I e ∣ ≤ ∣ T e ∣ + 3 |I_e| \leq|T_e| + 3 ∣ I e ∣ ≤ ∣ T e ∣ + 3 and ∣ I e ∣ ≤ s + 3 |I_e| \leq s + 3 ∣ I e ∣ ≤ s + 3 in every case, and by equation 18, E ∣ I e ∣ ≤ E ∣ T e ∣ + 3 ≤ 6 \mathbb{E}|I_e| \leq\mathbb{E}|T_e| + 3 \leq6 E ∣ I e ∣ ≤ E ∣ T e ∣ + 3 ≤ 6 .
(iii) The certificate fails only if ∣ T e ∣ > s |T_e| > s ∣ T e ∣ > s , which by Markov’s inequality and equation 18 has probability at most E ∣ T e ∣ / s ≤ 3 / s \mathbb{E}|T_e|/s \leq3/s E ∣ T e ∣/ s ≤ 3/ s . ∎
Since the full sample contains every certificate follows directly.
Proof of Theorem 2.1 . The full sample S S S contains S I e S_{I_e} S I e for every edge e e e . By Theorems B.6 and B.7, A ∗ ( S ) \mathcal{A}^*(S) A ∗ ( S ) is correct on ( e , ⊥ ) (e,\perp) ( e , ⊥ ) unless the certificate of e e e fails, which has probability at most 3 / s 3/s 3/ s , and the masked inputs have total probability p m a s k e d p_{\mathrm{masked}} p masked . Therefore
E S [ R P ( A ∗ ( S ) ) ] ≤ 3 p m a s k e d s ≤ 24 log 2 n ⋅ γ 8 k g r o u p ⋅ n n + v = 3 γ k g r o u p ⋅ n ( n + v ) log 2 n ≤ 2 5 λ γ ⋅ n ( n + v ) log 2 n , \begin{aligned}
\mathbb{E}_S\left[R_P(\mathcal{A}^*(S))\right] \leq\frac{3p_{\mathrm{masked}}}{s} \leq\frac{24}{\log_2 n}\cdot\frac{\gamma}{8k_{\mathrm{group}}}\cdot\frac{n}{n+v} \\
&= \frac{3\gamma}{k_{\mathrm{group}}}\cdot\frac{n}{(n+v)\log_2 n} \leq\frac{2}{5}\lambda\gamma\cdot\frac{n}{(n+v)\log_2 n},
\end{aligned} E S [ R P ( A ∗ ( S )) ] ≤ s 3 p masked ≤ log 2 n 24 ⋅ 8 k group γ ⋅ n + v n = k group 3 γ ⋅ ( n + v ) log 2 n n ≤ 5 2 λγ ⋅ ( n + v ) log 2 n n ,
using s ≥ 1 8 log 2 n s \geq\frac{1}{8}\log_2 n s ≥ 8 1 log 2 n , p m a s k e d = γ 8 k g r o u p ⋅ n n + v p_{\mathrm{masked}} = \frac{\gamma}{8k_{\mathrm{group}}}\cdot\frac{n}{n+v} p masked = 8 k group γ ⋅ n + v n , and k g r o u p ≥ 10 / λ k_{\mathrm{group}} \geq10/\lambda k group ≥ 10/ λ . ∎
Figure 6. Simple paths starting with e e e in a cubic graph: there are at most 2 ℓ 2^\ell 2 ℓ of length ℓ \ell ℓ , and each consists of missing edges with probability at most ( 3 / 8 ) ℓ (3/8)^\ell ( 3/8 ) ℓ . Since 2 ⋅ 3 8 < 1 2 \cdot\frac{3}{8} < 1 2 ⋅ 8 3 < 1 , the expected size of the component T e T_e T e is bounded, as for a subcritical branching process.
For part (ii), the oracle is restricted to m m m examples, but since it may depend on h h h , it needs only the certificates of the J J J active edges. Distinct active edges may share their certificate: all edges of a missing component T T T with ∣ T ∣ ≤ s |T| \le s ∣ T ∣ ≤ s have the same certificate, consisting of one index for each edge of ∂ T \partial T ∂ T , so the union of the certificates contains these indices only once per component. We therefore consider
F h : = ∣ { j : e ( j , h j ) is observed } ∣ + ∑ T : ∣ T ∣ ≤ s , T contains an active edge ∣ ∂ T ∣ . F_h := \left|\{j : e(j,h_j)\text{ is observed}\}\right| + \sum_{\substack{T:\ |T|\le s,\\ T\text{ contains an active edge}}} |\partial T|. F h := ∣ { j : e ( j , h j ) is observed } ∣ + T : ∣ T ∣ ≤ s , T contains an active edge ∑ ∣ ∂ T ∣.
where the sum runs over components of missing edges. It satisfies
∣ ⋃ j = 1 J I e ( j , h j ) ∣ ≤ F h ≤ ∑ j = 1 J ∣ I e ( j , h j ) ∣ , (19) \left|\bigcup_{j=1}^{J} I_{e(j,h_j)}\right| \le F_h \le\sum_{j=1}^{J} |I_{e(j,h_j)}|, \tag*{(19)} j = 1 ⋃ J I e ( j , h j ) ≤ F h ≤ j = 1 ∑ J ∣ I e ( j , h j ) ∣ , (19)
where the first inequality holds because the union consists of one index for each observed active edge and the boundary indices of the components that contain an active edge, and the second because a component containing r ≥ 1 r \ge1 r ≥ 1 active edges contributes ∣ ∂ T ∣ |\partial T| ∣ ∂ T ∣ to F h F_h F h and r ∣ ∂ T ∣ r|\partial T| r ∣ ∂ T ∣ to the sum. The next lemma shows that F h ≤ m F_h \le m F h ≤ m with high probability.
Lemma B.8 (Budget). For large n n n , E F h ≤ 3 5 λ n \mathbb{E}F_h \le\frac{3}{5}\lambda n E F h ≤ 5 3 λn and P ( F h > m ) ≤ 1458 s 2 / ( λ 2 n ) \mathbb{P}(F_h > m) \le1458s^2/(\lambda^2 n) P ( F h > m ) ≤ 1458 s 2 / ( λ 2 n ) .
Proof. By equation (19) , Theorem B.7(ii), J = N / k g r o u p ≤ n / k g r o u p J = N/k_{\mathrm{group}} \le n/k_{\mathrm{group}} J = N / k group ≤ n / k group and k g r o u p ≥ 10 / λ k_{\mathrm{group}} \ge10/\lambda k group ≥ 10/ λ ,
E F h ≤ ∑ j = 1 J E ∣ I e ( j , h j ) ∣ ≤ 6 J ≤ 6 n k g r o u p ≤ 3 5 λ n , \mathbb{E}F_h \le\sum_{j=1}^{J} \mathbb{E}|I_{e(j,h_j)}| \le6J \le\frac{6n}{k_{\mathrm{group}}} \le\frac{3}{5}\lambda n, E F h ≤ j = 1 ∑ J E ∣ I e ( j , h j ) ∣ ≤ 6 J ≤ k group 6 n ≤ 5 3 λn ,
and since m ≥ λ n − 1 m \ge\lambda n - 1 m ≥ λn − 1 , we obtain m − E F h ≥ 2 5 λ n − 1 ≥ λ n / 3 m-\mathbb{E}F_h \ge\frac{2}{5}\lambda n - 1 \ge\lambda n/3 m − E F h ≥ 5 2 λn − 1 ≥ λn /3 for large n n n .
To show that F h F_h F h concentrates, we bound the effect of replacing a single example and apply the Efron–Stein inequality. The quantity F h F_h F h depends on S S S only through the set of observed edges. Suppose that the status of a single edge f f f changes, and call a component of missing edges, before or after the change, affected if it shares a vertex with f f f . Unaffected components retain their edges, their boundary and their active edges, so their terms do not change. There are at most two affected components before the change and at most two after it: if f f f is missing, only its own component is affected, and if f f f is observed, at most one component meets each of its two endpoints. Each component term lies in [ 0 , s + 3 ] [0,s+3] [ 0 , s + 3 ] , since ∣ ∂ T ∣ ≤ s + 3 |\partial T| \le s+3 ∣ ∂ T ∣ ≤ s + 3 , so the sum changes by at most 2 ( s + 3 ) 2(s+3) 2 ( s + 3 ) , the first term by at most one, and F h F_h F h by at most 2 ( s + 3 ) + 1 2(s+3)+1 2 ( s + 3 ) + 1 . Replacing one example of S S S by an independent copy changes the status of at most two edges, namely those of the old and the new example, and therefore changes F h F_h F h by at most 2 ( 2 s + 7 ) ≤ 18 s 2(2s+7) \le18s 2 ( 2 s + 7 ) ≤ 18 s . Writing F h ( i ) F_h^{(i)} F h ( i ) for the value of F h F_h F h after the i i i -th example is replaced, the Efron–Stein inequality gives
Var ( F h ) ≤ 1 2 ∑ i = 1 n E [ ( F h − F h ( i ) ) 2 ] ≤ n 2 ( 18 s ) 2 = 162 n s 2 , \operatorname{Var}(F_h) \le\frac{1}{2}\sum_{i=1}^{n}\mathbb{E}\left[(F_h-F_h^{(i)})^2\right] \le\frac{n}{2}(18s)^2=162ns^2, Var ( F h ) ≤ 2 1 i = 1 ∑ n E [ ( F h − F h ( i ) ) 2 ] ≤ 2 n ( 18 s ) 2 = 162 n s 2 ,
and Chebyshev’s inequality gives
P ( F h > m ) ≤ P ( F h − E F h > λ n 3 ) ≤ 162 n s 2 ( λ n / 3 ) 2 = 1458 s 2 λ 2 n . \mathbb{P}(F_h>m)\le\mathbb{P}\left(F_h-\mathbb{E}F_h>\frac{\lambda n}{3}\right)\le\frac{162ns^2}{(\lambda n/3)^2}=\frac{1458s^2}{\lambda^2n}. P ( F h > m ) ≤ P ( F h − E F h > 3 λn ) ≤ ( λn /3 ) 2 162 n s 2 = λ 2 n 1458 s 2 .
We now combine Theorems B.7 and B.8 to prove part (ii).
Proof of Theorem 2.1 . Since I m ⋆ I_m^\star I m ⋆ minimizes R P ( A ⋆ ( S I ) ) R_P(A^\star(S_I)) R P ( A ⋆ ( S I )) over subsets of size m m m , it suffices to exhibit a subset I ~ ⊆ [ n ] \widetilde I\subseteq[n] I ⊆ [ n ] of size m m m , which may depend on P P P as I m ⋆ I_m^\star I m ⋆ does, and to bound E S [ R P ( A ⋆ ( S I ~ ) ) ] \mathbb{E}_S[R_P(A^\star(S_{\widetilde I}))] E S [ R P ( A ⋆ ( S I ))] . Call S S S good if F h ≤ m F_h\le m F h ≤ m . If S S S is good, let I ~ \widetilde I I contain the union ⋃ j I e ( j , h j ) \bigcup_j I_{e(j,h_j)} ⋃ j I e ( j , h j ) of the certificates of the active edges, which by equation (19) has at most F h ≤ m F_h\le m F h ≤ m indices, together with arbitrary further indices to reach exactly m m m . If S S S is not good, let I ~ : = [ m ] \widetilde I:=[m] I := [ m ] .
If S S S is good, S I ~ S_{\widetilde I} S I contains the certificate of every active edge, so by Theorems B.6 and B.7 it determines the label of every active edge whose certificate does not fail. Hence A ⋆ ( S I ~ ) A^\star(S_{\widetilde I}) A ⋆ ( S I ) errs only on inputs ( e ( j , h j ) , ⊥ ) (e(j,h_j),\perp) ( e ( j , h j ) , ⊥ ) whose certificate fails, each of probability p m a s k e d / J p_{\mathrm{masked}}/J p masked / J . If S S S is not good, the risk is still at most p m a s k e d p_{\mathrm{masked}} p masked by Theorem B.6(i). By Theorem B.7(iii) and Theorem B.8,
E S [ R P ( A ⋆ ( S I m ⋆ ) ) ] ≤ E S [ R P ( A ⋆ ( S I ~ ) ) ] ≤ p m a s k e d ( 3 s + 1458 s 2 λ 2 n ) . \mathbb{E}_S\left[R_P(A^\star(S_{I_m^\star}))\right]\le\mathbb{E}_S\left[R_P(A^\star(S_{\widetilde I}))\right]\le p_{\mathrm{masked}}\left(\frac{3}{s}+\frac{1458s^2}{\lambda^2n}\right). E S [ R P ( A ⋆ ( S I m ⋆ )) ] ≤ E S [ R P ( A ⋆ ( S I )) ] ≤ p masked ( s 3 + λ 2 n 1458 s 2 ) .
Since 1 8 log 2 n ≤ s ≤ log 2 n \frac{1}{8}\log_2 n\le s\le\log_2 n 8 1 log 2 n ≤ s ≤ log 2 n and 1458 ( log 2 n ) 2 λ 2 n ≤ 1 log 2 n \frac{1458(\log_2 n)^2}{\lambda^2n}\le\frac{1}{\log_2 n} λ 2 n 1458 ( l o g 2 n ) 2 ≤ l o g 2 n 1 for large n n n , the bracket is at most 25 log 2 n \frac{25}{\log_2 n} l o g 2 n 25 . Since
p m a s k e d = γ 8 k g r o u p ⋅ n n + v , p_{\mathrm{masked}}=\frac{\gamma}{8k_{\mathrm{group}}}\cdot\frac{n}{n+v}, p masked = 8 k group γ ⋅ n + v n ,
E S [ R P ( A ⋆ ( S I m ⋆ ) ) ] ≤ 25 γ 8 k g r o u p ⋅ n ( n + v ) log 2 n ≤ 2 5 λ γ ⋅ n ( n + v ) log 2 n , \mathbb{E}_S\left[R_P(A^\star(S_{I_m^\star}))\right]\le\frac{25\gamma}{8k_{\mathrm{group}}}\cdot\frac{n}{(n+v)\log_2 n}\le\frac{2}{5}\lambda\gamma\cdot\frac{n}{(n+v)\log_2 n}, E S [ R P ( A ⋆ ( S I m ⋆ )) ] ≤ 8 k group 25 γ ⋅ ( n + v ) log 2 n n ≤ 5 2 λγ ⋅ ( n + v ) log 2 n n ,
using k g r o u p ≥ 10 / λ k_{\mathrm{group}}\ge10/\lambda k group ≥ 10/ λ in the last step. The constants and the threshold n λ n_\lambda n λ depend only on λ \lambda λ , which completes the proof of Theorem 2.1 .
KL divergence in parameter space upper bounds the faithfulness error
Proof. Let P = A n ( S ) P=\mathcal{A}_n(S) P = A n ( S ) and Q = A m ( S I ) Q=\mathcal{A}_m(S_I) Q = A m ( S I ) , and write δ = E P [ q ] − E Q [ q ] \delta=\mathbb{E}_P[q]-\mathbb{E}_Q[q] δ = E P [ q ] − E Q [ q ] . If D K L ( P ∥ Q ) = ∞ D_{\mathrm{KL}}(P\|Q)=\infty D KL ( P ∥ Q ) = ∞ , the claim is immediate. Otherwise, set c = a + b 2 c=\frac{a+b}{2} c = 2 a + b . Since P P P and Q Q Q are both probability measures, ( P − Q ) ( R d ) = 0 (P-Q)(\mathbb{R}^d)=0 ( P − Q ) ( R d ) = 0 , so
δ = ∫ ( q − c ) d ( P − Q ) . \delta=\int(q-c)\,\mathrm{d}(P-Q). δ = ∫ ( q − c ) d ( P − Q ) .
Because q q q takes values in [ a , b ] [a,b] [ a , b ] , we have ∣ q − c ∣ ≤ b − a 2 |q-c|\le\frac{b-a}{2} ∣ q − c ∣ ≤ 2 b − a pointwise, and therefore
∣ δ ∣ ≤ b − a 2 ∥ P − Q ∥ 1 = ( b − a ) TV ( P , Q ) , |\delta|\le\frac{b-a}{2}\|P-Q\|_1=(b-a)\operatorname{TV}(P,Q), ∣ δ ∣ ≤ 2 b − a ∥ P − Q ∥ 1 = ( b − a ) TV ( P , Q ) ,
where TV ( P , Q ) = sup A ∣ P ( A ) − Q ( A ) ∣ = 1 2 ∥ P − Q ∥ 1 \operatorname{TV}(P,Q)=\sup_A|P(A)-Q(A)|=\frac{1}{2}\|P-Q\|_1 TV ( P , Q ) = sup A ∣ P ( A ) − Q ( A ) ∣ = 2 1 ∥ P − Q ∥ 1 is the total variation distance. Pinsker’s inequality gives
TV ( P , Q ) ≤ 1 2 D K L ( P ∥ Q ) . \operatorname{TV}(P,Q)\le\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P\|Q)}. TV ( P , Q ) ≤ 2 1 D KL ( P ∥ Q ) .
Combining the two bounds yields
∣ δ ∣ ≤ ( b − a ) 1 2 D K L ( P ∥ Q ) = ( b − a ) 2 2 D K L ( P ∥ Q ) . |\delta| \le(b-a)\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P\|Q)}=\sqrt{\frac{(b-a)^2}{2}D_{\mathrm{KL}}(P\|Q)}. ∣ δ ∣ ≤ ( b − a ) 2 1 D KL ( P ∥ Q ) = 2 ( b − a ) 2 D KL ( P ∥ Q ) .
The argument applies directly to ∣ δ ∣ |\delta| ∣ δ ∣ , so no separate treatment of the positive and negative parts is needed. This proof applies to every measurable q q q bounded in [ a , b ] [a,b] [ a , b ] .
Proof of the gradient trajectory upper bounding the faithfulness
Proof. For a sample S ′ ∈ { S , S I } S' \in\{S,S_I\} S ′ ∈ { S , S I } , let L S ′ L_{S'} L S ′ be its empirical loss, and let ( θ t S ′ ) t = 0 T (\theta_t^{S'})_{t=0}^{T} ( θ t S ′ ) t = 0 T be the ULA chain
θ t + 1 S ′ = θ t S ′ − h t ∇ L S ′ ( θ t S ′ ) + 2 h t β t ξ t + 1 , ξ t + 1 ∼ i . i . d . N ( 0 , I d ) , \theta_{t+1}^{S'}=\theta_t^{S'}-h_t\nabla L_{S'}(\theta_t^{S'})+\sqrt{\frac{2h_t}{\beta_t}}\xi_{t+1},\qquad\xi_{t+1}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,I_d), θ t + 1 S ′ = θ t S ′ − h t ∇ L S ′ ( θ t S ′ ) + β t 2 h t ξ t + 1 , ξ t + 1 ∼ i.i.d. N ( 0 , I d ) ,
started from the same initial law μ 0 \mu_0 μ 0 for both samples. Write μ t S ′ \mu_t^{S'} μ t S ′ for the law of θ t S ′ \theta_t^{S'} θ t S ′ , so that A n ( S ) = μ T S A_n(S)=\mu_T^S A n ( S ) = μ T S and A m ( S I ) = μ T S I A_m(S_I)=\mu_T^{S_I} A m ( S I ) = μ T S I , and let P S ′ \mathbb{P}^{S'} P S ′ be the law of the path ( θ 0 S ′ , … , θ T S ′ ) (\theta_0^{S'},\ldots,\theta_T^{S'}) ( θ 0 S ′ , … , θ T S ′ ) . Recall that
G T ( I ) = ∑ t = 0 T − 1 β t h t 4 E θ t ∼ μ t S [ ∥ ∇ L S I ( θ t ) − ∇ L S ( θ t ) ∥ 2 ] . G_T(I)=\sum_{t=0}^{T-1}\frac{\beta_t h_t}{4}\mathbb{E}_{\theta_t\sim\mu_t^S}\left[\|\nabla L_{S_I}(\theta_t)-\nabla L_S(\theta_t)\|^2\right]. G T ( I ) = t = 0 ∑ T − 1 4 β t h t E θ t ∼ μ t S [ ∥∇ L S I ( θ t ) − ∇ L S ( θ t ) ∥ 2 ] .
Since ℓ ( ⋅ , z ) \ell(\cdot,z) ℓ ( ⋅ , z ) is continuously differentiable, the map θ ↦ ∇ L S ′ ( θ ) \theta\mapsto\nabla L_{S'}(\theta) θ ↦ ∇ L S ′ ( θ ) is continuous, so the transition kernels
K t S ′ ( θ , ⋅ ) = N ( θ − h t ∇ L S ′ ( θ ) , 2 h t β t I d ) , t = 0 , … , T − 1 , K_t^{S'}(\theta,\cdot)=\mathcal{N}\left(\theta-h_t\nabla L_{S'}(\theta),\frac{2h_t}{\beta_t}I_d\right),\qquad t=0,\ldots,T-1, K t S ′ ( θ , ⋅ ) = N ( θ − h t ∇ L S ′ ( θ ) , β t 2 h t I d ) , t = 0 , … , T − 1 ,
are measurable. For fixed θ \theta θ and t t t , the kernels K t S ( θ , ⋅ ) K_t^S(\theta,\cdot) K t S ( θ , ⋅ ) and K t S I ( θ , ⋅ ) K_t^{S_I}(\theta,\cdot) K t S I ( θ , ⋅ ) are Gaussians with the same covariance 2 h t β t I d \frac{2h_t}{\beta_t}I_d β t 2 h t I d and means that differ by h t ( ∇ L S I ( θ ) − ∇ L S ( θ ) ) h_t(\nabla L_{S_I}(\theta)-\nabla L_S(\theta)) h t ( ∇ L S I ( θ ) − ∇ L S ( θ )) . The KL divergence between two Gaussians with a common covariance Σ \Sigma Σ is 1 2 ( Δ m ) ⊤ Σ − 1 Δ m \frac{1}{2}(\Delta m)^\top\Sigma^{-1}\Delta m 2 1 ( Δ m ) ⊤ Σ − 1 Δ m , so
D K L ( K t S ( θ , ⋅ ) ∥ K t S I ( θ , ⋅ ) ) = 1 2 ⋅ β t 2 h t ⋅ h t 2 ∥ ∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 = β t h t 4 ∥ ∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 . D_{\mathrm{KL}}\left(K_t^S(\theta,\cdot)\,\|\,K_t^{S_I}(\theta,\cdot)\right)=\frac{1}{2}\cdot\frac{\beta_t}{2h_t}\cdot h_t^2\|\nabla L_{S_I}(\theta)-\nabla L_S(\theta)\|^2=\frac{\beta_t h_t}{4}\|\nabla L_{S_I}(\theta)-\nabla L_S(\theta)\|^2. D KL ( K t S ( θ , ⋅ ) ∥ K t S I ( θ , ⋅ ) ) = 2 1 ⋅ 2 h t β t ⋅ h t 2 ∥∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 = 4 β t h t ∥∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 .
Both chains are Markov with the same initial law μ 0 \mu_0 μ 0 and use the same Gaussian noise structure, so the chain rule for KL divergence on Markov paths gives
D K L ( P S ∥ P S I ) = D K L ( μ 0 ∥ μ 0 ) + ∑ t = 0 T − 1 E θ t ∼ μ t S [ D K L ( K t S ( θ t , ⋅ ) ∥ K t S I ( θ t , ⋅ ) ) ] . D_{\mathrm{KL}}(\mathbb{P}^S\|\mathbb{P}^{S_I})=D_{\mathrm{KL}}(\mu_0\|\mu_0)+\sum_{t=0}^{T-1}\mathbb{E}_{\theta_t\sim\mu_t^S}\left[D_{\mathrm{KL}}\left(K_t^S(\theta_t,\cdot)\,\|\,K_t^{S_I}(\theta_t,\cdot)\right)\right]. D KL ( P S ∥ P S I ) = D KL ( μ 0 ∥ μ 0 ) + t = 0 ∑ T − 1 E θ t ∼ μ t S [ D KL ( K t S ( θ t , ⋅ ) ∥ K t S I ( θ t , ⋅ ) ) ] .
The outer expectation is under the marginal μ t S \mu_t^S μ t S of the first path law, which is why G T G_T G T involves only the full-data chain. Thus:
D K L ( P S ∥ P S I ) = G T ( I ) . D_{\mathrm{KL}}(\mathbb{P}^S\|\mathbb{P}^{S_I})=G_T(I). D KL ( P S ∥ P S I ) = G T ( I ) .
By Jensen’s inequality, for every θ \theta θ , ∥ ∇ L S ′ ( θ ) ∥ 2 ≤ 1 ∣ S ′ ∣ ∑ z ∈ S ′ ∥ ∇ ℓ ( θ , z ) ∥ 2 \|\nabla L_{S'}(\theta)\|^2\le\frac{1}{|S'|}\sum_{z\in S'}\|\nabla\ell(\theta,z)\|^2 ∥∇ L S ′ ( θ ) ∥ 2 ≤ ∣ S ′ ∣ 1 ∑ z ∈ S ′ ∥∇ ℓ ( θ , z ) ∥ 2 , so
∥ ∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 ≤ 2 ∥ ∇ L S I ( θ ) ∥ 2 + 2 ∥ ∇ L S ( θ ) ∥ 2 ≤ 2 m ∑ i ∈ I ∥ ∇ ℓ ( θ , Z i ) ∥ 2 + 2 n ∑ i = 1 n ∥ ∇ ℓ ( θ , Z i ) ∥ 2 . \|\nabla L_{S_I}(\theta)-\nabla L_S(\theta)\|^2\le2\|\nabla L_{S_I}(\theta)\|^2+2\|\nabla L_S(\theta)\|^2\le\frac{2}{m}\sum_{i\in I}\|\nabla\ell(\theta,Z_i)\|^2+\frac{2}{n}\sum_{i=1}^{n}\|\nabla\ell(\theta,Z_i)\|^2. ∥∇ L S I ( θ ) − ∇ L S ( θ ) ∥ 2 ≤ 2∥∇ L S I ( θ ) ∥ 2 + 2∥∇ L S ( θ ) ∥ 2 ≤ m 2 i ∈ I ∑ ∥∇ ℓ ( θ , Z i ) ∥ 2 + n 2 i = 1 ∑ n ∥∇ ℓ ( θ , Z i ) ∥ 2 .
The integrability assumption on ∇ ℓ ( θ , Z i ) \nabla\ell(\theta,Z_i) ∇ ℓ ( θ , Z i ) under μ t S \mu_t^S μ t S , for t ≤ T t\le T t ≤ T , therefore ensures that every term of G T ( I ) G_T(I) G T ( I ) is finite.
The map ( θ 0 , … , θ T ) ↦ θ T (\theta_0,\ldots,\theta_T)\mapsto\theta_T ( θ 0 , … , θ T ) ↦ θ T pushes P S \mathbb{P}^S P S and P S I \mathbb{P}^{S_I} P S I forward to μ T S \mu_T^S μ T S and μ T S I \mu_T^{S_I} μ T S I . Data processing for KL divergence then yields
D K L ( A n ( S ) ∥ A m ( S I ) ) = D K L ( μ T S ∥ μ T S I ) ≤ D K L ( P S ∥ P S I ) = G T ( I ) . D_{\mathrm{KL}}(A_n(S)\|A_m(S_I))=D_{\mathrm{KL}}(\mu_T^S\|\mu_T^{S_I})\le D_{\mathrm{KL}}(\mathbb{P}^S\|\mathbb{P}^{S_I})=G_T(I). D KL ( A n ( S ) ∥ A m ( S I )) = D KL ( μ T S ∥ μ T S I ) ≤ D KL ( P S ∥ P S I ) = G T ( I ) .
Proof of the quadratic program formulation of subset selection by optimizing the gradient trajectory
Proof. Write g i ( θ ) : = ∇ ℓ ( θ , Z i ) g_i(\theta) := \nabla\ell(\theta, Z_i) g i ( θ ) := ∇ ℓ ( θ , Z i ) , g ˉ ( θ ) : = ∇ L S ( θ ) = 1 n ∑ i = 1 n g i ( θ ) \bar{g}(\theta) := \nabla L_S(\theta) = \frac{1}{n}\sum_{i=1}^n g_i(\theta) g ˉ ( θ ) := ∇ L S ( θ ) = n 1 ∑ i = 1 n g i ( θ ) , so that ζ i = g i − g ˉ \zeta_i = g_i - \bar{g} ζ i = g i − g ˉ , and w t : = β t h t / 4 w_t := \beta_t h_t/4 w t := β t h t /4 . Since ∑ j = 1 n ζ j ( θ ) = 0 \sum_{j=1}^n \zeta_j(\theta) = 0 ∑ j = 1 n ζ j ( θ ) = 0 for every θ \theta θ ,
( C 1 ) i = ∑ t = 0 T − 1 w t E θ ∼ μ t s ⟨ ζ i ( θ ) , ∑ j = 1 n ζ j ( θ ) ⟩ = 0. (C\mathbf{1})_i = \sum_{t=0}^{T-1} w_t \mathbb{E}_{\theta\sim\mu_t^s}\left\langle\zeta_i(\theta), \sum_{j=1}^n \zeta_j(\theta)\right\rangle= 0. ( C 1 ) i = t = 0 ∑ T − 1 w t E θ ∼ μ t s ⟨ ζ i ( θ ) , j = 1 ∑ n ζ j ( θ ) ⟩ = 0.
For v ∈ R n v \in\mathbb{R}^n v ∈ R n , linearity gives
v ⊤ C v = ∑ t = 0 T − 1 w t E θ ∼ μ t s ∥ ∑ i = 1 n v i ζ i ( θ ) ∥ 2 ≥ 0 , v^\top C v = \sum_{t=0}^{T-1} w_t \mathbb{E}_{\theta\sim\mu_t^s}\left\|\sum_{i=1}^n v_i\zeta_i(\theta)\right\|^2 \ge0, v ⊤ C v = t = 0 ∑ T − 1 w t E θ ∼ μ t s i = 1 ∑ n v i ζ i ( θ ) 2 ≥ 0 ,
so C ⪰ 0 C \succeq0 C ⪰ 0 . Finally, for ∣ I ∣ = m |I| = m ∣ I ∣ = m ,
∇ L S I ( θ ) − ∇ L S ( θ ) = 1 m ∑ i ∈ I g i ( θ ) − g ˉ ( θ ) = 1 m ∑ i ∈ I ζ i ( θ ) , \nabla L_{S_I}(\theta)-\nabla L_S(\theta)=\frac{1}{m}\sum_{i\in I}g_i(\theta)-\bar{g}(\theta)=\frac{1}{m}\sum_{i\in I}\zeta_i(\theta), ∇ L S I ( θ ) − ∇ L S ( θ ) = m 1 i ∈ I ∑ g i ( θ ) − g ˉ ( θ ) = m 1 i ∈ I ∑ ζ i ( θ ) ,
and therefore
G T ( I ) = ∑ t = 0 T − 1 w t E θ ∼ μ t s ∥ 1 m ∑ i ∈ I ζ i ( θ ) ∥ 2 = 1 m 2 ∑ i , j ∈ I C i j = 1 m 2 1 I ⊤ C 1 I . G_T(I)=\sum_{t=0}^{T-1}w_t\mathbb{E}_{\theta\sim\mu_t^s}\left\|\frac{1}{m}\sum_{i\in I}\zeta_i(\theta)\right\|^2=\frac{1}{m^2}\sum_{i,j\in I}C_{ij}=\frac{1}{m^2}\mathbf{1}_I^\top C\mathbf{1}_I. G T ( I ) = t = 0 ∑ T − 1 w t E θ ∼ μ t s m 1 i ∈ I ∑ ζ i ( θ ) 2 = m 2 1 i , j ∈ I ∑ C ij = m 2 1 1 I ⊤ C 1 I .
Since I ↦ 1 I I\mapsto\mathbf{1}_I I ↦ 1 I is a bijection from subsets of size m m m onto B m \mathcal{B}_m B m , minimizing G T G_T G T over such subsets is the stated integer program.
Construction and analysis of the Swap algorithm
Setup. Write w t : = β t h t / 4 w_t := \beta_t h_t/4 w t := β t h t /4 . For α ∈ B m \alpha\in\mathcal{B}_m α ∈ B m , let D ( α ) = 1 m 2 α ⊤ C α D(\alpha)=\frac{1}{m^2}\alpha^\top C\alpha D ( α ) = m 2 1 α ⊤ C α be the objective of Theorem 4.4, so that D ( 1 I ) = G T ( I ) D(\mathbf{1}_I)=G_T(I) D ( 1 I ) = G T ( I ) , and let
s ( α ) : = ∇ D ( α ) = 2 m 2 C α , D ( α ) = 1 2 α ⊤ s ( α ) . s(\alpha):=\nabla D(\alpha)=\frac{2}{m^2}C\alpha,\qquad D(\alpha)=\frac{1}{2}\alpha^\top s(\alpha). s ( α ) := ∇ D ( α ) = m 2 2 C α , D ( α ) = 2 1 α ⊤ s ( α ) .
Since C ⪰ 0 C\succeq0 C ⪰ 0 and C 1 = 0 C\mathbf{1}=0 C 1 = 0 , D D D is convex and already centered. Fix
α ⋆ ∈ arg min α ∈ B m D ( α ) , D ⋆ : = D ( α ⋆ ) , r : = min { m , n − m } , \alpha^\star\in\arg\min_{\alpha\in\mathcal{B}_m}D(\alpha),\qquad D^\star:=D(\alpha^\star),\qquad r:=\min\{m,n-m\}, α ⋆ ∈ arg α ∈ B m min D ( α ) , D ⋆ := D ( α ⋆ ) , r := min { m , n − m } ,
and write [ x ] + : = max { x , 0 } [x]_+ := \max\{x,0\} [ x ] + := max { x , 0 } . Given an iterate α k = 1 I k \alpha_k=\mathbf{1}_{I_k} α k = 1 I k with stored s k : = s ( α k ) s_k:=s(\alpha_k) s k := s ( α k ) , let
i k ∈ arg max i ∈ I k s k ( i ) , j k ∈ arg min j ∉ I k s k ( j ) , γ k : = s k ( i k ) − s k ( j k ) , δ k : = e j k − e i k . i_k\in\arg\max_{i\in I_k}s_k(i),\qquad j_k\in\arg\min_{j\notin I_k}s_k(j),\qquad\gamma_k:=s_k(i_k)-s_k(j_k),\qquad\delta_k:=e_{j_k}-e_{i_k}. i k ∈ arg i ∈ I k max s k ( i ) , j k ∈ arg j ∈ / I k min s k ( j ) , γ k := s k ( i k ) − s k ( j k ) , δ k := e j k − e i k .
The pair ( i k , j k ) (i_k,j_k) ( i k , j k ) minimizes the linearized change s k ( j ) − s k ( i ) s_k(j)-s_k(i) s k ( j ) − s k ( i ) over all exchanges.
Algorithm 2 Gradient-ranked single-swap descent (indicator form)
1: Initialize α 0 : = 1 I 0 \alpha_0 := \mathbf{1}_{I_0} α 0 := 1 I 0 with ∣ I 0 ∣ = m \lvert I_0\rvert= m ∣ I 0 ∣ = m , and query C α 0 C\alpha_0 C α 0 to store s 0 s_0 s 0 . 2: Compute D ( α 0 ) D(\alpha_0) D ( α 0 ) from C α 0 C\alpha_0 C α 0 and set D − 1 : = − ∞ D_{-1} := -\infty D − 1 := − ∞ . 3: for k = 0 , 1 , … k = 0,1,\ldots k = 0 , 1 , … do 4: Choose i k i_k i k , j k j_k j k , γ k \gamma_k γ k , and δ k \delta_k δ k as above. 5: Set D k : = max { D k − 1 , D ( α k ) − r [ γ k ] + } D_k := \max\{D_{k-1},D(\alpha_k)-r[\gamma_k]_+\} D k := max { D k − 1 , D ( α k ) − r [ γ k ] + } and H ^ k : = D ( α k ) − D k \widehat{H}_k := D(\alpha_k)-D_k H k := D ( α k ) − D k . 6: if γ k ≤ 0 \gamma_k \le0 γ k ≤ 0 then 7: return ( α k , H ^ k ) (\alpha_k,\widehat{H}_k) ( α k , H k ) . 8: Set α ~ k : = α k + δ k \widetilde{\alpha}_k := \alpha_k+\delta_k α k := α k + δ k , query C α ~ k C\widetilde{\alpha}_k C α k , and store s ~ k : = s ( α ~ k ) \widetilde{s}_k := s(\widetilde{\alpha}_k) s k := s ( α k ) . 9: Compute Δ k : = 1 2 δ k T ( s k + s ~ k ) \Delta_k := \frac{1}{2}\delta_k^{\mathsf{T}}(s_k+\widetilde{s}_k) Δ k := 2 1 δ k T ( s k + s k ) . 10: if Δ k < 0 \Delta_k < 0 Δ k < 0 then 11: Set ( α k + 1 , s k + 1 ) : = ( α ~ k , s ~ k ) (\alpha_{k+1},s_{k+1}) := (\widetilde{\alpha}_k,\widetilde{s}_k) ( α k + 1 , s k + 1 ) := ( α k , s k ) and store D ( α k + 1 ) : = D ( α k ) + Δ k D(\alpha_{k+1}) := D(\alpha_k)+\Delta_k D ( α k + 1 ) := D ( α k ) + Δ k . 12: else 13: return ( α k , H ^ k ) (\alpha_k,\widehat{H}_k) ( α k , H k ) .
This is Algorithm 1 written on indicator vectors, with an early exit and the bookkeeping of D k D_k D k and H ^ k \widehat{H}_k H k . Neither changes the iterates, as shown below.
Proof of the swap gap
Proof. Let I ′ = ( I k ∖ { i k } ) ∪ { j k } I'=(I_k\setminus\{i_k\})\cup\{j_k\} I ′ = ( I k ∖ { i k }) ∪ { j k } , so that α ~ k = 1 I ′ \widetilde{\alpha}_k=\mathbf{1}_{I'} α k = 1 I ′ . Since D D D is quadratic,
Δ k = 1 2 δ k T ( s k + s ~ k ) = δ k T s k + 1 m 2 δ k T C δ k = D ( α ~ k ) − D ( α k ) = G T ( I ′ ) − G T ( I k ) . \Delta_k=\frac{1}{2}\delta_k^{\mathsf{T}}(s_k+\widetilde{s}_k)=\delta_k^{\mathsf{T}}s_k+\frac{1}{m^2}\delta_k^{\mathsf{T}}C\delta_k=D(\widetilde{\alpha}_k)-D(\alpha_k)=G_T(I')-G_T(I_k). Δ k = 2 1 δ k T ( s k + s k ) = δ k T s k + m 2 1 δ k T C δ k = D ( α k ) − D ( α k ) = G T ( I ′ ) − G T ( I k ) .
and δ k T s k = − γ k \delta_k^{\mathsf{T}}s_k=-\gamma_k δ k T s k = − γ k with δ k T C δ k ≥ 0 \delta_k^{\mathsf{T}}C\delta_k\ge0 δ k T C δ k ≥ 0 , so Δ k ≥ − γ k \Delta_k\ge-\gamma_k Δ k ≥ − γ k . Hence a candidate is accepted if and only if G T ( I ′ ) < G T ( I k ) G_T(I')<G_T(I_k) G T ( I ′ ) < G T ( I k ) . Moreover, if γ k ≤ 0 \gamma_k\le0 γ k ≤ 0 then Δ k ≥ 0 \Delta_k\ge0 Δ k ≥ 0 , so the candidate would be rejected anyway. The early exit therefore does not change the iterates, and the algorithm coincides with Algorithm 1.
(i) Since 1 ≤ m ≤ n − 1 1\le m\le n-1 1 ≤ m ≤ n − 1 , both I k I_k I k and its complement are nonempty, so i k ∈ I k i_k\in I_k i k ∈ I k and j k ∉ I k j_k\notin I_k j k ∈ / I k exist for every tie-breaking rule. Hence ∣ I ′ ∣ = m \lvert I'\rvert=m ∣ I ′ ∣ = m , and by induction every I k I_k I k has size m m m . Every accepted swap satisfies G T ( I k + 1 ) < G T ( I k ) G_T(I_{k+1})<G_T(I_k) G T ( I k + 1 ) < G T ( I k ) , so the values G T ( I 0 ) > G T ( I 1 ) > ⋯ G_T(I_0)>G_T(I_1)>\cdots G T ( I 0 ) > G T ( I 1 ) > ⋯ are strictly decreasing and the accepted subsets are pairwise distinct. There are only ( n m ) \binom{n}{m} ( m n ) subsets of size m m m , so at most ( n m ) − 1 \binom{n}{m}-1 ( m n ) − 1 swaps are accepted. The first rejected candidate (or the early exit) then makes the algorithm return I o u t = I k I_{\mathrm{out}}=I_k I out = I k .
(ii) By (i), G T ( I o u t ) ≤ G T ( I 0 ) G_T(I_{\mathrm{out}})\le G_T(I_0) G T ( I out ) ≤ G T ( I 0 ) for every I 0 I_0 I 0 and every tie-breaking rule, so E [ G T ( I o u t ) ] ≤ E [ G T ( I 0 ) ] \mathbb{E}[G_T(I_{\mathrm{out}})]\le\mathbb{E}[G_T(I_0)] E [ G T ( I out )] ≤ E [ G T ( I 0 )] . For I 0 I_0 I 0 uniform on the subsets of size m m m , we have P ( i ∈ I 0 ) = m n \mathbb{P}(i\in I_0)=\frac{m}{n} P ( i ∈ I 0 ) = n m and P ( i , j ∈ I 0 ) = m ( m − 1 ) n ( n − 1 ) \mathbb{P}(i,j\in I_0)=\frac{m(m-1)}{n(n-1)} P ( i , j ∈ I 0 ) = n ( n − 1 ) m ( m − 1 ) for i ≠ j i\ne j i = j . Therefore
E [ G T ( I 0 ) ] = 1 m 2 [ m n tr C + m ( m − 1 ) n ( n − 1 ) ∑ i ≠ j C i j ] . \mathbb{E}[G_T(I_0)]=\frac{1}{m^2}\left[\frac{m}{n}\operatorname{tr}C+\frac{m(m-1)}{n(n-1)}\sum_{i\ne j}C_{ij}\right]. E [ G T ( I 0 )] = m 2 1 n m tr C + n ( n − 1 ) m ( m − 1 ) i = j ∑ C ij .
Since C 1 = 0 C\mathbf{1}=0 C 1 = 0 , we have ∑ i ≠ j C i j = 1 T C 1 − tr C = − tr C \sum_{i\ne j}C_{ij}=\mathbf{1}^{\mathsf{T}}C\mathbf{1}-\operatorname{tr}C=-\operatorname{tr}C ∑ i = j C ij = 1 T C 1 − tr C = − tr C , and hence
E [ G T ( I 0 ) ] = tr C m 2 ⋅ m n ( 1 − m − 1 n − 1 ) = n − m m n ( n − 1 ) tr C . \mathbb{E}[G_T(I_0)]=\frac{\operatorname{tr}C}{m^2}\cdot\frac{m}{n}\left(1-\frac{m-1}{n-1}\right)=\frac{n-m}{mn(n-1)}\operatorname{tr}C. E [ G T ( I 0 )] = m 2 tr C ⋅ n m ( 1 − n − 1 m − 1 ) = mn ( n − 1 ) n − m tr C .
Finally, with ζ i = ∇ ℓ ( ⋅ , Z i ) − ∇ L S \zeta_i=\nabla\ell(\cdot,Z_i)-\nabla L_S ζ i = ∇ ℓ ( ⋅ , Z i ) − ∇ L S ,
tr C = ∑ i = 1 n C i i = ∑ t = 0 T − 1 w t ∑ i = 1 n E θ ∼ μ t ∥ ζ i ( θ ) ∥ 2 = n ∑ t = 0 T − 1 w t V t , \operatorname{tr}C=\sum_{i=1}^{n}C_{ii}=\sum_{t=0}^{T-1}w_t\sum_{i=1}^{n}\mathbb{E}_{\theta\sim\mu_t}\lVert\zeta_i(\theta)\rVert^2=n\sum_{t=0}^{T-1}w_tV_t, tr C = i = 1 ∑ n C ii = t = 0 ∑ T − 1 w t i = 1 ∑ n E θ ∼ μ t ∥ ζ i ( θ ) ∥ 2 = n t = 0 ∑ T − 1 w t V t ,
so that E [ G T ( I o u t ) ] ≤ E [ G T ( I 0 ) ] = n − m m ( n − 1 ) ∑ t = 0 T − 1 w t V t \mathbb{E}[G_T(I_{\mathrm{out}})]\le\mathbb{E}[G_T(I_0)]=\frac{n-m}{m(n-1)}\sum_{t=0}^{T-1}w_tV_t E [ G T ( I out )] ≤ E [ G T ( I 0 )] = m ( n − 1 ) n − m ∑ t = 0 T − 1 w t V t .
Experimental details
Caveat on the train / validation split
The reference trajectory is trained on a single random 90%/10% split (seed 42), whereas the selection experiments use five seeds, each with its own split. Only one seed therefore shares its pool with the reference run. For the other four, the selection pool S s S_s S s and the reference pool S r e f S_{\mathrm{ref}} S ref are different 45,000-example draws from the same 50,000 images, overlapping on about 90% of their elements. For these seeds, both the checkpoints used to compute G ^ T \widehat{G}_T G T and the full-data model A ( S ) A(S) A ( S ) in the faithfulness gap of Figure 1 come from S r e f S_{\mathrm{ref}} S ref rather than S s S_s S s . We did not retrain a reference trajectory per seed because of the cost (5 × 5 \times 5 × the most expensive step).
More empirical details
For each (dataset, architecture) pair we train one full-data model on the pool of seed 42 with the protocol of § 6 , and store the parameters at the end of selected epochs, together with the step index and learning rate η k \eta_k η k of that epoch. The same reference trajectory is used for all five seeds (see caveat in Section G.1).
We use the SGD objective: w k = η k / ∑ j η j w_k = \eta_k / \sum_j \eta_j w k = η k / ∑ j η j , where η k \eta_k η k is the cosine-schedule learning rate of the epoch e k e_k e k in which checkpoint k k k was saved, η k = 1 2 η 0 ( 1 + cos ( π ( e k − 1 ) / 300 ) ) \eta_k = \frac{1}{2}\eta_0(1 + \cos(\pi(e_k - 1)/300)) η k = 2 1 η 0 ( 1 + cos ( π ( e k − 1 ) /300 )) with η 0 = 0.01 \eta_0 = 0.01 η 0 = 0.01 . The weights are normalized to sum to one, so G ^ T \widehat{G}_T G T is a weighted mean over checkpoints. This rescales G ^ T \widehat{G}_T G T but changes no swap decision.
Checkpoints used for selection. For τ \tau τ checkpoints we take the stored epochs closest to τ \tau τ points equally spaced in optimizer-step time between epoch 1 and epoch 300. Hence τ = 1 \tau= 1 τ = 1 gives the epoch-1 checkpoint, and τ = 4 \tau= 4 τ = 4 gives approximately epochs 1, 100, 200, 300. Baseline comparison experiments (Figure 2 ) use τ = 1 \tau= 1 τ = 1 ; Section J varies τ \tau τ .
Empirical correlation between faithfulness error and trajectory gradient discrepancy
Below, we provide results for other settings showing the correlation between the faithfulness error and the estimate of the proxy, G ^ T ( I ) \sqrt{\widehat{G}_T(I)} G T ( I ) . We use similar settings as those explained in § 6 and Section G. The estimate of G T G_T G T is computed using a single training run on 45,000 sampled points from the training dataset.
Reference trajectory. For each of the six (dataset, architecture) pairs, we train one model on the 45,000 sampled training points using SGD, batch size 128, initial learning rate 0.01 annealed by a cosine schedule over 300 epochs, and we store the parameters θ k \theta_k θ k . This run plays the role of A ( S ) A(S) A ( S ) and is the only training on S S S that the proxy needs.
Estimating the discrepancy. For a candidate subset I I I we evaluate
G ^ T ( I ) = ∑ k w k ∥ ∇ L S I ( θ k ) − ∇ L S ( θ k ) ∥ 2 2 \widehat{G}_T(I) = \sum_k w_k \left\lVert\nabla L_{S_I}(\theta_k) - \nabla L_S(\theta_k) \right\rVert_2^2 G T ( I ) = k ∑ w k ∥ ∇ L S I ( θ k ) − ∇ L S ( θ k ) ∥ 2 2
the sum running over the stored checkpoints, with weights w k ∝ η k w_k \propto\eta_k w k ∝ η k normalised to sum to one. The two mean gradients are computed exactly, over all trainable parameters and over the whole pool. Examples are viewed through the deterministic test transform and the network is in evaluation mode, so each per-example gradient is a well-defined function of θ k \theta_k θ k alone. This replaces the expectation over μ t S \mu_t^S μ t S by its value at a single realised trajectory.
Candidate subsets and faithfulness error. The points of each panel are the subsets returned by the selection methods of § 6 , including swap-descent variant, at retention fraction 0.1 and over the 5 seeds; one point is one (method, seed) pair, with no averaging. Every subset is retrained from a shared initialization with the same optimizer, schedule and number of epochs as the reference run, and the official test set is evaluated once, after the final epoch. Each panel fixes the dataset, the architecture and the selection ratio is set to 10%.
Results. Figure 7 reports the Pearson correlation between the estimated faithfulness and the estimated G ^ T \widehat{G}_T G T , pooled over methods and seeds within each panel. It exceeds 0.70 in all six settings, so across architectures and datasets the subsets with the largest trajectory gradient discrepancy are also the ones whose retrained model departs most from full-data training.
Figure 7. Correlation between the empirical faithfulness gap and the estimate of the proxy G ^ T ( I ) / 2 \sqrt{\widehat{G}_T(I)/2} G T ( I ) /2 . Consistent correlation is shown across datasets (CIFAR10, first row, CIFAR100 second row) and architecture. The zoomed insets show the boxed region.
Gradient-Swap with warm starts
In order to show the benefit of minimizing the proxy G ^ T \widehat{G}_T G T as a way to improve the faithfulness of a subset, we ask whether, starting from a subset obtained by a given data selection method—we pick GraphCut (one of the best-performing baselines), Random, Herding, and EL2N (one of the least-performing ones)—applying swaps of Gradient Swap improves both the G ^ T \widehat{G}_T G T objective and downstream accuracy. As expected from Theorem 4.6 , the swaps lower G ^ T \widehat{G}_T G T for every starting selector, even though τ = 10 \tau=10 τ = 10 checkpoints are used for the swaps and all 300 are used for evaluation. The downstream accuracy results reflect the one-sided nature of Corollary 4.2 : once a selector already lies inside the low-G ^ T \widehat{G}_T G T faithfulness envelope (GraphCut, Herding, and Random), the upper bound is already small and further reducing G ^ T \hat{G}_T G ^ T leaves test accuracy unchanged within one standard deviation. Conversely, for EL2N, whose subsets severely violate trajectory fidelity (G ^ T = 81.22 \hat{G}_T = 81.22 G ^ T = 81.22 ), just K = 500 K=500 K = 500 swaps reduce G ^ T \hat{G}_T G ^ T by 16% and improve test accuracy by 2.6 percentage points, although it remains far from the other selectors. This confirms that G ^ T \hat{G}_T G ^ T acts as a one-sided safety certificate: it is most informative for diagnosing and repairing unfaithful subsets, whereas further decreases in the low-discrepancy regime do not translate into additional accuracy gains.
Table 2 : Warm start of full-network Gradient Swap on cifar10 / resnet18 at 10% of the pool. Accuracy is the last logged test epoch. G T G_T G T is the full-network objective on every reference checkpoint. The after columns are exact full-network Gradient Swap at τ = 10 \tau= 10 τ = 10 started from the baseline subset. Mean and standard deviation are over 5 seeds.
Table 2.
Table 3: Test accuracy (%) of full-network Gradient Swap on CIFAR10. Values are mean ± \pm ± standard deviation over seeds.
Table 3.
Ablation study on the number of used checkpoints
Tables 3 and 4 show the results of the checkpoint ablation on CIFAR10 and CIFAR100. Using the same setting as the aforementioned experiments, we can see that the number of used checkpoints does not consistently affect test accuracy for three architectures, motivating the use of τ = 1 \tau= 1 τ = 1 as a computational simplification for the estimation of G T G_T G T .
Table 4: Test accuracy (%) of full-network Gradient Swap on CIFAR100. Values are mean ± \pm ± standard deviation over seeds.
Table 4.
Johnson-Lindenstrauss Embeddings Ablation
Following Xia et al. [37 ] , we attempt dimensionality reduction techniques (Johnson Lindenstrauss Embeddings (Johnson et al., [15 ] )) on the gradient to reduce the computational and storage cost of algorithm 1. Full-network Gradient Swap stores one aggregate gradient per checkpoint. A count sketch of width p p p replaces each aggregate by its image in R p \mathbb{R}^{p} R p , and the swap test is exact for that sketched objective. In Table 5 and Table 6 , we compare p ∈ { 1024 , 2048 , 4096 } p \in\{1024, 2048, 4096\} p ∈ { 1024 , 2048 , 4096 } with the exact aggregates p = d p = d p = d on CIFAR-10 with ResNet-18 (d ≈ 10 7 d \approx10^{7} d ≈ 1 0 7 ), at checkpoint counts τ ∈ { 1 , 4 } \tau\in\{1, 4\} τ ∈ { 1 , 4 } and subset fractions 10%, 20%, 40%, and 50%. Each entry is the mean test accuracy and the standard deviation over five seeds. The sketch does not change the selected subset’s accuracy. At every fraction and both values of τ \tau τ , the three sketched runs sit on the exact run: the largest gap is 0.60 points (τ = 1 \tau= 1 τ = 1 , p = 2048 p = 2048 p = 2048 , 10%), and that gap is smaller than the seed standard deviation of either run. From 40% upward the gaps are about 0.1 points. Width 1024 is already enough. Increasing p p p to 2048 or 4096 does not produce a further gain, and the same match holds when the trajectory grows from one checkpoint to four. The embedding can therefore be used in place of the exact aggregates.
Table 5: Test accuracy (%) on CIFAR-10 with ResNet-18 at τ = 1 \tau= 1 τ = 1 . p = d p = d p = d is the exact aggregate. Mean and standard deviation over five seeds.
Table 5.
Table 6. Test accuracy (%) on CIFAR-10 with ResNet-18 at τ = 4 \tau=4 τ = 4 . p = d p=d p = d is the exact aggregate. Mean and standard deviation over five seeds.
Selected examples for each selection method
For each dataset and architecture we show the training images selected at 10% of the pool (seed 42). Each row is one method: Gradient Swap using full-network gradients and a single checkpoint (τ = 1 \tau=1 τ = 1 ), then Random, Herding, Moderate, EL2N, MoSo, GraphCut, and Facility Location. From that method’s saved subset we draw six examples without replacement. The stored indices are positions in the 90% training pool; we map them back to the original training set by replaying the same seed-42 split, and we display the raw images with no crop, flip, or normalization. The label under each image is its class.
Figure 8 (PDF p. 33). CIFAR-10 / VGG-16, 10% subset, seed 42
Figure 9 (PDF p. 34). CIFAR-10 / Inception, 10% subset, seed 42
Figure 10 (PDF p. 35). CIFAR-10 / ResNet-18, 10% subset, seed 42
Figure 11 (PDF p. 36). CIFAR-100 / VGG-16, 10% subset, seed 42
Figure 12 (PDF p. 37). CIFAR-100 / Inception, 10% subset, seed 42
Figure 13 (PDF p. 38). CIFAR-100 / ResNet-18, 10% subset, seed 42. Gradient Swap: willow tree, table, spider, cup, leopard, orange. Random: snail, can, bus, lamp, rabbit, clock. Herding: raccoon, plain, mountain, spider, tractor, seal. Moderate: can, maple tree, orange, pickup truck, aquarium fish, wardrobe. EL2N: leopard, otter, television, squirrel, possum, seal. MoSo: table, pickup truck, mushroom, flatfish, caterpillar, oak tree. GraphCut: shrew, pear, kangaroo, chair, cup, orange. Facility Location: willow tree, lizard, sunflower, lawn mower, man, lamp.