{"id":"7ca12dbd-5766-4070-aaee-acf1f023adb5","arxiv_id":"2505.08557","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Two OGD-based algorithms provably make deleted points statistically invisible in future outputs while adding only modest regret overhead.","lead":"This paper introduces the problem of online machine unlearning, where a model keeps learning from a stream while also deleting the influence of certain data points. It presents two algorithms with formal guarantees that forgetting can happen without significantly harming learning quality.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 2 only requires indistinguishability for intervals between consecutive deletions (i=1,...,k−1), so no constraint is imposed after the final deletion; for k=1 the definition is vacuous, which undermines the central 'protected forever' guarantee.","rationale":"The reader's weakest assumption was Assumption 2, which limits the active algorithm's O(log T) regret bound. That is a real concern but it is restricted to Section 4 and is explicitly acknowledged as an assumption. The more load-bearing issue is the formal definition of the main guarantee: Definition 2's quantifier stops at k−1, so the 'indistinguishable forever' promise is not actually stated for the final deletion interval, and for k=1 it is vacuous. I checked the proof of Theorem 1 to see whether the intended argument covers the final interval: the CNI analysis bounds divergence at each deletion time and uses post-processing to extend to the following interval, but the definition itself never asks for that extension after the last deletion. This affects every theorem that claims an (α,αε)-OLU guarantee, including the passive algorithm that does not rely on Assumption 2. Because the repair is straightforward—extend the quantifier to i=k and handle the final interval—the appropriate verdict remains conditional rather than reject. The reader's Assumption 2 concern is orthogonal and I do not fold it into this verdict.","tokens_in":30773,"tokens_out":7448,"duration_ms":71899,"concrete_test":"Set k=1 in Definition 2 and check whether the condition imposes any constraint on the output sequence after the single deletion at τ[1]; if the quantifier set 1≤i≤k−1 is empty, the definition is vacuous. Then check whether Theorem 1's proof explicitly bounds Dα over [τ[1],T]; if it does not, amend Definition 2 to include i=k with τ[k+1]=T (or T+1) and re-verify the post-processing argument for the final interval.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central formal guarantee is Definition 2. As written, the quantifier is ∀ i=1,...,k−1 and the compared outputs are restricted to [τ[i], τ[i+1]−1]. Consequently, the interval after the last deletion, [τ[k], T], is never covered, and for a single deletion request (k=1) the condition set is empty, making every algorithm trivially an (α,ε)-OLU. This is not a cosmetic issue: Theorems 1–6 all claim unlearning guarantees, and the abstract's promise is that 'after a data point is unlearned, all subsequent outputs must be statistically indistinguishable' from retraining without it. The proof of Theorem 1 bounds the Rényi divergence at each deletion time and then appeals to post-processing to extend to intervals (τ[i], τ[i+1]); however, the same post-processing extension to the final interval [τ[k], T] is not included in Definition 2. If the intended definition was ∀ i=1,...,k with τ[k+1]=T (or T+1), the fix is local and likely compatible with the proof; but as printed, the formal statement of the main guarantee is incomplete.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes online learning-unlearning (OLU), in which an online learner must, upon deletion requests, make future outputs statistically indistinguishable from a model trained without the deleted functions. It introduces an (α,ε)-OLU definition based on Rényi divergence, a passive OLU algorithm that injects Gaussian noise at deletion times under Markovian/contractive/sensitivity conditions on the base learner, and an active OLU algorithm based on descent-to-delete. The main theoretical claims are: passive OGD satisfies the unlearning guarantee and achieves regret O(log T + ...) for strongly convex and O(√T + ...) for convex losses; a constant step size gives uniform O(k^{1.1}√T/√ε) regret; and active OLU achieves O(log T + ...) regret under an additional assumption. The paper also compares with DP-online and retraining baselines.","tokens_in":31075,"tokens_out":24741,"duration_ms":233780,"significance":"If the results are correct, the paper makes a useful contribution by showing that unlearning can be layered onto OGD with only additive regret overhead. The use of contractive noise iteration to analyze passive unlearning is well matched to the problem, and the regret decompositions are mostly explicit. The main strengths are the clean separation of conditions C1–C3 and the explicitly calibrated noise schedule. However, the formal guarantee as written omits the interval after the final deletion, the comparison process used in the proof is not the standard noiseless retraining, and the active regret bound rests on a very restrictive assumption with an unproved step in Appendix C. These issues affect the central claims and need to be resolved.","major_comments":[{"comment":"The quantifier in Definition 2 is over i=1,...,k−1 and the compared output sequences are restricted to [τ[i], τ[i+1]−1]. As a result, the interval after the last deletion, [τ[k], T], is not covered, and for k=1 the condition set is empty, making every algorithm trivially (α,ε)-OLU. This contradicts the abstract's promise that all subsequent outputs are protected and the paragraph after the definition claiming a deleted point remains protected forever. The fix is local—set τ[k+1]=T (or T+1) and quantify i=1,...,k—and the post-processing argument in the proof of Theorem 1 appears to extend to the final interval, but as printed the central formal guarantee is incomplete and should be corrected before the theorems are evaluated.","section":"Section 2.2, Definition 2 (Eq. (4))"},{"comment":"In Definition 2 the reference run AR(S_{τ[i+1]-1}\\S^U_i, ∅, [T]_{1:i}) is passed the same deletion-time set [T]_{1:i} even though it deletes nothing, and Algorithm 1 injects noise at every t∈T regardless of whether a deletion is performed. The proof of Theorem 1 compares two CNIs with the same noise distribution at the deletion times, so the baseline is not the standard noiseless retrained model but a model that receives the same calibrated noise at the same times. Because the noise scale in Eq. (6) is set from Δ_{u[i]}, the baseline distribution may depend on the deleted point unless the Δ_t are explicitly public, data-independent worst-case bounds. The paper should state this non-standard baseline explicitly and clarify the status of Δ_{1:T}; otherwise the unlearning guarantee is weaker than the retraining-without-the-deleted-point interpretation in the abstract.","section":"Definition 2 and Appendix B.1 (proof of Theorem 1)"},{"comment":"Assumption 2 defines z⋆_i = argmin ∑_{t=1}^{τ[i]} f_t(z), i.e., the ERM of all functions up to τ[i] with no deletions, whereas the regret proof bounds quantities involving z⋆_{i,0}, the ERM after removing the deleted functions. In the proof of Eq. (54), the paper asserts without proof that by Assumption 2, a_i is close to the ERM solution z⋆_{i,0} and that GD(z⋆_{i,0}) = z⋆_{i,0}; neither assertion follows from Assumption 2 as stated, and no bound relating z⋆_i to z⋆_{i,0} of the needed order is provided. In addition, Assumption 2 requires a common zero-gradient point for all functions in each deletion interval, which in an adversarial sequence of strongly convex losses is rarely satisfied; the paper gives no example class. The (α,αε)-OLU claim in Theorem 6 appears not to need Assumption 2, but the advertised O(log T) regret bound does, so this gap is load-bearing for the active algorithm.","section":"Section 4, Assumption 2 and Theorem 6 (Appendix C)"}],"minor_comments":[{"comment":"The definition of z⋆_i has a summation j=0 to i over f_{u[j]}, with f_{u[0]} undefined; it should read j=1,...,i. The same typo recurs in the proof of Theorem 4.","section":"Section 2.2, Eq. (5)"},{"comment":"The definition of S' says f'_t=f_t for t∉T and f'_t=⊥ for t∈T; this should refer to U (the deletion indices), not T, to be consistent with the values s_t=Δ_t for t∈{u[1],...,u[k]} used in the same proof.","section":"Appendix B.1"},{"comment":"The displayed formula for σ_i is ambiguous: it should read σ_i = sqrt(ω i^ω/(2(ω−1)ε)) γ^{τ[i]−u[i]} Δ_{u[i]}, matching the squared expression used in the proof. Please typeset the squared term clearly.","section":"Algorithm 1, line 5"},{"comment":"The displayed regret bound contains garbled LaTeX (/radicaltp /radicalvertex) and should be rewritten; the same applies to Eq. (17) and (26) in the appendix.","section":"Theorem 4 and its proof"},{"comment":"Proposition 1 is stated and proved twice (once at the start of Appendix B.1 and again immediately after), which creates duplicate numbering.","section":"Appendix B.1"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the passive part of the paper is a solid contribution and, modulo the fix to Definition 2 and explicit clarification of the comparison process, I would be happy to see it published. The active regret analysis needs more careful work; as it stands, Theorem 6's O(log T) bound is not established. I recommend major revision rather than rejection because the gaps appear addressable within the scope of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something genuinely new: it formalizes online learning-unlearning, where deletion requests arrive between gradient updates, and gives two OGD-based algorithms with regret bounds that are clean and plausible. The passive algorithm is the real contribution. Injecting calibrated noise at deletion times, with the scale controlled by how much contraction has already erased the point's influence, is a natural idea and the PABI-style analysis is a good fit. Theorems 2 and 3 check out at a high level, and the regret overhead depending on k and d is honestly stated. No code or experiments, which is fine for a theory paper, though it does limit confidence. The main soft spot is Definition 2. As written, the guarantee only covers intervals between consecutive deletions, i=1,...,k-1. That means the interval after the last deletion is not covered at all, and for a single deletion request the condition set is empty, so every algorithm is trivially an (alpha,epsilon)-OLU. That contradicts the abstract's claim that after a point is unlearned, all subsequent outputs are indistinguishable from retraining without it. The fix looks local, just extend the quantification to i=1,...,k with tau[k+1]=T, and the proof's post-processing argument can likely handle the final interval too. But as printed, the main formal statement does not deliver what the paper advertises. There is also a proofreading issue in the proof of Theorem 1: the retraining sequence S' is defined with f'_t = bottom for t in the deletion-time set T, not the deleted-index set U. If that is a typo, fine; if not, the proof compares against the wrong object. Relatedly, Proposition 1 appears twice with inconsistent RDP parameters. These are the kind of things a careful referee would catch. The active algorithm is weaker than the paper's framing. Theorem 6's O(log T) regret depends on Assumption 2, which essentially requires that within each deletion interval there is a point near the ERM where every loss has zero gradient. For adversarial convex sequences that is rarely satisfied, and the paper gives no example class. Without Assumption 2, the active advantage over passive disappears. That is a real limitation, not a nitpick. Overall, this is a serious paper worth refereeing, but not in its current form. The passive framework is solid enough to be the core contribution; the active part needs either a motivating example for Assumption 2 or a weaker replacement. The definition gap must be fixed before any claims about 'protected forever' can stand. I would recommend sending it to a strong theory venue with conditions, and would want to see a corrected version before citing it.","headline":"A promising online-unlearning framework with a clean passive algorithm, but the formal guarantee as printed misses the final deletion interval and the active result leans on a very strong assumption.","tokens_in":767,"tokens_out":795,"would_cite":false,"duration_ms":58415,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C25","68P27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding calibrated noise at deletion times lets online gradient descent forget data while keeping near-standard regret.","keywords":["online convex optimization","machine unlearning","online gradient descent","Rényi divergence","regret bounds","right to be forgotten","deletion requests","privacy amplification by iteration"],"falsifier":"Build a sequence of smooth strongly convex quadratics on a bounded domain whose minimizers drift monotonically across each interval, so the common zero-gradient point required by Assumption 2 is absent. Run Algorithm 2 with the specified $I_{1,i}$ and $I_2$ steps and compare its output to retraining without the deleted points: if the $\\alpha$-R\\'enyi divergence exceeds $\\alpha\\varepsilon$ or the regret grows faster than $O(\\log T)$, Theorem 6's conclusion fails. For the passive claim, simulate a single deletion and check whether Gaussian noise of scale proportional to $\\gamma^{\\tau-u}\\Delta_u$ keeps the R\\'enyi divergence below the certified bound for every interval.","tokens_in":30573,"feed_emoji":"🗑️","tokens_out":8412,"duration_ms":83017,"temperature":0.7,"pith_summary":"This paper introduces online learning-unlearning: a model is updated round by round, and at certain rounds it receives a request to delete one of the cost functions it has already seen. The aim is to certify that after the request, every future output is statistically indistinguishable, in R\\'enyi divergence, from the outputs that would have been produced by retraining on the dataset without the deleted point. The paper claims this is achievable for online gradient descent: a passive algorithm that only adds calibrated Gaussian noise at deletion rounds satisfies the guarantee for both strongly convex and convex losses, with expected regret $O(\\log T + k^2 + d k^{1.7}/\\varepsilon)$ and $O(\\sqrt{T} + k^2 + d k^{1.7}/\\varepsilon)$, respectively. A second, active algorithm adds an offline descent-to-delete step and achieves $O(\\log T)$ regret for strongly convex losses under a geometric assumption the paper must impose on the loss sequence. If the claims are right, deletion requests need not force retraining from scratch or a restart, and the price of forgetting is a controlled additive term in regret.","feed_headline":"Online gradient descent can forget data at near-zero cost","feed_subtitle":"Two online unlearning algorithms make future outputs match retraining-without-the-deleted-point while preserving OGD regret.","key_machinery":"The load-bearing object is the contractive noisy iteration (CNI): a random process $X_{t+1} = \\psi_{t+1}(X_t) + \\xi_{t+1}$ with contractive maps $\\psi_t$ and noise inserted at selected steps. The passive proof views the two runs\\u2014with and without the deleted function\\u2014as two CNIs with the same noise, shows their sensitivity $s_t$ is nonzero only at the deleted index $u[i]$, and applies a shifted-R\\'enyi bound that amplifies contraction into privacy: the divergence after $\\ell = \\tau[i]-u[i]$ steps shrinks by $\\gamma^\\ell$ before the calibrated Gaussian noise is added. Conditions C1\\u2013C3 are the precise properties of OGD that make this work; the active algorithm replaces one noise-heavy step by the deterministic map that descends toward the empirical-risk minimizer of the retained set, trading computation for a smaller noise scale.","core_discovery":"On its own terms, the paper's discovery is a certificate and a rate. Theorem 1 shows that if the base learner's update functions satisfy three conditions\\u2014Markovian output, $\\gamma$-contraction, and bounded sensitivity\\u2014then Algorithm 1, which is the base algorithm with Gaussian noise $\\xi_i \\sim \\mathcal{N}(0, \\sigma_i^2 I_d)$ injected whenever a deletion is processed and with $\\sigma_i$ proportional to $\\gamma^{\\tau[i]-u[i]} \\Delta_{u[i]}$, is an $(\\alpha, \\alpha\\varepsilon)$-OLU. The consequences are regret theorems: for $L$-Lipschitz, $\\beta$-smooth, $\\mu$-strongly convex losses with learning rate $\\eta_t = 1/(\\mu t)$, the expected regret is $O(\\log T + k^2 + d k^{1.7}/\\varepsilon)$, and for convex losses satisfying quadratic growth it is $O(\\sqrt{T} + k^2 + d k^{1.7}/\\varepsilon)$. The active Algorithm 2, combining OGD with the descent-to-delete unlearner and noise, is also an $(\\alpha, \\alpha\\varepsilon)$-OLU and, under Assumption 2, has expected regret $O(\\log T + k(LD^2 + Ld/(\\mu\\varepsilon)) + G_2 + L^2k^2/\\mu)$, where $G_2$ decays exponentially with the spacing between deletion requests.","pith_inferences":["A testable corollary of the passive analysis is a forgetting-rate principle: any online update with contraction coefficient $\\gamma$ can set its deletion-noise variance by the contraction distance $\\gamma^{\\tau-u}\\Delta_u$, so algorithms with stronger contraction should need less noise; this could be checked numerically for mirror descent or proximal variants.","The active algorithm's success hinges on Assumption 2, so a natural extension is an adaptive scheme that tests for the common-zero-gradient point and falls back to passive noise when it is absent.","The interval-wise indistinguishability guarantee naturally composes with continual observation, suggesting a route to online unlearning for streaming deletion requests beyond the fixed schedule analyzed here.","The $\\varepsilon$-dependence in the convex regret bounds leaves open whether the $d k^{1.7}/\\varepsilon$ overhead is necessary; a lower bound for any $(\\alpha,\\varepsilon)$-OLU would decide whether the noise is priced in."],"forward_implications":["For strongly convex losses, passive OLU matches OGD's $O(\\log T)$ regret up to a deletion overhead that is polynomial in $k$ and inverse in $\\varepsilon$, so data removal is compatible with logarithmic regret.","For convex losses satisfying quadratic growth, passive OLU preserves $O(\\sqrt{T})$ regret, the same order as ordinary OGD, even when the best-in-hindsight comparator changes after each deletion.","No extra per-round computation is needed for passive unlearning: the only added cost is sampling Gaussian noise at deletion rounds.","Once a point is deleted, the interval-wise guarantee protects it at all later times, including after subsequent deletions of other points.","Active OLU can cut the noise and achieve $O(\\log T)$ regret for strongly convex losses, but it needs $O(\\log \\tau[i])$ gradient steps at each deletion and the geometric Assumption 2."],"supporting_citations":[{"why":"Supplies the descent-to-delete offline unlearning subroutine that Algorithm 2 adapts, and the baseline comparison for deletion cost.","marker":"[4]"},{"why":"Provides the contractive noisy iteration framework and the shifted-R\\'enyi privacy-amplification lemma used in Theorem 1's proof.","marker":"[20]"},{"why":"Gives the differentially private online learning baseline whose regret $O(dk\\sqrt{T}/\\varepsilon)$ and OLU translation are compared in Proposition 1 and Table 2.","marker":"[18]"},{"why":"Defines R\\'enyi differential privacy and supplies the Gaussian-divergence bound and RDP composition used throughout.","marker":"[29]"},{"why":"Establishes the standard OGD regret rates ($O(\\log T)$ strongly convex, $O(\\sqrt{T})$ convex) that the paper's regret bounds are measured against.","marker":"[10]"},{"why":"Supplies the quadratic-growth assumption and the stability lemma for ERM used to handle the changing comparator in Theorem 3.","marker":"[24]"},{"why":"Introduces contraction-based certified unlearning for noisy SGD; the passive OLU applies this idea in an online framework.","marker":"[13]"}],"fun_headline_variants":["Online unlearning via OGD: forget at near-zero extra cost","OGD that forgets: unlearning with no regret penalty","Learn and unlearn online: OGD keeps regret low","Forget deleted data without sacrificing OGD regret","Two OGD unlearning methods with baseline regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The active algorithm's advertised logarithmic regret rests on Assumption 2: during each interval between two deletion requests, every loss in that interval must have a common zero-gradient point $a_i$ lying within $1/\\tau[i]$ of the batch optimum, a condition that arbitrary online convex sequences are not guaranteed to satisfy and for which the paper gives no example loss family.","fun_headline_variants_meta":{"raw":{"variants":["Online unlearning via OGD: forget at near-zero extra cost","OGD that forgets: unlearning with no regret penalty","Learn and unlearn online: OGD keeps regret low","Forget deleted data without sacrificing OGD regret","Two OGD unlearning methods with baseline regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2864,"prompt_tokens":986,"completion_tokens":1878,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":1798}},"tokens_in":602,"tokens_out":1878,"duration_ms":13783,"temperature":1.0,"reasoning_tokens":1798,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:52:14.793384+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a sequence of smooth strongly convex quadratics on a bounded domain whose minimizers drift monotonically across each interval, so the common zero-gradient point required by Assumption 2 is absent. Run Algorithm 2 with the specified $I_{1,i}$ and $I_2$ steps and compare its output to retraining without the deleted points: if the $\\alpha$-R\\'enyi divergence exceeds $\\alpha\\varepsilon$ or the regret grows faster than $O(\\log T)$, Theorem 6's conclusion fails. For the passive claim, simulate a single deletion and check whether Gaussian noise of scale proportional to $\\gamma^{\\tau-u}\\Delta_u$ keeps the R\\'enyi divergence below the certified bound for every interval.","supporting_citations":[{"cited_title":"Des cent-to-delete: Gradient-based methods for ma- chine unlearning","cited_arxiv_id":null,"evidence_quote":"Supplies the descent-to-delete offline unlearning subroutine that Algorithm 2 adapts, and the baseline comparison for deletion cost."},{"cited_title":"Privacy Amplification by Iteration","cited_arxiv_id":null,"evidence_quote":"Provides the contractive noisy iteration framework and the shifted-R\\'enyi privacy-amplification lemma used in Theorem 1's proof."},{"cited_title":"(Nearly) optim al algorithms for private online learning in full-information and bandit settings","cited_arxiv_id":null,"evidence_quote":"Gives the differentially private online learning baseline whose regret $O(dk\\sqrt{T}/\\varepsilon)$ and OLU translation are compared in Proposition 1 and Table 2."},{"cited_title":"Rényi differential privacy","cited_arxiv_id":null,"evidence_quote":"Defines R\\'enyi differential privacy and supplies the Gaussian-divergence bound and RDP composition used throughout."},{"cited_title":"On the gene ralization ability of online gradient descent algorithm under the quadratic growth condition","cited_arxiv_id":null,"evidence_quote":"Supplies the quadratic-growth assumption and the stability lemma for ERM used to handle the changing comparator in Theorem 3."},{"cited_title":"Cert ified machine unlearning via noisy stochastic gradient descent","cited_arxiv_id":null,"evidence_quote":"Introduces contraction-based certified unlearning for noisy SGD; the passive OLU applies this idea in an online framework."}],"review_version":1}