Towards Memorization Estimation: Fast, Formal and Free
Authors: Deepak Ravikumar
Efstathia Soufleri
Abolfazl Hashemi
Kaushik Roy
Venue: ICML 2025 poster (2025)
Keywords: Memorization
Learning Time
Primary area: deep_learning->everything_else

Abstract: Deep learning has become the de facto approach in nearly all learning tasks. 
It has been observed that deep models tend to memorize and sometimes overfit data, which can lead to compromises in performance, privacy, and other critical metrics.
In this paper, we explore the theoretical foundations that connect memorization to sample loss, focusing on learning dynamics to understand what and how deep models memorize. 
To this end, we introduce a novel proxy for memorization: Cumulative Sample Loss (CSL).
CSL represents the accumulated loss of a sample throughout the training process.
CSL exhibits remarkable similarity to stability-based memorization, as evidenced by considerably high cosine similarity scores. We delve into the theory behind these results, demonstrating that low CSL leads to nontrivial bounds on the extent of stability-based memorization and learning time. 
The proposed proxy, CSL, is four orders of magnitude less computationally expensive than the stability-based method and can be obtained with zero additional overhead during training. 
We demonstrate the practical utility of the proposed proxy in identifying mislabeled samples and detecting duplicates where our metric achieves state-of-the-art performance.

Towards Memorization Estimation: Fast, Formal and Free
Deepak Ravikumar' Efstathia Soufleri
Abolfazl Hashemi
Kaushik Roy!
Abstract
Learning Time
Deep learning has become the de facto approach in nearly all learning tasks. It has been observed that deep models tend to memorize and sometimes overfit data, which can lead to compromises in performance, privacy, and other critical metrics. In this paper, we explore the theoretical founda- tions that connect memorization to sample loss, focusing on learning dynamics to understand what and how deep models memorize. To this end, we introduce a novel proxy for memorization: Cu- mulative Sample Loss (CSL). CSL represents the accumulated loss of sample throughout the train- ing process. CSL exhibits remarkable similarity to stability-based memorization, as evidenced by considerably high cosine similarity scores. We delve into the theory behind these results, demon- strating that low CSL leads nontrivial bounds the extent of stability- based memorization and learning time. The proposed proxy, CSL, is four orders of magnitude less computationally expen- sive than the stability-based method and can be obtained with zero additional overhead during training. We demonstrate the practical utility of the proposed proxy in identifying mislabeled sam- ples and detecting duplicates where our metric achieves state-of-the-art performance.
Theorem 5.4 Cuml. Sample bounds Learning Time
Learning Time bounds
Theorem 5.3
Memorization
Theorem 5,5
Cuml. Sample Memorization bounds
Cuml. Sample Loss
Memorization
Figure 1. Visualizing our contributions linking cumulative sample loss to memorization and learning time.
fit to the training data. While some memorization is indeed needed to obtain generalization (Feldman, 2020), these deep models also memorize totally random images (Zhang et al., 2017). Thus to understand memorization, researchers have put in significant effort (Zhang et al., 2017; Arpit et al., 2017; Carlini et al., 2019a; Feldman & Vondrak, 2019; Feld- man & Zhang, 2020; Feldman, 2020). Such focus is crucial due to the broad implications memorization for multi- ple connected areas, including generalization (Zhang et al., 2021; Brown al., 2021), noisy learning (Liu et al., 2020), identifying mislabeled examples (Maini et al., 2022), recog- nizing rare and challenging instances (Carlini et al., 2019a), ensuring privacy (Feldman, 2020), and addressing risks from membership inference attacks (Shokri et al., 2017; Carlini et al., 2022; Ravikumar et al., 2024b).
1. Introduction
Many approaches to study memorization have been pro- posed (Carlini et al., 2019a; Jiang al., 2021; Feldman, 2020). Notably, the stability- Feldman (2020) measures the change in expected output probability when the sample under investigation is removed from the training dataset. This measure offers a robust theo- retical framework for understanding memorization, which was subsequently validated empirically for deep neural net- works (Feldman & Zhang, 2020). However, this approach is impractical for most applications due to its high computa- tional cost. Recent literature has introduced other proxies for memorization, such as learning time (Jiang et al., 2021). adversarial distance (Del Grosso et al., 2022), model confi- dence (Carlini et al., 2019b), and input loss curvature (Garg et al., 2024; Ravikumar et al., 2024a). While these proxies
Deep learning has become the de facto standard for almost all machine learning tasks from image (Ho et al., 2020) and text generation (Radford et al., 2019) to classification (Krizhevsky et al., 2009; Soufleri et al., 2024a) and rein- forcement learning (Shakya al., 2023). While they have been extremely successful, they tend memorize and over-
measure proposed by
'Department of Electrical and Computer Engineering, Purdue University, West Lafayette, U.S.A. Correspondence to: Deepak Ravikumar <dravikum @ purd.e.edu>>.
Proceedings of the 4dnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
LLnnk to the implementation: https://githhe com/ DeepakTatachar CSL.

---

Towards Memorization Estimation: Fast, Formal and Free
have been successful in understanding the memorization be- havior of neural networks, most fail to capture certain prop- erties of memorization such as bi-modality (Lukasik et al., 2023). Thus, establishing strong theoretical foundation of memorization and its proxies is of critical importance.
for scalars, T for vectors, and capital letters V for matri- ces. All constants are represented using Greek symbols (with two exceptions L and Tmax). For simplicity and com- pactness, we ignore the notation when vectors are in the subscript, for example V. = Vg. Consider a learning problem, where the task is learning the mapping f T + y where ã ~ X E R" and y ~ Y X E R. A dataset S = (3 22 2............................... 2m) TT consists of m samples, where each sample E (5e, Vi) Z. We also use a leave one out set which the the dataset S with the 7th sample removed denoted by S = (3 ,,,,,, -..,,.... ).). We use g ~ Gs to denote the function learnt by the neural network by the application of possibly random training algorithm A, on the dataset 5 where p ~ P denotes the randomness of the al- gorithm. Let the row vector wi =wit") _7(2) ,.... _6(1 ~ W denote the weights of a q-layered network at iteration (R)
While prior work (Ravikumar et al., 2024a) has investigated the properties of the loss function, such as input curvature post-training and its connection to memorization, we es- tablish theoretical framework that explains how learning dynamics drive the similarity between loss, memorization and learning time. We propose a new proxy for memoriza- tion: Cumulative Sample Loss (CSL) to capture information from training dynamics. CSL represents the loss of a sample accumulated over the entire training process. The proposed CSL proxy is 4 orders of magnituee less computationally expensive than stability- based (Feldman & Zhang, 2020) memorization and R /4x less expensive than input loss curvature (Garg et al., 2024). It is important to note that the 14x estimate is conservative. This is because CSL can be obtained for free during training, making the computational benefits even greater than these numbers suggest.
t, where wi(h) W1,1,1 W1,12 ... w Li,d, is a flattened row vector representing the weights of the hth layer at iteration with input dimension dę- and out- put dimension da. Now, consider single data sample zे- = [ [[ vector. Then, we represent a mini-batch with b exam- ples as a matrix X, = [ 322 responding labels are denoted as Y, = [y1 wll Thus mini-batch is denoted as 74 (Xp. Y8). A cost func- tion c RYnge(Y) x GYnge(Y) - RR,, is used to eval- uate the performance of the model. The cost at sample o is referred to as the loss l evaluated at 7, defined as ((g, &) = (āg)) y.). In some cases, the loss function may involve weights or parameters W7, such as when the model is parameterized by weights. In such cases, we may write the loss function as ( Z.). When working with a batch of data, the loss function can be extended to a batch of samples 7, (X,, Yb). In this case, the loss function may be written as l(w,, Zτ) where the loss for the batch is typically the av- erage or sum of the losses for the individual samples within the batch. Typically, we are interested in the loss of g over the entire data distribution, called the population risk, which is defined as R(g)) E. (g, ž)]. Since the data distribution Z is generally unknown, instead evaluate the empirical m risk as follows Ramp (g. S) Eis Elg, 2,, 2 E S.
(N)
T22 ... Tin represented as column
We validate our theory with experiments and show that the proposed proxy has very high cosine similarity with the memorization score from (Feldman & Zhang, 2020). Fur- ther, we show that CSL can be used to identify duplicates and mislabeled examples; notably, the adoption of our pro- posed proxy leads to achieving tfte-offthhear performance in these applications. In summary, our contributions are:
Zo/. whose cor-
We present a new theoretical framework that links learning dynamics (e.g. sample learning time) and memorization, to cumulative sample loss as visualized in Figure 1.
We propose a new memorization proxy: Cumulative Sample Loss (CSL), which demonstrates very high similarity to stability- memorization methods and is significantly more computationally efficient, offering a reduction in computational cost by several orders of magnitude.
We validate our theory through experiments deep vision models, demonstrating the efficacy of CSL as strong memorization proxy.
3. Background
Memorization of the 7th element Eة = (0 9:) in the dataset S by an algorithm A is as:
We showcase the practical applications of our proxy in identifying mislabeled examples and duplicates in datasets, achieving state-of-the-art performance in these tasks.
mem(S, 2,) (G.)) = vd --rrr (7:) = ys] (1)
where the probability is taken over the randomness of the algorithm A. This definition of memorization is the from Feldman (2020).
2. Notation
We denote distributions using bold capital letters V. ran- dom variables sampled from them as italic small letters v
p-Lipschitz Gradient, The gradient of the loss function &
2

---

Towards Memorization Estimation: Fast, Formal and Free
Learnt Late Hard, Atypical mem 0.67
100
10-2
Loss
10-4
Learnt Early Easy, Typical mem 0.0
Easy
10-6
Hard
100
10
10a
Epochs
Figure 2. Visualizing peacock class learning in ImageNet. Average loss is shown for casy and hard-to-lcarn peacocks. The dashed line represents average loss, while solid lines show actual loss. Easy images are less memorized, while hard images are memorized more.
is said to be p-Lipschitz on Range W) if, for all W7, Wl E Range( W), there exists a constant >> such that:
training (Shokri et al., 2017; Carlini et al., 2022; Ravikumar et al., 2024b). Learning dynamics has been used in this con- text to build stronger privacy tests. Liu et al. (2022) leverage loss trajectories and distilled models to improve MIA, while Li et al. (2024) propose SeqMIA, an attention- re- current architecture that exploits intermediate model states. Both approaches demonstrate how learning dynamics can reveal training-set membership but at the cost of increased computational overhead. Additionally, Nasr et al. (2021) highlights how mean loss trajectories can reveal privacy leakage under differentially private training establishing a lower bound on leakage identification.
((TT) V {112)) S p|| r22l
Bounded Gradient. Suppose that for each iteration i, the expected euclidean norm the gradient with respect to the parameters t is bounded by a constant i...
Es | [|
<
(3)
Uniform Stability of a randomized algorithm for some is defined as in Kearns & Ron (1997):
Learning Dynamics. Beyond privacy, learning dynamics have been studied as proxies for memorization. Mangalam & Prabhu (2019) showed simpler examples are learned first while mislabeled or difficult samples may be repeatedly for- gotten or relearned (Toneva et al., 2019; Pleiss et al., 2020; Maini et al., 2022). Jagielski et al. (2023) explored how memorization fades when examples are removed. Carlini et al. (2019a) combine multiple metries to understand data retention, and Jiang et al. (2021) introduce the C-score to capture hard examples. Other works have proposed loss- sensitivity (Arpit et al., 2017), and sharpness of the loss function (Krueger et al., 2017) as memorization signals. More recently, Garg et al. (2024) used input loss curva- ture as a proxy for stability based memorization (Feldman, 2020), supported by theoretical analysis from Ravikumar et al. (2024a). In contrast, this paper investigates sample loss over training and its formal link to learning time and memorization.
[(g's 3)
Ligs... 3)
Vi E
(4)
I.-Bounded Loss. We say that loss a loss function is I.- bounded if it satisfies
4. Related Work
Memorization in deep neural networks has gained attention, with recent works improving our understanding of its mech- anisms and implications (Zhang et al., 2017; Arpit et al., 2017; Carlini et al., 2019a; Feldman & Vondrak, 2019; Feld- man, 2020; Feldman & Zhang, 2020; Lukasik et al., 2023; Garg et al., 2024; Ravikumar al., 2024a). This research is driven by the need to understand generalization (Zhang et al., 2017; Brown et al., 2021; Zhang et al., 2021; Kaplun et al., 2022; Bayat et al., 2025), identify mislabeled ex- amples (Pleiss et al., 2020; Maini et al., 2022), and detect out-of-distribution or rare sub-populations (Carlini et al., 2019a; Ravikumar al., 2023; Pezeshki al., 2023). Ad- ditionally, memorization impacts robustness (Shokri al., 2017: Carlini et al., 2022), unlearning (Kurmanji et al., 2023; Kodge et al., 2024) and privacy (Feldman, 2020; Soufleri et al., 2024b).
5. Learning Dynamics and Memorization
5.1. Proposed Memorization Proxy
To build intuition, let us explore the loss progression of two samples, namely, "easy" and "hard" example, both from the same class (peacock) in the ImageNet dataset (Rus-
Privacy is often tested using membership inference attacks (MIA), which tests whether a particular sample was used in
3

---

Towards Memorization Estimation: Fast, Formal and Free
sakovsky et al., 2015), as illustrated in Figure 2. In this context, loss refers to the per-sample cross-entropy loss, which tracks how well the model predicts a specific exam- ple at each epoch of training.
the average per iteration sample gradient norm falls below threshold r. Note that the approximation is justified by the law of large numbers. Using this idea we formally define the learning time Ts, of sample Σ = (æ,, vi) as the smallest time T at which the sample learning condition is satisfied. Formally:
In Figure 2, let's observe the behavior of an easy sample, represented by the loss visualized in green. This sample is learned early in the process. The loss follows a simple pattern: it starts high, quickly drops, and stays low for the rest of the training. The hard sample, on the other hand, behaves differently. Its loss remains high for much longer period before eventually dropping, indicating that is learned much later. This contrast in loss dynamics' patterns evidently shows how the cumulative sample loss throughout training can distinguish between easy and also illustrates that using thresholds (i.e. loss threshold) to define learning time and forgetting time, is less effective. This is because learning is a noisy process, i.e. a sample might be learnt in one epoch, unlearnt in the next. Thus traditional proxies which rely on thresholds to determine when a sample is learnt, may fall short of distinguishing between easy and hard examples. To overcome this noise, we propose using cumulative sample loss, CSL as more reliable proxy. The proposed proxy CSL of sample o can be formally defined as:
)1 S ( } }
T: min
T:
1 T
Σ t=0
where T > 0 is a predefined threshold that determines the acceptable magnitude of the average gradient norm. While non-intuitive, as we will demonstrate, this formulation of sample learning condition and learning time simplifies the mathematical expressions and analyses.
the definitions
hard examples with precision. Figure 2
5.3. Input Gradient Convergence
In this section, we analyze the evolution of input-space gradients during training. Specifically, we demonstrate that the norm of the gradient with respect to the weights bounds the norm of the gradient with respect to the input, ensuring convergence of the input gradient. Consequently, the sample learning condition defined in Eq. also converges. To establish this, we examine the gradient of the loss function with respect to sample, and relate it to the gradient with respect to the network weights.
Tmaz Σ t=
CSL(Z)) =
f(wi, E,)
(5)
Lemma 5.1 (Input gradient norm is bound by weight gradi- ent norm). For any neural network, given a mini-batch of inputs Zo = (Xp. Yo), the Frobenius norm of the gradient of the loss E with respect to the input is bounded by the norm of the gradient with respect to the network's 's weights wr Specifically:
where Tmax is the total number of iterations of SGD. This smooths out the noise from fluctuations during learning. As we will demonstrate, hard examples tend to be memorized by the model, while easy examples are likely generalized; the proposed cumulative proxy, tracked throughout the train- ing process, is key to capturing this correlation.
IVv Z S kg V w. (1 Zo)l
(8)
where hig = "Ie 11xx,,)*1l 11 and sp denotes the smallest singular value of =X (XT))* yt, where" + denotes pseudo- inverse.
sp
5.2. Learning Condition and Learning Time
To formalize this intuition, we introduce the concept of the sample learning condition. In optimization theory, the neces- sary condition for optimality for an unconstrained problem is typically expressed as V., ( = 0. In the case of opti- mizers like gradient descent or its extensions, convergence is typically characterized terms of gradient norm given as I m. l(ux))l22 S r, where é is the function minimize and r denotes an arbitrarily small threshold. Thus, as extension of this perspective, we define the sample learning condition as:
Sketch of Proof. The proof utilizes the chain rule to com- pute the gradients of the loss with respect to the inputs and the with respect to first-layer weights, establishing the rela- tion between the two. By leveraging the Frobenius norm, the proof establishes an upper bound on the gradient with respect to the inputs in terms of the gradient with respect to the weights. The proof is available Appendix C.I.
For convenience we group set of assumptions as SGD Convergence Assumptions. The convergence of SGD in gradient norm holds under the p-Lipschitz continuity of the loss function (Eq. 2), with a bounded variance norm (Eq. 16) and an unbiased gradient estimator.
ER [IV E (1) R T
Σ V.
(
ST.
(6)
where the gradient is with respect to the input Z.. We inter- pret Equation 6 as follows: A sample is considered learnt if
Theorem 5.2 (Convergence in input gradient norm). Under the SGD convergence assumptions, after T iterations of
4

---

Towards Memorization Estimation: Fast, Formal and Free
SGD with a learning rale ll 1/vT, the sample learning condition converges as follows:
follows that the expected memorization of samples in this subset is bounded by their learning times. Given that
1 T T = (1/VT)
pI 2L
TH
(9)
RT
20
Kmm L
where fim = max (x²)), it can be assumed that Kr is constant across different subsets (T). Thus, we can state that for any sample 2; E U (T). the expected memorization Es, [mem((2) follows
Sketch of Proof. The proof starts with SGD convergence analysis. Subsequently, using Lemma 5.1, the proof relates the weight gradient to the imput gradient through scaling factor that depends on kg. By de-telescoping the result over iterations, it follows that the cumulative input gradient is bounded by the cumulative loss decrease and term depend- ing on the learning rate, Lipschitz constant and iterations T. Using 7) = 1/VT we see that the cumulative input gradient. converges in O(I/VT). Full proof is in Appendix D.I.
E,, ( S KKTT + B/L
In simpler terms, this means that if a group of samples is learned early in the training process (i.e., they have smaller learning times), their expected memorization will also be lower compared to samples that are learned much later during training. This provides an intuitive link between learning time and the extent of memorization, suggesting that samples requiring more training time more likely to be memorized. Additionally, it can be demonstrated that Theorem 5.3 holds true for cross-entropy loss, by set- ting L = (see proof in Appendix D.2.1). Further, under reasonable generalization assumption Er,,, [d(wão: z
Discussion. The theorem establishes the convergence of the sample gradient norm when using SGD. It shows that the input gradient converges in a manner similar to the weight gradient. The difference being the upper bound has a dependence on the scaling factor Kg from Lemma 5.1.
Takeaways. (1) The big takeaway is that when we train model, even though don't i optimize in the input space, we do indirectly optimize it. (2) Sample learning condition (Eq. 6) is guaranteed to converge.
g*= (w" [[)] 2 O, the requirement for stability can be dropped (see discussion in Appendix D.2.2), leading to:
5.4. Learning Time, CSL and Memorization
Es, |memm (Z)) S Kr Ez.p [Tz.]
(11)
Theorem 5.3 (Learning Time bounds Memorization). Un- der the assumptions of SGD convergence, B-stability and L-bounded loss, there exists a KT > 0 such that the expected learning time for a sample o, bounds expected memorization score, i.e.
Theorem 5.4 (Cunulative loss bounds learning time). Let the assumptions for SGD convergence hold. Then, for any L-bounded loss, the learning time for any sample Σ S there exist KT >> O such that:
Ex; [CSL(E) -
KT Ez, [T:.] S
(12)
Ez, [em( S FT Ez.p [Tx]] + B/L,
(10)
L
where p denotes the randomness of the algorithm.
where & is an offset to scale CSL into the correct range.
Sketch of Proof. The key idea is to leverage the Theorem 5.2 to derive a closed-form expression for learning time. The proof begins by relating Ts, to the cumulative reduction in loss over training steps. The loss dynamics decomposed into two terms: the memorization score, and a residual term capturing the generalization gap. By analyzing these compo- nents and taking expectations over the data and randomness of the training process, it is shown that the expected learning time scales with the memorization score. The full proof is available in Appendix D.2.
Sketch of Proof. The proof begins by leveraging the input gradient convergence result (Theorem 5.2), which allows us to derive an expression for the learning threshold r. By rear- ranging this result, we establish a direct connection between Ty and CSL, demonstrating that the learning time scales with the cumulative sample loss. To refine this relationship. we define & as an offset representing the aggregate lower bound of the cumulative loss. Finally, by combining these results, we show that the expected learning time is propor- tional to the expected cumulative sample loss. The proof detailed in Appendix D.3. Additionally, this theorem holds for any unbounded loss with by setting L (see proof in Appendix D.3.
Interpreting Theory. Theorem 5.3 intuitively states that the expected memorization of group of samples is proportional to their expected learning times. To make this clearer, con- sider subset U'T)) C S, where UT) = { Te. < T}, meaning U (T) contains all samples that are learned within a time threshold T. From the relationship between mem- orization and learning time established in Equation 10, it
Interpreting Theory. The theorem highlights that the learn- ing time for a sample is directly tied to its Cumulative Sample Loss (CSL), which quantifies the total loss over time. This makes it possible to compare different subsets
5

---

Towards Memorization Estimation: Fast, Formal and Free
of samples based on their CSL and understand how it af- fects their learning time. & is offset such that CST is in the correct range, this is more clear when considering the result for memorization (see Theorem 5.5), we observe that & scales CST. so that it lies in the range R (0, 1) when s 0 (see more detailed discussion in Appendix D.3.2). To build intuition, consider a subset (C) S S, defined as UCC)= {& : (2) I C}. According to Theorem 5.4, which applies to any subset, the following holds:
established that SGD methods are uniformly stable (Hardt et al., 2016), supporting the plausibility of our assumptions stability (Eq. 4). Virmaux & Scaman (2018) provides general upper bound for the Lipschitz constant of any differentiable deep learning model, validating the Lipschitz continuity assumption in the context of deep models. The assumptions of an unbiased gradient estimator, along with bounded gradient norm, are widely used in the optimization literature (Ghadimi & Lan, 2013; Aketi et al., 2024), making these assumptions reasonable. In practice, loss functions are often upper-bounded. Additionally, our results apply to cross-entropy with minor changes as specified.
E,, C-
L
Here 5' is the minimum & across various subsets, thus ç' is the same across all subsets. Hence, we can compare subsets by their CSL: subsets with lower CSL will have shorter learning times. In simpler terms, if one group of samples hus lower CSL than another, they are expected to be learnt earlier during training. If the bounds are accurate, this rela- tionship is close to linear, meaning lower CSL consistently leads to shorter learning times.
Key Theory Takeaways. If the theory bounds are tight, we expect the following: (1) learning time to exhibit linear relationship with CSL, (2) stability-based memorization to also follow linear relationship with CSL, and (3) linear relationship between learning time and memorization.
6. Experiments
Theorem 5.5 (Cumulative Sample Loss bounds Memoriza- tion). Assume the loss function is L-bounded, and the as- sumptions for the convergence of SGD and B-stability hold. Then, the expected memorization score of any sample o, E S satisfies the following inequality:
6.1. Validating Theory
In this section, we conduct experiments to empirically val- idate the theoretical relationships established in the paper. Specifically, we investigate the following connections: (I) the relationship between learning time and our proxy CSL (Cumulative Sample Loss), (2) the relationship between memorization and learning time (3) the relation between CSL and memorization.
Ex, [mem( (2)) Ex,, [CSL(Z)) + 3 g
8
< 1
L
I
(13)
where p denotes the randomness of the algorithm.
Experiment. We trained a ResNet18 model on the CIFAR- 100 and ImageNet datasets, measuring learning time and CSL for each training sample. For memorization scores, we used precomputed stability-basee -aaledty--aeed scores from Feldman & Zhang (2020). To analyze the relationship between the CSL, learning time and memorization, we created binned scatter plot. Since the theorems apply to groups of samples (i.e. under expectation), we grouped data by the x-axis metric and calculated average scores for each bin. For instance, in Figure 3, samples are grouped by memorization scores on the x-axis, and the average learning time for each bin is plotted to generate the scatter plot (additional details are provided in Appendix B.4).
Sketch of proof. The proof connects memorization to CSL using Theorems 5.3 and 5.4. By taking the expectation over the algorithm's randomness in Theorem 5.4 and using it to bound Theorem 5.3, the result follows. The proof is provided in Appendix D.4.
Interpreting Theory. Consider a subset UCC C S where UCC) = {% CSL( & C}. For any two such sets, the set with a higher CSL likely to contain more memorized examples. In simpler terms, if one group of samples has lower CSL than another, it is expected to be less mem- orized and learned earlier during training. If the bounds from this theorem are tight, we can expect a linear rela- tionship between learning time and memorization. Under a reasonable generalization assumption, similar to Eq. 11, memorization is shown to be bounded by normalized CSL, which is upper-bounded by 1. This demonstrates that the CSL bound is non-trivial. Additionally, for cross-entropy loss the following holds true (details in Appendix D.4.1):
Results. The results are visualized in Figures 3, 4, 5, 6, 7, and 8. Figures 3 and 6 illustrate the relationship be- tween learning time and memorization for CIFAR-100 and ImageNet respectively, validating Theorem 5.3. Figures and 7 plot learning time versus CSL for CIFAR-100 and ImageNet, respectively, supporting Theorem 5.4. Figures 5 and 8 compare the memorization score from Feldman & Zhang (2020) with CSL for C1F and ImageNet, respectively, validating Theorem 5.5..
Es (mem(z)) S E.., [CSL(E) + 8 - (14)
Remark on Assumptions. We briefly and qualitatively evaluate the practicality of our assumptions. It has been
Takeaways. Theorems 5.3-5.5 establish bounds under ex- pectation over groups of samples, describing the relation-
6

---

Towards Memorization Estimation: Fast, Formal and Free
CIFAR-100
CIFAR-100
CIFAR-100
0.8
200
X
150
Leurning Time
0.6
150
0.4
CSL
100
4
4
CSL
100
X
X
x
0.2
K
Avg. Mem Score
Leariing Time
Avg. Mcm Score
Figure 3. Learning Time Memorization
Figure Learning time vs. CSL the CIFAR-100 datasct.
Figure 5. Memorization CIFAR-100 dataset.
CSL
score on CIFAR-100 100 dataset.
ImageNet
ImageNet
ImageNet
0.7
500
Learning Time
600
0.6
400
0.5
300
400
0.4
200
0.3
100
200
0.0
0.2
0.4
0.5
6,8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.6
1.0
Avg. Mcm Score
Learning Time
Avg. Mcm. Score
Figure 6. Learning Time Memorization score on ImageNet dataset.
Figure 7. Learning time vs. CSL on the ImageNet dataset.
Figure 8. Memorization score vs CSL on ImageNet dataset.
ship between learning time, memorization, and cumulative sample loss. Figures 3 to 8 illustrate these relationships, showing an almost linear trend that suggests the bounds from the theorems are likely tight. The slight non-linearity between learning time and memorization likely arises from the theoretical assumption of uniformly bounded loss, while the cross-entropy loss used in practice does not have uni- form bound across all subpopulations (see Ravikumar al. (2024a) for related discussion).
ples and the Top-K memorized examples. "Top 5K" refers to the 5,000 most memorized examples, identified using Feldman Zhang (2020), for which the cosine similarity is reported. For ImageNet, CSL proves to the superior proxy. On top 5k CIFAR- loss sensitivity has a slight edge over CSL. However, across all examples, CSL signif- icantly outperforms other methods. Figure 9 plots the L2 adversarial distance against both the memorization score and CSL for the CIFAR-100 100 dataset. Both exhibit similar trends: as memorization and CSL decrease, larger adversar- ial perturbations (i.e., greater distances) are required to flip the network's prediction.
6.2. Similarity with Memorization
Experiment. In this section, we examine how well our proposed proxy CSL correlates with the memorization score defined by Feldman Zhang (2020). We also compare our proxy with those proposed by Garg al. (2024), loss sensitivity (Arpit et al., 2017), forgetting frequency (Toneva et al., 2019), and final sample loss. This experiment trains an Inception model on CIFAR-100 100 and a ResNet50 model on ImageNet, using the same architectures as Feldman & Zhang (2020). For each dataset, we compute the memoriza- tion proxies and measure their cosine similarity with the memorization scores publicly made available by Feldman & Zhang (2020). This setup mirrors the approach used in Garg al. (2024). Additionally, to capture another aspect of memorization, we plot the L2 adversarial distance against both the memorization score and CSL. for the CIFAR-100 dataset. Please see Appendix B.1 for more setup details.
Takeaways. CSL serves an effective proxy for memoriza- tion, demonstrated on both the CIFAR- 100 and ImageNet datasets. Results across architectures (see Appendix B.2) confirm that these findings are consistent across architec- tures. CSL is computationally efficient, it is approximately 14x faster than curvature and 4 orders of magnitude faster memorization. A breakdown of com- pute costs provided in Appendix B.3. Additionally, CSL also captures the bimodal property (Lukasik et al., 2023) of memorization, shown in Figures 12 and 13.
than stability-
7. Theory to Practice
7.1. Mislabeled Detection
Experiment. In this section, we leverage insights from our theoretical framework to develop practical method for detecting mislabeled examples in training datasets.
Results. The results Table compare the cosine similarity between the proxies and sets of examples: all exam-

---

Towards Memorization Estimation: Fast, Formal and Free
Mem. and CSL vs, Adversarial Distance
41874 Otter
27737 Snake
16646 Mouse
46418 Willow
25347
Lion
9012 Otter
30418 Spider
43843
Shrew
500
0.6
400
46752
33638 Otter
23947 Seal
12702 Worm
31227 Whale
8393 Girl
31828 Shrew
10968 Snake
Worm
0.4
Memorization
300
36874 Baby
16461
7358
15750
34187
25858 Shrew
47806
16012
200
ChimpaaneeWWaale
0.2
100
22965
32828
12946 Apple
19639 Kangaroo
31128 Seal
14651 Turtle
1000 Orchid
3282 Osk
Raccoon
Maple
0.0
0.0
2.5
5.0
7.5
10.0
12.5
Adversarial Distance
Figure 10. 32 highest scores for CSL on clean CIFAR- 100 reveal confficting labels, such Crab and Spider outlined in red.
Figure 9. L2 Adversarial distance vs Mem. score (Feldman & Zhang, 2020) and CSL on CIFAR-100. Clearly, memorization and CSL increases for less robust samples (i.c. lower adv distance |ppl2) Thus CSL captures similar properties memorization
Under the Receiver Operating Characteristic (AUROC) met- ric, which measures the ability each method to correctly identify mislabeled examples under different noise condi- tions. Additional details of the experiments and the baseline techniques available in Appendix B.1 and B.5.
Table 1. CSL correlation and similarity with memorization com- pared other methods across CIFARR-10 and ImageNet datasets.
CS denotes cosine similarity and PC denotes Pcarson correlation.
The results are presented in Table 2, showcasing the performance of each method on CIFAR-10 and CIFAR- 100 at symmetric label noise levels of 1 1,, 2%, 5%, and 10%.
Results.
Dataset
Arch.
Subset
Method
CS
PC
The term Thr. LT (Threshold based Learning Time) refers to the first epoch at which a sample is correctly classified (Jiang et al., 2021; Maini et al., 2022), reflecting the epoch at which the model learns particular sample.
Final Sample Loss
0.33
0.06
Curv
0.87
0.16
Top 5k
Loss Sensitivity
0.97
0.39
CIFAR-100 100
Inception
Forget Freq.
0.96
0.29
CIFAR-
CSL (Ours)
0.93
0.40
Takeaways. The proposed CSL proxy consistently out- performs other methods in detecting mislabeled examples across various label noise levels ranging from 1% to 10%.
Final Sample Loss
0.24
0.17
Curv
0.69
0.49
All
Loss Sensitivity
0.81
0.76
Forget Freq.
0.76
0.59
Compute Cost. CSL incurs no additional computational overhead, unlike Confidence Learning (CL) (Northcutt et al., 2021), which requires training multiple models (3-folds in this case), significantly increasing cost. SSFT (Maini et al., 2022) approximately doubles training cost by training on two subsets, while input loss curvature demands 14 X more compute than CSL. Given that CSL and Thr. LT exhibit comparable computational costs, the superior performance and efficiency of CSL make a highly compelling choice.
CSL (Ours)
0.87
0.79
Final Sample Loss
0.78
0.12
Curv
0.84
0.05
Top 50k
Loss Sensitivity
0.79
0.04
ImageNet
Res
Forget Freq
0.68
0.15
CSL (Ours)
0.94
0.21
Final Sample Loss
0.64
0.50
Curv
0.62
0.33
All
Loss Sensitivity
0.49
0.17
Forget Freq.
0.49
0.04
CSL (Ours)
0.79
0.64
7.2. Duplicate Detection
Experiment. In this section, we apply the proposed memo- rization proxy to identify duplicate examples the dataset, We conduct two types of analysis: first, qualitative anal- ysis of duplicate detection on the unmodified CIFAR-100 dataset; second, quantitative experiment where we in- tentionally introduce duplicates (250 duplicates) into the dataset and use our proxy to identify them. We use a ResNet18 (He et al., 2016) model for this experiment, and the performance of our method is evaluated against other
evaluate the effectiveness of our approach by comparing it to several state-of-the- methods for label error detec- tion. The experiments are conducted on CIFAR-10 and C00,R-100, where varying levels of symmetric label noise are introduced. Specifically, labels are randomly flipped to another class, uniformly across all classes, excluding the true label. To assess performance, we employ the Area
8

---

Towards Memorization Estimation: Fast, Formal and Free
Table 2. Evaluating the performance of mislabeled detection of the proposed framework against existing methods on CIFAR- 10 and CIFAR- 100 datasets under various levels of label noise.
Dataset
Method
% Noise
2% Noise
5% Noise
10% Noise
Thr. Learning Time (LT)
0.4951 + 0.0248
0.4954 + 0.0044
0,4911 + 0.0071
0.4948 + 0.0057
Conf. (Carlini et al., 2019a)
0.8781 + 0.0177
0.8072 + 0.0130
0.7254 + 0.0214
0.6528 + 0.0042
CL (Northcutt et al., 2021)
0.8651 = 0.0127
0.8905 + 0.0115
0.8874 = 0.0019
0.8551 = 0.0030
SSFT (Maini et al., 2022)
0.9626 = 0.0018
0.9551 + 0.0020
0,9498 = 0.0042
0.9360 = 0,0020
CIFAR-10
Curv. (Garg et al., 2024)
0.9715 = 0.0045
0.9776 + 0.0033
0.9800 = 0.0003
0.9819 + 0.0006
CSL (Ours)
0.9845 + 0.0026
0.9864 + 0.0004
0.9870 = 0.0003
0.9869 = 0.0005
Thr. Learning Time (I.T)
0.5256 + 0.0012
0.5227 0.0100
0.5161 + 0.0051
0.5203 + 0.0029
In Conf. (Carlini et al., 2019a)
0.7258 = 0.0102
0.7236 + 0.0047
0.7069 = 0.0069
0.6884 = 0.0053
CL (Northcutt et al., 2021)
0.8723 = 0.0208
0.8838 + 0.0006
0.8733 = 0.0010
0.8536 = 0.0006
SSFT (Maini et al., 2022)
0.8915 = 0.0045
0.8893 + 0.0013
0.8784 = 0.0030
0.8664 = 0.0024
CIFAR-100
Curv. (Garg et al., 2024)
0.9856 + 0.0009
0.9865 + 0.0011
0.9876 + 0.0021
0.9892 = 0,0012
CSL (Ours)
0.9891 + 0.0003
0.9895 + 0.0002
0.9895 = 0.0001
0.9897 0.0001
Table Result of duplicate detection using the proposed methods and other baselines on CIFAR- 10 and CIFAR- 100 datasets.
We validate our framework through extensive experiments and show its practical applications in identifying mislabeled examples, and duplicates in datasets. The proposed proxy achieves state-of-the-ar performance in identifying dupli- cate and mislabeled examples. By offering efficient tools to understand memorization, our framework can lead to more interpretable models across various machine learning tasks.
Method
CIFAR-10 10
CIFAR- 100
Thr. LT
0.7029 + 0.0058
0.7419 + 0.0059
In Conf.
0.9237 + 0.0114
0.8623 1: 0.0131
CL
0.5533 + 0.0031
0.5873 0.0090
SSFT
0.8490 + 0.0034
0.7938 + 0.0045
Curv.
0.9536 + 0.0030
0.9639 + 0.0030
A Acknowledgements
CSL (Ours)
0.9821 + 0.0006
0.9886 + 0.0008
This research was supported in part by the Center for the Co-Design of Cognitive Systems (COCOSYS), a DARPA- sponsored JUMP center, the Semiconductor Research Cor- poration (SRC), the National Science Foundation (NSF), and Collins Aerospace. The authors gratefully acknowl- edge the valuable feedback provided by Jimmy Gammell earlier drafts of this manuscript.
techniques using AUROC (see Appendix B.1 for details).
The qualitative analysis results are presented in Figure 10, which demonstrates the detection of duplicates in the clean CIFAR- dataset. The quantitative experimental results are provided in Table 3, where we report the AUROC scores for our method compared to other techniques.
Results.
Takeaways. As shown in Figure 10, CSL effectively iden- tifies the majority of duplicates in the unmodified CIFAR- 100 dataset. This is further validated in Table 3, where we evaluate the performance of the method after inten- tionally introducing duplicates. Here, we observe that CSL consistently achieves the best performance identify- ing duplicates across both the CIFAR-10 and CIFAR-100 datasets. To improve reproducibility, we have provided the code for all the experiments at https: thub. com/ TarpaaaTttacaar/..
Impact Statement
The research presented this paper significantly advances our understanding of memorization in deep learning models by introducing Cumulative Sample Loss (CSL) as a novel proxy for quantifying memorization. This work establishes strong theoretical foundation connecting CSL to sample loss and stability- -base memorization, demonstrating that CSL bounds stability-based memorization and learning time. By offering a proxy that is four orders of magnitude more computationally efficient than stability-based methods and incurs zero additional training overhead, this paper provides practical and scalable tool for understanding and address- ing memorization in deep models. This research not only deepens the theoretical comprehension of learning dynam- ics in deep models but also delivers actionable insights for improving training efficiency, robustness, and model quality. It offers transformative potential for fields reliant on deep learning, particularly in applications where data quality and computational efficiency paramount.
8. Conclusion
This paper provides a comprehensive theoretical framework that connects memorization proxy, CSL, to learning time and stability-based memorization. We formalize the notion of learning time and our results demonstrate that CSL is not only highly effective in capturing memorization be- havior but also computationally efficient, being four orders of magnitude faster than existing stability-based metries.

---

Towards Memorization Estimation: Fast, Formal and Free
References
estimation. Advances in Neural Information Processing Systems, 33:2881-2891, 2020.
Aketi, S. A., Hashemi, A., and Roy, K. Global update tracking: A decentralized learning algorithm for hetero- geneous data. Advances in neural information processing systems, 36, 2024.
Garg, I., Ravikumar, D., and Roy, K. Memorization through the lens of curvature of loss function around samples. In Forty-first International Conference on Ma- chine Learning, 2024. URL https: /ttp://///eeeiieeeeeeeeeeeeeeeee net/forum? Wopp:dddwwooyyyyyyor
Arpit, D., Jastrrebssii, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj. T., Fischer, A., Courville, A., Bengio, Y., et al. A closer look at memorization in deep networks. In International conference on machine learning, pp. 233 232. PMLR, 2017.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):334-2238,, 2013.
Bayat, R., Pezeshki, M., Dohmatob, E., Lopez-Paz, D., and Vincent, P. The pitfalls of memorization: When memorization hurts generalization. In The Thirteenth International Conference on Learning Representations, 2025. URL 90wwhhZh22pTM.
Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In Inter- national conference machine learning, pp. 1225-1234 PMLR, 2016.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778. 2016.
Brown, G., Bun, M., Feldman, V., Smith, A., and Talwar, K. When is memorization of irrelevant training data necessary for high-accuracy learning? In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pp. 123-132, 2021.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems, 33:6840-6851, 2020.
Carlini, N., Erlingsson, U., and Papernot, N. Distribution density, tails, and outliers in machine learning: Met- rics and applications. arXiv preprint 1910:191..1444 2019a.
Jagielski, M., Thakkar, O., Tramer, F., Ippolito, D., Lee, K., Carlini, N., Wallace, E.,, Song, S., Thakurta, A. G., Papernot, N., and Zhang, C. Measuring forgetting of memorized training examples. In The Eleventh In- ternational Conference on Learning Representations, 2023. URL https: http:////ppeeeeeee//mmoo net forum? dd=7bJizxLKrs
Carlini, N., Erlingsson, U., and Papernot, N. Prototypical examples in deep learning: Metrics, characteristics, and utility, 2019b.
Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., and Tramer, F. Membership inference attacks from first prin- ciples. In 2022 IEEE Symposium Security and Privacy (SP), pp. 1897-1914. IEEE, 2022.
Jiang, Z., Zhang, C.,, Talwar, K., and Mozer, M. C. Charac- terizing structural regularities of labeled data in overpa- rameterized models. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 5034-5044. PMLR, 18-24 Jul 2021. URL http:: htt: https////ccocccepeeeeeeee mlr mir.press/ html.
Del Grosso, G., Jalalzai, H., Pichler, G., Palamidessi, C., and Piantanida, P. Leveraging adversarial examples to quantify membership information leakage. In Proceed- ings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 10399-10409, 2022.
Kaplun, G., Ghosh, N., Garg, S., Barak, B., and Nakkiran, P. Deconstructing distributions: A pointwise framework of learning. arXiv preprint arXiv:2202.09933 2022.
Feldman, V. Does learning require memorization? a short tale about long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 954-959, 2020.
Kearns, M. and Ron, D. Algorithmic stability and sanity- check bounds for leave-one-our cross- valsssstliit.on.. In Pro- ceedings of the tenth annual conference on Compula- tional learning theory, pp. 152-162, 1997.
Feldman, V. and Vondrak, J. High probability generaliza- tion bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pp- 1270-1279. PMLR, 2019.
Kodge, S., Ravikumar, D.. Saha, G., and Roy, K. Verifix: Post-training correction to improve label noise robustness with verified samples. arXiv preprint arXiv:2403.08615 2024.
Feldman, V. and Zhang, C. What neural networks mem- orize and why: Discovering the long tail via influence
10

---

Towards Memorization Estimation: Fast, Formal and Free
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images, 2009.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., al. Language models unsupervised multitask learners. OpenAl blog, 1(8)9, 2019.
Krueger, D., Ballas, N., Jastrzebski, S., Arpit, D., Kanwal, S., Maharaj, T., Bengio, E., Fischer, A., and Courville, A. Deep nets don't learn via memorization. In ICLR Workshop, 2017.
Ravikumar, D., Kodge, S., Garg, I., and Roy, K. Intra-class mixup for out-of-distribution detection. IEEE Access, 11: 25968-25981, 2023.
Kummanji, M., Triantafillou, P., and Triantafillou, E. To- wards unbounded machine unlearning. arXiv preprint arXiv:2302. 09880, 2023.
Ravikumar, D., Soufleri, E., Hashemi, A., and Roy, K. Unveiling privacy, memorization, and input curvature links. In Forty-first International Conference on Ma- chine Learning, 2024a. URL https:: /oppn//////....e.. net/
Li, H., Li, Z.., Wu, S., Hu, C., Ye, Y., Zhang. M., Feng. D., and Zhang, Y. Seqmia: Sequential-mete metric based member- ship inference attack. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pp. -5100, 2024.
Ravikumar, D., Soufleri, E., and Roy, K. Curvature clues: Decoding deep learning privacy with input loss curva- ture. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b. URL https: / // /oopeneevew..oo
Liu, S., Niles-Weed, J.. Razavian, N., and Fernandez- Granda, C. Farly-learning regularization prevents memo- rization of noisy labels. Advances in neural information processing systems, 13:20331-203444 2020.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211-252 2015. doi:
Liu, Y., Zhao, Z., Backes, M., and Zhang, Y. Membership inference attacks by exploiting loss trajectory. In Proceed- ings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2085-2098, 2022.
10.
Lukasik, M., Nagarajan, V., Rawat, A. S., Menon, A. K., and Kumar, What do larger image classifiers memorise? arXiv preprini arXiv:2310.0533 2023.
Sandler, M., Howard, A., Zhu, M., Zhmoginov, A., and Chen, L.-C. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510--5200, 2018.
Maini, P., Garg, S., Lipton, Z., and Kolter, Z. Charac- terizing datapoints via second-split forgetting. Advances in Neural Information Processing Systems, 35:30044- 30057, 2022.
Shakya, A. K., Pillai, G., and Chakrabarty, Reinforcement learning algorithms: A brief survey. Expert Systems with Applications, 231:120495, 2023.
Mangalam, K. and Prabhu, V. U. Do deep neural networks learn shallow learnable examples first? In ICML 2019 Workshop Identifying and Understanding Deep Learn ing Phenomena, 2019.
Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Mem- bership inference attacks against machine learning mod- els. In 20/7 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2017.
Nasr, M., Songi, S., Thakurta, A., Papernot, N., and Carlin, N. Adversary instantiation: Lower bounds for differen- tially private machine learning. In 2021 IEEE Symposium on security and privacy (SP), pp. 882. IEEE, 2021.
Simonyan, K. and Zisserman, A. Very deep convolu- tional networks for large-scale image recognition. arXiv preprint arXiv:1409.1s.. 2014.
Northcutt, C., Jiang, L., and Chuang, I. Confident learn- ing: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70: 111133-311111 2021.
Soufleri, E., Ravikumar, D., and Roy, K. Advancing com- pressed video action recognition through progressive knowledge distillation. arXiv preprint arXiv:2407.02713, 2024a.
Pezeshki, M., Bouchacourt, D., Ibrahim, M., Ballas, N., Vincent, P., and Lopez-Paz, D. Discovering environments with xrm. arXiv preprint X30v 16748, 2023.
Pleiss, G., Zhang, T., Elenberg, E., and Weinberger, K. Q. Identifying mislabeled data using the area under the mar- gin ranking. Advances in Neural Information Processing Systems, 33:1 04417744417000 17056, 2020.
Soufleri, E.. Ravikumar, D., and Roy, K. Dp-imgsyn: Dataset aligument for obfuscated, differentially private image synthesis. Transactions on Machine Learning Re- search, 2024b.

---

Towards Memorization Estimation: Fast, Formal and Free
Szegedy, C., Vanhoucke, V., loffe, S., Shlens, J., and Wojna, Z. Rethinking the inception architecture for computer vi- sion. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2818 11266, 2016.
Toneva, M., Sordoni, A., des Combes, R. T., Trischler, A., Bengio, Y., and Gordon, G. J. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2019. URL https: / id=BJ1xm xm30 c0Km.
Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Ad- vances in Neural Information Processing Systems, 31, 2018.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking gen- cralization. In International Conference on Learming Representations, 2017. URL https:: opw.revie.. net/forum? SofoorumiddSygyllllill SyxxxXxx.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
12

---

Towards Memorization Estimation: Fast, Formal and Free
Appendix
A. Stochastic Gradient Descent (SGD)
In SGD, model parameters ve at iteration / are updated using the gradient of the loss function computed with a mini-batch or single random sample 2. The update rule
+++ th T/e V ( Ei)
(15)
Here, TJ. is the learning rate, and V.,, E1,,, 2,) is an unbiased stochastic gradient estimator.
Bounded Gradient Variance. Let V w., ((we) denote the true gradient, and let Vw,, V.,e(ww ((we) be an unbiased estimator of this gradient. The estimator is said to have variance bounded by r if
E V u. ((w,) - V., (1) S
(16)
B. Experimental Details
B.1. Setup
Datasets. We use CIFAR-10, 10, CIFAR-100 (Krizhevsky et al., 2009) and ImageNet (Russakovsky et al., 2015) datasets. For experiments that use memorization scores, we use the pre-computed stability-based memorization scores from Feldman & Zhang (2020) which have been made publicly available by the authors.
Architectures. For all of experiments we train R8 (He et al., 2016) models from scratch, expect for the cross architecture results in Table where we train VGG16. MobileNetV2 and Inception (small inception used by Feldman Zhang (2020)). All the architectures used the same training recipe described below.
Training. When training models CIFAR-10 and 100 the initial learning rate was set to 0.1 and trained for 200 epochs. The learning rate is decreased by 10 at epochs 120 and 180. When training on CIFAR-10 10 and CIFAR- 100 datasets the batch size is set to 128. We use stochastic gradient descent for training with momentum set to 0.9 and weight decay set to le-4. For both CIFAR-10 and CIFAR-I00 datasets, we used the following sequence data augmentations for training: resize (32 x 32), random crop, and random horizontal flip, this is followed by normalization. For ImageNet we trained a ResNet18 for 200 epochs with the same setting except the resize random crop was set to 224 224.
Testing. During testing no augmentations were used, i.c. used resize followed by normalization. To improve reproducibility, we have provided the code in the supplementary material.
B.2. Similarity with Memorization Scores across Architectures
Experiment. In this section, we present the results of measuring the cosine similarity between the proposed memorization proxy (CSL) and the memorization score from Feldman & Zhang (2020) across different architectures. Specifically, we tested VGG (Simonyan & Zisserman, 2014), MobileNetV2 (Sandler et al., 2018), and Inception (Szegedy et al., 2016).
Results. The results are shown in Table 4, which reports the cosine similarity between the CSL proxy and the memorization score for the three architectures on the CIFAR- dataset. These models were trained using the methodology described in Section B.I.
The results indicate that the top 5K i.e., the similarity between the metries and the top 5000 most memorized samples according to Feldman & Zhang (2020) is highly consistent across architectures, and the overall match across the dataset is also quite high for CSL. However, two key observations are worth noting: (I) VGG16 shows a lower correlation on the 'All' category, and (2) Results on CSL are similar to the findings for ResNet18 in the main paper.
Takeaways.
B.3. Compute Cost Analysis
In this section, we provide a detailed analysis of the computational cost of the proposed proxies in comparison to other techniques. We assume the cost of one forward pass through a neural network is F, and consequently, the cost a backpropagation step is 2F, making the total cost for one herward-backward pass 3F. Using previously defined notation, let m represent the dataset size and the total number of training epochs.
13

---

Towards Memorization Estimation: Fast, Formal and Free
Architecture
Samples
CSL
Top 5K
1.00
VGG16
All
0.61
Top 5K
0.95
MobileNetV2
All
0.73
Top 5K
0.97
Inception
All
0.70
Table Cosine similarity between stability- all samples.
stability-based based memorization score with CSL different architectures on CIFAR- for Top 5K and
Stability-Based Memorization. Feldman & Zhang (2020) trained between 2,000 and 10,000 models compute the babed memorization score. Thus, the total computational cost is 10, 000 3F - m..
Cumulative Sample Curvature. Garg et al. (2024) trained single model and proposed using sample curvature averaged over training to estimate memorization. Hutchinson's trace estimator was employed to calculate curvature, which requires forward passes and backward pass, repeated n times over the entire dataset for each epoch. While their results show that n ranges from 2 to 10, we use n = 2 to provide the computational advantage in their favor, even though n 10 produces better results. Thus, the total cost consists of the training and curvature computation.
Cost = 3F -T m + 4F m
3F T- 4F -
11F .m
If 10 is used for optimal results, as reported in Tables 2 and 3, the total computational cost becomes 43F T m. CSL(Ours). CSL can be obtained without additional computational cost during training. Therefore, the only cost is that of the training process, which is 3F. T m. The computational cost comparison is summarized in Table 5.
m.
Method
Absolute Cost
Relative Cost
Stability-Basee (Feldman & Zhang, 2020) Cumulative Sample Curvature (Garg et al., 2024)
6000 30, FT.
2,000 -30, 000
11FTm 43FTm
3.6
14.33
CSL (Ours)
3FTm
1 x
Table 5. Summary of the compute cost of the proposed metric compared to existing methods.
B.4. Additional Details on Validating Theory Experiments
For the experiments described in Section 6.1, we provide additional details regarding the methodology. To generate the graphs in Figures 3, 4 and we collected all relevant proxies for each sample in the dataset and grouped them into bins based on the x-axis metric (learning time or memorization score) in each figure. For instance, in Figure samples were binned based on their learning time. Similarly, Figure 5, we binned samples based on their memorization scores as defined in (Feldman & Zhang, 2020) and in Figure 3, the samples were again binned by learning time.
Since the theoretical framework is developed in terms of expected learning time, memorization, and the CSL paradigm, the standard deviation is not directly relevant to the interpretation of the results. Nevertheless, for the sake of completeness, we have visualized the standard deviation for each bin in Figure 11, even though it does not significantly contribute to the theoretical insights derived from expected scores.
Learning Time Threshold r: For this and all experiments where learning time is used, we follow the learning time
14

---

Towards Memorization Estimation: Fast, Formal and Free
CIFAR-I00 100
CIFAR-100
CIFAR-100
1.00
Leurning Time
0.75
200
200
X
0.50
CSL
X
CSL.
X X
0.25
x
100
XXX X
Avg. Mcm Score
Learning Time
Avg. Mcm Score
ImageNet
ImageNet
ImageNet
0.8
600
800
Learning Lime
0.6
CSL
400
0.4
400
XXXX
200
0.2
200
Avg. Mem Score
Learning Time
Avg. Mem. Score
Figure 11 Validating theory results, linking learning time, memorization and CSL with error bars plotted as shaded area for CIFAR-100 and ImageNet.
definition (Eq. 7) and set the threshold r to the average of the per iteration sample gradient, i.e. for example for ImageNet
TemggeNet
Bre(O,-TTmaz ). ElmageNet
T
Σ V ((F,)
(17)
t=
CIFAR-100
ImageNet
300000
400000
8000
300000
6000
200000
4000
2000
100000
01
Normalized Learning Time
Normalized Learning Time
Figure 12. Histogram of learning times on CIFAR-100 100 dataset. Learning time captures the bimodal property of memorization score.
Figure 13. Histogram of learning times on the ImageNet dataset. Learning captures the bimodal property of memorization score.
B.5. Additional Details on Mislabelled Detection Experiments
In this section, we provide additional details regarding the setup for mislabel detection experiments. For all experiments, we trained the models using the training procedure outlined in Appendix B.I.
In Confidence. In-confidence (Carlini et al., 2019a) is calculated 1 "the predicted probability" of the true class.
Confident Learning. For the implementation of confident learning (Northcutt et al., 2021), we utilized the cleanlab library, which is available at https: / /tte:///iitie httpttttbbb.///////////////..ttt com/ ccleanaal aaaaaaabcllaaa cleanlab We applied 3-fold cross-validation to compute sft-lle probability scores for the samples. These probability scores were then input into the cleanlab implementation to generate the results reported.
15

---

Towards Memorization Estimation: Fast, Formal and Free
Histogrum of CIFARIOS 100 CSL Values
Histogram ImageNet CSL Values
140000
8000
100000
Count
80000
4000
60000
40000
2000
20000
20
CSL
CSL
Figure 14. CSL Histogram on CIFAR100, captures long tail.
Figure 15. CSL Histogram on ImageNet, captures long tail.
oro
0
6
0
3
Figure Lowest CSL Scores on CIFAR-100 captures easy-to- learn, Typical (likely generalized) examples. Visualized for the first 10 classes.
Figure 17. Highest CSL Scores on CIFAR-100 capture hard-to- learn, Atypical (likely memorized) examples. Visualized for the first 10 classes.
SSFT. Second Split Forgetting Time (SSFT) (Maini et al., 2022) is measured using two subsets, Set and Set 2. A model is first trained on Set 1 and subsequently fine-tuned on Set 2, during which we measure how quickly sample from Set is misclassified or "forgotten". This process is repeated for both subsets to cover the entire dataset. Specifically, after training on Set I and measuring the forgetting time for samples in Set I during fine-tuning on Set 2, the model is then trained on Set 2, and the forgetting time for Set 2 is measured during fine-tume siee-tuning on Set 1.
Thr. LT. (Threshold based Learning Time). Consider sample's correct predictions during training over 12 epochs in this 1, 1, Then Thr. LT would be calculated epoch 3 (beginning
case. Let the correct predictions be [0, 0, 0, at 0). This is normalized that it's between 0 1.
Curvature. To calculate the curvature of sample, we used the technique described in Garg et al. (2024). The hyperparame- ters were set to 10 and 0.001, following the same configuration as outlined by Garg et al. (2024).
16

---

Towards Memorization Estimation: Fast, Formal and Free
Figure Lowest CSL Scores on ImageNet captures easy-to- learn, Typical (likely generalized) examples. Visualized for the first 10 classes.
Figure 19. Highest CSL Scores on ImageNet capture hard-to-learn, Atypical (likely memorized) examples. Visualized for the first 10 classes.
C. Proofs
C.1. Proof of Lemma 5.1
Lemma 5.1 For any neural network and a given mini-batch of inputs Zo = (Xo. Yt), the Frobenius norm of the gradient of the loss with respect to the input is bounded by the norm of the gradient with respect to the network's 's weights wi Specifically:
LZ Zo)lle S kkgl E(E,, Zo) F
(18)
||W I| II(X))*I1
where kg
and sp denotes the smallest singular value of P X, (X,)), where + denotes
8p
pseudo-inverse.
Proof
Let the vector u7, (wx(") (1)
wx(2)
.... w (k)
denote the weights of a q-layered neural network iteration 4, where
W
w
1,1,
(k)
1,1.
(K)
(k) w da- E Rddddd
(19)
is flattened row vector representing the weights of the 1thh layer iteration with input dimension dę-1 and output dimension dy. This vector can be reshaped into matrix (((k) xdx-1 by rearranging its elements into the specified dimensions dz x dR-1 while maintaining the order of elements. The reshaping operation is formally defined as:
(k)
(k)
(k)
w W
Wii.2
.
(R)
(k)
(k)
((1) Reshape (1k)
112,1
w
2,2
2,2,4
(20)
(K)
(k)
(R)
2,
For our initial analysis, we consider a two-layer neural network given by:
(R() = (W((") Xb)
(21)
1RO)
(22)
where W(()) E dd xdo and w!(2) e Bddxxd are matrices constructed from wi and (2) respectively. Here, X3 E do represents the input batch, I (R)) Rdd denotes the intermediate representation after applying the activation function
17

---

Towards Memorization Estimation: Fast, Formal and Free
a()), and Y R represents the predicted output. In our case do and d2 Let the labels for the batch X be represented as Y2 [yi. y.]. the can use chain rule to write the gradients with respect input and weight parameters as below
V X, EiTT, Es) = Vyl(ur, Zo) VIROY Vx,IR
= (W "V, Zb) o ((R(
(z (wi (( Zb) o' ( X6)
(23)
Similarly for the gradient w.r.t to W!") we have
Wone(ur Σb) = Vyl(ur, Zo) VIR() & V WOO
-W, f(w), Z,) 2 (IR X5
(Wi E( Z,) 1 o o'(w:(") X1) X²
(24)
From Equations 23 and 24 we have:
(W V w. (( Zn) Vx, 2,)X
(25)
(W.")V won (x))) Vx, (WT, XT (x,))
I wo w (x,)) > |V Eei Z,) (x)))
(26)
Now note that Equations 25 and 26 hold for any deep neural network. Next if we let 8p denote the smallest singular value of P = (x}))
I(w("))Tll IF VI wors 1T) [1(x?)* 2 (xx
I(w/")ylle VI wi (w, Zo)lle (1xx)) ) +1| N Vxx, (wt, 2 2, (x,) + 2 spl Vx, Zb)
Thus we have
|/ V ((ūt, Z - 1(W()))/|1 11(X?)) 1FF 1 won E(ūr, Zb)lF
sp
[V, Ewi, Zb)l F S kig || V w. E Zb)l
Now observe that V/V ( Z,)]|r r < V w. (rū, 7,)]/= Fr where W. is the weights of the entire network (see proof in section C.I.1). Intuitively, the gradient with respect to a single layer is just a portion of the overall gradient vector, and removing coordinates (the other layers' gradients) cannot increase the Frobenius (or f2) norm.
(( ( Tll 11xx))+ll
VVx Zo)l
Vw, (w. Zb
SP
IVx, Zo S I Vw, e(T,, Zo)l
C. I. WEIGHT NORM RELATION PROOF
We aim to prove that
E Zb)l < V.,, (WT,, Zo)l P.
(27)
We consider a p-layer neural network whose entire weight vector at iteration t
Wr [wl
w (p))
where uT(() is the flattened vector of parameters in the kth layer.
18

---

Towards Memorization Estimation: Fast, Formal and Free
The gradient of the loss V wa {(,,, Zb) be viewed as the concatenation of the gradients with respect to each layer:
w
V
on (
((1,, Zb)
V
In particular, V witt e is just the top block (corresponding to the first layer) of the entire gradient vector.
Let us denote
g0 = v En Zo), Lo), : V ve ( Zo),
g0²l=
g(0) = wosps (( 2t)
Then the full gradient can be written
((1)
g(2)
G = Vu, eWT, Zo) =
(g(n)
By the definition of the Frobenius norm (which coincides with the Euclidean & norm on the flattened vector), we have
|| = 1 ||= + |1
+...
||
2 |19 12
(28)
Taking the square root both sides preserves the inequality:
|| / VIgg + ... || 2 VI = 1I
(29)
Since g()) V w Zb) and G Vw, E( Zo), we obtain
V En Zo)l S VV, (W Zo)l
(30)
Intuitively, the gradient with respect to single layer is just a portion the overall gradient vector, and removing coordinates (the other layers' gradients) cannot increase the Frobenius (or &g) norm.
D. Proofs
D.1. Proof of Theorem 5.2
Proof
Assumptions:
Assume that the loss function is p-Lipschitz.
Assume that the gradient estimator Vi unbiased i.e., E. (e (.e((T)))
Assume bounded gradient variance E |V ((wit) Van, E(Tt))11 ST3
Assume E, (( w. ((TT)) 8z)]
19

---

Towards Memorization Estimation: Fast, Formal and Free
Proof
Let Wi denote the vector of the weight parameters the td iteration. For simplicity, we slightly abuse the notation by using
V w Vi, throughout the paper for ease of reference. Using the p-Lipschitz assumption on the loss, for any vectors vi and w the function & satisfies the quadratic upper bound:
{(1(+1) & (((r) + (V. Tht1 - win + - 2.lur 01+1112
(31)
We know the SGD update equation is
x1+1 = nh. 11e vo, ((TT))
(32)
Using the SGD update in Eq. 31 we get
pnt
((w)+1) s ((TT)) - (V.. n v. (,,e)) +
w., (1))
(33)
2
((T++1) ((1T)) (V. ((i)))
e( 11
(34)
2
Following the trick from the SGD convergence proof by (Ghadimi & Lan, 2013) (for randomized stochastic gradient method), we have 62 ((Tt)) (()e(
PM
(( S ((ūr)) Th (Vel(wt)) Ve, (( To (e.((T)) 8.) +
V ww (21t
(35)
((w+41) S ((7+)) (V El 77 V Ve ((xt)) (o. 8z) + p
1 w/ E(tt))
(36)
2
Taking conditional expectation at timestep we get
pM
E, [[(E+++1) < ((T.) noll e(3,)))
0+
Ee
| w. {1tb)
(37)
0 pm
Er [((#++1)] < ((17)) - V E117))1
Ee V ur.
f (T
2(V w. ((7))) 5t) + [|..1
(38)
E, [((7(41)) S E(TT)) - pmf
pnf
V w. (w7, 12 +
E. 12(V w. ((T,)) 5,) + 6
(39)
2
2
Using the bounded variance assumption and E, ((V ((it), [+)] O, have
pnf
V w. [(TT))1 + p
Es = 7t
Ec
(40)
2
2
Rearranging and telescoping we get
pT)
< [E.[((()))) EE [[( + pnpr²
7h
E.
|I
w.
[1
(41)
2
2
T-1
pm
2 Σ
E+
||
[
E. (((wTo) {(
1/1
(42)
2
t=
Let's divide each side by
T-1 1
prè
Σ
T/t
2
0=0
20

---

Towards Memorization Estimation: Fast, Formal and Free
Now consider:
pM
E:
V (1Te)
2
pTi
Σ
T-1 t=0
T]t
2
This is nothing but weighted sum i.e. expectation, since we hold the choice of the weights, can chose them so that it is uniformly randomly distributed. Thus we can write the following below where R. is such variable.
1
ER
Ex [e(1bb) ((TT)]
pnf
Ei=0
111
2
21= 1/2
T
2
+
(43)
2
T-
0m
11e
The above the is standard convergence result for SGD from Ghadimi & Lan (2013). Let us now consider Eq. 41.
pni 2
1)
E:
V 10 { (1))) S (((ie)) E. [((w++1)] +
(44)
2
From Lemma 5.1 we know the input and weight gradient are related by Kig this varies as a function of w.. But there exists a constant K which satisfies Lemma 5.1 for all t. Trivially, xiT = max; rey. since n²g >> O. Let Km = maxx (xx)) (x.)) Now multiply both sides by Km,, we get
pm 2
II x. (17)) Km Ee(((())) Ea (e(wT++1)) (n (x
1/t
E.
(45)
Summing over /. = to / = T
1 we get
pl T-1
pn
Ee
El (1)
Km
RR [(( E. [((+++)))
+
(n (1 )2
(46)
2
2 1=
2 T-1
pri
Ex
V m.
El (T,
v Km
[b(((w))]
E. [[(wTT]] +
ne ne) )²
(47)
2
2
1=0
pnz
Let us divide each by
T-
1h
2
Et=o
T-1
Ttt
pmt
Es
V x.
2
pp?
1= (mi))))
Km
Eg [e( E. [[(wrr]+
T--1
17t
prf
2
Σ
17:
MM
2
2
2
(48)
Using the weighted sum argument, we can write this as follows
pr?
ΣT
(nig
Km
E. [[(Ww)))] E. [(((r)) +
(49)
ΣT-1
pM
ΣT-1
pm
171
110
21

---

Towards Memorization Estimation: Fast, Formal and Free
Now let f/
consider the first term on the right hand side
( 1
Km
E [((o)) - Ee (((TT)))) -0
=0
(50)
T/VT)
VT)
PTl
-
T/t
Let us now consider the second term
Σ
T-1
(Rig
T
1=
P
(51)
2
p
T
VT
E1=
91t
vT
2
Thus get the convergence result
ER [(R)]]
(52)
where Ri is the result iterate and 7' is an iterate greater than R. Additionally, see Corollary 2.2 from Ghadimi & Lan (2013)
where 7/. min L D
for some D 0, and taking the tower expectation over the iterate t (see Ghadimi & Lan
TTVT
(2013) for more details) we get the above convergence result.
D.2. Learning Time and Memorization
Theorem 5.3 (Learning Time bounds Memorization) Under the assumptions of SGD convergence and L-bounded loss, there exists KT >> 0 such that the expected learming time for sample 2 bounds expected memorization score follows.
Ez, mem] S KT Ezcp [Tx.]
(53)
Proof of Theorem 5.3
Assumptions:
Assume that the loss function is p-Lipschitz.
Assume that the gradient estimator V. unbiased i.c., Vel (w.(
Assume bounded gradient variance E (w, V.,, (( ST3
Assume loss is bounded < S
Assume B-stability as stated in Assumption 4.
Proof
Consider Equation 48:
Σ === (ni
Km
ER V2. ((RR)
[E[[((Wo]] - E. [[((TT]]
(54)
pri
Σ
1/:
Σ
9/1
2
Let
17
1h
(55)
2
ΣT-1
(m1)
7
(56)
pnz
Σ1=0
17
2
22

---

Towards Memorization Estimation: Fast, Formal and Free
pij
Using the above we have, 7s is independent of and for the worst case bound we can set = min,
7t
Thus we
2
write the following
Km
Kim Pm
ER | 2, (1
Es [((TTo) {(wrr))]
(57)
Tn
2
Km
Kim P
Er [E(w0)) E(vi") )
(58)
T'
where v²* is a solution that is as good or better than solution at iteration Tiax over the randomness of the algorithm.
Formally it can be defined as below
Definition D.I (Optimal weight w Let p P represent the randomness of the training algorithm
Wiae (p)
denote the mapping that, returns the weight vector WT (p) produced by a randomized learning algorithm at iteration T Tmax.
Define the optimal seed
p¹ E arg min E(wTT (p));
where ((wō is the loss function under consideration. Finally, let
W Tinse (p").
We call w the optimal weight at time Tmax: it is the weight vector (among all realizations of the randomness) that achieves the minimal loss E(-) at iteration mmax.
We can set r to this worst case upper bound, thus we get
Ki T/T2,
Et [l(1ño) - {(1T1)] +
Km Msm pl
(59)
Rearranging:
T1
1) m)pl
= Ex [((10)) - {(1#¹)]
(60)
Km
2
Er.z. [e(16, xi) - -((w", , []]]
(61)
Er,,, [e(1ño zi) ((""", ].]]]] + Rr [, Zi)
(62)
Er,,, (x7", z;) ((""", [ + Rt,z [E(wo, Zi) - (1"" (WT,))) z]]
(63)
Taking expectation over the randomness of the algorithm p we get
Ep T
Tn
17 Mepl u 2
Er,p, [= Ei) l( Z:)] Ee [E(Wo, 2,) - ( [,]]
(64)
Km
Er Lmmm [d]] + Et,..p [E(20o, (.) (2" [z)
(65)
Taking expectation over 2;:
Ep.z, [Ta]]
TW Km
11 p
Ee,e, mem(())) + Re,er [e(uoo 2,) (xT',
Using Stability (Eq. 4) we have
17 mopp?
Ep Ep.2,
[Ta
2 Ez, [ m2) + Ezu.p [E(ub, 2,) f(w" %,)]
Km
23

---

Towards Memorization Estimation: Fast, Formal and Free
Since Ep.z; [0(16, 2,) l(w"" 2)] 0:
Ep.z; [Tc]
TH
1 Napp
2
2 Es, L memm (2:) - B
Kim
2
Let:
57
17 7spp?
KT
Km
2L
Since
T=
Tq)
11 7
= Er [e(WTo - {(1T((1) 2 0
Rm
2L
L
TQ)
17 1
2 0, Since, T2 2 1
Kym L
2L
Finally we have:
S Kr Ep.zs [Tz;] + 3
E2, [mem(2:)]
D.2.1. PROOF OF THEOREM 5.3 FOR CROSS ENTROPY LOSS
Consider Eq. 64, we have
Ep
TT,
p.,. [e"" /4) f("" x.] + Be, [E(Wo, 2,) - g [,]]
Km
2
Using the result A.4 from Ravikumar et al. (2024a) which states for cross-entropy loss we have the following result:
Ep [e>* (1F", -3 E( =)] 2 mem(a;
(66)
Taking expectation w.r.t, ž and following the same procedure as the proof above we get: Taking expectation over zj:
Ep 2; [T,]]
Be [em)()]] + Er,e, [E(uoo Z.) - ( (w"", ā,]
Fim
2
Using Stability (Eq. 4) we have
E Ep.z, [2g]]
TQ
17
nspp?
2 Ez, mem [2:) + E2.. [e(wo, 2/) ,(1t", ..)]] 3
Km
2
Since Ep.z. [e(woo 2) E(w"* [.) 0:
Ep.z. [2x)
Tq
17 n
Es; memm(t) -3
Km
2
Let:
TH
17 napI
RTX
Km
2
Since
T
TD
mapp
Ee [E(18o) {((w") 20
Km
2
TT]
17 mapl 2
O, Since, Tr, 2
Km
2
Finally we have:
Es, [mcm(2))] S frx Ep.z. [Ty,
This is the same result as Theorem 5.3 but with T.
24

---

Towards Memorization Estimation: Fast, Formal and Free
D.2.2. REMARK THE REQUIREMENT FOR 3-STABILITY
Consider Eq. 64. We have:
Ep
[T,]]
TH
Mapl"
Bt... 2i) (( .z)]
Rym
+ Et, [((Wbs, Zi) (1 z))
Assuming sufficient generalization, we can reasonably state that:
Er,,, [e(10: 2i) e , 2 0.
Thus, we can write:
11 T x
Ep =:
2 Ee Ee [et 2i) A( ;
Km
1i MspT 2
Ep [T,]]
Er, mem (i:)
Km
Finally, we conclude:
E1,;,
mem [)]] & KT [p[
Thus we can drop the requirement for stability.
D.3. CSL and Learning Time Proof of Theorem 5.4
Assumptions:
Assume that the loss function is p-Lipschitz.
Assume that the gradient estimator Vizk unbiased i.e., E (v))(()))) v.n((
Assume bounded gradient as stated in Assumption 3.
Proof
We know from Equation 59
Km TTT,
Er [f(1i)) E(ui,, +
Km Emp
2
Rearranging:
T
TT]
17 mappI
Et [f(1))) E(WTT.
Kim
2
T
Tn
77 ?
< T Tmax
T1)
17 ?
2
Tiaae
Es [e(wT)) - [(10++1)
12
2
Km
2
1=0
T Tma
T Tmax-1
Es [e(wTe]]
E, [((()+1)]
17
1=
1=0
Tmax
1
Tmax
Ex, [e(Wee 2,)
Ei,,, [( 2,))
12
25

---

Towards Memorization Estimation: Fast, Formal and Free
Taking expectation over 2; get:
T Imax 11
Tmax
Ez,
Tx.
Tq
Σ t=
ElWig 2ii
- E1,
110r+1: 2t
1
Am
2
Tmaxe
(CSL(Z)) (2,)
12,,
{(1
17
To identify a tight bound that is also more interpretable, we identify & as below:
max
((1(+1,
Thus can be interpreted as offset to scale CSL correctly. Putting this together we have
LST Es, [Ta.] S Er,e, [CSL(E)]]
&
Er,e, CSSI(EE) - <
Ez, [Tz] S L
(67)
D. NOTE ON UNBOUNDED Loss
Note since the I--buuneed loss is only used for the upper bound, this result hold true for cross entropy, but with out the upper bound, i.c.
KTX Ez; [T,]] < Et [CSL(E))] - E
(68)
D.3.2. & A LOWER BOUND FOR CSL
In this section, we build intuition on &. We will that & can be interpreted as lower bound on CSL, which scales CSL into the appropriate range to bound learning time and memorization. Consider as defined by
max
Ra,z
l(1411 2)
t=U
Now assume Ex; (f(wo, =]] 2 Ez, ( }- This assumption, which is empirically justified for most deep neural networks, states that the loss at the beginning of training is higher than the end. Under this assumption, obtain:
Tmax
{ = Et,z
((1++1, &)
Tiaas
= -Et-1,2
((12+11 Ei) + l( zi)
< EE-1.
(1 Ei) + e(wo, xi)
< Et- 1,2
( Z
{ < E,-1,2 [C)L(E))
Since this holds for any 2 ~ Z. we conclude that is a lower bound on CSL. Moreover, when considering the result for memorization (see Theorem 5.5), we observe that & scales CSL so that it lies in the range (0, 1) when
26

---

Towards Memorization Estimation: Fast, Formal and Free
D.4. Memorization and Loss
Proof of Theorem 5.5
Assumptions:
Assume that the loss function is p-Lipschitz
Assume that the gradient estimator v is unbiased i.e., E. V. [(.,)) V.n.(t,,).
Assume bounded gradient stated in Assumption 3.
Assume loss is bounded <E7L L
Assume B-stability stated in Assumption 4.
Proof
This proof results from Theorem 5.3 and taking expectation over (randomness of the algorithm) on Theorem 5.4 have:
Ex, [mmm [2:) S Ez.p [CSL(E)]
3
S 1 +
(69)
L
D.4.1. NOTE ON CROSS ENTROPY LOSS AND NON-TRIVAL BOUND
Here we use the cross entropy results from Theorem 5.3 and 5.4. Specifically, using Equations 67 and 68. We take expectation over the randomness of the algorithm p on Equation 68 and use this in Eq. 67 to get
Ez, [mem [,]] S Ez,p (C)L( + -
(70)
Non-triviality. Here we would like to emphasize that the CSL bound on memorization is non-trivial. Specifically consider the result from Appendix D.2.2. Re-stating the result for convenience we get:
Er,,, mem [3) S KT Ep [Ta.]
This is under the reasonable generalization assumption:
Rt,. [[(mo, z,) - (T"", 2:] 2 0.
Using this result in the proof of Theorem 5.5 we get:
Es, [mem({)] E.z,p (C)L.
(71)
L
Thus CSL is effectively bounded between the memorization score and the trivial upper bound (i.e. 1), showing the CSL bound is non-trivial.
27


Reviews:
[{"review_id": "COhQm38UqM", "reviewer": "Reviewer_ZrxQ", "summary": "This paper introduces Cumulative Sample Loss (CSL) as a novel proxy for measuring memorization in deep learning models. The authors formally adopt the memorization definition established by Feldman(2020); Feldman & Zhang (2020) and develop a theoretical framework connecting CSL to both training time and memorization. Through the theoretical analysis, they prove these connections under specific assumptions about learning dynamics.\n\nThe authors empirically validate their theoretical findings by demonstrating high correlation between CSL and established memorization scores across multiple datasets and model architectures. They further showcase the practical utility of CSL by applying it to detect mislabeled examples and duplicate samples in datasets, where it achieves state-of-the-art performance compared to existing methods while being computationally more efficient.\n\n## Update after rebuttal\n\nMost of my concerns have been adequately addressed by the authors. \n1. Authors provided the calculations matching the setup from Feldman & Zhang\n2. Authors clarifies the generality of the proofs\n3. Authors included missing citations and clarified the relation to the prior literature\n\nI have therefore increased my score 2->3. Some remaining concerns I have:\n1. Given the training setup mismatch between some early experiments and Feldman & Zhang, I don't think it's entirely valid to use precomputed scores from the prior work - those need to be re-caclucated for each training setup\n2. Given existing literature on using loss trajectories to assess vulnerability, I'd expect more extensive comparison to baselines", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, we address the questions below. Tables and Figures are provided at ****[Rebuttal Page click here](https://lively-dune-08c51d610.6.azurestaticapps.net/).****\n\n1. A primary concern is the authors' use of memorization scores precomputed by Feldman & Zhang (2020) while employing different model architectures .... scores.\n\n**A**:  We agree with the reviewer. Feldman & Zhang used Inception for CIFAR100 and ResNet50 for ImageNet. We have added ResNet50 (same as Feldman & Zhang) and Inception (for CIFAR100 same as Feldman & Zhang) in Table 1 (rebuttal page above) along with more baselines (we reran Inception model, due to a minor bug fix, and present the updated scores). The choice of ResNet18 was dictated by its use in prior proxy such as curvature [3].  Additionally, we have included results using multiple architectures in Appendix B.2. These were already part of the appendix but not clearly referenced in the main text; we will fix this in the revised version. Our findings are inline with [3, 4, 5, 6] which have shown that memorization is often a dataset-level property, *given the model has sufficient capacity*. Also, please see our response to fZEA Q3.\n\n2. Furthermore, ... Without explicitly comparing against such straightforward alternatives, the paper fails to convincingly demonstrate the unique value of CSL over simpler approaches.\n\n**A**:  We have provided the final sample loss, loss sensitivity and forgetting frequency as a baselines (also suggested by reviewer fZEA) in Table 1 (rebuttal page above) . As noted by reviewer woPj, we have also added *Pearson correlation* $\\in (-1, 1)$, any magnitude > 0.25 is considered statistically significant correlation. And clearly we see $CSL$ has statistically significant result generally and outperforms other methods. Also, please see our response to reviewer fZEA Q3.\n\n3. Lemma 5.1, which states .. weight matrix configurations and with no bias.\n\n**A**:  We would like to clarify that Lemma 5.1 indeed holds for a general feed forward neural networks. While the proof in Appendix C.1 begins with the case of a linear layer for simplicity, the result extends to arbitrary feed forward networks (see steps eq. 23 -> 24 this is holds for a general feed forward NN). \n\nRegarding bias, this is a notational simplification. The inclusion of bias can be handled without loss of generality by augmenting the input vector with an additional identity row, a common technique to account for bias. As such, Lemma 5.1 holds for feed forward networks with and without bias. We will revise the appendix to make this generalization more explicit.\n\n 4. The theoretical framework relies on .. assumptions that may not hold in practical deep learning settings .. irregular.\n\n**A**:  First, our theoretical results do not assume convexity. In fact, our analysis applies to widely used unbounded, non-convex, cross-entropy loss, as noted in the paper. Additionally also for any non-convex bounded loss.\n\nSecond, the assumptions (e.g., smoothness, stability, bounded gradients) are well-supported in practice. Lipschitz continuity and smoothness of deep networks have been studied and validated in Virmaux & Scaman [1], and uniform stability of SGD has been established by Hardt et al. [2]. Please see our detailed discussion in lines (303-317). Therefore, we believe the theoretical framework remains broadly applicable to standard deep learning practice, especially for networks trained with SGD.\n\n5. Additionally, the paper is unclear about ... minibatches might affect the derived bounds.\n\n**A**:  Thank you for raising this important point. We understand the potential confusion, and we’d like to clarify. Our proof relies on lemma 5.1, since lemma 5.1 does not depend on the choice of minibatch, our proof can also be extended to SGD with minibatch size larger than 1.\n\n6. I also don't understand ... data subsets.\n\n**A**:  We would like to clarify that we meant arbitrary **random** subsets. Consider selecting a subset U at random; then T can be set as $\\max\\{T_{z_i} : z_i \\in U\\}$. Since Equation (10) holds for such a distribution, we obtain the stated result. We will revise the text to clarify this point and explicitly indicate that the subsets under consideration are random.\n\n7. Regarding Missing references w.r.t MIA:\n\n**A**: Please see our response to reviewer WoPj Q5.\n\n[1] Virmaux & Scaman Lipschitz regularity of deep neural networks: analysis and efficient estimation. NeurIPS 18\\\n[2] Hard  et al. Train faster, generalize better: Stability of stochastic gradient descent. ICML, 16\\\n[3] Garg et al. \"Memorization Through the Lens of Curvature of Loss Function Around Samples.\" ICML 24.\\\n[4] Garg & Roy. \"Samples with low loss curvature improve data efficiency.\" CVPR 23\\\n[5] Lukasik et al. What do larger image classifiers memorise? arXiv preprint arXiv:2310.05337, 2023\\\n[6] Ravikumar et al. \"Unveiling privacy, memorization, and input curvature links.\" ICML 24", "claims_and_evidence": "Discussed below", "methods_and_evaluation_criteria": "The paper utilizes standard benchmarks (CIFAR-10/100, ImageNet) and common architectures following established protocols from prior work. Their evaluation employs appropriate metrics: cosine similarity for correlating CSL with memorization scores and AUROC for mislabeled/duplicate detection tasks.\n\nA notable limitation is limited baselines for correlation with the memorization scores. While CSL outperforms input loss curvature, more extensive set of baselines is necessary - covering at least simple metrics like final loss or model confidence.", "theoretical_claims": "The core contribution of this paper lies in its theoretical framework connecting Cumulative Sample Loss (CSL) to memorization and learning time. However, several aspects of these theoretical claims are not entirely clear to me.\n\nLemma 5.1, which states that input gradient norm is bounded by weight gradient norm, appears to claim applicability to \"any neural network.\" However, its proof in C1 only covers a linear layer with particular weight matrix configurations and with no bias. \n\nThe theoretical framework relies on several strong assumptions that may not hold in practical deep learning settings. These include bounded loss functions, smooth loss landscapes, and uniform stability guarantees (which essentially implies bounded memorization by definition). While these assumptions facilitate mathematical analysis, they potentially limit the applicability of the results to real-world deep learning scenarios where loss functions may be unbounded (e.g., cross-entropy without clipping) and loss landscapes are known to be highly non-convex and irregular.\n\nAdditionally, the paper is unclear about how the theoretical results extend to minibatch training, which is standard practice. The proofs appear to consider individual sample updates, leaving questions about how gradient interactions within minibatches might affect the derived bounds.\n\nI also don't understand the authors' claim that certain theorems hold for any arbitrary subset of training data. This interpretation is not clearly justified, as the optimization steps in the proofs seem to rely on specific data distributions. The paper would benefit from clarifying how the expectation-based results generalize to arbitrary data subsets.", "experimental_designs_or_analyses": "The paper's experimental methodology exhibits some significant limitations that undermine the strength of its empirical validation. A primary concern is the authors' use of memorization scores precomputed by Feldman & Zhang (2020) while employing different model architectures in their own experiments (ResNet50 vs ResNet18). Since memorization scores are highly specific to particular training configurations (including architecture, optimization settings, and data processing), this mismatch raises questions about the validity of the correlation analysis between CSL and the referenced memorization scores.\n\nFurthermore, the paper lacks comprehensive comparison against simpler baseline metrics. Examining Figure 2, it appears that final sample loss might achieve similar correlation with memorization as the proposed CSL metric. This observation suggests that accumulating loss throughout training may not provide substantial additional benefit. Without explicitly comparing against such straightforward alternatives, the paper fails to convincingly demonstrate the unique value of CSL over simpler approaches.", "relation_to_broader_scientific_literature": "This paper makes a valuable contribution to the theoretical understanding of memorization in deep learning by establishing connections between CSL, learning time, and memorization. Its most significant practical contribution is providing a computationally efficient proxy for memorization, which traditionally requires expensive leave-one-out training procedures.\n\nBy demonstrating that CSL can be obtained with zero additional computational overhead during training, the authors offer a practical tool for analyzing memorization at scale. The work effectively builds upon prior research on input loss curvature while offering substantial computational advantages.", "essential_references_not_discussed": "The paper overlooks two works with a very similar idea of using loss trajectory to assess memorization/vulnerability of the target point. The papers in question, however, frame it in the context of a Membership Inference Attack, but it's still highly relevant to the proposed research.\n\n[1] Liu, Yiyong, et al. \"Membership inference attacks by exploiting loss trajectory.\" _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_. 2022.\n\n[2] Li, Hao, et al. \"Seqmia: Sequential-metric based membership inference attack.\" _Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security_. 2024.\n\nLoss trajectory (specifically mean loss) has also been previously used as memorization proxy in privacy auditing literature, e.g.\n\n[3] Nasr, Milad, et al. \"Adversary instantiation: Lower bounds for differentially private machine learning.\" 2021 IEEE Symposium on security and privacy (SP). IEEE, 2021.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gzHlQQWbEY", "reviewer": "Reviewer_woPj", "summary": "The paper proposes a computational efficient proxy metric (CSL) to the popular notion of memorization proposed by Zhang and Feldman (2020). The authors support this metric with theoretical analyses and empirical results on standard image classification benchmarks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, we address their questions below. Tables and Figures are provided at ****[Rebuttal Page clickable link](https://lively-dune-08c51d610.6.azurestaticapps.net/).****\n\n1. There is no description of how CSL is used to detect mislabeled samples (Section 7.1) and duplicate samples (Section 7.2). I also cannot find it in Appendix B.1 or B.5. Is this simply thresholding the CSL for each sample?\n\n**A**: Thank you for bringing this to our attention, we will clarify this in the revision. We do indeed use thresholding on each sample’s CSL, giving us a binary detector whose performance is measured and reported using AUROC.\n\n2. The expectation over samples. Starting from Theorem 5.3, there is an introduction to an expectation over training samples (). Looking at the proof quickly I believe that it is an expectation over the entire training data distribution. This already makes me curious about how this theorem would be used because we often care about memorization of a particular sample, not an expectation over a distribution. However, on L246, Theorem 5.3 is being interpreted as applying to “a group of samples” like  which is a subset of all training data . It is a bit unclear to me why this interpretation is valid, given the theorem holds in expectation for the entire training distribution. This is fairly important as it is used to motivate the experiments showing relationship between CSL and “Mem Score” (Figure 6 and 8). I might be missing something here.\n\n**A**: We would like to clarify that we meant arbitrary **random** subsets. Consider selecting a subset U at random; then T can be set as $\\max T_{z_i}$ for $z_i \\in U$. Since Equation (10) holds for such a distribution, we obtain the stated result. We will revise the text to clarify this point and explicitly indicate that the subsets under consideration are random.\n\n3. Assumption on L257: “it can be assumed that is constant across different subsets .” This assumption may need more explanation for why it is reasonable. My guess is that because depends on Frobenius norm and the singular values of the samples batch, which are arguably irrelevant to the difficulty to learn by neural network. This assumption may need more explanation for why it is reasonable. My guess is that because depends on Frobenius norm and the singular values of the samples batch, which are arguably irrelevant to the difficulty to learn by neural networks.\n\n**A**: The reviewers explanation is intuitive and correct. More formally, note that $\\kappa_g$  is not dependent on the training mini batch but is dependent on the choice of input made for computing the gradient norm w.r.t to the input, which is user controlled. The the input gradient bound for a given input is independent of the choice of the training mini batch. Now choosing $\\max_u \\kappa_{g_u},~u \\subset S$, i.e. max value over the subsets, we can get a worst case upper bound constant. \n\n4. Is there a particular reason for choosing cosine similarity as a metric instead of Pearson's correlation coefficient or mean square error? Correlation coefficient seems the most natural to me.\n\n**A**: We used cosine similarity because it was employed in prior methods and setups [3]. We have also added Pearson correlation in Table 1 (see the rebuttal page linked above). Any magnitude greater than 0.25 is considered a statistically significant correlation. Thus, the takeaways are similar between cosine similarity and Pearson correlation. Please also see our response to Q1 for reviewer ZrxQ.\n\n5. I believe that related works have been mentioned throughout the paper. I personally would like to see more discussion of the prior literature in more details.\n\n**A**: Thank you for the suggestion, other reviewers have also expressed similar concerns. We will expand our Related Works section to discuss more thoroughly (1) stability-based memorization and its computational challenges; (2) learning dynamics; and (3) broader loss trajectory works for membership inference attacks. This should clarify further how our approach (CSL) integrates with and advances prior research.\n\n6. I feel like Lemma 5.1 can be generally useful, and it’d be a nice contribution too (if it’s not been shown before)\n\n**A**: Thank you for recognizing the broader utility of Lemma 5.1. To our knowledge, it has not been explicitly presented before. We will emphasize this contribution and place it more prominently in the revised manuscript.\n\n7. I could not find how  l^z is defined. Is it loss when the sample z is removed from the  training set?\n\n**A**:  Yes, $l^{\\setminus {z_i}}(z_i)$ is the per-sample loss for ($z_i$) under the model trained on the leave-one-out dataset ($S^{\\setminus {z_i}}$). We will clarify that notation explicitly in the revised manuscript.\n\n[3] Garg et al. \"Memorization Through the Lens of Curvature of Loss Function Around Samples.\" ICML 24.", "claims_and_evidence": "The empirical claims that CSL are a better proxy metric to the baselines are convincing. There are 3 main portions of the empirical results:\n\n1. CSL is better correlated with memorization than the curvature-based method and is also more computationally efficient.\n2. CSL also performs better at detecting mislabeled samples due to symmetric label noise than the baselines.\n3. CSL detects duplicate samples with higher accuracy than the baselines.", "methods_and_evaluation_criteria": "Experiment methods and evaluation criteria are reasonable to me.\n\n**Question**: There is no description of how CSL is used to detect mislabeled samples (Section 7.1) and duplicate samples (Section 7.2). I also cannot find it in Appendix B.1 or B.5. Is this simply thresholding the CSL for each sample?", "theoretical_claims": "I skimmed over the proofs but did not check them carefully. All the claims and theorems seem to be reasonable, but I do have some questions below.\n\n**The expectation over samples.** Starting from Theorem 5.3, there is an introduction to an expectation over training samples ($z_i$). Looking at the proof quickly I believe that it is an expectation over the entire training data distribution. This already makes me curious about how this theorem would be used because we often care about memorization of a particular sample, not an expectation over a distribution.\n\nHowever, on L246, Theorem 5.3 is being interpreted as applying to “a group of samples” like $U(T)$ which is a subset of all training data $S$. It is a bit unclear to me why this interpretation is valid, given the theorem holds in expectation for the entire training distribution. This is fairly important as it is used to motivate the experiments showing relationship between CSL and “Mem Score” (Figure 6 and 8). I might be missing something here.\n\n**Assumption on L257**: “it can be assumed that $\\kappa_T$ is constant across different subsets $U(T)$.” This assumption may need more explanation for why it is reasonable. My guess is that because $k_g$ depends on Frobenius norm and the singular values of the samples batch, which are arguably irrelevant to the difficulty to learn by neural network.This assumption may need more explanation for why it is reasonable. My guess is that because $k_g$ depends on Frobenius norm and the singular values of the samples batch, which are arguably irrelevant to the difficulty to learn by neural networks.", "experimental_designs_or_analyses": "Question: Is there a particular reason for choosing cosine similarity as a metric instead of Pearson's correlation coefficient or mean square error? Correlation coefficient seems the most natural to me.", "relation_to_broader_scientific_literature": "I believe that related works have been mentioned throughout the paper. I personally would like to see more discussion of the prior literature in more details.", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "The paper is very well-written in my opinion. Even as a non-theorist, I feel like I understand the theorems and learn some useful tricks along the way. I feel like Lemma 5.1 can be generally useful, and it’d be a nice contribution too (if it’s not been shown before). The experiments are also convincing and a nice addition to the theoretical results.", "questions_for_authors": "Question: I could not find how $\\ell^{\\backslash z_i}$ is defined. Is it loss when the sample $z_i$ is removed from the training set?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NZhCDDz8pP", "reviewer": "Reviewer_fZEA", "summary": "This paper introduces cumulative sample loss, CSL as a way to measure memorization in neural networks. The key idea is that by tracking the cumulative loss over training, CSL can identify mislabeled and duplicate examples efficiently. The authors argue that CSL is both cheaper than stability-based methods and more effective at finding problematic examples. They evaluate their method on standard benchmark datasets and show that it outperforms existing heuristics for detecting mislabeled data.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback, we address their questions below. Tables and Figures are provided at ****[Rebuttal Page clickable link](https://lively-dune-08c51d610.6.azurestaticapps.net/).****\n\n1. Which other architectures and dataset sizes?\n\n**A**: Please see our response to reviewer ZrxQ Q1. Additionally we also ran the the long tail experiments, visualized in Figure 3,4,5,6 in the rebuttal page. See the Q2 for a more in-depth explanation.\n\n2. Other memorization-related signals used in curriculum learning or adversarial robustness:\n\n**A**: We would like to clarify that we provide two experiments, first *mislabeled detection*, second *duplicate detection* to capture mem. properties. Additionally, we ran the exps below\n\n- Adversarial Robustness (Fig 7 rebuttal page):\n    - We provide a visualization of  adversarial distance versus memorization  and CSL scores. Adversarial distance refers to how easily a sample can be perturbed to change its classification. The results show that samples with low adversarial distance (more vulnerable) tend to have higher memorization and CSL scores. This suggests that CSL and memorization capture similar properties and are strongly related to model robustness.    \n- Easy vs. Hard-to-Learn Samples:\n    - Fig 1 (on the Rebuttal Page (link above)) shows images with low CSL scores from CIFAR100, interpreted as easy or typical examples (class prototypes). Fig. 2 shows high CSL images from CIFAR100 capturing atypical and likely memorized examples.  Fig 3,4 presents the same for ImageNet. The high CSL visualizations clearly show we identify memorized (but not mislabeled) examples in such cases. This visualization is similar to [3] who show similar figures with their proposed proxy of curvature.\n- Long Tail Behavior \n\t-  Clean CIFAR100 and ImageNet datasets are also long tailed [11]. Fig 5 and Fig 6 plots the histogram of CSL on CIFAR100 and ImageNet showing that CSL captures long tail behavior\n- Additional Results Under Higher Noise (Table 2 rebuttal page)\n    - We evaluate CSL under higher label noise settings.\n    - CSL maintains its ability to distinguish clean from mislabeled examples, indicating its robustness across different noise levels.\n\n3. On Other learning dynamics method?\n\n**A**: Please note, Second Split Forgetting time (SSFT), Forgetting time, learning time, in-confidence (1 - confidence) and Curvature are learning dynamics based methods and clearly we see that CSL out performs them in both mislabeled detection and duplicate detection (Tables 2 and 3 in the main paper).  Regarding similarity with memorization scores we have added forgetting frequency, loss sensitivity, final epoch loss to the (Table 1 rebuttal page) as additional baselines.  \n\n4. Supplementary Material\n\n**A**: Feldman and Zhang [11] ran Inception on CIFAR10/100 and ResNet50 on ImageNet. Additionally, we have added ResNet50 to ImageNet experiments (Table 1 rebuttal page) and Inception on CIFAR100. To save space we kindly ask the reviewer to see our response to reviewer ZrxQ Q1.\n \n5. There are several recent works that explore similar ideas but in a broader context,.. would improve the positioning of the paper.\n\n**A**: Thank you for bringing this to our attention. While these works share similar goals, they differ from ours. We will include them in the related work section. [7] measures performance across multiple models on a single input, while CSL analyzes the distribution of memorization scores within a single training run, with no added overhead. In contrast, [7] is significantly more computationally expensive. [8] addresses how memorization and spurious correlations hinder generalization and proposes MAT to mitigate them. Our work introduces CSL, a fast, theoretical metric for estimating memorization, which we apply to detect mislabeled and duplicate data. [9] explores how memorization fades when examples are removed. CSL, on the other hand, focuses on efficiently estimating how memorized each sample is, offering both theoretical grounding and empirical utility. [10] proposes data splitting for robust OOD training. CSL instead offers a lightweight and accurate method for measuring memorization. Additionally please see our response to reviewer WoPj Q5.\n\n[3] Garg et al. \"Memorization Through the Lens of Curvature of Loss Function Around Samples.\" ICML 24.\\\n[7] Kaplun et al. \"Deconstructing Distributions: A Pointwise Framework of Learning.\" ICLR 23\\\n[8] Bayat et al.  \"The Pitfalls of Memorization: When Memorization Hurts Generalization.\" ICLR 25\\\n[9] Jagielski et al. \"Measuring Forgetting of Memorized Training Examples.\" ICLR 23\\\n[10] Pezeshki, et al. \"Discovering Environments with XRM.\" ICML 24\\\n[11] Feldman & Zhang  \"What neural networks memorize and why: Discovering the long tail via influence estimation\" NeurIPS 20.", "claims_and_evidence": "The authors claim that CSL is a better measure of memorization than previous methods, particularly stability-based approaches. The experimental results generally support this, showing that CSL can effectively finds mislabeled and duplicate samples. But, the claims about general memorization seem a bit narrow becuase the paper mainly focuses on mislabeled examples and does not explore broader notions of memorization, such as how it relates to generalization or robustness. Some comparisons to existing memorization measures could be stronger, especially with alternative ways of grouping examples based on learning dynamics.", "methods_and_evaluation_criteria": "The method itself is quite simple: the authors track the cumulative loss over training and use this as a signal for memorization. The evaluation criteria, identifying mislabeled and duplicate samples make sense for the problem, but they don’t fully capture memorization in a more general sense. It would be good to see how CSL performs on other memorization-related tasks, such as distinguishing between easy-to-learn and hard-to-learn examples or detecting spurious correlations. The benchmarks used are reasonable, but additional datasets or different noise levels could provide a more complete picture.", "theoretical_claims": "There aren’t many deep theoretical results in the paper, but the reasoning behind CSL is intuitive and aligns with prior work on learning dynamics. The authors suggest that CSL correlates with memorization, but this is mostly supported empirically rather than through a formal analysis.", "experimental_designs_or_analyses": "The experiments are well-structured and support the main claims of the paper. The ablation studies show that CSL is effective at detecting mislabeled data, and the comparison with stability-based methods highlights its efficiency. However, the evaluation could be more comprehensive. For example, it would be useful to test CSL across different architectures or dataset sizes to see if the trends hold more broadly. Additionally, it would be good to analyze whether CSL correlates with other memorization-related signals, such as those used in curriculum learning or adversarial robustness.", "relation_to_broader_scientific_literature": "The paper is connected to prior work on memorization in deep learning, particularly methods that use learning dynamics to classify examples as memorized or generalized. However, it focuses mainly on mislabeled and duplicate examples, which is only one aspect of memorization. There are several recent works that explore similar ideas but in a broader context, including those that analyze memorization in terms of generalization or in terms of progressive learning dynamics. A more thorough discussion of how CSL fits within these broader frameworks would improve the positioning of the paper.", "essential_references_not_discussed": "There are a few missing references that seem very relevant to this work. For example:\n\nhttps://arxiv.org/abs/2202.09931 studies learning dynamics as a way to classify examples into different categories. At the core this is very similar to CSL.\nhttps://arxiv.org/abs/2412.07684 studies the connection between memorization and generalization.\nhttps://arxiv.org/pdf/2207.00099 and https://arxiv.org/pdf/2309.16748 also look at memorization from a learning dynamics perspective.", "other_strengths_and_weaknesses": "Strengths:\n- CSL is a very simple and computationally cheap approach, making it practical for real-world use.\n- The method effectively detects mislabeled and duplicate examples, which is useful for dataset curation, specially these days that curating datasets seems more important than ever.\n- The paper is well-written and easy to follow.\n\nWeaknesses:\n- The focus on mislabeled examples is somewhat narrow and does not fully capture the complexity of memorization.\n- The comparisons to existing memorization measures could be stronger, especially with alternative approaches that the effect of memorization on generalization.", "other_comments_or_suggestions": "- It would be helpful to clarify whether CSL is robust across different architectures or if it mainly works well for the specific models tested.\n- Some additional theoretical grounding for why CSL is expected to work better than other methods would strengthen the argument.", "questions_for_authors": "1. How does CSL compare to other learning-dynamics-based methods beyond stability-based memorization?\n2. Have you tried applying CSL to a setting where memorization is not just about mislabeled examples but also about spurious correlations? For example memorization of examples that all benefit from a spurious correlation.\n\n---\n# Update on Mar 31st:\n\nDear authors,\n\nAt AC's request, here I provide more details on my initial review. Apologies for any missing details. I would be happy to update my score once I receive your reply.\n\n## Which other architectures and dataset sizes?\nThis paper reports results using a ResNet-18. But they reports the results against the memorization scores precomputed in [1] which was using a ResNet-50. So it makes sense to report on a ResNet-50 with the exact setup described in Appendix B of [1].\n\nRunning experiments on modern architectures like ViTs, specially since they have different inductive biases compared to ResNets, would also strengthen the paper. But I don’t expect the authors to rerun all their experiments with ViTs.\n\nLet me elaborate why I wished to see further experiment: Another aspect of memorization, beyond mislabeled examples, is the memorization of underrepresented examples. For example, if you train a large model on just a handful of examples, the model gets zero training error but won’t generalize. According to the definition of the memorization score in [1] (the difference between held-in and held-out performance), this is memorization. It would be interesting to test whether CSL can also identify memorized (but not mislabeled) examples in such cases. A natural testbed would be long-tailed datasets like ImageNet-LT or CIFAR-LT, where certain classes are underrepresented.\n\n## Other memorization-related signals used in curriculum learning or adversarial robustness:\nIn curriculum learning, [2] uses forgetting frequency as a signal: how often a sample flips from being correctly to incorrectly classified. [3] uses loss trajectory clustering to group examples similar to CSL. [4] uses model confidence on the true class and the variability of that confidence across epochs.\n\nIn adversarial robustness, [5] proposes loss-sensitivity, suggesting that memorized examples are more easily perturbed. [6] uses sharpness of the loss function at convergence as another signal.\n\n## Other learning-dynamics-based methods:\nEach of the papers above suggests a different signal: loss sensitivity, forgetting frequency, confidence, or confidence variability that may be compared with CSL. A comparison to at least one of these could strengthen the paper.\n\n## The theory and the supplementary material:\nI checked the supplementary material. I had initially missed that the authors also conducted experiments with VGG, MobileNetV2, and Inception. However, since the ground-truth memorization scores are precomputed using a ResNet-50, it would make a lot of sense to include that for a more direct comparison.\n\nI also revisited the theoretical section in the appendix and realized I had initially missed the link the authors make between two parts: one showing that CSL bounds learning time, and the other that learning time bounds memorization. I now value the theoretical contribution more.\n\n\nThank you!\n\n[1] \"What neural networks memorize and why: Discovering the long tail via influence estimation\" Vitaly Feldman and Chiyuan Zhang. NeurIPS 2020.\n\n[2] \"An empirical study of example forgetting during deep neural network learning\" Toneva et al. ICLR 2019.\n\n[3] \"Deconstructing Distributions: A Pointwise Framework of Learning\" Kaplun et al. ICLR 2023.\n\n[4] \"Dataset Cartography: Mapping and Diagnosing Datasets with Training Dynamics. Swayamdipta et al. EMNLP 2020.\n\n[5] \"A Closer Look at Memorization in Deep Networks\" Arpit et al. ICML 2017.\n\n[6] \"Deep Nets Don't Learn via Memorization\" Krueger et al. ICLR 2017.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work proposes a new proxy for measuring memorization, namely using the Cumulative Sample Loss (CSL) that represents the loss of a sample accumulated over the entire training process. The method is less computationally expensive than prior approaches. The important aspect is the theoretical contribution to the analysis of memorization in supervised learning. All the Reviewers agree that this is an important contribution to our community.

The authors put a substantial effort into the rebuttal and addressed most of the Reviewers' comments. However, the empirical analysis is still lacking and more comparisons to baselines should be added. Additionally, the authors should add the missing citations that Reviewers mentioned. Overall, we expect the authors to update the paper according to the feedback from the Reviewers.
Decision: Accept (poster)