PreprintCited by 224Privacy-Preserving Technologies in DataCryptography and Data SecurityCloud Data Security Solutions

Subsampled Rényi Differential Privacy and Analytical Moments Accountant

Open access
Wang, Yu-Xiang, Balle, Borja, Kasiviswanathan, Shiva·2018·arXiv

Abstract

We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Rényi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter. Our results generalize the moments accounting technique, developed by Abadi et al. (2016) for the Gaussian mechanism, to any subsampled RDP mechanism.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1808.00087

Cites

21 of 21 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Client data in federated learning can be noisy (e.g., noisy features or noisy labels) even without malicious intent.

    “Even if the data on a client is not intentionally malicious, it may have noisy features [350] (eg. in vision applications, a client may have a low-resolution camera whose output is scaled to a higher resolution) or noisy labels [356] (eg. if the user indicates that a recommendation by an app is not relevant accidentally).”

    From Advances and Open Problems in Federated Learning (2021) · cites this paper as [350]

    The citation to this paper is attached to the noisy-features part of the sentence; noisy labels has a separate citation. The Introduction (p. 1) discusses Gaussian noise added to gradients for differential privacy, not unintentionally noisy client features. Searches for low-resolution cameras, noisy features, malicious clients, and noisy labels found no passage addressing the attributed point. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

1 of the 22 references couldn’t be matched to a known paper.

Research works printed but not linked: 11

  1. Apple, D. (2017). Learning with privacy at scale. Apple Machine Learning Journal .
  2. Balle, B., & Wang, Y.-X. (2018). Improving gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. International Conference in Machine Learning (ICML) .
  3. Bassily, R., Smith, A., & Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In Foundations of Computer Science (FOCS-14) , (pp. 464-473). IEEE.
  4. Dwork, C., Rothblum, G. N., & Vadhan, S. (2010). Boosting and differential privacy. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , (pp. 51-60). IEEE.
  5. European Parliament, & Council of the European Union (2016). Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation). Official Journal of the European Union .
  6. Mironov, I. (2017). Rényi differential privacy. In Computer Security Foundations Symposium (CSF), 2017 IEEE 30th , (pp. 263-275). IEEE.
  7. Murtagh, J., & Vadhan, S. (2016). The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference , (pp. 157-175). Springer.
  8. Vajda, I. (1973). χ α -divergence and generalized fisher information. In Prague Conference on Information Theory, Statistical Decision Functions and Random Processes , (p. 223). Academia.
  9. Wang, Y.-X. (2018). Per-instance differential privacy. Journal of Confidentiality and Privacy, to appear .
  10. Wang, Y.-X., Fienberg, S., & Smola, A. (2015). Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning (ICML-15) , (pp. 2493-2502).
  11. Wang, Y.-X., Lei, J., & Fienberg, S. E. (2016). Learning with differential privacy: Stability, learnability and the sufficiency and necessity of erm principle. Journal of Machine Learning Research , 17 (183), 1-40.

Cited by

Sorted by citations

Authors
Wang, Y.-X., Balle, B., & Kasiviswanathan, S.
Affiliations
  • University of California, Santa Barbara (US)
  • Amazon (United States) (US)
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
10
Issue
2
ISSN
2575-8527 (ISSN-L)
OpenAlex
W2887654530
Cited by
224
References
22
Citations by year
2026: 24 · 2025: 30 · 2024: 44 · 2023: 17 · 2022: 13 · 2021: 48 · 2020: 35 · 2019: 12 · 2018: 1
FWCI
11.11
Type
journal article
Language
en
Open access
Locations
  • Journal of Privacy and Confidentiality (publishedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • eScholarship (California Digital Library) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
  • Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
Keywords
differential privacy, Rényi differential privacy, subsampling, randomized mechanisms, Gaussian mechanism

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review