提出二阶认证遗忘算法，证明其在特定条件下优化更简单且收敛更快。
On Optimization Complexity of Second-Order Certified Unlearning
- 基于拟自洽损失与各向异性高斯机制，设计新二阶遗忘算法
- 线性模型下实现认证遗忘的快速收敛，理论证明优于一阶方法
- 适用于逻辑回归等场景，适合关注模型可解释性的研究者
我们研究机器遗忘：从训练好的模型中移除记忆的训练数据。具体地，从优化角度分析认证遗忘的算法复杂度。将遗忘算法的目标形式化为同时实现认证遗忘和优化精度。利用一致凸正则项，通过一种新的泛化误差替代量，证明了初始模型与遗忘后模型之间的距离上界。理论上表明，若被移除的数据能被遗忘后的模型良好预测，则对应的优化问题更简单。此外，我们提出一种新的二阶遗忘算法，结合各向异性高斯机制，具备最优全局收敛性。针对具有准自洽损失的线性模型，证明了该方法在实现认证遗忘时具有快速收敛率。作为直接应用，该理论覆盖了逻辑回归与指数回归的遗忘场景，并证明了相比一阶方法，使用二阶信息可带来可证明的优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。