Gaussian certified unlearning in high dimensions: A hypothesis testing approach
Authors: Aaradhya Pandey
Arnab Auddy
Haolin Zou
Arian Maleki
Sanjeev Kulkarni
Venue: ICLR 2026 Oral (2026)
Keywords: Machine unlearning in high dimensions
Proportional asymptotics
High dimensional statistical theory
Privacy–accuracy tradeoff
Hypothesis testing
Gaussian noise calibration
Newton method
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We introduce the canonical dimension free notion of certifiability suitable to high dimensions and show its utility via a Newton based unlearning algorithm

Abstract: Machine unlearning seeks to efficiently remove the influence of selected data while preserving generalization. Significant progress has been made in low dimensions, where the dimension of the parameter $p$ is  much smaller than the sample size $n$, but high dimensions, including proportional regimes $p \sim n$, pose serious theoretical challenges as standard optimization assumptions of $\Omega(1)$ strong convexity and $O(1)$ smoothness of the per-example loss $f$ rarely hold simultaneously in proportional regimes $p\sim n$.
In this work, we introduce $\varepsilon$-Gaussian certifiability, a canonical and robust notion well-suited to high-dimensional regimes, that optimally captures a broad class of noise adding mechanisms. Then we theoretically analyze the performance of a widely used unlearning algorithm based on one step of the Newton method in the high-dimensional setting described above. Our analysis shows that a single Newton step, followed by a well-calibrated Gaussian noise, is sufficient to achieve both privacy and accuracy in this setting. This result stands in sharp contrast to the only prior work that analyzes machine unlearning in high dimensions \citet{zou2025certified}, which relaxes some of the standard optimization assumptions for high-dimensional applicability, but operates under the notion of $\varepsilon$-certifiability. That work concludes %that a single Newton step is insufficient even for removing a single data point, and
that at least two steps are required to ensure both privacy and accuracy. Our result leads us to conclude that the discrepancy in the number of steps arises because of the sub optimality of the notion of $\varepsilon$-certifiability and its incompatibility with noise adding mechanisms, which $\varepsilon$-Gaussian certifiability is able to overcome optimally.

Published as a conference paper at ICLR 2026
GAUSSIAN CERTIFIED UNLEARNING IN HIGH DIMEN- SIONS: A HYPOTHESIS TESTING APPROACH
Aaradhya Pandey', Arnab Auddy?, Haolin Zou", Arian Maleki", Sanjeev Kulkarni' Princeton University The Ohio State University SColumbia University
ap9898@princetonn edu, auddy. 18osu. edu, hz2574 17744//olmbii....mm mm43390columbia edu,
ABSTRACT
Machine unlearning seeks to efficiently remove the influence of selected data while preserving generalization. Significant progress has been made in low dimensions, where the dimension of the parameter p is much smaller than the sample size n, but high dimensions, including proportional regimes p n. pose serious theoretical challenges as standard optimization assumptions of (1)) strong convexity and (()) smoothness of the per-example loss f rarely hold simultaneously regimes p ~ n. In this work, we introduce e e-Gaussian certifiability, canonical and robust notion well-suited to high- nigh-dimensional regimes, that optimally captures a broad class of noise adding mechanisms. Then we theoretically analyze the performance of widely used unlearning algorithm based on one step the Newton method in the high gigh-dimensional setting deseribed above. Our analysis shows that a single Newton step, followed by a well well-calibrated Gaussian noise, is sufficient to achieve both privacy and accuracy in this setting. This result stands in sharp contrast to the only prior work that analyzes machine unlearning in high dimensions of the standard optimization assumptions
proportional
Zou al. 2025), which relaxes for high-dimensional applicability, but operates under the notion of e-certifiability. That work concludes that at least two steps are required ensure both privacy and accuracy. Our result leads us to conclude that the discrepancy in the number of steps arises because of the sub optimality of the notion of E-Certifiability and its incompatibility with noise adding mechanisms, which e- g-Gaussian certifiability is able overcome optimally.
INTRODUCTION AND THEORETICAL CONTRIBUTIONS
Modern ML models (from healthcare tools to systems like ChatGPT) are trained data that often includes sensitive personal information, creating risks memorization and leakage. Laws such as Union (2016); of California Department of Justice (2018); of Canada (2022) enforce a "right to be forgotten," requiring removal of both the data and its statistical influence on trained models. Because full retraining is costly, machine unlearning develops efficient methods to remove data traces while preserving model generalization. Recent years have seen rapid progress, fueled by substantial empirical results and rigorous theory Cao & Yang (2015), Bourtoule al. (2021). Chen al. (2021). )
Gupta et al. (202T) Ullah et al. (2021), et al. (2022). Chundawat et al. (2023) Warnecke let al. (2023). Tarun et al. (2024). Wang et al. (2024). Liu et al. (2025).
In addition to substantial progress in the practical development of machine unlearning algorithms, their theoretical understanding has also advanced significantly recent years. For example, Guo et al.. (2020) and /ekhari et al. (202T) studied Newton-bused unlearning algorithms and concluded that single Newton update, followed by appropriately calibrated noise, sufficient to ensure privacy for users requesting data removal while preserving the accuracy of the resulting estimates. In addition, Neel et al. (2021), }. Allouah et al. (2025b) examined the performance of approximate unlearning algorithms based gradient descent and stochastic gradient descent. Moreover, there have been recent works Ginart et al. (2019), Qiao et (2025), ). |Hu et al. (2025), (Shen et al. (2025) developing algorithms for online unlearning to handle continuous unlearning requests.
To fix ideas, consider a supervised learning problem of predicting response y based on p-dimensional feature based on training samples z; (æ,, IR++1 for [n]. A popular parametric

---

Published as a conference paper at ICLR 2026
version of the above problem is to consider the following optimization problem:
1 a = Σ [(3, i=1
arg min 3
arg min
[(3,2)) z.),
B n
where ((3,2) 2;) the per-example cost with n datapoints.
An important caveat in these theoretical papers is they implicitly assume the number of model param- eters p is significantly smaller than the number of observations n, by putting standard optimization assumptions on the loss, which fails to hold in high-dimensional proportional regimes. We prove this point later this section. So, these results are not useful for many Al applications, wherein the number of model parameters p is very large and comparable to the sample sizen. We refer to this as the high-ding nigh-dimensional setting, in contrast to the low-dimensional setting considered in Guo et al. (2020), Sekhari et al. 202T), Neel al. (202I). and Allouah et al. (2025b).
In the remaining of this section, we first show why the standard optimization assumptions of the per-example loss in Allouah et al. (2025b); /Skhari et al. (2021) break down in high dimensions. Then we compare our theoretical conclusions with Zou et al. (2025), as is most closely aligned with ours in high dimensions. We then describe our proposed method and its performance.
Failure of the assumptions in Allouah et al. (2025b), (Skhari et al. (2021). In their theory Allouah et al. 2025b) assumed] that f satisfies the standard optimization assumptions. More precisely, they assume B + f(B, zi) is simultancously p-strongly convex and L-smooth, i.c.,
plp < V [(3,2.) 3 LIp for all z;
for (11 and μ (1)). These two cannot hold simultaneously in high-dimensional pro- portional regime p ~ n. In fact these are even violated in simple examples such as linear regres- sion. To prove this, we consider one of the simplest estimators based on ridge regularized least square loss: >" 11 fB3, 2.) 0||2 + >i (1 x; 333 A computation of the Hessian gives 2X X + 2X1p- In high dimensional proportional regime p n that is studied in this paper, the condition = (1) smoothness constant of the per-example loss f in- evitably requires the scaling ||æ;||2 2/2 ~ (with high probability) for all E [n]]. which in turn requires = O(1). This, however, completely destroys the 211) strong convexity of the per-example loss f. as Amin f 2,) = -2.- More details can be found in Section D of the appendix.
4 V= [(,22)
Comparing with conclusions of Zou et al. (2025). In high dimensions, the is subtler than in low dimensions. Zou et al. (2025) is the only thcoretical work we know of that has studied machine unlearning when p n. by relaxing some of the standard optimization assumptions on the loss, relative to previous works with stringent assumptions Allouah et al. (2025b) Sekhari noisy Gaussian-Newtor step suffices (14) to un unlearn an RERM T1 in high dimensions under (ón, --GRR 3.2 stands in contrast with Zou et al. (0225). Their theoretical analysis relies on the (Ø, - certifibility (section 3.1) and shows that even for removing single data point, at least two Newton steps are required to ensure the accuracy. The sharp contrast between the analytical results highlights the tightness of our GPAR framework (32 in high dimensions. The suboptimality of e-certifiabiliy stems from its incompatibility with natural noise addition strategies, thereby necessitating the injection of disproportionately large noise to meet the certifiability criteria, an effect that is particularly pronounced in high-dimensional regimes.
interplay
eet al. (2021). Our rigorous result that
Theoretical contributions of this paper. We introduce the canonical notion of (ø, E) -Gaussian certifiability (3.2) that is particularly well suited for high dimensions, and analyze the performance of a widely used machine unlearning algorithm in the underexplored proportional regime p ~ n This requires us relax the stringent standard optimization assumptions the per-example loss ff in all previous works, including Guu et al. (2020). (.e0hrr et al. (202T), Neel et al. (202T), Allouah et al. (0255)). In this setting, work makes the following novel theoretical contributions:
Certifiability. Inspired by the hypothesis testing interpretation of differential privacy Wasserman & Zhou (2100) Kairouz et al. (2015). Liu et al. (2019), Balle et al. (020). Bu et al. (2020). et al. (2021), Awan & Dong 2022p, Awan Vadhan (2023). Dong et al. (2022). we introduce a practical, optimally achievable, statistically interpretable, and robust
Sekhari et al. 2021 assumes variation of standard optimization assumptions per-example loss whose conclusions blow up in high dimensions as well. This important case is treated in Section of the appendix.
2

---

Published as a conference paper at ICLR 2026
notion of certifiabilityy, called G-Gaussian certifiability. This notion is particularly well-suited for developing theory in -iseennnniiional situations. In fact, as proved in Dong et al. (2021), a broad class of noise-adding mechanisms converge in behavior to e- e-Gaussian certifiability as the dimensionality increases. This makes e-Gaussian certifiability the canonical framework of certifiability in high dimensions.
Performance. Similar to Guo et al. (2020): /Sekhari et al. (2021), and Zou et al. (225 we then theoretically investigate class of unlearning algorithms that perform a few steps of Newton's 's method, rather than fully re-optimizing the empirical risk. In contrast to Guo et al. (2020), Sekhari et al. (202I). Allouah et al. (2025b), we explore the theoretical behavior of these methods in high- siggh-dimessoonal proportional setting of p n, by relaxing the standard optimization assumptions (11) strong convexity and ((1) smoothness of the chosen per- example loss. We prove that a single Newton update with carefully calibrated independent Gaussian noise, simultaneously attains s-Gaussian certifiability and incurs only a vanishing degradation in generalization error. Note that while Sekhari al. (202T); Guo et al.) (2020) also concluded that a single Newton step is sufficient for approximate removal of a single datapoint, but due to their restrictive assumptions on the loss, their results fail completely in high-dimenn digh--imensions, even in the simplest setting of ridge regularized least squares.
Removing multiple data points. Our theory encompasses the simultancous removal of data from users and show that, even when the number of removal requests m grows with the sample size, accurate unlearning is still possible in high-dimensional settings provided that m = on /polylog(n))
Table I: Summary of prior certified unlearning notions and per-example loss assumptions, compared to our proposed (ye, e) -)Gaussiin certifiability framework (Def. 2}. Our notion is optimally achievable with practical Gaussian noise mechanisms in the proportional figh-dimensional regime, and it relies on relaxed convex per-example loss assumptions that remain valid in this setting (Sec. (4.).
Related works
Certifiability notion (optimality)
High dimensional applicability
Guo et al. (2020)
(e, Junllarnnn (suboptimal)
Assumptions fail in high dimensions Assumptions fail in high dimensions Assumptions fail in high dimensions Extends to high dimensions Extends to high dimensions
Sekhani et al.
12021
(c, 8) -unlearmnn (suboptimal)
Allouah ct al.
2025b
(g, e-)ééni (suboptimal)
Zou et al. 2025)
(ø, 8) -uunlearnnng (suboptimal)
Proposed in this paper
(d) e--Gaussian (optimal)
2 THE MACHINE UNLEARNING PROBLEM: PRIVACY AND ACCURACY
Let Dn denote the dataset, A(D,,) denote the machine learning model trained on Dn, and M C [n] the indices of points to be removed, with corresponding data DM- The problem of machine unlearning requires a procedure À to produce an update A,M == (A (DD,) that
closely approximates the ideal model A(D,, DM) retrained from scratch. We assume that A has access the model output A(),)) the dataset of removal requests 2.M and some auxiliary gradient or Hessian information T(D..) as in Sekhari et al. (2021) and Zou et al. (2025).
We focus on approximate unlearning (e.g. Guo et al. (2020). Sekhari et al. 2021 Neel et al. 2021
Allouah et al. (2025b) where, A achieves staristical proximity to the retrained model as opposed to exact unlearning Cao & Yang (2015), Boortoule et al. (2021) Basu Roy Chowdhury et al. (2025), Kuo et al. 2025), j, which requires literal equality A.M- A(D, DM) (almost surely or in distribution). Exact recomputation is often computationally infeasible, and since our focus is on extending the
theory of the proposed unlearming framework to large class of loss functions in dige-diimesi problems of interest, approximate removal methods offer a practical and scalable alternative. Note that the machine unlearning mechanism A.M is expected to satisfy the following two properties:
Protect user privacy. The output of the unlearning procedure A.M must leak no information about the removed subset D.M, even under arbitrary post-processing of the unlearned output.
Preserve model accuracy. The unlearned model A,M must incur only vanishing change in generalization capabilities compared to the ideal retrained from scratch model A(D,, \ (D))
2.1 GENERALIZED LINEAR MODEL (OF DATA) AND EMPIRICAL RISK MINIMIZATION
We now describe our high-dimensional setup step towards formalizing privacy and accuracy.
3

---

Published as a conference paper at ICLR 2026
GLM Data. We assume our data D,, := {(x,, U4) 34) with æ; E Ip denoting the features and y/ E R denoting the response. Further, (x1,0k) are i.i.d. samples from dp3- (ar, v) = dpl (p(x))dg(() /r (*) with density p: IR" + R20 and kernel q(-1ax (=)
Rzo with unknown 3 E B := R
High-dimensional focus. In many Al applications, the number of model parameters, p. often comparable to the sample size, So, we aim to study models under the proportional high dimensional setting which both n, are large while n 7. This sets the interpretation of all asymptotic expressions the directional limit - 00, p r2/7. For example, sequence of random variables Wn (1(1) means Wn, converges to zero in probability under the asymptotic setting above.
RERM training. The goal of learning procedure A is to estimate the parameter 3 from training data. A widely used approach is regularized empirical risk minimization (R-ERM), defined as:
B = A(Da) == arg min BERP
L(B) == arg min BERP
Xr( +
Elya x B),
(I)
where é (individual) loss function and r regularization term with factor A, which we assume is O(1) throughout. A statistically interpretable choice of the individual loss {(vlz) is the negative log likelihood log qgyl2), and the choice of the regularizer is often based on some prior information on 3 Popular choices include ridge (r = || 11 LASSO (r = || Il1), and their variants.
The objective of unlearning is remove the influence of subset M of observations, of size [M| m, that have requested removal from the training data. The ideal unlearned estimator would be the one retrained from scratch on the remaining data DIM == D,, DM:
Bim= A(D arg min
LMM(3) = arg min
Xr(B) + Σ E(ull,
(2)
BER"
BER"
igeM
To process deletions efficiently, without full retraining, and obscure residual information, we update G via the randomized procedure below.
B. = A(3, TM,,(DD),))) where b is a random noise.
(3)
Given a trained model, G. note that b is the only source of randomization during unlearning. In addition to the perturbation b, the unlearning procedure Á has access to the set DAM corresponding to the data to removed, and limited access the outputs of the learning algorithm A on D,, For example, (i) the original estimator B and (ii) some auxiliary information T(D,,) such as gradient or Hessian of the objective function on D.,, at 3.
3 FORMAL DEFINITIONS OF CERTIFIABILITY AND ACCURACY
As discussed in Section 2 machine unlearning algorithms are expected to satisfy two key criteria: (1) protect user privacy and (2) preserve model accuracy. The purpose of this section is to formalize the notions corresponding to these objectives by introducing: (1) (ó, -GGasssii certifiability as a canonical measure of privacy, and (2) Generalized error divergence
measure of accuracy. We
will formally establish later that both notions are particularly well suited to high-dimensions.
3.1 GENERAL CERTIFIABILITY THROUGH THE LENS OF HYPOTHESIS TESTING
Let us take the perspective of adversary who, given output 9 from unlearning algorithm A, performs the following hypothesis testing problem:
Ho B Pro vs. H Pun
where Pre and Pun are the conditional distributions of A( M. 0, ()) given the data D,M and A(B, DM. (DD), b) given the data D respectively. Indeed, if the adversary has sufficient evidence to reject Ho. it would mean that / has retained some information about DM- defcating the purpose of machine unlearning. Note that in all settings, the adversary may make mistakes in accepting or rejecting the null. Hence, to consistently evaluate the quality of the adversary's 's decision, we have to evaluate the probability of Type I error (i.e. the error of rejecting Ho when the truth is Ho), and Type II error (i.e. the error of not rejecting Ho when the truth is H1)..
For more details the claim that randomization is necessary to hide residual information and preserve privacy of individuals, please refer the literature of differential privacy Dwork Dwork (2006).
4

---

Published as a conference paper at ICLR 2026
Trade-off functions:
The above leads us the notion of trade-off curve defined below and studied extensively in the Statistics and information theory Lehmann et al. (1986), Poor] (1994). To introduce this notion, let simplify the notations of the above problem to the following. Suppose that random vector W is given, and we would like to perform the following test:
Ho W P US. H1 W Q
Definition 1. (Trade-off off function) Given two probability distributions P. Q on measurable space
Fw),, we define the trade-off function as the map T(P, Q) [0, - [0, 1| as
T(P)Q)aa):= == inf B. == =Bqll= - *l a Bp S a, W [0, measurable.. (5) =inff
In words, for any given type error a, the trade-off function returns the smallest possible value of type Il error 3.p over all possible test functions yp: W [0, 1].
Using the notion of trade-off functions, and inspired by the notion of f-differential privacy introduced in Dong et al. (2022), we aim to define a notion of certifiability that generalizes and unifies the existing techniques. Intuitively speaking, once we decide on a trade-off function ʃ [0. (0, 1] - [0, 1],
we can certify A if
T(Pre: (a)) 2 f(a) for all a E [0
(6)
To make certifiability criteria less restrictive, require the above definition be satisfied with high probability over datasets D. This leads us to the following definition of general f- certifiability. Definition 2 (f -frttiifiabilltty) Given @ > O, E [n] and Pun, Pre as define in (4), and trade-off curve f: [0, 1 - [0, 1]. we say unlearning algorithm A satisfies é-certifiable with respect to f if
P inf LIMISm
min(T((Pes) (an) (PP))P 2 f(a) for all a E [0. 21-6 (7)
where the probability F solely over the randomness of the data D.
Different choices of f yield different notions of certifiability. Observe that by choosing different trade-off functions, we can cover a wide range of notions of privacy in the literature Guo et al.
(2020), Sekhari et al. (2021) Zou al. 2025). For instance, by setting f(xx in the following way:
fe,6(a) == (0, 1 - - a e " (1-11 - - a)} for parameters 2 0,0 55
(8)
will obtain notion similar to (s-0) certifibbiyyyybiliiyy condition discussed in Sekhari al. 2021
3.2 (AUSS-GAUSSIAN CERTHIABILTTY CANONICAL CHOICE HIGH DIMENSIONS
We study machine unlearning in high dimensions, where choosing an appropriate f is the key to formalizing certifiability. In this regime, a natural (indeed canonical) choice of f emerges from two facts. 1) In practice, privacy is achieved by adding noise, and 2) intrinsically high-dimensional phenomenon implies that, with high probability (up to tolerance Φ), most ld projections of an isorropic high- ligh-dimensioall (log-concave) distribution are approximately Gaussiar Diaconis & Freedman (1984), Klartag (2007). A precise instantiation of this idea appears in the differential privacy literature Dong al. (202T). which motivates us to consider the following choice of the trade-off curve fa.. in Definition in comparison to previously proposed notions such as Je.8-
(N fa.s(a) = (ON (V) a)) ④ (1 a) =))
(9)
where (b-) is the edf of standard Gaussian variable ((t) (0, S for all R.
(a) possesses several attractive properties. The following lemma lists one such property of Gaussian trade-off functions known dimensionnfreeenss: This will be used later in this paper.
Lemma (Dimension freeness). For any μ1, μ1 E PR and a > 0 let := 1llm p2lla. Then
T(m + (N, + N (0, 1,)) T(N ((,,
(10)
Thiin of all the 1d projections of the uniform distribution high dimensional sphere as an example.
5

---

Published as a conference paper at ICLR 2026
We call the criterion of Definition 2 with f.) replacing f() as (Ø, () E to abbreviate (ó, e)- Gaussian Probabilistically certified Approximate data Removal or (Ø, e)-Gasssian certifiability. We enlist some more properties of (Ø,e) = that make it emerging in high digeenimensio settings:
Universality of Gaussian noise. Dong et al. (202T) shows that a broad class of isotropic log-concave noise-adding mechanisms (to achieve privacy) converge in behavior to (ø, e) Gaussian certifiability as asp- - co. This makes Gaussian mechanism the natural boise-adding mechanism in high dimensions.
the canonical Gaussian noise for randomizing the estimates, a consequence of Blackwell ordering says that the Gaussian trade-off' curve p is the tightest way capture the Gaussian mechanism Dong al. 20022)
Gaussian certifiability as the tightest notion. Now, once
Suboptimality of all other notions of certifiability. All the previously proposed notions of unlearn- ing, including s-Ō variations of Guo et al.] (2020), Sekhari al. (2021). Zou et al.) (2024). Rényi certifiability Allouah et al. (025b)) are not tightly achievable under the Gaussian mechanism except for Gaussian certifiability Dong et al. (2022). This establishes the natural emergence of the e-GPAR framework with tolerance & as superior over any other framework in high dimensions.
Appearance in practice, in related experiments. In the context of machine unlearning, Gaussian trade-off curves (9) (the core of Gaussian certifiability) have been experimentally shown to match empirical trade-off curves remarkably well for the removal of poisoned data PPawelzykk et al. (2025).
In Section 4 we will use the (Ø. (0.e)-GPAR framework to theoretically evaluate the user privacy protection capabilities of machine unlearning algorithms that are based on the Newton method.
3.3 GENERALIZATION ERROR DIVERGENCE: A MEASURE OF ACCURACY
In the previous subsection, we introduced a canonical notion of certifiability for unlearning. We now turn to the second criterion, which aims to evaluate model accuracy. Without such a criterion, an unlearning algorithm could output pure noise, achieving perfect user privacy the cost of severely degraded model performance. To formally evaluate the generalization capabilities of our unlearning procedure Á, we consider the metric Generalization error divergence (GED).
Definition 3. Given dataset Dn of n i.i.d. samples (æt, Y1) as introduced in Section 2.1 let (æg. Vo)
be a new sample i.i.d. with the observations in Dn, Let Elylæ T (3 be a measure of error between and x B. Then the Generalization Error Divergence (GED) of the couming-uulearning pair (A, A) on the dataset Dn with subset M C [n] of data removal requests is defined as:
CA == ([](goolz) A(D.))) - E(yol=) A(A(Da), DM. T(D...)). (D,) (11)
where we condition on the randomness of the data set Dn and average over the randomness of the unlearning algorithum A, as well as that of the test data point (zo, yo).
The above metric compares the generalization error of the unlearning algorithm Á given P and data removal requests M with that of the model A trained from scratch on DiM: on a fresh sample (wo. yo). We note that previously Sekhari et al. 22021) used the notion of excess risk of Á against that of the true minimizer of population risk But, as we will show in Section Df of appendix that this notion does not behave well under the proportional high-dimensional setting. We refer to Zou al. (2025) for more.
measure of accuracy of machine unlearning algorithms.
4 NEWTON-BASED MACHINE UNLEARNING: THEORETICAL GUARANTEES
Having settled down on both the evaluation criteria, we study the performance of unlearning procedure Á based one Newton step and perturbing the result with Gaussian noise achieve EPPAR.
4.1
NEWTON-BASE BASED UNLEARNING MECHANISM
Newton method is an iterative method for solving optimization problems based on a second-order Taylor approximation of the given optimizing function Boyd & Vandenberghe (2004).
method) Suppose that h Rp - TR is differentiable function with an invertible Jacobian matrix G anywhere on Rp and that h has a root h((g*) = O. Starting from an initial point (()) E TRP, the Newton method is the following iterative procedure: for step 2 1,
Definition& 4. (Newton-
( = =3((-1) - (g(0 (180-1))((88611))
G
(12)

---

Published as a conference paper at ICLR 2026
Using the Newton method (Sekhari et al. (2021) suggested the following unlearning algorithm:
Approximation step. starting from (3, we one Newton step with h VLA to obtain:
= -LW
where G(L)M) is the Hessian of L in
(13)
Randomization step. add a Gaussian noise b ~ NO0 TTp) to (M to have the unlearned output
Noisy one step Newton output: PM: ((..).) 3Mm == B a +b. (14)
First, the choice of will be discussed in our theoretical results. Next, note that since @ differs from B.M, the difference between the two vectors may reveal information about the data to be removed, DM. Hence, a standard practice is to obscure it by adding random noise b. Finally, the aim in the remaining part of this section is answer the following two questions:
Privacy. How choose a to ensure that B.M satisfies (Ø, e)-GPAR when n, large with n/p ?? Accuracy. Can we calculate the generalization error divergence of 3M given the choice of a obtained above? Does the GED go to zero as n. P - do while n/p + 7?
4.2 TECHNICAL ASSUMPTIONS ON THE LOSS FUNCTIONS AND THE DATA
Loss functions. We describe the assumptions on the unregularized individual loss I and the regularizer r [ To ensure that the RERM introduced in ( has unique solution (from strong convexity arguments) and Newton unlearning makes sense theoretically, the following assumption are made:
(A1) Separability of r. r:: RP >> R4 is separable. More precisely, r(3) = Eke(pl Th (3ee).
(A2) Smoothness of (l,r). E: R R + R+ and r : Rp + R. are both thrice differentiable.
(A3) Convexity of (l,r). f and proper convex, and is v-strongly convex for @(1) 0.
(A4) Polynomial growth. 3 constants C, 0 such that for all y, 2 (denote Ely, 2) oy((y.z)
max(e(y, ²), 14(y, 2)1. 1 (v, =] = C(1 + |v|" + [=|*) and V²r(3) = diag (i (Bx [NEp (15)
is (n))--shiis (in Frobenius norm) in ,3 for some C.r (polylogg(z)).
Note these assumptions on (f,r) are from Zou al. (2025), ) and they weaken many of the standard
optimization assumptions of (((1) strong convexity and O(1) smoothness of per example loss f in
Allouah et al. (20256) or variations thereof in Sekhari et al. (202I). Convexity of and v-Sttrng
convexity of above actually means that per-example loss B J(B 2) I(,, 2 () ((3) is A
strongly convex, which significant relaxation of 22(1) strong convexity of f. capturing the concrete case of the ridge regularized r(B)= || quadratic loss ((y, (y 2)² Allouah et al. (002b
and Sekhari et al. (2021) both fail to capture the simplest example of high dimensional statistics in their respective frameworks.
We require the following on the data that generates our features x; and responses 1/-
(B1) Subgaussian features. I, are mean sub- Gaussian vectors with covariance Σ denoted as aid
2; (0, E). We further assume that Amax (Σ) < Cx. for some constant Cx > O. ~
(B2) Sub-polylggarihhmic responses. We assume that P(|y:] Cy(n)) I (n) and Ely, Cy. for some (n) = Oppolylog(n)), a constant Cy,s and qn =(n
on mean-zero sub-Gaussian features is a mild and frequently made in many papers on high dimensional statistics. See for example Miolane & Montanari (2021): y); Rahnama Rad & Maleki (200)) Auddy al. (2024); Zheng et al. 2017):Donokl
Assumption BI
& Montanari (2016): Bellec et al.
20255) Assumption (B2) is not a stringent assumption either. and most popular models such as
logistic regression, Poisson regression, and linear regression satisfy this assumption. Using these assumptions, we can finally prove our main theoretical results.
4.3
THEORETICAL GUARANTEES: ENSURING USER PRIVACY AS WELL AS MODEL ACCURACY
One step Newton achieves (o. E) GPAR. Our first result shows that for suitable noise variance, the randomized one-step Newton unlearned estimator defined in (14) satisfies (d.e)-GAAR.
7

---

Published as a conference paper at ICLR 2026
Theorem 2. Suppose Assumptions (A7
(A4)
well [BT]
[B2) hold. Then there exist poly-
logarithmic Ci(n), C2(n) = O(polylog(n) jor which the randomized one-step Newton unlearning
14) when used with a perturbation vector N
00 10.-1y 1p), achieves (#,, with
C 2Aum
R R= C
&n = 8n ne n + 2e
0/2
(16)
The proof of this theorem is presented in Sections
G H of the appendix. After the above theoretical guarantee ensuring user privacy, we now calculate the GED of this machine unlearning algorithm.
Theorem 3. Suppose Assumptions (A4) as well as [B B2) hold. Consider the unlearning estimator defined in (14) with the noise variance ser according to Theorem Then, with probability
(A4)
at least (n + 1) 14n n/- - e- (1-1oo())))
(
1 vD )
m m (m + 2)
CED s sci
Avn polylog(n).
The final technical conclusion of the paper. Combining the above two theorems we reach the conclusion: If we set the variance of the Gaussian noise as suggested by Theorem 2 the machine unlearning algorithm Bim that is based on (4) offers ( well vanishing GED
= O, (
( (mppolyyog(n) as soon m m²polylog(n)
(17)
Vn
vn
In particular, if m = o(nt=a) for arbitrary > O, we have G.. 3r (1). Note that both theorems are valid in high-dimensional settings where n, p - Do, while n/p - Moreover,
appendix F.3 for discussion on calibrating without the constants C₁1 (n), C2(n), as well as procedure in practice to determine what they are given a dataset and the losses (E, r).
EXPERIMENTS VALIDATING OUR THEORETICAL CONTRIBUTIONS
Given our theoretical focus, and the abundance of empirical studies on Newton-based unlearning Guo et al. (2020), Bui et al. (2024), we present simulations solely to validate our results and to compare with the results of You al. (2025). The incompatibility of certifiability with noise adding mechanisms requires disproportionately large amount of isotropic Laplace noise in Zou et al. (2025) whereas e- e-GAAR criterion optimally captures the Gaussian mechanism. Our simulations show that leads to substantial improvement of the unlearned estimator across different settings.
Logistic regression model. For simplicity, E(ylæ 3), with random features 2; ~ NO, Ip) and true parameter B. ~ (N, Ip). To depict high- dimensionality, take n p. penalty parameter > 0.5, and show behavior of the varying the values of n, m. and certifiability parameter E. 1) When m = 1, we look at all possible removals of size one justifying robustness of our certifiability. 2) When m 1, instead of all possible removals, we study unlearning across 1000 randomly chosen subsets of size m. More details and codes in the appendix and https: //tp:///nnoomouu 4open science /nn//nnee leaneinaiinnng E1 4D
ridge penalized r(3) || logistic loss
metries by
6E0 vs. np m- and <- 0.75
GED vs for n- mpp.p m- and c- 0.75
GED vs for = -00000mm and c- 6.75
620
6180
4100
Dineesion
Dinessce
Dinessor
Figure 1: Comparison of unlearned estimators on new test data: mean GED (with 3 SD error bars)
across the dimension p (both log scale) for Laplace (in red) vs. Gaussian (in cyan). We set À = 0.5.
In the first figure we fix e = 0.75, and examine via GED [II) the generalization performance of unlearning on 100 previously unseen test data. We vary n p across 6 values from 500 5000
8

---

Published as a conference paper at ICLR 2026
equally spaced logarithmic scale. Figure Tigure[pie plots the average GED values (across 200 replications) against dimension p. transforming both X and axes to be on a logarithmic scale. The figures are repeated for unlearning sizes
1 (left). = 5 (middle), and m = 1, 5, 10, as 1. GED for Laplace perturbed estimator of zou et al. 2025 is unchanged, whereas Gaussian perturbed estimator decreases steadily. A linear regression of log (mean (eean(GGDD) vs. log(p) confirms this. The lines for Laplace unlearning had slopes of 0.03, -0,03, and -0.01 for m 1, 10 respectively, implying one step Laplace-Newton estimator has a non-vanishing GED as 7. This shows the sub- sub-optimality of e-certifiability by requiring at least two Newton steps to reach vanishing GED. In contrast, the Gaussian unlearning lines had slopes of -0.47,-0.54, -0.51, thus GED decaying at an order of p 0.5 supporting Theorem 3 The same performance persists when comparing performance on the unlearned dataset, where we compute the unlearned error divergence (UED) between the retrained and unlearned estimators (see appendix for more on UED).
10 (right). Observe for
We next fix n p 1255 and examine GED with X axis as & with m = 1, 10. Figure 2 reports boxplots of GED in this setting across 200 Monte Carlo replications. Our Gaussian perturbed estimator performs increasingly closer to that of the ideal retrained estimator as 1. The error for the -ertuurbe estimator remains high above its Gaussian counterpart, uniformly establishing robustness of Gaussian certifiability across all scales E. Similar behavior is reflected on the unlearned subset (see Section in appendix).
GED vs. 1255 and m1
GED frr 1255 and m
GED & 1255 and
Figure 2: Comparison of GED (plotted in log scale) across different values of for Laplace noise (in red) vs. Gaussian noise (in cyan). We set X = 0.5.
Finally fix 0.75, examine GED with X axis m n p varies between 500, 1500, 2500. We vary m across 6 values from 5 to 50 equally spaced on a log scale. Figure plots the average GED values (200 replications), transforming X and Y axes
log scale. For all three plots, m GED increases for both the estimators with Laplace high above Gaussian. A linear regression of log( log(mean(( CannannGGDD (GED)) vs. log(m) confirms this. The lines for Laplace unlearning had slopes of 0.26, 0.22, and 0.24 for p 500, 1500, 2500, whereas Gaussian unlearning had slopes of 1.37,1.42, 1.44, showing that GED values increase an order of approximately 1.5 supporting Theorem but suggests a better dependence on m in practice.
GEO vs. m farn =p 500 and <= 3.75
GED vs. m Bann =p 1500 and 0.75
GED vs. m Rarn -2500 and c- 0.75
0.50
Urinaring six
Uriumrin
Uriurringa wta.ggaiooooo
Figure 3: Comparison of mean GED (with 3 SD error bars) across the unlearning size (both in log scale) for Laplace noise (in red) vs. Gaussian noise (in cyan). We set À = 0.5.
5.1 LARGE DIMENSIONAL AND REAL DATA EXPERIMENTS
In this section, we add additional experiments with larger dimension p. The problem setting is exactly the same as in the previous section, but p now varies from 1000 to 10000. F shows that the same pattern as in Figure [ earlier persists here. In the above figure we have also added the GED and UED bounds from (0 unlearning of Sekhari et al. (2021) adapted to our setting. Note that (ő.s) Gaussian certifiability implies (ò, o) certifiability for (()) determined according to Corollary 2.13 Dong al. (2022). The above figure shows that, beyond the dimensionality drawbacks pointed

---

Published as a conference paper at ICLR 2026
GED vs. for = p/10, m
UED vs. for p/10, m
2.000
1.000
nobe
noise
Epe-ddele
Epo-deta
Generttation
2.000
Gasssan
0.300
Geussin
Ladiece
Laplace
1080
1000
Dimension
Dimension
Figure 4: Comparison of mean GED and UED (with 3 SD error bars) across the dimension p when the dimension is large, in that it varies from 1000 to 10000. We set À = 0.1.
out earlier, replacing (6 Gaussian certifiability by (ø, e, 8(E)) certifiability for the same e leads to strictly worse performance while maintaining the same level of certifiability.
We apply our methods to binary classification tasks on real data to check performance in cases where uub-Gaussianity assumptions are violated. The two examples are the low-dimensional MNIST data where we classify digits as '3' or '4'; and the high dimensional IMDb reviews data where we predict whether a text review positive or negative. While all three certifiability notions are comparable for the low-dimensional MNIST data, superior performance of the Gaussian framework is evident in the high-dimensional IMDb dataset from Figure
GED psilon p = 784,
ppsiion 1579, p =3161,
Gereritztion enoeenddddweee diergonce
8:20
noise
noise
Generetzation enter
1.50
3.43
Eps de
Gasssan
Gasssin
1.23
0.10
Lapace
2.03
0.30
-
Ceriifabllly Parameter
Certifabilly Parameters
Figure 5: Comparison of mean GED (with 3 SD error bars) across E for (left) low-dimensional MNIST data with 784, n = 1200 and (right) high dimensional IMDb data with 3161, n = 1579. We set = 0.01. Experiments were repeated 20 times across random draws of the test set.
6 CONCLUSION AND FUTURE DIRECTIONS OF RESEARCH
We introduce e-Gaussian certifiability and show that our noisy one Gaussian-Newtte step ensures both privacy and accuracy in the -igh-dimensional proportional setting. This contrasts with Zou ct al. (2025) which, under the ( -eeetiiiiiii framework, concludes that at least two Newton steps necessary, even for removing one data point. Our results indicate that this gap reflects the suboptimality of their (o.=)-certifiabbliiy which ( -Gausiinn certifiability resolves optimally.
Our analysis of models with large number of parameters opens new avenues for tackling several other important challenges. First, it would be interesting to see how much we can give up on the distributional assumptions on the data { }i in high dimensions, and going beyond the generalized linear model 4.2 Second, it would be of great importance to analyze (un)-learning algorithms for non- convex loss functions, to capture the complicated loss surfaces arising deep neural networks. Third, although the one-step noisy Newton proposed in this paper is theoretically efficient, but calculating the full Hessian and inverting it can expensive very high-dimensional settings. So, it would be interesting to investigate how the conclusions of this paper change under approximate second-order methods, such as Koh & Liang (0177). Park et al. (2023). Moreover, our one-step noisy Newton procedure effectively allows multiple simultaneous deletions of size with scaling m o(n) 3 and it would be interesting to strengthen it to match with the scaling m² = o(n) empirically observed in Figure 3] and how the conclusion changes for more sophisticated unlearning scenarios such as distributional unlearning such as class or concept unlearning Allouah et al. (2025a), online unlcarning such handling continuous unlearning requests Qiao et al. (2025)
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Youssef Allouah, Rachid Guerraoui, and Sanmi Koyejo. Distributional unlearning: For- getting distributions, not just samples. In JCMI. 2025 Workshop Machine Un- learning for Generative AI, 2025a, URL https::/ /otpgsss/e/errreee.eeeetett forum?idni?
Workshop paper.
Youssef Allouah, Joshua Kazdan, Rachid Guerraoui, and Sanmi Koyejo. The utility and complex- ity of in- and out-of-distribution machine unlearning. In The Thirleenth International Confer- ence on Learning Representations, 2025b. URL https:://///.... battps://openreiieee net wwte/eerummtao. forum?id НVFMооΚТНX
Arnab Auddy, Haolin Zou, Kamiar Rahnama Rad, and Arian Maleki. Approximate leave-one-out cross validation for regression with regularizers. IEEE Transactions on Information Theory, 70 (1):8040-807., 2024.
Jordan Awan and Salil Vadhan. Canonical noise distributions and private hypothesis tests. The Annals of Statistics, 51(2)5447-572 2023. doi: 10.1214/23-A052255
Jordan A. Awan and Jinshuo Dong. Log-concave and multivariate canonical noise distributions for differential privacy. In Advances in Neural Informa-
fion Processing Systems 35 (NeurlPS 2022), pp. 34229 34240, 2022. URL
httpps://m http::///ooeeedigg.n.errrrgeeiee cctpipppeccpppprrrprppppp wtless/ppprr/22//beeeee dd (d
Abstract Con.reeccecooeeeeee....e...e html
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and Rényi differential privacy. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty-Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2496-2506. PMLR, Aug 2020.
URL httpps::/ppccceeininaana http:///ww.......ppsss////.///// wtwps//vw0//aallleeeeeeeeeeeeeee 2tt220....mmmmmmmmmm.m..........
mlr
Somnath Basu Roy Chowdhury, Krzysztof Marcin Choromanski, Arijit Sehanobish, Kumar Avinava Dubey, and Snigdha Chaturvedi. Towards scalable exact machine unlearning using parameter- efficient fine-tuning. In Proceedings of the 13th International Conference on Learning Represen- tations (ICLR 2025), 2025. htt.l:tts::/// http:///peeeeeeee.eeeeeotoorrrre Poster.
Pierre C Bellec, Jin-Hong Du Takuya Koriyama, Pratik Patil, and Kai Tan. Corrected generalized cross-validation for finite ensembles of penalized estimators. Journal of the Royal Statistical Society Series B: Statistical Methodology, 87(2):289-31) 2025.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jía, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlcarning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159, IEEE, 2021, doi: 10.1109/SP40001 2021. 00019.
Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, 2004. ISBN 9780521833783. doi: 110117/CB097801118004448
Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su. Deep learning with gaussian differential privacy. Harvard Data Science Review, 2020022110.1112999900222.......2 2020. doi: 10.
1162/99608192.ccc5ddd2 URL wttpttt://// /ett:a////oii.oorrg///////////99
Nhung Bui, Xinyang Lu, Rachael Hwee Ling Sim, See-Kiong Ng, and Bryan Kian Hsiang Low. On newton's method to unlearn neural networks. arXiv preprint arXiv:2406. 14507, 2024. URL
https://arra org/ abs / abll///s//242 14507
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, pp. 463 480. IEFE, 2015. doi: 10.1109//P.0055.35
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security (C) pp. 986-911, 2021. doi: 10.1 155/3444000...
3484756.
11

---

Published as a conference paper at ICLR 2026
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communicaations Security (CCS 22), New York, NY. USA, 2022. Association for Computing Machinery. doi:
URL htt.tt:/pp///oi wttg/10..14////33311 htttpps///oll.rrr101115/////5//2
65593522
Vikram S. Chundawat, Ayush K. Tarun, Murari Mandal, and Mohan Kankanhalli. Zero-shot machine unlearning. IEEE Transactions on Information Forensics and Security, 18:2345-2354 2023. doi: N0.1109/TIFS.2223322665
Persi
Diaconis and David Freedman.
Asymptotics of graphical projection pursuit.
The Annals of Statistics, 12(3):793-815 815, 1984 doi: 10. 10.1214/00x/1176446707
URL 12t.//se-3///yytoataaaaa---- http:///wwc.cccooooooooooooaaaar
vo Lum
10. 1el1/22/////1763455555
Jinshuo Dong, Weijie J. Su, and Linjun Zhang. A central limit theorem for differen- tially private query answering. In Advances Neural Information Processing Systems 34 (NeurIPS 2021), 2021. URL httpss:/pproceedinggs heurseeeeiinngn.............. wttp:r/ppppccppppr////22//
.html
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 84(1):3-37, February 2022. doi: 10.1111/
1245. URLhttpss /tt::///ciiiie otg/10.0gg11... http//101111//ssss... 12454
David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166:935 9665935-969,9 2016.
Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1-12. Springer, 2006.
Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making Al forget you: Data dele- tion in machine learning. In Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL http:: htL //pperss .wwppperrsneuussssseeeese wwwripsu..... /tppp///////ppp//////1eee. http://:/..peee.eee..s...////spa
cb7 E235588aSS01111att66009111333333 Pape.... pdf
Pwper.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3832-3842. PMLR, 13-18 Jul 2020. URL htttps://proceeddngg
mlr. wttpppsss//111/gooocc.oomm html
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi- and Chris Waites.
Adaptive machine unlearning. In Advances in Neural Information Processing Systems 34 (NeurIPS
www.eeswweeeeeeeeeeeeeeeee cc/paper/ 8 7120
2021), pp. 16319-16330. 2021. URL
Yaxi Hu, Bernhard Schölkopf, and Amartya Sanyal. Online learning and unlearning. arXiv preprint
arXiv:2505.08557 2025. URL httttt:t///artttt wttp://///aaab..a.abse 08557
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1376-1385 Lille, France, 07-09 Jul 2015. PMLR. URL
mal.asmmmlll. mlr. www.s..p.pp..svv
Cairouzl5, html
Bo' az Klartag, A central limit theorem for convex sets. Inventiones mathematicae, 168(1)991-13,, 2007. doi: 10.
URL htl.hhttts::/ink..prrre
10.1007/300222 0002 0028-8
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In
Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1894,1894, PMLR, 2017. URL pttttp:://ppoccedingg
mlr. wt..press//7Dkkohl html
12

---

Published as a conference paper at ICLR 2026
Kevin Kuo, Amrith Setlur, Kartik Srinivas, Aditi Raghunathan, and Virginia Smith. Exact unlearning of finetuning data via model merging at scale. arXiv preprint arXiv:2504.04626, 2025. doi: 10.485500axx1.2254444633
Erich Leo Lehmann, Joseph Romano, al. Testing statistical hypotheses, volume 3. Springer, 1986.
Changchang Liu, Xi He, Thee Chanyaswad, Shiqiang Wang, and Prateek Mittal. Investigating statistical privacy frameworks from the perspective of hypothesis testing. Proceedings on Privacy Enhancing Technologies, 2019(3)233-2544 254, 2019, doi:
BRLhttps: //pet sympos simpppssuum..o www.m.rrrggg http.//pppppt/////////epeeooe -ttopppesss1119--0 0045. php
Sijia Liu, Yuanshun Yao, Jinghan Jia, Stephen Casper, Nathalie Baracaldo, Peter Hase, Yuguang Yao, Chris Yuhao Liu, Xiaojun Xu, Hang Li, Kush R. Varshney, Mohit Bansal, Sanmi Koyejo, and Yang Liu. Rethinking machine unlearning for large language models. Nature Machine Intelligence, 7 URL
(2):181-194, 2025. doi: 10.
012256-025-00020
Léo Miolane and Andrea Montanari. The distribution of the lasso: Uniform control over sparse balls and adaptive parameter tuning. The Annals of Statistics, 49(4), 2021.
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvaeeddi Descent-to-delete Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pp. 931-962. PMLR, 2021. URL
mlr. press /vl 32/ nee 221..html
Thanh Tam Nguyen, Thanh Trung Huynh, Zhao Ren, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoe Viet Hung Nguyen. A survey machine unlearning. arXiv preprint doi: 10448550/axX..22209.2222
mwXiv:2209.02290 2022.
htl.tttts://axii...om abs/
2209. 02299
Act State of California Department of Justice. California Consumer PrisuuccrPPivayy Act of 2018 (ccpa). Assembly Bill No. 375, 2018. URL http::ttt://// .a. htt..//o///vvacc/cc....... accessed 6 May 2025.
Government of Canada. Bill C-27: Consumer Privacy Protection Act (CPPA). Digital Char- ter Implementation Act, 2022, 2022. URL http:://iieed-sss...aaaaaaaa http:////w.ce.eeaaaaaaaaaaaaaaee
ianovattion-better
act pro-
posed legislatoo;: accessed 6 May 2025.
Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclere, and Aleksander Madry. TRAK:
Attributing model behavior at scale. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 27074-27113, PMLR, 2023. httttts:::/ / pttppeeicceengsss/
mll. wtt.:smmm.....r.mmmmmmmmmmmmmeee press v202 wttppppssss/222aaaaaaaap
html
Martin Pawelczyk, Jimmy Z. Di, Yiwei Lu, Ayush Sekhari, Gautam Kamath, and Seth Neel. Ma- chine unlearning fails remove data poisoning attacks. In International Conference on Learn- ing Representations (ICLR) 2025, 2025. URL https:/
http///ppnneeeie./e///// /ttps://openteveee..... net wtw.::/wwwwee/oouumeemm ftrm//orrmmmio
HaX48yksVI Published as a conference paper at ICLR 2025.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, Cambridge, feb 2025. ISBN 978- 108833900. doi: 1111179971110866633
URL httptttts///oi.oeeetee 11110//0111111110711111116663119
H. Vincent Poor. An Introduction to Signal Detection and Estimation. Springer Texts in Electrical Engineering. Springer, New York, NY, edition, mar 1994. ISBN 978-0-387-94173--8 doi: eBook ISBN:
10.10077978-1-4755-2233
Xinbao Qiao, Meng Zhang, Ming Tang, and Ermin Wei. Hessian-free online certified unlearning.
In The Thirteenth International Conference on Learning Representations, 2025. URI. https
/ooperrevies net.
Kamiar Rahnama Rad and Arian Maleki. A scalable estimate of the out-of prediction error via approximate leave-one-our cross-valides volss-vaii.iion. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(4):965-995 2020.
13

---

Published as a conference paper at ICLR 2026
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Re- member what you want to forget: Algorithms for machine unlearning. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neu- ral Information Processing Systems, volume 34, pp. 18075-18086. Curran Associates, Inc., neur wwwpppesccccpppppppppp........ a1c.:/acccaaaaaaaaaaa/0006666660
2021. URL
Shaofei Shen, Chenhao Zhang, Yawen Zhao, Alina Bialkowski, Weitong Chen, and Miao Xu. Machine unlearning for streaming forgetting. arXiv preprint, abs/2507.15280, 2025. doi: 10.
48550%\aXXiv2557. 15280..
Ayush K. Tarun, Vikram S. Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. IEEE Transactions Neural Networks and Learning Systems, 13055, 2024. doi: 10.109/TNN.S.2223322222..
Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of the 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 4126-4144 PMLR, 15-19 Aug 2021. URL u1lah21a.html
mlr. www.s/res/veee vv14/
European Union. Regulation (EU) 2016/679 of the European Parliament and the Council of 27 April 2016 (General Data Protection Regulation). Official Journal of the European Union, L119, 2016. GDPR.
Ramon van Handel. Ape 550: Lecture notes, /attps://web math. wrinceton.edu/-ae APC550. 2016. Course notes, accessed 2025-09-24.
Roman Vershynin. High-Diments Diahe-Dimesional Probability: An Introduction with Applications in Data Science, volume 47 Cambridge Series Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. 2018. URL https:: //www//www//////////////////. math. uci. www.uuiw...u..ueee....ee.e edu/~rvershyn Heperrs/DPP-boo////
pdd Prepublication PDF version.
Weiqi Wang, Zhiyi Tian, Chenhan Zhang, and Shui Yu. Machine unlearning: comprehensive survey. arXiv preprini arXiv:2405.07406 2024. doi: 10.48550\axxx.244557744666 URL https
7/arxiv. org/ http://ba/2200...0
Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. In Proceedings of the 2023 Network and Distributed System Security Symposium (NDSS'23) Internet Society, 2023. doi: 10. 10.144722ndss URL https
/0 1tt.::/...r/.................... 2733 23087
Larry Wasserman and Shuheng Zhou, A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):355-38, 2010. doi: 10.1198/jaaa.2099.mmmoll
Le Zheng, Arian Maleki, Haolei Weng, Xiaodong Wang, and Teng Long. Does t,-minimization outperform 4--minimizttion? IEEE Trunsactions on Information Theory, 63( 63((1):669666633 2017.
Haolin Zou, Arna Auddy. Kamiar Rahnama Rad, and Arian Maleki. Theoretical analysis of leave-one-out cross validation for non-differentiable penalties under high-dimensional settings. arXiv preprint arXiv:2402.08543, 2024.
Haolin Zou, Arnb Auddy, Yongchan Kwon, Kamiar Rahnama Rad, and Arian Maleki. Certified data removal under high-dimensional settings. arXiv preprint arXiv:2505.0764/ 2025. URL
https: //arvvvaavivv. http://wwww..r/r/o//////555.../
14

---

Published as a conference paper at ICLR 2026
A APPENDIX OF GAUSSIAN CERTIFIED UNLEARNING IN HIGH DIMENSIONS: A HYPOTHESIS TESTING APPROACH
In this supplement, provide motivations B for some of the procedures in the paper, more background on Gaussian certifiability C discussion and comparison of assumptions on the per- example loss functions D. proofs of theoretical results G H implementation details for experiments | and results from additional simulations. For completeness, we will also restate the proposed Newton-based unlearning algorithm B and theoretical results F
in the paper.
B MOTIVATIONS BEHIND OUR APPROACH ON A HIGH LEVEL
In this section, we provide motivations for several aspects of our paper a high level. First, we provide intuitions for our approach to describe the problem of machine unlearning. Then we discuss the theoretical assumption of (generalized) linearity of the model of data, and applicability of the framework in general. We end with discussing our experimental metrics and the reasoning behind their focus prediction-level distributional differences GED and UED,
B. MOTIVATION BEHINND THE DEFINITION OF MACHINEE UNLEARNING
On comparing the unlearned A(3, DM. T(D,), b) with A 0, M)) b) and not with the ideal retrained model A(D,M), for the criteria of Gaussian certifiability.
Condition D.
In considering Gaussian certifiability, the following the reason for comparing the output A(3, DM. T(D,), b) of 'the unlearming algorithm on the full dataset with removed set MM' and A(33MM 0, (DD, b) 'the result of the unlearning algorithm on the dataset without M with an empty removed set'. Our hypothesis testing procedure is conditional on the data D.
Why condition D.
This conditioning required as unlearning happens after learning, should be captured almost surely or conditionally on D. Therefore, the natural base candidate A(D,M) 'the learning result on the dataset without M to compare to, becomes deterministic. More precisely, conditionally on DD the distribution of A(D,,M becomes a Dirac mass probability distribution and hence trivially distinguishable from 'any other' probability distribution, unless the learning algorithm is itself randomized, which we do not know priori (in general). In our case, the learning algorithm is just Regularized Empirical Risk Minimization, which is deterministic given the data.
B.2 MODEL ASSUMPTION AND APPLICABILITY OF THE FRAMEWORK
On the assumption of (generalized) linearity of the model and applicability of the framework.
GLM in theory.
Within digh-dimensional statistics and machine learning, we consider a Generalized linear model dP (x,z) dp( ( 3))q(y))= x: 13²) capturing a large class of statistical models, includ- ing linear, Poisson, logit, multinomial regression, single index models, etc. This is indeed a large class of models among high-dimensional machine learning models considered in the theoretical literature.
Gausssian certifiability in theory.
Our focus in this paper is on closing the gap by proposing 'universally applicable' definition of certifiability that is well-suited in high dimensions. As argued in the paper, the proposed notion the most practical, optimally achievable, statistically interpretable, and robust notion of certifiability that optimally captures a broad class of noise adding mechanisms.
Practical and theoretical deficiency of previous notions of certifiability.
None the previously proposed notions of certifiability, including the proposals of Guo al. 2002 Sekhari al. (2021) 7ou al. (2025) variations of certifiability, and the
15

---

Published as a conference paper at ICLR 2026
proposal of Allouah et al. (2025b) on a divergence-basee certifiability, have all these nice theoretical properties of E Gaussian certifiability simultaneously. This essentially stems from the fact that all these previous notions are incompatible (in achieving optimality) with noise adding mechanisms, the practical way of achieving privacy. We refer the reader to Dong al. (2022) for elaborate discussions these deficiencies.
8 Gaussian certifiability in practice.
Gaussian trade-off curves the core of our proposed Gaussian certifiability framework, and they appear in practice, PPaelczyk et al. (2025). Here, these authors allow different choices of learning and unlearning algorithms of their choosing than the ones used to establish the theoretical results of the paper.
Applicability of our Gaussian certifiability framework beyond the proportional regime. We believe that because its intrinsic high dimensional nature, the current (Ó,e) Gaussian certifiability framework does provide canonically solid base for any such high-dimensional machine unlearning setting, proportional (p n) and beyond (p > n.) (including modern Neural networks), with varying loss functions (neural architectures). data distributions, learning, and unlearning algorithms. Validating the Gaussian certifiability framework with other learning or unlearning algorithms in regimes beyond the proportional regime is an interesting direction to pursue in the future.
Applicability of our more general f-certifiability framework.
We believe that our more general f-certifiability framework applies to the more sophisticated structured unlearning scenarios. including class or concept unlearning Allouah al. (225a). The algorithmic question would be an interesting direction to pursue in the future.
Summary of utility and flexibility our f certifiability framework.
We believe that in all the situations mentioned above, our (d, e) Gaussian certifiability framework would serve the tightest possible notion of certifiability in high dimensions, with changes in data distributions, loss functions, learning and unlearming algorithms. More precisely, Gaussian certifiability serves as the canonical and tightest possible notion of certifiability high dimensions, as long as the coordinates 3r of the released statistic 3 E IP are generically continuous, instead of being (structured or discrete) constrained such as binary 3 E {0, 1}. Even in such highly non-Gaue non-Gaussian and discrete high dimensional situations, our flexible and more general ʃ certifiability framework 2 applicable, and we believe that our framework is flexible enough to dictate what different baseline f to choose from depending on the class of problems hand. Natural examples of non-Gaussian baseline f includes f (1Po()), Po(E)), where Po(E) is the Poisson distribution with mean E. apply the Poisson framework for sparse networks, including problems of graph unlearning with approximately Poisson degree distributions Chen et al. (2022).
An interesting direction would
Newton-based unlearning in theory.
Given the superiority of our proposed E- Gaussian certifiability framework in high di- mensions, we restrict ourselves to showing its utility for particular noisy Newton based SenorithmSSekhann et al. (202I) in the Generalized linear model as a foundational step.
Newton-based unlearning in practice: (from GLM to LLM)
Newton-based unlearning popular in practice and has been used for neural networks in Bui existing papers Guo et al. (2020). Bui et al. (2024). We believe that the theoretical insights gained from analyzing these Generalized linear models can help us better understand the high-dimensional behavior of more sophisticated models, including going beyond proportional regimes, and Neural Networks used LLMs and vision.
B.3 EXPERIMENTAL METRICS AND PREDICTION LEVEL EVALUATIONS
On the accuracy metrics, and their focus prediction-level distributional differences
We do not rule out other accuracy criteria for machine unlearning problems. However, most of the existing literature has also focused prediction-level accuracy. This emphasis is because such a criterion is more closely aligned with many Al applications, including image classification and predictive modeling. Secondly, good prediction accuracy usually implies good "upper-stream'
16

---

Published as a conference paper at ICLR 2026
accuracies, such in the training level. This is indeed true in our study, Theorem in the supplement material indicates. Hence, to make our results comparable with the existing literature and clarify the benefits, also adopted notion of prediction level accuracy. For example, see definition of Generalization Error Divergence in the paper for measuring accuracy. Below, we explain the reason behind picking the experimental metrics GED and UED.
GED.
The notion of Generalization Error Divergence focuses on the distributional level general- ization eπror in comparison to previous notions like excess risk Sckhari et al. (202T). It has been shown in Zou et al. (2025) that such previous notions are not well-suited in high dimensions, which is based on the fact that the loss & (indeed with low tolerance) compared to the worst-case bounds, which very much restricts the class of loss functions, particularly in high dimensions, including the ridge regularized empirical risk minimization. UED.
allow unbounded Lipschitz bounds
In the experimental section, we evaluated the prediction accuracy on the Unlearned (Error Divergence) set as well, with the motivation that the unlcarned set should not have an undue advantage over new data in terms of prediction. Indeed, the error levels are comparable on the unlearned dataset as well as the new test data, thus validating that the unlearning algorithm has successfully removed the influence of the unlearned set from the training data.
C GAUSSIAN CERTIFIABILIT AND CONNECTIONS WITH RELATED NOTIONS
Having outlined the motivations for our approach on high level, now provide intuitions for some of the more technical aspects of the assumptions made in the paper. First, we describe in detail the relations between our Gaussian certifiability framework and other previously proposed frameworks. Second, we describe from a dual perspective the emergence of Gaussian certifiability over any other framework of certifiability high dimensions.
C.I THE GAUSSIAN CERTIFIABILITY FRAMEWORK: RELATIONS WITH OTHER NOTIONS
On comparison of Gaussian certifiability with variations of e-certifiability
In short, our definition of Gaussian certifiability (with tolerance Φ) implies (for a certain collection of pairs of e better known 'privacy profile"), ), collection of å extension of the unlearning framework proposed in Zou et al. (2025) with tolerance ø as well as collection of the certifiability definition of [Sekhari al. (202 with tolerance level Proposition 6 and Corollary of Dong et al. (2022).
0. This follows immediately from
On comparison of Gaussian certifiability with Rényi divergence based certifiability
In short, our definition of Gaussian certifiability (with tolerance Φ) also implies the Rényi certifiability framework of Allouah et al. (2025b) of all orders 'a' (with tolerance Φ) for a certain range of the other parameter. This follows immediately from Corollary B.6 in the appendix of ofon et al. (2022). So, the Gaussian certifiability framework also subsumes the Rényi divergence-ber based frameworks.
Intricate zoo of different notions of certifiability and Gaussian certifiability at its center
Having discussed that Gaussian certifiability (with tolerance Φ) implies previously proposed such notions, including their privacy profile versions, we would like to highlight three key points here.
Lossless conversions.
First, from the Dong et al. 2022 results, Gaussian certifiability with tolerance ø is in fact equivalent to collection of ε unlearning extension of the definition proposed in Zou (et al. (2025) with tolerance Φ. Therefore, the conversion is lossless, which is not the case for conversions from Rényi certifiability to e - certifiability and vice versa.
Blackwell ordering.
Secondly, Rényi divergence (even including all orders "a') does not determine Blackwell ordering (see Proposition B.7 in the appendix of Dong al. (2022)). For us, it means
17

---

Published as a conference paper at ICLR 2026
that Rényi divergence- basedd certifiability does not behave tightly under post-prne prostssrocsiing of the output of the unlearning algorithm. This a necessary requirement for an unlearning algorithm. In contrast, trade-off functions exactly capture Blackwell ordering (see Theorem 2 of Dong et al. )002)) and is the core of our definition of Gaussian certifiability, thereby confirming optimal behavior of our certifiability under any arbitrary post-processing.
About tolerance d.
Finally, as mentioned in the paper, we allow the tolerance & to be positive, and it is of utmost importance, especially high dimensions, and absent (Sekhari et al. (2021) Dong et al.) Allouah Allou,Allouah et al. (2255)). This allows us derivatives of the unregularized individual loss [ (as well as the regularizer r) have polynomial growth, in particular, unbounded (albeit with small tolerance Φ), whereas (Sekhari et al. (202I). Guo et al. (2020), AAlloahh al. (2025b) requires worst-case uniform bounds on them (simultancously with SI(1) strong convexity assumption), which break down in high dimensions even for ridge-regularized empirical risk minimization.
Choosing the tolerance in practice.
As mentioned above, the only practical requirement is that has be positive and is completely up to the user specification, and does not affect empirical performance or computational stability above threshold Φn (see Theorem for the value of Φn).
Example. The dominating term for the computation of the threshold Φn (see Theorem 4 under the proportional regime (consider the responses known to be bounded, so that 4n 0) is given by n3 so the smallest possible allowed choice of Φ for ~ n = 10a is given by approximately x 10-15, which effectively negligible. More generally, our results prove that the minimal threshold on, ngnn"
(y) + 8n + ne n/- + 2 - 0 as n. - 30, with an explicit dependence on (n, p) and growth of the response (see Theorem 4) which is known for given model of the problem (such as linear regression, binary classification or more generally whenever is known that responses remain bounded), and the threshold of smallest á for a fixed (n, be determined quite easily. Any e larger than the threshold on won't affect computational performance or stability.
C.2 GAUSSIAN CERTIFIABILITY THE CANONICAL FRAMEWORK OF CERTIRABILITY
As mentioned above, the thcoretical well practical implications of the (d.E)-GPAR framework are significant compared to all previously proposed notions of certifiability, especially in high dimensions. In summary, in (practice) every real-world scenario, where we achieve privacy by adding 'isotropic log-concave" noise, GPAR beats every other notion of privacy, in high dimensions.
On Gaussian certifiability as the canonical framework of certifiability in high dimensions
Dual perspective. A detailed answer to the above question lies in an interesting dual perspective. is the realization that the starting point in the theoretical investigation of unlearning (privacy) is not begin with a criterion of privacy, but with how we achieve it in practice.
Step 1.
The most natural and sought after way to achieve unlearning (privacy/certifaailiitt) is to add noise the (deterministic) algorithm output, and Gaussian noise appears as natural candidate high dimensions because the following intrinsically high dimensional fact that with high probability (up tolerance Φ). most 1d projections an isotropic high- dimensional (log-concave) distribution are approximately Gaussian Diaconis Freedman 1984)) Klartag [Theore 1.1].
Step 2.
In the context of differential privacy, this translates into the fact that up to tolerance ø. in high dimensions, a large collection of dog-concavee noise adding mechanisms becomes comparable to the Gaussian noise addition mechanism Dong et al. (Theor 3.1]. This makes the Gaussian perturbation mechanism the canonical noise adding mechanism in high dimensions.
Step 3.
18

---

Published as a conference paper at ICLR 2026
So. up tolerance 6, the question reduces to devising unlearning framework that can tightly capture the Gaussian mechanism. It turns out trade-off functions capture it in the tightest way possible through Blackwell's theorem Dong et al. [2022)] [Teorem 2].
Step 4.
More precisely, all the previously proposed notions of unlearning, including variations Guo et al. (2020), Sekhari et al. (202T). Zou et al. (2024), Rényi unlearning of Allouah et al. (2025b). are not tightly achievable under the Gaussian mechanism except for Gaussian certifiability Dong et al. [Th2rre 1, Equation 6]. So, this establishes the natural emergence of the (Ø,e)-GPAR framework with tolerance & as superior over any other framework in high dimensions.
D ASSUMPTIONS ON THE UNREGULARIZED INDIVIDUAL LOSS L,, REGULARIZER R AND COMPARISON WITH PREVIOUS WORKS
Before delving into precise comparisons with previous works such as Sekhari et al. (2021). Allouah al. (2025b), address the motivations behind some of the generic assumptions unregularized individual loss / and the regularizer r in the proportional regime.
== A(Da) = arg min
L(B) == arg min BERR
Xr(3) Σ Elvs x B),
(18)
Berr
D.1 ON CONVEXITY AND SMOOTHNESS OF UNREGULARIZES INDIVIDUAL LOSS I. AND THE REGULARIZER
Convexity of the pair of losses (f,r) and strong convexity of the regularizer are assumed to ensure that there exists unique minimum the total loss function L above (18). Smoothness the pair rf, is assumed so that the Newton method proposed in the paper makes sense theoretically.
However, we expect the theorems presented this paper to extend to certain non-convex loss functions, potentially under stronger constraints the size of the removal set. More specifically, as long as the local minimizer of the total loss function after data removal remains within the basin of attraction of the local minimizer for the full dataset, and the total loss function is strongly convex within that basin, a similar proof strategy should be applicable. The main remaining challenge, however, is to verify whether these assumptions hold for widely used AI models such transformers or multilayer perceptrons (MLPs). This is certainly an interesting question for future research and one of the directions we plan explore further. We also note that all prior theoretical works on certified unleaminn cited in our paper, including Guo et al. (2020), Sekkari et al. (2021) Allouah al. (2025b), Zou al. (2025) assume convexity of the pair (E,r).
D.2
ON THE REGULARIZATION PARAMETER BEING O(1)
Step 1- Natural growth of norm ||3 |2 = B MVVD) of the true parameter 3
In the high-ddmmensioal proportional regime p ~ n, it is natural to assume that the l2 norm ||33* ||2 of the true underlying parameter f is atleast of order / One reason for such an assumption comes from standard volume estimate of the ball of radius B dimension Vershynin ( Exercise 4.29]
7P/2
1
2 B p/2
(B))
BP
(19)
T(E +1)
VTP
p
This immediately implies that unless B translates to the fact that unless nothing p ac, and therefore not interesting regime. Moreover, stricter but more intuitive assumption on 3 causing this l2 growth is that the coordinates the underlying
2 volume of the ball goes zero. This Z volume of our possibilities for 3 shrinks to
*This is exactly assumption 3 of Sekhari al. 2021 where the parameter B should be treated as of order D) /p). This is one such quantity that contributes to the blowup all estimates of their paper.
19

---

Published as a conference paper at ICLR 2026
parameter (3 are of order individually, is often assumed for precise high-dimensional asymptotics Miolane & Montanari (2021)
P
p Σ B =
weak convergence
63: Σ
d p and lim p-oce
(20)
for some Borel probability measure j on with finite and positive second moment.
Step 2- balance between noise and regularizer.
Consider the simplest case ridge regularized r(3) = ||,112 quadratic loss ((y, x ()
=
(y x² [ Observe that the total loss has the form
L(8) = lyy x |||31|
(21)
Now, given that the true minimizer 3 has order one coordinates, we would also want to have order one coordinates for the minimizer 3 of the empirical total loss L. In this case we even have
(22) Now, under our normalization of each row I; of X is i.i.d. (sub)-Gaussian SW(0. Σ) with Amaux (Σ)= S we immediately have that ||X X| = (1)) with high probability Vershynin 2018 [Fxercise 4.43). Therefore, one would want À @(1) to not develop significant bias either towards the Hessian X X of the actual loss, nor towards the Hessian MI the regularization term
β = -x
D.3 ON COMPARISON WITH SEKHARI ET AL. (2021)
In this section, we show that the results of /ekharii al. (021) blow up in our high-dimensional proportional regime (18). and motivates our definition of Generalization Error Divergence. First, observe that (Skhari al. (202T) studies a one-step Newton method with Gaussian perturbation as machine unlearning algorithm that is similar to our work.
Step 1- mapping the optimization problem and loss functions.
To map their result to our setting, we first set the common ground for the optimization problem of the estimator 3 and define the per-example loss f in terms of the unregularized individual loss and regularizer r
1 12
12
i = arg min
Σ B n
f(3, 24) arg min Σ f(8, zi), where
(23)
f(8, 2) = Ely: B)+ + X r(B), and F(3) = [[f(
(24)
n
Step 2- mapping the assumptions.
Sckhari et al. [20 4, Second equation 24] assumes that f is worst case L = (ip--iipsh worst case À è -strongly convex, and worst case M O1))-Hessaa Lipschitz, and show the following analogue of Generalization error divergence result of ours (Theorem 3) after one noisy-Newtor step (substitute ||
1|2
((vP)).
XB2
mL2
E F( min F(g)
log
(25)
B
2
X3n2
An
n n
11
log
mL?
(26)
*The computation holds more generally in setting with the same scaling for and p up constants. 'This example makes it clear that according to the normalization in Sekhari al. (2021 the regularization parameter also called À should he taken to be of order @ (L) throughout their paper. This is another such quantity that contrihutes the blowup of all their results.
20

---

Published as a conference paper at ICLR 2026
Under our high-dimensional proportional regime p n, and from the arguments in D.2
follows immediately that À = + ( M = =1(1), and L = ((1). This simplifies (25 to:
F( min F(3) =0 00 ny nynMmm L3
log ( + mI.
(27)
1
E
which diverges n, dimensions,
with n/p - 7 making the result inapplicable in high-
Summary of the failure of [Sekhari et al. 2021) results and motivation for GED.
To summarize, the bound above (27) essentially concludes that one-step noisy Newton method of [Sekhari et al. (222)) under the notion of (e, (e.d))-nlearming does not achieve vanishing change in generalization capabilitiess (in fact it diverges), and therefore remains inconclusive in high- sigh-dimessional setting. We emphasize that failure of the above measure of accuracy (called excess risk) (25) in high dimensions motivates us to consider different way to measure accuracy, namely through the Generalization error divergence. which we show goes to zero even in the high-dimensional proportional regime.
Remark 1- On the regularization factor À (an important normalization).
Observe the A is used in (24) instead of X, since in Sekhari et al. (2021) |||3||2 has been added n times in total and once to every example (Sekhari et al.
4), whereas we only add it once to the entire pure loss part Dx= [yts, B). According to the arguments
D.2 A = (1) in our normalization of [X
X = ((). This translates to À = θ (t)
in their normalization, causing blowup in (25
These changes in normalization of X, although ineffective in low-dimension, turn out to be quite important in high-dimension. Finally, if some readers are still not convinced by our arguments in D.2 in favor of = ((1) in our normalization, observe that Sekhari et al. [ 2] also finds the 'optimal choice' of X is of constant order in our normalization or of order in their normalization.
Remark 2- On the worst case Lipschitz constant L of loss f (a weakening).
This worst case L (1) Lipschitzness of the per-example loss f fails even for the simplest ridge regularized r(3) = || quadratic case 3 + I(y) 2z" 3) = (y - x= 3)², since quadratic functions are never worst case Lipschitz. A weakening of this stringent assumption is given in our paper (A4) by allowing the Lipschitz constant 'é* of the individual loss é to have polynomial growth, which we will prove happens with low tolerance probability øb The key difference is that our proofs will be intricate and different in comparison to the standard proofs of such results using usual optimization assumptions.
Remark 3- On the worst case Hessian Lipschitz constant M of loss f (another weakening).
M does not appear in the simplest case of ridge regularized least squares, but, we weaken this stringent worst case Hessian Lipschitzness assumption by allowing polynomial growth of L in (A4)
D.4 ON COMPARISON WITH ALLOUAH ET AT.. (2025)
In this section, we show in detail that the standard optimization assumptions of 2((1) strong convexity and O(1) smoothness of the per-example loss f as made in Allouah et al. (2025b), fails completely in high dimensional proportional setting of ours. This in fact true in the simplest case of ridge regularized r(3) = || quadratic (unregularized individual) loss [(y] (3) (y x" 3) case.
Step 1-mapping the optimization problem and loss functions:
To map their result to our setting, we first set the common ground for the optimization problem of the estimator 3 and define the per-example loss f in terms of the unregularized individual loss & and regularizer r
x2 [(8 24), where Σ Σ ((3,2)) arg min 1=1
B = arg min
(28)
B
n
3
1=1
f(8, 2) = lly: x (3) + r(3).
(29)
21

---

Published as a conference paper at ICLR 2026
Step 2- Ridge plus quadratie loss.
Denote 2, (zt Ut) RR++1 Allouah et al. (2025b) assumes that per-example loss
satisfy standard optimization assumptions: / F13 z;) is simultancously
worst case 22(1) strongly convex
fB, z,) ž Help for all Z,
(30)
and worse case L (1) smooth
S 2:) 3 LIp for all z,-
(31)
Now, consider the ridge regularized case r(3) || with (unregularized individual)
quadratic loss 1yy|z" 3) = (y- x²" 3)² of our high dimensional setting ~ n 18 Then we have
A
G arg min
(., = arg min
f(3, with 1(3 = (yi (Vi- B) |131
(32)
Alp T +2 and V n
2 f(B, 2x:
f(B, -2X X + 2XIp
(33)
Step 3- Consequence of Hessian computation.
Since all the (distinct) eigenvalues of the Hessian of f are 1 2 + +2|12; 112] in the high dimensional proportional regime p ~ n, L = (1) smoothness constant of the per-example loss f inevitably requires the scaling ||ara] ~ 1 (with high probability) for all i E [m] 4.2 This in turn implies |X] (1) (with high probability) Vershynin [
4.43] and requires a comparable À = (() D.2 But, this completely destroys the P 21(1)
strong convexity of the individual loss f. as Amin (V2 2.) = 2 * (1)).
Summary of the failure of assumptions made in Allouah et al. (0255)) in high dimensions. The above bounds essentially convey that the standard optimization assumptions made about the per-exmaple loss f in Allouah al. (2025b) do not capture the simplest model of ridge regularized least squares in high dimensions, in the context of machine unlearning in high dimensions.
Remark Our relaxed of assumptions.
The failure of the assumptions made in Allouah et al. (2025b) demands a new set of relaxed assumptions for the per-example loss that are well-suited in high dimensions. In this regard, we work with the weaker set of assumptions F. Most importantly, our assumptions on (only requiring) convexity of f and v-Strong convexity of r above actually means that per- example loss B > f(B, z) = Iyy, x 3) + X (.3) is only required to be Av strongly convex, which is significant relaxation of the requirement of 12(1) strong convexity of f, capturing the concrete case of the ridge regularized r(3) = || quadratic loss I(y, 2) = (yv - 2)².
We end with the observation that on the algorithmic side Allouah et al. (2025)). Neel et al. (20TT) focuses on proposing first-order methods of machine unlearning based on gradient descent and stochastic gradient descent, whereas we focus second-order Newton-based method.
E NOISY NEWTON-BASED UNLEARNING MECHANISM
Newton method is an iterative method for solving optimization problems based on a second-order Taylor approximation of the given optimizing function Boyd & Vandenberghe (2004).
Definition 5. (Newton-Raphson method) Suppose that h Rp - IRP is differentiable function with an invertible Jacobian matrix G anywhere on Rp and that h has a root h((²)) = 0. Starting from an initial point (00) E IRP, the Newton method is the following iterative procedure: for step 2
3 = ((( -C- (30-
(34)
Using the Newton method Sckhari et al. (02T) suggested the following unlearning algorithm: Approximation step starting from (3, one Newton step with h VL to obtain:
( = --G(L,,)) where G(L,M) is the Hessian of L.M
(35)
22

---

Published as a conference paper at ICLR 2026
Randomization step. add Gaussian noise N(0, TTI,) @ to have the unlearned output
Noisy step Newton output: A(A PM: T(D,), BM b.
(36)
Intuition and the goal. First, the choice of a will be discussed in our theoretical results. Next, note that since {()) M differs from B.. the difference between the two vectors may reveal information about the data be removed, D.v- Hence, a standard practice to obscure by adding noise
F MAIN THEORETICAL RESULT: ASSUMPTIONS AND CONCLUSIONS
F.1 TECHNICAL ASSUMPTIONS ON THE LOSS FUNCTIONS AND THE DATA
Loss functions. We describe the assumptions on the unregularized individual loss and the regularizer r (18). To ensure that the RERM introduced in (18) has unique solution (from strong convexity arguments) and Newton unlearning makes sense theoretically, the following assumption are made:
(A1) Separability of r. r R + R+ is separable. More precisely, r(3) = Eke( Th (5x))
(A2) Smoothness of (1,r). 8 R R + R2 and R² + R_ are both thrice differentiable.
(A3) Convexity of (l,r). and r are proper convex, and r is v-strongly convex for + > 0.
(A4) poaenooiillggowwwtit 3 constants C, s > 0 such that for all y, (denote ély, 2) := 0,((y, =))
max({ly, 16(g, I 2)13 - C(1 |y| |z|*) and v2r(B) diaglix (Bx)) (Bx)]keppl (37)
is Crr (m)--pisii (in Frobenius norm) in ,3 for some (nr (polyylgg(n)).
Relaxed assumptions on (f, and the ridge example. First, note that these assumptions (e, r)
inspired from Zou et al. (2025), and they weaken many of the standard optimization assumptions
of (2(1) strong convexity and ((1) smoothness of per example loss in Allouah al. (2025b) or
variations thereof in Sckhari et al. (2021). Concretely, the ridge regularized r( 3 quadratic
loss ( 2) (y - 2)² satisfies all the assumptions above. But Allouuh al. (2025b) and Sekhari
et al. 2021 both fail to capture this example in their respective frameworks, as was detailed earlier.
Data. We require the following on the data that generates our features æ; and responses yi-
(BI) Subgaussian features. I; are mean zero sub-Gaussiae Gaussian vectors with covariance Σ denoted as 2; Add
SO, Σ). We further assume that Amax (Σ) < Cx, for some constant Cx > 0.
(B2) Sub-polyoggarihhiic responses. We assume that P( > C,(m)) S (n(n) and Ely, S Cy., for some (n) = O(polylog(n)), a constant Cy,s and gn = onn )
Intuition behind features and responses. Assumption B mean-zero sub-Gaussian features is mild and frequently made in many papers on high dimensional statistics. See for example Miolane Montanari (2021); Rahnama Rad & Maleki 2020); Auddy al. (2024); [Zheng al. (2017) Donoho & Montanari (2016); Bellec et al. (2025). Assumption [B2) not a stringent assumption either, and most popular models such logistic regression, Poisson regression, and linear regression satisfy this assumption. Using these assumptions we can finally prove our main theoretical results.
F.2 THEORETICAL GUARANTRES: USER PRIVACY AND MODEL ACCURACY
One step Newton achieves (ø, e) GPAR. Our first result shows that for suitable noise variance, the randomized one-step Newton unlearned estimator defined in (4p satisfies (ø, E)-ARR
Theorem 4. Suppose Assumptions (A7) (A4) as well as (BI) B2) hold. Then there exist poly-
logarithmic C₂ (n(n), (2(n) = Oppolylog( (n) n)) for which the randomized one-step Newton unlearning
14 when used with a perturbation vector b ~ N
122 2
IT),) achieves E)n,E) with
C2(n)m²
R Cm)
Φn =
) + 8n ne p/2 PP2 + 2e P-+ O.
(38)
2\vn
23

---

Published as a conference paper at ICLR 2026
The proof of this theorem is presented in the next section. After the above theoretical guarantee ensuring user privacy, we now calculate the GED of this machine unlearning algorithm.
Theorem 5. Suppose Assumptions (AA(AA)) as well as [B]]]
[B2) hold. Consider the unlearning
estimator defined in (14) with the noise variance set according to Theorem
2 Then, with probability
at least (n + 1) 1 14n ne p/2 22 P- - e-(1-log(2));
(1
1 vp
mm + 2) Aun
polylog(n).
F.3 ON THE PROBLEM OF DETERMINING THE POLYLOGARITHMIC FACTORS C. (n)), C2(n) AND DECIDING ON THE NOISE VARIANCR a IN PRACTICE ON A GIVEN DATASET 'D
In this section, we discuss the perspective of practitioner on how one decides on the noise variance of the Gaussian mechanism b in practice for a given dataset D. following our Sussy-Newton-basee This will lead us to discuss the
framework to ensure both certifiability 4 and generalizability dependence of the certifiability bound (Theorem and the generalization bound (Theorem 5 on the noise variance and eventually to the problem of determining or estimating the polylogarithmic factors Ci (n), (2(n) for a given dataset DD and for a specific choice of loss functions (4, r).
1. Dependence on Ø.
From the proof, it will be immediate that the (Ø, certifiability bound of Theorem 4 is satisfied for all choices of noise variance a above the critical threshold of a f with R
as mentioned in (38 Therefore, any amount (small or large) of positive deviations in user-chosen noise variance above the critical choice would not break the certifiability guarantees of Theorem 4 However, as expected, with increasing noise variance a, the
generalization error bound in Theorem [ will deteriorate. But, the dependence of the generalization error bound is linear in a as will be immediate from the proof, in the dominating term of the error involving _. So, the generalization error bound of Theorem will deteriorate only linearly with the noise variance a above its critical threshold. Therefore, the incentive lies with the user to choose the smallest possible value of noise variance a, or equivalently estimate the smallest value of R allowing the conclusion of Theorem 4 to hold given the dataset, user's s choice of loss functions, and other available problem parameters.
2. Computation of (2),
From the discussion above, is clear that to utilize the theoretical guarantees provided by our noisy-Newton based framework for given dataset D {x,,, Va fi=1, needs to explicitly compute an upper bound (as small as possible) on the value of R, as mentioned in Theorem 5 in terms of parameters available to (or chosen by) the practitioner.
3. Features.
First, to match the dataset with our framework of assumptions data distributions, one must center the feature vectors {r + { - Th with き- in such a way that they have the scaling of our assumptions (BI) The computation of the empirical (after centering and scaling) covariance matrix Σ n
1 nn Li Iú, and scale them B
and its corresponding top eigenvalue Xmax(E) can be done explicitly. Although not addressed in the theoretical results of this paper, under the sub- Gaussian assumptions on the features, E is strongly concentrated around its mean Σ, the population covariance matrix (see remark 4.7.3 of Vershynin (2018)). As consequence of this and since the eigenvalues of positive definite matrices are Lipschitz functions satisfying [mmax - Amax (B) S ||A - BlI, with
probability -P we have Xmaz (Σ) < Amax (Σ) E Σ/ S Cx + C( + Cx
C' for some universal constant C 0. Therefore, the conclusions of Theorems and
"Oe can consider smaller levels of noise a r. and our results would not break down, But, as expected,
going to smaller a would require us to analyze the dependence of the probability Pfmax (1 - 2
r] as a function of r(S R), involved Theorem which will he done elsewhere
*One way to scale is to divide each vector x; # by the 2a norm of itself to have each of them lie on the unit sphere in dimension p. This was the intuition hehind our scaling with dimension assumption (B1)
24

---

Published as a conference paper at ICLR 2026
5 will be useful in practice, since the empirical covariance matrix satisfies the same set of assumptions required in our framework with high probability, as is the case for the population covariance. In summary, it's safe in practice to work directly with the empirical covariance matrix Σ, rather than the practically unavailable population version. Finally, deciding whether the features (even after centering and scaling) of the given dataset are actually coming from a sub- Gaussian population or equivalently keeping our conclusions of without making any distributional assumptions on the features {az hi is an interesting question for future study.
Theorems 4 5
4. Response.
For the responses y, we have the technical assumption (B2) requiring (probability bound)
P[ > (n)) S Un and (expectation bound) IE 1/ S Cy.s for some Cn(n) = Oppolylog()) (n)
U constant Cy.s and nqgh = o(1). Both of these technical assumptions
used in our proofs, and most importantly, the quantity ngh appears in the 'tail' probability of both of our Theorems 5 Indeed, in practice, one can try verify whether the responses in the given dataset (avarlable to the practitioner) satisfy the above assumptions of our framework by computing the empirical probability bound and empirical expectation bound with respect to the background probability measure P, = n Ei= 6g.- Although not addressed in the theoretical results of this paper, since the responses are one-dimensional, there are no high-dimensional consequences of replacing IP with iP,, while computations only involve the responses {ur hi This is the same we do in the classical central limit theorem to find confidence intervals, and one expects strong concentration of functionals (such as moments tail probabilities) of IP,, to be around functionals of IP for a large class of marginal distributions on the response encompassing sub-Gaussian responses and many others. However, for a large class of responses y for which the responses {v: are already known (to the practitioner) to be bounded by M, such as binary or multiclass classification, there is no need for empirical verification with P,,, as described above; our framework applies directly, since both conditions are satisfied with Cy = M + 1, and
Cy.a MM with qi2h) 0. As will be shown later that framework also applies to problems where the practitioner is trying to model a feature- responsive dataset (x,, y: } coming from a high-dimensional linear regression, logistic regression. Even more generally, with the empirical measure, P., the practitioner can choose the growth constants (n), Cy,s of their choice so that they can control the value of nqn" in our results
(2) and their desired error probability
5. Loss and the regularizer.
We will soon show that the computation of the constants C (n). O2 (n) within the class of separable regularizer (AI) smooth loss and regularizer (A2) and convex loss (A3) depends through the strong convexity constant of (only) the regularizer (A3) and involve
the Lipsshitzz-yyee constants for the polynomial growth conditions for both the derivatives of loss and regularizer (A4) For high- -igheniieniional applicability,
would like to make
our framework available for a large collection of pairs of loss functions & and regularizers r. g.gnngg far beyond the implicitly low-dimensional standard optimization assumptions of Sekhari et al. (202T). Allouah et al. (2025a). These relaxations in assumptions and attempts to accommodate our results simultancously for a large class of loss-regularizer pairs make the constants C1 (n), (2(n) necessarily large. However, for fixed choice of (f, r). these constants can be computed, although we do not claim any sharpness of these constants (shown below) up to the constant order (1 + o()), since determining the constants in high dimensions often require exact asymptotics, whereas our focus was on getting practically useful and directly applicable non-asymptotic bounds. Before writing down a general expression for C1 (n), (2))), we describe a procedure to apply in practice to decide on the noise level a and finally compute these constants C1 (n.), C2 for linear regression and logistic regression examples.
6. Calibrating the noise level a.
We will show explicitly that (n(n) vlog n with nggh") 2 for high dimensional linear regression
and Cy.. ++1 1 (no polylog) for binary or multiclass & classification with gl.
25

---

Published as a conference paper at ICLR 2026
From the proof of Theorem 4 (see equation 611 noise b N( ((0, is injected in the estimate ((1) M where o²
R² 25
where R (i(n)
Ca(n)m²
as an upper bound to 2Aom
I² max R'M: where RiM - aMm - 8
First calibration method.
In practice, the unlearning algorithm designer would know what the deletion set M (along with the corresponding dataset {ri, Yi hem),, so its enough to bound (or practice for given deletion request
empirically estimate) R'M BM 3/
M 10
Observe that the unlearning algorithm designer does not have access to 3rM in our unlearning framework. Hence the ideal choice
the noise level o = R'M
is not possible in our framework.
(39)
Although not covered directly by our theoretical results, in practice one can choose a much more computationally explicit noise level given by |
R
where R'm ||
(MMM
G. (0)
[Σ> (. Ila,
(40)
SEM
where each of the quantities are defined below explicitly and is available in practice. Now, we explain the intuition behind the above choice of a given deletion request M. From the first order conditions (VL(B) VL,
0) for the total empirical 2 and applying integral form of Taylor's
loss L ① and its deleted version L
theorem (f(x) f(0))= So f'(tz (1 )dx the gradients VL, VL, at
their respective minimizers 3.3,M. we have the following exact representation
.. (G Σ ((())2)) whereG M := :m: iEM
BMM - B = G
dt, (1
(41)
where (B3 denotes the Hessian of total empirical loss (after deletion) L After one Newton step iM on L starting at the trained ML model 3 (35 we have
B B iM | G
((3)2;
(42)
iEM
Observe that the quantity that we are supposed compute (or estimate) is given by c G
R'm = -
Σ ((()a::) ll2
(43)
but unfortunately the right hand side of (42 uncomputable in our unlearning frame- work, since G.M involves the ideal unlearned estimator B... unavailable to the practitioner. So, in practice, we replace B.M with one-step Newton estimator { in the expression GIM for the computation of R'M = 113,, - (WNlll. and call that estimate of R'M as R2,, given by the following 12
R" = " GTM(()
Σ (()),,) SEM
1l2 = 1| H2
(44)
10Our theoretical results (see equation (61) is covering worst case situation over all deletion requests, but in practice knows the deletion request before running the unlearning algorithm, and utilize that information by choosing a smaller (and more informed) noise level a.
"e denote ((3) mean 0zl(y,, a! (), the first derivative of at the ith data point (æ., v.) evaluated T 3.
Recall that G denotes Hessian of the total empirical loss L and is related to the Hessian GIM of the total (delcted) empirical loss L.M as L(()) (),) EiE f(ys, ... (), so the computation (evaluations various 3s) involving G.M (potentially unavailable) can be reduced to the computation of the Hessian G of
the available losses (the total empirical loss used during training) and the deletion part Eiem Elyi, (3).
26

---

Published as a conference paper at ICLR 2026
where GMM i= S. G ( dt.
(45)
Now, priori computing the integral numerically inside GKM seems difficult, and one can in practice think of applying some general purpose tools simplify computations. such as Monte-Carlo, by uniformly sampling several points within the unit interval and taking the average as a proxy, or can use quadrature formulas of their choosing.
After having discussed some standard procedures compute the integral, we now discuss the extra structure that we have for our problem which might also help the practitioner to compute these quantities quickly. First, observe that we are only required to compute quantity of the form || H u1l2, and there are also numereical schemes that can compute quickly H H- since Hw = (=](w) = db f + ów)]l=p is a Hessian matrix-vector product for some function f a point so we can get away without actually computing the entire matrix H. Second, our Hessian matrices are structured enough in the generalized linear model class that the high dimensional matrix integral reduces to simpler tractable scalar integrals
G3M(3)= = x [in (addag((((())))) (1())) MM + Adlaag[F (3))
(46)
G"M= = A + B where
(47)
A X diagl
1.((tB +(1 (1-t) +(1-t)8()) (dd keM
(48)
B = Adiag|
Fa((tt +(1 (M)
(49)
Now for given loss- rasslaaulaii pair (f, the scalar integrals above can often be computed often in exact form or using some standard quadrature formulas. Having described the calibration method of computing the noise level a in practice, we now provide an argument why is that calibration procedure theoretically sound [1 The problem boils down to a computation of the upper bound on the following difference
RR4 R'ml s (I ( - G"AA))
Σ SEM
(.())o:)): l|2
(50)
Going again back to our assumptions (A4) and
and following the proof of Theorem f in
Zou al. (2025) on the high probability Lipschitz bound the third derivative on the pair (E. and the tool developed in Zou et al. (2025)[Lemma A. help us show that
this difference goes
with high probability. In summary, the plugin estimator in the fixed point equation (41) could help choose the noise level in practice (40).
Second calibration method.
Inspired by Zou et al. (0025). we propose to compute R' instead, although computing ||,
R' = max Ml5m R'M, where R'u- B -B ( requires evaluating all (j
possible subsets, which is computationally infeasible even for moderate n. Hence, instead of exhaustively enumerating all ((M) configurations, we select a random subset
of size (small) my 100 and compute the maximum || 3 ll over this subset (including the exact unlearned estimates). To approximate the maximum, we rescale the result by factor of Vlog (jM) /log///oooo/oo mg.
7. Exact expression of (n), (2)
An inspection of our proof of would reveal that the expression of the implicit constants
C (n). (2)n) boils down to the constants arise in the proof of Theorem 7 of Zou et al.
2025 Here summarize their exact formulas in terms of the following constants:
We denote (3()) to mean 0221(ys, x β), the second derivative of at the ith data point (.r, y:) evaluated at x! 3, and the same for the separable regularizer r.
A completely rigorous proof of this calibration method would be interesting direction for future research.
27

---

Published as a conference paper at ICLR 2026
A: the regularization strength,
70 n/p.
is the strong convexity parameter of the regularizer,
Cx is the constant Assumption (B1) [B = =|E>| S p -Cx
we have from Zou al. (2025)
2/3 Ci(n) 3X2 Cue(n) (G
(2(n) (1 + (v + Cx) + (n)), where
C (VTi 3) high probability bound for |
Ci(n) is high probability bound for max (0)) (the explicit term is polylogs below)
Cu(n) is (high probability) Lipschitz constant for (M) in neighborhood of 3 (the explicit expression is max/polylog (n)), polylog, (n)} below),
(n) is the Lipschitz constant of f((3 in Assumption (A4).
(za(n) is a high probability upper bound for the following quantity max
X MMMGG T (B X,ll2, and is given by
Czz(n) (n) (NTO 3)Cx V1 Av
m(1 20 log(n))
The explicit expressions of the polylog(n) terms are:
polylog, (n) = (oxx
polylog, (n) = 1 + (2(2) + (olylogi
polylogs (n) = polylog, (m) + Cx
Av polylog2(1)
polyloga (n) = 1 + (n) polylogā
polylogs (n) = 2( + 3)Cx
V m2m + log--loogpppolylogg.
Av
polyloga (n) = polylog, (n) + polylog, (n)
polylog, (n) = + Cg( + polylog
polylogs (n) polylogs 4Cx
Av polylog>(n)
polylog, (n) 1 + (n) + (mlylogå
polylog ()) 1 + C (n) + (olylog
polylogn (m) = 1 (z)) + ppolylos + 2 cx
(51)
Note that the above cumbersome constants are for general classes of problems. For specific problems (see the following example) they could take much simpler forms. Another comment that in practice we don't 't know Cx, the largest eigenvalue of pΣ, but a researcher with a specific model instance can estimate it through the sample covariance Ct. Details are in the Featurrss part above.
Example 3.1 (Linear ridge regression). Suppose ya xi ~ N(a 1r, 0²)), then we have y/ (0, 72) with
2 22==0 + 1188112
Its negative logeliiel is the &g loss:
Ely. 2) = (y 2)2
2 ily, 2) = = - y.
Ely,2) =1,
?(y, 2) =
28

---

Published as a conference paper at ICLR 2026
If we adopt ridge penalty then the constants can be further simplified into 1, Cu(n) Cr.(n) = 0. This would inevitably cause the noise scale R 0. and this is actually consistent with the fact that one Newton step for quadratie loss function achieves exact solution BMM (broadly comes under the exact unlearning framework).
Example 3.2 (Logistic regression). Suppose y ~ -Brnouuli(p.) where
P: [1+c) -1+
The negative log- log-likelihood is then fyy, 2) y log(1 =- (1 y) log(1 + y (0,1),
and in particular ((y, z) < 2 log((2 + 2z.
Obviously |ud| < 1 and moreover,
e²
j 2) = 1 6²
S 1++ |y| 22
e²
(((,,2) 2)
(1+
1
3
( [v,
1+ +
e=+
(1 + e=)3
have (i(n) 2, (n(n) 6. If we ridge penalty and assume p n, E 1T
then 70 = Cx = and (n) = 0, and we have
C = = 3x =4
(zz(n) = (1 + 20)
(n = 1280y3 x>
nZL (1 20 lo))
p
C2(n)= 150.
Again, when Cxx unknown to the researcher, can be estimated from data as described in '3. Features' above.
G PROOFS IN THE CASE OF GAUSSIAN FEATURES
The main goal of this section is to present the proofs of Theorem and Theorem 3 assumiig when
2; ~ (O, Σ) with Amax Σ < Cx for some constant C' > 0. After reviewing some preliminary
results that will be used in the proof in Section G.I we present the proof of Theorem in Section G.2 G.2
and the proof of Theorem 3 in Section G.3
G.1 PRELIMINARIES
Our first lemma summarizes some of the basic but extremely fruitful properties of the Gaussian trade-off function defined the main text.
Lemma 6. [Dong et al. (2022) The Gaussian trade off functions satisfy the following properties:
Monotonicity: For any pair 61, 0, E1 S 62 if and only if
fa.e. (ax) 2 fa.ea (a) for all a E [0, 1].
(52)
Closure under suprema: For any collection of (ei)ier C R with index set T
inf fG.e, fG.supier e, for all a E [0,1] iEJ
(53)
Symmetry: For any μl, U2 E Rd and a > 0
T(p2 + NN (p) + ((, Tp)) T(m aN(0, I2), P2 oN((0,T))
(54)
29

---

Published as a conference paper at ICLR 2026
Dimension freeness: For any Ml, E R and o let a l P2ll2. Then T(p1 + (0, 1p), P2 + (N))) = ((N Ne,,
(55)
Intuition and importance. The proof of this lemma is immediate from the explicit description of fa.=(a) = - '11 - a) E) where ((-) is the cdf of a standard Gaussian variable f = ([N ft for all R. It also requires applying the Neyman- Peaassn lemma the likelihood
ratio test Polyanskiy & Wu (025). But, the conclusions that they imply are extremely powerful.
Monotonicity. The monotonicity condition (52) reduces apriori difficult functional comparison between two functions f and at uncountably many points to a comparison of just one parameter e.
Closure under suprema. The closure under suprema property (53 essentially says two very important things. First, it makes easy to identify what the suprema of an apriori arbitrary collection of functions (fi) is (in fact explicitly). Second, the limiting object is function of the same kind: is again a Gaussian trade-off function with a different choice of parameter 8.
Symmetry. The symmetry property (54) (requires Neyman- Deyman-PParson Pearson lemma) is very interesting because the definition of a trade-off function T(P. Q) [ asymmetric in general, between its first and second arguments. But, for pair of shifted isotropic Gaussians, they match because of the spherical symmetry (orthogonal invariance) of the standard Gaussian density in any dimension.
Dimension freeness. The dimension freeness property (55) (requires Neyman-Pearse Pearson lemma) makes the case for Gaussian certifiability in high dimensions stronger than any other notion of certifiability. This is because, almost all the results of classical statistics that are true in low dimensions, fail to hold in high dimensions, because many of the quantities involved in controlling the errors are dimension dependent and blows up when p oc. It is often the case that finding a dimension-free quantity or even inequality that tensorizes' 15 help us resolve high dimensional issues.
The second preliminary work we will be using in our proof about the & difference of the a single step Newton approximation. Define the event F in the following way:
(2
F
max IMIs Sm
( MM
A,lll 2 Ci(D)
(56)
2Avn
Now, Theorem 3.4 of You et al. (0055) in the notation and setting of this paper becomes:
Theorem 7. Zou et al (2025) If the event F is as defined in (56. then
P(F)) S on:
where on, == nngh + 8n 1- + ne p/2 + P.
Based on these two results we can now work on the proofs of our main results.
G.2 PROOF OF THEOREM 2 IN THE GAUSSIAN CASE
Recall that we are supposed show the following with the prescribed choice of Φb On as in (16).
P inf [MiS
T(P (r))(a) 2 fa.e(a)) for all a E [0, [0.1] 2 - Φ. (57)
Let b (0, (independent of everthything else) with = R Then, observe that
Pro A(B T(D (D)))) -,,
P Pun A(3.DM,T(P)) 3 +
(58)
Note that since the distributions Pre and Pun are conditional distributions given the dataset D, we can use the dimension freeness property introduced Lemma [ and conclude that
T( + b, 3 b) = T(N 1), ( B,llle/ 1)),
(59)
We referring dimension free Poincare and Logarithmic Sobolev inequalities of high-dimensional statistics that extremely important in obtaining concentration bounds in high dimensions van Handel (2016).
30

---

Published as a conference paper at ICLR 2026
T( + b. + ((, 1), - -
(60)
Using these two equations we conclude the following chain of equalities, all follow from Lemma
inf min(T((ro, Pun Pir 2 Sa,((a) for all a E [0,
M
(a) inf T(N(O, N(1 B,lll20011) 2 fa,((a) for all a E [0.1]
[IMISm
(6)
IP
TON(O, N, sup M
113M B, fa,e(a) for all a E [0,1]
(c)
113 Bimll//ss
sup M
sup |M
1 3 $
(61)
The above inequalities have been obtained through the following arguments:
Equality (a): To obtain this equality we have used (59) and 660
Equality (b): We used the monotonicity property of (a. mentioned in Lemma 6
Equality (c): We have used the monotonicity property of fa,e(a) of Lemma 6 again.
Equality (d): To obtain equality (d) we have used the fact that R/e.
So, it remains prove the following with on, R prescribed in 2
P
sup
Bumlla S
(62)
LIMIS
Using Theorem 7 establishes this result.
Remark on Gaussianity assumption on features. Observe that our entire computation above was con- ditional on the data D, and therefore do not depend on the Gaussianity of the features at all, except while invoking Theorem 7 to establish (22 We will address this issue later in Section
G.3 PROOF OF THROREM THE GAUSSIAN CASE
Similar to Zou al.
2025
define the following two events:
Es = Ia 31 S v (Av) +
2Cx (v/0 + v)
m m22m + c)
Eg = max [MIsm
1 ( B(m) S
log(n)
p
We use the following result from Zou al. 2025 to establish some bounds on the above events.
Lemma 8. Thenfor for any D FS, we have
Cx p
P(D D) <P
T 3 [00
<
||ا||| 2clog(n)|D
< 2n 2n
Cx 113 B 2v/og((N) + clog(n) D
P(E D) <
Mil s m. x (8 B
/
< 2m
where N m
(*) < ()) < 22mmlog(n)
31

---

Published as a conference paper at ICLR 2026
Define the following two events
47 = (MMM S m,
m,, lay (B (BIM - -BIM + +6
$2v0x (2 + 1
Re, v(2m + c) log(n)
vp)
2R 22p
Eg = [1|b|| v
lyol Cy)n).
8
Define y==
2 + 1
Vr) Ren : (2m + +c) log(n). Note that using the union bound we have
P(B PC b) S e 2m log "p
2 (e IM - BM + b) 2 b)
2e log lo
(63)
By definition of F from 56 under Fe n Es.
(2v2p -1) R.n
1 3 3 bll S 111 - M + ||6|| -
Then, following the proof of Theorem 3.2 in Zou al. (025) we would have
P((E)) F n Eng S 2n
Under (n Va E (0, 1].
(E) w.p.2 1 - (n 1)gh (v) 14n 1-c ne p/2 2e e -(1-1g((2))
1 [a(3 M + b) + (1 - a) ,ul
$ 1 3u + a/20 (3())
(M - BMM +b)l
2v2
polylog, (n) + 2 Cx
+ vD)
R. ((2mm + log(n)
< (olylog2(n),
provided Re, = 0 (mpolylog(r))
so that the second term is O(polylog(n)), So we have
( + + (1 a)
< 1 Cj(n) + 10 la(B b) (1 - B
s (n).
and
ēol - -1, ((((((0 iM + b) + +(1 (1-a) a1 S polyyogg, (m).
Finally we have that, under (nf E,) Ey n FFF.
GED(B M)
Meo(Ba + b) - (o(3
< 1501 (BiM - 3,m + +b]l
(2
1
polylogs (n)22 Cx
R ((2m + c) log(n)
8
vp
(2
1
S polylog, (n)2 Cx
+
R (2m + c) log(n).
8
vp
Plugging in the value of R from Theorem finishes the proof.
32

---

Published as a conference paper at ICLR 2026
Remark on Gaussianity assumption features. Observe that the entire computation above was re- duced to getting the correct orderwise bound on the lablled set of the events Es. Es: E7, Es, E,, Egg above and event F 56 Now, all the labelled events Es, Eg, E,, Eg, Ey, E' involves fresh feature data 2o essentially in its linear component 2g for some vector u. Now, it is well known Vershynin (2018) that for sub-Gaussian vector 2p Sg(0, Σ), the linear projection a/ u has the same (or- derwise) Gaussian tail beahvior as if Zg was (0, 2), since in all these cases v is independent of the fresh sample zo and therefore, the same orderwise bounds of Ét, EG, E7, Es, Li, E% continue to hold except while invoking Theorem to establish 62 or equivalently the tail of 56 We will address this issue next.
H AN EXTENSION OF THE PROOF IN THE CASE OF SUB-GAUSSIAN FEATURES
Given the arguments already presented in the proofs of Theorems 2 and in section G it is
enough to establish that the Theorem Zfu Zou al. (2025) can be extended from ((0 Σ) to
~ (0, )) with the same assumptions on E. We now describe why is this possible. An inspection of the proof of Theorem 7f Zou al. (2025) reveals that their entire proof never uses the following potentially Gaussian facts that Fails when one goes from Gaussian to sub-Gaussian vectors. 1) It never uses orthogonal invariance of the feature vectors in the proof. 2) It never uses Gaussian conditioning technique: (X Y is Gaussian if (X, Y) is jointly Gaussian). Rather it relies on standard concentration bounds collected Lemma B.7 -B.11 11 in the appendix of et al. (025)[arxte version May 12] which can be all be generalized from Gaussian to nub--aassian vectors with exact same (mean, covariance) via a standard computation of its wooeent-generatie functions/ Morevoer, their proofs uses the well-know fact that m by matrix with centered, normalized independent columns has bounded operator norm (and its Wishart version) Vershynin ( [Exercise 4.43), be it Gaussaan Gaussian. More precisely, each of the results in has analogous sub-Gausse Sab-Gassiian extension (with potentially worse constants, which we disregard anyway) and therefore extends verbatim.
I ADDITIONAL NUMERICAL EXPERIMENTS
In this section, we provide results from additional numerical experiments under the ridge penalized r(3) = || logistic regression model E(ylæ: 3), with random features m, ~ N(O, TTIp) and true parameter B3, ~ (0, 4p). penalty parameter À 0.5 in the main paper 5 This further supports our theoretical results. These were not kept in the main paper for lack of space.
1.1 ADDITIONAL PLOTS FOR N=P
UED
6708
Figure 6:
Comparison on unlearned data: mean UED (with SD error bars) on the unlearned set across p (both in log scale) for Laplace (in red) vs. Gaussian noise (in cyan). We set À 0.5.
We plot UED:
the error divergence the unlearned estimator on unlearned data, with p 1255. as we vary s on X axis across 6 different values, and take m = 1,5, 10. The mean UED over 200 replications with standard error bars are presented in Figure 7
Now, we fix = = 0.75 and study the change in UED as the unlearning size m 1, varying m across values spaced equally between and 50 on the logarithmic scale. The mean UED over 200 replications along with standard error bars are presented in Figure
16A A sub-Gaussina vector SG Σ) by definition satisfies Ele"" S edv T Ev Vo E Rp Vershynin 2018).
33

---

Published as a conference paper at ICLR 2026
UED for 1255 and
UED for 1255 and
2.000
Enor on untearned
unleamed
0.250
0.601
0.25
025
Cerlifibllity Parameter
Certifibllll Parameter
UED for = 1255
2,000
Carillabliit Paremeters
Figure 7: Comparison of the difference in negative log likelihood the requested removal set (plotted in log scale) among the retrained estimator, with unlearned estimator with Laplace noise (in red) and Gaussian noise (in eyan). The left, middle, and right figures plot unlearning for removal sizes m 1, m = 5, and m 10 respectively. Here n = p 1255.
UED vs. m for = 500 and == 0.75
UED vs. for p 1500 and 8 0.75
3,00
3.003
Ererr urteamed pel
1.000
0.003
0.300
0.103
0.100
Unleerning
UED vs. m for p 2500 and = 0.75
3.000
0.100
Unleaming size (m)
Figure 8: Comparison of UED (plotted in log scale) across the unlcarning size m (plotted in log scale) for Laplace noise (in red) vs. Gaussian noise (in cyan).
34

---

Published as a conference paper at ICLR 2026
1.2 PLOTS FOR N=P/2
In this subsection we provide results for the analogous experiments in the high dimensional regime where p/2. It is evident from our results that the conclusions remain the same.
First set (meaning of figures 7 and 8). We plot GED as we vary on the axis and n = p/2 on a logarithmic scale, while keeping m fixed at 1, 5, 10 across the three plots. We find the mean GED values across 200 replications decrease with for Gaussian noise, but stay more or less the same for Laplace noise. Results are plotted in Figure 9 and Figure 10
GED vs. p for n = p/2, m =1 and == 0.75
GED vs. p for p/2, m = and = 0.75
Generaltaaton divergenoe
1,000
Gemeralizaton divergeeee
3.000
1.000
0.100
0:300
0.030
0.100
5000
1800
3000
5000
Dimersion
Dimension
GED vs. p for n - p/2, m 10 and Em 0.75
divergenco
8.000
0.000
0.300
1000
Jaop
5000
Dimension
Figure 9: Comparison unlearned estimators on new test data: mean GED (with SD error bars) the dimension p (both in log scale) for Laplace (in red) vs. Gaussian (in cyan). We À 0.2.
Second set (meaning figures 9 and 10). Now, we fix 2n = p = 1255 and examine GED as we vary on the X axis, while varies between m (left), m 5 (middle), and 10 (right). Figure and Figure 12 report boxplots of GED in this setting across 200 Monte Carlo replications.
Conclusions from figures and 10. The performance of Gaussian perturbed estimator becomes in- creasingly closer to that of the ideal retrained estimator as 1 on the X axis. The error for the Laplace perturbed estimator remains above its Gaussian counterpart, uniformly over Similar behavior is reflected on the unlearned subset as well. Results are Figure ITand and Figure 12
Final set (meaning of figures 11 and 12). In final of experiments, parameter ø 0.75, and examine GED as the unlearning size m varies on the X axis, while n, varies between 2n = p 500 (left), 2n p 1500 (middle), and 2n = p 2500 (right). We vary m across 6 values from 5 to 50 equally spaced on a logarithmic scale. Figure 13 plots the average GED values (averaged across 200 replications) against dimension m, transforming both and axes to be on logarithmic scale.
fix the certifiability
Conclusions from figures and 12. For all three plots, as m increases, unlearning accuracy as reflected in GED, worsens for both the estimators. Results are in Figure 1 Figure 14
35

---

Published as a conference paper at ICLR 2026
UED vs. form - p/2, m =1 and =m 0.75
UED vs. p for n p/2. m =5 and Em 0.75
1.000
Eiror Untesmeed
0.100
0.300
0.100
0.030
1889
3000
5050
100
3650
5:00
Dimension
Dimension
UED vs. for p/2, 10 and 0.75
3.000
0.300
500
1000
300g
Song
Dimension
Figure 10: Comparison on unlearned data: mean UED (with 3 SD error bars) on the unlearned set
across p (both log scale) for Laplace (in red) vs. Gaussian noise (in cyan). We set 0.2.
GED vs. :: for 2n = p 1255 and m
GED vs. e for 2n p 1255 and m =
Cenerelizatinn ero divergence
Generaiization divergence
2,000
1.000
060
022
028
Certifabilly Parameter
Cerlifebllly Parameter
GED for 2n = 1255 and 10
diverggneee
2.000
1.000
0.500
Cersiiabiity Parameter
Figure 11: Comparison of GED (plotted in log scale) across different values of e for Laplace noise (in red) Gaussian noise (in cyan). Here 2n 1255. We set 0.2.
36

---

Published as a conference paper at ICLR 2026
UED vs. for 2n 1255 and m
UED for p 12555 and
2/200
2.000
Ener urtearned
unteaindd
0.30
0.000
0.031
022
025
Certifialiity Parameter
Certifibliit Parameter
UED for p 1255 and 10
unicamed
1.000
0.000
0.125
Cantabiliyy Parametors
Figure 12: Comparison of the difference in negative log likelihood on the requested removal set (plotted in log scale) among the retrained estimator, with unlearned estimator with Laplace noise (in red) and Gaussian noise (in eyan). The left, middle, and right figures plot unlearning for removal sizes m 1, m = 5, and m 10 respectively. Here 2n 1255.
GED vs. for p 500 and 0.75
GED vs. = 1500 and = 0.75
Ceneratzation tzalion divergence
1.000
0.30
Unlearning
Unleerning
GED vs. m for 2n 2500 and = 0.75
Generaization
0.00
Unleaming szee (m)
Figure 13: Comparison of mean GED (with 3 SD error bars) across the unlearning size m (both in log scale) for Laplace noise (in red) vs. Gaussian noise (in eyan). We set X 0.2.
37

---

Published as a conference paper at ICLR 2026
UED vs. m for 2n 500 and = 0.75
UED vs. for 2n p 1500 and = 0.75
3.000
3.000
Eiror on uneamee est
0.000
0.000
0.103
Unlearning size (m)
Unlearning size (m)
UED vs. for 2n
2500 and = 0.75
3.000
unkamet
4.000
0.000
100
Unisaming s20 (m)
Figure 14: Comparison of UED (plotted in log scale) across the unlearning size m (plotted in log scale) for Laplace noise (in red) vs. Gaussian noise (in cyan).
38


Reviews:
[{"review_id": "5BoXXnyC4r", "reviewer": "Reviewer_3wiW", "summary": "This paper introduces **$(\\phi, \\epsilon)$-Gaussian certifiability**, a new privacy-certification framework for high-dimensional settings ($p \\approx n$). It shows that a single Newton step with Gaussian noise can achieve certified unlearning while maintaining model accuracy. The work improves upon prior high-dimensional unlearning methods by reducing the number of required Newton steps and provides empirical validation on synthetic linear models, demonstrating the advantages of Gaussian noise for generalization and unlearning metrics.", "questions": "I would appreciate it if you could also answer the following questions:\n\nQ1. **On the high-dimensional regime**. From what I understand, your theoretical framework is developed under the assumption that the number of features $p$ and the number of samples $n$ grow proportionally ($p \\sim n$), which allows the use of Random Matrix Theory results. While the framework is elegant in this setting, it is unclear how well it could extend to ultra high-dimensional regimes where $p \\gg n$, such as in modern neural networks. Do you think the current framework could provide a solid base for such settings, or would substantial modifications be needed?\n\nQ2. **On the deletion set structure**. Does you framework for more sophisticated/structured unlearning scenarios such as class or concept unlearning? \n\nQ3. **On the choice of $\\phi$ (tolerance):** How sensitive are the certified unlearning bounds to the tolerance parameter $\\phi_n$? Is there a principled way to choose $\\phi_n$ in practice, and how might different choices affect empirical performance or computational stability?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "-**Problem Significance:** This is a timely work in the important field of machine unlearning, addressing key limitations of existing methods. It does so by introducing a canonical privacy notion tailored to high-dimensional settings, bridging differential-privacy hypothesis testing and machine unlearning.\n\n-**Novelty and Theoretical Elegance:** The paper introduces $(\\phi, \\epsilon)$-Gaussian certifiability and proves that a single Newton step suffices for certified unlearning. This provides a rigorous, theoretically sound approach that balances privacy guarantees and model accuracy.\n\n-**Support for Multiple Deletions:** The method can handle multiple deletion requests simultaneously, as long as the total deletion size remains within the theoretical bound. This feature is valuable for practical batch-deletion scenarios.", "weaknesses": "-**On deletion size**. From what I understand, the certified unlearning guarantees hold only for relatively small deletion sets ($m = o(n^{1/4-\\alpha})$), which limits applicability when larger batches of records need to be removed. This is a clear theoretical limitation of the method.\n\n-**On noise-scale calibration**. While the paper provides a theoretical formula for Gaussian noise, it involves unspecified constants and poly-logarithmic factors, making practical calibration challenging. Implementing the noise correctly in real-world scenarios may be difficult.\n\n-**On model scope and empirical validation**. Experiments are restricted to linear ridge-regularized ERM models with Gaussian/sub-Gaussian features on synthetic datasets. Non-convex models, deeper architectures, and real-world datasets are not evaluated. Even though this is outside the scope and assumptions of the paper, I think it would be interesting to see a simple extension, such as a two-layer fully connected network on MNIST, with results compared against the frequently cited papers by Sekhari et al. and Guo et al.\n\n-**On scalability of Newton method**. The method requires inversion of the Hessian ($O(p^3)$), which may be difficult to compute in high-dimensional settings, as often encountered in deep neural networks. This can be computationally and memory intensive, and may also be numerically unstable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9EXvZ0MfIy", "reviewer": "Reviewer_xe5g", "summary": "This paper tackles the problem of certified machine unlearning in high-dimensional settings where the number of parameters p is comparable to the sample size n. It introduces a new privacy notion called (phi, epsilon)-Gaussian certifiability, which is argued to be the canonical and optimal framework for high dimensions. The main theoretical result shows that a single step of Newton's method, followed by calibrated Gaussian noise, is sufficient to achieve both this strong privacy guarantee and maintain model accuracy. This finding directly contrasts with the prior state-of-the-art analysis by Zou et al. (2025), which concluded that at least two Newton steps were necessary.", "questions": "n/a", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper's primary strength is its novel and theoretically sound analysis of unlearning in the challenging high-dimensional proportional regime (p ~ n). The introduction of varepsilon-Gaussian certifiability is well-motivated, leveraging a hypothesis testing perspective and properties of high-dimensional data to create a more natural and tighter privacy notion than previous frameworks like varepsilon-certifiability. The core result—that only one noisy Newton step is needed—is both surprising and significant, as it suggests prior analyses were suboptimal due to an incompatible privacy definition, not a fundamental algorithmic limitation. The theoretical claims are strongly supported by comprehensive experiments showing the clear superiority of the Gaussian mechanism over the Laplace mechanism from Zou et al. (2025).", "weaknesses": "The analysis relies on specific technical assumptions, such as the data features being sub-Gaussian and the loss functions being convex. While common in high-dimensional statistics, the practical implications for highly non-convex models (like large neural networks) remain an open and important question. Furthermore, the requirement for Hessian computation in the Newton step, though theoretically elegant, could be a scalability bottleneck for extremely large-scale models. The paper could also benefit from a more detailed discussion on the potential trade-offs or limitations of the Gaussian certifiability notion itself, beyond its superiority over prior work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ixlMa7rDu2", "reviewer": "Reviewer_qmUk", "summary": "This paper introduces ε-Gaussian certifiability, a novel and robust framework tailored for high-dimensional machine unlearning. The authors demonstrate that a single noisy Newton step suffices to achieve both privacy and statistical accuracy under this new notion, contrasting with prior work that required at least two steps. Theoretical results are supported by convincing simulations.", "questions": "Could you provide experiments with larger values of $p$ (e.g., 10K or 100K)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper proposes a novel, high-dimensional–friendly notion of certified unlearning (ε-Gaussian certifiability) that tightly captures Gaussian noise mechanisms and subsumes prior privacy definitions.\n2. The theoretical analysis is rigorous. The authors theoretically prove that a single Gaussian-Newton step simultaneously achieves (φ,ε)-GPAR privacy and vanishing generalization error in the proportional p∼n regime under relaxed assumptions.", "weaknesses": "1. Some writing issues:\n   - In the Abstract, the notation $ p \\ll n $ should be clarified by specifying what $ p $ and $ n $ represent, respectively.\n   - In the Introduction section, the reviewers suggests first discussing the shortcomings or failures of existing works before presenting the performance and contributions of the proposed method.\n   -  Using boldface followed by a colon for the first sentence of every paragraph throughout the paper harms the logical flow and readability, making it less reader-friendly.\n2. Some typos:\n   - $\\mathcal D$ shoud be $\\mathcal D_{\\backslash {\\mathcal M}}$ on Line 188.\n   - The symbols $\\epsilon$ and $\\delta$ are not defined in Eq.(8).\n   - $ p\\uparrow \\infty $ on Line 254.\n   - The symbol $ r $ is reused in Eq.(16). Earlier in the text, it denotes the regularization term.\n3. The paper lacks discussion on online unlearning (i.e., handling continuous unlearning requests).\n4. The reviewers suggets that using a table to compare the results of this work with those of existing methods would be clearer and more effective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E6PSSs8Dys", "reviewer": "Reviewer_WvFT", "summary": "The paper introduces ε-Gaussian certifiability (GPAR)—a new theoretical notion for analyzing machine unlearning in high-dimensional regimes (p ~ n). It reformulates unlearning guarantees via hypothesis testing and Gaussian trade-off functions, showing that a single Newton step with Gaussian noise suffices to ensure both privacy and accuracy. This contrasts with prior work (notably Zou et al., 2025), which required at least two steps under ε-certifiability. The authors also provide proofs of convergence, theoretical bounds for Generalization Error Divergence (GED), and simulation results validating the high-dimensional behavior.", "questions": "1. How sensitive is the ε-GPAR bound to mis-specification of noise variance? Could small deviations in σ break certifiability guarantees?\n\n2. The theorems assume a single batch of deletions of size m. What happens if deletions arrive sequentially? Is the GED bound sub-additive, or does error accumulate over multiple unlearning rounds?\n\n3. The constants C₁(n), C₂(n) are said to be polylog(n), but they are never specified. How large are they empirically, and do they affect practical implementability?\n\n4. The framework assumes exact access to the Hessian—what happens when it is estimated or approximated in large-scale models? For large $p$, forming and inverting $p \\times p$ Hessians is infeasible. Can similar theoretical results be shown for quasi-Newton or stochastic approximations?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Introducing ε-Gaussian certifiability as a canonical high-dimensional analogue to ε-certifiability is a meaningful contribution, bridging DP-inspired hypothesis testing with unlearning theory.\n\n2.  The paper convincingly argues that existing assumptions—especially Ω(1) strong convexity and O(1) smoothness—fail in proportional regimes, motivating a new approach.\n\n3. The contrast with Allouah et al. (2025), Sekhari et al. (2021), and Zou et al. (2025) is detailed—highlighting where previous frameworks break down.", "weaknesses": "1. Experiments are confined to synthetic logistic/ridge regression under controlled Gaussian features. There are no tests on real or non-linear models, limiting practical validation.\n\n2.  While the framework is theoretically extendable, the assumptions (convexity, separability, sub-Gaussian features) exclude modern deep models. Discussion on extending to non-convex objectives (e.g., neural networks) remains speculative.\n\n3. Although one-step Newton is theoretically efficient, computational overhead in large-scale settings (Hessian computation, inversion) is not discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)