Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing
Authors: Adel Javanmard
Rudrajit Das
Alessandro Epasto
Vahab Mirrokni
Venue: NeurIPS 2025 poster ()
Keywords: Retraining
Predicted Labels
Label Noise
Approximate Message Passing
Primary area: theory
TL;DR: We develop a principled framework using approximate message passing (AMP) to analyze iterative self-retraining of ML models and derive the optimal way to combine the given labels with model predictions at each retraining round.

Abstract: Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model’s performance. While prior works have demonstrated the benefits of specific heuristic retraining schemes, the question of how to optimally combine the model's predictions and the provided labels remains largely open. This paper addresses this fundamental question for binary classification tasks. We develop a principled framework based on approximate message passing (AMP) to analyze iterative retraining procedures for two ground truth settings: Gaussian mixture model (GMM) and generalized linear model (GLM). Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels, which when used to retrain the same model, minimizes its prediction error. We also quantify the performance of this optimal retraining strategy over multiple rounds. We complement our theoretical results by proposing a practically usable version of the theoretically-optimal aggregator function and demonstrate its superiority over baseline methods under different label noise models.

Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing
Adel Javanmard
Rudrajit Das Google Research dasrudrajit@googlee. com
Alessandro Epasto Google Research
University of Southern California
Google Research
aepasto@google.com com
aj avanma@usc.coommmmmmmm edu
Vahab Mirrokni
Google Research Aurrokni@googe.. com
Abstract
Retraining model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model's performance. While prior works have demonstrated the benefits of specific heuristic retraining schemes, the question of how to optimally combine the model's 's predictions and the provided labels remains largely open. This paper addresses this fundamental question for binary classification tasks. We develop principled framework based on approximate message passing (AMP) to analyze iterative retraining procedures for two ground truth settings: Gaussian mixture model (GMM) and generalized linear model (GLM). Our main contribution is the derivation of the Bayes optimal aggregator function to combine the current model's predictions and the given labels, which when used to retrain the same model, minimizes prediction error. We also quantify the performance of this optimal retraining strategy over multiple rounds. We complement our theoretical results by proposing a practically usable version the theoretically-optimal aggregator function and demonstrate its superiority over baseline methods under different label noise models.
Introduction
Learning effectively from data with noisy labels remains significant challenge in supervised machine learning (ML). simple approach to mitigate the impact of label noise involves leveraging the trained model's own (soft or hard) predictions to ameliorate the learning process. More specifically. prior works [25, 11, 10, 32, 9] have shown that retraining an already trained model using own predictions and the given labels (with which the model is initially trained) can lead to higher model accuracy, especially when the given labels are noisy. [11, 10, 32, 9] theoretically quantify the gains of simple retraining schemes and also provide principled explanations of why retraining is beneficial, such as the predicted labels leading to variance-reduction, leveraging large separability the classes, etc. However, key question that remains unanswered is the following:
"What is the optimal way to utilize the model's predicted labels and the given labels?"
In this work, we address this question for binary classification problems where the underlying ground truth model is: (i) Gaussian mixture model (GMM), or (ii) a generalized linear model (GLM). Further, we also analyze the effect of multiple rounds of retraining. More specifically, for a sample æ. suppose is the given noisy label and y is the model's predicted label at the th round of retraining,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

then we derive the Bayes optimal aggregator function (i .D) which should be used to retrain the model in the (t + 1)th round in order to minimize its prediction error. Our analysis technique is very different from the aforementioned prior works in this space and is based on Approximate Message Passing (AMP) [13, 35, 18]. We believe ours is the first work that addresses this question of optimally using the predicted and given labels. Building on our theoretical framework, we also develop an aggregator function that can be used in practice for training with the binary cross-entropy loss.
Before stating our contributions, we need to briefly introduce the problem setting. We consider binary classification setting (with labels {+1)), where for each sample æ, the given label y is equal to the true label y with probability 1 1-p> > 2 and the flipped label -y otherwise, independently for each sample. In the Gaussian mixture model (GMM) case, we have I = y/u+ + 2, where f e Rd and I). In the generalized linear model (GLM) case, we have Pyy = 1|2) h(x= for some G Rd and known function h(.). We are now ready to state our main contributions.
(a) We introduce and analyze an iterative retraining scheme based on Approximate Message Passing (AMP) [13, 35, 18]; see (4)-(5) for GMM and (17)(188 for GLM. We provide precise characteriza- tion of the effect of retraining in an asymptotic regime, where the ratio of the number of examples to the feature dimension converges to a constant. In particular, for our setting a concise deterministic recursion that captures the asymptotic behavior of the AMP-based estimator, see (8), Theorem 3.1 for GMM and (22), Theorem 4.2 for GLM.
derive the state evolution recursion
(b) We derive the Bayes optimal aggregator function gr (v' T) to combine the model's prediction y at the &d round of retraining and the given label T to be used in the (t + 1)th round of retraining for minimizing prediction error in Theorems 3.2 and 4.3 for GMM and GLM, respectively. To our knowledge, ours is the first work to analyze the optimal way to use the predicted and given labels for any retraining- like idea in any setting.
(c) Based on our theoretical analysis, we develop a strategy that can be used in practice to combine the given labels and predictions for training any model with the binary cross-entropy loss (Section 5). We show that our method outperforms existing retraining baselines under different label noise models.
2 Related Work
(i) Retraining (fully supervised setting). [9] theoretically analyze the idea of retraining a model with only its predicted hard labels and not reusing the given labels when they are noisy; they call this "full retraining". [9] also propose cconsensus-basee
retraining" which is the process of retraining only using the samples for which the predicted label matches the given label. Another related idea is "sstf-ddstillatiio"" " (SD) [15, 26]. where a teacher model's predicted soft (and not hard) labels are used to train student model having the same architecture as the teacher. [25] empirically demonstrate that SD can improve performance when the given labels are noisy. [11, 10] theoretically analyze the benefits of one round of SD in the presence of noisy labels, while [32] analyze the effect of multiple rounds of SD in setting similar to [10]. [39] do a statistical analysis of SD in the asymptotic limit, compare the effect of soft labels & hard labels, and also investigate the effect of multiple rounds of SD. But unlike us. [39] do not analyze the optimal way to combine given labels and model predictions.
(if) Self-training (ST). In the semi-supervised setting, ST [38, 43, 23] is the process of iteratively training a model wherein it is initially trained using the labeled samples, then labeling the unlabeled samples, followed by retraining the model on the labeled samples as well as the unlabeled samples on which the model is confident. This process is often repeated few times. While this sounds similar to retraining, our work is in fully supervised setting and retraining does not particularly rely on the model's 'ss confidence. See [2] for a survey on ST and some related approaches. There is also a significant amount of theoretical work on characterizing the efficacy of ST and related approaches [7, 34, 21, 8, 31, 41, 44]; but these results are not in the presence of noisy labels. Furthermore, there are empirical ideas related ST in the context of label noise [37, 40, 17, 30, 24, 16).
(iii) Approximate Message Passing, Due to lack of space, we defer this to Appendix A.
Notation: We use the boldface symbols to denote vectors and matrices. The lg norm of a vector e denoted by | For any n e N, the set (1...., n.) is denoted by [m]. With a slight abuse of notation, we use P(X) to indicate the probability mass function (for discrete random variable X) as well as the probability density function (for continuous variable X). We write & to denote

---

convergence 'in probability'. $(=) -/2 e du denotes the standard gaussian CDF. A function v IpP IR is said be pseudo-Lipschitz (of order 2) if for all u, R2, have (+(()) (x)) s L(1 ||u| + [|/l)[(e ol] for some constant L.
3 Gaussian Mixture Model (GMM)
Data model. We assume the training data {(z,, 3=) are generated i.id according to a Gaussian mixture model. In this model, each data point belongs to one of two classes {+1] with corresponding probabilities It, n-, such that TT + πー Denoting by y: E +1] the label for data point i, the features vectors æ; [dd for i [n]. J, generated independently as
yu
(1)
where = NO,,), In other words the mean of features vectors are + depending on its class. Throughout, we denote the features matrix and the labels vector by
x [..l...(m,)) Raxd
y [V1,
Vn R"
The learner does observe the labels Yı. rather she has access features vectors æ; and noisy labels Dú which are generated according to the following model:
with probability 1 P
T
-
with probability p,
where p 2 is the mislabeling or label flipping probability. Let ÿ = [T....., [[......,,.' R" denote the vector of the observed noisy labels.
Standard linear classifier model. Let first consider the following simple classifier model:
1 x
The above model has been used before in [9, 7]. For given point æ, the model's soft prediction is xe O and its predicted label is sign(a: 0).
In this work, we consider slightly different model inspired by Approximate Message Passing (AMP). Since focus is retraining over multiple rounds, we will delineate this an iterative procedure.
3.1 Retraining Framework Inspired by Approximate Message Passing
For ease of exposition, we begin by giving high-level outline of the retraining process. At iteration t of the process, let 0³ e Rd denote the current model and y E IR" denote the vector of the soft predictions of the model on the training data. In the next iteration, the algorithm combines y and the observed noisy labels ÿ using the function Jt to obtain 9: (v', " .7 which are the target labels for retraining in the (t + 1)th iteration. We refer to as aggregator function and keep it general for now. We will later discuss different options for gr, including the Bayes-optimal choice.
Let us now delve into the details. With an aggregator function gt, we have the following update rule for 2 0:
1
0+01
X
-
(model-update step),
(4)
Vn
d
-x0+ (3 77)
(soft-prediction step).
(5)
The function is applied entry wise, i.c., gr (yy' 3y,",, D is the vector whose 7th (i [n]] entry is given by go (v). D.). The coefficient C. R is given by
dg. Dy
C
(y. Th) y-
(6)
As mentioned in [9], this is reasonable simplification of the least squares' solution for analysis purposes.

---

We initialize this process with go (): G notice that Co = 0.
There crucial differences from the standard model in (3): (i) instead of having normalization factor of 1/n in the model-update step, we split it between the model-update and soft-prediction steps in our process by incorporating factor of 1/vni at each step. Note that the scaling of the estimator does not matter since the predicted labels only depend on the direction of the estimator. (it) we have 'memory correction' terms (-C,0' and - -9: (y' 77 d in both steps.
The updates (4) and (5) are in the form of Approximate Message Passing (AMP), which was introduced by adapting ideas from graphical models (belief propagation) and statistical physies to estimation problems [13, 35, 18]. The memory correction terms -C,0' and -9: wg",7 T7) d (also called "Onsager' correction in statistical physics and the AMP literature) can be thought of as momentum term, and plays a key role in ensuring that the asymptotic distributions of (0', yy are Gaussian. To build some insight on the role of these memory terms, note that the data matrix X is fixed across iterations, and so 0', y and are correlated, which induces some bias in the estimates, The memory terms are designed specifically to act as debiasing terms to compensate for this dependence. Specifically, the effect of these corrections is the same as an iterative procedure without these terms, wherein the data matrix is resampled at every iteration, making it independent from the current estimates (as pointed out by [4, 12J. Of course the latter not a practical algorithm, since the data matrix is fixed, but it is shown that both will have the same limiting behavior.
3.2 Analysis of the Retraining Process
Assumption We assume the following:
As n, d + co, the ratio d/n + a E (0,
The empirical distributions of the entries of (Vd+) (recall =u the class means; see (1)) converges weakly to probability distribution Vas on with bounded second moment. Let
72 = Euas [M²].
The function 9: IR R + IR is Lipschitz continuous.
We first characterize the test error of a model 0 under our data model.
Test classification error. For model 0, its predicted label for a test point x is given by sign(x:
Therefore, the classification error amounts to (recall that ((u)= V
1 S (1/ddtt):
11 T
Po( Pyy 0 < <) =P((( ==)0< P(yz To <xu +b
(7)
[001,
State evolution. A remarkable property of AMP algorithms is that their high- sigh-dimensional behavior admits an exact description. In essence, the vectors 0' y have asymptotically i.i.d. Gaussian entries in the asymptotic regime (Assumption 2), at fixed f. The mean and variance of 0', y² can be computed through deterministic recursion called state evolution. The validity of state evolution has been proved for a broad class of random matrices. Before describing it for our current setting, we establish some notation.
Let Y be a random variable distributed as original labels, namely PYY 1) = n. and P(Y = =1) = т...
Also, let Y be random variable distributed as noisy labels, namely P(Ý Y) (1 p) and P(Ý -Y) = p. The state evolution involves sequence of deterministic quantities (m4 dz 120 defined by the following recursions:
mr Vamm, am=a(m; + of)
Me+1 - f ()r) o.. (m,++,,,
(8)
where G~ ~ N(O, 1) is independent of other random variables. The next theorem (proved Ap- pendix B) implies that the the empirical distribution of ((Vdu, ( converges weakly to the probability distribution of (M, M + o,G), where (m) are given by the state evolution se- quence. As a consequence, can used to characterize the limiting behavior of (0) (test error of the model) in terms of state evolution sequence.

---

Theorem 3.1 Let (0', y'o be the AMP iterates given by (4)-(5) Also let (m4: 0t) so be the state function
evolution recursions given by (8). Then under Assumption L, for any wb: R² + R the following holds almost surely for & 0:
1 E ( Vap.e -F - (MM() =0,
Tim 20
where G ~ N(O,1), M ~ VM (see second bullet point of Assumption 1) are independent. Recall that (o(: 77) g. which corresponds the initialization of state evolution recursion with m. 711 - 2p)/ // and 01 = 1. In addition, we have almost surely:
lim Pe = -
(10)
V m2 +o7
3.3 Optimal Choice of Aggregator Functions
In the AMP iterations (4) and (5), O' is the model estimate and y² is the soft predictions vector at iteration t. We will now discuss some examples the aggregator function gri particular, these examples describe the retraining methods proposed in [9]:
Full retraining [9]: this case, 9: (3y 3) sign( y²) for t 2 1. So in this type of retraining, the noisy labels are not used and only the current model's 's predicted labels are used.
Consensus- based retraining [9]: Here, St (ty" D) 7 (1y' 7 0) for / 2 1. Thus, retraining is done only using the samples for which the predicted label matches the noisy label.
Note that the result of Theorem 3.1 does not apply to these examples directly, because the gi 's here are not Lipschitz. However, we can approximate them by Lipschitz functions, see (37) and Appendix for further details.
In this section, we aim to derive the optimal choice of aggregator functioon. Note that from Equa- tion (10), the test error of of is an increasing function of m//a:- Suppose that the retraining is run for iterations, so my og are determined. The optimal aggregator is the one that maximizes m./a. Recalling the state evolution (8), we have
m 72 Elgi(my + G.G. +o,G 72 E((2q)-1) a
Ti a E s
(11)
with 4: = P(Y = 1lm P). The above inequality holds because by the law of iterated expectations, we have
E(g((m, o, P)Y) [mga +G,G, E) +GG =m{g(my + G,,G, (, 1)},
and (11) follows from Cauchy-Schwarc inequality. Also, the upper bound is achieved when ge is (any scaling of) 2q: - 1. Therefore, for this optimal choice of 97 we have
m
E {(( (myy (m.Y+ +),
on. =
(12)
V
and M4411
2 oir Va
We let th
my and
Va
a² of
m
2 T a,
Th
m, onp
72 th (1 + 1).
(13)
Therefore, we write the state evolution and the optimal aggregator, only in terms of ne We formally state it in the next theorem (proved in Appendix C).
II is worth mentioning that [9] analyze the simple model in (3) and our based model.
5

---

Theorem 3.2 Recall that T- are the class probabilities and is the label flipping probability. The optimal aggregator functions for the AMP-based procedure (4)-(5) is given by:
9. (v.J)
(14)
1+
T-p exp
2y a( 1)
for 2 (recall that g6(- ()) 9). In addition, we have:
Po(O') 2
7h
Vn
where (16)221 is given by the following state evolution recursion:
2- I 12(00/( (oniin + a mmy nr 1G, a
Mh:1
(15)
with initialization 1/1 (1-
We perform some simulations in Appendix E to verify our theory, and compare the performance of optimal aggregator with the full retraining and the consensus- bases retraining schemes. Note that in the noiseless regime (p 0), the optimal aggregator becomes gī (y. 1) and 9 (v.-1) -1) -1 which is expected because in this regime, 1 is the ground truth label.
Discussion. The state evolution sequence (n)))a in (15) can be rewritten as n F( with
F(u) 2 E (0 a
G. P)) Ieu
2
TV
g(v.0)
(16)
14t
1 1-p
R
In Figure 1, we illustrate an example of this mapping along with the sequence (Th (Ti)) 121 (Cobweb diagram). As can be observed from the figure (and also formalized in Proposition 3.3), the mapping F is non-decreasing. When 7) small, the sequence Tr increases, while if 17 is large, the sequence decreases. Since the test error decreases initial model is poor, retraining helps improve its performance, but if the initial model is already good, retraining can actually hurt its performance. We formalize this observation in the next proposition (proved in Appendix D).
increases, this leads to an interesting observation: if the
Proposition 3.3 The following statements hold:
(i) The function F defined in (16) non-decreasing on co). Also, has at least one fixed point, i.e., there exists solution to n²² F Let n². be the smallest fixed point. If m. S Th then the state evolution sequence (11) is son-decreasing, and hence retraining reduces the test error.
(ii) Suppose that 7² Vo
ne 2.
sufficient condition for the sequence (11) be non-decreasing is -1-(1pp))
that e [pr, })) with < being the unique solution of the equation: +b
(T=(1-p))+aa
4 Generalized Linear Model (GLM)
Consider a data matrix X gaxd with rows æ1, x. N(O, La/n).² and corresponding labels = [yl....,y.. "n IR" generated with the following probabilistic rule:
P(y: 1|x;) h(2,.)))
for a known link function h. However, the learner observes noisy labels ÿ [T...... Fr R" where the T.'s follow the same noise model as (2) with being the label flipping probability. We also define (2) = (1 (2) + p(1 h(2)). Note that P(T: = 1|x,) = (=. (x)
'The scaling of 1/n in the covariance matrix is for ease of exposition. Our analysis can be extended even if the covariance matrix is Ia the cost of more tedious exposition.

---

Piv'
0.8
0.6
0.4
w/
0.5
Figure Cobweb plot for the state evolution in Theorem 3.1, with two initializations: (small)
TJ 0.2 and (large) 1. Here, 1.5, 0.3, a = 2, n 0.3, x_ 0.7.
AMP-based update rule: Similar to the AMP-hased iterative update rule for GMM in (4)-(5), we progressively update our classifier 3' iteration with an aggregator function gr as follows:
B++ XT "c 17 C. g x,g ge (v
(17)
d
(18)
n
Similar to the GMM case, the aggregator function is applied entry wise, the Onsager coefficient C. IR is given by
1 dge C
- 1 dy
y D.
V=
and the process is initialized with (o 77
We track the performance of the classifier 3 via its test error. For model 0, its predicted label for test point æ is given by sign(x' 0). We first state the assumptions needed for our subsequent results.
Assumption We assume the following:
As n, d oo, the ratio d/n + a (0,
The empirical distributions of the entries of B converges weakly to probability distribution 33 on with bounded second moment. Let = E, 1
The function 9: IR RR + is Lipschitz continuous.
Our next lemma (proved in Appendix G) characterizes test error of a model
Lemma 4.1 For a model 0 define its test error Pa(0) = Pp(y:: To 0), where (x,, y) is generated from the GLM. Define p 3 170
101l,,). Then,
pZ
(1-M + (V1 -
1-0 -0
M((Vr22)
P2(0) F(P) = T
V1 p
(Vi-p)
(19)
with Z N(0, 1). addition, F is a decreasing function, if h(u) h(-u), for all u 0.
State evolution. We will describe state evolution just as we did for the GMM case. The state evolution parameters (pe, 01 are recursively defined by:
2 2n E[Zh,
#1
01=1 =V=a
E(Z -EZIZz))
02 = o F P)]. ge (2,, 87).
P41
(20)
Var( 21
7

---

where Z ~ an²) and Z =, + G,G, where G ~ 1)), is independent of other random
variables. In addition, Y {-1,+11 ] with 1)) h (Z). Using the joint Gaussianity of (Zz, 2), we can calculate E(Z) 24) and Var Zi) more explicitly, as follows:
ap4
a0i?
E(Z]Z,)
ZE
Var (l) 0f app??
(21)
of + app
Using these identities, rewrite the state evolution recursion as:
2 E[Zhp(Z)],
A11 a??
oi=va
(22)
1 (2/22) an?
+ 1h of
Pt E[E(ZIZ, (9,1,,)))
= [[2,)(Z()))), of
8)).
Pt-1
The next theorem establishes that for every fixed t, the asymptotic behavior of 3 is precisely characterized by the state evolution recursion, which turn precisely provides the limiting behavior of the test error of ,3,, for every fixed iteration f. The proof largely follows from the analysis of generalized AMP (GAMPs) algorithm proposed by [35] along with Stein's lemma further simplify the state evolution recursion (similar to [27, Proposition 3.1)). Please refer to Appendix for further details and initialization of the state evolution.
Theorem 4.2 Let (B', .y' g') be the AMP iterates given by (17)-(18). Also let (pt, o1) be the state evolution recursions given by (22). Then under Assumption 2. for any pseudo- Lipschitt ab: R² + R the following holds almost surely t for
0:
1 d
Σ (3) -E [
- G
lim
(23)
Va
where ~ N(0,1) and 3 T (see second bullet point of Assumption 2) are independent. Recall that 90(-;) 7- T. which corresponds to the initialization of state evolution recursion with μi a7 F p where Z ~ N(O, an?), and as Va. In addition, we have almost surely,
lim Pe(3') F
(24)
1222
where T/2 pe/a: and (p) is given by (19).
Optimal choice of aggregator functions gt- Using Equation 24, and since a decreasing function, the optimal 9: is the one that, fixing the history of the algorithm, maximizes 1)+11 Invoking the state evolution (20), we have
1i+1
2
E (EZZZZ P)-I(2)))))((
(Z, 8) (2r(2)2.)
1 E a
E(Z 9) E(( 2
1
a F( ( P))
Var (2)
using the Cauchy-Sehie Schwarz inequality. The optimal aggregator for which the equality happens in the above equation, is when the aggregator is (any deterministic scalar) of
gi (Za, F) E( P) E(ZIZ))
E(ZIZ,,) 8)
Mt
1 E(Z P)
Mt
Z.
Ze. of
(25)
Var( 77)
ad2-2
of
We give a more explicit characterization the optimal aggregator in the next proposition, by writing E(Z|Z,Y P) explicitly using the Bayes rule. We also show that the state evolution for the optimal aggregator can be written directly in terms of T) ps/o1.
Theorem 4.3 The optimal aggregator functions in the AMP AMP-based procedure is given by:
2
1:3 (h)p))))
13 2²
_
2
(1 (1- kn))))
2072 de
9. (3. = {(a33' + Th
(26)
n (hx(2))
118
13
1_ e
23
(1 hpp)))
20 dz
8

---

fortz 1, and (x.0) = T. where (77))s1 is given by the following state evolution recursion:
2
(si om G,, o.n...D) }
1/1 23/2n²
E[ [Z),
Vi-1
(27)
a
where Z a(0) and G ~ N(O, 1) are independent of each other. In addition, Y E (-1,+1} with P(P 1[2) (Z).
The proof of Theorem 4.3 is in Appendix I. Similar trends to those described after Theorem 3.2 also hold in the context of GLMs. In Appendix J, we present a detailed discussion of special case of Theorem 4.3, specifically when the link function l is the sign function, along with additional remarks.
We discuss extension of our theory to the multi-class case and non-linear models in Appendix K.
5 Experiments
We show that extensions of the optimal 9i derived in Theorem 3.2 is very effective for improving the performance of standard linear probing (i.c., fitting a linear layer on top of pretrained model) [1, 22] as well as full network training with the cross-entropy loss for binary classification in the presence
of label noise. Here we consider two label noise models: (a) the uniform noise model in (2) with p
being the label flipping probability, and (b) a non-uniform noise model where P(ū: - -1yy = +1) =
and P(D: ++1y; -1) q with p q (independently for all E [n]). We adapt the derivation in (34) (in the proof Theorem 3.2) by considering general means and variances (instead of symmetric means and equal variances as (34)) obtained by fitting a bimodal GMM on the distribution of the unnormalized logits (E (-oo, oo) of the training set. Suppose the means and variances of the peaks corresponding to the positive and negative logits are (f,,o and (u_, .²). respectively. As shown in Appendix M, the aggregators we obtain here for logit 2 and given label T are the following for
2
(a) uniform noise model: g(2,0)
(28)
1+
(I-p)
exp
(z-Ra)² 20
2
(s-p )2
2
(b) non con-uriform noise model: g(=,))
1,
1
u(1-g) p(1-p) )
((--))(1-))
8/2
exp
(x-pe)² 2
(a-p-)) 2n
--
with g(z, 77 being the soft prediction we use for training in the next round. We call our method using the aggregation functions defined in (28) BayesMix RT, where RT is an abbreviation for retraining as used in [9]. Note that these aggregation functions are specific to the noise model and also depend on the noise model's parameters (e.g.. p. which may not be always available and easy estimate. So we propose the following simpler aggregation function that can be used under more general noise models (e.g., sample-dependen noise) and in scenarios where the noise model is not known:
2
Isimple (z. T)
(29)
1 + 7 exp
(3-Ra)² 207
(a-p_) 2
where y E (0,1) is a constant which can be tuned (and Isimple (2. TV is the soft prediction we use for training in the next round). Essentially, (29) replaces the ( (T-)) term in (a) of (28) by (tunable) constant 7. In our experiments, we fix 7 to 0.7 throughout without any tuning, thereby ensuring no reliance on the knowledge of the underlying noise model. We call our method using Isimlle 2. 7) BayesMix-Simpe RT and also propose to use it for full-network training." We compare BayesMix KT/BaaysMixx-Smppt RT with full RT and consensus- based RT proposed in [9].
For all our experiments, probing, we train only the linear head attached on top of the (frozen) pretrained body, while in full network training, we train the body well as the linear head. We consider two datasets available on TensorFlow: (i) MedMNIST Pneumonia [42] which is a medical binary classification dataset, and (fi) Food 101 [6] which is a multi-class food-based classification dataset, but we use only two similar classes, for e.g.. pho vs. ramen (because both are broth-basce dishes). All the results are averaged over 3 runs. The experimental details are deferred to Appendix N due to lack of space.
the body of a ResNet-50 model pretrained ImageNet. In linear
Linear probing. We run each method for 10 iterations. In Tables 1 and 2, we list the average test accuracies of full RT, consensus-basee RT, and BayesMix RT (28) after and 10 iterations for
'It is worth clarifying that all our aggregation functions depend on the class prior probabilities and ø-.

---

MedMNIST Pneumonia corrupted by the uniform noise model with p 0.45 (note that this is high degree of label noise) and the non-uniform noise model with p= 0.45 and q 0.2, respectively. RT after 10 iterations. Further,
Note that BayesMix RT is better than full RT and consensus-buse in Table 6 (Appendix L.), we conduct an ablation study on the uniform noise model to compare the three RT methods at different values of p. Next, in Table 7 (Appendix L), we compare full RT, consensus-based RT, and SerresMii--impplle RT (29) on MedMNIST Pneumonia corrupted by an adversarial noise model described in Appendix L.
Full network training. As mentioned earlier, we propose to use BayesMix-Simme RT (29) for full network training. We run full RT, consensus-basee RT, and BayesMix-Simple RT for iterations." In Tables and 4, we list the average test accuracies of each method after and iterations for 101 pho vs. ramen corrupted by uniform noise with = 0.4 and Food-105 10d spaghetti bolognese vs. spaghetti carbonara corrupted by non-uniform noise with p = 0.45 and q = 0.2, respectively. Note that BayexMix-Simpl RT is significantly better than full RT and consensus-based RT here (in fact, the latter two methods do not yield any gains here).
Table I; Linear probing and uniform noise (p- = 0.45): Average test accuracies + standard deviation for MedMNIST Pneumonia. In the first iteration of retraining, consensus-based RT performs the best, but at the tenth iteration, BayesMix RT performs the best.
Iteration #
Full RT
Consensus-basee RT
BayesMix RT (ours)
(initial model)
64.58 3.07
64.58 + 3.07
64.58 3.07
67.15 +: 4.28 (2.57 f)
68.32 + 1 1.88 (3.74
65.06 a 2.55 (0.48 f)
10
68.06 + 3.78 (3.48 1)
70.03 = 0.73 (5.45 1)
71.42 = 2.43 (6.84 f)
Table 2: Linear probing and non-uniform noise (p- 0.45, 0.2): Average test accuracies
4 standard deviation for MedMNIST Pneumonia. BayexMix RT performs the best.
Iteration #
Full RT
Consensus--ased RT
BayesMix RT (ours)
0 (initial model)
71.79 + 1.71
71.79 1.71
71.79 + 1.71
77.62 3.43 (5.83
77.85 2.69 (6.06 1)
82.63 + 2.02 (10.84 1)
10
79.74 3.40 (7.95 1)
82.85 1.44 (11.06 1)
84.39 = 0.79 (12.60 1)
Table 3: Full network training and uniform noise (p = 0.4): Average test accura- cies + standard deviation for Food-101 pho vs. ramen (both are broth-based dishes). BayesMix- RT is the clear winner; in faet, the other two RT methods do not lead to any improvements.
Iteration
Full RT
Consensus- based RT
SiresMix--Simplee RT (ours)
0 (initial model)
61.13 + 3.39
61.13 3.39
61.13 + 3.39
59.07 # 5.44 (2.06 1)
59.33 4.83 (1.80
66.73 + 3.72 (5.60 f)
3
57.67 # 7.47 (3.46 D)
58.47 6.78 (2.66 ()
70.67 + 4.65 (9.54 f)
Table 4: Full network training and non-uniform noise 0.45, q 0.2): Average test accuracies standard deviation for Food-101 spaghetti bolognese vs. spaghetti carbonara (both are spaghetti dishes). Again, BayesMix- SSmple RT is the clear winner.
Iteration
Full RT
Consensus-basee RT
FayesMix-Simplee RT (ours)
0 (initial model)
65.45 + 2.22
65.45 + 2.22
65.45 + 2.22
61.35 + 7.31 (4.10
61.30 (4.15
74.55 a 3.75 (9.10 f)
3
56.50 7.74 (8.95
59.70 5.57 (5.75
80.30 + 5.58 (14.85 f)
6
Conclusion
In this paper, we analyzed optimal model retraining by deriving the Bayes optimal aggregator function combine the given labels and model predictions for binary classification. Our framework quantified the performance of this strategy over multiple retraining iterations. We also proposed a practical variant and showed that it outperforms existing baselines under different label noise models. In the future, we would like to extend our results to the multi-class classification setting and theoretically analyze more general label noise models.
NNoe that training an entire deep network is much more computationally expensive than linear probing.
10

---

Acknowledgments
AJ was partially supported by the Sloan fellowship in mathematics, the NSF CAREER Award DMS- 1844481, the NSF Award DMS-231 an Amazon Faculty Research Award, Adobe Faculty Research Award, and an iORB grant from USC Marshall School of Business.
References
[1] G. Alain and Y. Bengio. Understanding intermediate layers using linear classifier probes. arXiv preprint arXiv: 1610,0164, 2016.
[2] M.-R. Amini, V. Feofanov, L. Pauletto, E. Devijver, and Y. Maximov. Self-training: A survey. arXiv preprint arXiv: 2022.
[3] J. Barbier, F. Krzakala, N. Macris, I.. Miolane, and I.. Zdeborová. Optimal errors and phase transitions high-dimensionall generalized linear models. Proceedings of the National Academy of Sciences, 116(12)5451-5466 2019.
[4] M. Bayati and Montanari. The dynamics of message passing on dense graphs, with appli- cations to compressed sensing. IEEE Transactions on Information Theory, 57(2):764-785, 2011.
[5] M. Bayati and A. Montanari. The lasso risk for gaussian matrices. IEEE Transactions on Information Theory, 5894)71997-2017, 2011.
[6] I.. Bossard, M. Guillaumin, and L.. Van Gool. Food-101 - mining discriminative components with random forests. European Conference on Computer Vision, 2014.
[7] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. S. Liang. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32, 2019.
[8] Y. Chen, C. Wei, A. Kumar, and T. Ma. Self-training avoids using spurious features under domain shift. Advances in Neural Information Processing Systems, 13:21061-21171, 2020.
[9] R. Das, I. S. Dhillon, A. Epasto, A. Javanmard, J. Mao, V. Mirrokni, S. Sanghavi, and P. Zhong. Retraining with predicted hard labels provably increases model accuracy. In International Conference on Machine Learning. PMLR, 2025.
[10] R. Das and S. Sanghavi. Understanding self-distillation in the presence of label noise. In International Conference on Machine Learning, pages 7102-7140. PMIR, 2023.
[11] B. Dong, J. Hou, Y. Lu, and 7. Zhang. Distillation early stopping? harvesting dark knowledge utilizing anisotropic information retrieval for overparameterized neural network. arXiv preprint 2019.
[12] D. L. Donoho, A. Javanmard, and A. Montanari. fiormation-thhoreticalll optimal com- pressed sensing via spatial coupling and approximate message passing. IEEE transactions information theory, 59(11): 59(11):7434-744
2013.
[13] D. L. Donoho, A. Malcki, and A. Montanari. Message-passine algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45):18914-1811) 2009.
[14] O. Y. Feng. R. Venkataramanan. C. Rush, R. J. Samworth, et al. A unifying tutorial on approximate message passing. Foundations and Trends@ in Machine Learning, 15(4):335-536 2022.
[15] Furlanello, Z. Lipton, M. Tschannen, L. Itti,, and A. Anandkumar, Born again neural networks. In International Conference Machine Learning, pages 1607-1616. PMLR, 2018.
[16] A. Goel, Jiao, and Massiah. Pars: Pseudo-lahel aware robust sample selection for learning with noisy labels. arXiv preprint arXiv:2201. 2022.

---

[17] J. Han, P. Luo, and X. Wang. Deep self-learning from noisy labels. In Proceedings of the IEEE/CVF international conference on computer vision, pages 5138-5147 2019.
[18] A. Javanmard and A. Montanari. State evolution for general approximate message passing algorithms, with applications to spatial coupling. Information and Inference: Journal the IMA, 252):115-14,, 2013.
[19] Y. Kabashima, F. Krzakala, M. Mézard, A. Sakata, and L. Zdeborová. Phase transitions and sample complexity in bayes-optimal matrix factorization. IEEE Transactions on information theory, 62(7))4228-42666 2016.
[20] M. Kendall, A. Stuart, and J. Ord. Vol. 1: Distribution theory. London [etc.]: Arnold [etc.]. 1994.
[21] A. Kumar, T. Ma, and Liang. Understanding self-training for gradual domain adaptation. In International conference muchine learning, pages 5468-5479, PMLR, 2020.
[22] A. Kumar, A. Raghunathan, R. Jones, Ma, and P. Liang. Fine-tuning can distort pretrained features and underperform dittr---iitiiittnnnn. arXiv preprint arXiv:2202.10054 2022.
[23] D.-H. Lee al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896. Atlanta, 2013.
[24] J. Li, R. Socher, and S. C. Hoi. Dividemix: Learning with noisy labels as semi-supervised learning. arXiv preprint arXiv:2002.07394 2020.
[25] Y. Li, J. Yang, Y. Song, L. Cao, Luo, and L.-J. Li. Learning from noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer Vision, pages 1910-1918, 2017.
[26] H. Mobahi, M. Farajtabar, and P. Bartlett. Self-distillation amplifies regularization in hilbert space. Advances in Neural Information Processing Systems, 33:3351-3361, 2020.
[27] M. Mondelli and R. Venkataramanan. Approximate message passing with spectral initialization for generalized linear models. In International Conference on Artificial Intelligence and Statistics, pages 397-405. PMLR, 2021.
[28] A. Montanari, Y. Eldar, and G. Kutyniok. Graphical models concepts in compressed sensing. Compressed Sensing, pages 394-438, 2012.
[29] A. Montanari and R. Venkataramanan. Estimation of low-rank matrices via approximate message passing. The Annals of Statistics, 49(1), 2021.
[30] D. T. Nguyen, C. K. Mummadi, T. N. Ngo. T. H. P. Nguyen, L. Beggel, and T. Brox. Self: Learning to filter noisy labels with self-ensembling. arXiv preprint arX1v:1910.01842 2019.
[31] S. Oymak and T. C. Gulcu. Statistical and algorithmic insights for semi-supervised learning with self-training. arXiv preprint arXiv:2006. /006, 2020.
[32] D. Pareck, S. S. Du, and S. Oh. Understanding the gains from repeated self-distillation. Advances in Neural Information Processing Systems, 37:7759-7796. 2024.
[33] A. Perry, A. S. Wein, A. S. Bandeira, and A. Moitra. dessaage-passing algorithms for synchro- nization problems over compact groups. Communications on Pure and Applied Mathematics, 71(11):2275-2322 2018.
[34] A. Raghunathan, S. M. Xie, F. Yang. J. Duchi, and P. Liang. Understanding and mitigating the tradcoff between robustness and accuracy. arXiv preprint arXiv:2002.10716. 2020.
[35] S. Rangan. Generalized approximate message passing for estimation with random linear mixing. In 201 IEEE International Symposium on Information Theory Proceedings, pages 2168-2172. IEEE, 2011.
12

---

[36] S. Rangan and A. K. Fletcher. Iterative estimation of constrained rank-one matrices in noise. In 2012 IEEE international symposuumm on information theory proceedings, pages 1246-1250. IEFE, 2012.
[37] S. Reed, H. Lee, D. Anguelov, C. Szegedy, D. Erhan, and A. Rabinovich. Training deep neural networks on noisy labels with bootstrapping. arXiv preprint arXiv:1412.6596 2014.
[38] H. Scudder. Probability of error of some adaptive pattem-recognition machines. IEEE Transac- fions on Information Theory, 11(3):63-333 371, 1965.
[39] K. Takanami, T. Takahashi, and A. Sakata. The effect of optimal self-distillation in noisy gaussian mixture model. arXiv preprint arXiv:2501. 2025.
[40] D. Tanaka, D. Ikami, T. Yamasaki, and K. Aizawa. Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5552-5560, 2018
[41] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self- self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622, 2020.
[42] J. Yang, R. Shi, D. Wei, Z. Liu, L. Zhao, B. Ke, H. Pfister, and B. Ni. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data, 10(1):41, 2023.
[43] D. Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd anmual meeting of the association for computational linguisties, pages 189-196, 1995.
[44] Zhang, M. Wang, S. Liu, P.-Y. Chen, and Xiong. How does unlabeled data improve generalization in self-nraining? a one-hidden-layer theoretical analysis. arXiv preprint arXiv:2201.08514, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Theoretical claims are in Sections 3 and 4. Experiments are in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please see the second paragraph of Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

All proof' are in the appendix and we have mentioned in the main paper where each proof the appendix. All assumptions are clearly stated the main paper.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
Experimental details are in Appendix N.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [No]
Justification: All our datasets are publicly available (links provided the paper). We have provided experimental details in Appendix N to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https:
ssi agionPoicyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Provided in Appendix N. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are averaged over 3 runs and we have reported the means and standard deviations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Appendix N.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https http://neurppppe wwt.rripp.ccpppuuuee httpp//////...ccccccueeeeee.ieee
Answer: [Yes]
Justification:
We have abided by it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our work is primarily theoretical and we do not foresee any direct societal impacts of our work. we did not discuss this in the paper.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There are no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have done it wherever it was relevant.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets have been released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not have any such experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Not relevant to this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs not involved in the core research of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https /tapps////eupps.../// /0tp//////ooeeeeeee//////////// for what should or should not be described.
20

---

Appendix
A Related Work on Approximate Message Passing
Approximate message passing (AMP) refers to a class of iterative algorithms derived through approximation of belief propagation dense factor graphs [4, 28]. AMP algorithms were first proposed for estimation in linear models [13], and for GLMs [35, 18). AMP has since been applied to wide range of high-dimensional statistical estimation problems including Lasso and M-estimators [5], low rank matrix estimation [36, 19, 29], and group synchronization [33], among others. AMP algorithms come with many appealing properties. They can easily be tailored take advantage of prior information on the structure of the signal, such as sparsity or other constraints. In addition, under suitable assumptions on the data matrix, AMP theory provides precise asymptotic characterization of the behavior of the estimator (despite the randomness of data) in the high dimensional regime constant. Even more, for
where the ratio of the number of observations dimensions converges wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms (see e.g. [12, 3, 29D. We refer to [14] for survey on AMP algorithms. In this work, we use the machinery of AMP algorithms to rigorously understand the effect of retraining model on its predicted labels over multiple rounds.
B Proof of Theorem 3.1
To build some intuition on the statement of the theorem and the choice of memory correction terms, we analyze the distribution of the first few estimate of the AMP updates in (4)-(5).
Since (o 77 T. we have C = and 0 --_-' T. Under the GMM, we have X = yp T Z with
Vn
Zi N(O, 1), independently. Fixing y. we have that and Z are independent. We write
0 1
X
Vn
(nyT
TTT
Vn
y
T
(30)
Vn
By law of large number, yig P, (1 11-22) 2p). Also under Assumption 1, a and the empirical distribution of Vdyu converges weakly to distribution of M UM- Therefore the first term in the decomposition (30) converges to (1 2p) w/ Given that y and are independent, thee second term distributed N(O, 1). This implies that the empirical distribution of 0* converges weakly
/ (1 2p) + G. with G N(0, This implies the claim of the theorem for 1, with mi = (1 /p/ and 01 1.
We next characterize the distribution of g' Va _ d which also sheds light on the choice of correction term n. y. We have
d 2² xx
- n
n
(ypT (TY 2 -
d n
n
[1mu?,, "vvv T
Z
+ y TT 22 "
-
n
n
y
11 Z
y
zz
7
Z 4
y 7
(31)
21

---

By law of large number and recalling Assumption 1, we have liat 2'u 3 (1-2p)>². Also given that Z and y are independent, σ vn N(0, J.). Since | - 7, which is of order one, we have + T z ÿ converges to zero.
The remaining terms in (31) can be written as A == n In + 2uy') )ÿ. Note that the term E(ZZ' /m) = (d/n) and so A is zero mean. (This also justifies the choice of correction term D.) In addition, by virtue of the central limit theorem, each entry A, is approximately normal with variance a² + (1 2 This implies that the empirical distribution of entries y' converges to my Y + GG with
my = >² 2p), aa= + 7
The proof of Theorem 3.1 follows by adapting techniques from standard AMP analysis (see e.g., [18, 29, 14J), and so omitted here. A major step in the proof to characterize the conditional distribution of 0',y² given the previous iterates (0", ,y" yy")r<t, and then show that the 'non-Gaussian components' thereof are asymptotically canceled out by the memory correction terms. A technical challenge though is that in the AMP theory the initialization should be independent from the random matrix X. Here the initial estimator 0¹ X T // v which depends on X. The trick is to consider the AMP updates, starting from t = O with 0 = O and g-1(;.) O. This way, the initialization is independent of X and by update rule (4)-(5 we have 3 = 0 and with gi (y. T) = T we get 0² x DVDVV so we will be on the trajectory of the updates.
To derive the limit of (0), we first note that the functions (2x y) = xy and (1x y) = x² are pseudo-Lipschit (of order 2). Therefore, using (9), the following limits hold almost surely,
lim n-000 d
1 lim
d Σ (())) mh ( M (
[[T ( = m + +o?
12 n0
d 1=
d Σ (Vānn (
[{(T M 0 M mh E[M M 7
lim vd
11 T
lim
d F=
where we used the identity F[M*] ? (second bullet point in Assumption 1). Hence, by using (7), we obtain
lim (0) lim 4b 1 To
(-
1 To 0'
(
m
lim n1-000
n1-00
1011e
011,2
m of
where the second equality is by continuity of d.
C Proof of Theorem 3.2
Our derivation prior to the statement of Theorem 3.2 showed that the optimal aggregator o is given by any scaling of 2q: 1; we will set the scaling to I so that the output of o [.. By Bayes' rule, we have
q: (v. T- = P(Y 1 1/m Y G.G y. Y= -))
P G y-mi 8= = Y =1) 1)
P G = y Muy 8 =
P P
y-ū y = g = -Y 1) o,
PP
G
R-e De
y
Y = 1)I((Y 1) + P G y+m
y = Y = -1)
at
P G== = yー P ( = 11)
P
G
m,
P
(P = गy Y 1) 1) = 1) + P G =
yo
P(PV=j) = T -1)P(Y -1)
oe
(32)
Under our noise model, we have
123 1-8 P(Ý - = 1) = (1 (1-p) p) 2 p
and P(Ý - BY -1) (1-p)
1-3 145
2 pp 2
(33)
22

---

Also, G ~ 1) and P(Y = 1) n and P(Y = -1) TT.. By substituting in (32) we get
(y 1
()v.))-
(1-p) -
T
1-1 [u-ma)²
1 0
(1 - p) 2 p 29
+ (1 (1-p)
2 2
22
(34)
1 1-p
By invoking (13), we have
m
72 al
+ 1)
mz +1
which by plugging into (32) gives the desired result.
Next by Equation (10) we have
Po(O') 24 $
1/1
For the sequence (71))11, note that by (12), we have
m 72 Mh.1 oi11 a
Elg) + G.G.
which gives the result after substituting for my and o from (13). Also from Theorem 3.1, we have M m1/01 >11 2a. This concludes the proof of theorem.
D Proof of Proposition 3.3
We start by proving the monotonicity of F (1). Since = a. is increasing in u suffices to I+u show that ()) )) is non-decreasing in n. Recall that ğ is the Bayes optimal estimator and also be characterized as g(Ý, P) [[[|] Tf /TG Y] (see derivation 32). Hence,
E[Yğ(Ý, F)] EÝ; 2) and we can write
R(7) E( g(
((o F))
So we need show that R(1) decreasing r7.
Next note that by Bayes-optimality of we have R( inf, E[(Y g(Ý, 8))2 where the infimum with respect to all measurable functions g, and Y n VTG. Now take in 772. The following
holds in distribution:
Th (Tp
q Z in
Y V
72
772
where G, 2 N(O, 1) independent of each other. We then write
R( f E[(Y -(m VnG,
E E
[ o tu
(7pY+ VT2)
7
(35)
where the inner expectation is conditional on 2 and the outer expectation is with respect to Z. For fixed z, define the function
h (v. 7) -
71
2.7
23

---

Continuing from (35) we get
R(h)= [())=E[[(xx--- h2s (12
+ VT2G, P)) '1 2 inf [(x - gl(na vaaG P I
9
= =(
where the inequality holds since hg is measurable function. This completes the proof of the non- decreasing nature of F.
To prove the claim about fixed points (i), consider the function H(u) F(u.... We have F(0) -- [[) 8)²]> > 0 and so (0) < 0. Also, lim F(u) 22 E[ō(>2Y 7, 8)3] z. Hence, oo (u)) oo and by the intermediate value theorem, H(u) has at least zero which corresponds to a fixed point of F.
Let v/ be the smallest fixed point of F (and so ((i = =0). Then, for any < The we have (1)) < 0 and 1/2 F(n²2. This implies that if 7 1),,, then n/ F(n) 7/. Further, by monotonicity of F, per item (i), if vf s 1 then n/41 F( s F (1(+1) 7/+22 which proves that the sequence (nd)=1 is monotone non-decreasing. Hence, the first step strictly reduces the test error and the next rounds of retraining do not increase the test error.
We next proceed with (ii). By the argument in (i). if m F(r) then the sequence (n: will be non-decreasing. To this end, we derive lower bound on F, such that F(u) F(u), Vu and establish condition on the label flipping probability p. so that of F(r) with 7/1
- 2p).
Va
To construct F, recall that ğ is the Bayes-optimal aggregator given by g(Y, V) F[Y] n VGG, JJ. Using the Cauchy-Schwarz inequality for all g.
E[E[Y|Ý, Fla P E[g(Y, 1y?]
E[Yg(Ý, ,Y)
E {1)))
E[g(Ý, F)2]
with being the function for which the equality occurs. By choosing, g(²; F) sign((), we obtain the following lower bound:
E[ghT
+ /iG)] E[sign (iogn((+++0)) [/G)))
since Y (11,+11 is independent of G N(O, 1). This gives the following lower bound on F(u),
F(u) 2
u
Itu G.P)
Y +
a
1 u
2
E sign {22
"V 1+u c))===((w))
1+u
We further simplify F(u) as
2
2
2
F(u) = 1 1-2P
(1-2p
20-(Pp G -7V 1+
1 24 - -7V
a
1+
For m/ Va
(1 3/(11 (1-2p), the condition / (( is equivalent to
72 101-20 (p1)
p +
(36)
1 + 1/
VV++ 72 2
24

---

We next show that there is a unique p. é (0, 1/2) for which the above inequality becomes equality. Define the function k(p)) +b
(1-2p)
2 (1-2p)3 p. The first two derivatives are given by
(2(1-pp)
27²a
(V())= 0
Va+ 72
7a+ (2p))2)///
(1p))pp)
27 - 2p)
(11
12 - 2p) (a + 72 -2p)2)
(p) o
+Ø
+a+ /0+
(a 7( 22p)232
(11+
(p))
6
=
1+
V 02 2p)
(a+ -2p) 2)²
Va + ?
We have (((2) neighborhood before 1/2. Since h(0) > O, there should be root p. for h in (0, 22 Therefore, h has least two zeros, p. and 1.2 Also note that is convex function because h²(p)) > 0, and therefore, these are the only two zeros of h. These properties give clear picture of the function h: it will be positive on [0. p.), negative on (p+: 2) and positive afterward. Hence, condition (36), i.e., h(p) s
23 va (0) 1-
-1
2 11 O. Also h(5)) 0, so h should be negative in
7 a/aa
holds if p [p.. 2) which completes the proof.
E Simulations to Verify the Theory in Section 3
In Figure 2, we compare the performance of different retraining methods on synthetic data, generated from a GMM model. The mean vector is generated by drawing its entries from N(0, 1) indepen- dently, and then normalize it to have || e, = 7. The two plots in Figure correspond to different values of label noise p and In both plots, we set the sample size to n 1000, d = na = 800 and the class probabilities π. 0.3 and π._ 0.7. The results are averages over 10 realizations of the setting.
The Opt-AMP is the algorithm based AMP updates (4)-(5), with the optimal aggregator function (14). Vanilla is the linear classifier (3) without retraining, so its performance does not vary by iteration, and its represented by a flat line. SE is the theoretical curve based on the state evolution recursion, FT and CT respectively denote the full-retraining and the consensus- -based retraining without the memory correction terms. (Note that the memory corrections are not well-defined in these cases since the aggregators are not Lipschitz and not differentiable everywhere.) From these plots, we see that there is great match between SE predictions and the simulated data point (Opt-AMP), We also observe the superiority of Opt-AMP over other retraining methods as well as the vanilla estimator.
In Figures 3 and 4, we compare Opt-AMP with some 'approximate" versions of full-retraining and consensus-based retraining. Recall that the aggregator functions in these cases are given by ge (y. 77 syg and 9e 77 71 0). Since the aggregators are not Lipschitz, the result of Theorem 3.1 (validity of state evolution) does not apply. Even the correction terms are well-defined. We instead approximate these aggregators as follows:
FT 9:
(y. 1)
1+ 1, gr (V. R
CT
T
(37)
1+e
For fixed B > 0 these functions are Lipschitz and hence the state evolution will predict the limiting behavior. As 3 grows these approximations become tighter. We refer to Appendix F for derivation of curves as 3 + oo and further comparison between full retraining and massensus-based retraining.
As the state evolution curves indicate, Opt-AMP outperforms the other rules significantly. Also, as we observe in Figure 3a, for the chosen parameters, the error of full retraining increases across iteration, indicating that sometime the retraining may hurt the performance.
F Comparison of Full Retraining and basse Retraining
As discussed after Theorem 3.2, the AMP theory requires the aggregator function to Lipschitz. For both, the full-retraining (ge 7) sign(y)) and the consensus-based retraining (g. ()
25

---

0.35
0.29
0.285
DpLAMP
0.3
OpLAMP
0.28
Vanila
Vanilla
test testenor
0.25
CT
test
0.2
0.27
0.265
0.15
0.26
0.2
0.255
Iteratioo
Iteration
(a) p= 0.4, 7y 1.5
(b) p= 0.2, y
Figure 2: Synthetic Experiments: Comparison between different retraining methods. FT and CT respectively denote the full-retraining and the consensus- based retraining without the memory correction terms. Vanilla is the estimator without any retraining. Here n 1000, d = 800, n. 0.3, т 0.7. Dots are the Opt-AMP algorithm and the solid black curve the state evolution.
0.45
0.15
OptAMP
dml
(=100
tast error
test enor
0.13
0.35
Opt-NMP
0.12
0e100
0.11
0.25
0.1
2
8
10
0
6
10
iteration
(a) p= 0.2, =
(b) 0.2, y 1.5
for Opt-AMP and the 'approximate" full retraining with the memory correction terms. As /3 grows the approximation full retraining becomes tighter. Here a 0.8, n. 0.3, T- = 0.7.
Figure State evolution
0.29
0.15
OptAMP
3=10
0.14
G-10
0.28
3-100
(m100
Seec
test ener
0.275
tast tast emor
0.13
0.27
0.12
0.265
0.255
0.1
2
6
0
10
iteration
Iteratioo
(a) p 0.2, y=1
(b) = 0.2, 7 1.5
Figure 4: State evolution training the memory correction terms. grows the approximation full retraining becomes tighter. Here a 0.8, n, 0.3, æ = 0.7.
for Opt-AMP and the 'approximate' consensus-basse
(vō 0)) the aggregator functions violate this assumption. As we discussed for Figures and we approximate the aggregator functions by Lipschitz functions given below:
9. FT (v.T) R 1 1,
9t
CT (v.T)
x
I T Puy
T
(38)
26

---

0.8
0.8
0.5
0.6
Pouter
0.5
Fouty!
Frcte's Poute!
Xr Ferl
Tyste?
0.2
02
0.2
0
(a)
0.2,
(b) 0.25,
(c) 0.3.
crossover 1/² 4.32.
crossover 17² 1.54.
crossover
1) 0.75.
Figure 5: The AMP update mappings for optimal aggregator, full-retraining and consensus- based retraining. Here, y= 1.5, = 0.3, = 0.7.
For these functions, we can run the AMP iterates (the memory correction terms are well defined and also derive the state evolution recursion predict the asymptotic behavior of estimates across iteration. We can then take the limit of that the order fo limits are important; we take the limit + oo after taking the limit n, co. The state evolution curves for several values of are plotted in Figures 3-4. Here, we derive the state cvolution curves for 3 + co.
to make this approximation tight. It is worth noting
Full retraining: Consider the state evolution (8) with of (v.T). For fixed i, taking 3 - results in the following update:
my = rV/mm, of = a(m; + of), Mi++
2
E(sinn (m, Y o,G)Y), 0+1
Va
Md Defining 7/: = a,
)² and
ma
the above recursion can be simplified to
2
(39)
m +
2 E(Y sign G)}2
1/
(40)
a
with initialization v/ = 711 2p)/va.
Since Y E +11,+1) independent of G N(O, 1), have
- E(YiignVVie G)) E(sign( /h= G)) 2P(-2 - - 1.
So the state evolution can be simplified as:
2
Me
7
2Φ
Th VI + T
3-11
(41)
Consensus-based retraining: Consider the state evolution (8) with CT (v, V). For fixed f, taking results in the following update:
me Tamm, of amm o?), > ca (m, +o,G)> 0))
j. (P
M,+1 Va
Defining i/= = ( m )² and m) = my the above recursion can be simplified to
a.
1/p +11
(42)
2 ELYP 0))²
(43)
E(1 +G))> 0)
27

---

with initialization ?) = =>(1- - (o(1-pp)/vo 2p)/va.
Let A = YÝ. Then P(A = 1) = 1 and P(A = -1) = Since G ~ N(O, 1) is independent of
Y, P, we have
(FTT((((V+++))) 0)) - E[AN(VTAA+>>))
=E(AR(
= () (-v
= --p+0(VVi (V)
We also have
E{1(Y (EL(YVVYYYo G)) 0} EIPPAVT G 0)}
=E(P(AV))) =LL-D)&(V + (p
=p+ (1+(22)))
Substituting these terms in (43), the state evolution reads:
it 72 17 ni +
x² (o(vTT) p)2
Me+1 p (1-2p) 1 vT)))
These derivations also provide valuable insight into full-retrane full-retraining and consensus-based retraining. We denote by FFT, FCT, and Föpt the AMP update mappings for full-retraining, consensus- baaseed retraining, and the Bayes-optimal aggregator, respectively. For example, the state evolution for full- retraining is given by 'h4-1 FPT (h) with FFT given by (41). In Figure 5, we plot these functions for different values of As we see, Fops is uniformly larger than the other two mappings, and so the corresponding state evolution sequence is uniformly larger than that of the other two aggregators. Recall that the test error of 0² decreases as T/ increases, and hence the optimal aggregator performs better than the other two, at every iteration, For FFT and FCT, there is a crossover point: before this, FcT(1²) > FFT(1")) and after it, (n" (rr()²) This is intuitive, because small r means that the current model quality is poor, so the consensus- based aggregator, which takes into account the noisy labels, works better. However, larger 1) means that the model quality is good enough that full-retraining, which ignores the noisy labels, works better. Furthermore, the crossover point depends on p: it increases as p decreases. This is also intuitive, because smaller p gives a larger range of n where considering noisy labels in the retraining step is beneficial.
G Proof of Lemma 4.1
For test data point (x, y), we have T sign(x and P(y +1|#) h(xTT)) We let z /nx O and z2 vnx= B. We have
P. P0) = P(yō 0)
P(zo > 0,y -1)+ + P(z0 <0,y=1) 1)
= [Pg[P(z0 > 0,y - 1|=0) + +P(z0 < 0, 1|z;)]
We continue by calculating (P > 0,y = - 1 Conditional on zg, and are independent. Therefore,
P(zo 0, - 1|20) = P P(==))
|00
We have (2) N(O,
). Hence.
BT0
||
BT
0)
= ~ N(a, b),
zB.
8² 101
| &
1/1
28

---

Using this characterization, we get
P(ze > 0/2Ø) =0(7)) 00 p 2/
v1 p² 13lez
Also under our data generative model, P(y = 1-=--1pp -1|=g) h/zz// Vn). Note that zg N(O, 1,31(,,)
and 1/3 Vn
Var, in probability. Hence, by Slutsky's theorem,
pZ
P(ze 0, -1|2g) + &b
(1 (1-b(Vay2))
(VI-
distribution with Z N(O, 1). By similar argument, we have
P(ze < 0, = 1|20) - +b -pZ h(Vanz).
Adding the previous two equations, we obtain the desired result.
We next show that F is decreasing. Using the relation $ (xx)) can write F(p) as:
pZ
F(D) F h(Van?) Φ
(1 - 22 222(VV021))
/1 1 p2
Hence,
F()) (1 32)3 E Zó
pZ
(1 (1- 22 (1-2h(Va72))
v1
p²
with ((u) = c 12 12/ /T. For any 2 > 0, we have
(1 - 2h((Vaa2)) 20
-p2
(1 (1-2h(-vara))
(11 11-11
2z
pz
(1((- (l((-Vayz) 11( (((v))=)) <0,
(44)
V1-p²
since 2 and by assumption h(u) > h(-u) for all 0. Also, since the Gaussian density is symmetric, (44) implies that (p) < O, which completes the proof.
H Proof of Theorem 4.2
Similar to the proof of Theorem 3.1, we build some intuition by analyzing the behavior of the first few estimate of AMP updates.
Since go 77 = T. we have C. 0 and B Ja X Recall that under GLM setting the entries of X are i.i. gaussian. Therefore, analyze the distribution of 31, use the rotation invariance
of Gaussian distribution, and without loss of generality we take , [|3]| e. ej We then have PP
(xx(1)
1/x) (1 .1). Also, B
where used the decomposition X
[1xx() X_1]
X
Note that ÿ and X_1 are independent since B= = ||B]e, ej. Hence, X_ ~ I4-1, given that the entries of X_1 are i.i drawn from N(0,1/n).
- For the first entry, we write (1) 20/ V where zn ~ N(O, Then (x(1), 7 /n (zo: 7). Note that the variables 20, are i.i.d and
# E7
E Zo 24 /o>Zo) - 1)]
2E Zohn [ (Van
with Zo ~ N(O, 1). Also o² := Varl 1- 4 Zohn (V772( By the central limit theorem, (())(), D VTiu) converges in distribution N(O, o²). Writing it differently, (e1, - 4p
V
29

---

converges in distribution to N(0, with e, = (1,0, R In addition, by Assumption 2, vi 1 and the the empirical distribution of the entries of B3 converges weakly to 3 7g. This 181, Vary
implies that the empirical distribution of entries of 3 converges in distribution to Jay 3 G with
G N(O, 1) independent of 3, which verifies the claim the theorem for t with
11
Van Vay F Zo [VarZo)]= (
E [[)) ar2
2
01 01 Va,
(45)
with Z ~ N(O, ar?).
The formal proof largely follows from the analysis of generalized AMP (GAMP) algorithm [35], which given an initial estimate 3 iteratively produces estimates B and y of B and x as follows:
dg: (vi.
B+d x ge 0) Cifi(B")
Ct Σ
11 dy
B, Σ 0f 1-1 dy
ydr - X3 - Bigilv' 1
(B))
where ge R² and fe IR IR are Lipschitz in their first argument. Suppose that
| BT
...
3 1|
With Σ the state evolution parameters dr R, o R20, E' R2x2 are recursively defined by
Pe+1 = E(O,g: (2))), = E,,((,,,
(46)
aB(3²)
a or- G++1)
r-1 [aE (Mer + +O+1GGG Gr+))
(47)
a1E(Sr- (pr.1 oo.1 Gr+1)) )2)
where Z, N(O, E,), and Y = (Z) {-1,+1} with P( 1|2) (Z). In addition.
Ge11 N(O, 1) independent of B nz.
Similar to [27, Proposition 3.1], Stein's lemma can be used to further simplify the state evolution. Define
Σg P2,
(Ei,2)
Z
Σ2,2
(48)
Σ
Σi,1
and let Z, uz + o with G N(O, 1) independent of Z. Then, the state evolution can be characterized by the sequence (41,0)))20 with
[(Z 2, Y [() 90 2(22.))..
P++1 E
=( 8)3).
(49)
Var Z.)
It is proved that the state evolution recursion precisely characterize the asymptotic behavior of the GAMP update as stated in the next theorem. We refer [35] or [14] for formal proof.
Theorem H.1 Let (3 y'))en be the AMP iterates given by (17)-(18), Also let (Mt, aee 02) be the state evolution recursions given by (22). Then, for any pseudo-Lipschitz, function R² + the following holds almost surely for 0:
lim
Σ
1=1
Σ ((A.))) - - =(,(
lim -000
where G ~ N(O.1) 1) and B Ty independently.
30

---

A challenge in applying Theorem H.1 is that it requires the initialization to be independent of the random matrix X, property that does not hold for 3 -x"3 y. The trick is that we consider the AMP updates, starting from / = 0 with initialization 3 = 0 and g-1(--) ) O, so the initialization is independent of X. By the update rules, we get 3d = 0 and 3 X T.. if we define go (y, V) T (and so Cu = 0). In other words, the next iteration we get our previous initialization. This way we can apply Theorem H.1. Note that
1
| 30
B B
a 2 0
0
62
Σ
0
B
||
71
From (48), we have μz,00
0z.0 0 and so by (49), we get
E( Y) E()
μ E
(Z. P))
Var 2o)
[(Z
= E
P) E(P2)
ay?
an2
2
0n (2) - -))
E( E(Zh,
where we used the fact that Zu- 0 in this case (since μzzu σN.0 0) and (o = T. In addition, of = E(go F)2) = 1. This is consistent with (45) where we applied the change variable Vao, Jr.
Next to obtain the state evolution recursion for t 1, we recall the construction of Σ' from (47), and take fo to be the identity functions, by which we obtain
ar² aamnn
aj4? al1?9² + oj)
Σ
(50)
By invoking (48), we have
aj4? an2 Pr. 02 a(p??² + +0,) (atle72)2
Pz.
ao
ar2
Hence, in the state evolution (49), we have Ze u + foo,G with Z ~ N(O, 2n This results in (20) after the change of variable Vao, ot, and so Theorem 4.2 follows from the result of Theorem H.
We next derive the limit of P. (0). As we showed in the proof of Theorem 3.1, functions (a y) = zy and (xx y) x are pseudo-Lipschite (of order 2). Therefore, using (23), the following limits hold almost surely,
lim
1 d
|091
82
lim 1
d
Σ ((8)) F
[m1.
- G Va
21
ph
2
[[
2
2
o
lim
|/312
lim
Σ (33) = [[
1=4000 d
oo
d 1=1
_ BTB n
lim
3
lim 10
Σ E
[[33]
d
Va
1=1
where we used the identity E[32] 7² (second bullet point in Assumption 2). Therefore, defining p² = 33131(111)) (1
we have
lim Pt n 00
NV W
2+
a
Next by Lemma 4.1 and continuity of function F, we have
lim Pe()) lim F(p:) = F lim pt) F
1/2222
which concludes the proof.
31

---

I Proof of Theorem 4.3
The proof follows from (25) and an explicit derivation of [(Z)Z, P). By Bayes rule,
P(Z = 21, Y = =
P(Z - 2|2, 2r, P 77)
P(Z Z4, V
7 2) 2)d2
00
20
h1(2) 1/ (1 hp(()) 1/2
Z002
2
00
(2t m(e
20
hp(2) # (1 hn(z)) :
200 de
22
2
Therefore,
(u-mee)²
EZ P)
2e
201
(x)2) 2 (1- hip())))))))))))))))))) 2 200 dz
(51)
(M-
207
(x) (1 h2(2))
11
18
207 dz
which after substituting in (25), results in
ge (u, (),
Mi
00
ze
fu m22)
201
hp(2)
112 (1 - hpp(2))
1
22 2nn2
d2
Mt
(52)
an?
L_ e
(u-pe))
20?
118 (z) 2 - (2))
1.
2
200
22
dz
of
In addition, using the characterization of of in (25), the state evolution (22) can be written
2
[[),;(Z), oi=Va,
141
an
Pt+1 Elgi ,,G, oi.1 = appe-
(53)
with 2 ~ N(O,N(O,))) 27)²) and G ~ N(0,1) independent of each other. In addition, Y e (-1,+1} with P(P 1[2)= hip (2), and g0 (:7) T.
We next note that by Equation 24, the test error depends on it = pe/o We proceed by writing the By substituting for pe-1 anje, and
state evolution (53) terms of 7/-- Note Mh-1
Meal
PioT
d+ll
Te = aaful 077 we arrive
1
2 (on) P m 03/2g²
F [[)),())]
The optimal aggregator (52) can also be written in terms of 17c as
gi (u. = aayz + 1/2
L ze 2m n)=)²
h1p
1477 (1 h
Ran
dz
u
( =)²²
h2(2) 1 h (2)
1 247
dz
00
12 us h
_
+ (1 h (z) 1/2 207 de
+ m
ary
[ e
22
118 (1 h (z)) 13 2प dz (x)
Finally, replacing u by gives us the desired result.
J Special Case: Sign Link Function
In this section, we specialize the result of Theorem 4.3 to sign link function namely l(z)) 1+sigu(=) In this case y sign(x' (x T (3).
32

---

0.4
0.38
OpEAMP
testerror
0.36
SE
CT
0.34
0.32
0.3
2
8
10
0.5
1.5
iteration
(b) Cobweb plot state evo- lution (56) GLM setting
(a) p 0.2, 7 10K, d 5K
Figure 6: Synthetic Experiments: (a) Comparison between different retraining methods under GLM setting with link function h(z) (1 Sigu()))/2 FT and CT respectively denote the full-retraining and the consensus- based retraining without the memory correction terms. Vanilla is the estimator without any retraining. (b) Cobweb plot for the state evolution mapping in
(56).
Proposition J.1 Under the GLM setting with h(2) the AMP procedure are given by:
1+sign(s)
the optimal aggregator functions in
(1 2p)
(u, 17
(54)
1 (1 211-pp) 1)
for 2 1, and 9o(--)) ((.0))=0 T. where ot state evolution recursion:
(2) )-² and the sequence (m))21 is given by the following
1 2p
(55)
a
Thot
2
Egge (onj on 8,,)),
(56)
with N(0, a) and N(O, 1) independent of each other, In addition, P e (-1,+1} with P(У = 2iggsn
For the estimators 3r given by the AMP updates (17)-(18), with the optimal aggregator function (54). the following holds almost surely
lim Pa( 10000
1
cos-1
1/t
(57)
1/2
2
Figure 6a compares various retraining methods synthetic GLM data, with drawn from N(O, 1), n = 1000, d = 500, and label flip probability 0.2. Results are averaged over 10 runs.
Opt-AMP uses AMP updates with the optimal aggregator. Vanilla is linear classifier without retraining, shown as a flat line. SE is the thcoretical state evolution curve. FT and CT are full- retraining and consensus-breg baseed retraining methods without memory corrections, which are undefined here due to non-Lipschinn SE predictions and Opt-AMP, and demonstrate the superior performance of Opt-AMP over other methods and the vanilla estimator.
non-differentiable aggregators. The plots show close agreement between
In Figure 6b, we plot the cobweb plot for the state evolution (55)-(56). As we see the state evolution map is increasing and has at least one fixed point. Further, similar to GMM setting, when yjI small (the initial model is poor), retraining helps improve its performance. However, if is large (above the fixed point) and so the initial estimator already good enough, then retraining can actually hurt its performance.
33

---

J.1 Proof of Proposition J.1
Consider the GLM setting with ft)=== 1tsign(=) In this case, hp(2)= = 1-20 sigu( 2). Also, note 2
that the data generative process does not depend Y (recall that | /d 72), since the sign function is invariant to scaling. Hence, for simplicity we take y= 1.
Before proceeding with this case, we derive an alternative expression for the optimal aggregator functions. We define the shorthand s/ ( + - and m, = Also let f(z) (2)2) تt (1
(=)) '." where the explicit dependence on the parameters p and is omitted in the notation for
simplicity. The function of given by (54) can be written terms of this notation as
(m-mp)
1 ]]((=ee o (u.
dz
of [S())e
[a-m,
de a
Let Z, m S with Z N(O, 1). Then,
ge (u. 1 E[Z)((Z)] u
of E[f(Z.) a
1 IF [mm 8,7)5( 8t
22
E[f(m: + s(Z)]
1 E[s:Zf(me + s
87 a
27 E[f(me 8zZ)]
E[Z[(m= st7)]
(58)
8t
E[f(m:+ + s(Z)]
For the case of sign link function, where h(2) 1+sign(=) 2
tte function f(z) can be written as
140 3" (1 h2(2))
1-6 2
1
1- 2p
sign (ūz).
2
Using this expression in (58), we get
1 [ + +s,Z)}
O (u.T)
8t E(S(m: + 8zZ)}
1 (1 - 2p) E[ Z[Zsign(T + s;2))]
(59)
8t 1 (1 2p) E(sign (7 m, + 81 S))
To calculate the expectation in the numerator, we write
Smm
12
-m//s
222
E(Zsign(m: sz
-mm//
V2T
V2T
-Sm/
22
melee
e. 2212
7
e
22
22T
2
v 2m
To compute the expectation in the denominator, write
6-2²12 dz
-ma/s 2=2212
E(sign(m, + s,Z)] -
dz = (D(mm/ss) 1.
22T
2m
Substituting the previous two identities in (59), obtain
1 (1 (1-2p)T 2/ TE
2
gi (u, T
81 1 (1 (1-120) (1-2pp) 2
1 (1-2p)
(60)
1+ (1 2p)
(2 Ue
34

---

Next note that (55) and (56) follows from Theorem 4.3 where we can calculate ? explicitly as (note that y 1 in the current case)
2
112h;
3/2
2
7
1-2p
sign( ]
0/2/
2
1-
2p
1- 2p
2 1 2p
E[|Z|]
El|Zal] = V
a3/2
αry
π
To prove (57), note that under the GLM setting with sing link function, the true label of features vector 2: is given by sign(æ' x 3), while the prediction by model B3r are given by sign(x' B³). Hence, (3 = P( 3 (2, B) < 0). Since x N(O, Ia/n), letting Z vn(æx B3/ ( and
7/2 (,( 1811ez we have (71, N(O, [ f with p
(9' 9
Hence,
B 2g
1
Pe P(2 < 0) cos (p).
See e.g. [20, Section 15. Using the result of Theorem 4.2, we have
p P
pC?
P4Y
717
7
1
of
V m2h
since 7 1. This completes the proof.
K
Extension of Theory to the Multi-Class Case and Non-Linear Models
Extension of theory to multi-class case. This can be done by following similar ideas in the binary case, but will be heavier in notation and will involve more tedious analysis. Here we outline how this extension can be made for the GMM case in Section 3. We first deseribe the setting. We define matrix Y Re*k where n is the number of samples and A is the number of classes, using one-hot encoding, where column i has for the samples belonging to class and otherwise. Next, define M RRax where row is the mean feature vector
class i. Eq. (1) then transforms to X -YM Z, where Z is random noise; so this is low rank matrix (YM is of rank k) plus noise. We can then generalize the AMP iterations for this low-rank model. The forms of eqs. (4) and (5) in this case will be the be applied row-wise instead of coordinate-wise, Also the coefficient C. in (6) will now be a x matrix, defined similarly using the Jacobian of ge instead of derivative. Likewise, the state evolution recursion (8) will be of the same form, with the modification that m, Tt. my, o. are now vectors of length k. The insights from the analysis sis will be similar but the analysis will be on multi-dimensional objects. A similar extension can be made for GLMs in Section 4, where / should now be defined as a matrix of size io d. The extension here for the AMP iterates (17), (18) and the state evolution (22) are similar to the GMM case described above.
with 9: redefined appropriately for the matrix case (here it will
Extension of theory to non-linear models. We note that the AMP techniques can be used analyze the statistical behavior of more general M-estimators (see for e.g., [14]). The corresponding update rule will involve applying the aggregator function (aggregating current predictions and the given noisy labels) as well as gradient descent type of update (similar to eq. (4)). The exact details of these updates and the analysis will be quite tedious and are left for future work.
35

---

L Remaining Empirical Results
In Table 5, we list the average test accuracies of full RT, consensus- based RT, and BayesMix RT (28) after I and 10 iterations for Food-101 pho vs. ramen corrupted by the uniform noise model with 0.45. In Table 6, we perform an ablation study to compare these three RT methods at different values of p for the same dataset. Note that BayesMix RT performs the best for larger values of p. i.e. in the high label noise regime, whereas consensus-based RT performs the best for smaller values of p.
Table Linear probing and uniform noise (p= = 0.45): Average test accuracies = standard deviation for Food-101 101 pho vs. ramen with p= 0.45. In the first iteration, consensus- RT is the best, but at the tenth iteration, BayesMix RT is the best by big margin.
Iteration #
Full RT
Consensus-based RT
BayesMix RT (ours)
(initial model)
58.13 2.54
58.13 2.54
58.13 = 2.54
61.33 2.54 (3.20
63.60 + 3.22 (5.47 t)
60.53 + 3.27 (2.40
10
62.60 + 2.12 (1.47))
64.87 = 4.07 (6.74
76.60 = 6.00 (18.47 1)
Table Linear probing under uniform noise with different values of p: Average test accuracies + standard deviation for Food-101 pho vs. ramen after 10 iterations of full RT, consensus-based RT, and BayesMix RT. Observe that BayesMix RT performs the best for larger values of p. i.c., the more challenging high-noise regime, whereas consensus-baset RT performs the best for smaller values of p.
p
Initial training
Full RT
Consensus-based RT
BayesMix RT (ours)
0.45
58.13= = 2.54
62.60 + 2.12
64.87 + 4.07
76.60 = 6.00
0.40
67.53 + 3.88
74.60 +: 6.57
79.87 +: 6.32
83.00 # 1.30
0.35
73.20 2.29
79.27 4.34
86.00 + 3.77
85.33 # 0.50
0.30
79.47 = 1.65
87.33 + 2.00
85.40 # 0.57
A Adversarial noise model. Now we consider a much harder noise model wherein an adversary gets to determine the "important" samples and flip their labels. The adversary determines important samples by training the same model which will be trained by us, but with clean labels instead and orders the samples in the decreasing order of the absolute value of the unnormalized logits. Note that a higher logit absolute value implies that the model is very confident on the sample, so flipping the label of such sample would be more detrimental to the model's 's training as it would need to adjust the decision boundary by large amount for this incorrectly labeled sample. The adversary then flips the labels of the top a fraction of the samples with largest absolute values of the unnormalized logits. Under this adversarial noise model with 0.25 for MedMNIST Pneumonia, we compare PrresMix-Siippie RT (29) with full RT and consensus-based RT after I and 10 iterations in Table 7 (again, the table below lists the average test accuracies).
Table 7: Linear probing and adversarial noise: Average test accuracies standard deviation for MedMNIST Pneumonia. BayesMix- Simple RT performs the best.
Iteration #
Full RT
Consensus- based RT
PoyesMix-Simpiee RT (ours)
0 (initial model)
63.94 1.51
63.94 + 1.51
63.94 + 1.51
66.83 + 1.93 (2.89
66.77 + 1.78 (2.83
67.15 + 1.83 (3.21 1)
10
73.77 + 0.79 (9.83 f)
76.76 2.51 (12.82
78.04 + 1.98 (14.10 1)
M Derivation of the Aggregator used in Experiments
Here we show the derivation of (28) used in our experiments. This is straightforward extension of (32). (34) (in Appendix C) with means and variances of the Gaussians corresponding to the positive and negative logits being (n-, a²) and (m_, .²). respectively. Specifically, letting denote the logit
'Please note that real data may not necessarily follow the GMM setting in Section 3, so BayesMix RT being the optimal strategy is not necessary.
36

---

and Y and Y denote the ground truth label and observed label random variables, respectively, we have (following the derivation of (32)):
9(2,7)
2P G 3يي a
P - = 1) = 1)
P(G= 2 ( /f Y 1) = 1) + (G= = Y =-1) 1. (61)
(Notice that unlike (32), dropped the dependence on t to lighten the notation.) Again, G ~ N(0. 1)
and (PYY 1) n, and P(Y -1) n__ Also, under the uniform noise model, P P -Y=1)
and PP (8- = -//y = -1) are the same as (33). This can be extended to the non-uniform noise model as
well, where P( --1 = +1) = p and P(P 1|/ = =-1) = q. to get:
P( / = 1) (1- 1 p -
and F(Y=Tly = -1) (1 4.
(62)
Using all of this in (61) followed by some algebraic simplification gives us (28).
N
Experimental Details
Here we provide details about our experiments.
Our experiments were done using TensorFlow and Keras on one 128 GB CPU and one 40 GB A100 GPU (per run). For initial training as well as for each iteration of retraining, the optimizer is Adam
(with default values of B1 0.9 and B2 0.999) with batch size = 32 & number of epochs 10 for linear probing and batch size = 128 & number of epochs 2 for full network training." We also apply weight decay 0.1 the case of full network training to mitigate overfitting." We tune the learning rate by monitoring the accuracy on small clean validation set (i.e., the labels of the validation set are not corrupted). For settings where we already know that the given labels will be noisy, we can manually clean up small part of the dataset and use that as the validation set to mitigate overfitting. each case, we first tune the learning rate for initial training; denote this by 1)o Then for each retraining method, we tune the learning rate for the first iteration and use it for all subsequent iterations; denote this by 7/1- Note that we use the same value of 7jo for all the retraining methods. Also recall that in the adversarial noise model described in Appendix L, the adversary initially trains the model with clean labels to determine the samples whose labels wishes to flip. The adversary's training details are the same described above; let us denote its learning rate, which is also tuned, by Tadv. We tune Jadv, 770 and 171 from (5 x 10-3, ,,10-3 5 x 10-4, 1001, ,,5 x 10-5 10-5, .5x x 10-6, 10-9).
1. MedMNIST Pneumonia (https: //www. tensorflow org/ htg//daaatts/ccaaaaaaa pneumonia, :: This has 4708 training examples and comes with a validation set of size 200. The test consists of 624 examples.
2. Food-101 (https: //www. www.:t.ensofflor. org/ /daaaasess/aatllgg/eeeteeee
Fach class
in Food-101 has 750 training examples; so the total number of examples for two classes (pho ramen and spaghetti bolognese vs. spaghetti carbonara) is 1500. Out of these 1500 examples, we randomly select 100 examples as our validation set. The test set consists of 500 examples in total.
"Note that training an entire deep network is much more computationally expensive than linear probing.
" "Note full network training much more prone to overfitting than lincar prohing.
We observed that one leamnnng rate for initial training and retraining does not work well.
37


Reviews:
[{"review_id": "GEXOCR9r4D", "reviewer": "Reviewer_ZTCf", "summary": "Previous work has proved the benefits of retraining, but few work have answered what is the optimal combination of the model's predictions and the provided labels. This paper addresses the fundamental question for binary classification tasks. They develop a framework based on approximate message passing to make an analysis for GMM and GLM. The contribution is the derivation of the bayes optimal aggregator function. Based on this, the authors propose a practically usable version of their theoretically optimal aggregator function. This practical version is tailored for linear probing with the cross-entropy loss. Through analysis and experiments, they demonstrate its superiority over baseline methods (like full retraining and consensus-based retraining) in high label noise regimes. The paper distinguishes its method from existing \"full retraining\" and \"consensus-based retraining\" schemes, which use hard predicted labels or only samples where predictions match noisy labels, respectively.", "questions": "1. How can you make a connection of the cases you study in the paper to other non-linear deep learning models? I would like to see the discussion on the practical computational overhead of the optimal method, particularly concerning the complexity of the optimal aggregator and its derivatives within the AMP updates, and how this might impact its usage on very large models or datasets.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength: \n1. The paper presents a good theoretical framework based on AMP to analyze iterative retraining. And based on the theoretical analysis, the paper develops a strategy to combine given labels and predicted labels for linear probing with the binary cross-entropy loss.\n2. The paper is the first work to analyze the optimal way to combine predicted and given labels for any retraining-like idea.\n3. The paper has a good writing structure and clearly articulates the problem statement and its motivations\n\nWeakness:\n1. The current theoretical results are primarily for linear models and binary classification. Although not necessary for this paper, it should be better to try the framework in a more general setting, like self-training for other deep learning models. At least one case should make the method more scalable and convincing research communities that it can be incorporated into recent AI system.\n2. Although the theoretical results are solid, the experimental results are using uniform noise. It is unknown how it can generalize to more complex scenarios like data dependent noise.", "was_revised": true, "final_justification": "The reviewers provide detailed reponses and additional experiments to answer my question. The concern regarding the generalization of the method to multi-class cases and other types of label noise have been resolved, while the concern regarding the generalization of the framework to non-linear model is still not clear, which the author left the detailed work for the future.", "rebuttal": "Thanks for your review and feedback! You have raised good points and we respond to your concerns and questions below.\n\n**Extension of theory to multi-class case.** This can be done by following similar ideas in the paper for the binary case, but will be heavier in notation and will involve more tedious analysis. Here we outline how this extension can be made for the GMM case in Section 3. We first describe the setting. We define a label matrix $Y \\in \\mathbb{R}^{n \\times k}$, where $n$ is the number of samples and $k$ is the number of classes, using one-hot encoding, where column $i$ has $1$ for the samples belonging to class $i$ and $0$ otherwise. Next, we define $M \\in \\mathbb{R}^{k \\times d}$ where row $i$ is the mean feature vector of class $i$. Equation (1) then transforms to $X = YM+Z$, where $Z$ is random noise; so this is a low rank matrix ($YM$ is of rank $k$) plus noise. We can then generalize the AMP iterations for this low-rank model. The forms of eqs. (4) and (5) in this case will be the same with $g_t$ redefined appropriately for the matrix case (here it will be applied row-wise instead of coordinate-wise). Also the coefficient $C_t$ in line 126 will now be a $k \\times k$ matrix, defined similarly using the Jacobian of $g_t$ instead of derivative. Likewise, the state evolution recursion (7) will be of the same form, with the modification that $m_t, \\sigma_t, \\bar{m_t}, \\bar{\\sigma}_t$ are now vectors of length $k$. The insights from the analysis will be similar but the analysis will be on multi-dimensional objects. A similar extension can be made for GLMs in Section 4, where $\\beta$ should now be defined as a matrix of size $k \\times d$. The extension here for the AMP iterates (16-17) and the state evolution (21) are similar to the GMM case described above.\n\n**Extension of theory to non-linear models.** We note that the AMP techniques can be used to analyze the statistical behavior of more general M-estimators (see for e.g., reference [14, section 4.4] in the paper). The corresponding update rule will involve applying the aggregator function (aggregating current predictions and the given noisy labels) as well as a gradient descent type of update (similar to eq. (4)). The exact details of these updates and the analysis will be quite tedious and are left for future work. \n\n**Extension in practice to different types of label noise (beyond uniform) and deep learning models.** Although our theoretical results focused on linear models, the algorithm is Section 5 proposed for use in practice, i.e. BayesMix RT, is based on insights that carry over to general ML models. Specifically, eq. (27) is obtained by fitting a GMM on the distribution of the unnormalized logits (following the derivation in eq. (30) for theory). Following the same approach (and even in multi-class setting), we can rewrite the Bayesian posterior of the class memberships, after observing the current model's unnormalized logits with the prior based on the label noise model (in our paper, we have considered the uniform prior). We can then derive the corresponding aggregating function $g$ similar to eq. (27) in the paper. In short, *BayesMix RT can be used in deep learning models and even with non-uniform label noise priors* (e.g., when the flipping probability from class i to class j is some $p_{i, j}$). As an example, in the binary case, consider the **non-uniform noise model**: $\\mathbb{P}(\\hat{y} = -1| y = +1) = p$ and $\\mathbb{P}(\\hat{y} = +1| y = -1) = q$ with $p \\neq q$. Then, eq. (27) changes to:\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\Big(\\frac{q(1-q)}{p(1-p)}\\Big) \\Big(\\frac{p q}{(1-p)(1-q)}\\Big)^{\\hat{y}/2} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1.$$\nWe show an experimental result under the above **non-uniform noise model** with $p=0.45$ and $q=0.2$ for the MedMNIST Pneumonia dataset in the same setting as Section 5 using the formula above for BayesMix RT; the table below lists the average *test* accuracies $\\pm$ standard deviation (over 3 runs) in this case. As we see below, **BayesMix RT performs the best**.\n\n|Iteration #| Full RT| Consensus-based RT| BayesMix RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|\n|1| $78.21 \\pm 2.04$ | $77.51 \\pm 1.92$ | $\\textbf{81.14} \\pm 0.46$ |\n|10| $81.62 \\pm 2.16$ | $82.26 \\pm 2.36$ | $\\textbf{84.62} \\pm 0.73$ |\n\nFor more **general types of label noise** (e.g., sample-dependent noise) or in scenarios **where the noise model is not known**, we propose the following **simpler aggregation function** (instead of eq. (27)):\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\gamma^{\\hat{y}} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1,$$\nfor some constant $\\gamma \\in (0,1)$ which can be tuned. We call this simpler version **BayesMix-Simple RT** (everything else is the same as BayesMix RT in the paper); in our implementation, we set $\\gamma = 0.7$ throughout without any tuning though. Please note that *this can be used with general ML models*.\n\n**(1)** To show the **efficacy of BayesMix-Simple RT**, we first consider an **adversarial noise model**. Specifically, an adversary gets to determine the \"important\" samples and flip their labels. The adversary determines important samples by training the same model which will be trained by us *with clean labels* and orders the samples in the decreasing order of the absolute value of the unnormalized logits. Note that a higher logit absolute value implies that the model is very confident on the sample, so flipping the label of such a sample would be more detrimental to the model's training as it would need to adjust the decision boundary by a large amount for this incorrectly labeled sample. The adversary then flips the labels of the top $\\alpha$ fraction of the samples with largest absolute values of the unnormalized logits. Under this **adversarial noise model** (we don't assume knowledge of this process in training to be clear) with $\\alpha=0.25$ for MedMNIST Pneumonia in the same setting as Section 5, we show the efficacy of **BayesMix-Simple RT** below compared to the baselines (again, the table below lists the average *test* accuracies $\\pm$ standard deviation over 3 runs). \n\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$63.94 \\pm 1.51$|$63.94 \\pm 1.51$|$63.94 \\pm 1.51$|\n|1| $66.83 \\pm 1.93$ | $66.77 \\pm 1.78$ | $\\textbf{67.15} \\pm 1.83$ |\n|10| $73.77 \\pm 0.79$ | $76.76 \\pm 2.51$ | $\\textbf{78.04} \\pm 1.98$ |\n\n**(2)** We now show the **efficacy of BayesMix-Simple RT** even for **deep network training**; recall that our earlier experiments are for linear probing with a pre-trained ResNet-50. Specifically, here we consider *training an **entire** pre-trained ResNet-50*; this is a **typical deep learning** setting. Because of the heavy computational cost of training an entire deep network, we only do 3 iterations of retraining here. We show results for two cases of Food-101:\n\n**i.** *Pho vs. Ramen corrupted by uniform noise with $p=0.4$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$61.13 \\pm 3.39$|$61.13 \\pm 3.39$|$61.13 \\pm 3.39$|\n|1| $59.07 \\pm 5.44$ | $59.33 \\pm 4.83$ | $\\textbf{66.73} \\pm 3.72$ |\n|3| $57.67 \\pm 7.47$ | $58.47 \\pm 6.78$ | $\\textbf{70.67} \\pm 4.65$ |\n\n**ii.** *Spaghetti Bolognese vs. Spaghetti Carbonara corrupted by non-uniform noise described above with $p=0.45$ and $q=0.2$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$65.45 \\pm 2.22$|$65.45 \\pm 2.22$|$65.45 \\pm 2.22$|\n|1| $61.35 \\pm 7.31$ | $ 61.30 \\pm 4.48$ | $\\textbf{74.55} \\pm 3.75$ |\n|3| $56.50 \\pm 7.74$ | $59.70 \\pm 5.57$ | $\\textbf{80.30} \\pm 5.58$ |\n\nNote that in the above two tables (for full ResNet-50 training), **BayesMix-Simple RT leads to significant gains** over the initial model, while Full RT and Consensus-based RT are actually detrimental.\n\n*So in summary, our proposed method is effective with different label noise models as well as for general ML models.* \n\nRegarding your question about practical computational overhead of our methods BayesMix RT and BayesMix-Simple RT, note that the major extra cost compared to Full RT and Consensus-based RT is in fitting the bimodal GMM to obtain the aggregation function $g$. But this is negligible when compared to the training (backward and forward propagation) cost of every epoch, especially for large models. So our proposed methods do not introduce too much extra overhead. It is worth mentioning that for larger models, having multiple rounds of retraining will be expensive. Also, just to clarify the AMP updates in eqs. (4-5) and (16-17) are for theory only. While the insights obtained from the AMP analysis are used to propose BayesMix/BayesMix-Simple RT, they do not use the specific AMP updates. Having said that, even if we consider the AMP updates in eqs. (4-5) for GMM (Sec 3), our algorithm has the same effective per-iteration complexity as Full RT and Consensus-based RT of $O(nd)$ due to the two matrix-vector multiplications (those involving $X$ and $X^\\top$). The only difference is in applying the optimal aggregator $g_t$ and also computing the correction (Onsager) term $C_t$; both of these are $O(n)$ which is negligible compared to $O(nd)$ for large $d$. A similar argument holds for the GLM case (Sec 4).\n\nWe will add all this discussion in the next version of our paper. We hope to have resolved your concerns and questions, but we're happy to discuss further if needed. If you're satisfied with our responses, **we sincerely hope you will raise your score**!"}, {"review_id": "yzIrFNzvpW", "reviewer": "Reviewer_Pm7K", "summary": "This paper tackles the open question of how to optimally combine a model’s own predictions with the original (potentially noisy) labels during retraining. Focusing on binary classification, the authors develop a theoretical framework based on Approximate Message Passing (AMP) to analyze iterative self-retraining for two settings: a Gaussian Mixture Model (GMM) and a Generalized Linear Model (GLM). \nThe main contributions are: Bayes-Optimal Aggregator: Derivation of the Bayes-optimal aggregator function gt that combines the model’s current predicted label and the given noisy label at each retraining round such that retraining on this combination minimizes the model’s prediction error. To our knowledge, this is the first work providing a theoretically optimal way to mix predicted and given labels in retraining, extending prior retraining methods (which used heuristics like “full” or “consensus” retraining) by rigorously identifying the optimal mixture. AMP-based Analysis of Multiple Retraining Rounds: Introduction of an iterative retraining scheme formulated as an AMP algorithm. The authors derive a state evolution recursion that exactly characterizes the asymptotic behavior (as data dimension and sample size grow proportionally) of the model’s accuracy over successive retraining rounds. Using this analysis, they quantify how the optimal retraining strategy performs over multiple iterations, and they prove theoretical results such as Theorem 3.1 (asymptotic Gaussianity of model estimates via AMP) and Theorem 3.2/4.3 (formulas for the optimal aggregator in GMM/GLM).\nKey Theoretical Insights: They show that using the Bayes-optimal aggregator strictly improves the model’s signal-to-noise ratio each round (when the model is not already near-perfect) and dominates earlier retraining schemes. A notable insight is that retraining is not universally beneficial: if the initial model is very strong, further retraining can hurt performance, whereas if the initial model is weaker, retraining helps (they formalize a condition for this crossover).\nPractical Method and Experiments: Building on the theory, the authors propose a practical version of the optimal aggregator for real data. In particular, for a pretrained model fine-tuned with a linear probe, they use a bimodal GMM fit on the model’s logit distribution to approximate the Bayes-optimal combination of labels. This method, termed “BayesMix RT”, is evaluated on image classification tasks with artificial label noise. In experiments on a medical imaging dataset and a Food-101 subset, BayesMix RT significantly outperforms two baseline retraining strategies from prior work (full retraining and consensus-based retraining) under high label noise (45% flipped labels). For instance, after 10 retraining iterations on one task, BayesMix RT reached ~76.6% accuracy vs ~64–65% with the baselines, demonstrating a substantial performance gain in noisy conditions. \nThe paper’s contributions are thoroughly evaluated through theoretical proofs (with detailed appendices) and simulation/empirical results, providing a holistic understanding of optimal self-retraining.", "questions": "The work is restricted to binary class labels. How challenging do the authors expect it to be to extend the Bayes-optimal aggregator derivation to a multi-class setting?  Could the authors elaborate on what the optimal aggregator might look like for $K>2$ classes?\n\nThe optimal aggregator formulas (e.g., Eq. (13) for GMM) explicitly depend on the label flipping probability $p$ (and class priors). In practice, $p$ might not be known exactly. Did the authors experiment with estimating $p$ from data or treating it as a tuned parameter? How sensitive is BayesMix RT to mis-specification of $p$? It would be useful to know if using a slightly wrong noise rate (or an adaptive estimate of it) significantly hurts performance or not. Similarly, the practical method requires fitting a GMM to logits and if this fit is imperfect (e.g. if the logit distribution is not a clean mixture of two Gaussians), does it degrade the results? Clarifying the robustness of the approach to these assumptions would help practitioners know how to apply it. \n\nThe theory (Proposition 3.3) indicates a scenario where retraining can degrade performance if the initial model’s accuracy is above a certain threshold relative to noise. This is a compelling insight. Could the authors provide more intuition or empirical confirmation for this phenomenon? In the experiments presented, BayesMix RT always improved accuracy over 10 iterations, even when starting from a reasonably good initial model (e.g., ~79% in Table 5 for p=0.30). Did the authors observe any instance where continuing to retrain actually made things worse (for either their method or the baselines)? It would be useful to know, for example, if one should stop retraining after a certain point. \n\nThe empirical demonstration is for retraining only the last layer of a neural network. Do the authors have thoughts on extending BayesMix retraining to fine-tuning an entire deep network? In principle, one could use the model’s predictions (or soft probabilities) in the loss for all layers. Would the aggregator still be applicable or would new complications arise (e.g., the model’s feature representation shifting while we alter labels)? This is related to the assumption in GLM analysis that features are fixed i.i.d. random vectors. How might one integrate the optimal label aggregation into an end-to-end training pipeline?\n\nThe paper assumes uniform random noise (each label flipped with the same probability p). If the noise were class-dependent (each class has its own flip probability) or feature-dependent (hard examples more likely mislabeled), the current aggregator might not directly apply. In such cases, do the authors expect the strategy to change?", "limitations": "The authors have adequately addressed the limitations of their work and potential societal impacts. They explicitly discuss key limitations in Section 6 (second paragraph): notably, the restriction to linear models, binary classification, and uniform noise. They frame these as avenues for future work, indicating awareness that the method needs extension to handle multi-class data and more complex noise distributions. They also acknowledge that their current practical method is tailored to linear probing and that extending to nonlinear deep models is a future goal. This openness about scope is commendable and readers are clearly informed about where the results apply or not which is good practice.\n\nOne limitation not deeply discussed (but worth reflecting on) is the assumption of knowing the noise level $p$. In practice how would one estimate it.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The paper answers a clear open question - what is the optimal way to mix predicted and given labels during retraining? They obtain this  by deriving the Bayes-optimal solution for that mixture. This is a notable advance since prior works on label-noise retraining either retrained on predicted labels alone or used heuristics (e.g. ignore or trust labels based on agreement) but did not determine an optimal combination rule. The authors’ use of AMP theory to derive a closed-form aggregator (e.g. Equation (13) for GMM) is elegant and appears novel. \n\nThe paper is technically solid. It provides precise asymptotic analysis of the retraining dynamics via state evolution equations (Theorem 3.1, 4.2) and proves the optimality of their proposed aggregator (Theorem 3.2, 4.3) with all assumptions clearly stated. The proofs are given in a detailed appendix, and the authors reference where each result is proven. The analytical work is thorough. For instance, authors even discuss how to handle non-Lipschitz aggregator functions via approximation to satisfy AMP conditions.  This level of rigor is required for  high quality paper in the theory development.\n\nThe theoretical results yield interesting insights into when retraining helps vs hurts. Proposition 3.3, for instance, shows that if the initial model’s accuracy is below a certain threshold (related to a fixed point of their state evolution), each retraining round will improve accuracy, but if it’s above that threshold, retraining could degrade accuracy. This explains and quantifies a phenomenon that practitioners might have observed anecdotally. The paper also neatly recovers prior strategies as special cases – e.g., “full retraining” corresponds to using only model predictions. \n\nDespite the heavy theory, the authors connect to practice by devising the BayesMix RT method for training a linear probe with noisy labels. This method is directly inspired by their theory (essentially implementing a softened version of the theoretical aggregator using a fitted mixture model). The experiments, though limited in scope (two datasets), demonstrate significant empirical gains in extremely noisy scenarios. This suggests the theory has practical merit. Furthermore, the authors conducted simulations (Appendix D) to verify that their state evolution predictions match finite-sample behavior and that the optimal aggregator improves over simpler retraining approaches.", "was_revised": true, "final_justification": "The authors' rebuttal has thoroughly addressed my concerns on multi-class extension, handling unknown p (via estimation and a simple p-independent variant), robustness to GMM fitting assumptions, and empirical confirmation of when retraining degrades performance (e.g., in full ResNet-50 experiments where baselines hurt but BayesMix-Simple RT helps). The new results on non-uniform and adversarial noise models further demonstrate the method's versatility beyond uniform noise, and the adaptation ideas for end-to-end deep training and complex noise priors suggest promising future extensions. \n\nThese responses reinforce the paper's strengths in deriving a theoretically optimal aggregator, providing insightful analysis via AMP, and bridging to practice with BayesMix RT. The authors have done a good job with the rebuttal, resolving all points raised. This remains a technically solid paper with high impact in theoretical ML and label noise handling, excellent evaluation (now bolstered by rebuttal experiments), and no ethical issues. I stand by my original accept recommendation.", "rebuttal": "Thanks for your detailed review and positive assessment of our work! You have raised great points and we address your questions and concerns below.\n\n**Extension of theory to multi-class case.** This can be done by following similar ideas in the paper for the binary case, but will involve more tedious analysis. Here we outline how this extension can be made for the GMM case in Section 3. We first describe the setting. We define a label matrix $Y \\in \\mathbb{R}^{n \\times k}$, where $n$ is the # of samples and $k$ is the # of classes, using one-hot encoding, where column $i$ has $1$ for the samples belonging to class $i$ and $0$ otherwise. Next, we define $M \\in \\mathbb{R}^{k \\times d}$ where row $i$ is the mean feature vector of class $i$. Eq. (1) then transforms to $X = YM+Z$, where $Z$ is random noise; so this is a low rank matrix ($YM$ is of rank $k$) plus noise. We can then generalize the AMP iterations for this low-rank model. The forms of eqs. (4) and (5) in this case will be the same with $g_t$ redefined appropriately for the matrix case (here it will be applied row-wise instead of coordinate-wise). Also the coefficient $C_t$ in line 126 will now be a $k \\times k$ matrix, defined similarly using the Jacobian of $g_t$ instead of derivative. Likewise, the state evolution recursion (7) will be of the same form, with the modification that $m_t, \\sigma_t, \\bar{m_t}, \\bar{\\sigma}_t$ are now vectors of length $k$. The insights from the analysis will be similar but the analysis will be on multi-dimensional objects. A similar extension can be made for GLMs in Section 4, where $\\beta$ should now be defined as a matrix of size $k \\times d$. The extension here for the AMP iterates (16-17) and the state evolution (21) are similar to the GMM case described above.\n\n**Dealing with unknown label flip probability $p$.** Great question! We propose the following way to estimate $p$. We focus on the samples for which the model is the most confident after training with the given noisy labels. Specifically, we pick the set of samples $S_\\text{conf}$ with the highest $\\rho$ (this should be small) fraction of absolute value of unnormalized logits; a higher value indicates higher confidence. The philosophy of self-training based ideas is that the model is probably correct on the samples for which it is very confident; so we treat the model's predicted labels for the samples in $S_\\text{conf}$ as the ground truth labels and calculate the % of samples in $S_\\text{conf}$ for which the predicted label matches the given label. This gives us an estimate for $p$. We tested this approach for MedMNIST Pneumonia dataset in the same setting as Sec. 5; here are the results averaged over 3 runs.\n\n|Actual $p$| Estimated $p$ (mean $\\pm$ std.)|\n|---|---|\n|0.45 |$0.41\\pm0.01$|\n|0.30| $0.26\\pm0.02$ |\n|0.15| $0.12\\pm0.01$ |\n\nSo this gives us a good estimate. We also saw that using the estimated $p$'s above basically didn't change the results at all. Noting this and also taking into account that the estimated $p$ may be off by a lot sometimes, we tested the following **simpler aggregator function** (as a substitute for eq. (27)) *independent of* $p$:\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\gamma^{\\hat{y}} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1,$$\nfor some constant $\\gamma \\in (0,1)$ which can be tuned. Note that $\\gamma$ essentially plays the role of $p/(1-p)$. We call this simpler version **BayesMix-Simple RT** (everything else is the same as BayesMix RT in the paper); in our implementation, we set $\\gamma = 0.7$ throughout w/o any tuning. We compare test accuracies (mean $\\pm$ std. averaged over 3 runs) for MedMNIST Pneumonia obtained after 10 iterations of Full RT, Consensus RT, BayesMix RT with the exact $p$ and BayesMix-Simple RT (with $\\gamma = 0.7$).\n\n|$p$|Initial Model|Full RT| Consensus RT| BayesMix RT with exact $p$| BayesMix-Simple RT|\n|---|---|---|---|---|---|\n|0.45|$64.58\\pm3.07$|$68.06\\pm3.78$|$70.03\\pm0.73$|$71.42\\pm2.43$|$72.38\\pm1.66$|\n|0.30|$78.42\\pm2.15$|$78.85\\pm3.14$|$82.16\\pm1.63$|$84.82\\pm0.89$|$84.67\\pm1.58$|\n|0.15|$81.41\\pm0.47$|$82.10\\pm1.74$|$84.88\\pm1.29$|$87.29\\pm1.40$|$85.90\\pm0.33$|\n\nNotice that *BayesMix-Simple RT is competitive with BayesMix RT* even though it does not use the value of $p$.\n\nRegarding your question about fitting a GMM to the logits, note that in reality the distribution is unlikely to be a GMM exactly. Yet our method consistently leads to good performance (we show results with more noise models below).\n\n**Extension in practice to different types of label noise and general ML models**. BayesMix RT is based on insights that carry over to general ML models. Specifically, eq. (27) is obtained by fitting a bimodal GMM on the distributions of the unnormalized logits (following the derivation in eq. (30) for theory). Following the same approach, we can rewrite the Bayesian posterior of the class memberships, after observing the current model's unnormalized logits with the prior based on the label noise model. We can then derive the corresponding aggregating function $g$ similar to eq. (27) in the paper. In short, *BayesMix RT can be used in deep learning models and even with non-uniform label noise priors* (e.g., when the flipping probability from class i to class j is some $p_{i, j}$). As an example, in the binary case, consider the **non-uniform noise model**: $\\mathbb{P}(\\hat{y} = -1| y = +1) = p$ and $\\mathbb{P}(\\hat{y} = +1| y = -1) = q$ with $p \\neq q$. Then, eq. (27) changes to:\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\Big(\\frac{q(1-q)}{p(1-p)}\\Big) \\Big(\\frac{p q}{(1-p)(1-q)}\\Big)^{\\hat{y}/2} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1.$$\nWe show a result under the above **non-uniform noise model** with $p=0.45$ and $q=0.2$ for the MedMNIST Pneumonia dataset in the same setting as Sec. 5 using the formula above for BayesMix RT; the table below lists the average *test* accuracies $\\pm$ std. (over 3 runs) in this case. As we see below, **BayesMix RT performs the best**.\n\n|Iteration #| Full RT| Consensus RT| BayesMix RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|\n|1| $78.21 \\pm 2.04$ | $77.51 \\pm 1.92$ | $\\textbf{81.14} \\pm 0.46$ |\n|10| $81.62 \\pm 2.16$ | $82.26 \\pm 2.36$ | $\\textbf{84.62} \\pm 0.73$ |\n\nFor **more general types of label noise** or **in scenarios where the noise model is not known**, we propose to use the **BayesMix-Simple RT** algorithm described above as it is independent of any noise distribution parameter and is competitive with BayesMix RT in the uniform noise case. Also note that **this can be used with general ML models**.\n\n**(1)** To show the **efficacy of BayesMix-Simple RT**, we first consider an **adversarial noise model**. Specifically, an adversary gets to determine the \"important\" samples and flip their labels. The adversary determines important samples by training the same model which will be trained by us *with clean labels* and orders the samples in the decreasing order of the absolute value of the unnormalized logits. Note that a higher logit absolute value implies that the model is very confident (and probably correct) on the sample, so flipping the label of such a sample would be more detrimental to the model's training as it would need to adjust the decision boundary by a large amount for this incorrectly labeled sample. The adversary flips the labels of the top $\\alpha$ fraction of the samples with largest absolute values of the unnormalized logits. Under this **adversarial noise model** (we don't assume knowledge of this process in training to be clear) with $\\alpha=0.25$ for MedMNIST Pneumonia in the same setting as Sec. 5, we show the efficacy of **BayesMix-Simple RT** below compared to the baselines (table below lists average *test* accuracies $\\pm$ std. over 3 runs). \n\n|Iteration #| Full RT| Consensus RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$63.94\\pm1.51$|$63.94\\pm1.51$|$63.94\\pm1.51$|\n|1| $66.83\\pm1.93$ | $66.77\\pm1.78$ | $\\textbf{67.15}\\pm1.83$ |\n|10| $73.77\\pm0.79$ | $76.76\\pm2.51$ | $\\textbf{78.04}\\pm1.98$ |\n\n**(2)** We now show the **efficacy of BayesMix-Simple RT** for **deep network training**. Recall that our earlier experiments are for linear probing with a pre-trained ResNet-50. Specifically, here we consider *training an **entire** pre-trained ResNet-50*. Because of the heavy computational cost of training an entire ResNet-50, we only do 3 iterations of retraining here. We show results for 2 cases of Food-101:\n\n**i.** *Pho vs. Ramen corrupted by uniform noise with $p=0.4$*\n|Iteration #| Full RT| Consensus RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$61.13\\pm3.39$|$61.13\\pm3.39$|$61.13\\pm3.39$|\n|1| $59.07\\pm5.44$ | $59.33\\pm4.83$ | $\\textbf{66.73}\\pm3.72$ |\n|3| $57.67\\pm7.47$ | $58.47\\pm6.78$ | $\\textbf{70.67}\\pm4.65$ |\n\n**ii.** *Spaghetti Bolognese vs. Spaghetti Carbonara corrupted by non-uniform noise described above with $p=0.45$ and $q=0.2$*\n|Iteration #| Full RT| Consensus RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$65.45\\pm2.22$|$65.45\\pm2.22$|$65.45\\pm2.22$|\n|1| $61.35\\pm7.31$ | $ 61.30\\pm4.48$ | $\\textbf{74.55}\\pm3.75$ |\n|3| $56.50\\pm7.74$ | $59.70\\pm5.57$ | $\\textbf{80.30}\\pm5.58$ |\n\nNote that in the above two tables (for entire ResNet-50 training), **BayesMix-Simple RT leads to significant gains** over the initial model, while Full RT and Consensus RT are actually detrimental; **the latter also answers your question about whether retraining can hurt performance in some cases**. It is possible that BayesMix-Simple RT hurts performance in some cases. \n\n*But in summary, our proposed method is effective with different label noise models as well as for general ML models.* \n\nWe hope to have resolved your concerns and questions, but we're happy to discuss further if needed."}, {"review_id": "YaybtbVSPM", "reviewer": "Reviewer_NMag", "summary": "**Summary**\nThis paper investigates how to optimally combine model predictions with noisy labels during iterative retraining in binary classification tasks. The authors develop a theoretical framework based on Approximate Message Passing (AMP) under both Gaussian Mixture Model (GMM) and Generalized Linear Model (GLM) settings. They derive the Bayes optimal aggregator function for label fusion and characterize the asymptotic performance via state evolution. A practical variant is also proposed for linear probing with cross-entropy loss, demonstrating empirical gains in high label noise regimes.", "questions": "1. Extension to Non-Uniform Noise Models:\nCould the authors comment on the feasibility of extending the analysis to more realistic, non-uniform or instance-dependent label noise models? A discussion or simulation could help assess robustness beyond uniform noise.\n2. Interpretation of the Aggregator Function:\nThe Bayes optimal aggregator is theoretically elegant, but can the authors provide more insight into its behavior (e.g., monotonicity, dependence on noise level, bias-variance trade-off)? This would help practitioners better understand when and how to use it.\n3. Scalability and Runtime Considerations:\nHow computationally efficient is the AMP-based retraining approach compared to existing heuristics? A brief runtime comparison or complexity discussion would help readers assess its practicality for large-scale use.\n4. Path Toward Non-Linear Models:\nGiven the growing use of deep models, can the authors elaborate on what specific challenges they foresee in extending their approach to non-linear architectures, and whether AMP or related techniques may still apply?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. Clean Theoretical Results: The paper provides a rigorous analysis of retraining procedures using AMP. The state evolution analysis provides transparent insight into how retraining affects generalization over iterations.\n2. Optimal Aggregator Derivation: The derivation of a Bayes optimal aggregator for combining predictions and noisy labels is a significant theoretical contribution.\n3. Empirical Gains: The theoretical insights are translated into a practical aggregator that can be used for linear probing to fine-tune deep neural networks. Empirical results show that this strategy performs particularly well in high label noise settings.\n\n**Weakness**\n1. Limited to Linear Models and Binary Classification: The current results are restricted to binary tasks and linear predictors. Extension to multi-class or non-linear models remains open.\n2. Assumption of Uniform Label Noise: The theoretical analysis assumes uniform random label flips, which may not hold in many practical settings.\n3. Lack of Theoretical Guarantees for Practical Variant:\nWhile the proposed aggregator function is shown to work well in practice, the prediction error under this retraining strategy is not theoretically characterized, especially when the optimal aggregator function is estimated from data (e.g., it seems very difficult to obtain a consistent estimator for the optimal aggregator function for GLMs). A formal analysis of its generalization behavior or error bounds would strengthen the practical significance and reliability of the method.\n4. Limited Empirical Evaluation: Experiments focus on synthetic and semi-synthetic settings. More diverse benchmarks would better support claims of practical relevance.", "was_revised": true, "final_justification": "The authors have comprehensively addressed most of my concerns and conducted extensive empirical analyses to demonstrate the performance of their method. I think it is a technically solid paper, and thus I raise my score.", "rebuttal": "Thanks for your review and feedback! You have raised great points and we address your questions below. \n\n**Extension in practice to different types of label noise (beyond uniform) and general ML models** (*Questions 1 and 4 & Weaknesses 1, 2 and 4*). Although our theoretical results focused on linear models, the algorithm is Sec. 5 proposed for use in practice, i.e. BayesMix RT, is based on insights that carry over to general ML models. Specifically, eq. (27) is obtained by fitting a bimodal GMM on the distributions of the unnormalized logits (following the derivation in eq. (30) for theory). Following the same approach, we can rewrite the Bayesian posterior of the class memberships, after observing the current model's unnormalized logits with the prior based on the label noise model (in our paper, we have considered the uniform prior). We can then derive the corresponding aggregating function $g$ similar to eq. (27) in the paper. In short, *BayesMix RT can be used in deep learning models and even with non-uniform label noise priors* (e.g., when the flipping probability from class i to j is some $p_{i, j}$). As an example, in the binary case, consider the **non-uniform noise model**: $\\mathbb{P}(\\hat{y} = -1| y = +1) = p$ and $\\mathbb{P}(\\hat{y} = +1| y = -1) = q$ with $p \\neq q$. Then, eq. (27) changes to:\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\Big(\\frac{q(1-q)}{p(1-p)}\\Big) \\Big(\\frac{p q}{(1-p)(1-q)}\\Big)^{\\hat{y}/2} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1.$$\nWe show a result under the above **non-uniform noise model** with $p=0.45$ and $q=0.2$ for the MedMNIST Pneumonia dataset in the same setting as Sec. 5 using the formula above for BayesMix RT; the table below lists the average *test* accuracies $\\pm$ std. (over 3 runs) in this case. Note **BayesMix RT performs the best**.\n\n|Iteration #| Full RT| Consensus-based RT| BayesMix RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|\n|1| $78.21 \\pm 2.04$ | $77.51 \\pm 1.92$ | $\\textbf{81.14} \\pm 0.46$ |\n|10| $81.62 \\pm 2.16$ | $82.26 \\pm 2.36$ | $\\textbf{84.62} \\pm 0.73$ |\n\nFor more **general types of label noise** (e.g., sample-dependent noise) or in scenarios **where the noise model is not known**, we propose the following **simpler aggregation function** (instead of (27)):\n$$g(z, \\hat{y}) = \\frac{2}{1+\\gamma^{\\hat{y}} \\exp\\Big(\\frac{(z-\\mu_{+})^2}{2\\sigma_{+}^2} - \\frac{(z-\\mu_{-})^2}{2\\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1,$$\nfor some constant $\\gamma \\in (0,1)$ which can be tuned. We call this simpler version **BayesMix-Simple RT** (everything else is the same as BayesMix RT in the paper); in our implementation, we set $\\gamma=0.7$ throughout w/o any tuning. Also note that **this can be used with general ML models**.\n\n**(1)** To show the **efficacy of BayesMix-Simple RT**, we first consider an **adversarial noise model**. Specifically, an adversary gets to determine the \"important\" samples and flip their labels. The adversary determines important samples by training the same model which will be trained by us *with clean labels* and orders the samples in the decreasing order of the absolute value of the unnormalized logits. Note that a higher logit absolute value implies that the model is very confident on the sample, so flipping the label of such a sample would be more detrimental to the model's training as it would need to adjust the decision boundary by a large amount for this incorrectly labeled sample. The adversary flips the labels of the top $\\alpha$ fraction of the samples with largest absolute values of the unnormalized logits. Under this **adversarial noise model** (we don't assume knowledge of this process in training to be clear) with $\\alpha=0.25$ for MedMNIST Pneumonia in the same setting as Sec. 5, we show the efficacy of **BayesMix-Simple RT** below compared to the baselines (table below lists the average *test* accuracies $\\pm$ std. over 3 runs). \n\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$63.94\\pm1.51$|$63.94\\pm1.51$|$63.94\\pm1.51$|\n|1| $66.83\\pm1.93$ | $66.77\\pm1.78$ | $\\textbf{67.15}\\pm1.83$ |\n|10| $73.77\\pm0.79$ | $76.76\\pm2.51$ | $\\textbf{78.04}\\pm1.98$ |\n\n**(2)** We now show the **efficacy of BayesMix-Simple RT** even for **deep network training**. Recall that our earlier experiments are for linear probing with a pre-trained ResNet-50. Specifically, here we consider *training an **entire** pre-trained ResNet-50*. Because of the heavy computational cost of training an entire ResNet-50, we only do 3 iterations of retraining here. We show results for two cases of Food-101:\n\n**i.** *Pho vs. Ramen corrupted by uniform noise with $p=0.4$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$61.13\\pm3.39$|$61.13\\pm3.39$|$61.13\\pm3.39$|\n|1| $59.07\\pm5.44$ | $59.33\\pm4.83$ | $\\textbf{66.73}\\pm3.72$ |\n|3| $57.67\\pm7.47$ | $58.47\\pm6.78$ | $\\textbf{70.67}\\pm4.65$ |\n\n**ii.** *Spaghetti Bolognese vs. Spaghetti Carbonara corrupted by non-uniform noise described above with $p=0.45$ and $q=0.2$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$65.45\\pm2.22$|$65.45\\pm2.22$|$65.45\\pm2.22$|\n|1| $61.35\\pm7.31$ | $ 61.30\\pm4.48$ | $\\textbf{74.55}\\pm3.75$ |\n|3| $56.50\\pm7.74$ | $59.70\\pm5.57$ | $\\textbf{80.30}\\pm5.58$ |\n\nNote that in the above two tables (for entire ResNet-50 training), **BayesMix-Simple RT leads to significant gains** over the initial model, while Full RT and Consensus-based RT are actually detrimental.\n\n*So in summary, our proposed method is effective with different label noise models as well as for general ML models.* \n\n**Extension of theory to non-linear models** (*Question 4 & Weakness 1*). We note that the AMP techniques can be used to analyze the statistical behavior of more general M-estimators (see for e.g., reference [14] in the paper). The corresponding update rule will involve applying the aggregator function (aggregating current predictions and the given noisy labels) as well as a gradient descent type of update (similar to eq. (4)). The exact details of these updates and the analysis will be quite tedious and are left for future work. \n\n**Extension of theory to multi-class case** (*Weakness 1*). This can be done by following similar ideas in the paper for the binary case, but will involve more tedious analysis. Here we outline how this extension can be made for the GMM case in Sec. 3. We first describe the setting. We define a matrix $Y \\in \\mathbb{R}^{n \\times k}$, where $n$ is the # of samples and $k$ is the # of classes, using one-hot encoding, where column $i$ has $1$ for the samples belonging to class $i$ and $0$ otherwise. Next, we define $M \\in \\mathbb{R}^{k \\times d}$ where row $i$ is the mean feature vector of class $i$. Eq. (1) then transforms to $X = YM+Z$, where $Z$ is random noise; so this is a low rank matrix ($YM$ is of rank $k$) plus noise. We can then generalize the AMP iterations for this low-rank model. The forms of eqs. (4) & (5) in this case will be the same with $g_t$ redefined appropriately for the matrix case (here it will be applied row-wise instead of coordinate-wise). Also the coefficient $C_t$ in line 126 will now be a $k \\times k$ matrix, defined similarly using the Jacobian of $g_t$ instead of derivative. Likewise, the state evolution recursion (7) will be of the same form, with the modification that $m_t, \\sigma_t, \\bar{m_t}, \\bar{\\sigma}_t$ are now vectors of length $k$. The insights from the analysis will be similar but the analysis will be on multi-dimensional objects. A similar extension can be made for GLMs in Sec. 4, where $\\beta$ should now be defined as a matrix of size $k \\times d$. The extension here for the AMP iterates (16-17) and the state evolution (21) are similar to the GMM case described above.\n\n**Interpretation of the Aggregator Function** (*Question 2*). Consider the aggregator in eq. (15) for the GMM case (similar insights hold for GLM and BayesMix RT). Recall that $g(y,\\hat{y})$ is the soft label obtained based on the soft prediction $y$ and the given noisy label $\\hat{y} \\in$ {$+1,-1$}. It is easy to see that $g(y,\\hat{y})\\in[-1,1]$, it is monotonic increasing in $y$ and $\\hat{y}$ (since $p<1/2$). Also it is increasing in $\\pi_+/\\pi_-$, accounting for class probabilities (so if $\\pi_+>\\pi_-$, our aggregated labels are biased towards the positive class). Also note the denominator can be rewritten as $1+\\exp\\Big(-\\log(\\frac{1-p}{p})\\hat{y} - 2y\\Big) \\frac{\\pi_-}{\\pi_+}$; so the term inside the exponential is a negative linear combination of $\\hat{y}$ and $y$. Now if the label flipping probability $p$ is small, we put a larger weight on the given labels $\\hat{y}$ relative to the predictions $y$, but as $p$ gets larger we reduce the weight on $\\hat{y}$, thereby relying more on the predictions $y$. These behavior trends of the aggregator are consistent with what we expect intuitively.\n\n**Scalability and Runtime Considerations** (*Question 3*). We focus on computational overhead of BayesMix(-Simple) RT as that's used in practice. The major extra cost compared to Full RT & Consensus RT is in fitting the bimodal GMM to obtain the aggregation function $g$. But this is negligible when compared to the training (backward & forward propagation) cost of every epoch, especially for large models. So our method doesn't introduce too much extra overhead. Note that even the AMP update rules for theory in Sec. 3 & 4 don’t introduce much extra overhead; the cost is dominated by the 2 matrix-vector multiplications involving $X$ and $X^\\top$.\n\nTheory for BayesMix RT is left for future work. \n\nWe hope to have resolved your concerns and questions, but we're happy to discuss further if needed. If you're satisfied with our responses, **we hope you will raise your score**!"}, {"review_id": "18vYDtgevG", "reviewer": "Reviewer_tTT7", "summary": "This paper addresses the problem of learning under noisy labels via retraining. Specifically, it investigates the optimal way to combine a model’s own predictions with noisy labels for binary classification, using the theoretical machinery of Approximate Message Passing (AMP). The authors derive the Bayes-optimal aggregator function for both Gaussian Mixture Models (GMMs) and Generalized Linear Models (GLMs), and analyze the iterative retraining dynamics through state evolution. They also propose a practical version for linear probing with binary cross-entropy loss, showing improved performance under high label noise.", "questions": "The authors claimed that this paper is the first work that addresses optimally using the predicted and given labels. To my knowledge, the following paper addresses how to combine the prediction and given labels to do label correction. \n\"SELC: self-ensemble label correction improves learning with noisy labels\"", "limitations": "The analysis and evaluation both restricted to binary classification with linear models. Broader empirical validation is necessary.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nTheoretical originality: The work provides the first principled derivation of optimal label aggregation in retraining using AMP. This paper addresses a key question on how to optimally combine labels and predictions.\n\nWeaknesses:\nThe analysis is restricted to binary classification with linear models. No results are presented for multi-class settings or nonlinear deep networks.\nThe evaluation is limited to two binary classification datasets with artificially injected noise. Broader empirical validation (e.g., on naturally noisy datasets) is needed.\nThe paper is heavy on derivations and could be difficult to follow for non-experts. Additional intuition, figures, or explanations would aid understanding.", "was_revised": true, "final_justification": "Thank you for the detailed response. The additional results and explanations have improved my understanding of the paper.", "rebuttal": "Thanks for your review and feedback! You have raised good points and we respond to your concerns and questions below.\n\n**Extension of theory to multi-class case.** This can be done by following similar ideas in the paper for the binary case, but will be heavier in notation and will involve more tedious analysis. Here we outline how this extension can be made for the GMM case in Section 3. We first describe the setting. We define a label matrix $Y \\in \\mathbb{R}^{n \\times k}$, where $n$ is the number of samples and $k$ is the number of classes, using one-hot encoding, where column $i$ has $1$ for the samples belonging to class $i$ and $0$ otherwise. Next, we define $M \\in \\mathbb{R}^{k \\times d}$ where row $i$ is the mean feature vector of class $i$. Equation (1) then transforms to $X = YM+Z$, where $Z$ is random noise; so this is a low rank matrix ($YM$ is of rank $k$) plus noise. We can then generalize the AMP iterations for this low-rank model. The forms of eqs. (4) and (5) in this case will be the same with $g_t$ redefined appropriately for the matrix case (here it will be applied row-wise instead of coordinate-wise). Also the coefficient $C_t$ in line 126 will now be a $k \\times k$ matrix, defined similarly using the Jacobian of $g_t$ instead of derivative. Likewise, the state evolution recursion (7) will be of the same form, with the modification that $m_t, \\sigma_t, \\bar{m_t}, \\bar{\\sigma}_t$ are now vectors of length $k$. The insights from the analysis will be similar but the analysis will be on multi-dimensional objects. A similar extension can be made for GLMs in Section 4, where $\\beta$ should now be defined as a matrix of size $k \\times d$. The extension here for the AMP iterates (16-17) and the state evolution (21) are similar to the GMM case described above.\n\n**Extension of theory to non-linear models.** We note that the AMP techniques can be used to analyze the statistical behavior of more general M-estimators (see for e.g., reference [14] in the paper). The corresponding update rule will involve applying the aggregator function (aggregating current predictions and the given noisy labels) as well as a gradient descent type of update (similar to eq. (4)). The exact details of these updates and the analysis will be quite tedious and are left for future work. \n\n**Extension in practice to different types of label noise (beyond uniform) and general ML models.** Although our theoretical results focused on linear models, the algorithm is Section 5 proposed for use in practice, i.e. BayesMix RT, is based on insights that carry over to general ML models. Specifically, eq. (27) is obtained by fitting a bimodal GMM on the distributions of the unnormalized logits (following the derivation in eq. (30) for theory). Following the same approach (and even in multi-class setting), we can rewrite the Bayesian posterior of the class memberships, after observing the current model's unnormalized logits with the prior based on the label noise model (in our paper, we have considered the uniform prior). We can then derive the corresponding aggregating function $g$ similar to eq. (27) in the paper. In short, *BayesMix RT can be used in deep learning models and even with non-uniform label noise priors* (e.g., when the flipping probability from class i to class j is some $p_{i, j}$). As an example, in the binary case, consider the **non-uniform noise model**: $\\mathbb{P}(\\hat{y} = -1| y = +1) = p$ and $\\mathbb{P}(\\hat{y} = +1| y = -1) = q$ with $p \\neq q$. Then, eq. (27) changes to:\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\Big(\\frac{q(1-q)}{p(1-p)}\\Big) \\Big(\\frac{p q}{(1-p)(1-q)}\\Big)^{\\hat{y}/2} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1.$$\nWe show a result under the above **non-uniform noise model** with $p=0.45$ and $q=0.2$ for the MedMNIST Pneumonia dataset in the same setting as Section 5 using the formula above for BayesMix RT; the table below lists the average *test* accuracies $\\pm$ standard deviation (over 3 runs) in this case. As we see below, **BayesMix RT performs the best**.\n\n|Iteration #| Full RT| Consensus-based RT| BayesMix RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|$71.85 \\pm 1.18$|\n|1| $78.21 \\pm 2.04$ | $77.51 \\pm 1.92$ | $\\textbf{81.14} \\pm 0.46$ |\n|10| $81.62 \\pm 2.16$ | $82.26 \\pm 2.36$ | $\\textbf{84.62} \\pm 0.73$ |\n\nFor more **general types of label noise** (e.g., sample-dependent noise) or in scenarios **where the noise model is not known**, we propose the following **simpler aggregation function** (instead of eq. (27)):\n$$g(z, \\hat{y}) = \\frac{2}{1+ \\gamma^{\\hat{y}} \\exp\\Big(\\frac{(z - \\mu_{+})^2}{2 \\sigma_{+}^2} - \\frac{(z - \\mu_{-})^2}{2 \\sigma_{-}^2}\\Big) \\frac{\\pi_-}{\\pi_+}} - 1,$$\nfor some constant $\\gamma \\in (0,1)$ which can be tuned. We call this simpler version **BayesMix-Simple RT** (everything else is the same as BayesMix RT in the paper); in our implementation, we set $\\gamma = 0.7$ throughout without any tuning. Also note that **this can be used with general ML models**.\n\n**(1)** To show the **efficacy of BayesMix-Simple RT**, we first consider an **adversarial noise model**. Specifically, an adversary gets to determine the \"important\" samples and flip their labels. The adversary determines the important samples by training the same model which will be trained by us *with clean labels* and orders the samples in the decreasing order of the absolute value of the unnormalized logits. Note that a higher logit absolute value implies that the model is very confident on the sample, so flipping the label of such a sample would be more detrimental to the model's training as it would need to adjust the decision boundary by a large amount for this incorrectly labeled sample. The adversary flips the labels of the top $\\alpha$ fraction of the samples with largest absolute values of the unnormalized logits. Under this **adversarial noise model** (we don't assume knowledge of this process in training to be clear) with $\\alpha=0.25$ for MedMNIST Pneumonia in the same setting as Section 5, we show the efficacy of **BayesMix-Simple RT** below compared to the baselines (again, the table below lists the average *test* accuracies $\\pm$ standard deviation over 3 runs). \n\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$63.94 \\pm 1.51$|$63.94 \\pm 1.51$|$63.94 \\pm 1.51$|\n|1| $66.83 \\pm 1.93$ | $66.77 \\pm 1.78$ | $\\textbf{67.15} \\pm 1.83$ |\n|10| $73.77 \\pm 0.79$ | $76.76 \\pm 2.51$ | $\\textbf{78.04} \\pm 1.98$ |\n\nWhile we did not have time to find and work with naturally noisy datasets, we believe the above result under adversarial noise clearly demonstrates the strength of our method. But in the future, we will test our algorithm on naturally noisy datasets as you suggested.\n\n**(2)** We now show the **efficacy of BayesMix-Simple RT** even for **deep network training**. Recall that our earlier experiments are for linear probing with a pre-trained ResNet-50. Specifically, here we consider *training an **entire** pre-trained ResNet-50*. Because of the heavy computational cost of training an entire deep network, we only do 3 iterations of retraining here. We show results for two cases of Food-101:\n\n**i.** *Pho vs. Ramen (just like in the paper) corrupted by uniform noise with $p=0.4$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$61.13 \\pm 3.39$|$61.13 \\pm 3.39$|$61.13 \\pm 3.39$|\n|1| $59.07 \\pm 5.44$ | $59.33 \\pm 4.83$ | $\\textbf{66.73} \\pm 3.72$ |\n|3| $57.67 \\pm 7.47$ | $58.47 \\pm 6.78$ | $\\textbf{70.67} \\pm 4.65$ |\n\n**ii.** *Spaghetti Bolognese vs. Spaghetti Carbonara (not in the paper) corrupted by non-uniform noise described above with $p=0.45$ and $q=0.2$*\n|Iteration #| Full RT| Consensus-based RT| BayesMix-Simple RT (ours)|\n|---|---|---|---|\n|0 (initial model)|$65.45 \\pm 2.22$|$65.45 \\pm 2.22$|$65.45 \\pm 2.22$|\n|1| $61.35 \\pm 7.31$ | $ 61.30 \\pm 4.48$ | $\\textbf{74.55} \\pm 3.75$ |\n|3| $56.50 \\pm 7.74$ | $59.70 \\pm 5.57$ | $\\textbf{80.30} \\pm 5.58$ |\n\nNote that in the above two tables (for entire ResNet-50 training), **BayesMix-Simple RT leads to significant gains** over the initial model, while Full RT and Consensus-based RT are actually detrimental.\n\n*So in summary, our proposed method is effective with different label noise models as well as for general ML models.*\n\nWhile we did not have enough time to concretely work on the multi-class case, *we believe our current contributions for binary classification are worthy and fundamental enough in their own right* and pave the way for the multi-class case in the future.\n\nWe agree our paper is pretty dense and math-heavy. We will provide some intuition about the theoretical results in the next version. We encourage you to take a look at our discussion for \"Interpretation of the Aggregator Function\" in our response to Reviewer NMag (sorry we couldn't include it here due to lack of space).\n\nThank you for pointing out the SELC paper; it is indeed relevant and we will cite it in the next version. However, please note that SELC is an empirical paper and it does not theoretically prove that their proposed method is optimal in any sense. On the other hand, our paper is primarily theoretical and our main goal is to derive the Bayes' optimal way to combine the given labels and the model's predictions for linear models. \n\nWe will add all this discussion in the next version of our paper. We hope to have resolved your concerns and questions, but we're happy to discuss further if needed. If you're satisfied with our responses, **we sincerely hope you will raise your score**!"}]

Author rebuttal:

Meta-review: This paper is focused on retraining—i.e. first training a predictor and then re-training that predictor on some combination of the data labels and the outputs from the predictions in the previous iteration. This paper analyzes the behavior of such rules in two cases: classification with binary isotropic GMMs, and GLMs more generally. In each case optimal retraining weights are derived under a model where the observed labels are the true ones with some probability of corruption. The reviewers appreciated this problem setting and contribution, so I recommend acceptance.

That said, I (the AC) have read this paper in depth and discussed it with the SAC. I suggest that the paper is in some respects currently quite sub-optimal as regards clarity. The mathematical writing is generally a bit sloppy. For example, here are some ways the paper might be improved:

- The justification for Equation 3 is quite sparse. This can be seen as exactly minimizing Σ_n ||x_n y_n - θ||^2, or "approximately" minimizing Σ_n ||y_n - θ^T x_n||^2. The given references also don't contain much justification.

- The scheme in Equations 4-5 seems to be off by a factor of \sqrt{n} when there is no label noise. This is explained as a result of being split between the two updates (for θ and y) but this doesn't quite seem to make sense—with zero noise, won't θ still be off by a factor of \sqrt{n}? This isn't considered a huge issue since classification error doesn't depend on the magnitude.

- Theorem 3.1 is a bit odd, on several grounds. First, equation 8 pertains to the average of some function \psi over the dimensions of θ. It's not entirely obvious why such an expectation is of interest or what features of the mean or (co)variance of θ or y could be recovered from this and no discussion is given. Second, the text above theorem 3.1 states that this describes the mean and variance of θ and y, but y does not appear in Equation 8 or 9.

- I (the AC) and the SAC were both initially confused by Eq. 13. It was not immediately obvious to us that this yielded a sensible update rule in the limit of zero noise. After consideration, we see that it does, but it's due to a relatively subtle relationship of the limit of p and \hat{y} that should be made explicit.

- It should be stressed more strongly that actually using the update rules requires knowledge of quantities like p, π, γ, which may not always be available in practice.
Decision: Accept (poster)