Online Learning and Unlearning

• URL: http://arxiv.org/abs/2505.08557v1
• Date: Tue, 13 May 2025 13:33:36 GMT
• Title: Online Learning and Unlearning
• Authors: Yaxi Hu, Bernhard Schölkopf, Amartya Sanyal,
• Abstract summary: We present two online learner-unlearner (OLU) algorithms, both built upon online gradient descent (OGD)<n>The first, passive OLU, leverages OGD's contractive property and injects noise when unlearning occurs, incurring no additional computation.<n>The second, active OLU, uses an offline unlearning algorithm that shifts the model toward a solution excluding the deleted data.
• Score: 56.770023668379615
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Online Prototypes and Class-Wise Hypergradients for Online Continual Learning with Pre-Trained Models [24.963242232471426]
  Continual Learning (CL) addresses the problem of learning from a data sequence where the distribution changes over time.<n>In this paper, we tackle both problems by leveraging Online Prototypes (OP) and Class-Wise Hypergradients (CWH)<n>OP leverages stable output representations of PTM by updating its value on the fly to act as replay samples without requiring task boundaries.<n>CWH learns class-dependent gradient coefficients during training to improve over sub-optimal learning rates.
  arXiv  Detail & Related papers  (2025-02-26T02:43:54Z)
• Online-BLS: An Accurate and Efficient Online Broad Learning System for Data Stream Classification [52.251569042852815]
  We introduce an online broad learning system framework with closed-form solutions for each online update.<n>We design an effective weight estimation algorithm and an efficient online updating strategy.<n>Our framework is naturally extended to data stream scenarios with concept drift and exceeds state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-01-28T13:21:59Z)
• Stabilizing Linear Passive-Aggressive Online Learning with Weighted Reservoir Sampling [46.01254613933967]
  Online learning methods are still highly effective for high-dimensional streaming data, out-of-core processing, and other throughput-sensitive applications. Many such algorithms rely on fast adaptation to individual errors as a key to their convergence. While such algorithms enjoy low theoretical regret, in real-world deployment they can be sensitive to individual outliers that cause the algorithm to over-correct.
  arXiv  Detail & Related papers  (2024-10-31T03:35:48Z)
• Hessian-Free Online Certified Unlearning [8.875278412741695]
  We develop an online unlearning algorithm that achieves near-instantaneous data removal.<n>We prove that our proposed method outperforms the state-of-the-art methods in terms of the unlearning and generalization guarantees.
  arXiv  Detail & Related papers  (2024-04-02T07:54:18Z)
• Continual learning for surface defect segmentation by subnetwork creation and selection [55.2480439325792]
  We introduce a new continual (or lifelong) learning algorithm that performs segmentation tasks without undergoing catastrophic forgetting. The method is applied to two different surface defect segmentation problems that are learned incrementally. Our approach shows comparable results with joint training when all the training data (all defects) are seen simultaneously.
  arXiv  Detail & Related papers  (2023-12-08T15:28:50Z)
• Efficient Online Learning with Offline Datasets for Infinite Horizon MDPs: A Bayesian Approach [25.77911741149966]
  We show that if the learning agent models the behavioral policy used by the expert, it can do substantially better in terms of minimizing cumulative regret. We then propose the Informed RLSVI algorithm to efficiently approximate the iPSRL algorithm.
  arXiv  Detail & Related papers  (2023-10-17T19:01:08Z)
• Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory [19.822215548822882]
  Online gradient descent (OGD) algorithms have been proposed to handle online pairwise learning, where data arrives sequentially. Recent advancements in OGD algorithms have aimed to reduce the complexity of calculating online gradients, achieving complexities less than $O(T)$ and even as low as $O(1)$. In this study, we propose a limited memory OGD algorithm that extends to kernel online pairwise learning while improving the sublinear regret.
  arXiv  Detail & Related papers  (2023-10-10T09:50:54Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  We study the problem of model selection in offline RL with value function approximation. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal inequalities up to logarithmic factors. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class.
  arXiv  Detail & Related papers  (2022-11-03T17:32:34Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  parameter-free algorithms are online learning algorithms that do not require setting learning rates. We propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties.
  arXiv  Detail & Related papers  (2022-03-19T13:39:49Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning [13.149070833843133]
  Machine unlearning, i.e. having a model forget about some of its training data, has become increasingly important as privacy legislation promotes variants of the right-to-be-forgotten. We first show that the definition that underlies approximate unlearning, which seeks to prove the approximately unlearned model is close to an exactly retrained model, is incorrect because one can obtain the same model using different datasets. We then turn to exact unlearning approaches and ask how to verify their claims of unlearning.
  arXiv  Detail & Related papers  (2021-10-22T16:16:56Z)

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

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