Predictability as a Fine-Grained Measure for Privacy

Karthik Sridharan; Linda Lu

arxiv: 2606.20546 · v1 · pith:XQ2AJGG2 · submitted 2026-06-18 · cs.LG

Predictability as a Fine-Grained Measure for Privacy

Linda Lu , Karthik Sridharan This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-26 17:31 UTCgrok-4.3pith:XQ2AJGG2 record.json open to challenge →

classification cs.LG

keywords predictabilityprivacydifferential privacygeneralized method of momentsstochastic processesoutput perturbationempirical risk minimizationmutual information

0 comments

The pith

Privacy via predictability measures leakage as the extra predictive power an algorithm output gives on sensitive queries about uncompromised individuals.

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

The paper defines predictability as the gain in an attacker's ability to predict sensitive information about unknown individuals from the algorithm output, after already using knowledge of a compromised data portion generated by a stochastic process. This produces a privacy metric that incorporates the attacker's specific knowledge and a chosen family of queries, making it finer-grained than differential privacy. The two measures are shown to be incomparable in general, yet predictability implies mutual-information differential privacy when all but one individual is compromised and queries are binary. A generalized method of moments framework analyzes asymptotic predictability under stationary ergodic mixing processes and yields a calibrated output perturbation for empirical risk minimization.

Core claim

Predictability is the incremental improvement in an attacker's ability to predict sensitive information about unknown individuals from the algorithm's output, beyond what is inferable from the compromised data portion. In the regime where all but one record is compromised and all binary queries are sensitive, this measure implies mutual-information differential privacy. A GMM-based analysis under stationary ergodic mixing processes enables derivation of predictability-calibrated perturbation schemes for ERM algorithms.

What carries the argument

Generalized method of moments analysis of asymptotic predictability for data generated by stationary, ergodic, mixing stochastic processes, which supports construction of output perturbations that control predictability.

If this is right

Predictability and differential privacy are incomparable: each can be small while the other is large.
In the worst-case regime where all but one individual is compromised and all binary queries are sensitive, predictability implies mutual-information DP.
The GMM framework permits asymptotic analysis of predictability when the compromised data follows a stationary, ergodic, mixing process.
A predictability-calibrated output perturbation scheme exists for empirical risk minimization.
Predictability supplies finer-grained control by tailoring the metric to specific sensitive information and attacker models.

Where Pith is reading between the lines

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

Mechanisms could achieve higher accuracy by exploiting known structure in the data generation process instead of worst-case assumptions.
Layering predictability with DP could protect against both known and unknown threats in the same system.
The GMM approach could extend to other algorithms or mildly non-stationary processes if the mixing condition is relaxed appropriately.
Finite-sample predictability could be validated directly on synthetic data drawn from mixing processes to test the asymptotic bounds.

Load-bearing premise

The compromised portion of the dataset is generated by a stationary, ergodic, mixing stochastic process.

What would settle it

A concrete instance with all but one record compromised and binary queries where predictability is small yet the mutual information between the output and the sensitive bit on the remaining record is large.

read the original abstract

Differential privacy (DP) ensures rigorous individual-level privacy guarantees against even the most knowledgeable attackers, but its worst-case nature can impose a costly privacy-accuracy tradeoff. We introduce privacy via predictability, a fine-grained framework that explicitly incorporates the attacker's core knowledge, a compromised portion of the dataset generated by a stochastic process, and a specified family of queries. Predictability measures privacy leakage as the incremental gain in an attacker's ability to predict sensitive information about unknown individuals after observing the algorithm's output, beyond what can already be inferred from the compromised data. We show that predictability and DP are generally incomparable: each can be small while the other is large. However, in the worst-case regime where all but one individual is compromised, and all binary queries are considered sensitive, predictability implies mutual-information DP. More generally, predictability provides a finer-grained privacy metric tailored to specific sensitive information and specific attacker models. We introduce a general framework, using the generalized method of moments (GMM), to analyze asymptotic predictability when the compromised data is generated by a stationary, ergodic, mixing process. Using this analysis, we derive a predictability-calibrated output perturbation scheme for ERM. Our approach is complementary to DP and can be used alongside DP to provide fine-grained privacy control.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Predictability gives a tunable privacy metric weaker than DP when attacker knowledge is partial, but the ERM perturbation scheme rests on a strong assumption about the data process.

read the letter

The paper defines predictability as the extra ability an attacker gains to predict sensitive info about uncompromised individuals after seeing the output, on top of what they already know from the compromised part of the data. It shows this measure is generally incomparable to differential privacy, yet implies mutual-information DP in the worst case where only one record is uncompromised and all binary queries count as sensitive. They also supply a GMM framework to analyze asymptotic predictability when the compromised data comes from a stationary ergodic mixing process, and they use that to build a predictability-calibrated output perturbation for ERM.

The definition itself is the clearest addition. It makes the attacker's prior knowledge and the query family explicit parameters, which lets the privacy level adjust to the actual setting instead of always taking the worst case. That is a reasonable direction if the goal is to avoid over-protecting against unrealistic attackers.

The main limitation is the mixing and ergodicity requirement for the GMM analysis and the resulting perturbation scheme. Real datasets often have long-range dependence or non-stationarity, so the concrete algorithmic contribution would lose its justification outside that regime. The incomparability and worst-case implication do not rely on the assumption, but without the full proofs it is hard to see how tight those results are or whether the derivation introduces hidden circularity.

This is for researchers who already work on privacy notions that try to incorporate partial attacker knowledge. A reader looking for complements to DP rather than replacements would find the framing useful. The work deserves a serious referee because the core idea is cleanly stated and the worst-case link to MI-DP is worth checking in detail, even if the GMM part needs the assumption to hold.

Referee Report

2 major / 1 minor

Summary. The paper introduces 'privacy via predictability,' a fine-grained privacy framework that measures leakage as the incremental gain in an attacker's ability to predict sensitive attributes of unknown individuals after observing an algorithm's output, given a compromised portion of the dataset generated by a stochastic process and a specified family of queries. It establishes general incomparability between predictability and differential privacy, shows that predictability implies mutual-information DP in the worst-case regime (all but one individual compromised, all binary queries sensitive), and develops a GMM-based framework for asymptotic predictability analysis under stationary ergodic mixing processes, from which a predictability-calibrated output perturbation scheme for ERM is derived. The approach is positioned as complementary to DP.

Significance. If the formal results and derivations hold, the work provides a useful complementary metric to DP by explicitly modeling partial attacker knowledge and query families, enabling finer control over privacy-accuracy tradeoffs. The worst-case implication to MI-DP is a concrete bridge to existing privacy notions, and the GMM analysis under explicit stochastic assumptions is a methodological strength for asymptotic regimes. The ERM perturbation scheme offers a practical instantiation.

major comments (2)

[GMM analysis framework (abstract and associated sections)] The GMM framework for asymptotic predictability (and the derived predictability-calibrated output perturbation for ERM) is explicitly conditioned on the compromised data being generated by a stationary, ergodic, mixing stochastic process. This assumption is load-bearing for the algorithmic contribution, as violations (e.g., long-range dependence or non-stationarity common in real datasets) would invalidate the GMM conditions and the resulting bounds.
[Worst-case implication to MI-DP (abstract and associated sections)] The claim that predictability implies mutual-information DP in the worst-case regime (all but one individual compromised, all binary queries sensitive) is stated as a derived result. Without the explicit definitions of predictability, the formalization of the implication, or the proof details, it is not possible to assess whether the implication is independent or follows tautologically from the definitions.

minor comments (1)

[Abstract] The abstract states the incomparability result and the worst-case implication but does not preview the precise conditions or counter-examples; expanding this would improve clarity for readers.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback and for recognizing the potential of predictability as a complementary privacy metric. We address each major comment below with specific responses and proposed revisions where appropriate.

read point-by-point responses

Referee: [GMM analysis framework (abstract and associated sections)] The GMM framework for asymptotic predictability (and the derived predictability-calibrated output perturbation for ERM) is explicitly conditioned on the compromised data being generated by a stationary, ergodic, mixing stochastic process. This assumption is load-bearing for the algorithmic contribution, as violations (e.g., long-range dependence or non-stationarity common in real datasets) would invalidate the GMM conditions and the resulting bounds.

Authors: We agree that the GMM framework is conditioned on the compromised data following a stationary, ergodic, mixing process, as explicitly stated in the abstract and developed in the relevant sections. This assumption enables the asymptotic analysis and the derivation of the calibrated perturbation scheme. We will revise the manuscript to add an expanded discussion subsection on the scope and limitations of these assumptions, including examples of when they may not hold (e.g., non-stationary data) and noting that the results apply in regimes satisfying the conditions. This addresses the concern without changing the core technical contribution. revision: partial
Referee: [Worst-case implication to MI-DP (abstract and associated sections)] The claim that predictability implies mutual-information DP in the worst-case regime (all but one individual compromised, all binary queries sensitive) is stated as a derived result. Without the explicit definitions of predictability, the formalization of the implication, or the proof details, it is not possible to assess whether the implication is independent or follows tautologically from the definitions.

Authors: The definitions of predictability (including the incremental predictive gain measure) are provided in Section 2, with the formal definition in Definition 2.3. The worst-case implication is stated and proved as Theorem 4.2 in Section 4, showing that zero predictability implies the relevant mutual information term vanishes in the specified regime (all but one compromised, binary queries). The proof in Appendix C establishes the connection by relating the predictability metric to conditional mutual information under the worst-case attacker; it is not tautological, as it requires a non-trivial bounding argument. We will revise to include a high-level proof sketch in the main text of Section 4 to facilitate assessment. revision: partial

Circularity Check

0 steps flagged

No significant circularity; new definition and GMM analysis are self-contained

full rationale

The paper defines predictability directly as incremental predictive gain beyond compromised data, states incomparability with DP, and derives a worst-case implication to mutual-information DP without visible reduction to tautology. The GMM asymptotic analysis is applied under an explicitly declared assumption (stationary ergodic mixing process) rather than smuggling an ansatz or renaming a fitted quantity as a prediction. No load-bearing self-citations, self-definitional loops, or uniqueness theorems imported from the authors' prior work appear in the provided text. The algorithmic perturbation scheme follows from the stated framework and assumptions, keeping the derivation independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review limited to abstract; ledger entries are inferred from stated assumptions. The central claim rests on the stochastic-process assumption for the compromised data and on the choice of query family and sensitive information.

axioms (1)

domain assumption Compromised data generated by a stationary, ergodic, mixing stochastic process
Required for the generalized method of moments asymptotic analysis

pith-pipeline@v0.9.1-grok · 5750 in / 1326 out tokens · 34886 ms · 2026-06-26T17:31:51.560679+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

61 extracted references · 2 canonical work pages

[1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016

2016
[2]

Adeleye, S

T. Adeleye, S. Berghel, D. Desfontaines, M. Hay, I. Johnson, C. Lemoisson, A. Machanavajjhala, T. Magerlein, G. Modena, D. Pujol, D. Simmons-Marengo, and H. Triedman. Publishing wikipedia usage data with strong privacy guarantees, 2023

2023
[3]

T. W. Anderson.An Introduction to Multivariate Statistical Analysis. Wiley, New York, 3 edition, 2003

2003
[4]

Apple differential privacy technical overview, 2016

Apple Inc. Apple differential privacy technical overview, 2016

2016
[5]

R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds, 2014. 10

2014
[6]

P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: risk bounds and structural results.Journal of Machine Learning Research, 3:463–482, Mar. 2003

2003
[7]

Bassily, A

R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 439–448, 2013

2013
[8]

Ben-Sasson and R

H. Ben-Sasson and R. Greenberg. 38tb of data accidentally ex- posed by microsoft ai researchers. https://www.wiz.io/blog/ 38-terabytes-of-private-data-accidentally-exposed-by-microsoft-ai-researchers? utm_source=chatgpt.com, 2023

2023
[9]

Berghel, P

S. Berghel, P. Bohannon, D. Desfontaines, C. Estes, S. Haney, L. Hartman, M. Hay, A. Machanavajjhala, T. Magerlein, G. Miklau, A. Pai, W. Sexton, and R. Shrestha. Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy. arXiv preprint arXiv:2212.04133, Dec. 2022

work page arXiv 2022
[10]

Berrios, J

N. Berrios, J. Fitzsimons, and S. Hod. The privacy deployments registry, 2024

2024
[11]

P. J. Bickel, C. A. J. Klaassen, Y . Ritov, and J. A. Wellner.Efficient and Adaptive Estimation for Semiparametric Models. Johns Hopkins University Press, 1993

1993
[12]

A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. InProceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 609–618, New York, NY , USA, 2008. Association for Computing Machinery

2008
[13]

Carlini, F

N. Carlini, F. Tramèr, E. Wallace, M. Jagielski, A. Herbert-V oss, K. Lee, A. Roberts, T. Brown, D. Song, Ú. Erlingsson, A. Oprea, and C. Raffel. Extracting training data from large language models. In30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650. USENIX Association, Aug. 2021

2021
[14]

Chaudhuri, S

K. Chaudhuri, S. M. Kakade, K. Livescu, and K. Sridharan. Multi-view clustering via canonical correlation analysis. InProceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 129–136, New York, NY , USA, 2009. Association for Computing Machinery

2009
[15]

Chaudhuri, C

K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization.J. Mach. Learn. Res., 12(null):1069–1109, July 2011

2011
[16]

A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Y . Ishai and V . Rijmen, editors,Advances in Cryptology – EUROCRYPT 2019, pages 375–403, Cham, 2019. Springer International Publishing

2019
[17]

Cuff and L

P. Cuff and L. Yu. Differential privacy as a mutual information constraint. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016

2016
[18]

J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy, 2019

2019
[19]

Dovonon, Y

P. Dovonon, Y . F. Atchadé, and F. Doko Tchatoka. Efficiency bounds for moment condition models with mixed identification strength.Journal of Econometrics, 248:105723, 2025

2025
[20]

C. Dwork. Differential privacy. In M. Bugliesi, B. Preneel, V . Sassone, and I. Wegener, editors, Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

2006
[21]

C. Dwork. Differential privacy: A survey of results. In M. Agrawal, D. Du, Z. Duan, and A. Li, editors,Theory and Applications of Models of Computation, pages 1–19, Berlin, Heidelberg,
[22]

Springer Berlin Heidelberg
[23]

Dwork, F

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors,Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. 11

2006
[24]

Dwork, M

C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. Pan-private streaming algorithms. InInternational Conference on Supercomputing, 2010

2010
[25]

Dwork, A

C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

2014
[26]

Gehrke, E

J. Gehrke, E. Lui, and R. Pass. Towards privacy for social networks: A zero-knowledge based definition of privacy. In Y . Ishai, editor,Theory of Cryptography, pages 432–449, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

2011
[27]

Ghazi, N

B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. Deep learning with label differential privacy, 2021

2021
[28]

Ghosal and A

S. Ghosal and A. van der Vaart.Fundamentals of Nonparametric Bayesian Inference. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017

2017
[29]

Ghosh and R

A. Ghosh and R. Kleinberg. Inferential privacy guarantees for differentially private mechanisms, 2017

2017
[30]

Gianola and K

M. Gianola and K. Pachacz. Introducing bigquery differential privacy and partnership with tumult labs, May 8 2023

2023
[31]

R. Hall, A. Rinaldo, and L. Wasserman. Random differential privacy, 2011

2011
[33]

L. P. Hansen. Large sample properties of generalized method of moments estimators.Econo- metrica, 50(4):1029–1054, 1982

1982
[34]

L. P. Hansen.Generalized method of moments estimation, pages 105–118. Palgrave Macmillan UK, London, 2010

2010
[35]

X. He, A. Machanavajjhala, and B. Ding. Blowfish privacy: tuning privacy-utility trade- offs using policies. InProceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD/PODS’14. ACM, June 2014

2014
[36]

Horowitz

J. Horowitz. A uniform law of large numbers and empirical central limit theorem for limits of finite populations.Statistics & Probability Letters, 10(2):159–166, 1990

1990
[37]

Jiang, F

Y . Jiang, F. Fu, X. Miao, X. Nie, and B. Cui. Osdp: Optimal sharded data parallel for distributed deep learning. In E. Elkind, editor,Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 2142–2150. International Joint Conferences on Artificial Intelligence Organization, 8 2023. Main Track

2023
[38]

S. M. Kakade and D. P. Foster. Multi-view regression via canonical correlation analysis. In N. H. Bshouty and C. Gentile, editors,Learning Theory, pages 82–96, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

2007
[39]

S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In D. Koller, D. Schuurmans, Y . Bengio, and L. Bottou, editors,Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008

2008
[40]

Kifer and A

D. Kifer and A. Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Trans. Database Syst., 39(1), Jan. 2014

2014
[41]

Ligett, C

K. Ligett, C. Peale, and O. Reingold. Bounded-Leakage Differential Privacy. In A. Roth, editor, 1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

2020
[42]

C. Mauran. 200,000 facebook marketplace user records were leaked on the dark web. https: //mashable.com/article/facebook-marketplace-data-breach-details, 2024. 12

2024
[43]

McFadden.Econometrics 240B Second Half Reader

D. McFadden.Econometrics 240B Second Half Reader. 1999

1999
[44]

McMahan, E

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In A. Singh and J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 ofProceedings of Machine Learning Research, pages 1273–1282. PMLR, 20–22 Apr 2017

2017
[45]

I. Mironov. Rényi differential privacy. In2017 IEEE 30th Computer Security Foundations Symposium (CSF), page 263–275. IEEE, Aug. 2017

2017
[46]

L. H. Newman. 1.2 billion records found exposed online in a single server. https://www. wired.com/story/billion-records-exposed-online/, 2019

2019
[47]

Nuradha and Z

T. Nuradha and Z. Goldfeld. Pufferfish privacy: An information-theoretic study.IEEE Transac- tions on Information Theory, 69(11):7336–7356, Nov. 2023

2023
[48]

Prášková and P

Z. Prášková and P. Sen. Asymptotics in finite population sampling.Handbook of Statistics, 29:489–522, 12 2009

2009
[49]

Rogers, S

R. Rogers, S. Subramaniam, S. Peng, D. Durfee, S. Lee, S. K. Kancha, S. Sahay, and P. Aham- mad. Linkedin’s audience engagements api: A privacy preserving data analytics system at scale, 2020

2020
[50]

Sindhwani, P

V . Sindhwani, P. Niyogi, and M. Belkin. A co-regularization approach to semi-supervised learning with multiple views. InProceedings of the Workshop on Learning with Multiple Views, 22nd ICML, 2005

2005
[51]

Sridharan and S

K. Sridharan and S. Kakade. An information theoretic framework for multi-view learning. In Conference on Learning Theory, pages 403–414, 01 2008

2008
[52]

Steinke and L

T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual informa- tion, 2020

2020
[53]

Triastcyn and B

A. Triastcyn and B. Faltings. Bayesian differential privacy for machine learning, 2020

2020
[54]

Losing face: Two more cases of third-party facebook app data exposure

UpGuard Team. Losing face: Two more cases of third-party facebook app data exposure. https://www.upguard.com/breaches/facebook-user-data-leak, 2019

2019
[55]

Census bureau sets key parameters to protect privacy in 2020 census results, 2021

US Census Bureau. Census bureau sets key parameters to protect privacy in 2020 census results, 2021

2020
[56]

A. W. van der Vaart.Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998

1998
[57]

J. G. Wang, J. Wang, M. Li, and S. Neel. Pandora’s white-box: Increased training data leakage in open llms, 2024

2024
[58]

Zhang, O

W. Zhang, O. Ohrimenko, and R. Cummings. Attribute privacy: Framework and mechanisms. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 757–766, New York, NY , USA, 2022. Association for Computing Machinery

2022
[59]

R-gap: Re- cursive gradient attack on privacy.arXiv preprint arXiv:2010.07733, 2020

J. Zhu and M. Blaschko. R-gap: Recursive gradient attack on privacy.arXiv preprint arXiv:2010.07733, 2020

work page arXiv 2010
[60]

L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients.Advances in neural information processing systems, 32, 2019

2019
[61]

P. Zsohar. Short introduction to the generalized method of moments.Hungarian Statistical Review, Special Number 16, 2012. 13 A Appendix Contents A.1 Batch Gradient Descent Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.2 Predictability Beyond Estimating the Average Value ofq(x). . . . . . . . . . . . . . 15 A.3 Notation . . . . ...

2012
[62]

Let ¯A⊺= [A⊺ 1 0]

A1 satisfies A⊺ 1G1 =I by the first order condition. Let ¯A⊺= [A⊺ 1 0]. Then ¯A⊺G=[ A⊺ 1 0]G =[ A⊺ 1 0][G1 G2 ] =A ⊺ 1G1 =I Thus, we must have( ¯A−A∗)⊺ΩA=0 . Thus, ¯A⊺ΩA∗=A ∗⊺ΩA∗. ¯A⊺ΩA∗is the covariance between (T 1 n−θ0) and(Tn−θ0) (when Tn is the optimal predictor). A∗⊺ΩA∗is the variance of(Tn−θ0) (when Tn is the optimal predictor). Thus, Cov(T 1 n, Tn...

[1] [1]

Abadi, A

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016

2016

[2] [2]

Adeleye, S

T. Adeleye, S. Berghel, D. Desfontaines, M. Hay, I. Johnson, C. Lemoisson, A. Machanavajjhala, T. Magerlein, G. Modena, D. Pujol, D. Simmons-Marengo, and H. Triedman. Publishing wikipedia usage data with strong privacy guarantees, 2023

2023

[3] [3]

T. W. Anderson.An Introduction to Multivariate Statistical Analysis. Wiley, New York, 3 edition, 2003

2003

[4] [4]

Apple differential privacy technical overview, 2016

Apple Inc. Apple differential privacy technical overview, 2016

2016

[5] [5]

R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds, 2014. 10

2014

[6] [6]

P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: risk bounds and structural results.Journal of Machine Learning Research, 3:463–482, Mar. 2003

2003

[7] [7]

Bassily, A

R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 439–448, 2013

2013

[8] [8]

Ben-Sasson and R

H. Ben-Sasson and R. Greenberg. 38tb of data accidentally ex- posed by microsoft ai researchers. https://www.wiz.io/blog/ 38-terabytes-of-private-data-accidentally-exposed-by-microsoft-ai-researchers? utm_source=chatgpt.com, 2023

2023

[9] [9]

Berghel, P

S. Berghel, P. Bohannon, D. Desfontaines, C. Estes, S. Haney, L. Hartman, M. Hay, A. Machanavajjhala, T. Magerlein, G. Miklau, A. Pai, W. Sexton, and R. Shrestha. Tumult Analytics: a robust, easy-to-use, scalable, and expressive framework for differential privacy. arXiv preprint arXiv:2212.04133, Dec. 2022

work page arXiv 2022

[10] [10]

Berrios, J

N. Berrios, J. Fitzsimons, and S. Hod. The privacy deployments registry, 2024

2024

[11] [11]

P. J. Bickel, C. A. J. Klaassen, Y . Ritov, and J. A. Wellner.Efficient and Adaptive Estimation for Semiparametric Models. Johns Hopkins University Press, 1993

1993

[12] [12]

A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. InProceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 609–618, New York, NY , USA, 2008. Association for Computing Machinery

2008

[13] [13]

Carlini, F

N. Carlini, F. Tramèr, E. Wallace, M. Jagielski, A. Herbert-V oss, K. Lee, A. Roberts, T. Brown, D. Song, Ú. Erlingsson, A. Oprea, and C. Raffel. Extracting training data from large language models. In30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650. USENIX Association, Aug. 2021

2021

[14] [14]

Chaudhuri, S

K. Chaudhuri, S. M. Kakade, K. Livescu, and K. Sridharan. Multi-view clustering via canonical correlation analysis. InProceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 129–136, New York, NY , USA, 2009. Association for Computing Machinery

2009

[15] [15]

Chaudhuri, C

K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization.J. Mach. Learn. Res., 12(null):1069–1109, July 2011

2011

[16] [16]

A. Cheu, A. Smith, J. Ullman, D. Zeber, and M. Zhilyaev. Distributed differential privacy via shuffling. In Y . Ishai and V . Rijmen, editors,Advances in Cryptology – EUROCRYPT 2019, pages 375–403, Cham, 2019. Springer International Publishing

2019

[17] [17]

Cuff and L

P. Cuff and L. Yu. Differential privacy as a mutual information constraint. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016

2016

[18] [18]

J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy, 2019

2019

[19] [19]

Dovonon, Y

P. Dovonon, Y . F. Atchadé, and F. Doko Tchatoka. Efficiency bounds for moment condition models with mixed identification strength.Journal of Econometrics, 248:105723, 2025

2025

[20] [20]

C. Dwork. Differential privacy. In M. Bugliesi, B. Preneel, V . Sassone, and I. Wegener, editors, Automata, Languages and Programming, pages 1–12, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

2006

[21] [21]

C. Dwork. Differential privacy: A survey of results. In M. Agrawal, D. Du, Z. Duan, and A. Li, editors,Theory and Applications of Models of Computation, pages 1–19, Berlin, Heidelberg,

[22] [22]

Springer Berlin Heidelberg

[23] [23]

Dwork, F

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevi and T. Rabin, editors,Theory of Cryptography, pages 265–284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. 11

2006

[24] [24]

Dwork, M

C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. Pan-private streaming algorithms. InInternational Conference on Supercomputing, 2010

2010

[25] [25]

Dwork, A

C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy.Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014

2014

[26] [26]

Gehrke, E

J. Gehrke, E. Lui, and R. Pass. Towards privacy for social networks: A zero-knowledge based definition of privacy. In Y . Ishai, editor,Theory of Cryptography, pages 432–449, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg

2011

[27] [27]

Ghazi, N

B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. Deep learning with label differential privacy, 2021

2021

[28] [28]

Ghosal and A

S. Ghosal and A. van der Vaart.Fundamentals of Nonparametric Bayesian Inference. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017

2017

[29] [29]

Ghosh and R

A. Ghosh and R. Kleinberg. Inferential privacy guarantees for differentially private mechanisms, 2017

2017

[30] [30]

Gianola and K

M. Gianola and K. Pachacz. Introducing bigquery differential privacy and partnership with tumult labs, May 8 2023

2023

[31] [31]

R. Hall, A. Rinaldo, and L. Wasserman. Random differential privacy, 2011

2011

[32] [33]

L. P. Hansen. Large sample properties of generalized method of moments estimators.Econo- metrica, 50(4):1029–1054, 1982

1982

[33] [34]

L. P. Hansen.Generalized method of moments estimation, pages 105–118. Palgrave Macmillan UK, London, 2010

2010

[34] [35]

X. He, A. Machanavajjhala, and B. Ding. Blowfish privacy: tuning privacy-utility trade- offs using policies. InProceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD/PODS’14. ACM, June 2014

2014

[35] [36]

Horowitz

J. Horowitz. A uniform law of large numbers and empirical central limit theorem for limits of finite populations.Statistics & Probability Letters, 10(2):159–166, 1990

1990

[36] [37]

Jiang, F

Y . Jiang, F. Fu, X. Miao, X. Nie, and B. Cui. Osdp: Optimal sharded data parallel for distributed deep learning. In E. Elkind, editor,Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 2142–2150. International Joint Conferences on Artificial Intelligence Organization, 8 2023. Main Track

2023

[37] [38]

S. M. Kakade and D. P. Foster. Multi-view regression via canonical correlation analysis. In N. H. Bshouty and C. Gentile, editors,Learning Theory, pages 82–96, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

2007

[38] [39]

S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In D. Koller, D. Schuurmans, Y . Bengio, and L. Bottou, editors,Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008

2008

[39] [40]

Kifer and A

D. Kifer and A. Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Trans. Database Syst., 39(1), Jan. 2014

2014

[40] [41]

Ligett, C

K. Ligett, C. Peale, and O. Reingold. Bounded-Leakage Differential Privacy. In A. Roth, editor, 1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

2020

[41] [42]

C. Mauran. 200,000 facebook marketplace user records were leaked on the dark web. https: //mashable.com/article/facebook-marketplace-data-breach-details, 2024. 12

2024

[42] [43]

McFadden.Econometrics 240B Second Half Reader

D. McFadden.Econometrics 240B Second Half Reader. 1999

1999

[43] [44]

McMahan, E

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In A. Singh and J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 ofProceedings of Machine Learning Research, pages 1273–1282. PMLR, 20–22 Apr 2017

2017

[44] [45]

I. Mironov. Rényi differential privacy. In2017 IEEE 30th Computer Security Foundations Symposium (CSF), page 263–275. IEEE, Aug. 2017

2017

[45] [46]

L. H. Newman. 1.2 billion records found exposed online in a single server. https://www. wired.com/story/billion-records-exposed-online/, 2019

2019

[46] [47]

Nuradha and Z

T. Nuradha and Z. Goldfeld. Pufferfish privacy: An information-theoretic study.IEEE Transac- tions on Information Theory, 69(11):7336–7356, Nov. 2023

2023

[47] [48]

Prášková and P

Z. Prášková and P. Sen. Asymptotics in finite population sampling.Handbook of Statistics, 29:489–522, 12 2009

2009

[48] [49]

Rogers, S

R. Rogers, S. Subramaniam, S. Peng, D. Durfee, S. Lee, S. K. Kancha, S. Sahay, and P. Aham- mad. Linkedin’s audience engagements api: A privacy preserving data analytics system at scale, 2020

2020

[49] [50]

Sindhwani, P

V . Sindhwani, P. Niyogi, and M. Belkin. A co-regularization approach to semi-supervised learning with multiple views. InProceedings of the Workshop on Learning with Multiple Views, 22nd ICML, 2005

2005

[50] [51]

Sridharan and S

K. Sridharan and S. Kakade. An information theoretic framework for multi-view learning. In Conference on Learning Theory, pages 403–414, 01 2008

2008

[51] [52]

Steinke and L

T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual informa- tion, 2020

2020

[52] [53]

Triastcyn and B

A. Triastcyn and B. Faltings. Bayesian differential privacy for machine learning, 2020

2020

[53] [54]

Losing face: Two more cases of third-party facebook app data exposure

UpGuard Team. Losing face: Two more cases of third-party facebook app data exposure. https://www.upguard.com/breaches/facebook-user-data-leak, 2019

2019

[54] [55]

Census bureau sets key parameters to protect privacy in 2020 census results, 2021

US Census Bureau. Census bureau sets key parameters to protect privacy in 2020 census results, 2021

2020

[55] [56]

A. W. van der Vaart.Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998

1998

[56] [57]

J. G. Wang, J. Wang, M. Li, and S. Neel. Pandora’s white-box: Increased training data leakage in open llms, 2024

2024

[57] [58]

Zhang, O

W. Zhang, O. Ohrimenko, and R. Cummings. Attribute privacy: Framework and mechanisms. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 757–766, New York, NY , USA, 2022. Association for Computing Machinery

2022

[58] [59]

R-gap: Re- cursive gradient attack on privacy.arXiv preprint arXiv:2010.07733, 2020

J. Zhu and M. Blaschko. R-gap: Recursive gradient attack on privacy.arXiv preprint arXiv:2010.07733, 2020

work page arXiv 2010

[59] [60]

L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients.Advances in neural information processing systems, 32, 2019

2019

[60] [61]

P. Zsohar. Short introduction to the generalized method of moments.Hungarian Statistical Review, Special Number 16, 2012. 13 A Appendix Contents A.1 Batch Gradient Descent Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.2 Predictability Beyond Estimating the Average Value ofq(x). . . . . . . . . . . . . . 15 A.3 Notation . . . . ...

2012

[61] [62]

Let ¯A⊺= [A⊺ 1 0]

A1 satisfies A⊺ 1G1 =I by the first order condition. Let ¯A⊺= [A⊺ 1 0]. Then ¯A⊺G=[ A⊺ 1 0]G =[ A⊺ 1 0][G1 G2 ] =A ⊺ 1G1 =I Thus, we must have( ¯A−A∗)⊺ΩA=0 . Thus, ¯A⊺ΩA∗=A ∗⊺ΩA∗. ¯A⊺ΩA∗is the covariance between (T 1 n−θ0) and(Tn−θ0) (when Tn is the optimal predictor). A∗⊺ΩA∗is the variance of(Tn−θ0) (when Tn is the optimal predictor). Thus, Cov(T 1 n, Tn...