arxiv: 2605.02319 · v1 · submitted 2026-05-04 · 💻 cs.CR · cs.IT· math.IT

Recognition: 3 theorem links

· Lean Theorem

Optimal Privacy-Utility Trade-Offs in LDP: Functional and Geometric Perspectives

Seung-Hyun Nam , Hyun-Young Park , Si-Hyeon Lee

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:04 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT

keywords local differential privacyprivacy-utility trade-offBlackwell orderpolytopeoptimal mechanismsBayesian riskminimax riskconvex geometry

0 comments

The pith

Maximal local differential privacy channels map one-to-one onto the vertices of a finite-dimensional polytope.

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

The paper develops a unified framework for finding the best privacy-utility trade-off when data must be released under local differential privacy. It first uses functional properties of risk measures to shrink the set of channels that need to be considered. It then proves that the channels that cannot be improved upon correspond exactly to the vertices of a polytope whose dimension depends only on the size of the data domain. This geometric fact turns the search for optimal channels into a standard vertex-enumeration or linear-programming task that works for any utility goal. When the underlying statistical problem has symmetry, the same geometry produces closed-form expressions without any numerical search.

Core claim

By leveraging the data processing inequality, direct-sum quasi-convexity, concavity, and symmetry invariance of Bayesian and minimax risks, the optimization domain for the optimal privacy-utility trade-off reduces to the maximal LDP channels under the Blackwell order. These maximal channels stand in one-to-one correspondence with the vertices of a finite-dimensional polytope, yielding an exact geometric characterization. The correspondence makes the optimal trade-off computable by vertex enumeration or linear programming and, for problems invariant under a transitive group action, supplies closed-form analytic expressions.

What carries the argument

The one-to-one correspondence between maximal LDP channels under the Blackwell order and the vertices of a finite-dimensional polytope.

If this is right

Optimal privacy-utility trade-offs for arbitrary Bayesian or minimax risks become computable by linear programming or vertex enumeration.
Problems with transitive symmetry admit exact closed-form expressions for the optimal trade-off without numerical optimization.
The same geometric reduction applies when the goal is to maximize mutual information, f-divergences, or Fisher information under LDP.
Known optimal mechanisms for specific tasks such as mean estimation or distribution estimation are recovered as special cases of the polytope vertices.

Where Pith is reading between the lines

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

The polytope view suggests that mechanism design for local privacy can be automated by off-the-shelf convex solvers rather than hand-crafted constructions.
Similar convex-geometric arguments may extend the tractability result to related privacy models such as the shuffle model or central differential privacy.
Verification on a previously unstudied utility such as logistic-regression accuracy would test whether the polytope still captures the optimum.

Load-bearing premise

The data processing inequality, direct-sum quasi-convexity, concavity, and symmetry invariance of Bayesian and minimax risks hold for every utility function considered.

What would settle it

An explicit LDP channel that achieves a strictly better utility than any vertex of the predicted polytope for a concrete estimation or hypothesis-testing task would disprove the claimed bijection.

Figures

Figures reproduced from arXiv: 2605.02319 by Hyun-Young Park, Seung-Hyun Nam, Si-Hyeon Lee.

**Figure 2.** Figure 2: A conceptual visualization of the dimensionality reduction of the optimization domain for view at source ↗

**Figure 1.** Figure 1: Privacy-preserving statistical decision-making scenario and the optimal PUT (details are in view at source ↗

read the original abstract

Local differential privacy (LDP) has emerged as a gold-standard framework for privacy-preserving data analysis. However, characterizing the optimal privacy-utility trade-off (PUT) and the corresponding optimal LDP channels remains largely fragmented, relying on problem-specific, case-by-case analyses. In this work, we develop a unified theoretical framework that systematically characterizes the optimal PUT and optimal LDP channels for general privacy-preserving statistical decision-making problems. We first identify key functional properties of Bayesian and minimax risks as functions of the LDP channel, including the data processing inequality (DPI), direct-sum quasi-convexity (or additivity), concavity, and symmetry invariance. Leveraging these properties, we reduce the optimization domain required to compute the optimal PUT. Additionally, building on convex geometric insights, we establish a one-to-one correspondence between maximal LDP channels under the Blackwell order and a finite-dimensional polytope, yielding an exact geometric characterization. This result renders the optimal PUT computationally tractable via vertex enumeration or linear programming. Furthermore, when the underlying problem exhibits symmetries characterized by a transitive group action, we derive an exact analytic expression for the optimal PUT, leading to closed-form solutions without numerical optimization. Our framework applies broadly beyond risk minimization, encompassing the maximization of information-theoretic measures such as mutual information, $f$-divergences, and Fisher information over LDP channels. We demonstrate the efficacy of our theoretical framework by recovering or strengthening several known results, and deriving exact analytic expressions for the optimal PUTs in specific tasks that were previously unaddressed.

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

This paper maps optimal LDP channels to vertices of a polytope via Blackwell order, turning PUT optimization into LP or vertex enumeration for symmetric cases.

read the letter

The core advance is the geometric reduction: maximal LDP channels under Blackwell order correspond one-to-one with a finite-dimensional polytope, so finding the best privacy-utility point reduces to checking vertices or solving a linear program. They first use standard properties of Bayesian and minimax risks—DPI, direct-sum quasi-convexity, concavity, symmetry invariance—to cut down the search space, then apply the polytope correspondence for tractability. For problems with transitive group symmetries they get closed-form expressions instead of numerical search. The framework also covers maximizing mutual information, f-divergences, and Fisher information under LDP, not just risk minimization. They recover several known results and supply exact expressions for a couple of previously open specific tasks. That part is clean and directly useful if the derivations hold up. The functional properties they invoke are standard in decision theory, so the reductions feel natural rather than forced. The polytope claim is the genuinely new piece; if the correspondence is exact, it explains why some earlier case-by-case solutions looked similar. Soft spots are modest. The abstract does not spell out the dimension of the polytope or how fast vertex enumeration scales, so practical tractability for larger alphabets remains to be checked in the full proofs. The symmetry assumption for closed forms is restrictive but clearly stated, so no overclaim there. No circularity or self-referential definitions appear in the stated program. This is for researchers who design or analyze LDP mechanisms in statistics and machine learning and want a unifying method instead of ad-hoc arguments. It is worth a serious referee because the geometric characterization is new, the reductions are reproducible in principle, and the closed forms for symmetric cases are concrete outputs that others can test. I would bring it to a reading group to walk through the polytope construction and the risk-function lemmas.

Referee Report

2 major / 2 minor

Summary. The paper develops a unified theoretical framework for characterizing optimal privacy-utility trade-offs (PUT) under local differential privacy (LDP) for general statistical decision problems. It first establishes functional properties of Bayesian and minimax risks (DPI, direct-sum quasi-convexity/additivity, concavity, symmetry invariance) to shrink the feasible set of channels, then proves a one-to-one correspondence between maximal LDP channels under the Blackwell order and the vertices of a finite-dimensional polytope, rendering the optimal PUT computable by vertex enumeration or linear programming. Under transitive group symmetries it further derives closed-form analytic expressions. The framework is shown to recover known results and to yield new exact expressions for previously unaddressed tasks, and is extended to maximization of mutual information, f-divergences, and Fisher information.

Significance. If the stated functional properties and the Blackwell-polytope correspondence hold, the work supplies a substantial unification of previously fragmented case-by-case analyses. The geometric reduction to a polytope and the consequent tractability via LP or vertex enumeration constitute a clear methodological advance; the closed-form results under symmetry and the recovery of prior results add credibility. The breadth to non-risk utilities further increases potential impact in privacy-preserving statistics and information theory.

major comments (2)

[§4] §4 (reduction via functional properties): the direct-sum quasi-convexity (or additivity) claim for minimax risk is load-bearing for the domain-reduction step, yet the manuscript provides only a sketch; an explicit verification or counter-example check for non-convex utility functions would be required to confirm that the reduced domain still contains all optima.
[§5] §5 (Blackwell-polytope correspondence): the one-to-one mapping between maximal LDP channels and polytope vertices is central to the tractability claim; the proof must explicitly verify that every vertex corresponds to an extremal channel for arbitrary utility functions, not merely for the risk functions used in the examples.

minor comments (2)

[§2] Notation for the polytope dimension and its relation to the input/output alphabets should be introduced earlier (ideally in §2) to improve readability of the geometric arguments.
A short table summarizing the recovered known results versus the new closed-form expressions would help readers quickly assess the framework's concrete contributions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the precise comments, which help clarify the presentation of our results. We address each major comment below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

Referee: [§4] §4 (reduction via functional properties): the direct-sum quasi-convexity (or additivity) claim for minimax risk is load-bearing for the domain-reduction step, yet the manuscript provides only a sketch; an explicit verification or counter-example check for non-convex utility functions would be required to confirm that the reduced domain still contains all optima.

Authors: We agree that the direct-sum quasi-convexity property for minimax risk is central to the domain reduction and that the manuscript currently offers only a sketch. In the revision we will replace the sketch with a complete, self-contained proof. The argument will explicitly treat general (possibly non-convex) utility functions and verify that every minimax-optimal channel remains inside the reduced domain, thereby confirming that no optima are lost. revision: yes
Referee: [§5] §5 (Blackwell-polytope correspondence): the one-to-one mapping between maximal LDP channels and polytope vertices is central to the tractability claim; the proof must explicitly verify that every vertex corresponds to an extremal channel for arbitrary utility functions, not merely for the risk functions used in the examples.

Authors: The Blackwell order is defined independently of any particular utility: a channel W dominates V if, for every decision problem, the risk achievable with W is at most that achievable with V. Consequently, any channel that is maximal under the Blackwell order is optimal for every utility function. Our geometric argument identifies the vertices of the LDP polytope precisely with these maximal channels. To address the concern directly, the revised §5 will contain an additional paragraph that invokes this definition to state explicitly that the vertex-extremal correspondence holds for arbitrary utilities, not merely the risk functions appearing in the examples. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation builds on standard external properties

full rationale

The paper's chain begins by identifying standard functional properties (DPI, direct-sum quasi-convexity, concavity, symmetry invariance) of Bayesian/minimax risks under LDP channels, then uses them to shrink the feasible set before invoking a Blackwell-order polytope correspondence for tractability. These properties and the Blackwell order are established concepts in decision theory and information theory, not derived from the paper's own fitted values or definitions. The claimed one-to-one correspondence and closed-form solutions under group actions are presented as new results that recover external known cases, with no equations shown reducing a 'prediction' to an input by construction, no load-bearing self-citation chains, and no ansatz smuggled via prior self-work. The framework is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on standard information-theoretic properties of risk functions and the Blackwell order; no new free parameters or invented entities are indicated in the abstract.

axioms (1)

domain assumption Bayesian and minimax risks satisfy data processing inequality, direct-sum quasi-convexity, concavity, and symmetry invariance as functions of the LDP channel.
Invoked to reduce the optimization domain and enable the geometric characterization.

pith-pipeline@v0.9.0 · 5587 in / 1258 out tokens · 82933 ms · 2026-05-08T18:04:31.376130+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Foundation/Atomicity.lean (generic conservation/preservation under serialization) — only superficially analogous; no J-cost or ratio-symmetry content sequential_preserves_conservation unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the optimal Bayesian and minimax risks ... satisfy key functional properties: the data processing inequality (DPI), direct-sum quasi-convexity (or additivity), concavity, and group invariance.
Cost/FunctionalEquation.lean (J(x)=½(x+x⁻¹)−1 is the unique calibrated reciprocal cost; no role here) washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the staircase matrix S_{X,ε} ∈ {1, e^ε}^{B(X)×X} ... extremal ε-LDP channels with weight vector c

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 28 canonical work pages

[1]

doi: 10.1109/SP.2008.33

Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In2008 IEEE Symposium on Security and Privacy (Sp 2008), pages 111–125, May 2008. doi: 10.1109/SP.2008.33

work page doi:10.1109/sp.2008.33 2008
[2]

Model inversion attacks that exploit confidence information and basic countermeasures

Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. InProceedings of the 22nd ACM SIGSAC Conference on Com- puter and Communications Security, CCS ’15, pages 1322–1333, New York, NY , USA, October 2015. Association for Computing Machinery. ISBN 978-1-4503-3832-5. doi: 1...

work page doi:10.1145/2810103.2813677 2015
[3]

Exposed! A survey of attacks on private data.Annual Review of Statistics and Its Application, 4(V olume 4, 2017):61–84, March 2017

Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman. Exposed! A survey of attacks on private data.Annual Review of Statistics and Its Application, 4(V olume 4, 2017):61–84, March 2017. ISSN 2326-8298, 2326-831X. doi: 10.1146/annurev-statistics-060116-054123

work page doi:10.1146/annurev-statistics-060116-054123 2017
[4]

Inverting gradients - How easy is it to break privacy in federated learning? InAdvances in Neural Information Processing Systems, volume 33, pages 16937–16947

Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients - How easy is it to break privacy in federated learning? InAdvances in Neural Information Processing Systems, volume 33, pages 16937–16947. Curran Associates, Inc., 2020

2020
[5]

URL https://doi.org/10.1137/090756090

Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately?SIAM Journal on Computing, 40(3):793–826, January 2011. ISSN 0097-5397, 1095-7111. doi: 10.1137/090756090

work page doi:10.1137/090756090 2011
[6]

The algorithmic foundations of differential privacy

Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.FNT in Theoretical Computer Science, 9(3-4):211–407, 2013. ISSN 1551-305X, 1551-3068. doi: 10.1561/0400000042

work page doi:10.1561/0400000042 2013
[7]

URLhttps://doi.org/10.1109/FOCS.2013.53

John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438, Berkeley, CA, USA, October 2013. IEEE. ISBN 978-0-7695-5135-7. doi: 10.1109/FOCS.2013.53

work page doi:10.1109/focs.2013.53 2013
[8]

Wagner, and Sudeep Kamath

Ibrahim Issa, Aaron B. Wagner, and Sudeep Kamath. An operational approach to information leakage. IEEE Transactions on Information Theory, 66(3):1625–1657, March 2020. ISSN 0018-9448, 1557-9654. doi: 10.1109/TIT.2019.2962804

work page doi:10.1109/tit.2019.2962804 2020
[9]

2006 , isbn =

Cynthia Dwork. Differential privacy. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors,Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-35908-1. doi: 10.1007/11787006_1

work page doi:10.1007/11787006_1 2006
[10]

Universally utility-maximizing privacy mechanisms

Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. InProceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, pages 351–360, New York, NY , USA, May 2009. Association for Computing Machinery. ISBN 978-1-60558-506-2. doi: 10.1145/1536414.1536464

work page doi:10.1145/1536414.1536464 2009
[11]

Maharaj, Code Construction on Fiber Products of Kummer Covers, IEEE Transactions on Information Theory 50 (9) (2004) 2169–2173.doi:10.1109/TIT

Quan Geng and Pramod Viswanath. The optimal noise-adding mechanism in differential privacy.IEEE Transactions on Information Theory, 62(2):925–951, February 2016. ISSN 1557-9654. doi: 10.1109/TIT. 2015.2504967

work page doi:10.1109/tit 2016
[12]

Extremal mechanisms for local differential privacy

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Journal of Machine Learning Research, 17(17):1–51, 2016. ISSN 1533-7928

2016
[13]

Optimal schemes for discrete distribution estimation under locally differential privacy.IEEE Transactions on Information Theory, 64(8):5662–5676, August 2018

Min Ye and Alexander Barg. Optimal schemes for discrete distribution estimation under locally differential privacy.IEEE Transactions on Information Theory, 64(8):5662–5676, August 2018. ISSN 0018-9448, 1557-9654. doi: 10.1109/TIT.2018.2809790

work page doi:10.1109/tit.2018.2809790 2018
[14]

Hadamard response: Estimating distributions privately, efficiently, and with little communication

Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. InProceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, pages 1120–1129. PMLR, April 2019. 10

2019
[15]

Local differential private data aggregation for discrete distribution estimation.IEEE Transactions on Parallel and Distributed Systems, 30(9):2046–2059, September 2019

Shaowei Wang, Liusheng Huang, Yiwen Nie, Xinyuan Zhang, Pengzhan Wang, Hongli Xu, and Wei Yang. Local differential private data aggregation for discrete distribution estimation.IEEE Transactions on Parallel and Distributed Systems, 30(9):2046–2059, September 2019. ISSN 1558-2183. doi: 10.1109/ TPDS.2019.2899097

work page arXiv 2046
[16]

Breaking the communication-privacy-accuracy trilemma

Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. Breaking the communication-privacy-accuracy trilemma. InAdvances in Neural Information Processing Systems, volume 33, pages 3312–3324. Curran Associates, Inc., 2020

2020
[17]

Fisher information under local differential privacy

Leighton Pate Barnes, Wei-Ning Chen, and Ayfer Özgür. Fisher information under local differential privacy. IEEE Journal on Selected Areas in Information Theory, 1(3):645–659, November 2020. ISSN 2641-8770. doi: 10.1109/JSAIT.2020.3039461

work page doi:10.1109/jsait.2020.3039461 2020
[18]

Optimal algorithms for mean estimation under local differential privacy

Hilal Asi, Vitaly Feldman, and Kunal Talwar. Optimal algorithms for mean estimation under local differential privacy. InProceedings of the 39th International Conference on Machine Learning, pages 1046–1056. PMLR, June 2022

2022
[19]

Exactly optimal and communication-efficient private estimation via block designs.IEEE Journal on Selected Areas in Information Theory, 5:123–134,

Hyun-Young Park, Seung-Hyun Nam, and Si-Hyeon Lee. Exactly optimal and communication-efficient private estimation via block designs.IEEE Journal on Selected Areas in Information Theory, 5:123–134,
[20]

doi: 10.1109/JSAIT.2024.3381195

ISSN 2641-8770. doi: 10.1109/JSAIT.2024.3381195

work page doi:10.1109/jsait.2024.3381195 2024
[21]

Achieving the exactly optimal privacy-utility trade-off with low communication cost via shared randomness.IEEE Transactions on Information Theory, 70(10):7447–7462, October 2024

Seung-Hyun Nam, Hyun-Young Park, and Si-Hyeon Lee. Achieving the exactly optimal privacy-utility trade-off with low communication cost via shared randomness.IEEE Transactions on Information Theory, 70(10):7447–7462, October 2024. ISSN 1557-9654. doi: 10.1109/TIT.2024.3448475

work page doi:10.1109/tit.2024.3448475 2024
[22]

Seung-Hyun Nam, Vincent Y . F. Tan, and Si-Hyeon Lee. Optimal private discrete distribution estimation with 1-bit communication.IEEE Transactions on Information Forensics and Security, 19:6514–6528, 2024. ISSN 1556-6021. doi: 10.1109/TIFS.2024.3419721

work page doi:10.1109/tifs.2024.3419721 2024
[23]

Exactly minimax-optimal locally differentially private sampling.Advances in Neural Information Processing Systems, 37:10274–10319, December 2024

Hyun-Young Park, Shahab Asoodeh, and Si-Hyeon Lee. Exactly minimax-optimal locally differentially private sampling.Advances in Neural Information Processing Systems, 37:10274–10319, December 2024. doi: 10.52202/079017-0329

work page doi:10.52202/079017-0329 2024
[24]

Efficient estimation of a Gaussian mean with local differential privacy

Kalinin Nikita and Lukas Steinberger. Efficient estimation of a Gaussian mean with local differential privacy. InProceedings of The 28th International Conference on Artificial Intelligence and Statistics, pages 118–126. PMLR, April 2025

2025
[25]

Fundamental limit of discrete distribution estimation under utility-optimized local differential privacy.arXiv preprint arXiv:2509.24173, September 2025

Sun-Moon Yoon, Hyun-Young Park, Seung-Hyun Nam, and Si-Hyeon Lee. Fundamental limit of discrete distribution estimation under utility-optimized local differential privacy.arXiv preprint arXiv:2509.24173, September 2025

work page arXiv 2025
[26]

Necessity of block designs for optimal locally private distribution estimation

Abigail Gentle. Necessity of block designs for optimal locally private distribution estimation. In2025 IEEE Information Theory Workshop (ITW), pages 1–6, September 2025. doi: 10.1109/ITW62417.2025. 11240420

work page doi:10.1109/itw62417.2025 2025
[27]

Quantum advantage in locally differentially private hypothesis testing.arXiv preprint arXiv:2501.10152, August 2025

Seung-Hyun Nam, Hyun-Young Park, Joonwoo Bae, and Si-Hyeon Lee. Quantum advantage in locally differentially private hypothesis testing.arXiv preprint arXiv:2501.10152, August 2025

work page arXiv 2025
[28]

On the role of symmetry for staircase mechanisms in local differential privacy efficiency across different privacy regimes.arXiv preprint arXiv:2603.27572, March 2026

Chiara Amorino and Arnaud Gloter. On the role of symmetry for staircase mechanisms in local differential privacy efficiency across different privacy regimes.arXiv preprint arXiv:2603.27572, March 2026

work page arXiv 2026
[29]

Optimality of staircase mechanisms for vector queries under differential privacy.arXiv preprint arXiv:2601.14597, January 2026

James Melbourne, Mario Diaz, and Shahab Asoodeh. Optimality of staircase mechanisms for vector queries under differential privacy.arXiv preprint arXiv:2601.14597, January 2026

work page arXiv 2026
[30]

Leith, and Oliver Mason

Naoise Holohan, Douglas J. Leith, and Oliver Mason. Extreme points of the local differential privacy polytope.Linear Algebra and its Applications, 534:78–96, December 2017. ISSN 00243795. doi: 10.1016/j.laa.2017.08.011

work page doi:10.1016/j.laa.2017.08.011 2017
[31]

Shahab Asoodeh, Maryam Aliakbarpour, and Flavio P. Calmon. Local differential privacy is equivalent to contraction of an f-divergence. In2021 IEEE International Symposium on Information Theory (ISIT), pages 545–550, July 2021. doi: 10.1109/ISIT45174.2021.9517999

work page doi:10.1109/isit45174.2021.9517999 2021
[32]

Comparison of experiments

David Blackwell. Comparison of experiments. InProceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, volume 2, pages 93–103. University of California Press, January 1951

1951
[33]

Academic Press,

Thomas Shelburne Ferguson.Mathematical Statistics: A Decision Theoretic Approach. Academic Press,
[34]

ISBN 978-0-12-253750-9. 11
[35]

On Optimum Recognition Error and Reject Tradeoff

James O. Berger.Statistical Decision Theory and Bayesian Analysis. Springer Series in Statistics. Springer, New York, NY , 1985. ISBN 978-1-4419-3074-3 978-1-4757-4286-2. doi: 10.1007/978-1-4757-4286-2

work page doi:10.1007/978-1-4757-4286-2 1985
[36]

Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, March 1965. ISSN 0162-1459. doi: 10.1080/01621459.1965.10480775

work page doi:10.1080/01621459.1965.10480775 1965
[37]

Athena Scientific, 1st edition, January 1997

Dimitris Bertsimas and John Tsitsiklis.Introduction to Linear Optimization. Athena Scientific, 1st edition, January 1997. ISBN 978-1-886529-19-9

1997
[38]

Graduate Texts in Mathematics, 152

Günter M. Ziegler.Lectures on Polytopes, volume 152 ofGraduate Texts in Mathematics. Springer, New York, NY , 1995. ISBN 978-0-387-94365-7 978-1-4613-8431-1. doi: 10.1007/978-1-4613-8431-1

work page doi:10.1007/978-1-4613-8431-1 1995
[39]

Tyrrell Rockafellar.Convex Analysis

R. Tyrrell Rockafellar.Convex Analysis. Princeton University Press, January 1997. ISBN 978-0-691- 01586-6

1997
[40]

Theory of Point Estimation

Erich L. Lehmann and George Casella.Theory of Point Estimation. Springer Texts in Statistics. Springer- Verlag, New York, 1998. ISBN 978-0-387-98502-2. doi: 10.1007/b98854. 12 A Convex Geometry We characterize maximal LDP channels using convex-geometric approaches. For a comprehensive treatment of the concepts in this subsection, we refer the reader to st...

work page doi:10.1007/b98854 1998
[41]

Then,Q∼Q ′

Relabeling: Let Q∈ P(X → Y 1), ϕ:Y 1 → Y2 be a bijection, and Q′ ∈ P(X → Y 2) be the induced channel defined byQ ′ y,x =Q ϕ−1(y),x. Then,Q∼Q ′
[42]

Then,Q⊕0 Y2,X ∼Q

Zero-padding: LetQ∈ P(X → Y 1)and letY 2 be a finite set. Then,Q⊕0 Y2,X ∼Q. 15
[43]

For any giveny 0 ∈ Yandλ∈[0,1], we have Q∼(⊕ y∈Y\{y 0}Qy,∗)⊕(λQ y0)⊕((1−λ)Q y0).(55) We omit the proof of the above lemma since it is easy to check

Row-splitting: LetQ∈ P(X → Y). For any giveny 0 ∈ Yandλ∈[0,1], we have Q∼(⊕ y∈Y\{y 0}Qy,∗)⊕(λQ y0)⊕((1−λ)Q y0).(55) We omit the proof of the above lemma since it is easy to check. Now, we prove Proposition B.3. Proof of Proposition B.3. (⇒) From Proposition A.3, there are a finite number of extreme rays of KX,ϵ , sayR(v 1), . . . ,R(vl). For everyy, there...
[44]

1 m m−1X x=0 (SX,ϵ )y,x 1− γ 2 cos 2πx m −a # (101) = X y∈O wO Z 2π 0 PA|Y (da|y)

Thus, u is also constant on X \ Z . Let uz =k for z /∈ Z. It follows that uz′ =ke ϵ for z′ ∈ Z . Therefore, u= (k/c)v , meaning u is proportional to v. Hence, we conclude that ker T (v) X,ϵ = span ({v}). (⇒) Leta= min x vx andb= max x vx, and define W={x∈ X:v x =a},Z={x∈ X:v x =b}.(65) It can be checked that vx >0 for all x∈ X , meaning both W and Z are n...