Seminars

View all Seminars  |  Download ICal for this event

Machine UnLearning via Algorithmic Stability

Series: Department Seminar

Speaker: Prof. Raman Arora, Associate Professor, Department of Computer Science, Johns Hopkins University

Date/Time: Oct 03 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
With data-driven analysis and services becoming uber-pervasive and increasingly woven into our social fabric, there is a growing push for broader awareness about privacy and ownership of user data. These efforts have led to several regulatory bodies enacting laws such as the European Union General Data Protection Regulation (GDPR) and California Consumer Act, which empower the user with (among other things) the right to request to have their personal data be deleted (see Link This motivates the problem of machine unlearning wherein a deployed (trained) machine learning model needs updating to comply with requests to unlearn/forget/delete an individuals data from the training dataset.

In this work, we focus on the strictest notion of exact unlearning, where the goal is to return the state of a trained machine-learning system to what it would have been if the user data (which is to be deleted) were absent to begin with. A straightforward way to comply with exact unlearning is to recompute (or retrain) each time a data deletion request is made. This, however, is often computationally expensive, and the goal is to design unlearning algorithms that are more efficient than naively retraining from scratch. In this talk, we will look at a notion of algorithmic stability, Total Variation (TV) stability, which we argue is suitable for the goal of exact unlearning.

For convex risk minimization problems, we give TV-stable algorithms based on noisy Stochastic Gradient Descent (SGD) and corresponding efficient unlearning algorithms based on constructing a near-maximal coupling of Markov chains for the noisy SGD procedure. To understand the trade-offs between accuracy and unlearning efficiency, we give upper and lower bounds on excess empirical and population risk of TV stable algorithms for convex risk minimization. Our techniques generalize to arbitrary non-convex functions, and our algorithms are also differentially private. We extend our results and methods to general structured learning algorithms.

Host Faculty: Prof. Siddharth Barman