PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Unlearning via Algorithmic Stability

Enayat Ullah, Tung Mai, Anup Rao, Ryan Rossi, Raman Arora

arXiv:2102.13179v1cs.LGstat.ML

TL;DR

Machine unlearning asks how to remove the effect of edited data while preserving the distribution that retraining would produce. The paper introduces TV-stable learning, constructs noisy-SGD and coupling-based exact unlearning algorithms, and analyzes their accuracy and runtime, with extensions to privacy and non-convex optimization. Its main limitation is that efficient coupling construction and verification remain constrained in some settings.

  • Problem

    Exact unlearning requires undoing computations derived from deleted data, but retraining is computationally expensive and efficient methods are needed for broad convex ERM settings.

  • Method

    The paper develops TV-stable noisy-SGD algorithms and unlearning procedures based on efficient coupling of the corresponding Markov chains.

  • Results

    The algorithms provide exact unlearning with expected runtime below repeated retraining in supported regimes, while supplying excess empirical and population-risk bounds and extensions beyond convexity.

  • Takeaways & Limitations

    TV stability provides a general framework for exact unlearning, with coupling-based procedures that can avoid recomputation and can also yield differential privacy for some noisy-SGD algorithms.

  • Takeaways & Limitations

    Efficient maximal coupling remains unresolved when rejection sampling fails, and some marginal-density evaluations are infeasible for mini-batch SGD.

Abstract

from arXiv · show

We study the problem of machine unlearning and identify 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 design TV-stable algorithms based on noisy Stochastic Gradient Descent (SGD). Our key contribution is the design of corresponding efficient unlearning algorithms, which are based on constructing a (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 populations risk of TV stable algorithms for convex risk minimization. Our techniques generalize to arbitrary non-convex functions, and our algorithms are differentially private as well.

1 Introduction

The paper frames exact machine unlearning as reproducing the state that training would have produced without an edited datum, without paying the full cost of retraining. It introduces TV stability and develops efficient coupling-based unlearning for convex ERM, with extensions to privacy and non-convex optimization.

  • Motivation: Retraining satisfies exact unlearning but is computationally expensive, motivating algorithms whose unlearning runtime is below recomputation time.The paper studies smooth convex ERM, including linear and logistic regression, where prior structure-specific methods do not directly apply.
  • Motivation: Exact unlearning requires the post-edit model to be indistinguishable from training on the updated dataset at every point in an edit stream.The setup considers insertion and deletion requests and requires this property throughout the stream.
  • Contributions: TV stability is proposed as an algorithmic property that yields an in-principle exact unlearning algorithm and captures prior randomized unlearning methods as special cases.The framework is stated to be general, while efficient implementation still depends on computational and data-access constraints.
  • Contributions: For smooth convex ERM, the paper constructs TV-stable algorithms and corresponding exact unlearning algorithms that retrain on only a ρ fraction of edit requests while controlling excess risk.It also provides excess population-risk bounds and preliminary lower bounds for TV-stable algorithms.
  • Extensions: Some noisy-SGD-based TV-stable algorithms are also (ϵ, δ)-differentially private, while approximate unlearning can be reduced to differential privacy with accuracy–runtime trade-offs.The paper presents privacy as an extension rather than the primary objective.
  • Extensions: The framework extends beyond convexity: the unlearning techniques apply to finite-sum optimization and provide exact guarantees whenever the algorithm avoids recomputation.For non-convex models, accuracy is verified empirically, while gradient clipping can enforce Lipschitzness for runtime bounds.

2 Problem setup and preliminaries

The paper formalizes learning and unlearning as randomized procedures over models and metadata, defines exact unlearning for one-edit and streaming settings, and introduces TV stability as the key distributional notion. It connects TV distance to couplings that can support unlearning updates.

  • Problem setup: A procedure consists of a batch learner A that outputs a model and metadata, and an unlearning algorithm U that updates both using an edit request.The model output excludes metadata, although exact unlearning is defined over the full state.
  • Exact unlearning: Exact unlearning requires the updated learner distribution to equal the distribution produced by applying U after a one-point insertion or deletion.For randomized procedures, equality is required for every measurable event over the model–metadata state.
  • Exact unlearning: The stronger definition requires the entire state, including metadata, to satisfy exact unlearning rather than only the released model.The condition generalizes inductively to streams of edit requests.
  • Problem setup: The setup studies insertion and deletion streams while assuming the number of available data points remains between n/2 and 2n.This bounded-size condition is imposed at every point in the stream.
  • Convex ERM: The optimization setting uses smooth, Lipschitz, convex losses over a closed convex parameter set and evaluates expected excess empirical risk relative to the empirical minimizer.The framework is broad enough to include statistical M-estimation.
  • TV stability: ρ-TV stability bounds distributional change between neighboring datasets, and repeated applications extend the bound to datasets differing by multiple insertions and deletions.For datasets with k1 deletions and k2 insertions, the supplied bound is TV(A(S), A(S′)) ≤ (2k1 + k2)ρ.
  • Couplings: Couplings are joint distributions with the target learner distributions as marginals, and maximal coupling achieves mismatch probability equal to total variation distance.This characterization supplies the probabilistic basis for coupling-based unlearning.

3 Main results

The paper gives exact-unlearning algorithms for smooth convex ERM that trade accuracy against unlearning efficiency through the parameter ρ. The algorithms satisfy exact unlearning while recomputing only a ρ fraction of edit requests, with matching upper and lower bounds characterizing accuracy under TV stability.

  • Main theorem: Theorem 1 provides learning and unlearning algorithms for smooth convex ERM that satisfy exact unlearning at every edit in a stream.The guarantee applies to L-smooth, G-Lipschitz convex losses.
  • Main theorem: The algorithms achieve expected unlearning runtime O(max {min {ρ, 1} k · Training time, k}) for k edit requests.The runtime reflects recomputation on only a fraction controlled by ρ.
  • Trade-off: ρ controls the trade-off between accuracy and unlearning efficiency: setting ρ < 1 improves unlearning time while retaining non-trivial accuracy.Larger ρ permits smaller excess empirical risk but can require more retraining computation.
  • Comparison and population risk: For target excess empirical risk α, the method has expected unlearning time ρk · Training time(α), smaller than retraining after every edit when ρ < 1, while excess population risk is 1/√n + α.In the high-accuracy regime α < α0, the unlearning algorithms are as good as recomputation; the strict improvement is emphasized for lower accuracy.
  • Algorithms: The algorithms use standard SGD and noisy accelerated mini-batch-SGD, with noisy methods also connected to differential privacy.The coupling construction for noisy accelerated mini-batch-SGD is efficient but not maximal, leaving an accuracy gap relative to maximal coupling.
  • Accuracy bounds: The paper establishes upper and lower bounds for excess empirical risk of TV-stable algorithms, including a lower bound whose dependence on ρ and n is fundamental for non-trivial accuracy.The lower-bound result is stated for 0 < ρ < 1, while the regime ρ ≥ 1 imposes no constraint on the algorithm.

4 Main ideas

The paper connects exact unlearning to optimal transport and identifies total variation stability as the minimum-computation criterion for transporting outputs across dataset edits. It then develops TV-stable learning and coupling-based unlearning methods, while characterizing accuracy, runtime, and scope limitations.

  • Total variation stability: Total variation stability arises by modeling recomputation as the cost of changing one coupled output into another.Under this model, the minimum expected computation cost equals the total variation distance between neighboring output distributions.
  • Total variation stability: The sequential edit setting motivates requiring an initial output distribution to remain close in total variation to every possible post-edit distribution.The incoming edit is unknown when the initial model is generated, so stability must hold uniformly over possible updated datasets.
  • Algorithm design: The framework seeks algorithms that maximize convex ERM accuracy while retaining a corresponding efficient unlearning procedure.This differs from ordinary optimal transport because the learning algorithm, updated algorithm, and coupling must be constructed together.
  • Privacy connection: Differential privacy provides a related tool because Gaussian noise can yield both differential privacy and total variation stability.The paper discusses noisy SGD-based constructions and contrasts output privacy with protecting the entire internal state.
  • Coupling-based unlearning: Unlearning requires coupling optimization trajectories without access to the future post-edit distribution and with lower cost than independent retraining.The paper addresses this through couplings of Markov chains and verification-based partial or full recomputation.
  • Limitations: The approach has scope and implementation limits: maximal coupling can be difficult to sample efficiently, and marginal-density evaluation may be infeasible for mini-batch mixtures.The paper also notes that its lower-bound and runtime conclusions constrain what TV-stable methods can achieve within the framework.

5 Algorithms

The paper presents two TV-stable learning algorithms and corresponding exact-unlearning procedures. These procedures couple mini-batch choices and noisy optimization trajectories, verify whether updated iterates remain valid, and recompute only when verification fails.

  • Sub-sample-GD: Sub-sample-GD uses uniformly sampled mini-batches and stores indices, gradients, and iterates for later unlearning.Its unlearning procedure can reuse the saved trajectory when an edit does not require recomputation.
  • Noisy-m-A-SGD: Noisy-m-A-SGD adds Gaussian noise to accelerated mini-batch SGD and saves mini-batches, models, gradients, and noise vectors.The algorithm is presented as a noisy accelerated method for convex ERM and differential-private training.
  • Algorithm guarantees: The noisy-m-A-SGD stability bound is tight up to constants across all problem parameters.The paper states this result for the upper bound on the total variation stability parameter.
  • Verification: Verification checks whether an updated iterate is likely under the edited dataset; successful checks avoid extra computation, while failures trigger partial or full recomputation.The verification failure probability depends on the TV-stability parameter.
  • Sub-sample-GD unlearning: For sub-sample-GD, deletion edits inspect whether the deleted point appeared in saved mini-batches, while insertion edits couple mini-batch indices probabilistically.The resulting procedure satisfies exact unlearning and recomputes with probability at most 2kρ for k edits.
  • Noisy-m-A-SGD unlearning: For noisy-m-A-SGD, unlearning couples Markov-chain trajectories using mini-batch replacement, reflection maps, and iterative rejection sampling.The procedure verifies noisy iterates through estimated marginal-density ratios and satisfies exact unlearning.

6 Proofs of main results

The proofs combine two TV-stable learning algorithms with corresponding exact-unlearning procedures, establishing accuracy, recomputation, and runtime guarantees alongside lower bounds for TV-stable convex ERM.

  • Upper-bound algorithms: The proof combines sub-sample-GD and noisy-m-A-SGD with their corresponding unlearning algorithms.These are used to establish the theorem’s upper bounds.
  • Sub-sample-GD: Sub-sample-GD is ρ-TV stable, exactly unlearnable, and recomputes with probability O(ρ^k) over k edit requests.Efficient implementations have runtime bounded by the maximum of k and a recomputation term involving training time.
  • Noisy-m-A-SGD: Noisy-m-A-SGD is TV stable and exactly unlearnable, with excess empirical risk controlled by its iteration count and mini-batch size.Its unlearning procedure also provides probabilistic recomputation and efficient runtime guarantees.
  • Combining bounds: The analysis selects between the two algorithms by comparing their excess empirical risk bounds and runtime regimes.The noisy method’s condition identifies when its risk is no larger than sub-sample-GD’s, while the other algorithm covers the complementary regime.
  • Lower bounds: TV-stable convex ERM has nontrivial accuracy lower bounds obtained by reducing the problem to TV-stable mean computation.The reduction yields α ≥ 1/(ρn) in one regime and α ≥ 1/√(ρn) in another, which transfer to excess-risk lower bounds.

7 Discussion

The discussion identifies open gaps in optimal TV-stable accuracy, efficient maximal coupling, and the behavior of the framework beyond smooth convex losses.

  • Open gaps: The upper and lower excess empirical risk bounds for TV-stable algorithms do not match.The paper leaves open whether stronger lower bounds or better algorithms will close this gap.
  • Open gaps: The coupling procedure for noisy-m-A-SGD is sub-optimal by a T factor in the measure of its diagonal.An efficient maximal coupling remains an open problem, although an inefficient rejection-sampling construction exists.
  • Beyond smooth convexity: The work focuses on smooth convex loss functions, while trade-offs for strongly convex, non-smooth, and some non-convex classes remain to be investigated.The authors state that the unlearning techniques and results extend to general non-convex functions.

A Additional related work

The related-work discussion contrasts this framework with prior unlearning methods by emphasizing exactness, runtime, accuracy guarantees, and applicability beyond narrowly structured problems.

  • Prior approaches: Earlier approaches include statistical-query methods, SISA’s divide-and-conquer training, and Newton-step methods for generalized linear models.The cited methods differ in their computational strategies and guarantees.
  • Comparison with [NRSM20]: The proposed framework provides provable exact unlearning with probabilistic runtime guarantees, whereas [NRSM20] provides deterministic runtime with approximate (ε, δ)-DP-based unlearning.The comparison treats large ε and δ as weaker unlearning criteria.
  • Comparison with [NRSM20]: For smooth convex functions and k edit requests, [NRSM20] is described as using k^2 full-gradient computations, while the proposed algorithms use a minimum of two upper bounds.The runtime comparison accounts for recomputation cost through the mini-batch size and iteration count.
  • Comparison with [NRSM20]: When d ≥ (ρn)^(3/4), the proposed runtime is smaller than [NRSM20]’s, using kn rather than k^2n gradient computations.The passage also reports excess empirical risk of 1/√n when ρ = 1 for the proposed method.

B Proofs for Section 5.1

These proofs establish TV stability and accuracy for sub-sample-GD and noisy-m-A-SGD using subsampling, divergence bounds, and accelerated-SGD guarantees.

  • Sub-sample-GD stability: Sub-sample-GD’s stability follows by bounding the probability that sampled mini-batches contain the differing data point.A uniform bound gives TV distance at most Tm/n, and choosing m = ρn/T yields min{ρ,1}-TV stability.
  • Sub-sample-GD accuracy: Sub-sample-GD has exact unlearning because its output distributions can be coupled across neighboring datasets through shared sampling randomness.The proof then uses unbiased subsampled gradients and bounded variance to invoke SGD convergence guarantees.
  • Noisy-m-A-SGD stability: For noisy-m-A-SGD, Rényi-divergence analysis bounds the effect of differing samples after Gaussian noise and subsampling.Sequential composition, data processing, and Pinsker’s inequality convert the divergence bound into a TV-stability guarantee.
  • Noisy-m-A-SGD stability: The noisy algorithm’s final-iterate stability follows from applying data processing to the iterate sequence and then converting KL divergence to total variation.The resulting bound is uniform over neighboring datasets.
  • Noisy-m-A-SGD accuracy: The noisy algorithm’s accuracy uses unbiased subsampled gradients, added mean-zero Gaussian noise, and accelerated-SGD convergence on smooth convex functions.The noise preserves unbiasedness while increasing the variance term analyzed by the accelerated method.
  • Lower-bound construction: The lower-bound construction uses neighboring datasets and smooth G-Lipschitz convex functions whose noisy-SGD iterate distributions have separated total variation.This establishes that the stability-accuracy trade-off cannot be avoided by the analyzed procedure.

C.1 Unlearning for sub-sample-GD

The sub-sample-GD unlearning procedure transports mini-batch distributions after deletions or insertions, then couples optimization runs on neighboring datasets. This yields exact unlearning with recomputation controlled by TV stability.

  • Coupling construction: The coupling replaces or resamples affected mini-batch indices so trajectories on neighboring datasets can be updated without retraining from scratch.The construction handles deletion and insertion by coupling corresponding mini-batches across the two datasets.
  • Unlearning guarantee: For a ρ-TV-stable algorithm, coupling disagreement is bounded by the TV-stability parameter, and recomputation after k edits is at most 2kρ under the stated stream-size assumption.The bound applies when the number of samples remains between n/2 and 2n.
  • Mini-batch transport: Deletion and insertion procedures transform mini-batch sampling measures into the uniform measures for the edited datasets.The deletion and insertion constructions are shown to preserve the relevant mini-batch probability masses.
  • Maximal coupling: Maximal coupling uses acceptance probability 1 − TV(P, Q), with reflection mapping used when the two trajectory distributions disagree.The reflection-based construction produces a maximal coupling of the distributions over iterates.

C.2.3 Coupling Markov chains

The noisy-SGD iterates and mini-batches form Markov chains whose trajectories can be coupled through rejection sampling and reflection. The construction preserves the edited algorithm’s state distribution while bounding recomputation through TV stability.

  • Markov-chain representation: Noisy SGD generates iterates and mini-batches as a first-order Markov chain, with joint densities factored across successive states and batches.The state includes the noisy iterates and the mini-batching indices.
  • Mini-batch coupling: The unlearning algorithm couples mini-batch sequences by retaining unaffected indices and randomly replacing an affected index.The coupled sequences are constructed separately for the two neighboring datasets.
  • Trajectory coupling: It samples the original trajectory, applies sequential rejection sampling using conditional density ratios, and reflects an iterate when rejection fails.After reflection, training continues under the Markov chain for the edited dataset.
  • Distributional correctness: The coupling preserves the full state distribution, including mini-batch indices, not only the marginal distribution of iterates.This transport property is established for measurable events over iterates and batch sequences.
  • Efficiency: The probability that all rejection steps accept is bounded using conditional TV distances, and k edits have total variation at most 2kρ under the stream-size assumption.This leads to a recomputation bound through the acceptance probability of the coupling.

D.1 Learning runtime

The runtime analysis compares stochastic-gradient learning costs with edit-handling costs. Acceleration reduces the number of iterations and recomputation risk, while coupling-based unlearning has runtime proportional to the edit count and training cost.

  • Learning cost: Algorithm 1 uses mT stochastic-gradient oracle calls and achieves the optimal number of oracle calls for its accuracy.The stated count is the basis for comparing learning runtimes.
  • Acceleration: Acceleration permits larger mini-batches and fewer iterations than noisy-m-SGD, reducing the probability of recomputation without changing the relevant unlearning-time advantage.The comparison contrasts T^3 with T iteration scaling in the supplied discussion.
  • Variance reduction: Katyusha improves learning runtime and oracle complexity in the high-accuracy regime but does not improve unlearning time beyond the accelerated method.The supplied analysis attributes the lack of unlearning improvement to the resulting iteration count.
  • Unlearning runtime: For k edits, the expected number of recomputations is at most 4kρ, while Algorithm 3 has expected total runtime O(max{k, min{ρ, 1} k · Training time}).The recomputation bound applies to coupling-based unlearning with acceptance probability at least 1 − ρ.
  • Verification cost: Verification for Algorithm 4 has expected compute Tm(G+d)/n, reflecting gradient and d-dimensional rejection-sampling work only when affected batches occur.The runtime analysis counts expected affected iterations as Tm/n.
  • Space complexity: Algorithm 3 uses O(Tm + d) words of space by storing used-sample indicators and the d-dimensional model.The storage bound follows from a hash table over saved mini-batch usage.

E.1 noisy-m-SGD

Noisy-m-SGD provides a non-accelerated TV-stable learning and unlearning pair for smooth convex risk minimization. Its guarantees include exact unlearning, excess-risk control, and runtime scaling with the TV-stability parameter.

  • Accuracy and stability: For smooth G-Lipschitz convex losses, noisy-m-SGD achieves a ρ-TV-stable output with an excess empirical-risk bound.The risk guarantee is obtained by balancing the optimization and noise terms.
  • Algorithm: Noisy-m-SGD adds Gaussian noise to mini-batch stochastic-gradient updates and projects the resulting iterate.The algorithm saves the mini-batch, noise, iterate, and gradient information needed for unlearning.
  • Exact unlearning: The noisy-m-SGD learning algorithm and its unlearning algorithm satisfy exact unlearning at every point in the edit stream.The guarantee is stated for streams whose dataset size remains between n/2 and 2n.
  • Runtime: For k edit requests, expected total unlearning runtime is O(max{ρk · Training time, k}).The runtime combines the probability of recomputation with the per-edit processing cost.

E.2 quantized-m-SGD

Quantized-m-SGD extends randomized quantization from k-means to convex risk minimization by quantizing mini-batch gradients, enabling TV-stable learning and exact batch unlearning through coupled randomness. The resulting procedure provides stability, accuracy, and runtime guarantees for batch edits.

  • Extensions: The framework also connects randomized quantization with prior k-means unlearning and supplies TV-stable mean procedures with accuracy guarantees.The paper identifies prior quantization-based unlearning as a special case of its coupling framework.
  • Quantized-m-SGD: Randomized quantization makes nearby gradient vectors coincide with probability controlled by their distance, dimension, and lattice spacing.For a vector u, the probability of a quantization change within radius δ is bounded by 2dδ/τ.
  • Quantized-m-SGD: Quantized-m-SGD samples mini-batches, computes gradients, applies random-phase quantization, and updates the iterate.The algorithm operates for T iterations with mini-batch size m.
  • TV stability: Coupling shared mini-batch samples and quantization randomness bounds the total variation distance between outputs on edited datasets.The proof compares sub-sampled quantized gradients and propagates the bound across iterations.
  • TV stability: Proposition 8 establishes that the quantized procedure is (k1, k2, (k1 + k2)ρ)-TV stable for smooth, Lipschitz, convex losses.The stability parameters account for deletions and insertions between the two datasets.
  • Batch unlearning: The coupled construction yields exact batch unlearning, with recomputation probability and expected runtime bounded across streams of batch edits.Batch handling extends naturally to related stochastic-gradient procedures, while its computational benefit over one-by-one handling is at most a constant factor of two.

F.1.1 Lower bound I

This section develops lower bounds for TV-stable algorithms using reductions from stable mean estimation and high-dimensional geometric constructions. The results show that stability imposes an accuracy or sample-complexity cost.

  • Reduction: A reduction converts any ρ-TV-stable mean algorithm with accuracy α into a 0.1-TV-stable algorithm on a larger dataset.The constructed dataset repeats samples so that neighboring changes amplify stability from ρ to 0.1.
  • Lower-bound construction: The lower-bound construction uses a 1-Lipschitz convex loss and a bounded-diameter constraint set to reduce mean estimation to convex optimization.The resulting dataset is chosen so neighboring means occupy separated regions in high dimension.
  • Geometric argument: High-dimensional spherical-cap geometry makes the regions associated with neighboring datasets nearly disjoint under the assumed output-density condition.The construction controls intersection mass through dimension-dependent cap-volume bounds.
  • Assumptions: The lower-bound proof relies on an output distribution supported on the unit Euclidean ball with density bounded relative to the uniform measure.This is an explicit assumption used in the geometric argument.
  • Lower bound: For the constructed mean problem, the analysis derives the accuracy relation α ≥ 1/√(ρn).The bound follows after combining TV stability with probability mass constraints across separated regions.

G.1 Upper bounds

The paper bounds population risk for TV-stable algorithms by combining stability-based generalization with empirical-risk guarantees, and proves a matching-style lower-bound framework. These results quantify the accuracy–stability trade-off for convex optimization.

  • Upper bounds: Uniform stability plus expected excess empirical risk upper-bounds expected excess population risk.This connects the paper’s TV-stable optimization guarantees to standard stability-based generalization results.
  • Upper bounds: Theorem 8 gives population-risk guarantees for a ρ-TV-stable algorithm on smooth, Lipschitz, convex losses.The proof uses sub-sample-GD and noisy-m-SGD as the underlying procedures.
  • Sub-sample-GD: For sub-sample-GD, the excess population-risk bound combines terms scaling with 1/√n and √ρ/√n.The displayed derivation obtains the population bound from the empirical-risk guarantee and stability contribution.
  • Lower bounds: Theorem 9 establishes a lower bound on expected excess population risk for every ρ-TV-stable algorithm on a suitable data distribution.The proof includes the general 1/√n lower bound and reduces population-risk performance to empirical-risk performance.

H Algorithms for approximate unlearning

The approximate-unlearning construction uses differential privacy as a reusable private-computation oracle, periodically refreshing the model after a stream of edits. Its guarantees trade update cost against privacy and accuracy parameters.

  • Definitions: Approximate unlearning is defined through differential-privacy-style indistinguishability between outputs on neighboring datasets.The definition quantifies the guarantee over measurable output events.
  • Private oracle: The privateCompute oracle returns a differentially private solution with accuracy αprivate(n, ϵ, δ).The approximate-unlearning algorithm builds on repeated calls to this oracle.
  • Guarantees: Theorem 10 guarantees approximate unlearning throughout a stream of k edit requests while bounding the number of privateCompute calls.The stated runtime is at most 2ρk privateCompute oracle calls.
  • Privacy accounting: The construction uses group differential privacy to preserve the guarantee across multiple edits between oracle refreshes.The privacy parameters are adjusted according to the number of edits in the group.
  • Convex ERM: For convex ERM, the paper instantiates privateCompute with a differentially private convex-optimization solver and compares its accuracy–runtime trade-off with prior work.The comparison favors the proposed method in regimes with sufficiently small unlearning parameter ϵ.

I Experiments

Experiments on MNIST evaluate logistic regression under randomly permuted deletions and insertions, comparing test accuracy with unstable edits as noise varies. Increasing σ reduces unstable edits, while small σ=0.1 causes less accuracy degradation than the reduction in unstable edits.

  • Experimental setup: The experiment uses a 60k-point MNIST training set with 300 random deletions and 300 random insertions, evaluated using Algorithms 5 and 6.The model is logistic regression, formulated as a smooth convex risk minimization problem.
  • Results: As σ increases, the number of unstable edits—and therefore retrain triggers—decreases.Figure 3a reports test accuracy and unstable edits as functions of σ.
  • Results: At σ=0.1, accuracy degradation is relatively small compared with the reduction in unstable edits.
Loading 2102.13179v1…