Capacity Bounded Differential Privacy

Ashwin Machanavajjhala; Jacob Imola; Kamalika Chaudhuri

arxiv: 1907.02159 · v1 · pith:KR4D2PCYnew · submitted 2019-07-03 · 💻 cs.LG · cs.CR· stat.ML

Capacity Bounded Differential Privacy

Kamalika Chaudhuri , Jacob Imola , Ashwin Machanavajjhala This is my paper

Pith reviewed 2026-05-25 09:48 UTC · model grok-4.3

classification 💻 cs.LG cs.CRstat.ML

keywords differential privacyf-divergencesprivacy relaxationsadversary capacitymachine learning privacystatistical divergencealgorithmic stability

0 comments

The pith

Capacity bounded differential privacy relaxes standard differential privacy by modeling the adversary as limited to a specific function class via restricted f-divergences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces capacity bounded differential privacy as a novel relaxation of differential privacy. Standard differential privacy measures distance between output distributions on neighboring datasets without restricting the adversary. Here the adversary is assumed to be capacity-bounded by the function class of their attack algorithm rather than by computational power. The authors formalize this using restricted f-divergences and examine the resulting definition along with algorithms that meet it. A sympathetic reader would care if the restriction produces privacy guarantees that are both meaningful and distinct from existing relaxations.

Core claim

Capacity bounded differential privacy is defined as the distance between the output distributions of an algorithm on neighboring datasets measured under restricted f-divergences, where the restriction corresponds to the function class from which the adversary's distinguishing algorithm is drawn. The paper studies properties of this definition and algorithms that satisfy it.

What carries the argument

Restricted f-divergences that limit the divergence measure to a chosen function class in order to capture capacity-bounded adversaries.

If this is right

Algorithms satisfying capacity bounded differential privacy protect against adversaries whose attacks are drawn from the restricted function class.
The definition can admit mechanisms with higher utility than those required by standard differential privacy.
Standard properties such as post-processing and composition hold or can be re-derived under the restricted divergence.
New mechanisms can be constructed that meet the capacity-bounded guarantee but violate ordinary differential privacy.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The definition may allow tighter analysis of privacy against concrete families of attacks such as linear classifiers or shallow decision trees.
It opens a route to hybrid guarantees that combine capacity bounds with computational bounds.
Empirical validation could involve enumerating attacks inside and outside the function class on benchmark datasets to measure the gap in success probability.

Load-bearing premise

Restricting f-divergences to a function class accurately and meaningfully captures the notion of a capacity-bounded adversary in a way that yields useful privacy guarantees distinct from prior relaxations.

What would settle it

An explicit attack drawn from a function class outside the assumed restriction that distinguishes neighboring outputs with probability exceeding the capacity-bounded bound, or a demonstration that every algorithm meeting the new definition also meets standard differential privacy.

read the original abstract

Differential privacy, a notion of algorithmic stability, is a gold standard for measuring the additional risk an algorithm's output poses to the privacy of a single record in the dataset. Differential privacy is defined as the distance between the output distribution of an algorithm on neighboring datasets that differ in one entry. In this work, we present a novel relaxation of differential privacy, capacity bounded differential privacy, where the adversary that distinguishes output distributions is assumed to be capacity-bounded -- i.e. bounded not in computational power, but in terms of the function class from which their attack algorithm is drawn. We model adversaries in terms of restricted f-divergences between probability distributions, and study properties of the definition and algorithms that satisfy them.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines capacity-bounded DP via restricted f-divergences as a new relaxation, but the abstract alone leaves it unclear whether the modeling produces distinct, usable guarantees.

read the letter

This paper puts forward capacity bounded differential privacy, where the adversary distinguishing output distributions is limited by the function class of its attack algorithm rather than by computational power or by standard divergence bounds. They model this with restricted f-divergences and say they study the resulting properties and mechanisms that meet the definition. That modeling choice is the main new element; it is not presented as a direct reduction of approximate DP or Rényi DP. The framing is clean and the authors are careful to position it as a relaxation tied to a specific kind of bounded adversary. If the full paper supplies concrete function classes, example mechanisms, and proofs that the definition is non-vacuous and yields better utility than standard DP for realistic attacks, the idea could be useful for ML settings where one can argue the attacker really is capacity-limited. The soft spot is that the abstract gives no such examples or comparisons, so it is hard to judge whether the restriction actually captures a meaningful adversary or simply weakens the guarantee without a clear payoff. The stress-test concern about whether the modeling is accurate and distinct lands because nothing in the provided text shows a mechanism that standard DP forbids but this version permits while still controlling the intended adversary. The citation pattern looks standard for the area and there are no obvious circularities. Readers already working on DP relaxations or on adversary modeling in privacy would get the most out of it; others can wait for the details. The work is coherent enough on its own terms to deserve a serious referee who can check the properties and examples in the full manuscript.

Referee Report

1 major / 0 minor

Summary. The paper introduces capacity bounded differential privacy as a relaxation of differential privacy. The distinguishing adversary is assumed to be capacity-bounded by the function class of its attack algorithm rather than computational power; this is modeled via restricted f-divergences. The work studies properties of the resulting definition and algorithms satisfying it.

Significance. If the restricted-f-divergence modeling is shown to be non-vacuous and to yield guarantees distinct from standard DP and prior relaxations (e.g., approximate or Rényi DP), the definition could enlarge the set of practical mechanisms that still control realistic, capacity-limited adversaries. Concrete function classes and example mechanisms would be needed to establish this utility.

major comments (1)

[Abstract] Abstract: the central modeling claim—that restricting f-divergences to a function class meaningfully captures a capacity-bounded adversary and produces distinct, useful privacy guarantees—remains unillustrated. No concrete function class, mechanism, or comparison showing when the definition permits algorithms forbidden by ε-DP is supplied, leaving the weakest assumption unaddressed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback on our manuscript. We address the major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central modeling claim—that restricting f-divergences to a function class meaningfully captures a capacity-bounded adversary and produces distinct, useful privacy guarantees—remains unillustrated. No concrete function class, mechanism, or comparison showing when the definition permits algorithms forbidden by ε-DP is supplied, leaving the weakest assumption unaddressed.

Authors: We agree that the manuscript would be strengthened by concrete illustrations of the modeling claim. The current version defines capacity-bounded DP via restricted f-divergences and studies its general properties along with algorithms satisfying the definition, but does not supply specific function classes, mechanisms, or direct comparisons to ε-DP. We will revise the manuscript (including the abstract) to incorporate such examples, for instance by adding the class of 1-Lipschitz functions as a capacity bound together with a mechanism whose noise scale depends on this bound, and by including a discussion or table contrasting the resulting guarantees with those of standard DP, approximate DP, and Rényi DP. revision: yes

Circularity Check

0 steps flagged

No circularity; new definition is a self-contained modeling choice

full rationale

The paper defines capacity bounded differential privacy directly as a relaxation using restricted f-divergences to model capacity-bounded adversaries. No derivation chain, equations, or results are shown that reduce a claimed prediction or theorem to a fitted parameter, self-citation, or input by construction. The modeling step is presented as an explicit definitional choice rather than derived from prior quantities, making the central contribution independent of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central contribution is the introduction of a new privacy definition; it rests on standard mathematical properties of f-divergences and the domain assumption that function-class restrictions meaningfully model adversary capacity. No free parameters or invented entities with independent evidence are described in the abstract.

axioms (2)

standard math f-divergences remain well-defined and satisfy standard properties when restricted to a function class.
Core modeling choice for the new definition.
domain assumption Capacity-bounded adversaries can be usefully captured by limiting the function class available for distinguishing distributions.
Foundational premise for the relaxation.

invented entities (1)

Capacity-bounded adversary no independent evidence
purpose: To define a relaxed privacy notion by limiting distinguishing power to a function class.
New conceptual entity introduced to relax standard DP.

pith-pipeline@v0.9.0 · 5647 in / 1212 out tokens · 30360 ms · 2026-05-25T09:48:36.468534+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 8 internal anchors

[1]

Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang

Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 308–318, New York, NY , USA, 2016. ACM

work page 2016
[2]

Generalization and equilibrium in generative adversarial nets (gans)

Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). International Conference on Machine Learning, 2017

work page 2017
[3]

Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069–1109, July 2011

work page 2011
[4]

Families of alpha- beta- and gamma- divergences: Flexible and robust measures of similarities

Andrzej Cichocki and Shun-ichi Amari. Families of alpha- beta- and gamma- divergences: Flexible and robust measures of similarities. Entropy, 12(6):1532–1568, 2010

work page 2010
[5]

Information-type measures of difference of probability distributions and indirect observation

Imre Csiszár. Information-type measures of difference of probability distributions and indirect observation. Studia Sci. Math. Hungary, 2:299–318, 1967

work page 1967
[6]

Preserving Statistical Validity in Adaptive Data Analysis

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Preserv- ing statistical validity in adaptive data analysis. CoRR, abs/1411.2664, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014
[7]

Calibrating noise to sensitivity in private data analysis

Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In In Proceedings of the 3rd Theory of Cryptography Conference, pages 265–284. Springer, 2006

work page 2006
[8]

The algorithmic foundations of differential privacy

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 2014

work page 2014
[9]

A Convex Duality Framework for GANs

Farzan Farnia and David Tse. A convex duality framework for gans. CoRR, abs/1810.11740, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[10]

Generalization for adaptively-chosen estimators via stable median

Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 , volume 65 of Proceedings of Machine Learning Research, pages 728–757. PMLR, 2017

work page 2017
[11]

Limits of computational differential privacy in the client/server setting

Adam Groce, Jonathan Katz, and Arkady Yerukhimovich. Limits of computational differential privacy in the client/server setting. In Proceedings of the 8th Conference on Theory of Cryptography, TCC’11, pages 417–431, 2011

work page 2011
[12]

Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies

Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowﬁsh privacy: Tuning privacy-utility trade-offs using policies. CoRR, abs/1312.3913, 2013

work page internal anchor Pith review Pith/arXiv arXiv 2013
[13]

The extent and consequences of p-hacking in science

Megan L Head, Luke Holman, Rob Lanfear, Andrew T Kahn, and Michael D Jennions. The extent and consequences of p-hacking in science. PLoS biology, 13(3):e1002106, 2015

work page 2015
[14]

Towards an axiomatization of statistical privacy and utility

Daniel Kifer and Bing-Rong Lin. Towards an axiomatization of statistical privacy and utility. InProceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS ’10, pages 147–158, New York, NY , USA, 2010. ACM

work page 2010
[15]

A rigorous and customizable framework for privacy

Daniel Kifer and Ashwin Machanavajjhala. A rigorous and customizable framework for privacy. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 77–88, New York, NY , USA, 2012. ACM

work page 2012
[16]

Pufferﬁsh: A framework for mathematical privacy deﬁnitions

Daniel Kifer and Ashwin Machanavajjhala. Pufferﬁsh: A framework for mathematical privacy deﬁnitions. ACM Trans. Database Syst., 39(1):3, 2014

work page 2014
[17]

Smith, and Abhradeep Thakurta

Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta. Private convex optimization for empirical risk minimization with applications to high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings,...

work page 2012
[18]

Optimizing linear counting queries under differential privacy

Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Jan Paredaens and Dirk Van Gucht, editors,Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 123–134. ACM, 2010

work page 2010
[19]

Optimal error of query sets under the differentially-private matrix mechanism

Chao Li and Gerome Miklau. Measuring the achievable error of query sets under differential privacy. CoRR, abs/1202.3399, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2012
[20]

Approximation and convergence properties of generative adversarial learning

Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence properties of generative adversarial learning. In Advances in Neural Information Processing Systems, pages 5545–5553, 2017

work page 2017
[21]

The Inductive Bias of Restricted f-GANs

Shuang Liu and Kamalika Chaudhuri. The inductive bias of restricted f-gans. arXiv preprint arXiv:1809.04542, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[22]

Optimizing error of high-dimensional statistical queries under differential privacy

Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. CoRR, abs/1808.03537, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[23]

Renyi differential privacy

Ilya Mironov. Renyi differential privacy. In CSF Synposium, 2017

work page 2017
[24]

Computational differential privacy

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’09, pages 126–142, Berlin, Heidelberg, 2009. Springer-Verlag

work page 2009
[25]

Estimating divergence functionals and the likelihood ratio by convex risk minimization.IEEE Transactions on Information Theory, 56(11):5847–5861, 2010

XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization.IEEE Transactions on Information Theory, 56(11):5847–5861, 2010

work page 2010
[26]

f-gan: Training generative neural samplers using variational divergence minimization

Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In D. D. Lee, M. Sugiyama, U. V . Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 271–279. Curran Associates, Inc., 2016

work page 2016
[27]

Russo and J

D. Russo and J. Zou. How much does your data exploration overﬁt? Controlling bias via information usage. arXiv e-prints, November 2015

work page 2015
[28]

A. D. Sarwate and K. Chaudhuri. Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data. IEEE Signal Processing Magazine, 30(5):86–94, Sep. 2013

work page 2013
[29]

Adam D. Smith. Information, privacy and stability in adaptive data analysis. CoRR, abs/1706.00820, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017
[30]

On integral probability metrics, \phi-divergences and binary classification

Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert R. G. Lanckriet, and Bernhard Schölkopf. A note on integral probability metrics and $\phi$-divergences. CoRR, abs/0901.2698, 2009

work page internal anchor Pith review Pith/arXiv arXiv 2009
[31]

Wang, Jing Lei, and Stephen E

Yu-Xiang. Wang, Jing Lei, and Stephen E. Fienberg. On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanisms. arXiv e-prints, May 2016

work page 2016
[32]

On-average kl-privacy and its equivalence to general- ization for max-entropy mechanisms

Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. On-average kl-privacy and its equivalence to general- ization for max-entropy mechanisms. In International Conference on Privacy in Statistical Databases, pages 121–134. Springer, 2016. 10 A Analysis of Gaussian Mechanism (a) Plots of (lin,Renyi ) capacity bounded DP and Renyi-DP parameters for Gaussian mec...

work page 2016
[33]

Suppose the ﬁrst case is true

or (D′ 1,D 2) where the pairsD1,D′ 1 andD2,D′ 2 differ in one row. Suppose the ﬁrst case is true. Then, (P1,P 2) = (A(D1),B (D2)) and (Q1,Q 2) = (A(D1),B (D′ 2)). Importantly, we have P1 = Q1. Then, letting P = P1⊗P2, Q =Q1⊗Q2, anda =α2−α, DH α (P,Q ) = inf P′ Dα(P′,Q ) + sup h∈H EP [h]− EP′[h] ≤ inf P′=P1⊗P′ 2 Dα(P′,Q ) + sup h∈H EP [h]− EP′[h] = inf P′=...

work page
[34]

Then, KLlin(P,Q ) = (µ1−µ2)2 2σ2 2 Proof

and Q =N (µ2,σ 2 2). Then, KLlin(P,Q ) = (µ1−µ2)2 2σ2 2 Proof. By deﬁnition, KLlin(P,Q ) = sup a aµ1− logeaµ2+a2σ2 2/2 = sup a a(µ1−µ2)− 1 2a2σ2 2 Differentiating wrta and setting the derivative to0, the optimum is achieved ata = (µ1−µ2)/σ2 2, at which the optimal value is (µ1−µ2)2/2σ2 2. C.3 Renyi, Unbounded Theorem 11 (Laplace Mechanism underα-Renyi). L...

work page

[1] [1]

Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang

Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 308–318, New York, NY , USA, 2016. ACM

work page 2016

[2] [2]

Generalization and equilibrium in generative adversarial nets (gans)

Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). International Conference on Machine Learning, 2017

work page 2017

[3] [3]

Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069–1109, July 2011

work page 2011

[4] [4]

Families of alpha- beta- and gamma- divergences: Flexible and robust measures of similarities

Andrzej Cichocki and Shun-ichi Amari. Families of alpha- beta- and gamma- divergences: Flexible and robust measures of similarities. Entropy, 12(6):1532–1568, 2010

work page 2010

[5] [5]

Information-type measures of difference of probability distributions and indirect observation

Imre Csiszár. Information-type measures of difference of probability distributions and indirect observation. Studia Sci. Math. Hungary, 2:299–318, 1967

work page 1967

[6] [6]

Preserving Statistical Validity in Adaptive Data Analysis

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Preserv- ing statistical validity in adaptive data analysis. CoRR, abs/1411.2664, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014

[7] [7]

Calibrating noise to sensitivity in private data analysis

Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In In Proceedings of the 3rd Theory of Cryptography Conference, pages 265–284. Springer, 2006

work page 2006

[8] [8]

The algorithmic foundations of differential privacy

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 2014

work page 2014

[9] [9]

A Convex Duality Framework for GANs

Farzan Farnia and David Tse. A convex duality framework for gans. CoRR, abs/1810.11740, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[10] [10]

Generalization for adaptively-chosen estimators via stable median

Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 , volume 65 of Proceedings of Machine Learning Research, pages 728–757. PMLR, 2017

work page 2017

[11] [11]

Limits of computational differential privacy in the client/server setting

Adam Groce, Jonathan Katz, and Arkady Yerukhimovich. Limits of computational differential privacy in the client/server setting. In Proceedings of the 8th Conference on Theory of Cryptography, TCC’11, pages 417–431, 2011

work page 2011

[12] [12]

Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies

Xi He, Ashwin Machanavajjhala, and Bolin Ding. Blowﬁsh privacy: Tuning privacy-utility trade-offs using policies. CoRR, abs/1312.3913, 2013

work page internal anchor Pith review Pith/arXiv arXiv 2013

[13] [13]

The extent and consequences of p-hacking in science

Megan L Head, Luke Holman, Rob Lanfear, Andrew T Kahn, and Michael D Jennions. The extent and consequences of p-hacking in science. PLoS biology, 13(3):e1002106, 2015

work page 2015

[14] [14]

Towards an axiomatization of statistical privacy and utility

Daniel Kifer and Bing-Rong Lin. Towards an axiomatization of statistical privacy and utility. InProceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS ’10, pages 147–158, New York, NY , USA, 2010. ACM

work page 2010

[15] [15]

A rigorous and customizable framework for privacy

Daniel Kifer and Ashwin Machanavajjhala. A rigorous and customizable framework for privacy. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 77–88, New York, NY , USA, 2012. ACM

work page 2012

[16] [16]

Pufferﬁsh: A framework for mathematical privacy deﬁnitions

Daniel Kifer and Ashwin Machanavajjhala. Pufferﬁsh: A framework for mathematical privacy deﬁnitions. ACM Trans. Database Syst., 39(1):3, 2014

work page 2014

[17] [17]

Smith, and Abhradeep Thakurta

Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta. Private convex optimization for empirical risk minimization with applications to high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings,...

work page 2012

[18] [18]

Optimizing linear counting queries under differential privacy

Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Jan Paredaens and Dirk Van Gucht, editors,Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 123–134. ACM, 2010

work page 2010

[19] [19]

Optimal error of query sets under the differentially-private matrix mechanism

Chao Li and Gerome Miklau. Measuring the achievable error of query sets under differential privacy. CoRR, abs/1202.3399, 2012

work page internal anchor Pith review Pith/arXiv arXiv 2012

[20] [20]

Approximation and convergence properties of generative adversarial learning

Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence properties of generative adversarial learning. In Advances in Neural Information Processing Systems, pages 5545–5553, 2017

work page 2017

[21] [21]

The Inductive Bias of Restricted f-GANs

Shuang Liu and Kamalika Chaudhuri. The inductive bias of restricted f-gans. arXiv preprint arXiv:1809.04542, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[22] [22]

Optimizing error of high-dimensional statistical queries under differential privacy

Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. CoRR, abs/1808.03537, 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[23] [23]

Renyi differential privacy

Ilya Mironov. Renyi differential privacy. In CSF Synposium, 2017

work page 2017

[24] [24]

Computational differential privacy

Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’09, pages 126–142, Berlin, Heidelberg, 2009. Springer-Verlag

work page 2009

[25] [25]

Estimating divergence functionals and the likelihood ratio by convex risk minimization.IEEE Transactions on Information Theory, 56(11):5847–5861, 2010

XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization.IEEE Transactions on Information Theory, 56(11):5847–5861, 2010

work page 2010

[26] [26]

f-gan: Training generative neural samplers using variational divergence minimization

Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In D. D. Lee, M. Sugiyama, U. V . Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 271–279. Curran Associates, Inc., 2016

work page 2016

[27] [27]

Russo and J

D. Russo and J. Zou. How much does your data exploration overﬁt? Controlling bias via information usage. arXiv e-prints, November 2015

work page 2015

[28] [28]

A. D. Sarwate and K. Chaudhuri. Signal processing and machine learning with differential privacy: Algorithms and challenges for continuous data. IEEE Signal Processing Magazine, 30(5):86–94, Sep. 2013

work page 2013

[29] [29]

Adam D. Smith. Information, privacy and stability in adaptive data analysis. CoRR, abs/1706.00820, 2017

work page internal anchor Pith review Pith/arXiv arXiv 2017

[30] [30]

On integral probability metrics, \phi-divergences and binary classification

Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert R. G. Lanckriet, and Bernhard Schölkopf. A note on integral probability metrics and $\phi$-divergences. CoRR, abs/0901.2698, 2009

work page internal anchor Pith review Pith/arXiv arXiv 2009

[31] [31]

Wang, Jing Lei, and Stephen E

Yu-Xiang. Wang, Jing Lei, and Stephen E. Fienberg. On-Average KL-Privacy and its equivalence to Generalization for Max-Entropy Mechanisms. arXiv e-prints, May 2016

work page 2016

[32] [32]

On-average kl-privacy and its equivalence to general- ization for max-entropy mechanisms

Yu-Xiang Wang, Jing Lei, and Stephen E Fienberg. On-average kl-privacy and its equivalence to general- ization for max-entropy mechanisms. In International Conference on Privacy in Statistical Databases, pages 121–134. Springer, 2016. 10 A Analysis of Gaussian Mechanism (a) Plots of (lin,Renyi ) capacity bounded DP and Renyi-DP parameters for Gaussian mec...

work page 2016

[33] [33]

Suppose the ﬁrst case is true

or (D′ 1,D 2) where the pairsD1,D′ 1 andD2,D′ 2 differ in one row. Suppose the ﬁrst case is true. Then, (P1,P 2) = (A(D1),B (D2)) and (Q1,Q 2) = (A(D1),B (D′ 2)). Importantly, we have P1 = Q1. Then, letting P = P1⊗P2, Q =Q1⊗Q2, anda =α2−α, DH α (P,Q ) = inf P′ Dα(P′,Q ) + sup h∈H EP [h]− EP′[h] ≤ inf P′=P1⊗P′ 2 Dα(P′,Q ) + sup h∈H EP [h]− EP′[h] = inf P′=...

work page

[34] [34]

Then, KLlin(P,Q ) = (µ1−µ2)2 2σ2 2 Proof

and Q =N (µ2,σ 2 2). Then, KLlin(P,Q ) = (µ1−µ2)2 2σ2 2 Proof. By deﬁnition, KLlin(P,Q ) = sup a aµ1− logeaµ2+a2σ2 2/2 = sup a a(µ1−µ2)− 1 2a2σ2 2 Differentiating wrta and setting the derivative to0, the optimum is achieved ata = (µ1−µ2)/σ2 2, at which the optimal value is (µ1−µ2)2/2σ2 2. C.3 Renyi, Unbounded Theorem 11 (Laplace Mechanism underα-Renyi). L...

work page