{
  "id": "1906.03049",
  "version": "v1",
  "published": "2019-06-07T12:33:46.000Z",
  "updated": "2019-06-07T12:33:46.000Z",
  "title": "Computing Exact Guarantees for Differential Privacy",
  "authors": [
    "Antti Koskela",
    "Joonas Jälkö",
    "Antti Honkela"
  ],
  "comment": "24 pages, 5 figures",
  "categories": [
    "stat.ML",
    "cs.CR",
    "cs.LG"
  ],
  "abstract": "Quantification of the privacy loss associated with a randomised algorithm has become an active area of research and $(\\varepsilon,\\delta)$-differential privacy has arisen as the standard measure of it. We propose a numerical method for evaluating the parameters of differential privacy for algorithms with continuous one dimensional output. In this way the parameters $\\varepsilon$ and $\\delta$ can be evaluated, for example, for the subsampled multidimensional Gaussian mechanism which is also the underlying mechanism of differentially private stochastic gradient descent. The proposed method is based on a numerical approximation of an integral formula which gives the exact $(\\varepsilon,\\delta)$-values. The approximation is carried out by discretising the integral and by evaluating discrete convolutions using a fast Fourier transform algorithm. We give theoretical error bounds which show the convergence of the approximation and guarantee its accuracy to an arbitrary degree. Experimental comparisons with state-of-the-art techniques illustrate the efficacy of the method. Python code for the proposed method can be found in Github (https://github.com/DPBayes/PLD-Accountant/).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-07T12:33:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "differential privacy",
      "computing exact guarantees",
      "fast fourier transform algorithm",
      "differentially private stochastic gradient descent",
      "approximation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}