Pith. sign in

REVIEW 3 major objections 5 minor 64 references

Randomized Projection with Clipping achieves minimax-optimal sparse-vector mean estimation under LDP while providing the first worst-case poisoning bound.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 00:53 UTC pith:G7QGGUX3

load-bearing objection RPC gives a clean bias-corrected sparse-projections estimator and the first poisoning bound for sparse LDP, but the main theorem's α bound is proved for R=√(2m), not the stated R=√m. the 3 major comments →

arxiv 2607.27815 v1 pith:G7QGGUX3 submitted 2026-07-30 stat.ML cs.LG

Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy

Puning Zhao , Zhikun Zhang , Shaowei Wang , Sheng Yue , Bangzhou Xin , Tianhang Zheng , Pengfei Zhang , Xiaochun Cao This is my paper
classification stat.ML cs.LG MSC 62G0562G3568P27
keywords local differential privacysparse vector mean estimationpoisoning attacksclipping bias correctionrandom projectionrobust estimationminimax optimalityRPC
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Local differential privacy (LDP) protects individual data but is notoriously vulnerable to poisoning attacks, in which corrupted users bend the aggregate estimate. This paper shows that for sparse multi-item data—each user holds an m-sparse vector with ±1 entries—robustness and accuracy do not have to be traded off. The proposed algorithm, Randomized Projection with Clipping (RPC), has each user project its vector onto a random binary vector, clip the projection to a small threshold R ≈ √m, and then perturb it, and the paper proves that the clipping bias can be removed exactly by a single correction factor α derived from the combinatorics of the projection. On clean data the estimator is unbiased and attains the information-theoretic minimax error O(d√(m/(nε²))); against an adversary corrupting q users, it gives the first worst-case ℓ1 error bound for sparse multi-item LDP, growing like q√(dm ln n)/(nε) under strong contamination and without the √ln n factor under additive contamination.

Core claim

The central claim is that clipping a random projection can be debiased exactly, and this exact debiasing is what buys robustness without losing statistical efficiency. For each user i, the server sends a uniform binary vector S_i ∈ {−1,1}^d; the user computes u_i = Clip(⟨x_i, S_i⟩, R) with R = ⌈√m⌉, then applies a finite-range unbiased ε-LDP randomizer to u_i/R and scales the result by R. The paper derives a closed-form expression for the bias of the clipped projection in terms of clipped sums of independent symmetric ±1 variables, and defines α = 1 / (1 − E[Clip(U, −R+1, R+1)]) so that (α/n) Σ Y_i S_i is unbiased for every coordinate when the data are m-sparse with entries in {−1, 1}. This

What carries the argument

Randomized Projection with Clipping (RPC): each user projects its m-sparse ±1 vector onto a random binary vector, clips the scalar projection to [−R, R] with R ≈ √m, and applies a finite-range unbiased ε-LDP randomizer. The load-bearing identity is the exact bias formula for the clipped projection: for coordinate j, the bias depends only on the clipped sum of m−1 independent symmetric ±1 variables, so a single correction factor α = 1 / (1 − E[Clip(U, −R+1, R+1)]) restores unbiasedness for every coordinate. Because the correction is exact rather than a bound, the clipping threshold can be made small without a bias–variance tradeoff; this simultaneously reduces the LDP noise (variance scales a

Load-bearing premise

The entire unbiasedness argument, and therefore both the minimax-optimality claim and the poisoning bound, rests on every user's vector being exactly m-sparse with nonzero entries in {−1, 1}; the paper's own Remark 1 concedes that when users have unequal item counts and m is not known, padding changes the problem and the resulting truncation bias is unanalyzed, and the continuous-value extension requires a known norm bound β (Assumption 1), which the experiments set from the

What would settle it

Compute E[Clip(U, −R+1, R+1)] by brute force for U equal to the sum of m−1 independent symmetric ±1 variables for, say, m = 5 and R = 2, and compare with formula (13)'s α; any mismatch invalidates Lemma 2 and cascades to Theorems 1–2. Alternatively, run RPC on clean synthetic data with m-sparse ±1 vectors and check that the empirical ℓ1 error at ε = O(1) tracks d√(m/(nε²)); an extra √m or √d factor would contradict the claimed minimax rate.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • On clean data, RPC achieves O(d√(m/(nε²))) ℓ1 error, matching the minimax lower bound for m-sparse mean estimation under LDP, so robustifying does not sacrifice asymptotic accuracy.
  • It provides the first worst-case upper bound on ℓ1 error for sparse multi-item LDP under poisoning: with q corrupted users, the error is bounded by O(d√(m/(nε²)) + q√(dm ln n)/(nε)) under strong contamination, giving a concrete security guarantee independent of attack strategy.
  • When m = 1, the strong-contamination bound reduces to the established single-item robust LDP result, showing RPC generalizes the previously solved case.
  • Because the bias correction is exact, clipping thresholds in LDP estimators no longer need to balance bias against variance; this suggests the same technique could improve other clipping-based private estimation pipelines.
  • For continuous values in [−1,1] with known norm bound β, the paper derives explicit error bounds (e.g., O(dβ√(m ln n/(nε²)) + d√(m/n) + qβ√(dm ln² n)/(nε))) and characterizes when direct estimation beats randomized rounding to ±1, namely when β√ln n < 1.

Where Pith is reading between the lines

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

  • A natural extension not explored in the paper: tune R adaptively per coordinate or per dataset while retaining the exact-bias correction, potentially improving constant factors without breaking unbiasedness.
  • The paper's padding argument for unequal item counts changes the problem and leaves truncation bias unanalyzed; a practical next step would be a private procedure that estimates the effective sparsity m before choosing R, which would make the method deployment-ready for heterogeneous user data.
  • The √ln n gap between additive and strong contamination bounds suggests a server-side diagnostic: if realized error under attack matches the additive-contamination rate rather than the strong-contamination rate, large-scale coordinated corruption may be absent, while a jump to the √ln n rate signals targeted manipulation.
  • RPC's communication cost is O(1) when the underlying randomizer is binary, so the robustness guarantee is compatible with very low communication overhead—an advantage that may matter more than statistical efficiency in bandwidth-limited federated systems.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes Randomized Projection with Clipping (RPC) for mean estimation of m-sparse vectors under ε-LDP. Each user projects its vector onto a server-generated random sign vector, clips the projection to a threshold R, and applies an unbiased LDP randomizer; the server aggregates and multiplies by an exactly computed bias-correction factor α. The main claims are: (i) in a trusted environment the clean-data ℓ1 error is O(d√(m/(nε²))), matching the known minimax rate; (ii) under poisoning with up to q corrupted users, the first worst-case upper bounds are O(d√(m/(nε²)) + q√(dm)/(nε)) under additive contamination and O(d√(m/(nε²)) + q√(dm ln n)/(nε)) under strong contamination; (iii) an extension to general numerical values in [−1,1] is given under an ℓ2-norm bound assumption on the user vectors. Experiments on synthetic and real data compare RPC with PCKV, the Succinct mechanism, and Collision, both with and without attacks.

Significance. If the technical gaps are repaired, this would be a genuinely useful contribution: it is the first poisoning upper bound for sparse multi-item LDP mean estimation, and it achieves this without sacrificing the minimax-optimal clean-data rate. The bias-correction formula is exact, depends only on m and R, and involves no data-dependent fitting; the error bounds are genuine worst-case upper bounds rather than heuristic defenses. The paper also provides code artifacts. The core algebra in Lemmas 1–2 and the general proof strategy in Theorems 1–2 are plausible. The main weakness is a concrete proof-theorem mismatch in the choice of R, plus some modeling inconsistencies in the additive-contamination proof and a missing discussion of the known-β requirement in the continuous-value extension.

major comments (3)
  1. [§5.1, Corollary 1; Appendix E.2; Appendix F after (90)] The theorems are stated with R=⌈√m⌉, but the only proof that α is O(1) is in Appendix E.2, where the choice is R=⌈√(2m)⌉. For R=⌈√m⌉, the same Hoeffding bound gives E[Clip]≤2e^{-1/2}≈1.213, which does not even imply the denominator 1−E[Clip] in (62) is positive. Since α multiplies both the clean error in Theorem 1 and the attack term in Theorem 2, the stated rates are not proven for the stated R. This is not a mere typo: the exact parameter in the statement and the parameter in the proof differ. Fix by restating all results with R=⌈√(2m)⌉ (the asymptotic rates are unchanged, as R=Θ(√m)), or by adding a valid tail bound for R=⌈√m⌉.
  2. [Appendix F, additive contamination model; §3.2] The proof of the additive-contamination half says 'C is randomly selected from all samples', but Section 3.2 defines additive contamination as 'the set C of corrupted users are fixed in advance'. The removal of the C(n,q) factor should be justified by the fact that C is fixed independently of the random S_i, so no union over C is needed; the random-selection wording is a different model. Also, the definition of Z in (18) quantifies over any set of up to q differences, which is the strong-contamination adversary; please align the definition of Z with the additive model or explain that the bound is uniform over fixed C.
  3. [§6, Assumption 1; §8.2 continuous-value experiment] The direct extension depends on β being known: Theorem 3 and 4 set R=β√(m ln n)+1 and the bias bound (24) contains β. The experiments set β=0.3 because the synthetic values are N(0,0.2²) truncated, but the paper does not discuss how a server would choose β when it is unknown, nor the effect of misspecifying β. This limits the direct method's practical applicability; please state explicitly that β is a known input and discuss estimation or the indirect method as the alternative.
minor comments (5)
  1. [Appendix A, Eq. (41)] E[W] should be Var(W) (or E[W²]); the Laplace mechanism has zero mean.
  2. [Appendix F, Eq. (89)] The first term in the displayed bound is missing a cε factor; from (80) and (88) both the q√(d ln n) and d√q terms carry cε. The subsequent equation (90) has the cε in the right place, but (89) should be corrected to avoid confusion.
  3. [Appendix E.1, around (65)] The notation y_{1:n} is used but y_i is never defined; it should be u_i = Clip(⟨x_i,S_i⟩,R).
  4. [§5.1, Figure 2 and Corollary 1] The statement that 'the optimal R is close to √m in general' is supported only by Figure 2 for d=20, n=1000, m=10. Please state this as a heuristic or provide an asymptotic justification.
  5. [Remark 7 / Table 1] The claim that the RPC bound is 'tighter' than Collision's bound is not uniform in all parameters: comparing q√(dm) with m(d√q+q√d) favors RPC for small q and large d, but not necessarily when m is large relative to d. Please specify the regime of parameters in which (19) dominates (21).

Circularity Check

0 steps flagged

No circularity: bias-correction alpha is derived exactly from the Rademacher projection distribution; the error bounds are genuine worst-case guarantees rather than fitted predictions.

full rationale

The paper's central derivation is self-contained rather than circular. The correction factor alpha in Eq. (13) is the exact reciprocal of 1 - E[Clip(U_ij, -R+1, R+1)] where U_ij is a sum of m-1 independent Rademacher variables; Lemma 2's proof (Appendix D, Eqs. (60)-(63)) computes this expectation from the binomial weights C(m-1,l)2^{-(m-1)}, so no parameter is fitted to data and then reported as a prediction. Theorem 1's clean-data bound is a genuine unbiasedness-plus-variance decomposition, and Theorem 2's attack term is a worst-case Hoeffding/union-bound argument. In the continuous-value extension, Assumption 1's beta enters an explicit bias bound 2exp(-(R-1)^2/(2m beta^2)), and choosing R = beta sqrt(m ln n)+1 makes the bias O(1/n) analytically, not by tuning to the dataset. Minor self-citations ([47], [57], [58]) appear only as background or as the independent published minimax lower bound; they do not supply the derivation's intermediate steps. The flagged mismatch between R=ceil(sqrt(m)) in Corollary 1/Theorem 2 and the alpha-bound proved only for R=ceil(sqrt(2m)) in Appendix E.2 -- with Appendix F simply asserting 'With R=sqrt(m), alpha is upper bounded by a constant' -- is a genuine proof/verification gap, but not circularity: alpha is still a deterministic function of (m,R), so the final rate does not reduce by construction to a fitted input. Similarly, Remark 1's admission that truncation bias for unknown m 'have not been analyzed' is an acknowledged limitation, not a disguised re-use of the target result. No circular step can be exhibited from the paper's equations.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

The central bound rests on exact m-sparse ±1 structure for the unbiasedness of α, a finite-range unbiased ε-LDP randomizer, and the threat-model restriction that attacked outputs stay in Y. The continuous-value extension adds Assumption 1 and a data-dependent β. No invented entities; α is derived, not postulated.

free parameters (2)
  • R (clipping threshold) = √m (binary case); β√(m ln n)+1 (continuous case)
    Design hyperparameter, not fit to attack data, but the stated asymptotic rates select these values. In the continuous case R depends on the assumed β.
  • β (energy bound coefficient) = 0.3 in experiments
    Assumption 1 requires a known β; experiments set β=0.3 because the synthetic data had σ=0.2. No private estimation procedure for β is given.
axioms (5)
  • domain assumption Each user vector is exactly m-sparse with nonzero entries in {−1,1} (X defined in Eq. 6).
    Lemma 2's α uses the fact that U_ij is a sum of m−1 Rademacher variables; breaks for general values, where Section 6 only bounds bias, not corrects it.
  • domain assumption Q is unbiased and satisfies ε-LDP for inputs in [−1,1], with finite cε and Vε=O(1/ε²).
    Used in Theorem 1 and Theorem 2; Laplace mechanism is excluded from the robustness theorem because cε=∞ (Remark 6).
  • domain assumption Adversarial outputs are constrained to the honest output space Y.
    Theorem 2's Z set (Eq. 18) and Remark 6 exclude infinite-range attacks; if the adversary sends arbitrary out-of-space values, the bound does not hold.
  • ad hoc to paper For general values, Σ_j x_ij² ≤ mβ² for known β (Assumption 1).
    Used in Theorem 3/4 to control the Hoeffding tail; in experiments β=0.3 is chosen from the data-generating σ=0.2.
  • standard math Hoeffding's inequality and standard concentration for Rademacher sums.
    Invoked in Appendix E and F for bias tails and attack-error maxima.

pith-pipeline@v1.3.0-daily-deepseek · 43446 in / 20769 out tokens · 187434 ms · 2026-08-01T00:53:52.335793+00:00 · methodology

0 comments
read the original abstract

Local differential privacy (LDP) protocols are vulnerable to poisoning attacks. Existing research have proposed efficient defense strategies for single-item users. However, in practice, a user may possess multiple items. The defense against poisoning attacks for multi-item users is challenging, because due to larger output spaces, the adversary can conduct more powerful attacks without being detected. In this paper, we address the robust sparse vector mean estimation problem, in which each user has a vector with $m$ nonzero coordinates. We propose Randomized Projection with Clipping (RPC). Firstly, the server sends a random binary vector to each user. The user then projects its local data on the vector, and clip the value to restrict the attacker's capability. To handle clipping bias, we propose a correction method based on a careful analysis that gives an exact expression of the bias. As a result, bias-variance tradeoff is no longer needed, thus the clipping threshold can be further reduced to shrink the output space and enhance robustness. We provide a rigorous theoretical guarantee of the estimation error under all possible attacks. Numerical experiments show that under trusted environments, our new method achieves comparable or better performance than existing methods, indicating that our method is already an efficient estimator in its own right. Under untrusted environments, our method is also significantly more robust to poisoning attacks.

Figures

Figures reproduced from arXiv: 2607.27815 by Bangzhou Xin, Pengfei Zhang, Puning Zhao, Shaowei Wang, Sheng Yue, Tianhang Zheng, Xiaochun Cao, Zhikun Zhang.

Figure 1
Figure 1. Figure 1: Illustration of the general framework with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Impact of 𝑅 on the estimation error 5 Theoretical Analysis We conduct theoretical analysis in two steps. In the first step, we analyze the estimation error in trusted environment. In other words, we assume that there are no poisoning attacks. In the second step, we analyze the performance with up to 𝑞 users being controlled by an adversary. The goal of the first step is to show that the robustness of our e… view at source ↗
Figure 9
Figure 9. Figure 9: It can be observed that with the increase of [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 3
Figure 3. Figure 3: The mean absolute error of frequency estimation in a trusted environment using synthesized data. [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The mean absolute error of mean estimation in a trusted environment, with values being [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The mean absolute error of mean estimation in a trusted environment, with values following normal distribution [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The mean absolute error of mean estimation in a trusted environment for four real datasets. [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The mean absolute error of frequency estimation in untrusted environment using synthesized data. [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The mean absolute error of mean estimation in untrusted environment using synthesized data. [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The mean absolute error of mean estimation in untrusted environment for four real datasets. [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

64 extracted references · 6 linked inside Pith

  1. [1]

    [n. d.]. Amazon - Ratings (Beauty Products). https://www.kaggle.com/datasets/skillsmuggler/amazon-ratings

  2. [2]

    [n. d.]. Clothing Fit Dataset for Size Recommendation. https://www.kaggle.com/datasets/rmisra/clothing-fit-dataset-for-size- recommendation

  3. [3]

    [n. d.]. Movie Rating Data. https://www.kaggle.com/datasets/ashukr/movie- rating-data

  4. [4]

    [n. d.]. Women’s E-Commerce Clothing Reviews. https://www.kaggle.com/datasets/nicapotato/womens-ecommerce-clothing- reviews/data

  5. [5]

    Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 1120–1129

    2019

  6. [6]

    Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy

  7. [7]

    Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy Nguyen, and Kunal Talwar. 2024. Fast optimal locally private mean estimation via random projections.Advances in Neural Information Processing Systems36 (2024)

    2024

  8. [8]

    Hilal Asi, Vitaly Feldman, and Kunal Talwar. 2022. Optimal algorithms for mean estimation under local differential privacy. InInternational Conference on Machine Learning. PMLR, 1046–1056

    2022

  9. [9]

    Raef Bassily and Adam Smith. 2015. Local, private, efficient protocols for succinct histograms. InProceedings of the forty-seventh annual ACM symposium on Theory of computing. 127–135

    2015

  10. [10]

    Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. 2018. Protection against reconstruction and its applications in private federated learning.arXiv preprint arXiv:1812.00984(2018)

    Pith/arXiv arXiv 2018

  11. [11]

    Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai

  12. [12]

    Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. 2003. Concentration inequalities. InSummer school on machine learning. Springer, 208–240

    2003

  13. [13]

    In2021 IEEE Symposium on Security and Privacy (SP)

    Lightweight techniques for private heavy hitters. In2021 IEEE Symposium on Security and Privacy (SP). IEEE, 762–776

  14. [14]

    Wei-Ning Chen, Peter Kairouz, and Ayfer Özgür. 2022. Breaking the communication-privacy-accuracy trilemma.IEEE Transactions on Information Theory69, 2 (2022), 1261–1281

    2022

  15. [15]

    Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2021. Data poisoning at- tacks to local differential privacy protocols. In30th USENIX Security Symposium (USENIX Security 21). 947–964

    2021

  16. [16]

    2023.Algorithmic high-dimensional robust statistics

    Ilias Diakonikolas and Daniel M Kane. 2023.Algorithmic high-dimensional robust statistics. Cambridge university press

    2023

  17. [17]

    Albert Cheu, Adam Smith, and Jonathan Ullman. 2021. Manipulation attacks in local differential privacy. In2021 IEEE Symposium on Security and Privacy (SP). IEEE, 883–900

    2021

  18. [18]

    Wei Dong, Qiyao Luo, Giulia Fanti, Elaine Shi, and Ke Yi. 2024. Almost instance- optimal clipping for summation problems in the shuffle model of differential privacy. InProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security. 1939–1953

    2024

  19. [19]

    Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately.Advances in Neural Information Processing Systems30 (2017)

    2017

  20. [20]

    John C Duchi, Michael I Jordan, and Martin J Wainwright. 2018. Minimax optimal procedures for locally private estimation.J. Amer. Statist. Assoc.113, 521 (2018), 182–201

    2018

  21. [21]

    John C Duchi, Michael I Jordan, and Martin J Wainwright. 2013. Local privacy and statistical minimax rates. In2013 IEEE 54th annual symposium on foundations of computer science. IEEE, 429–438

    2013

  22. [22]

    Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by shuffling: From local to central differential privacy via anonymity. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2468–2479

    2019

  23. [23]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Cali- brating noise to sensitivity in private data analysis. InTheory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3. Springer, 265–284

    2006

  24. [24]

    Huiyu Fang, Liquan Chen, and Suhui Liu. 2025. Further Study on Frequency Estimation under Local Differential Privacy. In34th USENIX Security Symposium (USENIX Security 25)

    2025

  25. [25]

    Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. Rappor: Random- ized aggregatable privacy-preserving ordinal response. InProceedings of the 2014 ACM SIGSAC conference on computer and communications security. 1054–1067

    2014

  26. [26]

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. 2023. Stronger privacy amplification by shuffling for rényi and approximate differential privacy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 4966–4981

    2023

  27. [27]

    Vitaly Feldman, Audra McMillan, and Kunal Talwar. 2022. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 954–964

    2022

  28. [28]

    Kai Huang, Gaoya Ouyang, Qingqing Ye, Haibo Hu, Bolong Zheng, Xi Zhao, Ruiyuan Zhang, and Xiaofang Zhou. 2024. LDPGuard: Defenses against data poisoning attacks to local differential privacy protocols.IEEE Transactions on Knowledge and Data Engineering(2024)

    2024

  29. [29]

    Xiaolan Gu, Ming Li, Yueqiang Cheng, Li Xiong, and Yang Cao. 2020. PCKV: Locally differentially private correlated Key-Value data collection with optimized utility. In29th USENIX security symposium (USENIX security 20). 967–984

    2020

  30. [30]

    Jinyuan Jia and Neil Zhenqiang Gong. 2019. Calibrate: Frequency estimation and heavy hitter identification with local differential privacy via incorporating prior knowledge. InIEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2008–2016

    2019

  31. [31]

    Ziyue Huang, Yuting Liang, and Ke Yi. 2021. Instance-optimal mean estimation under differential privacy.Advances in Neural Information Processing Systems34 (2021), 25993–26004

    2021

  32. [32]

    Jakub Konečn `y, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. 2016. Federated learning: Strategies for improving communication efficiency.arXiv preprint arXiv:1610.05492(2016)

    Pith/arXiv arXiv 2016

  33. [33]

    Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2011. What can we learn privately?SIAM J. Comput.40, 3 (2011), 793–826

    2011

  34. [34]

    Xiaoguang Li, Zitao Li, Ninghui Li, and Wenhai Sun. 2024. On the robustness of ldp protocols for numerical attributes under data poisoning attacks.arXiv preprint arXiv:2403.19510(2024)

    Pith/arXiv arXiv 2024

  35. [35]

    Xiaoguang Li, Ninghui Li, Wenhai Sun, Neil Zhenqiang Gong, and Hui Li. 2023. Fine-grained poisoning attack to local differential privacy protocols for mean and variance estimation. In32nd USENIX Security Symposium (USENIX Security 23). 1739–1756

    2023

  36. [36]

    Thông T Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. 2016. Collecting and analyzing data from smart device users with local differential privacy.arXiv preprint arXiv:1606.05053(2016)

    Pith/arXiv arXiv 2016

  37. [37]

    Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Škoric. 2020. Estimating numerical distributions under local differential privacy. InProceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 621–635

    2020

  38. [38]

    2018.Robust learning: Information theory and algorithms

    Jacob Steinhardt. 2018.Robust learning: Information theory and algorithms. Stan- ford University

    2018

  39. [39]

    Zhan Qin, Yin Yang, Ting Yu, Issa Khalil, Xiaokui Xiao, and Kui Ren. 2016. Heavy hitter estimation over set-valued data with local differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 192–203

    2016

  40. [40]

    2017.Learning with privacy at scale

    Apple Differential Privacy Team. 2017.Learning with privacy at scale. Technical Report

    2017

  41. [41]

    Xinyue Sun, Qingqing Ye, Haibo Hu, Jiawei Duan, Tianyu Wo, Jie Xu, and Renyu Yang. 2024. LDPRecover: Recovering frequencies from poisoning attacks against local differential privacy. In2024 IEEE 40th International Conference on Data Engineering (ICDE)

    2024

  42. [42]

    Wei Tong, Haoyu Chen, Jiacheng Niu, and Sheng Zhong. 2024. Data Poisoning Attacks to Locally Differentially Private Frequent Itemset Mining Protocols. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communi- cations Security. 3555–3569

    2024

  43. [43]

    Kurt Thomas, Damon McCoy, Chris Grier, Alek Kolcz, and Vern Paxson. 2013. Trafficking Fraudulent Accounts: The Role of the Underground Market in Twitter Spam and Abuse. In22nd USENIX Security Symposium (USENIX Security 13). 195–210

    2013

  44. [44]

    Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019. Collecting and analyzing multidimensional data with local differential privacy. In2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 638–649

    2019

  45. [45]

    Di Wang and Jinhui Xu. 2019. On sparse linear regression in the local differential privacy model. InInternational Conference on Machine Learning. PMLR, 6628– 6637

    2019

  46. [46]

    Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu, Wei Yang, Xiang-Yang Li, and Chunming Qiao. 2016. Mutual information optimally local private discrete distribution estimation.arXiv preprint arXiv:1607.08025 (2016)

    Pith/arXiv arXiv 2016

  47. [47]

    Shaowei Wang, Liusheng Huang, Yiwen Nie, Pengzhan Wang, Hongli Xu, and Wei Yang. 2018. Privset: Set-valued data analyses with locale differential privacy. InIEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 1088–1096. Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy CCS ’26, November 15–19,2026, Hague, Netherland

    2018

  48. [48]

    Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In26th USENIX Security Symposium (USENIX Security 17). 729–745

    2017

  49. [49]

    Shaowei Wang, Shiyu Yu, Xiaojun Ren, Jin Li, Yuntong Li, Wei Yang, and Hongyang Yan. 2023. Differentially Private Numerical Vector Analyses in the Local and Shuffle Model.IEEE Transactions on Dependable and Secure Computing (2023)

    2023

  50. [50]

    Tianhao Wang, Milan Lopuhaä-Zwakenberg, Zitao Li, Boris Skoric, and Ninghui Li. 2019. Locally differentially private frequency estimation with consistency. arXiv preprint arXiv:1905.08320(2019)

    Pith/arXiv arXiv 2019

  51. [51]

    Tianhao Wang, Ninghui Li, and Somesh Jha. 2018. Locally differentially private frequent itemset mining. In2018 IEEE Symposium on Security and Privacy (SP). IEEE, 127–143

    2018

  52. [52]

    Yongji Wu, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2022. Poisoning attacks to local differential privacy protocols for Key-Value data. In31st USENIX Security Symposium (USENIX Security 22). 519–536

    2022

  53. [53]

    Stanley L Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias.Journal of the American statistical association60, 309 (1965), 63–69

    1965

  54. [54]

    Qingqing Ye, Haibo Hu, Xiaofeng Meng, and Huadi Zheng. 2019. PrivKV: Key- value data collection with local differential privacy. In2019 IEEE Symposium on Security and Privacy (SP). IEEE, 317–331

    2019

  55. [55]

    Min Ye and Alexander Barg. 2018. Optimal schemes for discrete distribution estimation under locally differential privacy.IEEE Transactions on Information Theory64, 8 (2018), 5662–5676

    2018

  56. [56]

    Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi

  57. [57]

    Qingqing Ye, Haibo Hu, Xiaofeng Meng, Huadi Zheng, Kai Huang, Chengfang Fang, and Jie Shi. 2021. PrivKVM*: Revisiting key-value statistics estimation with local differential privacy.IEEE Transactions on Dependable and Secure Computing 20, 1 (2021), 17–35

    2021

  58. [58]

    Puning Zhao, Zhikun Zhang, Jiawei Dong, Jiafei Wu, Shaowei Wang, Zhe Liu, and Yunjun Gao. 2025. An Attack-Agnostic Defense Framework Against Manipulation Attacks under Local Differential Privacy. In2025 IEEE Symposium on Security and Privacy (SP). IEEE Computer Society, 3858–3876

    2025

  59. [59]

    Puning Zhao, Zhikun Zhang, Bo Sun, Li Shen, Liang Zhang, Shaowei Wang, and Zhe Liu. 2026. Consistent estimation of numerical distributions under local differential privacy by wavelet expansion. In2026 IEEE Symposium on Security and Privacy (SP). IEEE, 3243–3261

    2026

  60. [60]

    Puning Zhao, Qingqing Ye, Shaowei Wang, Jun Feng, Sheng Yue, Zhen Chen, and Xiaochun Cao. 2026. Sparse Estimation Under Local Differential Privacy at All Privacy Levels. In2026 IEEE Symposium on Security and Privacy (SP). IEEE, 2250–2268

    2026

  61. [63]

    Mingxun Zhou, Tianhao Wang, TH Hubert Chan, Giulia Fanti, and Elaine Shi

  62. [64]

    1 𝑛 𝑛∑︁ 𝑖=1 𝑢𝑖 S𝑖 # =E

    Locally differentially private sparse vector aggregation. In2022 IEEE Symposium on Security and Privacy (SP). IEEE, 422–439. A Discussions of Randomizers Here we analyze the values of𝑐𝜖 and𝑉𝜖 of randomizers listed in Section 2.2. Recall that𝑐𝜖 and𝑉𝜖 are defined in (2) and (3), respec- tively. Laplace mechanism [21].Recall that𝑌=𝑢+𝑊 , with𝑊 following Lapla...

    2026

  63. [2021]

    Differentially private learning with adaptive clipping.Advances in Neural Information Processing Systems34 (2021), 17455–17466

    2021

  64. [2022]

    InInternational Conference on Machine Learning, ICML 2022

    Understanding clipping for federated learning: Convergence and client- level differential privacy. InInternational Conference on Machine Learning, ICML 2022

    2022