The phenomenon of model-wise double descent, where the test error peaks and then reduces as the model size increases, is an interesting topic that has attracted the attention of researchers due to the striking observed gap between theory and practice [Belkin et al., 2018]. Additionally, while double descent has been observed in various tasks and architectures, the peak of double descent can sometimes be noticeably absent or diminished, even without explicit regularization, such as weight decay and early stopping. In this paper, we investigate this intriguing phenomenon from the optimization perspective and propose a simple optimization-based explanation for why double descent sometimes occurs weakly or not at all. To the best of our knowledge, we are the first to demonstrate that many disparate factors contributing to model-wise double descent (initialization, normalization, batch size, learning rate, optimization algorithm) are unified from the viewpoint of optimization: model-wise double descent is observed if and only if the optimizer can find a sufficiently low-loss minimum. These factors directly affect the condition number of the optimization problem or the optimizer and thus affect the final minimum found by the optimizer, reducing or increasing the height of the double descent peak. We conduct a series of controlled experiments on random feature models and two-layer neural networks under various optimization settings, demonstrating this optimization-based unified view. Our results suggest the following implication: Double descent is unlikely to be a problem for real-world machine learning setups. Additionally, our results help explain the gap between weak double descent peaks in practice and strong peaks observable in carefully designed setups.

§ INTRODUCTION

The phenomenon of double descent [Belkin et al., 2018, Nakkiran et al., 2020], where the generalization error first decreases, increases, and then decreases again as the model size $P$ surpasses the dataset size $N$ (the interpolation threshold), has attracted a lot of attention from the machine learning community. This unexpected behavior calls into question the traditional understanding of generalization in both under- and over-parameterized regimes. Over the past few years, the double descent phenomenon has been observed in various models [Nakkiran et al., 2020, Chang et al., 2020, Sahraee-Ardakan et al., 2021, Fonseca and Guidetti, 2022] and learning paradigms [Nakkiran et al., 2020, Rice et al., 2020, Hassani and Javanmard, 2022, Dar and Baraniuk, 2020, Cotter et al., 2021]. Previous research has contributed to our understanding of the double descent phenomenon in various contexts and from different perspectives, including bias-variance trade-off tools [Yang et al., 2020, d'Ascoli et al., 2020], VC theory [Lee and Cherkassky, 2022], condition numbers [Kuzborskij et al., 2021, Schaeffer et al., 2023] (the ratio between the maximum and the minimum singular values of the data matrix for linear regression), and aspects of optimization [Kini and Thrampoulidis, 2020, Gamba et al., 2022, Gamba et al., 2023]. Although double descent is ubiquitous across many machine learning and deep learning setups, it is not always observed [Huang et al., 2020, Dar et al., 2020, Buschjäger and Morik, 2021, Ba et al., 2020, Wang and Bento, 2022], and depends heavily on various factors [Nakkiran et al., 2020, Krijthe and Loog, 2016, d'Ascoli et al., 2020, Lin and Dobriban, 2020, Qu'etu and Tartaglione, 2023, Qu'etu and Tartaglione, 2023, Gu et al., 2023].

Many factors contribute to double descent occurring or not occurring in any given deep learning setup. These include the initialization, learning rate, scale of features, normalization, batch size, and choice of optimization algorithm. For the first time, we demonstrate that the effect of all these disparate factors is unified into a single phenomenon from the viewpoint of optimization: double descent is observed if and only if the given optimizer[We use the term “optimizer” to refer to an optimization algorithm configured with the corresponding hyperparameters.] can find a sufficiently low-loss minimum. For hyper-parameters affecting the underlying optimization problem, the condition number (the ratio between the largest and the smallest singular values of the feature matrix) is affected, which in turn affects the minimum being found by the optimizer. For hyper-parameters affecting the optimizer directly, those that lead to a worse minimum reduce the peak of double descent. Although, in hindsight, these results are intuitive and almost obvious, we are unaware of any prior work connecting these phenomena in this simple manner.

Our results on simple random feature models and two-layer neural networks indicate that classifiers in practice are unlikely to exhibit the peaking phenomenon. First, inductive biases and hyperparameters are usually chosen carefully using a validation set to prevent overfitting so that no model is over-trained. Second, even if a model overfits, many iterations are required for critically parameterized models to exhibit a strong double descent curve (<ref>). Therefore, realistic setups already act as a “natural” mitigator of double descent. While no existing theoretical framework explains all our results, we believe our results are particularly useful for suggesting avenues for further theoretical study.

§ RELATED WORK

There has been some previous work investigating when the double descent phenomena occur and when it doesn't [Krijthe and Loog, 2016, Nakkiran et al., 2020, Huang et al., 2020, Dar et al., 2020, Buschjäger and Morik, 2021, Ba et al., 2020, Wang and Bento, 2022, Gu et al., 2023]. Previous work has shown that the number of iterations (early-stopping) can affect the double descent peak, and sometimes eliminate it [Nakkiran et al., 2020, Bodin and Macris, 2021, Yang et al., 2020]. A recent study also argues that the double descent occurs due to label noise [Gupta et al., 2023], but we show that double descent can be observed with clean datasets. However, we are unaware of any work investigating the effect of normalization, learning rate, batch size, choice of optimization algorithm, or the other hyperparameters we investigate on the observed peak in double descent.

Apart from the double descent phenomenon in generalization error, prior work, from the optimization perspective, has also identified a similar descent-like phenomenon in the condition number for simple linear regression problems. Specifically, for least-squares linear regression, prior theoretical and experimental work has shown that the condition number increases near the peak of the double descent, where the condition number here is the ratio between the maximum and the minimum singular values of the data matrix for linear regression. Poggio et al., 2019 is the first to show that the condition number for a random matrix peaks when the number of rows equals the number of columns for linear regression. Rangamani et al., 2020 demonstrated that the condition number regulates the stability of the least squares solution, which is why the error peaks at $P = N$. Kuzborskij et al., 2021 argued that the condition number of the feature matrix is determined only by the minimal singular value under the assumption that the maximum singular value is constant. Their theory included dependence of the excess risk on the minimal eigenvalue. Mei and Montanari, 2019 hypothesized that the peaking at $P = N$ can be explained by the explosion of the variance, which is related to the condition number.

To the best of our knowledge, previous studies have theoretically identified the peak in the condition number of random matrices and observed it in some real datasets but have not established a connection to the double descent curve. Our work connects the previous finding on the peaking of the condition number and its effect on a double descent curve. In <ref>, the condition number is largest at $P=N$ (the double descent peak), which agrees with theoretical results. We find that this makes optimization harder at $P=N$, so models are less likely to converge, which causes the peak of double descent to be reduced or disappear, but reappear with longer training (<ref>). This finding extends the previous ones because we show the interplay of the condition numbers in features and other elements in optimization. Our observation on condition number also extends the previous work in that we can control the magnitude of double descent by controlling the condition number, as shown in <ref>. Our work is also related to the mitigation of double descent, which we briefly discuss in <ref>.

§ EXPERIMENTAL SETUP

We present empirical evidence on random feature models trained on MNIST [LeCun et al., 2010] and include additional results for both random feature models and two-layer neural networks on Fashion-MNIST [Xiao et al., 2017] and CIFAR-10 [Krizhevsky, 2009] in <ref>. Full experimental details are given in <ref>. We also emphasize that we choose a setup that avoids known factors that could mitigate the double descent phenomenon as much as possible. Specifically, we do not use early stopping, which is known to remove the double descent phenomenon [Nakkiran et al., 2020, Bodin and Macris, 2021, Yang et al., 2020]. On the contrary, in the default setup, we train all models for a sufficient number of epochs (1000) so that most models converge in the first $1/10$ of the epochs. To further exclude the possibility of stopping too early, even in this scenario (which is not likely), we extend it to 10,000 epochs in <ref>. We also do not use any norm-based weight penalty to restrict the parameter space [Nakkiran et al., 2020] or add dropout layers during training. See <ref> for a detailed experimental setup.

Condition number, test error, and training loss on random feature models with varying properties features on an RFM with ReLU features. Darker colors represent higher condition number in row 1, weaker double descent in row 2, and high training loss in row 3. Row 1: Normalizing the data and increasing the scale of the features and random matrix yield better (smaller) condition numbers at $P = N$. Row 2: Double descent does not occur in unnormalized, small-scale input features and small random matrix initialization. Double descent is observed more strongly when a lower condition number is at the peak. Row 3: A higher double descent peak corresponds to a lower training loss at $P = N$.

§ POOR CONDITIONING REDUCES DOUBLE DESCENT

It is well-known from optimization theory that better conditioning leads to faster convergence for gradient descent optimization [Nesterov, 2018]. We observe that the height of the double descent peak negatively correlates with the condition number of the random feature matrices. In <ref>, we see that, at $P = N$, the peak in condition number is always present, regardless of the peak in double descent. However, the height of the condition number matters because the setting with a lower condition number (lighter color in row 1) corresponds to a more prominent double descent peak (lighter color in row 2). Here, the poor conditioning of the optimization problem makes it more difficult for the model around $P/N = 1$ and the optimization algorithm to converge to a sufficiently low-loss minimum, as illustrated in the third row in <ref>. Previous studies also have shown the condition number peaks at the peak of the double descent (which occurs at $P=N$) [Poggio et al., 2019, Rangamani et al., 2020, Huang and Yang, 2020, Kuzborskij et al., 2021, Chen and Schaeffer, 2021]. We observe this to be the case in <ref>, confirming the findings of these previous studies.

We see that the double descent peaks disappear when the feature matrix is 1) unnormalized, or when the random matrix/features have a smaller scale due to the 2) scaling of the features (e.g., scaling the feature matrix by a small constant) or 3) the initialization of the random matrix (e.g., from a normal distribution with a small variance) (because they all change the input features to the linear classifier). We plot the training loss and observe that the setting where double descent occurs has a training loss much smaller than one in which double descent does not occur (<ref>, bottom).
The condition number is largest at $P=N$ (the double descent peak) in <ref>, which agrees with prior theoretical results (see <ref>). We find that this makes optimization harder at $P=N$, so models do not converge, which causes the peak of double descent to be reduced or disappear, but reappear with longer training (<ref>). We observe that double descent tends to occur in better-conditioned matrices because a lower minimum is found by the optimizer.

§ SLOW-CONVERGENCE LEADS TO DISAPPEARANCE OF DOUBLE DESCENT

Our results suggest that a slow-convergence setting[We use the term “slow-convergence setting” to refer to situations where the model converges slowly given the optimization problem, the optimization algorithm, its associated hyperparameters, and all other hyperparameters.] often reduces or removes the peaking phenomenon, and fast-convergence setting (i.e., finding a lower minimum) restores the peaking phenomenon. We observe this pattern in hyperparameters that affect the optimizer, such as learning rate (constant and decay), batch size, and optimization algorithm. All three factors can be considered as affecting the convergence of the optimizer directly, where a higher minimum found by the optimizer corresponds to a less prominent peak.

We observe that a faster-convergence optimization algorithm that finds a lower loss minimum exhibits double descent more strongly, and slow-convergence settings may not exhibit it at all (last two columns of <ref>).
We observe that the peak height negatively correlates with the training loss at $P = N$. For curves with Cholesky decomposition, the error rate approaches random guessing in both ridge regression and logistic regression. Similar observations can be made on SAGA and SGD, where the double descent peak occurs mildly with a slight increase in test error.

We observe that low learning rates, which are insufficient to reach a low-loss minimum, reduce or eliminate the double descent peak (first column of <ref>).  When the overparameterization ratio $P/N$ is greater than $3$, using a lower learning rate has almost no impact on the test error, but it eliminates the peak without any form of explicit regularization. The same result holds for learning rate decay. We observe that faster learning rate decay has a similar effect to a small constant learning rate, and decaying every iteration removes the peak entirely. Both imply that the emergence of double descent requires maintaining a stable and large enough learning rate during training, corresponding to a faster convergence optimization setting that lands at a lower minimum loss.

We observe that large batch sizes reduce or eliminate the double descent phenomenon. In <ref>, the peaking phenomenon disappears on the generalization curve for batch sizes of 500 (full-batch) and 256. Modifying the batch size changes the number of updates the optimization algorithm performs. Thus, large batch sizes take fewer steps.

Test error and training loss on random feature models with varying learning rates, batch sizes, and optimization algorithms. Double descent occurs with a sufficiently large and steady learning rate, a small enough batch size, or a low-enough minimum is obtained by the optimizer.

§ TRAINING LONGER RECOVERS DOUBLE DESCENT

We show that for hyper-parameter setups that do not exhibit double descent, we can recover this phenomenon simply by running the optimization procedure longer to reach a lower training loss. In <ref>, we increase the number of iterations by a factor of 10 so that the training loss of a slow-convergence setting is aligned with or approaches the default (a much lower one). We observe that the double descent peak is recovered for all factors. Precisely, in <ref> for the learning rate (column 4) and batch size (column 6), both the test error and training loss curves with ten times the original epochs exactly overlap with curves produced by the faster-converging optimization setup (i.e., the larger learning rate of $1e^{-2}$ or the smaller batch size of $32$). Our results suggest that the optimization length is a simple but strong indicator of why double descent is observed in some realistic settings.

In practical settings, proper regularization often prevents models from reaching 0 training error. Even though no explicit regularization is applied, we usually do not continue training for a large number of epochs when the model has already overfit the training set. In our experiments, for double descent to recover <ref>, models are usually trained 200-400 times longer after converging to 0 training error, which is not realistic for deep and large models used in practice. This also implies that the peak's emergence rate largely depends on the specific optimization setup, where optimization settings that converge slowly do not exhibit the peaking behavior.

Test error and training loss on random feature models with varying learning rates, batch sizes, and optimization algorithms at 10x iterations. The peaking phenomenon is recovered as long as a sufficient number of gradient updates is applied, even for ill-conditioned features.

§ EXPERIMENTS WITH TWO-LAYER NEURAL NETWORKS

We present results on two-layer neural networks in <ref> in the Appendix. Despite the fact that two-layer neural networks are fully non-linear models, we observe that the results on two-layer neural networks are consistent with our previous findings on random feature models.

§ CONCLUSION

In dissecting the occurrence of double descent in machine learning, our study elucidates a unifying underlying phenomenon tied to optimization: double descent occurs when the optimizer can achieve a low-loss minimum. While seemingly disconnected, factors like initialization, learning rate, normalization, batch size, and optimizer choice work together to influence the overall optimization trajectory, thereby affecting the optimizer's path to a minimum. Our findings not only simplify the understanding of these variables but also shed light on the practical likelihood of double descent, which is minimized due to careful hyperparameter selections and inherent inductive biases in real-world setups. Although current theoretical frameworks fall short of encapsulating our observations entirely, our results shed light on promising directions for deeper theoretical scrutiny into the interplay between optimization and double descent, thereby paving the way for a deeper understanding of the intriguing phenomenon.

[Ba et al., 2020]
Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang.
Generalization of two-layer neural networks: An asymptotic viewpoint.
In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
URL <https://openreview.net/forum?id=H1gBsgBYwH>.

[Belkin et al., 2018]
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal.
Reconciling modern machine-learning practice and the classical bias-variance trade-off.
Proceedings of the National Academy of Sciences, 116:0 15849–15854, 2018.

[Bodin and Macris, 2021]
Anthony Bodin and Nicolas Macris.
Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model.
In Neural Information Processing Systems, 2021.
URL <https://api.semanticscholar.org/CorpusID:239616354>.

[Buschjäger and Morik, 2021]
Sebastian Buschjäger and Katharina Morik.
There is no double-descent in random forests.
ArXiv preprint, abs/2111.04409, 2021.
URL <https://arxiv.org/abs/2111.04409>.

[Chang et al., 2020]
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis.
Provable benefits of overparameterization in model compression: From double descent to pruning neural networks.
In AAAI Conference on Artificial Intelligence, 2020.

[Chen et al., 2021]
John Chen, Qihan Wang, and Anastasios Kyrillidis.
Mitigating deep double descent by concatenating inputs.
Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.

[Chen and Schaeffer, 2021]
Zhijun Chen and Hayden Schaeffer.
Conditioning of random feature matrices: Double descent and generalization error.
ArXiv preprint, abs/2110.11477, 2021.
URL <https://arxiv.org/abs/2110.11477>.

[Cotter et al., 2021]
Andrew Cotter, Aditya Krishna Menon, Harikrishna Narasimhan, Ankit Singh Rawat, Sashank J. Reddi, and Yichen Zhou.
Distilling double descent.
ArXiv preprint, abs/2102.06849, 2021.
URL <https://arxiv.org/abs/2102.06849>.

[Dar and Baraniuk, 2020]
Yehuda Dar and Richard Baraniuk.
Double double descent: On generalization errors in transfer learning between linear regression tasks.
ArXiv preprint, abs/2006.07002, 2020.
URL <https://arxiv.org/abs/2006.07002>.

[Dar et al., 2020]
Yehuda Dar, Paul Mayer, Lorenzo Luzi, and Richard G. Baraniuk.
Subspace fitting meets regression: The effects of supervision and orthonormality constraints on double descent of generalization errors.
In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2366–2375. PMLR, 2020.
URL <http://proceedings.mlr.press/v119/dar20a.html>.

[d'Ascoli et al., 2020]
Stéphane d'Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala.
Double trouble in double descent : Bias and variance(s) in the lazy regime.
In International Conference on Machine Learning, 2020a.

[d'Ascoli et al., 2020]
Stéphane d'Ascoli, Levent Sagun, and Giulio Biroli.
Triple descent and the two kinds of overfitting: where and why do they appear?
Journal of Statistical Mechanics: Theory and Experiment, 2021, 2020b.

[Defazio et al., 2014]
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien.
SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.
In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1646–1654, 2014.
URL <https://proceedings.neurips.cc/paper/2014/hash/ede7e2b6d13a41ddf9f4bdef84fdc737-Abstract.html>.

[Dhifallah and Lu, 2020]
Oussama Dhifallah and Yue M. Lu.
A precise performance analysis of learning with random features.
ArXiv preprint, abs/2008.11904, 2020.
URL <https://arxiv.org/abs/2008.11904>.

[Emami et al., 2020]
Melikasadat Emami, Mojtaba Sahraee-Ardakan, Parthe Pandit, Sundeep Rangan, and Alyson K. Fletcher.
Generalization error of generalized linear models in high dimensions.
In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2892–2901. PMLR, 2020.
URL <http://proceedings.mlr.press/v119/emami20a.html>.

[Fonseca and Guidetti, 2022]
Nayara Fonseca and Veronica Guidetti.
Similarity and generalization: From noise to corruption.
ArXiv preprint, abs/2201.12803, 2022.
URL <https://arxiv.org/abs/2201.12803>.

[Gamba et al., 2022]
Matteo Gamba, Erik Englesson, Marten Bjorkman, and Hossein Azizpour.
Deep double descent via smooth interpolation.
ArXiv preprint, abs/2209.10080, 2022.
URL <https://arxiv.org/abs/2209.10080>.

[Gamba et al., 2023]
Matteo Gamba, Hossein Azizpour, and Marten Bjorkman.
On the lipschitz constant of deep networks and double descent.
ArXiv preprint, abs/2301.12309, 2023.
URL <https://arxiv.org/abs/2301.12309>.

[Gu et al., 2023]
Yufei Gu, Xiaoqing Zheng, and Tomaso Aste.
Unraveling the enigma of double descent: An in-depth analysis through the lens of learned feature space.
ArXiv preprint, abs/2310.13572, 2023.
URL <https://arxiv.org/abs/2310.13572>.

[Gupta et al., 2023]
Arunav Gupta, Rohit Mishra, William Luu, and Mehdi Bouassami.
On feature scaling of recursive feature machines.
ArXiv preprint, abs/2303.15745, 2023.
URL <https://arxiv.org/abs/2303.15745>.

[Hassani and Javanmard, 2022]
Hamed Hassani and Adel Javanmard.
The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression.
ArXiv preprint, abs/2201.05149, 2022.
URL <https://arxiv.org/abs/2201.05149>.

[Hastie et al., 2019]
Trevor J. Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani.
Surprises in high-dimensional ridgeless least squares interpolation.
Annals of statistics, 50 2:0 949–986, 2019.

[Huang and Yang, 2020]
Hanwen Huang and Qinglong Yang.
Large scale analysis of generalization error in learning using margin based classification methods.
Journal of Statistical Mechanics: Theory and Experiment, 2020, 2020.

[Huang et al., 2020]
Lang Huang, Chao Zhang, and Hongyang Zhang.
Self-adaptive training: beyond empirical risk minimization.
In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a.
URL <https://proceedings.neurips.cc/paper/2020/hash/e0ab531ec312161511493b002f9be2ee-Abstract.html>.

[Huang et al., 2021]
Lang Huang, Chaoning Zhang, and Hongyang Zhang.
Self-adaptive training: Bridging the supervised and self-supervised learning.
IEEE transactions on pattern analysis and machine intelligence, PP, 2021.

[Huang et al., 2020]
Ningyuan Teresa Huang, David W. Hogg, and Soledad Villar.
Dimensionality reduction, regularization, and generalization in overparameterized regressions.
SIAM J. Math. Data Sci., 4:0 126–152, 2020b.

[Hui and Belkin, 2020]
Like Hui and Mikhail Belkin.
Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks.
ArXiv preprint, abs/2006.07322, 2020.
URL <https://arxiv.org/abs/2006.07322>.

[Kan et al., 2020]
Kelvin K. Kan, James G. Nagy, and Lars Ruthotto.
Avoiding the double descent phenomenon of random feature models using hybrid regularization.
ArXiv preprint, abs/2012.06667, 2020.
URL <https://arxiv.org/abs/2012.06667>.

[Kini and Thrampoulidis, 2020]
Ganesh Ramachandra Kini and Christos Thrampoulidis.
Analytic study of double descent in binary classification: The impact of loss.
2020 IEEE International Symposium on Information Theory (ISIT), pages 2527–2532, 2020.

[Krijthe and Loog, 2016]
Jesse H. Krijthe and M. Loog.
The peaking phenomenon in semi-supervised learning.
In International Workshop on Structural and Syntactic Pattern Recognition, 2016.

[Krizhevsky, 2009]
Alex Krizhevsky.
Learning multiple layers of features from tiny images.
Technical report, 2009.

[Kuzborskij et al., 2021]
Ilja Kuzborskij, Csaba Szepesvari, Omar Rivasplata, Amal Rannen-Triki, and Razvan Pascanu.
On the role of optimization in double descent: A least squares study.
In Neural Information Processing Systems, 2021.

[LeCun et al., 2010]
Yann LeCun, Corinna Cortes, and CJ Burges.
Mnist handwritten digit database.
ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, 2, 2010.

[Lee and Cherkassky, 2022]
Eng Hock Lee and Vladimir Cherkassky.
Vc theoretical explanation of double descent.
ArXiv preprint, abs/2205.15549, 2022.
URL <https://arxiv.org/abs/2205.15549>.

[Lin and Dobriban, 2020]
Licong Lin and Edgar Dobriban.
What causes the test error? going beyond bias-variance via anova.
J. Mach. Learn. Res., 22:0 155:1–155:82, 2020.

[Loureiro et al., 2022]
Bruno Loureiro, C'edric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala.
Fluctuations, bias, variance & ensemble of learners: Exact asymptotics for convex losses in high-dimension.
ArXiv preprint, abs/2201.13383, 2022.
URL <https://arxiv.org/abs/2201.13383>.

[Luzi et al., 2021]
Lorenzo Luzi, Yehuda Dar, and Richard Baraniuk.
Double descent and other interpolation phenomena in gans.
ArXiv preprint, abs/2106.04003, 2021.
URL <https://arxiv.org/abs/2106.04003>.

[Mei and Montanari, 2019]
Song Mei and Andrea Montanari.
The generalization error of random features regression: Precise asymptotics and the double descent curve.
Communications on Pure and Applied Mathematics, 75, 2019.

[Misra, 2020]
Diganta Misra.
Mish: A self regularized non-monotonic activation function.
In 31st British Machine Vision Conference 2020, BMVC 2020, Virtual Event, UK, September 7-10, 2020. BMVA Press, 2020.
URL <https://www.bmvc2020-conference.com/assets/papers/0928.pdf>.

[Nakkiran et al., 2020]
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.
Deep double descent: Where bigger models and more data hurt.
In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a.
URL <https://openreview.net/forum?id=B1g5sA4twr>.

[Nakkiran et al., 2020]
Preetum Nakkiran, Prayaag Venkat, Sham M. Kakade, and Tengyu Ma.
Optimal regularization can mitigate double descent.
ArXiv preprint, abs/2003.01897, 2020b.
URL <https://arxiv.org/abs/2003.01897>.

[Nesterov, 2018]
Yurii Nesterov.
Lectures on convex optimization.
URL <https://api.semanticscholar.org/CorpusID:125291746>.

[Paige and Saunders, 1982]
Christopher C. Paige and Michael A. Saunders.
Lsqr: An algorithm for sparse linear equations and sparse least squares.
ACM Trans. Math. Softw., 8:0 43–71, 1982.

[Patil et al., 2022]
Pratik V. Patil, Jin-Hong Du, and Arun K. Kuchibhotla.
Bagging in overparameterized learning: Risk characterization and risk monotonization.

[Patil et al., 2022]
Pratik V. Patil, Arun K. Kuchibhotla, Yuting Wei, and Alessandro Rinaldo.
Mitigating multiple descents: A model-agnostic framework for risk monotonization.
ArXiv preprint, abs/2205.12937, 2022b.
URL <https://arxiv.org/abs/2205.12937>.

[Poggio et al., 2019]
Tomaso A. Poggio, Gil Kur, and Andy Banburski.
Double descent in the condition number.
ArXiv preprint, abs/1912.06190, 2019.
URL <https://arxiv.org/abs/1912.06190>.

[Qu'etu and Tartaglione, 2023]
Victor Qu'etu and Enzo Tartaglione.
Can we avoid double descent in deep neural networks?

[Qu'etu and Tartaglione, 2023]
Victor Qu'etu and Enzo Tartaglione.
Dodging the sparse double descent.
ArXiv preprint, abs/2303.01213, 2023b.
URL <https://arxiv.org/abs/2303.01213>.

[Rangamani et al., 2020]
Akshay Rangamani, Lorenzo Rosasco, and Tomaso A. Poggio.
For interpolating kernel machines, minimizing the norm of the erm solution maximizes stability.
Analysis and Applications, 2020.

[Rice et al., 2020]
Leslie Rice, Eric Wong, and J. Zico Kolter.
Overfitting in adversarially robust deep learning.
In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8093–8104. PMLR, 2020.
URL <http://proceedings.mlr.press/v119/rice20a.html>.

[Sahraee-Ardakan et al., 2021]
Mojtaba Sahraee-Ardakan, Tung Mai, Anup B. Rao, Ryan A. Rossi, Sundeep Rangan, and Alyson K. Fletcher.
Asymptotics of ridge regression in convolutional models.
In International Conference on Machine Learning, 2021.

[Schaeffer et al., 2023]
Rylan Schaeffer, Mikail Khona, Zachary Robertson, Akhilan Boopathy, Kateryna Pistunova, Jason W. Rocks, Ila Rani Fiete, and Oluwasanmi Koyejo.
Double descent demystified: Identifying, interpreting & ablating the sources of a deep learning puzzle.
ArXiv preprint, abs/2303.14151, 2023.
URL <https://arxiv.org/abs/2303.14151>.

[Singla et al., 2021]
Vasu Singla, Sahil Singla, David Jacobs, and Soheil Feizi.
Low curvature activations reduce overfitting in adversarial training.
2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 16403–16413, 2021.

[Wang and Bento, 2022]
Jianxin Wang and José Bento.
Optimal activation functions for the random features regression model.
ArXiv preprint, abs/2206.01332, 2022.
URL <https://arxiv.org/abs/2206.01332>.

[Wilson and Izmailov, 2020]
Andrew Gordon Wilson and Pavel Izmailov.
Bayesian deep learning and a probabilistic perspective of generalization.
ArXiv preprint, abs/2002.08791, 2020.
URL <https://arxiv.org/abs/2002.08791>.

[Xiao et al., 2017]
Han Xiao, Kashif Rasul, and Roland Vollgraf.
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.
ArXiv preprint, abs/1708.07747, 2017.
URL <https://arxiv.org/abs/1708.07747>.

[Yang et al., 2020]
Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma.
Rethinking bias-variance trade-off for generalization of neural networks.
ArXiv preprint, abs/2002.11328, 2020.
URL <https://arxiv.org/abs/2002.11328>.

§ EXPERIMENTAL SETUP AND HYPERPARAMETERS

In this section, we described the detailed setup of the dataset, models, and training.

§.§ Datasets

We perform all experiments on MNIST [LeCun et al., 2010], Fashion-MNIST [Xiao et al., 2017], and CIFAR-10 [Krizhevsky, 2009]. We select small subsets of size $N$ from the full training set as our training data and evaluate the generalization error using the complete test set. We trained models for RFMs with a random feature size of up to $P / N = 5$, while for two-layer NNs, we utilize models up to $P / N = 5 \cdot C$ parameters, where $C$ is fixed at 10 in our setting. For two-layer NNs, the interpolation threshold is at $N \cdot C$ instead of $N$ [Belkin et al., 2018]. By default, we normalize the image pixel features to follow a normal distribution by applying the transformation $\frac{\mathbf{X} - \mu}{s} \cdot \gamma$, where $\mu, s, \gamma$ are the mean, standard deviation, and the scaling factor, respectively.

§.§ Training

For random feature models, we use static first-layer weights $\overline{\mathbf{W}}_0 \in \mathbb{R}^{d \times P}$ and trainable second-layer weights $\mathbf{W}_1 \in \mathbb{R}^{P \times C}$, where $P$ and $C$ represent the projected feature dimension and the number of classes, respectively. We initialize both weight matrices from $\overline{\mathbf{W}}_0 \sim \mathcal{N} \left( 0, \frac{k_0}{\sqrt{D}} \right)$ and $\mathbf{W}_1 \sim \mathcal{N} \left( 0, \frac{k_1}{\sqrt{P}} \right)$, where $k_0$ is a scaling factor for the standard deviation of the weight matrix, and $D$ represents the input feature dimension. $k_1$ is always 1 in all experiments. Bias terms are always set to 0, and the ReLU nonlinearity is used by default. Our setup for two-layer neural networks resembles that of a random feature model. The only difference is that the first layer weights are trained.

Optimization. In our learning rate decay experiments, we adopt an inverse square root schedule similar to Nakkiran et al., 2020, but we multiply the initial learning rate by the factor $\frac{1}{\sqrt{\lfloor t/l \rfloor}+1}$, where $t$ is the current iteration and $l$ is an interval parameter. By controlling the interval $l$, we modify the decay frequency during the training trajectory. In optimizer experiments, we select numerical solvers, Cholesky and QR [Paige and Saunders, 1982], for ridge regression and Newton-Cholesky for logistic regression because they obtain solutions with much lower loss than SGD. We also chose SAGA [Defazio et al., 2014] as an alternative gradient-based algorithm that (empirically) converges slower than SGD with momentum for comparison. A small regularization constant 1e-8 is used for numerical stability. In the 10x iteration experiments, we ensure that the number of gradient updates matches that in a mini-batch case. Given a full-batch setting, we calculate the extended number of iterations by $\mathcal{T}_{\text{new}} = \lceil N / b \rceil \cdot \mathcal{T}$, which is equal to the number of gradient updates in a mini-batch setting with batch size $b$ and $\mathcal{T}$ iterations.

Producing double descents. Consistent with Belkin et al., 2018 and Nakkiran et al., 2020, we employed the same set of hyperparameters for all model sizes and trained them using SGD with a fixed number of epochs and constant step size. The default hyperparameters are selected based on two training error constraints: 1) the largest model has to attain 0 training error within the first $1/10$ iterations, and 2) (at least) all models with $P \geq N$ have to converge to 0 training error before the final iteration. These constraints, derived from empirical observations, are fast in convergence and effective in generating the double descent phenomenon for both RFM and two-layer NN trained with SGD on MNIST and Fashion-MNIST. After some exploration, we use SGD with a Nesterov momentum of 0.95, a mini-batch size of 32, and a constant step size of 1e-2 for 1000 epochs. For two-layer NNs, we increase the step size to 5e-2 and the number of epochs to 1500. By default, we utilize the standard MSE loss. When a specific hyperparameter is studied, all other parameters follow the default ones. We primarily focus on the MSE loss because it has been heavily studied in the literature [Belkin et al., 2018, Hastie et al., 2019, Mei and Montanari, 2019, Emami et al., 2020, Dhifallah and Lu, 2020]. We follow the previous implementation and do not include softmax at the network output Belkin et al., 2018, Hui and Belkin, 2020. In our experiments, we strictly control the confounding variables with potential effects on the peak in all experiments, such as label noise, which could exacerbate the curve [Nakkiran et al., 2020, Gu et al., 2023], and all forms of weight decay and early stopping, which are known to flatten the peak [Nakkiran et al., 2020]. This ensures the robustness of our results. All experiments are repeated at least five times.

§ RELATED WORK ON DOUBLE DESCENT MITIGATION

While we do not intend to mitigate the double descent, our work investigates conditions under which the peak of double descent does or does not occur. Related, various techniques have been demonstrated to successfully reduce the peak, including $\ell_2$ regularization [Mei and Montanari, 2019, Nakkiran et al., 2020, Nakkiran et al., 2020, d'Ascoli et al., 2020, Lin and Dobriban, 2020, Kan et al., 2020, Qu'etu and Tartaglione, 2023, Qu'etu and Tartaglione, 2023], ensemble methods [Wilson and Izmailov, 2020, d'Ascoli et al., 2020, Loureiro et al., 2022, Patil et al., 2022], cross-validation [Patil et al., 2022], dimensionality reduction [Huang et al., 2020], input concatenation [Chen et al., 2021], and the type of non-linear random features [Dhifallah and Lu, 2020]. Several works claim that double descent is not observed in certain settings, even without the explicit mitigation techniques mentioned above. These settings include self-adaptive training [Huang et al., 2020, Huang et al., 2021], level of supervision [Dar et al., 2020, Luzi et al., 2021], random forest models [Buschjäger and Morik, 2021], a two-layer neural network with certain initialization of the first layer weight [Ba et al., 2020], and special activation functions [Wang and Bento, 2022, Singla et al., 2021]. We highlight that our focus in this paper is not to propose a technique to mitigate double descent. Instead, we find that the conditioning of the optimization problem and specific setups significantly affects the magnitude of the peaking phenomenon, and models in slower-convergence settings do not exhibit the peak. However, this observation might be helpful as a simple technique to mitigate double descent in practice, which we leave to future research. We also emphasize the importance of carefully examining the effect of optimization in producing double descent. This is because optimization is involved in almost all settings mentioned above. Therefore, it is crucial to identify whether the absence of double descent is due to optimization before examining other more complicated factors.

§ ADDITIONAL EXPERIMENTS

Here, we present the exact figures as in the paper's main text but on additional datasets (Fashion-MNIST and CIFAR-10) and two-layer neural networks. Our findings in the paper's main text generalize to these datasets and models.

§.§ Time Evolution of A Double Descent Curve

The time evolution of a double descent curve. At the interpolation threshold $P = N$, all models have achieved zero training error, and the peak starts to emerge only after zero training error is obtained.

We present the temporal evolution of a double descent curve through gradient descent iterations, demonstrating that the peaks form only post-model convergence. This aligns with the theoretical findings and synthetic experiments by Bodin and Macris, 2021, indicating that the peaking phenomenon at $P \approx N$ appears only beyond a certain iteration, with a monotonic curve prevailing prior. Figure <ref> illustrates the iteration-wise change in training/test error and loss. We discern that models at $P \approx N$ converge on the training set after 50 epochs. Moreover, a training span of fewer than 200 epochs is inadequate for these models to manifest the peaking phenomenon. Despite the model maintaining a zero training error up to the 1000-th epoch, the peak in test error initiates and escalates as the training loss goes down. This insight corroborates preceding studies [Nakkiran et al., 2020, Bodin and Macris, 2021], asserting that early stopping diminishes the peak. Yet, we contend that the use of early stopping in hyperparameter tuning might be excessive for this goal, given double descent necessitates a substantial number of iterations post-convergence to appear. Hence, from an optimization standpoint, mitigating double descent is feasible, provided a model is not over-trained.

§.§ Ill-Conditioned Non-Linear Features

For random feature models, another way to modify the input features is the choice of the non-linear function. Previous work shows that activation functions reduce the peaking phenomenon [Dhifallah and Lu, 2020], but we show that we can recover the peak by simply increasing the number of iterations. In the left figure of <ref>, we employ ReLU, mish [Misra, 2020], softsign, and sigmoid nonlinearities. ReLU and sigmoid show consistent behavior for both RFM and two-layer neural networks, even though activation functions operate differently on these two models (i.e., one with the input and the other with the intermediate embeddings). However, for mish and softsign, double descent is only observed in RFMs. In the second figure of <ref>, we show that the absence of double descent on sigmoid follows the same pattern as our previous experiments in <ref>. Non-linear features produced by sigmoid make optimization difficult, resulting in monotonicity, but we can recover the peaking phenomenon by scaling the number of iterations by 10.

[Varying nonlinearities]
[Increasing iterations]
Left: Test error and training loss curves for RFMs trained and four different activation functions. Models with activation functions that converge a higher training loss tend to avoid double descent. Given the same optimization and hyperparameter setup, the sigmoid activation does not exhibit double descent in RFM and two-layer neural networks. Right: Test error and training loss curves for RFMs trained and sigmoid activation. 10x iterations recover double descent. This matches our findings on the impact of a slow-convergence setting on double descent.

Additional results to support <ref> using the Fashion-MNIST dataset.

Additional results to support <ref> using the CIFAR-10 dataset.

[Two-layer neural network on MNIST]
[Two-layer neural network on Fashion-MNIST]
Additional results to support <ref>. Test error and training loss curves by (using) normalization, varying scale of features or initialization, learning rate, batch size, and optimization algorithm of a two-layer neural network on MNIST and Fashion-MNIST. The peaking phenomenon becomes less prominent as the features become worse-conditioned or directly using a slow-convergence setting.

§.§ Slow-Convergence Settings in Optimization

[RFM on Fashion-MNIST]
[RFM on CIFAR-10]
Additional results to support <ref>. Test error and training loss curves by varying learning rate, batch size, and optimization algorithm of a random feature model on Fashion-MNIST and CIFAR-10. The peaks are reduced on slow-convergence settings with too small a learning rate, too frequent learning rate decay, too large batch size, and slow-convergence settings.

[RFM on Fashion-MNIST]
[RFM on CIFAR-10]
Additional results to support <ref>. Test error and training loss curves of slow-convergence settings with 10x iterations of RFMs on Fashion-MNIST and CIFAR-10. We are able to recover the peaking phenomenon in all cases by scaling the number of iterations by a factor of 10.

[Two-layer neural network on MNIST]
[Two-layer neural network on Fashion-MNIST]
Additional results to support <ref>. Test error and training loss curves of slow-convergence settings with 10x iterations of two-layer neural networks on MNIST and Fashion-MNIST. We are able to recover the peaking phenomenon in all cases by scaling the number of iterations by a factor of 10.


11institutetext: School of Engineering, University of Edinburgh, Edinburgh EH9
3FB, UK 22institutetext: The Alan Turing Institute, London, UK
22email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# Why patient data cannot be easily forgotten?

Ruolin Su 1*1* Xiao Liu 1*1* Sotirios A. Tsaftaris 1122

###### Abstract

Rights provisioned within data protection regulations, permit patients to
request that knowledge about their information be eliminated by data holders.
With the advent of AI learned on data, one can imagine that such rights can
extent to requests for forgetting knowledge of patient’s data within AI
models. However, forgetting patients’ imaging data from AI models, is still an
under-explored problem. In this paper, we study the influence of patient data
on model performance and formulate two hypotheses for a patient’s data: either
they are common and similar to other patients or form edge cases, i.e. unique
and rare cases. We show that it is not possible to easily forget patient data.
We propose a targeted forgetting approach to perform patient-wise forgetting.
Extensive experiments on the benchmark Automated Cardiac Diagnosis Challenge
dataset showcase the improved performance of the proposed targeted forgetting
approach as opposed to a state-of-the-art method.

###### Keywords:

Privacy Patient-wise Forgetting Scrubbing Learning

**footnotetext: Contributed equally

##  1 Introduction

Apart from solely improving algorithm performance, developing trusted deep
learning algorithms that respect data privacy has now become of crucial
importance [1, 15]. Deep models can memorise a user’s sensitive information
[2, 10, 11]. Several attack types [23] including simple reverse engineering
[7] can reveal private information of users. Particularly for healthcare,
model inversion attacks can even recover a patient’s medical images [24]. It
is then without surprise why a patient may require that private information is
not only deleted from databases but that any such information is forgotten by
deep models trained on such databases.

A naive solution to forget a patient’s data is to re-train the model without
them. However, re-training is extremely time-consuming and sometimes
impossible [21]. For example, in a federated learning scheme [17], the data
are not centrally aggregated but retained in servers (e.g. distributed in
different hospitals) which may not be available anymore to participate in re-
training.

As more advanced solutions, machine unlearning/forgetting approaches aim to
remove private information of concerning data without re-training the model.
This involves post-processing to the trained model to make it act like a re-
trained one that has never seen the concerning data. Several studies have
previously explored forgetting/unlearning data and made remarkable progress
[5, 8, 9, 18, 19]. When the concept of machine unlearning/forgetting was first
developed in [5], they discussed forgetting in statistical query learning
[12]. Ginart et al. [8] specifically deal with data deletion in k-means
clustering with excellent deleting efficiency. Another approach is to rely on
variational inference and Bayesian models [18]. Recently, Sekhari et al. [19]
propose a data deleting algorithm by expanding the forgetting limit whilst
reserving the model’s generalization ability. Golatkar et al. [9] address
machine unlearning on deep networks to forget a subset of training data with
their proposed scrubbing procedure (shown in Fig. 1(a)), which adds noise to
model weights that are uninformative to the remaining data (training data
excluding the concerning data) to achieve a weaker form of differential
privacy [6].

Figure 1: (a) Visualisation of the scrubbing and targeted forgetting methods.
$\mathcal{D}_{r}$ and $\mathcal{D}_{f}$ are the retaining data and the
forgetting data. (b) Illustration of the two hypotheses. Blue contour
delineates a big sub-population of similar samples within a common cluster;
red contours denote several small sub-populations of distinct samples in edge
cases. blueXblack and redXblack are examples of samples to be forgotten.

Different from previous work, we specifically consider the scenario of
patient-wise forgetting, where instead of forgetting a selected random cohort
of data, the data to be forgotten originate from a patient. We hypothesise
(and show experimentally) that in a medical dataset, a patient’s data can
either be similar to other data (and form clusters) or form edge cases as we
depict in Fig. 1(b). These hypotheses are aligned with recent studies on long-
tail learning [4, 16], where different sub-populations within a class can
exist with some being in the so-called long tail.111There is also a connection
between edge cases and active learning [20], where one aims to actively label
diverse data to bring more information to the model. Subsequently, we will
refer to these cases as common cluster and edge case hypotheses.

We first study the patient-wise forgetting performance with simple translation
of an existing machine unlearning method developed in [9]. For patients under
different hypotheses, forgetting and generalisation performance obtained after
scrubbing [9] vary as detailed in Section 3. In particular, the scrubbing
method removes information not highly related to the remaining data to
maintain good generalisation after forgetting, which is a weaker form of
differential privacy [6]. When forgetting a patient under common cluster
hypothesis, adequate performance can be achieved with the scrubbing method by
carefully tuning the level of noise added to the model weights. When
forgetting an edge-case patient, the scrubbing method does not remove
specifically the edge-case patient’s information but noise will be introduced
to model weights corresponding to most of the edge cases in the remaining
dataset. Hence, the overall model performance will be negatively affected. In
fact, we observed in our experiment that data of a large portion of patients
are edge cases while for computer vision datasets, the selected random cohort
of data to be forgotten usually falls in the common cluster hypothesis. This
limits the application of the scrubbing method and possibly other machine
unlearning approaches that designed specifically for vision datasets to
patient-wise forgetting.

To alleviate the limitation, we propose targeted forgetting, which only adds
weighted noise to weights highly informative to a forgetting patient. In
particular, we follow [9] to measure the informativeness of model weights with
Fisher Information Matrix (FIM), which determines the strength of noise to be
added to different model weights. With the proposed targeted forgetting, we
can precisely forget edge case data and maintain good model generalisation
performance. For patient data fall under the common cluster hypothesis, the
algorithm can forget their information with the trade-off of the model
performance on the whole cluster. This implies that for some patients within
the common cluster hypothesis, it is not easy to forget them without
negatively affecting the model.

Contributions:

  1. 1.

We introduce the problem of patient-wise forgetting and formulate two
hypotheses for patient-wise data.

  2. 2.

We show that machine unlearning methods specifically designed for vision
datasets such as [9] have poor performance in patient-wise forgetting.

  3. 3.

We propose a new targeted forgetting method and perform extensive experiments
on a medical benchmark dataset to showcase improved patient-wise forgetting
performance.

Our work we hope will inspire future research to consider how different data
affect forgetting methods especially in a patient-wise forgetting setting.

##  2 Method

Given a training dataset $\mathcal{D}$, a forgetting subset
$\mathcal{D}_{f}\subset\mathcal{D}$ contains the images to be removed from a
model $A(\mathcal{D})$, which is trained on $\mathcal{D}$ using any stochastic
learning algorithm $A(\cdot)$. The retaining dataset is the complement
$\mathcal{D}_{r}$=$\mathcal{D}\setminus\mathcal{D}_{f}$, thus
$\mathcal{D}_{r}\cap\mathcal{D}_{f}=\emptyset$. Test data is denoted as
$\mathcal{D}_{test}$. For patient-wise forgetting, $\mathcal{D}_{f}$ is all
the images of one patient. Let $\mathbf{w}$ be the weights of a model. Let
$S(\mathbf{w})$ denote the operations applied to model weights to forget
$\mathcal{D}_{f}$ in the model, and $A(\mathcal{D}_{r})$ be the golden
standard model.

###  2.1 The scrubbing method

Assuming that $A(\mathcal{D})$ and $\mathcal{D}_{r}$ are accessible, Golatkar
et al. [9] propose a robust scrubbing procedure modifying model
$A(\mathcal{D})$, to brings it closer to a golden standard model
$A(\mathcal{D}_{r})$. They use FIM to approximate the hessian of the loss on
$\mathcal{D}_{r}$, where higher values in FIM denote higher correlation
between corresponding model weights and $\mathcal{D}_{r}$. With the FIM, they
introduce different noise strength to model weights to remove information not
highly informative to $\mathcal{D}_{r}$, and thus forget information
corresponding to $\mathcal{D}_{f}$. The scrubbing function is defined as:

$\mathrm{S}(\mathbf{w})=\mathbf{w}+\left(\lambda\sigma_{h}^{2}\right)^{\frac{1}{4}}F_{\mathcal{D}_{r}}(\mathbf{w})^{-1/4},$
(1)

where $F_{\mathcal{D}_{r}}(\mathbf{w})$ denotes the FIM computed for
$\mathbf{w}$ on $\mathcal{D}_{r}$. Scrubbing is controlled by two
hyperparameters: $\lambda$ decides the scale of noise introduced to
$\mathbf{w}$ therefore it controls the model accuracy on $\mathcal{D}_{f}$;
$\sigma_{h}$ is a normal distributed error term which simulates the error of
the stochastic algorithm, ensuring a continuous gradient flow after the
scrubbing procedure. Practically during experiments, the product of the two
hyperparameters is tuned as a whole.

The Fisher Information Matrix $F$ of a distribution $P_{x,y}(\mathbf{w})$
w.r.t. $\mathbf{w}$ defined in [9] is:

${F}=\mathbb{E}_{x\sim\mathcal{D},y\sim p(y\mid
x)}\left[\nabla_{\mathbf{w}}\log p_{\mathbf{w}}(y\mid
x)\nabla_{\mathbf{w}}\log p_{\mathbf{w}}(y\mid x)^{T}\right]$ (2)

To save computational memory, only the diagonal values for FIM are computed
and stored. The trace of FIM is calculated by taking the expectation of the
outer product of the gradient of a deep learning model. In a medical dataset,
the FIM ($F_{\mathcal{D}_{r}}(\mathbf{w})$) is derived by summing up the
normalised FIM of each patient’s data in the retaining set $\mathcal{D}_{r}$
and take the expectation at patient-level. Therefore, weights highly related
to the cluster’s features show high values in FIM because several cluster
patients within $\mathcal{D}_{r}$ are correlated to these weights. Whereas for
edge cases, no other patients are correlated with the same weights as of these
edge cases; thus, the aggregated values in FIM for weights corresponding to
edge cases are relatively small.

A value within $F_{\mathcal{D}_{r}}(\mathbf{w})$ reflects to what extent the
change to its corresponding weights $\mathbf{w}$ would influence the model’s
classification process on this set $\mathcal{D}_{r}$. Hence, if a model weight
is correlated with multiple data and thus considered to be important in
classifying these data, its corresponding value in FIM would be relatively
high, and vice versa. This also explains that weights correlated to data under
common cluster hypothesis hold larger value than edge case hypothesis.
Therefore, when scrubbing an edge case from a model, weights correlated to
other edge cases even within $\mathcal{D}_{r}$ are also less informative to
the remaining data thus will be scrubbed as well, making the model performance
be negatively affected.

###  2.2 The targeted forgetting method

Based on the idea of scrubbing model weights, and the connection between the
hessian of a loss on a set of data of a model and the extent to which the
weights are informative about these data, we develop the targeted forgetting
procedure. We assume access to the forgetting data $\mathcal{D}_{f}$ instead
of $\mathcal{D}_{r}$. We believe that even in a real patient-wise forgetting
scenario, temporary access to patient data is permissible until forgetting is
achieved.

We compute FIM for $\mathbf{w}$ on $\mathcal{D}_{f}$ instead of
$\mathcal{D}_{r}$ to approximate the noise added to model weights. Instead of
keeping the most informative weights corresponding to $\mathcal{D}_{r}$ as in
[9], our method precisely introduce noise to model weights highly informative
about $\mathcal{D}_{f}$ (see Fig. 1(a)). Our proposed targeted forgetting is
defined as:

$\mathrm{S_{T}}(\mathbf{w})=\mathbf{w}+\left(\lambda_{T}\sigma_{h_{T}}^{2}\right)^{\frac{1}{4}}F_{\mathcal{D}_{f}}(\mathbf{w})^{1/4},$
(3)

where $\lambda_{T}$ and $\sigma_{h_{T}}$ are analogous parameters to $\lambda$
and $\sigma_{h}$ defined in Eq 1.

Performance on the two hypotheses Common cluster hypothesis: Targeted
forgetting will add noise to the most informative model weights corresponding
to $\mathcal{D}_{f}$ so it will also reduce model performance on the
corresponding cluster in $\mathcal{D}_{r}$ and $\mathcal{D}_{test}$. Edge case
hypothesis: Targeted forgetting will precisely remove information of an edge
case and maintain good model performance. Results and discussion are detailed
in Section 3.

##  3 Experiments

We first explore why scrubbing [9] works well on computer vision datasets but
shows poorer performance on patient-wise forgetting. We conduct an experiment
to demonstrate the intrinsic dataset biases of CIFAR-10 [14] and ACDC [3].
Then, we compare the forgetting and model performance after forgetting
achieved using the scrubbing and our targeted forgetting methods.

Figure 2: Example images of ACDC dataset. DCM: dilated cardiomyopathy. HCM:
hypertrophic cardiomyopathy. MINF: myocardial infarction. NOR: normal
subjects. RV: abnormal right ventricle.

Datasets: CIFAR-10 has 60,000 images (size $32\times 32$) of 10-class objects.
The Automated Cardiac Diagnosis Challenge (ACDC) dataset contains 4D cardiac
data from 100 patients with four pathologies classes and a normal group. We
split the 100 patients into training and testing subsets. Overall, by
preprocess the patient data into $224\times 224$ 2D images, there are 14,724
images from 90 patients form $D$, and 1,464 images from 10 patients form
$\mathcal{D}_{test}$. Patients in both sets are equally distributed across the
five classes. Example images from the ACDC dataset are shown in Fig. 2. When
conducting experiments under the patient-wise forgetting scenario, we only
select one patient to be forgotten devising the forgetting set composed of all
the images of the same patient.

Implementation details: For CIFAR-10, we follow the implementation steps in
[9]. When training the ACDC classifier, the model has a VGG-like architecture
as in [22]. We use Cross Entropy as the loss function and use Adam optimizer
[13] with $\beta_{1}=0.5$, $\beta_{2}=0.999$. During training we use data
augmentation including random rotation, Gaussian blur, horizontal and vertical
flip. We train all classifiers with a learning rate of 0.0001 for 13 epochs.
The original model trained with all 90 patients has $0.00$ error on
$\mathcal{D}_{r}$ and $\mathcal{D}_{f}$, and $0.19$ error on
$\mathcal{D}_{test}$.

Figure 3: Histograms of re-training experiments. The y-axis refers to the
total number of patients/sets whose golden standard lies within an
interval(e.g. [95,100]) of x-axis.

###  3.1 The hardness of patient-wise forgetting

Here we compare between CIFAR-10 and ACDC to show that some patient data are
hard to learn and forget. For 90 patients in ACDC, we remove one patient’s
data and re-train a model on the remaining 89 to be the golden standard model,
$A(\mathcal{D}_{r})$. We then measure the error of the deleted patient on
$A(\mathcal{D}_{r})$. We repeat this for all 90 patients. For CIFAR-10, we
select 10 non-overlapping sets from its training set, each with 100 images
from the same class, to be the deleting candidates and repeat the re-train
experiments. Data are hard to generalize by its golden model show high error
on $A(\mathcal{D}_{r})$ and thus should be hard to forget.

Results and discussion: Fig. 3 collects the findings of this experiment as
histograms and shows the differences between the two datasets. Overall, for
ACDC, the 90 individually measured results of classification error of a
$\mathcal{D}_{f}$ on its corresponding golden model $A(\mathcal{D}_{r})$ vary
from 0$\%$ to 100$\%$, whereas in CIFAR-10, the 10 experimental results only
vary from 10$\%$ to 25$\%$. High golden model error on a $\mathcal{D}_{f}$
means that the model is unable to generalise to this patient’s data; thus,
this patient is not similar to any other patients in the training set, and
must belong to the edge case hypothesis. By considering a threshold of $50\%$
on the error of the golden model, we find that $>60\%$ of patients in ACDC can
be considered to belong to the edge case hypothesis. This is remarkably
different in CIFAR-10: golden model results concentrate at low error
indicating that few edge cases exist. In addition, as discussed in section
2.1, when dealing with edge cases, scrubbing can degrade model performance.
This will explain the results of the scrubbing method: under-performance in
ACDC because many patients fall under the edge case hypothesis.

Table 1: Forgetting results for four patients. We report Error $=1-$Accuracy
on the forgetting ($\mathcal{D}_{f}$) and test ($\mathcal{D}_{test}$) sets
respectively. Scrubbing Method refers to the method of [9] whereas Targeted
Forgetting refers to the method in Section 2.2. redRedblack and blueblueblack
denote the golden standard of forgetting performance for each row
respectively, with performance being better when it is closer to the standard.
With respect to error on $\mathcal{D}_{f}$ High noise level refers to the
noise strength when a method reaches 1.00 error; Medium: 0.85$\pm$0.05 error;
and Low: 0.14$\pm$0.05 error. The confidence bar is obtained over three
experiments.

Patient ID | Error on |  Golden Standard | Noise level
---|---|---|---
Low | Medium | High
Scrubbing |  | Targeted
---
Forgetting
Scrubbing |  | Targeted
---
Forgetting
Scrubbing |  | Targeted
---
Forgetting
| 94
---
(Edge)
| $\mathcal{D}_{f}$
---
$\mathcal{D}_{test}$
|  blue1.000$\pm$0.000
---
red0.237$\pm$0.002
| 0.154$\pm$0.005
---
0.671$\pm$0.012
| 0.174$\pm$0.020
---
0.223$\pm$0.011
| 0.859$\pm$0.010
---
0.739$\pm$0.007
| 0.851$\pm$0.018
---
0.291$\pm$0.005
| 1.000$\pm$0.000
---
0.746$\pm$0.008
| 1.000$\pm$0.000
---
0.316$\pm$0.002
| 5
---
(Edge)
| $\mathcal{D}_{f}$
---
$\mathcal{D}_{test}$
|  blue0.809$\pm$0.009
---
red0.253$\pm$0.026
| 0.127$\pm$0.022
---
0.394$\pm$0.017
| 0.121$\pm$0.019
---
0.269$\pm$0.004
| 0.853$\pm$0.020
---
0.624$\pm$0.015
| 0.857$\pm$0.002
---
0.407$\pm$0.001
| 0.997$\pm$0.003
---
0.696$\pm$0.002
| 1.000$\pm$0.000
---
0.506$\pm$0.002
| 13
---
(Cluster)
| $\mathcal{D}_{f}$
---
$\mathcal{D}_{test}$
|  blue0.202$\pm$0.004
---
red0.194$\pm$0.012
| 0.111$\pm$0.006
---
0.361$\pm$0.001
| 0.092$\pm$0.002
---
0.343$\pm$0.007
| 0.871$\pm$0.018
---
0.590$\pm$0.005
| 0.850$\pm$0.021
---
0.524$\pm$0.013
| 1.000$\pm$0.000
---
0.694$\pm$0.004
| 1.000$\pm$0.000
---
0.602$\pm$0.016
| 9
---
(Cluster)
| $\mathcal{D}_{f}$
---
$\mathcal{D}_{test}$
|  blue0.010$\pm$0.002
---
red0.233$\pm$0.007
| 0.176$\pm$0.005
---
0.402$\pm$0.012
| 0.152$\pm$0.009
---
0.442$\pm$0.001
| 0.892$\pm$0.003
---
0.643$\pm$0.006
| 0.862$\pm$0.005
---
0.613$\pm$0.001
| 0.998$\pm$0.002
---
0.699$\pm$0.005
| 0.995$\pm$0.005
---
0.656$\pm$0.001

###  3.2 Patient-wise forgetting performance

We focus on four representative patients using the analysis in Section 3.1:
patients 94 and 5 that fall under the edge case hypothesis; and patients 13
and 9 fall under a common cluster hypothesis. Here we consider a stringent
scenario: the re-trained golden standard model is not available for deciding
how much to forget, so the level of noise to be added during scrubbing or
forgetting is unknown. We adjust noise strength (low, medium and high) by
modulating the hyperparameters in both methods to achieve different levels of
forgetting.222For our experiments we fix to introduce noise to 1$\%$ most
informative weights (based on extensive experiments) when applying the
targeted forgetting. We assess forgetting performance by comparing against
golden standard models: A method has good forgetting performance by coming as
close to the performance of the golden standard model on $\mathcal{D}_{test}$.

Table 2: The average noise value added to weights at High (when achieving 1.00
error on $\mathcal{D}_{f}$). Note that medium and low noise is with 66.7$\%$
and 30.0$\%$ of high noise level respectively.

Patient ID | High
---|---
Scrubbing | Targeted Forgetting
94 (Edge) | 2.33E-05 | 3.00E-06
5 (Edge) | 1.65E-05 | 4.5E-06
13 (Cluster) | 1.6E-05 | 8.66E-06
9 (Cluster) | 1.43E-05 | 1.2E-05

Is targeted forgetting better for forgetting edge cases? For edge cases,
forgetting can be achieved (compared to the golden standard) at high level of
noise with both methods. However, the scrubbing method significantly degrades
the model generalisation performance. With targeted forgetting, good model
generalisation performance on $\mathcal{D}_{test}$ at all noise levels is
rather maintained. Additionally from Table 2 we observe that the scrubbing
method adds more noise to model weights to forget an edge case. This further
supports our discussion in section 2.1 on how the scrubbing method negatively
affects the overall model performance when forgetting edge case.

Is targeted forgetting better for forgetting common cluster cases? For common
cluster cases, both methods can achieve standard forgetting with a near low
level of noise with nice model’s generalisation performance on
$\mathcal{D}_{test}$, as shown in Table 1. For example for patient 13, the
test error of two methods at low noise level is $0.361$ and $0.343$, which is
close and relatively small. When the noise level grows to medium and high to
forget more, although the test error with two methods still being close, it
grows to a high value. Overall, when forgetting common cluster cases, the two
methods show similar good performance at a standard level of forgetting and
they both can forget more about a patient by sacrificing the model’s
generalisation.

Can patient data be completely forgotten? Overall, for edge cases, using
targeted forgetting, the patient-wise data can be completely forgotten
(achieving error higher than 0.80 (random decision for 5 classes in our case)
on $\mathcal{D}_{f}$) without sacrificing the model generalisation
performance. While for common cluster cases, it is less likely to forget the
patient data as completely forgetting will result the significantly degraded
generalisation performance with the scrubbing or our targeted forgetting. In
fact, the level of noise added to the model weights affects the trade-off
between model performance and respecting data protection. Higher noise leads
to more information being removed, thus protecting the data better yet
degrading the model accuracy. Therefore, the noise needs to be carefully
designed such that a sweet spot between forgetting and generalisation
performance can be achieved.

##  4 Conclusion

We consider patient-wise forgetting in deep learning models. Our experiments
reveal that forgetting a patient’s medical image data is harder than other
vision domains. We found that this is due to data falling on two hypotheses:
common cluster and edge case. We identified limitations of an existing state-
of-the-art scrubbing method and proposed a new targeted forgetting approach.
Experiments highlight the different roles of these two hypotheses and the
importance of considering the dataset bias. We perform experiments on cardiac
MRI data but our approach is data-agnostic, which we plan to apply on
different medical datasets in the future. In addition, future research on
patient-wise forgetting should focus on better ways of detecting which
hypothesis the data of patients belong to and how to measure patient-wise
forgetting performance with considering the two hypotheses.

##  5 Acknowledgements

This work was supported by the University of Edinburgh, the Royal Academy of
Engineering and Canon Medical Research Europe by a PhD studentship to Xiao
Liu. This work was partially supported by the Alan Turing Institute under
EPSRC grant EP/N510129/1. S.A. Tsaftaris acknowledges the support of Canon
Medical and the Royal Academy of Engineering and the Research Chairs and
Senior Research Fellowships scheme (grant RC-
SRF1819$\backslash$8$\backslash$25) and the [in part] support of the
Industrial Centre for AI Research in digitalDiagnostics (iCAIRD,
https://icaird.com) which is funded by Innovate UK on behalf of UK Research
and Innovation (UKRI) [project number: 104690].

## References

  * [1] Abadi, M., Chu, A., Goodfellow, I., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. pp. 308–318 (2016)
  * [2] Arpit, D., Jastrzkebski, 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–242. PMLR (2017)
  * [3] Bernard, O., Lalande, A., Zotti, C., Cervenansky, F., Yang, X., Heng, P.A., Cetin, I., Lekadir, K., Camara, O., Ballester, M.A.G., et al.: Deep learning techniques for automatic mri cardiac multi-structures segmentation and diagnosis: is the problem solved? IEEE transactions on medical imaging 37(11), 2514–2525 (2018)
  * [4] Buda, M., Maki, A., Mazurowski, M.A.: A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks 106, 249–259 (2018)
  * [5] Cao, Y., Yang, J.: Towards making systems forget with machine unlearning. In: 2015 IEEE Symposium on Security and Privacy. pp. 463–480 (2015). https://doi.org/10.1109/SP.2015.35
  * [6] Dwork, C., Roth, A., et al.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9(3-4), 211–407 (2014)
  * [7] Fredrikson, M., Jha, S., Ristenpart, T.: Model inversion attacks that exploit confidence information and basic countermeasures. In: Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. pp. 1322–1333 (2015)
  * [8] Ginart, A., Guan, M.Y., Valiant, G., Zou, J.: Making ai forget you: Data deletion in machine learning. arXiv preprint arXiv:1907.05012 (2019)
  * [9] Golatkar, A., Achille, A., Soatto, S.: Eternal sunshine of the spotless net: Selective forgetting in deep networks. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 9304–9312 (2020)
  * [10] Hartley, J., Tsaftaris, S.A.: Unintended memorisation of unique features in neural networks. arXiv preprint arXiv:2205.10079 (2022)
  * [11] Jegorova, M., Kaul, C., Mayor, C., O’Neil, A.Q., Weir, A., Murray-Smith, R., Tsaftaris, S.A.: Survey: Leakage and privacy at inference time. arXiv preprint arXiv:2107.01614 (2021)
  * [12] Kearns, M.: Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) 45(6), 983–1006 (1998)
  * [13] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In proc. ICLR (2015)
  * [14] Krizhevsky, A., et al.: Learning multiple layers of features from tiny images (2009)
  * [15] Liu, X., Tsaftaris, S.A.: Have you forgotten? a method to assess if machine learning models have forgotten data. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 95–105. Springer (2020)
  * [16] Liu, Z., Miao, Z., Zhan, X., Wang, J., Gong, B., Yu, S.X.: Large-scale long-tailed recognition in an open world. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2537–2546 (2019)
  * [17] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial intelligence and statistics. pp. 1273–1282. PMLR (2017)
  * [18] Nguyen, Q.P., Low, B.K.H., Jaillet, P.: Variational bayesian unlearning. Advances in Neural Information Processing Systems 33 (2020)
  * [19] Sekhari, A., Acharya, J., Kamath, G., Suresh, A.T.: Remember what you want to forget: Algorithms for machine unlearning. arXiv preprint arXiv:2103.03279 (2021)
  * [20] Settles, B.: Active learning literature survey (2009)
  * [21] Shintre, S., Roundy, K.A., Dhaliwal, J.: Making machine learning forget. In: Annual Privacy Forum. pp. 72–83. Springer (2019)
  * [22] Thermos, S., Liu, X., O’Neil, A., Tsaftaris, S.A.: Controllable cardiac synthesis via disentangled anatomy arithmetic. In: MICCAI (2021)
  * [23] Truex, S., Liu, L., Gursoy, M.E., Yu, L., Wei, W.: Demystifying membership inference attacks in machine learning as a service. IEEE Transactions on Services Computing (2019)
  * [24] Wu, M., Zhang, X., Ding, J., Nguyen, H., Yu, R., Pan, M., Wong, S.T.: Evaluation of inference attack models for deep learning on medical data. arXiv preprint arXiv:2011.00177 (2020)

##  6 Appendix

Figure A1: Histograms of re-training experiments. The y-axis refers to the
total number of patients/sets whose golden standard lies within an
interval(e.g. [95,100]) of x-axis.

We explore if overfitting would be an issue affecting the results in Section
3.1 by redoing the experiment by early-stop training models. With all the
settings being the same as in Section 3, the training epochs for the 90
individual models is changed from 13 to 7 to obtain less overfitted models.

Fig. A1 collects the results with early stop models. Overall, compared with
Fig.3 in Section 3.1, although the distribution of the early stop results
histogram is slightly different, the 90 individually measured results of
classification error of a $\mathcal{D}_{f}$ on its corresponding golden model
$A(\mathcal{D}_{r})$ also vary from 0$\%$ to 100$\%$. By considering a
threshold of $50\%$ on the error of the golden model, there are still $>50\%$
of patients in ACDC can be considered to belong to the edge case hypothesis.
Therefore, overfitting is not considered the reason for the emergence of edge
cases.