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} 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 }\phi p,\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<0