The paper establishes that the optimal excess risk for ε-unlearning is the usual statistical error plus an unlearning penalty that interpolates between retraining-from-scratch and an exponentially smaller term as ε/d grows, with matching bounds for mean estimation.
Optimal Differentially Private Model Training with Public Data
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Differential privacy (DP) ensures that training a machine learning model does not leak private data. In practice, we may have access to auxiliary public data that is free of privacy concerns. In this work, we assume access to a given amount of public data and settle the following fundamental open questions: 1. What is the optimal (worst-case) error of a DP model trained over a private data set while having access to side public data? 2. How can we harness public data to improve DP model training in practice? We consider these questions in both the local and central models of pure and approximate DP. To answer the first question, we prove tight (up to log factors) lower and upper bounds that characterize the optimal error rates of three fundamental problems: mean estimation, empirical risk minimization, and stochastic convex optimization. We show that the optimal error rates can be attained (up to log factors) by either discarding private data and training a public model, or treating public data like it is private and using an optimal DP algorithm. To address the second question, we develop novel algorithms that are "even more optimal" (i.e. better constants) than the asymptotically optimal approaches described above. For local DP mean estimation, our algorithm is optimal including constants. Empirically, our algorithms show benefits over the state-of-the-art.
fields
cs.LG 2years
2026 2representative citing papers
DP-NGD enables second-order optimization under differential privacy by decoupling curvature estimation onto public data, performing isotropic DP operations in a whitened space, and dynamically clamping curvature eigenvalues to prevent instability.
citing papers explorer
-
Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses
The paper establishes that the optimal excess risk for ε-unlearning is the usual statistical error plus an unlearning penalty that interpolates between retraining-from-scratch and an exponentially smaller term as ε/d grows, with matching bounds for mean estimation.
-
Differentially Private Natural Gradient Descent
DP-NGD enables second-order optimization under differential privacy by decoupling curvature estimation onto public data, performing isotropic DP operations in a whitened space, and dynamically clamping curvature eigenvalues to prevent instability.