Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning
This work provides the first optimal guarantees for auditing RDP in black-box machine learning, addressing a critical need for reliable privacy verification.
The authors introduce an optimal black-box auditing framework for Rényi differential privacy (RDP) using Donsker-Varadhan variational estimators, achieving minimax optimal sample complexity and improving empirical RDP lower bounds over prior methods, especially at small and moderate Rényi orders.
We study black-box auditing for machine learning algorithms that claim R \ 'enyi differential privacy (RDP) guarantees. We introduce an auditing framework, based on hypothesis testing, that directly estimates Rényi divergence between neighboring executions using the Donsker-Varadhan (DV) variational estimator. Our analysis yields explicit and non-asymptotic confidence intervals for RDP auditing via class-restricted DV estimators, separating statistical estimation error from algorithmic privacy leakage. We prove matching minimax lower bounds showing that, up to logarithmic factors, our sample-complexity guarantees are information-theoretically optimal, thereby establishing the first optimal guarantees for auditing RDP via DV estimators. Empirically, we instantiate our framework for auditing DP-SGD in a fully black-box setting. Across MNIST and CIFAR-10, and over a wide range of privacy regimes, our auditors produce a strong overall improvement on empirical RDP lower bounds compared to prior state-of-the-art black-box methods especially at small and moderate Rényi orders where accurate auditing is most challenging.