Does the Data Processing Inequality Reflect Practice? On the Utility of Low-Level Tasks
Authors: Roy Turgeman
Tom Tirer
Venue: ICLR 2026 Poster (2026)
Keywords: Classification
denoising
dimensionality reduction
Bayes optimal classifier
Primary area: learning theory
TL;DR: We show that low-level processing can benefit even strong classifiers and analyze the factors of the gain.

Abstract: The data processing inequality is an information-theoretic principle stating that the information content of a signal cannot be increased by processing the observations. In particular, it suggests that there is no benefit in enhancing the signal or encoding it before addressing a classification problem. This assertion can be proven to be true for the case of the optimal Bayes classifier. However, in practice, it is common to perform "low-level" tasks before "high-level" downstream tasks despite the overwhelming capabilities of modern deep neural networks. In this paper, we aim to understand when and why low-level processing can be beneficial for classification. We present a comprehensive theoretical study of a binary classification setup, where we consider a classifier that is tightly connected to the optimal Bayes classifier and converges to it as the number of training samples increases. We prove that for any finite number of training samples, there exists a pre-classification processing that improves the classification accuracy. We also explore the effect of class separation, training set size, and class balance on the relative gain from this procedure. We support our theory with an empirical investigation of the theoretical setup. Finally, we conduct an empirical study where we investigate the effect of denoising and encoding on the performance of practical deep classifiers on benchmark datasets. Specifically, we vary the size and class distribution of the training set, and the noise level, and demonstrate trends that are consistent with our theoretical results.

Published as a conference paper at ICLR 2026
DOES THE DATA PROCESSING INEQUALITY REFLECT PRACTICE? ON THE UTILITY OF LOW-LEVEL TASKS
Roy Turgeman
Tom Tirer
Faculty of Engineering
Faculty of Engineering
Bar-Ilan University Ramat Gan, Israel
Bar-Ilan University
Ramat Gan, Israel
ABSTRACT
The data processing inequality is an information-theorrtic principle stating that the information content of a signal cannot be increased by processing the observations. In particular, it suggests that there is no benefit in enhancing the signal or encoding it before addressing a classification problem. This assertion can be proven to be true for the case of the optimal Bayes classifier. However, in practice, it is common to perform "low-level" tasks before "high-level" downstream tasks despite the overwhelming capabilities of modern deep neural networks. In this paper, aim understand when and why low-level processing can be beneficial for classification. We present a comprehensive theoretical study of binary classification setup, where we consider a classifier that is tightly connected to the optimal Bayes classifier and converges to it as the number of training samples increases. We prove that for any finite number of training samples, there exists pre- rre-classification processing that improves the classification accuracy. We also explore the effect of class separation, training set size, and class balance on the relative gain from this procedure. We support our theory with an empirical investigation of the theoretical setup. Finally, we conduct empirical study where we investigate the effect of denoising and encoding on the performance of practical deep classifiers on benchmark datasets. Specifically, we vary the size and class distribution of the training set, and the noise level, and demonstrate trends that are consistent with our theoretical results.
INTRODUCTION
Deep neural networks (DNNs) have demonstrated remarkable performance across an extensive range of tasks, spanning from image and speech recognition natural language processing and scientific discovery. When the end goal is to address "high-level" tasks, e.g., classification and detection, natural approach is to train a DNN to directly solve the task using the raw data/observations as input (Yim & Sohn 2017: Hendrycks & Dietterich, 2019: Singh et al. 2019). Yet, it is a common practice to begin with addressing a "low-level" task order improve the quality of the input for the high-level task. Such low-level tasks include signal/image restorations (Tieer & Giryes 2018
2020
Zhang et al.] 202T as considered in (Liu et al.] 2018)) Dai et al. 2016 Li et al.) [003)] [Son et al.
2020 Haris et al. 2021; Pei et al. 22018), or encoding to a learned embedding space (Lee et al. 2022
Zhou & Paffenroth| 2017 7] [u et al. 2023).
This common pipeline, however, stands in contrast to the data processing inequality, foundational concept in information theory (Cover 1999), which states that the information content of a signal cannot be increased by processing the observations. Concretely, consider the Markov chain of
three random variables: y - x + 2, which denotes that 2 is independent of given x, i.e. Pa la (2) y) = Pata (2 x)) in terms of probability distributions. This implies that pz,y. (2, 2) Py (=lp))
pa (z) (2l The data processing inequality reads
T(x, v) I(2.8)
(1)

---

Published as a conference paper at ICLR 2026
where I (2, y) is the mutual information of the random variables and y In particular, if y is the class of a data sample x, this implies that there is no "benefit" in low-level processing of the sample obtaining by denoising x) before directly considering the classification problem.
Focusing on classification and referring to better (top-1) 1) accuracy as "benefit", the previous assertion be proven be true for the case of the optimal Bayes classifier (more details in Section 2) Clearly, we expect performance gaps between practical classifiers and the optimal Bayes classifier. However, modern DNN-based classifiers reach outstanding classification performance, sometimes even exceeding human capabilities. This raises the question: What can we say about the margin between this implication of the data processing inequality and practical classifiers? To the best of our knowledge, no prior work has attempted to theoretically and systematically investigate this question.
In this paper, we aim understand when and why low-level processing can be beneficial for classification, even when the classifier is "strong" (e.g., converges to the optimal Bayes classifier when the number of training samples grows). Our main contributions include:
We present a theoretical study of a binary classification setup. where we consider a classifier that is tightly connected the optimal Bayes classifier (and converges to it). In the high-dimensional setting, we prove that for any finite number of training samples, there exist a pre-classification processing (specifically, dimensionality reduction procedure) that improves the classification accuracy.
We establish theoretical results on the effect of various factors, such as the number of training samples, the level of class separation and training set imbalance, on the relative gain from the data processing procedure that we construct. For example, we show that, aon-intuttively, the maximal relative gain increases when the class separation improves.
We present an empirical investigation of the theoretical model that corroborates our theory and sheds more light on the gains from low-level processing.
We complement our theoretical work with empirical study. We investigate the effeet of image denoising and self-supervised encoding on the performance of practical deep classifiers on bench- mark datasets, where vary the size of the training set, the class distribution in the training set, and the noise level in the samples. We demonstrate trends that are consistent with our theoretical results (e.g., the one on the maximal gain), highlighting the usefulness of the theoretical setup.
BACKGROUND AND RELATED WORK
Consider the classification task, where the data (I. y) is distributed on X' x [C1, with [C] = {1..... C} and distribution denoted by Pa.y. For the binary 0 - criterion, i.e., E(j y) I( + y). the expected risk is equivalent to the error probability E[((ū(z), y)] (P((()) # y). It is well-known that this objective is minimized by the (optimal) Bayes classifier: Copt (x) argmax vEIC) Pyla (y) 2r). where Pale is the true conditional probability of given (Bishop) 2006 Fukunaga 2013). In
practice, of course, the distributions are unknown and a classifier must be learned from data samples.
Consider data processing operation A X Z. This can be denoising, super-resolution, encoding, etc. Let = = A(x). Notice that y + x - z is a Markov chain because 2 is a function of x and thus P= P=lz.g (2|2,, v) (x(x). Therefore, the data processing inequality in Eq. holds. The processed sample argmax yE|C] pula (v) where Pa|= is the true conditional probability of y given 2.
optimal Bayes classifier that operates
A(x) is given by Cope(z)
Focusing on the case of binary classification (C' = 2), the following result shows that, similarly to the fact that A can increase information, there is also no hope in improving the accuracy of optimal Bayes classifiers via data processing.
Theorem Let y + x + be Markov chain where E {1,2} denotes the sample class. We have
(x) + v) I P(Copa + y).
(2)
where Copt and Copt denote optimal Bayes classifiers.
// Pe v) log
( ) drdy. (1)))))()))
'The mutual information is defined as 1(2. v)
2

---

Published as a conference paper at ICLR 2026
A similar statement and proof can be found in an arXiv version of (Liu et al. 2019). For completeness, we present a clearer proof in Appendix A Note that (Liu et al. 2019) studies a potential tradeoff between the error of low-level restoration task and the accuracy of fixed classifier, where only the restoration model is trained using the training data. In contrast, our work focuses on the high-level end goal-the classification performance and allows training the classifier after the low-level processing, as is done in practice. Therefore, (Liu et al. (2119) does not provide any reason why in practice it is common address low-level task before high-level ones, which the central question of our paper.
Our work is motivated by the contrast between common practice and the cntommtiion-thoorettit concept of the data processing inequality, as well as Theorem [ There exist works that use information- theoretic concepts or compute approximate metrics to analyze DNNs, e.g.. (Tishby & Zaslavsks 2015; Shwartz-Ziv & Tishby, 2017, Saxe et al. 2019, Gabrié et al. 2018 Jeon Van Roy| 2002). Interestingly, since a DNN processes data gradually, lly, layer by layer, the features across the layers form a Markov chain, and thus the data processing inequality applies. Yet, avoiding the loss of information relevant to the task being learned can be attributed to penalizing failures in predicting the target labels during training, while discarding task-irrelevant information (akin to compression) may be explained by the information bottleneck principle (Tishby & Zaslavsky 2015 Shwartz-ZZiv & Tishby 2017] Saxe et al., 2019). The contrast between representation learning and the data processing inequality has also motivated theoretical works (Xu al. 2020; Goldfeld & Greenewald (02T) to study variants of the mutual information, incorporating transformations of the signal or line projections. None of the aforementioned works consider a sequence of tasks or explain when and why low-level processing can be beneficial to practical classifiers. Moreover, here we directly analyze the classifier's 's probability of error, which is more interpretable than the pooomatiionthhoreee objectives studied before.
Finally, we emphasize that in the case of pre-trained classifier under distribution shift, data processing that 'reduces the gap' between the test data distribution and the training data distribution trivially expected to improve the classifier performance. However, we focus in this paper on the non- con-intuitive case where no distribution shift occurs, and the classifier is strong, in the sense that converges to the optimal Bayes classifier as the training set increases (with good statistical properties).
3 THEORY
In this section, we present our theoretical contributions. First, we describe the problem setup, the data distribution, the classifier under study, and a data processing operation. Next, we present our theoretical results demonstrating the benefits of this data processing. Finally, we validate our results through experiments and provide additional insights into the factors that affect the performance gain.
3.1 PROBLEM SETUP: DATA MODEL, CLASSIFIER, AND DATA PROCESSING
Data model. Similar to vast body of theoretical work on classifiers (Cao et al.
2021: Deng et al..
2022 Wang & Thrampoulidis 2022, Kothapalli & Tirer 2025), we consider binary classification
(C = 2), where the data is distributed according to a Gaussian Mixture Model (GMM) of order two in X' = Rd, with one mixture component per class. Formally,
y (1,2),
y = NiHH
Ply 5) Tj.
(3)
Similar to previous theoretical works, we further assume that = =3 = o²,
#2 = - M1 = μ
T1 = π2 = 11/2,
(4)
where the magnitudes of the entries of μ are bounded by some universal constant, and a is independent of d. Let us now define the separation quality factor of the GMM data, which can be understood as the signal-to-noise ratio (SNR):
11 M1l
S =
(5)
σ + 02
o²
Note that the considered setup is standard in theoretical works that aim at rigorous mathematical
analysis (Cao et al. 2021: Deng et al., 2022 Wang & Thrampoulidss 2022 Kothapalli & Tirer 2025).
Despite its compaetness, the learning problem studied in this paper can be arbitrarily hard because (unlike some of the aforementioned works) our analysis covers SNR arbitrarily close to zero i.e.,
nearly indistinguishable classes.
3

---

Published as a conference paper at ICLR 2026
The training data consists of N, labeled i..d. samples per class j. denoted by D { j {1, 21, = .,,...,Ny}} Without loss of generality, we denote N1 = .V and N₂ = 7/V for some Y (0.1).
The classifier. In the considered setting, the optimal Bayes classifier reads:
(- || pa (..ll) 2nd
Copt (x)) arg max T (yPo)y(Z)))) arg max exp (E(122
arg min o 14yl
jE(122
(1,22
In practice, the data distribution is unknown and thus classifier cannot the class means, {pz). but rather estimate them from the training set. We therefore study the classifier:
a D) arg min || Pgyl,
(6)
jE(1,2}
where PJ 1 N2 i= Dijj is the maximum likelihood estimate of μty from the j-th class's 's samples.
E
Ny
We want to explore if data processing can be beneficial even for "strong" classifier. It is easy to see that fij ~N (uj, g( In fact, this is efficient estimator that attains the Cramér-Rao lower bound on the variance for any Nj Kay 1993). Therefore, in our setting, not only that Z(-) structurally similar to Cope(.) and converges to for N; - oc, but also has strong statistical properties for finite Nj, making it natural choice for our study. Demonstrating the benefit of low- level processing for such a classifier, which is "almost optimal" for the considered setup, underscores the potential advantages for weaker classifiers.
Data processing. As the pre-classification data processing, we are going to study certain linear dimensionality reduction to S k < d. Specifically, we consider
Ax
with Rxxd that obeys
AA = Ik.
||u|||
||||||
Note that, for establishing our main theoretical claim on the practical limitation of Eq. 2 we just need the existence of processing for which we can rigorously show improved classification. Nevertheless, in the sequel, we provide a constructive proof that also shows how such can be learned from unlabeled data without prior knowledge of μ.. Hence, showing that this procedure improves classification performance in our setup underscores the promise of practical low-level procedures learned from unlabeled data.
Additional notations. We will analyze and compare the performance of the classifier in Eq. before and after the data processing procedure, namely, a(;; D) versus 2(2;2=), where D= 1,...,NNj N2}. We denote the probability of error in these two
{zij = Ax; : j E [1,2), cases by Pa (error) := (P(((>;; D) ff y) and Ps (error)) == P(](z; Dz) A y). Finally, we define the widely-used Q-function, which will be used to characterize the classification error probability:
((x) PP)(PP x)
exp (- 2-2) dt.
2n
3.2 THEORETICAL RESULTS
In this subsection, we present our theoretical results. In Section 3.2.1 we prove that the error probability decreases due the data processing. To this end, we establish expressions that accurately approximate the probability of error of the data-driven classifier before and after the processing. We then analyze their relation, where, due to different proof strategies, this is done separately for the balanced and imbalanced training set cases. Section 3.2.2 we provide a fine-grained analysis of the factors that affect the efficiency of the processing, and, for the balanced training set case, also establish a connection between the maximal gain and the SNR.
The proofs for all the claims deferred to Appendix A
4

---

Published as a conference paper at ICLR 2026
3.2.1 PERFORMANCE GAIN DUE TO DATA PROCESSING
We begin with characterizing the probability of error when the classifier applied without pre- processing. Recall the definitions of S and ((r) in Eq. 5 and Eq. respectively.
Theorem 2 (The probability of error before the processing). Consider the setup Section 3.1
With
approximation accuracy O(1/V vd) we have pæ (error) R Pa (errorr) = p(S, N, 7, d), where
vs
+ 4N
1-7
iS,,, 13,,N,,d) = 2 IN
V/
1+
14,²
d
+1
7
7
YN
(9)
VS
1-2
d
o
VS
1
147
+1
AN
8N2 7
Remark. The proof is mathematically involved. We express the error event as thresholding scalar random variable, suitable for an application of a generalized Berry-Fsseen theorem. However, this variable depends on the interrelation between the entries of #11. P2g and computing the required moments is technical challenge.
Discussion. Note that: 1) P is symmetric in the following sense: p (S,,N, = (
which is expected because swapping the amount of samples between the classes does not change the problem; 2) As S -> 0+ we have: lim P(S, N, d) 1/2, aligned with uniform guess; 3) As 5-00-
S have: lim N,
aligned with the classes being deterministically separable;
S-000
and 4) As N + do have: lim N(S,N,,, d) Q(VS), which is the probability of error of Copt+
N
which knows the exact distribution of the data (Fukunaga 2013
Let us explore the result of Theorem 2 for the case of balanced training data, 7 = (N₂ Ni = N),
in which the expression simplifies to:
Vs
Pa (error) = Q d +1)
(10)
48
N2
Fix >> 1, which ensures that the approximation is accurate. is easy to see that when the separation quality factor (SNR), S, decreases (with fixed df), the argument of the Q-function decreases, and thus the probability of error increases. In addition, as the number of training samples N increases, the argument increases, and thus the probability of error decreases. These two results are aligned with intuition. Interestingly, the effect of secreasin/ddecreasing d depends on its relation with S. For example, if d increases and S is fixed, which means that the average entry-wise SNR decreases, then the argument of the Q-function increases. The contrary holds if S x d, which means that the average entry-wise SNR fixed. In the latter case, high-dimensionnaityy is advantageous in terms of the probability of error.
Next, let establish the existence and learnability of the data processing proposed in Section 3.1
Theorem 3 (The existence and learnability of the processing). For all 1 < k d, there exists dimension- ddmeension-reduccnng reducing matrix A k with the properties stated in Eq. 7 Furthermore. given
sufficiently many unlabeled samples, such a matrix can be learned to arbitrary accuracy.
Remark. The proof of Theorem is constructive. It provides an algorithm for computing such A and efficiently estimating the direction of from unlabeled data.
Note that the semi-orthonormality of A implies that cannot increase the norm any vector, while the property |Aμi|| ||هه|| ensures that the separation quality remains unchanged (equal to Eq. 5) and is not reduced after the processing. In more detail, this implies that when applying Ax, the class-dependens component of (i.e., the projection of æ onto =44 is not attenuated. In contrast, the complementary component of x, which corresponds to within-class variability, is attenuated as the overall dimension is reduced and the cemi-orthonommalty of A prevents amplification. Taken
5

---

Published as a conference paper at ICLR 2026
together, this is expected to facilitate classification, will be rigorously proven below. More details and graphical illustration of the action of are presented in Appendix
We now turn to characterizing the probability of error when applying the classifier the processed data x = Ax.
Theorem 4 (The probability of error on the processed data). Consider the setup in Section 3.1 With
approximation accuracy (01/V/)) we have Ps (error) ~ Ps (error) (S N, 7, k), where P is defined in Eq.
The approximate probability error of the processed data, Pa. (error), admits an expression similar to the one obtained for the raw data, P= (error), but with different dimension parameter (k: instead of d). Note that in the high-dimensional case, i.e., d, k > 1, these estimators are guaranteed to be accurate. Now, let present the main outcomes of our theoretical study, which build on these expressions.
We start with the case where there is no class imbalance in the training set, i.e., so N₂ Ni N. The next theorem shows that the considered data processing yields a gain for any finite value N 1. We assume S > 0, S 0 is an uninteresting degenerate case.
Theorem 5 (Performance gain under balanced training data). For 7 and for all S > is < d, and N E N, we have
Pen (error) > fz (error).
(11)
Theorem shows that when the training samples are balanced among the classes, the chosen processing always strictly decreases the approximated probability of error.
Discussion. As shown in Theorems 2 and in the high-dimensional case the true probabilities of error, Pa (error) and P=(( (crror), are well approximated by Pav (error) and faz (error). This makes the result significant. Moreover, this result esuuiighodding for any finite N-is also quite surprising, since in the limit of N + oo we have that P* (error)) and ps (error) converge to P(Cope + v) and P(Cope (z) f v), respectively, which satisfy the opposite relation (5) shown in Theorem
We now consider the case of an imbalanced training set. The presence of under-representeed classes or groups is of significant interest in the machine learning community. as raises concerns about generalization and fairness (Chawla et al. 22002 Huang et al. 2016 Li et al. (021). Specifically, while the classes have equal probability (Ti 22 0.5), the number of training samples from each of the classes is assumed to be N₁ N and Nr >NN with 0 < 1. The following theorem demonstrates the benefit of the considered data processing this case as well.
Theorem (Performance gain under imbalanced training data). Let < <1, <
k < d. IfN 2
2--4++ then we have
27(1+7)
Pu (error) > Pa (error).
(12)
Remark. Unlike Theorem which considers 7 and is smoothly obtained from Theorems [nd
in this case the complexity of the formulas of Pa (crror) and P. (crror) required us to make technical assumptions on S and N in order to establish rigorous statement for y E (0. 1). Nevertheless, these assumptions are reasonable and still encompass the interesting case of low SNR and reasonable number of training samples. Note that for y 2 0.162, the requirement N 72-4x+1 is vacuous (since N > 1), so it only matters under severe imbalance (y < 0.162).
2y(1+%)
3.2.2 FACTORS THAT AFFECT THE PERFORMANCE GAIN
So far, we have only considered the relation between Pu (error) and Pa (error). Let us now discuss the margin between them, which reflects the efficiency of the processing.
Definition 1. We define the theoretical efficiency of the processing as
Pax (erro))))) - P2 (error))) Pmx ((rror))
=
100.
(13)

---

Published as a conference paper at ICLR 2026
The following theorem establishes an approximation of for N > 1, making it easier gain insights into the different factors that affect the efficiency of the processing in the case of a large number of training samples.
Theorem (Analysis of the asymptotic efficiency). S 0,
< S 1. Denote by NT = (1 + 7) N the total number of training samples. With approximation accuracy ((1/N we have
11 2/2 VS. Q (vV))
25
exp (-2)
3+ 27 + (d (d- k)
1)
1
(14)
Nr
In particular, for NT > 1: The efficiency increases when d - k increases or decreases within 0 < 7 S 1/v2; The efficiency decreases when S increases or NT increases.
Remark. The proof of Theorem 7 is based on first-order analysis, which differs from the proof technique used for Theorem 6 This allows us reach the conclusion that there exists No N such that for all N 2 No we have >> O (since the right-hand side of Eq. [4jis positive) which implics pe (error) > (error) without a technical assumption S. On the other hand, Theorem even for small values of N, depending on 7
6 can hold
Discussion. Let us discuss the intuition behind the insights provided in Theorem 7 First, notice that in the considered regime of Nr >> 1 training samples, the processing efficiency 1) monotonically decreases toward zero as Nr increases. This is consistent with the fact that in the limit Nr - oo the classifier approaches the optimal Bayes classifier, which cannot be improved by data processing. In this regime, higher class separation S can be interpreted as equivalent to having more effective samples (akin to larger Nr), and hence less improvement through the pre-classffication processing. Similarly, larger dimensionality reduction (d k) can be viewed as greater coverage of the input domain, again, analogous to having more samples. Lastly, lower < indicates that the classifier's training samples are less balanced between the classes and hence differ more from the data distribution. Intuitively, this leaves more room for improvement through pre-classification processing.
In addition, Appendix B provides an approximation of the difference A == Pax (error) - P2 (error) for N >> 1. The insights we obtain consistent with those reported in Theorem 7
So far, our theory shows that the processing efficiency v) is positive for all N for y = 1, and under technical assumption it is positive also for 7 E (0, Our formulas also show that 7y 0 at N = 0 (where P= = i0 = 0.5, i.e., probability of guessing) and that r7 + 0 at N + co (where á= P.. Q(VS). consistent with the classifier converging to the optimal Bayes classifier for which Theorem D applies). Together, these imply that there is maximum point of (N). Our final theorem provides surprising insight into this maximum efficiency.
Theorem 8 (Analysis of the maximal efficiency). Fix ry = 1, and let S > 0, S k < d. Consider the efficiency 1) = (TN)) as a function of continuous N R4. We have that the maximal efficiency Tmax max 77( (N) increases as a function of S.
N20
Discussion. In the asymptotic regime of N + oc, as discussed above, a higher SNR corresponds to lower 7,, which aligns with intuition. Interestingly, however, the theorem shows that higher SNR also leads to a larger 7max. which is somewhat counterintuitive. One might expect that lower noise would reduce efficiency across all sample sizes, since the raw data is already well-separated. This highlights the subtle relationship between 1) and the SNR. An extended version of the theorem can be found in Appendix A.8
3.3 EMPIRICAL VERIFICATION
In this subsection, we simulate the theoretical setup in order to further support our theoretical results and also gain more insights the model, e.g., factors that affect the efficiency of the data processing for small to moderate values of N.
We consider data dimension d = 2000, and fix 1. The SNR values we work with are S (0.75², 1.52), and for each fixed SNR, we use y E {0.25, 0.5, 1}. We also consider a wide range of Nuin. which denotes the total number of given training samples. For each fixed tuple (S, 7,,7, Nurin).
7

---

Published as a conference paper at ICLR 2026
Cereta via
A Ithory.
Ourena Dimmatte
thooy
N_rram
N tram
(a) S 0.75
(b) 8 1.5²
Figure 1: The theoretical setup. Efficiency of the data processing procedure versus the number of training samples Nirin for various values of the training imbalance factor, 7, and the SNR, S.
we randomize μ E Rd with |e|| = OvS, via μ = -VS v where v ~ N (N, Ia). We then Tell
construct the data processing matrix A E Rixd that reduces the dimension to 1000, using the algorithm described in Appendix A.3
trial, we sample N₁ = int Num training points from I+y
training points from N NH, Before and after the data processing, the per-class means are estimated using the training points, and the classifier defined in o is used on large amount of fresh test data, sampled with probability 0.5 from each of the two Gaussians. With a slight abuse of notation, we denote the empirical probabilities of error before and after the data processing by ps (error) and Pa (error), respectively. In order to compute pa (error), we use the training and test samples after processing them by multiplying with A. We then compute the empirical efficiency of the processing, defined by X (error))) Sosrror)-Paaeeeee pa Ps (error))
W(-u, Ia), and N2 int 7/Nmm
1+7
100. We repeat the
computation of X over 100 independent trials and report the average.
Figure presents both the theoretical efficiency y), defined Eq. 13 and the empirical efficiency X versus the number of training samples Nurin- for various values of and S. Note that the empirical and theoretical efficiencies closely match all the configurations.
Let us discuss the trends that are observed in Figure T First, note the non-monon monmoontoonic curves depicting the efficiency as function of Nirin When Nurin approaches zero or grows to infinity the efficiency tends to zero, aligned with our analytical formulas. Indeed, as discussed above, in the absence of training data the classification is based on guess, and thus there is no effect for the data processing. In the considered setup, as Nmain + oo, the classifiers tend to the optimal Bayes decision rules, which again implies zero efficiency. A major contribution of our paper is providing rigorous theory for the fact that the efficiency remains positive between these two extreme cases.
Let us now focus on Nuain >> (the right boundary of each sub-figure), We see that increased S moderately reduces the efficiency. For example, for (S, Nurain = (0.75² 1, 10K) the efficiency is around 6, while for (S, 7, Nirain) = (1.5², 1, 10K") it is around 5. Moreover, see that lower values of y, corresponding to more imbalanced training data, yield higher efficiency the data processing. Note that both aligned with the insights gained in Theorem 7
Next, note that each the curves depicts a single maximum point, whose value aligned with the non-intuitive prediction of Theorem Specifically, the maximal efficiency value increases with S.
Lastly, note that the empirical investigation our theoretical setup reveals behaviors at relatively small values of Nuain which lie beyond the scope of our theoretical analysis. Specifically, we observe that the relation between decrease in y and increase efficiency emerges already at quite low Nmmin We also observe dependency between the overall shape of the curves and the value of S.
Additional verification experiments with A that learned from unlabeled samples, and different values of S, k are presented in Appendix F All of them aligned with theoretical insights.
EXPERIMENTS IN PRACTICAL SETTINGS
While our paper focuses on theoretical contributions, in this section, we empirically examine the corrlation between the behaviors observed in four practical deep learning settings and the theoretical
8

---

Published as a conference paper at ICLR 2026
12.5
Effiienccy (98)
30
Elicenoy
10.0
25
0.0
5200
10100
1500)
20030
25200
33000
35000
5000
10000
30000 35000 15000
20030
25000
N. train
N. t.trran
(a) 0.25,
(b) a = 0.4,
Figure 2: Noisy CIFAR-10 and pre-classification denoising. Efficiency versus Nirain-
results. Note that such study, which examines the effects of sample size, SNR, and class balance, requires exhaustive training efforts of both the data-processing module and the classifier.
4.1 NOISY CIFAR-IO AND PRE-CLASSIFICATION DENOISING
We consider the CIFAR-10 dataset (Krizhevsky et al. 2009) and the ResNet18 model (He et al. 2016). The train and test sets both experience additive Gaussian noise of the same level (i.e., no distribution shift) with standard deviation a f0.25, 0.4). detailed description of the training procedure of the classifier is given in Appendix C We also note that we verify that the classifier performs well when trained clean CIFAR-10 data, achieving 90% accuracy.
The data processing step examined here is image denoising, applied to the noisy data, using the DnCNN model (Zhang et al. 2017). The denoiser trained with the MSE loss on 15,000 clean unlabeled images, which are not part of the classifier's training set. More details on the training procedure of the denoiser are given in Appendix C Note that, given such pretrained denoiser, the Markov chain: "noisy image" "deeoisddd image" still holds. Thus, the data processing inequality, as well as Theorem suggest that the denoiser will not improve the results.
In Appendix C we also investigate another setting, where we train the denoiser with SURE loss (i.e., without clean ground truth images) (Stein 1981. Soltanayev & Chun 2018), and observe similar results.
consider various values Nirain the total number of given training samples (across all 10 classes), and examine different training imbalance factors, here, and E (0.5, 0.75) in Appendix C For both the denoised and the noisy case, and for each fixed tuple (a, y, Numin), divide I+7
Nuw equally
among the first 5 classes, and NNNu I+y equally among the other classes. We train the classifier 6 times, each time with different seed, and report the average and standard deviation of the probabilities of error, to obtain a more reliable result. After we have the mean and standard deviation of the probability of error before and after the data processing, relative percentage change the probability of error induced by the denoising step.
compute the empirical efficiency, i.e., the
Figure presents the efficiency versus Nurin We see two main similarities to the theory. First, the non monoonootoocc behavior (increasing for small Nuain and decreasing for large Nuaii) ) is expected from the same argument in Section 3.3 the efficiency tends to zero Nuzan tends to either 0 or co, while, importantly, it remains positive between these two extreme cases, aligned with our theory. Second, see that the maximal efficiency value decreases with its value for 0.25 is larger than its value for = 0.4. That is, the maximal efficiency increases with the SNR.
4.2 NOISY MINI-IMAGENET AND PRE-CLASSIFICATION ENCODING
We turn to investigate a more complex data processing pipeline using the Mini Mini- ImageNet dataset (Vinyals et al. 2016) and the ResNer50 model. Both the training and test sets are subjected to additive Gaussian noise with standard deviations E (50/255, 100/255) The data processing step examined here is an encoding step, which maps the images from 224 x 224 pixels 256- dimensional embeddings. This encoder model follows (Lu et al. 2025) and is trained from scratch with eeff-uupevvision all noisy unlabeled images for each noise level. Then, for each combination of (a, y, Nuain), we divide New equally among the first 50 classes, and Nosi 1+7 equally among the other 50 classes. Then, across three seeds, train ResNet50 model the noisy images and, in parallel,
I+y

---

Published as a conference paper at ICLR 2026
25
Effic sancynnc
-2
36062
K.tran
(a)
253 Y
(b)
255 7
Figure 3: Noisy Mini-ImageNet and pre-classification encoding. Efficiency versus Nurin-
small MLP on the corresponding embeddings. After we have the mean and standard deviation of the probability of error before and after the data processing, compute the empirical efficiency, i.e., the relative percentage change in the probability error induced by the encoding step. Details training procedures for both the ResNet50 and the MLP are provided in Appendix D
Figure presents the efficiency versus Nuain for 7 = 1. Experiments for y E {0.5, 0.75} appear in Appendix D We see the same trends that are aligned with our theory before: 1) similar non- monotonicity of the curve while remaining positive, and 2) the maximal efficiency increases with the SNR. A message to practitioners is that when labeled samples are scarce, data processing be especially advantageous for 'high quality" data.
4.3 NOISY CIFAR-10 AND PRE-CLASSIHCATTOE ENCODING
we also examine the performance of data processing based on encoding instead of denoising. Due to space limitations, the details are deferred to Appendix E and the results are presented there in Figure 9 The trends stated above are observed there as well.
For the noisy CIFAR-10 setup considered in Section
These results further demonstrate higher efficiency values compared to those obtained for the de- noising procedure Section 4.1 indicating that, for the classification task, encoding may more effective low-level processing method than denoising. However, believe that this may not be the case for other high-level tasks, which may require preserving spatial information the image (e.g.. object detection).
5 CONCLUSION
In this paper, addressed the question: How explain the common practice of performing a "low-level" task before a "high-level" downstream task, such as classification, despite theoretical principles like the data processing inequality and the overwhelming capabilities of modern deep neural networks? We presented a theoretical study of a binary classification setup, where we considered "strong" classifier that is tightly connected the optimal Bayes classifier (and converges to it), and yet, we constructed pre-classification processing step that for any finite number of training samples provably improves the classification accuracy. We also provided both theoretical and empirical insights into various factors that affect the gains from such low-level processing. Finally, we demonstrated that the trends observed four practical deep learning settings, where image denoising or encoding is applied before image classification, are consistent with those established by our theoretical study.
Our work motivates ongoing research on signal and image restoration and enhancement (Garber & Tirer 2024 2025 Zhang et al., 2025 Hen al. 2025) and other low-level tasks. Since it shows the benefit of low-level tasks even when the classifier's 's training and test data share the same distribution, naturally suggests an even greater advantage in out-of-distribution scenarios. As directions for future research, it would be valuable to extend the theoretical analysis to high-level tasks beyond classification or to investigate non-lineat low-level processing. Another interesting direction is to study the optimal low-level processing corresponding given high-level task.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
The work was supported by the Israel Science Foundation (No. 1940/23) and MOST (No. 0007091) grants. LLMs were used only polish the writing.
REFERENCES
Christopher M Bishop. Pattern recognition and machine learning, volume 4. Springer, 2006.
Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-parametent wer-parameterized maximum margin classification on sub-guusee gaussian mixtures. Advances in Neural Information Processing Systems, 34: 8407-8418, 2021.
Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Dengxin Dai, Yujian Wang, Yuhua Chen, and Luc Van Gool. Is image super-resolution helpful for other vision tasks? In 2016 IEEE Winter Conference on Applications Computer Vision (WACV), pp. 1-9. IEEE, 2016.
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(2): 435-495. 2022.
William Feller. An introduction to probability theory and its applications, Volume 2, volume 2. John Wiley & Sons, 1991.
Keinosuke Fukunaga. Introduction to statistical pattern recognition. Elsevier, 2013.
Marylou Gabrié, Andre Manoel, Clément Luneau, Nicolas Macris, Florent Krzakala, Lenka Zde- borová, et al. Entropy and mutual information in models of deep neural networks. Advances in neural information processing systems, 31, 2018.
Tomer Garber and Tom Tirer. Image restoration by denoising diffusion models with iteratively preconditioned guidance. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 25245-25254, 2024.
Tomer Garber and Tom Tirer. Zero-shot image restoration using few-step guidance of consistency models (and beyond). In Proceedings of the Computer Vision and Pattern Recognition Conference, pp. 2398-2407, 2025.
Ziv Goldfeld and Kristjan Greenewald. Sliced mutual information: A scalable measure of statistical dependence. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Muhammad Haris, Greg Shakhnarovich, and Norimichi Ukita. Task-driven super resolution: Object detection in low-resolution images. In Neural Information Processing: 28th International Confer- ence, ICONIP 2021, Sanur: Bali, Indonesia, December 8-12, 2021, Proceedings, Part V 28, pp. 387-395. Springer, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Liav Hen, Tom Tirer, Raja Giryes, and Shady Abu-Hussein. Robust posterior ieftusion-basedd sampling via adaptive guidance scale. arXiv preprint arXiv:2511.1847,, 2025.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019.

---

Published as a conference paper at ICLR 2026
Chen Huang, Yining Li, Chen Change Loy, and Xiaoou Tang. Learning deep representation for imbalanced classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5-7553375555 2016.
Hong Jun Jeon and Benjamin Van Roy. An information-theorrtic framework for deep learning. Advances in Neural Information Processing Systems, 35:3279-3291, 2022.
Steven M Kay. Fundamentals of statistical signal processing: estimation theory. Prentice-Hall, Inc., 1993.
Vignesh Kothapalli and Tom Tirer. Can kernel methods explain how the data affects neural collapse? Transactions Machine Learning Research, 2025. ISSN 2835-8856.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Sohyun Lee, Taeyoung Son, and Suha Kwak. Fifo: Learning log-invariant features for foggy scene segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 18911-18922 2022.
Chengyang Li, Heng Zhou, Yang Liu, Caidong Yang, Yongqiang Xie, Zhongbo Li, and Liping Zhu. Detection-friee frrenddly dehazing: Object detection in real-worke hazy scenes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(7):8284 8295, 2023.
Mingchen Li, Xuechen Zhang, Christos Thrampoulidis, Jiasi Chen, and Samet Oymak. Autobalance: Optimized loss functions for imbalanced data. Advances in Neural Information Processing Systems, 14:3163-3177 2021.
Ding Liu, Bihan Wen, Xianming Liu, Zhangyang Wang, and Thomas S Huang. When image denoising meets high-level vision tasks: A deep learning approach. In 27th International Joint Conference on Artificial Intelligence, IJCAI 2018, pp. 842-848. International Joint Conferences on Artificial Intelligence, 2018
Dong Liu, Haochen Zhang. and Zhiwei Xiong. On the classificaioon-diitttiioon pitpraioiooottooooorppiooooooooo tradeoff. Advances in Neural Information Processing Systems, 32, 2019.
Wenquan Lu, Jiaqi Zhang, Hugues Van Assel, and Randall Balestriero. Ditch the denoiser: Emer- gence of noise robustness in self-supervised learning from data curriculum. arXiv preprint 12X.1:2505..2191, 2025.
Yanting Pei, Yaping Huang, Qi Zou, Yuhang Lu, and Song Wang. Does haze removal help enn-based image classification? In Proceedingy of the European conference on computer vision (ECCV), pp. 682-697, 2018.
Andrew M Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan D Tracey, and David D Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124000, 2019.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box deep neural networks via information. arXiv preprint arXiv: arXiv:103.000 000.0700300000.. 2017.
Maneet Singh, Shruti Nagpal, Richa Singh, and Mayank Vatsa. Dual directed capsule network for very low resolution image recognition. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 340-349, 2019.
Shakarim Soltanayev and Se Young Chun. Training deep learning based denoisers without ground truth data. Advances in neural information processing systems, 31, 2018.
Taeyoung Son, Juwon Kang, Namyup Kim, Sunghyun Cho, and Suha Kwak. Urie: Universal image enhancement for visual recognition in the wild. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings. Part IX 16, pp. 749-765. Springer, 2020.
Charles M Stein, Estimation of the mean of a multivariate normal distribution. The annals of Statistics, pp. 1135-1151, 1981.
12

---

Published as a conference paper at ICLR 2026
Tom Tirer and Raja Giryes. Image restoration by iterative denoising and backward projections. IEEE Transactions on Image Processing, 28(3):1220- 1234, 2018.
Tom Tirer and Raja Giryes. Back-projection based fidelity term for ill-posed linear inverse problems. IEEE Transactions on Image Processing, 29:6164-6179, 2020.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 ieee information theory workshop (ihw), pp. 1-5. leee, 2015.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal on Mathematics of Data Science, 4(1):260-284, 2022.
QuanLin Wu, Hang Ye, Yuntian Gu, Huishuai Zhang, Liwei Wang, and Di He. Denoising masked autoencoders help robust classification. In The Eleventh International Conference on Learning Representations, 2023.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable infor- mation under computational constraints. In International Conference on Learning Representations, 2020.
Jonghwa Yim and Kyung-Ah Sohn. Enhancing the performance of convolutional neural networks on quality degraded datasets. In 2017 International Conference on Digital Image Computing: Techniques and Applications (DICTA), pp. 1-8. IEEE, 2017.
Bingliang Zhang, Wenda Chu, Julius Berner, Chenlin Meng, Anima Anandkumar, and Yang Song. Improving diffusion inverse problem solving with decoupled noise annealing. In Proceedings of the Computer Vision and Pattern Recognition Conference, pp. 20895-20905, 2025.
Kai Zhang, Wangmeng Zuo, Yunjin Chen, Deyu Meng, and Lei Zhang. Beyond a gaussian denoiser: Residual learning of deep enn for image denoising. IEEE transactions on image processing, 26(7): 3142-3155, 2017.
Kai Zhang, Yawei Li, Wangmeng Zuo, Lei Zhang, Luc Van Gool, and Radu Timofte. Plug-and play image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44( (6110)6360--333 2021.
Chong Zhou and Randy C Paffenroth. Anomaly detection with robust deep autoencoders. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 665 674, 2017.
13

---

Published as a conference paper at ICLR 2026
A PROOFS
A.1 EXISTING RESULTS
Let us present proof for Theorem I which is similar to a proof that can be found in an arXiv version of (Liu al. 2019). but better clarifies how the Markovianity used.
Theorem 1. Let y x + be Markov chain where E {1, 2} denotes the sample class. We have
P(Copt (2) + - P(Cope (2) + y).
where Copt and Copt denote optimal Bayes classifiers.
Proof. Let us denote by X, Z the supports of r, 2, respectively, and by
P = (2 = 1), P2 = (2 2), the prior probability for the binary label E {1, 2). Let also define:
(15)
Prj (E) = P (I { | 1) Pm2 (E) = P (ax = 1
(16)
Now, from Eq. 15 and Eq. 16 the probability of error of the optimal Bayes classifier reads:
P (Copt (x) F))
Σ
min (Pipa, (E), P2P.ng (E))
CEX
(17)
1
1
PiPx, (5) P2Pu2 (E)
2
2
tEX
Similarly to Eq. 16
we define:
Pa, (C) = (z c1y= 1),
: P( 1 2)
(18)
From Eq. 15 and Eq. 18 the probability of error of the optimal Bayes classifier reads:
P (Copt( (2) x) =
Σ
min (Pips, ((P)s()))
CEZ
(19)
1
(iP,, (2)=2(())
2
2
CEZ
From Eq. 18 and the Markov assumption, we expand:
(z)(S)= = P===) = Σ
P (2 5,
Σ
P (2 -( a E, y PP (x = $|v=i)
SEE
(20)
Σ P2 1 E i)
Σ
(S (5).
SEA
The key step is the fourth equality, which eliminates the dependence on y in the first factor of the summand. We also denote
Pa12(C (5 (1/ ( = TP = x
14

---

Published as a conference paper at ICLR 2026
By substituting Eq. 20
into Eq.
19
get:
1
P (CCor((z)
x)
PPipa (S) (c)
2
2
SE2
1
Σ
PiPs ( ()p2) (5) (e ()p
2
(E2
EEE
1
Σ Σ
PS (5) -PiPe, (5) - P2P
2 2
SEZEEX
1 Σ
E
IPiPer (5) - P2P (9)
(21)
2 2
ÇER CEZ
1
Σ
[PiPe] PoPra( (5)1
Σ Psta(S15 (E)
2
SEX
ÇEZ
1
1
PIPE. (E) P2PE. (E)l
2
2
P (Copt (1) # y)
Let us now present a theorem that will be utilized in the proof of Theorem 2
Theorem 9 (Generalized Berry-Esseen Theorem, (Feller 1991 Let X X2.... Xa be independent random variables with:
Means i3s E[X,].
Variances E Var(X;).
Third absolute moments pa E |x. m/1*)
Define the normalized sum:
1 Σ(x: mp). Sa
v V d Dim & t=1
Then, there exists an absolute constant Co > 0 independent of d such that:
Co CoL
sup |P(SI > x) - 2(x) -
zER
d
In the following subsections, present the proofs of Theorems
2 3 4
A.2 PROOF OF THEOREM 2
Proof. The probability of error is
Pa (error) P (e(x) + v) - .P.
. (((x)) 2 1) + + (((x)) 11y= ylyy)) 2)
P (é(x)) = 2 1) P (((x) = 2)
2
(22)
2 (11,2) + 2 (2,11)
15

---

Published as a conference paper at ICLR 2026
where we used the assumption of uniform prior and defined
q(i.j) = P (Ō(x) = =jly = i).
(23)
Following Eq.
the first conditional probability of error g(1, 2) reads:
g11, 2) P [| 1=211 < || - p211 y 1)
PP ((:: (22) (ar (12)
(æ= -mn) T
(a: (1)) y =)
(+" TTa x - x pi2 - P2 a + m2 i22 < To x x po - Fo x
+
(-2p) x + || ? < _ x + ف 2 y v==
= (2 (11) Tx >>>> | 1|
7 2 1y=1)
(24)
1
2
ف |
P
(N2 ) T x
y = 1
2
| 2
(f2 ) TT. x
>
000y=1
2
P (w > y = 1)
where we defined
w (م - 11) x
1
|| - 112.112)
(25)
2
Let us define
y1 = (f12): Iz - (fi1); J2
(fi)) + 2 (Zi)
(26)
Thus,
V/+
(27)
In total, from Eq. 24 Eq. 27
it follows that:
d
(1, =
Σ yi > 01>001111
(28)
The setup of our theoretical investigation clearly implies that the random variables { defined
in Eq. 26 are independent, and thus we can apply Theorem 9 Let us now compute the following expressions, that will be crucial when applying Theorem 9
1.
17 Elys]
(29)
2.
2 = Var(y))
(30)
3.
P: E | me
(31)
Note that:
o² Ia pbj: N,
i ~~ N
Thus, given equations Eq. Eq. for each 1 sis < d, we have:
P5. = (7,); ~ N (11)): N,
0²
Iz y = 1~ 1NN((-M,
1
(32)
16

---

Published as a conference paper at ICLR 2026
and from Eq. 26 it follows that:
= P2, - P1, P22 + 2Pi,i
(33)
where from Eq. 4 Eq. 32 we have:
o² N ( (i No PI, N (-Mis N1 )
o²)
P2,
(34)
For every S i S d, let define the following random variables:
ag
(p2. P1.)) Isi by = P2.; pî..
(35)
Thus, from Eq. 33 it follows that:
y1 02 b.-
(36)
We first compute
EEy;] From Eq. 36 it follows that:
m
E
[a,]
2 B [b.]
(37)
We now compute each expectation separately. From Eq. 32 Eq. 34 and the assumption indepen- dence, it follows that:
E [a:] = EE [p2, EE [22
E
[p2,i]
IE [xx]]] E [1..]] E [r:]
(38)
-14
2p²
and
[b6,] = Elp3,1 - EE [pi.]]
0²
0²
+ m
+ m3
N2
N1
1
(39)
2²
7N
N
1
r²
7
Thus, from Eq. 37
Eq.
38
Eq.
39
have:
7i
2
2
1
g2
N
2212
2/1
+
1 1-7 o²
7 2N
(40)
We now compute
? Var(y:) From Eq. 36
we have:
?? Var(y:) Var(a:) 1
Var(b.)) Cov (ai, bz).
(41)
4
We now compute each piece separately, starting from Var(a,). From equations Eq. Eq. 38, it follows that:
32
Eq.
34
Eq
35
Var(a:) E[aa E[a,]2
= E (p2 - p1,.) )2]
.E [ 444
117 0²
N + +/4
.02 + +++?) 444
(42)
1+7 4
1 11
+ 117
+ 402
Y
N
N
17

---

Published as a conference paper at ICLR 2026
where we used the statistical independence between P2.., P1, and Eq.
34
to conclude that:
P2, Pı, ~ N
2/15
a²
-
PId ~ N p2;
2pc
1
++7
o²
(43)
Ni
N2
N
We now compute Var(b;). From equations Eq. P2. PI, it follows that:
34
Eq.
35
and the statistical independence between
Var(b,) Var (p²,:
p(,,)
Var (p5,)) + Var (pi.)
20
0²2
+ 20 2
+ 2/16
+ 2/0
N₂2
N₂
N1
N1
(44)
20
402
2
20a
402
+
+
N +
N2
7N
N
1+
20
1 + 7
402
722
N2
7
N
where we used the fact that if x ~ N (Mez o²), then
Var(x²) E|r*] - _[
(30² + 60 2 + (1 - (o² + =²)
(30 + 60 + +x+) - (0² + 20 + k2)
20 + 40
20 (o + 2
Finally, we compute Cov(a,, b,). From equations Eq. that:
32 Eq. 34
Eq.
35
Eq
38
Eq
39
it follows
E [a,b:] B[a,] B[b;] Cov(a, b,)
1-
20²
= [(2, PI.)) (p2, př.)) xx:
+
γ N
1 1-7
20 kt
(E [pă.] E [p2.1] E [pi.]]
E
[p.:s]
E [pž.1]
+ E [pi,,]) E [2::]
N
((
(#) + 3/4
g²)
o²
+ +
(
a² + 1²² - -(1² + 3/4
o² N1
-
N₂
N1
1 1-7
20
+
7
N
0²
G²
1-
20
444:
7N
N
7
40 k3
402
1- 2
20 4
N
>N
71
N
1-7
40
1 1-7
20 4
7
N
7
7
20
7
N
(45)
where we used the fact that if x N (Mas o.), then
Blar3|
11 + 3
(46)
18

---

Published as a conference paper at ICLR 2026
Thus, from equations Eq.
41
Eq. 42
Eq. 44
Eq. 45
follows that:
== 1++1
0²
1 1+7 o²
+ 40²
?
N
7
N
(1
7² 20
1 7
402
1-7_
20
4
72
N2
7
N
7 N
1 1+
04
1+
04
1+?
20²
7
20²
+ 14
+ 40
(47)
7/2
2N2
N
N
+7
0²
1
1+
0²
+ +11
1
+
+
1 7
?
N
2
N2
27
N
27
N
117 d²
1
1+
0²
1
=0²
+ App
1+
N
27
N2
?NN
We get the following lower bound:
01
(1
1+
2
=
(48)
N
27²
N
Finally, we compute Pi lI: n7
We will show that pa is globally bounded. We first note the
following inequality, which holds for any real- random variable with B[x*] < oo:
[ (E [==])*
This is a consequence of Lyapunov's inequality. Setting x y: 14 yields the following upper bound:
P: E 1y: m/1 S E (v: m)) m)'))
(49)
We now expand:
(us n1)* = v/= - 43 + Gu?'! - 4y.th + 1//
which, from Eq. 49 implies that:
P S (Blyf) 4m/ 11y'"1 + 6Ty Ely?) - 47/ Elys] + 11,)) 3
(Bly/) 4n: Elv:' + 67Ł (Var(w)) + B(y;12) 3ml) $
(50)
(Bly/1 4n, El ,. (E + n/²) 3nf)
(Ely/) 4n, |B + 67 3n +
where we used the definitions 5 Var(w:). 1 Emyr]. It is now left to compute
X = Ely'), &, EMA
(51)
which implies, from Eq. 50 that
p (x: 45,m + Gg2 3nt)
(52)
Let ʃ E (n.52,0,xx x). We argue that for all Sis S d:
dliff)
f= Σ
fi, n
(53)
k=0
where q(i, f) E N and the constants {cu (i, n
(9t,)) follows that structure in equations Eq. 40 Eq. 41
don't depend on d. We already saw that m/s E
We now compute d, From Eq. 36 follows that:
(al 1
8,
E
b,
2
(54)
3
=
E 2
E
aa5byy bu)
+
[abb)]
[b,
2
4
8
19

---

Published as a conference paper at ICLR 2026
now compute each part separately, starting with B.a]]. From equations Eq. 32 Eq. 35 assumption of independence, follows that:
and the
E
(P2,5 - p1,5) x
(p2. - pI,))²
E [..]]
1 1+7 o²
(55)
spe + 6
(-1 - -3
7 N
6(1 + 7) 0²)
= 8p4 +
(0² + 30
N
which is polynomial in 14, with real coefficients. The other expressions are computed similarly, and they all have the form in Eq. 53 We now turn to the assumption that
3M20 VEEN Vigiga Ima| S M
(56)
and thus for each F== ( 5, x) and for all 1 S i s d, from the triangle inequality, it follows that:
s(t.f)
lf S Σ (cx(t,)) 1nd* S
(i, f)l M
max glis))
max (cn(i, fil M² JEF
(57)
max (CF
Σ
max |cs(1, f)l M
max Isidd
JEF
km0
where we define (i, 0 for all k ((i, f). Let denote
max qlis))
L = max ISid
Σ
max leu (i, f-- M².
(58)
JeF
Thus, from Eq. 57 we have:
VerVissiaa S.
(59)
Now, L is independent of (because took the maximum over all possible 1 S S d) and d (because the degree and the coefficients e will never depend directly on d, because doesn't 't depend on d). We thus showed that the absolute value of each relevant moment is upper bounded by a global it follows that:
value L 2 0 that is independent of i and d. Thus, from Eq.
52 Eq.
59
Pi S (ix: 45,7, + 65?n + 3n.
S (Ixal 4|8.1 Ima 6E?'n2 3n
S (L + 4 +6, +31,)
= (1L 4 + +4I2 + 1)²
Let us now denote C' (77 independent of both and d, and
+ 2 L) 2 where L 2 defined in Eq. 58 Thus, C 2 is
Vigiga Pi S.
When combining this result with Eq. 48 depend on i or d such that
get that there exists some C 2 0, D 0 that doesn't 't
Pi P.S D. D.
Thus.
- Ps
Σ C
C
Di
(60)
22
E D)
-i=1
20

---

Published as a conference paper at ICLR 2026
We have verified that the conditions of Theorem independent of such that for all x E R
are are satisfied, and thus, there exists some Co 0
Co Ci Pi
P
> x b 11 1211=11 2(x) S 7;)
S
Vd
[Ei= ?
CoC
where we used Eq.
60, and denoted A
2 0. Now, ((1, which is defined in Eq.
28
reads:
D
d
(1,2) =
Σ Vi > 0 11
i=1
P
Σ (1 11) >
Σ x=1
Th y =
d
Σ i=
W3 m/)) >
2 =
Σ 1= S2
2
i=1
Σ 1i=1
57
E 11
1
+ +
Vd
Σ 5
Σラ=1 ?n + 1-
2N
o
+ vd
Ad 0²
1+7 o²
o2
+ 4/² (1+ x(x)
N
+ 27
N2
2||u|| 2 + 2N
1-7.0
+
1
02. (
02
1+72
0²
d + 4 (1+ n. l1<a11))
N
27
No
|||||
+ IN
1-2
Tell
a²
+
(Va
1
1
1+7.
2t2²
d (1 + x
IN
7
Tiut
||,a||
+ AN
d
1-7
147
( ||al||
1 1422
( [1 )²) d + (1+ x/x)
1N
7
8N2
(61)
We now revisit Eq. 5
||
S
Thus, from Eq. 61 q(1, 2) reads:
VS
+ 4N
1-7
d
((1,2) Q
VS
0
(62)
1t7
1477
d
Vd
IN
7
8
8NI
5
21

---

Published as a conference paper at ICLR 2026
We now compute q2, 1). Similarly to the computation of q(1, have:
(2, 1) = P()()) l = 2)
P (m² - (a)) ) |120
A 11
(63)
P(w < =0/y 2
= P Σ V1 < 0 y =
where the random variables {er 1 are defined in Eq. 33 The new conditional distribution of 2; is:
Visiga T; y 2 N (u,
(64)
We first compute y) = -Elys]. is easy to verify from Eq. 37 by:
Eq.
38
Bq.
39
Eq.
64
that Y given
= 2/4
(65)
7
2N
We now compute < =
Var (y:). It still has three components, as in Eq. Eq. that Var(b;) remains unchanged because it doesn't 't depend on the conditional distribution of
41 It is easy to see from
x; Thus,
Var(b.) 1 1+ 20 N2
1+7
40
(66)
72
7
N
We observe from Eq. 42 Eq. that Var(a;) remains unchanged since it depends on B[a;] which is unaffected.
+
1 1+7 0 + H
+ γ
Var(a;)
N + 40²
(67)
7 N
remains compute Cov(a;, b.) E [labb.] E(a, [b:.) From Eq. 38 and Eq. 64
we have
Eja,] 2y4.. According Eq. 39 Eb, is unchanged, as it does not depend on the conditional
distribution of æ,. Similarly, from Eq. 45 E[a,b;] picks up a minus sign, so overall, Cov(a,, by)
changes sign. Therefore, Eq. 45 implies:
1-7
20 E
Cov(ai, bi)
(68)
7
N
Thus, from equations Eq.
41
Eq. 66
Eq.
67
Eq.
68
follows that:
1++ ?
0
1++ o²
1
+
+ 402
N
N
+ 2
204
14%
40² n
1-7
20²
4
22
N2
7
N
N
1 1+1
04
1
1+72
04
1 ++? ?
202
1 1-7 ?
202
+ 11
40
N
72
2N
?
N
7
N
(69)
++
0²
1+ 1+,
d²
1 147
1 - ? 1
4μ²
1+
7
N
2²2
N2
27
27
N
1 1+7
o² 1+22
0²
1+ |
4p
7 N
272
N2
(1+7
1+72
D.
2x²
N
Thus, 6 D where D 0 is the same constant defined in Eq. 48
A similar argument for the case
y shows that p; Ely 11 C. where C > 0 and D are constants independent of i
22

---

Published as a conference paper at ICLR 2026
and d. Since the variables {ur)2=1 are independent, we may apply Theorem existence of constant Co > O independent of d such that for all x E R:
9 which guarantees the
P
[y m1)) > > = -(x)
S
Co d 1
Pi
A
vd
E
1==1
Where we denoted A CoC
2 0. Now, ((2, 1), which is defined in Eq.
63 reads:
D
d
((2. 1) P
Σ U1 <0lv= 2
d
TP
Σ (y: 11) <-
Σ
Th y
Σ d x= 73
(ys- 11()
1/ 2
d 2i=1
62 i=1
Σ -i=1
1
d
Di=1 11
=1-1 P
(yi - -nt)= 2
1y=2
Σ1 1= 1=1
22
=1 5
Σ ΣS= 1/i
o
Vdl
Σ Σi= ?
0
+0 Vd
Σi= ?
Σd (2n +
1-9 0²
2N
101 11
1
Σ 0²
(
1+1
o²
N
+
1+a2
2x
No
4n² (1+ +))
2 |||a||1
2 + 2N
1-1 0²
+
1
02.
(
[+x o²
+
1+g2
27
No
o²
d + 4 (1+ x)) [1()))))
|| +
d
1-7
0²
4N
100 +
IN
1
14x
7
[|]| )
o
+ SNZ
1
[iul
.d (1 +)
||
+
4N
d
1-7
TP
1
+
Va
1+2
2
1t22
d +1+ #)
4N
RNT
(70)
where we used the identity 2(-x)) 1
2(x). We now revisit Eq.
5
||0||
s
23

---

Published as a conference paper at ICLR 2026
Thus, from Eq. 70 q(2, 1) reads:
d vs
+
1 1-7
((2,1)=
1N
v8
+
(T))
1+ 7
1472
va
To finish the proof, from Eq.
22
Eq.
62
Eq.
the probability of error reads:
1
P
9(1,
2)
-
(2.1)
2
2
VS
1-2
4N
V$
2
1+2
1-7²
d
4N
7
8N2
7
7N
VS
1-1
d
o
4N
VS
+
1+1
4N
8
8N2
V8 +
1
1-1
1
4N
2
1 1-7
+
d
4N
7
7N
-
1
1-1
d
Q
4N
VS
= (1))
1+;
14y2
IN
3
8N7
P(S.N, d)
vd
where P is given in Eq. 9
A.3 PROOF OF THEOREM 3
Proof. We provide algorithm to construct A kxd given and prove that it satisfies Eq.
|
Later, we will show how to estimate it from unlabeled data.
1. Define = a1 ||l||| If k 1, define A = u Else, continue.
2. Find a2 ag E Rd such that (a,, u. = O and (a,, a,) = 6ig.
3. Define the matrix A E exd where the i-th row is given by a,"
The proof that the algorithm works is given below.
Step 1: If A = 1, we define A 1
is easy to ensure that it satisfics Eq.
Step 2: If μ = 0, then the result is trivial because we can construct on orthonormal set
(az a& C Rd..
Otherwise, 4 # 0 and let us define the following subset of i2d.
V = {a ed (x. 14) = 0} c RRd.
We see that V - (span [ is linear subspace of Rd of dimension d - 1. Thus, there exists basis (u....., 12-14 C V. We know that k -- 1 S d-1 and thus {vi,.... 0--1 S V is linearly independent set. That is, can apply the Gram-Schmide procedure this set, to get an orthonormal set { (az...., ag} C V. This is a subset of V because Tram-Schmidt outputs vectors that linear combinations of the input, which lie in V.
24

---

Published as a conference paper at ICLR 2026
Step 3: The rows of A are orthonormal, AA Ig. From step 2, it follows easily that
Ap
A = ||l
Thus, A meets the needed requirements, and thus we have proved the existence of such matrix A. Assuming + O, it is now left to prove that one can learn A from infinite unlabeled data [z;};=> This data is taken from the distribution
1 a N (-H,oo'aa) + N (u, Ia)
(72)
where the label is called y E [1, Let us assume that there m unlabeled data. We first compute
1
Em
2, T
1=1
As - oc, have Em as E, where
= E [x
'1 = xx y = 1] Py = +)+ [x T ly 2] Pv = 2)
1 (o Io'Is + uspe
(o (o² + m1p11)
= o² la + uh
where we used Eq. 72 That is, we can learn the matrix
E o2 paps"
(73)
We now argue that the maximal eigenvalue of Σ Amax 0² ||al with eigen-space Vinax span (t). Indeed, from Eq. 73 it follows that:
Ep (0² + [1|el1))
and for all we have
Ev -Z..
Thus, the eigenvalues of Σ are
Amin < Amax = 0² + -11ea1??
The eigen-space of Amin satisfies:
V Aun (Span((u)) dim (V\mn. d
Thus, dim (Vamn) = which implies that
Vinaz (p
(74)
We now apply the power iteration method the matrix Σ... For large enough number of iterations and sufficiently large m > 1, it returns a vector that is arbitrarily close to the eigenvector of Σ that corresponds to the maximal eigenvalue Amux (ensured by the spectral gap of || > 0 between the two largest eigenvalues of E), which from Eq. 74, is characterized as ass where 전 0 is a constant. /
Normalizing this vector leads
Now, we apply the algorithm we presented above compute
||
A. As a side note, using the vector a = 4 T
as the first row of A has no effect on the resulting ||||||
properties of A.
25

---

Published as a conference paper at ICLR 2026
A.4 PROOF OF THEOREM 4
Proof. We know that
== Ax,
where A Biixd is deterministic matrix satisfying:
AA Ig.
|| |
is a standard result that a linear transformation a Gaussian vector is also a Gaussian vector, thus:
VEE112) z y = ~ N (Apj, Ao I
that is, for all j E {1,2} have:
z y ~ N 7 I'
where
Apr.
We know that μ4 - 141 μ4, and thus 772 7/1 1 Ap. That is, model assumptions still hold, with the following modifications:
d m k. μ n Ap..
The new separation quality factor S₂ of the new GMM (computed similarly to Eq.5) is given by:
172
m1
2
AAp
2
2
S₂
S.
20
That is, the separation quality factor remains the same after the processing. The result now immediate from Thcorem 2 and changing d d k.
A.5 PROOF OF THEOREM 5
Proof. Let y and take some
S> 0, 1 N.
From Theorems 4 it follows that we need to show the following:
p(S, N. 1, < pSS, N,
(75)
where ş is given in Eq.
It is easy to prove that:
VS
Ye (S,
25
+
1)
+
N7
Following Eq. 75
we need to show that:
Vs
VS
e
<
V
28
k
+1
48
N
2S
+
48
N2
which is immediate because the argument in the strictly higher the LHS, and the Q function strictly decreasing.
26

---

Published as a conference paper at ICLR 2026
A.6 PROOF OF THEOREM 6
Proof. Let us take some
72- 47 27 (1+7)
0 0<<<1,<<
we need to show that That is, it sufficient to show that the function
SS N, k) < PS
f(x) S N, 7,
is strictly increasing for all 2 1, where is defined in Eq.
It is easy to verify that:
VS
VS
1-7
4yNVS
x
4yNVS
I
f(x) = Q
+ +
I+y
14-² 8y
14y
1t72
TyNS
I 7N
15N8
87N'S
I
(76)
Let us define the following functions:
VS
1-7
4yNvS T
91 (1())
(77)
1ty
1412
4WN8
8PN
. 7N
and
VS 1-7
I
(2(x)
4NNWS
(78)
1+. 4yN8
+
87N228
1422
I N +1
Thus, Eq. re]dd::::
[x) - (()))
(79)
From the chain rule, the derivative reads:
('(x) Q' (gi(x) (x))
s (x) + D' (g2 (z)) (2(2a)
1 9ी pf(x) // (I) + exp - -
1
(b((z)
exp
V
(80)
(wi (x) gi (z) + w2(2) gx(x))
V2
used the following property of the @ function:
(- x2
Q(x) 27
cxp
dx
2
and the following notation:
wx(x) = exp (-1 9 (1((x)
(81)
Thus, showing that f is strictly increasing for all 2 is equivalent to proving that for all x 2
f((x) > 0 + wz(x) (x) + w2(x) gz(2) < 0.
(82)
We argue now that for all 1:
1.
wi()) < w2
(83)
2.
(x(x) <
(84)
27

---

Published as a conference paper at ICLR 2026
3.
+ + (2()) 5
(85)
Let us first prove Eq. 83 From Eq. 81 it follows that it is sufficient to prove:
Va21 (x)
[9((z)]-
(86)
Let us take some x 2 1. is easy to see from Eq. that 91 (z) 2 0 and thus [g) 91 (z). That
is, it is sufficient to prove that
(1 > 92(x)
(87)
and
(2(2) > (z) + 91 (z) + (2(2) 0.
(88)
Let us now define the following parameters:
B 1 1-7
VS
C 1+9
1+
4NNS
822
(89)
C1 N
I
C2 +l<c
We also define the following functions:
Di(x)
Cr + D2(x) = VCx + < (i
(90)
From Eq.
77
Eq.
78
Eq.
89
Eq.
90
it follows that:
(1(x) = Vs + Ba
D1(x)
(91)
92(x)= = VS Br
D2(x)
We first prove Eq.
87
Their difference Φ1 (x)) (2(x)) reads:
V Br
V8. Br (V3 + Bx) D2(x) (V3 Br) Di(x)
(x) - -2(x)
(x)
D2(x)
D1(x)- D2(x)
(92)
VS (D2(x) D1(x)) + Br (D2(x) + Dz(x)) D1(x)- -D(xx)
Now, from Eq. 89
Eq.
90
we have:
Dz(x) - Df(x)
D2(x) Di(x)
02 -1 D2(x) + (i
D2(x) + (x)x)
N N.
(93)
(x)x) + D2(x)
1
N Dz(x) + (x)
In order to show Eq.
87
it is sufficient to show that the expression in Eq. 92 strictly positive.
Substituting Eq.
93 get:
S
1-7
1-7
x. r-(2(x)) + D1(x)) >
N
7
D2(x) + (I(x))
N vs
N.
VS. (D.()) Di(())
Vs
r. (D2(z) + (1))) > D2(x) + (x)))
4VS
(Dz(() Di(x)) 4S
28

---

Published as a conference paper at ICLR 2026
That is, in order to show Eq. 83 is sufficient to show that:
h(x)) x (D2(x) + Di(x))² > 48.
(94)
We now show that h(x) is strictly increasing:
1' ((xx) (D2(z) Di + 2x ( Di)))) > 0.
Thus, it follows that:
121=((a) h(1).
(95)
Now, from Eq. 94
it follows that:
h(1) (D2(1) + (1)) > 48 + D2(1) + DI(1) > 2VS.
Indeed, from Eq. 89 Eq. 90 we have:
D2(1) + (1(1) > 2. D2(1) 2 VC +
1
= V
C+
+1
N
>
2 2VS
where we used the assumption that S < 1, and C > 0. That is, we proved Eq. 87
We will now prove
Eq. 88. From Eq. 91] the sum 91 (z) + 92(x) reads:
(V8 + Bx)
D2(x) + (V8-Bx) - Di(x)
(x) + 92(x)= = VS+ B.r VS Ba
(1
D2(r)
D1(x) (2(x)
(Dz(t) + Dı(z)) + Br (D2(x) -D(x))
D1(x) -2(x))
(96)
In order show Eq. 88
it is sufficient to show that the expression in Eq. 96 is strictly positive.
Substituting Eq. 93 we get:
1-7
1 1-7
v8. (Dz(z) + Di(+))+
>
4ry N VS N
D2(x) + (1())
By (D2(m) (i))))
(1 71-
Vs. (D2(x) + Di
4S2 D2(x) D1(x)
(D2(x) + (z)))
(1-7)²
4N2NS
That is, in order to show Eq. 88 is sufficient to show that:
p(x) (D2(x) (x))²
(1 - 7)2
(97)
x
422
Indeed,
2o) + Df(x)
D3(x)) + D7(x)
p(x)=
2
I
Cr + c + Cx + 02
T 9 +2
20 +
20
(98)
1+7
1 1+
2yNS
4y2N28
1+7²
422N2
(1 (1-7)²
N25
29

---

Published as a conference paper at ICLR 2026
where used C1, 02 0 and (1 7) < 1 for all y 0.
That is, proved Eq. 88 and
thus we showed that Eq. 83 is satisfied. We will now prove Eq. 84 parametric function
Let us first define the following
TB,C,D(a)= VS+ Br (Cx+D
(99)
Its derivative reads:
C B. /Cx+ + 2v/CatD
(VB Be
T.c,,(())=
Cr + D
2B (Cx + D) C (VS + Bx)
(100)
2.(Cr D)1.5
BC I x 2- BD - VSC
2. (Cr + D)1.3
Now, from Eq. 78 Eq.
99 it follows that:
92(x) TTB,C,,2(x))
That is, from Eq.
100 have:
g2(x) BC x - -B 02 C xC. 02 + VS.
<0
(101)
2. (Cr +02)
2. 2. (2)
where we used B, C, C2
which follows from Eq. 89 and S 0. Finally, will prove Eq.
85
From Eq. 77 Eq. 99 Eq. 100 it follows that:
TB,Co, (x) (x) BC 2B .
gi (a)
(102)
2. OCr +c))
Thus, from Eq. 101 Eq. 102 proving that (x( gb(x) $ 0 is equivalent to proving that:
BC x + 2B c1 - V BC x + 2B 02 + C
2 (Cr + + 1.5
2 (Cr 12)
From Eq. 89 and the assumption of 0 < < 1, we know that e₁ C2. Thus, if the numerator in the LHS is negative, then the inequality holds trivially. Otherwise, is sufficient to prove that:
2B. VS. C 2B c2 .
2B (a - (2) $288.
B
- SV5.c
1
N.N N
Thus, we need to prove that:
1 -
VS.C
<
(103)
N
B
From Eq. 89 the RHS in Eq.
103 reads:
14y
147²
1++ 1++2
cS.C C
4...N../S
8.
8.
B
T-y
4.y.N.v
1+
1+g2
+
4
8 8.7-N
N
1 1-7
1 1+7
1 1+22
1-7
7. 7)
2.N
2N + +1
2N 7(1 17))
(2N +1) ,2 + 2N +1
2N 7 -7)
30

---

Published as a conference paper at ICLR 2026
Thus, Eq. 103 reads:
1 1-7 (2N + +1 + -7+1
7. N I
2N 11
2. (1 - -))² S (2N+1)) 72 +NN .7+1
+
2 (y 24
(2N -
2 2.7. (1
- N 2y(1 +7)
Which holds from the theorem assumptions. Finally, let us take some 2 1. We need to prove that:
wi (z) (x) + (2) (x(x) < + wi(x)) (x) w2) (x)
W2(x)
+ (
wi (2) (2(x).
Indeed, from Eq. 83 Eq.
101 Eq. 85
it follows that:
W2
wy (z)
(((x) < 2/ (x)
(-12(x)) wn (x)
2 (2).
w1 (x)
2 4+++1
Which finishes the proof. Note that for y 2 0.162, the requirement
vacuous (since
2x(1+7)
N 2 1), so it only matters under severe imbalance (7 0.162).
A.7 PROOF OF THEOREM 7
In order to have fair comparison between cases with different values of y, fix the total number of samples to be Ny. Thus, we take N1 = INr samples from the first class and N₂ = y xNrr from the second class such that:
1
N2 xNT + NNT NT
1+7
Meaning, the number of samples in the first class is
Nr
N
(104)
1 1+7
Proof. Let us take some Ny E N and
S S>0,15 <,0
Let us define the following parametric function:
VS+s + s. (1-7)-9
VS +
(x).((z) =
47.55 .
(105)
(1-7)-g 44.
1 (1+33)-9
C
D
à
x
8
2
where the parameters B, D,D are:
== (1 - -) q
47 VS
C (1 + 9
(106)
4 S
(1+
D 8
31

---

Published as a conference paper at ICLR 2026
From Definition 13 and Eq.
9 it follows that:
Ps (error))
100 (1- M(S, N; 7,
7 100
Po (error)
N.
2 (JI,m&&()) [(-1,A(N))
(107)
100
2 (f + +((f-1a((N))
100 h(N)
where we defined the following function:
h(x) = 1 2 ( (x)) + (V-1,1A())
(108)
Q (fi + (f-1,,((()
Now, let define the following parametric function:
VS+B.r
Is.a.g (x) = Ss,a.e
(109)
V2
where we used Eq.
105
Eq.
T06
Let also define:
2 +
(xx)
h
=
( (z) 2 (9-11d(())
(110)
where we used Eq.
109
Eq.
108
Thus, Taylor expansion to first order of yields:
{(x) {()) + (0) + 0 (x*)
Where the approximation is exact for x << 1. Thus, the following exact for
x 1= h(x) = = {(0) + (0)
(111)
x
Assuming:
NT + Ny 1+?
N 1+7
(112)
means that following first-order approximation is exact:
(0)
h (N) (()) N
O
(113)
N2
Let us first compute E(0):
Q (01.7,A (0) Q (g-1,1,x
2 Q(VS)
((0)
2 Q(VS) 00
(114)
2 ( 2 (g-1,1,((0))
Finally, we will compute (0):: We first compute Laan (0). From Eq.
109 follows that:
B B. 22 C. +1
2D.4+C
VS++Baa
2-
(x))
C.2
2B. (D. +2 + (2D C). (V8+B.x)
2 22 13
(BC-28D) x x2 CVS)
2. 1.5
Thus, the derivative is:
2B - CV3
g2 (0)
B CVS
2
s. s-11-)) .).g
1
(1+1)
1
vs
+ à
4
2
4 -
(1(1-))
(1+ Vs
(115)
4
8%. V8
2a
2s (1 7) q (1+7).1 Vs
8 S
2u
((s 1) (2s + 1) 7) -9
VS
8 vs
2a
32

---

Published as a conference paper at ICLR 2026
Now, from Eq. 110 the derivative E' (x(x reads
d Q +
(x)
dr 2 (g).))())) + 2 (((
d [u(z))
dr
v(x))
(116)
u'(x)) v(x) v' (z) u(x)
22 2
(x)) u(x)) u (z) v(r)
(x)
where we defined the following auxiliary functions:
[(()) Q ( + Q (0-1,,,(z)) u((x) 2 (0)x)(())) + (9-1,1,0(4))
(117)
From the chain rule, their derivatives are:
Ju' (x( ( @' (01,)(())) + g' (1) Q' (g-1,1,(2))
(118)
('(x) (1) Q' (I)) --) ②' (g-1.1d(z))
Now, from Eq. 116 Eq.
118
follows that:
((0) o'(0) (((0))((0) (0) (10) v(0)
(119)
It is easy to verify from Eq. 109 that Is.a,q (0) vS. Thus, from Eq. the following formulas:
117 Eq.
118
Eq.
115
we have
((0) = 2 2(VS)
v(0) 2. Q(VS)
(1 11-30 13y) k
VS
-3 (3+7))1 .k
VS
(0)
C'(VS)+
e'(Vs)
(120)
87 VS
27
87 VS
2
(1-33)-44 -d
VS
(3+ x)+
VS
0'(0) =
2((V5) +
2((V5)
8y VS
27
8y SS
2
Now, we substitute Eq. 120 in Eq.
119
to get the following formula for Ł(()):
((()) 2. 2(VS) ((
(1-3))
v
@((V)) + (-(3t))d v3
Q'
V3
4- 4-(2(VS)
2Q(V5) ((
(1-37))
VS
2((VS) +
(3+1)) vS)
87.55 2 2'(VS)
87.v/3 24
4. (VV)VV))
2((V3)
(1 (1-33)) 37) (d k)
(3 ++7) (d - k)
Q(V5)
87 VS
87 VS
(121)
C((S))
-2 2 4y
(d- k)
2. Q(((
8y VS
2'(VS)
1 27
(d (d- k)
Q(S)
8y VS.
2'(VS)
1
(d k)
8y 1
VS. Q(V8)
33

---

Published as a conference paper at ICLR 2026
Finally, from Eq.
107 Eq.
112
Eq.
113
Eq.
114
Eq.
121
it follows that:
"
100
h(N)
(0))
100
[(())
O
N
N2
(())
(122)
100
+0
N
N2
100
(V5)
1
(d - k)
+
+
O
VS. @(Vs)
8y
4
N
N2
We proceed with Eq.
122 and substitute Eq. 12
= Nr
1+7
to get the following approximation for yy:
@'(VS)
1
1
1
1 100
(d - k)
+
(11 7)
+
2(VS)
8y
4
NT
N2
(((S)
(
1
1
1
1
-50
(d- k).
+
(1+7)
+
+
VS. Q(v5)
2
NT
N
2((5))
(1+1) (1+>²) (1
1
50
(d--) -k)
+
O
V8. Q(vS)
44
NT
N
(123)
50 ((()))
(1+ 1
(d- k) - (1+ (1+27).
+0
4 4.V80(V3)
NT
N7
25. (VVV))
(d- h)
(3+27 + 7) Nr
+
2 VSQ(SVS
N
exp (-g)
3 + 27 + 1) (d- k)
+
2V2T
VS. Q vS)
NT
N7
where we used the following property of the Q function:
2
('(x) 22T
exp
2
It is now left to show the conclusions. For NT >> 1, we have from Eq.
123
that
" 7= C= 9(7) (d k)
(124)
NT
25
where C'
> 0, and
2T
exp (-
f(S) VS ((vS)
(125)
9(7) = 33 + 7
It is now clear from Eq. 124 that d - lo increases, the efficiency increases (linearly), and Ny increases, the efficiency decreases. It is easy to see that in (0, 1], the function defined in Eq. 125
achieves a minimum at 7 2
1 =
1
g(()) =
72
7
1
V2"
is easy to check that
1
g
< lim g(x) = 00,
< (())
/2
122
34

---

Published as a conference paper at ICLR 2026
Thus, from Eq. 124 in the range 0.
1 as y decreases, the efficiency increases. Finally, we will v2
prove that the function f. defined in Eq. 125 decreases as S increases, and thus from Eq. 124 the efficiency decreases as increases: It is now sufficient to prove the following:
((()) - 2 exp (- 2 VSQ VS
d
(VSQ (VS)
exp (- 72
as
SQ² VS)
V8 0 e(55)
d
(V8Q (5)) <0
ds
2 180 V8)
0 (5
+ VS o (v5)
1
2/8
2VS
-VSQ (V8)
2 (Vs)
1
S
exp
V8
2T
(V++
VS
1
Q
V$
1
2m
exp
S
2
2 e(v5)
1
V8
S
cxp
2t
S
S+1
2
82
Where we used the identity ('(8)
exp
Let us now prove the final inequality.
V2T
equivalent to the following inequality
x [SV:
x²a
exp
Φ(x)
(126)
V 2m
x
2
2
where we defined the following function:
1.2
((x) =
exp
(127)
2T
2
Indeed, for all x 2 O:
(1 1
x
1
2(xx) =
1
+ x22
Φ(u) du
x2
1
1 + u2
((u) du
(128)
(xx)
x
where we used the following identity:
du (- Φ(())
d'(u) u ((u) 6(u) u² (lu))
= -(1+1)
p(u).
(129)
22
u²
42
And Eq. 129 follows from the identity o' (u) - Φ(u) which is straightforward from the definition
of 6 in Eq. 127 Now, from Eq. 128 it follows that:
((x)
((x)
o(x)
x2 x2 +1
which proves exactly Eq. 126
It is left to show that:
NNNN (erroo)) < Pee (error).
(130)
That is, 17 > 0. We proved in Eq. 119 that:
Q((V5) (d (d-b) (2) 1 1 0.
(0)))
8y 4
(131)
VS.21 Q(VS)
35

---

Published as a conference paper at ICLR 2026
We defined ((r) in Eq. 111 as:
1
((x) =
h'
(132)
x²
where we used the chain rule. Finally, from Eq.
131
Eq.
132
follows that:
1
(0)) lim
W
lim t (t)
z 2-0
2
where we used the fact that if the two-sided limit exists, then each one-sided limit exists and they equal to the limit. In total,
lim (t)) 0.
This means that for large enough t, we have
(1()) <0
which implies that h is strictly decreasing, Thus, from Eq.
107 we have that for N > 1, is
decreasing. In addition, from Eq. 111 Eq. 114. it follows that:
lim 7 100 lim h(N) 100 000
lim N-
100 E(0)
0
700
N
Finally, 7) decreasing for large enough and approaches 0. It is now easy see that:
NNoENNNNN 7/
which exactly proves Eq. 130
A.8 PROOF OF THBOREM
Let state extended and more detailed version of the Theorem g
S Theorem (Analysis of the maximal efficiency). Fix ry = 1, and let 0,1 < Consider the efficiency 17 ()N function of continuous N E R., The following hold.
The maximal efficiency Tmaa
(N) increases a.function of S 0.
N20
For fixed r = and k >> max(1,S), the maximizer Nmax = arg max (NN) decreases N20
To
with S > 0 in both regimes S < 1,S > In addition, in the regime S < the following approximation holds:
r r (++-1)
k
N max
R3
(133)
28
r -
Finally, the regime S 1, the following upproximation holds:
k 2S
N Maxx
VF.
(134)
Proof. Fix 7 1, and take
8> 8>0,1 <d.
36

---

Published as a conference paper at ICLR 2026
Let us now define the following parametric function:
VS
fx(2,8)= =
V(28 28
VS
9+2S
25
4S.
VS
2x(g+28) 1821 48
(135)
2ST
24r + q + +48 4Sx²
2Srr
V(2x + 1)g + +
28x
(I)
where we denoted
Dy(x,S) (2x + 1)4 + 4x(1 + 1)8
(136)
488x + 2 228 + 9) x
From Definition
13 and Eq.
it follows that:
P= (error)
100 N,,,N,,,K)
7 = 100
Pex (error)
N,,,N,1,))
2 Q (fa(NN)
100
2 (
(137)
(ff(NN)
100
((a((N))
100 h(N,8)
where we defined the following function:
Mz, =) ((a(x,
(138)
(f((x,
Hence, our task reduces to proving that the following function is increasing:
V(S) max (), (x"))))))))))))))))
(139)
250
where we denoted
x (S) = arg max h(x, S).
(140)
2>0
We note that the proof holds for each stationary point, and in particular for maximizer that achieves the maximum value of the function h(x, S). addition, using the first-order condition:
Oh dr
(x (8), =0
(141)
We now aim to prove that V'(S) > 0, where V(S) is defined in Eq. 139 From the chain rule, we have:
0h (x (S), S) +
dh
Or Oh
V'(S) = as
(x (S),))
as as (S))
(142)
dr
37

---

Published as a conference paper at ICLR 2026
where we used Eq. 141
Let compute the partial derivative of h with respect to S:
0h á (Q((((,)))
as
as @(f((z,)))
as (f((2,))))) - @ - Q((((,,) Q((((,())))
@ (fa(z,
Q(f(r,,) Q (fa(z, S)) 88 Q (2, S)) ((fa(x,
(fa(z,5))
L' (Jalz, S))
((1((, - Q' (fr(z,
21 @ffa(z,))
05
@a (fa(z,
1
exp (-21(cr88)
8f. as
(Fa((z,)) exp (- (1, as
8f.
(fx(r,)))
2mm
Q2 (fa(r,
(143)
where we used the identity ('xx) =
exp (-2"²
x It now follows immediately from
22T
Eq. 142
Eq. 143
that proving V'(S) > is equivalent to proving the following inequality:
exp 1-
,3)
0fk as
(x (Ja((" > exp (- .s)
Ofa as (x (0,
(144)
We now turn to the first order condition for x (S) in Eq. 141 and thus equate the partial derivative of with respect to x to zero. Similarly to Eq. 143 one can prove that for all x we have:
Oh
(f((z))
dr
dr
2 (Ja(z))
1 exp (x,
0h. ((f((z,)) - exp (-2 S)) or
0/
((f((z,)))
or
22
@ (fa(zz S))
(145)
0h dr
That is, equating
0 yields the following equation for x (S):
exp (-2ri(orss))
0fk
(x" (f)((" (S) = exp dr
f-tt" 5))
Ofa
(x
()) S)).
Ox
(146)
We now divide both sides of the inequality in Eq. 144 by the (positive) value we have in the latter equality, in order get the following simplified inequality:
0fs (x"SS) S) 88
8fa (a" S)
as
(147)
0/
(I",S) 8x
0l. Oz
(x* S)
38

---

Published as a conference paper at ICLR 2026
afg dx
We indeed divided by positive amount, because exp(-) > 0, 2(-) 0, and from Eq.
for all x
135
Eq.
136
we have:
O5,
0
2Sx
dx
dx
V (T,
θ
=2S.
dx
(Dy(
VDy(a,S) x 8u
(Vyg 8)
=2S.
Dg(2,S)
VDy(z, x (D.(2.5)/08
2VD((x,S)
= -2..
Dg(I,
(148)
2 (I, 8) 8D,(2.5)
2S.
(D,( S)) 3/2
S
(2 (4S.x 228 + +))
②) (8Sx + (28 4)))
(Dy (z. (0xz))) 8))
(28 + 1) +)+++2))
(D, (x, S)) 3/2 S))3//
25
(22 q) x + +4)====
(D2 (1) 3/2
where we used the definition of D2 S) Eq. with respect to S:
136
We now compute the partial derivative of fg
05 Ø
2Sx
as
as
(D,(x,
2r as
SDg(E,S)
(D(x, 5) - -
8
(v)
03
2r
Dy(2, S)
(149)
VD S (D.
2 (x,
2r.
Dy(
2 D2 - (z.5)
2r
us
2 (D, (z, 5))3/2
3/2
We now use the definition of (x, S) from Eq. 136 and get
0fg as
(2 (4Sx² 2 + + 9) - S 4x(x + 1))
(1, S)) 3/2
I
(4Sx² + 4 + 9)x 4Sx - 24)
3/2 (D,(a, (T(xsS)) S))3/2
(150)
(4S.² + 4( + x) +2)
(D₂(1, S))
2x (Dg(2, S))3/2
(2Sx²² 2S + 9) +
39

---

Published as a conference paper at ICLR 2026
Let us now define
0.g (x, S)
(x,
BS
01g (z, S)
2r
(28x² + + 9) 9)
(D, (a.58))
28
((2S + ()
(151)
288x² + 2Sx 2x 9
2Sx + x 4
(2Sx (r 1) + (2x 1) 9
2Sx + (æ + 1
where we used the partial derivatives of fq. computed in Eq. 148 Eq. 150 We remember that we need to prove Eq. [47 which is equivalent to (r, S) being decreasing function in the argument (this is because
d). Indeed, let us compute
(x,
0 22x((x + 1) (2r + 1) 1)-9
dq
S
dq 2Sr + (a +0++ 1).1)) -9
x
(2x + 1) (2Sx + (x 1). 9)
(x + 1) (2Sx(x + 1) + (2x + -1).))
s
(2Sx + (x + 1) 4)²
2x(2x 1) S 2x(x 1)
(152)
(2Sx (xr + 1) q)²
2x (2x 1 - (z + 1)?
(2Sx + (x 1) 9)) 2
2x
(28x + (x + 1) g))
That is,
0Rg (x, 0q
2x
(2Sx (x 1) 9)² <0 0
which proves Eq. 147 We argued that this is equivalent Eq. 144 As proved in Eq. 142
this inequality is equivalent to proving V'( > 0. Finally, the result is straightforward because n 100 A(N,S) S). This proves the first part of the theorem.
We will now prove the second part of the theorem. Let us fix
> max(1, and
1. We prove that the maximizer x² (S), defined in Eq. 140 decreases as a function of S.
h
Let us first define the following rescaled x value:
xx1) =
S t.
(153)
Thus,
k: S
x² xS) =
arg max h (x(1),)). 150
(154)
40

---

Published as a conference paper at ICLR 2026
From Eq 135 it follows that:
28 x(t)
fo (x(1),
(2x((() 1) + 4z(()(=((++115
25. x(t)
2x(1)) y (1) S
28
2g x(0)
4S
28
V24 E7
S
48
(155)
V2V8. Vkt
V2q + 4kl.
2Sk
+ 2k
2St
+ 2/
where we assumed r=(t) > which follows from > 1, < g, O(1). We explain the
assumption O(1) in moment. Now, from Eq. 138 we have:
Q ((v 28t
h (x(1, =1 (Sa (c((()))))
(156)
(fa(()))
(v
25t r+
this motivates the assumption O(1) we used in Eq. 155 the maximizer
o V
28t
I+21
t" (r. arg max h (=(t), arg min t>0
t>0
Q
(vV
28t
(157)
r+21
arg min (t)
t>0
function of O(1) which is constant and S < k and thus in the region of interest (close to the maximizer), t = (1) does not scale with k. The key insight here is that t" (r, S) doesn't 't depend on k, d. We also defined the following function:
Q V
25r 1+2r
(t. =
(158)
Q
28t r+226
Finally, would like to analyze the dependency of (r, S) on S. We will prove that in both regimes < S > I, we have that t" Sr, does not depend on S, and thus in both regimes, from Eq. 154
Eq. 157 the maximizer
k S
x'
t" (r)
(159)
41

---

Published as a conference paper at ICLR 2026
is decreasing as function of S > 0. For the regime S < 1: We the approximation Q(x)
1
x for x < 1 and Eq. 158 to get
22
2
25t
28t
V
1+21
1+21
(t)r
Q
2St.
2St
r+
2
Vm
28
V
2m
1+21
281
V
742
2SI
2St
1+
V2T
1 2f
V 2
r + 2t
(160)
25t
2St
+
V2T
+ 21
V2T
+ 21
2
25t
2St
1 + 2
+ 2t
2
1 2/
+ 2/
This approximation is motivated from the fact that the argument of the Q function in both the numerator and the denominator is at most VS < 1. Thus, from Eq. 157
we have:
(VI+ 2t
t" (r, = arg min
(161)
V r 2t
(>0
is independent of S. We will also calculate the minimizer. Let us define
(t) V 1 2t
V r 2t
(162)
We now equate the derivative of 1 (t) to 0:
dv d
t
dt
di
V
1 2t
dt r 26
1
r
2
Vt. (1 ++))
Vi. (r + 2t)
(163)
1
1
2/F
(1 (1 + 21)
(r 20)
1
(r 2r)
- 2t)
2/t
(1 21)
(r 21)*
42

---

Published as a conference paper at ICLR 2026
where we used the following formula:
d
8
d
d8
a+
dt
a a 2t
2
[a+22)
2
a+
a
v a + 2t
(a + 21)²
2 Vl
a
2
Vt (a + 21)
Finally, from Eq. 163
we have:
(r 2t)) (1 + 2
r r+ 2 ق (1 + 2t")
21 (1 (1-r3) = 3 (1 1
r (1-ri) r3
2 1 rå
That is, the maximizer is unique, and from Eq.
159 in the regime S << 1 we have:
rd rd -1 1 1
=8))
(164)
2
r 1
S
which is strictly decreasing as function of
x
For the regime S >>> We use the approximation ((x)
exp
and Eq.
158 get
2
28t
1+2t
25t.
V
I+21
2St
exp
2
1+22
(t.
(V
r+
2St
V2T
r+
2St
exp
2
r+21
25t
St
1 + 2t
exp
I+28
(165)
+
St
exp
r+
1 + 2t
exp
-St
+
1 2t
r 2t
minimizing (t) is equivalent to minimizing In (ts):
(t) = In (gs,, = 2
(1 + 2t) (r + 21)
St.
(166)
1 2t
r 2t
43

---

Published as a conference paper at ICLR 2026
Let us equate the derivative of Ms (t) to 0:
d
t
d
t
S
0
1 + 21
r 21
1 21
+
1
8.
0
1+ 2t
r 2t
(1 + 21)²
(r+ 26)2
1
1
S
Sr
1 2t
+ 2t
(1 26)²
(r +r+ 2t)2
(1+ (r) (1+
- Sr(1 + 21)² = 2
(1 (1+22) (t) (r- = 10-)- (-- Sr (1+ 4t -t²)
(12+4rt+ - Sr (1 +1 +
4(r
(4S 4Sr) / + Sy Sr
4(r 1)-1)) + - -1) 4S - r) + Sr -)
4f + + + r 4St Sr
4 (1 + 8)(² + 1) ()) =0
Finally, we take the positive root (because E S) > 0) and get:
(r, 2( 1) + 4(r 1)2 16r(1 S) - 8)
8(1 +
(167)
(r+ + (r + 1)2 + 4r -S²-1) 1] 4(S 1)
we note that we got single solution and that the maximizer is unique, and S > and thus the formula well-defined. We note that
lim (r) = /r S
2
and thus, from Eq. 159 in the S > regime, we have
k (r (r 1)2 4r (82 - 1)
x² (S)
(168)
4 1)
rr S and thus in the S > regime we have x ==(S)
and as S > do we have (S) ~ decreasing function of S.
is
S
44

---

Published as a conference paper at ICLR 2026
B ADDITIONAL THEORETICAL RESULTS
We have established an approximation of the efficiency of the processing 1) for N >> 1. We now do the same for the difference
A = Pw (error) - م= (error).
This allows us to gain insight into the different factors that affect the difference A between the probability of error that caused by the processing.
Theorem 10 (Analysis of the asymptotic difference). Let S > 1 k< <d, 0 7 S 1. Denote by NT = ()+)) N the total number of training samples. With approximation accuracy O(1/2)) we have
1
exp (- e
(3+22) 2) (d (d-k)-
A
k).
(169)
4
2m
VS
NT
In particular, for NT > 1: The difference increases when d - k increases decreases within 0 S 1/v2: The difference decreases when S increases N1 increases.
Proof. Let take some Nr E N and
8 s>0,<<<<00<
Nr
We have NT = N + + (1 (1++)) N the total number of training samples, and thus N
1+7
Let us define the following parametric function:
VS + 8. (1-7)- 17.55
V8 +
(x,ag(D))= =
(170)
U+>2kg 47.5
1 x
1 + (1
V
C
+1
34.
where the parameters B, C, are:
B = (1 7) q
4y VS
C = (1 + 7)
(171)
47 S
(1 22)
872 S
From the Definition A = Pa (error) - (error) and Eq. 9 it follows that:
A (error) (error) = Ú(S -(S,
=Q + -U QU-L)) h(N)
(172)
where we defined the following function:
(xx) [2 (x)) + -(L-naab))--((Uxxxd)))+++++++
(173)
Now, let define the following parametric function:
9 (x) fe,a. (
VS+B.r
(174)
VD.
where we used Eq. 170
Eq. Let us also define:
((x) =
[Q (z))
(2 (I)) Qgg
(175)
where we used Eq.
Eq.
Thus, the first-order Taylor expansion
((x) E(0) (0) 0 (x²)
45

---

Published as a conference paper at ICLR 2026
Where the approximation is exact for < 1. Thus, the following is exact for > 1:
>> 1= h(x) = = {()) + (0) + +
1
(176)
x²
We have
NT
N
1 + Nr 11+
(177)
1+7
Thus,
I(N) = (()) (0)
0
(178)
N
N2
Let us first compute E(0):
(0) = 1 (I)) + 2 ((0-L1 (91. 2 (g- = 2-2 -
=
(179)
Finally, we will compute (0):: We first compute d' (0). From Eq. 174 follows that:
B B.VD. x2 C. 2
2D.r+C
VS++B B-
()))q()==
+
2B. (D (D.x² + -
(VS+B..)
2 CD 1.5
LBC-2S10 x (2B
x CVS)
2. C +++1)))) 1.5
Thus, the derivative at
2B CVS
ga (0) =
= B CV5
2
2
s. s. 61-1-1 (1-11) 7)
(1+ q
+ VS
4
2
4
8 (1-7) .9 (1+7) Vs
(180)
4
87 85. 2a
2s (1 - 7) 1 (1+7)
vs
8
2a
((2s 1) - (2s + 1) ())
VS
8y VS
Now, from Eq. 175 the derivative (x(x reads
d
('(x) dx (v(xx) u(x))
(181)
v'(x)) u' (x)
where we defined the following auxiliary functions:
(u(x)) 2 (x)) + (1)1,))(z)))
(182)
u(x)) Q (0)))(())) + Q (g-1,1,(4z)
From the chain rule, their derivatives are:
n (x) (1) Q' (x)) --1,1,1())) Q' (g-1,1x(x))
(183)
v'(x) = (x) & (g)))((z)) + g g-))) Q' (g-111e(x))
Now, from Eq. [8] Eq. 183
follows that:
E' (()) 0'(0) n/ (0)
(184)
46

---

Published as a conference paper at ICLR 2026
It is easy to verify from Eq. 174 that (s, VS. Thus, from Eq. have the following formulas:
182 Eq.
183 and Eq.
180
(1 - 37) k
Vs
(3 + 7) k
vs
(0)
C((V))
@'(V))
8y vs
27
8y VS
2
(185)
(1 (1-37) 37) d
vS
73+
VS
(0)
((V)))
2 2'(55)
8y v8
27
8y. VS
Now, we substitute Eq. 185 in Eq.
184 to get the following formula for (()::
(0) = 8
3
o
(V5) (d - k)
3+7 o (v5) (d k)
87v8
-2 47 o (V8) (d (d-k) k)
84/8
-2 + 27)
{ (d - k)
cxp (
(186)
84/8
2T
exp
(-
S
2)
1 17
(d - k)
4v
VS
exp
(-
2 2 1
(d - k)
4
VS
where we used the following property of the Q function:
2
exp
2T
Finally, from Eq.
172
Eq.
177
Eq.
178
Eq.
179
Eq.
186
it follows that:
h(N)
(0)
1
((0)
O
N
N2
(())
(187)
O
N
N2
exp
(-
S
1
1
1
2
(d - k)
+
2m
VS
N
N2
We proceed with Eq.
187 and substitute Eq.
177
N Nr
1+7
which leads to the following approximation of A:
1
cxp
(-9)
1+7
1
A
2 + 7
(d (d-k).
+0
4/2m
VS
Nr
NZ
(188)
1
exp
(- 3 + 2n +
1 7/ (d - k)
1
+
2m
VS
NT
We now analyze the dependence of Nr, d k. on A for Ny > 1. The results will be identical
to those derived in 7 From Eq. 188 the following hold for Ny >> 1:
A decreases with Ny.
A increases with d - k.
A increases when r decreases within
0, /2
this is because the function
1 7
f()) = 2
47

---

Published as a conference paper at ICLR 2026
1
has minimum at r within (0, 1).
v2
A decreases with S: this is because
9(S) = exp (-g
VS
decreases with S: indeed,
g'(S) - exp (-²) VS
exp (-g)
2/5
S
exp (-2)
(v5 +
1
<.
28
vS
C ADDITIONAL EMPIRICAL DETAILS AND RESULTS (CIFAR-10, DENOISING)
C.I EXPERIMENTS COMPUTE RESOURCES
We conducted our experiments using a few NVIDIA RTX 6000 Ada Generation GPUs with 48GB memory. The training time for each data point in Figures 2 and ranged from one hour to twelve hours, depending on the number of training samples.
C.2 TRAINING THE CLASSIFIER
We consider the CIFAR-10 dataset (Krizhevsky et al. 2009) and the ResNet18 model (He al., 2016). To train the model, we use: batch size 128 and 350 epochs; cross-entropy loss; SGD optimizer; learning rate: 0.0679; learning rate decay: 0.1 epochs 1 116 and 233; momentum: 0.9; weight decay: 0.0005. This setting yields 90% accuracy for clean data.
Per noise level f0.25, 0.4} of the additive Gaussian noise that has been added to the data, this setting to train two classifiers: one that operates directly on the noisy data and one that operates on the denoised data.
C.3 TRAINING THE DENOISER
For the denoiser, we use the DrCNN model (Zhang et al. 2017) and 15,000 training images while ignoring their labels. Per image, the clean version, Xgt. is the target and its noisy version, x, is the input to the model. To train the model, we use: batch size 64 and 1000 epochs; MSE loss; Adam optimizer; learning rate: 0.0001; learning rate decay: 0.5 iterations 20k, 40k, 60k, 80k, 100k, and 200k. The results with the MSE-based denoiser with < I are presented in Figure 6 Note that, in order for the division of samples among the first five classes to be valid, we require Nurain
1+7 < 17500 + Nuran - 17500 (1 + 7). This shows that the point Nuain 35000 is invalid for all 7 < 1. Thus, add sufficient amount of samples from the synthetic CIFAR-5m the classifier train set, both in the noisy and denoised case (where the noisy CIFAR-5m passes through the denoiser).
C.4 TRAINING THE DENOISER WITHOUT CLEAN IMAGES
Replacing the MSE loss with Stein's 's Unbiased Risk Estimate (SURE) (Stein) 1981 Soltanayev Chun 2018) allows to train the denoiser using only noisy images. Specifically, instead of MSE Z x), xx1) || xgell² 2 we use:
9 dz,
(X) = [(zo(x) - x12- 2 do + 20
2o(x),
48

---

Published as a conference paper at ICLR 2026
which obeys B[SURE(Zz(
E|MSE Xgt] for x|Xgt (xxx, I We use the common practice of approximating the divergence with g (zo(x (g) (x)x))/ where is small and g ~ (N, 1) is drawn per optimizer iteration. Additionally, we use: batch size 64 and 1000 epochs; Adam optimizer, learning rate: 0.0001; learning rate decay: 0.5 at iterations 20k, 40k, 60k, 80k, 100k, and 200k.
The results for the setup with the SURE-based denoiser are presented in Figure can be seen that they resemble the results for the MSE-based denoiser, which are presented in Section
C.5 NUMERICAL ACCURACY RESULTS
In the following Tables and
we report accuracy results related to Figure
N train
Error without denoising ( (%)
Error with denoising (%)
1000
71.12 +1.39
63.32 +0.96
2000
64.91 +1.44
58.14 #1.41
3000
63.19 +1.21
54.62 #0.37
5000
60.43 #1.42
49.79 #1.80
10000
46.15 +0.81
42.43 =0.25
15000
42.14 =0.8
39.74 #0.40
25000
38.48 +0.29
36.02 00.38
35000
35.77 +0.30
33.83 +0.25
Table 1: Classification enror rates (%) noisy and denoised CIFAR-10 images for varying training
set sizes Ntrain The noise level is a 0.25, 7 = 1, and the denoiser is trained with MSE loss.
Nirain
Error without denoising (%)
Error with denoising (%)
1000
74,45 + 0.81
64.82 + 1.14
2000
71.01 2.00
61.25 = 0.90
3000
67.86 + 1,46
58.30 =:00=000 0.66
5000
64.98 = 1.21
56.24 2.03
10000
54.70 + 1.14
49.64 = 0.50
15000
50.30 = 0.47
47.34 0.41
25000
47.65 + 0.37
45.14 + 0.43
35000
45.40 + 0.33
43.21 0.20
Table Classification error rates (%) on noisy and denoised CIFAR-10 images for varying training set sizes Nurin The noise level is 0.4, = 1, and the denoiser is trained using MSE loss.
Figure 4 shows the classification error vs. the training epoch in a single trial for noise level 0.25, 7 and 35,000 training images. demonstrates that the classifier does not suffer from overfitting.
Engr
Bost brie Ter Engr Aevigristtt (/00
Aoymplitee EAES
Menutll
Smar200
2000%
20-
Hmmll
1 www.mmm
10
130
200
300 350
180
1500
230
250
330
Noisy data
(b) Denoised data
Figure 4: Training and testing error as function of epochs for (a) noisy data and (b) denoised data. The noise level is 0.25, y = 1, and Nu 35,000. The denoiser trained using MSE loss.
49

---

Published as a conference paper at ICLR 2026
12
10
Efficiency (%)
Efficiency
5000
10000
15000
20200
25000
30000
35000
5000
10000
15000
20000
25000
30000
35000
N_train
N_train
(a) 0 = 0.25,1 7
(h) 0.4,-=1
Efficiency (%6
Efficiency
2
5000
25000
20000
N_train
N_train
(c) 0.25, 0.75
(d) 0.1, 0.75
10
10
Efficiency (%)
Efficiency
N_train
N_train
(e) = 0.25, 0.5
(1 0.4, 0.5
Figure 5: Practical deep learning setup with noisy CIFAR-10 10 and of the data processing procedure versus the number of training samples for various values of the training imbalance factor, 7, and the standard deviation of the noise, a.
denoiser. Efficiency
D ADDITIONAL EMPIRICAL DETAILS AND RESULTS (MINI-IMAGENET, ENCODING)
D. EXPERIMENTS COMPUTE RESOURCES
We conducted our experiments using 16 NVIDIA Tesla V100-SXM2 GPUs with 32GB memory, 12 NVIDIA RTX 6000 Ada Generation GPUs with 48GB memory, and 2 NVIDIA A100 PCIe GPUs with 80GB memory. The training time for each data point Figures and ranged from 10 hours to 30 hours, depending the number of training samples.
50

---

Published as a conference paper at ICLR 2026
16
14
14
Efficiency (96
40
Efficlency
8
2
0
5000
10000
15000
20000
25000
30000
35000
5000
10000
15000
20000
25000
30000
35000
N_train
N_train
(a) 0.25, 0.75
(b)
0.75
14
12
Efficiency (%)
Efficiency (96)
10
0
6
2
0
5000
10000
15000
20000
25000
30000
35000
5000
10000
15000
20000
25000 30000
35000
N_train
N_train
(c) 0.25, 0.5
(d) 0.4, 0.5
Figure 6: Practical deep learning setup with noisy CIFAR-10 and MSE-based denoiser. Efficiency of the data processing procedure versus the number of training samples for various values of the training imbalance factor, Y {0.5, 0.75), and the standard deviation of the noise, σ.
D.2 TRAINING THE CLASSIFIER
We consider the Mini-ImageNNe dataset and the ResNet50 model. To train the model, use: batch size 128 and 225 epochs; cross-entropy loss; SGD optimizer; learning rate: 0.0679; learning rate decay: 0.1 epochs 75 and 150; momentum: 0.9; weight decay: 0.0005. This setting yields 73% accuracy for clean data.
50 100
Per noise level {
255 255 of the additive Gaussian noise that has been added to the data, use this setting to train one classifier that operates directly on the noisy data.
D.3 TRAINING THE ENCODER
For self-supervised learning, adopt the DINOv2 framework (Lu et al., 2025). The student encoder Vision Transformer (ViT-S/16), which splits each input image of size 224x224 into 16x16 patches and produces 384-dimensional [CLS] token representation. This is passed through a 3-layer MLP projection head to produce the final -56-dimensional embedding (z E 2226),, which is used for self-supervised training. The teacher network has the same architecture and is updated as an exponential moving average of the student, providing stable target embeddings. Training is performed on the Imag-eet dataset for 200 epochs with per-GPU batch size 40. We apply the Adam W optimizer with a base learning rate of 0.004 (scaled with the square root of the effective batch size), 3 = (0.9, 0.999), weight decay scheduled from 0.04 to 0.4, and gradient clipping at 3.0. The teacher momentum is linearly increased from 0.992 to 1.0 over training. Multi-crop augmentation is employed with 2 global crops of size 224x224 and 8 local crops of size 96x96. Model evaluation is conducted every 6,250 iterations.
51

---

Published as a conference paper at ICLR 2026
30-
35
30
Efficleccy (%6
BRiciency
20
5000
10000
15000
20000
25000
30000
25000
40300
5000
15000
15000
20000
25000
30000
25000
40000
N_train
N_train
(a)
0
255
50
7 = 0.75
(b) 0
253
100
0.75
40
30
(%)
Effciency (K6
10-
10000
20000
30000
N_train
(c)
50
0.5
(d)
100
0.5
255
265
Figure 7: Practical deep learning setup with noisy Mini- MitieNm and pre-classification encoding. Efficiency of the data processing procedure versus the number of training samples for various values of the training imbalance factor, {0.5, 0.75), and the standard deviation of the noise, a.
D.4 TRAINING AN MLP ON TOP OF THE EMBEDDINGS
50 100
255 255 after training the DINOv2 encoder, we pass the noisy Mini- ImageNet images through the encoder to obtain 256-dimensional embeddings. On top of these embeddings, we train a multi-layer perceptron (MLP) classifier to perform image classification. The MLP consists of three hidden layers with dimensions 4096, 2048, and 1024, each followed by LayerNorm and GELU activation, and final linear layer mapping to the number of classes (i.e. 100). Hidden layers initialized with Xavier uniform, and the final layer with small normal distribution.
Per noise level {
To train the model, we use: Per-GPU batch size 128 and 20 epochs, with 1250 iterations per epoch; cross-entropy loss; SGD optimizer with cosine annealing learning rate schedule; momentum: 0.9; no weight decay. Linear evaluation is performed with periodic check-pointing and evaluation on the validation set. After training, the classifier is evaluated on the test set to report final accuracy.
The results for the setup with y < 1 are presented in Figure 7 can be seen that they resemble the results in 1) similar non-monotonieity of the curve while remaining positive, and 2) the maximal efficiency increases with the SNR, for fixed
D.5 NUMERICAL ACCURACY RESULTS
In the following Tables and we report accuracy results related to Figure 3 Lastly, in Figure & we present an image of noisy data for a E (50/255, 100/255], to show that the noise is not too-severe.
E ADDITIONAL EMPIRICAL DETAILS AND RESULTS (CIFAR- 10, ENCODING)
We investigate the CIFAR- 10 dataset and the ResNet18 model. Both the training and test sets are subjected to additive Gaussian noise with standard deviations E (0.25, 0.4). This time, as the
52

---

Published as a conference paper at ICLR 2026
Irain
Error without encoding (%)
Error with encoding (%)
5000
80.03 1125
48.67 =0.48
10000
74.56 =1.12
45.03 =0.27
20000
58.81 =0.45
41.45 #0.29
30000
49.92 +0.8
39.23 #0.39
40000
44.95 1137
37.99 #0.31
50000
40.07 0.58
36.62 0.255
Table 3: Classification error rates (%) noisy and encoded Mini-ImageNee images for varying
training set sizes Numin- The noise level is
205
30
=
Irann
Error without encoding (%)
Error with encoding (%)
5000
85.3 +0.95
60.94 +.22
10000
79.71 =1.73
57.28 10.23
20000
68.47 2215
53 0.27
30000
58.39 =1.77
50.92 #0.31
40000
54.62 =0.08
49.35 00.44
50000
50.01 00.6
48.23 0.227
Table 4: Classification error rates (%) noisy and encoded Mini- Mini-ImageNet images for varying
100
training set sizes Nuain- The noise level is
255
(a) clean
50 (b)
(c)
255
255
Figure 8: Clean and noisy Mini-Image ImageNet images. (a) Clean image. (b) Image with Gaussian noise 50
0 255 (c) Image with Gaussian noise o 255
100
53

---

Published as a conference paper at ICLR 2026
80
70
Efficiency (80)
60
Efficiency (96
50
30
80
30
30-
5000
10000
15000
20000 N. trainn
25000
30000
35000
5000
10000
15000
20000
25000
30000 35006
N_train
(a) 0.25, 7
(b) a 0.4,
Figure 9: Noisy CIFAR-10 and pre-classification encoding. Efficiency versus Nuain-
20.0
Gamma values
(theory)
y 0.25 Isimulation)
17.5
Y 0.5 (simulation)
(theory)
Efficiency (86)
12.5
(simulation)
10.0
7.5
25
0.0
2000
4000
6000
8000
10000
N_train
Figure 10: The theoretical setup. Efficiency of the data processing procedure versus the number of training samples Nuain, for various values of the training imbalance factor y, and SNR of = =.
data processing procedure we use an encoding step that maps each image (rescaled from its original CIFAR-IO resolution 224 224) into 256-dimensional embedding. This encoder model follows (Lu et al., 2025) and is trained from scratch with self- alf-suuervision on 45000 noisy unlabeled images each noise level. Then, for each combination of (o, Niram), considering the balanced case of = 1, we divide Nimin equally among all 10 classes. Then, we train a ResNetl8 model on the noisy images across seeds and, in parallel, a small MLP on the corresponding embeddings across seeds. After we have the mean of the probability of error before and after the data processing, we compute the empirical efficiency, i.c., the relative percentage change in the probability error induced by the encoding step. Details of the training procedures for the ResNet18 and the MLP are provided in Appendix and D respectively.
Figure Sacureepprrssee presents the efficiency versus Nurin- for 1. We see the same trends that are aligned with our theory as before: 1) similar non-monotonicity of the curve (increase to maximal efficiency value and then decrease) while remaining positive, and the maximal efficiency increases with the SNR.
F EXTENDED EMPIRICAL VERIFICATION
In this section, we extend our empirical verification. Figure I0 we simulate the theoretical setup, in 3.3 (we use d 2000, & 1000 and 1), but with S We see that the empirical efficiency coincides with the theoretical efficiency.
We examine the effect of S efficiency. We fix 7 1, 2000, 1000 and vary Se {0.52,1, 1.52). The results are presented Figure 11 Let us discuss the results. We see that for Numi > 1 (in the right Figure), for larger SNR (lower noise level), the efficiency decreases. However,
54

---

Published as a conference paper at ICLR 2026
07T 2011
2006
4003
50.0
0000
1800
3086
1580
2000
25300
3000
30.00
50000
(a) Nirain 5 10, 000
(b) 10, 000 5 Nirai S 50, 000
Figure 11: Extended simulation of the theoretical setup. Efficiency of the data processing versus the number of training samples Nirinn for 1, and various values of the SNR, S, for (a) low samples regime, and (b) high samples regime.
25
(nwer)
(nwery) K- 2500 (amnuatioo)
Efficency (1)
8
2000 4000
8000
5000
10000
Nutrain
Figure 12: The theoretical setup. Efficiency the data processing procedure versus the number of training samples Nurain for various values of the training imbalance factor, 7, and SNR of S 1.
as 8 suggests, when the number of samples is limited, and for larger SNR (lower noise level), the efficiency increases. We notice this phenomenon in the left Figure, presenting low Nurin compared to the right Figure. First, the efficiency increases with the SNRs, and then as Numin gets larger, the dependency flips. We also see different behavior that sheds more light on this conclusion: the difference between different SNRs is larger in the low-samples region than the inverse relation in the high-samples region. This concludes the non-monotonic and non-intuitive dependency of the efficiency on the SNR.
In addition, examine the effect of d k on efficiency. We fix 7 = 1, 2000, S and vary E (500, 1000, 1500]. The results are presented in Figure 12 We see that larger d corresponds greater accuracy. Theorem proves this for Nirin >> 1, but Nunin- Indeed, intuitively, reducing more dimensions is advantageous in terms of efficiency. This suggests that there is direct monotonic relationship between the efficiency and d k.
that this is true even for small
We now consider the same setting as in the empirical verification (d = 2000, k = 1000, = 1, Y (0.25, 0.5, 1}. E (0.75?, 1, 1.52)) but per Nuain the data processing matrix A is learned from 50,000 unlabeled samples using the algorithm described in the proof of Theorem corresponding results are shown in Figure [3 demonstrating the same trends as the theoretical efficiency. Moreover, as the number of unlabeled samples tends to infinity, the two curves coincide. To illustrate this, we also present results for the case that per Nuzin- the data processing matrix A is learned from 5, 5,,000.000 unlabeled samples in Figure Notice that as the amount of unlabeled samples available grows, the gap between the theoretical efficiency and the empirical efficiency is reduced.
The
Finally, we visualize the action of A IR22 on the GMM data in Figure 15 considers the regime d k > 1, as is common in practice, use small values of d 2 and k = 1 to enable visualization.
While our analysis
Recall that the plug-in classifier, before and after the data processing, depends only the distance of a test sample from each of the empirical means. Without processing, these empirical means
are given by fa N, Σ Dm æi.j and hence distributed as faz N (143, N, Ia). Similarly, after
55

---

Published as a conference paper at ICLR 2026
Cemera Shang
17.5
15.0
12.5
025 (heary
3.0
2000
6000
trah
8000
1003
12000
2003
4000
0000
5000
10000
(a) S = 0.75
(b)
2-222 Dheenl
23
H- Therp
Emiarnc
4000
5000
5000
10000
N.train
(c) 1.5
Figure 13: Extended empirical verification per Nurin A is learned from 50,000 unlabeled examples. Presented for (a) S = 0.75², (b) = 1 and (c) S 1.5
processing by Rd - R² the empirical means obey Aū, ~ N (AH1 o² semi-orthonormality AA T I is used. Consequently,
N₂ It). where the
[1ū 2nl = Σ (1āg)) - [mm]))
d
N₂
N₂
i=1
where we used [P,l - [Myls N (0. Similarly, [I
Au,
N₂
The data processing lowers the dimension from d to k and thus improves the average squared error of the mean estimator by
a² N (d k)>
Since the classifier, before and after the data processing, depends only on the distance of the test sample from each the empirical means, its accuracy increases when the accuracy the empirical means improves while the distance between the means of the difference classes does not significantly The latter is accounted for by the property ||||||| = |||||
reduce (i.e.. A Aprl of the operator.
Note that this behavior observed in Figure 15
In the red class, the distance between the empirical mean and the real mean is 0.4632 before applying A and 0.39 after applying A.
In the blue class, the distance between the empirical mean and the real mean 0.439 before applying A and 0.38 after applying A.
The distance between the empirical means of the different classes is 4.0374 before applying and 4.01 after applying A. Indeed, both are close to the distance between the real means, which is 4.
56

---

Published as a conference paper at ICLR 2026
Gartena velum
17.5
DJ theey!
15.0
10.0
1-233 Joary
(hwrry
0.0
2000
6000
EC00
10000
Nutrnn
N.tran
(a) 0.75
(b)
Conena valees
x- banelaee
0
Emr sancaay 19
1
(c) S 1.5
Figure 14: Extended empirical verification - per Nu A learned from 5,000,000 unlabeled examples. Presented for (a) S 0.75 (b) S = 1 and (c) S 1.5².
That is, A preserves the separation quality of the classes, while improving the estimation quality of μ.
57

---

Published as a conference paper at ICLR 2026
(a) The original data, sampled from GMM in R2a with μu - o == 1, and Nuain = 30. The true means (2,, are marked by black 'X's and the empirical means { fuz} are marked by green diamonds. The learned decision boundary is marked by the dashed line (determined by the distance to the empirical means).
1.62
2.39
(b) The data after applying E R22x2 (in this case, projection onto x-axis). As before, the true means [Api, Ap2) are marked by black 'X's and the empirical means (Atz, Aūa) are marked by green diamonds.
Visualization of the effect of A R22 > R. Note that the empirical means (green diamonds) closer to the means (black 'X's) after the operation A. The distance between the empirical means of the different classes remains similar.
Figure 15:
58


Reviews:
[{"review_id": "w8lTpnONWj", "reviewer": "Reviewer_p7cK", "summary": "This paper investigates theoretical perspectives on the data processing inequality in classification, suggesting that appropriate preprocessing can improve finite-sample performance.", "questions": "Please see weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper studies an interesting question: whether the data processing inequality reflects practical deep learning behavior and connects a foundational information-theoretic concept to empirical DNN practice.\n\n2. The theoretical derivation is mathematically sound under its assumptions, offering a clean proof for the potential benefit of preprocessing under finite-sample conditions.\n\n3. The paper is well-written and visually clear, with carefully structured derivations and supporting empirical examples.", "weaknesses": "1. The theoretical model y→x→z implies a generative process, but deep models for classification follow a discriminative direction \nx→z→ $\\hat{y} $. This mismatch weakens the claimed alignment between the theoretical framework and modern deep learning models.\n\n2. Eq. (3) assumes a Gaussian Mixture Model where data 𝑥 is generated conditional on label y. This assumption is conceptually inverted from real-world classification, where 𝑥 precedes 𝑦.\n\n3. The theory defines 𝐴 as a linear transformation matrix, while experiments use nonlinear modules (DnCNN, Lu et al., 2025). The inconsistency makes it unclear whether the empirical findings genuinely validate the theory.\n\n4. Although 𝐴 is constructively derived, the paper lacks intuitive explanation of how 𝐴 preserves or amplifies discriminative information. Visualizing its action in feature space or relating it to known transformations would strengthen the conceptual link between theory and practice.\n\n5. The preprocessing step 𝐴𝑥 resembles data augmentation. If its primary function is to improve robustness via representation smoothing, the novelty may be overstated. Clarification is needed on whether the proposed framework represents a fundamentally new mechanism.\n\n6. The experiments inject noise into data and then apply denoising, creating a circular setup that demonstrates improvement. This does not convincingly validate the theoretical claims or show robustness in realistic settings.\n\n7. CIFAR-10 uses denoising (DnCNN), while miniImageNet uses encoding (Lu et al., 2025). Why not keep the processing method consistent, and how is the appropriate process determined for different datasets? The theory treats the processing step \n𝐴 as a general transformation matrix and is not dataset-specific.\n\nMinor: \n\n1. The experiments on small datasets such as CIFAR-10 and miniImageNet, and ResNet only, are not enough to convincingly support the theoretical claims. Evaluating on larger-scale datasets and other architectures, such as ViT, is encouraged. Though the paper emphasizes theoretical contributions, demonstrating practical benefits is still necessary to substantiate its real-world relevance.\n\n2. Can you provide the source code for Figure 1? This will help me better understand the connection between the theoretical derivation and its empirical illustration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dFBwkwyxtp", "reviewer": "Reviewer_yFZ5", "summary": "Consider the binary classification problem.\nIt is a general belief that preprocessing data makes the performance of the Bayes classifier worse assuming that we know the ground truth distribution.\nWe would like to ask a question: If we use a practical classifier and we do not know the ground truth distribution, does the conclusion of the performance of the practical classifier getting worse still hold?\nIn this paper, the authors study this question and give a negative answer.\nThe authors consider the following setting.\nSuppose the underlying distribution is the mixture of two equally weighted standard Gaussians with symmetric means.\nEach sample from the training set is drawn from the distribution with a label indicating which Gaussian it is drawn from and the estimated mean for each Gaussian is the simple averaging of the corresponding samples.\nEach sample from the test set is also drawn from the distribution without a label.\nThe classifier is to classify the sample to be the Gaussian whose estimated mean is closer to the sample.\nThe preprocessing is a linear transformation whose matrix is semi-orthogonal and norm preserving.\nThe result shows that the error for the preprocessing data can be smaller than the error for the original data.", "questions": ".", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem is well-motivated.\nThe result may open a new line of work on this topic.", "weaknesses": "- Though the authors provide some experimental results, the theoretical explanation is based on a simplified setup.\nIn other words, the theory-practice gap is large that there may be a limited interpretation when extending to more realistic settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3XyDWUETj1", "reviewer": "Reviewer_PqbN", "summary": "This paper investigates when and why low-level data preprocessing can be beneficial for a strong classifier (e.g., one that converges to the optimal Bayes classifier). The authors first prove the existence of a preprocessing (dimension reduction) procedure that can improve classification performance. They then establish theoretical results illustrating the influence of various factors, such as the number of training samples and the degree of class separation. The analysis is further supported by both simulation studies and real-data experiments.", "questions": "1. Is the data processing step restricted to the dimension reduction procedure defined in Equation (7)?\n2. In Theorems 5 and 6, is it possible to characterize how $\\hat{p}_x$ compares to $\\hat{p}_z$? Specifically, does the difference between them vary with certain parameters?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem studied in this paper is interesting and important.\n2. The theoretical analysis is solid.\n3. The authors consider various scenarios and influencing factors in their theoretical derivations.", "weaknesses": "1. The writing can be improved. For example, Section 3.2 discusses multiple scenarios; it would be helpful to outline them at the beginning of the section. In addition, providing some intuition behind the theorems would improve readability and accessibility.\n2. Some theorems could potentially be extended (see the question below).\n3. The data processing analyzed in this paper can restrictive (see the question below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)