Descent-to-Delete: Gradient-Based Methods for Machine Unlearning (2020-07-06T00:00:00.000000Z)

TL;DR

This work gives the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence.

Abstract

We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.

Authors

Aaron Roth

9 papers

Seth Neel

4 papers

Saeed Sharifi-Malvajerdi

2 papers

Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

TL;DR

Abstract

Authors

References23 items

When Machine Unlearning Jeopardizes Privacy

Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations

Machine Unlearning

Certified Data Removal from Machine Learning Models

Pan-Private Uniformity Testing

Making AI Forget You: Data Deletion in Machine Learning

Machine, Unlearning

Membership Inference Attacks Against Machine Learning Models

Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds

Federated Learning of Deep Networks using Model Averaging

Towards Making Systems Forget with Machine Unlearning

The Algorithmic Foundations of Differential Privacy

Comunication-Efficient Algorithms for Statistical Optimization

Differential privacy under continual observation

Smooth sensitivity and sampling in private data analysis

Calibrating Noise to Sensitivity in Private Data Analysis

Random sampling with a reservoir

Ele 522 lecture notes: Gradient methods for unconstrained problems

Convex analysis and nonsmooth optimization, 2017. URL https://sites.math.washington.edu/ ̃burke/crs/516/ notes/graduate-nco.pdf

Let h be convex and M -smooth, and let θ∗ ∈ argminθ∈Θ h(θ). We have that after T steps of GD with step size ηt = 1

regression as long as the data distribution satisfies standard regularity conditions

Let's focus on the base case i = 1. For any partition j such that s 1j = 0, because the update algorithm doesn't make any updates

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names