Faster Privacy Accounting via Evolving Discretization
This work provides a faster privacy accounting method for practitioners in differential privacy, particularly for applications like differentially private stochastic gradient descent, though it is incremental as it builds on existing composition techniques.
The paper tackles the problem of efficiently computing differential privacy parameters for composed mechanisms, introducing an algorithm that achieves polylog(k) runtime and memory for self-composing a mechanism k times, compared to prior work with O(√k) runtime.
We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms. Our algorithm achieves a running time and memory usage of $\mathrm{polylog}(k)$ for the task of self-composing a mechanism, from a broad class of mechanisms, $k$ times; this class, e.g., includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent. By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task. Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon their running time and memory usage from $\widetilde{O}(k^{1.5})$ to $\widetilde{O}(k)$.