Pith. sign in

REVIEW 3 major objections 5 minor 32 references

Online Learning and Unlearning

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adding calibrated noise at deletion times lets online gradient descent forget data while keeping near-standard regret.

desk verdict 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. read the letter →

arxiv 2505.08557 v1 pith:G2ILNJ22 submitted 2025-05-13 cs.LG

Yaxi Hu , Bernhard Schölkopf , Amartya Sanyal This is my paper · ORCID
classification cs.LG MSC 68Q3290C2568P27
keywords onlineconvexoptimizationmachineunlearninggradientdescentRényidivergenceregretboundsrighttobeforgottendeletionrequestsprivacyamplificationbyiteration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 2.2, Definition 2 (Eq. (4))] 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.
  2. [Definition 2 and Appendix B.1 (proof of Theorem 1)] 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.
  3. [Section 4, Assumption 2 and Theorem 6 (Appendix C)] 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.
minor comments (5)
  1. [Section 2.2, Eq. (5)] 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.
  2. [Appendix B.1] 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.
  3. [Algorithm 1, line 5] 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.
  4. [Theorem 4 and its proof] The displayed regret bound contains garbled LaTeX (/radicaltp /radicalvertex) and should be rewritten; the same applies to Eq. (17) and (26) in the appendix.
  5. [Appendix B.1] Proposition 1 is stated and proved twice (once at the start of Appendix B.1 and again immediately after), which creates duplicate numbering.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the unlearning guarantees are proved from explicit contraction, sensitivity, and noise-calibration conditions, and the main caveat is a formal-strength gap in Definition 2 rather than circular reasoning.

full rationale

The derivation chain is self-contained and does not reduce to its own inputs. Theorem 1 proves the (α,αε)-OLU claim by comparing the two CNI processes generated from the base updates: the sensitivity term s_t is read off from Condition C3, the shift variables a_t are set to γ^{τ[i]−u[i]}Δ_{u[i]}, and the Gaussian noise scale in Algorithm 1 is chosen so that the accumulated Rényi terms telescope to αε (Eq. (8) in Appendix B.1). This is a calibration argument, not a fitted parameter renamed as a prediction. Lemma 3, the central amplification lemma, is proved in the appendix rather than imported as a black box; the external facts used (Rényi post-processing, Gaussian Rényi divergence, PABI-style contraction lemmas) are standard cited results with proofs supplied where needed. The regret bounds in Theorems 2–5 follow textbook OGD potential arguments augmented by stability lemmas (Lemmas 5 and 6) that are proved in the text, and the dynamic comparator in Eq. (5) is a definition of the performance measure rather than an input that forces the claimed rates. No load-bearing premise is justified only by a self-citation: the one co-authored reference ([3]) is motivational only, and the PABI/RDP references are external published results. The strongest caveat in the paper is a correctness/formal-strength issue, not circularity: Definition 2 as printed quantifies only over i = 1,...,k−1, so the interval after the last deletion is unconstrained and the k=1 case is vacuous; this is a mismatch between the abstract's promise of protection for 'all subsequent outputs' and the formal definition, but it does not make any derived result equivalent to its inputs by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard OCO regularity assumptions, the quadratic growth condition, and a strong ad hoc assumption (Assumption 2) for the active algorithm. No data-fitted parameters appear; omega and the I2 constant are hand-chosen design constants. The skip element is a modeling convention. The proof of the multi-deletion guarantee also relies on an external PABI lemma whose application is not fully spelled out, which affects soundness rather than circularity.

free parameters (2)
  • omega (ω) = 1.2 in Theorems 2/3, 1.5 in Theorem 4
    Hand-chosen exponent in the noise scale σ_i^2 = i^ω ω (...) / (2(ω−1)ε) to make the series Σ 1/i^ω converge. It appears in all regret bounds as a constant factor and does not change the asymptotics.
  • I2 constant 2.2 = 2.2
    In Theorem 6, the number of descent-to-delete steps is set to I2 ≥ 2.2 log(1/γ) k. The constant 2.2 is chosen by hand to guarantee contraction and enters the noise scale and the O(k...) regret term.
assumptions (5)
  • domain assumption Cost functions are L-Lipschitz, β-smooth, and (for Theorem 2/6) µ-strongly convex, defined on a set K of diameter D.
    Used throughout (Definition 3, Section 2.1). These regularity conditions are needed for OGD contractiveness and for the regret bounds.
  • domain assumption Quadratic Growth (Assumption 1) holds for each aggregate function Σ_{t=1}^{τ[i]} f_t with parameter κ(τ[i]−τ[i−1]).
    Needed in Theorems 3 and 5 to bound the movement of the changing comparator z⋆_i. It is a standard, though nontrivial, condition in optimization.
  • ad hoc to paper Assumption 2: for every deletion interval there exists a_i with ‖a_i − z⋆_i‖ ≤ 1/τ[i] and ∇f_t(a_i)=0 for all t in the interval.
    Introduced in Section 4 specifically to make the active OLU regret proof work. No example class is given, and it can fail for typical online convex sequences. This is a load-bearing premise for Theorem 6.
  • domain assumption Skip element ⊥: replacing a deleted function f_u with ⊥, and having the base algorithm ignore ⊥, exactly represents retraining without f_u.
    Definition 2 and the regret definition Eq. (5) rely on this encoding of the retained dataset. It is a modeling choice rather than an empirical fact.
  • standard math Privacy Amplification by Iteration (Lemma 3 from Feldman et al. [20]) and Rényi divergence properties (Lemma A, B from Mironov [29]) are used as external results.
    Used in Theorem 1 and Appendix B.1 to bound Rényi divergence between noisy and retrained trajectories. These are established results, but the paper adapts them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Learning and Unlearning." pith.science (2026). https://pith.science/paper/G2ILNJ22

@misc{pith2026250508557,
  author       = {Pith},
  title        = {Pith review of: Online Learning and Unlearning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G2ILNJ22}},
  note         = {Machine review of arXiv:2505.08557}
}
read the original abstract

We formalize the problem of online learning-unlearning, where a model is updated sequentially in an online setting while accommodating unlearning requests between updates. After a data point is unlearned, all subsequent outputs must be statistically indistinguishable from those of a model trained without that point. We present two online learner-unlearner (OLU) algorithms, both built upon online gradient descent (OGD). The first, passive OLU, leverages OGD's contractive property and injects noise when unlearning occurs, incurring no additional computation. The second, active OLU, uses an offline unlearning algorithm that shifts the model toward a solution excluding the deleted data. Under standard convexity and smoothness assumptions, both methods achieve regret bounds comparable to those of standard OGD, demonstrating that one can maintain competitive regret bounds while providing unlearning guarantees.

Figures

Figures reproduced from arXiv: 2505.08557 by the authors.

Figure 1
Figure 1. Visualization of the output sequence of algorithm A up to the first deletion τ [1] γ ∈ (0, 1] and ∆t < ∞, the update function gt satisfies: Markovian Output: gt(f1:t, z1:t−1) = gt(ft, zt−1), (C1) γ-Contraction: kgt(f, z1) − gt(f, z2)k2 ≤ γ kz1 − z2k2 , (C2) ∆1:T -Sensitivity: kgt(f, x) − xk2 ≤ ∆t. (C3) Condition C1 ensures that update gt depends only on the latest cost function and previous output, allowing it to be… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 28 canonical work pages

  1. [1]

    Membership inference attacks against machine learning models

    Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP) , 2017

    work page 2017

  2. [2]

    Reconstructing traini ng data from model gradient, provably

    Zihan Wang, Jason Lee, and Qi Lei. Reconstructing traini ng data from model gradient, provably. In Pro- ceedings of The 26th International Conference on Artificial Intelligence and Statistics, 2023

    work page 2023

  3. [3]

    Corrective machine unlearning

    Shashwat Goel, Ameya Prabhu, Philip Torr, Ponnurangam K umaraguru, and Amartya Sanyal. Corrective machine unlearning. Transactions on Machine Learning Research, 2024. ISSN 2835-8856

    work page 2024

  4. [4]

    Des cent-to-delete: Gradient-based methods for ma- chine unlearning

    Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Des cent-to-delete: Gradient-based methods for ma- chine unlearning. In Proceedings of the 32nd International Conference on Algori thmic Learning Theory , 2021

    work page 2021

  5. [5]

    Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot

    Lucas Bourtoule, V arun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlea rning. 2021 IEEE Symposium on Security and Privacy (SP) , 2019

    work page 2021

  6. [6]

    Remember what you want to forget: algorithms for machine unlearning

    A yush Sekhari, Jayadev Acharya, Gautam Kamath, and Anan da Theertha Suresh. Remember what you want to forget: algorithms for machine unlearning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021

    work page 2021

  7. [7]

    Rewind-to-delete: Certifie d machine unlearning for nonconvex functions

    Siqiao Mu and Diego Klabjan. Rewind-to-delete: Certifie d machine unlearning for nonconvex functions. ArXiv:2409.09778, 2024

    arXiv 2024

  8. [8]

    Algor ithms that approximate data removal: New results and limitations

    Vinith Menon Suriyakumar and Ashia Camage Wilson. Algor ithms that approximate data removal: New results and limitations. In Advances in Neural Information Processing Systems , 2022. 9

    work page 2022

Show all 32 references
  1. [9]

    Control, confidentiality, and the right to be forgotten

    Aloni Cohen, Adam Smith, Marika Swanberg, and Prashant N alini V asudevan. Control, confidentiality, and the right to be forgotten. In Proceedings of the 2023 ACM SIGSAC Conference on Computer an d Communications Security, 2023

    2023

  2. [10]

    Introduction to online convex optimizatio n

    Elad Hazan. Introduction to online convex optimizatio n. ArXiv: 1909.05207, 2019

    1909 arXiv

  3. [11]

    A modern introduction to online lea rning

    Francesco Orabona. A modern introduction to online lea rning. ArXiv:1912.13213, 2019

    1912 arXiv

  4. [12]

    Certified data removal from machine learning models

    Chuan Guo, Tom Goldstein, A wni Hannun, and Laurens V an D er Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machin e Learning, 2020

    2020

  5. [13]

    Cert ified machine unlearning via noisy stochastic gradient descent

    Eli Chien, Haoyu Peter Wang, Ziang Chen, and Pan Li. Cert ified machine unlearning via noisy stochastic gradient descent. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  6. [14]

    Differential privacy

    Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 2006

    2006

  7. [15]

    Counting distinct elements in the turnstile model with differential privacy u nder continual observation

    Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchi t Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy u nder continual observation. In Advances in Neural Information Processing Systems, 2023

    2023

  8. [16]

    Online convex programming and gener alized infinitesimal gradient ascent

    Martin Zinkevich. Online convex programming and gener alized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Internationa l Conference on Machine Learning , 2003

    2003

  9. [17]

    Dynamic regret of convex and smooth functions

    Peng Zhao, Y u-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020

    2020

  10. [18]

    (Nearly) optim al algorithms for private online learning in full-information and bandit settings

    Abhradeep Guha Thakurta and Adam Smith. (Nearly) optim al algorithms for private online learning in full-information and bandit settings. In Advances in Neural Information Processing Systems , 2013

    2013

  11. [19]

    Differentially private online learning

    Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta . Differentially private online learning. In Proceed- ings of the 25th Annual Conference on Learning Theory , 2012

    2012

  12. [20]

    Privacy Amplification by Iteration

    Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhrad eep Thakurta. Privacy Amplification by Iteration . In 2018 IEEE 59th Annual Symposium on F oundations of Computer S cience (FOCS), 2018

    2018

  13. [21]

    Privacy of noisy sto chastic gradient descent: More iterations without more privacy loss

    Jason Altschuler and Kunal Talwar. Privacy of noisy sto chastic gradient descent: More iterations without more privacy loss. In Advances in Neural Information Processing Systems , 2022

    2022

  14. [22]

    Resolving the mixin g time of the langevin algorithm to its stationary distribution for log-concave sampling

    Jason Altschuler and Kunal Talwar. Resolving the mixin g time of the langevin algorithm to its stationary distribution for log-concave sampling. In Proceedings of Thirty Sixth Conference on Learning Theory , 2023

    2023

  15. [23]

    Train faster , generalize better: Stability of stochastic gradient descent

    Moritz Hardt, Ben Recht, and Y oram Singer. Train faster , generalize better: Stability of stochastic gradient descent. In Proceedings of The 33rd International Conference on Machin e Learning, 2016

    2016

  16. [24]

    On the gene ralization ability of online gradient descent algorithm under the quadratic growth condition

    Daqing Chang, Ming Lin, and Changshui Zhang. On the gene ralization ability of online gradient descent algorithm under the quadratic growth condition. IEEE Transactions on Neural Networks and Learning Systems, 2018

    2018

  17. [25]

    Logarithmi c regret algorithms for online convex optimization

    Elad Hazan, Alekh Agarwal, and Satyen Kale. Logarithmi c regret algorithms for online convex optimization. In Proceedings of the 20th Annual Conference on Learning Theor y (COLT), 2007

    2007

  18. [26]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Y oram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research , 2011

    2011

  19. [27]

    Op timistic rates for learning with a smooth loss

    Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Op timistic rates for learning with a smooth loss. ArXiv:1009.3896, 2012

    2012 arXiv

  20. [28]

    Ticketed learning-unlearning schemes

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manuran gsi, A yush Sekhari, and Chiyuan Zhang. Ticketed learning-unlearning schemes. In 36th Annual Conference on Learning Theory , 2023

    2023

  21. [29]

    Rényi differential privacy

    Ilya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security F oundations Symposium (CSF), 2017

    2017

  22. [30]

    Ele522: Lecutre notes for gradient methods (unconstrained), 2020

    Y uxin Wang. Ele522: Lecutre notes for gradient methods (unconstrained), 2020. 10 A Omitted Proofs for Section 2 Definition 3. A functionf : X → Y , isL-Lipschitz if the following hold for all x,y ∈ X , ‖f (x) −f (y)‖2 ≤L ‖x −y‖2. f is calledµ-strongly convex if for all x,y ∈ X...

    2020

  23. [31]

    Lemma C (Shift-reduction lemma [20])

    For the induction step, let ξt+1 denote the random variable drawn from ζt+1, D(et+1) α ( Xt+1‖X ′ t+1 ) =D(et+1) α ( ψt+1(Xt) +ξt+1‖ψ′ t+1(X ′ t) +ξt+1 ) (a) ≤ D(et+1+at+1) α (ψt+1(Xt)‖ψt+1(X ′ t)) +Rα(ζt+1,a t+1) (b) ≤ D(γet+st+1) α (ψt+1(Xt)‖ψt+1(X ′ t)) +Rα(ζt+1,a t+1) (c) ...

  24. [32]

    The unlearning auxiliary function Uaux(ψj(z), Sτ [j], SU j ) performs these two phases: I1 GD steps on Sτ [j] (viaF0) and I2 GD steps on Sτ [j] \ S U j (viaF1)

    Con- sider the first I1 gradient descent (GD) steps of the unlearning algorithm on t he set Sτ [j], denoted by the func- tion F0, followed by I2 GD steps on the set Sτ [j] \ S U j , denoted by F1. The unlearning auxiliary function Uaux(ψj(z), Sτ [j], SU j ) performs these two p...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.