Predictability as a Fine-Grained Measure for Privacy

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Predictability as a Fine-Grained Measure for Privacy

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Predictability as a Fine-Grained Measure for Privacy

arXiv:2606.20546v1 [cs.LG] 18 Jun 2026

Linda Lu Cornell University [email protected]

Karthik Sridharan Cornell University [email protected]

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 sensitive 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 additional fine-grained privacy control.

Introduction

Data privacy has always been a central problem in machine learning, and it is even more critical today. Today’s machine learning models consume internet-scale data, much of which could be sensitive. Researchers have reconstructed training data from deep vision models [59, 58] and large language models [13, 56]; thus, privacy surrounding these systems is increasingly paramount. Differential privacy (DP) [22, 20, 21, 24] has long been considered the gold standard for privacy, providing rigorous privacy guarantees for unknown individuals. Differentially private algorithms inject noise during model training to ensure privacy [24, 1, 15]. Many differentially private algorithms have been deployed in practice [4, 29, 2, 48, 9]. However, the noise injected by differentially private algorithms degrades the accuracy, and the resulting tradeoff between privacy and performance is very costly. Due to this costly tradeoff, differentially private algorithms are often deployed with a large privacy parameter ε, as large as ε = 20 [10, 48, 54]. DP guarantees that, even against the most knowledgeable attacker (one with full knowledge of every individual but one), the attacker’s posterior beliefs about any feature of the unknown individual change by at most a factor of eε after observing the algorithm. For practical systems, the privacy guarantee from DP for these large ε is extremely weak. A system designer may want stronger privacy protections for specific types of sensitive information. Can we provide a finer-grained privacy metric tailored to specific sensitive information? Furthermore, this worst-case attacker that compromises every individual but one is extremely improbable; we would expect an attacker to either compromise some fraction of the dataset or the entire dataset. In the latter case, we cannot hope to provide any privacy anyway. Training Preprint.

data for large-scale machine learning is often sharded across many servers [43, 36]. Data breaches of these systems often target a single misconfigured data server containing a subset of training data [45, 53, 8, 41]. If only a fraction of the dataset is compromised, how do we ensure privacy for the entire population of unknown individuals? Consider a differentially private release of the proportion of smokers in a dataset. If the portion of the dataset compromised by the attacker contains a small number of smokers, then the release of the proportion of smokers reveals that there must be a large proportion of smokers among the unknown individuals. Even though DP ensures that the attacker cannot identify whether any particular unknown individual is a smoker, a lot of information is revealed about the overall set of unknown individuals. We propose studying the privacy guarantees of algorithms through the predictability of sensitive information on the set of unknown individuals, given the attacker’s knowledge. Predictability can be used to study the fine-grained guarantees of differentially private algorithms against specific types of attackers and sensitive queries, to inform users of more nuanced privacy guarantees. Predictability also informs us of new mechanisms to protect specific sensitive queries on the set of unknown individuals against specific attackers. Our contributions are as follows. • We introduce predictability, a privacy metric that explicitly incorporates the attacker’s knowledge (a portion of compromised data generated by a stochastic process) and the set of sensitive queries, and measures how well the attacker can predict sensitive information about the set of unknown individuals before and after observing the algorithm. • We show that predictability is incomparable to (neither implies nor is implied by) the privacy guarantees of differential privacy. However, under worst-case assumptions on the attacker’s knowledge, predictability implies mutual information differential privacy. • We introduce a framework using the generalized method of moments to compute the asymptotic predictability of an algorithm with respect to a single sensitive query when the attacker’s knowledge is generated by a known stationary, ergodic, strongly mixing process. We prove that, for a noisy algorithm release, asymptotic predictability is governed by a canonical correlation term between the query and moment condition of the algorithm, along with a noise-attenuation term. • We derive an improved predictability-calibrated output perturbation scheme for ERM. The scheme adapts the noise covariance to the loss curvature, gradient covariance, and attacker process, yielding improved accuracy bounds for linear regression compared with isotropic perturbation. • We extend the framework to the asymptotic predictability for query families (finite, linear, Lipschitz) and the asymptotic predictability when the process is unknown. 1.1

Related Work

Many variations of DP have been proposed, modifying its stringent requirements. Some examples include Rényi DP [44], KL-DP [5], mutual information DP [17], distributional DP [12], f -DP [18], random DP [30], label DP [26], coupled worlds DP [7], zero knowledge privacy [25], and Bayesian DP [52]. Some variations of DP also account for the attacker’s knowledge. Blowfish privacy [34] specifies the attacker’s knowledge through deterministic constraints on the dataset. Inferential privacy [28] specifies the attacker’s knowledge through prior distributions on the data. Bounded-leakage DP [40] assumes the attacker has additional information about the dataset through a leakage function. In the streaming setting, pan-privacy [23] assumes the attacker’s knowledge is the internal state of the algorithm. In distributed learning, shuffle DP [16] assumes the attacker’s knowledge is a shuffled set of messages. Pufferfish privacy [39] specifies the attacker’s knowledge through prior distributions on the data and specifies sensitive information through secret pairs. However, the mechanisms proposed for the Pufferfish framework are inefficient to compute without distributional assumptions on the dataset [39, 46]. We find that predictability can be computed efficiently, given any dataset. DP has also been extended to provide privacy for the membership of groups of individuals through group privacy [24]. Many of the above definitions have extensions to analogous group privacy definitions. Additionally, attribute privacy [57], an instantiation of the Pufferfish framework, has been proposed to provide privacy for global properties of a dataset.

Privacy via Predictability

The goal of a private learning algorithm is to prevent an attacker from extracting sensitive unknown information about a specific or random individual from the uncompromised population through the algorithm’s output. To better understand this goal, we take the perspective of the attacker. Before 2

observing the algorithm’s output, the attacker has some initial core knowledge about the dataset. We model this via a stochastic process that reveals a compromised portion of the dataset to the attacker. Let X be an instance space, and let S = (x1 , . . . , xN ) ∈ X N be a dataset over N individuals. Definition 2.1 (Core Knowledge). Let P be a stochastic process that, given a dataset S, generates a sequence x1 , . . . , xn , such that each xi ∈ S. The attacker’s core knowledge is C(S) = {x1 , . . . , xn }. A key example is an attacker that compromises a random shard of the dataset. This can be modeled by the stochastic process PRS that produces each xi by uniformly sampling from S without replacement. Generally, P can be much more complex. P could have a Markovian structure such that the choice of each xi depends on the previously selected xi−1 , or P could be biased towards a (potentially adversarial) subset of S. We keep P general to capture a variety of potential core knowledges. Let A ∶ X N ↦ ∆(F) be a randomized algorithm that takes in a dataset S and outputs a distribution over a model class F. We assume that the designer of A knows the process P but does not know the realized C(S). This captures a setting where the algorithm designer knows how a data breach occurs but does not know the exact set of compromised data. In Section 5, we relax the assumption that the process is known to the algorithm designer. The algorithm designer wants to protect the privacy of a family of sensitive queries Q. Using their core knowledge C(S) and A(S), the attacker will attempt to answer a query q ∈ Q about an unknown individual x as accurately as they can, where x ∼ Π, Π = Unif(S ∖ C(S)).

(1)

We select x uniformly at random from the unknown individuals to measure the attacker’s prediction for the average unknown individual. Definition 2.2 (Bayes Optimal Estimator). Given knowledge K(S) and query q, the Bayes optimal ∗ estimator for loss ℓ ∶ Θ × Y ↦ R is θ̂q∣K(S) = arg minθ̂ Ex∼Π [ℓ(θ̂, q(x)) ∣ K(S)]. The Bayes optimal estimator represents the best prediction of q(x) that an attacker could make. We primarily use K(S) = C(S) or K(S) = (C(S), A(S)) to compare the difference in prediction before and after observing A(S). The information contained in C(S) is already exposed to the attacker. The best that a private algorithm can do is to ensure that the attacker does not gain any additional information through the algorithm’s output. We formally define this goal as predictability. Definition 2.3 (Predictability). Let process P produce the core knowledge of the attacker C(S). Let ∗ Q = {q ∶ X ↦ Y} be a family of sensitive queries. Let ℓ ∶ Θ × Y ↦ R be a loss function. Let θ̂q∣C(S) ∗ and θ̂q∣C(S),A(S) be the Bayes optimal estimator for q(x) given C(S), and given C(S) and A(S), respectively. Then algorithm A has γ(P, Q, ℓ, A)-predictability γ if

γ(P, Q, ℓ, A) = sup

∗ ∗ [sup E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] ≤ γ.

S C(S)∼P,A q∈Q x∼Π

Given core knowledge C(S), predictability measures the increase in accuracy of the attacker’s prediction for any sensitive query q ∈ Q on an unknown individual before and after observing the algorithm’s output. If the difference in prediction is small, the algorithm’s output reveals very little additional information beyond what an attacker could have already learned about the average unknown individual from C(S). Predictability as a measure of the additional information exposed by A(S) about the unknown individuals with respect to q(x) is formalized when ℓ is the log loss. Theorem 2.4. Let PX denote the distribution of X. If Q ⊆ {q ∶ X → [K]} is a family of categorical queries and ℓ(θ̂, y) = −yi log(θ̂i ) is the log loss, predictability is equivalent to γ(P, Q, ℓ, A) = sup

[sup E [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]]

S C(S)∼P,A q∈Q x∼Π

≥ sup sup MI(q(x); A(S) ∣ C(S)) S

q∈Q

Under the log loss, predictability ensures that the amount of extra information A(S) reveals about a query q(x) on the average unknown individual beyond what is present in the core knowledge C(S) is bounded by γ. We can think of predictability as bounding the information exposure of a specific sensitive query over the whole set of unknown individuals. Compare this to differential privacy, which guarantees that information revealed by A(S) is bounded by ε for each unknown individual. Both privacy notions bound a form of information leakage, but are generally incomparable. 3

Theorem 2.5. Let ℓ(θ̂, y) = (θ̂ − y)2 be the squared loss. There exists a process P, query q, and algorithm A such that A is ε-differentially private, ε = O( √1N ), but γ(P, Q, ℓ, A)-predictability is Ω(1). Conversely, there exists a process P, query q, and algorithm A such that γ(P, Q, ℓ, A)predictability is O( N1 ), but A is not differentially private. Differential privacy measures, relative to the information in the rest of the dataset S ∖ {xi }, how much additional information can be learned about the last remaining individual. Predictability measures, relative to the information in C(S), how much additional information can be learned about the overall set of unknown individuals. When C(S) and S ∖ {xi } are very different, then the privacy leakage of predictability and differential privacy are measured relative to very different quantities. Consider when C(S) is very uninformative about the dataset (i.e. C(S) = ∅), then a differentially private algorithm that does not reveal much about any particular individual still reveals a lot about the overall dataset of unknown individuals. We also point out a key distinction between predictability and group privacy [24], a generalization of differential privacy. The individuals in the unexposed shards could be treated as a group. Group privacy guarantees that (almost) no information can be learned about the group of unknown individuals from the algorithm, including all group-level statistics. However, under predictability, if a group-level statistic on the set of unknown individuals can be well-estimated using only C(S) (i.e. C(S) is a random subset), then this information can be revealed by the algorithm because this information is already revealed to the attacker through C(S). Thus, an algorithm that reveals fairly accurate group-level statistics can maintain small predictability while providing little to no group privacy. We find that in worst-case settings, predictability implies mutual information differential privacy. Consider a process PDP that reveals the worst-case subset of n = N − 1 individuals from the dataset S and all binary queries are considered sensitive. This is exactly the worst-case setting considered by differential privacy and its variants. Definition 2.6 (ε-mutual-information differential privacy [17]). A randomized algorithm A(S) is ε-mutual-information differentially private (MI-DP) if sup χ∈∆(X N ),i∈[N ]

MI(xi ; A(S) ∣ S ∖ {xi }) ≤ ε.

Theorem 2.7. Let Qbin = {q ∶ X ↦ {0, 1}} be the set of all binary queries on X and let ℓ be the log loss. If algorithm A has γ(PDP , Qbin , ℓ, A)-predictability γ, then A is γ-MI-DP. √ Additionally, [17] showed that ε-MI-DP ⇒ (0, 2ε)-DP, establishing a connection between MI-DP √ and DP. However, when ε ≥ 0.5, which is very typical, (0, 2ε)-DP provides no individual-level privacy. Thus, we do not find the connection to be meaningful, and we believe this emphasizes the distinctiveness between predictability and differential privacy. Furthermore, the worst-case setting is overly stringent. An attacker may only have the ability to compromise a subset of the dataset via some process that is likely subject to stochasticity. An algorithm designer may only care about protecting privacy leakages of specific queries, but not all information leakages are created equal. Against these attackers and queries, predictability guarantees can be much more favorable. For the same algorithm, we can derive different predictability guarantees for different attacker models and query families, giving users a detailed understanding of an algorithm’s privacy guarantees beyond the worst-case setting. Remark 2.8. In Appendix A.2, we discuss an extension of predictability beyond the estimation of q(x) for the average unknown individual (in particular, when the attacker estimates Ex∼D′ [q(x)] for some other distribution D′ on the dataset S, instead of Π). This extension allows us to measure predictability guarantees for targeted subgroups of the dataset. In Appendix A.6, we establish post-processing and composition properties of predictability, analogous to the properties of conditional mutual information from [51]. 2.1

Computing Predictability

We focus on understanding the privacy guarantees of large-scale machine learning systems. Thus, we present a general framework to analyze the large sample, asymptotic predictability of a query q when 4

n, N → ∞. To bound predictability, we must bound the difference in loss between two estimators of q. For a convex and smooth loss (i.e. log loss or squared loss), the difference in the loss of the estimators can be characterized by the difference of the estimators themselves. Lemma 2.9. Let ℓ(θ̂) = Ex∼Π [ℓ(θ̂, q(x)] be a convex, H-smooth loss. Let θ0q = Ex∼Π [q(x)]. Then for any pair of estimators θ̂q∣C(S) and θ̂q∣C(S),A(S) , E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] ≤ H∣θ̂q∣C(S) − θ0 ∣ ⋅ ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣. q

xi ∼Π

For log loss, if the true p0 = Pr[q(x) = 1] satisfies p0 ∈ [τ, 1 − τ ], H = τ12 . For squared loss, H = 2. In particular, the difference in loss can be upper-bounded by the variance of θ̂q∣C(S) and θ̂q∣C(S),A(S) around the true θ0q . Thus, the best that an attacker could do is to select the estimator with the smallest variance among all possible estimators. In statistics, this is known as the efficient estimator. The efficient estimator represents the most accurate prediction that an attacker could make, given infinite computational resources. We will find that asymptotically, the efficient estimator coincides with the Bayes optimal estimator. Predictability only decreases if the attacker chooses a worse estimator. Importantly, we do not assume that the attacker uses the efficient estimator; it simply allows us to measure the worst-case increase in predictability. If the variance of the efficient estimator given C(S) and given C(S) and A(S) is known, then ∣θ̂q∣C(S) − θ0q ∣ and ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣ can be bounded. Receiving C(S) is equivalent to receiving a sample from dataset S generated from a stochastic process. A(S) then reveals some additional information about S. If the process is stationary, ergodic, and mixing, and the information from A(S) can be captured by a moment condition, the behavior of the efficient estimator can be found through the generalized method of moments.

Generalized Method of Moments

The generalized method of moments (GMM) [31, 33, 60] is a method for parameter estimation in semiparametric statistics. In semiparametric statistics, the parameter of interest is finite-dimensional, but the data distribution is assumed to be infinite-dimensional and not limited to a specific parametric family; thus, standard maximum likelihood estimation cannot be applied. GMM allows population moment conditions to be incorporated into the estimation along with the random sample to improve parameter estimation. GMM estimators are known to be consistent, asymptotically normal, and most efficient in the class of all estimators that do not use any additional information other than that contained in the moment conditions. Importantly, the behavior of the most efficient GMM estimator is known. Consider an algorithm that releases the mean of the dataset. The mean reveals a population moment condition on the dataset. For a binary q under the log loss, the attacker wants to estimate p = Pr[q(x) = 1]. Given only the compromised data, the attacker can estimate p with some accuracy. The additional mean moment condition can improve the accuracy of the estimate. The improvement in the variance of the best estimate of p with and without the moment condition can be determined using GMM. GMM assumes that the sample is produced by a stationary, ergodic, α-mixing process. Assumption 3.1. P is a stationary, ergodic, and α-mixing process over N elements (see definitions in Appendix A.4). P has stationary distribution D = (p1 , . . . , pN ), such that pi > 0, ∀i ∈ [N ]. Some examples of such processes are i.i.d. sampling, sampling without replacement from a dataset (this models an attacker that compromises a random shard of the data), a process that samples certain portions of the dataset with higher probability (this models a system where certain data servers are more susceptible to attacks), or a process that samples from an aperiodic, irreducible Markov chain. Let x1 , x2 , . . . , xn be a random sample drawn from a stochastic process satisfying Assumption 3.1. Let θ ∈ Rr be an unknown vector of parameters to estimate, with true value θ0 . Let population moment conditions f (x, θ) be a continuous and differentiable Rr ↦ Rm function of θ such that E[f (x, θ)] = 0, only at the true parameter θ0 . The first moment condition specifies the parameter of estimation, and additional moment conditions specify known population parameters. Additional moment conditions have the form g(x, λ) for some (possibly vector-valued) function g and known population parameter λ. For example, consider the problem of estimating p = E[q(x)] for some query q, given a known population mean µ. We have θ = (p) and f (x, θ) = [q(x) − p, x − µ]⊺ where g(x, µ) = x − µ. 5

GMM also allows for noisy moment conditions. If instead of knowing λ directly, we only know λ̃ = λ + ∆, where ∆ is independent mean-zero noise, then we have θ = (p, λ) and moment conditions f (x, θ) = [q(x) − p, g(x, λ), λ̃ − λ]⊺ . Let fn (θ) = n1 ∑ni=1 f (xi , θ) be the sample moments. Given the sample, the GMM estimator of θ is θ̂ = arg min r fn (θ)⊺ W fn (θ) θ∈Θ⊆R

where W is some positive definite m × m weight matrix. Under standard regularity conditions (listed in Appendix A.7.1), GMM estimators are regular, consistent, and asymptotically normal, and we can characterize the behavior of the efficient GMM estimator θ̂ GMM . (x,θ) ] be the Jacobian and let Ω = Theorem 3.2 (Efficient GMM Estimator [32]). Let G = E[ ∂f ∂θ ∞ ⊺ ∑k=−∞ E [f (x0 , θ)f (xk , θ) ] be the long-run covariance. As n → ∞, with W = Ω−1 (θ0 ), the efficient GMM estimator θ̂ GMM is regular and asymptotically efficient with asymptotic distribution √ n(θ̂ GMM − θ0 ) ∼ N (0, [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 ).

The proof of efficiency is standard from [31]. Importantly, the sample moments must follow an appropriate uniform law of large numbers (Theorem A.12) and central limit theorem (Theorem A.13). We assume the posterior induced by both C(S) and C(S), A(S) satisfies a Bernstein–von Mises ∗ (BvM) theorem for the query functional. Under this assumption, the Bayes optimal estimators θ̂q∣C(S) ∗ and θ̂q∣C(S),A(S) are known to be regular and asymptotically efficient. In this paper, we assume that the (functional) BvM holds, and under this condition, we show in the theorem below that one can replace the Bayes optimal estimator in the definition of predictability by the asymptotically efficient GMM estimator instead. Standard sufficient conditions for the BvM theorem have been extensively studied in statistics literature (see [55, Chapter 10], [11] [27, Chapter 12]).

Theorem 3.3. Let ℓ(θ̂) = Ex∼Π [ℓ(θ̂, q(x)] be a twice continuously differentiable loss function with ∇ℓ(θ0 ) = 0 and ∇2 ℓ(θ0 ) positive definite. Then ∗

∗

E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] ≤ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] + o( n )

x∼Π

GMM

x∼Π

As discussed above, under our assumption, both estimators, θ̂ GMM and θ̂∗ , are regular and asymptotically efficient. Thus, both estimators must share the same influence function and therefore, the same behavior up to lower order terms. As n → ∞, the lower order difference vanishes, and we can replace the difference in the loss of θ̂∗ with the difference in the loss of θ̂ GMM in the predictability bound. Then we can use the behavior of θ̂ GMM to bound predictability. 3.1

Applying GMM to Predictability

In the setting of predictability, the attacker receives C(S), a random sample of dataset S from process P. Using GMM, we want to compare the behavior of the estimator given only C(S) versus given C(S) and A(S). For GMM estimation, we must first specify our parameter of interest. For a single q, the attacker wants to estimate q(x) for the average individual in the dataset, p = EDU [q(x)], DU = Unif(S), given the information they have. This is almost in the right form for a moment condition, but the expectation is under a different distribution DU , instead of D. However, notice that a moment condition on DU implies a moment condition on D. In particular, at the unique θ0 , U EDU [f (x, θ0 )] = ED [w(x)f (x, θ0 )] = 0, where w(xi ) = dD (xi ) = pi1N . dD

To incorporate the information from the algorithm, consider A(S) = λ̃ = λ + ∆, for some λ and ∆ ∼ N (0, Σ∆ ). A(S) exactly reveals a noisy moment λ on the entire dataset S. If we can express λ in the form E[g(x, λ)] = N1 ∑N i=1 g(xi , λ) = 0 for some g, then the information from A(S) can be expressed as a moment condition on DU and thus, a weighted moment condition on D. Then the moment conditions for predictability are fC(S) (x, θ) = [w(x)(q(x) − p)] fC(S),A(S) (x, θ) = [w(x)(q(x) − p), w(x)g(x, λ), λ̃ − λ]⊺ 6

(2)

with θ = (p) and θ = (p, λ), respectively. We note that θ must capture all unknown parameters; however, we focus only on the variance of the estimate of p. GMM Recall from Lemma 2.9, to bound predictability, we must characterize the behavior of ∣θ̂q∣C(S) − θ0q ∣ GMM GMM GMM and ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣. Theorem 3.2 characterizes the behavior of ∣θ̂q∣C(S) −θ0q ∣. For the behavior GMM GMM of ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣, we employ one additional property of GMM estimators. GMM GMM Theorem 3.4. When the efficient GMM estimators θ̂q∣C(S) and θ̂q∣C(S),A(S) are constructed on the same sample, their difference has asymptotic distribution GMM GMM GMM GMM θ̂q∣C(S) − θ̂q∣C(S),A(S) ∼ N (0, Var[θ̂q∣C(S) ] − Var[θ̂q∣C(S),A(S) ])

GMM GMM Var[θ̂q∣C(S) ] and Var[θ̂q∣C(S),A(S) ] are found by directly computing n1 [G⊺ Ω−1 G]−1 , plugging the respective weighted moment conditions f (x, θ) into G and Ω−1 . Then we use the concentration of these estimators to bound the predictability.

) Definition 3.5 (Canonical Correlation [3]). Let ρ(X, Y ) = Cov(X,Y be standard correlation. The σX σY canonical correlation between 1-dimensional random variable X and vector random variable V is ρcc (X, V ) = maxc∈Rd ρ(X, c⊺ V ), the max correlation between X and any linear projection of V .

Theorem 3.6 (Asymptotic Predictability of a Query). Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). Assume process P satisfies Assumption 3.1. Assume the moment conditions in Equation 2 satisfy the √ √ GMM GMM regularity conditions (Appendix A.7.1). We have n(θ̂q∣C(S) − θ0q ) ∼ N (0, σ12 ) and n(θ̂q∣C(S) − GMM θ̂q∣C(S),A(S) ) ∼ N (0, σ12 − σ22 ). For a convex, H-smooth loss, with probability 1 − δ,

E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] ≤ GMM

GMM

xi ∼Π

√ H log(4/δ) ⋅ σ1 σ12 − σ22 . n

√ ⋅ σ1 σ12 − σ22 . Computing the expectation of the above, asymptotically, γ(P, q, ℓ, A) ≤ H(1+log(4)) n Let q ′ = w(x)(q(x) − p) and let g ′ = w(x)g(x, λ). Let ′

′

⊺

′

] (E [ ∂g ] Var[g ′ ]−1 E [ ∂g ] + Σ−1 c0 (w, q, g, ∆) = Var[q ′ ]−1 Cov(q ′ , g ′ )Var[g ′ ]−1 E [ ∂g ∆) ∂λ ∂λ ∂λ ′

−1

⊺

⋅ E [ ∂g ] Var[g ′ ]−1 Cov(q ′ , g ′ ). ∂λ

Plugging in the form of σ1 and σ2 , the algorithm has predictability γ(P, q, ℓ, A) ≤

√ H(1 + log(4)) ⋅ Var[q ′ ] ⋅ ρcc (q ′ , g ′ )2 − c0 (w, q, g, ∆). n

All expectations in Theorem 3.6 are weighted averages on the dataset using weights w(xi ) = pi1N . Therefore, given a dataset, all terms (expectations, variances, covariances) in Theorem 3.6 can be computed efficiently. Remark 3.7. The resulting predictability looks unwieldy, but we break down the key terms. • ρcc (q ′ , g ′ )2 - The canonical correlation captures how correlated q and A(S) are. Intuitively, it quantifies the most information we can extract from A(S) about q(x). Given a dataset and stationary dis1 ′ ′ ′ −1 tribution, ρcc can be efficiently computed, ρ2cc (q ′ , g ′ ) = Var[q Cov(g ′ , q ′ ). ′ ] ⋅ Cov(q , g )Var[g ] • c0 (w, q, g, ∆) - c0 captures how adding noise affects predictability. c0 ranges from 0 to ρcc (q ′ , g ′ )2 . Given a dataset and stationary distribution, c0 can also be efficiently computed. To better understand predictability, let Σ∆ = σ 2 Id , then consider: Condition

Predictability

Comment

σ →0 σ2 → ∞ ρcc (q ′ , g ′ ) = 0

4) γ = H(1+log ⋅ Var[q ′ ] ⋅ ∣ρcc (q ′ , g ′ )∣ n

Noiseless case, c0 → 0 Infinite noise, c0 → ρcc (q ′ , g ′ )2 Privacy for free; q and A are unrelated

γ=0 γ=0

Theorem 3.6 yields a general recipe for computing asymptotic predictability. • For a private algorithm A(S) = λ̃ = λ + ∆, express λ in the form E[g(x, λ)] = 0. 7

• Define moment conditions fC(S) (x, θ) and fC(S),A(S) (x, θ), accordingly. • Compute the variance of efficient estimators and apply Theorem 3.6. Random Shard is Compromised Consider the process PRS where a sample of size n = αN is drawn uniformly without replacement from the dataset. This is the setting in which the attacker compromises a random shard of data. Under PRS , the stationary distribution D = DU , and w(x) = 1. Corollary 3.8. Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). √ As n, N → ∞, n/N → α, for a convex, H-smooth ℓ, γ(PRS , q, ℓ, A) ≤ H(1+log(4)) ⋅ Var[q(x)] ⋅ ρcc (q(x), g(x, λ))2 − c0 (1, q, g, ∆). (1−α)αN For typical choices of losses (log loss and squared loss), we can plug in H = τ12 , H = 2, appropriately. Given a differentially private algorithm and query of interest, predictability bounds can be determined simultaneously for all random fractions α of compromised data that hold alongside worst-case guarantees from differential privacy, giving users a more detailed understanding of privacy.

Analyzing the Predictability of Private Algorithms Using GMM

For several important algorithms, we demonstrate how to express the algorithm as E[g(x, λ)] = 0. 4.1

Private Dataset Statistics

Consider an algorithm that releases a noisy aggregate statistic from the dataset, such as the proportion of smokers. Here, specifying the algorithm as a moment condition is straightforward. A statistic λ takes the form, λ = N1 ∑N i=1 Γ(xi ). For example, if λ is the mean, Γ(x) = x, or if λ is a count statistic, Γ(x) = 1{x is a smoker}. Then g(x, λ) = Γ(x) − λ ensures E[g(x, λ)] = 0 only at the true λ. Theorem 4.1. Let A(S) = λ̃ = N1 ∑N = Γ(x) − λ. For a i=1 Γ(xi ) + ∆, ∆ ∼ N (0, Σ∆ ). Let g(x, λ) √ Var[Γ(x)] . convex, H-smooth ℓ, γ(PRS , q, ℓ, A) = H(1+log(4)) ⋅ Var[q(x)] ⋅ ρ(q(x), Γ(x)) ⋅ Var[Γ(x)]+Σ (1−α)αN ∆ We plug the appropriate g(x, λ) into Corollary 3.8 to obtain the expression for predictability. When g(x, λ) = Γ(x) − λ, we obtain a simplified expression, c0 (1, q, g, ∆) = ρ(q(x), Γ(x))2 ⋅ Var[Γ(x)] ). Here, we can clearly observe how Σ∆ affects c0 and predictability. (1 − Var[Γ(x)]+Σ ∆ 4.2

Private Empirical Risk Minimization

Next, consider an algorithm that releases a noisy empirical risk minimizer (ERM). Many common machine learning problems can be reduced to ERM; thus, analyzing and understanding the privacy and predictability guarantees under the release of ERM is crucial. Dataset entries consist of z = (x, y) pairs. Consider some loss function ℓ(z, w). The ERM of ℓ is wERM = arg minw N1 ∑N i=1 ℓ(zi , w). This condition cannot be directly written in the form E[f (z, θ)] = 0. However, at wERM , we have N1 ∑N i=1 ∇ℓ(zi , wERM ) = E[∇ℓ(z, wERM )] = 0. Thus, let λ = wERM and g(x, wERM ) = ∇ℓ(z, wERM ). We restrict our attention to strictly convex ℓ to ensure E[g(x, wERM )] = 0 only holds at the wERM released by the algorithm. 2 Theorem 4.2. Let wERM = arg minw N1 ∑N i=1 ℓ(zi , w), ℓ strictly convex and E[∇ ℓ(z, wERM )] positive definite. Let A(S) = w̃ = wERM + ∆, ∆ ∼ N (0, Σ∆ ). Let√g(z, wERM ) = ∇ℓ(z, wERM ). For a convex, H-smooth ℓ, γ(PRS , q, ℓ, A) ≤ H(1+log(4)) ⋅ Var[q(z)] ⋅ ρcc (q(z), g(z, wERM ))2 − c0 (w, q, g, ∆). (1−α)αN

To achieve small canonical correlation, q(z) must be fairly unrelated to all coordinates of the loss gradient. We note that, surprisingly, it is not enough for the loss itself and the query to be uncorrelated. In Appendix A.1, we discuss how to express batch gradient descent (BGD) as a moment condition, thus allowing us to handle approximate or non-unique ERM computed by BGD. A more complete characterization of predictability for the ERM of a nonconvex loss is deferred to future work. 8

4.3

Predictability-Calibrated Noise Scheme for Private ERM

One could add isotropic noise to the ERM, Σ∆ = σ 2 Id , but this may not be the best choice. Instead, one could adapt the noise to the specific ERM and the process generating the compromised data. Lemma 4.3. Let ∇z = ∇ℓ(z, wERM ) and Hz = ∇2 ℓ(z, wERM ). Let A(S) = w̃ = wERM + ∆, ∆ ∼ N (0, σ 2 E[w(x)Hz ]−1 E[w(x)2 ∇z ∇⊺z ]E[w(x)Hz ]−1 ), where the expectation is taken with respect to the stationary distribution of process P. For a convex, √ 1 ′ ′ ′ H-smooth ℓ, γ(P, q, ℓ, A) ≤ H(1+log(4)) ⋅ Var[q ] ⋅ ρ (q , g ) ⋅ . cc (1−α)αN σ 2 +1 The calibrated noise scheme adapts to the specific ERM and stochastic process and results in a clear relationship between a desired level of predictability and the amount of noise required. We note that w(x) must be known. The complexity to compute the covariance of the noise is O(N d2 + d3 ). Linear Regression We instantiate the calibrated noise scheme for linear regression under the random sharding process to understand the structure of the noise and to highlight the improved tradeoff between predictability and accuracy. For linear regression under PRS , we have ℓ(z, w) = 12 (w⊺ x − ⊺ y)2 and w(x) = 1. Thus, we add noise ∆ ∼ N (0, σ 2 E[xx⊺ ]−1 E[(wERM x − y)2 xx⊺ ]E[xx⊺ ]−1 ). Analyzing the structure, we see that more noise is added in directions where wERM has a large loss or x’s are sparse. When wERM has a small empirical loss, w̃ is less noisy for the same predictability. ⊺ Theorem 4.4. Let w̃ = wERM + ∆, ∆ ∼ N (0, σ 2 ⋅ E[xx⊺ ]−1 E[(wERM x − y)2 xx⊺ ]E[xx⊺ ]−1 ). Then E[

σ 2 (maxi ∥xi ∥2 ) 1 N ⊺ ⊺ 2 ⋅ L̂S (wERM ), σ 2 d ⋅ L̂max (wERM )}. ∑(w̃ xi − wERM xi ) ] ≤ min { S N i=1 λmin (E[xx⊺ ])

⊺ 2 max ⊺ 2 where L̂S (wERM ) = N1 ∑N i=1 (wERM xi − yi ) and L̂S (wERM ) = maxi (wERM xi − yi ) .

We can upper bound the change in accuracy of w̃ in terms of the empirical loss. N 2 1 ⊺ ⊺ 2 2 Lemma 4.5. When ∆ ∼ N (0, σ 2 Id ), E [ N1 ∑N i=1 (w̃ xi − wERM xi ) ] = σ ( N ∑i=1 ∥xi ∥ ).

When L̂S (wERM ) or L̂max S (wERM ) is small (which we would expect), the calibrated noise scheme leads to a smaller change in accuracy compared to an isotropic noise scheme. Using post-processing of DP, we can compose our calibrated noise scheme for predictability with any differentially private algorithm to ensure stronger privacy protections for specific queries on unknown populations against specific types of attackers, in addition to typical worst-case DP guarantees. In particular, predictability-calibrated perturbation can be combined with DP mechanisms, provided that any data-dependent quantities (i.e. covariance of ∆) are computed in a differentially private manner.

Predictability of a Family of Queries or Unknown Process

So far, we have only analyzed the predictability of an algorithm with respect to a single query q when the algorithm knows the process P. However, in practice, we often want privacy guarantees against an entire family of sensitive queries. Additionally, the exact process P generating the attacker’s knowledge may be unknown to the algorithm designer. We extend the predictability analysis to a family of queries and an unknown process from a family of processes P. Finite Family of Queries and Processes Notice that for a particular process P ∈ P, the predictability depends on the weight function w ∈ WP derived from the stationary distribution of P. From Theorem 3.6, we know that for a fixed weight function w and query q, with high probability E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] GMM

GMM

xi ∼Π

is small. We use a union bound to show that for all w ∈ WP , q ∈ Q, the above is small with high probability. Then, taking the expectation, the worst-case predictability over P is bounded. Theorem 5.1. Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). For a family P satisfying Assumption 3.1 and a convex, H-smooth ℓ, the worst-case predictability is supP∈P γ(P, Q, ℓ, A) ≤

√ H(1 + log(4∣Q∣∣WP ∣)) sup sup Var[w(x)q(x)] ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆). n w∈WP q∈Q

Linear Query Family Consider the family Qlin = {q(x) = u⊺ x ∣ u ∈ Ulin ⊆ Rd }. For infinitely large families, we must rely on something stronger than the concentration of the estimators of single GMM GMM queries. Consider θ̂x∣C(S) and θ̂x∣C(S),A(S) , estimators for E[x ∣ C(S)] and E[x ∣ C(S), A(S)]. √ √ GMM GMM Using GMM, we know that n(θ̂x∣C(S) − µ) ∼ N (0, Σ1 ) and n(θ̂x∣C(S),A(S) − µ) ∼ N (0, Σ2 ). If estimates of x concentrate well, then estimates of linear functions of x also concentrate well. Theorem 5.2. Let query family Qlin = {q(x) = u⊺ x ∣ u ∈ Ulin ⊆ Rd }. If Ulin is contained within the Euclidean ball of radius B, √for a convex, H-smooth ℓ, the γ(PRS , Qlin , ℓ, A)-predictability is ≤ 4HB(2+log(2)) ⋅ tr(Var[x]) ⋅ (1−α)αN

(c0 (1,x,g,∆)) ρ1cc (x, g(x, λ))2 − λmintr(Var[x]) .

Definition 5.3 (First Canonical Correlation from CCA). For two vector random variables, X and Y , ρ1cc (X, Y )2 = λmax (Var[X]−1 Cov(X, Y )Var[Y ]−1 Cov(Y, X)). We recover a dependence on a correlation-type quantity, now between x and g(x, λ). Canonical correlation analysis (CCA) is a foundational technique in dimension reduction and multiview learning [37, 14, 49, 50], and we find its connection to predictability compelling. Importantly, CCA, and thus ρ1cc (x, g(x, λ)), can be computed efficiently. For general Ulin , see the bound on predictability for general linear query families (Theorem A.21), where the bound depends on the Gaussian complexity (Definition A.20) of Ulin . Lipschitz Query Family Similarly, if estimates of x concentrate well, then estimates of Lipschitz functions of x also concentrate well. Theorem 5.4. Let query family QL = {f (x) ∣ f√ is L-Lipschitz}. For a convex, H-smooth loss ℓ, (2+log(2)) γ(PRS , QL , ℓ, A) ≤ 4HL(1−α)αN ⋅ tr(Var[x]) ⋅ 2

(c0 (1,x,g,∆)) ρ1cc (x, g(x, λ))2 − λmintr(Var[x]) .

Discussion and Conclusion

We present predictability as a new fine-grained measure for privacy. We present a general framework for studying asymptotic predictability using GMM. We discuss a few extensions of our analysis. Under regularity assumptions (sub-Gaussian moment conditions, smoothness, etc.), one could convert the central limit theorem of the moments to appropriate tail bounds and follow this through to obtain a finite sample version of the asymptotic bound on predictability. We can also generalize predictability beyond a privacy measure for the average unknown individual by selecting the unknown individual x from another distribution, other than Π, and adjusting the weights w(x) accordingly. Open questions include developing a predictability-calibrated noise scheme for ERM when the process is unknown. Additionally, developing DP-style adaptive composition for predictability would be valuable.

Acknowledgments and Disclosure of Funding LL acknowledges support from the Cornell CIS LinkedIn Fellowship.

References [1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016. [2] 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. [3] T. W. Anderson. An Introduction to Multivariate Statistical Analysis. Wiley, New York, 3 edition, 2003. [4] Apple Inc. Apple differential privacy technical overview, 2016. [5] R. F. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds, 2014. 10

[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. [7] R. Bassily, A. Groce, J. Katz, and A. Smith. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 439–448, 2013. 38tb of data accidentally ex[8] H. Ben-Sasson and R. Greenberg. 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. [9] 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. [10] N. Berrios, J. Fitzsimons, and S. Hod. The privacy deployments registry, 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. [12] A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, page 609–618, New York, NY, USA, 2008. Association for Computing Machinery. [13] N. Carlini, F. Tramèr, E. Wallace, M. Jagielski, A. Herbert-Voss, K. Lee, A. Roberts, T. Brown, D. Song, Ú. Erlingsson, A. Oprea, and C. Raffel. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pages 2633–2650. USENIX Association, Aug. 2021. [14] K. Chaudhuri, S. M. Kakade, K. Livescu, and K. Sridharan. Multi-view clustering via canonical correlation analysis. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 129–136, New York, NY, USA, 2009. Association for Computing Machinery. [15] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12(null):1069–1109, July 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. [17] P. Cuff and L. Yu. Differential privacy as a mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, Oct. 2016. [18] J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy, 2019. [19] 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. [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. [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, 2008. Springer Berlin Heidelberg. [22] 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

[23] C. Dwork, M. Naor, T. Pitassi, G. N. Rothblum, and S. Yekhanin. Pan-private streaming algorithms. In International Conference on Supercomputing, 2010. [24] 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. [25] 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. [26] B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and C. Zhang. Deep learning with label differential privacy, 2021. [27] S. Ghosal and A. van der Vaart. Fundamentals of Nonparametric Bayesian Inference. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2017. [28] A. Ghosh and R. Kleinberg. Inferential privacy guarantees for differentially private mechanisms, 2017. [29] M. Gianola and K. Pachacz. Introducing bigquery differential privacy and partnership with tumult labs, May 8 2023. [30] R. Hall, A. Rinaldo, and L. Wasserman. Random differential privacy, 2011. [31] L. P. Hansen. Large sample properties of generalized method of moments estimators. Econometrica, 50(4):1029–1054, 1982. [32] L. P. Hansen. Large sample properties of generalized method of moments estimators. Econometrica, 50(4):1029–1054, 1982. [33] L. P. Hansen. Generalized method of moments estimation, pages 105–118. Palgrave Macmillan UK, London, 2010. [34] X. He, A. Machanavajjhala, and B. Ding. Blowfish privacy: tuning privacy-utility tradeoffs using policies. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD/PODS’14. ACM, June 2014. [35] 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. [36] 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. [37] 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. [38] 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. [39] D. Kifer and A. Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Trans. Database Syst., 39(1), Jan. 2014. [40] 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 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. [41] 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

[42] D. McFadden. Econometrics 240B Second Half Reader. 1999. [43] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas. CommunicationEfficient 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 of Proceedings of Machine Learning Research, pages 1273–1282. PMLR, 20–22 Apr 2017. [44] I. Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), page 263–275. IEEE, Aug. 2017. [45] L. H. Newman. 1.2 billion records found exposed online in a single server. https://www. wired.com/story/billion-records-exposed-online/, 2019. [46] T. Nuradha and Z. Goldfeld. Pufferfish privacy: An information-theoretic study. IEEE Transactions on Information Theory, 69(11):7336–7356, Nov. 2023. [47] Z. Prášková and P. Sen. Asymptotics in finite population sampling. Handbook of Statistics, 29:489–522, 12 2009. [48] R. Rogers, S. Subramaniam, S. Peng, D. Durfee, S. Lee, S. K. Kancha, S. Sahay, and P. Ahammad. Linkedin’s audience engagements api: A privacy preserving data analytics system at scale, 2020. [49] V. Sindhwani, P. Niyogi, and M. Belkin. A co-regularization approach to semi-supervised learning with multiple views. In Proceedings of the Workshop on Learning with Multiple Views, 22nd ICML, 2005. [50] K. Sridharan and S. Kakade. An information theoretic framework for multi-view learning. In Conference on Learning Theory, pages 403–414, 01 2008. [51] T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual information, 2020. [52] A. Triastcyn and B. Faltings. Bayesian differential privacy for machine learning, 2020. [53] UpGuard Team. Losing face: Two more cases of third-party facebook app data exposure. https://www.upguard.com/breaches/facebook-user-data-leak, 2019. [54] US Census Bureau. Census bureau sets key parameters to protect privacy in 2020 census results, 2021. [55] A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. [56] J. G. Wang, J. Wang, M. Li, and S. Neel. Pandora’s white-box: Increased training data leakage in open llms, 2024. [57] W. Zhang, O. Ohrimenko, and R. Cummings. Attribute privacy: Framework and mechanisms. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 757–766, New York, NY, USA, 2022. Association for Computing Machinery. [58] J. Zhu and M. Blaschko. R-gap: Recursive gradient attack on privacy. arXiv preprint arXiv:2010.07733, 2020. [59] L. Zhu, Z. Liu, and S. Han. Deep leakage from gradients. Advances in neural information processing systems, 32, 2019. [60] P. Zsohar. Short introduction to the generalized method of moments. Hungarian Statistical Review, Special Number 16, 2012.

Appendix

Contents A.1 Batch Gradient Descent Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.2 Predictability Beyond Estimating the Average Value of q(x) . . . . . . . . . . . . . . 15 A.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 A.4 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 A.5 Proofs from Section 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A.5.1 Theorem 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A.5.2 Theorem 2.5, Predictability and Differential Privacy are Incomparable . . . . 18 A.5.3 Theorem 2.7, Connection to Mutual Information Differential Privacy . . . . . 20 A.5.4 Lemma 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 A.6 Post-Processing and Composition of Predictability . . . . . . . . . . . . . . . . . . . . 22 A.7 Proofs from Section 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 A.7.1 Regularity Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 A.7.2 Theorem 3.2, GMM Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 A.7.3 Theorem 3.4, Difference of GMM Estimators . . . . . . . . . . . . . . . . . . 27 A.7.4 Theorem 3.6, Asymptotic Predictability of a Query . . . . . . . . . . . . . . . 28 A.8 Proofs from Section 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 A.8.1 Theorem 4.1, Private Dataset Statistics . . . . . . . . . . . . . . . . . . . . . . 34 A.8.2 Theorem 4.2, Private ERM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 A.8.3 Lemma 4.3, Calibrated Noise Scheme . . . . . . . . . . . . . . . . . . . . . . 36 A.9 Proofs from Section 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 A.9.1 Theorem 5.1, Finite Family of Queries and Processes . . . . . . . . . . . . . . 38 A.9.2 Theorem 5.2, Linear Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 A.9.3 Theorem 5.4, Lipschitz Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 45 A.10 Helpful Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

A.1

Batch Gradient Descent Discussion

When the exact, unique ERM is released, we apply Theorem 4.2 to compute the predictability. However, in many machine learning settings, the algorithm releases an approximate ERM, typically found through a version of gradient descent. We can express the result of batch gradient descent (BGD) as a moment condition. Recall the BGD update, 1 N ∑ ∇ℓ(zi , wt ). N i=1 We observe that each step of BGD can be expressed as a moment condition, g(z, wt−1,t ) = wt−1 − wt − η∇ℓ(z, wt−1 ). Given a sequence of wt ’s from BGD on a dataset, we define the algorithm’s moment condition g(z, w1∶T ) as a vector containing all T steps of BGD. ⎡ w0 − w1 − η∇ℓ(z, w0 ) ⎤ ⎢ ⎥ ⎢ w1 − w2 − η∇ℓ(z, w1 ) ⎥ ⎥ g(z, w1∶T ) = ⎢⎢ ⎥ ⋮ ⎥ ⎢ ⎢wT −1 − wT − η∇ℓ(z, wT −1 )⎥ ⎣ ⎦ Thus, using Theorem 3.6, we can compute the predictability for any approximate ERM obtained from BGD. Note that for a fixed starting point w0 , the sequence of wt ’s that satisfy E[g(z, w1∶T )] = 0 is unique for any ℓ, thus eliminating the need to assume strictly convex ℓ for proper estimation. wt+1 = wt − η ⋅

Predictability Beyond Estimating the Average Value of q(x)

A.2

Consider the following extension of predictability. We say algorithm A has γD′ (P, Q, ℓ, A)predictability γ if ∗ ∗ [sup E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] ≤ γ. E S C(S)∼P,A q∈Q x∼D ′ for some known distribution D′ = (p′1 , . . . , p′N ) on dataset S. A simple example is when the attacker ′

γD′ (P, Q, ℓ, A) = sup

cares about the average of q(x) on some particular subgroup G ⊆ S, and we have D = Unif(G).

In Section 3, we demonstrate how to use the generalized method of moments to compute asymptotic γ(P, Q, ℓ, A)-predictability, where the x is drawn uniformly from the set of unknown individuals, x ∼ Π. We can compute asymptotic γD′ (P, Q, ℓ, A)-predictability with one small change to the moment conditions. Consider when the attacker wants to estimate p = ED′ [q(x)], D′ = (p′1 , . . . , p′N ), given the information they have. Then, at the unique θ0 , p′

U ED′ [q(x) − p] = ED [w′ (x)(q(x) − p)] = 0, where w′ (xi ) = dD (xi ) = pii . dD

Note that we keep ′

EDU [g(x, λ)] = ED [w(x)g(x, λ)] = 0, where w(xi ) = dD (xi ) = pi1N , dD since we still expect A(S) to have the form N1 ∑N i=1 g(xi , λ) = 0. Then we use moment conditions fC(S) (x, θ) = [w′ (x)(q(x) − p)]

fC(S),A(S) (x, θ) = [w′ (x)(q(x) − p), w(x)g(x, λ), λ̃ − λ]⊺ GMM GMM to compute Var[θ̂q∣C(S) ], Var[θ̂q∣C(S),A(S) ], and the resulting predictability.

Theorem A.1. Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). Assume process P satisfies Assumption 3.1. Assume the moment conditions in Equation 2 satisfy the regularity conditions (Appendix A.7.1). Let q ′′ = w′ (x)(q(x) − p) and let g ′ = w(x)g(x, λ). Then A has predictability γ(P, q, ℓ, A) ≤

√ H(1 + log(4)) ⋅ Var[q ′′ ] ⋅ ρcc (q ′′ , g ′ )2 − c0 (w, q, g, ∆), n

where ′

′

⊺

′

−1

c0 (w, q, g, ∆) = Var[q ′′ ]−1 Cov(q ′′ , g ′ )Var[g ′ ]−1 E [ ∂g ] (E [ ∂g ] Var[g ′ ]−1 E [ ∂g ] + Σ−1 ∆) ∂λ ∂λ ∂λ ′

⊺

⋅ E [ ∂g ] Var[g ′ ]−1 Cov(q ′′ , g ′ ). ∂λ

A.3

Notation

• [N ] = {1, . . . , N } • Unif(S) is the uniform distribution over the element in set S • X ∼ N (µ, Σ) is normally distributed with mean µ and variance Σ • E[X] is the expected value of X • Var[X] = E[(X − E[X])2 ] for a one-dimensional random variable X • Var[V ] = E[(X − E[X])(X − E[X])⊺ ] for a vector random variable V • Cov(U, V ) = E[(U − E[U ])(V − E[V ])⊺ ] • ρ(X, Y ) = √ Cov(X,Y )

Var[X]⋅Var[Y ]

is the correlation between X and Y

• DKL (P ∥Q) is the KL-divergence between distributions P and Q • MI(X; Y ∣ Z) is the conditional mutual information between X and Y given Z • Xn →p Y0 , Xn converges to Y0 in probability • Xn →d Y0 , Xn converges to Y0 in distribution • A[i, j] denotes the (i, j) entry of matrix A

A.4

Definitions

Definition A.2 ((ε, δ)-Differential Privacy). A randomized algorithm A is (ε, δ)-differentially private, if for all neighboring datasets S, S ′ , and for all F ⊆ F , Pr[A(S) ∈ F ] ≤ eε Pr[A(S ′ ) ∈ F ] + δ. Definition A.3 (Stationarity). The stochastic process (Xt )t∈Z is stationary if for all k ∈ N, all d t1 , . . . , tk ∈ Z, and all h ∈ Z, (Xt1 , . . . , Xtk ) = (Xt1 +h , . . . , Xtk +h ). Definition A.4 (Ergodicity). The stochastic process (Xt )t∈Z is ergodic if for any integrable function f , the time average n1 ∑nt=1 f (Xt ) converges almost surely to E[f (X0 )]. Definition A.5 (α-mixing). For k ≥ 1, the α-mixing coefficients are defined as α(k) = sup

sup

t∈Z A∈σ(Xs ∶s≤t),B∈σ(Xs ∶s≥t+k)

∣Pr[A ∩ B] − Pr[A] Pr[B]∣ .

The stochastic process (Xt )t∈Z is α-mixing if α(k) → 0, as k → ∞. Definition A.6 (Convex Function). A function f is convex if f (y) ≥ f (x) + ∇f (x)⊺ ∥y − x∥. Definition A.7 (Smooth Function). A function f is H-smooth if ∥∇f (x) − ∇f (y)∥ ≤ H ⋅ ∥x − y∥. Definition A.8 (Lipschitz Function). A function f is L-Lipschitz if ∣f (x) − f (y)∣ ≤ L ⋅ ∥x − y∥.

A.5

Proofs from Section 2

A.5.1

Theorem 2.4

Theorem 2.4. Let PX denote the distribution of X. If Q ⊆ {q ∶ X → [K]} is a family of categorical queries and ℓ(θ̂, y) = −yi log(θ̂i ) is the log loss, predictability is equivalent to γ(P, Q, ℓ, A) = sup

[sup E [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]]

S C(S)∼P,A q∈Q x∼Π

≥ sup sup MI(q(x); A(S) ∣ C(S)) S

q∈Q

Proof. From predictability, we know that A(S) satisfies ∗ ∗ sup EC(S)∼P,A [sup Ex∼Π [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] ≤ γ. q∈Q

∗ ∗ Under the log loss, the optimal θ̂q∣C(S) and θ̂q∣C(S),A(S) predict Pr[q(x) = i ∣ C(S)] and Pr[q(x) = i ∣ C(S), A(S)], respectively, for each i ∈ [K]. Plugging these in and expanding the loss,

Ex∼Π,A [ℓ(Pr[q(x) = i ∣ C(S)], q(x)) − ℓ(Pr[q(x) = i ∣ C(S), A(S)], q(x))] K

i=1

= Ex∼Π,A [− ∑ 1{y = i} log(Pr[q(x) = i ∣ C(S)]) + ∑ 1{y = i} log(Pr[q(x) = i ∣ C(S), A(S)])] K

= Ex∼Π,A [− ∑ 1{y = i} log( i=1

Pr[q(x) = i ∣ C(S), A(S)] )] Pr[q(x) = i ∣ C(S)]

= Ex∼Π,A [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]. Thus, sup EC(S)∼P [sup Ex∼Π,A [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]] ≤ γ S

q∈Q

From here, observe that sup EC(S)∼P [sup Ex∼Π,A [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]] S

q∈Q

≥ sup sup EC(S)∼P,A [Ex∼Π [DKL (Pq(x)∣C(S),A(S) ∥Pq(x)∣C(S) )]] S

q∈Q

≥ sup sup MI(q(x); A(S) ∣ C(S)) S

A.5.2

q∈Q

Theorem 2.5, Predictability and Differential Privacy are Incomparable

∗ accurately. The best that θ̂q∣C(S) can do is estimate 0.5 because pS∖C(S) can range anywhere from 0 to 1 and C(S) is always a set of 1’s.

∗ can estimate pS∖C(S) very accurately. In particular, However, given C(S) and A(S), θ̂q∣C(S),A(S)

1 1 pC(S) + pS∖C(S) = p 2 2 pS∖C(S) = 2p − pC(S) ∗ Consider when θ̂q∣C(S),A(S) constructs the estimator

p̂S∖C(S) = 2 ⋅ A(S) − pC(S) (∆ ∼ Lap(0, Nε ))

= 2 ⋅ (p + ∆) − pC(S) = pS∖C(S) + 2∆ = pS∖C(S) + ∆′

(∆ ∼ Lap(0, 2ε )) N

Let ℓ(ŷ, y) = (ŷ − y)2 be the squared loss. Consider the predictability of q and plug in the estimators ∗ ∗ θ̂q∣C(S) and θ̂q∣C(S),A(S) , sup

∗ ∗ [ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]]

S C(S)∼P x∼Π,A

∗ ∗ [ E [(θ̂q∣C(S) − q(x)) − (θ̂q∣C(S),A(S) − q(x))]]

= sup

S C(S)∼P x∼Π,A

S C(S)∼P,A

∗ ∗ [(θ̂q∣C(S) − E [q(x)])2 + E [( E [q(x)] − q(x))2 ] − (θ̂q∣C(S),A(S) − E [q(x)])2 x∼Π

x∼Π

− E [( E [q(x)] − q(x)) ]] 2

x∼Π

(bias-variance decomposition of squared loss) = sup

∗ [(θ̂q∣C(S) −

= sup

∗ ∗ [(θ̂q∣C(S) − pS∖C(S) )2 − (θ̂q∣C(S),A(S) − pS∖C(S) )2 ]

= sup

[(0.5 − pS∖C(S) )2 − (pS∖C(S) + ∆′ − pS∖C(S) )2 ]

= sup

S C(S)∼P,A S C(S)∼P,A S C(S)∼P,A S C(S)∼P

x∼Π

[(0.5 − pS∖C(S) )2 − EA [(∆′ )2 ]]

8ε2 ] N2 S C(S)∼P 8 = sup E [(0.5 − pS∖C(S) )2 − ] N S C(S)∼P 8 = sup ((0.5 − pS∖C(S) )2 − ) N S = sup

∗

E [q(x)]) − (θ̂q∣C(S),A(S) − E [q(x)])

x∼Π

[(0.5 − pS∖C(S) )2 −

(ε = √1N ) (P always selects the same C(S))

For the worst case dataset S, pS∖C(S) → 0, and predictability → 0.52 − N8 . Thus, γ ≥ Ω(1). For the second part of the statement, let A(S) release the exact proportion, A(S) = p. Consider a process P which selects N2 entries i.i.d. from S to form C(S). Clearly, A(S) is not differentially private. ∗ We demonstrate that A maintains small predictability. Given A(S) and C(S), θ̂q∣C(S),A(S) can ∗ determine pS∖C(S) exactly. However, given only C(S), θ̂q∣C(S) can still estimate pS∖C(S) fairly accurately using pC(S) because C(S) is an i.i.d. draw from the overall dataset.

Let ℓ(ŷ, y) = (ŷ − y)2 be the squared loss. Consider the predictability of q and plug in the estimators ∗ ∗ θ̂q∣C(S) and θ̂q∣C(S),A(S) , sup

∗ ∗ [ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]]

S C(S)∼P x∼Π,A

= sup

∗ ∗ − q(x))2 − (θ̂q∣C(S),A(S) − q(x))2 ]] [ E [(θ̂q∣C(S)

= sup

[ E [(pC(S) − q(x))2 − (pS∖C(S) − q(x))2 ]]

= sup

[(pC(S) − E [q(x)])2 + E [( E [q(x)] − q(x))2 ] − (pS∖C(S)) − E [q(x)])2

S C(S)∼P x∼Π

S C(S)∼P x∼Π S C(S)∼P

x∼Π

− E [( E [q(x)] − q(x))2 ]] x∼Π

x∼Π

(bias-variance decomposition)

x∼Π

[(pC(S) − E [q(x)])2 − (pS∖C(S)) − E [q(x)])2 ]

= sup

[(pC(S) − pS∖C(S) ) − (pS∖C(S)) − pS∖C(S) )2 ]

= sup

[(pC(S) − pS∖C(S) )2 ]

= sup

[((pC(S) − pS ) − (pS∖C(S) − pS ))2 ]

= sup

[((pC(S) − pS ))2 ] +

= sup

S C(S)∼P

x∼Π

S C(S)∼P S C(S)∼P S C(S)∼P S C(S)∼P

C(S)∼P

[((pS∖C(S) − pS ))2 ] − 2

C(S)∼P

[(pC(S) − pS )(pS∖C(S) − pS )]

≤ O( N1 ) + O( N1 ) + 0 = O( N1 ), where the last line follows from the concentration of pC(S) and pS∖C(S) around pS . A.5.3

Theorem 2.7, Connection to Mutual Information Differential Privacy

Theorem 2.7. Let Qbin = {q ∶ X ↦ {0, 1}} be the set of all binary queries on X and let ℓ be the log loss. If algorithm A has γ(PDP , Qbin , ℓ, A)-predictability γ, then A is γ-MI-DP. Proof. We know that A(S) satisfies ∗ ∗ sup EC(S)∼PDP ,A [ sup Ex∼Unif(S∖C(S)) [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] ≤ γ. q∈Qbin

Plugging in the form of PDP , we have ∗ ∗ sup sup sup EA [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))]] ≤ γ. i} i },A(S) S i∈[N ] q∈Qbin

This is equivalent to ∗ ∗ sup ES∼χ [ sup sup EA [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))]] ≤ γ. i} i },A(S) i∈[N ] q∈Qbin

χ∈∆(X N )

Observe that ES∼χ [

sup i∈[N ],q∈Qbin

≥

∗ ∗ EA [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))]] i} i },A(S)

sup i∈[N ],q∈Qbin

∗ ∗ ES∼χ,A [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))] i} i },A(S)

Thus, sup i∈[N ],q∈Qbin

∗ ∗ ES∼χ,A [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))] ≤ γ. i} i },A(S)

∗ ∗ Under the log loss, the optimal θ̂q∣C(S) and θ̂q∣C(S),A(S) predict Pr[q(xi ) = 1 ∣ S ∖ {xi }] and Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)], respectively.

Plugging these in and expanding the loss, ES∼χ,A [ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }], q(xi )) − ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)], q(xi ))] = ES∖{xi }∼χ [Exi ∣S∖{xi },A [ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }], q(xi )) − ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)], q(xi ))]] 20

= ES∖{xi }∼χ [DKL (Pq(x)∣S∖{xi },A(S) ∥Pq(x)∣S∖{xi } )]

(Theorem 2.4)

= MI(q(xi ); A(S) ∣ S ∖ {xi }) where MI is the conditional mutual information between q(xi ) and A(S) given S ∖ {xi }. Thus, we have sup sup MI(q(xi ); A(S) ∣ S ∖ {xi }) ≤ γ,

sup

χ∈∆(X N ) i∈[N ] q∈Qbin

which implies sup

sup MI(xi ; A(S) ∣ S ∖ {xi }) ≤ γ.

χ∈∆(X N ) i∈[N ]

Thus, A(S) is γ-mutual-information differentially private (Definition 2.6). Theorem A.9. If A is ε-differentially private, then for process PDP , A satisfies ε-predictability for all binary queries Qbin under the log loss. Proof. Plugging in the form of PDP into predictability, we look to bound ∗ ∗ sup sup sup EA [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))] i} i },A(S) S i∈[N ] q∈Qbin

Since A is ε-differentially private, we know that for all S and i, e−ε ≤

Pr[A(S) ∣ S] ≤ eε . Pr[A(S) ∣ S ∖ {xi }]

Applying Bayes Rule, we know Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] =

Pr[A(S) ∣ S ∖ {xi }, q(xi ) = 1] ⋅ Pr[q(xi ) = 1 ∣ S ∖ {xi }] . Pr[A(S) ∣ S ∖ {xi }]

Let S = {S ′ ∣ S ′ ∖ {x′i } = S ∖ {xi } and q(x′i ) = 1. Then Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] =

∑S ′ ∈S Pr[A(S) ∣ S ′ ] ⋅ Pr[q(xi ) = 1 ∣ S ∖ {xi }] . Pr[A(S) ∣ S ∖ {xi }]

Thus, plugging in the ratio from differential privacy, we have e−ε ⋅ Pr[q(xi ) = 1 ∣ S ∖ {xi }] ≤ Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] ≤ eε ⋅ Pr[q(xi ) = 1 ∣ S ∖ {xi }]. We can similarly conclude e−ε ⋅ Pr[q(xi ) = 0 ∣ S ∖ {xi }] ≤ Pr[q(xi ) = 0 ∣ S ∖ {xi }, A(S)] ≤ eε ⋅ Pr[q(xi ) = 0 ∣ S ∖ {xi }]. In other words, −ε ≤ log (

Pr[q(xi ) = 0 ∣ S ∖ {xi }, A(S)] Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] ) , log ( ) ≤ ε. Pr[q(xi ) = 1 ∣ S ∖ {xi }] Pr[q(xi ) = 0 ∣ S ∖ {xi }]

Expanding out the log loss in the predictability bound, ∗ ∗ ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi )) i} i },A(S)

= ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }], q(xi )) − ℓ(Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)], q(xi )) = − Pr[q(xi ) = 1] ⋅ log(Pr[q(xi ) = 1 ∣ S ∖ {xi }]) − (1 − Pr[q(xi ) = 1]) ⋅ log(1 − Pr[q(xi ) = 1 ∣ S ∖ {xi }]) + Pr[q(xi ) = 1] ⋅ log(Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)]) − (1 − Pr[q(xi ) = 1]) ⋅ log(1 − Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)]) = Pr[q(xi ) = 1] ⋅ log (

Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] Pr[q(xi ) = 0 ∣ S ∖ {xi }, A(S)] ) + Pr[q(xi ) = 0] ⋅ log ( ) Pr[q(xi ) = 1 ∣ S ∖ {xi }] Pr[q(xi ) = 0 ∣ S ∖ {xi }] 21

Since both −ε ≤ log (

Pr[q(xi ) = 1 ∣ S ∖ {xi }, A(S)] Pr[q(xi ) = 0 ∣ S ∖ {xi }, A(S)] ) , log ( ) ≤ ε, Pr[q(xi ) = 1 ∣ S ∖ {xi }] Pr[q(xi ) = 0 ∣ S ∖ {xi }]

we must have ∗ ∗ −ε ≤ ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi )) ≤ ε. i} i },A(S)

The above holds for every S, i, and q; thus, we can conclude ∗ ∗ sup sup sup EA [ℓ(θ̂q∣S∖{x , q(xi )) − ℓ(θ̂q∣S∖{x , q(xi ))] ≤ γ. i} i },A(S) S i∈[N ] q∈Qbin

A.5.4

Lemma 2.9

Lemma 2.9. Let ℓ(θ̂) = Ex∼Π [ℓ(θ̂, q(x)] be a convex, H-smooth loss. Let θ0q = Ex∼Π [q(x)]. Then for any pair of estimators θ̂q∣C(S) and θ̂q∣C(S),A(S) , E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] ≤ H∣θ̂q∣C(S) − θ0 ∣ ⋅ ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣. q

xi ∼Π

For log loss, if the true p0 = Pr[q(x) = 1] satisfies p0 ∈ [τ, 1 − τ ], H = τ12 . For squared loss, H = 2. Proof. E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]

xi ∼Π

= ℓ(θ̂q∣C(S) ) − ℓ(θ̂q∣C(S),A(S) ) ≤ ℓ′ (θ̂q∣C(S) )∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣ ≤ H∣θ̂q∣C(S) − θ0q ∣ ⋅ ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣

A.6

(convexity) (smoothness)

Post-Processing and Composition of Predictability

Theorem A.10 (Post-Processing). If A(S) has γ(P, Q, ℓ, A)-predictability γ, then f ○ A has γ(P, Q, ℓ, f ○ A))-predictability γ. Proof. Notice that due to the monotonicity of Bayes risk, the Bayes optimal predictor must satisfy ∗ ∗ E[ℓ(θ̂q∣C(S),A(S) , q(x))] ≤ E[ℓ(θ̂q∣C(S),f (A(S)) , q(x))].

Thus, sup

∗ ∗ [sup E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),f (A(S)) , q(x))]]

S C(S)∼P,A q∈Q x∼Π

≤ sup

∗ ∗ [sup E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]]

S C(S)∼P,A q∈Q x∼Π

Theorem A.11 (Composition). For two algorithms A1 and A2 , the γ(P, Q, ℓ, A)-predictability of the composed (A1 (S), A2 (S)) is bounded by γ(P, Q, ℓ, (A1 , A2 )) ≤ sup

∗ ∗ [sup E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S)

S C(S)∼P,A1 q∈Q x∼Π

+ sup

∗ ∗ [sup E [ℓ(θ̂q∣C(S),A , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S) 1 (S),A2 (S)

S C(S)∼P,A1 ,A2 q∈Q x∼Π

Proof. sup

[sup

= sup

[sup

S C(S)∼P q∈Q x∼Π,A1 ,A2

∗ ∗ [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S),A2 (S)

S C(S)∼P q∈Q x∼Π,A1 ,A2

∗ ∗ [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A , q(x)) 1 (S)

∗ ∗ + ℓ(θ̂q∣C(S),A , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S) 1 (S),A2 (S)

≤ sup

[sup

S C(S)∼P q∈Q x∼Π,A1

+ sup

[sup

∗ ∗ [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S)

S C(S)∼P q∈Q x∼Π,A1 ,A2

∗ ∗ [ℓ(θ̂q∣C(S),A , q(x)) − ℓ(θ̂q∣C(S),A , q(x))]] 1 (S) 1 (S),A2 (S)

where the last line follows from the subadditivity of supremum. A.7 A.7.1

Proofs from Section 3 Regularity Conditions

Define sample quantities fn (θ) =

1 n ∑ f (xi , θ) n i=1

Gn (θ) =

1 n ∑ ∇f (xi , θ) n i=1

Ωn (θ) =

1 n ⊺ ∑ f (xi , θ)f (xi , θ) n i=1

and define population quantities E[f (θ)] = E[f (x, θ)] G(θ) = E[∇f (x, θ)] ∞

Ω(θ) = ∑ f (x0 , θ)f (xk , θ)⊺ . k=−∞

Assume the following regularity conditions. • The domain Θ of θ is a compact subset of Rr and θ0 is its interior. • f (x, θ) is Rr ↦ Rm function of θ, where r ≤ m. • f is continuous in θ and continuously differentiable on a neighborhood of θ0 in θ. • E[f (θ)] = 0 if and only if θ = θ0 . • G(θ0 ) is a m × r matrix of rank r. • Ω(θ0 ) is a m × m positive definite matrix. • W is a m × m positive definite matrix. • f (x, θ), G(θ), and Σ(θ) are dominated (there exists a function β(x) with E[β(x)] < +∞ such that ∣f (x, θ)∣ ≤ β(x), ∣G(θ)∣ ≤ β(x) and ∣Ω(θ)∣ ≤ β(x)). • For each θ, fn (θ) obeys a central limit theorem (Theorem A.13) • fn (θ), Gn (θ), and Ωn (θ) obey a uniform law of large numbers (Theorem A.12). Theorem A.12 (Uniform Law of Large Numbers for Stationary Ergodic Processes [32]). Let Y1 (θ), . . . , Yn (θ) be from a stationary ergodic process. Define ψ(θ) = E[Y1 (θ)],

Ȳn (θ) =

1 n ∑ Yi (θ). n i=1

Assume a finite mean ψ(θ) < +∞ for all θ in a closed bounded set Θ ⊆ Rk . Assume Yi (θ) is continuous at each θ ∈ Θ. Assume that Yi (θ) is dominated; there exists a random variable Z with a finite mean such that supθ∈Θ ∣Yi (θ)∣ ≤ Z. Then sup ∣Ȳn (θ) − ψ(θ)∣ →p 0 θ∈Θ

Theorem A.13 (Central Limit Theorem for Stationary Ergodic Processes [32]). Let X1 , . . . , Xn be from a stationary ergodic process. Assume (Xt ) is α-mixing with mixing coefficients satisfying ∞

∑ α(k)

δ/(2+δ)

< ∞.

k=1

As n → ∞,

√

n(X̄n − θ) →d N (0, Ω∞ )

where θ is the population mean and Ω∞ = ∑∞ k=−∞ Cov(X0 , Xk ) is the long-run covariance. A.7.2

Theorem 3.2, GMM Efficiency

(x,θ) Theorem 3.2 (Efficient GMM Estimator [32]). Let G = E[ ∂f ∂θ ] be the Jacobian and let Ω = ∞ ⊺ ∑k=−∞ E [f (x0 , θ)f (xk , θ) ] be the long-run covariance. As n → ∞, with W = Ω−1 (θ0 ), the efficient GMM estimator θ̂ GMM is regular and asymptotically efficient with asymptotic distribution

√ n(θ̂ GMM − θ0 ) ∼ N (0, [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 ).

This is a standard result from [32]. For completeness, we include a proof of the efficient GMM estimator for sampling without replacement. In particular, consider sample quantities fn (θ) =

1 n ∑ f (xi , θ) n i=1

Gn (θ) =

1 n ∑ ∇f (xi , θ) n i=1

Ωn (θ) =

1 n ⊺ ∑ f (xi , θ)f (xi , θ) n i=1

and population quantities E[f (θ)] =

1 N ∑ f (xi , θ) N i=1

G(θ) =

1 N ∑ ∇f (xi , θ) N i=1

Ω(θ) =

1 N ⊺ ∑ f (xi , θ)f (xi , θ) . N i=1

Consider the specific form of ULLN and CLT for sampling without replacement. Theorem A.14 (Uniform Law of Large Numbers for Sampling without Replacement [35]). Let Y1 (θ), . . . , Yn (θ) be a simple random sample without replacement from finite population {Y1 (θ), . . . , YN (θ)}, where n/N = ν, 0 < ν < 1. Define ψ(θ) =

1 N ∑ Yi (θ), N i=1

Ȳn (θ) =

1 n ∑ Yi (θ). n i=1

Theorem A.15 (Central Limit Theorem for Sampling without Replacement [47]). When sampling n elements from N elements uniformly at random, where n/N = ν, 0 < ν < 1. As n, N → ∞, √ n (X̄n − θ) →d N (0, F ) 1−ν where θ, F are the population mean and covariance matrix. 24

Theorem A.16 (Optimal GMM Estimator for Sampling without Replacement). Consider a sample without replacement x1 , . . . , xn from a larger population of N elements, where n/N = ν and 0 < ν < 1 is a constant. Given the sample, the GMM estimator of θ is defined as θ̂n = arg min r fn (θ)⊺ W fn (θ). θ∈Θ⊆R

Assume the regularity conditions from Appendix A.7.1 hold. Then θ̂n is asymptotically normal, √ n (θ̂n − θ0 ) →d N (0, (G(θ0 )⊺ W G(θ0 ))−1 G(θ0 )⊺ W Ω(θ0 )W G(θ0 )(G(θ0 )⊺ W G(θ0 ))−1 ). 1−ν With optimal choice W = Ω(θ0 ), θ̂nGMM is asymptotically normal as √ n (θ̂ GMM − θ0 ) →d N (0, (G(θ0 )⊺ W G(θ0 ))−1 . 1−ν n and is asymptotically efficient among the class of all regular estimators that only use the information contained in the moment conditions. Proof. The proof follows similarly to the standard GMM proof for IID samples from [42], Chapter 3, Theorem 3.1. Let Qn = fn (θ)⊺ W fn (θ). For every fixed θ, fn (θ), Gn (θ), and Ωn (θ) converge in probability to E[f (x, θ)], G(θ), and Ω(θ), respectively, using Theorem A.14. Furthermore, √ n Ω(θ0 )−1/2 (fn (θ0 )) ≡ Un →d U ∼ N (0, I). 1−ν For each fixed θ, the uniform law of large numbers implies that fn (θ) →p E[f (θ)]. This implies that n n ⋅ Qn (θ0 ) is stochastically bounded ( 1−ν ⋅ Qn (θ0 ) Qn (θ0 ) →p E[f (θ0 )]⊺ W E[f (θ0 )] = 0. Thus, 1−ν does not go to infinity in probability). Consider any estimator Tn∗ that satisfies Qn (Tn∗ ) →p 0. For each fixed θ, Theorem A.14 implies that fn (θ) →p E[f (θ)]. Then applying Theorem A.25, Qn (θ) →p E[f (θ)]⊺ W E[f (θ)]. Since E[f (θ)] = 0 only when θ = θ0 , then Tn∗ →p θ0 . Tn∗ is consistent. n Consider any estimator Tn∗ that satisfies 1−ν ⋅ Qn (Tn∗ ) is stochastically bounded. This implies that ∗ ∗ Qn (Tn ) →p 0, which means Tn →p θ0 . The mean value theorem and the CLT condition for fn (θ) give √ √ √ n n n (fn (Tn∗ )) = (fn (θ0 )) − Gn (TnMID ) (T ∗ − θ0 ) 1−ν 1−ν 1−ν n √ √ n n (fn (Tn∗ )) = Ω(θ0 )1/2 Un − Gn (TnMID ) (T ∗ − θ0 ) 1−ν 1−ν n 2

for some intermediate value TnMID . Then using the triangle inequality, ∥a − b∥W ≤ ∥a∥W + ∥b∥W , √ 2 √ 2 2 n n MID ∗ ∗ ∥Gn (Tn ) (T − θ0 )∥ ≤ ∥ (fn (Tn ))∥ + ∥Ω(θ0 )1/2 Un ∥W 1−ν n 1 − n/N W W n 1 ⊺ n ∗ MID ⊺ MID ∗ ∗ ⋅ (Tn − θ0 )Gn (Tn ) W Gn (Tn )(Tn − θ0 ) ≤ ⋅ Qn (Tn ) + Un Ω(θ0 )1/2 W Ω(θ0 )1/2 Un 1−ν 1−ν 2 n n Un and 1−ν ⋅Qn (Tn∗ ) are stochastically bounded, so 1−ν ⋅(Tn∗ −θ0 )Gn (TnMID )⊺ W Gn (TnMID )(Tn∗ −θ0 ) is stochastically bounded.

Since we have TnMID →p θ0 and uniform convergence of Gn (θ), Theorem A.26 implies that Gn (TnMID )⊺ W Gn (TnMID ) →p G(θ0 )⊺ W G(θ0 ), where G(θ0 )⊺ W G(θ0 ) is positive definite. Let λ be the smallest eigenvalue of G(θ)⊺ W G(θ). Then in the probability limit, √ 2 n n λ⋅∥ (Tn∗ − θ0 )∥ ≤ ⋅ (Tn∗ − θ0 )Gn (TnMID )⊺ W Gn (TnMID )(Tn∗ − θ0 ). 1−ν 1−ν 25

√ n √ n ⋅ (Tn∗ − θ0 ) must be stochastically bounded. This in turn implies that 1−ν (fn (Tn∗ )) is Thus, 1−ν stochastically bounded. Consider the estimator Tn = arg min Qn (θ). We must have Qn (Tn ) ≤ Qn (θ √0 ).n Qn (θ0 ) and (fn (Tn )) is Qn (Tn ) are stochastically bounded, which implies that Tn is consistent and 1−ν stochastically bounded, by applying the previous steps. T must satisfy the first order condition n √ n fn (Tn ) = 0. Using the mean value theorem, the first order condition is equivalent Gn (Tn )⊺ W 1−ν to √ n (Tn − θ0 ) −Gn (Tn )⊺ W Ω(θ0 )1/2 Un + Gn (Tn )⊺ W Gn (TnMID ) 1−ν In the probability limit, √ n (Tn − θ0 ) = (Gn (Tn )⊺ W Gn (TnMID ))−1 Gn (Tn )⊺ W Ω(θ0 )1/2 Un 1−ν exists because Gn (TnMID )⊺ W Gn (Tn ) →p G(θ0 )⊺ W G(θ0 ), and G(θ)⊺ W G(θ) is positive definite. Then in the limit, √ n (Tn − θ0 ) →d (G(θ0 )⊺ W G(θ0 ))−1 G(θ0 )⊺ W Ω(θ0 )1/2 U 1−ν where Gn (TnMID )⊺ W Gn (Tn ) converges in probability and in distribution to (G(θ0 )⊺ W G(θ0 ))−1 , Gn (Tn )⊺ W Ω(θ0 )1/2 converges in probability and in distribution to G(θ0 )⊺ W Ω(θ0 )1/2 , and Un converges in distribution to U . Thus, √ n (Tn − θ0 ) →d N (0, (G(θ0 )⊺ W G(θ0 ))−1 G(θ0 )⊺ W Ω(θ0 )W G(θ0 )(G(θ0 )⊺ W G(θ0 ))−1 ). 1−ν The choice of W = Ω(θ0 ) leads to the smallest covariance of (G(θ0 )⊺ Ω(θ0 )G(θ0 ))−1 using Theorem A.24. Finally, following [32] and Proposition 3.6 from [19], we justify why the choice of W = Ω(θ0 ) is asymptotically efficient. Consider any consistent regular estimator that only uses the moment conditions for estimation. It must lie in the span of the moment conditions and take the form, A⊺ fn , and have asymptotic variance A⊺ ΩA, since E[fn (θ0 )fn (θ0 )⊺ ] = Ω. The consistent estimator must also satisfy the first-order condition A⊺ G = I. Consider the minimum possible variance that can be achieved, min

A s.t. A⊺ G=I

A⊺ ΩA = (G⊺ ΩG)−1 ,

thus demonstrating optimality and asymptotic efficiency among the class of all estimators that only use the moment conditions for any estimator that achieves asymptotic variance (G⊺ ΩG)−1 . Theorem 3.3. Let ℓ(θ̂) = Ex∼Π [ℓ(θ̂, q(x)] be a twice continuously differentiable loss function with ∇ℓ(θ0 ) = 0 and ∇2 ℓ(θ0 ) positive definite. Then ∗

∗

E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] ≤ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] + o( n ) GMM

x∼Π

GMM

x∼Π

Proof. ∗

∗

E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))] − E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]

xi ∼Π

GMM

xi ∼Π

∗ ∗ GMM GMM = ℓ(θ̂q∣C(S) ) − ℓ(θ̂q∣C(S),A(S) ) − ℓ(θ̂q∣C(S) ) + ℓ(θ̂q∣C(S),A(S) ) ∗ GMM GMM ∗ = ℓ(θ̂q∣C(S) ) − ℓ(θ̂q∣C(S) ) + ℓ(θ̂q∣C(S),A(S) ) − ℓ(θ̂q∣C(S),A(S) ) 1 1 ≤ o( ) + o( ) (Theorem A.17) n n 1 = o( ) n

We can apply Theorem A.17 because both θ̂∗ and θ̂ GMM are asymptotically efficient, asymptotically normal, and regular. 26

Theorem A.17. Let θ̂1 and θ̂2 be any two asymptotically efficient and asymptotically normal regular estimators with respect to the same observation and information. Let ℓ(θ) be a twice continuously differentiable loss function with ∇ℓ(θ0 ) = 0 and ∇2 ℓ(θ0 ) positive definite. Then ℓ(θ̂1 )−ℓ(θ̂2 ) = o( n1 ). Proof. Since both θ̂1 and θ̂2 are regular and asymptotically efficient, they admit the same influence function ψ(X). Thus, we express each estimator as √

1 n n(θ̂1 − θ0 ) = √ ∑ ψ(Xi ) + o(1), n i=1

√

1 n n(θ̂2 − θ0 ) = √ ∑ ψ(Xi ) + o(1). n i=1

Taking the difference of the above, we have √ n(θ̂1 − θ̂2 ) = o(1) 1 θ̂1 − θ̂2 = o ( √ ) n Next, following the delta method from Lemma A.18, we perform a second-order Taylor expansion of ℓ(θ̂) around θ0 . 1 ℓ(θ̂) = ℓ(θ0 ) + ∇ℓ(θ0 )⊺ (θ̂ − θ0 ) + (θ̂ − θ0 )⊺ ∇2 ℓ(θ0 )(θ̂ − θ0 ) + o (∥θ̂ − θ0 ∥2 ) 2 1 ⊺ 2 = ℓ(θ0 ) + (θ̂ − θ0 ) ∇ ℓ(θ0 )(θ̂ − θ0 ) + o (∥θ̂ − θ0 ∥2 ) (∇ℓ(θ0 ) = 0) 2 Then consider ℓ(θ̂1 ) − ℓ(θ̂2 ), and plug in the second order expansion. 1 1 1 ℓ(θ̂1 ) − ℓ(θ̂2 ) = (θ̂1 − θ0 )⊺ ∇2 ℓ(θ0 )(θ̂1 − θ0 ) − (θ̂2 − θ0 )⊺ ∇2 ℓ(θ0 )(θ̂2 − θ0 ) + o ( ) 2 2 n 1 1 = (θ̂1 − θ̂2 )⊺ ∇2 ℓ(θ0 )(θ̂1 − θ̂2 ) + o ( ) 2 n 1 = o( ) (θ̂1 − θ̂2 = o( √1n )) n √ Lemma A.18 (Delta Method). Let Yn be a sequence of random variables that satisfies n(Yn −θ0 ) → N (0, σ 2 ) in distribution. For a given function g and θ0 , suppose that g ′ (θ0 ) = 0 and g ′′ (θ0 ) exists and is nonzero. Then n(g(Yn ) − g(θ0 )) → σ 2 A.7.3

g ′′ (θ0 ) 2 χ1 . 2

Theorem 3.4, Difference of GMM Estimators

GMM GMM Theorem 3.4. When the efficient GMM estimators θ̂q∣C(S) and θ̂q∣C(S),A(S) are constructed on the same sample, their difference has asymptotic distribution GMM GMM GMM GMM θ̂q∣C(S) − θ̂q∣C(S),A(S) ∼ N (0, Var[θ̂q∣C(S) ] − Var[θ̂q∣C(S),A(S) ])

Proof. We know

√

n (fn (θ0 )) ≡ Un →d U ∼ N (0, I). 1−ν We have, in the limit, for a GMM predictor Tn √ n (Tn − θ0 ) →d (G(θ0 )⊺ W G(θ0 ))−1 G(θ0 )⊺ W Ω(θ0 )1/2 Un 1−ν Ω(θ0 )−1/2

Thus, Tn is asymptotically linear with √ √ n n (Tn − θ0 ) →d (G⊺ W G)−1 G⊺ W (fn (θ0 )) 1−ν 1−ν Let (G⊺ W G))−1 G⊺ W = A⊺ . This predictor has covariance A⊺ E [

n fn (θ0 )fn (θ0 )⊺ ] A. 1−ν

All choices of A must satisfy A⊺ G = I for the first order condition. The optimal A also minimizes the above covariance. A∗ = arg

A⊺ ΩA

min

A s.t. A⊺ G=I

where E[fn (θ0 )fn (θ0 )⊺ ] = Ω. Consider another Ā that satisfies Ā⊺ G = I. The optimality condition of A∗ implies that ΩA∗ = GΛ where Λ is the Lagrangian multiplier. Consider (Ā − A∗ )⊺ ΩA = (Ā − A∗ )⊺ GΛ ⊺

= (Ā⊺ G − A∗ G)Λ = (I − I)Λ =0 The predictor that only uses the first half of the moment conditions in fn is asymptotically linear with √ √ n n 1 ⊺ −1 ⊺ (T − θ0 ) →d (G1 W1 G1 ) G1 W1 (f1 (θ0 )) 1−ν n 1−ν Let (G⊺1 W1 G1 ))−1 G⊺1 W1 = A⊺1 . A1 satisfies A⊺1 G1 = I by the first order condition. Let Ā⊺ = [A⊺1 0]. Then Ā⊺ G = [A⊺1

0] G

= [A⊺1

0] [

G1 ] G2

= A⊺1 G1 =I Thus, we must have (Ā−A∗ )⊺ ΩA = 0. Thus, Ā⊺ ΩA∗ = A∗ ⊺ ΩA∗ . Ā⊺ ΩA∗ is the covariance between (Tn1 −θ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(Tn1 , Tn ) = Var[Tn ], and Var[Tn1 −Tn ] = Var[Tn1 ]−Var[Tn ]. ∗ Thus, in the limit, Tn1 − Tn is distributed N (0, Var[Tn1 ] − Var[Tn ]). Here, θ̂q∣C(S) is exactly Tn1 , and ∗ θ̂q∣C(S),A(S) is exactly Tn .

A.7.4

Theorem 3.6, Asymptotic Predictability of a Query

√ H(1 + log(4)) ⋅ Var[q ′′ ] ⋅ ρcc (q ′′ , g ′ )2 − c0 (w, q, g, ∆), n

where ′

′

⊺

′

−1

c0 (w, q, g, ∆) = Var[q ′′ ]−1 Cov(q ′′ , g ′ )Var[g ′ ]−1 E [ ∂g ] (E [ ∂g ] Var[g ′ ]−1 E [ ∂g ] + Σ−1 ∆) ∂λ ∂λ ∂λ ′

⊺

⋅ E [ ∂g ] Var[g ′ ]−1 Cov(q ′′ , g ′ ). ∂λ

Proof. γ(P, q, ℓ, A) = sup

∗ ∗ [ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]]

S C(S)∼P x∼Π,A

1 GMM GMM [ E [ℓ(θ̂q∣C(S) , q(x)) − ℓ(θ̂q∣C(S),A(S) , q(x))]] + o ( ) n (using Theorem 3.3) 1 GMM GMM GMM ≤ sup E [H ⋅ ∣θ̂q∣C(S) − θ0q ∣ ⋅ ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣]] + o ( ) n S C(S)∼P (using Lemma 2.9) ≤ sup

= sup

S C(S)∼P x∼Π,A

S C(S)∼P

GMM GMM GMM [H ⋅ ∣θ̂q∣C(S) − θ0q ∣ ⋅ ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣]]

where asymptotically, we drop the lower-order term. GMM GMM GMM Then we bound ∣θ̂q∣C(S) − θ0q ∣ and ∣θ̂q∣C(S) − θ̂q∣C(S),A(S) ∣ using the behavior of the estimators.

σ2

GMM GMM = θ2 ∼ N (θ0 , n2 ). Thus, We know θ̂q∣C(S) = θ1 ∼ N (θ0 , n1 ) and θ̂q∣C(S),A(S)

Pr[∣θ1 − θ0 ∣ ≥ t] ≤ 2e−t n/σ1 2

We want this probability to be less than δ/2. 2 2 δ = 2e−t n/σ1 2 2 2 δ = e−t n/σ1 4 t2 n log(4/δ) = 2 σ1

√

σ2

σ12 log(4/δ) = t2 n σ12 log(4/δ) =t n

σ2

We know θ1 − θ2 ∼ N (0, n1 − n2 ). Pr[∣θ1 − θ2 ∣ ≥ t] ≤ 2e−t n/(σ1 −σ2 ) 2

We want this probability to be less than δ/2. 2 2 2 δ = 2e−t n/(σ1 −σ2 ) 2 2 2 2 δ = e−t n/(σ1 −σ2 ) 4 t2 n log(4/δ) = 2 (σ1 − σ22 )

√

(σ12 − σ22 ) log(4/δ) = t2 n (σ12 − σ22 ) log(4/δ) =t n

Then consider the difference in the loss. ℓ(θ1 ) − ℓ(θ2 ) ≤ H∣θ1 − θ0 ∣ ⋅ ∣θ1 − θ2 ∣ √ √ σ12 log(4/δ) (σ12 − σ22 ) log(4/δ) ≤H⋅ ⋅ n n 29

(Lemma 2.9) (with probability at least 1 − δ)

√ H log(4/δ) ⋅ σ1 σ12 − σ22 = n

(with probability at least 1 − δ)

Let X = ℓ(θ1 ) − ℓ(θ2 ). Note that predictability is γ = E[X]. Thus, using standard techniques to integrate the tail, we can convert the high-probability bound into a bound on the expectation, yielding the final predictability bound. We know √ ⎡ H log(4/δ) ⋅ σ1 σ12 − σ22 ⎤⎥ ⎢ ⎥ ≤ δ. Pr⎢X > ⎢ ⎥ n ⎣ ⎦ √

Let K =

H⋅σ1

σ12 −σ22

, then Pr[X > t] ≤ 4e−t/K .

Let t0 = K log(4). Thus, E[X] ≤ ∫ =∫

t0 0

1dt + ∫

K log(4) 0

∞

4e−t/K

1dt + ∫

∞

4e−t/K

K log(4)

= K log(4) + 4Ke−K log(4)/K = K log(4) + 4Ke− log(4) = K log(4) + K = K(1 + log(4)) Thus,

√ H(1 + log(4)) ⋅ σ1 σ12 − σ22 . γ= n

In particular, we consider n, N → ∞, n/N → 0, so we do not need to consider a finite sample correction when estimating Ex∼Unif(S∖C(S)) [q(x)]. GMM Now we compute the exact form of σ1 and σ2 using [G⊺ Ω−1 G]−1 . For θ̂q∣C(S) , we have θ = (p, λ) and

fC(S) (x, θ) = [w(x)(q(x) − p)] . We need to compute [G⊺ Ω−1 G]−1 . (x,θ) ] G = E [ ∂f ∂θ

= E [−w(x)] = −1 Ω−1 = E [f (x, θ)f (x, θ)⊺ ]

−1 −1

= E [[w(x)2 (q(x) − p)2 ]] = [Var[w(x)q(x)]] 1 = Var[w(x)q(x)] [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 =

−1

1 1 −1 ⋅ Var[w(x)q(x)] ⋅ −1

= Var[w(x)q(x)] 30

Then, GMM Var[θ̂q∣C(S) ]=

Var[w(x)q(x)] . n

Thus, σ12 = Var[w(x)q(x)]. GMM , where θ = (p, λ) and Next, we establish the variance of optimal predictor θ̂q∣C(S),A(S)

⎡w(x)(q(x) − p)⎤ ⎢ ⎥ fC(S),A(S) (x, θ) = ⎢⎢ w(x)g(x, λ) ⎥⎥ . ⎢ ⎥ λ̃ − λ ⎣ ⎦ We need to compute [G⊺ Ω−1 G]−1 . (x,θ) ] G = E [ ∂f ∂θ ⎡−w(x) ⎤ 0 ⎢ ⎥ ⎢ ∂w(x)g(x,λ) ⎥ ⎢ ⎥ =E ] 0 E[ ∂λ ⎢ ⎥ ⎢ 0 ⎥ −Id ⎣ ⎦ ⎤ ⎡−1 0 ⎥ ⎢ ⎥ ⎢ ⎥ = E ⎢ 0 E[ ∂w(x)g(x,λ) ] ∂λ ⎥ ⎢ ⎥ ⎢0 −I d ⎦ ⎣ −1

Ω−1 = E [f (x, θ)f (x, θ)⊺ ]

−1 ⎡⎡ w(x)2 (q(x) − p)2 w(x)2 (q(x) − p)g(x, λ)⊺ w(x)(q(x) − p)(λ̃ − λ)⊺ ⎤⎥⎤⎥ ⎢⎢ ⎥ ⎥ ⎢⎢ = E ⎢⎢w(x)2 g(x, λ)(q(x) − p) w(x)2 g(x, λ)g(x, λ)⊺ w(x)g(x, λ)(λ̃ − λ)⊺ ⎥⎥⎥⎥ ⎢⎢ ⊺ ⎥⎥ ⎢⎢ w(x)(λ̃ − λ)(q(x) − p) w(x)(λ̃ − λ)g(x, λ) (λ̃ − λ)(λ̃ − λ)⊺ ⎦⎦ ⎣⎣ −1 2 ⊺ ⎤ ⎡ Var[w(x)q(x)] E[w(x) (q(x) − p)g(x, λ) ] 0 ⎥ ⎢ ⎥ ⎢E[w(x)2 g(x, λ)(q(x) − p)] 2 ⊺ E[w(x) g(x, λ)g(x, λ) ] 0 ⎥ =⎢ ⎢ ⊺ ⎥ ⎥ ⎢ 0 0 E[( λ̃ − λ)( λ̃ − λ) ] ⎦ ⎣ −1

Var[w(x)q(x)] E[w(x)2 (q(x) − p)g(x, λ)⊺ ] Let U −1 = [ ] . 2 E[w(x) g(x, λ)(q(x) − p)] E[w(x)2 g(x, λ)g(x, λ)⊺ ]

Ω

−1

⎡U −1 [1, 1] ⎢ ⎢ = ⎢U −1 [2, 1] ⎢ ⎢ 0 ⎣

⎤ U −1 [1, 2] 0 ⎥ ⎥ −1 U [2, 2] 0 ⎥ ⎥ 0 E[(λ̃ − λ)(λ̃ − λ)⊺ ]−1 ⎥⎦

Putting it together, −1 0 G Ω G=[ ∂w(x)g(x,λ) ⊺ 0 E[ ] ∂λ ⊺

−1

−1 0 =[ ]⊺ 0 E[ ∂w(x)g(x,λ) ∂λ

−1 ⎡ −1 ⎤ ⎤ ⎡−1 0 0 ⎥ ⎥⎢ 0 ⎢⎢U −1 [1, 1] U −1 [1, 2] ⎥ ⎢ ∂w(x)g(x,λ) ⎥ 0 ⎥ ⎢ 0 E[ ⎥ ] ⎢U [2, 1] U [2, 2] ] ∂λ ⎢ ⎥ −Id ⎢⎢ ⊺ −1 ⎥ ⎥ ⎥⎢ 0 −I 0 0 E[( λ̃ − λ)( λ̃ − λ) ] d ⎣ ⎦ ⎦⎣ ∂w(x)g(x,λ) ⎡−U −1 [1, 1] U −1 [1, 2]E[ ⎤ ]⎥ ∂λ 0 ⎢⎢ −1 ⎥ ] ⎢−U [2, 1] U −1 [2, 2]E[ ∂w(x)g(x,λ) ]⎥⎥ ∂λ −Id ⎢⎢ 0 −E[(λ̃ − λ)(λ̃ − λ)⊺ ]−1 ⎥⎦ ⎣

U −1 [1, 1] =[ ∂w(x)g(x,λ) ⊺ −1 −E[ ] U [2, 1] ∂λ

−U −1 [1, 2]E[ ∂w(x)g(x,λ) ] ∂λ ] ∂w(x)g(x,λ) ⊺ −1 E[ ∂w(x)g(x,λ) ] U [2, 2]E[ ] + E[( λ̃ − λ)(λ̃ − λ)⊺ ]−1 ∂λ ∂λ

U −1 [1, 1] =[ ∂w(x)g(x,λ) ⊺ −1 −E[ ] U [2, 1] ∂λ

−U −1 [1, 2]E[ ∂w(x)g(x,λ) ] ∂λ ] ∂w(x)g(x,λ) ⊺ −1 ∂w(x)g(x,λ) E[ ] U [2, 2]E[ ] + Var[∆]−1 ∂λ ∂λ

A Using Schur’s complement, we can compute the entries of U −1 . Let U = [ C U −1 [1, 1] = (A − BD−1 C)−1 31

B ], then D

1 Var[w(x)q(x)] − E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)]

U −1 [1, 2] = −(A − BD−1 C)−1 BD−1 = −U −1 [1, 1] ⋅ E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 U −1 [2, 1] = −D−1 C(A − BD−1 C)−1 = −U −1 [1, 1] ⋅ E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)] U −1 [2, 2] = D−1 + D−1 C(A − BD−1 C)−1 BD−1

= E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 + (U −1 [1, 1]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)] ⋅ E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 ). A The [1, 1] entry of [G⊺ Ω−1 G]−1 characterizes the variance of p̂. For a matrix M = [ C M −1 [1, 1] = A−1 + A−1 B(D − CA−1 B)−1 CA−1 , using Schur’s complement. [G⊺ Ω−1 G]−1 [1, 1] =

1 U −1 [1, 1]

⊺

1 U −1 [1, 1]2

+ Var[∆]−1 −

B ], D

] (E [ ∂w(x)g(x,λ) ] U −1 [2, 2]E [ ∂w(x)g(x,λ) ] U −1 [1, 2]E [ ∂w(x)g(x,λ) ∂λ ∂λ ∂λ

⊺ 1 E [ ∂w(x)g(x,λ) ] U −1 [2, 1]U −1 [1, 2]E [ ∂w(x)g(x,λ) ]) ∂λ ∂λ −1 U [1, 1]

−1

⊺

⋅ E [ ∂w(x)g(x,λ) ] U −1 [2, 1] ∂λ =

1 1 + ⋅ U −1 [1, 2]E [ ∂w(x)g(x,λ) ] ∂λ U −1 [1, 1] U −1 [1, 1]2 ⊺

⋅ (E [ ∂w(x)g(x,λ) ] E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E [ ∂w(x)g(x,λ) ] + Var[∆]−1 ) ∂λ ∂λ

−1

⊺

⋅ E [ ∂w(x)g(x,λ) ] U −1 [2, 1] ∂λ =

1 + E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E [ ∂w(x)g(x,λ) ] ∂λ U −1 [1, 1] −1

⊺

⋅ (E [ ∂w(x)g(x,λ) ] E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ] + Var[∆]−1 ) ∂λ ∂λ ⊺

⋅ E [ ∂w(x)g(x,λ) ] E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)] ∂λ 1 + Var[w(x)q(x)] ⋅ c0 (w, q, g, ∆) U −1 [1, 1] = Var[w(x)q(x)] =

− E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)] + Var[w(x)q(x)] ⋅ c0 (w, q, g, ∆) where c0 (w, q, g, ∆) =

1 ⋅ E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E [ ∂w(x)g(x,λ) ] ∂λ Var[w(x)q(x)] ⊺

⋅ (E [ ∂w(x)g(x,λ) ] E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E [ ∂w(x)g(x,λ) ] + Var[∆]−1 ) ∂λ ∂λ

−1

⊺

⋅ E [ ∂w(x)g(x,λ) ] E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)]. ∂λ Recall from Definition 3.5, ρcc (w(x)q(x), w(x)g(x, λ)) = max ρ(w(x)q(x), c⊺ w(x)g(x, λ)) c∈Rd

= max √ c∈Rd

Cov(w(x)q(x), c⊺ w(x)g(x, λ)) Var[w(x)q(x)] ⋅ Var[c⊺ w(x)g(x, λ)] c⊺ Cov(w(x)q(x), w(x)g(x, λ)) Var[w(x)q(x)] ⋅ c⊺ Cov(w(x)g(x, λ), w(x)g(x, λ))c 32

Squaring the objective, c⊺ Cov(w(x)g(x, λ), w(x)q(x))Cov(w(x)g(x, λ), w(x)q(x))⊺ c Var[q(x)] ⋅ c⊺ Cov(w(x)g(x, λ), w(x)g(x, λ))c c∈Rd

ρcc (w(x)q(x), w(x)g(x, λ))2 = max

This is a generalized Rayleigh quotient with solution ρcc (w(x)q(x), w(x)g(x, λ))2 Cov(w(x)g(x, λ), w(x)q(x))⊺ Cov(w(x)g(x, λ), w(x)g(x, λ))−1 Cov(w(x)g(x, λ), w(x)q(x)) Var[w(x)q(x)] E[w(x)2 (q(x) − p)g(x, λ)⊺ ]E[w(x)2 g(x, λ)g(x, λ)⊺ ]−1 E[w(x)2 (q(x) − p)g(x, λ)] . = Var[w(x)q(x)]

Thus, [G⊺ Ω−1 G]−1 [1, 1] = Var[w(x)q(x)] − Var[w(x)q(x)] ⋅ ρcc (w(x)q(x), w(x)g(x, λ))2 + Var[w(x)q(x)] ⋅ c0 (w, q, g, ∆) = Var[w(x)q(x)] ⋅ (1 − ρcc (q(x), g(x, λ))2 + c0 (w, q, g, ∆)) Then, GMM Var[θ̂q∣C(S),A(S) ]=

Var[w(x)q(x)](1 − ρcc (w(x)q(x), w(x)g(x, λ))2 + c0 (w, q, g, ∆)) . n

Thus, σ22 = Var[w(x)q(x)](1 − ρcc (w(x)q(x), w(x)g(x, λ))2 + c0 (w, q, g, ∆)). √ √ √ σ1 σ12 − σ22 = Var[w(x)q(x)] ⋅ Var[w(x)q(x)] − Var[w(x)q(x)](1 − ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆)) √ √ = Var[w(x)q(x)] ⋅ Var[w(x)q(x)](ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆)) √ = Var[w(x)q(x)] ⋅ ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆) Plugging in the above into the predictability bound, √ H(1 + log(4)) ⋅ Var[w(x)q(x)] ⋅ ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆) γ≤ n

Theorem A.1 follows analogously by plugging in w′ (x)(q(x) − p) in place of w(x)(q(x) − p) is the proof above. Theorem A.19. Let S be a dataset of size N and let C(S) be random sample without replacement of size n = αN , 0 < α < 1. For any dataset S, given moment conditions fK(S) (x, θ), the optimal GMM predictor θ̂q∣K(S) of pS∖C(S) = Ex∼Unif(S∖C(S)) [q(x)] has asymptotic distribution √ GMM (1 − α)αN (θ̂q∣K(S) − θ0 ) ∼ N (0, [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1). Proof. The optimal predictor θ̂ GMM of p = EUnif(S) [q(x)] is √ αN GMM (θ̂ − θ0 ) ∼ N (0, [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 ), 1−α by plugging in n = αN and n appropriately into Theorem A.16. For any fixed sample C(S), an estimate for p implies an estimate for pS∖C(S) using a simple 1 translation and scaling, p = (1−α)pS∖C(S) +αEx∼Unif(C(S)) [q(x)]. Var[p̂S∖C(S) ] = (1−α) 2 ⋅Var[p̂].

GMM Thus, the optimal predictor θ̂q∣K(S) of pS∖C(S) = EUnif(S∖C(S)) [q(x)] is √ GMM (1 − α)αN (θ̂q∣K(S) − θ0 ) ∼ N (0, [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 ).

Corollary 3.8. Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). √ As n, N → ∞, n/N → α, for a convex, H-smooth ℓ, γ(PRS , q, ℓ, A) ≤ H(1+log(4)) ⋅ Var[q(x)] ⋅ ρcc (q(x), g(x, λ))2 − c0 (1, q, g, ∆). (1−α)αN Proof. We would like to find the efficient GMM estimator for pS∖C(S) = Ex∼Unif(S∖C(S)) [q(xi )]. Typical GMM for sampling without replacement finds the efficient estimator for pS = Ex∼Unif(S) [q(xi )]. We find that the efficient GMM estimator for pS implies an efficient GMM GMM estimator for pS∖C(S) . We use Theorem A.19 to find the efficient estimator θ̂q∣K(S) for pS∖C(S) . Theorem A.19 essentially performs a finite sample correction for estimation. From Theorem A.19, we have GMM Var[θ̂q∣C(S) ]=

σ1 (1 − α)αN

and GMM Var[θ̂q∣C(S),A(S) ]=

σ2 . (1 − α)αN

Following the proof of Theorem 3.6, we have σ12 = Var[w(x)q(x)], σ22 = Var[w(x)q(x)](1 − ρcc (w(x)q(x), w(x)g(x, λ))2 + c0 (w, q, g, ∆)), and √ √ σ1 σ12 − σ22 = Var[w(x)q(x)] ⋅ ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆) We plug in w(x) = 1 to get √ √ σ1 σ12 − σ22 = Var[q(x)] ⋅ ρcc (q(x), g(x, λ))2 − c0 (1, q, g, ∆) Thus, we have

√ H(1 + log(4)) ⋅ Var[q(x)] ⋅ ρcc (q(x), g(x, λ))2 − c0 (1, q, g, ∆) γ≤ (1 − α)αN

A.8 A.8.1

Proofs from Section 4 Theorem 4.1, Private Dataset Statistics

Theorem 4.1. Let A(S) = λ̃ = N1 ∑N = Γ(x) − λ. For a i=1 Γ(xi ) + ∆, ∆ ∼ N (0, Σ∆ ). Let g(x, λ) √ Var[Γ(x)] H(1+log(4)) . convex, H-smooth ℓ, γ(PRS , q, ℓ, A) = (1−α)αN ⋅ Var[q(x)] ⋅ ρ(q(x), Γ(x)) ⋅ Var[Γ(x)]+Σ ∆ Proof. From Corollary 3.8, we know c0 (1, q, g, ∆) =

1 ⋅ E[(q(x) − p)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ] ∂λ Var[q(x)] ⋅ (E [ ∂g(x,λ) ] ∂λ

⊺

⊺ −1

E[g(x, λ)g(x, λ) ]

E [ ∂g(x,λ) ] + Var[∆]−1 ) ∂λ

−1

⊺

] E[g(x, λ)g(x, λ)⊺ ]−1 E[(q(x) − p)g(x, λ)]. ⋅ E [ ∂g(x,λ) ∂λ When g(x, λ) = Γ(x) − λ, E [ ∂g(x,λ) ] = 1. Also notice that E[g(x, λ)g(x, λ)⊺ ] = E[(Γ(x) − ∂λ ⊺ λ)(Γ(x) − λ) ] = Var[Γ(x)]. Thus, c0 (1, q, g, ∆) =

1 −1 ⋅ E[(q(x) − p)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 (E[g(x, λ)g(x, λ)⊺ ]−1 + Var[∆]−1 ) Var[q(x)] ⋅ E[g(x, λ)g(x, λ)⊺ ]−1 E[(q(x) − p)g(x, λ)] 34

1 −1 ⋅ E[(q(x) − p)g(x, λ)⊺ ]Var[Γ(x)]−1 (Var[Γ(x)]−1 + Var[∆]−1 ) Var[Γ(x)]−1 Var[q(x)] ⋅ E[(q(x) − p)g(x, λ)]

1 1 1 1 ⋅ E[(q(x) − p)g(x, λ)⊺ ] ⋅ ( + ) Var[q(x)] Var[Γ(x)] Var[Γ(x)] Var[∆] ⋅ E[(q(x) − p)g(x, λ)]

1 Var[Γ(x)] + Var[∆] 1 ⋅ E[(q(x) − p)g(x, λ)⊺ ] ⋅ ( ) Var[q(x)] Var[Γ(x)] Var[Γ(x)]Var[∆] ⋅ E[(q(x) − p)g(x, λ)]

−1

1 Var[Γ(x)] 1 Var[Γ(x)]

1 1 Var[Γ(x)]Var[∆] 1 ⋅ E[(q(x) − p)g(x, λ)⊺ ] ⋅ ( ) ⋅ E[(q(x) − p)g(x, λ)] Var[q(x)] Var[Γ(x)] Var[Γ(x)] + Var[∆] Var[Γ(x)]

1 1 Var[∆] ⋅ E[(q(x) − p)g(x, λ)⊺ ] ⋅ ( ) E[(q(x) − p)g(x, λ)] Var[q(x)] Var[Γ(x)] Var[Γ(x)] + Var[∆] Cov(q(x) − p, g(x, λ)) Var[∆] = ⋅ Var[q(x)]Var[Γ(x)] Var[Γ(x)] + Var[∆] Var[∆] Cov(q(x), Γ(x)) = ⋅ Var[q(x)]Var[Γ(x)] Var[Γ(x)] + Var[∆] Var[∆] = ρ(q(x), Γ(x))2 ⋅ Var[Γ(x)] + Var[∆] =

= ρ(q(x), Γ(x))2 ⋅ (1 −

Var[Γ(x)] ) Var[Γ(x)] + Var[∆]

Plugging the above into Corollary 3.8 along with ρcc (q(x), g(x, λ))2 = ρ(q(x), Γ(x))2 , √ Var[Γ(x)] ) H(1 + log(4)) ⋅ Var[q(x)] ⋅ ρ(q(x), Γ(x))2 − ρ(q(x), Γ(x))2 ⋅ (1 − Var[Γ(x)]+Var[∆] γ= (1 − α)αN √ Var[Γ(x)] H(1 + log(4)) ⋅ Var[q(x)] ⋅ ρ(q(x), Γ(x))2 ⋅ Var[Γ(x)]+Var[∆] = (1 − α)αN √ Var[Γ(x)] H(1 + log(4)) ⋅ Var[q(x)] ⋅ ρ(q(x), Γ(x)) ⋅ Var[Γ(x)]+Var[∆] = (1 − α)αN

A.8.2

Theorem 4.2, Private ERM

2 Theorem 4.2. Let wERM = arg minw N1 ∑N i=1 ℓ(zi , w), ℓ strictly convex and E[∇ ℓ(z, wERM )] positive definite. Let A(S) = w̃ = wERM + ∆, ∆ ∼ N (0, Σ∆ ). Let√g(z, wERM ) = ∇ℓ(z, wERM ). For a convex, H-smooth ℓ, γ(PRS , q, ℓ, A) ≤ H(1+log(4)) ⋅ Var[q(z)] ⋅ ρcc (q(z), g(z, wERM ))2 − c0 (w, q, g, ∆). (1−α)αN

Proof. The result directly follows by plugging in g(z, wERM ) = ∇ℓ(z, wERM ) = ∇z into Corollary 3.8 with E [ ∂g(x,λ) ] = ∇2 ℓ(x, wERM ) = Hz . ∂λ 1 In particular, c0 (1, q, g, ∆) = Var[q(z)] ⋅ E[(q(x) − p)∇⊺z ]E[∇z ∇⊺z ]−1 E[Hz ](E[Hz ]E[∇z ∇⊺z ]−1 −1 −1 ⊺ −1 E[Hz ] + Var[∆] ) E[Hz ]E[∇z ∇z ] E[(q(x) − p)∇z ]

A.8.3

Lemma 4.3, Calibrated Noise Scheme

Lemma 4.3. Let ∇z = ∇ℓ(z, wERM ) and Hz = ∇2 ℓ(z, wERM ). Let A(S) = w̃ = wERM + ∆, ∆ ∼ N (0, σ 2 E[w(x)Hz ]−1 E[w(x)2 ∇z ∇⊺z ]E[w(x)Hz ]−1 ), where the expectation is taken with respect to the stationary distribution of process P. For a convex, √ H(1+log(4)) 1 ′ ′ ′ H-smooth ℓ, γ(P, q, ℓ, A) ≤ (1−α)αN ⋅ Var[q ] ⋅ ρcc (q , g ) ⋅ σ2 +1 . Proof. Let A = E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ]. Then −1

c0 (w, q, g, ∆) = E[w(z)2 (q(z) − p)∇⊺z ]E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ] (A + E[(w̃ − wERM )(w̃ − wERM )⊺ ]−1 ) ⋅ E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)2 (q(z) − p)∇z ] and E[(w̃ − wERM )(w̃ − wERM )⊺ ]−1 =

1 ⋅A σ2

Plugging in E[(w̃ − wERM )(w̃ − wERM )⊺ ]−1 , we have c0 (1, q, g, ∆) =

−1 1 1 ⋅ E[w(z)2 (q(z) − p)∇⊺z ]E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ] (A + 2 ⋅ A) Var[w(z)q(z)] σ

⋅ E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)2 (q(z) − p)∇z ] =

−1 1 1 ⋅ E[w(z)2 (q(z) − p)∇⊺z ]E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ] ((1 + 2 ) A) Var[w(z)q(z)] σ

⋅ E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)2 (q(z) − p)∇z ] 1 1 ⋅ ⋅ E[w(z)2 (q(z) − p)∇⊺z ]E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ]A−1 = Var[w(z)q(z)] 1 + σ12 ⋅ E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)2 (q(z) − p)∇z ] =

1 σ2 ⋅ 2 ⋅ E[w(z)2 (q(z) − p)∇⊺z ]E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)Hz ]E[w(z)Hz ]−1 Var[w(z)q(z)] σ + 1 ⋅ E[w(z)2 ∇z ∇⊺z ][E[w(z)Hz ]⊺ ]−1 E[w(z)Hz ]⊺ E[w(z)2 ∇z ∇⊺z ]−1 E[w(z)2 (q(z) − p)∇z ]

σ2 1 ⋅ 2 ⋅ E[w(z)2 (q(z) − p)∇⊺z ]E[[w(z)2 ∇z ∇⊺z ]−1 E[[w(z)2 (q(z) − p)∇z ] Var[w(z)q(z)] σ + 1 σ2 = 2 ⋅ ρcc (q ′ , g ′ )2 σ +1 =

Plugging in c0 (1, q, g, ∆) to the predictability bound from Theorem 3.6, H(1 + log(4)) ⋅ Var[q ′ ] √ ⋅ (ρcc (q ′ , g ′ )2 − c0 (1, q, g, ∆)) (1 − α)αN √ H(1 + log(4)) ⋅ Var[q ′ ] σ2 = ⋅ ρcc (q ′ , g ′ )2 − 2 ⋅ ρcc (q ′ , g ′ )2 (1 − α)αN σ +1 √ H(1 + log(4)) ⋅ Var[q ′ ] ρcc (q ′ , g ′ )2 = ⋅ . (1 − α)αN σ2 + 1

γ=

⊺ Theorem 4.4. Let w̃ = wERM + ∆, ∆ ∼ N (0, σ 2 ⋅ E[xx⊺ ]−1 E[(wERM x − y)2 xx⊺ ]E[xx⊺ ]−1 ). Then

σ 2 (maxi ∥xi ∥2 ) 1 N ⊺ ⊺ 2 ⋅ L̂S (wERM ), σ 2 d ⋅ L̂max (wERM )}. ∑(w̃ xi − wERM xi ) ] ≤ min { S N i=1 λmin (E[xx⊺ ])

⊺ 2 max ⊺ 2 where L̂S (wERM ) = N1 ∑N i=1 (wERM xi − yi ) and L̂S (wERM ) = maxi (wERM xi − yi ) .

Proof. E[

1 N ⊺ 1 N ⊺ 2 ⊺ 2 ∑(w̃ xi − wERM xi ) ] = E [ ∑(∆ xi ) ] N i=1 N i=1 = E[

1 N ⊺ ⊺ ∑ ∆ xi xi ∆] N i=1

= E [∆⊺ E[xx⊺ ]∆] = E [tr(∆⊺ E[xx⊺ ]∆)] = E [tr(E[xx⊺ ]∆∆⊺ )] = tr(E[xx⊺ ] ⋅ E[∆∆⊺ ]) ⊺ = tr(E[xx⊺ ] ⋅ σ 2 E[xx⊺ ]−1 E[(wERM x − y)2 xx⊺ ]E[xx⊺ ]−1 ) ⊺ = σ 2 ⋅ tr(E[(wERM x − y)2 xx⊺ ]E[xx⊺ ]−1 ) ⊺ = σ 2 ⋅ E [tr((wERM x − y)2 xx⊺ E[xx⊺ ]−1 )] ⊺ = σ 2 ⋅ E [(wERM x − y)2 ⋅ tr(xx⊺ E[xx⊺ ]−1 )] ⊺ = σ 2 ⋅ E [(wERM x − y)2 ⋅ tr(x⊺ E[xx⊺ ]−1 x)] ⊺ = σ 2 ⋅ E [(wERM x − y)2 ⋅ x⊺ E[xx⊺ ]−1 x]

From here, we establish two upper bounds. First, we establish an upper bound based on the average empirical loss. E[

1 N ⊺ ⊺ 2 2 ⊺ 2 ⊺ ⊺ −1 ∑(w̃ xi − wERM xi ) ] = σ ⋅ E [(wERM x − y) ⋅ x E[xx ] x] N i=1 ⊺ ≤ σ 2 ⋅ E [(wERM x − y)2 ⋅

∥x∥2 ] λmin (E[xx⊺ ])

⊺ ≤ σ 2 ⋅ E [(wERM x − y)2 ⋅

maxi ∥xi ∥2 ] λmin (E[xx⊺ ])

≤

σ 2 ⋅ (maxi ∥xi ∥2 ) ⊺ ⋅ E[(wERM x − y)2 ] λmin (E[xx⊺ ])

1 N ⊺ σ 2 ⋅ (maxi ∥xi ∥2 ) 2 ⋅ ( ∑(w xi − yi ) ) λmin (E[xx⊺ ]) N i=1 ERM

Next, we establish an upper bound based on the maximum empirical loss. E[

1 N ⊺ ⊺ 2 2 ⊺ 2 ⊺ ⊺ −1 ∑(w̃ xi − ŵ xi ) ] = σ ⋅ E [(ŵ x − y) ⋅ x E[xx ] x] N i=1 ≤ (max(ŵ⊺ xi − yi )2 ) ⋅ σ 2 ⋅ E [x⊺ E[xx⊺ ]−1 x] i

= (max(ŵ⊺ xi − yi )2 ) ⋅ σ 2 ⋅ E [tr(E[xx⊺ ]−1 xx⊺ )] i

= (max(ŵ⊺ xi − yi )2 ) ⋅ σ 2 ⋅ tr(E[xx⊺ ]−1 E[xx⊺ ]) i

= (max(ŵ⊺ xi − yi )2 ) ⋅ σ 2 ⋅ tr(Id ) i

= (max(ŵ⊺ xi − yi )2 ) ⋅ σ 2 ⋅ d i

N ⊺ ⊺ 2 2 1 2 Lemma 4.5. When ∆ ∼ N (0, σ 2 Id ), E [ N1 ∑N i=1 (w̃ xi − wERM xi ) ] = σ ( N ∑i=1 ∥xi ∥ ).

Proof. E[

A.9

1 N ⊺ 1 N ⊺ 2 ⊺ 2 ∑(w̃ xi − wERM xi ) ] = E [ ∑(∆ xi ) ] N i=1 N i=1 = E[

1 N ⊺ ⊺ ∑ ∆ xi xi ∆] N i=1

= E[

1 N ⊺ ⊺ ∑ tr(∆ xi xi ∆)] N i=1

= E[

1 N ⊺ ⊺ ∑ tr(∆∆ xi xi )] N i=1

1 N ⊺ ⊺ ∑ tr(E[∆∆ ] ⋅ xi xi ) N i=1

1 N 2 ⊺ ∑ tr(σ Id ⋅ xi xi ) N i=1

= σ2 ⋅ (

1 N ⊺ ∑ tr(xi xi )) N i=1

= σ2 ⋅ (

1 N ⊺ ∑ tr(xi xi )) N i=1

= σ2 ⋅ (

1 N 2 ∑ ∥xi ∥ ) N i=1

Proofs from Section 5

A.9.1

Theorem 5.1, Finite Family of Queries and Processes

Theorem 5.1. Let A(S) = λ̃ = λ + ∆, ∆ = N (0, Σ∆ ). For a family P satisfying Assumption 3.1 and a convex, H-smooth ℓ, the worst-case predictability is supP∈P γ(P, Q, ℓ, A) ≤

√ H(1 + log(4∣Q∣∣WP ∣)) sup sup Var[w(x)q(x)] ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (w, q, g, ∆). n w∈WP q∈Q

GMM Proof. Let n = (1 − α)αN . For a weight w ∈ WP and query q ∈ Q, let Xw,q = ℓ(θ̂q∣C(S) )− GMM ℓ(θ̂q∣C(S),A(S) ). From Theorem 3.6, we know

√ ⎡ ⎤ 2 2 ⎢ ⎥ H log(4/δ) ⋅ σ σw,q,1 − σw,q,2 w,q,1 ⎢ ⎥ ⎥ ≤ δ. Pr⎢Xw,q > ⎢ ⎥ n ⎢ ⎥ ⎣ ⎦ Furthermore, every Xw,q satisfies √ ⎡ ⎤ 2 2 ⎢ ⎥ − σw,q,2 H log(4/δ) ⋅ supq∈Q supw∈WP σw,q,1 σw,q,1 ⎥ ⎢ ⎥ ≤ δ. ⎢ Pr Xw,q > ⎥ ⎢ n ⎥ ⎢ ⎦ ⎣ Let Y = supq∈Q supw∈WP Xw,q . Then, using a union bound, with probability at least 1 − δ, √ ⎤ ⎡ 2 2 ⎥ ⎢ σw,q,1 − σw,q,2 H log(4∣Q∣∣W ∣/δ) ⋅ sup sup σ P w,q,1 q∈Q w∈W P ⎢ ⎥ ⎥ ≤ δ. Pr⎢Y > ⎥ ⎢ n ⎥ ⎢ ⎦ ⎣ Now, consider E[Y ]. Thus, using standard techniques to integrate the tail, we can convert the highprobability bound into a bound on the expectation, yielding the final predictability bound. Following 38

the proof from Theorem 3.6, we can conclude that E[Y ] ≤

H(1 + log(4∣Q∣∣WP ∣)) ⋅ supq∈Q σw,q,1

√ 2 2 σw,q,1 − σw,q,2

where n = (1 − α)αN . From Theorem 3.6, we have that 2 σw,q,1 = Var[w(x)q(x)], 2 2 σw,q,1 − σw,q,2 = Var[w(x)q(x)] ⋅

√

ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (1, q, g, ∆)

Thus, we can conclude that E[Y ] ≤

H(1 + log(4∣Q∣∣WP ∣)) ⋅ supq∈Q Var[q(x)] ⋅

√

ρcc (w(x)q(x), w(x)g(x, λ))2 − c0 (1, q, g, ∆)

Lastly, note that sup γ(P, Q, ℓ, A) ≤ E[Y ]

P∈P

by pulling out the supremum using Jensen’s inequality. A.9.2

Theorem 5.2, Linear Queries

Definition A.20 (Gaussian Complexity [6]). Let ξ ∼ N (0, Id ). The Gaussian complexity of a set K is defined as G(K) = E [supu∈K ⟨u, ξ⟩]. Theorem A.21. Let query family Qlin = {q(x) = u⊺ x ∣ u ∈ Ulin ⊆ Rd }. Let diameter DΣ (K) = supu∈K u⊺ Σu. Let Ulin,Σ = {Σ1/2 u ∣ u ∈ Ulin }. Using moment conditions fC(S) (x, θ) = [x − µ] and fC(S),A(S) (x, θ) = [x − µ, g(x, λ), λ̃ − λ]⊺ ,

(3)

we have √ √ GMM GMM (1 − α)αN (θ̂x∣C(S) − µ) ∼ N (0, Σ1 ) and (1 − α)αN (θ̂x∣C(S),A(S) − µ) ∼ N (0, Σ2 ) where Σ1 = Var[x], Σ2 = Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] − c0 (1, x, g, ∆). and

c0 (1, x, g, ∆)

E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ] (E [ ∂g(x,λ) ] ∂λ ∂λ −1

∂g(x,λ) ⊺ −1 ⊺ ] + Σ−1 E[g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ∆ ) E [ ∂λ ] E[g(x, λ)g(x, λ) ] E[g(x, λ)(x − µ) ]. ∂λ

The predictability of an algorithm A with respect to Qlin under a convex, H-smooth loss ℓ is γ≤

√ √ H (G(Ulin,Σ1 ) + 2(1 + log(2)) ⋅ DΣ1 (Ulin )) (G(Ulin,Σ1 −Σ2 ) + 2(1 + log(2)) ⋅ DΣ1 −Σ2 (Ulin )) . (1 − α)αN

GMM GMM Proof. For each u ∈ Ulin , θ̂u∣C(S) estimates E[u⊺ x ∣ C(S)] and θ̂u∣C(S),A(S) estimates GMM GMM E[u⊺ x ∣ C(S), A(S)]. Consider θ̂x∣C(S) which estimates E[x ∣ C(S)] and θ̂x∣C(S),A(S) estimates E[x ∣ C(S), A(S)]. GMM GMM We want to bound supu∈Ulin ℓ(θ̂u∣C(S) ) − ℓ(θ̂u∣C(S),A(S) ) where ℓ is the expected log loss. GMM GMM GMM GMM GMM sup ℓ(θ̂u∣C(S) ) − ℓ(θ̂u∣C(S),A(S) ) ≤ sup H ⋅ ∣θ̂u∣C(S) − θ0u ∣ ⋅ ∣θ̂u∣C(S) − θ̂u∣C(S),A(S) ∣

u∈Ulin

GMM GMM GMM − µ)∣ ⋅ ∣u⊺ (θ̂x∣C(S) − θ̂x∣C(S),A(S) )∣ = sup H ⋅ ∣u⊺ (θ̂x∣C(S)

u∈Ulin

√ √ GMM GMM − µ) ∼ N (0, Σ1 ), n(θ̂x∣C(S),A(S) − µ) ∼ From GMM and Theorem 3.4, we know that n(θ̂x∣C(S) √ GMM GMM N (0, Σ2 ), and n(θ̂x∣C(S) − θ̂x∣C(S),A(S) ) ∼ N (0, Σ1 − Σ2 ), n = (1 − α)αN . Using Theorem A.23, GMM GMM GMM we can bound the ∣u⊺ (θ̂x∣C(S) − µ)∣ and ∣u⊺ (θ̂x∣C(S) − θ̂x∣C(S),A(S) )∣ with high probability. Thus, with probability at least 1 − δ, GMM GMM GMM GMM GMM sup ℓ(θ̂u∣C(S) ) − ℓ(θ̂u∣C(S),A(S) ) ≤ sup H ⋅ ∣u⊺ (θ̂x∣C(S) − µ)∣ ⋅ ∣u⊺ (θ̂x∣C(S) − θ̂x∣C(S),A(S) )∣

u∈Ulin

√ H ⋅ (G(Ulin,Σ1 ) + 2 log(2/δ) ⋅ sup u⊺ Σ1 u) n u∈Ulin √ ⋅ (G(Ulin,Σ1 −Σ2 ) + 2 log(2/δ) ⋅ sup u⊺ (Σ1 − Σ2 )u)

≤

√

u∈Ulin

H ⋅ (G(Ulin,Σ1 ) + 2 log(2/δ) ⋅ DΣ1 (Ulin )) n √ ⋅ (G(Ulin,Σ1 −Σ2 ) + 2 log(2/δ) ⋅ DΣ1 −Σ2 (Ulin )) .

GMM GMM Let X = supu∈Ulin ℓ(θ̂u∣C(S) ) − ℓ(θ̂u∣C(S),A(S) ). Note that predictability is γ = E[X]. Thus, using standard techniques to integrate the tail, we can convert the high-probability bound into a bound on the expectation, yielding the final predictability bound. Let G1 = G(Ulin,Σ1 ), G2 = G(Ulin,Σ1 −Σ2 ), D1 = DΣ1 (Ulin ), and D2 = DΣ1 −Σ2 (Ulin ). We know √ √ H Pr[X > ⋅ (G1 + 2 log(2/δ) ⋅ D1 ) ⋅ (G2 + 2 log(2/δ) ⋅ D2 )] ≤ δ. n Let u = log(2/δ), then √ √ H Pr[X > ⋅ (G1 + 2D1 u) ⋅ (G2 + 2D2 u)] ≤ 2e−u n Pr[X > f (u)] ≤ 2e−u

Let t0 = f (log(2)). Thus, E[X] ≤ ∫

t0 0

1dt + ∫

= t0 + ∫

∞ t0

Pr[X > t]

= f (log(2)) + ∫ = f (log(2)) + ∫

∞ log(2) ∞ log(2)

Pr[X > f (u)]f ′ (u)du 2e−u f ′ (u)du

= f (log(2)) − f (log(2)) + ∫ =∫ =∫

∞

log(2)

2e−u f (u)du

log(2) ∞ −u′

∞

f (u′ + log(2))du

(u′ = u − log(2))

= E[f (β + log(2))] (β ∼ Exp(1)) √ √ √ H ⋅ (G1 G2 + G1 E [ 2D2 (β + log(2))] + G2 E [ 2D1 (β + log(2))] + 2 D1 D2 ⋅ E [β + log(2))]) = n √ √ √ H = ⋅ (G1 G2 + G1 2D2 (1 + log(2)) + G2 2D1 (1 + log(2))] + 2 D1 D2 (1 + log(2))) n (Jensen’s inequality and E[β] = 1) √ √ H = ⋅ (G1 + 2D1 (1 + log(2))) ⋅ (G2 + 2D2 (1 + log(2))) n √ √ H = (G(Ulin,Σ1 ) + 2(1 + log(2)) ⋅ DΣ1 (Ulin )) (G(Ulin,Σ1 −Σ2 ) + 2(1 + log(2)) ⋅ DΣ1 −Σ2 (Ulin )) . (1 − α)αN 40

The exact form of Σ1 and Σ2 are described in Theorem A.22. Theorem A.22. Applying GMM with moment conditions ⎡ x−µ ⎤ ⎢ ⎥ fC(S) (x, θ) = [x − µ] and fC(S),A(S) (x, θ) = ⎢⎢g(x, λ)⎥⎥ , ⎢ λ̃ − λ ⎥ ⎣ ⎦ √ √ GMM GMM − µ) ∼ N (0, Σ1 ), n(θ̂x∣C(S),A(S) − µ) ∼ N (0, Σ2 ), where we have n(θ̂x∣C(S) Σ1 = Var[x], Σ2 = Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] + c0 (1, x, g, ∆), Σ1 − Σ2 = E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] − c0 (1, x, g, ∆) ⊺

] (E [ ∂g(x,λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ]+ where c0 (1, x, g, ∆) = E[(x−µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E [ ∂g(x,λ) ∂λ ∂λ ∂λ −1

⊺

Var[∆]−1 ) E [ ∂g(x,λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] ∂λ GMM Proof. First, we establish the variance of the optimal predictor θ̂x∣C(S) where θ = (µ) and

fC(S) (x, θ) = [x − µ] . We need to compute [G⊺ Ω−1 G]−1 . (x,θ) ] G = E [ ∂f ∂θ

= [−Id ] Ω−1 = E [f (x, θ)f (x, θ)⊺ ] = E [(x − µ)2 ]

−1

= Var[x]−1 [G(θ0 )⊺ Ω−1 (θ0 )G(θ0 )]−1 = [Id Var[x]−1 Id ]−1 = Var[q(x)] Thus, Σ1 = Var[q(x)]. GMM Next, we compute the variance of the optimal predictor θ̂x∣C(S),A(S) where θ = (µ, λ) and

⎡ x−µ ⎤ ⎢ ⎥ fC(S),A(S) (x, θ) = ⎢⎢g(x, λ)⎥⎥ . ⎢ λ̃ − λ ⎥ ⎣ ⎦ We need to compute [G⊺ Ω−1 G]−1 . (x,θ) ] G = E [ ∂f ∂θ ⎡−Id ⎤ 0 ⎢ ⎥ ⎢ ∂g(x,λ) ⎥ ⎥ =⎢ 0 ] E[ ∂λ ⎢ ⎥ ⎢ 0 ⎥ −I d ⎣ ⎦

Ω−1 = E [f (x, θ)f (x, θ)⊺ ]

−1

⎡⎡ (x − µ)2 ⎢⎢ ⎢⎢ = E ⎢⎢ g(x, λ)(x − µ)⊺ ⎢⎢ ⎢⎢(λ̃ − λ)(x − µ)⊺ ⎣⎣

(x − µ)g(x, λ)⊺ g(x, λ)g(x, λ)⊺ (λ̃ − λ)g(x, λ)⊺ 41

−1 (x − µ)(λ̃ − λ)⊺ ⎤⎥⎤⎥ ⎥ ⎥ g(x, λ)(λ̃ − λ)⊺ ⎥⎥⎥⎥ (λ̃ − λ)(λ̃ − λ)⊺ ⎥⎦⎥⎦

⎡ Var[x] ⎢ = ⎢⎢E[g(x, λ)(x − µ)⊺ ] ⎢ 0 ⎣

−1

E[(x − µ)g(x, λ)⊺ ] ] . E[g(x, λ)g(x, λ)⊺ ]

Var[x] Let U −1 = [ E[g(x, λ)(x − µ)⊺ ]

Ω

−1

⎤−1 E[(x − µ)g(x, λ)⊺ ] 0 ⎥ ⊺ ⎥ E[g(x, λ)g(x, λ) ] 0 ⎥ ⊺ ⎥ 0 E[(λ̃ − λ)(λ̃ − λ) ]⎦

⎡U −1 [1, 1] ⎢ ⎢ = ⎢U −1 [2, 1] ⎢ ⎢ 0 ⎣

⎤ U −1 [1, 2] 0 ⎥ ⎥ −1 U [2, 2] 0 ⎥ ⊺ −1 ⎥ 0 E[(λ̃ − λ)(λ̃ − λ) ] ⎥⎦

Putting it together, −Id G Ω G=[ 0

] E[ ∂g(x,λ) ∂λ

−Id =[ 0

0 ] E[ ∂g(x,λ) ∂λ

⊺

−1

−1 ⎡ −1 ⎤ ⎡−Id 0 ⎥⎢ 0 ⎢⎢U −1 [1, 1] U −1 [1, 2] ⎥⎢ 0 ⎥⎢ 0 ] ⎢U [2, 1] U [2, 2] ⎢ −Id ⎢⎢ ⊺ −1 ⎥ ⎥⎢ 0 0 0 E[( λ̃ − λ)( λ̃ − λ) ] ⎣ ⎦⎣ ⎡−U −1 [1, 1] U −1 [1, 2]E[ ∂g(x,λ) ] ⎤⎥ ∂λ 0 ⎢⎢ −1 ⎥ ∂g(x,λ) ]⎢ U −1 [2, 2]E[ ∂λ ] ⎥⎥ −Id ⎢⎢−U [2, 1] 0 −E[(λ̃ − λ)(λ̃ − λ)⊺ ]−1 ⎥⎦ ⎣

U −1 [1, 1] =[ ∂g(x,λ) −E[ ∂λ ]U −1 [2, 1] U −1 [1, 1] =[ ∂g(x,λ) −E[ ∂λ ]U −1 [2, 1]

⎤ ⎥

⎥ ]⎥⎥ E[ ∂g(x,λ) ∂λ ⎥ −Id ⎦

−U −1 [1, 2]E[ ∂g(x,λ) ] ∂λ ] ∂g(x,λ) ∂g(x,λ) −1 E[ ∂λ ]U [2, 2]E[ ∂λ ] + E[(λ̃ − λ)(λ̃ − λ)⊺ ]−1 −U −1 [1, 2]E[ ∂g(x,λ) ] ∂λ ] ∂g(x,λ) ∂g(x,λ) −1 E[ ∂λ ]U [2, 2]E[ ∂λ ] + Var[∆]−1

A Using Schur’s complement, we can compute the entries of U −1 . Let U = [ C

B ], then D

U −1 [1, 1] = (A − BD−1 C)−1 = [Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]]−1 U −1 [1, 2] = −(A − BD−1 C)−1 BD−1 = −U −1 [1, 1] ⋅ E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 U −1 [2, 1] = −D−1 C(A − BD−1 C)−1 = −U −1 [1, 1] ⋅ E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] U −1 [2, 2] = D−1 + D−1 C(A − BD−1 C)−1 BD−1 = E[g(x, λ)g(x, λ)⊺ ]−1 + U −1 [1, 1]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 . A The [1, 1] entry of [G⊺ Ω−1 G]−1 characterizes the variance of p̂. For a matrix M = [ C M −1 [1, 1] = A−1 + A−1 B(D − CA−1 B)−1 CA−1 , using Schur’s complement. [G⊺ Ω−1 G]−1 [1, 1] = [U −1 [1, 1]]−1 + U −1 [1, 1]−1 U −1 [1, 2]E [ + Var[∆]

−1

∂g(x, λ) ∂g(x, λ) ∂g(x, λ) ] (E [ ] U −1 [2, 2]E [ ] ∂λ ∂λ ∂λ −1

∂g(x, λ) ∂g(x, λ) ∂g(x, λ) − E[ ] U −1 [2, 1][U −1 [1, 1]]−1 U −1 [1, 2]E [ ]) E[ ] ∂λ ∂λ ∂λ

⋅ U −1 [2, 1][U −1 [1, 1]]−1 = [U −1 [1, 1]]−1 + [U −1 [1, 1]]−1 U −1 [1, 2]E [ ⋅ (E [ ⋅ E[

B ], D

∂g(x, λ) ] ∂λ

∂g(x, λ) ∂g(x, λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E [ ] + Var[∆]−1 ) ∂λ ∂λ

∂g(x, λ) ] U −1 [2, 1][U −1 [1, 1]]−1 ∂λ 42

−1

= [U −1 [1, 1]]−1 + E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E [ ⋅ (E [ ⋅ E[

∂g(x, λ) ] ∂λ

∂g(x, λ) ∂g(x, λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E [ ] + Var[∆]−1 ) ∂λ ∂λ

−1

∂g(x, λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] ∂λ

= [U −1 [1, 1]]−1 + c0 (1, x, g, ∆) = Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] + c0 (1, x, g, ∆) where c0 (1, x, g, ∆) = E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E [ ⋅ (E [ ⋅ E[

∂g(x, λ) ] ∂λ

∂g(x, λ) ∂g(x, λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E [ ] + Var[∆]−1 ) ∂λ ∂λ

−1

∂g(x, λ) ] E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]. ∂λ

Thus, Σ2 = Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[(x − µ)g(x, λ)] + c0 (1, x, g, ∆). Finally, we have Σ1 − Σ2 = E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[(x − µ)g(x, λ)] − c0 (1, x, g, ∆) Theorem A.23. Let ξΣ ∼ N (0, Σ). With probability at least 1 − δ, √ sup⟨u, ξΣ ⟩ ≤ G(Σ1/2 K) + 2 log(1/δ) ⋅ sup u⊺ Σu u∈K

u∈K

Proof. Start by considering GΣ (K), GΣ (K) = E [sup⟨u, ξΣ ⟩] . u∈K

Let ξ ∼ N (0, Id ). Note that ξΣ = Σ1/2 ξ. Thus, GΣ (K) = E [sup⟨u, ξΣ ⟩] u∈K

= E [sup⟨u, Σ1/2 ξ⟩] u∈K

= E [sup⟨Σ1/2 u, ξ⟩]

(since Σ1/2 is symmetric)

u∈K

⎡ ⎤ ⎢ ⎥ = E ⎢⎢ sup ⟨u′ , ξ⟩⎥⎥ ′ ⎢u ∈KΣ1/2 ⎥ ⎣ ⎦ = G(KΣ1/2 )

(KΣ1/2 = {Σ1/2 u ∣ u ∈ K})

√ Let ξ ∼ N (0, Id ). The mapping g(ξ) ∶ ξ ↦ supu∈K ⟨Σ1/2 u, ξ⟩ is Lipschitz with L = supu∈K u⊺ Σu. Thus, we can use the concentration for Lipschitz functionals of standard Gaussians (Borel-CIS inequality) to get a high probability bound. Let Z = supu∈K ⟨u, ξΣ ⟩. Then Pr[Z ≥ E[Z] + t] = Pr[Z ≥ G(Σ1/2 K) + t] ≤ e−t /2L . 2

Let δ = e−t /2L 2

t2 2L2 2 2L log(1/δ) = t2 log(1/δ) =

√

2L2 log(1/δ) = t

Thus, with probability at least 1 − δ, sup⟨u, ξΣ ⟩ ≤ G(KΣ1/2 ) +

u∈K

√ 2 log(1/δ) ⋅ sup u⊺ Σu. u∈K

We can use standard techniques to compute Gaussian complexity G(Σ1/2 Qlin ). For example, if Qlin √ 1/2 is the Euclidean ball of radius B, then G(Σ Qlin ) = B tr(Σ). If Qlin is the L1 ball of radius B, √ √ then G(Σ1/2 Qlin ) = B log d ⋅ maxi Σ[i, i]. We refer the reader to [6, 38] for more details. Theorem 5.2. Let query family Qlin = {q(x) = u⊺ x ∣ u ∈ Ulin ⊆ Rd }. If Ulin is contained within the Euclidean ball of radius B, √for a convex, H-smooth ℓ, the γ(PRS , Qlin , ℓ, A)-predictability is ≤ 4HB(2+log(2)) ⋅ tr(Var[x]) ⋅ (1−α)αN

(c0 (1,x,g,∆)) ρ1cc (x, g(x, λ))2 − λmintr(Var[x]) .

Proof. From Theorem A.21, we know that √ √ H γ≤ (G(Ulin,Σ1 ) + 2(1 + log(2)) ⋅ DΣ1 (Ulin )) (G(Ulin,Σ1 −Σ2 ) + 2(1 + log(2)) ⋅ DΣ1 −Σ2 (Ulin )) (1 − α)αN When Ulin is contained within the Euclidean ball of radius B, √ G(Ulin,Σ ) = B tr(Σ), DΣ (Ulin ) = B 2 ⋅ λmax (Σ). From Theorem A.22, Σ1 = Var[x], Σ2 = Var[x] − E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] + c0 (1, x, g, ∆), Σ1 − Σ2 = E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] − c0 (1, x, g, ∆) Then λmax (Σ1 ) = λmax (Var[x]) λmax (Σ1 − Σ2 ) = λmax (E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] − c0 (1, x, g, ∆)) ≤ λmax (E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − λmin (c0 (1, x, g, ∆)) = λmax (Var[x]Var[x]−1 E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − λmin (c0 (1, x, g, ∆)) ≤ λmax (Var[x]) ⋅ λmax (Var[x]−1 E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − λmin (c0 (1, x, g, ∆)) = λmax (Σ1 ) ⋅ ρ1cc (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) = λmax (Σ1 ) ⋅ (ρ1cc (x, g(x, λ))2 −

λmin (c0 (1, x, g, ∆)) ) λmax (Σ1 )

= λmax (Σ1 ) ⋅ (ρ1cc (x, g(x, λ))2 −

λmin (c0 (1, x, g, ∆)) ) tr(Σ1 )

Next, consider tr(Σ1 − Σ2 ) = tr(E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ] − c0 (1, x, g, ∆)) 44

= tr(E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − tr(c0 (1, x, g, ∆)) = tr(Var[x]Var[x]−1 E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − tr(c0 (1, x, g, ∆))

≤ tr(Var[x]) ⋅ λmax (Var[x]−1 E[(x − µ)g(x, λ)⊺ ]E[g(x, λ)g(x, λ)⊺ ]−1 E[g(x, λ)(x − µ)⊺ ]) − tr(c0 (1, x, g, ∆)) (Holder’s inequality for matrices) = tr(Σ1 ) ⋅ ρ1cc (x, g(x, λ))2 − tr(c0 (1, x, g, ∆)) = tr(Σ1 ) ⋅ ρ1cc (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) = tr(Σ1 ) ⋅ (ρ1cc (x, g(x, λ))2 −

λmin (c0 (1, x, g, ∆)) ) tr(Σ1 )

Thus, √ √ H ⋅ (G(Ulin,Σ1 ) + 2(1 + log(2))DΣ1 (Ulin )) ⋅ (G(Ulin,Σ1 −Σ2 ) + 2(1 + log(2))DΣ1 −Σ2 (Ulin )) n √ √ √ √ H ≤ ⋅ (B tr(Σ1 ) + B 2(1 + log(2)) ⋅ λmax (Σ1 )) (B tr(Σ1 − Σ2 ) + B 2(1 + log(2)) ⋅ λmax (Σ1 − Σ2 )) n ¿ √ ⎛Á HB √ Àtr(Σ ) ⋅ (ρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) ) ⋅ ( tr(Σ1 ) + 2(1 + log(2)) ⋅ λmax (Σ1 )) ⋅ Á ≤ 1 cc n tr(Σ1 ) ⎝ ¿ Á λmin (c0 (1, x, g, ∆)) ⎞ À2(1 + log(2)) ⋅ λ 1 2 +Á ) max (Σ1 ) ⋅ (ρcc (x, g(x, λ)) − tr(Σ1 ) ⎠ ¿ √ √ 2 HB Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) ⋅ ( tr(Σ1 ) + 2(1 + log(2)) ⋅ λmax (Σ1 )) = ⋅Á cc n tr(Σ1 ) ¿ 2HB Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) ⋅ (tr(Σ1 ) + 2(1 + log(2)) ⋅ λmax (Σ1 )) = ⋅Á cc n tr(Σ1 ) ¿ 2HB Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) (tr(Σ1 ) + 2(1 + log(2)) ⋅ tr(Σ1 )) ⋅Á ≤ cc n tr(Σ1 ) ¿ 4HB Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) ((2 + log(2)) ⋅ tr(Σ1 )) ≤ ⋅Á cc n tr(Σ1 ) ¿ 4HB(2 + log(2)) ⋅ tr(Σ1 ) Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) = ⋅Á cc n tr(Σ1 ) ¿ 4HB(2 + log(2)) ⋅ tr(Var[x]) Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) = ⋅Á cc (1 − α)αN tr(Var[x])

γ=

A.9.3

Theorem 5.4, Lipschitz Queries

Theorem 5.4. Let query family QL = {f (x) ∣ f√ is L-Lipschitz}. For a convex, H-smooth loss ℓ, (2+log(2)) γ(PRS , QL , ℓ, A) ≤ 4HL(1−α)αN ⋅ tr(Var[x]) ⋅ 2

(c0 (1,x,g,∆)) ρ1cc (x, g(x, λ))2 − λmintr(Var[x]) .

GMM Proof. We want to bound supf ∈Q ℓ(θ̂fGMM ∣C(S) ) − ℓ(θ̂f ∣C(S),A(S) ) where ℓ is the expected log loss.

f GMM GMM GMM GMM sup ℓ(θ̂fGMM ∣C(S) ) − ℓ(θ̂f ∣C(S),A(S) ) ≤ sup H ⋅ ∣θ̂f ∣C(S) − θ0 ∣ ⋅ ∣θ̂f ∣C(S) ) − θ̂f ∣C(S),A(S) ∣ f ∈Q

f ∈Q

GMM GMM GMM = sup H ⋅ ∣f (θ̂x∣C(S) ) − f (µx )∣ ⋅ ∣f (θ̂x∣C(S) ) − f (θ̂x∣C(S),A(S) )∣

f ∈Q

GMM GMM GMM = HL2 ⋅ ∥θ̂x∣C(S) − µ∥ ⋅ ∥θ̂x∣C(S) − θ̂x∣C(S),A(S) ∥

√ GMM − µ) ∼ N (0, Σ1 ), Let n = (1 − α)αn. From GMM and Theorem 3.4, we know that n(θ̂x∣C(S) √ √ GMM GMM GMM n(θ̂x∣C(S),A(S) − µ) ∼ N (0, Σ2 ), and n(θ̂x∣C(S) − θ̂x∣C(S),A(S) ) ∼ N (0, Σ1 − Σ2 ). Thus, we can use standard concentration bounds for Gaussian random variables. With probability at least 1 − δ, GMM sup ℓ(θ̂fGMM ∣C(S) ) − ℓ(θ̂f ∣C(S),A(S) )

f ∈Q

GMM GMM GMM ≤ HL2 ⋅ ∥θ̂x∣C(S) − µ∥ ⋅ ∥θ̂x∣C(S) − θ̂x∣C(S),A(S) ∥

≤

√ √ √ HL2 √ ⋅ ( tr(Σ1 ) + 2λmax (Σ1 ) log(2/δ)) ⋅ ( tr(Σ1 − Σ2 ) + 2λmax (Σ1 − Σ2 ) log(2/δ)) n

GMM Let X = supf ∈Q ℓ(θ̂fGMM ∣C(S) ) − ℓ(θ̂f ∣C(S),A(S) ). Note that predictability is γ = E[X]. Thus, using standard techniques to integrate the tail, we can convert the high-probability bound into a bound on the expectation, yielding the final predictability bound. Following the proof in Theorem A.21,

γ = E[X] ≤

√ √ √ HL2 √ ⋅ ( tr(Σ1 ) + 2λmax (Σ1 )(1 + log(2))) ⋅ ( tr(Σ1 − Σ2 ) + 2λmax (Σ1 − Σ2 )(1 + log(2))) n

We can further simplify this by following Theorem 5.2 and substituting in Σ1 and Σ2 from Theorem A.22 ¿ 4HL2 (2 + log(2)) ⋅ tr(Σ1 ) Á Àρ1 (x, g(x, λ))2 − λmin (c0 (1, x, g, ∆)) ⋅Á γ= cc (1 − α)αN tr(Σ1 )

A.10

Helpful Theorems

Theorem A.24 ([42] Chapter 3, Lemma 3.1). (G⊺ W G)−1 G⊺ W ΩW G(G⊺ W G)−1 − (G⊺ Ω−1 G)−1 is positive semidefinite. Theorem A.25 ([42] Chapter 3, Lemma 3.2). If Yn →d Y0 and f is a continuous function of an open set that contains the support of Y0 , then f (Yn ) →d f (Y0 ). Theorem A.26 ([42] Chapter 3, Lemma 3.4). If Yn (θ) →p Y0 (θ) uniformly for θ ∈ Θ ⊆ Rd , random vectors τ0 , τn ∈ Θ satisfy τn →p τ0 , and Y0 (θ) is almost surely continuous at τ0 , then Yn (τn ) →p Y0 (τ0 ).

Record · ID 290562 · SHA-256 95f29b1453f87292
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.