pith. sign in

arxiv: 1906.11923 · v1 · pith:O2A6E6O3new · submitted 2019-06-27 · 🧮 math.ST · stat.ML· stat.TH

Differentially private sub-Gaussian location estimators

Marco Avella-Medina , Victor-Emmanuel Brunel This is my paper

Pith reviewed 2026-05-25 13:38 UTC · model grok-4.3

classification 🧮 math.ST stat.MLstat.TH
keywords differential privacysub-Gaussian estimatorsmedian estimationlocation parameterheavy-tailed datamean estimationLaplace mechanism
0
0 comments X

The pith

Two new differentially private algorithms estimate the median with sub-Gaussian errors for unbounded data without finite moments.

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

The paper seeks to produce location estimators that satisfy differential privacy yet retain sub-Gaussian deviation bounds even when the underlying distribution is heavy-tailed and unbounded. It first shows that directly applying the Laplace mechanism to recent non-private sub-Gaussian estimators yields worse error rates than necessary. The authors therefore construct two specialized private algorithms for the median that recover the target sub-Gaussian tails without any moment assumptions. The same finite-sample perspective reveals that privacy forces strictly larger deviations for mean estimation than the corresponding non-private sub-Gaussian procedures, in contrast to known asymptotic equivalence results.

Core claim

By revisiting non-private sub-Gaussian location estimators through the differential-privacy lens, the authors design two algorithms for private median estimation that achieve sub-Gaussian type errors. Both algorithms remain well-defined for random variables that need not be bounded or possess finite moments. In contrast, a direct Laplace mechanism applied to the same base estimators is shown to be sub-optimal. For the mean, natural private alternatives produce strictly worse deviation bounds than their non-private sub-Gaussian counterparts under heavy tails.

What carries the argument

Two specialized differentially private algorithms for median estimation that preserve sub-Gaussian deviation bounds by carefully controlling noise addition while avoiding moment requirements.

If this is right

  • Differentially private median estimation becomes possible at the same sub-Gaussian rate as the non-private case for heavy-tailed unbounded data.
  • The Laplace mechanism alone is insufficient to achieve optimal private sub-Gaussian rates for location parameters.
  • Under heavy tails the finite-sample cost of privacy is strictly positive for mean estimation, unlike the asymptotic regime.
  • Private location estimators can be constructed without requiring bounded support or moment existence.

Where Pith is reading between the lines

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

  • The same construction technique may extend to other robust location functionals beyond the median.
  • Finite-sample analyses of privacy-robustness trade-offs can differ markedly from their asymptotic counterparts.
  • These estimators could be combined with existing robust statistics pipelines to handle both privacy and heavy tails simultaneously.

Load-bearing premise

Non-private sub-Gaussian location estimators can be modified to satisfy differential privacy while keeping their original deviation bounds intact.

What would settle it

A data set drawn from a distribution with no finite moments on which either proposed private median estimator exhibits deviation probability larger than the claimed sub-Gaussian tail bound.

read the original abstract

We tackle the problem of estimating a location parameter with differential privacy guarantees and sub-Gaussian deviations. Recent work in statistics has focused on the study of estimators that achieve sub-Gaussian type deviations even for heavy tailed data. We revisit some of these estimators through the lens of differential privacy and show that a naive application of the Laplace mechanism can lead to sub-optimal results. We design two private algorithms for estimating the median that lead to estimators with sub-Gaussian type errors. Unlike most existing differentially private median estimators, both algorithms are well defined for unbounded random variables that are not even required to have finite moments. We then turn to the problem of sub-Gaussian mean estimation and show that under heavy tails natural differentially private alternatives lead to strictly worse deviations than their non-private sub-Gaussian counterparts. This is in sharp contrast with recent results that show that from an asymptotic perspective the cost of differential privacy is negligible.

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.

Referee Report

2 major / 0 minor

Summary. The paper claims to design two differentially private algorithms for median estimation that achieve sub-Gaussian deviation bounds without requiring finite moments and that apply to unbounded random variables. It further claims that natural DP alternatives for sub-Gaussian mean estimation yield strictly worse finite-sample deviations than their non-private counterparts, in contrast to recent asymptotic results showing negligible privacy cost.

Significance. If the algorithmic constructions and deviation bounds hold, the work would provide concrete tools for private robust location estimation under heavy tails and clarify finite-sample privacy costs for mean estimation, bridging differential privacy with recent advances in sub-Gaussian robust statistics.

major comments (2)
  1. Abstract: the central claims that the two private median algorithms achieve sub-Gaussian type errors and that natural DP mean estimators are strictly worse are stated without any derivation, proof sketch, theorem reference, or empirical verification visible in the supplied text, preventing assessment of soundness.
  2. Abstract (paragraph on revisiting estimators): the assumption that non-private sub-Gaussian location estimators can be privatized while preserving their deviation bounds is invoked but not shown to hold under the specific privacy mechanisms or tail conditions used.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and comments on the abstract. We address each major comment below.

read point-by-point responses

  1. Referee: Abstract: the central claims that the two private median algorithms achieve sub-Gaussian type errors and that natural DP mean estimators are strictly worse are stated without any derivation, proof sketch, theorem reference, or empirical verification visible in the supplied text, preventing assessment of soundness.

    Authors: The abstract provides a concise summary of the main contributions. The full proofs establishing the sub-Gaussian deviation bounds for the two median estimators appear in Section 3 (Theorems 3.1 and 3.2), including the analysis under unbounded support and no moment assumptions. The comparison showing strictly worse deviations for natural DP mean estimators is proven in Section 4 (Theorem 4.1). These sections contain the derivations and proof sketches. The paper is theoretical and does not include empirical verification, which is consistent with its focus on finite-sample bounds. revision: no

  2. Referee: Abstract (paragraph on revisiting estimators): the assumption that non-private sub-Gaussian location estimators can be privatized while preserving their deviation bounds is invoked but not shown to hold under the specific privacy mechanisms or tail conditions used.

    Authors: The abstract does not invoke or rely on such an assumption. It explicitly notes that a naive Laplace mechanism leads to sub-optimal results and then describes the design of two new algorithms that achieve the bounds. The manuscript shows that standard privatization fails to preserve the sub-Gaussian rates under the stated tail conditions and unbounded domain (see the analysis preceding the new constructions in Section 3), which motivates the proposed mechanisms. The specific privacy parameters and tail conditions under which the new estimators succeed are formalized in the theorems. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The abstract and context describe designing two private algorithms for median estimation achieving sub-Gaussian errors without moment assumptions, contrasting with mean estimation where DP alternatives are worse. No equations, derivations, fitted parameters, or self-referential definitions appear. Claims build on external recent statistics literature without reducing to inputs by construction, self-citations, or ansatzes smuggled via citation. The provided material shows no load-bearing steps that equate predictions to their own definitions or fits. This is the normal case of an honest non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no free parameters, invented entities, or paper-specific axioms can be extracted.

pith-pipeline@v0.9.0 · 5681 in / 1017 out tokens · 25750 ms · 2026-05-25T13:38:35.171780+00:00 · methodology

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

34 extracted references · 34 canonical work pages · 1 internal anchor

  1. [1]

    Deep learning with differ ential pri- DP LOCATION ESTIMATORS 11 vacy

    Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMaha n, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differ ential pri- DP LOCATION ESTIMATORS 11 vacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , pages 308–318. ACM, 2016

    work page 2016

  2. [2]

    Privacy-preserving parametric i nference: a case for robust statistics

    Marco Avella-Medina. Privacy-preserving parametric i nference: a case for robust statistics. (manuscript), 2019

    work page 2019

  3. [3]

    Robust estimation of high-dimensional covariance and prec ision matrices

    Marco Avella-Medina, Heather S Battey, Jianqing Fan, an d Quefeng Li. Robust estimation of high-dimensional covariance and prec ision matrices. Biometrika, 105(2):271–284, 2018

    work page 2018

  4. [4]

    Differentially private significance tests for regressi on coefficients

    Andr´ es F Barrientos, Jerome P Reiter, Ashwin Machanava jjhala, and Yan Chen. Differentially private significance tests for regressi on coefficients. Jour- nal of Computational and Graphical Statistics , pages 1–24, 2019

    work page 2019

  5. [5]

    Priva te empirical risk minimization: Efficient algorithms and tight error bounds

    Raef Bassily, Adam Smith, and Abhradeep Thakurta. Priva te empirical risk minimization: Efficient algorithms and tight error bounds. I n 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages 464–

    work page 2014

  6. [6]

    Bandits with heavy tail

    S´ ebastien Bubeck, Nicolo Cesa-Bianchi, and G´ abor Lug osi. Bandits with heavy tail. IEEE Transactions on Information Theory , 59(11):7711–7717, 2013

    work page 2013

  7. [7]

    Cai, Yichen Wang, and Zhang mLinjun

    Tony T. Cai, Yichen Wang, and Zhang mLinjun. The cost of pr ivacy: op- timal rates of convergence for paramer estimaion with differe ntial privacy. (manuscript), 2019

    work page 2019

  8. [8]

    Challenging the empirical mean and empi rical variance: a deviation study

    Olivier Catoni. Challenging the empirical mean and empi rical variance: a deviation study. In Annales de l’IHP Probabilit´ es et statistiques, volume 48, pages 1148–1185, 2012

    work page 2012

  9. [9]

    Convergence rates fo r differentially private statistical estimation

    Kamalika Chaudhuri and Daniel Hsu. Convergence rates fo r differentially private statistical estimation. In Proceedings of the 22nd International Con- ference on Machine Learning . NIH Public Access, 2012

    work page 2012

  10. [10]

    Differ- entially private empirical risk minimization

    Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sar wate. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(Mar):1069–1109, 2011

    work page 2011

  11. [11]

    Sub- gaussian mean estimators

    Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Rober to I Oliveira. Sub- gaussian mean estimators. The Annals of Statistics , 44(6):2695–2725, 2016

    work page 2016

  12. [12]

    The notion of breakdown point

    David L Donoho and Peter J Huber. The notion of breakdown point. A festschrift for Erich L. Lehmann , 157184, 1983

    work page 1983

  13. [13]

    Minimax optimal procedures for locally private estimation

    John C Duchi, Michael I Jordan, and Martin J Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182–201, 2018

    work page 2018

  14. [14]

    Differential privacy and robu st statistics

    Cynthia Dwork and Jing Lei. Differential privacy and robu st statistics. In STOC, volume 9, pages 371–380, 2009

    work page 2009

  15. [15]

    Calibrat- ing noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam S mith. Calibrat- ing noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265–284. Springer, 2006

    work page 2006

  16. [16]

    The algorithmic foundati ons of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundati ons of differential privacy. Foundations and Trends ® in Theoretical Computer Science , 9(3– 4):211–407, 2014

    work page 2014

  17. [17]

    Differentially private chi-squared hypothesis testing: Goo dness of fit and independence testing

    Marco Gaboardi, Hyun-Woo Lim, Ryan M Rogers, and Salil P Vadhan. Differentially private chi-squared hypothesis testing: Goo dness of fit and independence testing. In ICML’16 Proceedings of the 33rd International Conference on International Conference on Machine Learning-V olume 48 . 12 M. A VELLA-MEDINA AND V.-E. BRUNEL JMLR, 2016

    work page 2016

  18. [18]

    Loss minimization and para meter estimation with heavy tails

    Daniel Hsu and Sivan Sabato. Loss minimization and para meter estimation with heavy tails. The Journal of Machine Learning Research , 17(1):543–582, 2016

    work page 2016

  19. [19]

    Huber and Elvezio Ronchetti

    Peter J. Huber and Elvezio Ronchetti. Robust Statistics . Wiley, New York, New York, second edition, 2009

    work page 2009

  20. [20]

    Inference using noisy degrees: Dif- ferentially private beta-model and synthetic graphs

    Vishesh Karwa and Aleksandra Slavkovi´ c. Inference using noisy degrees: Dif- ferentially private beta-model and synthetic graphs. The Annals of Statistics , 44(1):87–112, 2016

    work page 2016

  21. [21]

    Priv ate convex em- pirical risk minimization and high-dimensional regressio n

    Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Priv ate convex em- pirical risk minimization and high-dimensional regressio n. In Conference on Learning Theory, pages 25–1, 2012

    work page 2012

  22. [22]

    Robust machine learning by median- of-means: theory and practice

    Guillaume Lecu´ e and Matthieu Lerasle. Robust machine learning by median- of-means: theory and practice. Annals of Statistics (to appear) , 2019

    work page 2019

  23. [23]

    Certified Robustness to Adversarial Examples with Differential Privacy

    Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu , Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples wi th differential privacy. arXiv preprint arXiv:1802.03471 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  24. [24]

    Differentially private M-estimators

    Jing Lei. Differentially private M-estimators. In Advances in Neural Infor- mation Processing Systems , pages 361–369, 2011

    work page 2011

  25. [25]

    Sub-gaussian estimators of the mean of a random vector

    G´ abor Lugosi, Shahar Mendelson, et al. Sub-gaussian estimators of the mean of a random vector. The Annals of Statistics , 47(2):783–794, 2019

    work page 2019

  26. [26]

    Sub-gaussian estimators of the mea n of a random matrix with heavy-tailed entries

    Stanislav Minsker. Sub-gaussian estimators of the mea n of a random matrix with heavy-tailed entries. The Annals of Statistics , 46(6A):2871–2903, 2018

    work page 2018

  27. [27]

    (nearly) optima l differentially pri- vate stochastic multi-arm bandits

    Nikita Mishra and Abhradeep Thakurta. (nearly) optima l differentially pri- vate stochastic multi-arm bandits. In Proceedings of the Thirty-First Con- ference on Uncertainty in Artificial Intelligence , pages 592–601. AUAI Press, 2015

    work page 2015

  28. [28]

    Smo oth sensitivity and sampling in private data analysis

    Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smo oth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM Symposium on Theory of Computing , pages 75–84. ACM, 2007

    work page 2007

  29. [29]

    Differentially private conte xtual linear ban- dits

    Roshan Shariff and Or Sheffet. Differentially private conte xtual linear ban- dits. In Advances in Neural Information Processing Systems , pages 4296– 4306, 2018

    work page 2018

  30. [30]

    Differentially private ordinary least squares

    Or Sheffet. Differentially private ordinary least squares . In Proceedings of the 34th International Conference on Machine Learning-Volum e 70 , pages 3105–3114. JMLR. org, 2017

    work page 2017

  31. [31]

    Privacy-preserving statistical estimati on with optimal conver- gence rates

    Adam Smith. Privacy-preserving statistical estimati on with optimal conver- gence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 813–822. ACM, 2011

    work page 2011

  32. [32]

    Ne arly optimal private lasso

    Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Ne arly optimal private lasso. In Advances in Neural Information Processing Systems , pages 3025–3033, 2015

    work page 2015

  33. [33]

    Algorit hms for differentially private multi-armed bandits

    Aristide CY Tossou and Christos Dimitrakakis. Algorit hms for differentially private multi-armed bandits. In Thirtieth AAAI Conference on Artificial Intelligence, 2016

    work page 2016

  34. [34]

    No Reply

    Larry Wasserman and Shuheng Zhou. A statistical framew ork for differential privacy. Journal of the American Statistical Association , 105(489):375–389, 2010. DP LOCATION ESTIMATORS 13 APPENDIX: DIFFERENTIALLY PRIVATE SUB-GAUSSIAN LOCATION ESTIMATORS Proof of Lemma 2 Let k0 = /uni230A.alt1 Lrn 2 /uni230B.alt1 . Note that k0 ≤n/slash.left 4, since 2 Lr ≤F (...

    work page 2010