Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses

• URL: http://arxiv.org/abs/2606.01527v1
• Date: Mon, 01 Jun 2026 01:19:04 GMT
• Title: Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses
• Abstract summary: Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models.<n>We prove upper and lower bounds on the excess population risk of approximate $varepsilon$-unlearning.<n>Our algorithm offers an exponential accuracy improvement over retraining the model from scratch.
• Score: 12.206530775105962
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Machine unlearning is motivated by legal and user-facing requirements to remove the influence of individuals' data from trained models, such as the right to be forgotten. Prior work has developed algorithms and error bounds for unlearning in smooth strongly convex stochastic optimization, but the fundamental statistical cost of unlearning has remained unclear. We nearly resolve this problem by proving upper and lower bounds on the excess population risk of approximate $\varepsilon$-unlearning; our bounds are tight up to a condition-number factor. For mean estimation over the unit ball, our upper and lower bounds match. The optimal rate is the usual statistical error plus an unlearning penalty that interpolates between the retraining-from-scratch rate and an exponentially smaller term as $\varepsilon/d$ grows, where $d$ is the dimension of the model. In particular, when $\varepsilon \gg d$, our $\varepsilon$-unlearning algorithm offers an exponential accuracy improvement over retraining the model from scratch and differentially private baselines. On the other hand, when $\varepsilon \le d$, retraining from scratch is optimal.

Related papers

• Optimally taming biases in black-box models for efficient semiparametric estimation [13.159615239651258]
  We show that the standard DML rate is not optimal in the regime where auxiliary function $mathbbE[T|X=x]$ cannot be consistently estimated.<n>Our results reveal a new principle: the first-order error of nuisance estimation can be eliminated without imposing any additional assumptions.
  arXiv  Detail & Related papers  (2026-06-04T16:36:18Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth and the teacher's own predictions.<n>We show that for any prediction risk, the optimally mixed student improves upon the ridge teacher for every regularization level.<n>We propose a consistent one-shot tuning method to estimate $star$ without grid search, sample splitting, or refitting.
  arXiv  Detail & Related papers  (2026-02-19T17:21:15Z)
• Nearly Optimal Differentially Private ReLU Regression [18.599299269974498]
  We investigate one of the most fundamental non learning problems, ReLU regression, in the Differential Privacy (DP) model.<n>We relax the requirement of $epsilon$ and public data by proposing and analyzing a one-pass mini-batch Generalized Model Perceptron algorithm.
  arXiv  Detail & Related papers  (2025-03-08T02:09:47Z)
• Time Transfer: On Optimal Learning Rate and Batch Size In The Infinite Data Limit [1.8337746049048673]
  We show an intricate dependence of optimal $eta$ scaling on the pretraining token budget $T$, $B$ and its relation to the critical batch size $B_mathrmcrit$.<n>Surprisingly, our results demonstrate that the observed optimal $eta$ and $B$ dynamics are preserved with $mu$P model scaling.
  arXiv  Detail & Related papers  (2024-10-08T09:06:34Z)
• Approximation Rates and VC-Dimension Bounds for (P)ReLU MLP Mixture of Experts [17.022107735675046]
  Mixture-of-Experts (MoEs) can scale up beyond traditional deep learning models. We show that MoMLPs can generalize since the entire MoMLP model has a (finite) VC dimension of $tildeO(LmaxnL,JW)$.
  arXiv  Detail & Related papers  (2024-02-05T19:11:57Z)
• Certified Minimax Unlearning with Generalization Rates and Deletion Capacity [28.998771902033003]
  We study the problem of $(epsilon,delta)$-certified machine unlearning for minimax models. We develop a new minimax unlearning step of a total-Hessian-based complete update.
  arXiv  Detail & Related papers  (2023-12-16T06:03:23Z)
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion [46.46038357597395]
  We present new algorithms for optimizing non-known, non-smooth objectives based on a novel analysis technique.<n>For deterministic second-order smooth objectives, applying advanced optimistic online learning techniques enables a new $O(delta0.5) all$ to recover optimal or best-known results.
  arXiv  Detail & Related papers  (2023-02-07T22:09:20Z)
• Differentially Private Image Classification from Features [53.75086935617644]
  Leveraging transfer learning has been shown to be an effective strategy for training large models with Differential Privacy. Recent works have found that privately training just the last layer of a pre-trained model provides the best utility with DP.
  arXiv  Detail & Related papers  (2022-11-24T04:04:20Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression [6.594338220264161]
  achieve optimal predictive risk in machine learning problems requires interpolating the training data. We characterize how prediction (test) error necessarily scales with training error in this setting. optimal performance requires fitting training data to substantially higher accuracy than the inherent noise floor of the problem.
  arXiv  Detail & Related papers  (2022-02-20T18:51:45Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.