A technique for extending certified unlearning from convex to nonconvex objectives in deep neural networks. The core idea is to add an l2 regularization term (lambda * ||w||2^2 / 2) to the loss function when computing the Hessian, effectively replacing the (possibly indefinite) Hessian H{w*} with (H_{w*} + lambda * I). This ensures the regularized Hessian is positive definite even when the original loss landscape is nonconvex, enabling the Newton update step used in certified unlearning to produce a well-defined approximation of the retrained model.
The key result (Theorem 3.4 in ZHANGB2024) shows that under Lipschitz gradient (L) and Lipschitz Hessian (M) assumptions, the approximation error is bounded by:
||w_tilde - w_tilde*||_2 ⇐ 2C(MC + lambda) / (lambda + lambda_min)
where C is the weight norm constraint, lambda_min is the smallest eigenvalue of the Hessian, and lambda > ||H_{w*}||_2 ensures positive definiteness. The lambda parameter controls a tradeoff: larger lambda makes the Hessian more well-conditioned (tighter error bound) but introduces more bias from the regularization. In practice, increasing lambda reduces the approximation error bound and slightly reduces real approximation error, as verified empirically on CIFAR-10 with AllCNN (Table 3 in ZHANGB2024).
This technique is combined with a weight norm constraint ||w||_2 ⇐ C during training (via projected gradient descent) to make the error bound independent of the unlearned set size. Together, these two modifications make the certified unlearning framework applicable to DNNs without requiring convexity of the loss function.