Why Less is More (Sometimes): A Theory of Data Curation Elvis Dohmatob, Mohammad Pezeshki, Reyhane Askari-Hemmat Abstract This paper introduces a theoretical framework to resolve a central paradox in modern machine learning: When is it better to use less data? This question has become critical as classical scaling laws suggesting “more is more” (Sun et al., 2025) are challenged by methods like LIMO (“less is more”) and s1 (Ye et al., 2025; Muenighoff et al., 2025), which achieve superior performance with small, aggressively curated datasets. Here, we study data curation strategies where an imperfect oracle selects the training examples according to their difficulty and correctness. Our results provide exact scaling law curves for test error under both label-agnostic and label-aware curation rules, revealing when and why keeping only a subset of data can improve generalization. In contrast to classical scaling laws, we show that under certain conditions, small curated datasets can outperform full datasets, and we provide analytical conditions for this by deriving precise phase transition curves tied to data size and quality. We validate these theoretical claims with empirical results on ImageNet, confirming our predictions about when curation improves accuracy and can even mitigate model collapse. Furthermore, our framework provides a principled explanation for the contradictory curation strategies recently observed in LLM mathematical reasoning. † † affiliation: Concordia University † † affiliation: FAIR at Meta † † affiliation: Mila–Quebec AI Institute † † correspondence: Elvis Dohmatob elvis.dohmatob@concordia.ca 1 Introduction Despite remarkable advances in large language models (LLMs) and other foundation models, training them remains highly inefficient, often requiring hundreds of billions of tokens. A key reason lies in how training data is used: standard training procedures treat all examples equally, regardless of their informativeness. Yet not all data points contribute equally to learning; while some accelerate progress, others are redundant or even detrimental ( 39 ) . This inefficiency motivates the exploration of principled data curation strategies. Recent empirical successes highlight the promise of aggressive data curation. Methods such as LIMO (Less Is More) ( 45 ) and s1 ( 31 ) show that curating compact sets of valid and challenging examples can dramatically improve reasoning performance, often with a fraction of the original data. These results stand in contrast to the traditional scaling law perspective ( 26 ; 25 ) , which suggests that simply increasing dataset size should monotonically improve generalization. The apparent contradiction between “less is more” and “more is more” ( 40 ) raises a fundamental question: under what conditions does data curation help, and when does full-data training remain optimal? In this work, our goal is not to propose another heuristic curation method, but rather to build a principled theoretical framework that explains why and when such strategies succeed. We analyze high-dimensional binary classification under pruning oracles that filter examples based on difficulty and correctness. Our theory provides exact scaling laws for test error, revealing sharp phase transitions tied to dataset size, label quality, and oracle reliability. These results establish conditions under which keeping only the hardest or easiest examples outperforms training on the full dataset. Crucially, we show how strategic curation can mitigate model collapse ( 38 ; 11 ) , where iterative self-training on noisy or synthetic data leads to catastrophic degradation. Main Contributions: • We develop a precise theoretical framework for data curation in high-dimensional learning, deriving exact scaling laws that characterize the effect of data pruning on generalization. • We demonstrate that, under realistic compute or label-quality constraints, strategically pruned datasets can outperform full datasets, thereby bending classical scaling laws. • We empirically confirm our theoretical predictions on ImageNet and connect them to recent large-scale results in LLM reasoning, providing a rigorous justification for why methods like LIMO and s1 succeed. • We show analytically that data curation can avert model collapse under label shift, establishing phase boundaries where uncurated training diverges while curated training remains stable. Together, these results reframe data curation not as a heuristic preprocessing step, but as a principled tool for stable and efficient learning. 2 Setup for Theoretical Analysis To formally analyze when “less is more” versus when “more is more”, we must first establish a precise mathematical setting, which is rich enough to capture the complexity of the problem, but simple enough to be analytically tractable. This section defines our data generation process, the model we analyze, and, most importantly, the key quantities that will allow us to distinguish between different learning regimes: the quality of the data generator and the quality of the pruning oracle . 2.1 Data, Model, and Assumptions Data Distributions. Let P_{w,A} denote the probability distribution on \mathbb{R}^{d}\times\mathbb{R} given by: (x,y)\sim P_{w,A}\quad\text{iff}\quad x\sim\mathcal{N}(0,A),\;\;y=\text{sign}(x^{\top}w). (1) The training dataset consists of n i.i.d. pairs (x_{i},y_{i}) from a distribution P_{g}=P_{w_{g},C_{g}} , where w_{g}\in\mathbb{R}^{d} and C_{g}\in\mathbb{R}^{d\times d} are the weights/labeling vector and the covariance matrix for the generative distribution (the “generator”). The true test data distribution is, however, P_{*}=P_{w_{*},\Sigma} , where w_{*}\in\mathbb{R}^{d} and \Sigma\in\mathbb{R}^{d\times d} are the true weights and covariance. In general, we consider w_{g}\neq w_{*} , corresponding to label shift and C_{g}\neq\Sigma , corresponding to covariate shift. The Model. Consider a vector \hat{w}\in\mathbb{R}^{d} defined as the solution to the convex optimization problem: \text{minimize }\frac{1}{n}\sum_{i=1}^{n}p_{i}\ell(x_{i}^{\top}w;y_{i})+\frac{\lambda}{2}\|w\|^{2},\text{ over }w\in\mathbb{R}^{d}. (2) Here, \ell(z;y):=(z-y)^{2}/2 is the squared L2 loss, \lambda>0 is a regularization parameter, and p_{i}\in\{0,1\} indicates if an example is kept. The downstream model is the linear classifier x\mapsto\text{sign}(x^{\top}\hat{w}) . Problem Eqn. 2 has the explicit solution given by: \hat{w}=RX^{\top}DY/n,\quad\text{with}\quad R:=\left(S+\lambda I_{d}\right)^{-1}\text{ and }S:=X^{\top}DX/n, (3) where X\in\mathbb{R}^{n\times d} is the design matrix, Y\in\mathbb{R}^{n} is the label vector, and D is a diagonal matrix with D_{ii}:=p_{i} , indicating which examples survive data curation. Object of Study: High-Dimensional Test Error. Our goal is to characterize the classification test error, E_{\text{test}}(\hat{w}):=\mathbb{P}(\text{sign}(x^{\top}\hat{w})\neq y) , in the high-dimensional proportionate scaling limit: n,d\to\infty,\quad d/n\to\phi\in(0,\infty). (4) The constant \phi\in(0,\infty) , also known as the parametrization rate , allows us to capture the effect of dataset size relative to the dimensionality of the problem. For simplicity of presentation of our main theoretical results and insights, we limit the analysis to the isotropic setting where the covariance matrices are identity matrices, i.e., C_{g}=\Sigma=I_{d} . More general results are deferred to the appendix. Thus, our focus here is on label shift, where the labels from the generator P_{g} might deviate from the ground-truth labels from P_{*} . 2.2 Data Curation Rules Label-Agnostic Curation. First, we consider a setting where an example (x_{i},y_{i}) is retained based only on its features x_{i} , via a pruning function q:\mathbb{R}\to\{0,1\} and an oracle pruning vector w_{o}\in\mathbb{R}^{d} : p_{i}=q(x_{i}^{\top}w_{o}). (5) This rule uses the function q to select examples based on their projection onto the oracle vector w_{o} . For instance, common strategies like “keep easy” and “keep hard” correspond to choosing q(t):=1[|t|\geq\alpha] to retain large-margin examples (far from the decision boundary) and q(t):=1[|t|\leq\alpha] to retain small-margin examples (close to the decision boundary), respectively. The notion of an example’s difficulty is thus determined by the oracle w_{o} , and the threshold \alpha>0 controls the proportion of data kept. This subsumes the setting considered in ( 39 ) . Label-aware Curation. We also analyze a more realistic data curation setting where the oracle filters for the correctness of the corresponding label as well. Here, an example (x_{i},y_{i}) is kept if its label y_{i} matches the oracle’s label y_{i}^{o} and it is deemed interesting by q : p_{i}=1\quad\text{iff}\quad y_{i}=y_{i}^{o}\;\;\text{and}\;\;q(x_{i}^{\top}w_{o})=1, (6) where y_{i}^{o}:=\sign(x_{i}^{\top}w_{o}) is the label according to the pruning oracle (not revealed to the learner!). In the practical setting of LIMO ( 45 ) and s1 ( 31 ) methods, the pruning function q might capture other heuristic rules which decides if an example is sufficiently diverse or interesting to be retained in the curated dataset. Desiderata: Importantly, our setup posits that the machine learner can only query the curation rule by submitting input/label pairs (x_{i},y_{i}) and obtaining bits p_{i}\in\{0,1\} , but has no access to the underlying pruning direction w_{o} , nor the oracle labels y_{i}^{o}=\text{sign}(x_{i}^{\top}w_{o}) . Remark 1 . The setups in 15 and 16 are a special case of Eqn. 6 . This occurs when the difficulty-based pruning is ignored ( q\equiv 1 ), meaning the curation rule retains an example if and only if its label y_{i} matches the oracle’s label y_{i}^{o} . Pruning Ratio. The fraction of data retained for learning is the pruning ratio , p:=\mathbb{E}[p_{i}]\in[0,1] . Out of n original examples, np survive curation on average. A small p corresponds to aggressive pruning, while p\to 1 means no data is discarded. 2.3 Quantifying the Quality of the Generator and the Pruning Oracle The following constants will play a crucial role in our theory: \rho:=\frac{w_{g}^{\top}Cw_{*}}{\|w_{g}\|_{C}\|w_{*}\|_{C}},\quad\rho_{*}:=\frac{w_{o}^{\top}Cw_{*}}{\|w_{o}\|_{C}\|w_{*}\|_{C}},\quad\rho_{g}:=\frac{w_{o}^{\top}Cw_{g}}{\|w_{o}\|_{C}\|w_{g}\|_{C}},\quad\tau:=\frac{\rho_{g}}{\sqrt{1-\rho_{g}^{2}}}, (7) where \|w\|_{C}:=\sqrt{w^{\top}Cw} is the Mahalanobis norm induced by the covariance matrix C . These constants measure the geometric alignment between the generator (the labeler of the training data, w_{g} ), the oracle (the pruner, w_{o} ), and the ground truth (the true labeler of the test data, w_{*} ). Geometrically, \rho , \rho_{*} , and \rho_{g} are the cosines of the angles between their respective vector pairs, while \tau is the cotangent of the angle between the pruner ( w_{o} ) and the generator ( w_{g} ). Crucially, \rho and \rho_{*} directly quantify the performance of the generator and the pruner. Their test errors are given by the simple relationship: E_{\text{test}}(w_{g})=(1/\pi)\arccos\rho\quad\text{and}\quad E_{\text{test}}(w_{o})=(1/\pi)\arccos\rho_{*}. Note that \arccos has range [0,\pi] . These constants have the following interpretation for our analysis: • Generator Quality ( \rho ): When \rho\to 1 , the generator is excellent, which we call a strong generator . When \rho<1 corresponding to label shift, it is a weak generator . • Oracle Quality ( \rho_{*} ): When \rho_{*}\to 1 , the pruning oracle is excellent and aligns well with the ground truth. The triplet (\rho,\rho_{g},\rho_{*}) will appear in our analytical descriptions of the limiting test error E_{\text{test}}(\hat{w}) . 3 Main Theory: When to Prune and When to Scale We established a precise mathematical framework in Section 2 , defining key quantities such as the data distribution, model, and curation rules. In this section, we use this framework to develop a core theory that explains when and why data pruning can improve performance by deriving exact scaling laws for test error under different data curation strategies. As we will demonstrate, our theory shows precisely how the optimal pruning strategy changes as a function of \rho . For simplicity, we present our main results for the isotropic setting where \Sigma=C_{g}=I_{d} and the pruning direction w_{o} has unit norm. General results are in the appendix. Assumption 1 (Symmetric Pruning Functions) . q is a symmetric binary-valued measurable function, i.e., q(t)=q(-t)\in\{0,1\} for all t\in\mathbb{R} . \mathcal{Q} denotes the collection of all such functions. This is a common setup that includes rules based on the absolute value of margins, such as keeping the "easiest" or "hardest" examples ( 39 ) . 3.1 Setting #1: Label-Agnostic Data Curation We first consider label-agnostic pruning, where the decision to keep an example (x_{i},y_{i}) depends only on the features x_{i} , as in Eqn. 5 . For any pruning function q\in\mathcal{Q} , we define four key constants that capture its effect on the learning dynamics: \displaystyle\begin{split}p&:=\mathbb{E}\,[q(G)],\quad\gamma:=\mathbb{E}\,[q(G)G^{2}],\quad\beta:=2\mathbb{E}\left[q(G)\varphi(\tau G)\right],\quad\tilde{\beta}:=2\mathbb{E}\left[q(G)\Phi\left(\tau G\right)G\right],\end{split} (8) where \varphi and \Phi are the pdf and cdf respectively of a standard Gaussian variable G\sim\mathcal{N}(0,1) . Note that p=p(q) defined above is just the average fraction of data kept by the pruning strategy in Eqn. 5 . Explicit formulae for the above constants are provided in the appendix (Table 3 ). The following theorem provides our first main result: an exact analytical formula for the test error. Theorem 1 (Exact Test Error) . In the limit Eqn. 4 , the test error of the model \hat{w} from Eqn. 3 is given by, \displaystyle E_{test}(\hat{w}) \displaystyle\to\frac{1}{\pi}\arccos(\frac{|m_{0}|}{\sqrt{\nu_{0}}}),\text{ where} (9) \displaystyle m_{0} \displaystyle:=\omega m(-\lambda)+\tilde{\omega}\tilde{m}(-\lambda),\quad\nu_{0}:=p\phi m^{\prime}(-\lambda)+r^{\prime}(-\lambda)-\frac{2\phi m^{\prime}(-\lambda)r(-\lambda)}{1+\phi m(-\lambda)}, \displaystyle\text{with }\omega \displaystyle:=(\rho-\rho_{g}\rho_{*}),\quad\tilde{\omega}:=\tilde{\beta}\rho_{*}, (10) where m , \tilde{m} , and r are functions explicitly determined by the constants in Eqn. 8 . In particular, m is the Stieltjes transform of a Marchenko-Pastur law, "deformed" by pruning. Refer to Appendix D for details. This theorem provides the machinery to analyze any pruning strategy q , and isolate its effect on the dynamics of the classification test error curve. This impact is entirely captured by the scalars p,\gamma,\beta , and \tilde{\beta} . Now, we use this tool to characterize the optimal choice of q . Sketch of Proof of Theorem 1 . The full proof is given in the appendix, and relies on the construction of suitable deterministic equivalents for the resolvent matrix R defined in Eqn. 3 and its square R^{2} . This allows us to calculate the limiting distribution of the “margin” yx^{\top}\hat{w} at a random test point x\sim\mathcal{N}(0,I_{d}) , and then the test error E_{test}(\hat{w}):=\mathbb{P}(yx^{\top}\hat{w}<0) . Our approach follows random matrix theory (RMT) techniques which are now prevalent in machine learning theory ( 3 ; 28 ; 9 ; 16 ) . Optimal Pruning Strategy. In the asymptotic limit Eqn. 4 , let F(q) be an error functional representing the limiting test error for a given strategy q in the data-rich, unregularized regime: \displaystyle F(q):=\lim_{\phi\to 0}\,\lim_{\lambda\to 0}\,\lim_{d,n\to\infty,\,d/n\to\phi}E_{test}(\hat{w}), (11) where \hat{w}=\hat{w}(q,n,d,\lambda,\rho_{*},\ldots) is the estimator Eqn. 3 fitted on a version of the training dataset D_{n} pruned with the pruning strategy q . The following theorem shows how the minimizer of F(q) changes based on the generator quality \rho . Theorem 2 (Optimal Pruning Strategy) . Suppose that the pruning direction w_{o} has a positive projection along the generator direction w_{g} ( \rho_{g}>0 ) and fix the pruning ratio p\in(0,1] . Let \mathcal{Q}_{p} be the set of strategies that keep a fraction p of the data. (A) If the generator is excellent ( \rho\to 1 ) and the pruner is excellent ( \rho_{*}\to 1 ), then the "keep hard" (KH) strategy uniquely minimizes the test error F(q) over \mathcal{Q}_{p} . (B) If the generator is poor ( \rho<1 ) but the pruner is excellent ( \rho_{*}\to 1 ), then the "keep easy" (KE) strategy uniquely minimizes the test error F(q) over \mathcal{Q}_{p} . Part (A) shows that for a strong model/generator that has already mastered the task, performance is refined by focusing on difficult examples—a "less is more" ( 45 ) approach. Part (B) captures the opposite scenario: for a weak model/generator, the best strategy is to keep easy examples. This less aggressive form of curation helps the model learn the basic data distribution, aligning with the "more is more" ( 40 ) principle that broader data exposure is beneficial during initial learning. This latter case is particularly relevant for mitigating model collapse, where a model trained on its own imperfect outputs acts as a poor generator ( 38 ; 12 ) . Also see Appendix C . 3.2 Setting #2: Label-aware Data Curation We now extend our analysis to the pruning rule from Eqn. 6 , inspired by methods like LIMO ( 45 ) and s1 ( 31 ) . Here, an example is kept only if an oracle deems its label to be correct and it satisfies the difficulty-based rule. This requires modifying the definitions of our key constants from Eqn. 8 . Set z_{i}:=x_{i}^{\top}w_{g} , z_{i}^{o}:=x_{i}^{\top}w_{o} , and f_{i}:=p_{i}y_{i} , where p_{i}\in\{0,1\} is as defined in Eqn. 6 . The modifications are: \displaystyle p \displaystyle:=\mathbb{E}[p_{i}],\quad\gamma:=\mathbb{E}[(y_{i}^{o})^{2}p_{i}],\quad\beta:=\mathbb{E}[\frac{\partial f_{i}}{\partial z_{i}}],\quad\tilde{\beta}:=\mathbb{E}[\frac{\partial f_{i}}{\partial z_{i}^{o}}]. (12) Expectations are over the training data and derivatives are in the distribution-theoretic sense. Explicit formulae for the above constants are provided in the appendix (Table 3 ). Theorem 3 (Test Error for Label-aware Curation) . In the limit Eqn. 4 , the test error E_{test}(\hat{w}) for label-aware curation is given by the same formula as in Theorem 1 , but using the modified constants from Eqn. 12 . Refer to the appendix for full proofs, various corollaries and their phenomenological implications. 4 Bridging Theory and Practice Our theoretical framework provides a clear principle: the optimal data curation strategy is not universal but depends on the interplay between the generator’s quality ( \rho ), the pruner’s quality ( \rho_{*} ), their alignment ( \rho_{g} ), and the amount of available data ( n ). In this section, we first validate our predictions in a controlled synthetic environment. We then use these validated principles as a lens to interpret and unify real-world results in LLM mathematical reasoning and ImageNet classification. For a comprehensive set of validations, please see Figure 4 and Appendix B . 4.1 Theory Prediction: The Interplay of Generator Quality and Data Scale We simulate four distinct learning regimes in a 2x2 grid to characterize the test error as we vary the generator’s quality ( \rho ) and the amount of available data ( n ). The left column shows a strong generator ( \rho=1 ), while the right shows a poor generator ( \rho<1 ). The top row represents a small- n regime, and the bottom represents a large- n regime. In each setting, we compare a strategic ‘‘keep hard’’ pruning strategy against a baseline ‘‘random’’ selection of the same size, where the pruner is uninformative 1 1 1 For the “keep hard” strategy, we set \rho_{g}=0.5 and \rho_{*}=\rho . The “random” strategy uses an orthogonal pruner where \rho_{*}=\rho_{g}=0 . . Figure 1 plots the test error, showing the match between our theoretical predictions and the empirical results. Figure 1: Theory Prediction across four key regimes. Test error as a function of fraction of data kept ( p=1 means keeping all the data) for “keep hard” and “random” pruning. Solid lines are theoretical predictions; dashed lines are empirical results with error bars. The plot reveals that a “more is more” strategy (optimal error at p=1) is the default, holding true for small datasets (top row) or a poor generator (right column). The bottom-left quadrant shows the crucial exception: only when data is abundant and the generator is strong does the "less is more" principle apply, with aggressive pruning yielding the lowest error. The results reveal a clear pattern for when to prune. In three of the four regimes, the test error is minimized when the pruning fraction p=1 , confirming the “more is more” ( 40 ) principle. This holds true when: • The amount of data is small (top row, both poor and strong generators). • The generator is poor, even with abundant data (bottom right). However, the bottom-left quadrant reveals the critical exception. When the data is abundant and the generator is strong ( \rho=1 ), the error is minimized at p\ll 1 . This confirms the “less is more” principle: in this specific regime, curating a small set of hard examples is the optimal strategy. 4.2 Reconciling Recent Findings in LLM Math Reasoning Our framework can interpret and unify seemingly contradictory findings in LLM mathematical reasoning. The following results are aggregated from existing literature and our theory provides a novel explanation for why different curation strategies succeed under different conditions. In this context, the generator ( w_{g} ) is the base LLM that produces reasoning traces, and its quality ( \rho ) reflects its proficiency on a specific slice of the test data. Recent methods like LIMO and s1 show that "less is more": aggressive curation of high-quality, difficult examples improves average performance on the AIME benchmark (Table 2 ). However, a paradox emerges when evaluating only on the hardest AIME questions: here, "more is more" holds true, and performance scales with the number of training examples (Table 2 ). Table 1: AIME 2024 (Average Performance) reported in 31 ; 45 . Training Data Size Pass@1 (%) 0 (Base Qwen2.5_32B) 16.5 114k (Openthinker) 50.2 59k (curated in s1) 53.3 1k (curated from pool of 59k) 56.7 Table 2: AIME (Hard-Level Questions) performance reported in 40 . Training Data Size Avg@8 (%) 0 (Base Qwen2.5_32B) 1.0 1k from OpenR1-Math 28.4 2k examples 35.4 10k examples 52.1 114k (Openthinker) 47.9 1M (Openthinker2) 64.9 Our theory resolves this cleanly: • For Average Performance , the base LLM is a strong generator (high \rho ) for the majority of problems. As predicted by our theory, the optimal strategy is to aggressively prune and "keep hard" examples to refine its already strong capabilities. • For Hard Performance , the same LLM is a weak generator (low \rho ) relative to this difficult data slice. In this regime, our theory correctly predicts that a "more is more" approach is superior, as the model needs a larger dataset to build foundational skills for these novel problems. The optimal strategy is not universal; it depends on the generator’s capability relative to the target task’s difficulty. 4.3 Curation on ImageNet: Data Scale and Model Collapse We demonstrate that the same principles apply to large-scale vision tasks. We use a pre-trained model as both the generator ( w_{g} ) and pruner ( w_{o} ) to create and select from a pseudo-labeled dataset. The strength of this generator is controlled by the size ( n ) of its initial training set. Optimal Strategy Depends on Data Scale. As predicted, the initial data size dictates the best pruning strategy. Figure 2 shows a clear crossover point: • Small n (Weak Generator): When trained on only 160K examples, the "keep easy" strategy is more effective. • Large n (Strong Generator): When trained on 1.2M examples, the "keep hard" strategy becomes superior, achieving performance close to a model trained on ground-truth labels. Figure 2: The optimal curation strategy depends on the data scale in ImageNet. A clear crossover point emerges as we vary the initial dataset size n , shifting the optimal strategy from "keep easy" to "keep hard" as the generator model becomes stronger. Strategic Pruning Prevents Model Collapse. This principle is vital for stability in iterative training. We simulate model collapse by repeatedly re-training on the model’s own pseudo-labels. Figure 3 shows that while training on all data causes performance to degrade, applying the "keep hard" strategy at each step stabilizes performance and effectively prevents collapse. This demonstrates that principled curation is crucial not only for one-shot efficiency but also for long-term stability in self-improvement loops. Figure 3: Strategic pruning prevents model collapse. Over multiple rounds of pseudo-labeling, training on all examples leads to performance degradation. In contrast, selectively training on only hard, valid examples consistently preserves performance across rounds. 5 Related Work Beating Neural Scaling Laws. The award-winning work of 39 show that pruning a training set with margin-based difficulty scores can bend neural scaling curves, delivering higher accuracy with fewer samples. More recent methods in reasoning and program-synthesis tasks—LIMO ( 45 ) and S1 ( 31 ) report an even more drastic picture: a compact set of challenging, high-quality examples drives larger gains than indiscriminate data expansion. In these pipelines the inputs (questions) are human-curated, while the outputs (answers or solutions) are generated by a large model such as R1 ( 19 ) . We provide theoretical justification for the improved scaling behavior and systematically study a simpler, yet analogous, setup through controlled experiments on ImageNet ( 10 ) . Model Collapse. Advances in generative models have led to synthetic data becoming widespread online, where it now irreversibly blends into training corpora. Recent studies have highlighted the potential for dramatic deterioration in downstream models, a phenomenon known as “model collapse" ( 37 ) . Empirical studies have demonstrated this issue in various settings ( 22 ; 29 ; 30 ; 5 ; 6 ) . Synthetic data can exacerbate biases via feedback loops ( 41 ; 44 ) , narrow content diversity ( 33 ; 20 ) , and distort underlying distributions ( 27 ) . Theoretical analysis also examines the effects of iterative training on self-generated data ( 1 ; 4 ; 11 ; 34 ) . Notably, 13 warns that model collapse signifies a break in customary neural scaling laws ( 26 ; 25 ) , where increasing synthesized data volume does not enhance performance as effectively as scaling with human-generated data. As a result, recent works have focused on avoiding or correcting synthetic data to prevent model collapse. 18 propose using a correction function informed by expert knowledge to modify the synthesized data. 2 leverage a model trained on synthetic data as negative guidance for diffusion models. 46 employ the confidence score and an AI detection classifier to discard synthesized data. In contrast, we propose leveraging the synthesized data through strategic selection techniques. We also note the approach proposed by 17 , which suggests accumulating multiple versions of the training dataset over time so that their union, unlike the latest version alone, retains crucial information about the ground truth distribution of the data. While this is an interesting direction, we believe it may face practical limitations as both models and datasets continue to scale over time. Building on the recent works of 15 ; 16 which assume a pruning oracle that can only guess which examples from the training data have correct labels, we propose and analyze a more general setup covering oracles which can also assess the difficulty of example. Benefits of Synthesized Data. Synthetic data holds great potential, as it is much easier and cheaper to scale compared to human-labeled data. Numerous empirical studies have demonstrated the benefits of synthesized data across a wide range of settings. Common practices include cases where the downstream task slightly differs from that of the data-generating model ( 7 ) , where the generating model is significantly stronger than the consuming one ( 23 ) , or when better prompt engineering and external information are utilized ( 36 ; 24 ; 32 ) . Data selection is already employed in some domains, particularly in code generation and mathematics, where natural verifiers such as compilers, solutions, or heuristic verifiers exist. For instance, 21 generate synthesized code and filter out incorrect samples. 43 use conversational metrics to filter synthetic dialogue data. 42 utilize a symbolic deduction engine to verify correct solutions for Olympiad geometry problems. 35 apply a final answer verifier to distinguish between good and bad synthetic data. Although verifiers are used in these cases, their effects on performance have not been systematically explored, especially in terms of how different types of verifiers influence outcomes. 6 Concluding Remarks We put forward a principled view of aggressive data curation, demonstrating that the striking results from systems like LIMO and s1 are not coincidences but follow from fundamental properties of learning with pruned data. By supplying a clean theoretical lens—validated on synthetic data and ImageNet, and shown to explain phenomena in LLMs—we give practitioners a clearer picture of when to discard data and why this can stabilize training and improve generalization. In doing so, we shift the focus from a "more is always better" mindset toward a more evidence-based, data-centric workflow. Furthermore, our framework explains how principled curation can mitigate model collapse 38 , a phenomenon characterized by a shift in scaling laws 13 ; 11 ; 12 . By revealing the stabilizing role of a strong pruning oracle, our findings also provide a theoretical basis for recent empirical successes in this area 15 . Future Directions. We see three immediate avenues for extending this work: (i) Analysis of non-linear models. Extending the theory to random-feature and kernel regimes—or to the infinite-width neural tangent kernel—would bridge the gap to practical deep learning architectures. (ii) Adaptive curation loops. Incorporating iterative re-scoring and re-training would capture the feedback dynamics used in modern self-distillation and RLHF pipelines. (iii) Broader evaluation. Testing theory-guided pruning on diverse modalities (text, code, speech) and assessing its impact on fairness, privacy, and energy consumption will clarify when and how “less is more” in large-scale ML. We hope this work provides a rigorous starting point for these efforts and for the principled design of future data-centric training pipelines. Appendix for “Why Less is More (Sometimes): A Theory of Data Curation” Appendix A Experimental Details for ImageNet We now provide details for the experimental results presented in Section 4.3 of the manuscript. A.1 Dataset All experiments are conducted on the ImageNet-1K ( 10 ) dataset, which contains approximately 1.2 million training images and 50,000 validation images across 1,000 classes. For experiments with reduced dataset sizes, we use random subsampling to generate smaller training sets at various fractions (e.g., 50%, 25%, 12.5%) of the full dataset. A.2 Model Architecture We use the Vision Transformer (ViT-B/16) ( 14 ) as our primary backbone, implemented via the MMPretrain framework ( 8 ) . The model uses a patch size of 16 and an input resolution of 224\times 224 . We apply a drop path rate of 0.1 and label smoothing with a smoothing value of 0.1 in the classification head. During training, we apply data augmentation techniques including Mixup ( \alpha=0.8 ) and CutMix ( \alpha=1.0 ). A.3 Training Setup All models are trained using the AdamW optimizer. The learning rate is scaled with global batch size according to the linear scaling rule. For ViT experiments, the base learning rate is 1\times 10^{-4}\times\frac{\text{batch size}}{256} , with a weight decay of 0.3, \epsilon=1\times 10^{-8} , and \beta=(0.9,0.95) . To ensure fairness across dataset sizes, we adjust the number of training epochs inversely proportional to the dataset fraction, so that the total number of iterations remains constant. Training is performed on 4 nodes, each with 8 NVIDIA H100 GPUs (total 32 GPUs), using PyTorch’s Distributed Data Parallel (DDP) via SLURM. The batch size per GPU is 128. We use synchronized batch normalization and standard augmentations including random resized crops, horizontal flips, RandAugment, and random erasing. Models are evaluated on the standard ImageNet-1K validation set using top-1 accuracy. Appendix B Empirical Confirmation of Our Theoretical Formulae . We validated our framework through extensive simulations and comparison with theory, summarized in Figure 4 . Synthetic datasets were generated under the model of Section 2 , with d=200 , varying sample size n , pruning fraction p , and generator angle \rho . Logistic regression with \lambda=10^{-6} was trained on curated subsets, and error was measured as the angular deviation between learned and true weights. Figure 4: Validation of theoretical error predictions against empirical simulations. (A) Scatter plot of theory vs. empirical error across 15 configurations, with diagonal = perfect agreement. (B–D) Parameter sweeps for pruning fraction, sample size, and generator angle. (E) Configuration-wise comparisons. All results use logistic regression with \lambda=10^{-6} . Coverage. We tested 15 parameter settings ( n\in\{500,1000,2000\} , p\in\{0.2,0.5,0.8\} , \rho\in\{0,\pi/12,\pi/6,\pi/4\} , keep-easy vs. keep-hard), spanning both typical and extreme regimes. Agreement. Theoretical and empirical results matched closely: mean relative error 1.8\% , all <5\% . Bland–Altman analysis showed mean difference 0.0019 with 95% limits of agreement [-0.0039,0.0077] . Sweeps and Landscapes. Parameter sweeps confirmed that theory captures observed non-monotonic pruning effects, power-law scaling with n , and angular dependence. Two-dimensional landscapes (sample size \times pruning fraction) showed near-identical patterns, with maximum absolute differences <0.01 . Statistical Checks. Empirical error distributions (50 runs) centered tightly around theoretical predictions, and theory lay within 95% confidence intervals across all tested settings. Robustness. Agreement held across configurations, including edge cases ( \rho=0 , extreme pruning), indicating the framework captures the essential mechanisms. Implication. These results establish that our theory accurately predicts generalization under pruning in high-dimensional linear classification, providing a reliable tool for analyzing and optimizing data curation strategies. B.1 Experiments for Label-Agnostic Curation Rule Eqn. 5 As promised in the main manuscript, Figure 5 presents results on toy data, with curation done according to the label-agnostic rule Eqn. 5 . (a) Beating scaling laws. (b) Mitigating model collapse due to label shift. Figure 5: Effect of Label-agnostic curation rule Eqn. 5 as proposed in ( 39 ) . B.2 Which is Better, "Keep Easy Examples" of "Keep Hard Examples"? See Figures 6 and 7 . (a) Label-agnostic curation rule Eqn. 5 (proposed in ( 39 ) ) (b) Label-aware curation rule Eqn. 6 Figure 6: Beating scaling laws. Solid lines are experiments; broken lines are our theoretical predictions (Theorem 1 and Theorem 3 ). For this experiment, the angle between generator labeling vector w_{g} is perfect, i.e w_{g}=w_{*} , the ground-truth. Notice the perfect agreement between theory and experiment. (a) Label-agnostic curation rule Eqn. 5 (proposed in ( 39 ) ) (b) Label-aware curation rule Eqn. 6 Figure 7: Mitigating model collapse. Solid lines are experiments; broken lines are our theoretical predictions (Theorem 1 and Theorem 3 ). For this experiment, the angle between generator labeling vector w_{g} and ground-truth w_{*} is \pi/20 , thus simulating an imperfect generator. Notice the perfect agreement between theory and experiment. The data is Gaussian, generated according to Eqn. 1 with C=I_{d} (covariance matrix of samples, under the generators distribution) and \Sigma=I_{d} (ground-truth covariance matrix). The sample size n sweeps the range 10 through 10^{6} in log-scale, while the input dimension fixed to d=200 . The data curation is done according to the Label-aware rule Eqn. 6 . The estimator \hat{w} defined in Eqn. 3 is computed using Scipy’s linear algebra functions operations (from the "linalg" module therein), with regularization parameter fixed at \lambda=10^{-6} . The classification test error E_{test} is defined as: \displaystyle\begin{split}E_{test}(\hat{w})&:=\mathbb{E}\,[\ell_{0/1}(\sign(x^{\top}\hat{w}),y)]=\mathbb{P}(\sign(x^{\top}\hat{w})\neq y).\end{split} (13) . The pruning direction w_{o} in Eqn. 6 is chosen to make an angle \theta=0 (perfect pruning direction) or \theta=\pi/10 (poor pruning direction) with the ground-truth labeling vector w_{*}=(1,0,\ldots,0) . For Figure 5 (a) ("beating neural scaling laws"), the labeling vector w_{g}\in\mathbb{R}^{d} for the generator equals that of the ground-truth. Thus, the generator is taken to be perfect, a setting also considered in ( 39 ) . For Figure 5 (b) ("mitigating model collapse"), the generator is imperfect: its labeling vector w_{g} makes an angle \pi/5 with the ground-truth w_{*} . This imperfection simulates the model collapse phenomenon ( 38 ; 11 ; 13 ; 15 ; 12 ) . Appendix C Results in the Regression Setting C.1 Theoretical Setup As promised in the main paper, we now turn to the case of regression, where the label variable y in the data distribution Eqn. 1 is now given by \displaystyle y=x^{\top}w_{*}+\eta, (14) where \eta\sim\mathcal{N}(0,\sigma^{2}) is a noise variable independent of the covariates x . The test error of the estimator \hat{w} is now measured by \displaystyle E_{reg}(\hat{w}):=\mathbb{E}_{(x,y)\sim P_{*}}[(x^{\top}\hat{w}-x^{\top}w_{*})^{2}]-\sigma^{2}. (15) C.2 Main Result for Regression Define the following auxiliary quantities \displaystyle\begin{split}w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}&:=(w_{g}^{\top}w_{o})w_{o},\,w_{g}^{\perp}:=w_{g}-w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}},\,\epsilon:=w_{g}-w_{*},\,a:=\epsilon^{\top}w_{g}^{\perp},\,b:=\epsilon^{\top}w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}},\,c^{2}:=\|\epsilon\|^{2}.\end{split} (16) Thus, w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}} is the component of w_{g} pointing in the direction of the pruning vector w_{o} and w_{g} is the perpendicular component. c^{2} measures the disparity between the generative and the ground-truth labeling vectors w_{g} and w_{*} respectively. It is clear that \displaystyle\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2} \displaystyle=\rho_{g}^{2}\|w_{g}\|^{2},\quad\|w_{g}^{\perp}\|^{2}=(1-\rho_{g}^{2})\|w_{g}\|^{2}, (17) \displaystyle a \displaystyle=\|w^{\perp}\|^{2}-\|w_{g}\|(\rho-\rho_{g}\rho_{*}),\quad b=\|w^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}-\|w_{g}\|\rho_{g}\rho_{*}, (18) where \rho , \rho_{g} , and \rho_{\star} are as defined in Eqn. 8 . The following is one of our main contributions. Theorem 4 . In the limit Eqn. 4 , the regression test error of the model \hat{w} defined in Eqn. 3 is given by \displaystyle\begin{split}E_{reg}(\hat{w})&\to B+V+{\color[rgb]{0,0,0}c^{2}-2\lambda\cdot(m(-\lambda)a+\tilde{m}(-\lambda)b)},\\ \text{with }B&:=\lambda^{2}\cdot\left(m^{\prime}(-\lambda)\|w_{g}^{\perp}\|^{2}+\tilde{m}^{\prime}(-\lambda)\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}\right),\quad V:=\sigma^{2}\phi\bar{m}^{\prime}(-\lambda).\end{split} (19) Universality. Note that for a fixed pruning rate p\in(0,1] and pruning direction w_{o} , the specific choice of pruning strategy q\in\mathcal{Q} used only enters the picture via \gamma=\gamma(q) , defines in Eqn. 8 . Two pruning strategies with the same value of \gamma induces exactly the same test error dynamics E_{reg} in the high-dimensional limit Eqn. 4 . Unregularized Regime. We now consider our theory in the limit \lambda\to 0 , in which case the estimator \hat{w} defined in Eqn. 3 reduces to the least-squares estimate for w_{*} , namely \hat{w}={X^{\prime}}^{\dagger}Y^{\prime} , where (X^{\prime},Y^{\prime}) is the pruned training dataset, i.e the nonzero rows of (DX,DY) . Corollary 1 . In the limit Eqn. 4 then \lambda\to 0 , it holds that E_{reg}\to L , where (A) If \phi

p , then with c_{0}:=1-p/\phi and c_{1}=\gamma/\phi+c_{0}=1-(p-\gamma)/\phi , we have L=\dfrac{\sigma^{2}}{\phi-p}+(\|w_{g}^{\perp}\|^{2}+\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}/c_{1})c_{0}+{\color[rgb]{0,0,0}c^{2}-2\left(a+b/c_{1}\right)c_{0}}. Note that when p=1 (corresponding to no pruning), the above result recovers one of the main results of 12 , namely, their Corollary 1. The following result is yet another important consequence. Corollary 2 . In the noiseless setting \sigma=0 , the following hold: \displaystyle\lim_{\phi\to 0}\lim_{\lambda\to 0}\lim_{\begin{subarray}{c}d,n\to\infty\\ d/n\to\phi\end{subarray}}E_{reg}(\hat{w})=\|w_{*}-w_{g}\|^{2}=c^{2}\,\,\forall p\in(0,1], \displaystyle\lim_{\phi\to 0}\inf_{p\in(0,1]}\lim_{\lambda\to 0}\lim_{\begin{subarray}{c}d,n\to\infty\\ d/n\to\phi\end{subarray}}E_{reg}(\hat{w})=\begin{cases}\|w_{*}-w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}0 and pruning rate p\in[0,1] . Lemma 1 . For every z=-\lambda<0 , m(z) is the unique positive solution to the fixed-point equation Eqn. 33 , and is given explicitly by formula \displaystyle m(z)=\frac{p-\phi-z-\sqrt{(p-\phi-z)^{2}-4\phi z}}{2\phi z}. (32) Alternatively, m(z) defined in Eqn. 32 unique positive solution to the fixed-point equation: \displaystyle\frac{1}{m}=-z+\frac{p}{1+\phi m},\text{ with }z:=-\lambda. (33) Thus Lemma 1 shows that m(z) is the Stieltjes transform of the limiting spectral density of the resolvent matrix R appearing in Eqn. 3 , and has the property (among many others) that d^{-1}\operatorname{tr}R\to m(z) in the limit Eqn. 4 . It represents a somewhat distorted Marchenko-Pastur law; indeed, the classical MP corresponds to p\to 1 (i.e. no pruning). Furthermore, it is not hard to see that \displaystyle\bar{m}(z)\equiv m(z)\equiv\delta(z)/\phi (34) in this case. Proof of Lemma 1 . Indeed, observe that in the isotropic case the equation Eqn. 29 reduces to p-\phi-t(z)=\phi z/(t(z)-z) , or equivalently \displaystyle 0=\phi z+(t(z)-p+\phi)(t(z)-z)=t(z)^{2}-(p-\phi+z)t(z)+pz. The discriminant of this quadratic equation evaluates to \displaystyle(p-\phi+z)^{2}-4pz \displaystyle=(p-\phi-z+2z)^{2}-4pz \displaystyle=(p-\phi-z)^{2}+4z^{2}+4z(p-\phi-z)-4pz \displaystyle=(p-\phi-z)^{2}-4\phi z, and so because z=-\lambda<0 , the positive solution is \displaystyle t(z)=\frac{p-\phi+z+\sqrt{(p-\phi-z)^{2}-4\phi z}}{2}. (35) We deduce that \displaystyle m(z) \displaystyle=\frac{1}{t(z)-z}=\left(\frac{p-\phi-z+\sqrt{(p-\phi-z)^{2}-4\phi z}}{2}\right)^{-1} \displaystyle=2\cdot\frac{p-\phi-z-\sqrt{(p-\phi-z)^{2}-4\phi z}}{(p-\phi-z)-((p-\phi-z)^{2}-4\phi z)} \displaystyle=\frac{p-\phi-z-\sqrt{(p-\phi-z)^{2}-4\phi z}}{2\phi z}, which is precisely the formula given in Eqn. 33 . ∎ Spectral Functions. Define the following auxiliary functions: \displaystyle\begin{split}\bar{m}(z)&:=zm(z),\quad s(z):=\frac{\gamma}{1+\phi m(z)},\quad\tilde{m}(z):=\frac{1}{s(z)-z},\quad r(z):=\beta^{2}m(z)+\tilde{\beta}^{2}\tilde{m}(z),\end{split} (36) where the constants \tilde{\beta} and \beta are as defined in Eqn. 8 . Notice that r is (proportional to) a convex combination of m and \tilde{m} . We will be needing the derivatives of m^{\prime} , \bar{m}^{\prime} , \tilde{m}^{\prime} , and r^{\prime} . This is the purpose of the next lemma. Lemma 2 . We have the following identities: \displaystyle m^{\prime}(z) \displaystyle=\frac{m(z)^{2}}{1-(1+\bar{m}(z))^{2}\phi/p},\quad\bar{m}^{\prime}(z)=\frac{p}{(z+\phi\bar{m}(z))^{2}/\bar{m}(z)^{2}-p\phi}=\frac{p}{(\phi+1/m(z))^{2}-p\phi}, \displaystyle\tilde{m}^{\prime}(z) \displaystyle=\tilde{m}(z)^{2}\left(\frac{\gamma\phi m^{\prime}(z)}{(1+\phi m(z))^{2}}+1\right),\quad r^{\prime}(z)=\beta^{2}m^{\prime}(z)+\tilde{\beta}^{2}\tilde{m}^{\prime}(z). The following result then follows directly from Proposition 1 . Corollary 3 . In the isotropic setting, we have the following deterministic equivalents: \displaystyle R \displaystyle\simeq\bar{R},\text{ with }\bar{R}=m(z)\Pi^{\perp}+s(z)\Pi, (37) \displaystyle R^{2} \displaystyle\simeq m^{\prime}(z)\Pi^{\perp}+\tilde{m}^{\prime}(z)\Pi. (38) where \tilde{m}(z):=1/(s(z)-z) , s(z)=\gamma/(1+\phi m(z)) , and \gamma\geq 0 is as given in Eqn. 8 . D.3 Test Error Representation: The Classification Setting WLOG, suppose henceforth that \bar{w}_{g}:=C^{1/2}w_{g} , \bar{w}_{o}:=C^{1/2}w_{o} , and \bar{w}_{*}:=C^{1/2}w_{*} are unit vectors in \mathbb{R}^{d} . Let u=\bar{w}_{o} and let v be its completion to an orthonormal basis for the span of \bar{w}_{o} and \bar{w}_{g} (if \bar{w}_{o} and \bar{w}_{g} are parallel, i.e if \rho_{g}=\pm 1 , we simply set v=0 ). Define c\in\mathbb{R}^{d} by \displaystyle c:=\mathbb{E}[p_{i}y_{i}x_{i}], (39) for a random training data point (x_{i},y_{i})\sim P_{g} and corresponding selection/no select bit p_{i}\in\{0,1\} (e.g, p_{i} is as given in Eqn. 5 in the case of label-agnostic data curation and Eqn. 6 in the case of Label-aware data pruning). Also define p=p(q)\in[0,1] and \gamma=\gamma(q)\geq 0 by \displaystyle p=\mathbb{E}[p_{i}],\quad\gamma:=\mathbb{E}[(x_{i}^{\top}w_{o})^{2}p_{i}]. (40) Lemma 3 . It holds that c=\beta_{1}C^{1/2}u+\beta_{2}C^{1/2}v , with the \beta_{k} ’s as given in Table 3 . Also, the constants p and \gamma defined in Eqn. 40 are as given in the table. Curation p(q) \gamma(q) \beta_{2}(q) \beta_{1}(q) Label-agnostic \mathbb{E}[q(G)] \mathbb{E}[q(G)G^{2}] 2\mathbb{E}[q(G)\varphi(\tau G)] 2\mathbb{E}[q(G)\Phi(\tau G)G] Label-aware \mathbb{E}[q(G)\Phi(\tau|G|)] \mathbb{E}[q(G)\Phi(\tau|G|)G^{2}] \mathbb{E}[q(G)\varphi(\tau G)] \mathbb{E}[q(G)\Phi(\tau|G|)|G|] Table 3: Fundamental constants. Here, q\in\mathcal{Q} is any even/symmetric pruning function and G\sim\mathcal{N}(0,1) , with pdf \varphi and cdf \Phi . Recall that \tau:=\rho_{g}/\sqrt{1-\rho_{g}^{2}} , and we use the identification \beta\to\beta_{2} , \tilde{\beta}\to\beta_{1} . Note that taking q\equiv 1 on the second row corresponds to the setup of 15 and 16 . We are now ready to state our main results, which is a generalization of Theorem 1 and 3 . Proposition 2 . Let c\in\mathbb{R}^{d} be as defined in Eqn. 39 . For a random test point (x,y)\sim P_{*} , we have the following high-dimensional representation (where G_{1} and G_{2} are iid from \mathcal{N}(0,1) ): \displaystyle yx^{\top}\hat{w} \displaystyle\overset{L}{\to}m|G_{1}|+\sqrt{\nu-m^{2}}G_{2},\text{ with } (41) \displaystyle m \displaystyle\simeq\frac{m_{0}}{1+\delta},\quad m_{0}:=\frac{c^{\top}\bar{R}\Sigma w_{*}}{\|\Sigma^{1/2}w_{*}\|}, (42) \displaystyle\nu \displaystyle\simeq\frac{\nu_{0}}{(1+\delta)^{2}},\quad\nu_{0}:=\frac{p}{n}\operatorname{tr}\Sigma C^{\prime}+c^{\top}\Sigma^{\prime}c-\frac{2c^{\top}\bar{R}c}{1+\delta}\frac{1}{n}\operatorname{tr}\Sigma C^{\prime}, (43) \displaystyle\bar{R} \displaystyle:=\mathbb{E}[R],\quad C^{\prime}:=\mathbb{E}[RCR],\quad\Sigma^{\prime}:=\mathbb{E}[R\Sigma R], (44) where \delta=\delta(-\lambda)>0 is as defined by the fixed-point equations Eqn. 25 . Furthermore, it holds that \displaystyle E_{test}(\hat{w}):=\mathbb{P}(yx^{\top}\hat{w}\leq 0)\to\frac{1}{\pi}\arccos(|m_{0}|/\sqrt{\nu}_{0}). (45) Remark 2 . Note that the above result is valid for any curation strategy which maps easy training example (x_{i},y_{i}) to a prune/no prune bit p_{i}\in\{0,1\} , in an iid fashion. The choices Eqn. 5 (label-agnostic) and Eqn. 6 (Label-aware) are but particular cases. Appendix E Proof of Proposition 2 For a random test point (x,y)\sim P_{*} , we can write yx^{\top}\hat{w}=yz^{\top}\Sigma^{1/2}\hat{w}=sign(z^{\top}\Sigma^{1/2}w_{*})z^{\top}\Sigma^{1/2}\hat{w}. Write \Sigma^{1/2}\hat{w}=\alpha\Sigma^{1/2}w_{*}+r , where r=\Sigma^{1/2}\hat{w}-\alpha\Sigma^{1/2}w_{*} and \alpha\geq 0 is to be determined. Observe that r is perpendicular to \Sigma^{1/2}w_{*} iff r^{\top}\Sigma^{1/2}w_{*}=\hat{w}^{\top}\Sigma w_{*}-\alpha\|\Sigma^{1/2}w_{*}\|^{2}=0 iff \displaystyle\alpha=\hat{w}^{\top}\Sigma w_{*}/\|\Sigma^{1/2}w_{*}\|^{2}. (46) With this choice of \alpha , one computes \displaystyle yx^{\top}\hat{w}=\alpha yz^{\top}\Sigma^{1/2}w_{*}+yz^{\top}r. (47) Because r is perpendicular to \Sigma^{1/2}w_{*} , we know that the above is a sum of two independent random variables. For the first summand in Eqn. 47 , observe that yz^{\top}\Sigma^{1/2}w_{*}=yx^{\top}w_{*}=\sign(x^{\top}w_{*})x^{\top}w_{*}=|x^{\top}w_{*}|, which has the same distribution as |G| for G\sim N(0,w_{*}^{\top}\Sigma w_{*}) . For the second summand, it has distribution \mathcal{N}(0,\|r\|^{2}) with \|r\|^{2}=\|\Sigma^{1/2}\hat{w}\|^{2}-\alpha^{2}\|\Sigma^{1/2}w_{*}\|^{2} . E.1 Asymptotics of \|\Sigma^{1/2}\hat{w}\|^{2} Now, one computes \hat{w}=\frac{1}{n}\sum_{i}p_{i}y_{i}Rx_{i}=\frac{1}{(1+\delta)n}\sum_{i}p_{i}y_{i}R_{-i}x_{i}. We deduce that \displaystyle(1+\delta)^{2}n^{2}\|\Sigma^{1/2}\hat{w}\|^{2}=n\sum_{i}p_{i}x_{i}^{\top}R_{-i}\Sigma R_{-i}x_{i}+\sum_{i,j,\,j\neq i}p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-i}\Sigma R_{-j}x_{j}. Now, observe that \displaystyle\frac{1}{n^{2}}\sum_{i}p_{i}x_{i}^{\top}R_{-i}\Sigma R_{-i}x_{i} \displaystyle=\frac{1}{n^{2}}\sum_{i}\operatorname{tr}(p_{i}x_{i}x_{i}^{\top}R_{-i}\Sigma R_{-i}) \displaystyle\simeq\frac{1}{n^{2}}\sum_{i}\operatorname{tr}(\mathbb{E}[p_{i}x_{i}x_{i}^{\top}R_{-i}\Sigma R_{-i}]) \displaystyle=\frac{p}{n}\operatorname{tr}CR_{-i}\Sigma R_{-i} \displaystyle\simeq\frac{p}{n}\operatorname{tr}\Sigma C^{\prime}. For i,j\in[n] with j\neq i , we have \displaystyle R_{-i} \displaystyle=R_{-ij}-\frac{1/n}{1+\delta}R_{-ij}x_{j}x_{j}^{\top}R_{-ij}, \displaystyle R_{-i}\Sigma R_{-j} \displaystyle=(R_{-ij}-\frac{1/n}{1+\delta}R_{-ij}x_{j}x_{j}^{\top}R_{-ij})\Sigma(R_{-ij}-\frac{1/n}{1+\delta}R_{-ij}x_{i}x_{i}^{\top}R_{-ij}) \displaystyle=R_{-ij}\Sigma R_{-ij}-\frac{1/n}{1+\delta}R_{-ij}\Sigma R_{-ij}x_{i}x_{i}^{\top}R_{-ij}-\frac{1/n}{1+\delta}R_{-ij}x_{j}x_{j}^{\top}R_{-ij}\Sigma R_{-ij} \displaystyle\quad+\frac{1/n^{2}}{(1+\delta)^{2}}R_{-ij}x_{j}x_{j}^{\top}R_{-ij}\Sigma R_{-ij}x_{i}x_{i}^{\top}R_{-ij} and so \displaystyle\mathbb{E}[p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-i}\Sigma R_{-j}x_{j}]=A_{1}-A_{2}-A_{3}+A_{4},\text{ where} \displaystyle A_{1}:=\mathbb{E}[p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-ij}\Sigma R_{-ij}x_{j}], \displaystyle A_{2}:=\frac{1/n}{1+\delta}\mathbb{E}[p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-ij}\Sigma R_{-ij}x_{i}x_{i}^{\top}R_{-ij}x_{j}], \displaystyle A_{3}=\frac{1/n}{1+\delta}\mathbb{E}[p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-ij}x_{j}x_{j}^{\top}R_{-ij}\Sigma R_{-ij}x_{j}], \displaystyle A_{4}=\frac{1/n^{2}}{(1+\delta)^{2}}\mathbb{E}[p_{i}q_{j}y_{i}y_{j}x_{i}^{\top}R_{-ij}x_{j}x_{j}^{\top}R_{-ij}\Sigma R_{-ij}x_{i}x_{i}^{\top}R_{-ij}] By symmetry, it is clear that A_{4}=0 . In order to compute A_{2} and A_{3} , we shall need the following result which can be obtained by applying Wick’s idendity (aka Anderson-Isserlis arguments). Lemma 4 . Let x and z be iid \mathcal{N}(0,C) and let g:\mathbb{R}^{d}\to\mathbb{R} be an odd function. Define c:=\mathbb{E}[g(x)x] . Then, for possibly random random d\times d matrices A and B independent of x and z , \displaystyle\mathbb{E}[g(x)g(z)x^{\top}Az\mid A] \displaystyle=c^{\top}Ac, \displaystyle\mathbb{E}[g(x)g(z)(x^{\top}Az)(x^{\top}Bx)\mid A,B] \displaystyle=\operatorname{tr}(BC)c^{\top}Ac+2c^{\top}ACBc, \displaystyle\mathbb{E}[g(x)g(z)(x^{\top}Az)(x^{\top}Bz)^{2}\mid A,B] \displaystyle=\operatorname{tr}(BC)^{2}c^{\top}Ac+4\operatorname{tr}(BC)c^{\top}ACBc+2c^{\top}ACBCBc. Applying the first part of the lemma with A=R\Sigma R gives A_{1}\simeq c^{\top}\Sigma^{\prime}c , where \Sigma^{\prime}:=\mathbb{E}[R\Sigma R] . Applying the second part of the lemma with A=R_{-ij}\simeq R and B=R_{-ij}\Sigma R_{-ij}\simeq R\Sigma R gives \displaystyle A_{3} \displaystyle=A_{2}\simeq\frac{1}{1+\delta}\frac{1}{n}\left(\operatorname{tr}(\Sigma C^{\prime})c^{\top}Rc+2c^{\top}RCR\Sigma Rc\right) \displaystyle\simeq\frac{1}{1+\delta}\frac{1}{n}\operatorname{tr}(\Sigma C^{\prime})c^{\top}Rc\simeq\frac{c^{\top}\bar{R}c}{1+\delta}\frac{1}{n}\operatorname{tr}\Sigma C^{\prime}. We deduce that \displaystyle\|\Sigma^{1/2}\hat{w}\|^{2}\simeq\frac{1}{(1+\delta)^{2}}\left(\frac{p}{n}\operatorname{tr}\Sigma C^{\prime}+c^{\top}\Sigma^{\prime}c-\frac{2c^{\top}\bar{R}c}{1+\delta}\frac{1}{n}\operatorname{tr}\Sigma C^{\prime}\right)=:\nu. (48) E.2 Asymptotics of \alpha Mean. One computes \displaystyle\|\Sigma^{1/2}w_{*}\|^{2}\mathbb{E}\alpha=\mathbb{E}\hat{w}^{\top}\Sigma w_{*} \displaystyle\simeq\frac{1}{1+\delta}\mathbb{E}\frac{1}{n}\sum_{i}p_{i}y_{i}x_{i}^{\top}R_{-i}\Sigma w_{*} \displaystyle\simeq\frac{1}{1+\delta}\mathbb{E}[p_{i}y_{i}x_{i}^{\top}R_{-i}\Sigma w_{*}] \displaystyle=\frac{1}{1+\delta}\mathbb{E}[p_{i}y_{i}x_{i}]^{\top}\mathbb{E}[R_{-i}]\Sigma w_{*} \displaystyle\simeq\frac{c^{\top}\bar{R}\Sigma w_{*}}{1+\delta}. Variance. On the other hand, observe that \|\Sigma^{1/2}w_{*}\|^{4}\alpha^{2}=(\hat{w}^{\top}\Sigma w_{*})^{2}=\hat{w}^{\top}\Sigma w_{*}w_{*}^{\top}\Sigma\hat{w}. So, applying Eqn. 48 with \Sigma replaced with the rank one matrix \Sigma w_{*}w_{*}^{\top}\Sigma and \Sigma^{\prime} replaced with R\Sigma w_{*}w_{*}^{\top}\Sigma R , we get \|\Sigma^{1/2}w_{*}\|^{4}\mathbb{E}\alpha^{2}=\mathbb{E}[\hat{w}^{\top}\Sigma w_{*}w_{*}^{\top}\Sigma\hat{w}]\simeq\frac{1}{(1+\delta)^{2}}\mathbb{E}[c^{\top}R\Sigma w_{*}w_{*}^{\top}\Sigma Rc]\simeq\frac{1}{(1+\delta)^{2}}(c^{\top}\bar{R}\Sigma w_{*})^{2}, where we have ignored all trace terms which are now of order 1/n (negligible). The RHS of the above display coincides with the square of the estimate for \|\Sigma^{1/2}w_{*}\|^{2}\mathbb{E}[\alpha] provided earlier. We deduce that the variance of \alpha vanishes, and so \displaystyle\alpha\simeq\mathbb{E}\alpha\simeq\frac{c^{\top}\bar{R}\Sigma w_{*}}{(1+\delta)\|\Sigma^{1/2}w_{*}\|^{2}}=:\frac{m}{\|\Sigma^{1/2}w_{*}\|}. Combining with 47 and Eqn. 48 completes the proof of the first part of Proposition 2 , namely the convergence Eqn. 41 . E.3 Asymptotics of Classification Test Error In the asymptotic limit Eqn. 4 , one may use the representation Eqn. 41 to write \displaystyle\lim E_{test}(\hat{w}) \displaystyle=\lim\mathbb{P}(yx^{\top}\hat{w}\leq 0) \displaystyle=\mathbb{P}(m|G_{1}|+\sqrt{\nu-m^{2}}G_{2}\leq 0) \displaystyle=\mathbb{P}(\frac{G_{2}}{|G_{1}|}\leq-\frac{m}{\sqrt{\nu-m^{2}}}) \displaystyle=\mathbb{P}(\frac{G_{2}}{G_{1}}\leq-\frac{|m|}{\sqrt{\nu-m^{2}}}) \displaystyle=\frac{1}{2}+\frac{1}{\pi}\arctan(-|m|/\sqrt{\nu-m^{2}}) \displaystyle=\frac{1}{\pi}\arccos(|m|/\sqrt{\nu})=\frac{1}{\pi}\arccos(|m_{0}|/\sqrt{\nu}_{0}), as claimed. Note that, we have used the fact that G_{2}/G_{1} is standard Cauchy random variable, for independent G_{1},G_{2}\sim\mathcal{N}(0,1) . This completes the proof Proposition 2 . ∎ Appendix F Proof of Proposition 1 Using Theorem 4 of ( 28 ) (and the proof thereof) combined with some basic algebraic manipulations, we can write \displaystyle R \displaystyle\simeq\bar{R}, (49) \displaystyle\text{where }\bar{R}^{-1} \displaystyle=C^{1/2}\mathbb{E}\,\left[\frac{p_{i}}{1+p_{i}\delta(z)}(\Pi^{\perp}+(\Pi x_{i})(\Pi x_{i})^{\top})\right]C^{1/2}-zI_{d}, (50) for a random training example (x_{i},y_{i})\sim P_{g} from the generator, and corresponding prune/no prune bit p_{i} . The matrix C is the covariance matrix of x_{i} . Since p_{i} is Bernoulli with mean p:=\mathbb{P}(p_{i}=1) , it is clear that \mathbb{E}\,\left[\frac{p_{i}}{1+p_{i}\delta(z)}\right]=\frac{p}{1+\delta(z)}:=t(z). This further gives \displaystyle\begin{split}\bar{R}^{-1}&=t(z)C^{1/2}\Pi^{\perp}C^{1/2}-zI_{d}+C^{1/2}\Pi K\Pi C^{1/2},\\ \text{with }K&:=\mathbb{E}\left[\frac{p_{i}}{1+p_{i}\delta(z)}uu^{\top}\right],\end{split} (51) where u:=\Sigma^{-1/2}x_{i}\sim\mathcal{N}(0,I_{d}) and v:=C^{1/2}w_{o} . Now, to determine the matrix K , we first rewrite u=(u_{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}},u_{\perp}) and v=(v_{1},v_{\perp}) , where \displaystyle u_{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}} \displaystyle:=\frac{u^{\top}w_{o}}{\|w_{o}\|}\in\mathbb{R},\quad v_{1}:=\frac{v^{\top}w_{o}}{\|w_{o}\|}\in\mathbb{R}, (52) \displaystyle u_{\perp} \displaystyle:=\Pi^{\perp}u\in\mathbb{R}^{d-1},\quad v_{\perp}:=\Pi^{\perp}v\in\mathbb{R}^{d-1}. (53) The advantage of this representation is that: • u_{\perp} and v_{\perp} are orthogonal to w_{o} . • u_{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}} and u_{\perp} are statistically independent. • u_{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}} has distribution \mathcal{N}(0,1) . • u_{\perp} has distribution \mathcal{N}(0,I_{d-1}) . Combining with the fact that due to the evenness of the pruning function q (in Eqn. 5 , Eqn. 6 , etc.), the distribution of (x_{i},y_{i},q_{i}) doesn’t change if x_{i} is replaced by -x_{i} (so that \mathbb{E}\,[p_{i}u_{i}u_{j}]=0 for all i\neq j ), we get: \displaystyle K \displaystyle=s(z)\Pi+s_{\perp}(z)\Pi^{\perp}, \displaystyle\text{where }s(z) \displaystyle:=\mathbb{E}[h_{i}G_{1}^{2}],\quad s_{\perp}(z):=\mathbb{E}[h_{i}G_{\perp}^{2}] \displaystyle h_{i} \displaystyle:=\frac{p_{i}}{1+p_{i}\delta(z)},\quad(G_{1},G_{\perp})\sim\mathcal{N}(0,I_{2}). Combining with Eqn. 51 , we get \displaystyle\bar{R}^{-1} \displaystyle=C^{1/2}(a(z)I_{d}+b(z)\Pi)C^{1/2}, (54) \displaystyle\text{where }a(z) \displaystyle=t(z)-z,\quad t(z)=\frac{p}{1+\delta(z)},\quad b(z)=s(z)-t(z). (55) Now, using the Matrix-Inversion Lemma , one can obtain \bar{R} from \bar{R}^{-1} as follows: C^{1/2}\bar{R}C^{1/2}=(a(z)I_{d}+b(z)\Pi)^{-1}=\frac{1}{a(z)}\left(I_{d}-\frac{b(z)/a(z)}{b(z)/a(z)+1}\Pi\right)=\frac{1}{a(z)}\Pi^{\perp}+\frac{1}{b(z)+a(z)}\Pi. It suffices to notice that 1/(b(z)+a(z))=1/(s(z)-z)=\tilde{m}(z) and 1/a(z)=\check{m}(z) by definition, and the result follows. ∎ Appendix G Proof of Theorem 1 , Theorem 3 , and Corollaries Theorem 1 and Theorem 3 are direct consequences of Proposition 2 , where we use the deterministic equivalents provided in Corollary 3 , to considerably simplify the resulting formulae. Corollary 1 is a consequence of Theorem 1 and limiting behavior of the spectral functions given in Eqn 36 . G.1 Proof of Theorem 1 and Theorem 3 Set z=-\lambda . Also recall that c=\beta_{1}u+\beta_{2}v , where u , v , \beta_{1} , and \beta_{2} are as in Lemma 3 . Note that we have the identification \beta=\beta_{2} and \tilde{\beta}=\beta_{1} . We know from Proposition 1 that R\simeq\bar{R}=m(z)\Pi^{\perp}+\tilde{m}(z)\Pi , where \Pi=uu^{\top} . One computes \displaystyle m_{0}=(w_{*}/\|w_{*}\|)^{\top}\bar{R}c \displaystyle=\frac{1}{\|w_{*}\|}w_{*}^{\top}\left(m(z)\Pi^{\perp}+\tilde{m}(z)\Pi\right)(\beta_{1}u+\beta_{2}v), \displaystyle=\frac{1}{\|w_{*}\|}w_{*}^{\top}\left(\beta_{1}\tilde{m}(z)u+\beta_{2}m(z)v\right), Moreover, on computes w_{*}^{\top}u/\|w_{*}\|=\rho_{*} by definition, and \displaystyle\frac{w_{*}^{\top}v}{\|w_{*}\|} \displaystyle=\frac{(w_{g}-(w_{g}^{\top}w_{o})w_{o})^{\top}w_{*}/\|w_{*}\|}{\|w_{g}-(w_{g}^{\top}w_{o})w_{o}\|}=\frac{w_{g}^{\top}w_{*}/\|w_{*}\|-\rho_{g}\|w_{g}\|(w_{o}^{\top}w_{*}/\|w_{*}\|)}{\|w_{g}\|\sqrt{1-\rho_{g}^{2}}} \displaystyle=\frac{\rho-\rho_{g}\rho_{*}}{\sqrt{1-\rho_{g}^{2}}}=\frac{\cos\theta-\cos\theta_{g}\cos\theta_{*}}{\sin\theta_{g}}=\sin\theta_{*}\cos\xi=\sqrt{1-\rho_{*}^{2}}\cos\xi=:\omega/\beta_{2}, where we have used the identity \cos\theta=\cos\theta_{g}\cos\theta_{*}+\sin\theta_{g}\sin\theta_{*}\cos\xi , known as the Spherical Law of Cosines . Putting things together gives m_{0}\simeq\omega m(z)+\tilde{\omega}\tilde{m}(z) as claimed. Likewise, one computes \displaystyle\frac{1}{n}\operatorname{tr}\Sigma C^{\prime} \displaystyle=\frac{1}{n}\operatorname{tr}R^{2}\simeq\frac{1}{n}\operatorname{tr}\left(m^{\prime}(z)\Pi^{\perp}+\tilde{m}^{\prime}(z)\Pi\right)\simeq\phi m^{\prime}(z), \displaystyle c^{\top}\bar{R}c \displaystyle=c^{\top}\left(m(z)\Pi^{\perp}+\tilde{m}(z)\Pi\right)c=(\beta_{1}u+\beta_{2}v)^{\top}(\tilde{m}(z)\Pi+m(z)\Pi^{\perp})(\beta_{1}u+\beta_{2}v) \displaystyle=\beta_{2}^{2}m(z)+\beta_{1}^{2}\tilde{m}(z)=\beta^{2}m(z)+\tilde{\beta}^{2}\tilde{m}(z)=:r(z), \displaystyle c^{\top}\Sigma^{\prime}c \displaystyle=c^{\top}\mathbb{E}\,[R^{2}]c\simeq c^{\top}\left(m^{\prime}(z)\Pi^{\perp}+\tilde{m}^{\prime}(z)\Pi\right)c=\beta^{2}m^{\prime}(z)+\tilde{\beta}^{2}\tilde{m}^{\prime}(z)=r^{\prime}(z). We deduce that \nu=\nu_{0}/(1+\delta)^{2} , where \displaystyle\nu_{0} \displaystyle=\frac{p}{n}\operatorname{tr}\Sigma C^{\prime}+c^{\top}\Sigma^{\prime}c-\frac{2c^{\top}\bar{R}c}{1+\delta}\frac{1}{n}\operatorname{tr}C\Sigma^{\prime} \displaystyle\simeq\frac{p}{n}\operatorname{tr}R^{2}+r^{\prime}(z)-\frac{2r(z)}{1+\delta(z)}\frac{1}{n}\operatorname{tr}R^{2}=p\phi m^{\prime}(z)+r^{\prime}(z)-\frac{2r(z)\phi m^{\prime}(z)}{1+\phi m(z)}. the result then follows from Proposition 2 .∎ G.2 Proof of Corollary 1 As usual, set z:=-\lambda<0 . (A) For \phi

p . Observe that m_{0}=\sqrt{\nu_{0}-m_{0}^{2}}=-zm_{0}/\sqrt{z^{2}-z^{2}m_{0}^{2}} . On the other hand, from Eqn. 32 we know that \displaystyle-zm(z)=\frac{\sqrt{(p-\phi-z)^{2}-4\phi z}-(p-\phi-z)}{2\phi} (56) Combining with Lemma 2 , we deduce the following limits \displaystyle-zm(z),z^{2}m^{\prime}(z) \displaystyle\to c_{0}:=1-p/\phi>0, \displaystyle\bar{m}^{\prime}(z) \displaystyle\to\frac{p/\phi}{\phi-p}, \displaystyle-z\tilde{m}(z),z^{2}\tilde{m}^{\prime}(z) \displaystyle\to\frac{c_{0}}{\gamma/\phi+c_{0}}, \displaystyle\frac{-zm^{\prime}(z)}{1+\phi m(z)} \displaystyle\to\frac{1}{\phi}. Furthermore, one computes \displaystyle-zr(z) \displaystyle=\beta_{2}^{2}\cdot(-zm(z))+\beta_{1}^{2}\cdot(-z\tilde{m}(z))=\beta_{2}^{2}c_{0}+\beta_{1}^{2}\frac{c_{0}}{\gamma/\phi+c_{0}}=:c_{0}r_{0}, \displaystyle z^{2}r^{\prime}(z) \displaystyle=\beta_{2}^{2}z^{2}m^{\prime}(z)+\beta_{1}^{2}z^{2}\tilde{m}(z)=\beta_{2}^{2}c_{0}+\beta_{1}^{2}\frac{c_{0}}{\gamma/\phi+c_{0}}=c_{0}r_{0}, \displaystyle-zm_{0} \displaystyle=\sqrt{2/\pi}\cdot(-zm(z)\omega-z\tilde{m}(z)\tilde{\omega})\to\sqrt{2/\pi}c_{0}\cdot(\omega+\tilde{\omega}/(\gamma/\phi+c_{0})):=a, \displaystyle z^{2}\nu_{0} \displaystyle=p\phi z^{2}m^{\prime}(z)+z^{2}r^{\prime}(z)-2\phi\frac{-zm^{\prime}(z)}{1+\phi m(z)}\cdot(-zr(z)) \displaystyle\to p\phi c_{0}+r_{0}c_{0}-2r_{0}c_{0}=c_{0}\cdot(p\phi-r_{0})=:b. We deduce that m_{0}/\sqrt{\nu}_{0}=-za/\sqrt{z^{2}b}=a/\sqrt{b}, and the result follows from Theorem 1 . ∎ G.3 Proof of Theorem 2 Taking the limit \phi\to 0 in Corollary 1 , we have \displaystyle r_{0}^{\prime} \displaystyle\to p\cdot(\beta^{2}+\tilde{\beta}^{2}p^{2}/\gamma^{2}),\quad b\to\frac{\beta^{2}+\tilde{\beta}^{2}p^{2}/\gamma^{2}}{p^{2}},\quad a\to\frac{\omega+\tilde{\omega}p/\gamma}{p}, \displaystyle a/\sqrt{b} \displaystyle\to\frac{\omega/p+\tilde{\omega}/\gamma}{\sqrt{\beta^{2}/p^{2}+\tilde{\beta}^{2}/\gamma^{2}}}=\frac{(\beta/p)\sqrt{1-\rho_{*}^{2}}\cos\zeta+(\tilde{\beta}/\gamma)\rho_{*}}{\sqrt{\beta^{2}/p^{2}+\tilde{\beta}^{2}/\gamma^{2}}}=\frac{j\sqrt{1-\rho_{*}^{2}}\cos\zeta+1}{\sqrt{j^{2}+1}}, \displaystyle\text{with }j \displaystyle=j(q):=\frac{\gamma(q)\beta(q)}{p\tilde{\beta}(q)}>0. where we recall that \omega=\beta\sqrt{1-\rho_{*}^{2}}\cos\zeta and \tilde{\omega}=\tilde{\beta}\rho_{*} . Part (A). Taking \rho_{*}=1 , meaning that pruning is done along the ground-truth, gives \displaystyle a/\sqrt{b}=1/\sqrt{j^{2}+1}. From Corollary 1 , we see that the limiting value of E_{clf}(\hat{w}) , i.e the functional F defined in Eqn. 11 , is an increasing function of the ratio j(q) . The proof is completed by invoking Lemma 5 which establishes that i q_{\operatorname{KH}(p)} (resp. q_{\operatorname{KE}(p)} ) is the unique minimizer (resp. maximizer) of the ratio j(q) over q\in\mathcal{Q}_{p} . Part (B). On the other hand, taking \rho=1 gives \rho_{g}=\rho_{*} , \zeta=0 , \omega=\beta\sqrt{1-\rho_{g}^{2}} . We get a>0 , and \displaystyle a/\sqrt{b}\to\frac{j\sqrt{1-\rho_{*}^{2}}+\rho_{*}}{\sqrt{j^{2}+1}}. It is easy to show that the RHS is strictly decreasing function of j . As with part (A), the proof is completely by invoking Lemma 5 to extremize the ratio j=j(q) . ∎ Lemma 5 . Suppose \rho_{g}>0 . For any fixed pruning strategy p\in(0,1] , ignoring null-sets, the unique maximizer (resp. minimizer) of the ratio j(q) over \mathcal{Q}_{p}:=\{q\in\mathcal{Q}\mid p(q)=p\} is the "keep hard examples" pruning strategy q_{\operatorname{KH}(p)} (resp. the "keep easy examples" pruning strategy q_{\operatorname{KE}(p)} ). Proof. Clearly, there is a bijective correspondence between \mathcal{Q}_{p} and the collection \mathcal{S}_{p} of Borell subsets S\subseteq\mathbb{R} of Gaussian measure equal to p , and verifying the symmetry condition -S=S . This correspondence is simply S\mapsto 1_{S} , the indicator function of S . Furthermore, for any S\in\mathcal{S}_{p} , one can write \displaystyle\gamma(1_{S}) \displaystyle=2F_{0}(S_{+}),\quad\tilde{\beta}(1_{S})=2F_{1}(S_{+}),\quad\beta(1_{S})=2F_{2}(S_{+}),\text{with } \displaystyle S_{+} \displaystyle:=S\cap(0,\infty),\quad F_{k}(T):=\int_{T}f_{k}(t)\varphi(t)\mathrm{d}t, \displaystyle f_{0}(t) \displaystyle:=t^{2},\quad f_{1}(t):=(2\Phi(\tau t)-1)t,\quad f_{2}(t):=\varphi(\tau t),\quad\tau:=\rho_{g}/\sqrt{1-\rho_{g}^{2}}. Define a_{p},b_{p}>0 such that the sets I_{p}:=\{t\in\mathbb{R}\mid|t|\geq a_{p}\} and J_{p}:=\{t\in\mathbb{R}\mid|t|\leq b_{p}\} both have Gaussian measure p . We shall show that over the collection \mathcal{T}_{p} of Borell subsets of (0,\infty) with Gaussian measure equal to m=p/2 , the functional T\mapsto F_{0}(T)F_{2}(T) is minimized (resp. maximized) by J_{p}^{+}:=[a_{p},\infty) (resp. I_{p}^{+}:=[0,b_{p}] ), while modulo null sets, and F_{1} is uniquely maximized (resp. minimized) by J_{p}^{+} (resp. I_{p}^{+} ). Step 1: Reduction to Integration w.r.t Lebesgue Measure. For any t>0 and u\in[0,1/2] , define M(t):=\mu([0,t]),\quad N(u):=M^{-1}(u). Under the change of variable t=N(u) , one has F_{k}(T)=\bar{F}_{k}(M(T)),\text{ where }\bar{F}(U):=\int_{U}g_{k}(u)\mathrm{d}u,\quad g_{k}:=f_{k}\circ N,\text{ and }M(T):=\{M(t)\mid t\in T\}. Thus, the minimizers (resp. maximizers) of F over T\in\mathcal{T}_{p} are of the form N(U) where U minimizes (resp. maximizes) \bar{F}(U):=\bar{F}_{0}(U)\bar{F}_{1}(U)/\bar{F}_{2}(U) over Borell sets U\subseteq(0,1/2) verifying |U|=m . Let us show that modulo null sets, \bar{F} is minimized by (0,m] and maximized by (1/2-m,1/2) where m:=p/2\in(0,1/2) . For any r\geq 0 , consider the equivalent linear-fractional program \displaystyle\min_{r\geq 0,\,U\subseteq(0,1/2)}\frac{r\bar{F}_{1}(U)}{\bar{F}_{2}(U)}\text{ subject to }|U|=m,\,\bar{F}_{0}(U)\leq r. (57) Step 2: Dinkelback re-Parametrization. For fixed r\geq 0 , consider the change of variable \lambda=\bar{F}_{1}(U)/\bar{F}_{2}(U) , and define \displaystyle v(\lambda):=\max_{U\subseteq(0,1/2)}\bar{F}_{1}(U)-\lambda\bar{F}_{2}(U)\text{ subject to }|U|=m,\,\bar{F}_{0}(U)\leq r. (58) The "Dinkelbach trick" tells us that \lambda^{*}=\max_{U}\bar{F}_{1}(U)/\bar{F}_{2}(U) iff v(\lambda^{*})=0 . Now, the Lagrangian for the auxiliary problem is given by \displaystyle\mathcal{L}(U,\lambda,\eta,\zeta) \displaystyle=\bar{F}_{1}(U)-\lambda\bar{F}_{2}(U)+\eta\cdot(r-\bar{F}_{0}(U))+\zeta\cdot(m-|U|) \displaystyle=\int_{U}H(u,\lambda,\eta,\zeta)\mathrm{d}u+\eta r+\zeta m,\text{ with }H(u,\lambda,\eta,\zeta):=g_{1}(u)-\lambda g_{2}(u)-\eta g_{0}(u)-\zeta. The first-order optimality conditions of U can then be expressed as \displaystyle H(u,\lambda,\eta,\zeta)\begin{cases}\geq 0,&\mbox{ if }u\in U,\\ \leq 0,&\mbox{ otherwise.}\end{cases} (59) Step 3: Shape Analysis. Now, under the assumption that \rho_{g}>0 , the functions f_{0} and f_{1} (therefore g_{0} and g_{2} ) are increasing and g_{1} (therefore g_{1} ) is decreasing. Thus, for any \lambda,\eta\geq 0 , the function u\mapsto H(u,\lambda,\eta,\zeta) is a non-increasing function, for any feasible \lambda,\eta,\zeta . A non-increasing function crosses zero at most once. We deduce that the optimal U must be of the form [b,1/2) , modulo a null set. The condition |U|=m forces b=1/2-m . We conclude that [1/2-m,1/2) is the unique minimizer of \bar{F} . Similarly, one shows that [0,m] is the unique maximizer of \bar{F} . ∎ Appendix H Proof of Theorem 4 (Regression Analysis) H.1 A Modified Bias-Variance Decomposition We start with the following general bias-variance decomposition for the regression test error. Proposition 3 . The regression test error of the estimator \hat{w} defined in Eqn Eqn. 3 is given exactly by \displaystyle E_{reg}(\hat{w})=\lambda^{2}\mathbb{E}\,[w_{g}^{\top}R\Sigma Rw_{g}]+\sigma^{2}\mathbb{E}\,\frac{1}{n}\operatorname{tr}SR^{2}\Sigma+{\color[rgb]{1,0,0}c^{2}-2\lambda\mathbb{E}\,[w_{g}^{\top}R\Sigma\epsilon]}, (60) where \epsilon:=w_{g}-w_{*} , c^{2}:=\epsilon^{\top}\Sigma\epsilon , and S and R are the random matrices defined in Eqn Eqn. 3 . The first two terms in the above sum correspond to bias and variance if we had w_{g}=w_{*} , i.e if we had no label-shift; the last two terms in red are a correction to take into account label shift. H.2 Proof of Theorem 4 Now, from Proposition 1 with \Sigma=I_{d} , we have the following deterministic equivalents: \displaystyle R \displaystyle\simeq m(z)\Pi^{\perp}+\tilde{m}(z)\Pi, \displaystyle SR-I_{d} \displaystyle=zR\simeq zm(z)\Pi^{\perp}+z\tilde{m}(z)\Pi, \displaystyle R^{2} \displaystyle=\frac{\partial}{\partial z}R\simeq m^{\prime}(z)\Pi^{\perp}+\tilde{m}^{\prime}(z)\Pi, \displaystyle SR^{2} \displaystyle=\frac{\partial}{\partial z}SR\simeq(m(z)+zm^{\prime}(z))\Pi^{\perp}+(\tilde{m}(z)+z\tilde{m}^{\prime}(z))\Pi \displaystyle=(m(z)+zm^{\prime}(z))I_{d}+(\tilde{m}(z)-m(z)+z\tilde{m}^{\prime}(z)-zm^{\prime}(z))\Pi. Furthermore, notice that because \Pi is a fixed-rank (in fact rank-1) matrix, so is S\Pi\Sigma , and so \mathbb{E}\,(1/n)\operatorname{tr}S\Pi\Sigma\to 0 in the limit n\to\infty . Thus, in view of using Proposition 3 , one computes \displaystyle\mathbb{E}\,[w_{g}^{\top}R\Sigma Rw_{g}] \displaystyle=w_{g}^{\top}\mathbb{E}\,[R^{2}]w_{g}=m^{\prime}(z)\|w_{g}^{\perp}\|^{2}+\tilde{m}^{\prime}(z)\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}, \displaystyle\mathbb{E}\,\frac{1}{n}\operatorname{tr}SR^{2}\Sigma \displaystyle\simeq\phi\cdot\mathbb{E}\,\frac{1}{d}\operatorname{tr}SR^{2}\Sigma\simeq\phi\cdot(m(z)+zm^{\prime}(z))=\phi\bar{m}^{\prime}(z), \displaystyle\mathbb{E}\,[w_{g}^{\top}R\Sigma\epsilon] \displaystyle=\mathbb{E}\,[w_{g}^{\top}R\epsilon]\simeq\epsilon^{\top}(m(z)w_{g}^{\perp}+\tilde{m}(z)w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}). Putting things together then gives \displaystyle\begin{split}E_{reg}(\hat{w})&\simeq\lambda^{2}\cdot\left(m^{\prime}(-\lambda)\|w_{g}^{\perp}\|^{2}+\tilde{m}^{\prime}(-\lambda)\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}\right)+\sigma^{2}\phi\bar{m}^{\prime}(-\lambda)\\ &\quad+\|\epsilon\|^{2}-2\lambda\epsilon^{\top}(m(-\lambda)w_{g}^{\perp}+\tilde{m}(-\lambda)w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}})\\ &=\lambda^{2}\cdot\left(m^{\prime}(-\lambda)\|w_{g}^{\perp}\|^{2}+\tilde{m}^{\prime}(-\lambda)\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}\right)+\sigma^{2}\phi\bar{m}^{\prime}(-\lambda)\\ &\quad+c^{2}-2\lambda\cdot(m(-\lambda)a+\tilde{m}(-\lambda)b)\text{ with }a:=\epsilon^{\top}w_{g}^{\perp},\,b:=\epsilon^{\top}w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\text{ and }c^{2}:=\|\epsilon\|^{2},\end{split} which proves Theorem 4 . ∎ H.3 Proof of Corollary 2 The first equation follows by taking the limit \phi\to 0^{+} in part (A) of Corollary 1 . For the second equation, note that in the limit Eqn. 4 Corollary 1 gives E_{reg}\simeq L=c^{2}+L_{0} , with L_{0}=L_{0}(\phi,p):=\begin{cases}0,&\mbox{ if }\phip,\end{cases} where D:=\|w_{g}^{\perp}\|^{2}-2a , E:=\|w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2}-2b , and we recall that c_{0}:=1-p/\phi,\quad c_{1}:=\gamma/\phi+c_{0}=1-(p-\gamma)/\phi,\quad\gamma=p+2\alpha\varphi(\alpha),\quad\alpha=\Phi^{-1}(1-p/2). Now, on the second branch, one computes \displaystyle\gamma^{\prime}:=\frac{\partial\gamma}{\partial p}=\alpha^{2},\quad\frac{\partial L_{0}}{\partial p}=-\frac{D}{\phi}-E\frac{\gamma+(\phi-p)\gamma^{\prime}}{(\phi-(p-\gamma))^{2}}=-\frac{D}{\phi}-E\frac{\gamma+(\phi-p)\alpha^{2}}{(\phi-(p-\gamma))^{2}}, One can further show the Hessian of L_{0} is nonnegative everywhere provided E>0 , and so every stationary point is a global minimum, provided it lies in the interval (0,\phi) . Expanding to first order in p , observe that if t:=-D/E>0 , then we have a unique stationary point p_{0}=p_{0}(\phi) . By the way, observe that D+c^{2}=\|w_{*}-w_{g}^{\mathrel{\vbox{\hbox{$\scriptscriptstyle/$}\vskip-1.50694pt\hbox{$\scriptscriptstyle/$}}}}\|^{2} and E+c^{2}=\|w_{*}-w_{g}^{\perp}\|^{2} , where c^{2}:=\|w_{*}-w_{g}\|^{2} as usual, and so the condition D<0b(u)\} , where a(u):=\alpha_{min}((1-u)p) and b(u):=\alpha_{min}(pu) . It is easy to verify that b(u)\geq a(u) . Indeed, because \Phi^{-1} is non-decreasing, we know from the definition of \alpha_{max} and \alpha_{min} functions that \alpha_{max}(pu)\geq\alpha_{min}((1-u)p)\iff 1-pu/2\geq(1+(1-u)p)/2\iff(1+p)/2\leq 1\iff p\leq 1. If follows that I_{u} and J_{u} are disjoint and so q_{u}(t)=1_{I_{u}\cup J_{u}}=1_{I_{u}}+1_{J_{u}}, It is easy to verify that p(q_{u})=pu+(1-u)p=p and \gamma(q_{u})=p-2a(u)\varphi(a(u))+2b(u)\varphi(b(u)). Observe that u\mapsto\gamma(q_{u}) increases continuously from \gamma_{min}(p) at u=0 to \gamma_{max}(p) for u=1 . It follows from the Intermediate Value Theorem that there exists u_{0}\in[0,1] such that \gamma(q_{u_{0}})=\gamma . It suffices to take q=q_{u_{0}} . Finally, \operatorname{Spec}(\mathcal{Q})=\operatorname{Spec}(\mathcal{Q}_{*}) follows directly from the construction of q_{u} . ∎ Lemma 7 . For any p\in[0,1] , we have the following. (A) The minimum of \gamma(q) over all q\in\mathcal{Q} is given by \displaystyle\gamma_{min}(p)=p-\alpha_{min}(p)\varphi(\alpha_{min}(p)),\text{ with }\alpha_{min}(p):=\Phi^{-1}((1+p)/2), (68) and is attained by setting q(t)\equiv 1_{|t|\leq\alpha_{min}(p)} . (B) The maximum of \gamma(q) over all q\in\mathcal{Q} is given by \displaystyle\gamma_{max}(p)=p+\alpha_{max}(p)\varphi(\alpha_{max}(p)),\text{ with }\alpha_{max}(p):=\Phi^{-1}(1-p/2). (69) and is attained by setting q(t)=1_{|t|>\alpha_{max}(p)} . Appendix J Proofs of Lemmas J.1 Proof of Lemma 2 The formula for m^{\prime}(z) from differentiating through Eqn. 33 w.r.t z , and then doing some basic algebraic manipulations. All the other formulae for \bar{m}^{\prime}(z) , \tilde{m}(z) , and r^{\prime}(z) follow from the definition of the quantities and the chain rule. ∎ Appendix K Proof of Lemma 7 (A) Every q\in\mathcal{Q} is the indicator function of some measurable A\subseteq\mathbb{R} . We wish to maximize \gamma(q)=\int_{A}t^{2}\varphi(t)\mathrm{d}t over A , subject to p(q)=\int_{A}\varphi(t)\mathrm{d}t=p . The Lagrangian is \mathcal{L}(A,\lambda)=\int_{A}t^{2}\varphi(t)\mathrm{d}t+\lambda\cdot\left(p-\int_{A}\varphi(t))\mathrm{d}t\right)=\int_{-\infty}^{\infty}(t^{2}-\lambda)1_{A}(t)\varphi(t)\mathrm{d}t+p\lambda. Since \varphi(t)>0 for all t , it is clear that the integrand is minimized by taking 1_{A}(t)=\begin{cases}1,&\mbox{ if }t^{2}>\lambda\\ 0,&\mbox{ otherwise}.\end{cases} Thus, by the Rearrangement inequality (for measures), it is optimal to take A=(-\infty,\sqrt{\lambda})\cup(\sqrt{\lambda},\infty) for some \lambda\geq 0 . The constraint \int_{A}\varphi(t)\mathrm{d}t=p then gives \sqrt{\lambda}=\Phi^{-1}((1+p)/2)=:\alpha_{min}(p). (B) Analogous arguments. ∎ Appendix L Proof of Lemma 3 L.1 Non-LIMO Case Let us prove the formula for \beta_{1} and \beta_{2} given in the first row of Table 3 . Consider F=\sign(U)q(V) , where U=Z^{\top}\bar{w}_{g} and V:=Z^{\top}\bar{w}_{o} , for Z\sim\mathcal{N}(0,I_{d}) . Note that we can write C^{-1/2}c=\mathbb{E}[FZ] . By Stein’s lemma, we have C^{-1/2}c=a\bar{w}_{g}+b\bar{w}_{o} , where \displaystyle a:=\mathbb{E}[\frac{\partial F}{\partial U}],\quad b:=\mathbb{E}[\frac{\partial F}{\partial V}]. (70) By direct computation, one has \displaystyle\frac{\partial F}{\partial U} \displaystyle=2\delta(U)q(V), (71) \displaystyle\frac{\partial F}{\partial V} \displaystyle=\sign(U)q^{\prime}(V), (72) in the distribution-theoretic sense. Thus, one computes \displaystyle\mathbb{E}[\delta(U)q(V)] \displaystyle=\varphi(0)\mathbb{E}[q(V)\mid U=0]=\varphi(0)\mathbb{E}[q(V)\mid U=0]=\varphi(0)\mathbb{E}[q(G)] \displaystyle=\varphi(0)\int_{-\infty}^{\infty}q(\sigma t)\varphi(t)\mathrm{d}t=\frac{\varphi(0)}{\sigma}\int_{-\infty}^{\infty}q(t)\varphi(t/\sigma)\mathrm{d}t \displaystyle=\frac{1}{\sigma}\mathbb{E}[q(G)\varphi(\tau G)], where we have used the fact that \varphi(\tau t)\varphi(t)=\frac{1}{\sqrt{2\pi}}\varphi(t\sqrt{\tau^{2}+1})=\varphi(0)\varphi(t/\sqrt{1-\rho^{2}})=\varphi(0)\varphi(t/\sigma). We deduce that a=(2/\sigma)\mathbb{E}[q(G)\varphi(\tau G)] . On the other hand, for any s\in\mathbb{R} , one computes \displaystyle\mathbb{E}[\sign(U)\delta(V-s)] \displaystyle=\varphi(s)\mathbb{E}[\sign(U)\mid V=s] \displaystyle=\varphi(s)(\mathbb{P}(U\geq 0\mid V=s)-\mathbb{P}(U<0\mid V=s)). But, conditioned on V=s the distribution of U is \mathcal{N}(\rho_{g}s,\sigma^{2}) , where \sigma:=\sqrt{1-\rho_{g}^{2}} . We deduce that \mathbb{P}(U\geq 0\mid V=s)=\mathbb{P}(\mathcal{N}(0,\sigma^{2})\geq-\rho_{g}s)=\mathbb{P}(\mathcal{N}(0,\sigma^{2})\leq\rho_{g}s)=\Phi(\tau s) . Likewise, \mathbb{P}(U<0\mid V=s)=\mathbb{P}(\mathcal{N}(0,\sigma^{2})<-\rho_{g}s)=\Phi(-\tau s)=1-\Phi(\tau s) . We deduce that \mathbb{E}[\sign(U)\delta(V-s)]=\varphi(s)(2\Phi(\tau s)-1) , and so \displaystyle\mathbb{E}[\sign(U)q^{\prime}(V)\mid V=s] \displaystyle=\int q^{\prime}(s)(2\Phi(\tau s)-1)\varphi(s)\mathrm{d}x=\mathbb{E}[q^{\prime}(G)(2\Phi(\tau G)-1))] \displaystyle=2\mathbb{E}[q^{\prime}(G)\Phi(\tau G)]-\mathbb{E}[q^{\prime}(G)]=2\mathbb{E}[q^{\prime}(G)\Phi(\tau G)], where we have used the evenness of q to write \mathbb{E}[q^{\prime}(G)]=\mathbb{E}[Gq(G)]=0 . We deduce that \displaystyle a \displaystyle=2\sigma^{-1}\mathbb{E}[q(G)\varphi(\tau G)],\quad b=2\mathbb{E}[q^{\prime}(G)\Phi(\tau G)]. (73) Lets write C^{-1/2}c=a\bar{w}_{g}+b\bar{w}_{o}=\tilde{\beta}u+\beta v , where u=\bar{w}_{o} and v is an unit-vector perpendicular to u but in the plane spanned by \bar{w}_{o} and \bar{w}_{g} . It is easy to see that v=\frac{\bar{w}_{g}-\rho_{g}u}{\|\bar{w}_{g}-\rho_{g}u\|}=\frac{\bar{w}_{g}-\rho_{g}u}{\sqrt{1-2\rho_{g}^{2}+\rho_{g}^{2}}}=\frac{\bar{w}_{g}-\rho_{g}u}{\sigma}. We deduce that \displaystyle\beta \displaystyle=c^{\top}v=(\bar{w}_{g}^{\top}v)a=\sigma a=2\mathbb{E}[q(G)\varphi(\tau G)]=:\beta_{2}, (74) \displaystyle\tilde{\beta} \displaystyle=c^{\top}u=b+\rho_{g}a=2\mathbb{E}[q^{\prime}(G)\Phi(\tau G)]+2\tau\mathbb{E}[q(G)\varphi(\tau G)]. (75) To match the formulae for \beta_{1} and \beta_{2} given in Table 3 , we must now show that \mathbb{E}[q^{\prime}(G)\Phi(\tau G)]=\mathbb{E}[q(G)\Phi(\tau G)G]-\tau\mathbb{E}[q(G)\varphi(\tau G)] and conclude that \tilde{\beta}=\beta_{1} . To this end, write \mathbb{E}[q^{\prime}(G)\Phi(\tau G)]=\mathbb{E}[q^{\prime}(G)f(G)] , where f(t):=\Phi(\tau G) . By Stein’s lemma (Gaussian integration by parts), we have \displaystyle\mathbb{E}[q^{\prime}(G)f(G)] \displaystyle=\mathbb{E}[q(G)(Gf(G)-f^{\prime}(G))]=\mathbb{E}[q(G)(G\Phi(\tau G)-\tau\varphi(\tau G))] \displaystyle=\mathbb{E}[q(G)\Phi(\tau G)G]-\tau\mathbb{E}[q(G)\varphi(\tau G)], as claimed. Computing p and \gamma . We now compute the pruning ratio by definition as p:=\mathbb{E}[p_{i}]=\mathbb{E}[q(V)]=\mathbb{E}[q(G)] and \gamma=\mathbb{E}[(x_{i}^{\top}w_{o})^{2}q_{i}]=\mathbb{E}[q(V)V^{2}]=\mathbb{E}[q(G)G^{2}] for G\sim\mathcal{N}(0,1) . This matches the formulae given in the first row of Table 3 . ∎ L.2 LIMO Case Let us now prove the formula for \beta_{1} and \beta_{2} given in the second row of Table 3 . Here F:=\sign(U)q(V)H(UV) , where H is the Heaviside step function with the convention H(0)=1/2 . Now, one computes \displaystyle\frac{\partial F}{\partial U} \displaystyle=2\delta(U)q(V)H(UV)+\sign(U)q(V)V\delta(UV), (76) \displaystyle\frac{\partial F}{\partial V} \displaystyle=\sign(U)q^{\prime}(V)H(UV)+\sign(U)q(V)U\delta(UV), \displaystyle=\sign(U)q^{\prime}(V)H(UV)+|U|q(V)\delta(UV) (77) Computing the a coefficient. One computes \displaystyle\mathbb{E}[\delta(U)q(V)H(UV)] \displaystyle=\varphi(0)\mathbb{E}[\delta(U)q(V)H(0)\mid U=0]=\frac{\varphi(0)}{2}\mathbb{E}[q(V)\mid U=0] \displaystyle=\ldots=\frac{1}{2\sigma}\mathbb{E}[q(G)\varphi(\tau G)]. On the other hand, using the well-known identity \delta(xy)=\delta(y)/|x|+\delta(x)/|y|, one computes \displaystyle\mathbb{E}[\sign(U)q(V)V\delta(UV)] \displaystyle=\mathbb{E}[\sign(U)q(V)V\delta(V)/|U|]+\mathbb{E}[\sign(U)q(V)V\delta(U)/|V|] \displaystyle=\mathbb{E}[(1/U)q(V)\underbrace{V\delta(V)}_{=0}]+\mathbb{E}[\sign(U)\delta(U)\sign(V)q(V)] \displaystyle=\varphi(0)\mathbb{E}[\sign(V)q(V)\mid U=0]=0, where the last step is because t\mapsto\sign(t)q(t) is an odd function, and the distribution of V conditioned on U=0 is \mathcal{N}(0,\sigma^{2}) which is symmetric around the origin. We deduce that \displaystyle a=\sigma^{-1}\mathbb{E}[q(G)\varphi(\tau G)]. (78) Computing the b coefficient. For any s\in\mathbb{R} , \displaystyle\mathbb{E}[\sign(U)q^{\prime}(V)H(UV)\mid V=s] \displaystyle=q^{\prime}(s)\varphi(s)\mathbb{E}[\sign(U)1_{sU\geq 0}\mid V=s] \displaystyle=q(s)\varphi(s)\left(\mathbb{P}(U\geq 0,\,sU\geq 0\mid V=s)-\mathbb{P}(U<0,\,sU\geq 0\mid V=s)\right). Now, since the distribution of U conditioned on V=s is \mathcal{N}(\rho_{g}s,\sigma^{2}) , we have \displaystyle\mathbb{P}(U\geq 0,\,sU\geq 0\mid V=s)=\begin{cases}\mathbb{P}(U\geq 0\mid V=s)=\Phi(\tau s),&\mbox{ if }s\geq 0,\\ \mathbb{P}(U=0\mid V=s)=0,&\mbox{ if }s<0,\end{cases} \displaystyle\mathbb{P}(U<0,\,sU\geq 0\mid V=s)=\begin{cases}\mathbb{P}(U<0,\,U\geq 0\mid V=s)=0,&\mbox{ if }s\geq 0,\\ \mathbb{P}(U<0\mid V=s)=\Phi(-\tau s),&\mbox{ if }s<0.\end{cases} Therefore, \mathbb{E}[\sign(U)q^{\prime}(V)H(UV)\mid V=s]=q^{\prime}(s)\sign(s)\varphi(s)\Phi(\tau|s|) , and we conclude that \displaystyle\mathbb{E}[\sign(U)q^{\prime}(V)H(UV)]=\mathbb{E}[q^{\prime}(G)\Phi(\tau|G|)\sign(G)], with G\sim\mathcal{N}(0,1) . Define h(t):=\Phi(\tau|t|)\sign(t) . It is clear that h^{\prime}(t)=2\delta(t)\Phi(\tau|t|)+\tau\varphi(\tau|t|)=2\delta(v)\Phi(0)+\tau\varphi(\tau t)=\delta(v)+\tau\varphi(\tau t). Gaussian integration by parts then gives \displaystyle\mathbb{E}[q^{\prime}(G)\Phi(\tau|G|)\sign(G)] \displaystyle=\mathbb{E}[q^{\prime}(G)h(G)]=\mathbb{E}[q(G)(Gh(G)-h^{\prime}(G))] \displaystyle=\mathbb{E}[q(G)\Phi(\tau|G|)|G|]-\tau\mathbb{E}[q(G)\varphi(\tau G)]-\varphi(0)q(0). But q^{\prime} is odd (because q is even), and also t\mapsto\Phi(\tau|t|) is obviously even. We deduce that \mathbb{E}[\sign(U)q^{\prime}(V)H(UV)]=0 . Likewise, using the identity \delta(UV)=\delta(V)/|U|+\delta(U)/|V| , one computes \displaystyle\mathbb{E}[|U|q(V)\delta(UV)] \displaystyle=\mathbb{E}[q(V)\delta(V)]+\mathbb{E}[|U|q(V)\delta(U)/|V|] \displaystyle=\varphi(0)q(0)+\mathbb{E}[\underbrace{|U|\delta(U)}_{0}q(V)/|V|]=\varphi(0)q(0). We deduce that b=\mathbb{E}[q(G)\Phi(\tau|G|)|G|]-\tau\mathbb{E}[q(G)\varphi(\tau G)] . Therefore, writing C^{-1/2}c=\tilde{\beta}u+\beta v as before, we have \displaystyle\beta \displaystyle=\sigma a=\mathbb{E}[q(G)\varphi(\tau G)]=:\beta_{2}, \displaystyle\tilde{\beta} \displaystyle=b+\rho_{g}b=\mathbb{E}[q(G)\Phi(\tau|G|)|G|]=:\beta_{1}, which are precisely the formulae given in Table 3 . Computing p and \gamma . We now compute the pruning ratio p:=\mathbb{E}[p_{i}]=\mathbb{E}[q(V)H(UV)] and \gamma:=\mathbb{E}[(x_{i}^{\top}w_{o})^{2}p_{i}]=\mathbb{E}[V^{2}q(V)H(UV)] by definition of p_{i} in Eqn. 6 . Now, for any s\in\mathbb{R} , we have \displaystyle\mathbb{E}[H(UV)\mid V=s] \displaystyle=\begin{cases}\mathbb{P}(U\leq 0\mid V=s)=\Phi(-\tau s),&\mbox{ if }s<0,\\ 1/2,&\mbox{ if }s=0,\\ \mathbb{P}(U\geq 0\mid V=s)=\Phi(\tau s),&\mbox{ if }s>0\end{cases} \displaystyle=\Phi(\tau|s|). Integrating out s with density \varphi(s) , we deduce that \displaystyle p=\mathbb{E}[q(G)\Phi(\tau|G|)],\quad\gamma=\mathbb{E}[q(G)\Phi(\tau|G|)G^{2}], as claimed. ∎ Appendix M Analytic Formulae for p(q) , \gamma(q) , \beta(q) , and \tilde{\beta}(q) Note that every symmetric pruning function q\in\mathcal{Q} is the support function of sum T:=-S\cup S , where S is (up to a null set) a countable union of closed intervals. We consider a subclass of symmetric pruning functions corresponding to finite unions, i.e \displaystyle q=1_{T},\text{ with }T=-S\cup S,\,\,S=\cup_{j=1}^{k}[a_{j},b_{j}],\,\,0\leq a_{1}0 ): \displaystyle q_{\operatorname{KE}}(t) \displaystyle:=1[|t|\geq\alpha],\text{ i.e }q_{\operatorname{KE}}(t)=1\text{ if }|t|\geq\alpha\text{ and }q_{\operatorname{KE}}(t)=0\text{ otherwise}, (80) \displaystyle q_{\operatorname{KH}}(t) \displaystyle:=1[|t|\leq\alpha],\text{ i.e }q_{\operatorname{KH}}(t)=1\text{ if }|t|\leq\alpha\text{ and }q_{\operatorname{KH}}(t)=0\text{ otherwise}, (81) where \alpha>0 which controls the proportion p=\mathbb{E}[p_{i}] of training data which survives the curation. Since they correspond to taking S=[\alpha,\infty] and S=[0,\alpha] respectively. The representation 79 also generalizes the setup of 15 and 16 corresponds to q\equiv 1 , i.e S=[0,\infty] . For any \alpha\in[0,\infty] , define I_{k}(\alpha):=\int_{0}^{\alpha}f_{k}(x)\varphi(x)\mathrm{d}x , where the functions f_{k} are defined by \displaystyle f_{1}(x) \displaystyle:=\Phi(\tau x),\,\,f_{2}(x):=\varphi(\tau x),\,\,f_{3}(x):=x\Phi(\tau x),\,\,f_{4}(x):=x^{2}\Phi(\tau x). As usual, \varphi and \Phi are the standard normal pdf and cdf respectively. Proposition 5 . Consider a symmetric pruning function q of the form Eqn. 79 . (A) For label-agnostic curation Eqn. 5 , it holds that \displaystyle p(q) \displaystyle=\sum_{j=1}^{k}g(b_{j})-g(a_{j}),\text{ with }g(z):=2\Phi(z)-1 (82) \displaystyle\gamma(q) \displaystyle=\sum_{j=1}^{k}g(b_{j})-g(a_{j}),\text{ with }g(z):=2(\Phi(z)-z\varphi(z))-1, (83) \displaystyle\beta_{1}(q) \displaystyle=..., (84) \displaystyle\beta_{2}(q) \displaystyle=2\varphi(0)\sigma\sum_{j=1}^{k}\Phi(b_{j}/\sigma)-\Phi(a_{j}/\sigma). (85) (B) For Label-aware curation Eqn. 6 , it holds that \displaystyle p(q) \displaystyle=2\sum_{j=1}^{k}I_{1}(b_{j})-I_{1}(a_{j}), (86) \displaystyle\gamma(q) \displaystyle=2\sum_{j=1}^{k}I_{4}(b_{j})-I_{4}(a_{j}), (87) \displaystyle\beta_{1}(q) \displaystyle=2\sum_{j=1}^{k}I_{3}(b_{j})-I_{3}(a_{j}), (88) \displaystyle\beta_{2}(q) \displaystyle=2\sum_{j=1}^{k}I_{2}(b_{j})-I_{2}(a_{j}). (89) Part (A) of the proof follows directly from Eqn. 8 . Part (B) of the proof is a consequence of the identity \int_{a}^{b}h(x)\mathrm{d}x\equiv I(b)-I(a) , where I(\alpha):=\int_{0}^{\alpha}h(x)\mathrm{d}x , combined with the following lemma. Lemma 8 . For any \alpha\in[0,\infty) , the following identities hold: \displaystyle I_{1}(\alpha) \displaystyle=\Phi(\alpha)-1/2-[\Phi_{2}(\alpha,0;\rho)-\Phi_{2}(0,0;\rho)], (90) \displaystyle I_{2}(\alpha) \displaystyle=\sigma\varphi(0)[\Phi(\alpha/\sigma)-1/2], (91) \displaystyle I_{3}(\alpha) \displaystyle=\tau I_{2}(\alpha)-[\varphi(\alpha)\Phi(\tau\alpha)-\varphi(0)/2], (92) \displaystyle I_{4}(\alpha) \displaystyle=I_{1}-\alpha\varphi(\alpha)\Phi(\tau\alpha)+\rho\sigma\left[\varphi(0)^{2}-\varphi(\alpha)\varphi(\tau\alpha)\right]. (93) The results are extended to \alpha=\infty by noting that \displaystyle\lim_{\alpha\to\infty}\alpha\varphi(\alpha)=\lim_{\alpha\to\infty}\varphi(\alpha)=0,\quad\lim_{\rho\to 1}\tau I_{2}(\alpha)=\frac{\varphi(0)}{2}.