The gradient residual is the norm of the gradient of the loss function evaluated at the approximately unlearned model parameters w⁻ on the remaining dataset D’: ||∇L(w⁻; D’)||₂. It is the primary measure of approximation quality for Newton-step-based certified removal mechanisms. A zero gradient residual means w⁻ is exactly the minimizer of L(·; D’), i.e., the unlearning is exact.
The gradient residual controls the certified removal guarantee: given a loss perturbation vector b ~ N(0, σI)^d and a removal mechanism producing w⁻ with ||∇L(w⁻; D’)||₂ ≤ ε’, the mechanism achieves (ε, δ)-certified removal with δ = 1.5·exp(-c²/2) when b ~ N(0, cε’/ε)^d.
Key Details
- Worst-case bound (Theorem 1, Guo et al.): ||∇L(w⁻; D’)||₂ ≤ 4γC²/(λ²(n-1))
- Data-dependent bound (Corollary 1): ||∇L(w⁻; D’)||₂ ≤ γ||X⁻||₂ · ||H⁻¹Δ||₂ · ||X⁻H⁻¹Δ||₂ — orders of magnitude tighter
- Multiple removals: Scales linearly (T·ε’) for sequential single removals, quadratically for batch
- Removal budget: Total β = Σ gradient residuals; if β > σε/c, must retrain from scratch
- For least squares: Gradient residual is exactly zero (Newton step is exact)
- For logistic regression: Bounded by O(1/λ²n) with Lipschitz constant γ = 1/4