pith. sign in

arxiv: 2605.21860 · v1 · pith:4OZYQU2Lnew · submitted 2026-05-21 · 🧮 math.ST · cs.DS· cs.IT· math.IT· stat.ML· stat.TH

Robust Statistical Estimators with Bounded Empirical Sensitivity

Valentio Iverson , Gautam Kamath , Argyris Mouzakis , Adam Smith This is my paper

Pith reviewed 2026-05-22 03:23 UTC · model grok-4.3

classification 🧮 math.ST cs.DScs.ITmath.ITstat.MLstat.TH
keywords empirical sensitivityrobust estimationGaussian mean estimationlower boundsEfron-Stein argumentstatistical robustnesshigh-dimensional statistics
0
0 comments X

The pith

Any estimator achieving optimal error for Gaussian mean estimation must have empirical sensitivity at least Omega(eta + sqrt(eta d/n)).

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

The paper introduces empirical sensitivity as a robustness measure for statistical estimators: with high probability over a dataset, the output changes little when up to an eta fraction of points are modified. For estimating the mean of a d-dimensional Gaussian, it proves that any estimator attaining the optimal l2 error of O(sqrt(d/n)) must have empirical sensitivity at least Omega(eta + sqrt(eta d/n)). This lower bound splits into separate contributions from obstructions on the estimator's mean and on its variance, established via an Efron-Stein argument. The authors further show the bound is tight up to logarithmic factors by appealing to recent constructions of robust mean estimators.

Core claim

For any estimator hat mu which achieves an optimal l2-error bound of O(sqrt(d/n)), the empirical sensitivity is at least Omega(eta + sqrt(eta d/n)). The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument). This bound is tight up to logarithmic factors by employing recent results for robust empirical mean estimation.

What carries the argument

empirical sensitivity: the property that, with high probability over the original dataset, modifying at most eta n points produces an output close to the original estimator output

If this is right

  • Optimal error and low empirical sensitivity cannot be achieved simultaneously for Gaussian mean estimation.
  • The sensitivity lower bound decomposes into a linear term in eta from the mean obstruction and a square-root term from the variance obstruction.
  • Recent robust mean estimators nearly match the lower bound on empirical sensitivity up to logarithmic factors.
  • The result applies under high-probability guarantees for data drawn from the Gaussian distribution.

Where Pith is reading between the lines

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

  • This tradeoff suggests that in some applications one may need to tolerate mildly suboptimal error to obtain meaningfully lower sensitivity.
  • The Efron-Stein technique for separating mean and variance obstructions could be applied to derive sensitivity bounds for other estimation problems such as covariance or linear regression.
  • Similar lower bounds on empirical sensitivity may hold for non-Gaussian distributions or under different error metrics.

Load-bearing premise

The estimator is assumed to achieve the optimal O(sqrt(d/n)) l2 error with high probability over datasets drawn from a d-dimensional Gaussian.

What would settle it

Constructing an estimator that attains O(sqrt(d/n)) error but has empirical sensitivity o(eta + sqrt(eta d/n)) with high probability over Gaussian data would falsify the lower bound.

read the original abstract

We introduce a new measure of robustness for statistical estimators, which we call \emph{empirical sensitivity}. An estimator $\hat \theta$ has bounded empirical sensitivity if, with high probability over a dataset $X = (X_1, \dots, X_n) \sim \mathcal{D}^{\otimes n}$, for any dataset $Y$ obtained by modifying at most $\eta n$ points in $X$, we have that $\hat \theta(Y)$ is close to $\hat \theta(X)$. We study bounds on this quantity for the prototypical problem of Gaussian mean estimation. We prove new lower bounds, showing that for any estimator $\hat \mu$ which achieves an optimal $\ell_2$-error bound of $O\left(\sqrt{d/n}\right)$, the empirical sensitivity is at least $\Omega\left(\eta + \sqrt{\eta d/n}\right)$. The two terms arise due to obstructions on the mean and variance (via an Efron-Stein argument) of such an estimator. We show that this bound is tight up to logarithmic factors, by employing recent results for robust empirical mean estimation.

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

1 major / 2 minor

Summary. The paper introduces empirical sensitivity as a new robustness measure for statistical estimators: with high probability over a dataset X drawn from D^n, the estimator output on any Y differing from X in at most ηn coordinates remains close to the output on X. For d-dimensional Gaussian mean estimation, it proves that any estimator achieving the optimal O(√(d/n)) ℓ₂ error must have empirical sensitivity at least Ω(η + √(η d/n)), with the two terms arising from a mean obstruction and a variance obstruction derived via the Efron-Stein inequality. The lower bound is shown to be tight up to logarithmic factors by invoking recent results on robust mean estimation.

Significance. If the lower bound holds, the work supplies a clean, first-principles characterization of the robustness cost incurred by statistically optimal estimators. The explicit separation into mean and variance obstructions, together with the matching upper bound from existing robust algorithms, gives a precise quantitative trade-off that is independent of self-referential parameters. The result is likely to be cited in future work on robust high-dimensional statistics and on sensitivity measures more generally.

major comments (1)
  1. [§3] §3 (lower-bound argument): the high-probability qualifier on the O(√(d/n)) error assumption is used to condition both the mean-obstruction and Efron-Stein pieces, yet the final Ω(η + √(η d/n)) statement does not explicitly track the failure probability; a short paragraph clarifying how the constants and logarithmic factors absorb the union bound would remove any ambiguity about the precise high-probability regime.
minor comments (2)
  1. Notation: the symbol η is used both for the contamination fraction and (implicitly) for the sensitivity radius; a brief sentence distinguishing the two usages would improve readability.
  2. [Introduction] References: the tightness claim invokes 'recent results for robust empirical mean estimation' without a specific citation in the abstract; adding the relevant reference (or a pointer to the theorem number) in the introduction would help readers locate the matching upper bound.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment of our results on empirical sensitivity. We appreciate the recommendation for minor revision and the specific suggestion to clarify the high-probability aspects of the lower bound in Section 3. We address this point below and will incorporate the requested clarification.

read point-by-point responses

  1. Referee: [§3] §3 (lower-bound argument): the high-probability qualifier on the O(√(d/n)) error assumption is used to condition both the mean-obstruction and Efron-Stein pieces, yet the final Ω(η + √(η d/n)) statement does not explicitly track the failure probability; a short paragraph clarifying how the constants and logarithmic factors absorb the union bound would remove any ambiguity about the precise high-probability regime.

    Authors: We agree that explicitly tracking the failure probability improves clarity. In the revised version we will insert a short paragraph at the conclusion of Section 3 noting that the Ω(η + √(η d/n)) lower bound is stated in the same high-probability regime as the O(√(d/n)) error assumption. The constants hidden by the Ω notation are chosen large enough that a union bound over the (finitely many) events appearing in the mean-obstruction and Efron-Stein arguments is absorbed into the logarithmic factors already present in the bound; consequently the failure probability remains o(1) and does not alter the asymptotic form. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The lower bound derivation relies on an Efron-Stein inequality applied to the variance obstruction and a separate mean-obstruction argument, both conditioned on the external optimality assumption of O(√(d/n)) ℓ₂ error under Gaussian data. These are standard first-principles concentration tools that do not reduce to any fitted parameters, self-definitions, or the paper's own constructions. Tightness up to logs is established by citing external recent results on robust mean estimation rather than self-citations or internal ansatzes. The argument separates cleanly into independent components with no load-bearing self-referential steps, rendering the central claim self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard domain assumptions for Gaussian mean estimation and on the optimality of the estimator under consideration. No free parameters are fitted inside the paper, and no new entities are postulated.

axioms (2)
  • domain assumption Data points are drawn i.i.d. from a d-dimensional Gaussian distribution.
    Invoked throughout the mean estimation problem and the error-rate assumption.
  • domain assumption The estimator achieves the optimal ℓ₂ error rate O(√(d/n)) with high probability.
    This optimality premise is required for the Efron-Stein and mean-obstruction arguments to produce the stated sensitivity lower bound.

pith-pipeline@v0.9.0 · 5747 in / 1548 out tokens · 42760 ms · 2026-05-22T03:23:16.546712+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

300 extracted references · 300 canonical work pages · 9 internal anchors

  1. [1]

    Journal of the Royal Statistical Society

    Pyke, Ronald , title =. Journal of the Royal Statistical Society. Series B (Methodological) , volume =

    work page

  2. [2]

    Proceedings of the 40th International Conference on Machine Learning , series =

    Data Structures for Density Estimation , author =. Proceedings of the 40th International Conference on Machine Learning , series =. 2023 , publisher =

    work page 2023

  3. [3]

    Advances in Neural Information Processing Systems 37 , series =

    Statistical-Computational Trade-offs for Density Estimation , author =. Advances in Neural Information Processing Systems 37 , series =. 2024 , pages =

    work page 2024

  4. [4]

    Proceedings of the 50th Annual ACM Symposium on the Theory of Computing , series =

    Aaronson, Scott , title =. Proceedings of the 50th Annual ACM Symposium on the Theory of Computing , series =. 2018 , pages =

    work page 2018

  5. [5]

    arXiv preprint arXiv:1802.09025 , year =

    Online Learning of Quantum States , author =. arXiv preprint arXiv:1802.09025 , year =

    work page arXiv

  6. [6]

    TensorFlow: A System for Large-Scale Machine Learning , booktitle =

    Abadi, Mart. TensorFlow: A System for Large-Scale Machine Learning , booktitle =. 2016 , pages =

    work page 2016

  7. [7]

    Proceedings of the 2016 ACM Conference on Computer and Communications Security , series =

    Deep Learning with Differential Privacy , author =. Proceedings of the 2016 ACM Conference on Computer and Communications Security , series =. 2016 , publisher =

    work page 2016

  8. [8]

    American Economic Review: Insights , volume =

    Abadie, Alberto , title =. American Economic Review: Insights , volume =. 2020 , publisher =

    work page 2020

  9. [9]

    , title =

    Abbeel, Pieter and Koller, Daphne and Ng, Andrew Y. , title =. Journal of Machine Learning Research , volume =. 2006 , publisher =

    work page 2006

  10. [10]

    Harvard Data Science Review , year =

    Abowd, John and Ashmead, Robert and Cumings-Menon, Ryan and Garfinkel, Simson and Heineck, Micah and Heiss, Christine and Johns, Robert and Kifer, Daniel and Leclerc, Philip and Machanavajjhala, Ashwin and Moran, Brett and Sexton, William and Spence, Matthew and Zhuravlev, Pavel , title =. Harvard Data Science Review , year =

    work page

  11. [11]

    Advances in Neural Information Processing Systems 31 , series =

    Learning and Testing Causal Models with Interventions , author =. Advances in Neural Information Processing Systems 31 , series =. 2018 , publisher =

    work page 2018

  12. [12]

    Test without Trust: Optimal Locally Private Distribution Testing , booktitle =

    Acharya, Jayadev and Canonne, Cl. Test without Trust: Optimal Locally Private Distribution Testing , booktitle =. 2019 , publisher =

    work page 2019

  13. [13]

    Distributed Simulation and Distributed Inference

    Distributed Simulation and Distributed Inference , author =. arXiv preprint arXiv:1804.06952 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  14. [14]

    Inference under Information Constraints: Lower Bounds from Chi-Square Contraction , booktitle =

    Acharya, Jayadev and Canonne, Cl. Inference under Information Constraints: Lower Bounds from Chi-Square Contraction , booktitle =. 2019 , pages =

    work page 2019

  15. [15]

    Adaptive Estimation in Weighted Group Testing , booktitle =

    Acharya, Jayadev and Canonne, Cl. Adaptive Estimation in Weighted Group Testing , booktitle =. 2015 , pages =

    work page 2015

  16. [16]

    A Chasm Between Identity and Equivalence Testing with Conditional Queries , booktitle =

    Acharya, Jayadev and Canonne, Cl. A Chasm Between Identity and Equivalence Testing with Conditional Queries , booktitle =. 2015 , pages =

    work page 2015

  17. [17]

    A Chasm Between Identity and Equivalence Testing with Conditional Queries , journal =

    Acharya, Jayadev and Canonne, Cl. A Chasm Between Identity and Equivalence Testing with Conditional Queries , journal =. 2018 , volume =

    work page 2018

  18. [18]

    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms , series =

    Acharya, Jayadev and Daskalakis, Constantinos , title =. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms , series =. 2015 , pages =

    work page 2015

  19. [19]

    Proceedings of the 24th Annual Conference on Learning Theory , series =

    Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun , title =. Proceedings of the 24th Annual Conference on Learning Theory , series =. 2011 , pages =

    work page 2011

  20. [20]

    Proceedings of the 25th Annual Conference on Learning Theory , series =

    Acharya, Jayadev and Das, Hirakendu and Jafarpour, Ashkan and Orlitsky, Alon and Pan, Shengjun and Suresh, Ananda , title =. Proceedings of the 25th Annual Conference on Learning Theory , series =. 2012 , pages =

    work page 2012

  21. [21]

    Advances in Neural Information Processing Systems 28 , series =

    Acharya, Jayadev and Daskalakis, Constantinos and Kamath, Gautam , title =. Advances in Neural Information Processing Systems 28 , series =. 2015 , pages =

    work page 2015

  22. [22]

    Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms , series =

    Acharya, Jayadev and Diakonikolas, Ilias and Li, Jerry and Schmidt, Ludwig , title =. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms , series =. 2017 , pages =

    work page 2017

  23. [23]

    Proceedings of the 34th International Conference on Machine Learning , series =

    Acharya, Jayadev and Das, Hirakendu and Orlitsky, Alon and Suresh, Ananda Theertha , title =. Proceedings of the 34th International Conference on Machine Learning , series =. 2017 , pages =

    work page 2017

  24. [24]

    Journal of Machine Learning Research , volume =

    Acharya, Jayadev and Falahatgar, Moein and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha , title =. Journal of Machine Learning Research , volume =. 2018 , publisher =

    work page 2018

  25. [25]

    arXiv preprint arXiv:1711.00814 , year =

    Measuring Quantum Entropy , author =. arXiv preprint arXiv:1711.00814 , year =

    work page arXiv

  26. [26]

    Proceedings of the 35th Annual Conference on Learning Theory , series =

    Acharya, Jayadev and Jain, Ayush and Kamath, Gautam and Suresh, Ananda Theertha and Zhang, Huanyu , title =. Proceedings of the 35th Annual Conference on Learning Theory , series =. 2022 , pages =

    work page 2022

  27. [27]

    Proceedings of the 16th International Conference on Artificial Intelligence and Statistics , series =

    Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha , title =. Proceedings of the 16th International Conference on Artificial Intelligence and Statistics , series =. 2013 , pages =

    work page 2013

  28. [28]

    Proceedings of the 2014 IEEE International Symposium on Information Theory , series =

    Acharya, Jayadev and Jafarpour, Ashkan and Orlitsky, Alon and Suresh, Ananda Theertha , title =. Proceedings of the 2014 IEEE International Symposium on Information Theory , series =. 2014 , pages =

    work page 2014

  29. [29]

    Proceedings of the 35th International Conference on Machine Learning , series =

    INSPECTRE: Privately Estimating the Unseen , author =. Proceedings of the 35th International Conference on Machine Learning , series =. 2018 , pages =

    work page 2018

  30. [30]

    The Journal of Privacy and Confidentiality , year =

    INSPECTRE: Privately Estimating the Unseen , author =. The Journal of Privacy and Confidentiality , year =

    work page

  31. [31]

    Proceedings of the 26th International Conference on Artificial Intelligence and Statistics , series =

    Acharya, Jayadev and Liu, Yuhan and Sun, Ziteng , title =. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics , series =. 2023 , pages =

    work page 2023

  32. [32]

    IEEE Transactions on Information Theory , year =

    Acharya, Jayadev and Orlitsky, Alon and Suresh, Ananda Theertha and Tyagi, Himanshu , title =. IEEE Transactions on Information Theory , year =

    work page

  33. [33]

    Advances in Neural Information Processing Systems 31 , series =

    Differentially Private Testing of Identity and Closeness of Discrete Distributions , author =. Advances in Neural Information Processing Systems 31 , series =. 2018 , publisher =

    work page 2018

  34. [34]

    Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics , series =

    Acharya, Jayadev and Sun, Ziteng and Zhang, Huanyu , title =. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics , series =. 2019 , publisher =

    work page 2019

  35. [35]

    Proceedings of the 32nd International Conference on Algorithmic Learning Theory , series =

    Differentially Private Assouad, Fano, and Le Cam , author =. Proceedings of the 32nd International Conference on Algorithmic Learning Theory , series =. 2021 , publisher =

    work page 2021

  36. [36]

    Journal of Computer and System Sciences , year =

    Achlioptas, Dimitris , title =. Journal of Computer and System Sciences , year =

    work page

  37. [37]

    Proceedings of the 18th Annual Conference on Learning Theory , series =

    Achlioptas, Dimitris and McSherry, Frank , title =. Proceedings of the 18th Annual Conference on Learning Theory , series =. 2005 , pages =

    work page 2005

  38. [38]

    and Worthmann, John C

    Adam, Nabil R. and Worthmann, John C. , title =. ACM Computing Surveys (CSUR) , volume =. 1989 , publisher =

    work page 1989

  39. [39]

    A Note on Concentration for Polynomials in the

    Adamczak, Rados. A Note on Concentration for Polynomials in the. Electronic Journal of Probability , year =

    work page

  40. [40]

    Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms , series =

    Adamaszek, Michat and Czumaj, Artur and Sohler, Christian , title =. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms , series =. 2010 , pages =

    work page 2010

  41. [41]

    2021 , publisher =

    On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians , booktitle =. 2021 , publisher =

    work page 2021

  42. [42]

    Advances in Neural Information Processing Systems 34 , series =

    Privately Learning Mixtures of Axis-Aligned Gaussians , author =. Advances in Neural Information Processing Systems 34 , series =. 2021 , publisher =

    work page 2021

  43. [43]

    Adell, Jos. Exact. Journal of Inequalities and Applications , volume =. 2006 , publisher =

    work page 2006

  44. [44]

    Learning with Privacy at Scale , year =

    work page

  45. [45]

    Proceedings of the 35th International Conference on Algorithmic Learning Theory , series =

    Afzali, Mohammad and Ashtiani, Hassan and Liaw, Christopher , title =. Proceedings of the 35th International Conference on Algorithmic Learning Theory , series =. 2024 , pages =

    work page 2024

  46. [46]

    Proceedings of the 30th Annual Conference on Learning Theory , series =

    Agarwal, Arpit and Agarwal, Shivani and Assadi, Sepehr and Khanna, Sanjeev , title =. Proceedings of the 30th Annual Conference on Learning Theory , series =. 2017 , pages =

    work page 2017

  47. [47]

    Auto-Vectorizing TensorFlow Graphs: Jacobians, Auto-Batching And Beyond

    Auto-Vectorizing TensorFlow Graphs: Jacobians, Auto-Batching And Beyond , author =. arXiv preprint arXiv:1903.04243 , year =

    work page internal anchor Pith review Pith/arXiv arXiv 1903

  48. [48]

    Agarwal, Naman and Kairouz, Peter and Liu, Ziyu , booktitle =. The. 2021 , publisher =

    work page 2021

  49. [49]

    Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms , series =

    Agarwal, Sushant and Kamath, Gautam and Majid, Mahbod and Mouzakis, Argyris and Silver, Rose and Ullman, Jonathan , title =. Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms , series =. 2025 , pages =

    work page 2025

  50. [50]

    Agarwal, Naman and Suresh, Ananda Theertha and Yu, Felix Xinnan X and Kumar, Sanjiv and McMahan, Brendan , booktitle =. cp. 2018 , publisher =

    work page 2018

  51. [51]

    Intrinsic Dimensionality Explains the Effectiveness of Language Model Fine-Tuning , author =. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers) , series =. 2021 , publisher =

    work page 2021

  52. [52]

    , title =

    Agrawal, Dakshi and Aggarwal, Charu C. , title =. Proceedings of the 20th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , series =. 2001 , pages =

    work page 2001

  53. [53]

    Categorical Data Analysis , year =

    Agresti, Alan , publisher =. Categorical Data Analysis , year =

    work page

  54. [54]

    Sorting and Selection with Imprecise Comparisons , booktitle =

    Ajtai, Mikl. Sorting and Selection with Imprecise Comparisons , booktitle =

    work page

  55. [55]

    An O(n n) Sorting Network , booktitle =

    Ajtai, Mikl. An O(n n) Sorting Network , booktitle =. 1983 , pages =

    work page 1983

  56. [56]

    Deterministic Selection in O( n) Parallel Time , booktitle =

    Ajtai, Mikl. Deterministic Selection in O( n) Parallel Time , booktitle =. 1986 , pages =

    work page 1986

  57. [57]

    Privately estimating a

    Alabi, Daniel and Kothari, Pravesh K and Tankala, Pranay and Venkat, Prayaag and Zhang, Fred , booktitle =. Privately estimating a. 2023 , publisher =

    work page 2023

  58. [58]

    Proceedings of the 35th International Conference on Machine Learning , series =

    Differentially Private Identity and Closeness Testing of Discrete Distributions , author =. Proceedings of the 35th International Conference on Machine Learning , series =. 2018 , pages =

    work page 2018

  59. [59]

    Advances in Neural Information Processing Systems 32 , series =

    Private Testing of Distributions via Sample Permutations , author =. Advances in Neural Information Processing Systems 32 , series =. 2019 , pages =

    work page 2019

  60. [60]

    Advances in Neural Information Processing Systems 36 , series =

    Hypothesis Selection with Memory Constraints , author =. Advances in Neural Information Processing Systems 36 , series =. 2023 , pages =

    work page 2023

  61. [61]

    Advances in Neural Information Processing Systems 37 , series =

    Optimal Hypothesis Selection in (Almost) Linear Time , author =. Advances in Neural Information Processing Systems 37 , series =. 2024 , pages =

    work page 2024

  62. [62]

    Proceedings of the 17th Annual ACM Symposium on the Theory of Computing , series =

    Alon, Noga , title =. Proceedings of the 17th Annual ACM Symposium on the Theory of Computing , series =. 1985 , pages =

    work page 1985

  63. [63]

    SIAM Journal on Computing , year =

    Alon, Noga and Azar, Yossi , title =. SIAM Journal on Computing , year =

    work page

  64. [64]

    SIAM Journal on Discrete Mathematics , year =

    Alon, Noga and Azar, Yossi , title =. SIAM Journal on Discrete Mathematics , year =

    work page

  65. [65]

    Proceedings of the 39th Annual ACM Symposium on the Theory of Computing , series =

    Alon, Noga and Andoni, Alexandr and Kaufman, Tali and Matulef, Kevin and Rubinfeld, Ronitt and Xie, Ning , title =. Proceedings of the 39th Annual ACM Symposium on the Theory of Computing , series =. 2007 , pages =

    work page 2007

  66. [66]

    Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science , series =

    Alon, Noga and Azar, Yossi and Vishkin, Uzi , title =. Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science , series =. 1986 , pages =

    work page 1986

  67. [67]

    Advances in Neural Information Processing Systems 32 , series =

    Limits of Private Learning with Access to Public Data , author =. Advances in Neural Information Processing Systems 32 , series =. 2019 , pages =

    work page 2019

  68. [68]

    Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science , series =

    Alon, Noga and Klartag, Bo'az , title =. Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science , series =. 2017 , pages =

    work page 2017

  69. [69]

    Random Structures and Algorithms , pages =

    Finding a Large Hidden Clique in a Random Graph , author =. Random Structures and Algorithms , pages =

    work page

  70. [70]

    Proceedings of the 51st Annual ACM Symposium on the Theory of Computing , series =

    Alon, Noga and Livni, Roi and Malliaris, Maryanthe and Moran, Shay , title =. Proceedings of the 51st Annual ACM Symposium on the Theory of Computing , series =. 2019 , pages =

    work page 2019

  71. [71]

    Journal of Computer and System Sciences , year =

    Alon, Noga and Matias, Yossi and Szegedy, Mario , title =. Journal of Computer and System Sciences , year =

    work page

  72. [72]

    Proceedings of the 39th International Conference on Machine Learning , series =

    Public Data-Assisted Mirror Descent for Private Model Training , author =. Proceedings of the 39th International Conference on Machine Learning , series =. 2022 , publisher =

    work page 2022

  73. [73]

    Advances in Neural Information Processing Systems 32 , series =

    Differentially Private Covariance Estimation , author =. Advances in Neural Information Processing Systems 32 , series =. 2019 , pages =

    work page 2019

  74. [74]

    arXiv preprint arXiv:1911.01452 , year =

    Pan-Private Uniformity Testing , author =. arXiv preprint arXiv:1911.01452 , year =

    work page arXiv 1911

  75. [75]

    Proceedings of the 36th International Conference on Machine Learning , series =

    Amin, Kareem and Kulesza, Alex and Munoz, Andres and Vassilvtiskii, Sergei , title =. Proceedings of the 36th International Conference on Machine Learning , series =. 2019 , pages =

    work page 2019

  76. [76]

    , title =

    Anderson, Joseph and Belkin, Mikhail and Goyal, Navin and Rademacher, Luis and Voss, James R. , title =. Proceedings of the 27th Annual Conference on Learning Theory , series =. 2014 , pages =

    work page 2014

  77. [77]

    Proceedings of the 57th Annual ACM Symposium on the Theory of Computing , series =

    Sample-Optimal Private Regression in Polynomial Time , author =. Proceedings of the 57th Annual ACM Symposium on the Theory of Computing , series =. 2025 , pages =

    work page 2025

  78. [78]

    Advances in Neural Information Processing Systems 34 , series =

    Differentially Private Learning with Adaptive Clipping , author =. Advances in Neural Information Processing Systems 34 , series =. 2021 , publisher =

    work page 2021

  79. [79]

    To Shuffle or not to Shuffle: Auditing

    Annamalai, Meenatchi Sundaram Muthu Selva and Balle, Borja and De Cristofaro, Emiliano and Hayes, Jamie , journal =. To Shuffle or not to Shuffle: Auditing

    work page

  80. [80]

    Machine Learning , volume =

    Angluin, Dana , title =. Machine Learning , volume =. 1988 , publisher =

    work page 1988

Showing first 80 references.