SALSA: A Secure, Adaptive and Label-Agnostic Scalable Algorithm for Machine Unlearning

Owais Makroo, Atif Hassan, Swanand Khare
Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, PMLR 286:2892-2905, 2025.

Abstract

Machine Learning as a Service (MLaaS) has simplified access to powerful machine learning models but faces challenges in complying with the “right to be forgotten” while resisting adversarial threats. Machine Unlearning (MU) addresses these issues by enabling selective data removal from models. However, existing methods are slow, label-dependent, vulnerable to black-box attacks, and computationally impractical for large-scale MLaaS deployments. We introduce SALSA, a Secure, Adaptive, Label-Agnostic, Scalable Algorithm for efficient and robust machine unlearning tailored to classification tasks in MLaaS. SALSA redistributes the class-wise predicted probabilities of data to be forgotten and optimizes a novel loss function that minimizes the divergence between redistributed and predicted probabilities while anchoring model parameters near their initialization. This ensures simultaneous unlearning and generalization. SALSA requires neither labels nor access to the remaining data, making it ideal for MLaaS environments. It is exceptionally fast, achieving at least $25\times$ faster unlearning, on average, than the fastest baseline, while consistently outperforming five state-of-the-art MU techniques across eight metrics on benchmark datasets. Experiments on synthetic data show that SALSA’s altered decision boundaries closely approximate exact unlearning. Rigorous evaluations against state-of-the-art black-box attacks demonstrate its resilience to security threats. Thus, SALSA redefines practical machine unlearning, offering a scalable and resilient solution for safeguarding privacy in modern MLaaS systems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v286-makroo25a, title = {SALSA: A Secure, Adaptive and Label-Agnostic Scalable Algorithm for Machine Unlearning}, author = {Makroo, Owais and Hassan, Atif and Khare, Swanand}, booktitle = {Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence}, pages = {2892--2905}, year = {2025}, editor = {Chiappa, Silvia and Magliacane, Sara}, volume = {286}, series = {Proceedings of Machine Learning Research}, month = {21--25 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v286/main/assets/makroo25a/makroo25a.pdf}, url = {https://proceedings.mlr.press/v286/makroo25a.html}, abstract = {Machine Learning as a Service (MLaaS) has simplified access to powerful machine learning models but faces challenges in complying with the “right to be forgotten” while resisting adversarial threats. Machine Unlearning (MU) addresses these issues by enabling selective data removal from models. However, existing methods are slow, label-dependent, vulnerable to black-box attacks, and computationally impractical for large-scale MLaaS deployments. We introduce SALSA, a Secure, Adaptive, Label-Agnostic, Scalable Algorithm for efficient and robust machine unlearning tailored to classification tasks in MLaaS. SALSA redistributes the class-wise predicted probabilities of data to be forgotten and optimizes a novel loss function that minimizes the divergence between redistributed and predicted probabilities while anchoring model parameters near their initialization. This ensures simultaneous unlearning and generalization. SALSA requires neither labels nor access to the remaining data, making it ideal for MLaaS environments. It is exceptionally fast, achieving at least $25\times$ faster unlearning, on average, than the fastest baseline, while consistently outperforming five state-of-the-art MU techniques across eight metrics on benchmark datasets. Experiments on synthetic data show that SALSA’s altered decision boundaries closely approximate exact unlearning. Rigorous evaluations against state-of-the-art black-box attacks demonstrate its resilience to security threats. Thus, SALSA redefines practical machine unlearning, offering a scalable and resilient solution for safeguarding privacy in modern MLaaS systems.} }
Endnote
%0 Conference Paper %T SALSA: A Secure, Adaptive and Label-Agnostic Scalable Algorithm for Machine Unlearning %A Owais Makroo %A Atif Hassan %A Swanand Khare %B Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2025 %E Silvia Chiappa %E Sara Magliacane %F pmlr-v286-makroo25a %I PMLR %P 2892--2905 %U https://proceedings.mlr.press/v286/makroo25a.html %V 286 %X Machine Learning as a Service (MLaaS) has simplified access to powerful machine learning models but faces challenges in complying with the “right to be forgotten” while resisting adversarial threats. Machine Unlearning (MU) addresses these issues by enabling selective data removal from models. However, existing methods are slow, label-dependent, vulnerable to black-box attacks, and computationally impractical for large-scale MLaaS deployments. We introduce SALSA, a Secure, Adaptive, Label-Agnostic, Scalable Algorithm for efficient and robust machine unlearning tailored to classification tasks in MLaaS. SALSA redistributes the class-wise predicted probabilities of data to be forgotten and optimizes a novel loss function that minimizes the divergence between redistributed and predicted probabilities while anchoring model parameters near their initialization. This ensures simultaneous unlearning and generalization. SALSA requires neither labels nor access to the remaining data, making it ideal for MLaaS environments. It is exceptionally fast, achieving at least $25\times$ faster unlearning, on average, than the fastest baseline, while consistently outperforming five state-of-the-art MU techniques across eight metrics on benchmark datasets. Experiments on synthetic data show that SALSA’s altered decision boundaries closely approximate exact unlearning. Rigorous evaluations against state-of-the-art black-box attacks demonstrate its resilience to security threats. Thus, SALSA redefines practical machine unlearning, offering a scalable and resilient solution for safeguarding privacy in modern MLaaS systems.
APA
Makroo, O., Hassan, A. & Khare, S.. (2025). SALSA: A Secure, Adaptive and Label-Agnostic Scalable Algorithm for Machine Unlearning. Proceedings of the Forty-first Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 286:2892-2905 Available from https://proceedings.mlr.press/v286/makroo25a.html.

Related Material