Pith. sign in

REVIEW 3 major objections 4 minor 50 references

Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes the exact asymptotic privacy–utility tradeoff for discrete distribution estimation under utility-optimized local differential privacy, giving the precise worst-case mean-squared-error constant as the value of a finite-

desk verdict Real advance on the exact ULDP constant, but equation (58) has an inverted trace identity that must be fixed before the converse proof is credible. read the letter →

arxiv 2509.24173 v1 pith:J54OXQYU submitted 2025-09-29 cs.CR cs.ITmath.IT

Sun-Moon Yoon , Hyun-Young Park , Seung-Hyun Nam , Si-Hyeon Lee This is my paper · ORCID
classification cs.CRcs.ITmath.IT MSC 62B1062F1268P27
keywords localdifferentialprivacyutility-optimizeddiscretedistributionestimationprivacy-utilitytradeoffCramér-Raolowerboundblockdesignminimaxsaddle-pointoptimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims to settle the exact asymptotic privacy–utility tradeoff for discrete distribution estimation under utility-optimized local differential privacy (ULDP), where only some categories are sensitive. It characterizes the optimal worst-case mean squared error (scaled by n) as the value of a finite-dimensional concave–convex saddle-point problem, sup over alpha and inf over t of M(alpha,t), with M a sum of three terms corresponding to estimating the relative frequencies over sensitive categories, the relative frequencies over non-sensitive categories, and the total sensitive mass. The converse builds on a uniform asymptotic Cramér–Rao lower bound and a reduction to a newly defined class of extremal ULDP mechanisms. The achievability side constructs utility-optimized block design (uBD) schemes that mix multiple block design mechanisms and use score-based linear estimators. If correct, this gives the exact leading constant for all w>v and epsilon>0, resolving an open gap left by earlier order-optimal and rate-optimal results.

What carries the argument

The load-bearing object is the saddle-point function M(alpha,t) — the sum of three Fisher-information terms M1, M2, M3 — together with two structural results: a uniform asymptotic Cramér–Rao lower bound (Theorem 7) that upgrades pointwise CRLB to a uniform bound over a compact degrading class, and a reduction (Theorem 8) showing that every ULDP mechanism is degraded by an extremal ULDP mechanism whose protected outputs follow the staircase pattern matrix. The achievability side is built from uBD schemes, which mix block design mechanisms with proportions t_k and use a score-based linear estimator derived from the same H1⊕H2⊕H3 decomposition of the tangent space.

What would settle it

Construct a ULDP mechanism whose protected-output matrix is not dominated by the staircase pattern and show that none of its rows can be written as a convex combination of extremal-ULDP rows; if such a mechanism exists, Theorem 8 fails and the converse bound (49) collapses. Alternatively, for a specific (w,v,epsilon) in the intermediate regime, solve the saddle-point problem and exhibit a ULDP estimator scheme whose asymptotic error is strictly smaller than M(alpha*,t*), a direct counterexample to Theorem 3.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 3: for w>v and epsilon>0, the asymptotically optimal worst-case mean squared error (scaled by n) equals sup_{alpha in [0,1]} inf_{t in Delta_v} M(alpha,t), where M is the sum of the three terms in (24)–(26). Each term is the Cramér–Rao lower bound for one component of a decomposition of the unknown distribution: the relative values over sensitive categories, the relative values over non-sensitive categories, and the total probability of sensitive data. Since M is concave–convex on a compact domain, the sup-inf is a genuine saddle-point value, and Corollary 12 shows that a uBD scheme built from a saddle point (alpha*, t*) attains this value. Thus the formula i

Load-bearing premise

The converse lower bound rests on Theorem 8's claim that every ULDP mechanism can be simulated by post-processing some extremal ULDP mechanism; if a single ULDP mechanism escapes this reduction, the claimed minimax constant could be lower than the formula predicts.

Editorial extensions

If this is right

  • For any (w,v,epsilon), the optimal leading constant becomes computable: it is the value of a finite-dimensional concave–convex saddle-point problem solvable by standard convex optimization solvers.
  • In the Case (a) regime of Theorem 4, the earlier uRR scheme is asymptotically optimal, giving the first proof of optimality for uRR in any regime.
  • In the Case (b) regime (v≥4 and epsilon below E(v,1)), the previously proposed uSS scheme is strictly suboptimal, so the uBD class genuinely improves on known schemes.
  • In that same Case (b), the optimal error equals the LDP-only error on the v sensitive categories, meaning the non-sensitive categories can be disclosed at no asymptotic privacy cost (Remark 3).
  • In several regimes the optimal uBD scheme can be implemented with only log2 w bits of communication per client, the minimum needed for consistent estimation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the numerical observation that the optimal mixture t* concentrates on k=1 and k=2 in the intermediate regime suggests a structural conjecture — optimal extremal ULDP mechanisms may only need to mix two block designs — which, if proven, would simplify implementation and sharpen Theorem 4.
  • Editorial extension: the same template — uniform asymptotic CRLB plus an extremal-mechanism reduction plus distribution decomposition — should transfer to neighboring models such as (epsilon,delta)-ULDP, high-low LDP, or input-discriminative LDP; the H1,H2,H3 split indicates that the minimax error separates into per-component Fisher terms in these settings too.
  • Editorial extension: the exact constants have finite-sample consequences: for fixed n, the optimal unbiased scheme has error R1(Q,hat P)/n with R1 exactly characterized, so practitioners can choose (alpha,t) by the same saddle-point computation rather than by tuning heuristics.
  • Editorial extension: the paper leaves open a complete closed form in the intermediate regime epsilon in (epsilon_L, epsilon_H); an analytic characterization there would complete the story and could reveal whether the two-point support of t* is exact.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies discrete distribution estimation under utility-optimized local differential privacy (ULDP). Its main claim is a complete characterization of the asymptotic minimax mean-squared-error constant: for all w > v >= 1 and epsilon > 0, M*(w,v,epsilon) = sup_{alpha in [0,1]} inf_{t in Delta_v} M(alpha,t), where M is the sum of the three components in (24)-(26). The converse is built from a uniform asymptotic Cramer-Rao lower bound, a reduction of the ULDP class to a newly defined class of extremal ULDP mechanisms, and a decomposition of the distribution space into three orthogonal subspaces. The achievability side introduces utility-optimized block design (uBD) schemes, mixing block-design mechanisms and using score-based linear estimators, and proves that an optimized uBD scheme attains the saddle-point value. Closed-form saddle points are given in some regimes, identifying when uRR is optimal and when uSS is strictly suboptimal, and numerical experiments on ACS data support the theoretical results.

Significance. If correct, this is a substantial result: it gives the exact leading constant of the privacy-utility tradeoff under ULDP for all w > v and epsilon > 0, closing a gap left by prior order-optimal analyses. The authors make several genuinely useful technical contributions: a uniform asymptotic CRLB that is not tied to LDP-specific structure, a reduction to extremal ULDP mechanisms that makes the minimax problem finite-dimensional, and an explicit concave-convex saddle-point optimization formulation. The proposed uBD schemes are constructive and the paper includes reproducible code for the experiments. However, the main converse proof as printed contains a load-bearing algebraic inversion in the trace identity used in Proposition 9; this must be corrected and the surrounding calculations updated before the central claim can be considered verified.

major comments (3)
  1. [§V-C, Eq. (58)] The identity as printed is inverted. Combining tr(B_i)=d_i^2 M_i(alpha,t(Q)) with the preceding AM-HM inequality tr^{-1}(B_i) >= d_i^2/tr(B_i) gives tr^{-1}(B_i) >= 1/M_i, not M_i, so the desired bound (59) does not follow. A numerical check for v=2, w=3, epsilon=ln 2, alpha=1/2, t=delta(1;v) gives M_3=15/8 from (26), while Table I and (102)-(108) give tr(B_3)=8/15=1/M_3. The corrected identity tr(B_i)=d_i^2/M_i restores the AM-HM step. Please fix (58) and the surrounding calculation in Appendix C-F, or re-derive independently; as printed, Proposition 9 is internally inconsistent.
  2. [Appendix B] The saddle-point existence proof is not rigorous as written. The text sets dom(M)=[0,1] x (Delta_v \ {delta(v;v)}) and then claims M is continuous everywhere in [0,1] x Delta_v and invokes Sion's theorem on the compact set [0,1]. But M_1(alpha,delta(v;v))=infinity, so M is not real-valued continuous there, and Delta_v \ {delta(v;v)} is not compact. Since Corollary 12 relies on existence of a saddle point, please replace this paragraph by an extended-real or restricted-domain minimax argument (e.g., lower semicontinuity on the compact simplex) or prove directly that the t-minimizer avoids the singular vertex.
  3. [Appendix C-D / Theorem 8] The reduction of all ULDP mechanisms to extremal mechanisms is the load-bearing step for the uniform-CRLB lower bound (49), but the proof is highly compressed. The conic-hull decomposition of an arbitrary protected column via (90)-(91) and the verification that the gamma defined in (93) satisfies the normalization (48) are asserted rather than derived. Please expand these steps; a gap here would invalidate the converse bound even after the trace-identity correction.
minor comments (4)
  1. [§V-A, Eqs. (39)-(42)] The prior term changes notation from pi^2 n^{1/2} I in (39) to pi^2 n^{-1/2} I in (42). Please align these expressions with the Bayesian CRLB convention used.
  2. [Definition 10] The continuous extension of the estimator at alpha=0,1 is left implicit. For reproducibility, give the explicit limiting formula, especially in the cases where M_i(alpha,t) is singular.
  3. [Definition 8 / Fig. 3] The quantity f(gamma)=1-sum_{y' in Y_P} gamma(y') is used in the display and figure before being formally named. Define it in Definition 8.
  4. [Table I] The table is dense; a short sentence explaining the column grouping, particularly the Y_I columns for x in y versus x not in y, would improve readability.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the saddle-point value is derived through a proved extremal-mechanism reduction and a matching uBD construction; only minor non-load-bearing self-citations appear.

full rationale

The derivation of Theorem 3 is self-contained. The converse lower bound is built on Theorem 7 (uniform asymptotic CRLB), proved in the paper, and Theorem 8, which reduces all ULDP mechanisms to extremal ULDP mechanisms through a conic-hull post-processing argument in Appendix C-D rather than by an unproved uniqueness theorem. Proposition 9 then links the Fisher-information traces to the M_i terms. The trace identity (58) appears inverted as printed, which is a correctness/typo concern rather than a circularity; the intended AM-HM step gives the sum M(alpha,t). On the achievability side, the uBD estimator (63) uses coefficients M_i/d_i obtained from the same Fisher-information computation; this is CRLB matching, not fitting. Proposition 11 and Corollary 12 close the bound. References [29] and [30] are self-authored but independent published tools (block-design optimality under LDP and a score-based linear estimator) that do not assume the ULDP result; the paper re-derives the needed identities in Appendices D-E. No 'prediction' reduces by construction to an input.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard statistical and combinatorial facts plus the paper's own lengthy proof machinery. I found no fitted free parameters or invented physical entities. The optimization variables alpha and t are design parameters chosen by the saddle-point problem, not parameters fitted to data, so they are not counted as free parameters. The main external inputs are the uniform CRLB toolkit, block-design existence, the conic-hull lemma for LDP, and Sion's theorem.

assumptions (5)
  • standard math The standard asymptotic Cramer-Rao lower bound and local asymptotic normality machinery from [32]-[34] can be made uniform over a compact class of mechanisms.
    Theorem 7 is the main converse engine and directly relies on the Bayesian CRLB argument in [32, Section 29.1].
  • domain assumption The conic-hull characterization of protected LDP output columns, borrowed from [11, Lemma 12], is valid.
    Theorem 8 uses it to represent every protected-output column of a ULDP mechanism as a conical combination of staircase vectors.
  • standard math Complete block designs exist for every v and k with k <= v.
    Remark 2 and Definition 9 need a (v, choose(v,k), choose(v-1,k-1), k, choose(v-2,k-2)) block design for every k; existence is cited to [35].
  • standard math Sion's minimax theorem applies to the concave-convex function M on [0,1] x simplex.
    Appendix B uses Sion's theorem [46] to assert existence of a saddle point, which is needed for Corollary 12 and the closed-form cases.
  • domain assumption The ULDP model with protected and invertible outputs, i.i.d. samples from a finite alphabet, and worst-case mean squared error captures the intended setting.
    Definition 1 and equations (4)-(9) fix the model. The result is specific to ULDP with a known partition into sensitive and non-sensitive categories, not to general privacy definitions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy." pith.science (2026). https://pith.science/paper/J54OXQYU

@misc{pith2026250924173,
  author       = {Pith},
  title        = {Pith review of: Fundamental Limit of Discrete Distribution Estimation under Utility-Optimized Local Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/J54OXQYU}},
  note         = {Machine review of arXiv:2509.24173}
}
read the original abstract

We study the problem of discrete distribution estimation under utility-optimized local differential privacy (ULDP), which enforces local differential privacy (LDP) on sensitive data while allowing more accurate inference on non-sensitive data. In this setting, we completely characterize the fundamental privacy-utility trade-off. The converse proof builds on several key ideas, including a generalized uniform asymptotic Cram\'er-Rao lower bound, a reduction showing that it suffices to consider a newly defined class of extremal ULDP mechanisms, and a novel distribution decomposition technique tailored to ULDP constraints. For the achievability, we propose a class of utility-optimized block design (uBD) schemes, obtained as nontrivial modifications of the block design mechanism known to be optimal under standard LDP constraints, while incorporating the distribution decomposition idea used in the converse proof and a score-based linear estimator. These results provide a tight characterization of the estimation accuracy achievable under ULDP and reveal new insights into the structure of optimal mechanisms for privacy-preserving statistical inference.

Figures

Figures reproduced from arXiv: 2509.24173 by the authors.

Figure 1
Figure 1. Comparison between two binary randomized response [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Overview of system model. X = [w] for w ∈ N≥2, we identify P(X ) with the probability simplex, ∆w := ( P ∈ R w : Xw x=1 Px = 1 and ∀x ∈ [w], Px ≥ 0 ) . (1) The relative interior of ∆w is ∆◦ w := {P ∈ ∆w : Px > 0, ∀x ∈ [w]}, (2) and its direction space is ∆⃗ w := ( h ∈ R w : Xw x=1 hx = 0) . (3) For x ∈ [w], we write δ (x;w) ∈ ∆w for the point mass at x, i.e., δ (x;w) x′ = 1(x = x ′ ). For a conditional distribution … view at source ↗
Figure 3
Figure 3. Visualization of staircase pattern matrix and extremal [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Visualization of (5, 3, ϵ, t)-uBD mechanism. A. Construction of uBD Schemes a) Privacy mechanism: We first propose a uBD mecha￾nism which perturbs the data. To construct a uBD mechanism, we first prepare a collection of block design mechanisms (Q(k) : [v] → P(2[v] ))k∈…
Figure 5
Figure 5. Figure 5: ϵ vs. PUT where (w, v) = (277, 35). (a) ϵ ∈ [0.1, ϵL] (b) ϵ ∈ [ϵL, ϵH] (c) ϵ ∈ [ϵH, 10] [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: ϵ vs. PUT where (w, v) = (277, 253). (a) (w, v) = (277, 35) (b) (w, v) = (277, 253) [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: ϵ vs. t ∗ i , where the vertical lines represent ϵL and ϵH. throughout ϵ ∈ (ϵL, ϵH). The MATLAB codes for experiments are available at https://github.com/phy811/uBD. VIII. CONCLUSION In this paper, we characterized the optimal PUT for discrete distribution estimation u…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 3 linked inside Pith

  1. [29]

    Exactly optimal and communication-efficient private estimation via block designs,

    H.-Y . Park, S.-H. Nam, and S.-H. Lee, “Exactly optimal and communication-efficient private estimation via block designs,”IEEE J. Select. Areas Inf. Theory, vol. 5, pp. 123–134, 2024

    2024

  2. [30]

    Optimal private discrete distribution estimation with 1-bit communication,

    S.-H. Nam, V . Y . F. Tan, and S.-H. Lee, “Optimal private discrete distribution estimation with 1-bit communication,”IEEE Trans. Inf. Forensics Security, vol. 19, pp. 6514–6528, 2024

    2024

  3. [1]

    What can we learn privately?,

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?,”SIAM J. Comput., vol. 40, no. 3, pp. 793–826, 2011

    2011

  4. [2]

    Local privacy and statistical minimax rates,

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” inProc. IEEE 54th Annu. Symp. Found. Comput. Sci., pp. 429–438, 2013

    2013

  5. [3]

    The algorithmic foundations of differential privacy,

    C. Dwork, A. Roth,et al., “The algorithmic foundations of differential privacy,”Foundations and Trends® Theoretical Comput. Sci., vol. 9, no. 3–4, pp. 211–407, 2014

    2014

  6. [4]

    Collecting telemetry data privately,

    B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” inProc. Adv. Neural Inf. Process. Syst., vol. 30, 2017

    2017

  7. [5]

    Learning with privacy at scale

    Apple Differential Privacy Team, “Learning with privacy at scale.” Apple Machine Learning Research, Dec. 2017

    2017

  8. [6]

    Understanding aggregate trends for apple intelligence using differential privacy

    Apple Machine Learning Research, “Understanding aggregate trends for apple intelligence using differential privacy.” Apple Machine Learning Research blog, Apr. 2025

    2025

Show all 50 references
  1. [7]

    RAPPOR: Randomized aggregatable privacy-preserving ordinal response,

    ´U. Erlingsson, V . Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,” inProc. 2014 ACM SIGSAC Conf. Comput. Commun. Secur., pp. 1054–1067, 2014

    2014

  2. [8]

    Prochlo: Strong privacy for analytics in the crowd,

    A. Bittau, ´U. Erlingsson, P. Maniatis, I. Mironov, A. Raghunathan, D. Lie, M. Rudominer, U. Kode, J. Tinnes, and B. Seefeld, “Prochlo: Strong privacy for analytics in the crowd,” inProc. 26th Symp. Operating Syst. Princ., pp. 441–459, 2017

    2017

  3. [9]

    An operational approach to information leakage,

    I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,”IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1625– 1657, 2020

    2020

  4. [10]

    Randomized response: A survey technique for eliminating evasive answer bias,

    S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,”J. Am. Stat. Assoc., vol. 60, no. 309, pp. 63–69, 1965

    1965

  5. [11]

    Optimal schemes for discrete distribution estima- tion under locally differential privacy,

    M. Ye and A. Barg, “Optimal schemes for discrete distribution estima- tion under locally differential privacy,”IEEE Trans. Inf. Theory, vol. 64, no. 8, pp. 5662–5676, 2018

    2018

  6. [12]

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

    J. Acharya, Z. Sun, and H. Zhang, “Hadamard response: Estimating distributions privately, efficiently, and with little communication,” in Proc. 22nd Int. Conf. Artif. Intell. Stat., pp. 1120–1129, 2019

    2019

  7. [13]

    Private frequency estimation via projective geometry,

    V . Feldman, J. Nelson, H. Nguyen, and K. Talwar, “Private frequency estimation via projective geometry,” inProc. 39th Int. Conf. Mach. Learn., pp. 6418–6433, 2022

    2022

  8. [14]

    Locally differentially private protocols for frequency estimation,

    T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” inProc. 26th USENIX Secur. Symp. (USENIX Secur. 17), pp. 729–745, 2017

    2017

  9. [15]

    Utility-optimized local differential privacy mechanisms for distribution estimation,

    T. Murakami and Y . Kawamoto, “Utility-optimized local differential privacy mechanisms for distribution estimation,” inProc. 28th USENIX Secur. Symp. (USENIX Secur. 19), pp. 1877–1894, 2019

    2019

  10. [16]

    An alternative randomized response proce- dure,

    N. Mangat and R. Singh, “An alternative randomized response proce- dure,”Biometrika, vol. 77, no. 2, pp. 439–442, 1990

    1990

  11. [17]

    Context aware local differential privacy,

    J. Acharya, K. Bonawitz, P. Kairouz, D. Ramage, and Z. Sun, “Context aware local differential privacy,” inProc. 37th Int. Conf. Mach. Learn., pp. 52–62, 2020

    2020

  12. [18]

    Frequency estimation mech- anisms under(ϵ, δ)-utility-optimized local differential privacy,

    Y . Zhang, Y . Zhu, Y . Zhou, and J. Yuan, “Frequency estimation mech- anisms under(ϵ, δ)-utility-optimized local differential privacy,”IEEE Trans. Emerg. Topics Comput., vol. 12, no. 1, pp. 316–327, 2024

    2024

  13. [19]

    Mean estimation of numerical data under(ϵ, δ)-utility-optimized local differential privacy,

    Y . Zhang, Y . Zhu, S. Wang, and X. Huang, “Mean estimation of numerical data under(ϵ, δ)-utility-optimized local differential privacy,” IEEE Trans. Inf. Forensics Security, 2024

    2024

  14. [20]

    Providing input-discriminative protection for local differential privacy,

    X. Gu, M. Li, L. Xiong, and Y . Cao, “Providing input-discriminative protection for local differential privacy,” inProc. IEEE 36th Int. Conf. Data Eng. (ICDE), pp. 505–516, 2020

    2020

  15. [21]

    Automatic tuning of privacy budgets in input-discriminative local differential privacy,

    T. Murakami and Y . Sei, “Automatic tuning of privacy budgets in input-discriminative local differential privacy,”IEEE Internet Things J., vol. 10, no. 18, pp. 15990–16005, 2023

    2023

  16. [22]

    UKVLDP: Utility-optimized local differential privacy mechanism for key-value IoT data collection,

    B. Wang, C. Yang, and J. Ma, “UKVLDP: Utility-optimized local differential privacy mechanism for key-value IoT data collection,”IEEE Internet Things J., 2025

    2025

  17. [23]

    Enabling health data sharing with fine-grained privacy,

    L. Bonomi, S. Gousheh, and L. Fan, “Enabling health data sharing with fine-grained privacy,” inProc. 32nd ACM Int. Conf. Inf. Knowl. Manage., pp. 131–141, 2023

    2023

  18. [24]

    An intelligent privacy preservation scheme for EV charging infrastructure,

    S. Islam, S. Badsha, S. Sengupta, I. Khalil, and M. Atiquzzaman, “An intelligent privacy preservation scheme for EV charging infrastructure,” IEEE Trans. Ind. Informat., vol. 19, no. 2, pp. 1238–1247, 2023

    2023

  19. [25]

    Differential privacy for text analytics via natural text sanitization,

    X. Yue, M. Du, T. Wang, Y . Li, H. Sun, and S. S. Chow, “Differential privacy for text analytics via natural text sanitization,” inFindings Assoc. Comput. Linguistics: ACL-IJCNLP 2021, pp. 3853–3866, 2021

    2021

  20. [26]

    Multidimensional epidemiological survey data aggregation scheme based on personalized local differential privacy,

    X. Liu, Q. Liu, J. Wang, and H. Sun, “Multidimensional epidemiological survey data aggregation scheme based on personalized local differential privacy,”Symmetry, vol. 16, no. 3, p. 294, 2024

    2024

  21. [27]

    Addressing sensitivity distinction in local differential privacy: A general utility-optimized framework,

    X. He, Y . Zhu, R. Liu, G. Pan, and C. Dong, “Addressing sensitivity distinction in local differential privacy: A general utility-optimized framework,” inProc. 34th USENIX Secur. Symp. (USENIX Secur. 25), pp. 2753–2769, 2025

    2025

  22. [28]

    Extremal mechanisms for local differential privacy,

    P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,”J. Mach. Learn. Res., vol. 17, no. 17, pp. 1–51, 2016

    2016

  23. [31]

    Asymptotically optimal private estimation under mean square loss,

    M. Ye and A. Barg, “Asymptotically optimal private estimation under mean square loss,” 2017.arXiv:1708.00059

    2017 arXiv

  24. [32]

    Polyanskiy and Y

    Y . Polyanskiy and Y . Wu,Information Theory: From Coding to Learn- ing. Cambridge University Press, 1st ed., Dec. 2024

    2024

  25. [33]

    A. W. van der Vaart,Asymptotic Statistics. Cambridge Series in Statis- tical and Probabilistic Mathematics, Cambridge: Cambridge University Press, 1998

    1998

  26. [34]

    Le Cam and G

    L. Le Cam and G. Lo Yang,Asymptotics in Statistics. Springer Series in Statistics, New York, NY: Springer New York, 2000

    2000

  27. [35]

    Y . J. Ionin and M. S. Shrikhande,Combinatorics of symmetric designs, vol. 5. Cambridge, U.K.: Cambridge University Press, 2006

    2006

  28. [36]

    S. P. Boyd and L. Vandenberghe,Convex optimization. Cambridge, UK ; New York: Cambridge University Press, 2004

    2004

  29. [37]

    Equivalent comparisons of experiments,

    D. Blackwell, “Equivalent comparisons of experiments,”Ann. Math. Stat., vol. 24, no. 2, pp. 265–272, 1953

    1953

  30. [38]

    Fisher information under local differential privacy,

    L. P. Barnes, W.-N. Chen, and A. ¨Ozg¨ur, “Fisher information under local differential privacy,”IEEE J. Select. Areas Inf. Theory, vol. 1, pp. 645– 659, Jan. 2020

    2020

  31. [39]

    A. M. Bikchentaev, F. Kittaneh, M. S. Moslehian, and Y . Seo,Trace Inequalities: For Matrices and Hilbert Space Operators. Forum for Interdisciplinary Mathematics, Singapore: Springer Nature Singapore, 2024

    2024

  32. [40]

    Rudin,Principles of Mathematical Analysis

    W. Rudin,Principles of Mathematical Analysis. International Series in Pure and Applied Mathematics, McGraw-Hill, 1976

    1976

  33. [41]

    Quantum advan- tage in locally differentially private hypothesis testing,

    S.-H. Nam, H.-Y . Park, S.-H. Lee, and J. Bae, “Quantum advan- tage in locally differentially private hypothesis testing,” Aug. 2025. arXiv:2501.10152

    2025 arXiv

  34. [42]

    Factorization by extremal privacy mecha- nisms: New insights into efficiency,

    C. Amorino and A. Gloter, “Factorization by extremal privacy mecha- nisms: New insights into efficiency,” July 2025.arXiv:2507.21769

    2025 arXiv

  35. [43]

    Communication complexity in locally private distribution estimation and heavy hitters,

    J. Acharya and Z. Sun, “Communication complexity in locally private distribution estimation and heavy hitters,” inProc. 36th Int. Conf. Mach. Learn., pp. 51–60, 2019

    2019

  36. [44]

    American community survey (ACS) 2023 1-year public use microdata sample (PUMS)

    U.S. Census Bureau, “American community survey (ACS) 2023 1-year public use microdata sample (PUMS).” [Online]. Available: https://www. census.gov/programs-surveys/acs/microdata.html, Oct. 2024. Accessed: Aug. 18, 2025

    2023

  37. [45]

    Efficiency in local differential privacy,

    L. Steinberger, “Efficiency in local differential privacy,”Ann. Stat., vol. 52, pp. 2139–2166, Oct. 2024

    2024

  38. [46]

    On general minimax theorems,

    M. Sion, “On general minimax theorems,”Pacific J. Math., vol. 8, pp. 171–176, Jan. 1958. 14 x∈ XS x∈ XN y∈ Y(k) P ,x∈y y∈ Y(k) P ,x /∈y y∈ YI y∈ Y(k) P y∈ YI, x∈y y∈ YI, x /∈y (ηP (α),Q (y))x veϵ αk(eϵ −1) +v v αk(eϵ −1) +v 0 v αk(eϵ −1) +v w−v 1−α 0 Π1 ηP (α),Q (y) x (v−k)(e ...

    1958

  39. [47]

    APPENDIXD DETAILEDPROOF FORSECTIONVI A

    = 0, (w−v)(w−v−1) (1−α) 2 , v(w−v) w(1−α) 2 .(107) Thus, we have tr(Bi) = vX k=1 QP (α) (Y (k) P )Ai,k ! +Q P (α) (YI)A′ i.(108) The desired result (58) follows from the direct calculation. APPENDIXD DETAILEDPROOF FORSECTIONVI A. Proof of Proposition 10 We show (62) separately...

  40. [48]

    Thus,R(QuSS,k, ˆPuSS,k)> M∗(w, v, ϵ)

    Ifk= 1, then sinceϵ <ln q (v−1)(v−2) 2 =E(v,1), we have1/∈K ∗(v, ϵ), and henceR BD(v, k, ϵ)> M ∗(w, v, ϵ). Thus,R(QuSS,k, ˆPuSS,k)> M∗(w, v, ϵ)

  41. [49]

    Ifk≥2, thenR BD(v, k, ϵ)≥M∗(w, v, ϵ)and2(k−1) v−k >

  42. [50]

    This ends the proof of Corollary 6

    Thus,R(Q uSS,k, ˆPuSS,k)> M∗(w, v, ϵ). This ends the proof of Corollary 6. Remark 8.Originally, [27] formulated the estimator error in terms of the MSE between the empirical frequency ofX n and the estimated distribution. That is, lettingT (n) : [w]n →∆ w, T (n) x′ (xn) = 1 n ...

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.