On Optimization Complexity of Second-Order Certified Unlearning

• URL: http://arxiv.org/abs/2607.20192v1
• Date: Wed, 22 Jul 2026 14:16:02 GMT
• Title: On Optimization Complexity of Second-Order Certified Unlearning
• Abstract summary: We formalize the goal of an unlearning algorithm as simultaneously achieving certified unlearning and optimization accuracy.<n>We develop a new second-order unlearning algorithm with an anisotropic Gaussian mechanism and state-of-the-art global convergence.
• Score: 13.772246033005672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study machine unlearning: the removal of memorized training data from a trained model. Specifically, we investigate the algorithmic complexity of certified unlearning from an optimization perspective. We formalize the goal of an unlearning algorithm as simultaneously achieving certified unlearning and optimization accuracy. Utilizing the notion of uniformly convex regularizers, we prove new bounds on the distance between initial and unlearned models using a novel substitute for generalization error. Thus we theoretically demonstrate that if the removed data is well-predicted by the unlearned model, the corresponding optimization problem is simple. Furthermore, we develop a new second-order unlearning algorithm with an anisotropic Gaussian mechanism and state-of-the-art global convergence. We prove fast rates for our method in achieving certified unlearning for linear models with quasi-self-concordant losses. As a direct application, our theory covers unlearning for logistic and exponential regressions and shows a provable benefit of utilizing second-order information compared to first-order unlearning methods.

Related papers

• Heterogeneous Self-Supervised Acoustic Pre-Training with Local Constraints [64.15709757611369]
  We propose a new self-supervised pre-training approach to dealing with heterogeneous data.<n>The proposed approach can significantly improve the adaptivity of the self-supervised pre-trained model for the downstream supervised fine-tuning tasks.
  arXiv  Detail & Related papers  (2025-08-27T15:48:50Z)
• L-SR1: Learned Symmetric-Rank-One Preconditioning [5.421390145168128]
  End-to-end deep learning has achieved impressive results but remains limited by its reliance on large labeled datasets.<n>In contrast, classical optimization methods are data-efficient and lightweight but often suffer from slow convergence.<n>We propose a novel learned second-order vectors that introduces a trainable preconditioning unit to enhance the classical Symmetric-Rank-One algorithm.
  arXiv  Detail & Related papers  (2025-08-17T07:37:29Z)
• Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
  Influence-based unlearning has emerged as a prominent approach to estimate the impact of individual training samples on model parameters without retraining.<n>This paper establishes a theoretical link between memorizing (incremental learning) and forgetting (unlearning)<n>We introduce the Influence Approximation Unlearning algorithm for efficient machine unlearning from the incremental perspective.
  arXiv  Detail & Related papers  (2025-07-31T05:34:27Z)
• 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)
• Learning to optimize with convergence guarantees using nonlinear system theory [0.4143603294943439]
  We propose an unconstrained parametrization of algorithms for smooth objective functions. Notably, our framework is directly compatible with automatic differentiation tools.
  arXiv  Detail & Related papers  (2024-03-14T13:40:26Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• Algorithms that Approximate Data Removal: New Results and Limitations [2.6905021039717987]
  We study the problem of deleting user data from machine learning models trained using empirical risk minimization. We develop an online unlearning algorithm that is both computationally and memory efficient.
  arXiv  Detail & Related papers  (2022-09-25T17:20:33Z)
• Information bottleneck theory of high-dimensional regression: relevancy, efficiency and optimality [6.700873164609009]
  Overfitting is a central challenge in machine learning, yet many large neural networks readily achieve zero training loss. We quantify overfitting via residual information, defined as the bits in fitted models that encode noise in training data.
  arXiv  Detail & Related papers  (2022-08-08T00:09:12Z)
• Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning [90.8576971748142]
  We develop a novel surrogate that can be optimized by closed-form solutions. We exploit upperwise correlation for completion, and thus an adaptive correlation learning model.
  arXiv  Detail & Related papers  (2022-03-04T08:50:50Z)
• 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)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48: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.