{"id":"a53e6a20-fe32-46ff-b785-e5fcce41b2b9","arxiv_id":"2507.15280","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"SAFE performs streaming machine unlearning with one gradient step per deletion request using only deleted data and per-class Gaussian statistics, claiming an O(sqrt(T)+V_T) regret bound.","lead":"This paper introduces SAFE, an algorithm for erasing data from trained models when deletion requests arrive one at a time, without re-accessing the original training data. It models unlearning as a distribution shift and claims a regret bound of O(sqrt(T)+V_T), but the proof has gaps.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed-variance Gaussian noise forces linear unlearning regret, so the claimed O(sqrt(T)+V_T) bound is false even for convex quadratic risks.","rationale":"The paper's central claim is the O(sqrt(T)+V_T) dynamic regret bound for streaming unlearning. For that claim to hold, the per-round expected excess risk must be summable to sublinear regret even though the algorithm injects independent Gaussian noise at every round. The stated noise variance is a constant determined by the desired (epsilon, delta) guarantee, independent of T. In any strongly convex loss, independent noise of fixed variance contributes a fixed positive excess risk per round, giving Theta(T) cumulative regret. A one-dimensional quadratic example makes this immediate and does not require any non-convexity, smoothness, or data-access assumptions. The proof's treatment of the noise term B_t is therefore the load-bearing weak point: it is discarded into a crude W^2 bound, but that cannot remove the T*phi term. This is a correctness risk, not a disagreement with consensus. I agree with the reader's overall rejection, but the reader's stated weakest assumption focused on non-convex gradient inequalities; the noise-variance obstruction is even more basic because it invalidates the claimed bound for convex losses too. The experimental results and the streaming-unlearning framing are valuable, but the theoretical guarantee is the advertised contribution and it is not supported as written.","tokens_in":25654,"tokens_out":12509,"duration_ms":151918,"concrete_test":"Run the following check on Theorem 2/3: choose R_t(w) = w^2 with w*_t = 0 for all t, w0 = 1, W >= 2, gamma = sqrt(W)/(K sqrt(T)), and noise variance phi = W*sqrt(2 ln(1.25/delta))/epsilon as specified. Algorithm 1 then produces w_t = 1 - gamma - b_t with b_t ~ N(0, phi). Direct calculation gives E[sum_t (R_t(w_t) - R_t(w*_t))] = T[(1 - gamma)^2 + phi]. For any fixed epsilon, delta, this is Theta(T), while V_T = 0. Ask the authors to identify the line in the proof where the T*phi contribution is canceled; no such cancellation exists in the current Appendix A.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised result is the regret bound in Theorem 2/3. Even granting convexity, smoothness, and the reset-to-w0 update, Theorem 2(iii) prescribes a Gaussian perturbation b_t ~ N(0, phi) with phi = W*sqrt(2 ln(1.25/delta))/epsilon, a constant independent of T. For any risk that is strongly convex near the comparator, e.g. the 1D quadratic R_t(w) = (w - w*_t)^2, the excess risk at the algorithm's output w_t = w0 - gamma*g_t/||g_t|| - b_t contains an irreducible additive term phi coming from the independent noise. Concretely, if w0 = 1 and w*_t = 0 for all t, then E[R_t(w_t) - R_t(w*_t)] = (1 - gamma)^2 + phi. Summing over T gives a Theta(T) contribution, while V_T = 0. Thus the claimed E[sum_t (R_t(w_t)-R_t(w*_t))] <= O(sqrt(T)+V_T) cannot hold as stated. The proof in Appendix A.3 hides this by absorbing B_t, which contains ||b_t - b_{t-1}||^2, into a constant W^2 bound without exhibiting the T*phi term; that step is not valid. This is not a subtle non-convexity gap: it breaks the theorem in the simplest convex quadratic setting, so the central claim is false as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formulates machine unlearning with sequentially arriving deletion requests as a streaming problem, models the post-deletion retrained model as a distribution shift from the original model, and proposes SAFE. SAFE stores no original training set: it keeps a precomputed gradient at the initial parameters, recursively updates deletion-set gradients and per-class Gaussian statistics in a low-dimensional projection, and at each round makes a single normalized gradient step from the initial parameters with added Gaussian noise. The authors claim a surrogate risk approximation (Theorem 1), a per-step O(√T) error and cumulative O(√T + V_T) unlearning regret under only bounded gradients and without convexity (Theorems 2 and 3), and an (ε,δ)-approximate unlearning guarantee (Theorem 4). Experiments on MNIST, Fashion, CIFAR10, TinyImagenet, SST-2, and CoverType compare SAFE with Retrain, Unroll, CaMU, Lcode, and Desc on accuracy, forgetting accuracy, test accuracy, MIA, and runtime.","tokens_in":26042,"tokens_out":10200,"duration_ms":107423,"significance":"The problem is timely and the empirical evaluation is unusually broad for an unlearning paper: it includes ablations, varying numbers of rounds and deletion sizes, class-targeted streaming unlearning, tabular and text data, and privacy-attack metrics, and the authors provide code. If the theory were correct, the paper would be the first to give a dynamic-regret guarantee for data-free streaming unlearning, which would be an important advance. However, the theoretical core is not sound: the advertised cumulative bound is contradicted by a simple convex quadratic example, and the non-convex claim rests on an unjustified descent-type inequality. The paper's demonstrated value is therefore empirical, not theoretical, and cannot support the central claims as written.","major_comments":[{"comment":"The claimed cumulative bound O(√T + V_T) is false for the algorithm as stated because the Gaussian perturbation has constant variance. Take the one-dimensional quadratic risk R_t(w) = (w − w*_t)^2 with w_0 = 1 and w*_t = 0 for all t, so V_T = 0. The normalized gradient of R_t at w_0 is +1, hence w_t = 1 − γ − b_t and E[R_t(w_t) − R_t(w*_t)] = (1 − γ)^2 + φ_t, with φ_t = W√(2 ln(1.25/δ))/ε independent of t. Summing over T gives a Θ(T) term, not O(√T). The proof in Appendix A.3 hides this by absorbing the term B_t, which contains E||b_t − b_{t−1}||^2 = 2d φ_t (or d times this, depending on dimension convention), into constants W^2 and dropping it; this step is not valid. This counterexample is in the simplest convex quadratic setting, so the error is not a subtle non-convexity issue.","section":"Section 3.3, Theorem 2; Algorithm 1, step 9; Appendix A.3"},{"comment":"The proof bounds the per-step function error by E|R_t(w_t) − R_t(w*_t)| ≤ U E|(∇_{t+1})^T(w_t − w*_t)|. This inequality is a convexity-based descent inequality (or requires an unstated smoothness/descent lemma); it is not a consequence of the stated assumption ∥∇R_t(w)∥ ≤ U. Consequently, the advertised claim that the O(√T + V_T) bound holds 'without the strong restriction of convex loss function' is not proven. Since the experiments are on non-convex neural networks, this is a load-bearing gap, not a cosmetic one.","section":"Appendix A.3, proof of Theorem 2; main text Section 3.3"},{"comment":"Theorem 1 assumes p0(y|x) = f(x; w0), an idealized condition that is not satisfied by trained neural networks, and the proof silently uses additional conditions: the total deleted size must satisfy sqrt(|D_t|) ≫ sum_i |F_i| and sum_i |F_i| < |D_t|. These conditions do not appear in the theorem statement. Furthermore, the derivation of the bound for |R~_t(w) − R_t(w)| jumps from a Berry-Esseen error O(|D_t|^{−1/2}) for the estimated conditional density to the displayed bound C∑|F_i|/|D_t|^{3/2} without justifying the intermediate inequality involving log ratios. The theorem is therefore not established as stated.","section":"Section 3.3, Theorem 1; Appendix A.3"},{"comment":"Theorem 4 asserts that each step satisfies (ε,δ)-approximate unlearning, but its proof is only a citation to the Gaussian mechanism for differential privacy. The definition requires closeness between the output distribution of the unlearning algorithm and the distribution of the retrained model A(D_t), not a differential-privacy guarantee of the gradient update. No coupling, sensitivity analysis, or explicit construction of the two distributions is provided, so the (ε,δ) claim is unsupported. Independently, the fixed-variance noise needed for that claim is precisely what forces the linear regret in Major Comment 1, so the two parts of the theorem cannot both hold as stated.","section":"Theorem 4 and Definition 1"}],"minor_comments":[{"comment":"The notation table describes d_KL as 'cosine similarity loss,' but in the main text it is the Kullback-Leibler divergence; the table entry should be corrected.","section":"Table 3"},{"comment":"The discussion of Figure 1 refers to the baseline 'Descent,' while the method is called 'Desc' throughout the rest of the paper; the naming should be made consistent.","section":"Section 4.2"},{"comment":"The heading 'Theoritical Proof' is misspelled, and Theorems 2, 3, and 4 restate the three items of the main-text Theorem 2 as separate theorems; unifying the presentation would improve readability.","section":"Appendix A.3"},{"comment":"Theorem 2(i) states a per-step bound of O(√T), which grows with the horizon T; as written this bound is vacuous for any bounded risk and should be clarified as a worst-case-horizon statement rather than a rate in t.","section":"Section 3.3"}],"recommendation":"reject","confidential_remarks":"I recommend rejection because the main theorem is false as stated and the contradiction is elementary; a revised paper that restricts claims to the empirical method or replaces the theory would require major restructuring. If the authors resubmit, the editor may wish to verify the novelty claim about being 'the first' streaming unlearning regret bound against [7,22,34,39,57], and to request a full proof of the (ε,δ)-approximate unlearning claim rather than a citation to the Gaussian mechanism."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about arXiv:2507.15280. First, the algorithm is genuinely novel: framing streaming unlearning as a distribution shift, estimating per-class Gaussian density ratios in a random projection space, and doing single-step updates from the original model without touching the training data is a fresh construction. The empirical study is broad and plausible, with strong time-efficiency numbers and results that often track the retrained model. Second, the central theoretical claim does not hold. The proof of Theorem 2 uses a step that is valid only under convexity or Lipschitz smoothness to upper bound the risk gap by a gradient inner product, but the paper only assumes bounded gradients and explicitly claims no convexity. That is a real gap for non-convex neural networks.\n\nThe more decisive problem is the perturbation. The variance phi is constant in T, so even in a 1D quadratic with a stationary optimum, the independent noise b_t contributes an additive phi to the per-round excess risk. Summing over T gives Theta(T), while V_T = 0. The proof hides this by absorbing the B_t terms into constants without exhibiting the T*phi contribution. So the theorem is false as stated, not merely unproven. The stress-test counterexample is correct, and it breaks the paper in the simplest possible setting. Theorem 1 also assumes p0(y|x) = f(x; w0) exactly, which is highly idealized. The appendix has smaller but annoying inconsistencies: the main text says lambda=1000/120000, while Appendix B.2 says 2000/6000/100000/1000000; K for TinyImageNet is 4 in B.2 and 2.5 in B.5. These are minor, but they hurt reproducibility.\n\nWhat is good: the problem is real, the distribution-shift formalization is worth thinking about, and the algorithm has practical promise. The paper deserves a serious referee because the flaws are specific and potentially fixable, e.g., a variance schedule that decays with T, explicit smoothness assumptions, and a corrected regret proof. But as submitted, the main contribution is not sound. My recommendation: send it to review, expect heavy revision, and do not let the current theorem through without a rigorous derivation or a retraction of the non-convex claim.","headline":"The SAFE algorithm is a creative take on streaming unlearning, but the advertised O(sqrt(T)+V_T) regret bound is false as stated; the fixed-variance Gaussian perturbation alone forces linear regret even for convex quadratics.","tokens_in":26503,"tokens_out":2575,"would_cite":false,"duration_ms":30406,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that sequential deletion requests can be handled as a distribution-shift estimation problem, and that the resulting SAFE algorithm achieves an O(√T + V_T) unlearning regret bound without convexity or access to the…","keywords":["machine unlearning","streaming forgetting","dynamic regret","distribution shift","data deletion","approximate unlearning","online learning","Gaussian density ratio"],"falsifier":"Run SAFE on a non-convex network over $T$ rounds with the stated learning rate and measure the average per-round risk gap by retraining a reference model each round; if the gap does not remain $O(\\sqrt{T})$ for a deletion sequence with $V_T=0$, or if the total regret grows superlinearly, then the unstated convexity or smoothness step is doing the work.","tokens_in":25464,"feed_emoji":"🧹","tokens_out":8250,"duration_ms":87754,"temperature":0.7,"pith_summary":"The paper addresses machine unlearning when deletion requests arrive one at a time over a long sequence, rather than as one batch. It proposes SAFE, which treats each round of forgetting as a distribution-shift problem: the unknown retrained model is approximated by reweighting the original model's predictions with label ratios and class-conditional Gaussian density ratios estimated on randomly projected data. All updates are single gradient steps from the original model, so the original training set is never accessed again after initialization. The paper's central claim is that this procedure has unlearning regret $O(\\sqrt{T} + V_T)$ over $T$ requests, where $V_T$ measures how much the ideal retrained model drifts, and that this holds without assuming the loss is convex. If correct, this would make continuous data deletion practical for deep models at roughly constant per-request cost.","feed_headline":"SAFE forgets streamed data with O(√T) regret","feed_subtitle":"One gradient step per deletion request approximates the retrained model, keeping accuracy and cutting cost.","key_machinery":"The central object is the streaming risk estimator $R_t(w)$ from Eq. (10)/(13): the loss on remaining data plus a KL-divergence penalty pulling the model's predictions toward the estimated unlearned target. Its optimization is carried by the posterior-shift approximation $q_t^{(y)}(x) = \\frac{n_t(y)}{n_0(y)} \\frac{|D_0|}{|D_t|} \\frac{\\mathcal{N}(z\\mid \\mu_t^{(y)}, \\Sigma_t^{(y)})}{\\mathcal{N}(z\\mid \\mu_0^{(y)}, \\Sigma_0^{(y)})}$, which uses Bayes' theorem to express the class-conditional distribution after deletion as a ratio of Gaussian densities in a random low-dimensional projection. This ratio turns the unobservable retrained model into a computable reweighting of the original model's outputs, enabling single-step gradient updates from $w_0$ and recursive mean/covariance updates (Eqs. 22 and 23) that never revisit $D_0$. The Gaussian perturbation $b_t$ is the mechanism that yields the $(\\epsilon,\\delta)$-approximate unlearning guarantee via the same argument as the Gaussian mechanism in differential privacy.","core_discovery":"On the paper's own terms, SAFE is the first streaming unlearning method with a dynamic regret guarantee that does not require convexity or access to the original training data. The key move is replacing the per-step ideal model $w^*_t$ (the model retrained on $D_t$) by an explicit reweighting of the original model's predictive distribution: $f(x; w^*_t) \\approx q_t^{(y)}(x) f(x; w_0)$, with $q_t^{(y)}(x)$ equal to the label proportion ratio times the ratio of two Gaussian densities fitted to randomly projected class-conditional features. The risk estimator $R_t(w)$ combines a retention term on remaining data and a forgetting term measuring KL divergence to this reweighted target; both can be updated recursively from the deletion sets alone. The main theorem states that under bounded gradients and bounded parameters, with learning rate $\\gamma = \\sqrt{W}/(K\\sqrt{T})$ and Gaussian perturbation of variance $\\phi_t$, the expected per-step gap $\\mathbb{E}[R_t(w_t) - R_t(w^*_t)]$ is $O(\\sqrt{T})$ and the accumulated regret over $T$ rounds is $O(\\sqrt{T} + V_T)$, with $V_T = \\sum_t \\|w^*_t - w^*_{t-1}\\|_2$. The paper also claims each step satisfies $(\\epsilon,\\delta)$-approximate unlearning.","pith_inferences":["If the regret bound survives scrutiny, the same distribution-shift estimator could be adapted to incremental learning, where data arrives rather than being deleted, by reversing the sign of the recursive updates.","An implicit testable consequence is that SAFE's regret degrades gracefully only when the retrained models change slowly, so deletion orders that target rare classes should be harder than random-subset deletions because they move the class-conditional Gaussians more.","The Gaussianity of the random projection is checked empirically with a multivariate normality test; a stress test on a dataset whose latent projections are visibly non-Gaussian would show whether the approximation error bound in the first theorem is what actually drives performance.","The paper does not compare against storing a small coreset of remaining data; a practical extension would test whether fitting the reweighting term with a coreset instead of parametric Gaussians keeps the same regret with fewer distributional assumptions."],"forward_implications":["Each deletion request costs computation proportional to $|F_t|$, not to the size of the original dataset, after one initial gradient computation.","The original training data does not need to be stored or accessed during unlearning; only the deletion sets and per-class Gaussian statistics are kept.","Across $T$ streaming requests, the accumulated quality gap versus retraining grows like $O(\\sqrt{T} + V_T)$, so long unlearning sequences remain under control when the ideal model drifts slowly.","Every round is $(\\epsilon,\\delta)$-approximately unlearned, giving a formal privacy-like guarantee per deletion step.","On the evaluated image, text, and tabular benchmarks, the method matches or beats batch and streaming baselines on remaining, forgetting, and test accuracy, and is the fastest on the image datasets."],"supporting_citations":[{"why":"Supplies the density-ratio modeling view that motivates approximating the posterior shift by label and class-conditional ratios.","marker":"[41]"},{"why":"Provides the direct importance-estimation technique adapted to estimate the reweighting function $q_t^{(y)}(x)$.","marker":"[46]"},{"why":"Justifies projecting data into a latent space that approximates a Gaussian, making the density ratio computable.","marker":"[28]"},{"why":"Supports the empirical claim that random linear projections of data tend toward Gaussian or maximal-entropy distributions.","marker":"[17]"},{"why":"Gives the incremental multivariate Gaussian estimation that underlies the recursive mean and covariance updates.","marker":"[11]"},{"why":"Provides the incremental weighted mean and variance formulas used to update Gaussian statistics under deletion.","marker":"[16]"},{"why":"Is the non-convex online-learning dynamic regret result that SAFE's $O(\\sqrt{T}+V_T)$ bound is compared against.","marker":"[18]"},{"why":"Defines $(\\epsilon,\\delta)$-approximate unlearning, the notion used in Definition 1 and Theorem 2(iii).","marker":"[21]"},{"why":"Is the perturbed gradient descent baseline that SAFE must beat in the streaming setting.","marker":"[39]"},{"why":"Supplies the Gaussian mechanism argument used in the proof of the $(\\epsilon,\\delta)$-approximate unlearning guarantee.","marker":"[14]"}],"fun_headline_variants":["SAFE: streaming unlearning with O(√T) regret","No convexity needed for streaming unlearning regret","Forget streamed data in one step, provably","Streaming unlearning without retraining or data replay"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the per-step risk gap can be bounded by an inner product of the gradient with the parameter error—an inequality the proof uses without stating and that only holds for convex or smooth losses—together with the assumption that the original model already equals the true class-conditional distribution.","fun_headline_variants_meta":{"raw":{"variants":["SAFE: streaming unlearning with O(√T) regret","No convexity needed for streaming unlearning regret","Forget streamed data in one step, provably","Streaming unlearning without retraining or data replay"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000263,"raw_usage":{"total_tokens":1649,"prompt_tokens":1044,"completion_tokens":605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":539}},"tokens_in":660,"tokens_out":605,"duration_ms":6990,"temperature":1.0,"reasoning_tokens":539,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:36:09.510557+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SAFE on a non-convex network over $T$ rounds with the stated learning rate and measure the average per-round risk gap by retraining a reference model each round; if the gap does not remain $O(\\sqrt{T})$ for a deletion sequence with $V_T=0$, or if the total regret grows superlinearly, then the unstated convexity or smoothness step is doing the work.","supporting_citations":[{"cited_title":"Quiñonero-Candela, M","cited_arxiv_id":null,"evidence_quote":"Supplies the density-ratio modeling view that motivates approximating the posterior shift by label and class-conditional ratios."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the empirical claim that random linear projections of data tend toward Gaussian or maximal-entropy distributions."},{"cited_title":"Dasgupta and D","cited_arxiv_id":null,"evidence_quote":"Gives the incremental multivariate Gaussian estimation that underlies the recursive mean and covariance updates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the incremental weighted mean and variance formulas used to update Gaussian statistics under deletion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the non-convex online-learning dynamic regret result that SAFE's $O(\\sqrt{T}+V_T)$ bound is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines $(\\epsilon,\\delta)$-approximate unlearning, the notion used in Definition 1 and Theorem 2(iii)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Is the perturbed gradient descent baseline that SAFE must beat in the streaming setting."},{"cited_title":"Dwork and A","cited_arxiv_id":null,"evidence_quote":"Supplies the Gaussian mechanism argument used in the proof of the $(\\epsilon,\\delta)$-approximate unlearning guarantee."}],"review_version":1}